上傳人：宋***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：吳**（實名認(rèn)證）

IP屬地：重慶

IP屬地：重慶 上傳時間：2023-06-14 格式：DOC 頁數(shù)：16 大?。?55KB 積分：12 舉報 版權(quán)申訴

精品文檔數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾婵删庉嬁删庉嬀肺臋n可編輯《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告專業(yè)班級 姓名 學(xué)號 指導(dǎo)教師起止時間數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第1頁。課程設(shè)計：排序綜合一、任務(wù)描述利用隨機(jī)函數(shù)產(chǎn)生n個隨機(jī)整數(shù)（20000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。（1）至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。（2）統(tǒng)計每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。要求：根據(jù)以上任務(wù)說明，設(shè)計程序完成功能。二、問題分析1、功能分析分析設(shè)計課題的要求，要求編程實現(xiàn)以下功能：（1）隨機(jī)生成N個整數(shù)，存放到線性表中；（2）起泡排序并計算所需時間；（3）簡單選擇排序并計算時間；（4）希爾排序并計算時間；（5）直接插入排序并計算所需時間；（6）時間效率比較。2、數(shù)據(jù)對象分析存儲數(shù)據(jù)的線性表應(yīng)為順序存儲。三、數(shù)據(jù)結(jié)構(gòu)設(shè)計使用順序表實現(xiàn)，有關(guān)定義如下：typedefintStatus;typedefintKeyType;//設(shè)排序碼為整型量typedefintInfoType;typedefstruct{//定義被排序記錄結(jié)構(gòu)類型KeyTypekey;//排序碼I nfoTypeotherinfo;//其它數(shù)據(jù)項}RedType;typedefstruct{ RedType*r;//存儲帶排序記錄的順序表//r[0]作哨兵或緩沖區(qū) intlength;//順序表的長度}SqList;//定義順序表類型四、功能設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第2頁。（一）主控菜單設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第2頁。為實現(xiàn)通各種排序的功能，首先設(shè)計一個含有多個菜單項的主控菜單程序，然后再為這些菜單項配上相應(yīng)的功能。程序運(yùn)行后，給出5個菜單項的內(nèi)容和輸入提示，如下：起泡排序簡單選擇排序希爾排序4.直接插入排序0.退出系統(tǒng)（二）程序模塊結(jié)構(gòu)由課題要求可將程序劃分為以下幾個模塊（即實現(xiàn)程序功能所需的函數(shù)）：主控菜單項選擇函數(shù)menu()創(chuàng)建排序表函數(shù)InitList_Sq()起泡排序函數(shù)Bubble_sort()簡單選擇排序函數(shù)SelectSort()希爾排序函數(shù)ShellSort();對順序表L進(jìn)行直接插入排序函數(shù)Insertsort()（三）函數(shù)調(diào)用關(guān)系程序的主要結(jié)構(gòu)（函數(shù)調(diào)用關(guān)系）如下圖所示。其中main()是主函數(shù)，它負(fù)責(zé)調(diào)用各函數(shù)。進(jìn)行調(diào)用菜單函數(shù)menu()，根據(jù)選擇項0~4調(diào)用相應(yīng)的函數(shù)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第3頁。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第3頁。for循環(huán)實現(xiàn)重復(fù)選擇。其循環(huán)結(jié)構(gòu)如下：for(;;) { longstart,end; switch(menu()) { case1: printf("*起泡排序*\n"); start=clock();Bubble_sort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:起泡排序.txt","w"); if(fp==NULL)//打開文件失敗 { printf("打開文件失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case2: printf("*簡單選擇排序*\n"); start=clock(); SelectSort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:直接插入排序.txt","w"); if(fp==NULL)//打開文件失敗 { printf("簡單選擇排序!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case3: printf("*希爾排序*\n"); start=clock(); ShellSort(L,an,14); end=clock();數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第4頁。 fp=fopen("D:希爾排序.txt","w"); if(fp==NULL)//打開文件失敗 { printf("打開文件失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case4: printf("*直接插入排序*\n"); start=clock(); Insertsort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:直接插入排序.txt","w"); if(fp==NULL)//打開文件失敗 { printf("打開文件失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case0: printf("\t退出！\n"); return; } } （四）文件結(jié)構(gòu)1、sort.h：單鏈表相關(guān)的定義與聲明2、sort.cpp：單鏈表運(yùn)算的實現(xiàn)3、menu.h：主菜單函數(shù)的聲明4、menu.cpp：主菜單函數(shù)的實現(xiàn)5、mn.cpp：主函數(shù)（五）各函數(shù)的算法設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第5頁。1、InitList_Sq數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第5頁。算法原理：數(shù)組指針r指示線性表的基址，length指示線性表的當(dāng)前長度，將隨機(jī)生成的數(shù)賦給線性表，并生成相應(yīng)文件。流程圖： 開始申請內(nèi)存隨機(jī)生成30000個數(shù)字生成文件 Fp=NULL 將順序表打印到文件內(nèi)終止程序關(guān)閉文件結(jié)束 代碼描述：StatusInitList_Sq(SqList&L){//構(gòu)造一個線性表 FILE*fp; L.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType)); if(!L.r)exit(OVERFLOW);//存儲分配失敗 L.length=30001;//表長度為30001 srand((unsigned)time(NULL)); for(inti=1;i<=L.length;i++) L.r[i].key=rand()%30001+1; fp=fopen("D:構(gòu)造一個線性表.txt","w"); if(fp==NULL)//打開文件失敗 { printf("打開文件失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); returnOK;}//InitList_Sq算法的時間復(fù)雜度分析：O(n)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第6頁。2.Bubble_sort()算法原理：每趟不斷將記錄兩兩比較，若發(fā)現(xiàn)逆序，則交換兩個記錄，使排序碼較小的元素逐漸從后部移向前部（就象水底的氣泡一樣逐漸向上冒）。流程圖：代碼描述：voidBubble_sort(SqList&L){RedTypex; intn;n=L.length;//表長數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第7頁。for(inti=1;i<n;i++)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第7頁。{intflag=0;//進(jìn)入循環(huán)，清標(biāo)志for(intj=n-1;j>=i;j--)if(LT(L.r[j+1].key,L.r[j].key)){ flag=1;//有交換，置標(biāo)志x=L.r[j];//L.r[j]←→L.r[j+1]L.r[j]=L.r[j+1];L.r[j+1]=x;}if(flag==0)break;//若無交換則可結(jié)束冒泡排序}}算法的時間復(fù)雜度分析：O(n2) 3、SelectSort()算法原理：第1趟：從R[1]~R[n]中選取最小值,與R[1]交換;第2趟：從R[2]~R[n]中選取最小值,與R[2]交換;第i趟：從R[i]~R[n]中選取最小值,與R[i]交換; ………第n-1趟：從R[n－1]~R[n]中選取最小值,與R[n－1]交換.共通過n－1趟,得到一個按排序碼從小到大排列的有序序列數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第8頁。流程圖：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第9頁。代碼描述：voidSelectSort(SqList&L){//對順序表進(jìn)行簡單選擇排序 RedTypex;for(inti=1;i<L.length;++i){//在L.r[i..L.length]中選擇key最小的記錄intk=i;for(intj=i+1;j<=L.length;j++)if(LT(L.r[j].key,L.r[k].key))k=j; if(k!=i){ x=L.r[i];L.r[i]=L.r[j]; L.r[j]=x; }}}//SelectSort算法的時間復(fù)雜度分析：O(n2)4、ShellInsert()算法原理：（1）、分組、組內(nèi)直接插入排序；（2）、組數(shù)逐次減小；（3）、組數(shù)=1，結(jié)束。代碼描述：voidShellInsert(SqList&L,intdk){//一趟Shell排序，dk為步長 inti; for(i=dk+1;i<=L.length;i++) { if(LT(L.r[i].key,L.r[i-dk].key)){ L.r[0]=L.r[i]; intj; for(j=i-dk;(j>0)&&(LT(L.r[0].key,L.r[j].key));j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0];}}}數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第10頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第10頁。voidShellSort(SqList&L,intdlta[],intt){//Shell排序，dlta[]為增量序列，t為增量個數(shù) intk; for(k=0;k<t;k++)ShellInsert(L,dlta[k]);}//ShellSort算法的時間復(fù)雜度分析：O(n(㏒2n)2)Insertsort()算法原理：每步將一個待排序的對象，按其排序碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。在已形成的有序表中順序查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第11頁。流程圖：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第11頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第12頁。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序?qū)嶒瀳蟾嫒墓?6頁，當(dāng)前為第12頁。代碼描述：voidInsertsort(SqList&L)//對順序表L進(jìn)行直接插入排序{for(inti=2;i<=L.length;i++)if(LT(L.r[i].key,L.r[i-1].key))//需將L.r[i]插入有序表{L.r[0]=L.r[i];//復(fù)制為“哨兵”，暫存for(in