数据结构实验指导书重要参考.doc

数据结构实验指导前 言数据结构是计算机相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写试验指导书；同时，为每个主要的知识点配有精选的典型习题。希望学生对习题要注意理解。一、实验目的 更好的理解算法的思想、培养编程能力。二、实验要求1. 每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。2. 在指导教师的帮助下能够完成实验内容，得出正确的实验结果。3. 实验结束后总结实验内容、书写实验报告。4. 遵守实验室规章制度、不缺席、按时上、下机。5. 实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。6. 实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。三、实验环境 Turbo C或VC+6.0四、说明1. 本实验的所有算法中元素类型可以根据实际需要选择。2. 实验题目中带者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。3. 数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。五、实验报告的书写要求1. 明确实验的目的及要求;2. 记录实验的输入数据和输出结果;3. 说明实验中出现的问题和解决过程;4. 写出实验的体会和实验过程中没能解决的问题;六、成绩考评办法1 期末考试占80分，闭卷。2 平时考评占20分。其中实验环节占15分（实验准备、上机、报告、考试等）；平时占5分（出勤，作业，测验等）七、参考书目1. 数据结构（语言版） 严蔚敏等 清华大学出版社 2. 数据结构题集 （C语言版） 严蔚敏等 清华大学出版社 3. DATA STRUCTURE WITH C+ William Ford,William Topp清华大学出版社（影印版）实验一 线性表的顺序存储结构实验学时 2学时背景知识:顺序表的插入、删除及应用。目的要求： 1掌握顺序存储结构的特点。 2掌握顺序存储结构的常见算法。实验内容 1输入一组整型元素序列，建立顺序表。 2实现该顺序表的遍历。 3在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 4判断该顺序表中元素是否对称,对称返回1,否则返回0。5实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。6输入整型元素序列利用有序表插入算法建立一个有序表。 7利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。8编写一个主函数,调试上述算法。 * 9综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）实验说明 1.算法1至算法7可以以头文件的方式存储,主函数实现该头文件的包含即可调用 2.存储定义 #define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType；/元素类型 typedef struct list ElemType elemMAXSIZE;/静态线性表 int length; /表的实际长度 SqList;/顺序表的类型名 3.建立顺序表时可利用随机函数自动产生数据。注意问题 插入、删除时元素的移动原因、方向及先后顺序。 解不同的函数形参与实参的传递关系。实验二 链式存储结构（一）-单向链表的有关操作实验学时 学时背景知识：单向链表的插入、删除及应用。目的要求 1掌握单向链表的存储特点及其实现。 2掌握单向链表的插入、删除算法及其应用算法的程序实现。实验内容 1随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 2遍历单向链表。 3把单向链表中元素逆置（不允许申请新的结点空间）。 4在单向链表中删除所有的偶数元素结点。 5编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 6利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 7利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。 8利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。 * 9采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。10在主函数中设计一个简单的菜单，分别调试上述算法。 *11综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）实验说明 1类型定义 #include typedef int ElemType；/元素类型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; 2为了算法实现简单，最好采用带头结点的单向链表。注意问题 1重点理解链式存储的特点及指针的含义。 2注意比较顺序存储与链式存储的各自特点。 3注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 4单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。实验三 链式存储结构（二）-双向链表的有关操作实验学时 学时背景知识：双向链表的插入、删除及应用。目的要求 掌握双向链表的存储特点及其实现。 掌握双向链表的插入、删除算法及其应用算法的程序实现。实验内容 利用尾插法建立一个双向链表。 遍历双向链表。 实现双向链表中删除一个指定元素。 在非递减有序双向链表中实现插入元素e仍有序算法。 判断双向链表中元素是否对称若对称返回1否则返回0。 设元素为正整型,实现算法把所有奇数排列在偶数之前。 在主函数中设计一个简单的菜单调试上述算法。双向链表的类型定义 typedef int ElemType；/元素类型 typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; 注意问题 注意比较单向、双向链表的特点。实验四 栈队列实验学时 学时背景知识：入栈、出栈，入队、出队。目的要求 1掌握栈、队列的思想及其存储实现。 2掌握栈、队列的常见算法的程序实现。实验内容 1采用链式存储实现栈的初始化、入栈、出栈操作。 2采用顺序存储实现栈的初始化、入栈、出栈操作。 3采用链式存储实现队列的初始化、入队、出队操作。 4采用顺序存储实现循环队列的初始化、入队、出队操作。 5在主函数中设计一个简单的菜单，分别测试上述算法。 *6综合训练:1)利用栈实现表达式求值算法。 2)利用栈实现迷宫求解。实验说明 1基本要求：实现算法1、3或算法2、4即可。 2类型定义 顺序栈示例#define MAX 100 /栈的最大值typedefstruct ElemType *base；int top；SqStack； 顺序队列示例#define MAX 100 /队列的最大长度typedefstruct ElemType *base；int front，rear；SqQueue； 3算法6的每个子功能尽可能写成函数形式。注意问题 1重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。 2注意算法6的各个函数之间值的传递情况。 3栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。实验五 二叉树的常见操作实验学时 学时背景知识：二叉树的存储、建立、遍历及其应用。目的要求 1掌握二叉树的存储实现。 2掌握二叉树的遍历思想。 3掌握二叉树的常见算法的程序实现。实验内容 1输入字符序列，建立二叉链表。 2中序遍历二叉树:递归算法。 3中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法） 4求二叉树的高度 。 5求二叉树的叶子个数。 *6将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。 *7建立中序线索二叉树，并实现中序遍历。 8借助队列实现二叉树的层次遍历。 9在主函数中设计一个简单的菜单，分别调试上述算法。 *10综合训练：为N个权值设计哈夫曼编码。实验说明 类型定义 /二叉链表存储 #define ElemType char/元素类型 typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;元素类型可以根据实际情况选取。注意问题 1注意理解递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法。实验六 图的有关操作实验学时 学时背景知识：图的存储、遍历、及其应用。目的要求 掌握图的存储思想及其存储实现。 掌握图的深度、广度优先遍历算法思想及其程序实现。 掌握图的常见应用算法的思想及其程序实现。实验内容 键盘输入数据，建立一个有向图的邻接表。 输出该邻接表。 *建立一个无向图的十字链表。 在有向图的邻接表的基础上计算各顶点的度，并输出。 以有向图的邻接表为基础实现输出它的拓扑排序序列。 *采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。 采用邻接表存储实现无向图的深度优先非递归遍历。 采用邻接表存储实现无向图的广度优先遍历。 *采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。 *10判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。11在主函数中设计一个简单的菜单，分别调试上述算法。 *12综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。实验说明 类型定义（邻接表存储） #define MAX_VERTEX_NUM 8 /顶点最大个数 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; int weight; /边的权 ArcNode; /表结点 #define VertexType int /顶点元素类型 typedef struct VNode int degree,indegree;/顶点的度，入度 VertexType data; ArcNode *firstarc; VNode/*头结点*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/顶点的实际数，边的实际数 ALGraph; 上述类型定义可以根据实际情况适当调整。算法、分别利用栈、队列实现非递归算法。 注意问题 注意理解各算法实现时所采用的存储结构。注意区别正、逆邻接。实验七 查找的有关操作实验学时 2学时背景知识:顺序查找、树表查找、散列查找。目的要求： 1掌握折半查找算法的思想及程序实现。 2掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。3掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。实验内容 1利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。 2随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。 *3建立树并实现删除某一指定关键字元素。 4已知散列函数为H(key)=key%p（p为自定的常数），冲突处理方法分别为线性探测法、外拉链法实现散列表的建立（利用插入算法实现）。 实验说明 1存储定义（散列表的外拉链法） #define n 9 typedef struct node int key; struct node *next; NODE; NODE *HashTable9; 算法1、2、3可以参考顺序表，二叉链表的存储实现。2各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。3算法1存储在文件seqlist.h中,算法2、3存储在文件bintree.h中,算法4存储在文件hash.h中注意问题 1注意理解折半查找的适用条件（链表能否实现折半查找？）。 2注意建立二叉排序树、散列表时相同元素的处理。3注意理解静态查找、动态查找概念。4比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。实验八 排序实验学时 学时背景知识：各种排序方法目的要求 掌握常见的排序算法的思想及其适用条件。 掌握常见的排序算法的程序实现。实验内容 输入一组关键字序列分别实现下列排序: 1.实现简单选择排序、直接插入排序和冒泡排序。 2.实现希尔排序算法。 3.实现快速排序算法。 4.实现堆排序算法。 *5.快速排序的非递归算法。 *6.实现折半插入排序。 *7.采用链式存储实现简单选择排序、直接插入排序和冒泡排序。8.在主函数中设计一个简单的菜单，分别测试上述算法。 *9综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。实验说明 1类型定义 #define MAXSIZE 100 /*参加排序元素的最大个数*/ typedef struct list int key; RedType; typedef struct RedType rMAXSIZE+1; int length; /*参加排序元素的实际个数*/ SqList;2算法可以借助栈实现。注意问题 1在RedType中增加一个数据项验证各种排序算法的稳定性。2注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。/部分算法程序示例/实验一 线性表的顺序存储结构 #include stdio.h #include stdlib.h #define Status int #define OVERFLOW 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 100 typedef int ElemType; typedef struct list ElemType elemMAXSIZE; int length; SqList; void InitList(SqList &L) L.length=0; /*建立顺序表*/ void CreateList(SqList &L) int i; printf(input the length); scanf(%d,&L.length);/输入表长 for(i=1;i=L.length;i+) scanf(%d,&L.elemi-1);/输入元素 /顺序表的遍历 void printdata(ElemType e) printf(%4d,e); void Traverse(SqList L,void (*visit)(ElemType e) int i; printf(The elements of the lists are:n); for(i=1;i=L.length;i+) if (i%10=0)printf(n);/每行显示10个元素 visit(L.elemi-1);/输出表中元素 printf(n); /有序顺序表L中插入元素e使序列仍有序 void Insert(SqList &L,ElemType e) int i,j; if (L.length=MAXSIZE)exit(OVERFLOW);/表满,不能插入 for(i=1;i=L.length&L.elemi-1=i;j-) L.elemj=L.elemj-1;/元素后移 L.elemi-1=e;/插入e L.length=L.length+1;/表长加 /建立递增有序的顺序表 void CreateList_Sorted(SqList &L) int i,num; ElemType e; L.length=0; printf(Create a sorted list,Input the length of the listn); scanf(%d,&num); printf(Input the data %d numbersn,num); for(i=1;iMAXSIZE) exit(OVERFLOW); else pa=La.elem;pb=Lb.elem;pc=Lc.elem; while (paLa.elem+La.length&pbLb.elem+Lb.length) *pc+=(*pa=*pb)?*pa+:*pb+;/*公共部分合并*/ while (paLa.elem+La.length) *pc+=*pa+; /*R1表的剩余部分放到R的后部*/ while (pbLb.elem+Lb.length) *pc+=*pb+; /*R2表的剩余部分放到R的后部*/ Lc.length=La.length+Lb.length;/*R表长*/ /判断元素是否对称，对称返回TRUE 否则返回FALSE Status Symmetric(SqList L) int low,high; low=0; high=L.length-1; while(lowhigh) if (L.elemlow=L.elemhigh)low+;high-; else return(FALSE); return(TRUE); /顺序表的主函数部分/#include seqlist.h void main() SqList L1,L2,L; int select; ElemType e; doprintf(n1 insert 2 merge); printf(n3 symmetric 0 exit n); printf(Please select(0-3)n); scanf(%d,&select); switch(select) case 1: InitList(L); CreateList_Sorted(L); Traverse(L,printdata); printf(nInput the element of insertedn); scanf(%d,&e); Insert(L,e); Traverse(L,printdata); break; case 2: InitList(L1); CreateList_Sorted(L1); Traverse(L1,printdata); InitList(L2); CreateList_Sorted(L2); Traverse(L2,printdata); InitList(L); MergeList(L1,L2,L); Traverse(L,printdata); break; case 3: InitList(L); CreateList(L); Traverse(L,printdata); if (Symmetric(L) printf(Yes!n); else printf(Notn); break; case 0:break; default:printf(Error! Try again!n); while(select); /*实验二 链式存储结构（一）-单向链表的有关操作/*类型定义及头文件部分,文件名为sllink.h*/ #include #include typedef int ElemType;/元素实际类型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; /定义结点、指针类型名 /头插法建立无序链表 void CreateList(LinkList &L) LinkList p; ElemType e; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(头插法建立链表，以0结束n); scanf(%d,&e); while(e) p=(LinkList)malloc(sizeof(LNode); p-data=e; p-next=L-next; L-next=p; scanf(%d,&e); /*非递减有序单向链表L插入元素e序列仍有序*/ void Insert_Sort(LinkList &L,ElemType e) LinkList p,s; s=(LinkList)malloc(sizeof(LNode); s-data=e; p=L; while(p-next&p-next-datanext;/*查找插入位置*/ s-next=p-next; /*插入语句*p结点后插入*s结点*/ p-next=s; /*建立递增有序的单向链表*/ void Create_Sort(LinkList &L) ElemType e; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(建立有序表，输入任意个整型数据以0结束n); scanf(%d,&e); while(e) Insert_Sort(L,e); scanf(%d,&e); /*单向链表的遍历*/ void Traverse(LinkList L) LinkList p; printf(遍历链表); for(p=L-next;p;p=p-next) printf(%5d,p-data); printf(n); /*在单向链表删除元素e*/ void Delete(LinkList &L,ElemType e) LinkList p,q; p=L; q=L-next; while(q& q-data!=e)/查找元素的删除位置 p=q; q=q-next; if(!q) printf(nnot deleted);/*未找到元素e*/ else p-next=q-next;/*找到删除*/ free(q); /*单向链表的逆置*/ void exch(LinkList &L) LinkList p,s; p=L-next; L-next=NULL; while(p) s=p; p=p-next; s-next=L-next; L-next=s; /*两个非递减有序单向链表合并后仍为非递减序列*/ void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc) LinkList p,q,s,rear; p=La-next; q=Lb-next; Lc=rear=La; free(Lb); while(p&q) if (p-datadata) s=p;p=p-next; else s=q;q=q-next; rear-next=s;/*较小元素插入表尾*/ rear=rear-next; if (p) rear-next=p; else rear-next=q; /*主函数部分,文件名为sllink.c*/#include sllink.h void main() LinkList La,Lb,Lc; ElemType e; int select; do printf( 1 建立无序表，再删除指定元素n); printf( 2 建立递增有序表，再逆置n); printf( 3 建立两个递增有序表，将它们和并为一个仍递增表n); printf( 0 退出，请输入选项(0-3)n); scanf(%d,&select); switch(select) case 0: break; case 1: CreateList(La); Traverse(La); printf(输入需删除的元素n); scanf(%d,&e); Delete(La,e); Traverse(La); break; case 2: Create_Sort(La); Traverse(La); exch(La); printf(The list that is exchagedn); Traverse(La); break; case 3: Create_Sort(La);Traverse(La); Create_Sort(Lb);Traverse(Lb); MergeIncrease(La,Lb,Lc);Traverse(Lc); break; default: printf(输入选项错误，请重新输入！n); while(select); 实验三 链式存储结构（二）-双向链表的有关操作/*双向链表的有关操作*/ #include #include typedef int ElemType; typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; /*尾插法建立双向链表*/ void CreateList(DuLinkList *L) DuLinkList p; ElemType e; printf(Create a new double_linked_list:n); *L=(DuLinkList)malloc(sizeof(DuLNode); (*L)-next=(*L)-prior=*L; printf(Input data(end of 0)n); scanf(%d,&e); while(e) p=(DuLinkList)malloc(sizeof(DuLNode); p-data=e; p-next=*L; p-prior=(*L)-prior; (*L)-prior=(*L)-prior-next=p; /*在*h结点前插入结点*p*/ scanf(%d,&e); /*遍历双向链表*/ void visit(DuLinkList L) DuLinkList p; printf(遍历链表n); for(p=L-next;p!=L;p=p-next) printf(%5d,p-data); printf(n); /*设元素为整型,把所有奇数排列在偶数之前*/ void Divi(DuLinkList *L) DuLinkList p,q; p=(*L)-next; q=(*L)-prior; while (p!=q) while(p!=q&p-data%2!=0)p=p-next; /*从前向后查找偶数*/ while(p!=q&q-data%2=0)q=q-prior; /*从后向前查找奇数*/ (*L)-data=p-data; p-data=q-data; q-data=(*L)-data; / p, q所指结点的元素交换，头结点为中间变量 /*非递减有序双向链表的插入元素k序列仍有序*/ void Insert(DuLinkList *L,ElemType e) DuLinkList p,s; s=(DuLinkList )malloc(sizeof(DuLNode); s-data=e; p=(*L)-next; while(p!=*L & p-datanext; s-next=p; s-prior=p-prior; p-prior=p-prior-next=s; /*结点*p之前插入结点*s */ /*判断双向链表中元素是否对称若对称返回1否则返回0*/ int Symmetric(DuLinkList L) DuLinkList p,q; p=L-next; q=L-prior; while (p!=q&q-next!=p) if (p-data=q-data) p=p-next;q=q-prior; else return(0); return(1); /*主函数部分*/ void main() DuLinkList L; ElemType e; int select; do printf(n1 Judge if the list is symmetric); printf(n2 divide odd and even); printf(n3 Insert an element in a sorted list); printf(n0 退出 Please select(0-3):n); scanf(%d,&select); switch(select) case 1: CreateList(&L); visit(L); if(Symmetric(L) printf(n元素对称！); else printf(n元素不对称！); break; case 2: CreateList(&L);visit(L); Divi(&L);visit(L); break; case 3: CreateList(&L);visit(L); printf(Input an element); scanf(%d,&e); Insert(&L,e); visit(L); break; case 0: break; default: printf(Error! Again!n); while(select); /* 实验四 栈和队列 */ #include #include typedef int SElemType;/栈的元素类型 /*链栈的定义*/ typedef struct Node SElemType data; struct Node *next; NODE; typedef struct NODE *top;/链式栈的栈顶指针 Stack; #define TRUE 1 #define FALSE 0 #define OK 1 #define OVERFLOW -2 typedef int Status; /*链式栈的操作示例*/ void InitStack(Stack &S) S.top=(NODE *)malloc(sizeof(NODE); if (!S.top)exit(OVERFLOW);/栈溢出 S.top-next=NULL; Status StackEmpty(Stack S) if (S.top-next=NULL) return(TRUE); else return(FALSE); void Push(Stack &S,SElemType e) NODE *p; p=(NODE *)malloc(sizeof(NODE); if (!p)return; /栈满溢出 p-data=e; p-next=S.top-next; S.top-next=p; void Pop(Stack &S,SElemType &e) NODE *p; if (StackEmpty(S) return;/栈空 else p=S.top-next; e=p-data; S.top-next=p-next; free(p); SElemType Gettop(Stack &S) NODE *p; if (StackEmpty(S)return 0;/栈空 else p=S.top-next; return(p-data); /*主函数部分示例文件名为stackqueue.c*/#include linksq.h void main() int select; SElemType num=1,e; Stack S; InitStack(S); do printf(n1 Push 2 Popn); printf(0 exitn please selcet(0-2)n); scanf(%d,&select); switch(select) case 1: printf(Push%2d ,num); Push(S,num+); b