数据结构实验指导书(1)

数据结构试验指导书

实验03 栈的基本操作

实验学时：２学时 实验类型：上机

背景知识：顺序栈、链栈，入栈、出栈。

目的要求：

1．掌握栈的思想及其存储实现。 2．掌握栈的常见算法的程序实现。

实验内容：

（1） 采用顺序存储实现栈的初始化、入栈、出栈操作。 （2） 采用链式存储实现栈的初始化、入栈、出栈操作。 （3） 在主函数中设计一个简单的菜单，分别测试上述算法。 （4） * 综合训练：

1） 堆栈操作合法性：假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序

列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。 2） 括号匹配检验：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())

或[([][])]等为正确的格式，[(])或([())等均为不正确格式。输入一个表达式，判断其中的括号是否能正确匹配。

3） 表达式转换：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表

达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\\以及左右括号()，表达式不超过20个字符。在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

实验说明：

1．类型定义 顺序栈示例

#define MAX 100 //栈的最大值 typedef struct { SElemType *base； SElemType *top；

19

数据结构试验指导书

int stacksize； }SqStack； 链栈示例

typedef int ElemType; //元素类型 typedef struct snode {

SElemType data;

struct snode *next; }StackNode, *LinkStack;

2．算法4的每个子功能尽可能写成函数形式。

注意问题：

1．重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。 2．注意算法4的各个函数之间值的传递情况。

3．栈的算法是后续实验的基础（树、图、查找、排序等）。

20

数据结构试验指导书

实验04 队列的基本操作

实验学时：２学时 实验类型：上机

背景知识：循环队列、链队列，入队、出队。

目的要求：

1．掌握队列的思想及其存储实现。 2．掌握队列的常见算法的程序实现。

实验内容：

（1） 采用顺序存储实现循环队列的初始化、入队、出队操作。 （2） 采用链式存储实现队列的初始化、入队、出队操作。 （3） 在主函数中设计一个简单的菜单，分别测试上述算法。 （4） *综合训练：

银行排队系统模拟:请用一个队列来模拟银行排队系统，队列中存储序号。请设置一个菜单，包括叫号和排号两个选项。若选择叫号，则输出并删除队首元素；若选择排号，则顺序生成一个序号，加入队列，并输出该序号和前面有多少人等候。

实验说明：

1．类型定义 循环队列示例

#define MAXQSIZE 100 //队列的最大长度 typedef struct { QElemType *base；

int front； int rear； }SqQueue；

链队列示例

typedef struct QNode

{

QElemType data;

21

数据结构试验指导书

struct QNode *next; }QNode, *QueuePtr;

typedef struct { QueuePtr front;

QueuePtr rear; }LinkQueue;

注意问题：

1．重点理解队列的算法思想，能够根据实际情况选择合适的存储结构。 2．队列的算法是后续实验的基础（树、图、查找、排序等）。

22