?文章來源地址http://www.zghlxwxcb.cn/news/detail-517510.html

目錄

一、緒論

1.數(shù)據(jù)結構基本概念

2.算法定義與特征

二、線性表

1.線性表的定義

2.順序表的存儲結構

3.鏈式存儲結構

三、棧和隊列

1、棧的基本概念

2.隊列的基本概念

3.循環(huán)隊列?

四、字符串和多維數(shù)組

1.字符串的基本概念

2.串的簡單模式匹配

3.多維數(shù)組

3.1數(shù)組的定義

3.2數(shù)組的特點

3.4數(shù)組的存儲結構與尋址——一維數(shù)組

3.5數(shù)組的存儲結構與尋址——二維數(shù)組

4.矩陣的壓縮存儲

4.1.概念

4.2對稱矩陣

4.3三角矩陣

4.4對角矩陣

?4.5稀疏矩陣

5.廣義表

5.1概念

5.2題目? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

五、樹和二叉樹

1.樹的邏輯結構

1.1樹的基本概念

1.2樹的基本術語

1.3樹的遍歷操作

2.樹的存儲結構

2.1 雙親表示法

2.2孩子表示法

?2.3孩子兄弟表示法

小結

3.二叉樹的邏輯結構

3.1二叉樹基本概念

3.2二叉樹的性質

3.3二叉樹的存儲結構

3.4二叉樹的遍歷

4. 樹、森林與二叉樹的轉換

5.最優(yōu)二叉樹——哈夫曼樹

六、圖

1.圖的定義

2.圖的存儲結構

2.1鄰接矩陣法o(n^2)

2.2鄰接表法o(n+e)

2.2.1鄰接表存儲的基本思想：

2.2.1鄰接表構建

3.圖的遍歷

1.深度優(yōu)先遍歷(dfs)

2.廣度優(yōu)先遍歷（bfs)

4.最小生成樹

1.prim算法

2.Kruskal算法:

5.最短路徑

6.aov網(wǎng)與拓撲排序

1.概念

2.拓撲排序算法

7.關鍵路徑

七、查找

?1.基本概念

2.查找算法的性能

3.順序表查找

4.折半查找

5.二叉排序樹

6.平衡二叉樹

7.散列表查找技術

八、排序

1.選擇排序

2.冒泡排序

3.插入排序

4.快速排序

5.歸并排序

?

一、緒論

1.數(shù)據(jù)結構基本概念

（1）數(shù)據(jù)：對客觀事物的符號表示。（是計算機中可以操作的對象，是能被計算機識別，并 輸入給計算機處理的符號集合。數(shù)據(jù)不僅僅包括整型、實型等數(shù)值類型，還包括字符 及聲音、圖像、視頻等非數(shù)值類型。）

（2）數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位。（人類中，人就是是數(shù)據(jù)元素。）

（3）數(shù)據(jù)項：數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)的最小單位。 但真正討論問題時，數(shù)據(jù)元素才是數(shù)據(jù)結構中建立數(shù)據(jù)模型的著眼點。

（比如人這樣的數(shù)據(jù)元素，可以有眼、耳、鼻、嘴、手、腳這些數(shù)據(jù)項，也可以有姓 名、年齡、性別、出生地址、聯(lián)系電話等數(shù)據(jù)項）

（4）數(shù)據(jù)對象：具有相同性質的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。（比如，還是剛才的 例子，人都有姓名、生日、性別等相同的數(shù)據(jù)項）

（5）數(shù)據(jù)結構：是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。

數(shù)據(jù)結構由邏輯結構和存儲結構（物理結構）和基本操作組成。

邏輯結構：是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系。包括四種結構：集合結構、線性結構、樹形結構、圖形結構。

存儲結構（物理結構）：是指數(shù)據(jù)的邏輯結構在計算機中的存儲形式。有兩種：順序存儲和鏈式存儲。

?

2.算法定義與特征

?

?1.概念：算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列。

2.五個基本特性：輸入、輸出、有窮性、確定性和可行性。

3.什么是好算法：好的算法，應該具有正確性、可讀性、健壯性、高效率和低存儲量的特征。

4.算法分析：目的是分析算法效率以求改進，兩個主要方面是時間性能和空間性能。

常用時間復雜度所耗費的時間從小到大依次是：?

我們所求的時間復雜度一般在沒有特殊說明的情況下，都是指最壞時間復雜度。

二、線性表

1.線性表的定義

（1）線性表：零個或多個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的有限序列。

第一個元素無前驅，最后一個元素無后繼。

2.順序表的存儲結構

? (1)順序表：順序存儲的線性表，其基本思想是用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

（2）特點：隨機存儲，邏輯上相鄰的元素其存儲的物理位置也是相鄰的

（3）設順序表的每個元素占用 c 個存儲單元，則第 i 個元素的存儲地址為：

　　　LOC ( a i ) = LOC ( a 1 ) ＋ ( i － 1 ) × c

（4）順序存儲的實現(xiàn)：一維數(shù)組存儲順序表中的數(shù)據(jù)。

插入操作：o(n)? ? ? 刪除操作：o(n)? ? 按值查找、按位查找

（5）缺點：插入或刪除運算不方便，其效率較低，存儲分配只能預先進行靜態(tài)分配，因此當表長變化較大時，難以確定合適的存儲規(guī)模。

3.鏈式存儲結構

? ?3.1? 鏈式存儲分配的特點：

? 根據(jù)線性表的長度動態(tài)的申請存儲空間，以解決順序存儲中存在的存儲空間難以確定的問題?

3.2? 鏈式存儲結構的實現(xiàn)

? 單鏈表

? 雙向鏈表

? ? ? ? ? 循環(huán)鏈表等??

3.3? ?單鏈表

