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

数据结构试验指导书

实验03 栈的基本操作

实验学时:2学时 实验类型:上机

背景知识:顺序栈、链栈,入栈、出栈。

目的要求:

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 队列的基本操作

实验学时:2学时 实验类型:上机

背景知识:循环队列、链队列,入队、出队。

目的要求:

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

联系客服:779662525#qq.com(#替换为@)