*e=S.base[--S.top];
return S; }
void Stack_display(Sqstack S) /*顺序栈的输出函数*/ { int i;
for(i=0; i { Sqstack S; int i,j,n,x,e; printf(\请求输入顺序栈中元素个数*/ scanf(\ printf(\请求输入顺序栈中各个元素值*/ for(i=0;i scanf(\ S.top=n; printf(\ Stack_display(S); printf(\请求输入需要入栈的新元素*/ scanf(\ S=Push(S,x); printf(\提示输出入栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ S=Pop(S,&e); printf(\输出出栈元素的值*/ printf(\提示输出出栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ } 4．运行结果参考如图3-1所示： 21 图3-1：验证性实验运行结果 七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现链栈的入栈和出栈操作。 ⑴ 实验要求 （1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。 （2）将数据元素x入栈，并输出入栈后的链栈中各元素值。 （3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。 ⑵ 核心算法提示 采用链式存储结构的栈称为链栈，链栈的存储结构描述如下： typedef struct Snode { Selemtype data;/*数据域*/ struct Snode *next;/*指针域*/ }SNODE,* LinkStack;/*其中SNODE为链栈中的结点类型名, LinkStack为指向结点的指针类型名*/ 如果栈中元素序列为{a1,a2，?,an}，则链栈的存储结构如下图3-1所示： 图3-2： 链栈的存储结构示意图 top an an-1 an-2 … a1 ^ 从图3-1可看出，栈的链式存储结构与单链表的存储结构相同，所有在链栈上进行入栈和出栈操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点： （1）链栈中无需加头结点。 （2）链栈中的指针是指向栈中元素序列的前驱结点。 （3）链栈中的入栈和出栈操作都是在链表的表头进行。 ⑶ 核心算法描述 status Push(LinkStack &top,int e) /*将数据元素e压入到链栈top中，使其成为新的栈项元素*/ { LinkStack p; p=(LinkStack)malloc(sizeof(SNODE)); /*生成一个新的结点*/ if (!p) /*如果分配空间失败，则函数返回\ return OVERFLOW; p->data=e; /*新结点的数据域赋值*/ p->next=top; /*修改链使新结点插入到链表的头部,并成为新的栈顶元素*/ top=p; return OK; } status Pop(LinkStack &top,int &e) /*将链栈top中的栈顶元素从栈中删除，并用e返回其值*/ 22 { LinkStack q; if (!top) /*如果栈空，则函数返回ERROR*/ return ERROR; e=top->data; /*将被删的栈顶元素的值保存在e中*/ q=top; /*用q记下待删的栈顶元素*/ top=q->next; /*修改链使待删结点从链中“卸下”，此时被删结点的后继成为新的栈顶元素结点*/ free(q); /*释放被删结点的存储空间*/ return OK; } 2．编程实现汉诺（Hanoi）塔求解问题。 ⑴ 实验要求 假设有三个命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同且从小到大编号为1,2,??,n的圆盘。现要求将塔座X上的n个圆盘借助于塔座Y移至塔座Z上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则： ① 每次只能移动一个圆盘； ② 圆盘可以插在X、Y和Z中的任何一个塔座上； ③ 任何时刻都不能将一个较大的圆盘压在较小的圆盘上。 ⑵ 核心算法提示 当n=1时，问题比较简单，只要将编号为1圆盘从塔座X直接移动到塔座Z上即可；当n>1时，若能将压在编号为n的圆盘上的n-1个圆盘从塔座X借助于塔座Z移至塔座Y上，则可先将编号为n的圆盘从塔座X移至塔座Z上，再将塔座Y上的n-1个圆盘借助于塔座X移至塔座Z上。而将n-1个圆盘从一个塔座借助于另一个塔座而移至到第三个塔座上是一个与原问题具有相同特征属性的问题，只是问题规模小1,因此可以用解决原问题的方法来解决。 23 实验B04: 队列的操作实验 一、实验名称和性质 所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 队列的操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的 1．掌握队列存储结构的表示和实现方法。 2．掌握队列的入队和出队等基本操作的算法实现。 3．了解队列在解决实际问题中的简单应用。 三、实验内容 1．建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作（验证性内容）。 2．建立循环链队列，并在循环链队列上实现入队、出队基本操作（设计性内容）。 3．实现键盘输入循环缓冲区问题（应用性设计内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） Windows环境下的TurboC2.0以上或VC++ 使用的软件名称、版本号以及模块： 五、知识准备 前期要求熟练掌握了C语言的编程规则、方法和顺序循环队列、循环链队列的基本操作算法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。 （2）将数据元素e入队，并输出入队后的队列中各元素值。 （3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。 2. 实验相关原理： 队列是一种插入操作限制在表尾，而删除操作限制在表头进行的特殊线性表，它的操作具有“先进先出”的特性。采用顺序存储结构的队列称为顺序队列，顺序队列的存储结构描述如下： #define MAXQSIZE 100/*顺序循环队列的最大长度*/ typedef struct { Qelemtype base[MAXQSIZE]; /*存放队列元素的数组空间*/ int front; /*头指针，若队列不空，则指向队列头元素*/ 24 int rear; /*尾指针，若队列不空，则指向队列尾元素的下一个存储单元*/ }Sqqueue; 【核心算法提示】 1．顺序循环队列入队操作的基本步骤：首先判断队列是否为满，如果队列满，则函数返回ERROR，否则将待入队的数据元素e存放在尾指针rear所指示的存储单元中，再使尾指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。 2．顺序循环队列出队操作的基本步骤：首先判断队列是否为空，如果队列空，则函数返回ERROR，否则将头指针所指示的队首元素用e返回其值，再使头指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。 【核心算法描述】 status enqueue(Sqqueue &Q,Qelemtype e) /*在循环队列Q中，插入新元素使其成为队尾元素*/ { if ((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; /*若队列满，插入操作不能进行，函数返回ERROR*/ Q.base[Q.rear]=e; /*新元素成为队尾元素*/ Q.rear=(Q.rear+1)%MAXQSIZE;/*利用模运算,“尾指针”加1,使尾指针后移一个位置*/ return OK; } status dequeue(Sqqueue &Q，Qelemtype &e) /*在循环队列Q中，删除Q的队首元素*/ { if (Q.front==Q.rear) return ERROR;/*若队列空，删除操作不能进行，函数返回ERROR*/ e=Q.base[Q.front];/*将队首元素用e保存其值*/ Q.front=(Q.front+1)%MAXQSIZE;/*利用模运算,“头指针”加1,使头指针后移一个位置*/ return OK; } 3．源程序代码参考 #define MAXQSIZE 100 typedef struct { int base[MAXQSIZE]; int front; int rear; } Sqqueue; Sqqueue enqueue(Sqqueue Q,int e)/*队列的入队函数*/ { if ((Q.rear+1)%MAXQSIZE==Q.front) printf(\ else {Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; } 25