数据结构试验指导书修订版

1、数据结构 实验指导书郑州轻工业学院2016.02.20目录、八前言实验 01 顺序表的基本操作 5实验 02 单链表的基本操作 13实验 03 栈的基本操作 21实验 04 队列的基本操作 23实验 05 二叉树的基本操作 25实验 06 哈夫曼编码 26实验 07 图的两种存储和遍历 28实验 08 最小生成树、拓扑排序和最短路径 31实验 09 二叉排序树的基本操作 33实验 10 哈希表的生成 34实验 11 常用的内部排序算法 35附：实验报告模板 错 误！未定义书签。3数据结构 是计算机相关专业的一门核心基础课程，是编译原理、 操作系统、 数据库系统及其 它系统程序和大型应用程序开发

2、的重要基础， 也是很多高校考研专业课之一。它主要介绍线性结构、 树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算 法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中 的表示、存储和运算， 培养学生能够设计有效表达和简化算法的数据结构， 从而提高其程序设计能力。 通过学习，要求学生能够掌握各种数据结构的特点、 存储表示和典型算法的设计思想及程序实现，能 够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的 学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，

3、通过算 法设计和上机实践的训练， 能够培养学生的数据抽象能力和程序设计能力。 学习这门课程，习题和实 验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能 否学好数据结构的关键。为了更好地配合学生实验，特编写实验指导书。一、实验目的本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念 和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从 实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学 习、大型软件的开发、实际工程问题打下良好的软件开发基础。二、实验要求1、每

4、次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。3、实验结束后总结实验内容、书写实验报告。4、遵守实验室规章制度、不缺席、按时上、下机。5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取 消本次上机资格，平时成绩扣 10 分。6、实验报告有一次不合格，扣 5 分，两次以上不合格者，平时成绩以零分记。三、实验环境VC+6.0 或其他 C+ 相关的编译环境。四、说明1、本实验的所有算法中元素类型应根据实际需要合理选择。2、实验题目中带者为较高要求，学生可自选；其余部分为基本内容，应尽量完

5、成 （至少完成 70%，否则实验不合格）。3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在 学习过程中注意各种算法的理解，以便为考研做一定的准备。4、好的算法决定了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据 结构，因此数据结构是有效进行程序设计的基础，是每个程序员的必修课。五、实验报告的书写要求1、明确实验的目的及要求。2、记录实验的输入数据和输出结果。3、说明实验中出现的问题和解决过程。4、写出实验的体会和实验过程中没能解决的问题。5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h 中，对应的函数实现存放在

6、源文件 *.c 中； main（） 函数存放在另一个源文件中，该文件包含头文件*.h 即可。六、成绩考评办法1、期末考试占 70 分，闭卷。2、平时考评占 30 分。其中实验环节占 20 分（实验准备、上机、报告、验收等） ；平时占 10 分 （出勤、作业、测验等） 。七、参考书目1、 数据结构（C语言版）严蔚敏等 清华大学出版社。2、 数据结构题集（C 语言版） 严蔚敏等 清华大学出版社。3、数据结构与算法分析 C 语言描述 ，Mark Allen Weiss 著，机械工业出版社， 2012。实验 01 顺序表的基本操作实验学时 ：2 学时 实验类型： 上机 背景知识 ：顺序表的插入、删除及

7、应用。目的要求 ：1掌握顺序存储结构的特点。2掌握顺序存储结构的常见算法。实验内容：编写一个完整的程序，实现顺序表的生成、插入、删除、输出等基本运算。（ 1） 建立一个顺序表，含有 n 个数据元素。（ 2） 输出顺序表。（ 3） 在顺序表中删除值为 x 的结点或者删除给定位置 i 的结点。（ 4） 实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。（ 5） 输入整型元素序列，利用有序表插入算法建立一个有序表。（6）*利用算法5建立两个非递减有序表 A和B,并把它们合并成一个非递减有序表C。（ 7）在主函数中设计一个简单的菜单，分别测试上述算法。（ 8）* 综合训练：利用顺序表实现

