关于数据结构的课程设计
n的阶。现通过随机输入多组不同个数的数据，对各种算法的关键字比较次数、移动次数及执行时间进行比较，以求得实验理论。
• 基本要求
• 随机产生n=100，200，300，1000，2000个整数并存于数组A[1..n]中。对主要查找算法（顺序查找、插入排序、归并排序、堆排序、快速排序）进行实验比较，计算出平均比较次数 、平均移动次数 及执行时间 。 、 由程序自动计算， 由手工计时。
• 对实验结果数据进行对比分析 展开
#include "stdio.h"
#define MAX 30000
/* 函数声明区 */
int SequenceSearch(int e[], int len, int key);
int BinarySearch(int e[], int len, int key);
void StraightInsertSort(int e[], int len);
void QuickSort(int e[], int first, int end);
void MergeSort(int e[],int a[],int first,int end);
void HeapSort(int e[],int len);
void Print(int e[], int len, int cols);
/* 全局变量区 */
long compare; /* 比较次数 */
long move; /* 移动次数 */
void main()
{
int i;
int n;
int table[MAX], table1[MAX];
int key;
int pos;
int choice;
int cols = 10;
system("cls");
printf("***********************************************************\n");
printf("INITIALIZE TABLE\n");
printf("n = ");
scanf("%d", &n);
srand(time(NULL));
for(i=0; i<n; i++)
{
table[i] = rand();
table1[i] = table[i];
}
while(1)
{
system("cls");
printf("***********************************************************\n");
printf("ORIGIN TABLE (%d) : \n", n);
Print(table, n, cols);
printf("***********************************************************\n");
printf("ORDER TABLE (%d) : \n", n);
StraightInsertSort(table1, n);
Print(table1, n, cols);
printf("***********************************************************\n");
printf(" ALGORITH ANALYSIS SYSTEM \n\n");
printf(" 1. SEQUENCE SEARCHING \n");
printf(" 2. BINARY SEARCHING \n");
printf(" 3. STRAIGHT INSERT SORTING \n");
printf(" 4. MERGE SORTING \n");
printf(" 5. HEAP SORTING \n");
printf(" 6. QUICK SORTING \n");
printf(" 0. EXIT SYSTEM \n\n");
printf("***********************************************************\n\n");
printf(" YOUR CHOICE : ");
scanf("%d", &choice);
switch(choice)
{
case 0:
return;
case 1:
{
/***********************************************************************/
/* 执行顺序查找 */
printf("\t\tkey = ");
scanf("%d", &key);
compare = 0;
pos = SequenceSearch(table, n, key);
printf("\t\tSequence Searching \n");
printf("----------------------------------------\n");
printf("Analysis details : \n");
if(pos == -1)
{
printf("\tsearch %d fail.\n", key);
printf("\tcompare : %ld times.", compare);
}
else
{
printf("\tsearch %d success.\n", key);
printf("\tcompare : %ld times.", compare);
}
printf("\n\n");
/***********************************************************************/
break;
}
case 2:
{
/***********************************************************************/
/* 执行二分查找 */
printf("\t\tkey = ");
scanf("%d", &key);
compare = 0;
pos = BinarySearch(table1, n, key);
printf("\t\tBinary Searching \n");
printf("----------------------------------------\n");
printf("Analysis details : \n");
if(pos == -1)
{
printf("\tsearch %d fail.\n", key);
printf("\tcompare : %ld times.", compare);
}
else
{
printf("\tsearch %d success.\n", key);
printf("\tcompare : %ld times.", compare);
}
printf("\n\n");
/***********************************************************************/
break;
}
case 3:
{
/***********************************************************************/
/* 执行直接插入排序 */
for(i=0; i<n; i++)
table1[i] = table[i];
compare = move = 0;
StraightInsertSort(table1, n);
printf("\t\tStraight Insert Sorting \n");
printf("----------------------------------------\n");
printf("Analysis details : \n");
printf("\tcompare : %ld times.\n", compare);
printf("\tmove : %ld times.\n\n", move);
/***********************************************************************/
break;
}
case 4:
{
/***********************************************************************/
/* 执行归并排序 */
for(i=0; i<n; i++)
table1[i] = table[i];
compare = move = 0;
MergeSort(table1, table, 0, n-1);
printf("\t\tMerge Sorting \n");
printf("----------------------------------------\n");
printf("Analysis details : \n");
printf("\tcompare : %ld times.\n", compare);
printf("\tmove : %ld times.\n\n", move);
/***********************************************************************/
break;
}
case 5:
{
/***********************************************************************/
/* 执行堆排序 */
for(i=0; i<n; i++)
table1[i] = table[i];
compare = move = 0;
HeapSort(table1, n);
printf("\t\tHeap Sorting \n");
printf("----------------------------------------\n");
printf("Analysis details : \n");
printf("\tcompare : %ld times.\n", compare);
printf("\tmove : %ld times.\n\n", move);
/***********************************************************************/
break;
}
case 6:
{
/***********************************************************************/
/* 执行快速排序 */
for(i=0; i<n; i++)
table1[i] = table[i];
compare = move = 0;
QuickSort(table1, 0, n-1);
printf("\t\tQuick Sorting \n");
printf("----------------------------------------\n");
printf("Analysis details : \n");
printf("\tcompare : %ld times.\n", compare);
printf("\tmove : %ld times.\n\n", move);
/***********************************************************************/
break;
}
default:
break;
}/* end of switch*/
system("pause");
getch();
}
}
/* 顺 序 查 找 */
int SequenceSearch(int e[], int len, int key)
{
int i;
for(i=0; i<len ; i++)
if(++compare && e[i]==key)
return i;
++compare;
return -1;
}
/* 二 分 查 找 */
int BinarySearch(int e[], int len, int key)
{
int high,low,mid;
high=len-1;
low=0;
while(low<=high)
{
mid=(low+high)/2;
++compare;
if(key==e[mid])
return mid;
else if(key>e[mid])
low=mid+1;
else
high=mid-1;
}
++compare;
return -1;
}
/* 直 接 插 入 排 序 */
void StraightInsertSort(int e[], int len)
{
int i,j,temp;
for(i=1; i<len; i++)
{
temp=e[i];
++move;
for(j=i-1; j>=0; j--)
{
if(++compare && e[j] > temp)
{
e[j+1]=e[j];
++move;
}
else
break;
}
e[j+1]=temp;
++move;
}
}
/* 快 速 排 序 */
void QuickSort(int e[], int first, int end)
{
int i=first,j=end,temp=e[first];
while(i<j)
{
while(++compare && i<j && e[j]>=temp)
j--;
e[i]=e[j];
++move;
while(++compare && i<j && e[i]<=temp)
i++;
e[j]=e[i];
++move;
}
e[i]=temp;
if(first<i-1)
QuickSort(e,first,i-1);
if(end>i+1)
QuickSort(e,i+1,end);
}
/* 归 并 排 序 */
void MergeSort(int e[],int a[],int first,int end)
{
void Merge(int e[],int a[],int first,int m,int end);
int m;
int bak[MAX];
if(first==end)
a[first]=e[first];
else
{
m=(first+end)/2;
MergeSort(e,bak,first,m);
MergeSort(e,bak,m+1,end);
Merge(bak,a,first,m,end);
}
for(m=0;m<=end;m++)
e[m]=a[m];
}
void Merge(int e[],int a[],int first,int m,int end)
{
int i=first,j=m+1,k=first;
while(i<=m && j<=end)
{
++compare;
++move;
if(e[i]<=e[j])
a[k++]=e[i++];
else
a[k++]=e[j++];
}
while(i<=m && ++move)
a[k++]=e[i++];
while(j<=end && ++move)
a[k++]=e[j++];
}
/* 堆 排 序 */
void HeapSort(int e[],int len)
{
void sift(int e[],int l,int m);
int i,temp;
for(i=len/2-1;i>=0;i--)
sift(e,i,len);
for(i=len-1;i>=1;i--)
{
move += 2;
temp=e[i];
e[i]=e[0];
e[0]=temp;
sift(e,0,i-1);
}
}
void sift(int e[],int l,int m)
{
int i,j,x;
i=l;
j=2*i+1;
x=e[i];
while(j<=m)
{
if(j<m && ++compare && e[j]<e[j+1])
j++;
if(++compare && x<e[j])
{
++move;
e[i]=e[j];
i=j;
j=2*i+1;
}
else j=m+1;
}
e[i]=x;
++move;
}
void Print(int e[], int len, int cols)
{
int i;
for(i=1; i<=len; i++)
{
printf("%6d", e[i-1]);
if(i%cols == 0)
printf("\n");
}
printf("\n");
}
运行测试：
已赞过
已踩过<
