(完整版)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

“quicksort(sqlistl,intlow,inthigh)”“quicksort(sqlistl,intlow,inthigh)”：該函數(shù)實現(xiàn)的功能同上，只是原數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告前沿：排序是數(shù)據(jù)結(jié)構(gòu)中的一塊難點，也是重點。熟練的掌握各種各樣的排序算法是對每個編程人員的基本的要求。歷年的考研還是期末考中，排序都占了比較大的比重。二．程序?qū)崿F(xiàn)的功能：本程序采用了各種不同的方法對同一個輸入進行排序，且每一個元素其本身亦是一個結(jié)構(gòu)體，又可以進行擴充，使其可以存儲其他的相關(guān)的信息。在此我僅僅舉了結(jié)構(gòu)體本身只有一個元素的情況。a)采用的數(shù)據(jù)類型：為了討論的方便，本程序采用了復(fù)合型的結(jié)構(gòu)體類型，且才用了靜態(tài)線性表的形式，不能進行擴充，一旦空間開辟，就不能在擴充(注意)。具體如下：typedefstruct{//每個元素的類型定義，為了討論的方便本程序采用了單關(guān)鍵字；intkey;//但可以根據(jù)需要擴充，每個關(guān)鍵字令其為整型的；}redtype;typedefstruct{//開辟的數(shù)組，以上述類型的元素組成；redtype*r;//存入要輸入的元素的數(shù)組；intlength;〃數(shù)組的長度，shellsort中要用到；}sqlist;四．對部分頭文件和函數(shù)的說明：<conio.h>：改頭文件主要用來實現(xiàn)清屏，使得出的結(jié)果更清晰明白?！皊hellsort(sqlistl,intd)”：該函數(shù)主要實現(xiàn)希爾排序，使無序的數(shù)據(jù)排列成有序的序列理不同“heapadjust(sqlistl,ints,intm)”：該函數(shù)實現(xiàn)調(diào)整無序的數(shù)據(jù)序列使其成為大頂堆，即樹型結(jié)構(gòu)的最上面是值最大的，這樣進過一次的調(diào)整便得到了值最大的元素，即可進過多次的排序使一個無序的序列又序。“heapsort(sqlistl)”：該函數(shù)實現(xiàn)建立堆的過程。在其中間調(diào)用heapadjust實現(xiàn)最終建立大頂?shù)娜蝿?wù)?！皁esort(sqlistl,intn)”：該函數(shù)進行奇偶排序?qū)o序的數(shù)據(jù)排成有序的。五．核心程序算法：voidshellsort(sqlist&l,intd){//采用希爾排序，本程序中的l.r[0].key使暫存單元，非哨兵。d=l.length/2;while(d>0){for(i=d+1;i<=l.length;++i)if(l.r[i].key<l.r[i-d].key){l.r[0]=l.r[i];for(j=i-d;j>0&&l.r[0].key<l.r[j].key;j-=d)l.r[j+d]=l.r[j];l.r[j+d]=l.r[0];}d=d/2;}}基本思想：先取一個小于n的整數(shù)di作為第一個增量，把文件的全部記錄分成di個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dtvdt-l<???<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。該方法實質(zhì)上是一種分組插入方法voidquicksort(sqlist&l,intlow,inthigh){//快速排序if(lowvhigh));//Mr[low??high]進行一次快速排序{i=low;j=high;l.r[0]=l.r[i];do{while(ivj&&l?r[j]?key>l?r[0]?key)--j;if(ivj){l?r[i]=l?r[j];++i;}while(ivj&&l?r[i]?keyv=l?r[0]?key)++i;if(ivj){l?r[j]=l?r[i];--j;}}while(i!=j);l?r[i]=l?r[0];quicksortQJowj-l);對r[low??i-1]進行快速排序quicksort(l,i+1,high)；對r[I+1?high]進行快速排序}}基本思想設(shè)當(dāng)前待排序的無序區(qū)為r[low..high],利用分治法可將快速排序的基本思想描述為：①分解：在r[low??high]中任選一個記錄作為基準(Pivot),以此基準將當(dāng)前無序區(qū)劃分為左、右兩個較小的子區(qū)間r[low??pivotpos-1]和r[pivotpos+1??high],并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準記錄(不妨記為pivot)的關(guān)鍵字pivot?key,右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot?key,而基準記錄pivot則位于正確的位置(pivotpos)上,它無須參加后續(xù)的排序。注意：劃分的關(guān)鍵是要求出基準記錄所在的位置pivotpos。劃分的結(jié)果可以簡單地表示為(注pivot=r[pivotpos])r[low??pivotpos-l]?keysSR[pivotpos]?key^R[pivotpos+l??high]?keys其中l(wèi)ow<pivotpos<high。②求解：通過遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間R[low??pivotpos-1]和r[pivotpos+1??high]快速排序。③組合：因為當(dāng)"求解"步驟中的兩個遞歸調(diào)用結(jié)束時,其左、右兩個子區(qū)間已有序。對快速排序而言,"組合"步驟無須做什么,可看作是空操作。voidheapadjust(sqlist&l,ints,intm){///篩選法調(diào)整堆,使其成為大頂堆rc=l?r[s]?key;for(j=2*s;j<=m;j*=2){if(j<m&&l?r[j]?key<l?r[j+1]?key)j++;if(rc>l?r[j]?key)break;l?r[s]?key=l?r[j]?key;s=j;}l?r[s]?key=rc;}voidheapsort(sqlist&l){//建堆的過程for(i=l.length/2;i>0;i--)heapadjust(l,i,l.length);for(i=l.length;i>1;i--){t=l.r[1].key,l.r[1].key=l.r[i].key,l.r[i].key=t;heapadjust(l,1,i-1);}}基本思想：堆排序利用了大根堆堆頂記錄的關(guān)鍵字最大這一特征，使得在當(dāng)前無序區(qū)中選取最大關(guān)鍵字的記錄變得簡單。先將初始文件R[1??n]建成一個大根堆，此堆為初始的無序區(qū)。再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄r[n]交換，由此得到新的無序區(qū)r[1?.n-1]和有序區(qū)r[n]，且滿足r[1??n-1]?keysSr[n]?key。由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)r[1??n-1]調(diào)整為堆。然后再次將r[1??n-1]中關(guān)鍵字最大的記錄r[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)r[1??n-2]和有序區(qū)r[n-1??n]，且仍滿足關(guān)系r[1??n-2]?keys<r[n-1??n]?keys,同樣要將r[1??n-2]調(diào)整為堆。直到無序區(qū)只有一個元素為止。voidoesort(sqlist&l,intn){//奇偶交換排序change=1;標志變量，若其為零，即兩次更替的交換中都沒有交換數(shù)據(jù)，即排序結(jié)束while(change){change=0;for(i=1;ivn;i+=2)//堆奇數(shù)進行一趟排序if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}for(i=2;ivn;i+=2)//堆偶數(shù)進行一趟排序if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}}}算法過程：第一趟對序列中的所有奇數(shù)項i掃描，第二趟對序列中的所有偶數(shù)項i掃描。若ri]>r[i+1],則交換它們。第三趟有對所有的奇數(shù)項，第四趟對所有的偶數(shù)項，……如此反復(fù)，直到整個序列全部排好序為止。五．源程序：#include"stdio.h"#include"malloc.h"#include"conio.h"#definemaxsize5typedefstruct{intkey;}redtype;typedefstruct{redtype*r;intlength;}sqlist;voidshellsort(sqlistl,intd){inti,j;d=l.length/2;while(d>0){for(i=d+1;i<=l.length;++i)if(l.r[i].key<l.r[i-d].key){l.r[0]=l.r[i];for(j=i-d;j>0&&l.r[0].key<l.r[j].key;j-=d)l.r[j+d]=l.r[j];l.r[j+d]=l.r[0];}d=d/2;}}voidquicksort(sqlistl,intlow,inthigh){inti,j;if(low<high){i=low;j=high;l.r[0]=l.r[i];do{while(i<j&&l.r[j].key>l.r[0].key)if(i<j){l.r[i]=l.r[j];++i;}while(i<j&&l.r[i].key<=l.r[0].key)++i;if(i<j){l.r[j]=l.r[i];--j;}}while(i!=j);l.r[i]=l.r[0];quicksort(l,low,i-1);quicksort(l,i+1,high);}}voidheapadjust(sqlistl,ints,intm){intrc,j;rc=l.r[s].key;for(j=2*s;j<=m;j*=2){if(j<m&&l.r[j].key<l.r[j+1].key)j++;if(rc>l.r[j].key)break;l.r[s].key=l.r[j].key;s=j;}l.r[s].key=rc;};voidheapsort(sqlistl){inti,t;for(i=l.length/2;i>0;i--)heapadjust(l,i,l.length);for(i=l.length;i>1;i--){t=l.r[1].key,l.r[1].key=l.r[i].key,l.r[i].key=t;heapadjust(l,1,i-1);}}voidoesort(sqlistl,intn){intt,i,change;change=1;while(change){change=0;for(i=1;i<n;i+=2)if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}for(i=2;i<n;i+=2)if(l.r[i].key>l.r[i+1].key){t=l.r[i].key,l.r[i].key=l.r[i+1].key,l.r[i+1].key=t;change=1;}}}main(){inti,j,low,high,a[maxsize+1];charch;sqlistl;clrscr();l.r=(redtype*)malloc(maxsize*sizeof(int));if(!l.r)printf("overflow");l.length=0;printf("\n\npleaseinputfiveelements:\n\n");for(i=1;i<maxsize+1;i++){scanf("%d",&a[i]);l.length++;}getchar();do{for(j=1,i=1;j<maxsize+1;i++,j++)l.r[i].key=a[j];printf("\n\nWelcometousePanWeiFeng'sKeChenSheJi\n\n");printf("s:shellsort\tq:quicksort\n\n");printf("h:heapsort\te:oesort\n\n");printf("o:quit\n\n");printf("pleaseinputtheway:");ch=getchar();clrscr();printf("\n\ntheorignalarray:");for(i=1;i<maxsize+1;i++)printf("%d",l.r[i].key);printf("\n\n");/*printf("pleaseinputtheway:");ch=getchar();*/getchar();switch(ch){case's':shellsort(l,l.length);printf("\n\ntheoderedfor(i=1;i<maxsize+1;i++)printf("%d",l.r[i].key);printf("\n\n");break;case'q':low=1;high=l.length;quicksort(l,low,high);printf("\n\ntheoderedfor(i=1;i<maxsize+1;i++)printf("%d",l.r[i].key);printf("\n\n");break;case'h':heapsort(l);printf("\n\ntheoderedfor(i=1;i<maxsize+1;i++)printf("%d",l.r[i].key);printf("\n\n");break;case'e':oesort(l,l.length);printf("\n\ntheoderedarry:");arry:");arry:");arry:");for(i=1;i<maxsize+1;i++)printf("%d",l.r[i].key);printf("\n\n");break;case'o':exit(0);default:printf("\n\nerror!writeagain!\n");}}while(1);}六．程序運行結(jié)果：當(dāng)你編譯連接通過后，運行。pleaseinputfiveelements:64583回車后出現(xiàn)大括號內(nèi)的部分{WelcometousePanWeiFeng'sKeChenSheJis:shellsortq:quicksorth:heapsorte:oesorto:quitpleaseinputtheway:}s輸入s回車后出現(xiàn)大括號內(nèi)的部分{theorignalarray:64583theoderedarray:34568WelcometousePanWeiFeng'sKeChenSheJis:shellsortq:quicksorth:heapsorte:oesorto:quitpleaseinputtheway:}q輸入q回車后出現(xiàn)大括號內(nèi)的部分{theorignalarray:64583theo