數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)緒論時(shí)間復(fù)雜度T（n）=O（f（n））通常用：常量階O(1)線(xiàn)性階O(n)平方階O(n^2)對(duì)數(shù)階O(logn)指數(shù)階O(2^n)計(jì)算的復(fù)雜性：算法的計(jì)算量的大小算法的時(shí)間復(fù)雜度取決于問(wèn)題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。算法：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列。（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)棧與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)串是線(xiàn)性結(jié)構(gòu)有序表屬于邏輯結(jié)構(gòu)連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址一定連續(xù)一、數(shù)據(jù)：是對(duì)客觀(guān)事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。它是計(jì)算機(jī)程序加工的“原料”。二、數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。三、數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第1頁(yè)。四、數(shù)據(jù)機(jī)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問(wèn)題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱(chēng)為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第1頁(yè)。五、元素在存貯結(jié)構(gòu)（1）物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：它包括數(shù)據(jù)元素的表示和關(guān)系。（2）邏輯結(jié)構(gòu)六、位bit：在計(jì)算機(jī)中表示信息的最小單位是二進(jìn)制的一位七、元素element/節(jié)點(diǎn)node：位串八、數(shù)據(jù)域：當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串九、數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法，順序映像和非順序映像，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)（借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系）。算法：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列。（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出算法設(shè)計(jì)要求：（1）正確性（2）可讀性（3）健壯性（4）效率與低存儲(chǔ)量需求-------------------------------------------------------------------------------線(xiàn)性表：采用順序存儲(chǔ)，便于進(jìn)行插入和刪除的操作順序表的優(yōu)點(diǎn)：結(jié)構(gòu)緊湊，存儲(chǔ)空間利用率高，操作簡(jiǎn)單。（存儲(chǔ)密度大）數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第2頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第2頁(yè)。當(dāng)線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。若某線(xiàn)性表最常用的操作是存取任一指定序號(hào)的元素和最后進(jìn)行插入和刪除運(yùn)算，則利用順序表的存儲(chǔ)方式最節(jié)省時(shí)間；若某線(xiàn)性表最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除一個(gè)元素，則采用僅有尾指針的單循環(huán)鏈表的存儲(chǔ)方式最節(jié)省時(shí)間。設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)或刪除尾結(jié)點(diǎn)，則利用帶頭結(jié)點(diǎn)的雙循環(huán)鏈表的存儲(chǔ)方式最節(jié)省時(shí)間。若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則利用帶頭結(jié)點(diǎn)的雙循環(huán)鏈表的存儲(chǔ)方式最節(jié)省時(shí)間。鏈表的優(yōu)點(diǎn)：在空間的合理利用上和插入、刪除時(shí)不需要移動(dòng)，是線(xiàn)性表的首選存儲(chǔ)結(jié)構(gòu)。（不必事先估計(jì)存儲(chǔ)空間、所需空間與線(xiàn)性長(zhǎng)度成正比）缺點(diǎn)：求線(xiàn)性表的長(zhǎng)度時(shí)不如順序存儲(chǔ)結(jié)構(gòu)（不可隨機(jī)訪(fǎng)問(wèn)任一元素）線(xiàn)性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)；線(xiàn)性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比。對(duì)于順序存儲(chǔ)的線(xiàn)性表，訪(fǎng)問(wèn)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O（1），插入和刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為O（n）。對(duì)于鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表，訪(fǎng)問(wèn)第i個(gè)元素的時(shí)間復(fù)雜度為O（n）。對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線(xiàn)性鏈表分為單鏈表和多重鏈表；根據(jù)指針的連接方式，鏈表又可分為動(dòng)態(tài)鏈表和靜態(tài)鏈表。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第3頁(yè)。鏈表的頭結(jié)點(diǎn)的作用：數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第3頁(yè)。靜態(tài)鏈表中指針表示的是下一個(gè)元素地址靜態(tài)鏈表能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類(lèi)似，不需做元素的移動(dòng)。線(xiàn)性表是線(xiàn)性結(jié)構(gòu)的基本形式線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表的定義線(xiàn)性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間是一種線(xiàn)性關(guān)系，數(shù)據(jù)元素“一個(gè)接一個(gè)的排列”。線(xiàn)性表是具有相同數(shù)據(jù)類(lèi)型的n(n>=0)個(gè)數(shù)據(jù)元素的有限序列，記為：(a1，a2，…ai-1，ai，ai+1，…an)；其中：n為表長(zhǎng)，n＝0時(shí)稱(chēng)為空表。表中相鄰元素之間存在順序關(guān)系：ai-1稱(chēng)為ai的直接前趨，ai+1稱(chēng)為ai的直接后繼。a1，…an-1有且僅有一個(gè)直接后繼；（非空線(xiàn)性表）a2，…an有且僅有一個(gè)直接前趨。（非空線(xiàn)性表）線(xiàn)性表的順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線(xiàn)性表的各元素，用這種存儲(chǔ)形式存儲(chǔ)的線(xiàn)性表稱(chēng)其為順序表。存儲(chǔ)的特點(diǎn)：物理上的相鄰實(shí)現(xiàn)了邏輯相鄰的表示。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第4頁(yè)。順序存儲(chǔ)能隨機(jī)訪(fǎng)問(wèn)第i個(gè)元素：數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第4頁(yè)。設(shè)a１的存儲(chǔ)地址為L(zhǎng)oc(a１)，每個(gè)數(shù)據(jù)元素占d個(gè)存儲(chǔ)地址，則第i個(gè)數(shù)據(jù)元素的地址為：Loc(ai)=Loc(a１)+(i-1)*d1≤I≤n順序表插入運(yùn)算時(shí)間主要消耗：數(shù)據(jù)的移動(dòng)。一般情況下，在第i（1<=i<=n）個(gè)元素之前插入一個(gè)元素時(shí)，需將第n至第i（共n-i+1）個(gè)元素向后移動(dòng)一個(gè)位置。（在第i個(gè)位置上插入x，從ai到an都要向下移動(dòng)一個(gè)位置，共需要移動(dòng)n－i＋1個(gè)元素。）一般情況下，刪除第i（1<=i<=n）個(gè)元素時(shí)，需從第i+1至第n（共n-i）個(gè)元素向前移動(dòng)一個(gè)位置i的取值范圍為：1≤i≤n+1（即有n＋1個(gè)位置可以插入）。設(shè)在第i個(gè)位置上作插入的概率為Pi：在等概率情況下：Pi=1/(n+1)，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)則為：這說(shuō)明：在順序表上做插入操作需移動(dòng)表中一半的數(shù)據(jù)元素。顯然順序表上插入時(shí)間復(fù)雜度為Ｏ(n)。intSeqlistInsert(A[],n,i，x){if(i<1||i>n)//檢查插入位置的正確性{Printf(“參數(shù)非法”);return0;//插入位置參數(shù)錯(cuò)，返回錯(cuò)誤代碼0數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第5頁(yè)。}數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第5頁(yè)。else{for(k=n;k>=i;k--)A[k-1]<=A[k];//結(jié)點(diǎn)移動(dòng)A[i]<=x;//新元素插入n<=n+1;//n指向新的最后元素returnn;//插入成功，返回成功代碼}}線(xiàn)性表的刪除運(yùn)算是指將表中第i個(gè)元素從線(xiàn)性表中去掉。SeqlistDelete(A[],n,i){if(i<1ORi>n)//檢查空表及刪除位置的合法性{Printf(“參數(shù)非法”);return0;//不存在第i個(gè)元素，返回錯(cuò)誤代碼0}else{for(k=i+1;k<n;k++)A[k-1]<=A[k];//數(shù)據(jù)元素向前移動(dòng)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第6頁(yè)。n<=n-1;//n指向新的最后元素?cái)?shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第6頁(yè)。returnn;//刪除成功，返回成功代碼}刪除算法的時(shí)間性能分析與插入運(yùn)算相同，其時(shí)間主要消耗在了移動(dòng)元素上。計(jì)算數(shù)據(jù)移動(dòng)的次數(shù)：某次刪除數(shù)據(jù)的移動(dòng)次數(shù)與具體位置有關(guān)。求平均性能。刪除第i個(gè)元素時(shí)，其后面的元素ai+1～an都要向上移動(dòng)一個(gè)位置，共移動(dòng)了n-i個(gè)元素。i的取值范圍為：1≤i≤n（即有n個(gè)位置可以刪除）。設(shè)在第i個(gè)位置上作刪除的概率為Pi，平均移動(dòng)數(shù)據(jù)元素的次數(shù)：在等概率情況下：Pi=1/n，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)則為：這說(shuō)明順序表上作刪除運(yùn)算時(shí)大約需要移動(dòng)表中一半的元素。顯然該算法的時(shí)間復(fù)雜度為Ｏ(n)。線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不要求邏輯上相鄰的兩個(gè)數(shù)據(jù)元素物理上也相鄰，因此不需要用地址連續(xù)的存儲(chǔ)單元來(lái)實(shí)現(xiàn)。鏈表是通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素的，對(duì)每個(gè)數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼ai+1所在的存貯單元的地址，這兩部分信息組成一個(gè)“結(jié)點(diǎn)”。存放數(shù)據(jù)元素信息的稱(chēng)為數(shù)據(jù)域，存放其后繼地址的稱(chēng)為指針域。鏈表的表示：鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第7頁(yè)。結(jié)點(diǎn)的申請(qǐng)：p=newLNode;結(jié)點(diǎn)的釋放：deletep；數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第7頁(yè)。在某結(jié)點(diǎn)后面插入新結(jié)點(diǎn)：設(shè)p指向單鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的后面。操作如下：①s->next=p->next;②p->next=s;注意：兩個(gè)指針的操作順序不能交換。在某結(jié)點(diǎn)前面插入新結(jié)點(diǎn)：設(shè)ｐ指向鏈表中某結(jié)點(diǎn)，ｓ指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面。與后插不同的是：首先要找到*p的前驅(qū)*q，然后再完成在*q之后插入*s。設(shè)單鏈表頭指針為L(zhǎng)，操作如下：q=L;while(q->next!=p)q=q->next;//找*p的直接前驅(qū)s->next=q->next;q->next=s;刪除結(jié)點(diǎn)：設(shè)p指向單鏈表中某結(jié)點(diǎn)，刪除*p。作業(yè)1：線(xiàn)性表中元素為整型，以50為界，小于50在左，大于50在右。作業(yè)講解：x<=A[i];數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第8頁(yè)。 while(A[j]>=xandi<j)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第8頁(yè)。 { j<=j-1; if(A[j]<x) {A[i]<=A[j]; i<=i+1;}while(A[i]<xandx<j) i<=i+1;if(A[i]>=x){A[j] <=A[i];j<=j-1;}插入a1：*p=a1;改為：p->date=a1;指針p指向?qū)ο骴ate=a1，該對(duì)象是一個(gè)結(jié)構(gòu)體，指向結(jié)構(gòu)體里a1那部分刪除a1并把存儲(chǔ)空間解放：free（p）；二、鏈表的構(gòu)造q<=NULL;for(j=n;i>=1;i--)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第9頁(yè)。{數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第9頁(yè)。p<=(NODE*)malloc(sizeof(NODE));p->date<=an;將an替換為ai注：i此處為n-1p->next<=NULL;把指針設(shè)為空指針，替換為qq<=p;}考慮鏈表的頭指針當(dāng)ai未插入時(shí)：算法：CreatLinkList(n)構(gòu)造鏈表，n為節(jié)點(diǎn){q<=NULL;for(i=n;i>=1;i--){p<=(NODE*)malloc(sizeof(NODE));scanf(ai);p->date<=ai;p->next<=q;q<=p;}return(p);}數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第10頁(yè)。注：此時(shí)p、q一樣∵已被賦值給對(duì)方數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第10頁(yè)。作業(yè)4：倒過(guò)來(lái)。從前節(jié)點(diǎn)到后節(jié)點(diǎn)。頭指針headp<=head;從頭指針出發(fā)，依次輸出節(jié)點(diǎn)。可用for循環(huán)或while循環(huán)（不確定循環(huán)次數(shù)時(shí)用）p<=head;while(p=\NULL){printf(p->data);p<=p->next;}三、鏈表的插入算法：假定：在表中值為x的節(jié)點(diǎn)前面插入一個(gè)值為y的節(jié)點(diǎn)。分析：1.空鏈2.表中第1個(gè)節(jié)點(diǎn)的值為x3.表中有一個(gè)值為x的節(jié)點(diǎn)4.表中沒(méi)有值為x的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第11頁(yè)。5.表中有多個(gè)值為x的節(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第11頁(yè)。NODE*InsertLinkList(head,x,y){q<=(NODE*)malloc(sizeof(NODE));q->data<=y;q->next<=NULL;if(head=NULL)head<=q;elseif(head->date=x){q->next<=head;head<=q;}else{r<=head;p<=head->next;while(p->data=/xandp=\NULL)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第12頁(yè)。p<=p->next;數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第12頁(yè)。if(p=\NULL){q->next<=p;r->next<=q;}elser->next<=q;}return(head);}假定：刪除表中值為x的節(jié)點(diǎn)分析：1.空表； 2.第1個(gè)節(jié)點(diǎn)的值為x； 3.在表中有值為x的節(jié)點(diǎn)； 4.在表中沒(méi)有值為x的節(jié)點(diǎn)NODE*=DeleteLinkList(head,x,t)（返回指針）a.值參callbyvalue數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第13頁(yè)。{b.變參callbyaddress數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第13頁(yè)。 s<=NULL; if(head=NULL) printf("這是一個(gè)空表") elseif(head->data=x) { s<=head; head<=head->next; } else q<=head;（返回內(nèi)容不同） p<=head->next; while(p->data=\xandp->next=\NULL) { q<=p; p<=p->next; } if(p->data=x) { s<=p; q->next<=p->next;數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第14頁(yè)。 }數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第14頁(yè)。 else printf("表中沒(méi)有值為x的節(jié)點(diǎn)")；}if(s=\NULL){ t<=s->data; free(s); return(head);（返回值）}}四、鏈?zhǔn)酱尜A結(jié)構(gòu)的棧五、鏈?zhǔn)酱尜A結(jié)構(gòu)的隊(duì)列六、循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。雙向鏈表在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(qū)。二叉鏈表的特征：n個(gè)結(jié)點(diǎn)，則鏈指針?biāo)傅臑閚-1二叉鏈表總鏈域個(gè)數(shù)2n，頭指針指向根結(jié)點(diǎn)，其余n-1個(gè)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第15頁(yè)?！嘣谟衝個(gè)結(jié)點(diǎn)的K叉樹(shù)鏈表中，值為非空的鏈域個(gè)數(shù)為n-1；數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第15頁(yè)?？盏逆溣騻€(gè)數(shù)為kn-（n-1）=kn-n+1對(duì)于任意給定的一個(gè)線(xiàn)性表：L=(a1,a2,……,an),寫(xiě)出構(gòu)造一個(gè)鏈表的算法。節(jié)點(diǎn)類(lèi)型及其算法頭部約定如下：structnode{ElemTypedata；structnode*next；}；typedefstructnodeNODE；NODE*CreateLinkList(intn)算法如下：NODE*CreateLinkList(intn){q(NODE*)malloc(sizeof(NODE));scanf(an);q->dataan;q->nextNULL;for(i=n-1;i≥1;i--){p(NODE*)malloc(sizeof(NODE));scanf(ai);數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第16頁(yè)。p->dataai;數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第16頁(yè)。p->nextq;qp;}return(p);}有一個(gè)單鏈表（不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相同），其頭指針為head，編寫(xiě)一個(gè)函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。鏈表節(jié)點(diǎn)結(jié)構(gòu)定義如下：datanext解：遍歷該鏈表的每個(gè)結(jié)點(diǎn)，每遇到一個(gè)結(jié)點(diǎn)，判斷其值是否為x，是的話(huà)就計(jì)數(shù)。結(jié)點(diǎn)個(gè)數(shù)存儲(chǔ)在變量n中。算法如下：intCounter(head,x)

{

intn=0;

p<=head;

while(p!=NULL)

{

if(p->data=x)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第17頁(yè)。n<=n+1;

p<=p->next;

}

return(n);

}

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第17頁(yè)。-------------------------------------------------------------------------------棧和隊(duì)列棧：限定僅在表尾進(jìn)行插入或刪除棧：是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表表尾（棧頂）表頭（棧底）假設(shè)棧S=（a1，a2，…，an），則稱(chēng)a1為棧底元素，an為棧頂元素。棧中元素按a1，a2，…，an的次序進(jìn)棧，退棧的第一元素應(yīng)為棧頂元素。換句話(huà)說(shuō)，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱(chēng)為后進(jìn)后出的線(xiàn)性表。壓棧算法：intPushStack(s[],top,x){ if(top>=SMAX) { printf("overlow");數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第18頁(yè)。 return0;數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第18頁(yè)。 } else { S[top]<=x; top=top++; }}出棧算法：ElemTypePopstack(s[],top,bottom){ if(top<=bottom) { printf("overlow"); } return0; } else { top<=top-1; y<=S[top];數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第19頁(yè)。 returny;數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第19頁(yè)。 }作業(yè)2：為了節(jié)省空間，兩個(gè)棧共享一段內(nèi)存，寫(xiě)出這兩個(gè)棧的壓棧及出棧算法。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)地內(nèi)存空間時(shí)，應(yīng)將兩棧的棧底，分別設(shè)在這片內(nèi)存空間的兩端，這樣，當(dāng)兩個(gè)棧的棧頂在?？臻g的某一位置相遇時(shí)，才會(huì)產(chǎn)生上溢。兩個(gè)棧共享空間的條件：兩棧頂指針值相減的絕對(duì)值為1（兩棧頂指針相鄰）數(shù)組Q[0..n-1]作為一個(gè)環(huán)形隊(duì)列，f為當(dāng)前隊(duì)頭元素的前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)總小于n，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式是(n+r-f)mod隊(duì)列特點(diǎn)：先進(jìn)先出，隊(duì)頭出，隊(duì)尾進(jìn)，當(dāng)隊(duì)尾大于隊(duì)頭時(shí)，說(shuō)明進(jìn)的比出的多，此時(shí)元素個(gè)數(shù)為Rear–Front循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是(rear-front+m)MODm循環(huán)隊(duì)列兩指針front指示隊(duì)列頭元素位置rear指示隊(duì)列尾元素位置初始化建空隊(duì)列時(shí)，令front=rear=0，插入新的尾元素->尾指針+1；刪除隊(duì)列頭元素->頭指針+1數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第20頁(yè)。頭指針始終指向隊(duì)列頭元素?cái)?shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第20頁(yè)。尾指針始終指向隊(duì)列尾指針的下一個(gè)位置在棧滿(mǎn)的情況下，不能作進(jìn)棧運(yùn)算，否則產(chǎn)生“上溢”。隊(duì)列：1.什么是隊(duì)列？也是一種特殊的線(xiàn)性表（插入在表的一端，刪除在表的另一端）隊(duì)列：先進(jìn)先出數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第21頁(yè)。區(qū)別于線(xiàn)性表：插入、刪除在同一端。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第21頁(yè)。2.隊(duì)列的操作：1.插入。判別隊(duì)列空間“空”或“滿(mǎn)”a.另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列“空”或“滿(mǎn)”b.少用一個(gè)元素空間，約定以“隊(duì)列頭指針在隊(duì)列尾指針的下一個(gè)位置（指環(huán)狀的下一位置）”上作為隊(duì)列呈“滿(mǎn)”狀態(tài)的標(biāo)志總結(jié)：若Rear>Front，元素個(gè)數(shù)為Rear-Front；若Rear<Front，元素個(gè)數(shù)為(Rear-Front+N)%N(N為隊(duì)列容量)如何判斷其滿(mǎn)？intQueueInsert(Q[],front,rear,x){ if(rear>=QMAX) { printf("Overlow");數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第22頁(yè)。 return0;數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第22頁(yè)。 } else { rear=rear+1; Q[rear]<=x; return1; }}2.刪除：ElemTypeQueueDelete(Q[],front,rear){ if(rear<=front) { printf("Overlow"); return0; } else { front=front+1; }}數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第23頁(yè)。以上為錯(cuò)誤算法,rear<QMAX才能插入，空隊(duì)列：rear=front指針重疊“假滿(mǎn)”∵刪除/插入一次無(wú)事，N次則無(wú)用了。插入滿(mǎn)了只能刪除，rear、front均在尾，插入為滿(mǎn)，刪除為空∴成為了無(wú)用隊(duì)列。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第23頁(yè)。正確的隊(duì)列插入與刪除算法如下：intQueueInsert(Q[],front,rear,x){ if((rear+1)modQMAX=front) { printf("Overlow"); return0; } else { modQMAX數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第24頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第24頁(yè)。 return1; }}ElemTypeQueueDelete(Q[],front,rear){ if(rear<=front) { printf("Overlow"); return0; } else { modQMAX }3.隊(duì)列的應(yīng)用keyboardbuffer32byte如何解決“假滿(mǎn)”？---------還有空的地方卻不能再插入。答：接為環(huán)狀（上彎下彎不同）總結(jié)：優(yōu)點(diǎn)：1.不要求連續(xù)的、大塊的內(nèi)存，充分地利用內(nèi)存空間 2.動(dòng)態(tài)的存儲(chǔ)結(jié)構(gòu)不足：1.空間復(fù)雜度增加數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第25頁(yè)。2.操作（算法）復(fù)雜些數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第25頁(yè)。雙端隊(duì)列：限定插入和刪除操作在表的兩端進(jìn)行的線(xiàn)性表。這兩端分別是端點(diǎn)1和端點(diǎn)2。在實(shí)際使用中，還可以有輸出受限的雙端隊(duì)列（即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許插入的雙端隊(duì)列）和輸入受限的雙端隊(duì)列（即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許刪除的雙端隊(duì)列）。而如果限定雙端隊(duì)列從某個(gè)端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則該雙端隊(duì)列就蛻變成兩個(gè)棧底相鄰接的棧了。鏈隊(duì)列：用鏈表表示的隊(duì)列。-------------------------------------------------------------------------------數(shù)組和廣義表數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第26頁(yè)。從一給定的數(shù)組A[]中刪除元素值在x到y(tǒng)（x≤y）之間的所有元素（假定數(shù)組中有n個(gè)元素）。算法頭部約定如下：數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第26頁(yè)。voidDelete(A[],n,x,y)本題的算法思想是：先將A[]中所有元素值在x≤y之間的元素置成一個(gè)特殊的值（如0），并不立即刪除它們，然后從最后向前依次掃描，對(duì)于該特殊值的元素便移動(dòng)其后面的元素將其刪除，這種算法比每刪除一個(gè)元素后立即移動(dòng)其后元素效率要高一些。實(shí)現(xiàn)本題功能的過(guò)程如下：voidDelete(A[],n,x,y)

{

for(i1;i≤n;i++)if(A[i]≥x&&A[i]≤y)A[i]0;for(in;i≥1;i--)if(A[i]==0){for(kj;k≤(n-1);k++)A[k]A[k+1];nn-1;}}---------------------------------------------------------------------樹(shù)和二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第27頁(yè)。設(shè)一棵Huffman樹(shù)中度為2的節(jié)點(diǎn)數(shù)為n2，則該樹(shù)的總節(jié)點(diǎn)數(shù)為2n2+1數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第27頁(yè)。度的概念：結(jié)點(diǎn)的度指結(jié)點(diǎn)的孩子結(jié)點(diǎn)個(gè)數(shù)，例如度為2就是有2個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)；葉子結(jié)點(diǎn)就是度為0的結(jié)點(diǎn)，沒(méi)有孩子結(jié)點(diǎn)的結(jié)點(diǎn).按照這個(gè)概念，度為2的結(jié)點(diǎn)樹(shù)為n2,即為非葉子結(jié)點(diǎn)，Huffman樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)是非結(jié)點(diǎn)個(gè)數(shù)+1，所以總結(jié)點(diǎn)個(gè)數(shù)：n2+n2+1有一棵非空的二叉樹(shù)（第0層為根結(jié)點(diǎn)），其第i層上至多有2i個(gè)結(jié)點(diǎn)。對(duì)于n個(gè)節(jié)點(diǎn)的滿(mǎn)二叉樹(shù)，設(shè)葉節(jié)點(diǎn)數(shù)為m，分枝節(jié)點(diǎn)數(shù)為k，則n=k+m滿(mǎn)二叉樹(shù)中，除了葉子結(jié)點(diǎn)，就是分支結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第28頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第28頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第29頁(yè)。將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)表示后,該二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第29頁(yè)。已知完全二叉樹(shù)的第八層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是68。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第30頁(yè)。注意是根結(jié)點(diǎn)為第1層，第7層該有26=64個(gè)結(jié)點(diǎn)，第八層有8個(gè)結(jié)點(diǎn)用去第7層的4個(gè)結(jié)點(diǎn)，所以葉子結(jié)點(diǎn)總數(shù)：64-4+8=68。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第30頁(yè)。葉子的帶權(quán)路徑長(zhǎng)度=權(quán)值*路徑長(zhǎng)度數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第31頁(yè)。樹(shù)的帶權(quán)路徑長(zhǎng)度=所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第31頁(yè)。已知某二叉樹(shù)中，有n0個(gè)葉節(jié)點(diǎn)，n1個(gè)度為1的節(jié)點(diǎn)，n2個(gè)度為2的節(jié)點(diǎn)。則：n0=n2+1二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)（數(shù)組形式）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表）來(lái)存儲(chǔ)。高度為k的二叉樹(shù)至多有2^k-1個(gè)節(jié)點(diǎn)。二叉樹(shù)節(jié)點(diǎn)數(shù)目的算法。counter<=0;voidNumbers(NODE*tree)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第32頁(yè)。{數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第32頁(yè)。if(tree){counter++;Numbers(tree->Lsubtree);Numbers(tree->Rsubtree);}}設(shè)二叉樹(shù)的根節(jié)點(diǎn)的指針為tree，每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)為：LsubtreedataRsubtree試寫(xiě)一算法，用于輸出該二叉樹(shù)中最大的節(jié)點(diǎn)值。算法如下：max<=0;voidMaxNode(NODE*tree){if(tree){if(tree->data>max)max<=tree->data;MaxNode(tree->Lsubtree);MaxNode(tree->Rsubtree);}數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第33頁(yè)。}數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第33頁(yè)?；蛘撸簃ax<=0;voidMaxNode(NODE*tree){if(tree){x<=tree->data;y<=MaxNode(tree->Lsubtree);z<=MaxNode(tree->Rsubtree);reyurn(max(x，y，z));}elsereturn(-∞);}---------------------------------------------------------------------圖設(shè)有向圖G有n個(gè)頂點(diǎn)，m條弧，則其鄰接表中鏈上的節(jié)點(diǎn)個(gè)數(shù)為m若一無(wú)向圖是連通的，且其中有n個(gè)頂點(diǎn)和e條邊，則必滿(mǎn)足e≥n-1數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第34頁(yè)。有向圖強(qiáng)連通分量在有向圖G中，如果兩個(gè)頂點(diǎn)vi,vj間（vi<>vj）有一條從vi到vj的有向路徑，同時(shí)還有一條從vj到vi的有向路徑，則稱(chēng)兩個(gè)頂點(diǎn)強(qiáng)連通(stronglyconnected)。如果有向圖G的每?jī)蓚€(gè)頂點(diǎn)都強(qiáng)連通，稱(chēng)G是一個(gè)強(qiáng)連通圖。非強(qiáng)連通圖有向圖的極大強(qiáng)連通子圖，稱(chēng)為強(qiáng)連通分量(stronglyconnectedcomponents)。記主要特征：強(qiáng)聯(lián)通分量圖中兩兩都可達(dá)，也可見(jiàn)下圖實(shí)例。按照這個(gè)定義，得到圖G中的強(qiáng)聯(lián)通分量共3個(gè)：<1,2>,<3,5,6>,<4>數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第34頁(yè)。在一個(gè)有n（n≥1）個(gè)頂點(diǎn)的有向圖中，邊數(shù)最多為n(n-1)帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中第i列非∞且非O的元素個(gè)數(shù)有向圖中，結(jié)點(diǎn)i的入度就是指向i結(jié)點(diǎn)的弧的條數(shù),而鄰接矩陣是行數(shù)據(jù)中非0非無(wú)窮元素個(gè)數(shù)為i的出度，列才為入度有向圖用鄰接矩陣表示后，頂點(diǎn)i的出度等于第i行中非0且非∞的元素個(gè)數(shù)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第35頁(yè)。圖的深度優(yōu)先和廣度優(yōu)先都要弄清楚。深度優(yōu)先為相連訪(fǎng)問(wèn)（注意退回到還有連接結(jié)點(diǎn)沒(méi)有訪(fǎng)問(wèn)過(guò)的那個(gè)結(jié)點(diǎn)上，廣度優(yōu)先為層次訪(fǎng)問(wèn),先訪(fǎng)問(wèn)的結(jié)點(diǎn)其子樹(shù)也先訪(fǎng)問(wèn)（子樹(shù)訪(fǎng)問(wèn)無(wú)次序，僅對(duì)下層訪(fǎng)問(wèn)有影響）數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第35頁(yè)。廣度優(yōu)先和深度優(yōu)先遍歷序列均可能是不唯一的。---------------------------------------------------------------------查找數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第36頁(yè)。折半查找算法。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第36頁(yè)。intBinSearch(sqlistr,intk,intn){low1；highn；find0;while(low≤highandnotfind){mid(low+high)/2;if(k<r[mid].key)highmid-1;elseif(k>r[mid].key)lowmid+1;else{imid;find1;}}if(notfind)i0;return(i);}數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第37頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第37頁(yè)。折半查找法使用于存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)且按關(guān)鍵字排好序的線(xiàn)性表。在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長(zhǎng)度不僅與表的個(gè)數(shù)有關(guān)，而且與每一塊中的元素個(gè)數(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第38頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第38頁(yè)。---------------------------------------------------------------------排序在已知待排序文件已基本有序的前提下，效率最高的排序方法是直接插入排序考排序的效率和特點(diǎn)：數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第39頁(yè)。一、插入排序(InsertionSort)

1.基本思想：

每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。

2.排序過(guò)程：

【示例】：

[初始關(guān)鍵字][49]38659776132749

J=2(38)[3849]659776132749

J=3(65)[384965]9776132749

J=4(97)[38496597]76132749

J=5(76)[3849657697]132749

J=6(13)[133849657697]2749

J=7(27)[13273849657697]49

J=8(49)[1327384949657697]

二、選擇排序

1.基本思想：

每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

2.排序過(guò)程：

【示例】：

初始關(guān)鍵字[4938659776132749]

第一趟排序后13［38659776492749]

