【数据结构上机实验指导书】

1、计算机科学与工程学院目 录第一部分 数据结构课程实验概述4一实验目的4二实验要求52.1实验步骤52.2 实验报告的内容62.3实验报告格式72.4考核及评分办法8三、验证算法的方法83.1 类c语言与标准c的转换要点83.2 验证算法的源程序结构123.3 验证算法的源程序举例13第二部分 上机实验内容17实验一 c语言复习及初步认识17实验二 线性表19实验三 栈和队列32实验四 串42实验五 数组和广义表49实验六 树59实验七 图66实验八 查找73实验九 排序76第三部分 数据结构课程设计79课程设计的基本要求和方法79附件1：课程设计报告封面（a4纸）80附件2：课程设计报告内容（

2、a4纸）81附件3：课程设计资料袋封面填写模板82附件4：课程设计光盘中的目录结构及编写方式83附件5：课程设计报告范文84附件6：课程设计心得范文87数据结构课程设计题目程序调试类题目88一、单链表的基本操作88二、用单链表编制集合运算的程序93三、用数组实现两个非稀疏矩阵的相乘运算95四、按层次遍历二叉树96五、快速排序99六、堆排序100七、二叉树的建立及操作101八、无向图的建立及遍历操作104数据结构课程设计题目程序编写类题目107一、一元稀疏多项式计算器107二、迷宫问题108三、哈夫曼编/译码器108四、教学计划编制问题110五、成绩分析问题111六、二叉排序树与平衡二叉树的实现

3、111七、图的基本操作与实现112八、全国交通咨询模拟112九、内部排序算法的性能分析113十、背包问题的求解113十一、稀疏矩阵的操作114十二、josephu 问题114第一部分 数据结构课程实验概述一实验目的数据结构是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和

4、应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。数据结构课对理论与实践的要求都相当高，并且内容多难度大。虽然多数数据结构教材都强调了实践的重要性，但比较缺乏供实践练习的材料，很多教材对算法的描述也只是扼要的和概述性的，很多算法都采用类c或类pascal语言描述，无法直接上机实现。针对这种情况，我们编写了这本数据结构上机实验指导书。本书可作为”数据结构”课程的辅助教材，供计算机专业或非计算机专业的学生以及本科或专科的学生在”数据结构”课程实习时使用，以帮助学生在尽可能短的时间内对数据结构知识的实践与应用有一个比较全面、深入和系统的认识，达到理论与实践相结合的

5、目的。上机实验是对学生的一种全面综合训练，是与课堂听课、自学和练习相辅相成的必不可少的一个教学环节。实验目的着眼于原理与应用的结合，使学生学会如何把书上的知识用语解决实际问题，能够理解和运用常用的数据结构，如线性表、栈、队列、树、图、查找表等，并在此基础上建立相应的算法；通过上机实验使学生了解算法和程序的区别，培养学生把算法转换为程序的能力，提高学生解决实际问题的能力；学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。加*号的题目可以选做。二实验要求2.1实验步骤 设计步骤的规范不但可以培养学生科学

6、的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是： 2.1.1问题分析 充分地分析和理解问题本身，明确问题要求做什幺。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构

7、清晰、合理、简单和易于调试。 编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。对程序中的疑问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。 2.1.3上机前程序静态检查 上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。 静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事先排除。2.1.4上机调试程序上机实验时要带上c语言教材、数据结构教材、数据结构上机实验指导书，调试最好分模块进行，自底向下，即先调试低层过

8、程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。2.1.5完成上机实验报告2.2 实验报告的内容1、需求分析陈述程序设计的任务，强调程序要解决的问题是什么？明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；测试数据。 2、设计设计思路：写出存储结构，主要算法的基本思想。设计表示：每个操作及模块的伪码算法。列出每个过程或函数所调用和被调用的过程或函数，也可以通过调用关系（层次）图表达。实现注释：各项功能的实现程度、在完成基本要求的基础上还实现了什么功能。3、调试分析调试过程中遇

