××大学计算机工程学院实验报告

课程名称：数据结构 班级：xxxx 实验成绩：

指导老师：××× 姓名：xxx

实验项目名称：复数四则运算 学号：2005810112 上机实践日期：

实验项目编号：实验一 组号： 上机实践时间：学时

一 目的（本次试验所涉及并要求掌握的知识点）

熟悉抽象数据类型的表示和实现方法。抽象数据类型需借助固有数据类型来表示和实现，及利用高级程序设计语言中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作，具体实现细节则依赖于所用的语言的功能。通过本次实习还可以帮助读者复习高级语言的使用方法。

二实验内容与设计思想（设计思路 主要数据结构 主要代码结构。主要代码段分析 电路图）

1．问题描述

设计一个可进行复数运算的演示程序

2．基本要求

实现下列六种基本运算：1）由输入的实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数的求积；5）从已知复数中分离出实部；6）从已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。

3．程序代码

#include

typedef struct Complex

{

float shi;

float xu;

}Complex;

void CreatComplex(Complex &c,float a,float b)

{

cshi=a;

cxu=b;

}

void AddComplex(Complex &sum,Complex c1,Complex c2)

{

sumshi=c1shi+c2shi;

sumxu=c1xu+c2xu;

}

void ChaComplex(Complex &cha,Complex c1,Complex c2)

{

chashi=c1shi-c2shi;

chaxu=c1xu-c2xu;

}

void JiComplex(Complex &ji,Complex c1,Complex c2)

{

jishi=c1shic2shi-c1xuc2xu;

jixu=c1shic2xu+c1xuc2shi;

}

void Print(Complex c)

{

if(cshi==00)

printf("%52f\n",cshi);

else

printf("%52f+i%52f\n",cshi,cxu);

if(cxu==00)

printf("%i52f\n",cxu);

}

void Print_shi(Complex c)

{

printf("该复数的实部是：%52f\n",cshi);

}

void Print_xu(Complex c)

{

printf("该复数的虚部是：i%52f\n",cxu);

}

void main()

{

float a,b,c,d;

int i,j;

Complex c1,c2,sum,cha,ji;

printf("请分别输入两个复数的实部和虚部：\n");

scanf("%f%f%f%f",&a,&b,&c,&d);

CreatComplex(c1,a,b);

Print(c1);

Print_shi(c1);

Print_xu(c1);

CreatComplex(c2,c,d);

Print(c2);

Print_shi(c2);

Print_xu(c2);

printf("1求和,\t2求差,\t3求积\t,4退出\n");

for(j=0;;j++)

{

scanf("%d",&i);

switch(i)

{

case 1:

AddComplex(sum,c1,c2);

Print(sum);

Print_shi(sum);

Print_xu(sum);

break;

case 2:

ChaComplex(cha,c1,c2);

Print(cha);

Print_shi(cha);

Print_xu(cha);

break;

case 3:

JiComplex(ji,c1,c2);

Print(ji);

Print_shi(ji);

Print_xu(ji);

break;

case 4:

return;

}

}

}

三实验使用环境（本实验所使用的平台和相关的软件）

Microsoft Visual C++ 60

四 实验步骤和调试过程（实验步骤 测试数据设计 测试结果分析）

1测试数据设计

测试数据： 1)0，0；0，0

2)31，0；422，89

3)-133，234；01，-65

4)0，97；-21，-97

5)77，-8；-77，0

测试结果： 1)0

2)732+i89

3)-123-i416

4)-21

5)-i8

2测试结果:

图略

五 实验小结（实验过程中遇到的问题及解决过程实验体会和收获）

1 通过学习以前C语言课程中的函数思想,可以重新熟悉函数在编程中的设置方法,熟悉函数中参数的设置和传递过程

2 通过多个函数出现在同一个程序中的实现,便于熟悉全局变量和局部变量在程序中的不同作用域的问题

六附录（参考文献和相关资料）

[1]严蔚敏，吴伟民编著：《数据结构(C语言版)》，北京：清华大学出版社，1997

[2]严蔚敏，吴伟民，米宁编著：《数据结构题集(C语言版)》，北京：清华大学出版社

设人数为N，且只有相邻的能够交换，则1要走过的距离为N-1（即需要N-1次交换），2需要N-2次交换，3需要N-3次交换，一直到N，需要N-(N-1)=1次，则总需要的时间为1到N-1的求和。

等于N(N-1)/2

数据结构实验报告

实验名称： 实验四——题目一

学生姓名： 唐文旭

班 级：2013211118

班内序号： 09

学 号： 2013210524

日 期： 2015年1月5日

1．实验要求

使用简单数组实现下面各种排序算法，并进行比较。

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2 程序分析

21 存储结构

22 关键算法分析

北京邮电大学信息与通信工程学院

第2页

