數(shù)據(jù)結(jié)構(gòu)試驗(yàn)哈希表優(yōu)質(zhì)資料

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)哈希表優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）

第10章實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)試驗(yàn)哈希表優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）實(shí)驗(yàn)名稱：考試日程安排與成績統(tǒng)計(jì)實(shí)驗(yàn)類型：綜合性性實(shí)驗(yàn)班級：20210611學(xué)號：2021061118姓名：郭鑫問題描述=1\*GB3①問題描述現(xiàn)要安排考試的考表（即考試日程表），假設(shè)共有10個班的學(xué)生，要安排10門必修課程的考試，必修課程是以班級來確定的，每個班各有3門必修課，因此各班的考試科目是不相同的；安排考表的原則是：相同課程采用統(tǒng)一的試卷，因此同一門課程的考試必須在相同時間進(jìn)行，同一個班所修的科目必須安排在不同的時間進(jìn)行考試，以避免考試時間的沖突。并要求全部考試的日程盡可能短。要求對考試結(jié)果做統(tǒng)計(jì)和排序。假設(shè)分別以編號0,1,2,3,4,5,6,7,8,9代表10門要考試的課程，以B1，B2，B3，B4，B5，B6，B7，B8，B9，B10代表10個班，每個人的信息包括學(xué)號、姓名、班級、各門考試課程成績、三門課程總成績，每個班的學(xué)生人數(shù)自行設(shè)定。要求設(shè)計(jì)一個簡單的考試成績的查詢統(tǒng)計(jì)系統(tǒng)實(shí)現(xiàn)以下功能：顯示學(xué)生考試情況-按考試總分從高到底輸出全體學(xué)生的信息。-按照從B1到B10的班級順序，分班級按照考試總分從高到底的順序輸出各班學(xué)生的信息。-輸出指定班的學(xué)生考試成績信息。統(tǒng)計(jì)學(xué)生考試成績-按總成績統(tǒng)計(jì)出90分以上、80~89分、70~79分、60~69分、60分以下各分?jǐn)?shù)段的人數(shù)，并按總分從高到低分段輸出。-根據(jù)指定的某們課程的成績，統(tǒng)計(jì)出上述各分?jǐn)?shù)段的人數(shù)，并按分?jǐn)?shù)從高到低分段輸出。-統(tǒng)計(jì)并輸出指定班級中總成績或某一門課成績的各分?jǐn)?shù)段人數(shù)和每個人具體的信息。查找學(xué)生成績-查找總分或某一門課程成績的指定分?jǐn)?shù)段的人數(shù)及學(xué)生的詳細(xì)信息。-查找指定班級中總分或某一門課程成績屬于某分?jǐn)?shù)段的學(xué)生詳細(xì)信息。-查找指定學(xué)生（例如給定學(xué)號）的具體信息，包括：姓名、班級、各科分?jǐn)?shù)、總分?jǐn)?shù)等。=2\*GB3②求解方法說明考試日程安排問題。該問題實(shí)際上是對若干元素進(jìn)行子集劃分的問題，要求所劃分的每個子集中的元素沒有“考試沖突”關(guān)系。假設(shè)各個班的考試課程分別為：(1,4,8),(1,3,7),(8,2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,9),(2,9,7),(6,0,3),(5,6,9)。根據(jù)題中考試安排原則，各個班要進(jìn)行的考試課程可以抽象為“考試沖突關(guān)系”，歸納各個班的考試課程可以整理得到考試沖突關(guān)系：R={(1,4),(1,8),(4,8),(1,3),(1,7),(3,7),(8,2),(2,4),(1,0),(1,5),(0,5),(2,6),(2,9),(6,9),(3,0),(0,8),(3,8),(4,5),(5,9),(4,5),(2,7),(9,7),(6,0),(6,3),(5,6)}。顯然，“考試沖突”關(guān)系R的每個有序?qū)χ械膬砷T課程不能安排在同一時間考試，據(jù)此可以將10門課劃分為若干個考試時間沒有沖突的子集，并且使考場的場次盡量少，使得整個考試時間盡可能短。上述子集劃分問題可以用對集合中的元素逐個“篩選”的辦法來解決。首先將集合的第1個元素置為第1個子集，再逐個檢查集合中的其余元素是否和第1個元素有考試沖突，若不存在考試沖突，則將其加入到第1個子集中，繼續(xù)檢查集合中的其余元素，凡是不與第1個子集中的元素沖突的元素都逐個將其加入到其中；接著按同樣的方法“篩選”出若干沒有考試沖突的元素構(gòu)成第2個子集，…，該過程一直到集合中的全部元素都分到某個子集中結(jié)束。得到的每一個子集中的課程就是可以安排在同一時間考試的課程。不同子集的課程則要安排在不沖突的時間考試?？荚嚪?jǐn)?shù)的統(tǒng)計(jì)與排序考試成績輸出每個學(xué)生的信息記錄數(shù)據(jù)項(xiàng)應(yīng)包括：學(xué)號、姓名、班級、課程1、課程2、…、課程10、總成績。按總分高低輸出所有學(xué)生信息時，應(yīng)該以總成績?yōu)殛P(guān)鍵字從高分到低分對所有的學(xué)生記錄進(jìn)行排序，排序方法自行選定，然后依次輸出各個記錄。按照班級順序和總分高低輸出各班學(xué)生信息時，要對學(xué)生記錄進(jìn)行多關(guān)鍵字排序，首先以總成績?yōu)殛P(guān)鍵字從高分到低分對所有的學(xué)生記錄進(jìn)行排序，然后再以班號為關(guān)鍵字對全部學(xué)生記錄排序，再輸出結(jié)果。統(tǒng)計(jì)成績統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)，要求由用戶輸入，具體要求可以有：按照總成績統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)，并輸出各分?jǐn)?shù)段的學(xué)生記錄，即在統(tǒng)計(jì)一個分?jǐn)?shù)段的人數(shù)過程中，要輸出滿足查找條件的學(xué)生記錄，再輸出統(tǒng)計(jì)的結(jié)果。指定某一門課程，統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)并輸出各分?jǐn)?shù)段的學(xué)生記錄。對指定班級中總成績或指定課程成績做各分?jǐn)?shù)段人數(shù)的統(tǒng)計(jì)，也要輸出各分?jǐn)?shù)段的學(xué)生記錄。查找成績查找要求由用戶輸入，可以輸入以下條件：查找指定分?jǐn)?shù)項(xiàng)（總分或某一門課程）的某分?jǐn)?shù)段的學(xué)生信息，輸出查找結(jié)果。查找指定班級、指定分?jǐn)?shù)項(xiàng)的某分?jǐn)?shù)段的學(xué)生信息，輸出查找結(jié)果。查找指定學(xué)生（給定學(xué)號）的具體信息，輸出查找結(jié)果。③算法提示考試場次的劃分——“無考試沖突”子集劃分的算法思路。為了把10門課程劃分為時間上不沖突的若干場考試，可以利用一個循環(huán)隊(duì)列來實(shí)現(xiàn)求解方法中說明的“篩選”過程。首先定義一個循環(huán)隊(duì)列，再把10門課程的編號從小到大依次加入到循環(huán)隊(duì)列中，然后重復(fù)下列步驟：隊(duì)頭元素出隊(duì)并作為當(dāng)前子集的第1個元素。隊(duì)頭元素繼續(xù)依次出隊(duì)，每出隊(duì)一個隊(duì)頭元素都要檢查與當(dāng)前子集中的元素是否有“考試沖突”；如果沒有沖突，則將其加入到當(dāng)前子集中，否則將其重新加入隊(duì)列中，等待以后加入新子集的機(jī)會。比較剛出隊(duì)元素與前一出隊(duì)元素編號。因?yàn)殛?duì)列中原有的元素是以編號從小到大的順序排列的，重新入隊(duì)的元素編號一定小于它的前一元素，所以一旦發(fā)現(xiàn)目前出隊(duì)的元素編號小于前一個出隊(duì)的元素，就可以斷定當(dāng)前的“考試沖突”子集已經(jīng)構(gòu)建完，隊(duì)列中剩余元素應(yīng)該構(gòu)建新的子集。為此，在當(dāng)前的隊(duì)頭元素出隊(duì)前，要先記下剛剛出隊(duì)的元素，以便判斷當(dāng)前出隊(duì)的元素是否要開始構(gòu)建一個新子集。重復(fù)上述步驟一直到隊(duì)列空，則“無考試沖突”子集劃分完成。由上述算法思路可以知道，“無考試沖突”子集的劃分過程是一個循環(huán)的執(zhí)行過程，循環(huán)中的主要操作是元素出隊(duì)和判斷的操作。判斷操作包括出隊(duì)元素是否可以加入當(dāng)前子集和是否要開始構(gòu)建一個新子集兩個方面，對后一個判斷如前所述，通過比較出隊(duì)元素與前一個出隊(duì)元素編號大小可以確定。為了判斷出隊(duì)元素與當(dāng)前子集中的元素是否有“考試沖突”，可以定義一個二維數(shù)組conf[n][n]來表示課程的考試沖突關(guān)系矩陣，矩陣中各元素的值根據(jù)以下規(guī)則確定，若編號為i的課程和編號為j的課程有考試沖突，則置conf[i][j]=1，否則置conf[i][j]=0，考試沖突關(guān)系矩陣如圖1所示。0101011010100111011000001011111100001110011001001111001010011011010001011100000111111000000010111100圖1考試沖突關(guān)系矩陣?yán)谩翱荚嚊_突”關(guān)系矩陣可以檢查出隊(duì)元素i是否與當(dāng)前子集中的元素有考試沖突，其方法是：當(dāng)課程號為j1，j2，…，jk的元素已經(jīng)在當(dāng)前子集S中，要判斷目前出隊(duì)的元素i是否可以加入子集S，只要檢查“考試沖突”關(guān)系矩陣中第i行的元素conf[i][j1]，conf[i][j2]，…conf[i][jk]的值是否為0即可。如果這些元素的值都為0，表示課程i與子集中的課程沒有考試沖突，可以加入其中，否則說明表示課程i與子集中的某些課程有考試沖突，它不能加入該子集中。為了減少在二維數(shù)組conf中查找元素的操作，可以定義一個一維數(shù)組clash[n]來方便出隊(duì)元素i是否要加入當(dāng)前子集的判斷，數(shù)組clash[n]用于記錄出隊(duì)元素i與當(dāng)前子集中的元素是否存在考試沖突的信息。每當(dāng)開始構(gòu)建一個新子集時，先將數(shù)組clash[n]的各元素初始化為0，當(dāng)有編號為i的課程加入子集時，將“考試沖突”關(guān)系矩陣中第i行的各列的值與數(shù)組clash的各對應(yīng)元素的值相加，因而使得數(shù)組clash中和編號為i的元素有考試沖突的相應(yīng)元素的值不再是0，當(dāng)下一個隊(duì)頭元素j出隊(duì)時，只要檢查數(shù)組clash中第j個元素的值是否為0，就可以判斷其是否與當(dāng)前子集中的元素有考試沖突；若數(shù)組clash中第j個元素的值不為0，則說明元素j與當(dāng)前子集中元素存在考試沖突，應(yīng)將其重新加入隊(duì)列；若數(shù)組clash中第j各元素的值為0，則說明它與當(dāng)前子集中元素不存在考試沖突，應(yīng)該將它加入當(dāng)前子集中，同時要將“考試沖突”關(guān)系矩陣中第j行的各列的值與數(shù)組clash的各對應(yīng)元素的值相加，這個過程一直到隊(duì)列空，則劃分無考試沖突子集完成。劃分結(jié)果可以用一個二維數(shù)組來記錄各子集中的元素的方式來表示，也可以用一個一維數(shù)組來記錄每個元素其所屬的子集號的方式來表示。上述算法的思路可以描述如下：建立表示課程考試沖突關(guān)系矩陣的二維數(shù)組conf[n][n]；定義用于檢查當(dāng)前子集的課程考試沖突信息的數(shù)組clash[n]；定義用于記錄子集劃分結(jié)果的數(shù)組result[n]；pre=n;//pre用于記錄前一個出隊(duì)元素的編號，初始值置為n以新建第1個子集k=0；//k用于記錄子集序號0~9(課程編號)依次入隊(duì)；while（隊(duì)列不空）{隊(duì)頭元素i出隊(duì)；if(i<pre)//剛出隊(duì)元素小于前一個出隊(duì)元素，生成一個新子集{k++;數(shù)組clash初始化；}if(i可以加入當(dāng)前子集)//如果剛出隊(duì)元素與當(dāng)前子集中的元素?zé)o考試沖突，將其加入當(dāng)前子集{將i加入當(dāng)前子集，記錄i所屬子集的序號；將conf數(shù)組第i行各列的值與clash數(shù)組對應(yīng)列的值相加并記入clash中；}else//如果剛出隊(duì)元素與當(dāng)前子集中的元素有考試沖突，將其重新入隊(duì)將i重新加入隊(duì)列；pre=i;}考試成績統(tǒng)計(jì)和排序的實(shí)現(xiàn)按總成績或按某一門課的成績統(tǒng)計(jì)并輸出人數(shù)時，應(yīng)該使各分?jǐn)?shù)段的人數(shù)和每個學(xué)生的信息清晰的分開。對全體學(xué)生或?qū)δ骋粋€班的學(xué)生的成績進(jìn)行排序時，排序方法可以任意選擇。就本實(shí)驗(yàn)問題而言，因表長不大采用簡單的排序方法就可以達(dá)到目的，但為了比較各種常用排序方法性能和適用場合，還可以采用不同的排序方法實(shí)現(xiàn)排序。對多關(guān)鍵字的排序要求，要注意排序方法的穩(wěn)定性問題。例如，在按總成績從高分到低分對全體學(xué)生進(jìn)行排序后，再按班級從高分到低分進(jìn)行排序，此時要求分班級排序時采用的排序方法其動態(tài)性能必須是穩(wěn)定的。同樣地，如果在按總成績從高分到低分排序的基礎(chǔ)上，再要求按某一門課的成績從高分到低分排序，也要求第2層排序一定注意選擇動態(tài)性能穩(wěn)定的排序方法。在實(shí)現(xiàn)查找或排序功能時，其查找或排序的依據(jù)（指定項(xiàng)）和目標(biāo)（輸出結(jié)果）通過提示用戶輸入來確定。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)typedefintKeyType;typedefcharInfoType[10];typedefstruct/*記錄類型*/{KeyTypekey;/*關(guān)鍵字項(xiàng)*/InfoTypedata;/*其他數(shù)據(jù)項(xiàng),類型為InfoType*/}RecType算法設(shè)計(jì)#include<iostream>usingnamespacestd;#defineMAXE20/*線性表中最多元素個數(shù)*/typedefintKeyType;typedefcharInfoType[10];typedefstruct/*記錄類型*/{KeyTypekey;/*關(guān)鍵字項(xiàng)*/InfoTypedata;/*其他數(shù)據(jù)項(xiàng),類型為InfoType*/}RecType;voidSelectSort(RecTypeR[],intn)/*直接選擇排序算法*/{inti,j,k,l;RecTypetemp;for(i=0;i<n-1;i++)/*做第i趟排序*/{k=i;for(j=i+1;j<n;j++)/*在當(dāng)前無序區(qū)R[i..n-1]中選key最小的R[k]*/if(R[j].key<R[k].key)k=j;/*k記下目前找到的最小關(guān)鍵字所在的位置*/if(k!=i)/*交換R[i]和R[k]*/{temp=R[i];R[i]=R[k];R[k]=temp;}printf("i=%d",i);/*輸出每一趟的排序結(jié)果*/for(l=0;l<n;l++)printf("%2d",R[l].key);printf("\n");}}intmain(){inti,k,n=10,m=5;KeyTypea[]={6,8,7,9,0,1,3,2,4,5};RecTypeR[MAXE];for(i=0;i<n;i++)R[i].key=a[i];printf("\n");printf("初始關(guān)鍵字");/*輸出初始關(guān)鍵字序列*/for(k=0;k<n;k++)printf("%2d",R[k].key);printf("\n");SelectSort(R,n);printf("最后結(jié)果");/*輸出初始關(guān)鍵字序列*/for(k=0;k<n;k++)printf("%2d",R[k].key);printf("\n\n");system("pause");}4.界面設(shè)計(jì)程序包含有多個功能，所以，采用菜單，以方便用戶進(jìn)行功能選擇。菜單如下：1：1：直接插入排序算法驗(yàn)證2：快速排序算法驗(yàn)證。3:直接選擇排序算法驗(yàn)證。4:退出運(yùn)行、測試與分析1）直接插入排序算法驗(yàn)證快速排序算法驗(yàn)證。3）直接選擇排序算法驗(yàn)證。實(shí)驗(yàn)收獲及思考這次實(shí)驗(yàn)我對選擇拍循序，插入排序，快速排序有了更好的理解，以及時間復(fù)雜度的問題分析，通過這次實(shí)驗(yàn)，我對排序的內(nèi)容有了更深入的了解。編程技術(shù)有了很大的提高1．實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康?通過編程，學(xué)習(xí)、實(shí)現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。理解算法的主要思想及流程。實(shí)驗(yàn)內(nèi)容：使用鏈表實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、冒泡排序（改進(jìn)型冒泡排序）3、快速排序4、簡單選擇排序5、堆排序（小根堆）要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動）。3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時間復(fù)雜度編寫測試main()函數(shù)測試線性表的正確性代碼要求：1、必須要有異常處理，比如刪除空鏈表時需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說明該函數(shù)的功能關(guān)鍵代碼應(yīng)說明其功能3、遞歸程序注意調(diào)用的過程，防止棧溢出2.程序分析通過排序算法將單鏈表中的數(shù)據(jù)進(jìn)行由小至大（正向排序）2.1存儲結(jié)構(gòu)……單鏈表存儲數(shù)據(jù)：……structnode{intdata;node*next;};單鏈表定義如下：classLinkList{private:node*front;public: LinkList(inta[],intn);//構(gòu)造 ~LinkList();voidinsert(node*p,node*s);//插入voidturn(node*p,node*s);//交換數(shù)據(jù)voidprint();//輸出voidInsertSort();//插入排序voidBubbleSort();//pos冒泡voidQSort();//快速排序voidSelectSort();//簡單選擇排序node*Get(inti);//查找位置為i的結(jié)點(diǎn)voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的遞歸主體voidheapsort(intn);//堆排序算法};關(guān)鍵算法分析：1.直接插入排序：首先將待排序數(shù)據(jù)建立一個帶頭結(jié)點(diǎn)的單鏈表。將單鏈表劃分為有序區(qū)和無序區(qū)，有序區(qū)只包含一個元素節(jié)點(diǎn)，依次取無序區(qū)中的每一個結(jié)點(diǎn)，在有序區(qū)中查找待插入結(jié)點(diǎn)的插入位置，然后把該結(jié)點(diǎn)從單鏈表中刪除，再插入到相應(yīng)位置。分析上述排序過程，需設(shè)一個工作指針p->next在無序區(qū)中指向待插入的結(jié)點(diǎn)，在找到插入位置后，將結(jié)點(diǎn)p->next插在結(jié)點(diǎn)s和p之間。voidLinkList::InsertSort()//將第一個元素定為初始有序區(qū)元素，由第二個元素開始依次比較{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*p=front->next;//要插入的節(jié)點(diǎn)的前驅(qū)while(p->next) {node*s=front;//充分利用帶頭結(jié)點(diǎn)的單鏈表while(1) { comparef++;if(p->next->data<s->next->data)//[P后繼]比[S后繼]小則插入 { insert(p,s);break; } s=s->next;if(s==p)//若一趟比較結(jié)束，且不需要插入 { p=p->next;break; } } } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}2.快速排序：主要通過軸值將數(shù)據(jù)從兩端向中間進(jìn)行比較，交換以實(shí)現(xiàn)排序。通過遞歸的調(diào)用來實(shí)現(xiàn)整個鏈表數(shù)據(jù)的排序。代碼中選用了第一個元素作為軸值。一趟排序的代碼：voidLinkList::QSZ(node*b,node*e){if(b->next==e||b==e)//排序完成return;node*qianqu=b;//軸點(diǎn)前驅(qū)node*p=qianqu->next;while(p!=e&&p!=e->next) { comparef++;if(qianqu->next->data>p->next->data)//元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 {if(p->next==e)//若該元素為e，則將其前驅(qū)設(shè)為ee=p; insert(p,qianqu); qianqu=qianqu->next; }elsep=p->next; } QSZ(b,qianqu);//繼續(xù)處理軸點(diǎn)左側(cè)鏈表 QSZ(qianqu->next,e);//繼續(xù)處理軸點(diǎn)右側(cè)鏈表}整個快速排序的實(shí)現(xiàn):voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*e=front;while(e->next) { e=e->next; } QSZ(front,e); QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}3.改進(jìn)版的冒泡排序：通過設(shè)置pos來記錄無序邊界的位置以減少比較次數(shù)。將數(shù)據(jù)從前向后兩兩比較，遇到順序不對是直接交換兩數(shù)據(jù)的值。每交換一次movef+3；voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*p=front->next;while(p->next)//排序查找無序邊界 { comparef++;if(p->data>p->next->data) turn(p,p->next); p=p->next; }node*pos=p;p=front->next;while(pos!=front->next) {node*bound=pos; pos=front->next;while(p->next!=bound) { comparef++;if(p->data>p->next->data) { turn(p,p->next);pos=p->next; } p=p->next; } p=front->next; } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}4.選擇排序：每趟排序再待排序的序列中選擇關(guān)鍵碼最小的元素，順序添加至已排好的有序序列最后，知道全部記錄排序完畢。voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*s=front;while(s->next->next) {node*p=s;node*index=p;while(p->next) { comparef++;if(p->next->data<index->next->data) index=p; p=p->next; } insert(index,s); s=s->next; } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}5.堆排序：利用前一趟比較的結(jié)果來減少比較次數(shù)，提高整體的效率。其中通過鏈表儲存了一棵樹。選擇使用小根堆進(jìn)行排序。voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m) { comparef++;if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; } }}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)for(inti=n/2;i>=1;i--) sift(i,n);for(inti=1;i<n;i++) { turn(Get(1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}其中堆排序中需要知道孩子節(jié)點(diǎn)和父親節(jié)點(diǎn)處的值，故設(shè)置了函數(shù)獲取i出的指針。node*LinkList::Get(inti){node*p=front->next;intj=1;while(j!=i&&p) { p=p->next; j++; }if(!p)throw"查找位置非法";elsereturnp;};6.輸出結(jié)果的函數(shù)：voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){a.print(); comparef=0;movef=0;a.InsertSort(); cout<<"排序結(jié)果：";a.print(); cout<<"1.插入排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;b.BubbleSort(); cout<<"2.改進(jìn)型冒泡排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;c.QSort(); cout<<"3.快速排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;d.SelectSort(); cout<<"4.簡單選擇排序法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;e.heapsort(10); cout<<"5.堆排序算法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl;}7.統(tǒng)計(jì)時間的函數(shù)：#include<windows.h>{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*p=front->next;//要插入的節(jié)點(diǎn)的前驅(qū)QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;};2.3其他算法的時間復(fù)雜度：排序方法隨機(jī)序列的平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)改進(jìn)版冒泡排序O(n2)O(n)O(n2)O(1)選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)3.程序運(yùn)行結(jié)果1.流程圖開始：開始初始化正序鏈表，調(diào)用初始化正序鏈表，調(diào)用各類排序，并輸出運(yùn)行結(jié)果初始化逆序鏈表初始化逆序鏈表，調(diào)用各類排序，并輸出運(yùn)行結(jié)果初始化順序隨機(jī)的鏈表，調(diào)用初始化順序隨機(jī)的鏈表，調(diào)用各類排序，并輸出運(yùn)行結(jié)果結(jié)束結(jié)束2.測試條件：如果需要對不同的正序，逆序隨機(jī)序列進(jìn)行排序，則需要在main函數(shù)中進(jìn)行初始化設(shè)置。3.測試結(jié)論：4.總結(jié)通過這次實(shí)驗(yàn)我再次復(fù)習(xí)了鏈表的建立及相應(yīng)的操作，對各類排序算法的實(shí)現(xiàn)也有了新的理解，在調(diào)試過程中出現(xiàn)了許多問題也花費(fèi)了很多時間和精力去逐步解決，最后程序運(yùn)行成功的瞬間真的很開心。問題一：直接插入排序中若是使用從后向前比較插入的話（即書上的辦法）難以找到該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，不方便進(jìn)行操作，所以最后采用了從前向后進(jìn)行比較。voidLinkList::InsertSort()//將第一個元素定為初始有序區(qū)元素，由第二個元素開始依次比較{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*p=front->next;//要插入的節(jié)點(diǎn)的前驅(qū)while(p->next) {node*s=front;//充分利用帶頭結(jié)點(diǎn)的單鏈表while(1) { comparef++;if(p->next->data<s->next->data)//[P后繼]比[S后繼]小則插入 { insert(p,s);break; } s=s->next;if(s==p)//若一趟比較結(jié)束，且不需要插入 { p=p->next;break; } } }問題二：如何將書上以數(shù)組方式儲存的樹轉(zhuǎn)化為鏈表儲存并進(jìn)行操作？原本打算建立一顆完全二叉樹儲存相應(yīng)數(shù)據(jù)再進(jìn)行排序，但是那樣的話需要新設(shè)置結(jié)點(diǎn)存左孩子右孩子，比較麻煩容易出錯，所以選擇了利用Get(inti)函數(shù)將篩選結(jié)點(diǎn)的位置獲得。與書上代碼相比修改如下：if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; }問題三：時間如何精確至微秒？需要調(diào)用函數(shù)，這個問題是上網(wǎng)查找解決的。總結(jié)：解決了以上的問題后代碼就比較完整了，可是還是希望通過日后的學(xué)習(xí)能將算法編寫得更完善，靈活，簡捷。附錄：完整代碼如下：#include"lianbiaopaixu.h"#include<windows.h>usingnamespacestd;voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,10};LinkListzhengxu1(a,10),zhengxu2(a,10),zhengxu3(a,10),zhengxu4(a,10),zhengxu5(a,10); cout<<"正序數(shù)列："; tell(zhengxu1,zhengxu2,zhengxu3,zhengxu4,zhengxu5);intb[10]={10,9,8,7,6,5,4,3,2,1};LinkListnixu1(b,10),nixu2(b,10),nixu3(b,10),nixu4(b,10),nixu5(b,10); cout<<"\n逆序數(shù)列："; tell(nixu1,nixu2,nixu3,nixu4,nixu5);intc[10]={2,6,10,5,8,3,9,1,4,7};LinkListsuiji1(c,10),suiji2(c,10),suiji3(c,10),suiji4(c,10),suiji5(c,10); cout<<"\n隨機(jī)數(shù)列："; tell(suiji1,suiji2,suiji3,suiji4,suiji5);}#include<iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<iomanip>#include<windows.h>usingnamespacestd;intcomparef;intmovef;structnode{intdata;node*next;};classLinkList{private:node*front;public: LinkList(inta[],intn);//構(gòu)造 ~LinkList();voidinsert(node*p,node*s);//插入voidturn(node*p,node*s);//交換數(shù)據(jù)voidprint();//輸出voidInsertSort();//插入排序voidBubbleSort();//pos冒泡voidQSort();//快速排序voidSelectSort();//簡單選擇排序node*Get(inti);//查找位置為i的結(jié)點(diǎn)voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的遞歸主體voidheapsort(intn);//堆排序算法};LinkList::LinkList(inta[],intn){ front=newnode; front->next=NULL;for(inti=n-1;i>=0;i--) {node*p=newnode;//新節(jié)點(diǎn) p->data=a[i]; p->next=front->next; front->next=p;//頭插法建立單鏈表，最先加入的被不斷后移 }}LinkList::~LinkList(){node*q=front;while(q) { front=q; q=q->next;deletefront; }}voidLinkList::insert(node*p,node*s)//將p->next插入s和s->next之間{node*q=p->next;p->next=p->next->next; q->next=s->next;s->next=q; movef++;}voidLinkList::turn(node*p,node*s)//交換數(shù)據(jù){inttemp=p->data;p->data=s->data;s->data=temp; movef+=3;}voidLinkList::print()//輸出需要顯示的內(nèi)容{node*p=front->next;while(p) { cout<<p->data<<''; p=p->next; } cout<<endl;}voidLinkList::InsertSort()//將第一個元素定為初始有序區(qū)元素，由第二個元素開始依次比較{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*p=front->next;//要插入的節(jié)點(diǎn)的前驅(qū)while(p->next) {node*s=front;//充分利用帶頭結(jié)點(diǎn)的單鏈表while(1) { comparef++;if(p->next->data<s->next->data)//[P后繼]比[S后繼]小則插入 { insert(p,s);break; } s=s->next;if(s==p)//若一趟比較結(jié)束，且不需要插入 { p=p->next;break; } } } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}voidLinkList::QSZ(node*b,node*e){if(b->next==e||b==e)//排序完成return;node*qianqu=b;//軸點(diǎn)前驅(qū)node*p=qianqu->next;while(p!=e&&p!=e->next) { comparef++;if(qianqu->next->data>p->next->data)//元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 {if(p->next==e)//若該元素為e，則將其前驅(qū)設(shè)為ee=p; insert(p,qianqu); qianqu=qianqu->next; }elsep=p->next; } QSZ(b,qianqu);//繼續(xù)處理軸點(diǎn)左側(cè)鏈表 QSZ(qianqu->next,e);//繼續(xù)處理軸點(diǎn)右側(cè)鏈表}voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*e=front;while(e->next) { e=e->next; } QSZ(front,e); QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*p=front->next;while(p->next)//排序查找無序邊界 { comparef++;if(p->data>p->next->data) turn(p,p->next); p=p->next; }node*pos=p;p=front->next;while(pos!=front->next) {node*bound=pos; pos=front->next;while(p->next!=bound) { comparef++;if(p->data>p->next->data) { turn(p,p->next);pos=p->next; } p=p->next; } p=front->next; } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)node*s=front;while(s->next->next) {node*p=s;node*index=p;while(p->next) { comparef++;if(p->next->data<index->next->data) index=p; p=p->next; } insert(index,s); s=s->next; } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}node*LinkList::Get(inti){node*p=front->next;intj=1;while(j!=i&&p) { p=p->next; j++; }if(!p)throw"查找位置非法";elsereturnp;}voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m) { comparef++;if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; } }}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動次數(shù) QueryPerformanceCounter(&t1);//測前跳動次數(shù)for(inti=n/2;i>=1;i--) sift(i,n);for(inti=1;i<n;i++) { turn(Get(1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//測后跳動次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時間差秒 cout<<"操作時間為："<<d<<endl;}voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){a.print(); comparef=0;movef=0;a.InsertSort(); cout<<"排序結(jié)果：";a.print(); cout<<"1.插入排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;b.BubbleSort(); cout<<"2.改進(jìn)型冒泡排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;c.QSort(); cout<<"3.快速排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;d.SelectSort(); cout<<"4.簡單選擇排序法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;e.heapsort(10); cout<<"5.堆排序算法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl;}數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告-順序表的創(chuàng)建、遍歷及有序合并操作二、實(shí)驗(yàn)內(nèi)容與步驟實(shí)現(xiàn)順序表的創(chuàng)建、遍歷及有序合并操作，基本數(shù)據(jù)結(jié)構(gòu)定義如下：typedefintElemType;#defineMAXSIZE100#defineFALSE0#defineTRUE1typedefstruct{ElemTypedata[MAXSIZE];intlength;}seqlist;創(chuàng)建順序表，遍歷順序表#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100#defineIcreament20#defineFALSE0#defineTRUE1typedefintElemType;//用戶自定義數(shù)據(jù)元素類型//順序表結(jié)構(gòu)體的定義typedefstruct{ElemType*elem;//順序表的基地址intlength;//順序表的當(dāng)前長度intlistsize;//預(yù)設(shè)空間容量}SqList;//線性表的順序存儲結(jié)構(gòu)SqList*InitList()//創(chuàng)建空的順序表{SqList*L=(SqList*)malloc(sizeof(SqList));//定義順序表Lif(!L){printf("空間劃分失敗，程序退出\n");returnNULL;}L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!L->elem){printf("空間劃分失敗，程序退出\n");returnNULL;}L->length=0;L->listsize=MAXSIZE;returnL;}intCreateList(SqList*L)//創(chuàng)建順序表（非空）{intnumber;//順序表中元素的個數(shù)inti;//循環(huán)變量printf("請輸入順序表中元素的個數(shù)：");scanf("%d",&number);if(number>MAXSIZE)//一定要判斷輸入的個數(shù)是否大于順序表的最大長度{printf("輸入個數(shù)大于順序表的長度\n");return0;}for(i=0;i<number;i++){printf("輸入第%d個數(shù):",i+1);scanf("%d",L->elem+i);//L->elem+i：每次的輸入都保存在順序表元素中的下一個地址，而不是一直放在元素的首地址}//給順序表中每個數(shù)據(jù)元素賦值L->length=number;//當(dāng)前順序表的長度return1;}voidprint(SqList*L)//遍歷順序表{inti; printf("\n開始遍歷順序表\n");