算法与数据结构实验指导书

1、目 录预备知识3实验一：线性表的基本操作5一、线性表的顺序存储实验5（一）实验目的5（二）实验内容5（三）程序实现6（四）思考题10二、线性表的链式存储实验10（一）实验目的10（二）实验内容10（三）程序实现11（四）思考题13实验二：栈的基本操作14一、栈的顺序存储实验14（一）实验目的14（二）实验内容14（三）程序实现14（四）思考题17二、栈的链式存储实验17（一）实验目的：17（二）实验内容：17（三）程序实现17（四）思考题：19实验三：数组的基本操作20（一）实验目的20（二）实验内容20（三）程序实现20（四）思考题23实验四：二叉树的各种操作算法实现24（一）实验目的24（

2、二）实验内容24（三）程序实现24（四）思考题28实验五：图的各种操作算法实现30（一）实验目的30（二）实验内容30（三）程序实现30（四）思考题34实验六：综合设计实验-漫步迷宫36（一）实验目的36（二）实验内容36（三）程序设计37（四）思考题3939预备知识实验中的源程序一般分四部分：库文件和预设宏定义，数据存储结构定义，函数定义和实现，主函数调用。对于需要自己解决的实验题目，参考如下所示的一般结构，就能顺利编写数据结构程序。实验以visual c+6.00为调试环境，程序行的注释有两种：“/*-*/”或“/-”。/-库文件和预设宏定义#include /定义杂项函数及内存分配函数#

3、include #include #difine maxsize 100#define ok 1#define error 0/-定义数据存储结构typedef struct elemtype datamaxsize; int length;sqlist;/*-*/函数名：函数名称/参数： 参数描述/返回值：此函数返回值定义/功能：描述此函数的功能作用/*-*/void function1 (para1, para2) /*注释*/函数结束int function2 (para1, para2) /*注释*/ return ok;/函数结束/-主程序-void main () /注释-调用函数

4、function1 void function1 (p1,p2); /*注释*/实验一：线性表的基本操作一、线性表的顺序存储实验（一）实验目的1. 掌握线性表的基本运算。2. 掌握顺序存储的概念，学会对顺序存储数据结构进行操作。3. 加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力。4. 初步接触vc+6.0，练习在vc+6.0环境下编写c语言程序。（二）实验内容1. 基础题(1) 编写线性表基本操作函数。a 初始化线性表 sqlistinit ()b 创建一个线形表 sqlistcreat()c 向线性表指定位置插入元素 sqlistinsert(l, i, x)d 删除指定位置

5、的线性表记录 sqlistdelete(l, i) e 查找线性表中的元素位置 sqlistlocate(l, x)f 输出线性表 sqlistoutput(l)(2) 调用上述函数实现下列操作，操作步骤如下。a 调用创建函数建立一个线性表ab 调用插入函数建立一个线性表bc 在线性表中插入元素。d 在线性表中删除指定位置的元素。e 输出某元素在线形表中的位置。f 遍历并输出线性表。注意：每完成一个步骤，必须及时输出线性表元素，便于观察操作结果。2. 提高题(1) 编程实现删除线性表中元素值在x到y(x和y自定)之间的所有元素。思路1：在线性表中设置两个初值为0的下标变量i，i为比较元素的下标

6、。依次取线性表中下标为i的元素与x和y比较，假若是x到y之间的元素，则删除此元素。思路2：在线性表中设置两个初值为0的下标变量j和j，其中，i为比较元素的下标，j为赋值元素的下标。依次取线性表中下标为i的元素与x和y比较，假若是x到y之外的元素，则赋值给下标为j的元素。这种算法比删除一个元素后立即移动其后面的元素的效率高得多。(2) 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。解题思路：由于两个线性表中的元素呈有序排列，在进行合并的时候，依次比较，哪个线性表的元素值小，就先将这个元素复制到新的线性表中，若两个元素相等，则复制一个即可，这样一直到其中的一个线性表结束，然后将

7、剩余的线性表复制到新的线性表中即可。（三）程序实现#include #define maxsize 100#define flag 999/*-定义数据存储结构-*/typedef int elemtype; typedef struct elemtype datamaxsize; /顺序存放线形表元素，maxsize是最大存储个数 int length;sqlist;/*-*/*初始化线形表*/sqlist sqlistinit() sqlist l; l.length=0; return l;/*-*/函数名：sqlist sqlistcreat()/参数： /返回值：返回创建的线性表/功

