《数据结构》实验指导书(修订版)

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业数据结构实验指导书郑州轻工业学院2016.02.20目 录 TOC o 1-3 h z u 前 言数据结构是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计

2、有效表达和简化算法的数据结构，从而提高其程序设计能力。通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写实验指导书。一、实验目的本课程实验主要是为了原理和应用的结

3、合，通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础。二、实验要求1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。4、遵守实验室规章制度、不缺席、按时上、下机。 5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消

4、本次上机资格，平时成绩扣10分。6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。三、实验环境 VC+6.0或其他C+相关的编译环境。四、说明1、本实验的所有算法中元素类型应根据实际需要合理选择。2、实验题目中带者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。4、好的算法决定了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据结构，因此数据结构是有效进行程序设计的基础，是每个程序员

5、的必修课。五、实验报告的书写要求1、明确实验的目的及要求。2、记录实验的输入数据和输出结果。 3、说明实验中出现的问题和解决过程。4、写出实验的体会和实验过程中没能解决的问题。5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h中，对应的函数实现存放在源文件*.c中；main()函数存放在另一个源文件中，该文件包含头文件*.h即可。六、成绩考评办法1、期末考试占70分，闭卷。2、平时考评占30分。其中实验环节占20分（实验准备、上机、报告、验收等）；平时占10分（出勤、作业、测验等）。七、参考书目1、数据结构（语言版） 严蔚敏等 清华大学出版社。 2、数据结构题集 （

6、C语言版） 严蔚敏等 清华大学出版社。 3、数据结构与算法分析C语言描述，Mark Allen Weiss著，机械工业出版社，2012。实验01 顺序表的基本操作实验学时：2学时实验类型：上机背景知识：顺序表的插入、删除及应用。目的要求： 1掌握顺序存储结构的特点。 2掌握顺序存储结构的常见算法。实验内容：编写一个完整的程序，实现顺序表的生成、插入、删除、输出等基本运算。建立一个顺序表，含有n个数据元素。输出顺序表。在顺序表中删除值为x的结点或者删除给定位置i的结点。实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。输入整型元素序列，利用有序表插入算法建立一个有序表。*利用算法5

7、建立两个非递减有序表A和B，并把它们合并成一个非递减有序表C。在主函数中设计一个简单的菜单，分别测试上述算法。*综合训练： 利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。实验说明：1请构建多文件程序，算法1至算法6对应的函数原型声明存放在头文件SqList.h中，对应的函数实现存放在源文件SqList.c中；main()函数存放在另一个源文件中，该文件包含头文件SqList.h即可。2类型定义 #define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType; /元素类型 typedef struct ElemType *ele

8、m; /线性表 int length; /表的实际长度 int listsize; /当前分配的存储容量 SqList; /顺序表的类型名3建立顺序表时可利用随机函数自动产生数据。注意问题：插入、删除时元素的移动原因、方向及先后顺序。理解函数形参与实参的传递关系。部分源代码：DS.h#include #include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;SqList.h#ifndef SQLIST_H_INCLUDED#define SQLIST

9、_H_INCLUDED#include DS.htypedef int ElemType;typedef struct ElemType *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,int i,ElemType &e);/*删除第

10、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，并把它们合并成一个非递减有序表C*/#endif / SQLIST_H_INCLUDEDSqList.cpp#include SqList.hvoid

