《数据结构》实验教案

数据结构

实验报告

实验课程：数据结构

学号：2016031124

学生姓名：

班级：16软件

2017年月日

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验一函数与结构体（复习）

一、实验目的：

巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容：

1.用数组处理Fibonacci数列问题。

已知Fibonacci数列：

112358132134„„输出数列的前20项。

#include<stdio.h>

intmain()

{

inta[22],i,n;

a[0]=a[1]=1;

for(i=2;i<21;i++)

a[i]=a[i-1]+a[i-2];

printf("%d",a[0]);

for(i=1;i<21;i++)

printf("%d",a[i]);

printf("\n");

return0;}

2.下面的程序的功能是：输入三个整数，输出其中最大的数，补足所缺语句。

2

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

#include<stdio.h>

intmax(intx,inty);/*函数max的声明*/

intmax3(intx,inty,intz);/*函数max3的声明*/

voidmain()

{

inta,b,c,m;

printf("请输入三个整数，用逗号隔开：\n");

scanf("%d,%d,%d",&a,&b,&c);/*从键盘接收3个整数*/

m=max3(a,b,c);

printf("Maxis%d\n",m);

getch();

}

intmax(intx,inty)/*函数功能：返回x、y的最大值*/

{

return(x>y?x:y);

}

intmax3(intx,inty,intz)/*函数功能：返回x、y、z的最大值*/

{

intm;

m=max(max(x,y),z);

returnm;

}

3.学生信息的显示，具体要求如下：

1）定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址)；

2）设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型；

3）设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不

少于5人）。

3

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

提示：可用结构体数组保存学生信息。

4.输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元

素值。例如输入：1023045，逆置后显示为：5430210。

四、程序运行结果和源代码为：

此处写程序源代码，请在程序中适当注释，便于老师更快地看懂你的程序。

此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果

不正确是什么原因。

五、实验总结

1、收获

2、存在的问题

4

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验二线性表的算法实现

一、实验目的：

1、掌握线性表的定义方法；

2、.掌握线性表基本操作的实现方法；

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

1、线性表的定义：

#defineMAX最大长度值

typedefstruct

{datatypedata[MAX];

intlast;

}list;

2、线性表的初始化

思路：顺序表的初始化就是构造一个空表，或者说是为了给线性表l分配存储空间。由于采用的是

静态存储结构（数组），线性表的存储空间是由编译系统分配的，因此，只要对线性表的长度进行

初始化即可。

3、求线性表的长度

4、插入运算

思路：在保证所给插入位置i合理的前提下，必须先将第i个及其以后的数据元素，向后移动一个

元素的位置，然后才能将新的元素x存入留出的空位置上，插入后使原表长last的长度值加1。

5、删除运算

思路：在此讨论线性表的删除运算是指将表中第i个元素从线性表中去掉，因为是顺序存储结构，

在保证所给删除位置i合理的前提下，删除后必须将第i+1个及其以后的元素前移一个位置，最后

表的长度减1。

5

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

6、查找

思路：在此讨论线性表的查找是指在线性表中查找与给定值x相等的数据元素。从线性表的第一个

元素l->data[1]起依次和x比较，直到找到一个与x相等的数据元素，则返回它在线性表中

的存储下标；或者查遍整个表都没有找到与x相等的元素，返回0。

7、线性表元素的输出

8、主函数main()

程序结构：

（1）声明变量及线性表；

（2）初始化线性表；

（3）输入线性表的元素（提示：用插入算法来实现）；

（4）输出线性表中的元素；

（5）显示线性表的长度；

（6）在线性表中进行元素查找（可提供元素值，也可以提供元素位置）；

（7）往线性表中插入数据元素（提供元素值及位置）；

（8）删除线性表中的数据元素（提供元素值或位置）；

（9）输出线性表中最后的结果。

四、程序运行结果和源代码为：

五、实验总结：

1、收获

2、存在的问题

6

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验三线性表的应用

一、实验目的：

