《数据结构》实验教案(1-13)

1、数 据 结 构实验报告实验课程： 数据结构 学 号： 2016031124 学生姓名： 郑世林 班 级： 16软件 2017年 月 日实验一 函数与结构体（复习）一、实验目的：巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容：1. 用数组处理Fibonacci数列问题。已知Fibonacci数列：1 1 2 3 5 8 13 21 34 输出数列的前20项。#include<std

2、io.h> int main() int a22,i,n; a0=a1=1; for(i=2;i<21;i+) ai=ai-1+ai-2; printf("%d",a0); for(i=1;i<21;i+) printf(" %d",ai); printf("n"); return 0;2. 下面的程序的功能是：输入三个整数，输出其中最大的数，补足所缺语句。#include <stdio.h>int max(int x,int y); /*函数max的声明*/int max3(int x,int y,in

3、t 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();int max(int x, int y) /*函数功能：返回x、y的最大值*/ return (x>y?x:y);int max3(int x, int y, int z) /*函数功能：返回x、y、

4、z的最大值*/int m; m=max(max(x,y),z); return m;3.学生信息的显示，具体要求如下：1）定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址)；2）设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型；3）设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。提示：可用结构体数组保存学生信息。4. 输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。例如 输入：10 2 30 4 5，逆置后显示为：5 4 30 2 10。四、 程序运行结果和源代码为：此处写程序源代

5、码，请在程序中适当注释，便于老师更快地看懂你的程序。此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。五、实验总结1、收获2、存在的问题实验二 线性表的算法实现一、实验目的：1、掌握线性表的定义方法；2、.掌握线性表基本操作的实现方法；二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、线性表的定义：#define MAX 最大长度值typedef struct dataty

6、pe dataMAX; int last; list;2、线性表的初始化思路：顺序表的初始化就是构造一个空表，或者说是为了给线性表l分配存储空间。由于采用的是静态存储结构（数组），线性表的存储空间是由编译系统分配的，因此，只要对线性表的长度进行初始化即可。3、求线性表的长度4、插入运算思路：在保证所给插入位置i合理的前提下，必须先将第i个及其以后的数据元素，向后移动一个元素的位置，然后才能将新的元素x存入留出的空位置上，插入后使原表长last的长度值加1。5、删除运算思路：在此讨论线性表的删除运算是指将表中第 i 个元素从线性表中去掉，因为是顺序存储结构，在保证所给删除位置i合理的前提下，删除

7、后必须将第i+1个及其以后的元素前移一个位置，最后表的长度减1。6、查找思路：在此讨论线性表的查找是指在线性表中查找与给定值x相等的数据元素。从线性表的第一个元素 l->data1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在线性表中的存储下标；或者查遍整个表都没有找到与 x 相等的元素，返回0。7、线性表元素的输出8、主函数main()程序结构：（1） 声明变量及线性表；（2） 初始化线性表；（3） 输入线性表的元素（提示：用插入算法来实现）；（4） 输出线性表中的元素；（5） 显示线性表的长度；（6） 在线性表中进行元素查找（可提供元素值，也可以提供元素位置）；（7）

8、往线性表中插入数据元素（提供元素值及位置）；（8） 删除线性表中的数据元素（提供元素值或位置）；（9） 输出线性表中最后的结果。四、 程序运行结果和源代码为：五、实验总结：1、收获2、存在的问题实验三 线性表的应用一、实验目的：1、进一步掌握线性表的定义方法；2、进一步掌握线性表基本操作的实现方法；3、掌握线性表的应用。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、有两个线性表la和lb，类型为list。编写一个算法

9、将它们合并成一个线性表la ，要求将lb接到la的后面，并且要求lb中的元素在la中已存在，则不把该元素合进去。算法思路：把线性表la和lb的长度分别赋给n和m；从lb中的第一个元素起，对每一个元素与la中的每一个元素进行查找比较，若未找到则将这个lb元素插入到la表尾，否则继续比较下一个，直到lb中所有元素比较完，则合并完成；并应保证la表足够长。2、已知一个线性表la中的元素已按升序排列，其类型为list。编写一个算法将该线性表中的重复元素删除（即在表中不能有相同的元素）。算法思路：由于线性表la中的元素已按升序排列，所以值相同的元素必为相邻的元素，因此依次比较相邻的两个元素，若值相等，则

10、删除其中的一个，否则继续向后比较，直到表尾。3、有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此址到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。4、主函数main()程序结构：（1） 声明变量及线性表；（2） 初始化线性表；（3） 输入线性表的元素（提示：用插入算法来实现）；（4） 输出线性表中的元素；（5） 对两个线性表进行按升序合并（6） 输出合并后线性表中元素。四、 程序