（1）結點由數(shù)據(jù)域和指針域兩部分組成。

L1,L2是頭指針，也是鏈表的名字，我們設立頭節(jié)點只是為了運算更加方便。

?（2）頭指針和頭節(jié)點的異同

?（3）單鏈表的實現(xiàn)和操作

單鏈表的構造：頭插法和尾插法

支持操作：按值查找、按位查找、刪除操作，插入操作：o(n)?

遍歷

template <typename T>
void LinkList<T>::PrintList()
{

      Node<T>*p=first->next;//工作指針p初始化
      while(p!=nullptr)
      {
          cout<<p->data<<"\t";
          p=p->next;
      }
}

按位查找

template <typename T>
T LinkList<T>::Get(int i)
{
   Node<T>*p=first->next;
   int count=1;
   while(p!=nullptr&&count<i)
   {
      p=p->next;
      count++:
   }
  if(p==nullptr)throw"查找位置錯誤"
  else return p->data;
}

插入操作

template <typename T>
void LinkList<T>::Insert(int i,T x)
{
   Node<T>*p=first->next,*s=nullptr;
   int count=1;
   while(p!=nullptr&&count<i-1)
   {
      p=p->next;
      count++:
   }
  if(p==nullptr)throw"插入位置錯誤";
 else 
  {
    s=new Node<T>;
    s->data=x;
    s->next=p->next;
    p->next=s;
  }
}

刪除操作

T LinkList<T>::Delete(int i)//刪除第i個結點
{ 
   T x;
   Node<T>*p=first->next,q=nullptr;
   int count=1;
  while(p!=nullptr&&count<i-1)
  {
     p=p->next;
     count++;
   }
  if(p==nullptr||p->next==nullptr)throw"刪除位置錯誤"
 else 
  {
    q=p->next;
    x=q->data;
    p->next=q->next;
    delete q;
    return x;
  }
}

3.4雙向鏈表

結點由三部分構成：前驅指針域，數(shù)據(jù)域，后繼指針域。

優(yōu)點：更方便數(shù)據(jù)的插入和刪除

3.5循環(huán)鏈表

特點：首尾相接的鏈表。

優(yōu)點：可以從任一節(jié)點出發(fā)，訪問鏈表中的所有節(jié)點。

判斷循環(huán)鏈表中尾結點：

?????????????????? q->next==first。

3.6循環(huán)雙鏈表

優(yōu)點：刪除最后一個結點或在最后一個結點之后插入結點十分快。o(1)

3.7順序表與單鏈表比較

?若線性表的操作主要是進行查找，很少做插入和刪除時，宜采用順序表做存儲結構。

?

對于頻繁進行插入和刪除的線性表， 宜采用鏈表做存儲結構。

當線性表的長度變化不大， 易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結構。

三、棧和隊列

1、棧的基本概念

（1）棧：只允許在一端進行插入和刪除操作的線性表

（2）空棧：不含任何數(shù)據(jù)元素的棧

（3）棧頂：允許插入和刪除的一端。

插入：入棧、進棧、壓棧

刪除：出棧、彈棧

（4）棧底：另一端。

（5）特性：先進后出

（6）n個不同元素進棧，出棧元素不同排列的個數(shù)為

逐一進行模擬即可。?

鏈棧對比順序棧的優(yōu)點是便于多個棧共享存儲空間和提高效率，且不存在棧滿上溢的情況。

（7）用處：棧能適用于遞歸算法、表達式求值、括號匹配。

（8）兩棧共享空間判滿：top1+1==top2為棧滿

2.隊列的基本概念

(1)隊列：只允許在表的一端插入，另一端刪除的線性表。

允許插入的一端叫隊尾， 允許刪除的一端叫隊頭。

（2）特性：先進先出

(3)隊列的順序存儲

初始狀態(tài)：q.front==q.rear==0

判空操作：q.front==q.rear==0

進隊操作：隊不滿時，先送值到隊尾元素，在將rear++;

出隊操作：隊不空時，先取隊頭元素值，再將front++;

無法判滿，因為會假溢出

3.循環(huán)隊列?

（1）初始：q.front=q.rear=0;

（2）隊首指針進1：q.front=(q.front+1)%maxsize

? ?(3)隊尾指針進1：q.rear=(q.rear+1)%maxsize

（4）隊列長度：(q.rear+maxsize-q,front)%maxsize

? (5)隊空條件：q,front=q,rear=0;

（6）隊滿條件：(q.rear+1)%maxsize==q.front

需要犧牲一個空間，只能存儲maxsize-1個元素

（7）時間復雜度：鏈隊列和循環(huán)隊列都是o(1)

空間復雜度：循環(huán)隊列會產(chǎn)生空間浪費，鏈隊列不會.

四、字符串和多維數(shù)組

1.字符串的基本概念

(1)字符串（簡稱串）：是由零個或多個字符組成的有限序列。

串的長度：串中字符的個數(shù)

子串：字符串中任意個連續(xù)的字符組成的子 序列。

主串：包含子串的串

字符在串中的位置：該字符在串中的序號

子串在主串中的位置以子串的第一個字符在主串中的位置來表示，當兩個串的長度相等且每個對應位置的字符都相等時，稱這兩個串是相等的。

空格串：由一個或多個空格組成的串。

（2）特性：從數(shù)據(jù)結構來看，串是一種特殊的線性表，特殊性體現(xiàn)在數(shù)據(jù)元素可以是一個字符。

2.串的簡單模式匹配

? (1)模式匹配：子串的定位操作，它求的是子串在主串中的位置。

（2）匹配算法：bf算法，kmp算法

kmp算法一般要求求next數(shù)組，在選擇題里

T="abcabc"

