2022年《数据结构》实验指导书 .pdf

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

1、数据结构实验指导书软件学院2013 年 9 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 19 页 - - - - - - - - - 1 概述实习目的和要求数据结构在计算机科学中是一门实践性较强的专业基础课，上机实习是对学生的一种全面综合训练，是与课堂听讲、自习和练习相辅相成的必不可少的一个教学环节。实习着眼于原理与应用的结合，使学生学会把学到的知识用于解决实际问题，起到深化理解和灵活掌握教学内容的目的。同时，通过本课程的上机实习，使学生在程序设计方法及上机操作等基

2、本技能和科学作风方面受到比较系统和严格的训练。实习包括的步骤1简要描述题目要求，对问题的描述应避开算法及所涉及的数据类型，只是对所需完成的任务做出明确的陈述，例如输入数据的类型、值的范围以及输入的形式，输出数据的类型、值的范围以及输出的形式。2选定数据结构，写出算法，根据自顶向下发展算法的方法，首先描述算法的基本思想，然后进行算法细化，再对所设计的算法的时间复杂性和空间复杂性进行简单分析。3 准备好上机所需的程序，选定一种程序设计语言 （如 C 语言） ，手工编好上机程序，并进行反复检查，使程序中的逻辑错误和语法错误减少到最低程度。对程序中有疑问的地方，应做出标记，以便在上机时给予注意。4上机

3、输入和调试程序，在调试程序过程中除了系统的问题以外，一般应自己独立解决。在程序调试通过后，打印输出程序清单和运行结果。5上机结束后，总结和整理实习报告。实习报告的内容1简述题目要解决的问题是什么，并说明输入和输出数据的形式。2简述存储结构和算法的基本思想。3列出调试通过的源程序。4列出上面程序对应的运行结果。5分析程序的优缺点、时空性能以及改进思想，写出心得体会。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 19 页 - - - - - - - - - 2 实验一线性表

4、一目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二例题 问题描述 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。输入 初始字符串，插入位置，插入字符，删除字符。输出 已建立链表（字符串） ，插入字符后链表，删除字符后链表，逆转后链表。存储结构 采用链式存储结构算法的基本思想 建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将

5、新结点插入到该位置之前；删除字符： 根据读入的删除字符在链表中找到被删结点后，将其从链表中删除； 链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。参考源程序 #define NULL 0 typedef struct node char a; struct node *link; node,*nodelink; void readlink(nodelink head) nodelink p,q; char c; p=head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

