數(shù)據(jù)結構知識點總結-

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

{

intn=0;

p<=head;

while(p!=NULL)

{

if(p->data=x)數(shù)據(jù)結構知識點總結-全文共47頁，當前為第17頁。n<=n+1;

p<=p->next;

}

return(n);

}

數(shù)據(jù)結構知識點總結-全文共47頁，當前為第17頁。-------------------------------------------------------------------------------棧和隊列棧：限定僅在表尾進行插入或刪除棧：是限定僅在表尾進行插入或刪除操作的線性表表尾（棧頂）表頭（棧底）假設棧S=（a1，a2，…，an），則稱a1為棧底元素，an為棧頂元素。棧中元素按a1，a2，…，an的次序進棧，退棧的第一元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧又稱為后進后出的線性表。壓棧算法：intPushStack(s[],top,x){ if(top>=SMAX) { printf("overlow");數(shù)據(jù)結構知識點總結-全文共47頁，當前為第18頁。 return0;數(shù)據(jù)結構知識點總結-全文共47頁，當前為第18頁。 } 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ù)結構知識點總結-全文共47頁，當前為第19頁。 returny;數(shù)據(jù)結構知識點總結-全文共47頁，當前為第19頁。 }作業(yè)2：為了節(jié)省空間，兩個棧共享一段內存，寫出這兩個棧的壓棧及出棧算法。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)地內存空間時，應將兩棧的棧底，分別設在這片內存空間的兩端，這樣，當兩個棧的棧頂在棧空間的某一位置相遇時，才會產生上溢。兩個棧共享空間的條件：兩棧頂指針值相減的絕對值為1（兩棧頂指針相鄰）數(shù)組Q[0..n-1]作為一個環(huán)形隊列，f為當前隊頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)總小于n，計算隊列中元素個數(shù)的公式是(n+r-f)mod隊列特點：先進先出，隊頭出，隊尾進，當隊尾大于隊頭時，說明進的比出的多，此時元素個數(shù)為Rear–Front循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是(rear-front+m)MODm循環(huán)隊列兩指針front指示隊列頭元素位置rear指示隊列尾元素位置初始化建空隊列時，令front=rear=0，插入新的尾元素->尾指針+1；刪除隊列頭元素->頭指針+1數(shù)據(jù)結構知識點總結-全文共47頁，當前為第20頁。頭指針始終指向隊列頭元素數(shù)據(jù)結構知識點總結-全文共47頁，當前為第20頁。尾指針始終指向隊列尾指針的下一個位置在棧滿的情況下，不能作進棧運算，否則產生“上溢”。隊列：1.什么是隊列？也是一種特殊的線性表（插入在表的一端，刪除在表的另一端）隊列：先進先出數(shù)據(jù)結構知識點總結-全文共47頁，當前為第21頁。區(qū)別于線性表：插入、刪除在同一端。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第21頁。2.隊列的操作：1.插入。判別隊列空間“空”或“滿”a.另設一個標志位以區(qū)別隊列“空”或“滿”b.少用一個元素空間，約定以“隊列頭指針在隊列尾指針的下一個位置（指環(huán)狀的下一位置）”上作為隊列呈“滿”狀態(tài)的標志總結：若Rear>Front，元素個數(shù)為Rear-Front；若Rear<Front，元素個數(shù)為(Rear-Front+N)%N(N為隊列容量)如何判斷其滿？intQueueInsert(Q[],front,rear,x){ if(rear>=QMAX) { printf("Overlow");數(shù)據(jù)結構知識點總結-全文共47頁，當前為第22頁。 return0;數(shù)據(jù)結構知識點總結-全文共47頁，當前為第22頁。 } 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ù)結構知識點總結-全文共47頁，當前為第23頁。以上為錯誤算法,rear<QMAX才能插入，空隊列：rear=front指針重疊“假滿”∵刪除/插入一次無事，N次則無用了。插入滿了只能刪除，rear、front均在尾，插入為滿，刪除為空∴成為了無用隊列。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第23頁。正確的隊列插入與刪除算法如下：intQueueInsert(Q[],front,rear,x){ if((rear+1)modQMAX=front) { printf("Overlow"); return0; } else { modQMAX數(shù)據(jù)結構知識點總結-全文共47頁，當前為第24頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第24頁。 return1; }}ElemTypeQueueDelete(Q[],front,rear){ if(rear<=front) { printf("Overlow"); return0; } else { modQMAX }3.隊列的應用keyboardbuffer32byte如何解決“假滿”？---------還有空的地方卻不能再插入。答：接為環(huán)狀（上彎下彎不同）總結：優(yōu)點：1.不要求連續(xù)的、大塊的內存，充分地利用內存空間 2.動態(tài)的存儲結構不足：1.空間復雜度增加數(shù)據(jù)結構知識點總結-全文共47頁，當前為第25頁。2.操作（算法）復雜些數(shù)據(jù)結構知識點總結-全文共47頁，當前為第25頁。雙端隊列：限定插入和刪除操作在表的兩端進行的線性表。這兩端分別是端點1和端點2。在實際使用中，還可以有輸出受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許插入的雙端隊列）和輸入受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許刪除的雙端隊列）。而如果限定雙端隊列從某個端點插入的元素只能從該端點刪除，則該雙端隊列就蛻變成兩個棧底相鄰接的棧了。鏈隊列：用鏈表表示的隊列。-------------------------------------------------------------------------------數(shù)組和廣義表數(shù)據(jù)結構知識點總結-全文共47頁，當前為第26頁。從一給定的數(shù)組A[]中刪除元素值在x到y(tǒng)（x≤y）之間的所有元素（假定數(shù)組中有n個元素）。算法頭部約定如下：數(shù)據(jù)結構知識點總結-全文共47頁，當前為第26頁。voidDelete(A[],n,x,y)本題的算法思想是：先將A[]中所有元素值在x≤y之間的元素置成一個特殊的值（如0），并不立即刪除它們，然后從最后向前依次掃描，對于該特殊值的元素便移動其后面的元素將其刪除，這種算法比每刪除一個元素后立即移動其后元素效率要高一些。實現(xiàn)本題功能的過程如下：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ù)據(jù)結構知識點總結-全文共47頁，當前為第27頁。設一棵Huffman樹中度為2的節(jié)點數(shù)為n2，則該樹的總節(jié)點數(shù)為2n2+1數(shù)據(jù)結構知識點總結-全文共47頁，當前為第27頁。度的概念：結點的度指結點的孩子結點個數(shù)，例如度為2就是有2個孩子結點的結點；葉子結點就是度為0的結點，沒有孩子結點的結點.按照這個概念，度為2的結點樹為n2,即為非葉子結點，Huffman樹中葉子結點個數(shù)是非結點個數(shù)+1，所以總結點個數(shù)：n2+n2+1有一棵非空的二叉樹（第0層為根結點），其第i層上至多有2i個結點。對于n個節(jié)點的滿二叉樹，設葉節(jié)點數(shù)為m，分枝節(jié)點數(shù)為k，則n=k+m滿二叉樹中，除了葉子結點，就是分支結點。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第28頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第28頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第29頁。將一棵樹轉換為二叉樹表示后,該二叉樹的根結點沒有右子樹。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第29頁。已知完全二叉樹的第八層有8個結點，則其葉子結點數(shù)是68。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第30頁。注意是根結點為第1層，第7層該有26=64個結點，第八層有8個結點用去第7層的4個結點，所以葉子結點總數(shù)：64-4+8=68。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第30頁。葉子的帶權路徑長度=權值*路徑長度數(shù)據(jù)結構知識點總結-全文共47頁，當前為第31頁。樹的帶權路徑長度=所有葉子結點的帶權路徑長度之和數(shù)據(jù)結構知識點總結-全文共47頁，當前為第31頁。已知某二叉樹中，有n0個葉節(jié)點，n1個度為1的節(jié)點，n2個度為2的節(jié)點。則：n0=n2+1二叉樹采用順序存儲結構（數(shù)組形式）和鏈式存儲結構（二叉鏈表）來存儲。高度為k的二叉樹至多有2^k-1個節(jié)點。二叉樹節(jié)點數(shù)目的算法。counter<=0;voidNumbers(NODE*tree)數(shù)據(jù)結構知識點總結-全文共47頁，當前為第32頁。{數(shù)據(jù)結構知識點總結-全文共47頁，當前為第32頁。if(tree){counter++;Numbers(tree->Lsubtree);Numbers(tree->Rsubtree);}}設二叉樹的根節(jié)點的指針為tree，每個節(jié)點的結構為：LsubtreedataRsubtree試寫一算法，用于輸出該二叉樹中最大的節(jié)點值。算法如下：max<=0;voidMaxNode(NODE*tree){if(tree){if(tree->data>max)max<=tree->data;MaxNode(tree->Lsubtree);MaxNode(tree->Rsubtree);}數(shù)據(jù)結構知識點總結-全文共47頁，當前為第33頁。}數(shù)據(jù)結構知識點總結-全文共47頁，當前為第33頁?；蛘撸簃ax<=0;voidMaxNode(NODE*tree){if(tree){x<=tree->data;y<=MaxNode(tree->Lsubtree);z<=MaxNode(tree->Rsubtree);reyurn(max(x，y，z));}elsereturn(-∞);}---------------------------------------------------------------------圖設有向圖G有n個頂點，m條弧，則其鄰接表中鏈上的節(jié)點個數(shù)為m若一無向圖是連通的，且其中有n個頂點和e條邊，則必滿足e≥n-1數(shù)據(jù)結構知識點總結-全文共47頁，當前為第34頁。有向圖強連通分量在有向圖G中，如果兩個頂點vi,vj間（vi<>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(stronglyconnected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量(stronglyconnectedcomponents)。記主要特征：強聯(lián)通分量圖中兩兩都可達，也可見下圖實例。按照這個定義，得到圖G中的強聯(lián)通分量共3個：<1,2>,<3,5,6>,<4>數(shù)據(jù)結構知識點總結-全文共47頁，當前為第34頁。在一個有n（n≥1）個頂點的有向圖中，邊數(shù)最多為n(n-1)帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中第i列非∞且非O的元素個數(shù)有向圖中，結點i的入度就是指向i結點的弧的條數(shù),而鄰接矩陣是行數(shù)據(jù)中非0非無窮元素個數(shù)為i的出度，列才為入度有向圖用鄰接矩陣表示后，頂點i的出度等于第i行中非0且非∞的元素個數(shù)。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第35頁。圖的深度優(yōu)先和廣度優(yōu)先都要弄清楚。深度優(yōu)先為相連訪問（注意退回到還有連接結點沒有訪問過的那個結點上，廣度優(yōu)先為層次訪問,先訪問的結點其子樹也先訪問（子樹訪問無次序，僅對下層訪問有影響）數(shù)據(jù)結構知識點總結-全文共47頁，當前為第35頁。廣度優(yōu)先和深度優(yōu)先遍歷序列均可能是不唯一的。---------------------------------------------------------------------查找數(shù)據(jù)結構知識點總結-全文共47頁，當前為第36頁。折半查找算法。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第36頁。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ù)結構知識點總結-全文共47頁，當前為第37頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第37頁。折半查找法使用于存儲結構為順序存儲且按關鍵字排好序的線性表。在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表的個數(shù)有關，而且與每一塊中的元素個數(shù)有關。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第38頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第38頁。---------------------------------------------------------------------排序在已知待排序文件已基本有序的前提下，效率最高的排序方法是直接插入排序考排序的效率和特點：數(shù)據(jù)結構知識點總結-全文共47頁，當前為第39頁。一、插入排序(InsertionSort)

