数据结构实验指导书.docx

1、数据结构实验指导书实验一、线性结构的插入和删除实验目的和要求：掌握线性结构的定义、组织形式、结构特征和类型说明以及在这两种存储方式下实现的插入、删除和按值查找的算法。循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。实验内容：实验题目1、已知长度为n的线性表,要求将new_data插入到线性表中使之成为第j个元素。2、已知长度为n的线性表,要求将线性表中第j个位置上的数据元素删除。实验准备1、思考怎样实现线性表顺序存储结构中元素的插入。2、思考怎样实现线性表顺序存储结构中元素的删除。实验步骤1、将new_data插到长度为n的线性表中，使之成为第j个元素。(1)腾位置 将自第n

2、个位置开始至第j个位置上的所有数据元素统统往后移动一个位置。(2)插入元素 将new_data 插入到线性表中第j个位置。(3)线性表长度增1顺序表的类型 struct seqlist datatype listmax ;int length ; ; void insert （struct seqlist *L , int i , int new_data ） int j ; if (L-length= = max) exit () ;else for(j=L-length-1; j= i ; j+) L-listj+1=L-listj ; L-listi=new_data ; L-lengt

3、h+ ; 2、将长度为n的线性表中第j个位置上的数据元素删除 (1)移动删除 将自第j+1个位置开始至线性表中最后一个位置的数据元素全部前移一个位置。(2)线性表长度减1 顺序表的类型 struct seqlist datatype listmax ;int length ; ; void delete（struct seqlist *L , int i , int new_data ） int j ; if (L-length= = -1) exit () ;else for(j=i+1; jlength ; j+) L-listj-1=L-listj ; L-length- ; 实验二、树

4、型结构的遍历实验目的和要求：树的遍历是树的算法中最具有典型的,它的特点为递归,树的其它算法如：求树的高度、求叶子数等,都同该算法同出一辙,另外树的遍历算法应用比较广泛。实验内容：实验题目编写前序遍历、中序遍历、后序遍历二叉树的程序。实验准备1、掌握二叉树的特点及其存储方式。2、掌握二叉树的创建和显示方法。3、掌握二叉树遍历的基本方法：前序（DLR）、中序（LDR）、后序（LRD）实验步骤按下图的二叉树进行操作。1、 按上图建立二叉树，输入方法为：请输入按先序建立二叉树的结点序列： 说明：0代表后继结点为空，请逐个输入，按回车键输入下一个结点。 请输入根结点：a请输入a结点的左子结点: b请输入

5、b结点的左子结点: d请输入d结点的左子结点: 0请输入d结点的右子结点: 0请输入b结点的右子结点: 0请输入a结点的右子结点: c请输入c结点的左子结点:e请输入e结点的左子结点:0请输入e结点的右子结点: 0请输入c结点的右子结点: f请输入f结点的左子结点:0请输入f结点的右子结点: 02、 检查前序、中序、后序算法的正确。例：该二叉树前序遍历序列为：a b d c e f 该二叉树中序遍历序列为：d b a e c f该二叉树后序遍历序列为：d b e f c a 3、 遍历算法（递归过程）（1）前序遍历 若二叉树为空，遍历结束。否则A、访问根结点。B、前序遍历根结点的左子树。C、前

6、序遍历根结点的右子树。 void preorder(BT *T) if (T!=NULL) printf(“%c”, T-data) ; preorder(T-lchild) ; preorder(T-rchild) ; （2）中序遍历 若二叉树为空，遍历结束。否则A、中序遍历根结点的左子树。B、访问根结点。C、中序遍历根结点的右子树。 void preorder(BT *T) if (T!=NULL) preorder(T-lchild) ; printf(“%c”, T-data) ;preorder(T-rchild) ; （3）后序遍历若二叉树为空，遍历结束。否则A、 后序遍历根结点的

7、左子树。B、 后序遍历根结点的右子树。C、 访问根结点 void preorder(BT *T) if (T!=NULL) preorder(T-lchild) ; preorder(T-rchild) ; printf(“%c”, T-data) ; 实验三、图型结构算法及应用实验目的和要求：图有二个存储结构：邻接矩阵和邻接表,邻接矩阵的实验可以借鉴于实验一,邻接表的实验类似于单链表,图是最复杂的一种数据结构,掌握它有一定的代表意义。实验内容：实验题目邻接表表示图，并进行深度优先遍历实验准备了解什么是邻接表，什么是深度优先遍历实验步骤1、 定义数据类型#define MAX_VERTEX_N

