宗合久久92,伊人九九九精品一本色,zzyow亚洲

參考書：《數據結構（C語言版）》，嚴蔚敏、吳偉民編著

1 線性表

1.1 順序存儲結構

只要確定了線性表的起始位置，線性表中的任一數據元素都可以隨機存取，因此線性表的順序存儲結構是一種隨機存取的存取結構。

1.2 鏈式線性表

單鏈表是非隨機存取的存儲結構

2 棧和隊列

2.1 棧

棧，后進先出（last in first out，LIFO）

2.2 隊列

隊列，先進先出（first in first out，FIFO），在隊頭刪除數據，隊尾插入數據。
雙端隊列：兩端都可以插入刪除
輸出受限的雙端隊列：一個端點允許插入刪除，另一個端點只允許插入
輸入受限的雙端隊列：一個端點允許插入刪除，另一個端點只允許刪除

3 串

3.1 串的表示和實現

定長順序表示：類似數組
堆分配存儲：使用malloc和free進行動態(tài)分配內存
塊鏈存儲表示：類似線性表的鏈式存儲結構，但每個結點可以存儲一個或多個字符

3.2 串的模式匹配算法

求子串的位置Index（S,T,pos）:
返回子串T在主串S中第pos個字符之后的位置，若不存在則返回0
經典算法：

int Index(sstring S,sstirng T,int pos){//時間復雜度O（m*n）
  i=pos; j=1;
  while(i<=s[0]&&j<=T[0]){
    if(s[i]==T[j]){
      ++i;++j;
    }
    else{
      i=i-j+2;j=1;
    }
  }
  if(j>T[0])
    return i-T[0];
  else
    return 0;
}

KMP算法：

int Insex_KMP(sstring S,sstring T,int pos){//時間復雜度O（m+n）
  i=pos;j=1;
  while(i<=s[0]&&j<=T[0]){
    if(j==0||s[i]==T[i]){
      ++i;++j;
    }
    else j=next[j];
  }
  if(j>T[0])
    return i-T[0];
  else 
    return 0;
}

void get_next(sstring T,int next[]){//時間復雜度O（m）
   i=1;next[0]=1;
  while(i<T[0]){
    if(j==0||T[i]==T[j]){
      ++i;++j;
      next[i]=j;
    }
    else 
      j=next[j];
  }
}

void get_nextval(sstring T,int nextval[]){
  i=1;nextval[1]=0;j=0;
  while(i<T[0]){
    if(j==0||T[i]==T[j]){
      ++i;++j;
      if(T[i]!=T[j])
        nextval[i]=j;
      else
        nextval[i]=nextval[j];
    }
    else 
      j=nextval[j];
  }
}

KMP算法僅當子串與主串之間存在許多部分匹配的情況下才比經典算法快很多，其最大的特點是主串指針不需回溯，可以邊讀入邊匹配

4 數組和廣義表

4.1 稀疏矩陣的壓縮

稀疏矩陣：矩陣中非零元素的分布不規(guī)律
壓縮方法：
1.三元順序表

2.行邏輯鏈接的順序表

3.十字鏈表
矩陣的非零元個數和位置變化較大時通常使用十字鏈表。
十字鏈表中，每個非零元可用一個含5個元素的節(jié)點表示，其中i,j,e分別表示該元素所在的行，列和值，向右域right用以連接同一行中下一個非零元，向下域down連接同一列中下一個非零元。

 typedef struct OLNode{   //單個非零元節(jié)點
  int i, j;  //該非零元的行和列的下標
  ElemType e;  //該非零元的值
  struct OLNode *right, *down;  //該非零元所在行表和列表的后繼域
}OLNode； *OLink

typedef struct {   //表示稀疏矩陣的十字鏈表
  OLink *rhead, *chead; //行和列鏈表頭基址
  int mu, nu, tu;  //稀疏矩陣的行數、列數和非零元素個數
}CrossList；

4.2 廣義表

廣義表一般記作
LS=（a1,a2,...,an）
ai可以是單個元素，稱為原子，也可以是廣義表，稱為子表。
當廣義表非空時，稱第一個元素為表頭，其余元素組成的表成為表尾。廣義表有以下性質：
1.列表的元素可以是子表，子表的元素也可以是子表
2.列表可以為其他列表所共享
3.列表可以是遞歸結構，即列表可以是其本身的一個子表
存儲結構
廣義表內有兩種元素：
表節(jié)點，由3個元素組成，標志域，用于指示表頭的指針域和指示表尾的指針域
原子節(jié)點，由兩個元素組成，標志域，值域
其中，標志域用于指示該節(jié)點是表節(jié)點還是原子節(jié)點
廣義表可以用于表示m元多項式

5 樹和二叉樹

5.1 樹

結點的度：結點擁有的子樹的數量
樹的度：樹內各結點的度的最大值
樹的深度：樹中結點的最大層次
若樹的子樹從左至右是有次序的則成為有序樹，有序樹最左邊的子樹的根結點稱為樹的第一個子結點。
森林是m棵互不相交的樹的集合

