数据结构实验指导书

1、1.2实验报告(文档)书写规范实验报告（文档）应包括以下7个方面的内容： 1、问题分析根据对实验任务的理解，以无歧义的陈述说明程序设计的任务，强调的是程序要做什么。指出解决问题的关键步骤，如果问题复杂，应将问题分解成若干个子问题。明确规定：（1）本实验的任务以及程序所能达到的功能；（2）完成该任务需要解决的关键问题；（3）程序设计中输入数据的类型、形式及输入值的范围；（4）设置测试数据：包括正确的输入及预计的输出结果和含有错误的输入及预计输出结果。2概要设计针对问题分析中提出的关键问题进行分析（可以列举实例进行分析），从而总结出关键问题的解决思路，给出解决关键问题的算法思想。说明本程序中用到的

2、所有程序模块、各程序模块之间的层次(调用)关系以及主程序的流程，各程序模块使用中文名称即可。3详细设计根据概要设计中提出的关键问题的解决思路，设计本程序中用到的所有数据结构，要求做到：（1）在所设计的数据结构下分析关键问题的具体解决方案和步骤，给出相应的用类C语言描述的算法；（2）分析设计程序中需要用到的变量、全局变量及其数据类型定义；（3）设计程序中的所有模块（自定义函数和主函数），通过分析定义函数的类型、描述函数参数、说明函数名称，并给出相应类C语言描述的算法(类C语言算法达到的详细程度建议为：按照该算法可以直接写出高级程序设计语言程序)；（4）画出函数和过程的调用关系图。4调试分析程序调

3、试主要实现程序的语法错误检查和功能性错误检查。调试最好分模块进行，自底向上，即先调试低层过程或函数。在实验报告中应有如下内容：（1）记录调试过程中遇到的问题及其解决方案，如果由此反映出程序设计的不足，应对设计与实现进行回顾讨论和分析，并修正；（2）算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；（3）经验和体会等。5测试结果将程序的测试结果截图，展示出你的测试过程和结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于问题分析中所列。6附录带注释的源程序。如果提交源程序电子档，可以只列出程序文件名的清单。值得注意的是，实验报告文档的前三部分要在程序开发的

4、过程中逐渐充实形成，而不是最后补写。实验一算法设计：（1）用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个函数，n和各整数在主函数中输入，最后在主函数中输出。（2）编程求出10000以内的所有符合如下条件的数：其高位数字小于低位数字。如25，349，2468等，但32，845不符合条件。（3）编程求出数列的所有升或降的最大子序列。如数列（1，20，30，12，3，5，7，4，6，100，11，8）的所有升或降的最大子序列如下： （1，20，30），（30，12，3），（3，5，7），（7，4），（4，6，100），（100，11，8）实验二 顺序表实验【实验任务】1、程序验证

