《数据结构》上机实验指导new.doc

《《数据结构》上机实验指导new.doc》由会员分享，可在线阅读，更多相关《《数据结构》上机实验指导new.doc（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导书方义秋 编著黄梅根 改程序计算机综合实验中心目录数据结构上机实验的目的和要求1实验一、单链表的插入和删除2实验二、二叉树操作6实验三、图的遍历操作10实验四、排序17实验五、查找23数据结构上机实验的目的和要求通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：1、 需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（1） 输入的形式和输出值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入输出结果和错误的输入及输出结果。2、 概要设计

2、：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。3、 详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。4、 调试分析：（1） 调试过程中所遇到的问题及解决方法；（2） 算法的时空分析；（3） 经验与体会。5、 用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。6、 测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。实验一、单链表的插入和删除一、目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有

3、重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。三、示例程序：(vc+调试通过)#includestdio.h#includestring.h#includestdlib.h#includectype.htypedef struct node /定义结点 char data10; /结点的数据域为字符串struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表ListNode *Locate

4、Node(); /函数，按值查找结点void DeleteList(); /函数，删除指定值的结点void printlist(); /函数，打印链表中的所有值void DeleteAll(); /函数，删除所有结点，释放内存/=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode *p=head-next; /从开始结点比较 while(p&strcmp(p-data,key)!=0) /直到p为NULL或p-data为key止p=p-next; /扫描下一个结点 return

5、p; /若p=NULL则查找失败，否则p指向找到的值为key的结点/=用尾插入法建立带头结点的单链表= LinkList CreatListR1(void) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 ListNode *s,*r,*pp; r=head; r-next=NULL; printf(Input # to end ); /输入“#”代表输入结束 printf(Please input Node_data:); scanf(%s,ch); /输入各结点的字符串 while(strcmp(ch,#

6、)!=0) pp=LocateNode(head,ch); /按值查找结点，返回结点指针 if(pp=NULL) /没有重复的字符串，插入到链表中 s=(ListNode *)malloc(sizeof(ListNode); strcpy(s-data,ch); r-next=s; r=s; r-next=NULL; printf(Input # to end ); printf(Please input Node_data:); scanf(%s,ch); return head; /返回头指针/=删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,

7、char *key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找结点的 if(p=NULL ) /若没有找到结点，退出printf(position error);exit(0); while(q-next!=p) /p为要删除的结点，q为p的前结点q=q-next; r=q-next; q-next=r-next; free(r); /释放结点/=打印链表=void printlist(LinkList head) ListNode *p=head-next; /从开始结点打印 while(p)printf(%s, ,p-

8、data);p=p-next; printf(n);/=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p-next)r=p-next;free(p);p=r; free(p);/=主函数=void main() char ch10,num10; LinkList head; head=CreatListR1(); /用尾插入法建立单链表，返回头指针 printlist(head); /遍历链表输出其值 printf( Delete node (y/n):); /输入“y”或“n”去选择是否删除结点 sc

9、anf(%s,num); if(strcmp(num,y)=0 | strcmp(num,Y)=0) printf(Please input Delete_data:); scanf(%s,ch); /输入要删除的字符串 DeleteList(head,ch); printlist(head); DeleteAll(head); /删除所有结点，释放内存四、实验内容1、 分析、理解程序。2、 调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、 修改程序：（1

10、） 增加插入结点的功能。（2） 将建立链表的方法改为头插入法。五、实验报告要求1、 基本要求见第一页内容。2、 写出实验结果，并画出所建链表的示意图。实验二、二叉树操作一、 目的掌握二叉树的定义、性质及存储方式，各种遍历算法。二、 要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、 示例程序（vc+）#include stdafx.h#includestdlib.h#includestdio.h#includestring.h#define Max 20 /结点的最大个数typedef struct node char da

11、ta; struct node *lchild,*rchild;BinTNode; /自定义二叉树的结点类型typedef BinTNode *BinTree; /定义二叉树的指针int NodeNum,leaf; /NodeNum为结点数，leaf为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点“#”以示空指针的位置=BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar()=#)return(NULL); /读入#，返回空指针 else T=(BinTNode *)malloc(sizeof(Bi

12、nTNode); /生成结点T-data=ch;T-lchild=CreatBinTree(); /构造左子树T-rchild=CreatBinTree(); /构造右子树return(T); /=NLR 先序遍历=void Preorder(BinTree T) if(T) printf(%c,T-data); /访问结点Preorder(T-lchild); /先序遍历左子树Preorder(T-rchild); /先序遍历右子树 /=LNR 中序遍历= void Inorder(BinTree T) if(T) Inorder(T-lchild); /中序遍历左子树printf(%c,T

13、-data); /访问结点Inorder(T-rchild); /中序遍历右子树 /=LRN 后序遍历=void Postorder(BinTree T) if(T) Postorder(T-lchild); /后序遍历左子树Postorder(T-rchild); /后序遍历右子树printf(%c,T-data); /访问结点 /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T) int hl,hr,max; if(T)hl=TreeDepth(T-lchild); /求左深度hr=TreeDepth(T-rchild); /求右深度m

