苏州科技学院

数据结构（C语言版）

实验报告

专业班级   测绘0911   

学    号   0920115130  

姓    名    朱辉      

实习地点    C1-203      

指导教师     史守正     

实验四   图

一、程序设计的基本思想，原理和算法描述：

图是一种较线性表和树更加复杂的一种数据结构，在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关，图主要有无向图，有向图等

（1）建立无向网的邻接矩阵存储并输出，参考程序清单，实现无向图的邻接矩阵表示。

（2）建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历

备注：无向图已完成，无向网需要自己建立(参照算法7.2)；参照算法7.4， 7.5，7.6完成图的深度遍历，广度遍历；请添加适当的注释。

二、源程序及注释（打包上传）：

三、运行输出结果：

四、调试和运行程序过程中产生的问题及采取的措施：

在程序编辑的过程中，有许多地方出现不能顺序运行的，还有代码出现遗漏出错，图的遍历是重点但因为知识的残缺不能完整的编译出来，又或者编译的程序不能正确的得到结果，再通过多人合作共同讨论后得到了满意的解决。

五、对算法的程序的讨论、分析，改进设想，其它经验教训：

经过这次这么复杂的程序实验，我终于发现了调用函数的巨大优越性，以前遇到都是很短的程序，感觉调用有点多余，但复杂的程序时，如果不采用调用的话，会使程序非常的乱，改程序时不知道从哪改，调用函数能够更好使程序简洁话，层次话，更加容易让人看懂这次试验的逻辑性给了我们很大启发通过本次实验让我对图有了更深刻的认识，再通过多次的更改后终于将实验做出来，在实验中也出现了许多问题，有不出结果，有不能运行的，但最终只要努力都会搞定的

实验五   查找

一、程序设计的基本思想，原理和算法描述：

实现二叉排序树上的查找、插入、删除算法。具体实现要求：

1.       用二叉链表做存储结构，输入键值序列，利用查找、插入算法建立一棵二叉排序树。

2.       按中序遍历这棵二叉排序树。

3.       在二叉排序树上插入结点。

4.       删除二叉排序树上的结点。

二、源程序及注释（打包上传）：

三、运行输出结果：

四、调试和运行程序过程中产生的问题及采取的措施：

查找是一种常用到的方法在程序中十分常见，在程序运行中。由于对遍历了解的不深刻不能够完全领悟其中的运行原理，所以出现没有结果输出的现象。在书中不断的了解分析下从而得到了解决，书本的知识很有作用。

五、对算法的程序的讨论、分析，改进设想，其它经验教训：

 经过这次这么复杂的程序实验，我终于发现了调用函数的巨大优越性，以前遇到都是很短的程序，感觉调用有点多余，但复杂的程序时，如果不采用调用的话，会使程序非常的乱，改程序时不知道从哪改，调用函数能够更好使程序简洁话，层次话，更加容易让人看懂这次试验的逻辑性给了我们很大启发，在程序不断复杂的今天只有很好了解程序的过程，把握程序中心思想才能够更好的完善研发程序，在不断的累积中达到更高的层次。

实验六   排序

一、程序设计的基本思想，原理和算法描述

排序是计算机程序设计中的一种重要操作。它的主要思想是将一个数据元素的任意序列，比较多种排序的优劣主要是看它排序的效率。重新排列成一个按关键字有序的序列，编写主函数，分别实现直接插入、冒泡排序（算法在P16）、快速排序、简单选择排序、堆排序等排序算法。

（1）直接插入排序：是一种最简单的排序，是将一个记录插入到已排好序的初始排列中

冒泡排序；依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

　　由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

　　用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i。

二、源程序及注释（打包上传）：

三、运行输出结果：

四、调试和运行程序过程中产生的问题及采取的措施：

   刚开始看到程序，太长，一点也看不懂它的意思，无从下手的感觉，这是就要考验人的耐心，慢慢看，结合书里所讲的知识，终于理解整个程序，还有递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。

五、对算法的程序的讨论、分析，改进设想，其它经验教训：

排序是非常重要的一种技术手段，能够提高效率，简化过程，选择何种排序方法需要我们更好的理解各种排序方法的主要思想及原理，这对我们以后工作的帮组是非常大的，经过这次这么复杂的程序实验，我终于发现了调用函数的巨大优越性，以前遇到都是很短的程序，感觉调用有点多余，但复杂的程序时，如果不采用调用的话，会使程序非常的乱，改程序时不知道从哪改，调用函数能够更好使程序简洁话，层次话，更加容易让人看懂这次试验的逻辑性给了我们很大启发。

第二篇：数据结构c语言版实验报告

1. 【98初程P71】 内的最确切的解答，把相应编号写在答卷的对应栏内。

设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。

供选择的答案：

A～D：①a1 ②a2 ③ a3 ④a4

E： ①1 ②2 ③ 3 ④ 0

答：ABCDE＝2, 4, 1, 2, 2

D2．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元

素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为

（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f;

（Ｄ）（n＋r－f）% n

3. 【94初程P75】 内的最确切的解答，把相应编号写在答卷的对应栏内。

栈是一种线性表，它的特点是 A 。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。

供选择的答案：

A： ① 先进先出 ②后进先出 ③进优于出 ④出优于进 ⑤ 随机进出 B，C： ① 加1 ②减1 ③不变 ④清0 ⑤ 加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c

E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2

答案：ABCDE=2, 2, 1, 6, 4

4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120

5.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

6. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

10.求下列广义表操作的结果：

（1） GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号

（2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;

（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ;

（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） ;

7.【94程P12】 有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 A 个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A[2,4]的第一个字节的地址是 C 。若按列存储，则A[5,7]的第一个字节的地址是 D 。

供选择的答案

A～D：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120

⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288

答案：ABCD=12, 10, 3, 9

( B )5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是：

Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j

?a1,1?

A??a2,1a2,2

?

??

??an,1an,2

6. 【91初程P78】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。

存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是 B 和 C 。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E 。

供选择的答案：

A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108

⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188

答案：ABCDE=8, 3, 5, 1, 6

????a?n,n???