6、- - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 19 页 - - - - - - - - - 3 printf(Input a linktable(a string):); scanf(%c,&c); if (c=n) printf(This string is empty。); while(c!=n) q=(nodelink)malloc(sizeof(node); q-a=c; p-link=q; p=q; scanf(%c,&c); p-link=NULL; void writelink(nodelink head) nodelink q;

7、if (head-link=NULL) printf( This link is empty。n); for(q=head-link;q;q=q-link) printf(%c,q-a); printf(n); int insert(nodelink head,char k1,char k2) nodelink p,q; p=head-link; while(p-a!=k1&p) p=p-link; if(p) q=(nodelink)malloc(sizeof(node); q-a=k2; q-link=p-link; p-link=q; return 1; else printf(Ther

8、e is no %cn,k1); return 0; int delete(nodelink head,char k) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - 4 nodelink p,q; q=head; p=head-link; while(p-a)!=k)&p) q=q-link; p=p-link; if(p) q-link=p-link; return 1; else printf(There is no %

9、cn,k); return 0; void opside(nodelink head) nodelink p,q; p=head-link; while(p-link) q=p-link; p-link=q-link; q-link=head-link; head-link=q; main() char k1,k2,k3; nodelink head; head=(nodelink)malloc(sizeof(node); head-link=NULL; readlink(head); if (head-link!=NULL) printf(Build link is :); writelin

10、k(head); if (head-link!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 19 页 - - - - - - - - - 5 printf(Please input a char you want to insert after:); k1=getch(); printf(%cn,k1); printf(Please input a char you want to insert:); k2=getch(); printf(%cn,k2);

11、 if (insert(head,k1,k2) printf(After %c insert %c,link is:,k1,k2); writelink(head); printf(Please input a char you want to delete:); k3=getch(); printf(%cn,k3); if (delete(head,k3) printf(after delete %c,link is:,k3); writelink(head); if (head-link!=NULL) printf(Opsite result is :); opside(head); wr

12、itelink(head); free(head); 三实习题1设顺序表 A 中的数据元素递增有序，试写一程序，将x 插入到顺序表的适当位置上，使该表仍然有序。2用单链表 ha 存储多项式 A（x ）=a0+a1x1+a2x2+, +anxn(其中 aI为非零系数 )，用单链表hb 存储多项式 B（x ）=b0+b1x1+b2x2+, +bmxm(其中 bj为非零系数 )，要求计算 C（x ）= A（x ）+B（x ） ，结果存到单链表hc 中。试写出程序。3设有 n 个人围坐在一个圆桌周围，现从第s 个人开始报数，数到第m 的人出列，然后从出列的下一个人重新开始报数，数到m 的人又出列，如此

13、重复，直到所有的人全部出列为止。 Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n 个人员的顺序表。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19 页 - - - - - - - - - 6 实验二树一目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二例题问题描述 任意给定一棵二叉树。 试设计一个程序， 在计算机中构造该二叉树，并对它进行遍历。输入 一棵二叉树的结点若无子树，则可将其

14、子树看作“. ” ，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD . EH.CF. I. G. 。A B C D E F G H I 输出 若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA 。存储结构 采用二叉链表存储。算法的基本思想 采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。参考源程序 #include #include struct node char inf

15、o; struct node *llink,*rlink; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - 7 ; typedef struct node NODE; NODE *creat() char x; NODE *p; scanf(%c,&x); printf(%c,x); if(x!=.) p=(NODE *)malloc(sizeof(NODE); p-info=x; p-llink=creat(); p-rli

16、nk=creat(); else p=NULL; return p; void run(NODE *t) if(t) run(t-llink); run(t-rlink); printf(%c,t-info); main() NODE *T; printf(PLease input a tree:n); T=creat(); printf(n); if(!T) printf(This is a empty binary tree.); else printf(The result of post travese is:n ); run(T); printf(n); 名师资料总结 - - -精品

17、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 19 页 - - - - - - - - - 8 三实习题1 编写递归算法，计算二叉树中叶子结点的数目。2 编写递归算法，在二叉树中求位于先序序列中第K 个位置的结点。3 将上述例题用非递归程序实现。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 19 页 - - - - - - - - - 9 实验三图一目的与要求熟悉图的存储结

18、构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二例题问题描述 给定一个图，设计一个程序，找出一条从某一顶点A 到另一顶点 B 边数最少的一条路径。输入 图的顶点个数N，图中顶点之间的关系及要找的路径的起点A 和终点 B。输出 若 A 到 B 无路径，则输出“ There is no path” ，否则输出 A 到 B 路径上各顶点。存储结构 图采用邻接矩阵的方式存储。算法的基本思想 采用广度优先搜索的方法，从顶点 A 开始，依次访问与 A 邻接的顶点 VA1, VA2,.,VAK,访问遍之后 ,若没有访问 B，则继续访问与VA1邻接的顶点VA11, VA12,.,VA1M，

19、再访问与VA2邻接顶点 . ，如此下去，直至找到B，最先到达 B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。参考源程序 #include int number; typedef struct int q20; int f,r; queue; int nodelist2020; queue Q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

20、- - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - 10 int z20; int a,b,n,i,j,x,y; int finished; void enq(queue *Q,int x) Q-qQ-r=x; if(Q-r=19) Q-r=0; else Q-r+; if(Q-r=Q-f) printf(Overflow!n); front(queue *Q) if(Q-r=Q-f) printf(Underflow!n); else return(Q-qQ-f); void deq(queue *Q) if(Q-r=

21、Q-f) printf(Underflow!n); else if(Q-f=19) Q-f=0; else Q-f+; int qempty(queue Q) if(Q.f=Q.r) return 1; else return 0; void readgraph() printf(nPlease input n:); scanf(%d,&n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - 11 printf(Please

22、 input nodelistij:n); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&nodelistij); printf(n); printf(List-link is bulitn); for(i=1;i=n;i+) for(j=1;j=n;j+) printf(%3d,nodelistij); printf(n); void shortest(int a,int b) if(a=b) nodelistaa=2; else enq(&Q,a); nodelistaa=2; finished=0; while(!qempty(Q)&!finishe

23、d) a=front(&Q); deq(&Q); j=1; while(j=n)&!finished) if(nodelistaj=1)&(nodelistjj!=2) enq(&Q,j); nodelistjj=2; zj=a; if(j=b)/*&(nodelistaj=1)*/ finished=1; if(!finished) j+; if (!finished) printf(There is no path.); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，

24、共 19 页 - - - - - - - - - 12 void writepath(int a,int b) i=b; while(i!=a) printf(%d - ,i); i=zi; printf(%d,a); main() readgraph(); printf(Please input a:); scanf(%d,&a); printf(Please input b:); scanf(%d,&b); Q.f=0; Q.r=0; shortest(a,b); if (finished) writepath(a,b); 三实习题1.采用邻接表存储结构，编写一个求无向图的连通分量个数的算

25、法。2.试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点 Vi到 Vj顶点的路径 (ij)。3.在上述例题中，如改用邻接表的方式存储图，试编一程序实现上述算法。顶点表 nodelist的每个元素包含四个字段：info mark pre out 其中 mark 为布尔类型，用来标记顶点是否被访问过。开始时，所有元素的mark 字段为 false，每访问过一个顶点，则mark 字段置为 true。info 为顶点值， pre 为访问路径上该顶点的前驱顶点的序号，out 指向该顶点的出边表。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

26、 - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 19 页 - - - - - - - - - 13 实验四查找一目的与要求通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。二例题问题描述 将折半查找算法写成完整的程序，并上机通过。输入 有序表（ 12,23,28,35,37,39,50,60,78,90 ）及待查找记录23,58。输出 输入 23，表中存在待查找记录， 则显示该记录在表中位置2，输入 58 显示该记录不存在。存储结构 有序表采用顺序方式存储。算法的基本思想 首先用待查找记录与查找区间中间位置记录比较，若相等则查找成功，

27、返回该记录在表中的位置数，若小于中间位置记录，则修改区间上界为中间位置减1，若大于中间位置记录，则修改区间下界为中间位置加1，在新的区间内继续查找。当查找区间下界大于上界，则该记录不存在。参考源程序 #includestdio.h typedef struct int a30; int length; sqtable; sqtable st; int b=0; void createst(int k) int i; printf(Please input data:); st.a0=-100; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

28、 - - - 名师精心整理 - - - - - - - 第 14 页，共 19 页 - - - - - - - - - 14 for (i=1;(!b&(i=k);i+) scanf(%d,&(st.ai); if (st.aist.ai-1) printf(Input data error.n); b=1; if (!b) st.length=k; printf(The table is builted.n); void stfind(sqtable st,int y) int f,l,h,m; l=1;h=st.length; f=1; while (l=h)&f) m=(l+h)/2;

29、if (y=st.am) f=0; else if (yst.am) h=m-1; else l=m+1; if (!f) printf(Find %d in position %d.n,y,m); else printf(Not find %d.n,y); main() int n,x; printf(nPlease input n:); scanf(%d,&n); createst(n); if (b=0) printf(Please input you want find value:); scanf(%d,&x); stfind(st,x); 名师资料总结 - - -精品资料欢迎下载

30、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 19 页 - - - - - - - - - 15 三实习题1 编写程序实现下面运算：在二叉排序树中查找关键字为key 的记录。2 试将折半查找的算法改写成递归算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 19 页 - - - - - - - - - 16 实验五内排序一目的与要求通过本次实验，掌握线性表的排序方法，并分析时间复杂度

31、。二例题问题描述 将快速排序算法写成完整的程序上机通过，并统计递归深度。输入 待排序记录个数n，各待排序记录值。输出 n 个记录由小到大排列的结果。存储结构 待排序记录顺序存储。算法的基本思想 快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组，将所有关键字小于或等于标准的记录都放在它的位置之前，将所有关键字大于标准的记录都放在它的位置之后。对这两组再进行快速排序，直到完全有序。每递归1 次，递归深度加1。参考源程序 #include typedef int node; node afile20; node x; int d,dl,n; int l,r,i,j; void q(in

32、t l,int r) int p; d+; if(dld) dl=d; printf(dl=%d ,dl); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 19 页 - - - - - - - - - 17 printf(d=%dn,d); if(lx)&(ji) j-; if(ij) afilei+=afilej; while(afileii) i+; if(ij) afilej-=afilei; afilei=x; for(p=1;p=n;p+) printf(%

33、d,afilep); printf(n); q(l,i-1); q(i+1,r); d-; printf( * *%d* *n,d); main() int p; printf(nPlease input n:n); scanf(%d,&n); printf(Please input a string:); for(p=1;p=n;p+) scanf(%d,&(afilep); d=0; dl=0; l=1; r=n; q(l,r); for(p=1;p=n;p+) printf(%d,afilep); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

34、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 19 页 - - - - - - - - - 18 printf(dl=%dn,dl); 三实习题1设计一个用链表表示的直接选择排序算法，并用程序实现。算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用 r 来指示。 r 以前为已排序序列，r 以后为未排序序列。 再从未排序序列中找出最小结点插入r 的后面， 让 r 指向这个结点。 反复执行这个过程，直到排好序。2 对 N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O(N)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 19 页 - - - - - - - - -