next[i]的值表示前0~i個字符串中最大公共前后綴的前綴的最后一個元素的下標，并且規(guī)定next[0]=-1

3.多維數(shù)組

（1）（多維）數(shù)組：線性表中的數(shù)據(jù)元素可以是線性表，但所有元素的類型相同。

（2）廣義表：線性表中的數(shù)據(jù)元素可以是線性表，且元素的類型可以不相同。

3.1數(shù)組的定義

數(shù)組是由一組類型相同的數(shù)據(jù)元素構成的有序集合，每個元素受n(n≥1)個線性關系的約束，并稱該數(shù)組為 n 維數(shù)組。

3.2數(shù)組的特點

（3）二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。

3.4數(shù)組的存儲結構與尋址——一維數(shù)組

Loc(ai)＝Loc(al)＋(i－l)×c

3.5數(shù)組的存儲結構與尋址——二維數(shù)組

（1）按行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。

4.矩陣的壓縮存儲

4.1.概念

(1)壓縮存儲：為多個值相同的元素只分配一個存儲空間，對零元素不分配存儲空間，目的是為了節(jié)省存儲空間。特殊矩陣才能進行壓縮存儲。

（2）特殊矩陣：具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布具有一定的規(guī)律性的矩陣。

常見的特殊矩陣有對稱矩陣、三角矩陣、對角矩陣等。

4.2對稱矩陣

將內存映射到一維數(shù)組?

元素個數(shù)=1+2+...+n=n(n+1)/2

在從0開始的一維數(shù)組中的下標=n(n+1)/r

下三角中的元素aij(i≥j), 在一維數(shù)組中的下標k與i、j的關系為：?

aij是第幾個數(shù)? =1+2+...+（i-1）+j=i(i-1)/2 +j；

由于一維數(shù)組下標從0開始

所以k＝i×(i-1)/2＋j-1

上三角中的元素aij（i＜j），因為aij＝aji，則訪問和它對應的元素aji即可，即：

k＝j×(j-1)/2＋i -1

注意題目要求的是下標還是第幾個值，行優(yōu)先還是列優(yōu)先

4.3三角矩陣

下三角矩陣的壓縮存儲和對稱矩陣類似，不同之處在于除了存儲下三角中的元素個數(shù)，還要存儲對角線上方的常數(shù)，因為是同一個常數(shù)，所以只存儲一個即可。?

（a)? k=n(n+1)/2? ?i>j??

? (b)? k=n+(n-1)+...+(n-i+2)+(j-i+1)-1=(i-1)(2n-i+2)/2 +(j-i)。

4.4對角矩陣

（1）對角矩陣：所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，除了主對角線和它的上下方若干條對角線的元素外，所有其他元素都為零。

（2）

?共有n+n-1+n-1=3n-2個元素

aij序號=前i-1行元素個數(shù)+第i行元素個數(shù)

=2+3（i-2）+j-i+2

=2i+j-2

下標=2i+j-3

?4.5稀疏矩陣

（1）概念：矩陣中非零元素的個數(shù)r遠遠小于矩陣元素個數(shù)s。零元素的分布無規(guī)律

將非零元素及其行和列構成一個三元組（行標、列標、值）

（2）稀疏矩陣的存儲方法：三元組順序表、十字鏈表

?

5.廣義表

5.1概念

廣義表（列表）：? n ( >=0 )個表元素組成的有限序列，記作：

LS = (a0, a1, a2, …, an-1)