1、进一步掌握线性表的定义方法；

2、进一步掌握线性表基本操作的实现方法；

3、掌握线性表的应用。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

1、有两个线性表la和lb，类型为list。编写一个算法将它们合并成一个线性表la，要求将lb接到

la的后面，并且要求lb中的元素在la中已存在，则不把该元素合进去。

算法思路：把线性表la和lb的长度分别赋给n和m；从lb中的第一个元素起，对每一个元素与la

中的每一个元素进行查找比较，若未找到则将这个lb元素插入到la表尾，否则继续比较下一个，

直到lb中所有元素比较完，则合并完成；并应保证la表足够长。

2、已知一个线性表la中的元素已按升序排列，其类型为list。编写一个算法将该线性表中的重复

元素删除（即在表中不能有相同的元素）。

算法思路：由于线性表la中的元素已按升序排列，所以值相同的元素必为相邻的元素，因此依次

比较相邻的两个元素，若值相等，则删除其中的一个，否则继续向后比较，直到表尾。

3、有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，

要求C的元素也是从小到大的升序排列。

算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此址

到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、

B两个线性表相加的长度。

7

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

4、主函数main()

程序结构：

（1）声明变量及线性表；

（2）初始化线性表；

（3）输入线性表的元素（提示：用插入算法来实现）；

（4）输出线性表中的元素；

（5）对两个线性表进行按升序合并

（6）输出合并后线性表中元素。

四、程序运行结果和源代码为：

五、实验总结：

1、收获

2、存在的问题

8

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验四栈的实现

一、实验目的：

1、理解栈的线性结构的特点；

2、掌握栈的顺序表示；

2、掌握栈基本操作的实现方法；

3、能够应用栈设计算法解决实际问题。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

1、栈的定义：

#defineMAX栈中允许存放元素的最大个数

typedefstruct

{datatypedata[MAX];

inttop;

}stack;

2、栈的基本算法的实现

⑴栈初始化：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,而转换后的八进制数是kmkm-1„k3k2k1，从结果看恰好与计算过程相反，因此

9

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

转换过程中每得到一位八进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。此种方法同

样适用于将十进制数转换为r进制的数。把十进制整数11转换为八进制的过程如下：

（1）定义“栈”的结构

（2）实现“栈”的基本操作

①栈初始化操作InitStack

②进栈操作Push

③出栈操作Pop

④判断栈是否为空操作Empty

（3）实现主程序main()

主程序主要是用来控制程序的执行过程，实现数制的转换操作，以及输入、输出。

程序结构：

①声明变量及栈；

②初始化栈；

③输入要转换的十进制数；

④进行进制转换，余数入栈，商作为被除数继续运算；

⑤显示转换后的八进制数（利用出栈）。

（4）程序的编译、链接

（5）程序的调试

4、双栈操作

设有两个栈s1和s2共享一个连续的存储空间ds[1]~ds[m]，它们对应的栈顶指针分别是top1和

top2，s1的栈底设在ds[1]处，s2的栈底设在ds[m]处，分别编写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、存在的问题

10

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验五栈的应用和队列的实现

一、实验目的：

1、理解栈和队列的定义及线性存储；

2、掌握栈和队列的运算方法；

3、了解循环队列的定义及相关算法；

3、能够应用栈和队列设计算法，解决实际问题。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

1、队列的定义：

#defineMAX队列的最大容量

typedefstruct

{datatypedata[MAX];

intf,r;

}queue;

2、队列的基本算法的实现

（1）队列初始化：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

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

3、利用栈结构实现“算术表达式”问题

要求：输入的一个十进制数，能够转换成相应的八进制数，并输出。

思路：1、先将输入的中缀表达式，存入字符数组a中，取出a数组中的每一个字符存于c变量中，

对于每一个c变量的值做如下处理：

①若c为数字，则存于数组b中；

②若c为左括号'('，则将其压入栈s;

③若c为右括号')'，则将栈s中左括号'('以后的运算符依次出栈，存于数组b中，然后将