1.基本思想：

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

2.排序過程：

【示例】：

[初始關鍵字][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ù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

2.排序過程：

【示例】：

初始關鍵字[4938659776132749]

第一趟排序后13［38659776492749]

第二趟排序后1327［659776493849]

第三趟排序后132738[9776496549]

第四趟排序后13273849[49976576]

數(shù)據(jù)結構知識點總結-全文共47頁，當前為第40頁。第五趟排序后1327384949[979776]

第六趟排序后132738494976[7697]

第七趟排序后13273849497676[97]

最后排序結果1327384949767697

三、冒泡排序(BubbleSort)

1.基本思想：

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

2.排序過程：

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

【示例】：

4913131313131313

3849272727272727

6538493838383838

9765384949494949

7697654949494949

1376976565656565

2727769776767676

數(shù)據(jù)結構知識點總結-全文共47頁，當前為第41頁。4949497697979797

四、快速排序（QuickSort）

1.基本思想：

在當前無序區(qū)R[1..H]中任取一個數(shù)據(jù)元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。

2.排序過程：

【示例】：

初始關鍵字[4938659776132749］

第一次交換后［2738659776134949］

第二次交換后［2738499776136549］

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

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

J向左掃描［2738134976976549］

（一次劃分過程）

初始關鍵字［4938659776132749］

數(shù)據(jù)結構知識點總結-全文共47頁，當前為第42頁。一趟排序之后［273813］49［76976549］

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

三趟排序之后1327384949［65］7697

最后的排序結果1327384949657697

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

五、堆排序(HeapSort)

1.基本思想：

堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。

2.堆的定義:N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：

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

堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。

3.排序過程：

堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關鍵字小（或最大）的數(shù)據(jù)結構知識點總結-全文共47頁，當前為第43頁。記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區(qū)調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。

【示例】：對關鍵字序列42，13，91，23，24，16，05，88建堆

對于已排好序的、具有12個數(shù)據(jù)元素的線性表，采用冒泡排序方法排序時最少需要11比較。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第39頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第40頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第41頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第42頁。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第43頁。冒泡排序法：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ù)為逆序時，冒泡排序所執(zhí)行的比較次數(shù)最多。數(shù)據(jù)結構知識點總結-全文共47頁，當前為第44頁。冒泡排序在最壞情況是初始序列為“逆序”，需要進行N-1次排序，進行的比較次數(shù)為：∑（i-1），下標從n到2，即n(n-1)/2.數(shù)據(jù)結構知識點總結-全文共47頁，當前為第44頁。簡單選擇排序算法，效率不高voidSelectSort(intr[],intn)

{

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

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

if(r[j]<r[k