? LS是表名，ai是表元素，它可以是表 (稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。

??n為表的長度。n = 0 的廣義表為空表。

長度：廣義表LS中的直接元素的個數(shù)；

深度：廣義表LS中括號的最大嵌套層數(shù)。

表頭：廣義表LS非空時，稱第一個元素為LS的表頭；

表尾：廣義表LS中除表頭外其余元素組成的廣義表

5.2題目? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

A ＝( )? ? ? ? ? ? ? ? 空表 ，長度0，深度1

B ＝(e)? ? ? ? ? ? ? ?只有一個單元素，長度1，深度1

C ＝(a, (b，c，d))? ? 有一個單元素和一個子表，長度2，深度2

D ＝(A, B, C)? ? ? 有三個子表，長度3，深度3

E ＝(a, E)? ? ? ?遞歸表，長度2 ，深度無限

? ? ? ? F ＝(( ))? ? ? 只有一個空表，長度1，深度2

五、樹和二叉樹

1.樹的邏輯結構

1.1樹的基本概念

（1）樹：n（n≥0）個結點的有限集合。

當n=0時，稱為空樹。

樹中的每個元素只可能有一個直接前驅，但可以有多個直接后繼

（2）任意一棵非空樹滿足以下條件：

?有且僅有一個特定的稱為根的結點；

?當n＞1時，除根結點之外的其余結點被分成m（m>0）個互不相交的有限集合T1,T2,… ,Tm，其中每個集合又是一棵樹，并稱為這個根結點的子樹。

（3）樹的定義是采用遞歸方法

1.2樹的基本術語

結點的度：結點所擁有的子樹的個數(shù)。

樹的度：樹中各結點度的最大值。

葉子結點：度為0的結點，也稱為終端結點。

分支結點：度不為0的結點，也稱為非終端結點。

孩子、雙親：樹中某結點子樹的根結點稱為這個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；

兄弟：具有同一個雙親的孩子結點互稱為兄弟。

祖先、子孫：在樹中，如果有一條路徑從結點x到結點y，那么x就稱為y的祖先，而y稱為x的子孫。

路徑：如果樹的結點序列n1, n2, …, nk有如下關系：結點ni是ni+1的雙親（1<=i<k），則把n1, n2, …, nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。

結點所在層數(shù)：根結點的層數(shù)為1；對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層。

樹的深度：樹中所有結點的最大層數(shù)，也稱高度。

層序編號：將樹中結點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。

有序樹、無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。

森林：m (m≥0)棵互不相交的樹的集合

1.3樹的遍歷操作

?

前序遍歷：根左右? ?ABDEHIFCG

后序遍歷：左右根? ?DHIEFBGCA

層序遍歷：自上而下逐層遍歷，在同一層中，按從左到右的順序對結點逐個訪問。ABCDEFGHI

2.樹的存儲結構

2.1 雙親表示法

基本思想：

用一維數(shù)組來存儲樹的各個結點（一般按層序存儲），

數(shù)組中的一個元素對應樹中的一個結點，

每個結點記錄兩類信息：結點的數(shù)據(jù)信息以及該結點的雙親在數(shù)組中的下標。

?

其中data是數(shù)據(jù)域，存儲結點的數(shù)據(jù)信息。而parent是指針域，存儲該結點的雙親在 數(shù)組中的下標。

2.2孩子表示法

這 n 個單鏈表共有 n 個頭指針，這 n 個頭指針又組成了一個線性表。

為了便于進行查找采用順序存儲存儲每個鏈表的頭指針。

最后，將存放 n 個頭指針的數(shù)組和存放n個結點的數(shù)組結合起來，構成孩子鏈表的表頭數(shù)組。

?2.3孩子兄弟表示法

firstchild：指針域，指向該結點第一個孩子；

data：數(shù)據(jù)域，存儲該結點的數(shù)據(jù)信息；

rightsib：指針域，指向該結點的右兄弟結點。

小結

?

順序存儲：本質上是靜態(tài)指針

雙親表示法

雙親、孩子表示法

鏈式存儲：

多重鏈表示法

孩子鏈表表示法

孩子兄弟表示法?

3.二叉樹的邏輯結構

3.1二叉樹基本概念

1.定義：二叉樹是n（n≥0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

2.特點：

⑴ 每個結點最多有兩棵子樹；

⑵ 二叉樹是有序的，其次序不能任意顛倒。

注意：二叉樹和樹是兩種樹結構。

3.幾個特殊的二叉樹：

（1）滿二叉樹

?在一棵二叉樹中，所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上

對于編號為i的結點，他的左孩子為2i，右孩子為2i+1

（2）完全二叉樹

在滿二叉樹的基礎上，在最后一層的葉子結點，從右往左減去一些結點

i<=n/2時，說明該節(jié)點是一個分支節(jié)點

最多只有一個度為1的結點

3.2二叉樹的性質

（1）在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有: n0＝n2＋1。

?證明·：樹中結點數(shù)目=度數(shù)之和+1

n0+n1+n2=0*n0+1*n1+2*n2+1

可得 n0=n2+1

(2)非空二叉樹上第k層上至多有2^（k-1）個結點

(3)高度為h的二叉樹最多有2^h -1個結點。

（4）具有n個結點的完全二叉樹的深度為 log2n? +1。

（5）

?對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結點（簡稱為結點i），有：

（1）如果i＞1，

? 則結點i的雙親結點的序號為 ?i/2；如果i＝1，

? 則結點i是根結點，無雙親結點。

(2)如果2i≤n，

? 則結點i的左孩子的序號為2i；

? 如果2i＞n，則結點i無左孩子。

(3)如果2i＋1≤n，

? 則結點i的右孩子的序號為2i＋1；如果2i＋1＞n，則結點 i無右孩子。

題目1

已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數(shù)最多是(?? )

????? A．39??B.52??C.111??D.119???

解：保證結點最多，說明一共有7層才對，由性質3可以得知，前6層共有結點2^6-1=63個，第6層有2^(6-1)=32個結點，減去8個葉子結點，分支結點還有24個，要保證最多，這24個結點應該全都有兩個孩子，所以最多=前6層+第7層=63+24 x 2=111。本題選c

?

題目2

一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點,10個度為1的結點，則樹T的葉節(jié)點個數(shù)是(?? )

????? A：41?? B：82?? C：113?? D：122

解：葉子結點就是度數(shù)為1的結點，假設有n0個

根據(jù)樹的性質 結點數(shù)=度數(shù)之和+1

n0+20+10+1+10=0 x n0+20x4+10x3+1x2+10x1+1

n0=82

選b

3.3二叉樹的存儲結構

（1）順序存儲

二叉樹的順序存儲結構一般僅存儲完全二叉樹

（2）鏈式存儲

基本思想：令二叉樹的每個結點對應一個鏈表結點，鏈表結點除了存放與二叉樹結點有關的數(shù)據(jù)信息外，還要設置指示左右孩子的指針。

在含有 n個結點的二叉鏈表中，含有n+1個空指針，含有n-1個非空指針。

3.4二叉樹的遍歷

前序遍歷 ：根左右

遞歸算法

void   BiTree::PreOrder(BiNode<T> *root) 
{
        if (root == nullptr)  return;     
        else {
            cout<<root->data;         
            PreOrder(root->lchild );    
            PreOrder( root->rchild);    
        }
 }

中序遍歷：左根右

void BiTree::InOrder (BiNode<T> *root)
{
         if (root== nullptr) 
               return;     
         else {
               InOrder(root->lchild); 
               cout<<root->data; 
               InOrder(root->rchild);
         }
}

后序遍歷：左右根

void BiTree::PostOrder(BiNode<T> *root)
{ 
    if (root== nullptr)
     return; 
    else {
         PostOrder(root->lchild); 
         PostOrder(root->rchild); 
         cout<<root->data;          
    }
}

二叉樹的建立

1.按擴展前序遍歷序列輸入結點的值

2.如果輸入結點值為“#”,則建立一棵空的子樹

3.否則，根結點申請空間，將輸入值寫入數(shù)據(jù)域中，

4.以相同方法的創(chuàng)建根結點的左子樹

5.以相同方法創(chuàng)建根結點的右子樹

遞歸方法

template <class T>
BiNode<T> * BiTree ::Creat(){
     BiNode<T> *root; char ch;
    cin>>ch;
    if (ch=='# ')     root= nullptr; 
    else {
        root=new BiNode<T>; 
        root->data=ch;
        root->lchild=creat(); 
        root->rchild= creat(); 
    }  
  return root
}

求樹結點的數(shù)目

template<class T>
int BiTree<T>::count(BiNode<T>* root){
	int number=0;

	if (root== nullptr)
		number=0;
	else
		number=count(root->lchild)+count(root->rchild)+1;
	return number;
}

求葉子結點數(shù)目

template<typename T> 
void BiTree<T>:: countleaf(BiTreeNode<T> * root){
	if (root) {
		if (root->lchild== nullptr && root->rchild== nullptr)
			leafcount=leafcount+1;
		else
		{
			countleaf(root->lchild);
			countleaf(root->rchild);
		}
	}
	return;
}

1.已知一顆二叉樹的先序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果是（）。

首先構建二叉樹

前序遍歷首先遍歷根節(jié)點，所以A為根節(jié)點，對應中序遍歷，分為CB（左子樹） EDF（右子樹）。前序遍歷根左右，所以V、B是根，C是B的·左子樹，對于EDF，在前序中，D是根，則E是D的左孩子，F(xiàn)是有孩子。所以后序遍歷 CBEFDA

題目

1.某二叉樹結點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其根節(jié)點左子樹的結點數(shù)目為（4）。

后序遍歷最后訪問的是根節(jié)點，前序最先訪問根節(jié)點，我們在遇到這種問題時，首先考慮前序和后續(xù)找到根節(jié)點。

?

注意！由前序和后序遍歷，后序和中序遍歷序列，可以唯一確定一顆二叉樹，但由前序和后序卻不能唯一確定一顆二叉樹，因為他們倆的根節(jié)點不一定相同。

4. 樹、森林與二叉樹的轉換

1.樹轉化為二叉樹

（1）在兄弟結點之間加一條線

（2）對每個結點，只保留他與第一個孩子的連線，抹去與其他孩子的連線。

（3）以樹根為軸心，順時針旋轉45度，

?

?

由樹轉化為二叉樹，其根節(jié)點的右子樹總是空的

2.森林轉化為二叉樹

(1)把森林中的每顆二叉樹轉換成相應的二叉樹

（2）每顆樹的根也可以視為兄弟節(jié)點，在每顆樹的樹根之間加一條連線

（3）以第一顆樹的樹根為根節(jié)點，順時針選擇45度

?轉化為二叉樹，是沒有右兒子的，但是變成森林以后，第二三課樹都成為了第一棵樹的右兒子。D

3.二叉樹轉化為森林或樹

⑴ 加線——若某結點x是其雙親y的左孩子，則把結點x的右孩子、右孩子的右孩子、……，都與結點y用線連起來；

⑵ 去線——刪去原二叉樹中所有的雙親結點與右孩子結點的連線；

⑶ 層次調整——整理由⑴、⑵兩步所得到的樹或森林，使之層次分明。

4.森林的遍歷

森林有兩種遍歷方法：

⑴前序（根）遍歷：前序遍歷森林中的每一棵樹。（一顆一顆來）

⑵后序（根）遍歷：后序遍歷森林中的每一棵樹。 ?

5.最優(yōu)二叉樹——哈夫曼樹

1、葉子結點的權值：對葉子結點賦予的一個有意義的數(shù)值量。

2、二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和。 記為：

lk是從根結點到第k個葉子的路徑長度

wk第k個葉子的權值

3.哈夫曼樹：帶權路徑長度最小的二叉樹。

給定n個權值分別為w1,w2，···，w,的結點，構造哈夫曼樹的算法描述如下!

(1) 將這n 個結點分別作為n棵僅含一個結點的二叉樹，構成森林F

(2)構造一個新結點，從F中選取兩棵根結點權值最小的樹作為新結點的左、右子樹，(小的在左，大的在右），且將新結點的權值置為左、右子樹上根結點的權值之和。

(3)從F中刪除剛才選出的兩棵樹，同時將新得到的樹加入F中。

(4) 重復步驟 (2) 和(3)，直至F中只剩下一棵樹為止。

?

4.哈夫曼樹的特點：

1. 權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。

2. 只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.

?

?1 。對n(n≥2)個權值均不相同的字符構成哈夫曼樹，關于該哈弗曼樹的敘述中，錯誤的是（ ）.

????? A：該樹一定是一棵完全二叉樹

????? B：樹中一定沒有度為1的結點

????? C：樹中兩個權值最小的結點一定是兄弟結點

????? D：樹中任一非葉結點的權值一定不小于下一層任一結點的權值

答：選A，不一定是一顆完全二叉樹

?選D

哈夫曼樹不存在度數(shù)為1的點

選C，10是110的前綴子串，不符合

?

六、圖

1.圖的定義

（1) 有向圖：若E是有向邊(弧) 的有限集合時，則圖G為有向圖?；∈琼旤c的有序對記為<v,w>，其中v,w是頂點，v稱為弧尾，w稱為弧頭，<v,w>稱為從頂點v到頂點w的弧。

(2)無向圖：若E是無向邊 (邊) 的有限集合時，則圖G為無向圖。邊是頂點的無序對記為(v,w)或(w,v)，因為兩者相等，其中v,w是頂點，頂點v,w互為鄰接點。邊(v,w)依附于頂點v,w，或者邊(v,w)和頂點v,w相關聯(lián)。

（3）簡單圖：一個圖G若滿足: 不存在重復邊; 不存在頂點到自身的邊，則稱圖G為簡單圖。

(4)多重圖：若圖G中某兩個結點之間的邊數(shù)多于一條，又允許頂點通過一條邊和自己關聯(lián)，則圖G為多重圖。

（5）完全圖 (簡單完全圖)：對于無向圖，任意兩個頂點之間都存在邊5)對于有向圖，任意兩個頂點之間都存在方向相反的兩條弧。