11、运行结果和源代码为：五、实验总结：1、收获2、存在的问题实验四 栈的实现一、实验目的：1、理解栈的线性结构的特点；2、掌握栈的顺序表示；2、掌握栈基本操作的实现方法；3、能够应用栈设计算法解决实际问题。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、栈的定义：#define MAX 栈中允许存放元素的最大个数typedef struct datatype dataMAX; int top;stack;2、栈的基本算法的

12、实现 栈初始化：init(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,而转换

13、后的八进制数是km km-1k3 k2 k1，从结果看恰好与计算过程相反，因此转换过程中每得到一位八进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。此种方法同样适用于将十进制数转换为r进制的数。把十进制整数11转换为八进制的过程如下：（1）定义“栈”的结构（2）实现“栈”的基本操作栈初始化操作InitStack进栈操作Push出栈操作Pop判断栈是否为空操作Empty（3）实现主程序main()主程序主要是用来控制程序的执行过程，实现数制的转换操作，以及输入、输出。程序结构：声明变量及栈；初始化栈；输入要转换的十进制数；进行进制转换，余数入栈，商作为被除数继续运算；显示转换后的八进制数（

14、利用出栈）。（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时对s1进行操作，否则对s2进行操作。当top2=top1+1表示栈满，都不能进栈，当top1=0时s1不能出栈，而top2=m+1时s2不能出栈。四、 程序运行结果和源代码为：五、实验总结：1、收获2、存在的问题实验五 栈的应用

15、和队列的实现一、实验目的：1、理解栈和队列的定义及线性存储；2、掌握栈和队列的运算方法；3、了解循环队列的定义及相关算法；3、能够应用栈和队列设计算法，解决实际问题。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、队列的定义：#define MAX 队列的最大容量typedef struct datatype dataMAX; int f,r; queue;2、队列的基本算法的实现（1）队列初始化：init(q)（2）

16、入队操作：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)3、利用栈结

17、构实现“算术表达式”问题要求：输入的一个十进制数，能够转换成相应的八进制数，并输出。思路：1、先将输入的中缀表达式，存入字符数组a中，取出a数组中的每一个字符存于c变量中，对于每一个c变量的值做如下处理： 若c为数字，则存于数组b中； 若c为左括号'('，则将其压入栈s; 若c为右括号')'，则将栈s中左括号'('以后的运算符依次出栈，存于数组b中，然后将左括号'('出栈； 若c为'+'或'-'，则将栈s中左括号'('以后的所有运算符依次出栈，存于数组b中，然后将c压入栈s中； 若c

18、为'*'或'/'，则将栈s中的栈顶端连续的'*'或'/'出栈，存于数组b中，然后将c压入栈s中 若c为'='，则将栈S中的所有运算符依次出栈，存于数组b中，然后将c存于数组b中，最后得到的后缀表达式存储在字符数组b中。2、后缀表达式求值具体思路：需要一个存放数值的栈s1，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时栈顶存放的值就是后缀表达式的结果。4、主程序主要是用来控制程序的执行过程。四、 程序运行结果和源

19、代码为：五、实验总结：1、收获2、存在的问题实验六八 链表的建立及应用、链栈及链队列一、实验目的：1、理解单链表的定义及存储结构；2、掌握单链表的基本运算方法；3、了解链栈和链队列的应用方法；4、能够应用单链表设计算法，解决实际问题。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。单链表的定义：typedef struct node datatype data; struct node *next; linklist ;1

20、、利用首插法和尾插法实现单链表的创建。2、单链表的插入运算。 要求： 在单链表的第i个元素之前插入一个元素x。实现思想：（1）找到第i-1个元素（2）在i-1个元素之后插入x3、在单链表中按值查找。算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的地址，否则继续向后查找，直到链表结束为止。找不到时返回空。4、单链表的删除运算。（1）在指定位置删除。要求：删除单链表的第i个元素实现思想：1、找到第i-1个元素；2、删除第i个元素。（2）根据所给条件找到位置再进行删除。5、试写一算法求带头结点的单链表L的长度。思路：单链表的长度是指单链表中结点的个数。求单链表表长的

21、基本操作是移动指针，将指针从表头移动到表尾。在指针移动过程中，累计扫描过的结点数即为表长。由此需要设一个指针p，顺链向后移动；还要设一个整型变量j，作为计数器。指针p的初始值指向头结点，计数器j的初始值为0。程序参考：int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向头结点*/ int j=0; while (p->next) p=p->next; j+ /* p所指的是第 j 个结点*/ return j;6、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值为x的结点插人表中，使L仍然有序。 7、试写一