8、一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。实验说明：1请构建多文件程序，算法 1至算法 6对应的函数原型声明存放在头文件 SqList.h 中， 对应的 函数实现存放在源文件 SqList.c中；main（）函数存放在另一个源文件中，该文件包含头文件SqList.h即可。2类型定义#define MAXSIZE 100/表中元素的最大个数typedef int ElemType; /元素类型typedef structElemType *elem; /线性表int length;/表的实际长度int listsize; /当前分配的存储容量SqList;/顺序表的类型名53建

9、立顺序表时可利用随机函数自动产生数据。注意问题：1、 插入、删除时元素的移动原因、方向及先后顺序。2、 理解函数形参与实参的传递关系。部分源代码：DS.h#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;SqList.h#ifndef SQLIST_H_INCLUDED#define SQLIST_H_I

10、NCLUDED#include "DS.h"typedef int ElemType;typedef structElemType *elem;int length;int listsize;SqList;void menu();Status InitList_Sq(SqList &L, int n);/* 初始化顺序表 */Status CreateList_Sq(SqList &L);/* 建立顺序表 */void PrintList_Sq(SqList L);/* 输出顺序表 */Status DeleteList_Sq(SqList &L,i

11、nt i,ElemType &e);/* 删除第 i 个元素 */Status DeleteListX_Sq(SqList &L,ElemType x);/* 删除值为 x 的元素 */Status AdjustList_Sq(SqList &L);/* 奇数排在偶数之前 */Status OrderList_sq(SqList &L, int n);/* 插入法生成递增有序表 */void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/* 两个非递减有序表 A 和 B ，并把它们合并成一 个非递减有序

12、表 C*/ #endif / SQLIST_H_INCLUDEDSqList.cpp#include "SqList.h" void menu()printf("ttt 顺序表基本操作 nn");printf("ttt1. 建 立 顺 序 表 n"); printf("ttt2. 遍 历 顺 序 表 n");printf("ttt3. 删除 第 i 个 元 素 n"）;printf("ttt4. 删 除 值 为 x 的 元 素 n"); printf("ttt5.

13、奇 数 排 在 偶 数 之 前 n");printf("ttt6. 插 入 法 生 成 递 增 有 序 表 n");printf（"ttt7. 两个非递减有序表 La 和 Lb 合并成非递减有序表 Lcn"）;printf("ttt0. 退出 nn");/* 初始化顺序表 */Status InitList_Sq(SqList &L, int n)L.elem=(ElemType*)malloc(n*sizeof(ElemType);if(!L.elem) exit(OVERFLOW);L.length=0;L.li

14、stsize=n;return OK;/* 建立顺序表 */Status CreateList_Sq(SqList &L)int n, i;printf(" 请输入顺序表长度： ");scanf("%d", &n);if(InitList_Sq(L, n)printf(" 请输入 %d 个元素： ", n);for(i = 0; i < n; i+)scanf("%d", &L.elemi);L.length+;return OK;elsereturn ERROR;/* 输出顺序表 *

15、/void PrintList_Sq(SqList L)int i;printf(" 顺序表中元素为： n");for(i = 0; i < L.length; i+)printf("%d ", L.elemi);printf("n");/*删除第 i 个元素*/Status DeleteList_Sq(SqList &L,int i,ElemType &e) ElemType *p, *q;if( (i<1) | (i>L.length) ) return ERROR;p = &(L.ele

16、mi-1);e = *p;q = L.elem+L.length-1;for(+p; p <= q; +p) *(p-1) = *p;-L.length;return OK;/*删除值为 x 的元素，删除成功返回 OK ，删除失败返回 ERROR*/Status DeleteListX_Sq(SqList &L,ElemType x)ElemType *p, *q;/* 奇数排在偶数之前 */Status AdjustList_Sq(SqList &L)ElemType *p, *q;int temp;return OK;/*插入法生成递增有序表，有序表生成成功返回OK

17、，失败返回 ERROR*/Status OrderList_sq(SqList &L, int n)int i, j, x; /*x 表示每次待插入的元素 */*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc )ElemType *pa, *pb, *pc, *pa_last, *pb_last;pa = La.elem; pb = Lb.elem;Lc.listsize = Lc.length = La.length+Lb.length;pc = Lc.elem