9、到的主要问题，是如何解决的，对设计和编码的回顾讨论和分析；改进设想；经验和体会等。4、测试结果列出测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。5、用户手册说明如何使用你编写的程序，详细列出每一步操作步骤。6、附录即带注释的源程序清单和结果。除原有注释外再加一些必要的注释和断言(关键语句或函数功能的注释)。 对填空和改错题还要写出正确答案，如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含其它测试数据及其运行输出。2.3实验报告格式题目：班级： 姓名： 学号： 完成日期： 1 需求分析2 设计3 调试分析4 测试结果5 用户手册6 附录2

10、.4考核及评分办法上机实验成绩根据上机考勤、调试情况、实验报告评分，分为五级制：优、良、中、及格、不及格。期末上机考试以抽签的方式选择考题,占总成绩的10%。三、验证算法的方法数据结构教材上的算法都是用类c语言来描述，但要验证算法只能用标准c来验证，所以存在类c语言与标准c的转换及验证算法的源程序编写问题。3.1 类c语言与标准c的转换要点3.1.1 预定义常量和类型的问题在类c语言的算法中出现了下列常量，验证时就需在源程序中定义：#define true 1#define false 0#define ok 1#define error 0#define infeasible -1#defi

11、ne overflow -2#define int status3.1.2 算法描述的变量问题在类c语言算法（函数）中，辅助变量没有作变量说明，但在验证源程序的函数定义时，需对所有使用的变量（除函数参数外）作说明。例1：顺序表的插入算法（类c语言）：status listinsert_sq(sqlist &l, int pos, elemtype e) / 在顺序线性表l的第pos个元素之前插入新的元素e，pos为位序/ pos的合法值为1poslistlength_sq(l)+1if (pos l.length+1) return error; / 插入位置不合法if (l.length =