含有n個頂點的無向完全圖有n×(n-1)/2條邊。

含有n個頂點的有向完全圖有n×(n-1)條邊。

(6) 子圖：若圖G=（V，E），G'=（V'，E'），如果: V'是V?的子集且E' 是 E?的子集，則稱圖G'是G的子圖。

(7)連通、連通圖
在無向圖中，若從頂點v到頂點w有路徑存在，則稱v和w是連通的。

若圖G中任意兩個頂點都是連通的，則稱圖G是連通圖

連通分量：非連通圖的極大連通子圖稱為連通分量。

強連通圖：在有向圖中，對圖中任意一對頂點vi和vj (i≠j)，若從頂點vi到頂點vj和從頂點vj到頂點vi均有路徑，則稱該有向圖是強連通圖。

強連通分量：非強連通圖的極大強連通子圖。

生成樹：n個頂點的連通圖G的生成樹是包含G中全部頂點的一個極小連通子圖。

（點不變，邊是n-1條，還連通）

（8）稀疏圖：稱邊數(shù)很少的圖為稀疏圖；

? ? ? ?稠密圖：稱邊數(shù)很多的圖為稠密圖。

（9）頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD (v)。

?

? ? ? ? ?頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID (v)；

? ? ? ? ?頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD (v)。

