數(shù)據(jù)結(jié)構(gòu)順序表實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料

數(shù)據(jù)結(jié)構(gòu)順序表實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）

洛陽(yáng)理工學(xué)院實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)順序表實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）系別計(jì)算機(jī)班級(jí)學(xué)號(hào)姓名課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期10/23實(shí)驗(yàn)名稱順序表的基本操作成績(jī)實(shí)驗(yàn)?zāi)康模菏煜ふ莆站€性表順序存儲(chǔ)結(jié)構(gòu)，掌握與應(yīng)用順序表的查找、插入、刪除等基本操作算法，訓(xùn)練和提高結(jié)構(gòu)化程序設(shè)計(jì)能力及程序調(diào)試能力。實(shí)驗(yàn)條件：計(jì)算機(jī)一臺(tái)，VisualC++6.0實(shí)驗(yàn)內(nèi)容：?jiǎn)栴}描述以順序表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)以下基本操作：在第i個(gè)元素前插入一個(gè)新元素。查找值為x的某個(gè)元素。若成功，給出x在表中的位置；不成功給出提示信息。刪除第i個(gè)元素，若成功，給出提示信息并顯示被刪元素的值；不成功給出失敗的提示信息。數(shù)據(jù)結(jié)構(gòu)類(lèi)型定義typedefstruct{ ElemTypeelem[MAXSIZE];Intlast;}SeqList;模塊劃分(1)創(chuàng)建順序表輸入函數(shù)：voidInput(SeqList*L,intn)；(2)創(chuàng)建順序表輸出函數(shù)：voidOutput(SeqList*L)；(3)創(chuàng)建順序表的內(nèi)容查找函數(shù)：intLocate(SeqListL,ElemTypee)；(4)創(chuàng)建順序表的插入函數(shù)：intInsList(SeqList*L,inti,ElemTypee)；(5)創(chuàng)建順序表的刪除函數(shù)：intDelList(SeqList*L,inti,ElemType*e)；(6)主函數(shù)：voidmain()詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR-1#defineTRUE1#defineFALSE0#defineElemTypeint#define MAXSIZE100//最大長(zhǎng)度typedefstruct{ ElemTypeelem[MAXSIZE];intlast;}SeqList;voidInput(SeqList*L,intn)//輸入函數(shù){inti;printf("請(qǐng)輸入線性表的各元素值:\n");for(i=0;i<n;i++)scanf("%d",&L->elem[i]); }voidOutput(SeqList*L)//輸出函數(shù){inti;for(i=0;i<=L->last;i++) printf("%2d,",L->elem[i]);printf("\n");}intLocate(SeqListL,ElemTypee)//內(nèi)容查找函數(shù){ inti;i=0;while((i<=L.last)&&(L.elem[i])!=e)i++;if(i<=L.last)return(i+1);//返回序號(hào)elsereturn(-1);}intInsList(SeqList*L,inti,ElemTypee)//插入數(shù)據(jù){ intk; if((i<1)||(i>L->last+2))/*首先判斷插入位置是否合法*/ { printf("插入位置不合法\n"); return(ERROR); } if(L->last>=MAXSIZE-1) { printf("表已滿無(wú)法插入"); return(ERROR); } for(k=L->last;k>=i-1;k--)//為插入元素而移動(dòng)位置 L->elem[k+1]=L->elem[k]; L->elem[i-1]=e;//第i個(gè)元素的下標(biāo)為i-1 L->last++; return(OK);}intDelList(SeqList*L,inti,ElemType*e)//刪除函數(shù)/*在順序表L中刪除第i個(gè)數(shù)據(jù)元素，并用指針參數(shù)e返回其值。i的合法取值為1≤i≤L.last+1*/{ intk; if((i<1)||(i>L->last+1)) { printf("刪除位置不合法!\n"); return(ERROR); } *e=L->elem[i-1];/*將刪除的元素存放到e所指向的變量中*/ for(k=i;k<=L->last;k++) L->elem[k-1]=L->elem[k];/*將后面的元素依次前移*/ L->last--; return(TRUE); }voidmain()//主函數(shù){SeqListl,*la; intp,q,r,k,j,m,num; printf("請(qǐng)輸入線性表的長(zhǎng)度:"); scanf("%d",&r); l.last=r-1;la=&l;Input(la,la->last+1);Output(la);//按內(nèi)容查找元素 printf("請(qǐng)輸入要查找的元素值:\n"); scanf("%d",&q); p=Locate(l,q); if(p==-1) printf("在此線性表中沒(méi)有該元素!\n"); else printf("該元素在線性表中的位置為:%d\n",p); //插入元素（在i處插入元素e） printf("請(qǐng)輸入要插入的位置:\n"); scanf("%d",&k); printf("請(qǐng)輸入要插入的元素值:\n"); scanf("%d",&j); InsList(la,k,j);//調(diào)用插入函數(shù) Output(la); //刪除元素刪除第i個(gè)元素 printf("請(qǐng)輸入需要?jiǎng)h除的元素的位置：\n"); scanf("%d",&m); DelList(la,m,&num); printf("刪除成功,刪除的元素為%d",num); printf("\n");Output(la); }5.測(cè)試數(shù)據(jù)及結(jié)果實(shí)驗(yàn)總結(jié)：經(jīng)過(guò)調(diào)試與測(cè)試，實(shí)驗(yàn)結(jié)果與測(cè)試預(yù)期一致。順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)。線性表采用順序存儲(chǔ)的方式存儲(chǔ)就稱之為順序表。順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組地址連續(xù)的存儲(chǔ)單元中。第10章實(shí)驗(yàn)實(shí)驗(yàn)名稱：考試日程安排與成績(jī)統(tǒng)計(jì)實(shí)驗(yàn)類(lèi)型：綜合性性實(shí)驗(yàn)班級(jí)：20210611學(xué)號(hào)：2021061118姓名：郭鑫問(wèn)題描述=1\*GB3①問(wèn)題描述現(xiàn)要安排考試的考表（即考試日程表），假設(shè)共有10個(gè)班的學(xué)生，要安排10門(mén)必修課程的考試，必修課程是以班級(jí)來(lái)確定的，每個(gè)班各有3門(mén)必修課，因此各班的考試科目是不相同的；安排考表的原則是：相同課程采用統(tǒng)一的試卷，因此同一門(mén)課程的考試必須在相同時(shí)間進(jìn)行，同一個(gè)班所修的科目必須安排在不同的時(shí)間進(jìn)行考試，以避免考試時(shí)間的沖突。并要求全部考試的日程盡可能短。要求對(duì)考試結(jié)果做統(tǒng)計(jì)和排序。假設(shè)分別以編號(hào)0,1,2,3,4,5,6,7,8,9代表10門(mén)要考試的課程，以B1，B2，B3，B4，B5，B6，B7，B8，B9，B10代表10個(gè)班，每個(gè)人的信息包括學(xué)號(hào)、姓名、班級(jí)、各門(mén)考試課程成績(jī)、三門(mén)課程總成績(jī)，每個(gè)班的學(xué)生人數(shù)自行設(shè)定。要求設(shè)計(jì)一個(gè)簡(jiǎn)單的考試成績(jī)的查詢統(tǒng)計(jì)系統(tǒng)實(shí)現(xiàn)以下功能：顯示學(xué)生考試情況-按考試總分從高到底輸出全體學(xué)生的信息。-按照從B1到B10的班級(jí)順序，分班級(jí)按照考試總分從高到底的順序輸出各班學(xué)生的信息。-輸出指定班的學(xué)生考試成績(jī)信息。統(tǒng)計(jì)學(xué)生考試成績(jī)-按總成績(jī)統(tǒng)計(jì)出90分以上、80~89分、70~79分、60~69分、60分以下各分?jǐn)?shù)段的人數(shù)，并按總分從高到低分段輸出。-根據(jù)指定的某們課程的成績(jī)，統(tǒng)計(jì)出上述各分?jǐn)?shù)段的人數(shù)，并按分?jǐn)?shù)從高到低分段輸出。-統(tǒng)計(jì)并輸出指定班級(jí)中總成績(jī)或某一門(mén)課成績(jī)的各分?jǐn)?shù)段人數(shù)和每個(gè)人具體的信息。查找學(xué)生成績(jī)-查找總分或某一門(mén)課程成績(jī)的指定分?jǐn)?shù)段的人數(shù)及學(xué)生的詳細(xì)信息。-查找指定班級(jí)中總分或某一門(mén)課程成績(jī)屬于某分?jǐn)?shù)段的學(xué)生詳細(xì)信息。-查找指定學(xué)生（例如給定學(xué)號(hào)）的具體信息，包括：姓名、班級(jí)、各科分?jǐn)?shù)、總分?jǐn)?shù)等。=2\*GB3②求解方法說(shuō)明考試日程安排問(wèn)題。該問(wèn)題實(shí)際上是對(duì)若干元素進(jìn)行子集劃分的問(wèn)題，要求所劃分的每個(gè)子集中的元素沒(méi)有“考試沖突”關(guān)系。假設(shè)各個(gè)班的考試課程分別為：(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ù)題中考試安排原則，各個(gè)班要進(jìn)行的考試課程可以抽象為“考試沖突關(guān)系”，歸納各個(gè)班的考試課程可以整理得到考試沖突關(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的每個(gè)有序?qū)χ械膬砷T(mén)課程不能安排在同一時(shí)間考試，據(jù)此可以將10門(mén)課劃分為若干個(gè)考試時(shí)間沒(méi)有沖突的子集，并且使考場(chǎng)的場(chǎng)次盡量少，使得整個(gè)考試時(shí)間盡可能短。上述子集劃分問(wèn)題可以用對(duì)集合中的元素逐個(gè)“篩選”的辦法來(lái)解決。首先將集合的第1個(gè)元素置為第1個(gè)子集，再逐個(gè)檢查集合中的其余元素是否和第1個(gè)元素有考試沖突，若不存在考試沖突，則將其加入到第1個(gè)子集中，繼續(xù)檢查集合中的其余元素，凡是不與第1個(gè)子集中的元素沖突的元素都逐個(gè)將其加入到其中；接著按同樣的方法“篩選”出若干沒(méi)有考試沖突的元素構(gòu)成第2個(gè)子集，…，該過(guò)程一直到集合中的全部元素都分到某個(gè)子集中結(jié)束。得到的每一個(gè)子集中的課程就是可以安排在同一時(shí)間考試的課程。不同子集的課程則要安排在不沖突的時(shí)間考試。考試分?jǐn)?shù)的統(tǒng)計(jì)與排序考試成績(jī)輸出每個(gè)學(xué)生的信息記錄數(shù)據(jù)項(xiàng)應(yīng)包括：學(xué)號(hào)、姓名、班級(jí)、課程1、課程2、…、課程10、總成績(jī)。按總分高低輸出所有學(xué)生信息時(shí)，應(yīng)該以總成績(jī)?yōu)殛P(guān)鍵字從高分到低分對(duì)所有的學(xué)生記錄進(jìn)行排序，排序方法自行選定，然后依次輸出各個(gè)記錄。按照班級(jí)順序和總分高低輸出各班學(xué)生信息時(shí)，要對(duì)學(xué)生記錄進(jìn)行多關(guān)鍵字排序，首先以總成績(jī)?yōu)殛P(guān)鍵字從高分到低分對(duì)所有的學(xué)生記錄進(jìn)行排序，然后再以班號(hào)為關(guān)鍵字對(duì)全部學(xué)生記錄排序，再輸出結(jié)果。統(tǒng)計(jì)成績(jī)統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)，要求由用戶輸入，具體要求可以有：按照總成績(jī)統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)，并輸出各分?jǐn)?shù)段的學(xué)生記錄，即在統(tǒng)計(jì)一個(gè)分?jǐn)?shù)段的人數(shù)過(guò)程中，要輸出滿足查找條件的學(xué)生記錄，再輸出統(tǒng)計(jì)的結(jié)果。指定某一門(mén)課程，統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)并輸出各分?jǐn)?shù)段的學(xué)生記錄。對(duì)指定班級(jí)中總成績(jī)或指定課程成績(jī)做各分?jǐn)?shù)段人數(shù)的統(tǒng)計(jì)，也要輸出各分?jǐn)?shù)段的學(xué)生記錄。查找成績(jī)查找要求由用戶輸入，可以輸入以下條件：查找指定分?jǐn)?shù)項(xiàng)（總分或某一門(mén)課程）的某分?jǐn)?shù)段的學(xué)生信息，輸出查找結(jié)果。查找指定班級(jí)、指定分?jǐn)?shù)項(xiàng)的某分?jǐn)?shù)段的學(xué)生信息，輸出查找結(jié)果。查找指定學(xué)生（給定學(xué)號(hào)）的具體信息，輸出查找結(jié)果。③算法提示考試場(chǎng)次的劃分——“無(wú)考試沖突”子集劃分的算法思路。為了把10門(mén)課程劃分為時(shí)間上不沖突的若干場(chǎng)考試，可以利用一個(gè)循環(huán)隊(duì)列來(lái)實(shí)現(xiàn)求解方法中說(shuō)明的“篩選”過(guò)程。首先定義一個(gè)循環(huán)隊(duì)列，再把10門(mén)課程的編號(hào)從小到大依次加入到循環(huán)隊(duì)列中，然后重復(fù)下列步驟：隊(duì)頭元素出隊(duì)并作為當(dāng)前子集的第1個(gè)元素。隊(duì)頭元素繼續(xù)依次出隊(duì)，每出隊(duì)一個(gè)隊(duì)頭元素都要檢查與當(dāng)前子集中的元素是否有“考試沖突”；如果沒(méi)有沖突，則將其加入到當(dāng)前子集中，否則將其重新加入隊(duì)列中，等待以后加入新子集的機(jī)會(huì)。比較剛出隊(duì)元素與前一出隊(duì)元素編號(hào)。因?yàn)殛?duì)列中原有的元素是以編號(hào)從小到大的順序排列的，重新入隊(duì)的元素編號(hào)一定小于它的前一元素，所以一旦發(fā)現(xiàn)目前出隊(duì)的元素編號(hào)小于前一個(gè)出隊(duì)的元素，就可以斷定當(dāng)前的“考試沖突”子集已經(jīng)構(gòu)建完，隊(duì)列中剩余元素應(yīng)該構(gòu)建新的子集。為此，在當(dāng)前的隊(duì)頭元素出隊(duì)前，要先記下剛剛出隊(duì)的元素，以便判斷當(dāng)前出隊(duì)的元素是否要開(kāi)始構(gòu)建一個(gè)新子集。重復(fù)上述步驟一直到隊(duì)列空，則“無(wú)考試沖突”子集劃分完成。由上述算法思路可以知道，“無(wú)考試沖突”子集的劃分過(guò)程是一個(gè)循環(huán)的執(zhí)行過(guò)程，循環(huán)中的主要操作是元素出隊(duì)和判斷的操作。判斷操作包括出隊(duì)元素是否可以加入當(dāng)前子集和是否要開(kāi)始構(gòu)建一個(gè)新子集兩個(gè)方面，對(duì)后一個(gè)判斷如前所述，通過(guò)比較出隊(duì)元素與前一個(gè)出隊(duì)元素編號(hào)大小可以確定。為了判斷出隊(duì)元素與當(dāng)前子集中的元素是否有“考試沖突”，可以定義一個(gè)二維數(shù)組conf[n][n]來(lái)表示課程的考試沖突關(guān)系矩陣，矩陣中各元素的值根據(jù)以下規(guī)則確定，若編號(hào)為i的課程和編號(hào)為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)課程號(hào)為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與子集中的課程沒(méi)有考試沖突，可以加入其中，否則說(shuō)明表示課程i與子集中的某些課程有考試沖突，它不能加入該子集中。為了減少在二維數(shù)組conf中查找元素的操作，可以定義一個(gè)一維數(shù)組clash[n]來(lái)方便出隊(duì)元素i是否要加入當(dāng)前子集的判斷，數(shù)組clash[n]用于記錄出隊(duì)元素i與當(dāng)前子集中的元素是否存在考試沖突的信息。每當(dāng)開(kāi)始構(gòu)建一個(gè)新子集時(shí)，先將數(shù)組clash[n]的各元素初始化為0，當(dāng)有編號(hào)為i的課程加入子集時(shí)，將“考試沖突”關(guān)系矩陣中第i行的各列的值與數(shù)組clash的各對(duì)應(yīng)元素的值相加，因而使得數(shù)組clash中和編號(hào)為i的元素有考試沖突的相應(yīng)元素的值不再是0，當(dāng)下一個(gè)隊(duì)頭元素j出隊(duì)時(shí)，只要檢查數(shù)組clash中第j個(gè)元素的值是否為0，就可以判斷其是否與當(dāng)前子集中的元素有考試沖突；若數(shù)組clash中第j個(gè)元素的值不為0，則說(shuō)明元素j與當(dāng)前子集中元素存在考試沖突，應(yīng)將其重新加入隊(duì)列；若數(shù)組clash中第j各元素的值為0，則說(shuō)明它與當(dāng)前子集中元素不存在考試沖突，應(yīng)該將它加入當(dāng)前子集中，同時(shí)要將“考試沖突”關(guān)系矩陣中第j行的各列的值與數(shù)組clash的各對(duì)應(yīng)元素的值相加，這個(gè)過(guò)程一直到隊(duì)列空，則劃分無(wú)考試沖突子集完成。劃分結(jié)果可以用一個(gè)二維數(shù)組來(lái)記錄各子集中的元素的方式來(lái)表示，也可以用一個(gè)一維數(shù)組來(lái)記錄每個(gè)元素其所屬的子集號(hào)的方式來(lái)表示。上述算法的思路可以描述如下：建立表示課程考試沖突關(guān)系矩陣的二維數(shù)組conf[n][n]；定義用于檢查當(dāng)前子集的課程考試沖突信息的數(shù)組clash[n]；定義用于記錄子集劃分結(jié)果的數(shù)組result[n]；pre=n;//pre用于記錄前一個(gè)出隊(duì)元素的編號(hào)，初始值置為n以新建第1個(gè)子集k=0；//k用于記錄子集序號(hào)0~9(課程編號(hào))依次入隊(duì)；while（隊(duì)列不空）{隊(duì)頭元素i出隊(duì)；if(i<pre)//剛出隊(duì)元素小于前一個(gè)出隊(duì)元素，生成一個(gè)新子集{k++;數(shù)組clash初始化；}if(i可以加入當(dāng)前子集)//如果剛出隊(duì)元素與當(dāng)前子集中的元素?zé)o考試沖突，將其加入當(dāng)前子集{將i加入當(dāng)前子集，記錄i所屬子集的序號(hào)；將conf數(shù)組第i行各列的值與clash數(shù)組對(duì)應(yīng)列的值相加并記入clash中；}else//如果剛出隊(duì)元素與當(dāng)前子集中的元素有考試沖突，將其重新入隊(duì)將i重新加入隊(duì)列；pre=i;}考試成績(jī)統(tǒng)計(jì)和排序的實(shí)現(xiàn)按總成績(jī)或按某一門(mén)課的成績(jī)統(tǒng)計(jì)并輸出人數(shù)時(shí)，應(yīng)該使各分?jǐn)?shù)段的人數(shù)和每個(gè)學(xué)生的信息清晰的分開(kāi)。對(duì)全體學(xué)生或?qū)δ骋粋€(gè)班的學(xué)生的成績(jī)進(jìn)行排序時(shí)，排序方法可以任意選擇。就本實(shí)驗(yàn)問(wèn)題而言，因表長(zhǎng)不大采用簡(jiǎn)單的排序方法就可以達(dá)到目的，但為了比較各種常用排序方法性能和適用場(chǎng)合，還可以采用不同的排序方法實(shí)現(xiàn)排序。對(duì)多關(guān)鍵字的排序要求，要注意排序方法的穩(wěn)定性問(wèn)題。例如，在按總成績(jī)從高分到低分對(duì)全體學(xué)生進(jìn)行排序后，再按班級(jí)從高分到低分進(jìn)行排序，此時(shí)要求分班級(jí)排序時(shí)采用的排序方法其動(dòng)態(tài)性能必須是穩(wěn)定的。同樣地，如果在按總成績(jī)從高分到低分排序的基礎(chǔ)上，再要求按某一門(mén)課的成績(jī)從高分到低分排序，也要求第2層排序一定注意選擇動(dòng)態(tài)性能穩(wěn)定的排序方法。在實(shí)現(xiàn)查找或排序功能時(shí)，其查找或排序的依據(jù)（指定項(xiàng)）和目標(biāo)（輸出結(jié)果）通過(guò)提示用戶輸入來(lái)確定。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)typedefintKeyType;typedefcharInfoType[10];typedefstruct/*記錄類(lèi)型*/{KeyTypekey;/*關(guān)鍵字項(xiàng)*/InfoTypedata;/*其他數(shù)據(jù)項(xiàng),類(lèi)型為InfoType*/}RecType算法設(shè)計(jì)#include<iostream>usingnamespacestd;#defineMAXE20/*線性表中最多元素個(gè)數(shù)*/typedefintKeyType;typedefcharInfoType[10];typedefstruct/*記錄類(lèi)型*/{KeyTypekey;/*關(guān)鍵字項(xiàng)*/InfoTypedata;/*其他數(shù)據(jù)項(xiàng),類(lèi)型為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)前無(wú)序區(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ì)程序包含有多個(gè)功能，所以，采用菜單，以方便用戶進(jìn)行功能選擇。菜單如下：1：1：直接插入排序算法驗(yàn)證2：快速排序算法驗(yàn)證。3:直接選擇排序算法驗(yàn)證。4:退出運(yùn)行、測(cè)試與分析1）直接插入排序算法驗(yàn)證快速排序算法驗(yàn)證。3）直接選擇排序算法驗(yàn)證。實(shí)驗(yàn)收獲及思考這次實(shí)驗(yàn)我對(duì)選擇拍循序，插入排序，快速排序有了更好的理解，以及時(shí)間復(fù)雜度的問(wèn)題分析，通過(guò)這次實(shí)驗(yàn)，我對(duì)排序的內(nèi)容有了更深入的了解。編程技術(shù)有了很大的提高目錄TOC\o"1-3"\h\u166971選題背景2232202方案與論證3258412.1鏈表的概念和作用3265912.3算法的設(shè)計(jì)思想4187062.4相關(guān)圖例5150312.4.1單鏈表的結(jié)點(diǎn)結(jié)構(gòu)5277712.4.2算法流程圖5122303實(shí)驗(yàn)結(jié)果6220343.1鏈表的建立6258113.2單鏈表的插入6320213.3單鏈表的輸出7190563.4查找元素7135493.5單鏈表的刪除8325073.6顯示鏈表中的元素個(gè)數(shù)（計(jì)數(shù)）9165624結(jié)果分析1098784.1單鏈表的結(jié)構(gòu)1050594.2單鏈表的操作特點(diǎn)10204464.2.1順鏈操作技術(shù)10123154.2.2指針保留技術(shù)10131654.3鏈表處理中的相關(guān)技術(shù)10226005設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)1119571參考文獻(xiàn)1214900附錄代碼：131選題背景陳火旺院士把計(jì)算機(jī)60多年的發(fā)展成就概括為五個(gè)“一”：開(kāi)辟一個(gè)新時(shí)代信息時(shí)代，形成一個(gè)新產(chǎn)業(yè)信息產(chǎn)業(yè)，產(chǎn)生一個(gè)新科學(xué)計(jì)算機(jī)科學(xué)與技術(shù)，開(kāi)創(chuàng)一種新的科研方法計(jì)算方法，開(kāi)辟一種新文化計(jì)算機(jī)文化，這一概括深刻影響了計(jì)算機(jī)對(duì)社會(huì)發(fā)展所產(chǎn)生的廣泛而深遠(yuǎn)的影響。數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)求解問(wèn)題過(guò)程的兩大基石。著名的計(jì)算機(jī)科學(xué)家P.Wegner指出，“在工業(yè)革命中其核心作用的是能量，而在計(jì)算機(jī)革命中其核心作用的是信息”。計(jì)算機(jī)科學(xué)就是“一種關(guān)于信息結(jié)構(gòu)轉(zhuǎn)換的科學(xué)”。信息結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）是計(jì)算機(jī)科學(xué)研究的基本課題，數(shù)據(jù)結(jié)構(gòu)又是算法研究的基礎(chǔ)。2方案與論證2.1鏈表的概念和作用鏈表是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈表屬于線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也是常用的動(dòng)態(tài)存儲(chǔ)方法。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象)+

