五、思考题
1. 实现单链表就地逆置操作。
2. 建立一个循环链表，并且实现插入、删除操作。 3. 建立一个双向循环链表。
4. 建立一个双向循环链表,在双向链表中实现基本操作。 5．用单链表实现两个多项式的和。
6．将两个递增的单链表合并成一个非递减的单链表。
六、报告要求
1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。
2．报告中应书写主要源程序，且源程序中要有注释。
3．报告中应包含运行结果及结果分析。如调试通过，请注明‘通过’并写出输入的数据及运行结果。
4．报告最后包含实验总结和体会。 5．给出时间和空间复杂度分析。
6．如未调试通过或结果不正确，试分析原因，利用课余时间独立完成，完成后方可书写实验报告。
10
实验四 栈的基本操作
实验预备知识：
1．熟练运用线性结构进行数据处理。 2．掌握递归程序设计思想。 3．掌握堆栈的应用背景与场合。 4．理解堆栈的数据类型。
一、实验目的
1．掌握栈的抽象数据类型。
2．掌握实现栈的各种操作的算法。 3．理解栈与递归的关系。
二、实验环境
⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；
三、实验要求
1．用Ｃ描述栈的每种操作在顺序栈或链栈上的实现。
2.将建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素分别定义为5个子函数，通过主函数实现对上述子函数的调用。
四、实验内容
1．在自己的U盘的“姓名+学号”文件夹中创建“实验4”文件夹，本次实验的所有程序
和数据都要求存储到本文件夹中。
2．定义两个堆栈：数据栈和操作栈 3．实现如下堆栈处理函数。
11
4．完成一个表达式求值算法（输入一个复杂表达式，利用数据栈和操作栈进行表达式求值）。
5．具体实验原理参考教材中的表达式求值部分。
五、思考题
1. 结合教材和参考资料理解函数的嵌套调用、递归调用与堆栈的关系。 2．理解Fibonacci数列递归求值中，堆栈的使用情况。
六、报告要求
1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。
2．报告中应书写主要源程序，且源程序中要有注释。
3．报告中应包含运行结果及结果分析。如调试通过，请注明‘通过’并写出输入的数据及运行结果，同时注明堆栈的变化情况。
4．报告最后包含实验总结和体会。
5．如未调试通过或结果不正确，试分析原因，利用课余时间独立完成，完成后方可书写实验报告。
12
实验五 队列的基本操作
实验预备知识：
1．熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。 2．掌握队列的应用背景与场合。 3．理解队列的数据类型。
一、实验目的
1．掌握队列的抽象数据类型。
2．掌握实现队列的各种操作的算法。
3．掌握队列的链式存贮结构及基本操作，深入了解链队列的基本特性，以便在实际问题背景下灵活运用它们。
二、实验环境
⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；
三、实验要求
1．用Ｃ描述每种操作在链队列上的实现。
2．将建队列、初始化队列、判断队列是否非空、求队列的长度、输出队列的元素分别定义为5个子函数，通过主函数实现对上述子函数的调用。
3. 输入数据：数据域（data）设定为整型。
四、实验内容
1．在自己的U盘的“姓名+学号”文件夹中创建“实验5”文件夹，本次实验的所有程序
和数据都要求存储到本文件夹中。
2．实现如下链队列处理函数。
13
五、思考题
1. 用顺序表实现循环队列。
2．假设每个链表结点表示一个任务，而数据域表示本结点的处理时间。在计算机中 通常采用短作业优先调度算法（时间短的优先处理，再处理过程中不允许打断），现在请你设计一个队列来表示这个处理过程（即所有结点的时间总是按照由小到大的顺序排列，任务处理完成后退出该队列）。
六、报告要求
1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。
2．报告中应书写主要源程序，且源程序中要有注释。 3．报告最后包含实验总结和体会。
4．如未调试通过或结果不正确，试分析原因，利用课余时间独立完成，完成后方可书写实验报告。
14