《《数据结构》实验指导书new》由会员分享，可在线阅读，更多相关《《数据结构》实验指导书new（17页珍藏版）》请在金锄头文库上搜索。
1、1计算机科学与技术专业数据结构实验指导书关于实习步骤的要求和建议从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规 范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的 程序编制风格，培养严谨、科学、高效的工作方式。在以往的教学实践中，经常发现很多学生抱怨说，化了两个小时才找出一 个错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自 己。有的学生不屑于按实习步骤规范去做，甚至对于实习步骤的要求和建 议看都不看一遍，认为那是浪费时间，这是及其害的。实习步骤规范不但 可以培养科学化的工作作风，而且还能有效地避免错误。具体的步骤机规范如下：1问题分析与系统的结构设计充
2、分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照 以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操 作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要综合考 虑系统功能。要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个 子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示则更加清晰，这样便完成了系统结构设计。2详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、 WHILE 和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的 是避免陷入细节。在编码是，可以对详细设计的结果进一步求
3、精，用高级语言 表示出来。程序的每一行最好不超过 60 个字符。每个子程序（或过程、函数）通 常不要太长，以 40 行为宜。子程序（或过程、函数）包含的程序行数太多， 易于造成理解的困难。控制 IF 、WHILE 等语句的连续嵌套的深度。程序的目 的性必须明确。对每一段程序完成的作用，除非常明显的除外（如：x = x + 1; 注释为 x 加 1，没有什么意义），都应加以注释。这会对程序的调试提供很多 方便。另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你 的设想是否一致。另外，对于输入输出语句，必须对它们的作用加以说明。否 则，在调试程序时，无法了解系统需要输入说明，系统输出的
4、又是什么。程序 的书写，必须按照一定的规范，如保留字小写时涂黑，或者大写等等。具体的 要求可参看软件工程中的有关规定。 3上机准备和静态检查1 高级语言文本2 熟悉机器的用户手册，熟悉常用的命令。3 准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具可供利用，可以自己先设计一些以供使用。4 静态检查自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了解该程序的逻辑。4 上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联 调。调试正确后将源程序和运行结果加以列印输出。25 实习报告的整理1 需求及规格说明问题描述，求解的问题是什么。2 设计：设计思想
5、：存储结构、主要的算法思想。设计表示：子程序（过程或函数）的规格说明，通过调用关系图表 示它们之间的调用关系。实现注释：详细设计表示：主要算法的框架。3 用户手册：使用说明。4 调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体会、时空复杂度等。5 附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据。提倡用英文描述。6 实验报告要求：在程序开发过程中，逐步形成各种必要的文档及资料。可以写在实 验报告纸上，或以电子文档的形式进行书写。上机实习以下的实习题目配合课程的进度，请同学们自己务必完成。为了锻炼自 己的应用各种不同的数据结构的能力，尽可能的多作一些题目是非常必
6、 要的。在完成各种不同题目的过程中，对各种算法的时、空复杂性的分 析，将帮助您在更高的角度解决各种应用问题。实验一 线性表的插入和删除一、 实验目的1、 掌握用 Turbo C 上机调试线性表的基本方法；2、 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、 实验内容线性表基本操作的实现当我们要在线性表的顺序存储结构上的第 i 个位置上插入一个元素时，必须先将线性表的第 i 个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第 i 个元素时，也必须把第 i 个元素之后的所有元素前移一个位置。程序实现：t
7、ypedef Null 0;typedef int datatype;#define maxsize 1024;3typedef struct datatype datamaxsize;int last;sequenlist;int insert(L, x, i)sequenlist *L;int i; int j;if (*L).last= =maxsize-1) printf(“overflow”);return Null;elseif (i(*L).last+1) printf(“error”);return Null;else for(j=(*L).last; j=i-1; j-)(*
8、L).dataj+1=(*L).dataj;(*L).datai-1=x;(*L).last=(*L).last+1;return(1);int delete(L,i)sequenlist *L;int i; int j;4if (i(*L).last+1)printf (“error”);return Null;else for(j=i, ji) AND (ga.arcsi,j.adj0) AND (visitedjtrue)THEN dfsmatrix(ga,visited,j,n);END;END;初始化邻接表PROCEDURE initgadjoin(VAR ga:adjlist;n:
9、integer);VAR j:integer;BEGINFOR j:=1 TO n DOBEGINgaj.link:=NIL;write(input value:);read(gaj.data);END;FOR j:=1 TO n DOBEGINwriteln(gaj.data);END;END;PROCEDURE createadjoin(VAR ga:adjlist;n:integer); 用邻接矩阵建立无向无权图VAR e:integer;i,j,k:integer;p,q:edgeptr;BEGINwrite(Please input the num of edges:);read(e
10、);13FOR k:=1 TO e DOBEGINwriteln(input two vertexs:);read(i,j); 输入一条无向无权的边的两个顶点的序号向序号为 i 的单链表的表头插入一个边结点new(p);p.adjvex:=j;p.next:=gai.link;gai.link:=p;向序号为 j 的单链表的表头插入一个边结点new(q);q.adjvex:=i;q.next:=gaj.link;gaj.link:=q;END;END;优先深度算法遍历图，邻接表PROCEDURE dfsadjoin(ga:adjlist;VAR visited:bool;i,n:integer
11、);VAR j:integer;p:edgeptr;BEGINwrite(i, );write(gai.data,; );visitedi:=true;p:=gai.link;WHILE pNIL DOBEGINj:=p.adjvex;IF (visitedjtrue)THEN dfsadjoin(ga,visited,j,n);p:=p.next;END;END;VARmyga:graph;myvisited:bool;i:integer;gl:adjlist;BEGIN14create(myga); 用邻接矩阵建立无向无权图邻接矩阵，优先深度算法遍历图FOR i:=1 TO vtxnum
12、DO myvisitedi:=false;dfsmatrix(myga,myvisited,1,vtxnum);用邻接表建立无向无权图initgadjoin(gl,vtxnum);IF gl1.link=NIL THEN write(null)ELSE write(not null);createadjoin(gl,vtxnum);邻接表，优先深度算法遍历图FOR i:=1 TO vtxnum DO myvisitedi:=false;dfsadjoin(gl,myvisited,1,vtxnum);END.实验 7 排序一、 实验目的1、 掌握常用的排序方法，并掌握用高级语言实现排序算法的方
13、法；2、 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3、 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、 实验内容统计成绩问题描述给出 n 个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2） 按名次列出每个学生的姓名与分数。基本要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。算法实现下面给出的是用直接选择排序算法实现的 C 语言程序。#define n 30typedef struct student char nam
14、e8;int score;15student Rn;main ( ) int num, i, j, max, temp;printf(“n 请输入学生成绩: n”);for (i=0; iRmax.score)max=j;if (max!=i) temp = Rmax;Rmax=Ri;Ri= temp;if (i0)&(Ri.scoreRi-1.score)num=num+1;printf(“%4d%s%4d”, num, Ri.name, Ri.score);实验五 查找一、实验目的1、掌握查找的不同方法，并能用高级语言实现查找算法；162、熟练掌握二叉树的构造和查找方法。二、实验内容设计一
15、个读入一串整数构成一棵二叉排序树的算法。实现提示二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。算法实现typedef struct node int key;int other;struct node *lchild, *rchild; bstnode;void inorder ( t )bstnode *t; if (t!=Null) inorder(tlchild);printf(“%4d”, tkey);inorder(trchild);bstnode *insertbst(t, s)bstnode *s, *t; bstnode *f, *p;p=t;while(p!=Null) f=p;if (skey= =pkey) return t;if (skeypkey) p=plchild;else17p=prchild;if(t= =Null) return s;if (skeyfkey) flchild=s;elsefrchild