11、 menu() printf(ttt 顺序表基本操作nn); printf(ttt1.建 立 顺 序 表n); printf(ttt2.遍 历 顺 序 表n); printf(ttt3.删 除 第 i 个 元 素n); printf(ttt4.删 除 值 为 x 的 元 素n); printf(ttt5.奇 数 排 在 偶 数 之 前n); printf(ttt6.插 入 法 生 成 递 增 有 序 表n); printf(ttt7.两个非递减有序表La和Lb合并成非递减有序表Lcn); printf(ttt0.退 出nn);/*初始化顺序表*/Status InitList_Sq(SqLis

12、t &L, int n) L.elem=(ElemType*)malloc(n*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=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+

13、; return OK; else return ERROR;/*输出顺序表*/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( (iL.length) ) return ERROR;p = &(L.elemi-1);e = *p; q = L.elem+L.le

14、ngth-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，失败返回ERROR*/Status OrderList_sq(SqList &L, in

15、t 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 = (ElemType *)malloc(Lc.listsize * sizeof(ElemType)

16、; 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 = pb_last) *pc+ = *pb+;main.cpp#include SqList.hint main() int choice, n,

17、 i, x; SqList L, La, Lb, Lc; while(1) menu(); printf(选择你的操作：); scanf(%d,&choice); switch(choice) case 1: if(CreateList_Sq(L) printf(顺序表创建成功n); else printf(顺序表创建失败n); break; case 2: PrintList_Sq(L); break; case 3: printf(请输入删除元素的位置：); scanf(%d, &i); if(DeleteList_Sq(L, i, x) printf(被删除元素值为：%dn,x); el

18、se printf(删除失败n); break; case 4: printf(请输入删除元素值：); scanf(%d, &x); if(DeleteListX_Sq(L, x) printf(删除成功n); else printf(删除失败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); P

19、rintList_Sq(L); else printf(顺序表创建失败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; case 0: return 0; default: printf(输入错误，请重新输入n); 实验02 单链表的基本

20、操作实验学时：2学时实验类型：上机背景知识：单链表的插入、删除及应用。目的要求： 1掌握单链表的存储特点及其实现。 2掌握单链表的插入、删除算法及其应用算法的程序实现。实验内容： 编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。计算单链表的长度，遍历单链表。把单链表中的元素逆置（不允许申请新的结点空间）。在单链表中删除所有值为偶数的元素结点。编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单链表。* 利用算法5建立两个非递减有序单链表，然后合并成一个非递增有序链表。* 利

21、用算法5建立两个非递减有序单链表，然后合并成一个非递减有序链表。* 利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。* 采用单链表实现一元多项式的存储并实现两个多项式相加并输出结果。在主函数中设计一个简单的菜单，分别调试上述算法。* 综合训练： 1）利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中） 2）约瑟夫环问题：设有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，n，坐在编号为1的位置上的人从1开始报数，数到m的人便出列；下一个（第m+1个）人又从1开始报数，数到m的人便

22、是第二个出列的人；如此重复下去，直到最后一个人出列为止，得到一个出列的编号顺序。例如，当n=8，m=4时，若从第一个位置数起，则出列的次序为4，8，5，2，1，3，7，6。试编写程序确定出列的顺序。要求用不带头结点的单向循环链表作为存储结构模拟此过程，按照出列顺序打印出个人编号。实验说明： 1类型定义 typedef int ElemType; /元素类型 typedef struct node ElemType data; struct node *next; LinkNode, *LinkList; 2为了算法实现简单，建议采用带头结点的单链表。注意问题：1重点理解链式存储的特点及指针的含

23、义。 2注意比较顺序存储与链式存储的各自特点。 3注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 4单链表的操作是数据结构的基础，一定要注意对这部分常见算法的理解。部分源代码：DS.h#include #include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;LinkList.h#include DS.htypedef int Elemtype;typedef struct Node Elemtype data;struct Node *

24、next;Lnode,*LinkList;void menu(); /*菜单*/Status Init_Linklist(LinkList &L); /*初始化空表*/Status Creat_Linklist(LinkList &L); /*尾插法建立单链表*/void Disp_Linklist(LinkList L); /*单链表遍历*/int length_Linklist(LinkList L); /*计算单链表长度*/void Reverse_Linklist(LinkList L); /*单链表逆置*/void DelEven_Linklist(LinkList L); /*删除

25、值为偶数的结点*/Status Insert_Linklist(LinkList L, int x); /*在有序单链表L中插入元素x，链表仍然有序*/Status CreatOrder_Linklist(LinkList &L); /*创建非递减有序单链表*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc); /

26、*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/void Split_Linklist(LinkList La, LinkList &Lb); /*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/LinkList.cpp#include LinkList.hvoid menu() printf(ttt 单链表基本操作nn); printf(ttt1.建 立 单 链 表n); printf(ttt2.遍 历 单 链 表n); printf(ttt3.计 算 链 表 长 度n); printf(ttt4.链 表 逆 置n); printf(ttt5.删 除 偶 数 节

27、 点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) return ERROR;L-next=NULL;return OK;/*尾插法建立单链表*/Status Creat_Linklist(LinkLi

28、st &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-next = p; rear = p; rear-next = NULL; return OK;/*单链表遍历*/void Disp_Linklist(LinkList L) LinkList p; p = L-next; while(

29、p) printf(%d , p-data); p = p-next; printf(n);/*计算单链表长度*/int length_Linklist(LinkList L) int count = 0; /*count表示单链表长度*/ LinkList p; return count;/*单链表逆置*/void Reverse_Linklist(LinkList L) LinkList p, q ; /*删除值为偶数的结点*/void DelEven_Linklist(LinkList L) LinkList p, q; /*在有序单链表中插入元素，链表仍然有序，插入成功返回OK，插入失

30、败返回ERROR*/Status Insert_Linklist(LinkList L, int x) ;/*创建非递减有序单链表，创建成功返回OK，创建失败返回ERROR*/Status CreatOrder_Linklist(LinkList &L) /*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) /*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/void MergeAscend_Linklist(LinkList La,

31、LinkList Lb, LinkList &Lc) LinkList pa, pb, pc; pa = La-next; pb = Lb-next; pc = Lc = La; while(pa & pb) if(pa-data data) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; free(Lb);/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/void Split_Linklist(LinkList La,

32、LinkList &Lb) main.cpp#include LinkList.hint main() int choice, length; LinkList L, La, Lb, Lc; while(1) menu(); printf(选择你的操作：); scanf(%d,&choice); switch(choice) case 1: if(Creat_Linklist(L) printf(单链表创建成功n); else printf(单链表创建失败n); break; case 2: Disp_Linklist(L); break; case 3: length = length_Li

33、nklist(L); printf(单链表长度为：%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); else printf(单链表创建失败n); break; case 7: Crea

34、tOrder_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_Linklist(Lc); break; case 9: Creat_Linklist(L); Split_Link

35、list(L, Lb); printf(分裂后的新链表为：n); Disp_Linklist(L); Disp_Linklist(Lb); break; case 0: return 0; default: printf(输入错误，请重新输入n); 实验03 栈的基本操作实验学时：2学时实验类型：上机背景知识：顺序栈、链栈，入栈、出栈。目的要求： 1掌握栈的思想及其存储实现。 2掌握栈的常见算法的程序实现。实验内容：采用顺序存储实现栈的初始化、入栈、出栈操作。采用链式存储实现栈的初始化、入栈、出栈操作。在主函数中设计一个简单的菜单，分别测试上述算法。* 综合训练：堆栈操作合法性：假设以S和X分

36、别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。括号匹配检验：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意，即()或()等为正确的格式，()或()等均为不正确格式。输入一个表达式，判断其中的括号是否能正确匹配。表达式转换：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入在一行中给出不含空格的中

37、缀表达式，可包含+、-、*、以及左右括号()，表达式不超过20个字符。在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。实验说明：1类型定义 顺序栈示例#define MAX 100 /栈的最大值typedefstruct SElemType *base； SElemType *top；int stacksize；SqStack； 链栈示例 typedef int ElemType; /元素类型 typedef struct snode SElemType data; struct snode *next; StackNode, *LinkS

38、tack;2算法4的每个子功能尽可能写成函数形式。注意问题： 1重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。 2注意算法4的各个函数之间值的传递情况。 3栈的算法是后续实验的基础（树、图、查找、排序等）。实验04 队列的基本操作实验学时：2学时实验类型：上机背景知识：循环队列、链队列，入队、出队。目的要求： 1掌握队列的思想及其存储实现。 2掌握队列的常见算法的程序实现。实验内容：采用顺序存储实现循环队列的初始化、入队、出队操作。采用链式存储实现队列的初始化、入队、出队操作。在主函数中设计一个简单的菜单，分别测试上述算法。*综合训练：银行排队系统模拟:请用一个队列来模拟银行排队系

39、统，队列中存储序号。请设置一个菜单，包括叫号和排号两个选项。若选择叫号，则输出并删除队首元素；若选择排号，则顺序生成一个序号，加入队列，并输出该序号和前面有多少人等候。实验说明： 1类型定义 循环队列示例#define MAXQSIZE 100 /队列的最大长度typedefstruct QElemType *base；int front；int rear；SqQueue；链队列示例typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; Qu

40、euePtr rear; LinkQueue;注意问题： 1重点理解队列的算法思想，能够根据实际情况选择合适的存储结构。 2队列的算法是后续实验的基础（树、图、查找、排序等）。实验05 二叉树的基本操作实验学时：2学时实验类型：上机背景知识：二叉树的存储、建立、遍历及其应用。目的要求： 1掌握二叉树的存储实现。 2掌握二叉树的遍历思想。 3掌握二叉树的常见算法的程序实现。实验内容：从键盘上输入数据，建立二叉链表。 前序遍历、中序遍历、后序遍历二叉树：递归算法。前序遍历、中序遍历、后序遍历二叉树：非递归算法。借助队列实现二叉树的层次遍历。在主函数中设计一个简单的菜单，分别调试上述算法。*综合训练

41、：家族关系查询系统：建立家族关系数据库，可以实现家族成员的添加，可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。实验说明： 1类型定义 /二叉链表存储 #define TElemType char /元素类型 typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;注意问题： 1注意理解递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法。实验06 哈夫曼编码实验学时：4学时实验类型：综合型实验背景知识：二叉树的应用、哈夫曼树。

42、目的要求： 掌握哈夫曼树和哈夫曼编码的基本思想和算法的程序实现。实验内容：（1）修理牧场：农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

43、请编写程序帮助农夫计算将木头锯成N块的最少花费。首先输入一个正整数N（N104），表示要将木头锯成N块。接着给出N个正整数Li（Li50），表示每段木块的长度。输出一个整数，即将木头锯成N块的最少花费。例如：输入：84 5 1 2 1 3 1 1输出：49*（2）压缩软件：给定一篇文章，只含有英文大小写字母和空格，以.txt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。实验说明：1参考类型定义 /双亲孩子表示法 typedef struct unsigned int weight; unsig

44、ned int parent, lchild, rchild; HTNode, *HuffmanTree; /动态分配数组存储哈夫曼树 typedef char * * HuffmanCode; /动态分配数组存储哈夫曼编码表注意问题：1递归算法的灵活应用。2多级指针的使用。实验07 图的两种存储和遍历实验学时：2学时实验类型：上机背景知识：图的存储、遍历及其应用。目的要求：1掌握图的存储思想及其存储实现。 2掌握图的深度、广度优先遍历算法思想及其程序实现。实验内容：键盘输入数据，分别建立一个有向图和一个无向图的邻接表。输出该邻接表。在有向图的邻接表的基础上计算各顶点的度，并输出。采用邻接表存

45、储实现无向图的深度优先遍历。采用邻接表存储实现无向图的广度优先遍历。在主函数中设计一个简单的菜单，分别调试上述算法。*综合训练地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？输入格式：输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1N1000，表示通道所有交叉点和端点）、边数M（M3000，表示通道数）和探索起始节点编号S（节点从1到N编号）。随后的M行对应M条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。输出格式：若可以点亮所有节点的灯，则

46、输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出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 Arc

47、Node int adjvex; struct ArcNode *nextarc; int weight; /边的权值 ArcNode; /表结点 #define VertexType int /顶点元素类型 typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM; / typedef struct AdjList vertices; int vexnum, arcnum; /顶点的实际数，边的实际数 int kind; ALGraph; 2上述类型定义可以根据实际情况适当调整。

48、3算法4、5分别利用栈、队列实现非递归算法。注意问题： 1注意理解各算法实现时所采用的存储结构。2注意区别正、逆邻接。实验08 最小生成树、拓扑排序和最短路径实验学时：2学时实验类型：上机背景知识：图的存储、遍历及其应用。目的要求：掌握图的常见应用算法的思想及其程序实现。实验内容：（1）键盘输入数据，分别建立一个有向图的邻接表和一个无向图的邻接矩阵。（2）输出该邻接表和邻接矩阵。（3）以有向图的邻接表为基础输出它的拓扑排序序列。（4）以无向图的邻接矩阵为基础实现最小生成树的PRIM算法。（5）以有向图的邻接矩阵为基础实现Dijkstra算法输出单源点到其它顶点的最短路径。（6）在主函数中设计一

49、个简单的菜单，分别调试上述算法。（7）*综合训练：校园导航1）问题描述：在给出校园各主要建筑的名称信息及有路线连通的建筑之间的距离（或行进时间）的基础上，利用校园导航系统计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线。2）设计要求：文件读入或键盘方式读入校园主要建筑信息及建筑间的距离（或行进时间）信息。创建完地图后，以文件形式保存，以免重复创建。计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线，并输出该路线（包括经过哪些建筑）及其总距离（或总行进时间）。实验说明： 1类型定义邻接表存储见实验07邻接矩阵存储示例 #define MAX_VERTEX_NUM 20

50、/顶点最大个数 typedef enum DG, DN, UDG, UDN GraphKind;typedef struct ArcCell VRType adj; int weight; /边的权值 ArcCell; AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum, arcnum; /顶点的实际数，边的实际数 GraphKind kind; MGraph; 注意问题： 注意理解各算法实现时所采用的存储结构。实验09

51、二叉排序树的基本操作实验学时：2学时实验类型：上机背景知识：树表查找。目的要求： 掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。实验内容：随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。* 建立AVL树并实现删除某一指定关键字元素。*综合训练：树种统计随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。首先输入正整数N（105），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（不区分大小写）。按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，每种树的信息占一行。实验说明： 1存储定义参见实验05二叉链表的存储。2各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。注意问题： 1注意建立二叉排序树时相同元素的处理。2注意理解动态查找概念。实验10 哈希