10学时 数据结构与算法实验指导书

《数据结构与算法》

实 验 指 导 书

沈阳工程学院信息工程系

目录

实验一：线性表的实现 实验二：顺序栈、链栈的实现 实验三：队列的实现

实验四：二叉树的存储和实现 实验五：图的存储和实现 实验六：常用排序算法的实现 实验七：基本查找算法的实现

3

错误！未定义书签。 错误！未定义书签。

5 6 7 8

实验一：线性表的实现

一、实验目的与要求

1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验环境

安装有Visual C++6.0或其它C编译环境的PC机一台。

三、实验预习与准备

1．复习教材相关章节内容。

2．复习C语言中关于结构体与指针的相关内容。 3．认真阅读实验题目，事先写好程序。

四、实验内容和步骤

实验题目1：实现顺序表各种基本运算的算法。

编写一个程序，实现顺序表的各种基本运算，以下各功能分别用一个函数来实现，并在此基础上设计一个主函数进行验证各函数的正确性：

（1）初始化顺序表L。（必做） （2）输出顺序表L。（必做） （3）输出顺序表L的长度。 （4）判断顺序表L是否为空。 （5）输出顺序表L的第i个元素的值。 （6）输出元素x的位置。

（7）在第i个元素位置上插入x元素。（必做） （8）删除L的第i个元素。（必做） （9）删除L中值为x的元素。

实验题目2：实现单链表各种基本运算的算法。

编写一个程序，实现单链表的各种基本运算，以下各功能分别用一个函数来实现，并在此基础上设计一个主函数进行验证各函数的正确性：

（1）初始化单链表L。（必做） （2）输出单链表L。（必做）

（3）释放单链表L。 （4）输出单链表L的长度。 （5）判断单链表L是否为空。 （6）输出单链表L的第i个元素的值。 （7）输出元素x的位置（或地址）。

（8）在第i个元素位置上插入值为x的元素。（必做） （9）删除L的第i个元素（或值为x的元素）。（必做）

五、实验报告要求

按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。

六、实验注意事项

1．依据线性表的操作，程序中可包含如下函数：

? InitList()：初始化线性表。 ? DestroyList(*L)：释放线性表L。

? ListEmpty(*L)：判断线性表L是否为空表。 ? ListLength(*L)：返回线性表L的长度。 ? DispList(*L)：输出线性表L。

? GetElem(*L,int i)：返回线性表L的第i个元素。

? LocateElem(*L,ElemType e)：在线性表L中查找元素e，若存在，则返回第一个e

在线性表中的位置，若不存在，则返回0。

? ListInsert(*L,int i,ElemType e)：在线性表L中第i个位置上插入元素e。 ? ListDelete(*L,int i)：在线性表L中删除第i个元素。

2．完成两个实验

3．有能力的同学可选做实验中的其他功能。

实验二：二叉树的存储和实现

一、实验目的与要求

1、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 2、掌握如何在内存中创建二叉树。

3、掌握二叉树的各种遍历算法的递归或非递归实现。

二、实验环境

安装有Visual C++6.0或其它C编译环境的PC机一台。

三、实验预习与准备

1．复习教材相关章节内容。

2．认真阅读实验题目，事先写好程序。

四、实验内容和步骤

编写一个程序，建立一个二叉树，并实现以下操作：

实验题目1：以二叉链表作为存储结构，实现二叉树的前序遍历或中序遍历算法的递归算法或非递归算法。（必做）

实验题目2：以二叉链表作为存储结构，编写算法求二叉树的高度（递归和非递归）。（选做）

实验题目3：以二叉链表作为存储结构，编写算法求二叉树的结点个数。（选做） 实验题目4：以二叉链表作为存储结构，编写算法求二叉树的叶子结点个数。（选做） 实验题目5：编写算法实现有二叉树的前序序列和中序序列（或后序序列和中序序列）构造该二叉树。（选做）

实验题目6：以二叉链表作为存储结构，编写二叉树的层序遍历算法。（选做） 实验题目7：编写算法实现哈夫曼树的构造。（选做）

实验题目8：以二叉链表作为存储结构，编写算法输出二叉树。（必做） 实验题目9：以顺序结构作为存储结构，编写构造二叉树的算法。（选做）

五、实验报告要求

按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。

六、实验注意事项

1．尽量试着用非递归的方法实现二叉树的各种遍历算法，以此加强对堆栈和队列的理解和应用。

实验三：图的存储和实现

一、实验目的与要求

1、掌握图的基本存储方法；

2、掌握有关图的操作算法并用高级语言实现； 3、熟练掌握图的两种搜索路径的遍历方法。

二、实验环境

安装有Visual C++6.0或其它C编译环境的PC机一台。

三、实验预习与准备

1．复习教材相关章节内容。

2．认真阅读实验题目，事先写好程序。

四、实验内容和步骤

编程：以图的邻接矩阵或邻接表存储一个图，并实现以下功能： 实验题目1：，对图进行深度优先和/或广度优先遍历。（必做） 实验题目2：求顶点的度（入度或出度）。（选做） 实验题目3：使用普瑞姆算法求最小生成树。（选做） 实验题目4：使用克鲁斯卡尔算法求最小生成树。（选做） 实验题目5：求单源点最短路径。（选做）

五、实验报告要求

按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。

六、实验注意事项

1． 注意不同的存储结构对应的遍历算法的差别。

实验四：常用排序算法的实现

一、实验目的与要求

1、 掌握几种常用的排序算法。 2、 熟悉它们的性能与效率。

二、实验环境

安装有Visual C++6.0或其它C编译环境的PC机一台。

三、实验预习与准备

1．复习教材相关章节内容。

2．认真阅读实验题目，事先写好程序。

四、实验内容和步骤

分别使用希尔排序，快速排序和堆排序对一组数进行排序。

五、实验报告要求

按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。

六、实验注意事项

实验五：基本查找算法的实现

一、实验目的与要求

1、 掌握线性表的二分查找与分块查找算法。 2、 掌握树表的二叉排序树查找方法。 3、 掌握散列表的查找方法。

二、实验环境

安装有Visual C++6.0或其它C编译环境的PC机一台。

三、实验预习与准备

1．复习教材相关章节内容。

2．认真阅读实验题目，事先写好程序。

四、实验内容和步骤

1．实现线性表的二分查找算法。（必做） 2．实现树表的二叉排序树查找。（必做） 3．实现散列表的散列查找方法。（选做）

五、实验报告要求

按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。

六、实验注意事项

1．注意散列函数的构造方法 2．注意处理冲突的各种方法。

本文来源：https://www.bwwdw.com/article/gizd.html