左括号'('出栈；

④若c为'+'或'-'，则将栈s中左括号'('以后的所有运算符依次出栈，存于数组b中，然后将

c压入栈s中；

⑤若c为'*'或'/'，则将栈s中的栈顶端连续的'*'或'/'出栈，存于数组b中，然后将c压入

栈s中

⑥若c为'='，则将栈S中的所有运算符依次出栈，存于数组b中，然后将c存于数组b

中，最后得到的后缀表达式存储在字符数组b中。

2、后缀表达式求值

具体思路：需要一个存放数值的栈s1，当从左向右扫描表达式时，每遇到一个操作数就送入栈中

保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个

表达式结束，这时栈顶存放的值就是后缀表达式的结果。

4、主程序主要是用来控制程序的执行过程。

四、程序运行结果和源代码为：

五、、实验总结：

1、收获

2、存在的问题

12

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验六——八链表的建立及应用、链栈及链队列

一、实验目的：

1、理解单链表的定义及存储结构；

2、掌握单链表的基本运算方法；

3、了解链栈和链队列的应用方法；

4、能够应用单链表设计算法，解决实际问题。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

单链表的定义：

typedefstructnode

{datatypedata;

structnode*next;

}linklist;

1、利用首插法和尾插法实现单链表的创建。

2、单链表的插入运算。

要求：

在单链表的第i个元素之前插入一个元素x。

实现思想：

（1）找到第i-1个元素

（2）在i-1个元素之后插入x

3、在单链表中按值查找。

算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的地址，

否则继续向后查找，直到链表结束为止。找不到时返回空。

13

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

4、单链表的删除运算。

（1）在指定位置删除。

要求：删除单链表的第i个元素

实现思想：1、找到第i-1个元素；2、删除第i个元素。

（2）根据所给条件找到位置再进行删除。

5、试写一算法求带头结点的单链表L的长度。

思路：单链表的长度是指单链表中结点的个数。求单链表表长的基本操作是移动指针，将指针从表

头移动到表尾。在指针移动过程中，累计扫描过的结点数即为表长。由此需要设一个指针p，顺链

向后移动；还要设一个整型变量j，作为计数器。指针p的初始值指向头结点，计数器j的初始值

为0。

程序参考：

intLength_LinkList1(LinkListL)

{Lnode*p=L;/*p指向头结点*/

intj=0;

while(p->next)

{p=p->next;j++}/*p所指的是第j个结点*/

returnj;

}

6、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值为x的结点插

人表中，使L仍然有序。

7、试写一算法对带头结点的单链表实现就地逆置。

算法描述：

（1）空表或长度为1的表不做任何处理

（2）长度大于等于2时，做如下处理：从表中第二个结点开始，依次取原链表中的结点，将其作

为第一个结点插入到新链表中去。

8、编程序判断一个字符序列是否是回文，要求采用链式队列和链式堆栈。

算法提示：设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆

栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列

14

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

是回文，否则就不是回文。

四、程序运行结果和源代码为：

五、、实验总结：

1、收获

2、存在的问题

15

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验九——十二叉树的建立及遍历

一、实验目的：

1、熟悉二叉链表表示的二叉树结构及其递归遍历；

2、掌握建立二叉链表要领；

3、理解递归遍历二叉链表的执行路径；

4、掌握二叉树的中序遍历的非递归思路；了解二叉树的后序遍历的非递归思路

5、能利用二叉树的遍历策略解决实际问题；

6、了解哈夫曼编码的思路及方法。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

二叉树的二叉链表存储表示可描述为：

typedefstructbitnode

{elemtypedata;

structbitnode*lchild,*rchild;

/*左、右孩子指针*/

}bintree;

1、建立一颗二叉链表表示的二叉树。

思路：

先将二叉树通过加入虚节点的方式使其完全化，然后按层将其输入。可以用二叉树中不会出现

字符表示虚节点例如#，用例二叉树如图1所示。

