数据结构与算法-东北林业大学 《数据结构》实验指导书new.doc

1计算机科学与技术专业《数据结构》实验指导书关于实习步骤的要求和建议从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规 范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的 程序编制风格，培养严谨、科学、高效的工作方式在以往的教学实践中，经常发现很多学生抱怨说，化了两个小时才找出一 个错误，甚至一无所获他们不明白造成这种情况的原因，正是他们自 己有的学生不屑于按实习步骤规范去做，甚至对于实习步骤的要求和建 议看都不看一遍，认为那是浪费时间，这是及其害的实习步骤规范不但 可以培养科学化的工作作风，而且还能有效地避免错误具体的步骤机规范如下：1．问题分析与系统的结构设计充分地分析和理解问题本身，弄清要求作什么，限制条件是什么按照 以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操 作，使得对数据结构的存取通过这些操作加以实现在这个过程中，要综合考 虑系统功能要考虑系统结构清晰、合理、简单并且易于调试最后写出每个 子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示则更加清晰，这样便完成了系统结构设计2．详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。

用 IF 、 WHILE 和赋值语句等，以及自然语言写出算法的框架利用自然语言的目的 是避免陷入细节在编码是，可以对详细设计的结果进一步求精，用高级语言 表示出来程序的每一行最好不超过 60 个字符每个子程序（或过程、函数）通 常不要太长，以 40 行为宜子程序（或过程、函数）包含的程序行数太多， 易于造成理解的困难控制 IF 、WHILE 等语句的连续嵌套的深度程序的目 的性必须明确对每一段程序完成的作用，除非常明显的除外（如：x = x + 1; 注释为 x 加 1，没有什么意义），都应加以注释这会对程序的调试提供很多 方便另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你 的设想是否一致另外，对于输入输出语句，必须对它们的作用加以说明否 则，在调试程序时，无法了解系统需要输入说明，系统输出的又是什么程序 的书写，必须按照一定的规范，如保留字小写时涂黑，或者大写等等具体的 要求可参看软件工程中的有关规定 3．上机准备和静态检查1 高级语言文本2 熟悉机器的用户手册，熟悉常用的命令3 准备调试的工具，考虑调试方案如果机器上没有现成的调试工具可供利用，可以自己先设计一些以供使用。

4 静态检查自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了解该程序的逻辑4． 上机调试程序自底向上，先调试底层模块，再调试上层模块最后，整个程序进行联 调调试正确后将源程序和运行结果加以列印输出25． 实习报告的整理1 需求及规格说明问题描述，求解的问题是什么2 设计：设计思想：存储结构、主要的算法思想设计表示：子程序（过程或函数）的规格说明，通过调用关系图表 示它们之间的调用关系实现注释：详细设计表示：主要算法的框架3 用户手册：使用说明4 调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体会、时空复杂度等5 附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据提倡用英文描述6 实验报告要求：在程序开发过程中，逐步形成各种必要的文档及资料可以写在实 验报告纸上，或以电子文档的形式进行书写上机实习以下的实习题目配合课程的进度，请同学们自己务必完成为了锻炼自 己的应用各种不同的数据结构的能力，尽可能的多作一些题目是非常必 要的在完成各种不同题目的过程中，对各种算法的时、空复杂性的分 析，将帮助您在更高的角度解决各种应用问题实验一 线性表的插入和删除一、 实验目的1、 掌握用 Turbo C 上机调试线性表的基本方法；2、 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、 实验内容线性表基本操作的实现当我们要性表的顺序存储结构上的第 i 个位置上插入一个元素时，必须先将线性表的第 i 个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置若要删除第 i 个元素时，也必须把第 i 个元素之后的所有元素前移一个位置程序实现：typedef Null 0;typedef int datatype;#define maxsize 1024;3typedef struct{ datatype data[maxsize];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--)(*L).data[j+1]=(*L).data[j];(*L).data[i-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.arcs[i,j].adj0) AND (visited[j]true))THEN dfsmatrix(ga,visited,j,n);END;END;{初始化邻接表}PROCEDURE initgadjoin(VAR ga:adjlist;n:integer);VAR j:integer;BEGINFOR j:=1 TO n DOBEGINga[j].link:=NIL;write('input value:');read(ga[j].data);END;FOR j:=1 TO n DOBEGINwriteln(ga[j].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);13FOR k:=1 TO e DOBEGINwriteln('input two vertexs:');read(i,j); {输入一条无向无权的边的两个顶点的序号}{向序号为 i 的单链表的表头插入一个边结点}new(p);p^.adjvex:=j;p^.next:=ga[i].link;ga[i].link:=p;{向序号为 j 的单链表的表头插入一个边结点}new(q);q^.adjvex:=i;q^.next:=ga[j].link;ga[j].link:=q;END;END;{优先深度算法遍历图，邻接表}PROCEDURE dfsadjoin(ga:adjlist;VAR visited:bool;i,n:integer);VAR j:integer;p:edgeptr;BEGINwrite(i,' ');write(ga[i].data,'; ');visited[i]:=true;p:=ga[i].link;WHILE pNIL DOBEGINj:=p^.adjvex;IF (visited[j]true)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 DO myvisited[i]:=false;dfsmatrix(myga,myvisited,1,vtxnum);{用邻接表建立无向无权图}initgadjoin(gl,vtxnum);IF gl[1].link=NIL THEN write('null')ELSE write('not null');createadjoin(gl,vtxnum);{邻接表，优先深度算法遍历图}FOR i:=1 TO vtxnum DO myvisited[i]:=false;dfsadjoin(gl,myvisited,1,vtxnum);END.实验 7 排序一、 实验目的1、 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；2、 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3、 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、 实验内容统计成绩[问题描述]给出 n 个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2） 按名次列出每个学生的姓名与分数[基本要求]学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制[算法实现]下面给出的是用直接选择排序算法实现的 C 语言程序define n 30typedef struct student{ char name[8];int score;15}student R[n];main ( ){ int num, i, j, max, temp;printf(“\n 请输入学生成绩: \n”);for (i=0; iR[max].score)max=j;if (max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;}if ((i>0)&&(R[i].score

二、实验内容设计一个读入一串整数构成一棵二叉排序树的算法[实现提示]二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可[算法实现]typedef struct node { int key;int other;struct node *lchild, *rchild;} bstnode;void inorder ( t )bstnode *t;{ if (t!=Null){ inorder(t→lchild);printf(“%4d”, t→key);inorder(t→rchild);}}bstnode *insertbst(t, s)bstnode *s, *t;{ bstnode *f, *p;p=t;while(p!=Null){ f=p;if (s→key= =p→key) return t;if (s→key