指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。以“結(jié)點(diǎn)的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i單鏈表1、鏈接存儲(chǔ)方法鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表（LinkedList）。鏈表的具體存儲(chǔ)表示為：①用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）②鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈(link)）注意：鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)┌───┬───┐│data│next│└───┴───┘data域--存放結(jié)點(diǎn)值的數(shù)據(jù)域next域--存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）注意：①鏈表通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。②每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（SingleLinkedList）。3、頭指針head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開(kāi)始結(jié)點(diǎn)。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來(lái)命名。終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。2.2實(shí)驗(yàn)的基本要求（軟硬件）用VC++6.0軟件平臺(tái)，操作系統(tǒng)：WindowsXP硬件：內(nèi)存要求：內(nèi)存大小在256MB，其他配置一般就行。2.3算法的設(shè)計(jì)思想（a）定義一個(gè)創(chuàng)建鏈表的函數(shù)，通過(guò)該頭插法創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈表，在接下來(lái)的鏈表操作中使用。（b）定義輸出鏈表的算法，遍歷結(jié)點(diǎn)的指針域判斷是否為空，如果不為空則輸出其數(shù)據(jù)域，直到指針域?yàn)榭諡橹埂＃╟）定義一個(gè)遍歷查找的算法，通過(guò)遍歷的數(shù)據(jù)域，分別與要查詢的元素進(jìn)行比較，如果查找到則返回并輸出，如入查找失敗則返回錯(cuò)誤提示信息。（d）定義插入結(jié)點(diǎn)的算法，首先查找指針域?yàn)榭盏慕Y(jié)點(diǎn)，并申請(qǐng)空間插入在結(jié)點(diǎn)的后邊，并且將其指針域置空。（e）定義刪除節(jié)點(diǎn)的操作，這個(gè)算法用于對(duì)鏈表中某個(gè)多余節(jié)點(diǎn)的刪除工作，其關(guān)鍵在于前驅(qū)結(jié)點(diǎn)的保留，查找到需刪除的結(jié)點(diǎn)，將其刪除，并將其后繼結(jié)點(diǎn)連到其前驅(qū)結(jié)點(diǎn)。2.4相關(guān)圖例2.4.1單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如圖2-1所示,為單鏈表的結(jié)點(diǎn)結(jié)構(gòu)示意圖：Data域Next域Data域Next域圖2-1單鏈表的結(jié)點(diǎn)結(jié)構(gòu)2.4.2算法流程圖如圖2-2所示，為此算法流程圖：開(kāi)始開(kāi)始定義結(jié)構(gòu)體Node定義結(jié)構(gòu)體Node構(gòu)建各種對(duì)鏈表操作的函數(shù)（插入、刪除、查找、輸出），并寫(xiě)出相應(yīng)的算法及實(shí)現(xiàn)過(guò)程創(chuàng)建一個(gè)單鏈表，用于之前所定義的函數(shù)對(duì)其進(jìn)行操作按要求輸出結(jié)果結(jié)束圖2-2算法流程圖3實(shí)驗(yàn)結(jié)果3.1鏈表的建立圖3-1鏈表的建立3.2單鏈表的插入圖3-2單鏈表的插入3.3單鏈表的輸出圖3-3輸出單鏈表元素3.4查找元素圖3-4查找成功圖3-5查找失敗3.5單鏈表的刪除圖3-6刪除成功圖3-6刪除失敗3.6顯示鏈表中的元素個(gè)數(shù)（計(jì)數(shù)）圖3-7輸出長(zhǎng)度4結(jié)果分析4.1單鏈表的結(jié)構(gòu)一般情況下，使用鏈表，只關(guān)心鏈表中結(jié)點(diǎn)間的邏輯順序，并不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置，因此通常情況下用箭頭來(lái)表示鏈域中的指針，于是鏈表就可以更直觀的畫(huà)成用箭頭鏈接起來(lái)的結(jié)點(diǎn)序列，如下圖所示：ABABCDE^H圖4-1單鏈表的示例圖4.2單鏈表的操作特點(diǎn)4.2.1順鏈操作技術(shù)從“頭”開(kāi)始，訪問(wèn)單鏈表L中的結(jié)點(diǎn)i（p指向該節(jié)點(diǎn)）時(shí)，由于第i個(gè)結(jié)點(diǎn)的地址在第i-1個(gè)結(jié)點(diǎn)（pre指向該結(jié)點(diǎn)，為p的前驅(qū)）的指針域中存放，查找必須從單鏈表的“首結(jié)點(diǎn)”開(kāi)始（p=L）；通過(guò)p=p->next并輔助計(jì)數(shù)器來(lái)實(shí)現(xiàn)。4.2.2指針保留技術(shù)通過(guò)對(duì)第i個(gè)結(jié)點(diǎn)進(jìn)行插入、刪除等操作時(shí)，需要對(duì)第i-1個(gè)結(jié)點(diǎn)的指針域進(jìn)行鏈址操作（pre->next），因此在處理過(guò)程中始終需要維持當(dāng)前指針p與其前驅(qū)指針pre的關(guān)系，將這種技術(shù)稱為“指針保留技術(shù)”。4.3鏈表處理中的相關(guān)技術(shù)1）單鏈表與多重鏈表的差別在于指針域的個(gè)數(shù)。2）判斷當(dāng)前結(jié)點(diǎn)p是否為表尾。一半鏈表中，p結(jié)點(diǎn)是表尾的條件是：該節(jié)點(diǎn)的后繼結(jié)點(diǎn)為空指針，即p->next==NULL;3）鏈表的長(zhǎng)度并未顯示保存。由于鏈表是動(dòng)態(tài)生成的結(jié)構(gòu)，其長(zhǎng)度要通過(guò)順鏈查找到表尾得到。因此在處理鏈表時(shí)，往往是以當(dāng)前處理結(jié)點(diǎn)p是否為表尾作為控制條件，而不是長(zhǎng)度n作為控制條件。5設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)通過(guò)這次實(shí)驗(yàn)加深了我對(duì)于單鏈表的進(jìn)一步了解，了解到了單鏈表在內(nèi)存中的存儲(chǔ)結(jié)構(gòu)，最重要的是學(xué)會(huì)了如何運(yùn)用C語(yǔ)言將單鏈表的建立，插入、刪除、添加等操作。在程序?qū)崿F(xiàn)中也遇到了一些困難，在單鏈表初始化時(shí)，使用了0作為結(jié)束輸入符，導(dǎo)致單鏈表不能存儲(chǔ)數(shù)據(jù)0；單鏈表中只能存儲(chǔ)相同類(lèi)型的數(shù)據(jù)，在存儲(chǔ)不同類(lèi)型的數(shù)據(jù)時(shí)需要改變輸入結(jié)束標(biāo)志，程序通用性比較差。在進(jìn)行程序設(shè)計(jì)的時(shí)候沒(méi)有考慮好刪除和查找的方式，只進(jìn)行了輸入元素的查找和刪除，而且進(jìn)行鏈表的插入時(shí)，只考慮了頭插法在結(jié)尾插入，而沒(méi)有考慮輸入結(jié)點(diǎn)插入等，程序的靈活性比較低。通過(guò)這次課程設(shè)計(jì)，讓我充分認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)在編寫(xiě)程序方面的重要地位。不僅僅是單鏈表的操作，還有棧和隊(duì)列等特殊的單鏈表操作，以及其他一些常用的數(shù)據(jù)結(jié)構(gòu)對(duì)于程序的效率和內(nèi)存使用有很大的幫助。我希望在接下來(lái)的學(xué)習(xí)中收獲更多的東西。參考文獻(xiàn)[1]耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)--用C語(yǔ)言描述[M].北京:高等教育出版社,2021.6.[2]譚浩強(qiáng).C程序設(shè)計(jì)[M].北京:清華大學(xué)出版社,2004.6.附錄代碼：結(jié)構(gòu)體定義：#pragmaonce#include<stdio.h>#include<stdlib.h>enummy_enum{_EXIT,_CREATE,_INSERT,_PRINT,_SEARCH,_DELETE,_COUNT,};staticintcount=0;typedefintElemtype;typedefstructNode/*單鏈表結(jié)構(gòu)體的定義*/{Elemtypedata;structNode*next;}Node,*LinkList;voidtest();/*測(cè)試函數(shù)*/voidmain_menu();//主菜單函數(shù)voidCreatFromHead(LinkList*l);/*頭插法建立單鏈表*/voidInsert(LinkListl);//單鏈表的插入voidPrint(LinkListl);/*單鏈表的輸出*/intSearch(LinkListl,Elemtypee);//查找指定的元素voidDeletelist(LinkListl,Elemtypee);//刪除元素voidCount();//計(jì)數(shù)voidCREATE(LinkList*head);voidINSERT(LinkList*head);voidPRINT(LinkList*head);voidSEARCH(LinkList*head);voidDELET(LinkList*head);voidCOUNT();單鏈表操作函數(shù)：#define_CRT_SECURE_NO_WARNINGS#include"linklist.h"voidmain_menu(){printf("\t單鏈表的簡(jiǎn)單操作\t\t\n\n");printf("\t1單鏈表的建立\n");printf("\t2單鏈表的插入\n");printf("\t3單鏈表的輸出\n");printf("\t4單鏈表的查找\n");printf("\t5單鏈表的刪除\n");printf("\t6單鏈表的長(zhǎng)度\n");printf("\t0退出\n");}voidCreatFromHead(LinkList*l)/*頭插法建立單鏈表*/{Node*s;intc=0;intflag=1;*l=(Node*)malloc(sizeof(Node));if(*l==NULL){printf("申請(qǐng)空間失?。?！\n");return;}(*l)->next=NULL;while(flag){scanf("%d",&c);if(c!=0){s=(Node*)malloc(sizeof(Node));if(s==NULL){printf("申請(qǐng)空間失?。?！\n");return;}s->data=c;s->next=(*l)->next;(*l)->next=s;count++;}elseflag=0;}}voidInsert(LinkListl)//單鏈表的插入{intinsert=0;Node*s=NULL;printf("請(qǐng)輸入需要插入的元素：");scanf("%d",&insert);s=(Node*)malloc(sizeof(Node));if(s==NULL){printf("申請(qǐng)空間失?。?！\n");return;}while(l->next!=NULL){l=l->next;}s->data=insert;s->next=l->next;l->next=s;count++;}voidPrint(LinkListl)/*單鏈表的遍歷*/{Node*p;p=l->next;while(p!=NULL){printf("%d",p->data);p=