希尔排序又称“缩小增量排序”，是对直接插入排序的一种改进，它利用了直接插入的两个特点：1 基本有序的序列，直接插入最快；2 记录个数很少的无序序列，直接插入也很快。希尔排序的基本思想为：将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。

冒泡排序的基本思想是：两两比较相邻的元素，如果反序，则交换位置，直到没有反序的元素为止。具体的排序过程是：将整个待排序元素划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的元素；对无序区从前向后依次将相邻元素的关键码进行比较，若反序则交换，从而使得关键码小的元素向前移，关键码大的元素向后移；重复执行前一个步骤，直到无序区中没有反序的元素。

快速排序元素的比较和移动是从两端向中间进行的。快速排序的基本思想是：在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分区重复上述过程，直到整个序列有序。

简单选择排序的基本思想是：第1趟，在待排序记录r[1„n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2„n]中选出最小的记录，将它与r[2]交换；以此类推，第i 趟，在待排序记录r[i„n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

r[0]留空，初始时赋为0

22 关键算法分析

1、直接插入排序

自然语言描述：

（1） 将整个待排序的记录划分成有序区和无序区。有序区为待排序记录的第一个记录， 无序区为所有剩余带待排序记录。

（2） 从第二个数据开始依次插入到有序区中，直到所有记录插入完毕。 （3） 在r[0]处设置“哨兵”，记为要插入的记录r[i]，在自i-1起往前查找的过程中，同时

后移记录。

（4） 找到插入位置后，将待插入记录插入到有序表中。

（5） 重复执行（3）、（4），直到无序区中没有记录。

伪代码描述：

初始化比较次数compare =0，移动次数move =0 2 for(int i=2;i

for(j=i-1;r[0]

r[j+1]=r[j] 比较次数++；移动次数++；

r[j+1]=r[0]，移动次数++

时间复杂度：最好情况下，待排序序列为正序，每趟秩序与有序序列的最后一个纪录的关键码比较一次，移动两次记录。总的比较次数为n-1，记录移动的次数为2（n-1）。因此，时间复杂度为O （n ）。

最坏情况下，待排序序列为逆序，比较次数为(n+2)(n+1)/2，移动次数为(n+4)(n-1)/2因此，时间复杂度为O （n2）

平均情况下，总的比较次数为n （n-1）/4，移动次数为（n+4）（n-1）/4，因此，时间复杂度

为O （n2）

2、希尔排序

自然语言描述：

（1） 假设待排序记录为n 个，先取整数d

中的前一个记录比较，在插入记录r[i]时，自r[i-d]往前查找待插入位置，在查找过程中，记录后移也是移动d 个位置。

（3） 当搜索位置j=r[j]，表示插入位置已经找到。在整个序列中，前d 个记 录分别是d 个子序列的第一个记录，所以从第d+1个记录开始插入。 （4） 再缩小d ，重复以上步骤，再对每个子序列进行直接插入排序，直到d=1，即将所有

记录放在一组进行一次直接插入排序，最终将所有记录重新排序得到有序序列。

伪代码描述：

1 初始化比较次数compare =0，移动次数move =0

for(int d=n/2;d>=1;d=d/2)

for(int i=d+1;i

if(r[i]

r[0]=r[i]，移动次数++

for(j=i-d;i>0&&r[0]

r[j+d]=r[j] 比较次数++，移动次数++

r[j+d]=r[0]，移动次数++

时间复杂度：

希尔排序的时间性能分析是一个复杂的问题，因为它是所取增量的函数。有人在大量实验的基础上指出，希尔排序的时间性能在O （n2）和O （nlog2n ）之间

3、冒泡排序

自然语言描述：

（1） 将整个待排序的记录划分成有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量pos ，此位置之后的所有记录均已经有序。

（2） 对无序区从前向后一次将相邻记录的关键码进行比较，若反序则交换，从而使得关 键码小的记录前移，关键码大的记录后移。

（3） 每趟冒泡排序开始之前，设pos 初值为0，在该趟排序过程中，只要有记录的交换，pos 就大于0。通过pos 是否为0判断是否有记录的交换，从而判断冒泡排序是否结束。 伪代码描述：

初始化比较次数compare =0，移动次数move =0

int pos=0 2 while(pos!=0)

int bound=pos，pos=n

for(int j=1;j

if(r[j]>r[j+1])

r[0]=r[j]，r[j]=r[j+1],r[j+1]=r[0]

pos=j，move+=3

时间复杂度：

最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键妈的比较，不需要移动记录，时间复杂度为O （n ） 最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的纪录被交换到最终位置，故算法执行n-1趟，第i 趟排序执行了n-1

次关键码的比较和n-i 次记录的交换，这样，关键码的比较次数为n （n-1）/2，记录的移动次数为3n （n-1）/2平均情况下，起泡排序的时间复杂度与最坏情况同数量级。

4、快速排序

自然语言描述：

（1） 取第一个记录作为基准，设置两个参数i ，j 分别用来指示将要与基准记录进行比较 的左侧记录位置和右侧记录位置，也就是本次划分的区间。 （2） 右侧扫描过程：将基准记录与j 指向的记录进行比较，如果j 指向记录的关键码大，

则j--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[i]=r[j] （3） 左侧扫描过程：将基准记录与i 指向的记录进行比较，如果i 指向记录的关键码大，

则i--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[j]=r[i]

（4） 重复执行（2）、（3），直到i 、j 指向同一位置。 （5） r[i]=pivot （6） 返回i 的位置 伪代码描述：

int i=first; int j=end; int pivot=r[i] 2 while(i

while((i=pivot))

j--; 比较次数++

r[i]=r[j] 23 if(i

while((i

r[j]=r[i] 26 if(i

r[i]=pivot; return i ;

时间复杂度：

最好情况下，每次划分对一个记录定位后，该记录的左侧子序列和右侧子序列的长度相同。在具有n 个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需时间为O

（n ）。时间复杂度为O （nlog2n ）。 最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个纪录的子序列（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i 趟划分需要经过n-i 次关键码的比较才能找到第i 个记录的基准记录，因此总的比较次数为n （n-1）/2，记录的移动次数小于等于比较次数。因此时间复杂度为O （n2） 平均情况下，可以用归纳法证明，其数量级也为O （nlog2n ）。

5、简单选择排序

自然语言描述：

（1） 将整个记录划分为有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量index ，记录一次比较中关键码最小的位置。

（2） 第i 趟简单选择排序的待排序区间是r[i]-r[n]，首先将index 设定为当前无序区的第一个位置，然后用r[index]与无序区中其他记录进行比较，若有比r[index]小的记录，就将index 改为这个新的最小的记录的位置。

（3） 如果index 不等于i ，则将它与无序区中第一个记录交换，有序区增加一个记录，无 序区减少一个记录。 （4） 重复（2）（3），直到无序区只剩下一个记录为止。此时所有记录已经按照从小到大

的顺序排好。 伪代码描述：

初始化比较次数compare=0，移动次数move=0

for(int i=1;i

int index=i

for(int j=i+1;j

if(r[j]

if(index!=i)

r[0]=r[i];r[i]=r[index];r[index]=r[0]

move+=3

时间复杂度：待排序序列为正序时，记录的移动次数最少，为0次。在待排序序列为逆序时，记录的移动次数最多为3（n-1）次。

无论记录的初始排列如何，关键码的比较次数相同，第i 趟排序需进行n-1次关键码的比较，而简单选择排序需进行n-1趟排序，则总的比较次数为n （n-1）/2=O（n2）。所以， 总的时间复杂度为O(n2)，这是简单选择排序最好、最坏、和平均的时间性能。

3 程序运行结果

测试条件：

问题规模的数量级是4，正序逆序由键盘输入，随机数由随机数生成函数生成。

测试结论：

程序对不同序列的数组运用各种不同方法进行排序时均能得到正确的排序结果，同时能够给出正确的比较次数和移动次数。

4 总结

插入排序：nn的时间复杂度，稳定排序，原地排序。在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。

希尔排序：nlog(n)的时间复杂度， 非稳定排序，原地排序。主要思想是分治，不过他的分治和合并排序的分治不一样，他是按步长来分组的，而不是想合并那样左一半右一半。 开始

输出测试数组

进行简单插入排序 进行希尔排序

进行起泡排序 进行快速排序

进行简单选择排序 结束

开始步长为整个的长度的一半，然后每组排序。接个步长减为原来的一半在分组排序，直到步长为1，排序之后希尔排序就完成了。这个思路很好，是插入排序的升级版，我觉得他是一个特别好的排序方法了。他的缺点就是两个数可能比较多次，但效率也是很高的。

冒泡排序，nn的时间复杂度，稳定排序，原地排序。冒泡排序的思想很不错，一个一个比较，把小的上移，依次确定当前最小元素。因为他简单，稳定排序，而且好实现，所以用处也是比较多的。

选择排序，nn的时间复杂度， 稳定排序，原地排序。选择排序就是冒泡的基本思想，从小的定位，一个一个选择，直到选择结束。和插入排序是一个相反的过程，插入是确定一个元素的位置，而选择是确定这个位置的元素。它的好处就是每次只选择确定的元素，不会对很多数据进行交换。所以在数据交换量上应该比冒泡小。

很难吗？树结构哦。看你数据结构学的怎么样呗。呵呵，我先想到的数据结构是双亲孩子表示法，当然查找关系的时候就要进行一些条件设置，比如祖孙的关系数大于父子的关系数2，兄弟拥有相同的双亲，堂兄弟的双亲是兄弟，回溯到相同的祖先结点则有共同的祖先咯。