数据结构(C语言版)实验报告

QuickSort(R,pivotpos+1,high); //对右区间递归排序 } }

//======直接选择排序======== void SelectSort(SeqList R) {

int i,j,k;

for(i=1;i

for(j=i+1;j<=n;j++) //在当前无序区R[i‥n]中选key最小的记录R[k] if(R[j].key

k=j; //k记下目前找到的最小关键字所在的位置 if(k!=i) { // //交换R[i]和R[k] R[0]=R[i]; R[i]=R[k]; R[k]=R[0]; } //endif } //endfor }

//==========大根堆调整函数=======

void Heapify( SeqList R,int low,int high)

{ // 将R[low..high]调整为大根堆,除R[low]外,其余结点均满足堆性质 int large; //large指向调整结点的左、右孩子结点中关键字较大者 RecType temp=R[low]; //暂存调整结点

for(large=2*low; large<=high;large*=2){ //R[low]是当前调整结点

//若large>high,则表示R[low]是叶子,调整结束;否则先令large指向R[low]的左孩子

if(large

large++; //若R[low]的右孩子存在且关键字大于左兄弟,则令large指向它

//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者 if(temp.key>=R[large].key) //temp始终对应R[low]

break; //当前调整结点不小于其孩子结点的关键字,结束调整 R[low]=R[large]; //相当于交换了R[low]和R[large]

low=large; //令low指向新的调整结点,相当于temp已筛下到large的位置 }

R[low]=temp; //将被调整结点放入最终位置上 }

//==========构造大根堆========== void BuildHeap(SeqList R)

{ //将初始文件R[1..n]构造为堆 int i;

for(i=n/2;i>0;i--)

Heapify(R,i,n); //将R[i..n]调整为大根堆 }

//==========堆排序=========== void HeapSort(SeqList R)

{ //对R[1..n]进行堆排序,不妨用R[0]做暂存单元 int i;

BuildHeap(R); //将R[1..n]构造为初始大根堆

for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序,共做n-1趟。 R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换

Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆,仅有R[1]可能违反堆性质。 } }

//=====将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]== void Merge(SeqList R,int low,int m,int high) {

int i=low,j=m+1,p=0; //置初始值 RecType *R1; //R1为局部量

R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //申请空间

while(i<=m && j<=high) //两个子序列非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)? R[i++]:R[j++];

while(i<=m) //若第一个子序列非空,则复制剩余记录到R1 R1[p++]=R[i++];

while(j<=high) //若第二个子序列非空,则复制剩余记录到R1中 R1[p++]=R[j++];

for(p=0,i=low;i<=high;p++,i++)

R[i]=R1[p]; //归并完成后将结果复制回R[low..high] }

//=========对R[1..n]做一趟归并排序======== void MergePass(SeqList R,int length) {

int i;

for(i=1;i+2*length-1<=n;i=i+2*length)

Merge(R,i,i+length-1,i+2*length-1); //归并长度为length的两个相邻的子序列

if(i+length-1

//注意:若i≤n且i+length-1≥n时,则剩余一个子序列轮空,无须归并 }

//========== 自底向上对R[1..n]做二路归并排序=============== void MergeSort(SeqList R) {

int length;

for(length=1;length

MergePass(R,length); //有序长度≥n时终止 }

//==========输入顺序表======== void input_int(SeqList R) { int i;

printf(\ scanf(\

printf(\ for(i=1;i<=n;i++)

scanf(\}

//==========输出顺序表======== void output_int(SeqList R) {

int i;

for(i=1;i<=n;i++)

printf(\}

//==========主函数====== void main() {

int i; SeqList R; input_int(R);

printf(\ printf(\ printf(\ printf(\

printf(\ printf(\ printf(\ printf(\

printf(\ scanf(\输入整数1-7,选择排序方式 switch (i){

case 1: InsertSort(R); break; //值为1,直接插入排序 case 2: BubbleSort(R); break; //值为2,冒泡法排序 case 3: QuickSort(R,1,n); break; //值为3,快速排序

case 4: SelectSort(R); break; //值为4,直接选择排序 case 5: HeapSort(R); break; //值为5,堆排序

case 6: MergeSort(R); break; //值为6,归并排序 case 7: exit(0); //值为7,结束程序 }

printf(\ output_int(R); }

实验结果:

Please input num(int):10 Plase input 10 integer:265 301 751 129 937 863 742 694 76 438 ******** Select ********** 1: Insert Sort 2: Bubble Sort 3: Quick Sort 4: Straight Selection Sort 5: Heap Sort 6: Merge Sort 7: Exit ***************************

1 129, 265, 301, 751, 937, 863, 742, 694, 76, 438, 129, 265, 301, 751, 863, 937, 742, 694, 76, 438, 129, 265, 301, 742, 751, 863, 937, 694, 76, 438, 129, 265, 301, 694, 742, 751, 863, 937, 76, 438, 76, 129, 265, 301, 694, 742, 751, 863, 937, 438, 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 2

76,265,301,751,129,937,863,742,694,438, 76,129,265,301,751,438,937,863,742,694, 76,129,265,301,438,751,694,937,863,742, 76,129,265,301,438,694,751,742,937,863, 76,129,265,301,438,694,742,751,863,937,

Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 3

76,129,265,751,937,863,742,694,301,438, 76,129,265,751,937,863,742,694,301,438,

76,129,265,438,301,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937,

Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 4

76,301,751,129,937,863,742,694,265,438, 76,129,751,301,937,863,742,694,265,438, 76,129,265,301,937,863,742,694,751,438, 76,129,265,301,438,863,742,694,751,937, 76,129,265,301,438,694,742,863,751,937, 76,129,265,301,438,694,742,751,863,937,

Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 5

863,694,751,265,438,301,742,129, 76,937, 751,694,742,265,438,301, 76,129,863,937, 742,694,301,265,438,129, 76,751,863,937, 694,438,301,265, 76,129,742,751,863,937, 438,265,301,129, 76,694,742,751,863,937, 301,265, 76,129,438,694,742,751,863,937, 265,129, 76,301,438,694,742,751,863,937, 129, 76,265,301,438,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937,

Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 6

265,301,129,751,863,937,694,742, 76,438, 129,265,301,751,694,742,863,937, 76,438, 129,265,301,694,742,751,863,937, 76,438, 76,129,265,301,438,694,742,751,863,937,

Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 7

Press any key to continue

运行速度比较:

直接排序 冒泡排序 直接插入 冒泡排序 快速排序

时间复杂度 O(n2),其中快速排序效率较高 其它的效率差不多 堆排序 归并排序

时间复杂度 (nlogn) ,平均效率都很高

心得体会:

此次试验了解了各种排序的基本思想,在分析各种排序的程序代码,对程序进行调试执行等等过程中,锻炼了自己分析数据结构的能力。此次试验然我知道排序的多种方法,也让我知道要编写好一个程序,首先要掌握其基本的思想及算法。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4