?

（10）權：是指對邊賦予的有意義的數(shù)值量。

? ? ? ? ? 網(wǎng)：邊上帶權的圖，也稱網(wǎng)圖。

?

（11）回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。

? ? ? ? ? ?簡單路徑：序列中頂點不重復出現(xiàn)的路徑。

? ? ? ? ? ?簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復出現(xiàn)的回路。

?1.一個n個頂點的連通無向圖，其邊的個數(shù)至少為(n-1)條

?2.要連通具有n個頂點的有向圖，至少需要（? n? ）條邊

?3.無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的兩倍。

?

若無向圖G=(V,E)中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是

( )

????? A ：6?? B：15? C：16?? D：21

分析：要想保證在任何情況下都連通，其中6個頂點組成完全圖。包含6個頂點的完全圖中包含6*5/2=15個條邊。第7個頂點和其他6個頂點之間有一條邊，就能保證圖是聯(lián)通的。因此，至少需要16條邊

2.圖的存儲結構

2.1鄰接矩陣法o(n^2)

2.1.1基本思想：

（1）用一個一維數(shù)組存儲圖中頂點的信息

（2）用一個二維數(shù)組（稱為鄰接矩陣）存儲圖中各頂點之間的鄰接關系。

?

假設圖G＝(V，E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：

?

2.1.2無向圖的鄰接矩陣的特點？

（1）主對角線為 0 且一定是對稱矩陣。

（2）頂點i的度數(shù)=鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。

（3）求頂點 i 的所有鄰接點，將數(shù)組中第 i 行元素掃描一遍，若arc[i][j]為1，則頂點 j 為頂點 i 的鄰接點。

2.1.3有向圖鄰接矩陣

（1）有向圖的鄰接矩陣不一定對稱。

（2）頂點 i 的出度=鄰接矩陣的第 i 行元素之和。

（3）頂點 i 的入度=鄰接矩陣的第 i 列元素之和。

2.1.4

?

創(chuàng)建無向圖鄰接矩陣代碼

1.確定圖的頂點個數(shù)和邊的個數(shù)；

2.輸入頂點信息存儲在一維數(shù)組vertex中；

3.初始化鄰接矩陣；

4.依次輸入每條邊存儲在鄰接矩陣arc中；

???? 4.1 輸入邊依附的兩個頂點的序號i, j；

???? 4.2 將鄰接矩陣的第i行第j列的元素值置為1；

???? 4.3 將鄰接矩陣的第j行第i列的元素值置為1；

template <class T>
MGraph::MGraph(T a[ ], int n, int e) {
    vertexNum=n; arcNum=e;
    for (i=0; i<vertexNum; i++) 
        vertex[i]=a[i];
    for (i=0; i<vertexNum; i++)    //初始化鄰接矩陣
	   for (j=0; j<vertexNum; j++)
           arc[i][j]=0;             
    for (k=0; k<arcNum; k++) {
        cin>>i>>j;     //邊依附的兩個頂點的序號
        arc[i][j]=1;  arc[j][i]=1;  //置有邊標志    
    }
}

2.2鄰接表法o(n+e)

2.2.1鄰接表存儲的基本思想：

對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表）

所有邊表的頭指針和存儲頂點信息的一維數(shù)組構成了頂點表。

2.2.1鄰接表構建

vertex：數(shù)據(jù)域，存放頂點信息。

firstedge：指針域，指向邊表中第一個結點。

adjvex：鄰接點域，邊的終點在頂點表中的下標。

next：指針域，指向邊表中的下一個結點。

有向圖構建步驟

?

1. 確定圖的頂點個數(shù)和邊的個數(shù)；

?

2. 輸入頂點信息，初始化該頂點的邊表；

3. 依次輸入邊的信息并存儲在邊表中；

? ? ?3.1? 輸入邊所依附的兩個頂點的序號i和j；

???? 3.2? 生成鄰接點序號為j的邊表結點s；

? ? ?3.3 將結點s插入到第i個邊表的頭部；

template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{   
    vertexNum=n; arcNum=e; 
    for (int i=0; i<vertexNum; i++)   
    {
       adjlist[i].vertex=a[i];
       adjlist[i].firstedge= NULL; //初始化鏈表頭     
    } 
   
     for (int k=0; k<arcNum; k++)   
     {
         cin>>i>>j; //輸入i-j這條邊   
         s=new ArcNode;
         s->adjvex=j;  	        
         s->next=adjlist[i].firstedge; //頭插法
         adjlist[i].firstedge=s;
     }
}

3.圖的遍歷

1.深度優(yōu)先遍歷(dfs)

深度優(yōu)先遍歷（Depth_First_Search），也有稱為深度優(yōu)先搜索，簡稱為DFS。

類似前序遍歷

數(shù)據(jù)結構：stack
優(yōu)勢：空間:o(h)
劣勢：不具最短路
每一個dfs對應一個樹
重要：順序（暴搜）
知識點：
{
回溯：往回走的過程，記得恢復現(xiàn)場
遞歸：同上
剪枝：提前判斷，不合適直接跳過
}

基本思想：

⑴ 訪問頂點v；

⑵ 從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；

⑶ 重復上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。

鄰接矩陣dfs

int visited[MaxSize];
template <class T>
void MGraph::DFSTraverse(int v){
     cout<<vertex[v]; 
     visited [v]=1;
     for (j=0; j<vertexNum; j++)
         if (arc[v][j]==1 && visited[j]==0)
            DFSTraverse( j );
}

?

2.廣度優(yōu)先遍歷（bfs)

