《数据结构》级实验报告模板Word格式.docx

1、一、实验目的：1掌握VC6.0开发环境下C/C+程序的编辑、编译和运行。 2通过实验回顾复习C语言中关于结构体、指针等知识的应用。3了解学习数据结构的主要方法和课程的主要知识框架。二、实验环境： 个人电脑、Windows XP、VC6.0或以上版本。三、实验内容、程序代码、程序测试运行界面 1设计一个程序，输出所有小于等于n（n为一个大于2的正整数）的素数。要求：（1）每行输出10个素数；（2）尽可能采用较优的算法。2编写一个程序，计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。3编写一个程序，判断一个字符串是否为“回文”（顺读和倒读都一样的字符串称为“回文”），并分析算法的时间复

2、杂度。四、心得体会与建议实 验 报 告（二）线性表的基本操作及其应用1熟练掌握线性表的顺序存储结构的概念及各种基本操作的C语言实现。 2熟练掌握线性表的链式存储结构中的单链表的概念及各种基本操作的C语言实现。3了解双向链表及循环链表的基本操作。1编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为char），并在此基础上设计一个程序完成如下功能：（1）初始化顺序表L；（2）采用尾插法依次插入元素a，b，c，d，e；（3）输出顺序表L；（4）输出顺序表L长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第3个元素；（7）输出元素a的位置；（8）在第4个位置上插入元素f；（9）输出顺

3、序表L；（10）删除L的第3个元素；（11）输出顺序表L；（12）释放顺序表L。程序代码如下：程序运行结果如下：2编写一个程序，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化单链表h；（3）输出单链表h；（4）输出单链表h长度；（5）判断单链表h是否为空；（6）输出单链表h的第3个元素；（9）输出单链表h；（10）删除h的第3个元素；（11）输出单链表h；（12）释放单链表h。3编写一个程序，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化双链表h；（3）输出双链表

4、h；（4）输出双链表h长度；（5）判断双链表h是否为空；（6）输出双链表h的第3个元素；（9）输出双链表h；（11）输出双链表h；（12）释放双链表h。实 验 报 告（三）栈、队列和串的应用1掌握栈的特点（先进后出FILO）及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2掌握队列的特点（先进先出FIFO）及基本操作，如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现。3掌握顺序串和链串的特点及基本操作，如串的插入、求子串、串的输出、串的连接等。1编写一个程序，实现顺序栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序

5、完成如下功能：（1）初始化栈s；（2）判断栈s是否非空；（3）依次进栈元素a，b，c，d，e；（4）判断栈s是否非空；（5）输出栈长度；（6）输出从栈顶到栈底元素；（7）输出出栈序列；（8）判断栈s是否非空；（9）释放栈。2编写一个程序，实现链栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序，完成如下功能：（1）初始化链栈s；（2）判断链栈s是否非空；（3）依次进链栈元素a，b，c，d，e；（4）判断链栈s是否非空；（5）输出链栈长度；（6）输出从链栈顶到栈底元素；（7）输出出链栈序列；（8）判断链栈s是否非空；（9）释放链栈。3编写一个程序，实现链队的各种基本运算（假

6、设队列中元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化链队q；（2）判断链队q是否非空；（3）依次进队元素a，b，c；（4）出队一个元素，并输出该元素；（5）输出链队q的元素个数；（6）依次进链队元素d，e，f；（7）输出链队q的元素个数；（8）输出出队序列；（9）释放链队。4编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个程序，完成如下功能：（1）建立串s=“abcdefghefghijklmn”和串s1=“xyz”（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的

7、5个字符而产生串s2；（7）输出串s2；（8）将串s的第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。5编写一个程序，实现链串的各种基本运算，并在此基础上设计一个程序，完成如下功能：实 验 报 告（四）数组及广义表应用1掌握二维数组的特点及基本操作，为图的邻接矩阵表示做准备。2了解广义表的概念及应用。1以下是一个55阶螺旋方阵。设计一个程序，输出该形式的nn（n10）阶方阵（顺时针方向旋进）。1 2 3 4 516 17 18 19

8、 615 24 25 20 714 23 22 21 813 12 11 10 92如果矩阵A中存在一个元素Aij满足条件：Aij是第i行中值最小的元素，且又是第j列中值最大的元素，则称为该矩阵的一个马鞍点。设计一个程序，计算出mn的矩阵A的所有马鞍点。实 验 报 告（五）树和二叉树的建立和应用1掌握二叉树的逻辑结构和存储结构。2掌握和指针类型描述、访问和处理二叉树的各种运算。3掌握二叉树的各种遍历方法。4掌握哈夫曼树的构造和哈夫曼编码。1编写一个程序，实现二叉树的各种运算，并在此基础上设计一个程序完成如下功能（b为如图所示的一棵二叉树）：（1）输出二叉树b；（2）输出H节点的左、右孩子节点值

9、（3）输出二叉树b的深度；（4）输出二叉树b的宽度；（5）输出二叉树b的节点个数；（6）输出二叉树b的叶子节点个数。2设计一个程序实现二叉树的先序遍历、中序遍历和后序遍历的递归和非递归算法，以及层次遍历的算法。并对图中所示的二叉树b给出求解结果。3设计一个程序构造一棵哈夫曼树，输出对应的哈夫曼编码和平均查找长度。并用下表所示的数据进行验证。实 验 报 告（六）图的建立及应用1掌握图的邻接矩阵和邻接链表存储结构。2掌握图的生成树算法。3掌握计算图的最短路径算法。1编写一个程序，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序实现如下功能：

10、（1）建立如图所示的有向图G的邻接矩阵，并输出；（2）由有向图G的邻接矩阵产生邻接表，并输出；（3）再由（2）的邻接表产生对应的邻接矩阵，并输出；2编写一个程序，实现图的遍历运算，并在此基础上设计一个程序完成如下功能：（1）输出如图的有向图G从顶点0开始的深度优先遍历序列（递归算法）；（2）输出如图的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；（3）输出如图的有向图G从顶点0开始的广度优先遍历序列；3设计一个程序，对于如图所示的无向带权图G采用普里姆算法输出从顶点O出发的最小生成树。实 验 报 告（七）内排序算法的实现1掌握各种排序算法的工作原理。2理解各种内排序算法的时间复杂度和空间复杂度。3对比同一组数据应用不同排序算法的优劣。1设计一个程序实现希尔插入排序算法，并输出9，8，7，6，5，4，3，2，1，0的排序过程2设计一个程序实现二路归并排序算法，并输出18，2，20，34，12，32，6，16，5，8的排序过程3设计一个程序实现基数排序算法，并输出75，23，98，44，57，12，29，64，38，82的排序过程。