《《数据结构》实验教案.pdf》由会员分享，可在线阅读，更多相关《《数据结构》实验教案.pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数 据 结 构实验报告数 据 结 构实验报告实验课程：数据结构学号：2016031124学生姓名：实验课程：数据结构学号：2016031124学生姓名：班级：16 软件2017 年月日班级：16 软件2017 年月日山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验一函数与结构体（复习）一、实验目的：一、实验目的：巩固复习前期所学 C 语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、
2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容：三、实验内容：1.用数组处理 Fibonacci 数列问题。已知 Fibonacci 数列：1 1 2 3 5 8 13 21 34输出数列的前 20 项。#includeint main()int a22,i,n;a0=a1=1;for(i=2;i21;i+)ai=ai-1+ai-2;printf(%d,a0);for(i=1;i21;i+)printf(%d,ai);printf(n);return 0;2.下面的程序的功能是：输入三个整数，输出其中最大的数，补足所缺语句。2
3、山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：#include int max(int x,int y);/*函数 max 的声明*/int max3(int x,int y,int z);/*函数 max3 的声明*/void main()int a,b,c,m;printf(请输入三个整数，用逗号隔开：n);scanf(%d,%d,%d,&a,&b,&c);/*从键盘接收 3 个整数*/m=max3(a,b,c);printf(Max is%dn,m);getch();in
4、t max(int x,int y)/*函数功能：返回 x、y 的最大值*/return(xy?x:y);int max3(int x,int y,int z)/*函数功能：返回 x、y、z 的最大值*/int m;m=max(max(x,y),z);return m;3.学生信息的显示，具体要求如下：1）定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址)；2）设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型；3）设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于 5 人）。3山东信息职业技术学院实验报告山东信息职业技术学院实验报
5、告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：提示：可用结构体数组保存学生信息。4.输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。例如 输入：1023045，逆置后显示为：5430210。四、四、程序运行结果和源代码为：程序运行结果和源代码为：此处写程序源代码，请在程序中适当注释，便于老师更快地看懂你的程序。此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。五、实验总结五、实验总结1、收获2、存在的问题4山东信息职业技术学院实验报告山东信息职
6、业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验二线性表的算法实现一、实验目的：一、实验目的：1、掌握线性表的定义方法；2、.掌握线性表基本操作的实现方法；二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、线性表的定义：#define MAX#define MAX最大长度值最大长度值typedef st
7、ructtypedef struct datatype dataMAX;datatype dataMAX;int last;int last;list;list;2、线性表的初始化思路：顺序表的初始化就是构造一个空表，或者说是为了给线性表l 分配存储空间。由于采用的是静态存储结构（数组），线性表的存储空间是由编译系统分配的，因此，只要对线性表的长度进行初始化即可。3、求线性表的长度4、插入运算思路：在保证所给插入位置 i 合理的前提下，必须先将第 i 个及其以后的数据元素，向后移动一个元素的位置，然后才能将新的元素 x 存入留出的空位置上，插入后使原表长 last 的长度值加 1。5、删除运算
8、思路：在此讨论线性表的删除运算是指将表中第 i 个元素从线性表中去掉，因为是顺序存储结构，在保证所给删除位置 i 合理的前提下，删除后必须将第 i+1 个及其以后的元素前移一个位置，最后表的长度减 1。5山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：6、查找思路：在此讨论线性表的查找是指在线性表中查找与给定值 x 相等的数据元素。从线性表的第一个元素l-data1 起依次和 x 比较，直到找到一个与 x 相等的数据元素，则返回它在线性表中的存储下标；或者查遍整个表都没有找到与
9、x 相等的元素，返回 0。7、线性表元素的输出8、主函数 main()程序结构：（1）声明变量及线性表；（2）初始化线性表；（3）输入线性表的元素（提示：用插入算法来实现）；（4）输出线性表中的元素；（5）显示线性表的长度；（6）在线性表中进行元素查找（可提供元素值，也可以提供元素位置）；（7）往线性表中插入数据元素（提供元素值及位置）；（8）删除线性表中的数据元素（提供元素值或位置）；（9）输出线性表中最后的结果。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、实验总结：五、实验总结：1、收获2、存在的问题6山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：20160
10、31124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验三线性表的应用一、实验目的：一、实验目的：1、进一步掌握线性表的定义方法；2、进一步掌握线性表基本操作的实现方法；3、掌握线性表的应用。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、有两个线性表la 和 lb，类型为list。编写一个算法将它们合并成一个线性表la，要求将lb 接到la
11、 的后面，并且要求 lb 中的元素在 la 中已存在，则不把该元素合进去。算法思路：把线性表la 和 lb 的长度分别赋给 n 和 m；从lb 中的第一个元素起，对每一个元素与la中的每一个元素进行查找比较，若未找到则将这个 lb 元素插入到 la 表尾，否则继续比较下一个，直到 lb 中所有元素比较完，则合并完成；并应保证 la 表足够长。2、已知一个线性表 la 中的元素已按升序排列，其类型为 list。编写一个算法将该线性表中的重复元素删除（即在表中不能有相同的元素）。算法思路：由于线性表 la 中的元素已按升序排列，所以值相同的元素必为相邻的元素，因此依次比较相邻的两个元素，若值相等，
12、则删除其中的一个，否则继续向后比较，直到表尾。3、有顺序表 A 和 B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表 C，要求 C 的元素也是从小到大的升序排列。算法思路：依次扫描通过 A 和 B 的元素，比较当前的元素的值，将较小值的元素赋给 C，如此址到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给 C 即可。C 的容量要能够容纳 A、B 两个线性表相加的长度。7山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：4、主函数 main()程序结构：（
13、1）声明变量及线性表；（2）初始化线性表；（3）输入线性表的元素（提示：用插入算法来实现）；（4）输出线性表中的元素；（5）对两个线性表进行按升序合并（6）输出合并后线性表中元素。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、实验总结：五、实验总结：1、收获2、存在的问题8山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验四栈的实现一、实验目的：一、实验目的：1、理解栈的线性结构的特点；2、掌握栈的顺序表示；2、掌握栈基本操作的实现方法；3、能够应用栈设计算法解决
14、实际问题。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、栈的定义：#define MAX#define MAX 栈中允许存放元素的最大个数栈中允许存放元素的最大个数typedef structtypedef struct datatype dataMAX;datatype dataMAX;int top;int top;stack;stack;2、栈的基本算法的实现 栈初始化：i
15、nit(s)构造了一个空栈；判栈空：empty(s)若栈 s 为空栈返回为 1，否则返回为 0；入栈：push(s,x)在栈 s 的顶部插入一个新元素 x，使 x 成为新的栈顶元素；出栈：pop(s)栈 s 的顶部元素从栈中删除；读栈顶元素：get(s)取栈顶元素作为结果返回；置栈空：clear(s)清除栈 s 中的所有元素，使之成为空栈。利用主函数 main()调用上述函数。3、利用栈结构实现“数制转换”问题要求：输入的一个十进制数，能够转换成相应的八进制数，并输出。思路：把十进制数转换为八进制数采用的方法是“除 8 取余”，直到商为 0。依次得到的余数是k1,k2,k3,km,而转换后的八
16、进制数是 km km-1k3 k2 k1，从结果看恰好与计算过程相反，因此9山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：转换过程中每得到一位八进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。此种方法同样适用于将十进制数转换为 r 进制的数。把十进制整数 11 转换为八进制的过程如下：（1）定义“栈”的结构（2）实现“栈”的基本操作栈初始化操作 InitStack进栈操作 Push出栈操作 Pop判断栈是否为空操作 Empty（3）实现主程序 main()主程序主要是用来
17、控制程序的执行过程，实现数制的转换操作，以及输入、输出。程序结构：声明变量及栈；初始化栈；输入要转换的十进制数；进行进制转换，余数入栈，商作为被除数继续运算；显示转换后的八进制数（利用出栈）。（4）程序的编译、链接（5）程序的调试4、双栈操作设有两个栈 s1 和 s2 共享一个连续的存储空间 ds1dsm，它们对应 的栈顶指针分别是 top1 和top2，s1 的栈底设在 ds1处，s2 的栈底设在 dsm处，分别编写 s1 和 s2 的进栈函数 push(ds,x,k)和出栈函数 pop(ds,k)。提示：利用一个变量判断应对 s1 还是 s2 进行操作。算法思路：按提示设当 K=1 时对
18、s1 进行操作，否则对 s2 进行操作。当 top2=top1+1 表示栈满，都不能进栈，当 top1=0 时 s1 不能出栈，而 top2=m+1 时 s2 不能出栈。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、五、实验总结：、实验总结：1、收获2、存在的问题10山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验五栈的应用和队列的实现一、实验目的：一、实验目的：1、理解栈和队列的定义及线性存储；2、掌握栈和队列的运算方法；3、了解循环队列的定义及相关算法；3、
19、能够应用栈和队列设计算法，解决实际问题。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、队列的定义：#define MAX#define MAX 队列的最大容量队列的最大容量typedeftypedefstructstruct datatype dataMAX;datatype dataMAX;int f,r;int f,r;queue;queue;2、队列的基本算法的实现（1）队
20、列初始化：init(q)（2）入队操作：insert(q,x)思路：入队时，首先判队是否满了，队满的条件为：q-r=MAX-1，队满时，不能入队，可以进行溢出错误处理，若可以入队则先将队尾指针后移(q-r+)，再将元素赋给队尾单元。（3）出队操作：delete(q,x)思路：先判队列是否为空，为空时不能出队，若可以出队，则可先将队首元素赋给指定变量（若不需要保留，可以省去这一步），队首指针后移（q-f-）。（4）读队头元素：get(q,x)思路：先判队列是否为空，为空时不能取元素，否则取出队首元素，但队首指针保持不变。（5）判队空操作：empty(q)（6）置队空：clear(q)11山东信息
21、职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：3、利用栈结构实现“算术表达式”问题要求：输入的一个十进制数，能够转换成相应的八进制数，并输出。思路：1、先将输入的中缀表达式，存入字符数组a 中，取出a 数组中的每一个字符存于 c 变量中，对于每一个 c 变量的值做如下处理：若 c 为数字，则存于数组 b 中；若 c 为左括号(，则将其压入栈 s;若 c 为右括号)，则将栈s 中左括号(以后的运算符依次出栈，存于数组b 中，然后将左括号(出栈；若 c 为+或-，则将栈 s 中左括号(以后
22、的所有运算符依次出栈，存于数组 b 中，然后将c 压入栈 s 中；若 c 为*或/，则将栈 s 中的栈顶端连续的*或/出栈，存于数组 b 中，然后将 c 压入栈 s 中若 c 为=，则将栈 S 中的所有运算符依次出栈，存于数组 b 中，然后将 c 存于数组 b中，最后得到的后缀表达式存储在字符数组 b 中。2、后缀表达式求值具体思路：需要一个存放数值的栈 s1，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时栈顶存放的值就是后缀表达式的结果。4、主程序主要是用来控制程序的执行过程。四、四、程
23、序运行结果和源代码为：程序运行结果和源代码为：五、五、实验总结：、实验总结：1、收获2、存在的问题12山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验六八链表的建立及应用、链栈及链队列一、实验目的：一、实验目的：1、理解单链表的定义及存储结构；2、掌握单链表的基本运算方法；3、了解链栈和链队列的应用方法；4、能够应用单链表设计算法，解决实际问题。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12
24、人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。单链表的定义：单链表的定义：typedef struct nodetypedef struct node datatype data;datatype data;struct node*next;struct node*next;linklist;linklist;1、利用首插法和尾插法实现单链表的创建。2、单链表的插入运算。要求：在单链表的第 i 个元素之前插入一个元素 x。实现思想：（1）找到第 i-1 个元素（2）在 i-1 个元素之后插入 x3、在单链表中按值
25、查找。算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于 x，若是，返回该结点的地址，否则继续向后查找，直到链表结束为止。找不到时返回空。13山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：4、单链表的删除运算。（1）在指定位置删除。要求：删除单链表的第 i 个元素实现思想：1、找到第 i-1 个元素；2、删除第 i 个元素。（2）根据所给条件找到位置再进行删除。5、试写一算法求带头结点的单链表 L 的长度。思路：单链表的长度是指单链表中结点的个数。求单链表表长的基本操
26、作是移动指针，将指针从表头移动到表尾。在指针移动过程中，累计扫描过的结点数即为表长。由此需要设一个指针p，顺链向后移动；还要设一个整型变量 j，作为计数器。指针 p 的初始值指向头结点，计数器 j 的初始值为 0。程序参考：intLength_LinkList1(LinkList L)Lnode*p=L;/*p指向头结点*/intj=0;while(p-next)p=p-next;j+/*p所指的是第 j 个结点*/returnj;6、已知带头结点的动态单链表 L 中的结点是按整数值递增排列的，试写一算法将值为 x 的结点插人表中，使 L 仍然有序。7、试写一算法对带头结点的单链表实现就地逆置
27、。算法描述：（1）空表或长度为 1 的表不做任何处理（2）长度大于等于 2 时，做如下处理：从表中第二个结点开始，依次取原链表中的结点，将其作为第一个结点插入到新链表中去。8、编程序判断一个字符序列是否是回文，要求采用链式队列和链式堆栈。算法提示：设字符数组 str 中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列14山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：是回文，否则就不
28、是回文。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、五、实验总结：、实验总结：1、收获2、存在的问题15山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验九十二叉树的建立及遍历一、实验目的：一、实验目的：1、熟悉二叉链表表示的二叉树结构及其递归遍历；2、掌握建立二叉链表要领；3、理解递归遍历二叉链表的执行路径；4、掌握二叉树的中序遍历的非递归思路；了解二叉树的后序遍历的非递归思路5、能利用二叉树的遍历策略解决实际问题；6、了解哈夫曼编码的思路及方法。二、实验要求
29、二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。二叉树的二叉链表存储表示可描述为：二叉树的二叉链表存储表示可描述为：typedef struct bitnodetypedef struct bitnode elemtype data;elemtype data;struct bitnode*lchild,*rchild;struct bitnode*lchild,*rchild;/*/*左、右孩子
30、指针左、右孩子指针*/*/bintree;bintree;1、建立一颗二叉链表表示的二叉树。思路：先将二叉树通过加入虚节点的方式使其完全化，然后按层将其输入。可以用二叉树中不会出现字符表示虚节点例如#，用例二叉树如图 1 所示。图 1输入该二叉链表时，应按如下顺序：AB#DE#C#。16山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：2、对其进行先序，中序，后序输出。（用递归方法实现）（1）先序遍历（2）中序遍历（3）后序遍历3、实现二叉树的中序遍历的非递归算法。提示：二叉树以二
31、叉链表存放，一维数组 stackMAX用以实现栈，变量 top 用来表示当前栈顶的位置。4、统计二叉树中叶结点的数目算法思想：（1）若二叉树为空，则它的叶结点的数目为 0（2）若二叉树只有一个结点，则它的叶结点的数目为 1（3）否则，它的叶结点的数目等于左子树的叶结点的数目和右子树叶结点的数目之和。5、求二叉树的深度算法思想：（1）若二叉树为空，则它的深度等于 0（2）否则，它的深度等于左子树和右子树中的最大深度加 1。6、在二叉树中查找数据元素算法思想：在二叉树中查找数据元素 x。查找成功时返回该结点的指针；查找失败时返回空指针。17山东信息职业技术学院实验报告山东信息职业技术学院实验报告学
32、号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：7、实现哈夫曼编码实现哈夫曼编码的算法可分为两大部分：（1）构造哈夫曼树；（2）在哈夫曼树上求叶子结点的编码。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的 0，1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。可以设置一结构数组huffcode 用来存放各字符的哈夫曼编
33、码信息，数组元素的结构如下：bitstart其中，分量 bit 为一维数组，用来保存字符的哈夫曼编码，start 表示该编码在数组 bit 中的开始位置。所以，对于第 i 个字符，它的哈夫曼编码存放在 huffcodei.bit 中的从 huffcodei.start 到 n 的分量上。8、完成知识实践九。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、五、实验总结：、实验总结：1、收获2、存在的问题18山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验十一静态查找
34、一、实验目的：一、实验目的：1、加深对查找的理解；2、掌握静态查找表的存储结构；3、掌握顺序查找、二分查找及其查找的算法。4、了解分块查找的思路。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。静态查找表的顺序存储结构静态查找表的顺序存储结构typedef structtypedef struct elemtype elemMAX;elemtype elemMAX;/*/*数组基址数组
35、基址*/*/int length;int length;/*/*表长度表长度*/*/s_tbl;s_tbl;静态查找表的链式存储结构静态查找表的链式存储结构typedef struct nodetypedef struct node elemtype elem;elemtype elem;/*/*结点的值域结点的值域*/*/struct node*next;struct node*next;/*/*下一个结点指针域下一个结点指针域*/*/nodetype;nodetype;（一）顺序查找算法的实现1、正确设计程序，并编译、链接成可执行文件（1）首先正确写出查找表的结构体 typedef str
36、uct SSTable（2）正确写出顺序查找算法 Search_Seq（3）写出主程序 main，提供输入与输出操作本程序的特点是对于用户给定的一组关键字序列（64，80，13，56，37，92，19，05，88，21，75），采用顺序查找算法找到给定的关键字，并返回其在查找表中的下标。2、进行程序测试直接运行可执行文件，通过不同的值来观察输出结果。19山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：（二）折半查找算法的实现1、正确设计程序，并编译、链接成可执行文件（1）首先正确
37、写出查找表的结构体 typedef struct SSTable（2）正确写出折半查找算法 Search_Bin（3）写出主程序 main，提供输入与输出操作本程序的特点是对于用户给定的一组有序的关键字序列（05，13，19，21，37，56，64，75，80，88，92），采用折半查找算法找到给定的关键字，并返回其在查找表中的下标。2、进行程序测试直接运行可执行文件，通过不同的值来观察输出结果。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、五、实验总结：、实验总结：1、收获2、存在的问题20山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：
38、郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：实验十二十三排序一、实验目的：一、实验目的：1 理解排序的定义和各种排序方法的特点，并能灵活运用。2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3.了解各种方法的排序过程及其依据的原则。二、实验要求二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12 人为 1 小组，实验过程中独立操作、相互学习。三、实验内容及思路：三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、对于给定的整数序列（4949，3838，6565，9797，
39、7676，1313，2727，4949），实现直接插入排序。思路：将 Ri插入到有序表 R1.i-1中，进行如下操作：（1）暂存记录 Ri，即 R0=Ri（2）用顺序查找的方法对有序表进行倒序扫描，并将关键字大于 R0的记录后移，直到找到一个记录 Rj，其关键字小于 R0结束（3）将记录 R0存于 Rj+1中2、对于给定的整数序列（4949，3838，6565，9797，7676，1313，2727，4949），实现折半插入排序。思路：折半查找时，将待插入记录的关键字和处于有序序列中间位置记录的关键字比较，若待插入的记录关键字小于有序序列中间位置记录的关键字，则 high=mid-1；否则，l
40、ow=mid+1。依此查找下去，直到 lowhigh 时，由折半查找得到的插入位置为 low 或 high+1。3、对于给定的整数序列（4949，3838，6565，9797，7676，1313，2727，4949），实现冒泡排序。思路：每趟排序都从头开始扫描待排记录的序列，并按顺序依次比较相邻两个记录关键字的大小，若与排序要求相逆，则将两者交换。不断将相邻的两记录中关键字大的记录向后移动，最后将待排记录序列中的关键字最大的记录换到待排序列的末尾。通过第一趟排序，将最大关键字记录移动到第 n 个位置，然后进行第二趟排序，这趟只需对前n-1 个记录进行同样的操作，使次大的记录放在第 n-1 个位
41、置，重复此过程直到排好序为止。若在某一趟排序的过程中，没有发现一个逆序，则排序过程结束。所以冒泡排序最多进行 n-1 趟。21山东信息职业技术学院实验报告山东信息职业技术学院实验报告学号：2016031124姓名：郑世林 班级：16 软件同组者：课程名称：数据结构指导老师：武洪萍实验成绩：4、对于给定的整数序列（4949，3838，6565，9797，7676，1313，2727，4949），实现选择排序。思路：第一趟，从 n 个记录中找出关键字最小的记录与第一个记录交换；第二趟，从第二个记录开始的 n-1 个记录中再选出关键字最小的记录与第二个记录交换；如此，第 i 趟，则从第 i 个记录开
42、始的 n-i+1 个记录中选出关键字最小的记录与第 i 个记录交换，直到整个序列按关键字有序排列。5、对于给定的整数序列（4949，3838，6565，9797，7676，1313，2727，4949），实现快速排序。思路：通过比较关键字、来交换记录，以某个记录的关键字为基准（一般选取第一个记录的关键字为基准），将待排序列分成两部分。其中前一部分所有记录的关键字小于等于基准关键字，而后一部分所有记录的关键字大于等于基准关键字。将待排序列按基准关键字为界分成两部分的过程，称为一次划分。对各部分不断进行划分，直到整个序列按关键字有序，则排序完成。四、四、程序运行结果和源代码为：程序运行结果和源代码为：五、五、实验总结：、实验总结：1、收获2、存在的问题22