《数据结构与算法实验指导书.》由会员分享，可在线阅读，更多相关《数据结构与算法实验指导书.（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实验指导书数据结构与算法实验指导书实验 1顺序表一、实验目的（ 1）掌握顺序表的逻辑结构、存储结构及描述方式。（ 2）掌握顺序表的定位、插入、删除等操作。二、实验要求（ 1）调试程序要记录调试过程中出现的问题及解决办法；（ 2）给出每个问题的算法或画出流程图；（ 3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验；（ 4）做完实验后给出本实验的实验报告。三、实验设备、环境奔腾以上计算机，装有Turbo C 2.0或 Visual C+ 软件四、实验步骤及内容实验步骤：1根据题目，编写程序。2上机调试通过。3按照金陵科技
2、学院实验报告格式，撰写各实验报告。实验内容：（1）编写一个函数print_all_data ，该函数的作用是逐个输出顺序表中所有数据元素的值。编写主函数，从键盘输入顺序表，调用函数print_all_data ，测试结果。（2）编写顺序表定位操作函数locata ，该函数的作用是在顺序表中查找是否存在数据元素的值与变量x 的值相等。如果存在满足条件的数据元素，则返回顺序表中和x 值相等的第1 个数据元素在表中的下标；如果不存在，则返回1 。编写主函数，从键盘输入顺序表，以及变量x 的值，调用函数locate ，测试结果。（3）编写一个函数insert ，该函数的作用是在递增有序的顺序表中插入一
3、个新结点x，要求保持顺序表的有序性，输出插入前后顺序表状态。编写主函数，从键盘输入顺序表以及变量x 的值，调用函数insert ，测试结果。（4）编写一个函数delete ，该函数的作用是删除顺序表中所有等于X 的数据元素。若顺序表中没有满足条件的数据元素，则输出合适的信息。若有满足条件的数据元素，则输出删除前后顺序表状态。编写主函数，从键盘输入顺序表以及变量x 的值，调用函数153数据结构与算法实验指导书delete ，测试结果。五、讨论、思考题1、如何在排列有序的顺序表中插入新元素，而保证顺序表的有序性？2、如何在排列有序的顺序表中删除某元素，而保证顺序表的有序性？实验 2单链表一、实验目
4、的（ 1）掌握单链表的逻辑结构、存储结构及描述方式。（ 2）掌握单链表的定位、插入、删除等操作。二、实验要求（ 1）调试程序要记录调试过程中出现的问题及解决办法；（ 2）给出每个问题的算法或画出流程图；（ 3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验；（ 4）做完实验后给出本实验的实验报告。三、实验设备、环境奔腾以上计算机，装有Turbo C 2.0或 Visual C+ 软件四、实验步骤及内容实验步骤：1根据题目，编写程序。2上机调试通过。3按照金陵科技学院实验报告格式，撰写各实验报告。实验内容：（1）编写函数print_a
5、ll_data ，该函数的作用是逐个输出单链表中所有数据元素的值。编写主函数，从键盘输入单链表的内容，调用函数print_all_data，测试结果。（2）编写函数insert ，在递增有序的单链表中插入一个新结点x，保持单链表的有序性。编写主函数，从键盘输入单链表以及变量x 的值，调用函数insert ，测试结果。（3）编写函数，实现带头结点单链表就地逆置的功能，并编写主函数测试结果。五、讨论、思考题1、如何在排列有序的单链表表中插入新元素，而保证顺序表的有序性？2、如何在排列有序的单链表中删除某元素，而保证顺序表的有序性？3、如何计算带有头结点的单链表的长度，将计算结果记录在头结点的数据域
6、中？154数据结构与算法实验指导书实验 3堆栈和队列一、实验目的（ 1 ）掌握应用栈解决问题的方法。（ 2 ）掌握利用栈进行表达式求和的算法。二、实验要求（ 1）调试程序要记录调试过程中出现的问题及解决办法；（ 2）给出每个问题的算法或画出流程图；（ 3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验；（ 4）做完实验后给出本实验的实验报告。三、实验设备、环境奔腾以上计算机，装有Turbo C 2.0或 Visual C+ 软件四、实验步骤及内容实验步骤：1 根据题目，编写程序。2 上机调试通过。3 按照金陵科技学院实验报告格式，撰
7、写各实验报告。实验内容：（1 ）判断一个算术表达式中开括号和闭括号是否配对。提示：对表达式进行扫描，凡是遇到 （就进栈，遇到） 就退掉栈顶的 （，表达式被扫描完毕时，栈应为空。此时，开闭括号为配对，否则不配对。（ 2 ）设单链表中存放着 n 个字符，试编写算法，判断该字符串是否有中心对称关系，例如 xyzzyx 、 xyzyx 都是中心对称的字符串。要求用尽可能少的时间完成判断。提示：将一半字符先依次进栈。要考虑字符串长为奇数的情况。（ 3 ）假设算术表达式仅由加减乘除运算符组成，编写一个函数对用后缀表达式表示的算术表达式求值。要求使用顺序堆栈。五、讨论、思考题1、如何判断堆栈（顺序栈、链栈）
8、栈满和栈空？2、如何判断队列（顺序队列、循环队列、链队列）队满和队空？3、如何在堆栈（顺序栈、链栈）中压入和弹出元素？4、如何在队列（顺序队列、循环队列、链队列）中插入和删除元素？155数据结构与算法实验指导书实验 4串、递归算法一、实验目的（ 1 ）掌握串的应用。（ 2 ）掌握递归算法的设计方法。二、实验要求（ 1）调试程序要记录调试过程中出现的问题及解决办法；（ 2）给出每个问题的算法或画出流程图；（ 3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验；（ 4）做完实验后给出本实验的实验报告。三、实验设备、环境奔腾以上计算机，装
9、有Turbo C 2.0或 Visual C+ 软件四、实验步骤及内容实验步骤：1根据题目，编写程序。2上机调试通过。3按照金陵科技学院实验报告格式，撰写各实验报告。实验内容：（1 ）设字符串采用静态数组存储结构。编写输出字符串s 中值等于字符ch 的第一个字符的函数，并用主函数测试结果。（2 ）设字符串采用静态数组存储结构。编写输出字符串s 中值等于字符ch 的所有字符的函数，并用主函数测试结果。（3 ）设字符串采用单字符的链式存储结构，编程删除串s 从位置 i 开始长度为k 的子串。（4 ）测试“汉诺塔”问题。（5 ） Ackerman函数的定义如下：n+1当 m=0 时AKM(m,n)=
10、AKM(m-1,1)当 m0,n=0时AKM(m-1,AKM(m,n-1)当 m0,n0时请写出递归算法。五、讨论、思考题1、串是如何存储的？2、递归算法是如何执行的？156数据结构与算法实验指导书实验 5二叉树一、实验目的（ 1 ）掌握二叉树的生成，以及前、中、后序遍历算法。（ 2 ）掌握应用二叉树递归遍历思想解决问题的方法。二、实验要求（ 1）调试程序要记录调试过程中出现的问题及解决办法；（ 2）给出每个问题的算法或画出流程图；（ 3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验；（ 4）做完实验后给出本实验的实验报告。三、实
11、验设备、环境奔腾以上计算机，装有Turbo C 2.0或 Visual C+ 软件四、实验步骤及内容实验步骤：1根据题目，编写程序。2上机调试通过。3按照金陵科技学院实验报告格式，撰写各实验报告。实验内容：（ 1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。（ 2）求二叉树中叶结点的个数。（3）写出在前序线索二叉树中查找给定结点*P 的前序后继的算法。（4）假设通讯电文由 8 个字母组成，字母在电文中出现的频率分别为：7，19，2，6，32， 3 ， 21， 10 。试为这 8 个字母设计哈夫曼编码。五、讨论、思考题1、二叉树是如何存储的？2、二叉树有哪些遍历算法？这
12、些遍历算法有何特点？3、找出分别满足下面条件的所有二叉树：（ 1）前序序列和中序序列相同；（ 2）前序序列和后序序列相同；（ 3）后序序列和中序序列相同；4、若以二叉链表作存储结构，如何求二叉树高度？提示：用递归的方法。157数据结构与算法实验指导书实验6图一、实验目的（ 1 ）熟练掌握图的基本概念、构造及其存储结构。（ 2 ）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。二、实验要求（ 1）调试程序要记录调试过程中出现的问题及解决办法；（ 2）给出每个问题的算法或画出流程图；（ 3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验；（ 4）做完实验后给出本实验的实验报告。三、实验设备、环境奔腾以上计算机，装有Turbo C 2.0或 Visual C+ 软件四、实验步骤及内容实验步骤：1根据题目，编写程序。2上机调试通过。3按照金陵科技学院实验报告格式，撰写各实验报告。实验内容：1构造一个无向图，要求用邻接矩阵表示存储结构。2对上面构造的无向图，进行深度优先遍历和广度优先遍历，分别输出遍历序列。3构造一个连通网络，分别用 PRIM 算法和 KRUSKAL算法构造该网络的最小生成树。五、讨论、思考题1、图是如何存储的？2、如何从一个无向图的邻接矩阵（或邻接表）中，判断图中有多少条边？任意两个顶点 i 和 j
