《数据结构实验指导书》

目录《数据结构实验》教学大纲......................................1数据结构上机实验编程指南......................错误!未定义书签。实验一线性表................................................5实验二栈与队列.............................................12实验三二叉树...............................................17实验四图...................................................21实验五查找.................................................27实验六排序.................................................31《数据结构实验》教学大纲《DataStructureExperiment》TeachingProgram课程类别：必修课适用专业：计算机应用技术、计算机网络技术学时：22教研室主任：大纲执笔人：大纲审批人：一、本实验课的性质、任务与目的《数据结构》课程是计算机科学与技术专业的一门重要的专业基础课。通过此实验教学和学生的上机实践，要求学生掌握各种数据结构的具体物理实现方法，掌握用数据结构知识解决实际问题的方法，以达到理论指导实践的目的。从而进一步提高学生的编程能力、算法设计能力及分析问题、解决问题的能力。二、本实验课的基本理论1．线性表存储结构及其基本操作的实现。2．栈和队列的存储结构及其基本操作的实现。3．二叉树的存储结构及其基本操作的实现。4．图的存储结构及其基本操作的实现。5．各类查找算法的设计6．各类排序算法的设计三、实验内容和教学基本要求序号实验名称学时实验内容实验要求实验类型1线性表2（1）顺序表的定义及其相关操作算法的实现；必做设计性（2）链表的定义及其相关算法的实现；必做设计性（3）集合的表示与运算。选做综合性（4）一元多项式的表示与运算选做综合性2栈与队列2（1）顺序栈的定义及其操作算法的实现；必做设计性（2）链式队列定义及其操作算法的实现；选做设计性（3）循环队列定义及其操作算法的实现；必做设计性（4）利用栈实现进制转换选做综合性（5）利用栈实现括号匹配检测选做综合性3二叉树2（1）二叉树的创建、递归遍历及其它基本操作的实现。必做设计性（2）二叉树的创建、非递归遍历及其它基本操作的实现。选做设计性（3）哈夫曼树及哈夫曼编码的算法实现。选做综合性4图2（1）图的邻接矩阵存储方式的实现、图的遍历算法。必做设计性（2）图的邻接矩阵存储方式的实现、图的遍历算法。必做设计性（3）图最小生成树算法选做综合性（4）图的拓扑排序算法选做综合性（5）图的最短路径算法选做综合性5查找2（1）顺序查找算法、二分法查找算法、必做设计性（2）二叉排序树的创建与查找、选做设计性（3）哈希表的造表与查找算法选做设计性（4）班级学生成绩管理（表的存储、相关查找等）选做综合性6排序2（1）直接插入排序算法、SHELL排序算法必做设计性（2）快速排序算法、归并排序算法选做设计性（3）选择排序算法、堆排序算法必做设计性（4）班级学生成绩管理（利用某种排序方法实现按某个或某些关键字排序）选做综合性四、仪器设备配置每人一台计算机，安装TurboC软件。五、教学文件与教学形式1．教学文件《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，2002.9。2．教学形式应用多媒体讲授实验内容、要求及注意事项，上机辅导，最后进行实验总结。六、考核方法及成绩评定办法每次完成实验内容，进行总结分析，写出实验报告。按照实验内容完成情况及实验报告书写情况进行考核，成绩按优、良、中、及格、不及格五级分评定。数据结构实验指导书为了更好地帮助同学们做好数据结构实验，在此给出数据结构上机编程的一般思路和程序的基本框架结构。具体程序结构按先后顺序可分为以下3个部分：1、预定义常量及类型对于相关的常量与类型（如状态类型）进行定义，如：#defineOK1#defineERROR0#defineOVERFLOW–2#defineTRUE1#defineFALSE0typedefintStatus;2、相关数据结构类型定义此部分包括对所使用的数据结构给出其类型定义，及基本操作函数定义。（具体内容可参见实验一）3、主调程序的定义此部分给出相关的主调程序，在此程序中定义相关数据结构变量，并通过调用其操作函数，实现设计目的。（具体内容可参见实验一）实验一线性表一、实验目的1．掌握顺序表及其基本操作的实现。2．掌握链表及其基本操作的实现。3．掌握利用TC实现数据结构的编程方法。4．通过上机实践进一步加深对线性表的顺序存储方式及链式存储方式的理解。5．通过上机实践加强利用数据结构解决实际应用应用问题的能力。二、实验要求1．实验前做好充分准备，包括复习第一章、第二章所学内容，事先预习好本次实验内容。2．实验时记录实验结果，按要求完成各题。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型线性表2（1）顺序表的定义及其相关操作算法的实现；必做设计性（2）链表的定义及其相关算法的实现；必做设计性（3）集合的表示与运算。选做综合性（4）一元多项式的表示与运算选做综合性说明：（1）实验内容1）与实验内容2）为必做内容。（2）实验内容3）与实验内容4）为选做内容。四、实验内容与要求1、实验题目一：顺序表的定义及其相关操作算法的实现要求：编程实现顺序表的类型定义及顺序表的初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。2、实验题目二：链表的定义及其相关操作算法的实现要求：编程实现单链表（或双向链表、循环链表）的类型定义及其初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。3、实验题目三：集合的表示与运算要求：利用题目一或题目二所定义的线性表（顺序表或链表）实现集合的表示及其并、交等运算，并进行验证给出结果。4、实验题目四：一元多项式的表示与运算要求：利用线性表（顺序表或链表）实现一元多项的类型定义及其相加等等运算，并进行验证给出结果。五、实验程序示例1、顺序表实验程序示例#includestdio.h#includealloc.h/*-------------（1）预定义常量及类型-----------------*/#defineOK1#defineERROR0#defineOVERFLOW-2#defineTRUE1#defineFALSE0typedefintStatus;/*-------（2）顺序表类型及其基本操作函数的定义---------*/#defineInitSize100#defineINCR20typedefintElemType;/*定义元素类型为int类型*/typedefstruct{ElemType*Elem;intLength;intListSize;}SqList;/*SqList类型为顺序表类型*/StatusInitList_sq(SqList&L)/*初始化操作函数定义*/{L.Elem=(ElemType*)malloc(InitSize*sizeof(ElemType));if(!(L.Elem))return(OVERFLOW);L.Length=0;L.ListSize=InitSize;returnOK;}StatusListInsert_sq(SqList&L,inti,ElemTypee)/*插入操作函数定义*/{intj;if(i1||iL.Length+1)returnERROR;if(L.Length=L.ListSize){L.Elem=(ElemType*)malloc((L.ListSize+INCR)*sizeof(ElemType));if(!(L.Elem))return(OVERFLOW);L.ListSize+=INCR;}for(j=L.Length-1;j=i-1;j--)L.Elem[j+1]=L.Elem[j];L.Elem[i-1]=e;L.Length++;returnOK;}voidListOutput_sq(SqListL)/*顺序表输出操作*/{inti;for(i=0;i=L.Length-1;i++)printf(%6d,L.Elem[i]);printf(\n);}/*其它操作如删除、查找、判空等操作略*//*-------------（3）主函数定义--------------------*/main(){SqListLa;inti;InitList_sq(La);for(i=0;i5;i++)ListInsert_sq(La,i+1,2*i);ListOutput_sq(La);ListInsert_sq(La,1,999);ListOutput_sq(La);ListInsert_sq(La,4,888);ListOutput_sq(La);ListInsert_sq(La,La.Length+1,111);ListOutput_sq(La);}2、单链表(带头结头)实验程序示例#includestdio.h#includealloc.h/*-------------------（1）预定义常量及类型---------------*/#defineOK1#defineERROR0#defineOVERFLOW-2#defineTRUE1#defineFALSE0typedefintStatus;/*------------（2）单链表类型及其基本操作函数的定义------*/typedefintElemType;/*定义元素类型为int类型*/typedefstructLnode{ElemTypedata;structLnode*next;}*LinkList;/*LinkList为单链表类型*/StatusInitList_l(LinkList&L)/*初始化操作函数定义*/{L=(LinkList)malloc(sizeof(structLnode));if(!L)return(OVERFLOW);L-next=NULL;returnOK;}StatusListInsert_l(LinkList&L,inti,ElemTypee)/*插入操作函数定义*/{LinkListp,s;intj;p=L;j=0;while(p&&ji-1){p=p-next;j++;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(structLnode));s-data=e;s-next=p-next;p-next=s;returnOK;}voidListOutput_l(LinkListL)/*输出操作函数定义*/{LinkListp;p=L-next;while(p){printf(%6d,p-data);p=p-next;}printf(\n);}/*其它操作如删除、查找、判空等操作略*//*-------------（3）主函数定义--------------------*/main(){inti;LinkListLa;InitList_l(La);for(i=0;i5;i++)ListInsert_l(La,i+1,3*i);ListOutput_l(La);ListInsert_l(La,1,999);ListOutput_l(La);ListInsert_l(La,4,888);ListOutput_l(La);}3、一元多项式的单链表表示与相加操作的实现程序示例#includestdio.h#includeal