5.2 二叉樹

5.2.1定義和性質

二叉樹（binary tree）是一種特殊的樹結構，其每個結點至多只能有兩棵子樹，且有次序之分
二叉樹有以下重要性質：

在第i層上至多有 $ 2^(i-1) $ 個結點
深度為k的二叉樹的最大結點數為2^（k）-1個結點
2.1 一棵深度為k，且有2^（k）-1個結點的二叉樹稱為滿二叉樹
2.2 按照從上到下，從左到右的順序從根結點開始對滿二叉樹的結點編號，則若深度為k且其每一個結點的編號都與滿二叉樹的結點一一對應時，則為完全二叉樹。完全二叉樹的終端結點只可能在層次最大的兩層上出現；對任意結點，若其右分支下的子孫最大層次為l，則其左分支下的子孫最大層為l或l+1
對任意一棵二叉樹，如果其終端結點數為m，度為2的結點數為n，則m=n+1
具有n個結點的完全二叉樹的深度為floor（（log_2 n ）+1）
如果對一棵有n個結點的完全二叉樹進行編號，則對任一結點i，有：
5.1 若i=1，則結點i為根結點；若i>1,則其父結點為floor（i/2）
5.2 若2i>n,則結點i為終端結點；否則其左結點為2i
5.3 若（2i+1）>n則其無右結點；否則其右結點為2i+1

5.2.2二叉樹的存儲結構

順序存儲結構
用一組連續(xù)的地址單元從上到下從左到右存儲二叉樹的元素，沒有元素的節(jié)點用0表示。
只適用于完全二叉樹。
鏈式存儲結構
二叉鏈：數據域，左右指針域
三叉鏈：數據域，左右指針域，父結點指針域

5.3 遍歷二叉樹和線索二叉樹

5.3.1遍歷二叉樹

遍歷二叉樹是以一定規(guī)則將二叉樹的節(jié)點排成一個線性序列，實際上是對一個非線性結構進行線性化操作

先序
中序
后序

5.3.2線索二叉樹

為保存遍歷過程中的信息，在每個結點中增加兩個指針域，fwd和bkwd分別指示結點的前驅結點和后繼結點，但是會增加所需存儲空間，因此規(guī)定：
若結點有左子樹，則lchild指針指向其左側子結點，否則指示遍歷過程中其前驅結點；若結點有右子樹，則rchild指針指向其右側子結點，否則指示遍歷過程中其后繼結點。為避免子結點和前驅后繼結點混淆，增加兩個標志域LTag和RTag（同樣增大了所需存儲空間？）

以這種結點構成的二叉鏈表稱為線索鏈表，指向前驅結點和后繼結點的指針稱為線索。
對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化。
線索化的過程即在遍歷中修改指針的過程

5.4 樹和森林

5.4.1樹的存儲結構

父結點表示法
假設以一組連續(xù)空間存儲樹的節(jié)點，同時在每個結點中增加一個指示器指示其父結點的位置
子結點表示法
兄弟子結點表示法

5.4.2二叉樹和森林的轉換

二叉樹轉換為森林
森林轉換為二叉樹

5.4.3 樹與等價問題

（沒看懂，待補充）

5.5 赫夫曼樹及其應用

5.5.1 最優(yōu)二叉樹

樹的路徑長度：從樹根到每一個結點的路徑長度之和。
樹的帶權路徑長度（WPL）：樹中所有葉子結點的帶權路徑長度之和。
假設有n個結點，構造一棵有n個葉子結點的二叉樹，其中帶權路徑長度最小的樹稱為最優(yōu)二叉樹或赫夫曼樹。
構造赫夫曼樹：

根據給定的權值構成n棵二叉樹的集合F，其中每棵二叉樹僅有一個結點。
在集合F中選擇權值最小的兩棵樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹根結點的權值為左右兩棵子樹根結點的權值之和。
在F中刪掉這兩棵樹，同時將新的二叉樹加入到F中。
重復2-3，直到F中僅剩一棵樹為止。

5.5.2 赫夫曼編碼

若有一棵二叉樹，其左分支為0，右分支為1，則可以用從根結點到葉子結點路徑上組成的字符作為該結點的編碼。

image.png

6 圖

7 動態(tài)存儲管理

8 查找

本節(jié)內容如下：

查找表

8.1 靜態(tài)查找

功能：查找摸個元素是否在表中。檢索某個特定元素的各種屬性。

8.1.1 順序表的查找