14、ax=hlhr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0，即为叶子。return(max+1); else return(0);/=利用“先进先出”（FIFO）队列，按层次遍历二叉树=void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum;p=cqfront; /出队pr

15、intf(%c,p-data); /出队，输出结点的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-lchild; /左子树入队if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild; /右子树入队 /=主函数=void main() BinTree root; int i,depth; printf(n);printf(Creat Bin_Tree； Input preorder:); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=Crea

16、tBinTree(); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。printf(t* select *n);printf(t1: Preorder Traversaln); printf(t2: Iorder Traversaln);printf(t3: Postorder traversaln);printf(t4: PostTreeDepth,Node number,Leaf numbern);printf(t5: Level Depthn); /按层次遍历之前，先选择4，求出该树的结点数。printf(t0: Exitn);printf(t*n);scanf(%d

17、,&i); /输入菜单序号（0-5）switch (i)case 1: printf(Print Bin_tree Preorder: );Preorder(root); /先序遍历break;case 2: printf(Print Bin_Tree Inorder: );Inorder(root); /中序遍历break;case 3: printf(Print Bin_Tree Postorder: );Postorder(root); /后序遍历break;case 4: depth=TreeDepth(root); /求树的深度及叶子数printf(BinTree Depth=%d

18、BinTree Node number=%d,depth,NodeNum);printf( BinTree Leaf number=%d,leaf);break;case 5: printf(LevePrint Bin_Tree: );Levelorder(root); /按层次遍历break;default: exit(1);printf(n); while(i!=0);四、 实验内容1、 分析、理解程序。2、 调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。五、 实

19、验报告要求1、 基本要求见第一页。2、 画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。3、 给出实验结果。实验三、图的遍历操作一、 目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、 要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。三、 DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，依次

20、继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，Vt；再依次访问与V1，V2，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、 示例程序1 邻接矩阵作为存储结构的程序示例（vc+）#includestdio.h#includestdlib.h#define MaxVertexNum 100 /定义最大顶点数typed

21、ef struct char vexsMaxVertexNum; /顶点表 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数eMGraph; /用邻接矩阵表示的图的类型/=建立邻接矩阵=void CreatMGraph(MGraph *G) int i,j,k; char a; printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /输入顶点数和边数 scanf(%c,&a); printf(Input Vertex str

22、ing:); for(i=0;in;i+) scanf(%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表 for(i=0;in;i+)for(j=0;jn;j+) G-edgesij=0; /初始化邻接矩阵 printf(Input edges,Creat Adjacency Matrixn); for(k=0;ke;k+) /读入e条边，建立邻接矩阵 scanf(%d%d,&i,&j); /输入边（Vi，Vj）的顶点序号 G-edgesij=1; G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef

23、enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j; printf(%c,G-vexsi); /访问顶点Vi visitedi=TRUE; /置已访问标志 for(j=0;jn;j+) /依次搜索Vi的邻接点if(G-edgesij=1 & ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点void DFS(MGraph *

24、G) int i; for(i=0;in;i+)visitedi=FALSE; /标志向量初始化 for(i=0;in;i+)if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索/=BFS：广度优先遍历=void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定义队列 for(i=0;in;i+)visitedi=FALSE; /标志向量初始化 for(i=0;in;i+)cqi=-1; /队列初始化 printf(%c,G-v

25、exsk); /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) /队非空则执行 i=cqf; f=f+1; /Vf出队 for(j=0;jn;j+) /依次Vi的邻接点Vj if(G-edgesij=1 & !visitedj) /Vj未访问 printf(%c,G-vexsj); /访问Vj visitedj=TRUE; r=r+1; cqr=j; /访问过Vj入队 /=main=void main() int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGrap

26、h); /为图G申请内存空间 CreatMGraph(G); /建立邻接矩阵 printf(Print Graph DFS: ); DFS(G); /深度优先遍历 printf(n); printf(Print Graph BFS: ); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf(n);执行顺序：V6V4V5V7V2V3V1V0Vo图G的示例Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: Input edges,Creat Adjacency Matrix0 10 21 31 42 52 63

