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

《数据结构》实验指导书(修订版)《数据结构》实验指导书(修订版)《数据结构》实验指导书(修订版)《数据结构》实验指导书(修订版)编制仅供参考审核批准生效日期地址：电话：传真:邮编:《数据结构》实验指导书郑州轻工业学院

目录前言 3实验01顺序表的基本操作 7实验02单链表的基本操作 19实验03栈的基本操作 32实验04队列的基本操作 35实验05二叉树的基本操作 38实验06哈夫曼编码 40实验07图的两种存储和遍历 42实验08最小生成树、拓扑排序和最短路径 46实验09二叉排序树的基本操作 48实验10哈希表的生成 50实验11常用的内部排序算法 52附：实验报告模板 54

前言《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力。通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。一、实验目的本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础。二、实验要求1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。3、实验结束后总结实验内容、书写实验报告。4、遵守实验室规章制度、不缺席、按时上、下机。5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。三、实验环境VC++或其他C++相关的编译环境。四、说明1、本实验的所有算法中元素类型应根据实际需要合理选择。2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。4、好的算法决定了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据结构，因此数据结构是有效进行程序设计的基础，是每个程序员的必修课。五、实验报告的书写要求1、明确实验的目的及要求。2、记录实验的输入数据和输出结果。3、说明实验中出现的问题和解决过程。4、写出实验的体会和实验过程中没能解决的问题。5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h中，对应的函数实现存放在源文件*.c中；main()函数存放在另一个源文件中，该文件包含头文件*.h即可。六、成绩考评办法1、期末考试占70分，闭卷。2、平时考评占30分。其中实验环节占20分（实验准备、上机、报告、验收等）；平时占10分（出勤、作业、测验等）。七、参考书目1、《数据结构》（Ｃ语言版）严蔚敏等清华大学出版社。2、《数据结构题集》（C语言版）严蔚敏等清华大学出版社。3、《数据结构与算法分析——C语言描述》，MarkAllenWeiss着，机械工业出版社，2012。

实验01顺序表的基本操作实验学时：2学时实验类型：上机背景知识：顺序表的插入、删除及应用。目的要求：1．掌握顺序存储结构的特点。2．掌握顺序存储结构的常见算法。实验内容：编写一个完整的程序，实现顺序表的生成、插入、删除、输出等基本运算。建立一个顺序表，含有n个数据元素。输出顺序表。在顺序表中删除值为x的结点或者删除给定位置i的结点。实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。输入整型元素序列，利用有序表插入算法建立一个有序表。*利用算法5建立两个非递减有序表A和B，并把它们合并成一个非递减有序表C。在主函数中设计一个简单的菜单，分别测试上述算法。*综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。实验说明：1．请构建多文件程序，算法1至算法6对应的函数原型声明存放在头文件中，对应的函数实现存放在源文件中；main()函数存放在另一个源文件中，该文件包含头文件即可。2．类型定义#defineMAXSIZE100立顺序表\n");printf("\t\t\t2.遍历顺序表\n");printf("\t\t\t3.删除第i个元素\n");printf("\t\t\t4.删除值为x的元素\n");printf("\t\t\t5.奇数排在偶数之前\n");printf("\t\t\t6.插入法生成递增有序表\n");printf("\t\t\t7.两个非递减有序表La和Lb合并成非递减有序表Lc\n");printf("\t\t\t0.退出\n\n");}/*初始化顺序表*/StatusInitList_Sq(SqList&L,intn){=(ElemType*)malloc(n*sizeof(ElemType));if(!exit(OVERFLOW);=0;=n;returnOK;}/*建立顺序表*/StatusCreateList_Sq(SqList&L){intn,i;printf("请输入顺序表长度：");scanf("%d",&n);if(InitList_Sq(L,n)){printf("请输入%d个元素：",n);for(i=0;i<n;i++){scanf("%d",&[i]);++;}returnOK;}elsereturnERROR;}/*输出顺序表*/voidPrintList_Sq(SqListL){inti;printf("顺序表中元素为：\n");for(i=0;i<;i++){printf("%d",[i]);}printf("\n");}/*删除第i个元素*/StatusDeleteList_Sq(SqList&L,inti,ElemType&e){ ElemType*p,*q; if((i<1)||(i>)returnERROR; p=&[i-1]); e=*p; q=+; for(++p;p<=q;++p)*(p-1)=*p; ; returnOK;}/*删除值为x的元素，删除成功返回OK，删除失败返回ERROR*/StatusDeleteListX_Sq(SqList&L,ElemTypex){ ElemType*p,*q; }/*奇数排在偶数之前*/StatusAdjustList_Sq(SqList&L){ElemType*p,*q;inttemp;returnOK;}/*插入法生成递增有序表，有序表生成成功返回OK，失败返回ERROR*/StatusOrderList_sq(SqList&L,intn){inti,j,x;/*x表示每次待插入的元素*/}/*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=;pb=;==+;pc==(ElemType*)malloc*sizeof(ElemType));if(!exit(OVERFLOW);pa_last=+-1;pb_last=+-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++;}#include""intmain(){intchoice,n,i,x;SqListL,La,Lb,Lc;while(1){menu();printf("选择你的操作：");scanf("%d",&choice);switch(choice){case1:if(CreateList_Sq(L))printf("顺序表创建成功\n");elseprintf("顺序表创建失败\n");break;case2:PrintList_Sq(L);break;case3:printf("请输入删除元素的位置：");scanf("%d",&i);if(DeleteList_Sq(L,i,x))printf("被删除元素值为：%d\n",x);elseprintf("删除失败\n");break;case4:printf("请输入删除元素值：");scanf("%d",&x);if(DeleteListX_Sq(L,x))printf("删除成功\n");elseprintf("删除失败\n");PrintList_Sq(L);break;case5:AdjustList_Sq(L);printf("新链表为：\n");PrintList_Sq(L);break;case6:printf("请输入顺序表长度：");scanf("%d",&n);if(OrderList_sq(L,n)){printf("值有序顺序表为：\n");PrintList_Sq(L);}elseprintf("顺序表创建失败\n");break;case7: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;case0:return0;default:printf("输入错误，请重新输入\n");}}}

