《数据结构》实验指导书(源代码).doc

实验一 线性表的链式存储结构一、 实验目的： 1掌握线性表的链式存储结构。2熟练地利用链式存储结构实现线性表的基本操作。 3能熟练地掌握链式存储结构中算法的实现。二、实验内容： 1用头插法或尾插法建立带头结点的单链表。 2实现单链表上的插入、删除、查找、修改、计数、输出等基本操作 。三、实验要求：1. 根据实验内容编写程序，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时：2学时五、实验步骤：1进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。 定义单链表的数据类型，然后将头插法和尾插法、插入、删除、查找、修改、计数、输出等基本操作都定义成子函数的形式，最后在主函数中调用它，并将每一种操作前后的结果输出，以查看每一种操作的效果。 部分参考程序/单链表的建立(头插法)，插入，删除，查找、修改、计数、输出 #include #define elemtype intstruct link elemtype data；/元素类型 link *next； /指针类型，存放下一个元素地址; /头插法建立带头结点的单链表 link *hcreat() link s,p; elemtype i; couti； p=new link； p-next=NULL； while(i) /当输入的数据不为0时，循环建单链表 s=new link； s-data=i； s-next=p-next； p-next=s； cini； return p；/输出单链表void print(1ink *head) 1ink *p； p=head-next； while(p-next!=NULL) coutdata”； /输出表中非最后一个元素p=p-next； coutdata； /输出表中最后一个元素 coutnext； while(p!=NULL)&(p-data!=x) p=p-next； return p； /在head为头指针的单链表中，删除值为x的结点 void deletel(1ink *head，elemtype x) 1ink *p， *q； q=head； p=head-next； while(p!=NULL)&(p-data!=x) q=p；p=p-next；If(p=NULL) coutnext=p -next；delete(p)；/在头指针head所指的单链表中，在值为x的结点之后插入值为y的结点void insert(1ink *head，elemtype x，elemtype y) link *p， *s； s=new link； s-data=y； if(head-next=NULL) /链表为空head-next=s；s-next=NULL： p=Locate(head，x)；/调用查找算法 if(p=NULL)coutnext=p-next；p-next=s；/将单链表p中所有值为x的元素修改成yvoid change(1ink *p,elemtype x,elemtype y)link *q；q=p-next；while(q!=NULL) if(q-data=x) q-data=y； q=q-next； void count(1ink *h) /统计单链表中结点个数1ink *p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next；return n;void main() int n； elemtype x，y； link *p， *q； p=hcreat()； /头插法建立链表 print(p)； /输出刚建立的单链表 couty； deletel(p，y)； print(p)； /输出删除后的结果 coutx； couty； insert(p，x，y)； print(p)； /输出插入后的结果 coutxy； change(p，x，y)； print(p)； coutx； q=Locate(p，x)； if(q=NULL)coutx”不在表中，找不到!”endl； else coutx”在表中，已找到!”endl； n=count(p)； cout”链表中结点个数为：”nendl： /单链表的建立(尾插法)、插入、删除、查找、修改、计数、输出#include#define elemtype intstruct link elemtype data；/元素类型 link *next；/指针类型，存放下-个元素地址；/尾插法建立带头结点的单链表link *rcreat() link *s， *p， *r； elemtype i；couti; p=r=new link； p-next=NULL； while(i) s=new link； s-data=i； r-next=s； r=s； cini； r-next=NULL；return p；/输出单链表void print(1ink *head)link *p； p=head-next； while(p-next!=NULL) coutdata”; /输出表中非最后一个元素 p=p-next； ) coutdata； /输出表中最后一个元素 coutendl； link *Locate(1ink *head，int x) 在单链表中查找第x个结点 link *p； p=head； int j=0； while(p!=NULL)&(jnext; j+； return p； void delete I(1ink *head，elemtype x)/在head为头指针的单链表中，删除值为x的结点 link *p, *q； q=head； p=head-next； while(p!=NULL)&(p-data!=x) q=p； p=p-next；) if(p=NULL)coutnext=p-next；delete(p)； void insert(1ink *head，int x,elemtype y)/在头指针head所指单链表中，在第x个结点之后插入值为y的结点link *p， *s； s=new link； s-data=y； if(head-next=NULL)/链表为空 head-next=s； s-next=NULL： p=Locate(head，x)； /调用查找算法 if(p=NULL) coutnext=p-next；p-next=s；void change(1ink *p,elemtype x，elemtype y)将单链表P中所有值为x的元素改成值为ylink *q； q=p-next； while(q!=NULL) if(q-data=x)q-data=y； q=q-next； void count(1ink *h) /统计单链表中结点个数(1ink *p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next； retum n;void main() int n; link p,q;p=rcreat()；/尾插法建立链表print(p)； /输出刚建立的单链表couty；deletel(p，y)；print(p)； /输出删除后的结果coutx；couty；insert(p，x，y)；print(p)； /输出插入后的结果coutxy；change(p，x，y)；print(p)；coutx；q=Locate(p ,x)；if(q=NULL)coutx”不在表中,找不到!”endl；else coutx”在表中，已找到!”endl；n=count(p)；cout”链表中结点个数为：”nendl;六、选作实验试设计一元多项式相加（链式存储）的加法运算。 A（X）=7+3X+9X8+5X9 B（X）=8X+22X7-9X8 1建立一元多项式； 2输出相应的一元多项式； 3相加操作的实现。实验二 循环链表的操作一、 实验目的： 通过本实验中循环链表和双向链表的使用，使学生进一步熟练掌握链表的操作方式。二、实验内容： 本次实验可以从以下两个实验中任选一个： 1建立一个单循环链表并实现单循环链表上的逆置。 所谓链表的逆置运算(或称为逆转运算)是指在不增加新结点的前提下，依次改变数据元素的逻辑关系，使得线性表(al，a2，a3，an)成为(an，a3，a2，a1)。2. 构建一个双向链表，实现插入、查找和删除操作。三、实验要求：1. 根据实验内容编写程序，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时：2学时五、实验步骤：1进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。 建立一个带头结点的单循环链表，从头到尾扫描单链表L，把p作为活动指针，沿着链表向前移动，q作为p前趋结点，r作为q的前趋结点。其中，q的next值为r；r的初值置为head。 双向链表的构造与单链表相同，至于它的插入与删除运算比单链表复杂，插入运算需要4步操作，删除运算需要2步操作，注意语句的次序，不要任意交换位置，以免不能正确插入或删除结点。 部分参考程序/循环链表 头文件h1h的内容 #define NULL 0 #include #include typedef struct node int num； struct node *next；linklist；以下是主程序#include”h1h”输出循环链表的信息void output(linklist *head)linklist *p；p=head-next；while(p!=head)printf(”d”，p-num)；p=p-next；printf(”n”)；/建立单循环链表Linklist *creat(int n) int k; linklist *head,*r,*p； p=(linklist*)malloc(sizeof(linklist)； head=p； r=p； p-next=p；for(k=1；knum=k； r-next=p； r=p； p-next=head；return(head)；逆置函数linklist *invert(linklist *head)Linklist *p，*q，*r；p=head-next；q=head；while(p!=head) r=q； q=p； p=p-next； q-next=r； head-next=q； return(head)； void main() int n； Linklist *head； printf(“输入所建立的循环链表的结点个数：n”)； scanf(“%d”，n)； head=creat(n)； printf(”输出建立的单循环链表：n”)； output(head)； printf(”现在进行逆置! n”)； head=invert(head)； printf(”输出进行逆置运算后的单循环链表的结点信息! n”)； output(head)； /双向链表参考程序 /以下是头文件hhh的内容 #include #include typedef struct dupnode int data； struct dupnode *next,*prior；dulinklist；/以下是主程序的内容#include”hhh”/create函数用来构建双向链表dulinklist *create()dulinklist *head,*p，*r; int i，n；head=(dulinklist*)malloc(sizeof(dulinklist )；head-next=NULL；head-prior=NULL；r=head；printf(“请输入所建双向链表中结点的个数：n”)；scanf(“d”,n)；for(i=l；idata)； p-next=NULL； r-next=p； p-prior=r； r=r-next； return(head)；/find函数用来实现在双向链表中按序号查找某个结点的功能。void find(dulinklist *h)int k,i；dulinklist *p；p=h；i=0：printf(”输入要查找结点的序号：n”)； scanf(”%d”,&k)； while(p!=NULL)&(inext； i+： if(p)printf(”所查到的结点的值为：n”)； printf(”%dn”,p-data)； elseprintf(”没找到该结点! n”)；/insdulist函数用来实现在双向链表中按序号插入结点的功能dulinklist *insdulist(dulinklist *head，int i，int x)dulinklist *p，*s；int j；p=head；j=0；whi1e(p-next!=head)&(jnext；j+；If(j=i-1)s(dulinklist*)malloc(sizeof(dulinklist)；s-data=x；s-prior=p；s-next=p-next；p-next-prior=s；p-next=s；elseprintf(”errorn”)；return head；/deledulist函数实现在双向链表中按序号删除某个结点的功能dulinklist *deledulist(dulinklist *head，int i)dulinklist *p；int j；p=head； j=0while(p-next!=head)&(jnext； j+； If(j=i)p-prior-next=p-next；p-next-prior=p-prior；free(p)；else printf(”error n”)；return head； /output函数用来输出整个双向链表的结点值void output(dulinklist *h) dulinklist *p；p=h-next；while(p!=NULL)printf(”输出该双向链表的结点，分别为： n”)；printf(”%dn”,p-data)；p=p-next； void main()dulinklist *head；int flag=l，i，k，x；while(flag) /flag作为判断循环的标志位 printf(”1建立双向链表 n”)； printf(”2查找某个结点 n”)； printf(”3插入一个结点 n”)； prtntf(”4删除一个结点 n”)； printf(”5退出 n”)；printf(”请输入选择：n“)；scanf(”%d”，&i)；switch(i) case 1：head=create0；break； case 2：find(head)；break； case 3：printf(”输入待插的结点的序号及新插入结点的data值. n”); scanf(”%d%d”，k，x)； head=insdulist(head，k，x)； output(head)； break； case 4：printf(”输入要删除的结点的序号. n”)；scanf(”%d，k)；head=deledulist(head，k)；output(head)；break；case 5: flag=0；/while循环结束此程序不论是插入、查找还是删除运算均是按序号的方式来处理，当然也可改为按结点的值来作相应的处理，试修改以上程序实现按值操作的功能。 六、选作实验 利用单循环链表存储结构，解决约瑟夫（Josephus）环问题。即：将编号是1,2,n(n0)的n个人按照顺时针方向围坐一圈，每人持有一个正整数密码。开始时任选一个正整数作为报数上限值m,从某个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有的人全部出列为止。令n最大值取30。设计一个程序，求出出列顺序，并输出结果。实验三 树形结构一、 实验目的： 1掌握二叉树的数据类型描述及二叉树的特性。2掌握二叉树的链式存储结构(二叉链表)的建立算法。3掌握二叉链表上二叉树的基本运算的实现。二、实验内容： 从以下1、2和3、4中各选择一项内容1. 用递归实现二叉树的先序、中序、后序3种遍历。2. 用非递归实现二叉树的先序、中序、后序3种遍历。3. 实现二叉树的层次遍历。4.将一棵二叉树的所有左右子树进行交换。 三、 实验要求： 1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时：4学时五、实验步骤： 1进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。 将建立二叉树及先序、中序、后序3种遍历算法都写成子函数，然后分别在主函数中调用它，但在建立二又树中，必须把二叉树看成完全二叉树的形式。若不是完全二叉树，则在输入数据时，用虚结点(不存在)表示(本算法中，用“，”号代替)。 用非递归法实现二叉树的遍历非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈顶指针。 实现二叉树的层次遍历 用一个一维数组代替队列，实现二叉树的层次遍历。将一棵二叉树的所有左右子树进行交换。 本算法只要增加一个实现二叉树左右子树交换的子函数即可。为了便于查看，在主函数将交换前后的三种遍历效果，分别输出。以下为部分参考程序：/递归实现二叉树的3种遍历#includetypedef char elemtype；struct bitree定义二叉树数据类型elemtype data； /结点信息bitree *lchild，*rchild； /左右孩子;bitree *create() /建立二叉链表 bitree *root, *s，*q100； /q为队列，最大空间为100int front=l，rear=0； /队列头、尾指针char ch；root=NULL；cout”请输入结点值(，为虚结点，#结束)：”ch；while(ch!=#)s=NULL；if(ch!=,) s=new bitree； s-data=ch； s-lchild=NULL； s-rchild=NULL； rear+； qrear=s； /进队 if(rear=1) root=s；elseif(s!=NULL)&(qfront!=NULL) if(rear%2=0) qfront-lchild=s； else qfront-rchid=s；if(rear2=1)front+； /出队cinch；return root：void preorder(bitree *root) /先序遍历bitree *p；p=root；if(p!=NULL)coutdatalchild)； preorder(p-rchild)；void inorderl(bitree *root) /中序遍历bitree*p；p=root；if(p!=NULL) inorder(p-lchild)； coutdatarchild)；void postorder( bitree *root) /后序遍历 bitree *p；p=root；if(p!=NULL) postorder(p-lchild)； postorder(p-rchild)；coutdata“”； void main()bitree *root；root=create()； /建立二叉链表cout”先序遍历的结果”endl； preorder(root)；coutendl； cout”中序遍历的结果”endl；inorder(root)；coutendl：cout”后序遍历的结果”endl；postorder(root)；cout0) while(p!=NULL) coutdatalchild； p=stop-； /退栈p=p-rchild； void inorderl(bitree*root) /中序遍历bitree*p，*s100； int top=0； p=root； while(p!=NULL)Il(topO) while(p!=NULL) s+top=p；p=p-lchild； p=stop-； coutdatarchild； void postorderl( bitree *root) /后序遍历(bitree *p *sl100； int s2100，top=0，b； p=root； do while(p!=NULL) s1top=p；s2top+=0； p=p-lchild；) if(top0) (b=s2-top； p=s1top； if(b=0) sltop=p；s2top+=l； p=p-rchild； elsecoutdata0)；/ /建立二叉链表参考前述程序/按照层次遍历二叉链表#includetypedef char elemtype；struct bitree elemtype data； /结点信息bitree *lchild，*rchild； /左右孩子;/按层次遍历二叉树(建立二叉链表同前)void lorder(bitree *t) bitree q100，*p； /q代表队列int f,r; /f，r类似于队列头、尾指针q1=t； f=r=l；cout”按层次遍历二叉树的结果为：”;while if=r) p=qf； f+； /出队 coutdatalchild!=NULL) r+；qr=p-lchild； /入队 if p-rchild!=NULLl r+； qr=p-rchild; /入队 coutlchild); leftOright(root-rchild); bitree *t=root-lchild; root-lchild=root-rchild; root-rchild=t;/主函数 void main()bitree *root；root=create()； /建立二叉链表coutendlendl”左右子树交换前的遍历结果”endl；cout”先序遍历的结果”endl； preorder(root)；coutendl； cout”中序遍历的结果”endl；inorder(root)；coutendl：cout”后序遍历的结果”endl；postorder(root)；coutendl；leftTOright(root)；coutendlendl”左右子树交换后的遍历结果”endl；cout”先序遍历的结果”endl；preorder(root)；coutendl；cout”中序遍历的结果”endl；inorder(root)；coutendl；cout”后序遍历的结果”endl；postorder(root)；coutarcsvw.adj=l； return； void del_arc(graph *g，int v，int w) g-arcvw.adj=0； retum; /内容1参考程序 #define maxnode 40 #define null 0 #include typedef struct st_arc int adjvex； int weight； struct st_arc *nextrac；arcnode； typedef struct int vertex； struct st_arc *firstarc；vernode； typedef vernode adjlistmaxnode； void del_arc(vernode g，int v，int w) /删除从顶点v到顶点w的边 arcnode *rl,*r2； rl=gvfrrstarc；r2=rl；while(r1!=null&r1-adjvex!=w)r2=rl;rl=rl-nextarc；if (rl=null)printf(”no edge v-w”)；return；elseif(r1=r2) /当只有一个边结点时gv.firstarc=r1-nextarc；else r2-nextarc=r1-nextarc； /有多个边结点时rl=gw.firstarc；r2=rl；while(r1!=null&r1-adjvex!=v) /在以v为头结点的链表中，删除相应的 /边结点r2=rl；rlrl-nextarc；if (rl=null)printf(”no edge v-w.”)；return；elseif(r1=r2)gw.firstarc=rl-nextarc；elser2-nextarc=r1-nextarc；void print(vernode g，int n) /打印图中各结点的结构arcnode *q；int i；printf(”adjacency list of the graph：n”)；for(i=0；iadjvex)；printf(”%dt”，q-weight)；q=q-nextarc； printf(”n”)； main() int i，j，n，k，w，v； arcnode *p，*q； adjlist g； printf(”Input node： ”)； /输入图中顶点个数 scanf(”%d”，&n)； for(k=0；kadjvex=j； q-weight=w； q-nextarc=gi.firstarc； /头指针指向新的边结点 gi.firstarc=q； p=(arcnode*)malloc(sizeof(arcnode)； p-nextarc=gi.firstarc； gi.firstarc=q； p=(arcnode*)malloc(sizeof(arcnode)； p-adjvex=i； p-weight=w； p-nextarc=gj.firstarc； gj.firstarc=p； print(g，n)； printf(”Delete edge V-w：”)；scanf(”%d%d”，v，&w)；del_arc(g，v，w)；print(g，n)； 内容2的知识要点：构造有向图链接表与无向图链接表的算法区别是：无向图两结点无向对偶，因而邻接表有一定的对偶性；有向图两结点间有向无对偶关系，因而建立邻接表时应根据输入的顶点及边的有向关系建立(当箭头方向离开结点为有关，当箭头方向指向结点为无关)。/内容2的参考程序/有向图链表的存储结构为：typedef struct st_arc int aajvex； /存放依附于该边的另一顶点在一维数组中的序号int weight； /存放和该边有关的信息，如权值等struct st_arc *nextarc； /依附于该顶点的下一个边结点的指针arcnode；typedef structint vertex； /存放与顶点有关的信息struct st_arc*firstarc；vernode； /存储顶点信息typedef vernode adjlistmaxnode；/参考程序见内容1 内容3的知识要点：深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从vo出发，访问vo的一个未被访问过的邻接顶点w1，再