8、能：创建一个线形表/*-*/sqlist sqlistcreat() sqlist l; l.length=0; elemtype x; int j=0; printf(请输入线形表的数据元素n); scanf(%d, &x); while(x!=flag) _ /循环多次输入线性表各元素 _ _ return l; /*-在顺序表l的第i个元素之前插入元素x-*/sqlist sqlistinsert(sqlist l, int i, elemtype x) int j; if (l.length = maxsize) printf(表满n); if (il.length+1) printf

9、(插入位置错n); for (j=l.length-1; j=i-1; j-) _ _ _ return l;/*-删除线形表中第i个元素-*/void sqlistdelete(sqlist *l, int i) int j; if (il-length) printf(删除位置错n); for (j=i; jlength-1; j+) _ _/*-用插入操作创建一个线形表-*/sqlist sqlistcreat2() sqlist l; l.length=0; elemtype x; int j=1; printf(请输入线形表的数据元素n); scanf(%d, &x); while(

10、x!=flag) l=sqlistinsert(l,j,x);/每输入一个新元素就将其插入到线性表的后面 j+; scanf(%d, &x); return l; /*找线形表中第一个与元素x相同的元素，若查找成功，返回其在顺序表中的位置*/int sqlistlocate(sqlist *l, elemtype x) int j=1; while(_) j+; if (j length) return j; else printf(无此元素n);/*-输出线形表中的各元素-*/void sqlistoutput(sqlist l) int j; printf(此线性表个元素为：n ); fo

11、r (j=1; j=l.length; j+) printf(%2dn , l.dataj-1);/ printf(n%2d %6d, j, l.dataj-1);/*-合并两个线性表-*/sqlist sqlistmerge(sqlist la,sqlist lb)sqlist lc; lc=sqlistinit();int m,n,t,i=0,j=0,k=0;m=la.length;n=lb.length;while(im&jn)if(la.datailb.dataj)lc.datak=lb.dataj;j+;k+;lc.length+;else if(la.datai=lb.dataj)

12、lc.datak=la.datai;i+;j+;k+;lc.length+;if (i=m)for (t=j; tn; t+)lc.datak=lb.datat;k+;lc.length+;elsefor (t=i; tm; t+)lc.datak=la.datat;k+;lc.length+;return lc;/*-删除线性表中元素值在x和y之间的数-*/sqlist sqlistdelbtw(sqlist l, elemtype x,elemtype y) sqlist c; c=sqlistinit(); int i,j=0; for(i=0; i=l.length-1; i+) if

13、(l.dataiy) _ _ _ return c;/*-主程序-*/void main() sqlist a; /创建表a a=sqlistcreat(); sqlistoutput(a); sqlist b; /创建表b b=sqlistcreat2(); sqlistoutput(b); a=sqlistinsert(a,3,10); /表中某位置插入一元素 sqlistoutput(a); sqlistdelete(&a,4); /删除表中指定位置的某元素 sqlistoutput(a); int m; /找到某元素在表中的位置 m=sqlistlocate(&a,10); a=sql

14、istdelbtw(a,4,7); /删除a中在4和7之间的元素 sqlistoutput(a); sqlist c; /合并线性表c=sqlistinit();c=sqlistmerge(a,b);sqlistoutput(c);（四）思考题1.在线性表中删除指定值的元素。2.用两个思路分别实现提高题（1）二、线性表的链式存储实验（一）实验目的1. 掌握链式存储的概念，学会对链式存储数据结构进行操作。2. 加深对指针类型数据的理解，能熟练运用指针。3. 加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。（二）实验内容1. 基础题(1) 编写单链表的基本操作函数。a 用尾插法创建一

15、个带头节点的单链表 linkedlistcreat() b 向单链表指定位置插入元素 listedlistinsert(l, i, x) c 删除指定位置的单链表元素 listedlistdelete( l, i)d 查找单链表中的某个元素 linkedlistlocate(l ,x)e 思考：查找单链表中的第i个元素 linkedlistlocate2(l ,i)f 输出单链表 linkenlistoutput( l)(2) 调用上述函数实现下列操作，操作步骤如下。a 用尾插法建立一个带头节点的单链表。b 在单链表中插入元素。c 在单链表中删除元素d 遍历并输出线性表。注意：每完成一个步骤，