实验02单链表的基本操作实验学时：2学时实验类型：上机背景知识：单链表的插入、删除及应用。目的要求：1．掌握单链表的存储特点及其实现。2．掌握单链表的插入、删除算法及其应用算法的程序实现。实验内容：编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。计算单链表的长度，遍历单链表。把单链表中的元素逆置（不允许申请新的结点空间）。在单链表中删除所有值为偶数的元素结点。编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单链表。*利用算法5建立两个非递减有序单链表，然后合并成一个非递增有序链表。*利用算法5建立两个非递减有序单链表，然后合并成一个非递减有序链表。*利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。*采用单链表实现一元多项式的存储并实现两个多项式相加并输出结果。在主函数中设计一个简单的菜单，分别调试上述算法。*综合训练：1）利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）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。试编写程序确定出列的顺序。要求用不带头结点的单向循环链表作为存储结构模拟此过程，按照出列顺序打印出个人编号。实验说明：1．类型定义typedefintElemType;立单链表\n");printf("\t\t\t2.遍历单链表\n");printf("\t\t\t3.计算链表长度\n");printf("\t\t\t4.链表逆置\n");printf("\t\t\t5.删除偶数节点\n");printf("\t\t\t6.生成值有序单链表\n");printf("\t\t\t7.合并生成降序链表\n");printf("\t\t\t8.合并生成升序链表\n");printf("\t\t\t9.分解链表\n");printf("\t\t\t0.退出\n\n");}/*初始化空表*/StatusInit_Linklist(LinkList&L){L=(LinkList)malloc(sizeof(Lnode));if(!L)returnERROR; L->next=NULL; returnOK;}/*尾插法建立单链表*/StatusCreat_Linklist(LinkList&L){intx;LinkListp,rear;Init_Linklist(L);rear=L;printf("输入-1表示输入结束\n");while(scanf("%d",&x),x!=-1){p=(LinkList)malloc(sizeof(Lnode));if(!p)returnERROR;p->data=x;rear->next=p;rear=p;}rear->next=NULL;returnOK;}/*单链表遍历*/voidDisp_Linklist(LinkListL){LinkListp;p=L->next;while(p){printf("%d",p->data);p=p->next;}printf("\n");}/*计算单链表长度*/intlength_Linklist(LinkListL){intcount=0;/*count表示单链表长度*/LinkListp;returncount;}/*单链表逆置*/voidReverse_Linklist(LinkListL){LinkListp,q;}/*删除值为偶数的结点*/voidDelEven_Linklist(LinkListL){LinkListp,q;}/*在有序单链表中插入元素，链表仍然有序，插入成功返回OK，插入失败返回ERROR*/StatusInsert_Linklist(LinkListL,intx){;}/*创建非递减有序单链表，创建成功返回OK，创建失败返回ERROR*/StatusCreatOrder_Linklist(LinkList&L){}/*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/voidMergeDescend_Linklist(LinkListLa,LinkListLb,LinkList&Lc){}/*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/voidMergeAscend_Linklist(LinkListLa,LinkListLb,LinkList&Lc){LinkListpa,pb,pc;pa=La->next;pb=Lb->next;pc=Lc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=papa:pb;free(Lb);}/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/voidSplit_Linklist(LinkListLa,LinkList&Lb){}#include""intmain(){intchoice,length;LinkListL,La,Lb,Lc;while(1){menu();printf("选择你的操作：");scanf("%d",&choice);switch(choice){case1:if(Creat_Linklist(L))printf("单链表创建成功\n");elseprintf("单链表创建失败\n");break;case2:Disp_Linklist(L);break;case3:length=length_Linklist(L);printf("单链表长度为：%d\n",length);break;case4:Reverse_Linklist(L);printf("逆置后的链表为：\n");Disp_Linklist(L);break;case5:DelEven_Linklist(L);printf("新链表为：\n");Disp_Linklist(L);break;case6:if(CreatOrder_Linklist(L)){printf("值有序链表为：\n");Disp_Linklist(L);}elseprintf("单链表创建失败\n");break;case7:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeDescend_Linklist(La,Lb,Lc);printf("合并后的新链表为：\n");Disp_Linklist(Lc);break;case8:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeAscend_Linklist(La,Lb,Lc);printf("合并后的新链表为：\n");Disp_Linklist(Lc);break;case9:Creat_Linklist(L);Split_Linklist(L,Lb);printf("分裂后的新链表为：\n");Disp_Linklist(L);Disp_Linklist(Lb);break;case0:return0;default:printf("输入错误，请重新输入\n");}}}实验03栈的基本操作实验学时：2学时实验类型：上机背景知识：顺序栈、链栈，入栈、出栈。目的要求：1．掌握栈的思想及其存储实现。2．掌握栈的常见算法的程序实现。实验内容：采用顺序存储实现栈的初始化、入栈、出栈操作。采用链式存储实现栈的初始化、入栈、出栈操作。在主函数中设计一个简单的菜单，分别测试上述算法。*综合训练：堆栈操作合法性：假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。括号匹配检验：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或([())等均为不正确格式。输入一个表达式，判断其中的括号是否能正确匹配。表达式转换：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。实验说明：1．类型定义顺序栈示例#defineMAX100xt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。实验说明：1．参考类型定义//双亲孩子表示法typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表注意问题：1．递归算法的灵活应用。2．多级指针的使用。