图1

输入该二叉链表时，应按如下顺序：AB#DE###C##。

16

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

2、对其进行先序，中序，后序输出。（用递归方法实现）

（1）先序遍历

（2）中序遍历

（3）后序遍历

3、实现二叉树的中序遍历的非递归算法。

提示：二叉树以二叉链表存放，一维数组stack[MAX]用以实现栈，变量top用来表示当前栈顶的

位置。

4、统计二叉树中叶结点的数目

算法思想：

（1）若二叉树为空，则它的叶结点的数目为0

（2）若二叉树只有一个结点，则它的叶结点的数目为1

（3）否则，它的叶结点的数目等于左子树的叶结点的数目和右子树叶结点的数目之和。

5、求二叉树的深度

算法思想：

（1）若二叉树为空，则它的深度等于0

（2）否则，它的深度等于左子树和右子树中的最大深度加1。

6、在二叉树中查找数据元素

算法思想：

在二叉树中查找数据元素x。查找成功时返回该结点的指针；查找失败时返回空指针。

17

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

7、实现哈夫曼编码

实现哈夫曼编码的算法可分为两大部分：

（1）构造哈夫曼树；

（2）在哈夫曼树上求叶子结点的编码。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回

退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字

符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0，1序列，因此先得

到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。可以设置一结构数组

huffcode用来存放各字符的哈夫曼编码信息，数组元素的结构如下：

bitstart

其中，分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位

置。所以，对于第i个字符，它的哈夫曼编码存放在huffcode[i].bit中的从huffcode[i].start到n的分

量上。

8、完成知识实践九。

四、程序运行结果和源代码为：

五、、实验总结：

1、收获

2、存在的问题

18

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验十一静态查找

一、实验目的：

1、加深对查找的理解；

2、掌握静态查找表的存储结构；

3、掌握顺序查找、二分查找及其查找的算法。

4、了解分块查找的思路。

二、实验要求

1、学生提前准备好实验报告，预习并熟悉实验步骤；

2、遵守实验室纪律，在规定的时间内完成要求的内容；

3、1~2人为1小组，实验过程中独立操作、相互学习。

三、实验内容及思路：

要求：将调试好的代码存放到各算法的空白处。

静态查找表的顺序存储结构

typedefstruct

{elemtypeelem[MAX];/*数组基址*/

intlength;/*表长度*/

}s_tbl;

静态查找表的链式存储结构

typedefstructnode

{elemtypeelem;/*结点的值域*/

structnode*next;/*下一个结点指针域*/

}nodetype;

（一）顺序查找算法的实现

1、正确设计程序，并编译、链接成可执行文件

（1）首先正确写出查找表的结构体typedefstructSSTable

（2）正确写出顺序查找算法Search_Seq

（3）写出主程序main，提供输入与输出操作

本程序的特点是对于用户给定的一组关键字序列（64，80，13，56，37，92，19，05，88，21，

75），采用顺序查找算法找到给定的关键字，并返回其在查找表中的下标。

2、进行程序测试

直接运行可执行文件，通过不同的值来观察输出结果。

19

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

（二）折半查找算法的实现

1、正确设计程序，并编译、链接成可执行文件

（1）首先正确写出查找表的结构体typedefstructSSTable

（2）正确写出折半查找算法Search_Bin

（3）写出主程序main，提供输入与输出操作

本程序的特点是对于用户给定的一组有序的关键字序列（05，13，19，21，37，56，64，75，

80，88，92），采用折半查找算法找到给定的关键字，并返回其在查找表中的下标。

2、进行程序测试

直接运行可执行文件，通过不同的值来观察输出结果。

四、程序运行结果和源代码为：

五、、实验总结：

1、收获

2、存在的问题

20

山东信息职业技术学院实验报告

学号：2016031124姓名：郑世林班级：16软件同组者：

课程名称：数据结构指导老师：武洪萍实验成绩：

实验十二——十三排序

一、实验目的：

1理解排序的定义和各