《数据结构与算法》实验指导书
《数据结构与算法》实验指导书
实验1 顺序表
一、实验目的
（1）掌握顺序表的逻辑结构、存储结构及描述方式。 （2）掌握顺序表的定位、插入、删除等操作。
二、实验要求
（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；
（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。
三、实验设备、环境
奔腾以上计算机，装有Turbo C 2.0或Visual C++软件
四、实验步骤及内容
实验步骤：
1．根据题目，编写程序。 2．上机调试通过。
3．按照金陵科技学院实验报告格式，撰写各实验报告。 实验内容：
（1）编写一个函数print_all_data，该函数的作用是逐个输出顺序表中所有数据元素的值。编写主函数，从键盘输入顺序表，调用函数print_all_data，测试结果。
（2）编写顺序表定位操作函数locata，该函数的作用是在顺序表中查找是否存在数据元素的值与变量x的值相等。如果存在满足条件的数据元素，则返回顺序表中和x值相等的第1个数据元素在表中的下标；如果不存在，则返回－1。编写主函数，从键盘输入顺序表，以及变量x的值，调用函数locate，测试结果。
（3）编写一个函数insert，该函数的作用是在递增有序的顺序表中插入一个新结点x，要求保持顺序表的有序性，输出插入前后顺序表状态。编写主函数，从键盘输入顺序表以及变量x的值，调用函数insert，测试结果。
（4）编写一个函数delete，该函数的作用是删除顺序表中所有等于X的数据元素。若顺序表中没有满足条件的数据元素，则输出合适的信息。若有满足条件的数据元素，则输出删除前后顺序表状态。编写主函数，从键盘输入顺序表以及变量x的值，调用函数
153
《数据结构与算法》实验指导书
delete，测试结果。
五、讨论、思考题
1、如何在排列有序的顺序表中插入新元素，而保证顺序表的有序性？ 2、如何在排列有序的顺序表中删除某元素，而保证顺序表的有序性？
实验2 单链表
一、实验目的
（1）掌握单链表的逻辑结构、存储结构及描述方式。 （2）掌握单链表的定位、插入、删除等操作。
二、实验要求
（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；
（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。
三、实验设备、环境
奔腾以上计算机，装有Turbo C 2.0或Visual C++软件
四、实验步骤及内容
实验步骤：
1．根据题目，编写程序。 2．上机调试通过。
3．按照金陵科技学院实验报告格式，撰写各实验报告。 实验内容：
（1）编写函数print_all_data，该函数的作用是逐个输出单链表中所有数据元素的值。编写主函数，从键盘输入单链表的内容，调用函数print_all_data，测试结果。 （2）编写函数insert，在递增有序的单链表中插入一个新结点x，保持单链表的有序性。编写主函数，从键盘输入单链表以及变量x的值，调用函数insert，测试结果。 （3）编写函数，实现带头结点单链表就地逆置的功能，并编写主函数测试结果。
五、讨论、思考题
1、如何在排列有序的单链表表中插入新元素，而保证顺序表的有序性？ 2、如何在排列有序的单链表中删除某元素，而保证顺序表的有序性？
3、如何计算带有头结点的单链表的长度，将计算结果记录在头结点的数据域中？
154
《数据结构与算法》实验指导书
实验3 堆栈和队列
一、实验目的
（1）掌握应用栈解决问题的方法。 （2）掌握利用栈进行表达式求和的算法。
二、实验要求
（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；
（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。
三、实验设备、环境
奔腾以上计算机，装有Turbo C 2.0或Visual C++软件
四、实验步骤及内容
实验步骤：
1． 根据题目，编写程序。 2． 上机调试通过。
3． 按照金陵科技学院实验报告格式，撰写各实验报告。 实验内容：
（1）判断一个算术表达式中开括号和闭括号是否配对。
提示：对表达式进行扫描，凡是遇到‘（’就进栈，遇到‘）’就退掉栈顶的‘（’，表达式被扫描完毕时，栈应为空。此时，开闭括号为配对，否则不配对。
（2）设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系，例如xyzzyx、xyzyx都是中心对称的字符串。要求用尽可能少的时间完成判断。 提示：将一半字符先依次进栈。要考虑字符串长为奇数的情况。
（3）假设算术表达式仅由加减乘除运算符组成，编写一个函数对用后缀表达式表示的算术表达式求值。要求使用顺序堆栈。
五、讨论、思考题
1、如何判断堆栈（顺序栈、链栈）栈满和栈空？
2、如何判断队列（顺序队列、循环队列、链队列）队满和队空？ 3、如何在堆栈（顺序栈、链栈）中压入和弹出元素？
4、如何在队列（顺序队列、循环队列、链队列）中插入和删除元素？
155