c++ 数据结构 课程设计

Question

1．排序算法比较
利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。
要求 ：每一种排序都要使用，统计时间要求调用系统时间然后做差求出。
2．二叉树的周游
对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用递归或非递归方式实现二叉树的先序、中序、后序三种周游，输出三种周游的结果。

要求 所有程序无错误，运行速度快，数据无冗余~

Answer 1

1、起泡排序
算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好

bubblesort(struct rec r[]，int n)
{
int i，j;
struct rec w;
unsigned long int compare=0，move=0;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
{
if(r[j].key<r[j-1].key)
{
w=r[j];
r[j]=r[j-1];
r[j-1]=w;
move=move+3;
}
compare++;
}
printf("
BubbleSort compare= %ld，move= %ld
"，compare，move);
}

2、直接插入排序
算法：经过i-1遍处理后，L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止

insertsort(struct rec r[]，int n)
{
int i，j;
unsigned long int compare=0，move=0;
for(i=2;i<=n;i++)
{compare++;
r[0]=r[i];
move++;
j=i-1;
while(r[0].key {r[j+1]=r[j];
j--;
move++;
++compare;}
r[j+1]=r[0];
move++;
}
printf("
InsertSort compare= %ld，move= %ld
"，compare，move);
}

3、简单选择排序
算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。

selectsort(struct rec r[]，int n)
{
unsigned long int compare=0，move=0;
int i，j，k;
struct rec w;
for(i=1;i<=n-1;i++)
{ k=i;
for(j=i+1;j<=n;j++)

{ if(r[j].key>r[k].key) {k=j; compare++; }
w=r[i];
r[i]=r[k];
r[k]=w;
move=move+3;

}
}
printf("
SelectSort compare= %ld，move= %ld
"，compare，move);
}

4、快速排序
算法：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。
通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多

q(struct rec r[]，int s，int t)
{
int i=s，j=t;
if(s<t)
{
r[0]=r[s]; ++a; c++;
do{
while(j>i&&r[j].key>=r[0].key)
{j--;
++a; }
if(i<j)
{ r[i]=r[j];
i++;
c++; }
while(i<j&&r[i].key<=r[0].key)
{i++;
++a; }
if(i<j)
{ r[j]=r[i];
j--;
c++; }
} while(i<j);
r[i]=r[0];
c++;
q(r，s，j-1);
q(r，j+1，t);
}
}

5. 堆排序
(1) 基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
(2) . 堆的定义: N个元素的序列K1，K2，K3，...，Kn.称为堆，当且仅当该序列满足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

sift(struct rec r[]，int l，int m)
{
int i，j;
struct rec w;
i=l; j=2*i;
w=r[i];
while(j<=m)
{
if(j<m&&r[j].key<r[j+1].key) { j++;
}
if(w.key<r[j].key)
{
r[i]=r[j];
i=j;
j=2*i;
}
else j=m+1;
}
r[i]=w;
}

heapsort(struct rec r[]，int n)
{
unsigned long int compare=-1，move=-1;
struct rec w;
int i;
int a;
for(i=n/2;i>=1;i--) a=sift(r，i，n);
compare++;
move++;

for(i=n;i>=2;i--)
{
w=r[i];
r[i]=r[1];
r[1]=w;
a=sift(r，1，i-1);
compare+=a;
move+=a;
}
}

Answer 2

这么多....