類似層序遍歷

數(shù)據(jù)結構：隊列

缺點：空間:o(2^h)
優(yōu)點:具有最短路性質
但是只有當所有的邊權都一樣時，才能用bfs求最短路

?

?

基本思想：

⑴ 訪問頂點v；

⑵ 依次訪問v的各個未被訪問的鄰接點v1, v2, …, vk；

⑶ 分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。

鄰接矩陣bfs

int visited[MaxSize];
template <class T>
void MGraph::BFSTraverse(int v){     
    front=rear=-1;   //假設采用順序隊列且不會發(fā)生溢出
   int Q[MaxSize]; cout<<vertex[v]; visited[v]=1;  Q[++rear]=v; 
    while (front!=rear)    {
         v=Q[++front];   
         for (j=0; j<vertexNum; j++)
            if (arc[v][j]==1 && visited[j]==0 ) {
                  cout<<vertex[j]; visited[j]=1; Q[++rear]=j;
            }
      }
}

4.最小生成樹

所謂的最小成本，就是n個頂點，用n-1條邊把 一個連通圖連接起來，并且使得權值的和最小。

最小生成樹不一定唯一

1.prim算法

時間復雜度o(n^2)

（1）任取一頂點(或題中已告知頂點)，去所有邊
（2）選擇一個與當前頂點集合距離最近的頂點，并將該頂點和相應的邊加入進來，同時不形成回路
（3)? ?重復2，直至圖中所有頂點都并入。

2.Kruskal算法:

時間復雜度 o(eloge)

（1）去掉所有邊
（2）選邊(權最小，且不構成回路)

（3）一直重復第（2）步，直至圖中所有頂點都并入

5.最短路徑

1.dijkstra算法

基本思想：

1. 設置一個集合 S 存放已經(jīng)找到最短路徑的頂點 ， S 的初始狀態(tài)只包含源點 v ，

2. 對 v i ∈ V - S ，假設從源點 v 到 v i 的有向邊為最短路徑（從 v 到其余頂點的最短路徑的初值）。

3. 以后每求得一條最短路徑 v , …, v k ，就將 v k 加入集合 S 中，并將路徑 v , …, v k , v i 與原來的假設相比較，取路徑長度較小者為最短路徑。

重復上述過程，直到集合V中全部頂點加入到集合S中。

6.aov網(wǎng)與拓撲排序

1.概念

1.AOV網(wǎng)：在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系，這樣 的有向圖為頂點表示活動的網(wǎng)，我們稱為AOV網(wǎng)（ActivityOn Vertex Network）。 AOV網(wǎng)中的弧表示活動之間存在的某種制約關系。

2.設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列v1，v2，……，vn，滿足若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。則我們稱這樣的頂 點序列為一個拓撲序列。

2.拓撲排序算法

時間復雜度：O(n+e)

對AOV網(wǎng)進行拓撲排序

基本思路是：

（1）從AOV網(wǎng)中選擇一個入度為0的頂點輸出，然后刪去此頂點，并刪除以此頂點為尾的弧。

（2）繼續(xù)重復（1）步驟，直到輸出全部頂點或者 AOV網(wǎng)中不存在入度為0的頂點為止。

7.關鍵路徑

1.AOE網(wǎng)：在一個表示工程的帶權有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權值表示活動的持續(xù)時間，稱這樣的有向圖叫做邊表示活動的網(wǎng)，簡稱AOE網(wǎng)。

2.AOE網(wǎng)中沒有入邊的頂點稱為始點（或源點），沒有出邊的頂點稱為終點（或匯點）。

始點：該頂點所代表的事件無任何先決條件，可首先開始。

終點：表示一項工程的結束。

正常的AOE網(wǎng)只有一個始點和一個終點。

3.AOE網(wǎng)的性質：

⑴ 只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各活動才能開始；

⑵ 只有在進入某頂點的各活動都結束，該頂點所代表的事件才能發(fā)生。

4.關鍵路徑：

在AOE網(wǎng)中，從始點到終點具有最大路徑長度（該路徑上的各個活動所持續(xù)的時間之和）的路徑稱為關鍵路徑。