18、= (ElemType *)malloc(Lc.listsize * sizeof(ElemType);if (!Lc.elem) exit (OVERFLOW);pa_last = La.elem + La.length - 1;pb_last = Lb.elem + Lb.length - 1;while (pa <= pa_last && pb <= pb_last)if (*pa <= *pb) *pc+ = *pa+;else *pc+ = *pb+;while(pa <= pa_last) *pc+ = *pa+;while(pb <=

19、 pb_last) *pc+ = *pb+;main.cpp#include "SqList.h"int main()int choice, n, i, x;SqList L, La, Lb, Lc;while(1)menu();printf(" 选择你的操作： ");scanf("%d",&choice);switch(choice)case 1:if(CreateList_Sq(L)printf(" 顺序表创建成功 n"); elseprintf(" 顺序表创建失败 n"); bre

20、ak;case 2:PrintList_Sq(L);break;case 3:printf(" 请输入删除元素的位置： "); scanf("%d", &i);if(DeleteList_Sq(L, i, x)printf(" 被删除元素值为： %dn",x); elseprintf(" 删除失败 n");break;case 4:printf(" 请输入删除元素值： ");scanf("%d", &x);if(DeleteListX_Sq(L, x)prin

21、tf(" 删除成功 n"); elseprintf(" 删除失败 n");PrintList_Sq(L);break;case 5:AdjustList_Sq(L);printf(" 新链表为： n");PrintList_Sq(L);break;case 6:printf(" 请输入顺序表长度： ");scanf("%d", &n);if(OrderList_sq(L, n)printf(" 值有序顺序表为： n");PrintList_Sq(L);elseprin

22、tf(" 顺序表创建失败 n");break;case 7:printf(" 请输入顺序表 La 的长度： ");scanf("%d", &n);OrderList_sq(La, n);printf(" 请输入顺序表 Lb 的长度： "); scanf("%d", &n);OrderList_sq(Lb, n);MergeList_Sq(La, Lb, Lc);printf(" 合并后的顺序表为： n");PrintList_Sq(Lc); break;cas

23、e 0:return 0;default:n");printf(" 输入错误，请重新输入 11实验 02 单链表的基本操作实验学时： 2 学时实验类型： 上机背景知识： 单链表的插入、删除及应用。目的要求：1掌握单链表的存储特点及其实现。 2掌握单链表的插入、删除算法及其应用算法的程序实现。实验内容：编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。（ 1） 随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。（ 2） 计算单链表的长度，遍历单链表。（ 3） 把单链表中的元素逆置（不允许申请新的结点空间）。（ 4） 在单链表中删除所有值为偶数的元

24、素结点。（ 5） 编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单链表。（6） * 利用算法 5 建立两个非递减有序单链表，然后合并成一个非递增有序链表。（7） * 利用算法 5 建立两个非递减有序单链表，然后合并成一个非递减有序链表。（ 8） * 利用算法 1 建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。（ 9） * 采用单链表实现一元多项式的存储并实现两个多项式相加并输出结果。（ 10） 在主函数中设计一个简单的菜单，分别调试上述算法。（ 11） * 综合训练：1）利用链表实现一个班级学生信

25、息管理 （数据录入、插入、删除、排序、查找等，并能够 实现将数据存储到文件中）2）约瑟夫环问题：设有 n个人围坐在圆桌周围，从某个位置开始编号为1, 2, 3,，n,坐在编号为 1 的位置上的人从 1 开始报数，数到 m 的人便出列；下一个（第 m+1 个）人又从 1 开始报数,数到 m 的人便是第二个出列的人；如此重复下去,直到最后一个人出列为止,得到 一个出列的编号顺序。例如,当n=8, m=4 时,若从第一个位置数起,则出列的次序为4, 8,5, 2, 1 , 3, 7, 6。试编写程序确定出列的顺序。要求用不带头结点的单向循环链表作为存储 结构模拟此过程,按照出列顺序打印出个人编号。#

26、实验说明：1类型定义typedef int ElemType; / 元素类型typedef struct nodeElemType data;struct node *next;LinkNode, *LinkList;2为了算法实现简单，建议采用带头结点的单链表。注意问题：1重点理解链式存储的特点及指针的含义。2注意比较顺序存储与链式存储的各自特点。3注意比较带头结点、无头结点链表实现插入、删除算法时的区别。4单链表的操作是数据结构的基础，一定要注意对这部分常见算法的理解。部分源代码：DS.h#include <stdio.h>#include <stdlib.h>#i

27、nclude <string.h>#include <math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;LinkList.h#include "DS.h"typedef int Elemtype;typedef struct Node Elemtype data; struct Node *next; Lnode,*LinkList;void menu();Status Init_Linklist(LinkList &L); St

28、atus Creat_Linklist(LinkList &L); void Disp_Linklist(LinkList L); int length_Linklist(LinkList L); void Reverse_Linklist(LinkList L);/*菜单 */* 初始化空表 */* 尾插法建立单链表 */* 单链表遍历 */* 计算单链表长度 */* 单链表逆置 */* 删除值为偶数的结点 */void DelEven_Linklist(LinkList L);19Status Insert_Linklist(LinkList L, int x);Status Cr

29、eatOrder_Linklist(LinkList &L);/*在有序单链表L中插入元素x，链表仍然有序*/*创建非递减有序单链表 */void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc);/* 两个非递减有序单链表Lb 合并成一个非递增有序链表 Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*两个非递减有序单链表 La合并成一个非递减有序链表 Lc*/void Split_Linklist(

30、LinkList La, LinkList &Lb); 全部为偶数 */*链表La按值分解成两个链表，La全部为奇数La 和和 LbLbLinkList.cpp#include "LinkList.h"void menu()printf("ttt单链表基本操作 nn");printf("ttt1.建立单链表 n");printf("ttt2.遍历单链表 n");printf("ttt3.计算链表长 度 n");printf("ttt4.链表逆置 n ”)；printf(&quo

31、t;ttt5.删除偶数节 点 n");printf("ttt6.生成值有序单 链 表 n");printf("ttt7.合并生成降序链表n");printf("ttt8. 合 并 生 成 升 序 链 表 n"); printf("ttt9. 分 解 链 表 n");printf("ttt0. 退 出 nn");/* 初始化空表 */Status Init_Linklist(LinkList &L)L=(LinkList)malloc(sizeof(Lnode);if(!L) r

32、eturn ERROR;L->next=NULL;return OK;/* 尾插法建立单链表 */Status Creat_Linklist(LinkList &L) int x;LinkList p,rear;Init_Linklist(L); rear = L;printf(" 输入 -1 表示输入结束 n");while(scanf("%d",&x),x != -1)p = (LinkList)malloc(sizeof(Lnode); if(!p) return ERROR;p->data = x;rear->n

33、ext = p;rear = p;rear->next = NULL;return OK;/* 单链表遍历 */void Disp_Linklist(LinkList L)LinkList p;p = L->next; while(p)printf("%d ", p->data); p = p->next; printf("n");/* 计算单链表长度 */int length_Linklist(LinkList L)int count = 0; /*count 表示单链表长度 */ LinkList p;return count

34、;/* 单链表逆置 */void Reverse_Linklist(LinkList L)LinkList p, q ;/* 删除值为偶数的结点 */void DelEven_Linklist(LinkList L)LinkList p, q;ERROR*/* 在有序单链表中插入元素，链表仍然有序，插入成功返回OK ，插入失败返回Status Insert_Linklist(LinkList L, int x)/*创建非递减有序单链表，创建成功返回 OK ，创建失败返回 ERROR*/ Status CreatOrder_Linklist(LinkList &L)/*两个非递减有序单链

35、表La和Lb合并成一个非递增有序链表Lc*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc)/*两个非递减有序单链表 La 和 Lb 合并成一个非递减有序链表 Lc*/ void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc)LinkList pa, pb, pc;pa = La->next;pb = Lb->next;pc = Lc = La;while(pa && pb)if(pa->

36、data <= pb->data)pc->next = pa; pc = pa; pa = pa->next;elsepc->next = pb; pc = pb; pb = pb->next;pc->next = pa ? pa : pb; free(Lb);/*链表 La 按值分解成两个链表， La 全部为奇数， Lb 全部为偶数 */ void Split_Linklist(LinkList La, LinkList &Lb)main.cpp#include "LinkList.h"int main()int choi

37、ce, length;LinkList L, La, Lb, Lc;while(1)menu();printf(" 选择你的操作： ");scanf("%d",&choice);switch(choice)case 1:if(Creat_Linklist(L)printf(" 单链表创建成功 n");elseprintf(" 单链表创建失败 n"); break;case 2:Disp_Linklist(L);break;case 3:length = length_Linklist(L);printf(&

38、quot; 单链表长度为： %dn",length); break;case 4:Reverse_Linklist(L);printf(" 逆置后的链表为： n");Disp_Linklist(L);break;case 5:DelEven_Linklist(L);printf(" 新链表为： n");Disp_Linklist(L);break;case 6:if(CreatOrder_Linklist(L)printf(" 值有序链表为： n");Disp_Linklist(L);elseprintf(" 单链

39、表创建失败 n");break;case 7:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeDescend_Linklist(La, Lb, Lc);printf(" 合并后的新链表为： n");Disp_Linklist(Lc); break;case 8:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeAscend_Linklist(La, Lb, Lc);printf(" 合并后的新链表为： n");Disp_Linkli

40、st(Lc); break;case 9:Creat_Linklist(L);Split_Linklist(L, Lb);printf(" 分裂后的新链表为： n");Disp_Linklist(L);Disp_Linklist(Lb);break;case 0:return 0;default:printf(" 输入错误，请重新输入 n");#实验 03 栈的基本操作实验学时： 2 学时实验类型： 上机背景知识 ： 顺序栈、链栈，入栈、出栈。目的要求：1掌握栈的思想及其存储实现。2掌握栈的常见算法的程序实现。实验内容：（ 1）采用顺序存储实现栈的初始化

41、、入栈、出栈操作。（ 2）采用链式存储实现栈的初始化、入栈、出栈操作。（ 3）在主函数中设计一个简单的菜单，分别测试上述算法。（ 4）* 综合训练：1） 堆栈操作合法性：假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态 也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S 和 X 序列，判断该序列是否合法。2）括号匹配检验：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意， 即（） 或（） 等为正确的格式， （） 或（） 等均为不正确格式。输入一个表达式，判断其 中的括号是否能正确

42、匹配。3）表达式转换：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达 式转换为后缀表达式。输入在一行中给出不含空格的中缀表达式，可包含+、-、*、 以及左右括号 （），表达式不超过 20 个字符。在一行中输出转换后的后缀表达式，要求不同对象 （运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。实验说明：1 类型定义顺序栈示例#define MAX 100 / 栈的最大值typedef structSElemType *base；SElemType *top ；21实验 04 队列的基本操作i

43、nt stacksize；SqStack ；链栈示例typedef int ElemType; /元素类型typedef struct snodeSElemType data; struct snode *next;StackNode, *LinkStack;2算法 4 的每个子功能尽可能写成函数形式。注意问题：1重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。 2注意算法 4 的各个函数之间值的传递情况。3栈的算法是后续实验的基础（树、图、查找、排序等）。25实验学时： 2 学时 实验类型： 上机 背景知识 ： 循环队列、链队列，入队、出队。目的要求：1掌握队列的思想及其存储实现。

44、 2掌握队列的常见算法的程序实现。实验内容：（ 1） 采用顺序存储实现循环队列的初始化、入队、出队操作。（ 2） 采用链式存储实现队列的初始化、入队、出队操作。（ 3） 在主函数中设计一个简单的菜单，分别测试上述算法。（ 4） *综合训练：银行排队系统模拟 : 请用一个队列来模拟银行排队系统，队列中存储序号。请设置一个菜单， 包括叫号和排号两个选项。若选择叫号，则输出并删除队首元素；若选择排号，则顺序生成一 个序号，加入队列，并输出该序号和前面有多少人等候。实验说明：1类型定义 循环队列示例 #define MAXQSIZE 100 / 队列的最大长度 typedef struct QElem

45、Type *base ；int front ；int rear；SqQueue ；链队列示例typedef struct QNodeQElemType data;struct QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;注意问题：1重点理解队列的算法思想，能够根据实际情况选择合适的存储结构。 2队列的算法是后续实验的基础（树、图、查找、排序等）。实验 06 哈夫曼编码实验学时： 2 学时实验类型： 上机背景知识 ： 二叉树的存储、建立、遍历及其应用。目的要求：1掌握二叉树的

46、存储实现。2掌握二叉树的遍历思想。 3掌握二叉树的常见算法的程序实现。实验内容：1)从键盘上输入数据，建立二叉链表。2)前序遍历、中序遍历、后序遍历二叉树：递归算法。3)前序遍历、中序遍历、后序遍历二叉树：非递归算法。4)借助队列实现二叉树的层次遍历。5)在主函数中设计一个简单的菜单，分别调试上述算法。6)*综合训练：家族关系查询系统：建立家族关系数据库，可以实现家族成员的添加，可以查询家族成员的双 亲、祖先、兄弟、孩子和后代等信息。实验说明：1类型定义 / 二叉链表存储#define TElemType char / 元素类型typedef struct BiTNodeTElemType d