16、必须及时输出线性表元素，便于观察操作结果。2. 提高题编程实现将两个单链表进行合并，要求同样的数据元素只出现一次。解题思路：由于两个单链表中的元素呈有序排列，在进行合并的时候，依次比较，哪个单链表的元素值小，就先将这个元素复制到新的单链表中，若两个元素相等，则复制一个即可，这样一直到其中的一个单链表结束，然后将剩余的单链表复制到新的单链表中即可。（三）程序实现 /*-头文件和宏定义-*/#include #include #define flag 999/*-数据存储结构定义-*/typedef int elemtype;typedef struct lnode/定义单链表结点类型 _ _ln

17、ode,* linkedlist;/*-函数定义和实现-*/*-用尾插法建立带头节点的单链表-*/linkedlist linkedlistcreat()参考课本p38页设计出算法程序/*-查找单链表中的某个元素-*/linkedlist linkedlistlocate(linkedlist l,elemtype x)linkedlist p=l-next;int n=1;while (p!=null & p-data!=x)p=p-next;n+;if (p=null)printf(无此元素n);elsereturn p; /返回p结点（地址）/*在单链表指定位置插入元素*/void li

18、stedlistinsert(linkedlist l,int i,elemtype x)int j=1;lnode *p,*s;p=l;while (jnext; if (p=null|jnext;printf(此单链表的各元素为：n);while(p!=null)printf(%dn,p-data);p=p-next;printf(n);/*-合并两个单链表-*/linkedlist linkedlistmerge(linkedlist la,linkedlist lb)linkedlist lc;lnode * pa, *pb, *pc; /pa,pb,pc分别为指向各链表的动态指针ln

19、ode *qa, *qb; /qa,qb分别为各链表结点的中转指针pa=la-next;pb=lb-next;lc=la;pc=lc;while(pa!=null&pb!=null) /la和lb都不为空if(pa-datadata) /la元素值小于lb元素值qa=pa-next; /将la的此结点链接到lc中pc-next=pa;pc=pc-next;pa=qa;else if(pa-datapb-data) /la元素值大于lb元素值_ /将lb的此结点链接到lc中 _ _ _else if(pa-data=pb-data) /la元素值等于lb元素值qa=pa-next; /将la或l

20、b的此结点链接到lc中 qb=pb-next;pc-next=pa;pc=pc-next;pa=qa;free(pb); /释放没有链接的结点pb=qb;if (pa!=null) /la没有结束，将剩余元素链接到lc中 pc-next=pa;if (pb!=null) /lb没有结束，将剩余元素链接到lc中 pc-next=pb;free(lb); return lc;/*-主函数-*/void main() linkedlist a; /创建单链表a a=linkedlistcreat(); linkenlistoutput(a); linkedlist b; /创建单链表b b=link

21、edlistcreat(); linkenlistoutput(b); lnode *p; p=linkedlistlocate(a,3); listedlistinsert(a, 3, 10); /插入某个元素 linkenlistoutput(a); listedlistdelete(a,4); /删除某位置元素 linkenlistoutput(a); linkedlist c; /链表合并 c=linkedlistmerge(a, b); linkenlistoutput(c);（四）思考题1.用头插法创建一个带头节点的单链表 linkedlistcreat2()。2.用单链表的存储方

22、式实现顺序表实验中的提高题（1）。实验二：栈的基本操作一、栈的顺序存储实验（一）实验目的1. 熟悉栈的定义和栈的基本操作。2. 掌握顺序存储栈的基本运算。3. 加深对栈结构的理解逐步培养解决实际问题的编程能力。4. 练习在vc+6.0环境下编写c语言程序。（二）实验内容(1) 编写顺序栈的基本操作函数：a 顺序栈的初始化操作 sqstack sqstackinit()b 判栈空操作 int sqstackempty(sqstack s)c 进栈操作 void sqstackpush(sqstack *s,elemtype x)d 出栈操作 elemtype sqstackpop(sqstack

23、 *s)e 取栈顶元素操作 elemtype sqstackgettop(sqstack s)f 输出整个栈的元素 void sqstackoutput(sqstack s)(2) 调用上述函数实现下列操作：a 初始化顺序栈ab 判栈a是否为空c 输入元素依次进栈d 输出此时栈的长度e 取出栈顶元素f 元素依次出栈g 判栈是否为空注意：每完成一个步骤，必须及时输出栈，便于观察操作结果。（三）程序实现/*-头文件和宏定义-*/#include #include #define maxsize 100 /栈的最大可能存储空间#define tuse 1#define flase 0#define

24、flag 0/*-数据存储结构定义-*/typedef char elemtype;typedef struct elemtype datamaxsize;int top; /栈指针 sqstack; /将顺序栈类型声明为sqstack类型/*-函数定义和实现-*/*-顺序栈的初始化操作-*/sqstack sqstackinit()sqstack s;s.top=-1; /空栈时栈顶指针为-1return s;/*-顺序栈的判空操作-*/int sqstackempty(sqstack s) if(s.top=-1)return tuse; else return flase;/*-顺序栈的

25、入栈操作-*/思考：能否将函数形参类型由sqstack *s改为sqstack s，为什么？/若将函数形参改为sqstack s，要如何改变程序指令才能完成函数功能void sqstackpush(sqstack *s,elemtype x)if (s-top=maxsize-1)printf(栈空间已满，不能入栈n);s-top+_ _s.datas-top=x_/*-顺序栈的出栈操作-*/若栈不空 删除栈顶元素，并返回其值elemtype sqstackpop(sqstack *s)elemtype x;if (s-top=-1)printf(栈已空，不能出栈n);x=s-datas-to

26、p;_/更简单指令return(s-datas-top),将3条指令变一条_s-top-_ /*-取栈顶元素操作-*/elemtype sqstackgettop(sqstack s)if (s.top=-1)printf(栈已空，无元素n);return(_);/*-输出整个栈元素的操作-*/void sqstackoutput(sqstack s)int i;printf(现此栈个元素为：);for (i=s.top;i=0;i-)printf(%c ,s.datai);printf(n);/*-主函数-*/void main() sqstack a;printf(初始化栈an); /初始

27、化顺序栈aa=sqstackinit(); printf(栈为%sn,(sqstackempty(a)?空:非空); /判栈是否为空printf(请将元素依次进栈n); /元素依次进栈 elemtype x;scanf(%c,&x); while(x!=flag)_ _sqstackoutput(a); printf(栈长度:%dn,_); /输出栈的长度printf(栈顶元素为：%cn,_); /取出栈顶元素 printf(元素出栈，出栈元素为%cn,_); /元素出栈 printf(元素出栈，出栈元素为%cn,_); sqstackoutput(a);printf(栈为%sn,(sqsta

28、ckempty(a)?空:非空); /判栈是否为空 （四）思考题1.结构体类型数据做函数参数的时候应该如何实现实参到形参的传递。2.如何用栈实现迷宫问题。二、栈的链式存储实验（一）实验目的：1. 熟悉栈的定义和栈的基本操作。2. 掌握链栈的基本运算。3. 加深对栈结构的理解逐步培养解决实际问题的编程能力。（二）实验内容：(1) 编写链栈的基本操作函数：a 链栈的初始化操作 linkedstack linkedstackinit()b 判栈空操作 int linkedstackempty(linkedstack top)c 求链栈栈长操作 int linkedstacklength(linked

29、stack top)d 入栈操作 linkedstack linkedstackpush(linkedstack top,elemtype x)e 出栈操作 elemtype linkedstackpop(linkedstack &top)f 取栈顶元素操作 elemtype linkedstackgettop(linkedstack top )g 输出整个栈的元素 void linkedstackoutput(linkedstack top)(2) 调用上述函数实现下列操作：a 初始化链栈ab 判栈是否为空c 输入元素依次进栈d 输出栈的长度e 取出栈顶元素f 元素依次出栈g 判栈是否为空

30、注意： 每完成一个步骤，必须及时输出栈，便于观察操作结果。（三）程序实现/*-头文件和宏定义-*/#include #include #include #define tuse 1#define flase 0#define flag 0/*-数据存储结构定义-*/typedef char elemtype;typedef struct stacknodeelemtype data;/数据域struct stacknode *next; /指针域 stacknode,*linkedstack;/*-函数定义和实现-*/*-链栈的初始化操作-*/linkedstack linkedstackin

31、it()linkedstack top; top=null; /构造一个不带头结点的空栈，栈顶指针为topreturn top;/*-链栈的判空操作-*/int linkedstackempty(linkedstack top)return(top=null); /思考：与顺序栈的判空算法比较/*-链栈的栈长操作-*/int linkedstacklength(linkedstack top)/自行设计此程序/*-链栈的入栈操作-*/linkedstack linkedstackpush(linkedstack top,elemtype x)/参考课本p51设计此程序/*-链栈的出栈操作-*/

32、elemtype linkedstackpop(linkedstack &top) /注意其参数形式linkedstack p;elemtype x;if (top=null) /栈空的情况printf(栈已空，不能出栈n);p=top; /p指向第一个数据结点x=top-data;top=top-next;free(p);return x;/*-链栈的取元素操作-*/elemtype linkedstackgettop(linkedstack top )if (top=null) /栈空的情况printf(栈已空，不能出栈n);return (top-data);/*-输出整个栈元素的操作-

33、*/void linkedstackoutput(linkedstack top)linkedstack p=top;while (p!=null)printf(%c ,p-data);p=p-next;printf(n);/*-主函数-*/void main()/初始化链栈a linkedstack a;printf(初始化栈an); a=linkedstackinit(); /判栈是否为空 _ /元素依次进栈 参考顺序栈完成 linkedstackoutput(a); printf(栈长度:%dn,_); /输出栈的长度printf(栈顶元素为：%cn,_); /取出栈顶元素 printf

34、(元素出栈，出栈元素为%cn,_); /元素出栈 printf(元素出栈，出栈元素为%cn,_); linkedstackoutput(a);printf(栈为%sn,(linkedstackempty(a)?空:非空); /判栈是否为空 （四）思考题：1. 链栈的入栈操作函数参数的传递2. 链栈出栈操作函数参数的传递实验三：数组的基本操作（一）实验目的1. 熟悉稀疏矩阵的基本操作。2. 掌握稀疏矩阵压缩存储的基本运算。3. 加深数组结构的理解逐步培养解决实际问题的编程能力。（二）实验内容(1) 编写顺序栈的基本操作函数：a 产生稀疏矩阵的三元组表示 tsmatrix tsmatrixcrea

35、t(elemtype amn)b 输出矩阵的三元组表示 void tsmatrixoutput(tsmatrix t)c 求三元组表矩阵的转置 tsmatrix tsmatrixtrans(tsmatrix t)d 查找三元组表中下标为i，j的元素值 elemtype value(tsmatrix c,int i,int j)e 求两个三元组表和的三元组表 tsmatrix tsmatrixadd(tsmatrix a,tsmatrix b)(2) 调用上述函数实现下列操作：a 产生两个稀疏矩阵的三元组表a，bb 输出他们的三元组表c 查找某下标的元素值d 求a的转置的三元组表e 求a，b这两

36、个矩阵和的三元组表c注意：每完成一个步骤，必须及时输出三元组表，便于观察操作结果。（三）程序实现/*-头文件和宏定义-*/#include #define m 4 /矩阵的行数和列数（根据自己的输入矩阵而定）#define n 4#define maxsize 30/矩阵中非零元素最多个数/*-数据存储结构定义-*/typedef int elemtype;typedef struct int row; /行号 int col; /列号 elemtype e; /元素值 triple; /三元组定义typedef struct int rows; /行数值 int cols; /列数值 int

37、 nums; /非零元素个数 triple datamaxsize; tsmatrix; /三元组顺序表定义/*-函数定义和实现-*/*-产生稀疏矩阵的三元组表示-*/tsmatrix tsmatrixcreat(elemtype amn)/自行设计此算法/*-输出矩阵的三元组表示-*/void tsmatrixoutput(tsmatrix t)int i;if (t.nums=0) return;printf(t%dt%dt%dn,t.rows,t.cols,t.nums);printf(t-n);for (i=0;it.nums;i+)printf(t%dt%dt%dn,t.datai.row,t.datai.col,t.datai.e);/*-求三元组表矩阵的转置-*/tsmatrix tsmatrixtrans(tsmatrix t)/ 参考课本p92设计此程序/*-求两个三元组表矩阵的和矩阵-*/tsmatrix tsmatrixadd(tsmatrix a,tsmatrix b) tsmatrix c;int i=0,j=0,k=0;elemtype v;if (a.rows!=