--以順序表或線性鏈表表示靜態(tài)查找表。
--過程：從最后一個記錄開始，逐個將元素的關鍵值和給定值進行比較。如果某個元素的關鍵值和給定值相等，則查找成功；若直到第一個元素都沒有找到相應元素，則查找不成功。
--可以將第0個元素的關鍵值賦值為給定值，可以免去查找過程中檢測整個表是否查找完畢的步驟。
--當每個元素的查找概率不相等時，應先按查找概率對元素進行排序以提高查找效率。
--無法預測查找概率時，可以為每個元素增加一個訪問頻度的屬性，并使順序表中的元素始終按照訪問頻度次序排列，使概率較大的元素在查找過程中不斷后移?；蛎看尾檎抑髮偛榈降脑刂苯右苿拥侥┪?。
--優(yōu)點：算法簡單，適應面廣。
--缺點：平均查找長度大，效率低。

8.1.2 有序表的查找

--以有序表表示靜態(tài)查找表。一般使用折半查找法（二分法）。
--過程：先確定需要查找的元素所在區(qū)間范圍，然后逐步縮小范圍直到找到或者找不到該元素為止。
--折半查找過程可以看作一棵二叉樹（這時二叉樹可以稱為判定樹），找到有序表中任意元素的過程就是走了一套從根節(jié)點到該元素對應節(jié)點的路徑。和給定值比較的次數為該節(jié)點在樹上的層次數。
--優(yōu)點：效率高于順序查找
--缺點：只適用于順序存儲結構，對線性鏈表無法有效進行。
--除折半查找之外，還有斐波那契查找和插值查找。

8.1.3 靜態(tài)樹表的查找

--當有序表中各元素的查找概率不等時，折半查找法的性能未必最優(yōu)。
--靜態(tài)最優(yōu)查找樹：各個元素的帶權路徑之和最小的判定樹稱為靜態(tài)最優(yōu)查找樹，可以使查找性能達到最優(yōu)狀態(tài)。
--構造靜態(tài)最優(yōu)查找樹的方法：（待補充）
--構造次優(yōu)查找樹的方法：在有序表中取元素r構造根節(jié)點，應使r左樹權值之和與右樹的權值之和相差最小。然后分別對左樹和右樹構造次優(yōu)查找樹。

8.1.4 索引順序表的查找

--以索引順序表示靜態(tài)查找表，可以用分塊查找實現。
索引表
--除需要被查找的表之外，還需為它建立一個索引表，如下圖所示。

索引表

--上圖中，下方為需要被查找的表，可以分為三個子表。在索引表中為每個子表建立索引項，包含：關鍵字項（該子表內的最大值）、指針項（該子表的第一個元素在表中的位置）。
--索引表按照關鍵字有序，則表為有序表或者分塊有序（即第二個子表中所有元素的值均大于第一個子表中元素的值）。
分塊查找
--分塊查找的過程：先確定待查記錄所在的子表（可以用折半查找或順序查找），再在子表中順序查找。

8.2 動態(tài)查找

--功能：除靜態(tài)查找的功能以外，還可以在查找的同時插入表中不存在的元素，或者從表中刪除摸個已經存在的元素。
--動態(tài)查找表的結構是在查找過程中動態(tài)生成的，若表中存在與給定值相等的記錄，則查找成功返回，否則在表中插入值等于給定值的元素。

8.2.1 二叉排序樹

--二叉排序樹：空樹，或者有以下性質的二叉樹：1.若左子樹不為空，則左樹上所有結點的值均小于根結點的值；2.若右子樹不為空，則右樹上所有的結點均大于根結點的值；3.其左右子樹也為二叉排序樹。
查找
--查找過程：1.判斷給定值與根結點是否相同，相同則返回；2.若小于根結點，則進入左樹進行查找；3.若大于根結點則進入右樹進行查找（遞歸方法）。
插入
--新插入的結點一定是葉子結點，并且是查找不成功時查找路徑上最后一個結點的左結點或右結點。如下圖：

插入新結點

刪除
--1.若刪除的結點為葉子結點，則直接刪除不影響其他元素。
--2.若刪除的結點只有左子樹或右子樹，則只要將其子樹代替該節(jié)點的位置即可，如下圖。

刪除結點-1

--3.若刪除的結點既有左子樹也有右子樹，設需要刪除的結點為P，其父節(jié)點為F，有兩種方式：
---3.1 設P為F的右結點，則令P的右子樹為F的右子樹，令P的左子樹為S的左子樹，其中S為P右子樹的左樹的盡頭結點，如下圖。

刪除結點-3.1

---3.2 用P的直接前驅或直接后驅代替P，然后再從二叉樹中刪去他的直接前驅或直接后驅（迭代方法），如下圖。

刪除結點-3.2

8.2.2 平衡二叉樹

--二叉樹的結構不唯一，若為單支樹，則查找效率最低，因此構造二叉樹時需要進行平衡化。
--平衡二叉樹：其左子樹和右子樹的深度之差的絕對值不超過1，且他的左子樹和右子樹都為平衡二叉樹。
--平衡化過程中有4種調整方法：單向左旋、單向右旋、先左旋再右旋、先右旋再左旋，如下圖。