22、算法对带头结点的单链表实现就地逆置。算法描述：（1）空表或长度为1的表不做任何处理（2）长度大于等于2时，做如下处理：从表中第二个结点开始，依次取原链表中的结点，将其作为第一个结点插入到新链表中去。8、编程序判断一个字符序列是否是回文，要求采用链式队列和链式堆栈。算法提示：设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。四、 程序运行结果和源代码为：五、实验总结：1、收获2、存在的问题实验九十 二叉树的建立及遍历一、实验目的：1、熟悉二叉链表表示的二叉树结

23、构及其递归遍历；2、掌握建立二叉链表要领；3、理解递归遍历二叉链表的执行路径；4、掌握二叉树的中序遍历的非递归思路；了解二叉树的后序遍历的非递归思路5、能利用二叉树的遍历策略解决实际问题；6、了解哈夫曼编码的思路及方法。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。二叉树的二叉链表存储表示可描述为：typedef struct bitnode elemtype data; struct bitnode *lchild,*

24、rchild; /*左、右孩子指针*/ bintree;1、建立一颗二叉链表表示的二叉树。思路：先将二叉树通过加入虚节点的方式使其完全化，然后按层将其输入。可以用二叉树中不会出现字符表示虚节点例如#，用例二叉树如图1所示。图1输入该二叉链表时，应按如下顺序：AB#DE#C#。2、对其进行先序，中序，后序输出。（用递归方法实现）（1）先序遍历（2）中序遍历（3）后序遍历3、实现二叉树的中序遍历的非递归算法。提示：二叉树以二叉链表存放，一维数组stackMAX用以实现栈，变量top用来表示当前栈顶的位置。 4、统计二叉树中叶结点的数目算法思想：（1）若二叉树为空，则它的叶结点的数目为0（2）若二叉

25、树只有一个结点，则它的叶结点的数目为1（3）否则，它的叶结点的数目等于左子树的叶结点的数目和右子树叶结点的数目之和。5、求二叉树的深度算法思想：（1）若二叉树为空，则它的深度等于0（2）否则，它的深度等于左子树和右子树中的最大深度加1。6、在二叉树中查找数据元素算法思想：在二叉树中查找数据元素x。查找成功时返回该结点的指针；查找失败时返回空指针。 7、实现哈夫曼编码实现哈夫曼编码的算法可分为两大部分： （1）构造哈夫曼树；（2）在哈夫曼树上求叶子结点的编码。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶 子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而

26、得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。可以设置一结构数组huffcode用来存放各字符的哈夫曼编码信息，数组元素的结构如下：bitstart其中，分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在huffcodei.bit中的从huffcodei.start到n的分量上。 8、完成知识实践九。四、 程序运行结果和源代码为：五、实验总结：1、收获2、存在的问题实验十一

27、 静态查找一、实验目的：1、加深对查找的理解；2、掌握静态查找表的存储结构；3、掌握顺序查找、二分查找及其查找的算法。4、了解分块查找的思路。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。静态查找表的顺序存储结构 typedef struct elemtype elemMAX; /*数组基址*/ int length; /*表长度*/s_tbl; 静态查找表的链式存储结构 typedef struct node elem

28、type elem; /*结点的值域*/ struct node *next; /*下一个结点指针域*/nodetype;（一）顺序查找算法的实现1、正确设计程序，并编译、链接成可执行文件（1）首先正确写出查找表的结构体 typedef struct SSTable（2）正确写出顺序查找算法 Search_Seq（3）写出主程序 main ，提供输入与输出操作本程序的特点是对于用户给定的一组关键字序列（64，80，13，56，37，92，19，05，88，21，75），采用顺序查找算法找到给定的关键字，并返回其在查找表中的下标。2、进行程序测试直接运行可执行文件，通过不同的值来观察输出结果。（

29、二）折半查找算法的实现1、正确设计程序，并编译、链接成可执行文件（1）首先正确写出查找表的结构体 typedef struct SSTable（2）正确写出折半查找算法 Search_Bin（3）写出主程序 main ，提供输入与输出操作本程序的特点是对于用户给定的一组有序的关键字序列（05，13，19，21，37，56，64，75，80，88，92），采用折半查找算法找到给定的关键字，并返回其在查找表中的下标。2、进行程序测试直接运行可执行文件，通过不同的值来观察输出结果。四、 程序运行结果和源代码为：五、实验总结：1、收获2、存在的问题实验十二十三 排序一、实验目的：1理解排序的定义和各种排序方法的特点，并能灵活运用。2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3.了解各种方法的排序过程及其依据的原则。二、实验要求1、学生提前准备好实验报告，预习并熟悉实验步骤；2、遵守实验室纪律，在规定的时间内完成要求的内容；3、12人为1小组，实验过程中独立操作、相互学习。三、实验内容及思路：要求：将调试好的代码存放到各算法的空白处。1、对于给定的整数序列（49，38，65，97，76，13，27，49），实现直接插入排序。思路：将Ri插入