return Q; }
Sqqueue dequeue(Sqqueue Q,int *e)/*队列的出队函数*/ { int x;
if (Q.front==Q.rear) printf(\ else
{ *e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; } return Q; }
void display(Sqqueue Q)/*队列元素输出函数*/ { int k,m;
k=Q.front;m=Q.rear; while(k!=m)
{ printf(\ k=(k+1)%MAXQSIZE;} printf(\ }
main()/*主函数*/ { Sqqueue Q; int i,n,x,y,e;
Q.rear=Q.front=0; /*初始化顺序队列，使其成为空队列*/ printf(\请求输入队列的长度*/ scanf(\
printf(\请求输入队列中各个元素*/ for(i=1;i<=n;i++) {scanf(\
Q=enqueue(Q,x);}/*调用队列插入函数*/ printf(\
display(Q);/*调用队列元素输出函数*/
printf(\请求输入需要插入的元素*/ scanf(\
Q=enqueue(Q,y);/*调用队列插入函数*/
printf(\提示显示执行入队操作后的队列*/ display(Q);/*调用队列元素输出函数*/ Q=dequeue(Q,&e);/*调用队列删除函数*/
26
printf(\显示被删的队首元素值*/
printf(\提示显示执行出队操作后的队列*/ display(Q);/*调用队列元素输出函数*/ }
4．运行结果参考如图4-1所示：
图4-1: 验证性实验运行结果
七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现对循环链队列的入队和出队操作。
⑴ 实验要求
①根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列（循环链队列），并且只设一个尾指针来指向尾结点，然后输出队列中各元素值。
②将数据元素e入队，并输出入队后的队列中各元素值。
③将循环链队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。 ⑵ 核心算法分析
采用链式存储结构的队列称为链队列，链队列的存储结构描述如下：
typedef struct CQnode {
Qelemtype data;/*数据域*/ struct CQnode *next;/*指针域*/ }CQNODE,*CQLink;
如果队列中元素序列为{a1,a2，?,an}，则带头结点的循环链队列的存储结构如下图4-1所示：
图4-2： 循环链队列的存储结构示意
rear a1 a2 … an
从图4-1可看出，队列的循环链式存储结构与循环单链表的存储结构相同，所有在循环链队列上进行入队和出队操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：
27
①此循环链队列是通过一个指向队尾结点的指针rear来标识的,则rear指向队尾元素结点，rear->next指向队头结点，而rear->nexnt->next指向队首元素结点。
②队列的入队操作是在链表的表尾（队尾）进行，而出队操作则在链表的表头（队首）进行。
③在出队操作时要注意：如果当链表中只有一个结点，即被删结点既是队首结点，又是队尾结点时，要进行尾指针的修改。
⑶ 核心算法描述
void InitCiQueue(CQLink &rear)
/*初始化循环链表表示的队列rear,其中rear指向队尾元素*/
{ rear=(CQNODE*)malloc(sizeof(CQNODE)); /*产生一个头结点，并使队尾指针指向它*/ rear->next=rear; /*形成循环*/ }
入队操作：
status EnCiQueue(CQLink &rear, int x) /*把元素x插入到循环链表表示的队列rear中*/ { p=(CQNODE*)malloc(sizeof(CQNODE)); If
p->data=x; /*产生一个新结点p*/
p->next=rear->next; /*直接把p插入到rear的后面*/ rear->next=p;
rear=p; /*修改尾指针,使p成为新的队尾结点*/ }
status DeCiQueue(CQLink &rear, int &x)
/*从用队尾指针rear表示的循环链表删除一个队首元素，并用x返回其数据域的值。*/ { if(rear==rear->next) return ERROR; /*如果队列为空，则函数返回ERROR*/ p=rear->next->next;/*用p指针指向队首结点,也是待删结点*/ x=p->data; /* 用x保存待删队首结点的数据域的值*/
rear->next->next=p->next;/*修改链，使p的后继成为新的队首结点*/
if (rear==p) /*如果待删的结点p是队尾结点,则要使队尾指针指向原来队尾结点的后继(头结
点)*/
rear=rear->next;
free(p); /*释放待删结点的空间*/ return OK; }
2．编程实现键盘输入循环缓冲区问题。 ⑴ 实验要求
有两个进程同时存在于一个应用程序中。其中一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户链入的字符并保存到缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。当用户键入一个逗号“，”时表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键
28
入字符，直到用户输入一个分号“；”键，才结束第一个进程，同时也结束整个进程。
⑵ 核心算法提示
在操作系统中，循环队列经常用于实时应用程序。例如，当程序正在执行其他任务时，用户可以从键盘上不断键入所要输入的内容。很多字处理软件就是这样工作的。系统在利用这种分时处理方法时，用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统缓冲区中，然后继续运行原来的进程。在当前工作的进程结束后，系统就从缓冲区中取出键入的字符，并按要求进行处理。所以，这里的键盘输入缓冲区可采用循环队列。队列保证了输入字符先输入、先保存、先处理的要求，循环结构又有效地限制了缓冲区的大小，并避免了假溢出问题。
29
实验B05: 二叉树的操作实验
一、实验名称和性质
所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 二叉树的操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的
1．理解二叉树的类型定义与性质。
2．掌握二叉树的二叉链表存储结构的表示和实现方法。 3．掌握二叉树遍历操作的算法实现。 4．熟悉二叉树遍历操作的应用。 三、实验内容
1．建立二叉树的二叉链表存储结构。
2．实现二叉树的先序、中序和后序三种遍历操作（验证性内容）。
3．应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作（设计性内容）。 4．求从二叉树根结点到指定结点p之间的路径（应用性设计内容）。 四、实验的软硬件环境要求
硬件环境要求：
PC机（单机）
Windows环境下的TurboC2.0以上或VC++ 使用的软件名称、版本号以及模块： 五、知识准备
前期要求掌握二叉树的二叉链表的存储结构表示和三种遍历操作算法。 六、验证性实验 1．实验要求
编程实现如下功能：
（1）假设二叉树的结点值是字符，根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。
（2）对二叉树进行先序、中序和后序遍历操作，并输出遍历序列，观察输出的序列是否与逻辑上的序列一致。
（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种遍历操作。 2. 实验相关原理：
二叉树的形式定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。
二叉树的二叉链表存储结构描述为：
typedef char Telemtype; typedef struct Bitnode
30