47、ata;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;注意问题：1注意理解递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法。实验学时： 4 学时实验类型： 综合型实验背景知识 ： 二叉树的应用、哈夫曼树。目的要求：掌握哈夫曼树和哈夫曼编码的基本思想和算法的程序实现。实验内容：( 1)修理牧场：农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N 块木头，每块木头长度为整数 Li 个长度单位，于是他购买了一条很长的、能锯成 N 块的木头，即该木头的长度是 Li 的总和。但是农夫自己没有锯子，请人锯木头

48、的酬金跟这段木头的长度成正比。为简单起见，不妨 就设酬金等于所锯木头的长度。例如，要将长度为 20 的木头锯成长度为 8、7 和 5 的三段，第 一次锯木头花费 20 ，将木头锯成 12 和 8；第二次锯木头花费 12，将长度为 12 的木头锯成 7 和 5，总花费为 32。如果第一次将木头锯成15 和 5，则第二次锯木头花费 15，总花费为 35(大于32)。请编写程序帮助农夫计算将木头锯成 N 块的最少花费。首先输入一个正整数N ( N< 104),表示要将木头锯成N块。接着给出N个正整数Li(Li w 50，表示每段木块的长度。输出一个整数，即将木头锯成N块的最少花费。例如：输入：

49、84 5 1 2 1 3 1 1输出：49* ( 2)压缩软件： 给定一篇文章，只含有英文大小写字母和空格，以 .txt 格式存储，统计该文件中各种字符的频 率，对各字符进行 Huffman 编码，将该文件翻译成 Huffman 编码文件，再将 Huffman 编码文件 翻译成源文件。实验说明：1 参考类型定义/双亲孩子表示法typedef struct 27unsigned int weight;unsigned int parent, lchild, rchild; HTNode, *HuffmanTree;/ 动态分配数组存储哈夫曼树typedef char * * HuffmanCod

50、e; / 动态分配数组存储哈夫曼编码表注意问题：1递归算法的灵活应用。2多级指针的使用。33实验07图的两种存储和遍历实验学时：2学时实验类型：上机背景知识：图的存储、遍历及其应用。目的要求：1 掌握图的存储思想及其存储实现。2 掌握图的深度、广度优先遍历算法思想及其程序实现。实验内容：(1) 键盘输入数据，分别建立一个有向图和一个无向图的邻接表。(2) 输出该邻接表。(3) 在有向图的邻接表的基础上计算各顶点的度，并输出。(4) 采用邻接表存储实现无向图的深度优先遍历。(5) 采用邻接表存储实现无向图的广度优先遍历。(6) 在主函数中设计一个简单的菜单，分别调试上述算法。(7) *综合训练地

51、下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点(包括通道 的端点)上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到 起点？输入格式:输入第一行给出三个正整数，分别表示地下迷宫的节点数N (1<NK 1000,表示通道所有交叉点和端点)、边数M ( MK 3000，表示通道数)和探索起始节点编号 S (节点从1到N编号)。 随后的M行对应M条边(通道)，每行给出一对正整数，分别是该条边直接连通的两个节点 的编号。输出格式：若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边(通道)；否则虽然不能点亮

52、所有节点的灯，但还是输出点亮部分灯的节点 序列，最后输出 0，此时表示迷宫不是连通图。 由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节 点小编号优先的次序访问 （点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。 输入样例：6 8 11 22 33 44 55 66 43 61 5输出样例：1 2 3 4 5 6 5 4 3 2 1实验说明：1类型定义（邻接表存储）#define MAX_VERTEX_NUM 20/顶点最大个数typedef struct ArcNodeintadjvex;struct ArcNode *nextarc;intweig

53、ht; /边的权值ArcNode; /表结点#define VertexType int /顶点元素类型typedef struct VNodeVertexType data;ArcNode *firstarc;VNode, AdjListMAX_VERTEX_NUM; /typedef structAdjList vertices;int vexnum, arcnum; / 顶点的实际数，边的实际数int kind;ALGraph;2上述类型定义可以根据实际情况适当调整。3算法 4、5 分别利用栈、队列实现非递归算法。注意问题：1注意理解各算法实现时所采用的存储结构。2注意区别正、逆邻接。实

54、验 08 最小生成树、拓扑排序和最短路径实验学时： 2 学时实验类型： 上机背景知识 ： 图的存储、遍历及其应用 。 目的要求：掌握图的常见应用算法的思想及其程序实现。实验内容：（1）键盘输入数据，分别建立一个有向图的邻接表和一个无向图的邻接矩阵。（2）输出该邻接表和邻接矩阵。（3）以有向图的邻接表为基础输出它的拓扑排序序列。（4）以无向图的邻接矩阵为基础实现最小生成树的PRIM 算法。（5）以有向图的邻接矩阵为基础实现Dijkstra 算法输出单源点到其它顶点的最短路径。（6）在主函数中设计一个简单的菜单，分别调试上述算法。（7）*综合训练：校园导航1）问题描述： 在给出校园各主要建筑的名称

55、信息及有路线连通的建筑之间的距离（或行进时间）的基础上， 利用校园导航系统计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线。信息。2）设计要求： 文件读入或键盘方式读入校园主要建筑信息及建筑间的距离（或行进时间）创建完地图后，以文件形式保存，以免重复创建。计算出给定的起点到终点之间距离最近（或行进 时间最短）的行进路线，并输出该路线（包括经过哪些建筑）及其总距离（或总行进时间）。 实验说明：1类型定义邻接表存储见实验 07邻接矩阵存储示例#define MAX_VERTEX_NUM 20/顶点最大个数typedef enum DG, DN, UDG , UDN GraphKind

56、;typedef struct ArcCellVRType adj;int weight; /边的权值ArcCell; AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum, arcnum; / 顶点的实际数，边的实际数 GraphKind kind;MGraph;注意问题：注意理解各算法实现时所采用的存储结构。实验 09 二叉排序树的基本操作实验学时： 2 学时 实验类型： 上机 背景知识： 树表查找。目的要求：掌握二叉排序树、 AVL 树的查找、插入、删除、建立算