關鍵活動：關鍵路徑上的活動稱為關鍵活動。

計算描述

⑴ 事件的最早發(fā)生時間ve[k]

ve[1]=0

ve[k]=max{ve[j]+len<vj, vk>} (<vj, vk>∈p[k])??????????????????????

p[k]表示所有到達vk的有向邊的集合

?

⑵ 事件的最遲發(fā)生時間vl[k]

?

vl[n]=ve[n]

vl[k]=min{vl[j]-len<vk , vj>}（<vk, vj>∈s[k]）

s[k]為所有從vk發(fā)出的有向邊的集合

⑶ 活動的最早開始時間e[i]

?

若活動ai是由弧<vk , vj>表示，則活動ai的最早開始時間應等于事件vk的最早發(fā)生時間。因此，有：

?????? e[i]=ve[k]???????????????????????????????????????????

⑷ 活動的最晚開始時間l[i]

?

活動ai的最晚開始時間是指，在不推遲整個工期的前提下， ai必須開始的最晚時間。

若ai由弧<vk，vj>表示，

則ai的最晚開始時間要保證事件vj的最遲發(fā)生時間不拖后。

因此，有：????? l[i]=vl[j]-len<vk, vj>? ?

七、查找

?1.基本概念

列表：由同一類型的數(shù)據(jù)元素組成的集合。

關鍵碼：數(shù)據(jù)元素中的某個數(shù)據(jù)項，可以標識列表中的一個或一組數(shù)據(jù)元素。

鍵值：關鍵碼的值。

主關鍵碼：可以唯一地標識一個記錄的關鍵碼。

次關鍵碼：不能唯一地標識一個記錄的關鍵碼。 ? ? ? ? ?

靜態(tài)查找 ：不涉及插入和刪除操作的查找 。

動態(tài)查找 ：涉及插入和刪除操作的查找。

?線性表：適用于靜態(tài)查找，主要采用順序查找技術、折半查找技術。

樹表：適用于動態(tài)查找，主要采用二叉排序樹的查找技術。

散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術

2.查找算法的性能

查找頻率與算法無關，取決于具體應用

平均查找長度：將查找算法進行的關鍵碼的比較次數(shù)的數(shù)學期望值定義為平均查找長度。計算公式為：

? ? ? ? ? ? n：問題規(guī)模，查找集合中的記錄個數(shù)；

???????? ???pi：查找第i個記錄的概率；

??????????? ci：查找第i個記錄所需的關鍵碼的比較次數(shù)。

也可以計算為=總查找次數(shù)/n

3.順序表查找

（1）優(yōu)點

算法簡單而且使用面廣。

對表中記錄的存儲結構沒有任何要求，順序存儲和鏈接存儲均可；

4.折半查找

（1）適用條件：

int BinSearch(int a[],int n,int k)
{

    int l=1,r=n;
    int mid=l+r>>1;
   while(l<=r)
   {
     if(a[mid]>k)r=mid-1;
     else if(a[mid]<k)l=mid+1;
     else return mid;
   }
return 0;
}

6.平衡二叉樹

1.平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質的二叉排序樹：

⑴ 根結點的左子樹和右子樹的深度最多相差1;

⑵ 根結點的左子樹和右子樹也都是平衡二叉樹。

void select(int n,int a[])
{
	int min=0;
	for(int i=0;i<n-1;i++)
	{
		min=i;
		for(int j=i+1;j<n;j++)
		{
			if(a[j]<a[min])
			{
				min=j;
			}
		}
		if(i!=min)
		{
			int t=a[i];
			a[i]=a[min];
			a[min]=t;
		}
	}
	for(int i=0;i<n;i++) cout<<a[i]<<" ";
	cout<<endl;
}

#include<iostream>
using namespace std;
int main()
{
  int a[5]={3,2,7,4,1};
  for(int i=0;i<5;i++)
  {
  	for(int j=0;j<5-i-1;j++)
  	{
  		if(a[j+1]<a[j])
  		{
  			int t=a[j+1];
  			a[j+1]=a[j];
  			a[j]=t;
		  }
	  }
  }
  for(int i=0;i<5;i++)cout<<a[i]<<" ";
}

#include<iostream>
using namespace std;
int main()
{
    int a[5]={4,2,8,1,0};
    for(int i=0;i<5-1;i++)
    {
        int end=i;//記錄最后一個有序元素的下標
        int t=a[end+1];//待插入元素
        while(end>=0)
        {
            if(t<a[end])//
            {
                a[end+1]=a[end];
                end--;
            }
            else break;//找到第一個小于他的數(shù)，停止循環(huán)
        }
        a[end+1]=t;
    }
    for(int i=0;i<5;i++)cout<<a[i]<<" ";
}

void quick_sort(int q[],int l,int r)
{
    if(l>=r)return;
    int i=l-1,j=r+1,x=q[(l+r)/2];
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
        else break;
    }
    quick_sort(q,l,j),quick_sort(q,j+1,r);
}

void merge_sort(int a[],int l,int r)
{
  if(l>=r)return;
  int temp[10000],mid=(l+r)/2;//向下取整
   merge_sort(a,l,mid);
   merge_sort(a,mid+1,r);
   int i=l,j=mid+1,k=0;
   while(i<=mid&&j<=r)
   {
       if(a[i]<a[j])
       {
           temp[k++]=a[i++];
       }
       else
       {
           temp[k++]=a[j++];
       }
   }
   while(i<=mid)
   {
       temp[k++]=a[i++];
   }
   while(j<=r)
   {
       temp[k++]=a[j++];
   }
   for(int i=l,j=0;i<=r;i++,j++)
   {
       a[i]=temp[j];
   }
}

?

到了這里，關于數(shù)據(jù)結構筆記（c++版，期末復習）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！