12、 l.listsize) / 当前存储空间已满，增加分配newbase = (elemtype *)realloc(l.elem,(l.listsize+listincrement)*sizeof (elemtype); if (!newbase) exit(overflow); / 存储分配失败l.elem = newbase; / 新基址l.listsize += listincrement; / 增加存储容量q = &(l.elempos-1); / q指示插入位置for (p = &(l.eleml.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后

13、的元素右移*q = e; / 插入e+l.length; / 表长增1return ok; / listinsert_sq验证算法源程序中算法所对应的函数定义：int listinsert_sq(sqlist *l, int pos, elemtype e)elemtype *newbase,*p,*q;if (pos l-length+1) return (-1);if (l-length = l-listsize)newbase= (elemtype *)realloc(l-elem,(l-listsize+listincrement)*sizeof (elemtype);if (!new

14、base) exit(-1);l-elem = newbase;l-listsize += listincrement;q =&(l-elem)pos-1);for (p=&(l-elem)l-length-1);p=q;-p) *(p+1)=*p;*q = e;+l-length;return (1);3.1.3 算法描述的参数问题在类c语言算法（函数）中，在形参定义时，以“&”打头的参数作为引用参数，即在函数调用后发生改变的量，但在验证源程序的函数定义时，需对引用参数转换为指针类型，在函数定义内，把引用参数的使用转换为引用参数对象的使用。例2：顺序表的插入算法（类c语言）：status l

15、istinsert_sq(sqlist &l, int pos, elemtype e) / 在顺序线性表l的第pos个元素之前插入新的元素e，pos为位序/ pos的合法值为1poslistlength_sq(l)+1if (pos l.length+1) return error; / 插入位置不合法if (l.length = l.listsize) / 当前存储空间已满，增加分配newbase = (elemtype *)realloc(l.elem,(l.listsize+listincrement)*sizeof (elemtype); if (!newbase) exit(ove

16、rflow); / 存储分配失败l.elem = newbase; / 新基址l.listsize += listincrement; / 增加存储容量q = &(l.elempos-1); / q指示插入位置for (p = &(l.eleml.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+l.length; / 表长增1return ok; / listinsert_sq验证算法源程序中算法所对应的函数定义：int listinsert_sq(sqlist *l, int pos, elemtype e)elem

17、type *newbase,*p,*q;if (pos l-length+1) return (-1);if (l-length = l-listsize)newbase= (elemtype *)realloc(l-elem,(l-listsize+listincrement)*sizeof (elemtype);if (!newbase) exit(-1);l-elem = newbase;l-listsize += listincrement;q =&(l-elem)pos-1);for (p=&(l-elem)l-length-1);p=q;-p) *(p+1)=*p;*q = e;+

18、l-length;return (1);3.2 验证算法的源程序结构文件包含预处理符号常量的定义类型定义/*确定数据结构*/返回类型 自定义函数名（形式参数表）/*自定义函数的定义，即算法*/main()变量定义；/*定义处理对象*/建立对象；/*根据存储类型，给变量赋值，以确定具体的处理对象*/调用自定义函数；/*引用函数对处理对象进行操作，实现算法的功能*/打印输出；/*给出结果*/3.3 验证算法的源程序举例例3：顺序表的插入算法的验证方法顺序表的插入算法：status listinsert_sq(sqlist &l, int pos, elemtype e) / 在顺序线性表l的第po

19、s个元素之前插入新的元素e，pos为位序/ pos的合法值为1poslistlength_sq(l)+1if (pos l.length+1) return error; / 插入位置不合法if (l.length = l.listsize) / 当前存储空间已满，增加分配newbase = (elemtype *)realloc(l.elem,(l.listsize+listincrement)*sizeof (elemtype); if (!newbase) exit(overflow); / 存储分配失败l.elem = newbase; / 新基址l.listsize += listi

20、ncrement; / 增加存储容量q = &(l.elempos-1); / q指示插入位置for (p = &(l.eleml.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+l.length; / 表长增1return ok; / listinsert_sq验证“顺序表的插入算法”的源程序：/文件包含预处理#include #include /符号常量的定义#define list_init_size 5#define listincrement 5/类型定义（确定数据结构）typedef int elemtyp

21、e;typedef struct elemtype *elem;int length;int listsize; sqlist; int initlist_sq(sqlist *l)l-elem=(elemtype*)malloc(list_init_size *sizeof(elemtype);if (!l-elem) exit(-1);l-length = 0;l-listsize = list_init_size;return (1);int listinsert_sq(sqlist *l, int pos, elemtype e)elemtype *newbase,*p,*q;if (

22、pos l-length+1) return (-1);if (l-length = l-listsize)newbase = (elemtype *)realloc(l-elem,(l-listsize+listincrement)*sizeof (elemtype);if (!newbase) exit(-1);l-elem = newbase;l-listsize += listincrement;q =&(l-elem)pos-1);for (p=&(l-elem)l-length-1);p=q;-p) *(p+1)=*p;*q = e;+l-length;return (1);voi

23、d traverse(sqlist l) int i; printf(the list data is:n); for (i=0;il.length;i+) printf(%5d,l.elemi); printf(n); getch(); main()int i; sqlist l; /*定义处理对象*/initlist_sq(&l); /*建立对象：根据存储类型，给变量赋值，以确定具体的处理对象*/for (i=1;i=10;i+) listinsert_sq(&l, i, i+1);/*调用自定义函数：引用函数对处理对象进行操作，实现算法的功能*/traverse(l); /*打印输出：给

24、出结果*/第二部分 上机实验内容实验一 c语言复习及初步认识一、 实验目的本实验的目的是帮助大家复习c语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备。二、实验内容1、 请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。2、 计算1+2+3+100，要求用指针进行设计。即设计函数int fun(int *n)实现求1+2+3+*n，在主函数中输入、调用、输出结果。3、 请编写函数int fun(

25、int *a,，int *max),函数的功能是求数组a中最大数的值。在主函数中输入10个整数、调用函数fun、输出结果。4、 请编写函数fun(int *a,int n, int *odd, int *even),函数的功能是分别求出数组a中所有奇数之和和所有偶数之和。形参n给出数组中数据的个数；利用指针odd和even分别返回奇数之和和偶数之和。在主函数中输入10个整数、调用函数fun、输出结果。5、 请编写函数int fun(int *a, int *b，int n),函数的功能是把数组a中所有为偶数的数，放在另一个数组中b。在主函数中输入10个整数、调用函数fun、输出结果。6、 请编

26、写函数int fun(int *a,，int n),函数的功能是把数组a中最大数和最小数交换。在主函数中输入10个整数、调用函数fun、输出结果。7、 请编写函数int fun(int a44),函数的功能是把矩阵a转置。在主函数中输入、调用函数fun、输出结果。8、 请编写函数int fun(char *a),函数的功能是分别求出字符串a 的长度。在主函数中输入1个字符串、调用函数fun、输出结果。9、 设计一个可进行复数运算的演示程序。要求：实现下列六种基本运算：1）由输入的实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数求积；5）从已知复数中分离出实部；6）从已知

27、复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。10、 有5个学生，每个学生的数据包括学号、姓名、3门课的成绩，从键盘输入5个学生数据，要求打印出3门课总平均成绩，以及最高分的学生的数据。要求：用input函数输入5个学生数据，用average 函数求总平均分；用max函数找出最高分的学生数据；总平均分和最高分学生的数据都在主函数中输出。实验二 线性表一、 实验目的1.掌握数据结构中表的基本概念。2熟练掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的实现。3.熟练掌握链表的各种操作和应用。二、实验内容顺序表的基本运算的算法：创建顺序表：输

28、出顺序表；插入运算；删除运算；查找运算单链表的基本运算的算法：创建一个单链表；输出一个单链表；求单链表的长度；查找第i个结点；插入一个结点；删除一个结点；1、设有一个顺序表a，包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间外再增加一个附加的工作单元。（根据题目完善源程序）#include #define maxlen 50typedef int elemtype;struct datatypeelemtype *elem; int length;typedef struct datatype sqlist;void create (sqlist *a)int i,n;a-

29、elem=(elemtype *)malloc(maxlen*sizeof(elemtype);printf(创建一个顺序表n);printf(输入元素个数n);scanf(%d,&a-length);for (i=0;ilength;i+) printf(输入第%d个元素值:,i+1); scanf(%d,a-elem+i);void invert(sqlist *a) int m=a-length/2,i;elemtype temp;for (i=0;ielem+i)= ; =temp; void disp(sqlist *a) int i;for (i=0;ilength;i+) pri

30、ntf(%5d:%dn,i+1,*(a-elem+i);getch();void main()sqlist a;create(&a);disp(&a);invert(&a);disp(&a);创建一个顺序表输入元素个数：5输入第1个元素值：2输入第2个元素值：6输入第3个元素值：3输入第4个元素值：1输入第5个元素值：8输出一个顺序表 输出一个顺序表 2、有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表（根据题目填空完善程序）#include #include #define null

31、 0typedef int elemtype;typedef struct linknodeelemtype data;struct linknode *next;nodetype;nodetype *create()elemtype d;nodetype *h,*s,*t;int i=1;h=null;printf(建立一个单链表n);while (1) printf(输入第%d节点data域值:,i); scanf(%d,&d);if (d=0) ; /*以0表示输入结束*/if(i=1) /*建立第一个结点*/h= ;h-data=d;h-next=null;t=h;elses=(nod

32、etype *)malloc(sizeof(nodetype);s-data=d;s-next=null;t-next=s; ; /*t始终指向生成的单链表的最后一个结点*/i+;return h;void disp(nodetype *h)nodetype *p=h;printf(输出一个单链表：n);if (p=null) printf(空表);while (p!=null)printf(%d,p-data); ;printf(n);getch();int len(nodetype *h)int i=0;nodetype *p=h;while (p)i+;p=p-next;return(i

33、);nodetype *invert(nodetype *h)nodetype *p,*q,*r;if (len(h)next;while (q!=null)r=q-next;q-next=p;p=q;q=r;h-next=null;h=p;return h;void main()nodetype *head;head=create();disp(head);head=invert( );disp(head);建立一个单链表输入第1个节点data 域的值：1输入第2个节点data 域的值：2输入第3个节点data 域的值：3输入第4个节点data 域的值：4输入第5个节点data 域的值：5输

34、入第6个节点data 域的值：0输出一个单链表： 3、将两个非递减有序的单链表归并为一个非递减有序的单链表（根据题目填空完善程序）#include “stdio.h”#include “alloc.h”struct node char data； struct node *next； listnode；typedef struct node *link；void print(link head) struct node *p； printf（“n”）； printf（“n”）； p= head-next； while(p) printf（“%c”, p-data）； ； link creat(

35、) /*头插法建立单链表*/ link head ,s； char ch； head = malloc(sizeof(listnode)； head-next =null； while( ch= getchar()!=n) s= malloc(sizeof(listnode)； s-data= ch； s-next = ； = s； return head；link merge(link a , link b) link p , q , s , c； c= malloc(sizeof(listnode)； c-next =null； p=a； q=b； while(p-next&q-next)

36、 if (p-next-datanext-data) s = p-next；p-next=s-next； else s = q-next；q-next = s-next； s-next = c-next； c-next = s； while (p-next) s = p-next； p-next = s-next； s-next = c-next； c-next = s； while(q-next) s = q-next； q-next = s-next； s-next = c-next； c-next = s； free(p)；free(q)； return c；main() link a

37、, b , c； a = creat()； b = creat()； print(a)； print(b)； c = merge ( )； print(c)； printf（“n”）；输入：ysplhd zyxrmhb输出 4、键盘输入学生信息（包括学号和成绩），学号为0作为结束标志，建立其对应的线性表并输出各结点中的数据。注：试以顺序表和单链表两种不同的存储结构实现。5、将上题线性表中学生的成绩从低到高排列输出，要求每行一个，包括学号和成绩。注：试以顺序表和单链表两种不同的存储结构实现。6、设计一个算法求a和b两个单链表表示的集合的交集。提示：a和b中相同的结点的集合。7、设计一个算法求a和

38、b两个单链表表示的集合的并集。提示：将a和b合并。8、设计一个算法求a和b两个单链表表示的集合的差集。（每个单链表中不存在重复的元素）提示：即在a中而不在b中的结点的集合。 *9、用头插法把单链表b中在单链表a中未出现的结点合并到单链表a中 *10、a,b,c为三个单链表，要求删除a表中、在b表和c表中同时出现的结点。 *11、设a=(a1,a2,an)和b=(b1,b2,bm)是两个不带哨兵的单链表.若n=m,且ai=bi(i=1,n),则称a=b；若ai=bi(i=1,j)且aj+1bj+1(jn=m),则称ab.试编写一个比较a和b的算法,当ab时分别输出-1、0或1。提示：算法comp

39、（）的思想是先找出a和b单链表中对应位置相同值的结点，pa和pb分别指向a和b单链表中对应位置不相同的结点。然后根据pa和pb的情况得到a和b单链表的比较结果。 *12、设计一个统计选票的算法，输出每个候选的得票结果（假设采用单链表存放选票，候选人编号依次为1，2，3，n，且每张选票选且只选一人）。提示：以单链表存放选票，每个结点的data域存放该选票所选的候选人。用一个数组a统计得票结果。 *13、假设一个循环单链表,其结点有left,data和right三个域,其中data为数据域,存放元素的有效信息,right为指针域,它指向后继结点,left为指针域,它的值为null.编写一个算法将此

40、表改为循环双链表。提示：本题算法依次从左向右遍历每个结点，并设置每个结点的left值。14、编写一个算法实现两个有序（从小到大）顺序表合并为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设两个顺序表中没有相同的元素）提示：两个顺序表a和b的合并过程是从a和b中的最后一个元素逐个向前进行比较，将较大的元素先定位在a中。*15、生成两个多项式pa和pb，求pa和pb之和，输出“和多项式”。分别用顺序存储和链式存储两种存储结构实现。16、设线性表中的数据元素是按值非递减有序排列的，试以顺序存储和链式存储两种存储结构实现，编写一算法，将x插入到线性表的适当位置上，以保持线性表的有

41、序性。实验三 栈和队列一、 实验目的1 了解栈和队列的特性，以便灵活应用。2 熟练掌握栈和有关队列的各种操作和应用。二、实验内容栈的基本运算：初始化栈；进栈；退栈；判断栈是否为空栈；获取栈顶元素；输出栈的所有元素； 队列的基本运算：初始化队列；入队列；出队列；判断队列是否为空；判断队列头元素；1、设单链表中存放n 个字符,设计一个算法,使用栈判断该字符串是否中心对称,如abccba即为中心对称字符串. （根据题目填空完善程序）提示：先用create()函数从用户输入的字符串创建相应的单链表，然后调用bj()函数判断是否为中心对称字符串。在 bj（）函数中先将字符串进栈，然后将栈中的字符逐个与单

42、链表中字符进行比较。# include # include # define maxlen 100typedef struct node char data；struct node *next；cnode；cnode *create (char s)int i=0；cnode *h, *p, *r；while (si!=0)p=(cnode *)malloc(sizeof(cnode)；p-data=si；p-next=null；if (i= =0)h=p；. (1) ； /*r始终指向最后一个结点*/elser-next=p；r=p；i+；return h；int judge(cnode *

43、h)char stmaxlen；int top=0；cnode *p=h；while (p!=null)sttop=p-data；top+；p=p-next；p=h；while (p!=null)top-；if (p-data= =sttop)p=p-next；elsebreak；if (p= =null)return (2) ；elsereturn (3) ；void main()char strmaxlen；cnode *h；printf（“输入一个字符串：”）；scanf（“%c”,str）；h=create( (4) )；if (judge(h)= = 1)printf( “ str是

44、中心对称字符串n”）；elseprintf（“str不是中心对称字符串n”）；输入一个字符串：abccba输出： (5) 2、假设以数组sequ0.maxsize-1存放环形队列的元素，同时设变量rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。试写出此环形队列队满的条件，并设计相应入队和出队的算法。（根据题目填空完善程序）提示：该环形队列对满的条件为：len= =maxsize，队空的条件为：len= =0。由rear,len求队列头指针front的过程为： front=rear-len+1； if (front0) front=front+maxsize；即 front=(

45、rear-len+1+maxsize)%maxsize# include # define maxsize 6typedef char queue maxsize；int rear=0, len=0；int enqueue (queue qu, char x)if (len= =maxsize)return 0；elserear=(rear+1) %maxsize；qurear=x；len+；return 1；int dequeue (queue qu, char *x)int front；if (len= =0)return 0；elsefront=(rear-len+1+maxsize)

46、%maxsize；*x=qufront；len-；return 1；void main()char x；queue qu；printf( “a入队n”）；enqueue (qu, a)；printf( “b入队n”）；enqueue (qu, b)；printf( “c入队n”）；enqueue (qu, c)；printf( “出队一次：”）；dequeue (qu, &x)；printf( “%cn”,x)；printf( “d入队n”）；enqueue (qu, d)；printf( “e入队n”）；enqueue (qu, e)；printf( “出队一次：”）；dequeue (qu

47、, &x)；printf（“%cn”,x)；printf( “f入队n”）；enqueue (qu, f)；printf( “g入队n”）；enqueue (qu, g)；printf( “出队一次：”）；dequeue (qu, &x)；printf（“%cn”,x)；printf（“余下元素出列：”）；while (len0)dequeue (qu, &x)；printf（“%cn”,x)；printf（“n”）；输出：. 1 入队. 2 入队出队一次： 3 . 4 入队. 5 入队出队一次： 6 . 7 入队. 8 入队出队一次： 9 余下元素出列： 10 3、设一个算术表达式中包含圆括

48、号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。提示：本题使用一个运算符栈st，当遇到的（、或时进栈，当遇到、）时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。 *4、到医院看病的过程是，患者先排队等候，排队过程中主要重复两件事：（1）病人到达诊室时，将病历交给护士，排到等候队列中候诊。（2）护士从等候队列中取出下一个患者的病历，该患者进入诊室就诊。在排队时按照”先到先服务”的原则。设计一个算法模拟病人等候就诊的过程。其中”病人到达”用命令a（a）表示，”护士让下一位患者就诊”用命令n（n）表示，命令q（q）表示不再接受病人排队。提示：这里采用一个队列，有”病

49、人到达”命令时即入队，有”护士让下一位患者就诊”命令时即出队，命令q即队列中所有元素出队。5、设计一个程序，演示用算符优先法对算术表达式求值的过程。基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3_1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。测试数据：3*（7-2） 6、如果用一个循环数组 qu0，m0-1表示队列时，该队列只有一个头指针 front，不设队尾指针 rear，而改置计数器 count 用以记录队列中结点的个数。 编写实现队列的五个基本运算；并编写主函数调用验证。7、试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中不包含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属于该模式的字符序列，而1+2&2-1则不是。8、编写一个函数将一般算术表达式转化为逆波兰表达