5、（1）建立含有若干个元素的顺序表，并实现顺序表的插入、删除、查找等操作。（2）阅读下列程序，指出算法的功能，写出其运行结果，并通过运行来验证。include “malloc.h” define maxlen 50typedef structint datamaxlen； int last；3我Sequenlist；Sequenlist *ABC(Sequenlist *A , Sequenlist *B) int i, j; Sequenlist *C; C = malloc(sizeof(Sequenlist); C-last = -1; for(i=0; ilast; i+) for(j=

6、0; jlast; j+) if(A-datai= = B-dataj) C-last+; C-dataC-last = A-datai; break; return C;Sequenlist *SqLset( )Sequenlist *L；int i;L=malloc( sizeof(Sequenlist)；L-last = -1；scanf(“%d”, &i); /输入表长if( i0) for(L-last=0; L-last last +) scanf(“%d”, & L-dataL-last);L-last-； return ( L)；main( ) Sequenlist *A ,

7、*B, *C; int i; A = SqLset( ); B = SqLset( ); C = ABC(A, B); for(i=0; ilast; i+) printf(“%4d”, C-datai ); （3）下面算法的预定功能是实现顺序表的倒置，试检查其中是否有错；若有错，指出错误所在，并修改之，然后通过运行来验证。include “malloc.h” define maxlen 50typedef structint datamaxlen； int last；Sequenlist；Sequenlist *SqLset( )Sequenlist *L；int i;L=malloc( s

8、izeof(Sequenlist)；L-last = -1；scanf(“%d”, &i); /输入表长if( i0) for(L-last=0; L-last last +) scanf(“%d”, & L-dataL-last); return ( L)； Sequenlist *reverse(Sequenlist *L) int i, j, x; for(i=0, j=L-last-i+1; idatai; L-datai= L-dataj; L-dataj=x; return ( L)；main( ) Sequenlist *A; int i; A = SqLset( ); for(

9、i=0; ilast; i+) printf(“%4d”, A-datai ); printf(“n”);A = Sequenlist ( );for(i=0; ilast; i+) printf(“%4d”, A-datai ); printf(“n”);2、算法填空请在下面算法的空格处填入适当内容，以使算法能求出顺序表中的最大和最小值，并通过运行来验证。include “malloc.h” define maxlen 50typedef structint datamaxlen； int last；Sequenlist；Sequenlist *SqLset( )Sequenlist *L；

10、int i;L=malloc( sizeof(Sequenlist)；L-last = -1；scanf(“%d”, &i); /输入表长if( i0) for(L-last=0; L-last last +) scanf(“%d”, & L-dataL-last); return ( L)； void maxmin(Sequenlist *L) int min, max, i;if( ) max = min = L-data0;for(i =1; i = ; i +) if( max datai) max = L-datai;if( min L-datai) min = L-datai; p

11、rintf(“max=%d, min= %dn”, max, min );main( ) Sequenlist *A; A = SqLset( ); maxmin(A); 3、算法设计（1）设计算法实现删除顺序表中多余重复元素。如：对于顺序表（1，2，3，1，3，4，3，5），删除第四个元素1及第五、第七个元素3。（2）设计算法，实现在一个递增有序的顺序表的适当位置插入元素x，使得该顺序表仍然递增有序。分析算法的时间复杂度。实验三 链表实验【实验任务】1、程序验证 建立含有若干个元素的链表，并实现链表的插入、删除、查找等操作2、算法填空（1）下面建立以head为头指针的单链表，完善该算法，并输

12、出表中元素。已知单链表节点类型为：typedef struct nodeint data；struct node *next；LinkList；LinkList *create ( )LinkList *p，*q；int k；q=head；scanf (“%d”，&k)；while( k0) ； ； ； ； scanf (“%d”，&k)； q-next = NULL；（2）已给如下关于单链表的类型说明： typedef struct nodeint data； struct node *next；LinkList；以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性

13、(升序)，这里两链表的头指针分别为p和q。完善该算法，输出合并后表中的元素。LinkList *mergelink(LinkList *p，LinkList *q)LinkList *h，LinkList *r； ； h-next= NULL；r=h； while( p!=NULL&q!=NULL) if (p-datadata) ；r=p；p=p-next； else ；r=q；q=q-next； if (p= =NULL) r-next=q； else ；return h； （3）la为指向带头节点的单链表的头指针，本算法在表中第i个元素之前插入元素b。完善该算法，并通过运行来验证。Lin

14、kList *insert (LinkList *la，int i，datatype b)LinkList *p，*s；int j；p= ；j= ；while ( p!=NULL & ) p = ；j=j+1； if (p= =NULL | ) error (No this position) else s = malloc ( sizeof (LinkList) )； s-data=b；s-next=p-next；p-next=s；return la；（4）已知双链表中节点的类型定义为：typedef struct Dnode int data； struct Dnode *prior，*n

15、ext； DLinkList ；如下过程将在双链表第i个节点(i=0)之后插入一个元素为x的节点。请完善该算法，并通过运行来验证。DLinkList *insert(DLinkList *head，int i，int x)DLinkList *s，*p；int j；s = malloc ( sizeof (LinkList) )； s-data=x；if (i= = 0) /如果i=0，则将s节点插入到表头后返回s-next = head； ；head=s else p = head； ；/在双链表中查找第i个节点，由p所指向 while ( p!= NULL & jnext= =NULL)

16、p-next=s；s-next =NULL； else s-next=p-next； ；p-next = s； ； else printf (“can not find node!”)； 3、算法设计：（1）在一个非递减有序链表中，插入一个值为x的元素，使插入后的链表仍为非递减有序。（2）设计算法将一个线性链表逆置，即将表(a1，a2，an)逆置为(an，an-1，a1)，要求逆置后的链表仍占用原来的存储空间。（3）假设有一个循环链表的长度大于1，且表中既无头节点也无头指针。已知s为指向链表某个节点的指针，试编写算法在链表中删除指针s所指节点的前驱节点。试写一算法，在无表头节点的单链表中值为a

17、的节点前插入一个值为b的节点，如果a 不存在，则把b插在表尾。（4）假设有一个单向循环链表，其节点包含三个域：data、pre和next，其中data为数据域，next为指针域，其值为后继节点的地址，pre也为指针域，其初值为空(NULL)，试设计算法将此单向循环链表改为双向循环链表。（5）假设字符串str存储在带表头节点的单链表中，编写删除串str从位置i开始长度为k的子串的算法。实验四 堆栈实验【实验任务】1、程序验证 分别建立含有若干个元素的顺序栈和链栈，并分别实现顺序栈和链栈的入栈和出栈操作。2、算法填空 将十进制正整数转换成十六进制数的算法如下。完善该算法，并通过运行来验证。void

18、 dectohex(long num) SeqStack s; InitStack(&s); while(num) int k=num%16; Push(&s,k); ; while(!StackEmpty(&s) int x=GetTop(&s); if(x10) printf(%d ,x); else switch( ) case 10: printf(A );break; case 11: printf(B );break; case 12: printf(C );break; case 13: printf(D );break; case 14: printf(E );break; c

19、ase 15: printf(F );break; Pop(&s); printf(n);3、算法设计（1）编写算法，利用栈判断所给字符串是否具有中心对称关系。要求用尽可能少的时间完成判断。提示：字符串的中心对称是如 xyzyx 和abcddcba的形式；字符串可以考虑顺序存储或链接存储；判断该字符串是否中心对称，可以将一半字符先入栈。（2）设计算法判断一个算术表达式的圆括号是否正确配对。提示：对表达式进行扫描，凡遇（就入栈，遇）就将栈顶元素（出栈；表达式被扫描完毕，栈应为空。（3）设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。实验五 队列实验【实验任务】1、程序验证（1）分别

20、建立含有若干个元素的循环队列和链队列，并分别实现循环队列和链队列的入队和出队操作。（2）写出下列程序段的输出结果，并通过运行来验证。void print( ) SeqQueue *q; char x, y; x=e; y=c; InitQueue(q); Add(q, h); Add(q, r); Add(q, y); x=GetHead(q); Delete(q); Add(q, x); x=GetHead(q); Delete(q); Add(&q,a); while(QueueEmpty(q)= =0) y=GetHead(q); Delete(q); printf(%c,y); pri

21、ntf(%c,x);2、算法设计（1）假设以数组sem存放循环队列的元素，同时设变量rear和num分别作为队尾指针和队中元素个数记录。试讨论判别此循环队列的队满条件，写出相应入队和出队算法，并通过运行验证之。（2）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点。试编写相应的置空队、判队空、入队和出队等算法，并通过运行验证之。（3）设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n,a2n-1,a1,要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n,a2n-2,a4,a2, a2n-1, a2n-3, ,a3,a1,请设计算法实现该操作，要求空间复

22、杂度和时间复杂度均为O(n)。实验六 矩阵实验【实验任务】1、程序验证 （1）建立一个nn的对称矩阵，并将该对称矩阵用一维数组存储。（2）采用三元组表存储稀疏矩阵，并实现其转置。2、算法填空 （1）完善该算法，并通过运行来验证：设有一对角矩阵A，用一维数组B存放A中的对角线上的元素aij（按行优先存放）。试设计由A确定B中元素的算法。算法描述如下： void exstorge(int ann,int n) int b3*n; int p,j,k; for(p=0;pn;p+)for(j=0; ; j+)if(apj!=0) k = ; bk=apj;（2）完善该算法，并通过运行来验证：对于二维

23、数组Amn，其中m=80，n=80，先读入m、n，然后读该数组的全部元素，对如下3种情况分别编写相应算法： 求数组A靠边元素之和。 求从A00开始的互不相邻的各元素之和。 当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息。 main ( ) int A8080, m, nint s1, s2, s3;scanf(“%d%d”, &m, &n);for( i=1; im; i+) for( j=1; jn; j+)scanf(“%d”, &m, & Aij); s1= fun1(A, m, n); s2= fun2(A, m, n); if( m= =n) s3= fun3(A,

24、m); else printf(“%d ! =%dn”, m, n); int fun1(int A8080, int m, int n) int i, s=0;for( i=0; in; i+) s+= ;for( i=1; im-1; i+) s+= ;return (s); int fun2(int A8080, int m, int n) int i, j, s=0;for( i=0; im; i+) for( j= ; jn; ) s+= Aij;return (s); int fun3(int A8080, int m) int i, s=0;for( i=0; ilchild)；

25、 Preorder(T-rchild)； （2）中序遍历递归算法：void Inorder(Bitree *T)if(T) Inorder( T-lchild)； visite( T)； Inorder( T-rchild)； （3）后序遍历递归算法：void Postorder(Bitree *T) if( T) Postorder(T-lchild)； Postorder(T-rchild)； visite(T)；二叉树的遍历也可以采用非递归的算法来实现。在二叉树的非递归遍历算法中，我们可以定义一个栈，利用栈存储已访问（或经过）过的节点。二叉树的递归遍历思想将二叉树的遍历简化为对根节点的访

26、问。利用这一特点，适当修改访问操作的内容，就可以得到许多实际问题的求解算法。【实验任务】1、程序验证 （1）建立一棵含有n个结点的二叉树，采用二叉链表存储。（2）前序（或中序、后序）遍历该二叉树。（3）采用孩子兄弟表示法建立一棵树。（4）基于孩子兄弟表示法存储的树实现前序遍历操作。（5）阅读程序，写出程序的功能，并通过运行验证之。 typedef struct nodeint data； struct node *lchild，*rchild；Bitree； p = NULL; void delete(Bitree *root, int x) if( root ) if( root-data

27、= = x) if( !p ) root = NULL; else if( p-lchild = = root) p-lchild = NULL; else p-rchild = NULL; else p = root; delete( root-lchild, x); delete( root-rchild, x); （6）阅读程序，写出程序功能，并通过运行验证之。 typedef struct char data； CSTreeNode *firstChild；CSTreeNode *nextSibling； CSTreeNode；int dep(CSTreeNode *root ) if

28、( !root ) return 0; else n1 = dep( root- firstChild); n2 = dep( root- nextSibling); return max( n1+1, n2); （7）对给定的一组无序序列，建立一棵二叉排序树。（8）对建立的二叉排序树实现查找操作。2、算法填空 （1）完善下述算法，并通过运行来验证：设二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树中双孩子结点的数目。算法描述如下： struct bitreeelemtype data;bitree *lchild,*rchild;int twochild(bitree *t)int

29、num1,num2;if(t=NULL)return 0;elseif(t-lchild!=NULL)&(t-rchild!=NULL) num1 = ;num2 = ;return num1+num2+1;elsenum1 = ;num2 = ;return num1+num2;（2）完善下述算法，并通过运行来验证：求给定结点在二叉排序树中所在的层数。 int level(Bstnode *root, Bstnode *p) if( !p) return 0; if( p = = root ) return 1; else if ( p-key key ) return ; else ret

30、urn ; 3、算法设计（1）设二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树中叶子结点的数目。（2）在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先结点的算法。提示：对二叉树进行先序遍历，查找值为x的结点；找到值为x的结点时，栈中存放的是x的所有祖先结点。（3）编写算法交换二叉树中所有结点的左右子树。（4）试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不相同。（5）编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。（6）以孩子兄弟链表作为存储结构，求树中结点x的第i个孩子。实验八 图实验【实验任务】1、程序验证 （1

31、）阅读下列程序，指出程序的功能，并通过运行验证之。typedef struct nodeint adjvex; struct node *next; edgnode; typedef struct vextype vertex; edgnode *link; vexnode; vexnode gan;void creatdjlist(vexnode ga)int i, j, k; edgnode *s; for(i=0; in; i+) gai.vertex=getchar(); gai.link=NULL; for(k=0; kadjvex=j;s-next=gai.link; gai.link=s; s=malloc(sizeof(edgnode); s-adjvex=i; s-next=gaj.link; gaj.link=s; （2）在第（1）题的基础上编写广度优先遍历程序，输出遍历序列。（3）建立无向图的邻接矩阵存储，并分别对建立的无向图进行深度优先遍历和广度优先遍历。（4）建立有向图的邻接表存储，并分别对建立的有向图进行深度优先遍历和广度优先遍历。2、算法填空 （1）下列函数MDFSFor