27、74 75 6Print Graph DFS: Print Graph BFS: 2 邻接链表作为存储结构程序示例#includestdio.h#includestdlib.h#define MaxVertexNum 50 /定义最大顶点数typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域EdgeNode;typedef struct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针VertexNode;typedef VertexNode Ad

28、jListMaxVertexNum; /AdjList是邻接表类型typedef struct AdjList adjlist; /邻接表 int n,e; /图中当前顶点数和边数 ALGraph; /图类型/=建立图的邻接表=void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定义边表结点 printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /读入顶点数和边数 scanf(%c,&a); printf(Input Vertex st

29、ring:); for(i=0;in;i+) /建立边表 scanf(%c,&a);G-adjlisti.vertex=a; /读入顶点信息G-adjlisti.firstedge=NULL; /边表置为空表 printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /建立边表 scanf(%d%d,&i,&j); /读入边（Vi，Vj）的顶点对序号s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点s-adjvex=j; /邻接点序号为js-next=G-adjlisti.firstedge;G

30、-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /邻接点序号为is-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(ALGraph *G,int i) /以Vi为出发点

31、对邻接链表表示的图G进行DFS搜索 EdgeNode *p; printf(%c,G-adjlisti.vertex); /访问顶点Vi visitedi=TRUE; /标记Vi已访问 p=G-adjlisti.firstedge; /取Vi边表的头指针 while(p) /依次搜索Vi的邻接点Vj，这里j=p-adjvexif(! visitedp-adjvex) /若Vj尚未被访问 DFSM(G,p-adjvex); /则以Vj为出发点向纵深搜索p=p-next; /找Vi的下一个邻接点 void DFS(ALGraph *G) int i; for(i=0;in;i+)visitedi=

32、FALSE; /标志向量初始化 for(i=0;in;i+)if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索/=BFS：广度优先遍历=void BFS(ALGraph *G,int k) /以Vk为源点对用邻接链表表示的图G进行广度优先搜索 int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /定义FIFO队列 for(i=0;in;i+)visitedi=FALSE; /标志向量初始化 for(i=0;in;i+)cqi=-1; /初始化标志向量 printf(%c,G-adjlistk.vertex)

33、; /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) 队列非空则执行i=cqf; f=f+1; /Vi出队p=G-adjlisti.firstedge; /取Vi的边表头指针while(p) /依次搜索Vi的邻接点Vj（令p-adjvex=j） if(!visitedp-adjvex) /若Vj未访问过printf(%c,G-adjlistp-adjvex.vertex); /访问Vjvisitedp-adjvex=TRUE;r=r+1; cqr=p-adjvex; /访问过的Vj入队 p=p-next

34、; /找Vi的下一个邻接点 /endwhile/=主函数=void main() int i;printf(input vex);scanf(%d,&i); ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatALGraph(G); printf(Print Graph DFS: ); DFS(G); printf(n); printf(Print Graph BFS: ); BFS(G,i); printf(n);执行顺序：Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: V6V4V5V7V2V3V1V0Vo图G的示例Input edges,Creat Adjacency List0 10 21 31 42 52 63 74 75 6Print Graph DFS: Print Graph BFS: 五、 实验内容1、 分析、理解程序。2、 调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有