《数据结构实验指导书》

第一部分 上机实践

（4）程序运行结果：

四、实验总结

-11-

成绩：

第一部分 上机实践

实验二 栈与队列

实验时间： 月 日

一、实验目的

1．掌握栈的存储实现方式及其基本操作的实现； 2．掌握队列的存储实现方式及其基本操作的实现； 3．进一步掌握利用TC实现数据结构的编程方法。

二、实验题目与要求

1．实验题目一：顺序栈的定义及其操作算法的实现

要求：编程实现顺序栈表的类型定义及顺序表的初始化操作、入栈操作、出栈操作、取栈顶元素操作、输出操作等，并对其进行验证。

2．实验题目二：链式队列的定义及其相关操作算法的实现

要求：编程实现链式队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。

3．实验题目三：循环队列定义及其操作算法的实现

要求：编程实现循环队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。

说明：实验题目一与实验题目三为必做内容；实验题目二为选做内容。

三、实验内容

1.顺序栈的实现

（1）顺序栈的类型及基本操作的定义。将如下代码设计完整，并保存为“sqStack.h”。 ///顺序栈类型及其基本操作的实现 #define Init_Size 100 #define INCR 20 typedef struct

{ SElemType *Elem; int Top;

int StackSize;

}SqStack; //顺序栈类型

Status InitStack(SqStack &S) //初始化操作 { //代码略 }

void ClearStack(SqStack &S) //栈清空操作 { //代码略 }

-12-

第一部分 上机实践

Status StackEmpty(SqStack S) //判空操作 { //代码略 }

int StackLength(SqStack S) //求栈长 { //代码略 }

Status GetTop(SqStack S, SElemType &e) //取栈顶元素操作 { //代码略 }

Status Push(SqStack &S, SElemType e) //入栈操作 { //代码略 }

Status Pop(SqStack &S, SElemType &e) //出栈操作 { //代码略 }

（2）顺序栈应用程序设计

如下给出了利用栈实现10进制数转换为2进制数的程序代码的框架结构。同学还可自行设计其他栈的应用实例，如括号匹配、文本编辑处理等问题。

#include #include \ #include \

typedef int SElemType; //定义元素类型为int类型 #include \void DToB(int n) { SqStack S; SElemType e;

printf(\

if(n==0) {printf(\ InitStack(S); while(n)

{ Push(S,n%2); n/=2; } while(!StackEmpty(S))

{ Pop(S, e); printf(\ } printf(\}

int main() { int n;

printf(\ scanf(\

-13-

第一部分 上机实践

while(n>=0) { DToB(n);

printf(\ scanf(\ }

return 0; }

（3）完整代码 -14-