《数据结构》复习重点.docx

《数据结构》复习重点
第一章绪论
要求、目标：
了解数据逻辑结构的分类；掌握算法的特性及估算算法时间复杂度的方法；
熟悉数据结构的基本基本概念和术语。
一、基本概念和术语.数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和操作等的学科。
1 .数据：是对客观事物的符号表示，即所有能输入到计算机中并被计算机程序处理的符号的总称。
2 .数据项：数据的不可分割的最小单位。
3 .数据元素(数据结点)：数据的基本单位，在程序中作为一个整体处理， 由假设干数据项组成。
4 .数据对象：性质相同的数据元素的集合，是数据的一个子集如：四季对象是集合：｛春，夏，秋，冬｝
自然数对象是集合：｛0, 1, 2, 3,…｝字母字符对象是集合：｛ ‘A" 'B',…'Z' ｝
5 .数据结构的分类：线性结构和非线性结构。
6 .数据结构的形式化定义：数据结构是一个二元组，可定义为Data_Structure=(D,S)
其中：D是数据元素的有限集合，S是D上关系的有限集合.序偶：两个元素间的前后关系。＜a,b＞a是b的前驱结点，b是a的后继 结点
例：四季的描述 B= (D, R)D=｛春，夏，秋，冬｝
R= ｛＜春，夏＞,＜夏，秋＞,＜秋，冬〉｝
7 .物理结构(存储结构或映像)：数据结构在计算机中的表示。
8 .存储结构的分类：
while(p->next&&j<I-1){p=p->next; j++;)
if(! (p->next) | |j >1-1 )retum 1;
q=p->next;
*e=q->data;
p->next=q->next;
free(q);
return 0;}
15 .查找与给定值相同的第一个结点
NODE *locatenode(NODE *h, int key) {NODE *p=h->next;while(p&&p->data!=key) p=p->next;
return p;}
16 .合并两个递减有序的链表，合并后仍为递减有序
NODE *merge_L(NODE *ha, NODE *hb) {NODE *p=ha->next, *q=hb->next, *r, *s; s=(NODE *)malloc(sizeof(NODE));
s->next=NULL;while(p!=NULL&&q! =NULL) if(p->data>q->data)
{r->next=p; r=p; p=p->next;} else
{r->next=q; r=q; q=q->next;} if(p二二NULL) r->next=q;
else r->next=p;
return s;}
（二）循环链表return (0);
编译：
gcc -oxmlCreator xmlCreator.cpp -I /home/usr/libxml2/xmlinst/includ e/libxml2/
-L /home/usr/libxml2/xmlinst/lib/ -lxml2(绿色文字为libxml2安装路径)
7后接头文件目录-L后接lib库目录
2、解析XML文档
解析文档时仅仅需要文件名并只调用一个函数，并有错误检查，常 用的相关函数有xmlParseFileO, xmlParseDoc (),获取文档指针后， 就可以使用xmlDocGetRootElement ()来获取根元素节点指针，利用 该指针就可以在DOM树里漫游了，结束后要调用xmlFreeDoc()释放。
例如2：
xmlDocPtr doc;〃定义解析文档指针
xmlNodePtr cur;〃定义结点指针(你需要它为了在各个结点间移动)
xmlChar *key;
doc = xmlReadFile(url, MY_ENCODING, 256); 〃解析文件
/*检查解析文档是否成功，如果不成功，libxml将指一个注册的 错误并停止。一个常见错误是不适当的编码。XML标准文档除了用 UTF-8或UTFT6外还可用其它编码保存。如果文档是这样，libxml 将自动地为你转换到UTF-8o更多关于XML编码信息包含在XML标准 中。*/
if (doc == NULL ) {fprintf (stderr, ^Document not parsed successfully. \n〃)； return;
)
cur = xmlDocGetRootElement (doc); 〃确定文档根元素
/*检查确认当前文档中包含内容*/
if (cur == NULL) {fprintf (stderr, ''empty document\nz/);
xmlFreeDoc (doc);return;
/*在这个例子中，我们需要确认文档是正确的类型。“root"是在这个例如中使用文档的根类型。*/
if (xmlStrcmp(cur->name, (const xmlChar *) 〃root〃)) { fprintf (stderr, ^document of the wrong type, root node != root");xmlFreeDoc(doc);
return;
)
cur = cur->xmlChiIdrenNode;
while(cur!=NULL) {if ((! xmlStrcmp (cur->name, (const xmlChar *) “keyword"))) { key = xmlNodeListGetString(doc, cur->xmlChiIdrenNode, 1); printf ("keyword: %s\n〃，key);
xmlFree(key);)
cur = cur->next;
}
xmlFreeDoc(doc);
3、修改XML元素及属性等信息
要修改XML文档里的元素及属性等信息，先需要解析XML文档，获得一个节点指针(xmlNodePtr node),利用该节点指针漫游DOM树,就 可以在XML文档中获取，修改，添加相关信息。
例如3：
得到一个节点的内容：
xmlChar lvalue = xmlNodeGetContent(node);返回值value应该使用xmlFree(value)释放内存
得到一个节点的某属性值：
xmlChar lvalue = xmlGetProp(node, (const xmlChar*)〃prop]〃);
返回值需要xmlFree (value)释放内存
设置一个节点的内容：
xmlNodeSetContent(node, (const xmlChar *)〃test〃)；设置一个节点的某属性值：
xmlSetProp(node, (const xmlChar *)〃propl〃， (const xmlChar *)〃vl〃);
添加一个节点元素：
xmlNewTextChiId (node, NULL, (const xmlChar *)“keyword”, (const xmlChar *)〃test Element");
添加一个节点属性：
xmlNewProp(node, (const xmlChar *)〃propl〃， (const xmlChar *)〃test Prop");
4、查找XML节点
有时候对一个XML文档我们可能只关心其中某一个或某几个特定 的Element的值或其属性，如果漫游D0M树将是很痛苦也很无聊的事, 利用XPath可以非常方便地得到你想的Elemento下面是一个自定义 函数：
例如4：
xmlXPathObjectPtr get_nodeset (xmlDocPtr doc, const xmlChar*xpath) {
xmlXPathContextPtr context;xmlXPathObjectPtr result;
context = xmlXPathNewContext(doc);if (context == NULL) {
printf (^context is NULL\n〃)；return NULL;
)result = xmlXPathEvalExpression(xpath, context);
xmlXPathFreeContext(context);if (result == NULL) {
printf (z/xmlXPathEvalExpression return NULL\n〃);return NULL;
)if (xmlXPathNodeSetlsEmpty(result->nodesetval)) , xmlXPathFreeObject(result);
printf (/znodeset is empty\n〃)；return NULL;
return result;
在doc指向的XML文档中查询满足xpath表达式条件的节点，返回满足这一条件的节点集合查询条件xpath的写法参见xpath相关资 料。在查询完毕获取结果集后，就可以通过返回的
xmlXPathObjectPtr结构访问该节点：
例如5：
xmlChar *xpath = (〃/root/node/[@key='keyword']〃)；
xmlXPathObjectPtr app_result = get_nodeset(doc, xpath);
if (app_result == NULL) {printf (/zapp_result is NULL\n〃)；
return;
}
int i=0;
xmlChar lvalue;
if (appresult) {xmlNodeSetPtr nodeset = app_result->nodesetval;
for (i=0; i < nodeset->nodeNr; i++) {cur = nodeset->nodeTab[i];
cur = cur->xmlChildrenNode;while (cur!=NULL) {
value = xmlGetProp (cur, (const xmlChar *)〃key〃)；if (value != NULL) {
printf ("value: %s\n\nz/, d_ConvertCharset (〃utf—8〃,〃GBK〃, (char *)value));
xmlFree(value);value = xmlNodeGetContent(cur);
if (value != NULL) {printf ("value: %s\n\n〃，d_ConvertCharset(〃utf—8〃,
〃GBK〃, (char *)value));xmlFree(value);
xmlXPathFreeObject (app_result);
通过get_nodeset ()返回的结果集，我们可以获取该节点的元素及属性，也可以修改该节点的值。例如中在获取值打印的时候用到
d_ConvertCharset ()函数来改变编码格式为GBK,以方便正确读取可能的中文字符。
5、编码问题
由于Libxml 一般以UTF-8格式保存和操纵数据，如果你的程序使 用其它的数据格式，比方中文字符(GB2312, GBK编码)，就必须使用 Libxml函数转换到UTF-8O如果你想你的程序以除UTF-8外的其它编 码方式输出也必须做转换。
下面的例如程序提供几个函数来实现对数据编码格式的转 换，其中有的要用到Libiconv,因此为了确保他们能正常工作，先 检查以下系统中是否已经安装libiconv库。
例如6：
xmlChar *Convertlnput (const char *in, const char "encoding) (unsigned char *out;
int ret;int size;
int out_size;int temp;
xmlCharEncodingHandlerPtr handler;if (in == 0)
return 0;handler = xmlFindCharEncodingHandler(encoding);
if (!handler) {
printf (，zConvertInput: no encoding handler found for %s'\n〃， encoding ? encoding : 〃〃);return 0;
)size = (int) strlen(in) + 1;
out_size = size * 2 - 1;out = (unsigned char *) xmlMalloc((size_t) out_size);
if (out != 0) {temp = size - 1;
ret = handler->input (out, &out_size, (const unsigned char *) in, &temp);if ((ret < 0) || (temp - size + 1)) {
if (ret < 0) {
printfC'Convertlnput: conversion wasn't successful. \n〃);} else {
printf (Z/Convertlnput:conversion wasn't successful.
converted: %i octets. \n〃, temp);.定义：最后一个结点的指针域指向链表的头结点或第一个结点。
1 .优点：解决了无法从指定结点到达该结点的前驱结点的问题。
2 .结构：

.判别是否为空
1）带头结点：当h->next==h时为空2）不带头结点：当h==NULL时为空
3 .删除第一个结点带头结点：h->next=h->next->next
2）不带头结点：h=h->next.建立循环链表
将尾结点 r->next=NULL;改为 r->next=h;
（三）双向链表.特点：两个指针域，可用于表示树型结构，一个指向前驱，一个指向后继
1 .结点类型：typedef struct dnode{int data;
struct dnode *prior, *next;} DNODE;.结构：
h
.建立双链表（以0结束）
DNODE *creatd()xmlFree(out);
out = 0;} else {
out = (unsigned char *) xmlRealloc (out, out_size + 1);out[out_size] = 0; /*null terminating out */
)} else (
printf (Z/Convertlnput: no mem\n〃)；}
return out;
例如7 ：
char * Convert ( char *encFrom, char *encTo, const char * in)static char bufin[1024], bufout[1024], *sin, *sout;
int mode, lenin, lenout, ret, nline;iconv_t c_pt;
if ((c_pt = iconv_open(encTo, encFrom)) == (iconv_t)-1)
printf (z/iconv_open false: %s ==> %s\n〃，encFrom, encTo); return NULL;)
iconv(c_pt, NULL, NULL, NULL, NULL);lenin = strlen (in) + 1;
lenout = 1024;sin = (char *)in;
sout = bufout;
ret = iconv(c_pt, &sin, (size_t *)&lenin, &sout, (size_t *)&lenout);if (ret == -1) {
return NULL;)
iconv_close(c_pt);return bufout;
例如8：
char *d_ConvertCharset(char *cpEncodeFrom, char*cpEncodeTo, const char *cplnput) {
static char s_strBufOut[1024], *sin, *cp0ut;size_t ilnputLen, iOutLen, iReturn;
iconv_t c_pt;
if ((c_pt = iconv open (cpEncodeTo, cpEncodeFrom))== (iconv_t)-1) {printf (z/iconv_open failed! \nzz);
return NULL;}
iconv(c_pt, NULL, NULL, NULL, NULL);ilnputLen = strlen (cplnput) + 1;
iOutLen = 1024;sin = (char *)cplnput;
cpOut = s_strBufOut;iReturn = iconv(c_pt, &sin, &iInputLen, &cp0ut, &i0utLen);
if (iReturn =二-1) {return NULL;
iconv_close(c_pt);return s strBufOut;
{DNODE *h, *p, *q;
int x;
h=p=(*DNODE)malloc(sizeof(DNODE));
scanf(“％d”,&x);
while(x!=0)
{q=(*DNODE)malloc(sizeof(DNODE));q->data=x;
p->next=q;q->prior=p;
p=q;scanf("％cT',&x);}
p->next=NULL; h->prior=NULL;return h;}
2 .在双链表的第I个结点之后后插入一新结点
void insertd(DNOD **h,int I, int x)
{DNODE *s, *p;
intj；
s=(DNODE *)malloc(sizeof(DNODE));
s->data=x;
if(I==0)
{s->next=*h; *h->prior=s; *h=s; *h->prior=NULL;} else
{p=*h;j=l;
while(p!=NULL&&j<i){j++； p=p->next;}
if(p!=NULL)if(p-〉next==NULL)
{p->next=s; s->prior=p; s->next=NULL;}else
{s->next=p->next; p->next->prior=s; s->prior=p; p->next=s; }else
printfC'No found'n");}}.删除双链表中值为x的结点
void delete(DNODE **h, int x){DNODE *p;
if(*h==NULL) printfC'overflow\n,9);
if(*h->data==x)
{p=*h; *h= *h->next; *h->prior=NULL; free(p);}
else
{p=*h->next;while(p! =NULL&&p->data! =x)
p=p->next;if(p!=NULL)
if(p->next==NULL){p->prior->next=NULL; free(p);}
else
{p->prior->next=p->next; p->next->prior=p->prior; free(p);} elseprintfC'No found'n");}}
第二章复习题
一、填空.在线性结构中元素之间存在一对一关系,第一个结点没有 前驱结点,其 余每个结点有且只有」一个前驱结点；最后一个结点没有后继结点,其余每个 结点有目只有」一个后继结点。
1 .线性结构的顺序存储结构是一种随机存取的存储结构,逻辑上相邻的元素 物理位置上必紧临；其链式存储结构是一种顺序存取的存储结构,逻辑上相 邻的元素物理存储位置不一定连续。
二、选择.在一个单链表中，假设P所指结点不是最后结点，在P之后插入S所指结点， 那么执行（B ）o
A. s->next=p; p->next=s;B. s->next=p->next; p->next=s;C. s->next=p->next; p=s;D. p->next=s; s->next=p;
2.在一个单链表中，假设删除p所指结点的后续结点，那么执行（A ）。
A. p->next=p->next->next;B. p->next=p->next;C. p=p->next; p->next=p->next->next; D. p=p->next->next;
3 .在一个单链表中，q所指结点是p所指结点的前驱结点，假设在q和p之 间插入s结点，那么执行（C ）。
A. s->next=p->next; p->next=s;p->next=s->next; s->next=p;
B. s->next=p; q->next=s;p->next=s; s->next=q;
4 .非空的循环单链表头指针为front, p指向尾结点，那么应满足（C ）。
A. p->next==NULL; B. p==NULL; C. p->next==front; D. p==front;.带头结点的单链表头指针front为空的判定条件是（B ）。
A. front-NULLB. front->next=NULLC. front->next==frontD. front!=NULL
6.不带头结点的单链表头指针front为空的判定条件是（A ）0
A. front二二NULLB. front->next二二NULL
C. front->next==frontD. front!=NULL.在循环双链表的p所指结点之后插入s所指结点的操作是（D ）o
A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
B. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
7 .在双链表的p所指结点之前插入s所指结点的操作是（A ）0s->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s;
A. s->next=p; s->prior=p->prior; p->prior=s; p->prior->next=s;p->prior=s; s->next=p; p->prior->next=s; s->prior=p->prior;
B. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;.删除双链表中p所指结点的操作是(C )0
A. p->prior=p->prior->prior; p->prior->next=p; free (p);p->next=p->next->next; p->next->prior=p; free(p);
B. p->prior->next=p->next; p->next->prior=p->prior; free(p);p->next->prior=p->prior; p->prior->next=p; free (p)
三、
编程
.含n个元素的顺序表X按升序排列，删除线性表中值介于a与b之间的元素。 void del (int x[], int *n, int a, int b)
{ int i=0, k;while (i<*n)
if (x[i]>a&&x[i]<b){ for(k=i;k<*n;k++)
x[k]=x[k+l];(*n) —;)
else i++;}.含n个元素的顺序表A按升序排列，删除线性表中多余的值相同的元素。
int del (int a[], int n){ int i=0, j;
while (i<=n-l)if (a[i]!=a[i+l]) i++;
else{ for(j=i;j<n;j++)
a[j]=a[j+l];
n--;}return n;}
1 .含n个元素的顺序表A中元素按升序排列，插入一个元素x后，使A中元素 仍有序。
int insert(int a[], int n,int x){ int i, j;
if (x>=a[n-l])a[n]=x;else{ i=0;
while(x>=a[i]i++;for(j=n-l; j>=i; j—) a[j+l]=a[j];
a[i]=x;n++;}
return n;}.求单链表的长度
int count (NODE *h)
{int n=0;
NODE *p;
P=h;
if (h=NULL) n=0;
elsewhile (p!=NULL)
{n++; p=p->next;}
return n;}第三章栈和队列
要求、目标：
熟悉栈和队列特点、数据结构的定义
掌握在栈上的各种操作、使用数组和链表实现栈
掌握用数组和链表实现队列
掌握循环队列的相关操作 一、栈
（一）概述.堆栈：只允许在表的一端进行插入和删除操作的线性表。
1 .栈顶：允许进行添加或删除元素的一端.栈底：不允许进行添加或删除元素的一端
2 .空栈：没有元素的栈.入栈（进栈/压栈）（push）：栈的插入运算
3 .出栈（退栈/弹出）（pop）：栈的删除运算.栈的特点：后进先出（LIFO）
在栈中插入和删除的例如
（二）栈的顺序存储结构.栈类型的定义
#define STACKMAX 100int top;
int stack[STACKMAX];.栈的初始化
top值为下一个进栈元素在数组中的下标值，入栈操作是先压栈再移动栈顶 指针，出栈操作是先移动栈顶指针再取出元素1）栈空：top==0
2）栈满：top==STACKMAX.进栈与出栈顺序
假设进栈序列为a、b、c,那么全部可能出栈的序列为（，一，表示进，’一，表示出）：
①af a- bf b- cf c-即 abc②af b— b- c- c- a―即 bca ③af a- bf cf c- b-即 acb ④af bf b- a- cf c-即 bac ⑤af bf cf c— b— a—即 cba 4.判定栈是否为空
int empty()
{if(top==0) return 1;
else return 0;).压栈的实现
int top=0;
int push(int x){if(top>=STACKMAX) rerurn 1; stack[top++]=x;
return 0;}.出栈的实现 int pop(int *p) {if(top==0) rreturn 1;
*p=stack[—top];
return 0;}.读栈顶元素 void readtop(int *p) {if(top==0) printfC'No element'rT);
else *p=stack[—top];
top++;}
(三)栈的链式存储结构.链栈：用线性链表表示的栈
1 .栈顶指针：链栈的表头指针.栈的变化
1)栈空：top==NULL2)非空：top指向链表的第一个结点，栈底结点的指针域为空
•无栈满情况.结点类型
typedef struct snode
{int data;
struct snode *next;} SNODE;.进栈的实现
SNODE *top=NULL;
void push_L(int x)
{SNODE *p;
p二(SNODE *)malloc(sizeof(SNODE));
p->data=x;
p->next=top;
top=p；}.判链栈是否为空
int empty_L(SNODE *top)
{if(top==NULL) return 1;
else return 0;}.出栈的实现
int pop_L(SNODE *top, int *p)
{SNODE *q;
if(top==NULL) return 1;
*p=top->data;
q=top;
top=top->next;
free(q);
return 0;}.求链栈中结点的个数
int count_L(SNODE *top)
{SNODE *p;顺序存储结构：利用元素的相对位置来表示元素间的位置关系，是一 种随机存取结构，逻辑上相邻的数据物理上也紧临，静态分配空间；
① 链式存储结构：借助元素存储的指针来表示元素之间的关系，逻辑上 相邻的数据物理上不一定紧临，动态分配空间。
11 .逻辑结构和物理结构的关系：是密切相关的两个方面，任何一个算法的 设计取决于逻辑结构，而算法的实现那么依赖于采用的存储结构。
12 .数据类型：是一个值的集合和定义在这个值集上的一组操作的总称，规 定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值 上允许进行的操作。
二、算法和算法分析
1 .算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。
2 .算法的特性：
①有穷性：算法在执行有究步之后结束，每一步在有穷时间内完成。
②确定性：每一条指令必须有确切的含义，不应产生二义性，相同的输入只 能得出相同的输出。
③可行性：一个算法可以通过已经实现的基本运算执行有限次来实现。
④输入性：一个算法有零个或多个输入。
⑤输出性：一个算法有一个或多个输出。
3 .算法分析考虑的方面：
①正确性②可读性③健壮性④效率与低存储量需求
4 .语句频度：一条语句被执行的次数.渐近时间复杂度：所有语句频度之和，主要考虑嵌套最深语句的频度，假设频 度为多项式取指数最高的一项去掉系数即为渐近时间复杂度。
T(n)=O(f(n))—f(n)为时间复杂度值
例：(l){++x; s=0;}0(1)(2)for( i=l; iv=n; i++ ){++x; s+=x}0(n)
(3)for( j=1; j<=n; j++ )O(n2)for( k=l; k<=n; k++ ){++x; s+=x;}
(4)for(j=l;j<n;j++)
int n=0;
p=top;
while(p!=NULL)
{n++； p=p>next;}
return n;}
(四)栈的应用.数数制转换(十进制一八进制)
void convert()
{int x,n,m;
top=0;
scanf("％d”,&n);
while(n)
{m=push(n%8);if(m) printf(overflow\n);
else n/=8;}
while(! empty ())
{m=pop(&x);if(m) printfC'No element'rT);
else printf("％d”,x);}}.表达式求值
1)算术表达式的中缀表示：运算符放在两个操作数中间的算术表达式
例：a+b*c+d/e*f2)中缀表示在计算机处理中的的问题
受括号、优先级和结合律的限制，不一定按运算符出现的先后顺序执行，完 成运算需对表达式进行多遍扫描，浪费时间。
3)算术表达式的后缀表示(逆波兰表示法)
例：a+b- ab+ a*b- ab* 4)中缀表达式到后缀表达式的转换规那么①找出最先运算的运算符，将其移至两个操作数的后面，假设有括号那么删掉
②把得到的后缀表达式作为一个整体放在原表达式中③找下一个要运算的运算符，重复上述转换直到所有运算符处理完毕
例：a+b*c-d/（e*f）f a+b*c-d/ef*f a+bc*-def*/f abc*+-def*/f abc*+def*/-.后缀表达式的求值
从左f右扫描，遇到运算符将该运算符前面两个数取出运算，结果带回后缀 表达式参与后面的运算，直到扫描到最后一个运算符并计算得最终结果
例：345/6*+2- 3 0.8 6*+2- 3 4.8+2-- 7.8 2-- 5.8.运用栈完成后缀表达式求值
运用栈保存操作数和结果，从左一右扫描，假设为操作数那么将其入栈，假设为运 算符那么弹出两个数进行运算，并将结果入栈，直到扫描到表达式的最后一个字符, 栈顶的值为最终的结果。
5 .运用栈完成中缀表达式到后缀表达式的转换
运用栈保存运算符、取中缀表达式中的一字符，假设为数字那么输出； 假设为（那么入栈；假设为运算符当其优先级高于栈顶运算符的栈中优先级时那么入栈， 否那么栈顶运算符出栈并输出；假设为）那么依次退出栈中运算符并输出直到（， 将（退栈但不输出；假设为'\0'那么依次退栈并输出二、队列
（一）概述.队列：只允许在表的一端进行插入操作而在另一端进行删除操作的线性表
1 .队尾：允许进行插入操作的一端.队首：允许进行删除操作的一端
2 .特点：先进先出（FIFO）
（二）队列的顺序存储结构.顺序队列的类型
#define QUEUEMAX 100
char queue [QUEUEMAX];
int front,rear;.顺序队列的变化
front指向队首元素的前一个位置，rear指向队尾元素的位置，入队操作是先 移动队尾指针，再插入元素；出队操作是先移动队首指针，再取出元素1) 空：front==rear==-1
2)非空：rear>front3)满：rear二二 QUEUEMAX-1
3 .判别队列是否为空
int empty()
{if(front==rear) return 1;
else return 0;}.初始化队列
void init()
{int front=-1 ,rear=-1;}.入队的实现
int ins_queue(char x)
{if(rear== QUEUEMAX-1) return 1;
queue [++rear]=x;
return ();}.出队的实现
int del_queue(char *p)
{if(front==rear) return 1;
*p=queue[++front];
return 0;}.假溢出
1)假满：当rear==QUEUEMAX-l时，数组前端有空闲单元，出现假满2)解决方案：
①一个元素出队时，将所有元素依次向队首方向移动一个位置，修改头尾指针， 使空闲单元留在后面，此方案花费时间较多②出队时队列不移动，当出现假溢出时，将所有元素依次向队首方向移动，此方 案也要花费较多时间
③把队列看作是一个首尾衍接的循环队列，这是最有效的解决方案
（三）循环队列.特点：空闲单元单元总是在尾指针后面，front指向队首前一个位置
1 .循环队列的变化ARRAYMAX = 16

ARRAYMAX = 16
队列的队首
0 1