实验07图的两种存储和遍历实验学时：2学时实验类型：上机背景知识：图的存储、遍历及其应用。目的要求：1．掌握图的存储思想及其存储实现。2．掌握图的深度、广度优先遍历算法思想及其程序实现。实验内容：键盘输入数据，分别建立一个有向图和一个无向图的邻接表。输出该邻接表。在有向图的邻接表的基础上计算各顶点的度，并输出。采用邻接表存储实现无向图的深度优先遍历。采用邻接表存储实现无向图的广度优先遍历。在主函数中设计一个简单的菜单，分别调试上述算法。*综合训练地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点输入格式：输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1<N≤1000，表示通道所有交叉点和端点）、边数M（M≤3000，表示通道数）和探索起始节点编号S（节点从1到N编号）。随后的M行对应M条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。输出格式：若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。输入样例：6811223344556643615输出样例：12345654321实验说明：

1．类型定义（邻接表存储）#defineMAX_VERTEX_NUM20//顶点最大个数typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;//边的权值}ArcNode;//表结点

#defineVertexTypeint//顶点元素类型typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//typedefstruct{AdjListvertices;intvexnum,arcnum;//顶点的实际数，边的实际数intkind;}ALGraph;2．上述类型定义可以根据实际情况适当调整。3．算法4、5分别利用栈、队列实现非递归算法。注意问题：1．注意理解各算法实现时所采用的存储结构。2．注意区别正、逆邻接。

实验08最小生成树、拓扑排序和最短路径实验学时：2学时实验类型：上机背景知识：图的存储、遍历及其应用。目的要求：掌握图的常见应用算法的思想及其程序实现。实验内容：（1）键盘输入数据，分别建立一个有向图的邻接表和一个无向图的邻接矩阵。（2）输出该邻接表和邻接矩阵。（3）以有向图的邻接表为基础输出它的拓扑排序序列。（4）以无向图的邻接矩阵为基础实现最小生成树的PRIM算法。（5）以有向图的邻接矩阵为基础实现Dijkstra算法输出单源点到其它顶点的最短路径。（6）在主函数中设计一个简单的菜单，分别调试上述算法。（7）*综合训练：校园导航1）问题描述：在给出校园各主要建筑的名称信息及有路线连通的建筑之间的距离（或行进时间）的基础上，利用校园导航系统计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线。2）设计要求：文件读入或键盘方式读入校园主要建筑信息及建筑间的距离（或行进时间）信息。创建完地图后，以文件形式保存，以免重复创建。计算出给定的起点到终点之间距离最近（或行进时间最短）的行进路线，并输出该路线（包括经过哪些建筑）及其总距离（或总行进时间）。实验说明：

1．类型定义邻接表存储见实验07邻接矩阵存储示例#defineMAX_VERTEX_NUM20//顶点最大个数typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{VRTypeadj;intweight;//边的权值}ArcCell;AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;//顶点的实际数，边的实际数GraphKindkind;}MGraph;注意问题：注意理解各算法实现时所采用的存储结构。

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

实验10哈希表的生成实验学时：2学时实验类型：上机背景知识：哈希查找。目的要求：掌握哈希存储结构的思想，能选择合适的哈希函数，实现不同冲突处理方法的哈希表的查找、建立。实验内容：（1）设计哈希函数及处理冲突的方法；（2）键盘输入数据，利用设计的哈希函数及线性探测法生成哈希表；（3）用同样的输入数据和哈希函数，用链地址法处理冲突生成哈希表；（4）在主函数中设计一个简单的菜单，分别调试上述算法；（5）分析两种方法的平均查找长度。（6）*综合训练：QQ帐户的申请与登陆首先输入一个正整数N（≤105），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超