8、UM 20 /最大顶点数 #define MAX_EDGE_NUM 40 /最大边数 int visited MAX_VERTEX_NUM; typedef int VertexType ; /顶点数据类型 typedef struct ArcNode int adjvex; int weight; struct ArcNode *nextarc; ArcNode; typedef struct VNode VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertic

9、es; int vexnum,arcnum; int kind; ALGraph; 2、 创建一个图void CreateDG(ALGraph &G) int i,j,k; ArcNode *p; cout创建一个图:endl; coutG.vexnum;coutendl; coutG.arcnum; coutendl; for(i=0;iG.vexnum;i+) G.verticesi.data=i; G.verticesi.firstarc=NULL; for(k=0;kG.arcnum;k+) cout请输入第k+1ij; p=(ArcNode*)malloc(sizeof(ArcNod

10、e); p-adjvex=j; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; 3、 输出图void Disp(ALGraph G) int i,j; ArcNode *p; cout输出图为:endl; for(i=0;iG.vexnum;i+) p=G.verticesi.firstarc; j=0; while(p!=NULL) cout(i,adjvexnextarc; j=1; if(j=1) coutendl; 4、 图的深度优先遍历void dfs(ALGraph G,int v) /深度优先遍历 ArcNode *

11、p; coutvadjvex) dfs(G,p-adjvex); p=p-nextarc; return ; void dfs1(ALGraph G) int i; for(i=0;iG.vexnum;i+) if(visitedi=0) dfs(G,i); 5、 主函数void main() ALGraph G; CreateDG(G); int v; Disp(G); coutv; cout深度优先序列:; dfs1(G); coutendl; 实验四、查找算法应用实验目的和要求：查找是日常经常使用的一种操作,掌握各种数据结构的查找算法有十分重要的意义。通过本次实验掌握顺序查找、树表查找、

12、散列表查找的基本思想及存储、运算的实现。实验内容：实验题目设有关键字序列k= 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 查找key=21的数据元素实验准备1、从键盘输入上述8个整数，存放在数组bub8中，并输出其值。2、从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。2、 从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。3、 具体算法int binarysearch(struct sstable stn+1 , elemtype k) int low=1 , high=1

13、; while(low=high) mid=(low+high)/2 ; if(k= =stmid.key) return(mid) ; else if(k high 时，返回查找失败信息； /表空，查找失败3、low =high , mid = (low+high)/2 / 取中点 (1) 若key bubmid , low=mid+1 ; 转2 (3) 若key = bubmid，返回数据元素在表中位置。实验五、排序算法应用实验目的和要求：掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想及实现。实验内容：实验题目将一组数据（97、49、65、76、49、

14、13、38、27）进行大堆排序实验准备1、 只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间2、 掌握堆的概念 什么是堆？n个元素的序列k1,k2,.,kn当且仅当满足下列关系时，称之为堆。关系一：ki=k2i 关系二：ki=k2i 1（i=1,2,.,n/2)3、堆排序要解决两个问题：a、如何由一个无序序列建成一个堆？ b、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？实验步骤sift(ListType &r,int k,int m) i=k;j=2*i;x=rk.key;finished=FALSE;t=rk;while(j=m)&(!finished) if (jr

15、j 1.key) j ;if (x0;i-) sift(r,i,n); for(i=n;i1;i-)r1ri;sift(r,i,i-1)实验六、设计学生成绩管理系统实验目的和要求：这是一个综合性、设计性实验，是为了让大家将前面所学的知识点进行概括和总结，并能够解决实际的应用问题。实验内容：实验题目利用前面所学到的知识设计出学生成绩管理系统合适的数据结构，并编程实现增加记录、删除记录、查找和排序功能。实验准备先复习链表结构、c语言的各种数据类型及操作语言的用法。熟练查找和排序的多种算法。实验步骤1、 定义学生成绩的数据结构 struct nodeint number;/*学号*/char nam

16、e10;/*姓名*/float yuwen;/*语文成绩*/float yingyu;/*英语成绩*/float shuxue;/*数学成绩 */struct node *next;2、 创建链表3、 增加学生资料,并且将所有学生资料按学号排序4、 查询学生成绩 struct *search2311(struct *head)/*函数search2311,功能：查询学生成绩*/int number;struct *p1,*p2;printf(输入要查询的学生的学号,);scanf(%d,&number);while(number!=0)if(head=NULL)printf(n没有任何学生资料

17、!n);return(head);printf(-n);printf(|学号t|姓名t|语文t|英语t|数学t|n);printf(-n);/*打印表格域*/p1=head;while(number!=p1-number&p1-next!=NULL)p2=p1;p1=p1-next; if(number=p1-number) printf(|%dt|%st|%.1ft|%.1ft|%.1ft|n,p1-number,p1-name,p1-yuwen,p1-yingyu,p1-shuxue);printf(-n);/*打印表格域*/else printf(%d不存在此学生!n,number);p

18、rintf(输入要查询的学生的学号,);scanf(%d,&number);printf(已经退出了!n);return(head);5、 删除学生资料struct *del2311(struct *head)/*函数del2311，功能：删除学生资料*/struct *p1,*p2;int number;printf(输入要删除的学生的学号(输入0时退出):);scanf(%d,&number);getchar();while(number!=0)/*输入学号为0时退出*/if(head=NULL)printf(n没有任何学生资料!n);return(head);p1=head;while(

19、number!=p1-number&p1-next!=NULL)/*p1指向的不是所要找的首结点，并且后面还有结点*/p2=p1;p1=p1-next; /*p1后移一个结点*/if(number=p1-number) /*找到了*/ if(p1=head)head=p1-next;/*若p1指向的是首结点，把地二个结点地址赋予head*/else p2-next=p1-next;/*否则将下一个结点地址 赋给前一结点地址*/printf(删除:%dn,number);n=n-1;elseprintf(%d不存在此学生!n,number);/*找不到该结点*/printf(输入要删除的学生的学

20、号:);scanf(%d,&number);getchar();#ifdef DEBUG printf(已经退出了!n);#endifprintf(现在的学生数为:%d个!n,n);return(head); 6、 定义排序函数struct *taxis2311(struct *head) /*定义排序函数。此函数带回一个指向链表头的指针*/ struct *p,*max;int i,j,x;float fen;char t10;if(head=NULL)printf(n没有任何学生资料，请先建立链表!n);return(head);/*链表为空*/max=p=head;for(i=0;i80

21、;i )printf(*);printf(1按学生学号排序t2按学生姓名排序t3按语文成绩排序n);printf(4按英语成绩排序t5按数学成绩排序tn);for(i=0;i80;i )printf(*);printf(请选择操作:);scanf(%d,&x);/*选择操作*/getchar();switch(x) /*用switch语句实现功能选择*/case 1 : for(i=1;in;i )for(j=i 1;jnext;if(max-numberp-number)k=max-number;max-number=p-number;p-number=k;/*交换前后结点中的学号值，使得学

22、号大者移到后面的结点中*/scpy(t,max-name);scpy(max-name,p-name);scpy(p-name,t);/*交换前后结点中的姓名，使之与学号相匹配*/fen=max-yuwen;max-yuwen=p-yuwen;p-yuwen=fen;/*交换前后结点中的语文成绩，使之与学号相匹配*/fen=max-yingyu;max-yingyu=p-yingyu;p-yingyu=fen;/*交换前后结点中的英语成绩，使之与学号相匹配*/fen=max-shuxue;max-shuxue=p-shuxue;p-shuxue=fen;/*交换前后结点中的数学成绩，使之与学号

23、相匹配*/max=head;p=head;/*重新使max,p指向链表头*/print2311(head);break;/*打印值排序后的链表内容*/case 2 : for(i=1;in;i )for(j=i 1;jnext;if(scmp(max-name,p-name)0)/*scmp=字符串比较函数*/scpy(t,max-name);/*scpy=字符串复制函数*/scpy(max-name,p-name);scpy(p-name,t);/*交换前后结点中的姓名，使得姓名字符串的值大者移到后面的结点中*/ k=max-number;max-number=p-number;p-numb

24、er=k;/*交换前后结点中的学号值，使之与姓名相匹配*/ fen=max-yuwen;max-yuwen=p-yuwen;p-yuwen=fen;/*交换前后结点中的语文成绩，使之与姓名相匹配*/fen=max-yingyu;max-yingyu=p-yingyu;p-yingyu=fen;/*交换前后结点中的英语成绩，使之与姓名相匹配*/fen=max-shuxue;max-shuxue=p-shuxue;p-shuxue=fen;/*交换前后结点中的数学成绩，使之与姓名相匹配*/p=head;max=head;print2311(head);break;case 3 : for(i=1;in;i )for(j=i 1;jnext;if(max-yuwenp-yuwen)fen=max-yuwen;max-yuwen=p-yuwen;p-yuwen=fen;/*交换前后结点中的语文成绩，使得语文成绩高者移到后面的结点中*/k=max-number;max-number=p-number;p-number=k; /*交换前后结点中的学号，使之与语文成绩相匹配*/scpy(t,max-name);scpy(max-name,p-name);scpy