循环队列的类型定义
#define MAXSIZE 10 //下面的循环以列及操作依据少用个元素空间来实现 //循环队列的类型定义及基本运算如下。 typedef int ElemType; typedef struct{ ElemType elem [MAXSIZE];//队列的存储区 //队头队尾指针 int front, rear; }CSeQueue;//循环队列
循环队列的基本运算
相关代码请看配套资源
6-循环队列.c
int main(){ CSeQueue *cs=IniseQueue(); int x=1; InSeQueue(cs,x); printf("%d",EmptySeQueue(cs));//0 int x0; OutSeQueue(cs,&x0); printf("%d",x0);//1 printf("%d",EmptySeQueue(cs));//1 }
运行结果如下
3.3.3 链队列
链式存储的队列称为链队列
可以采用带头结点的单链表表示队列。
头指针始终指向头结点，尾指针指向当前最后一个元素结点
//链队列的数据类型描述如下。 typedef struct node{ DataType data; struct node * next; }QNode; //链队列结点的类型 typedef struct{ QNode * front; QNode * rear; } LQueue;//将头尾指针封装在一起的链队列
链队列的基本运算
相关代码请看配套资源
7-链队列.c
int main(){ LQueue *lq=Init_LQueue(); printf("%d",Empty_LQueue(lq));//1 int x=1; InLQueue(lq,x); printf("%d",Empty_LQueue(lq));//0 int x0; Out_LQueue(lq,&x0); printf("%d",x0);//1 printf("%d",Empty_LQueue(lq));//0 }
运行结果如下
3.4 实例分析与实现
应用实例一 迷宫求解
应用实例二 马踏棋盘
应用实例三 计算器
3.5 算法总结 ——递归与分治 算法
习题3
题目
1.单项选择题
(1)(2010考研真题)若元素a,b,e,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是____。
A. d,c,e,b,f,a
B. c,b,d,a,e,f
C. b.c,a,e,f,d
D. a,f,e,d,c,b
(2)若某堆栈的输人序列为1,2,3,n-l,n,输出序列的第1个元素为n,则第i个输出元素为____。
A. n-i+1
B. n-1
C. i
D.哪个元素都有可能
(3)以数组Q[0…m-1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是___。
A. rear-qulen
B. rear-qulen+m
C. m-qulen
D. (1+(rear-qulentm))mod m
(4)设输人元素为1,2,3,A,B,输人次序为123AB,元素经过栈后到达输出序列,当所有元素均到达输出序列后,序列____是不可能的。
A. BA321
B. A3B21
C. B32A1
D. AB321
(5)(2012年考研真题)已知操作符包括“+”“一”“”“/”“(”和“)”。将中缀表达式a+b-a((c+d)/e-)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次
A. 5
B. 7
C. 8
D.11
2.综合题
(2) 回文是指正读反读均相同的字符序列,如“abba”和“abdba"均是回文,但“good"不是回文。试写一个算法判定给定的字符串是否为回文。
(6) 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的置空队、判队空、入队和出队算法。
(8) 在循环队列中,可以设置一个标志域tag,以区分当尾指针和头指针相等时,队列状态是“空”还是“满”（tag的值为0表示“空”,tag的值为1表示“满”),编写此结构相应的队列初始化、入队、出队算法。
参考
1.单项选择题
(1) D
(2) A
(3) D
(4) C
(5) A
2.综合题
(2)
相关代码请看配套资源
2.c
int main(){ char str[10]; gets(str); printf("输入字符串\n"); printf("%s",str); BracketMatch(str); }
运行结果如下
(6)
相关代码请看配套资源
6.c
int main(){ XQueue *lq=Init_XQueue(); printf("%d",Empty_XQueue(lq));//1 int x1=1; InXQueue(lq,x1); printf("%d",Empty_XQueue(lq));//0 int x2=2; InXQueue(lq,x2); int y1; Out_XQueue(lq,&y1); printf("%d",x1);//1 int y2; Out_XQueue(lq,&y2); printf("%d",y2);//2 printf("%d",Empty_XQueue(lq));//0 }
运行结果如下
(8)
相关代码请看配套资源
8.c
int main(){ CSeQueue *cs=IniseQueue(); printf("%d",EmptySeQueue(cs));//1 int x1=1; InSeQueue(cs,x1); int x2=2; InSeQueue(cs,x2); printf("%d",ManSeQueue(cs));//1 int y1; OutSeQueue(cs,&y1); printf("%d",y1);//1 printf("%d",EmptySeQueue(cs));//0 int y2; OutSeQueue(cs,&y2); printf("%d",y2);//2 printf("%d",EmptySeQueue(cs));//1 }
运行结果如下