第二趟排序后1327［659776493849]

第三趟排序后132738[9776496549]

第四趟排序后13273849[49976576]

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第40頁(yè)。第五趟排序后1327384949[979776]

第六趟排序后132738494976[7697]

第七趟排序后13273849497676[97]

最后排序結(jié)果1327384949767697

三、冒泡排序(BubbleSort)

1.基本思想：

兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。

2.排序過(guò)程：

設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。

【示例】：

4913131313131313

3849272727272727

6538493838383838

9765384949494949

7697654949494949

1376976565656565

2727769776767676

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第41頁(yè)。4949497697979797

四、快速排序（QuickSort）

1.基本思想：

在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?/p>

2.排序過(guò)程：

【示例】：

初始關(guān)鍵字[4938659776132749］

第一次交換后［2738659776134949］

第二次交換后［2738499776136549］

J向左掃描，位置不變，第三次交換后［2738139776496549］

I向右掃描，位置不變，第四次交換后［2738134976976549］

J向左掃描［2738134976976549］

（一次劃分過(guò)程）

初始關(guān)鍵字［4938659776132749］

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第42頁(yè)。一趟排序之后［273813］49［76976549］

二趟排序之后［13］27［38］49［4965］76［97］

三趟排序之后1327384949［65］7697

最后的排序結(jié)果1327384949657697

各趟排序之后的狀態(tài)

五、堆排序(HeapSort)

1.基本思想：

堆排序是一樹(shù)形選擇排序，在排序過(guò)程中，將R[1..N]看成是一顆完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。

2.堆的定義:N個(gè)元素的序列K1,K2,K3,...,Kn.稱(chēng)為堆，當(dāng)且僅當(dāng)該序列滿(mǎn)足特性：

Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

堆實(shí)質(zhì)上是滿(mǎn)足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個(gè)堆，它對(duì)應(yīng)的完全二叉樹(shù)如上圖所示。這種堆中根結(jié)點(diǎn)（稱(chēng)為堆頂）的關(guān)鍵字最小，我們把它稱(chēng)為小根堆。反之，若完全二叉樹(shù)中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱(chēng)之為大根堆。

3.排序過(guò)程：

堆排序正是利用小根堆（或大根堆）來(lái)選取當(dāng)前無(wú)序區(qū)中關(guān)鍵字?。ɑ蜃畲螅┑臄?shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第43頁(yè)。記錄實(shí)現(xiàn)排序的。我們不妨利用大根堆來(lái)排序。每一趟排序的基本操作是：將當(dāng)前無(wú)序區(qū)調(diào)整為一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無(wú)序區(qū)中的最后一個(gè)記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個(gè)記錄區(qū)。

【示例】：對(duì)關(guān)鍵字序列42，13，91，23，24，16，05，88建堆

對(duì)于已排好序的、具有12個(gè)數(shù)據(jù)元素的線(xiàn)性表，采用冒泡排序方法排序時(shí)最少需要11比較。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第39頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第40頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第41頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第42頁(yè)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第43頁(yè)。冒泡排序法：For(i=0;i<n-1;i++)For(j=0;j<n-1-I;j++)If(a[j]>a[j+1]則交換優(yōu)化一下冒泡排序法Intf=0;For(i=0;i<n-1;i++){For(j=0;j<n-1-I;j++)If(a[j]>a[j+1])則{F=1；交換}if(！f)break;//如果第一趟排序，發(fā)現(xiàn)已經(jīng)是有序，則退出了，只比較了第一趟的11次

}只有在初始數(shù)據(jù)為逆序時(shí)，冒泡排序所執(zhí)行的比較次數(shù)最多。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第44頁(yè)。冒泡排序在最壞情況是初始序列為“逆序”，需要進(jìn)行N-1次排序，進(jìn)行的比較次數(shù)為：∑（i-1），下標(biāo)從n到2，即n(n-1)/2.數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-全文共47頁(yè)，當(dāng)前為第44頁(yè)。簡(jiǎn)單選擇排序算法，效率不高voidSelectSort(intr[],intn)

{

for(i1；i≤n-1；i++)

for(ji+1；j≤n；j++)

if(r[j]<r[k