AHPU__數據結構部分筆記

知識角度
1. 專業基礎課
2. 鍛鍊數據抽象思維
3. 形成基本演算法分析和設計能力
4. 企業面試
5. 考研
應用角度
1. 開發任何規模的軟體，都要數據結構
2. 程式語言內奸數據結構相關的語法和API
  - c：陣列，指針
  - C++：STL（標準模板庫）
  - java：（java.util包）
    - map
      - Hashmap 陣列
      - Linkhashmap 雙向鏈表
      - Treemap：紅黑樹
  - python：元組、列表、字典、集合
  - JavaScript：JSON
爲什麼程式語言提供了那麼豐富的語法和API爲什麼我們不直接用還要學習數據結構呢？
&emsp只有瞭解了數據結構在明白在什麼情況下運用什麼樣的包

學習方法

多迭代
多做題
多實踐（多寫程式碼）
多交流

實踐環境

程式語言
- 理論上沒有限定
- 推薦使用強型別語言
- 推薦使用面相物件語言(c++)
- 不推薦語言內建的數據結構相關語法特性和API
- 本課程用的C語言（及c++的參照參數特性）
IDE
- vc6.0
- vs
- vscode + 外掛 +MinGW

一.緒論

1.1數據結構是什麼

數據結構是什麼
- 用計算機求解問題的一般步驟
  - 分析問題->建立數學模型–>設計演算法–>程式設計/偵錯–>結果
- 建模的本質：
  - 從問題中抽取關鍵物件
  - 找出這些物件之間的關係
  - 以合適的語言加一描述
問題的種類
1. 數值型（Numerical）：百錢白雞、水仙花數
2. 非數值型（Non-Numerical）：選課系統、人臉識別…
起源
- Donald Ervin Knuth
所處地位
- 來源於數學
- 介於數學、程式設計、硬體系統
- 程式=數據結構+演算法

1.2概念和術語

數據（Data)：指計算機能夠處理的任何資訊。數據是一種符號（Symbol）
數據元素（DataElement）：指數據的基本組成單位——數據是由若幹數據元素構成的有限集，如學生表中的每一行。通常簡稱爲元素
數據項（DataItem）：指數據元素的基本組成單元——具有原子性（不可再分），如學生表中某個學生的每一例。
數據結構（DataStructure）：彼此間具有一種或多種關係的數據元素的集合。DateStructure=(D,R)&nbsp&nbspD:數據元素，元素間的關係
邏輯結構（LogisticStructure）：站在真實世界觀察數據結構，即數據元素在真實世界中所具有的的邏輯關係
- 4種邏輯結構
  - 集合：set
  - 線性結構
  - 樹形結構
  - 網狀結構
物理結構（PhysicalStructure）站在計算機世界（主要指記憶體）觀察數據結構———數據元素及關係在計算機記憶體中的儲存方式
- 兩種物理結構：
  - 順序結構（SequentialStructure）
    - 用一段連續的記憶體單元依次存放元素
    - 邏輯上相鄰的元素所佔的記憶體單元也相鄰
    - 以物理位置（記憶體）的相鄰來表示元素在邏輯上的相鄰
  - 鏈式結構（LinkedStructure）
    - 元素所佔的記憶體單元可以是任意的
    - 爲還原彼此之間的邏輯關係，每個元素自身資訊外，還需存放與之具有關係的那個元素的儲存位置（即鏈、指針）
邏輯結構VS物理結構
- 邏輯結構關注元素及其關係在真實世界中的呈現————元素有哪些、關係是什麼
- 物理結構則關注元素及其關係在計算機記憶體中如何實現

1.3抽象數據型別

數據型別（DataType）
- 若幹值的集合，在這些值上能夠執行某些操作。
- 原子型別：不可再分，如整型、實行、字元、布爾、指針
- 結構型別：有原子（或結構）型別組合而成，如字串、陣列
- ！！！不同語言，編譯器，甚至同一語言的不同版本，支援的數據型別可能不盡相同
抽象數據型別（Abstract Data Type,ADT）
- 從邏輯結構的角度來描述元素、關係、及操作，與計算機和程式語言無關。
  - $ADT=（D,R,P)$
  - D：數據元素
  - R：元素間的關係
  - P：元素支援的操作（Operation）
- 抽象的意義
  1. 分離數據型別的描述和實現
  2. 拼比計算機軟硬體平臺的差異
  3. 替身模型的可理解性和可複用性

1.4演算法及其設計要求

演算法（Algorithm）
- 演算法特性：
  - 有窮性：步驟的總執行次數有限，且每一步在（合理）時間內完成
  - 確定性：每一步所做的事是確定的，不能有歧義
  - 可行性：每一步在現有的技術條件下都是可行的
  - 至少有一個輸入：此處的輸入指的是演算法要處理的數據
  - 至少有一個輸出：此處的輸出泛指演算法的到的結果或者執行的操作
演算法的設計要求
- 設計良好的演算法應滿足：
  - 正確性：演算法所做的事情是嚴格滿足問題要求的
  - 可讀性：易於理解（相對）、偵錯及擴充套件（從工程角度）
  - 健壯性：當輸入不合理、惡意，或者到達邊界條件，演算法均能正確處理，而不能得到非預期結果或崩潰
  - 高效率：所需計算量和儲存空間儘可能小（優勢優先順序高於可讀性）
演算法 VS 程式

可以用任何語言描述演算法，而程式必須用計算機能夠理解的語言——程式語言
程式是演算法的實現，可用不同的程式語言實現同一演算法
演算法是不能被計算機執行，而程式可以
演算法必須滿足有窮性，而程式可以無限執行下去————例如OS

1.5演算法分析與度量

如何衡量演算法的效率
- 測量：用程式語言將演算法編寫爲程式，並在電腦上執行——測量程式執行所耗費的時間。
  - 需要編寫程式
  - 依賴於程式語言、編譯器自身的效率
  - 依賴於硬體（如cpu，Gpu，記憶體，i/o）效能
  - 某些偶發因素對測量結果影響較大
- 分析：通過人腦分析演算法，統計其中基本步驟的總執行次數
  - 無需編寫程式
  - 結果不受演算法之外的任何因素影響
時間複雜度（Time Complexity）
- 基本步驟的總執行次數是關於n的函數，記爲F(n)
  - n指問題的規模，即演算法要處理的數據量
  - 通常情況下F(n)是增函數
- 假設存在一臺超腦能執行演算法：
  - 器執行演算法中的各種基本步驟所耗費的時間是常數C
  - 則演算法的總執行時間 $T(n)=F(n)×c=O(F(n))$
  - 所以，直接用F(n)衡量演算法的總執行時間
  - O(F(n))稱爲大O表示法。也稱爲時間複雜度
如何確定演算法的基本步驟
- 哪些佔據演算法絕大部分執行時間的步驟就是基本步驟
- 通常情況下，僅將回圈體中的語句作爲基本步驟
- 巢狀最深的基本步驟的行爲代表了整個演算法的行爲

第二章線性表

2.1概念及ADT

線性表（linear list）
- 若幹元素構成的有序序列
- L=( $a_1$ , $a_2$ , $a_3$ ,…, $a_n$ )
  - 表頭元素：a1
  - 表尾元素：an
  - 表長： n，若n=0，則L爲空表
  - 前驅：ai-1爲ai的前驅（predecessor或prior）
  - 後繼： $a_{i+1}$ 爲 $a_i$ 的後繼（successor或next）
線性表的特性
- 對於任一非空線性表，有：
  - 有且僅有一個表頭元素
  - 有且僅有一個表尾元素
  - 除表頭外，其他元素有且僅有一個前驅
  - 除表尾外，其他元素有且僅有一個後繼

2.2線性表的順序實現————順序表

以一段連續的記憶體單元依次存放線性表中的各個元素————順序表（Sequential List）
$Loc(a_i)=Loc(a_{i-1})+d=Loc(a_i)+(i-1)*d$
- d:每個元素所佔的位元組數
  - 隨機存取（Random Access）的本質

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10

typedef int ElemType;
typedef struct{
   int length;
   int size;
   ElemType *elem; 
}SqList;

void init(SqList &L){
   L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
   if(!L.elem){
      exit(-1);
   }
   L.length=0;
   L. size=LIST_INIT_SIZE;
}
void getElem(SqList L,int i,ElemType &e){
   if(i<1||i>L.length){
      return;
   }
   e=L.elem(i-1);
}
void insert(ElemType &e,int i,SqList &L){
   if(i<1||i>L.length+1){
      return;
   }
   if(L>length==L.size){
      ElemType *base=(Elemtype *)realloc(L.elem,(L.size+LIST_INCREMENT)*sizeof(ElemType));
      if(!base){
         exit(-1);
      } 
      L.elem=base;
      L.size +=LISI_INCREMENT;
}
   for(int m=L.length-1;m>=i-1;--m){
      L.elem[m+1]=L.elem[m];
   }
   L.elem[i-1]=e;
   L.length++;
}

2.3 線性表的鏈式實現——鏈表

定義：表中個元素多佔的記憶體單元是任意的。除自身資訊外，元素還需附帶指向其後繼元素的指針（即鏈）————鏈表（LinkList)
- 指針在紙上的畫法
- 指針L指向a1，通過a1附帶的指針可找到a2，如此下去…
- 表尾元素an附帶的指針爲空（圖中常以^標識）
- 知道了L,便能依次確定鏈表中的每個元素
- 元素自身資訊及其附帶的指針合稱爲鏈表的結點（NODE）
- 注意鏈表L的稱法並不真正代表整個鏈表（L的本質只是指向一個節點的指針）
單鏈表

每個結點只附帶了其後繼指針，也稱爲單（向）鏈表
每個節點均包含2部分資訊—————數據域和後繼指針域
非空鏈表
空鏈表：L爲空（即L==NULL)

帶頭結點的單鏈表

爲了程式設計方便，通常在表頭元素錢認爲附設以個節點————頭結點(HEAD NODE HEADER)，指向頭結點的指針爲頭指針
頭結點的結構與元素結點一致
頭結點的指針域指向表頭元素，數據域不用管它
非空鏈表

單鏈表的定義

typedef int ElemType;
typedef struct _Node{//定義結點的結構
   ElemType data;    //數據域（元素自身的資訊）
   struct _Node *next;//指針域（指向的結構與當前結構一致）
}Node,*LinkList;      //2個型別別名（注意第2個我指針型別名）

public class LinkListNode{
   pricate int data;
   pricate LinkListNode next;

}
4. 演算法實現————得到表長
```cpp
void getLength(LinkList L,int &length){
 Node *p=L;    //p指向頭結點
 length=0;
 while(p->next){//等價於：p->next!=NULL
    length++;
    p=p->next;//P指向下一結點
 }
}

int getElem(LinkList L,int i,ElemType &e)
{
 Node *p=L->next;//p指向首結點
 int j=1;         //計數器
 while(p&&j<i){   //未到達表尾且計數器喂到達i
    j++;
    p->next;
 }
 //執行到這，有三種情況：①p==NULL，②j>i③j==i；
 if(!p){
    return -1;
 }
 if(j>i){
    return -2;
 }
 e=p->data;
 return 0;
}
//因無法直接得到表長，所以無法直接判斷i的合法性
//鏈表不支援隨機存取
//從表頭遍歷

void insert(LinkList&L,int i,ElemType e){
 Node *p=L;
 int j=0;
 while(p&&j<j-1>){
    j++;
    p=p->next;
 }
 if(!p||j>i-1){
    Node *node=(LinkList)malloc(sizeof(Npde));
    node->data=e;
    node->next->p->next;
    p->next=node;
 }
}
//刪除演算法
//先找到第i-1個元素的指針p
//修改p的後繼指針，使其指向第i+1個結點
//釋放第i個結點所佔的記憶體
void del(LinkList &L,int i,ElemType &e)
{
 Node *p=L;
 int j=0;
 while(p->next&&j<i-1){
    j++;
    p=p->next;
 }
 if(!(p->next)||j>i-1){
    return ;
 }
 Node *q=p->next;
 p->next=q->next;
}
//演算法實現——建立
//create(LinkList &L,ElemType e[],int n)
//初始化頭結點
//讀取e中的下一元素，插到L的表頭（頭插法）或表尾（尾插法）
//重複上述步驟
void createFromTail(LinkList &L,ElemType e[],int n){

 L=(LinkList)malloc(sizeof(Node));
 L->next=NULL;
 for(int i=0;i<n;i++){
    Node *p=(LinkList)malloc(sizeof(Node));
    p->data=e[i];
    p->next=L->next;
    L->next=p;
 }
}
/*尾插法——從表頭到表尾依次建立結點*/
void createFormHead(LinkList &L,ElemType e[],int n)
{
 L=(LinkList)malloc(sizeof(Node));
 L->next=NULL;
 Node *tail=L;
 for(int i=0;i<n;i++){
    Node *p=(LinkList)malloc(sizeof(Node));
    p->next=NULL;
    tail->next=p;//tail 指向新的最後一個節點
    tail=p;
 }
}

單鏈表的優缺點
1. 優點
  - 無需佔據連續記憶體
  - 按需申請記憶體，不會造成浪費；
  - 插入、刪除無需移動元素
2. 缺點
  - 不支援亂數存取————按位元置查詢元素時需要歷遍鏈表
  - 僅支援單向（從表頭到表尾）歷遍

2.4線性表的應用————多項式

順序儲存
1. 用下標對應指數，結構清晰
2. 查詢、插入、刪除、相加等操作容易實現
3. O(1),O(1),O(1),O(max(na,nb))
4. 對於稀疏多項式，浪費空間： $(n+1)c=<S<=(max+1)c$
鏈式儲存
1. 按需分配： $S=(N_{items}+1)(c+e+p)≈3（N_{items}+1）c<<(n+1)c$
2. 查詢、插入、刪除、相加等操作相對複雜
3. O(n)、O(n)、O(n)、？

第三章棧和佇列

3.1棧的定義以及ADT

棧

棧是操作受限的線性表——僅允許在表的一端進行插入和刪除，該端稱爲棧頂（TOP），另一端稱爲棧底（Bottom或者Base）
上述限制使得棧具有後進先出的特性
爲了區別於線性表的插入、刪除
1. 插入：入棧
2. 刪除：出棧

棧的順序實現————順序棧
1.定義

#define STACK_INIT_SIZE 100 //初始容量
#define STACK_INCREMENT 10  //追加容量

type int ElemType;

type struct{
   ElemType *base;//棧底指針（連續記憶體的首地址）
   ElemType *top;// 棧頂指針（本課程約定其指向棧頂元素的下一位置)
   int size;//棧容量
}sqStack;//型別別名

sqStack s;
*(s.base)//棧底元素
s.top   //下一入棧位置
*(s.top-1)//棧頂元素
s.top-s.base  //棧中元素個數
s.top==s.base  //空棧
s.top-s.base=s.size  //棧滿

演算法實現——初始化
init(sqStack &S)
爲S分配記憶體
爲S各成員賦初始值

void init(sqStack &S){
   S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
   if(!S.base){
      exit(-1);
   }
   S.top=S.base;
   S.size=STACK_INIT_SIZE;
}

3.演算法實現————得到棧頂元素

getTop(sqStack S,ElemType &e)
判斷棧是否爲空
注意本課程對top指針的約定

void getTop(sqStack S,Elemtype &e){
   if(S.top==s.base){
      return ;
   }
   e=*(S.top-1);//真正的棧頂元素在top指針的前一個位置
}

演算法實現————將e入棧
push(sqStack &S,ElemType e)
若棧已滿，則追加空間
入棧，並修改各個成員

void push(sqStack &s,Elemtype e){
   if(S.top-S.base==S.size){
      S.base=(ElemType * )realloc(S.base,(S.size+STACK_INCREMENT)*sizeof(ElemType));
      if (!S.base){
         exit(-1);
      }
      S.top=S.base+S.size;//修改棧頂指針
      S.size+=STACK_INCREMENT;//修改棧容量
   }

 *(S.top++)=e;
}

演算法實現————出棧
pop (sqStack &S,ElemType &e)
判斷棧是否爲空
修改top指針

void pop (sqStack &S,ElemType &e){
   if(S.size==S.base){
      return;
   }
   e=*--S.top;
}

棧的鏈式實現————鏈棧
- top指針指向頭結點
- 節點結構與鏈表一致
- 棧頂元素：top->next->data
總結
1. 後入棧的先出棧
2. 無論順序棧還是鏈棧，前述個演算法的T(n)=O(1)
3. 計算機底層硬體就有棧
  1. cpu中的棧頂指針（SP）暫存器
  2. cpu的入棧（PUSH）及出棧（POP）指令
  3. 呢村中劃分堆疊段
4. 應用及其廣泛

3.3 棧的應用

進位制轉換

void conversion(int N,int r){
   init(S);
   while(N){
      push(S,N%r);
      N/=r;
   }
   while(!isEmpty(S)){
      pop(S,e);
      printg("%d",e);
   }
}

3.4 棧與遞回

遞回
- 遞回是一類演算法思想——演算法中的某一（幾）步是演算法本身，但是後者設計的問題規模更小。
- 對於程式設計，遞回是指函數呼叫了本身
- 遞回可用於一些難以用常規演算法求解的問題

遞回問題分類————問題定義是遞回的 n！

long f(int n){
   if(n==0){
      return 1;
   }
   else{
      return n*f(n-1);
   }
}

遞回問題分類————問題結構是遞回的

得到非空單鏈表的最後一個元素

ElemType getLast(LinkList L){
   return !L->next->data:getLast(L->next);
}

遞回問題分類————求解思想是遞回的
遞回演算法

任何遞回演算法都由兩部分組成：

終結條件————可直接得到結果而無需遞回的部分
地櫃部分————與原問題性質相同，但規模更小的若乾子問題

  void solution (scale){
     if(termination_condition){
        直接得到結果；
     }
     else{
        solution(smaller_scale);
     }
  }

棧與遞回

遞回演算法通常很簡潔，但執行過程較爲複雜
每次遞回（包括呼叫其他函數）前，需要暫存當前參數、語句地址等，以便遞回結束時，能返回到該呼叫處繼續往下執行
後呼叫的函數先返回
對於計算機來說，遞回和普通的函數呼叫沒有差別
上述過程對程式設計者是透明的

3.5 佇列的定義及ADT

佇列

佇列也是操作受限的線性表————僅允許在表的一段進行插入、另一端進行刪除，這兩端分別稱爲隊尾（Rear）、對頭（Front）
上述限制使得佇列具有先進先出（FIFO，First In First Out）特性：排隊
爲區別與線性表的插入、刪除
佇列的插入：入隊ENTER
佇列的刪除：出對REMOVE

3.6佇列的實現————回圈佇列

定義

#define SIZE 100//佇列容量
typedef int ElemType;//簡單起見，每個元素爲int型

typedef struct{
   ElemType *base;//連續空間起始地址
   int front;//對頭下標
   int rear;//隊尾下標（本課程約定其爲隊尾元素的下一位置
}sqQueue;

sqQueue Q;
Q.base[Q.front]//隊頭元素
Q.base[Q.rear-1]//隊尾元素
Q.rear         //入隊元素下標

將e入隊

void enter(SqQueue &Q,ElemType e){
   int len;
   getLength(Q,len);
   if(len==SIZE-1){
      return ;
   }
   Q.base[Q.rear]=e;//入隊
   if(Q.rear<SIZE-1){
      Q.rear++;   //rear後移
   }
   else{          //rear==SIZE-1
      Q.rear=0;   //回到0的位置
   }
}

出隊

void remove(SqQueue &Q,ElemType &e){
   if(Q.front==Q.rear){       //佇列爲空
      return;
   }
   e=Q.base[Q.front];   //儲存隊頭
   if(Q.front<SIZE-1){
      Q.front++;     //front後移
   }else{            //front==SIZE-1
      Q.front=0;   //回到0位置
   }
}

問題：

經過多次入隊、出隊，可能出現rear=SIZE
此時，佇列中可能存在未用單元

約定

SIZE-1的下一位置是0
屬於佇列的元素：從front出發，沿着下標遞增方向，直至到達rear
rear指向的不是隊尾，而是隊尾的下一位置（故最多隻能存放SIZE-1）元素

第4章陣列

4.1 陣列的定義

陣列（Array）

若幹相同類型元素構成的有限序列，如向量
各元素又可以是陣列————多維陣列，如矩陣、張量

4.2素組的順序實現

儲存結構
- 記憶體總是一維結構
- 多維陣列需要對映爲一組陣列，才能纔能存放
- 以行(高維)爲主序，以列（低維）爲主序
- 所有的高階語言都支援原生陣列語法
隨機存取（Random Access）
- RA是順序儲存纔有的特性
- 本質：目標元素的地址=首地址+偏移量
- 一維陣列An:Loc(i)=Loc(0)+i*d
- 二維陣列A m*n:Loc(i,j)=Loc(0,0)+(i * n+j)d
- 三維陣列A pmn=Loc(0,0,0)+(imn+j*n+k)*d

4.3 特殊矩陣的壓縮儲存

某些矩陣的元素分佈有一定的規律，出於節省空間的目的，只儲存其部分值——進行壓縮儲存，並能根據儲存的元素還原回矩陣。

對稱矩陣
- $a_{ij}$ == $a_{ji}$ ;
- 只儲存主對角線及一側的值
上/下三角矩陣
- 主對角線一側的元素均爲常數c（通常是0）
- 只儲存c、主對角線及一側的值
對角矩陣
- 非零元素僅出現在以主對角線爲中心的帶狀區域，區域全爲0
- 只儲存帶狀區域的元素

4.4稀疏矩陣的壓縮儲存

係數矩陣
- 絕大多數元素爲0
- 非零元的分佈沒有規律
三元組順序表
- 每個非零元由三個值唯一確定： $(i,j,a_{ij})$ ——三元組
- 用一維陣列按行序依次存放各三元組———三元組順序表
- 存放矩陣的行列數

#define SIZE 100     //非零元個數上限
typedef int ElemType;//簡單起見，每個元素定義爲int型

typedef struct {
   int i,j;//非零元行列下標
   ElemType v;//非零元值
}Triple;    //型別別名（三元組）

typedef struct {
   Triple data[SIZE];   //一維矩陣存放所有非零元
   int m,n,t;           //矩陣行列數及非零元個數
}Matrix;                //型別別名（三元組順序表）

演算法實現————列印
- 總要列印m*n個元素
- 判斷當前內外村回圈變數是否分別與當前非零元的i,j相同

void print(Matrix A){
   for(int p=0,i=0;i<A.m;i++){
      for(int j=0;j<A.n;j++){
         if(p<A/.t&&A.data[p].i==i&&A.data[p].j==j)
         printf("%4d",A.data[p++].v);
         else 
         printf("%4d",0);
      }
      printf("\n");
   }
}

演算法實現————轉置

B=A^T,交換A中三元組的i,j
保證B按照A中j非遞減排列
掃描A中全部三元組n次

void  transpose(Matrix A,Matrix &B){
   int q=0;
   B.m=A.n,B.b+A.m,B.t=A.t;
   for(int col=0;col<A.n;col++)P
   for(int p=0;p<A.t;p++){
      if(A.data[p].j==col){
         B.data[q].i=A.dara[p].j;
         B.data[q].j=A.data[p].i;
         B.data[q].v=A.data[p].v;
         q++;
      }
   }
}

演算法實現————快速轉置

統計A中每列非零元個數：num[ ]
計算A中每列首歌非零元在B.data 中的位置：pos[ ]
- pos[0]=0
- ops[j]=pos[j-1]+num[j-1]
依次讀入A中三元組，直接放在B.data的合適位置

void fastTranspose(Matrix A,Matrix &B){
   B.m=A.n,B.n=A.m,B.t=A.t;
   int num[100]={0},pos[100]={0},q;
   fot(int p=0;p<A.t;p++){
      num[A.data[p].j]++;//初始化num
   }
   for(int i=1;i<A.n;j++){
      pos[j]=pos[j-1]+num[j-1];//初始化pos
   }
   fot(int p=0;p<A.t;p++){
      Triple tr=A.data[p];
      q=pos[tr.j];
      B.data[q].i=tr.j;
      B.data[q].j=tr.i;
      B.data[q].v=tr.v;
      pos[tr.j]++;   //計算該列下一非零元素的位置
      
   }
}

第5章樹和二元樹

5.1 概念及術語

樹(Tree)
- 由若乾結點構成的集合。對於任意一個非空樹：
  - 有且僅有一個根（Root）結點
  - 剩餘結點可被分爲若幹不相交的子集——根的子樹(Subtree)
  - 上述定義本身就是遞回的
  - 從上到下看：一個結點對應零到多個子結點
  - 從下到上看：一個結點對應一個父結點（除根外）
術語
- 子結點/孩子（children）：結點的子樹的根，如H是D的子結點
- 父結點/雙親（parent）：
- 分支/邊(Branch)：父子結點間的關係（連線）
- 結點的度（Degree）：結點的孩子個數
- 樹的度：樹中結點的度的最大值
- 葉子/終端結點（Leaf）：度爲0的節點，反之爲非葉節點
- 兄弟（Sibling）：父結點相同的結點
- 堂兄弟（Cousin）：父結點在同一層的結點
- 子孫（Descendant）：子樹中的任意結點
- 祖先（Ancestor）：結點到根所經歷的任意結點
- 結點的層次（Level）：根在第1層，L層的節點的孩子在L+1層
- 樹的深度/高度（Depth/Height）：節點的最大層次

5.2 二元樹及其性質

二元樹（Binnary Tree）
- 每個結點至多有兩個孩子———不存在度大於3的節點
- 結點的孩子有左右之分，分別稱爲左孩子，右孩子
- 5中基本形態
  1. 空二元樹
  2. 僅包含根節點
  3. 僅包含左結點
  4. 僅包含右結點
  5. 兩個節點都包含
二元樹的性質
- 第i層最多有 $2^{i-1}$
- 高度爲k的二元樹最多有 $2^{k-1}個結點：$ $\sum_{i=1}^{n} 2{i-1}$
- 設樹中度爲i的結點爲 $n_i$ ,則有 $n_0=n_2+1$
滿二元樹（Full Binary Tree）

高度爲k的二元樹 $2^k-1$ 個結點

完全二元樹（Complete Binary Tree）

高度爲k，上k-1層是滿二元樹，第k層從右至左連續減少若幹個結點
葉結點只可能出現在最下2層

完全二元樹的性質

n個結點的完全二元樹高度爲 $[log_{2}{n}]+1$
若 $i>1$ ,則i的父結點爲 $[i/2]$ ;否則i無父節點
若 $i<=n/2$ ，則i的左孩子爲2i；否則i無左孩子（即i爲葉子）
若 $i<=(n-1)/2$ ,則i的右孩子爲 $2i+1$ ;否則i無右孩子

5.3 二元樹的儲存

順序儲存
- 用以爲陣列存放所有的結點（從上到下，從左到右）
- 用完全二元樹的思想對結點編號————作爲結點的下標
- 爲了能還原回樹，要將樹補全爲完全二元樹
- 適合儲存完全二元樹
- 對於普通的樹，可能會浪費大量空間

鏈式儲存

每個節點存放其左右孩子的指針————二叉鏈表
n個結點的二叉鏈表有 $n+1$ 個空指針

typedef char ElemType;

typedef struct Node{
   ElemType data;
   struct Node *left;
   struct Node *right;
}BinTreeNode,*BinTree;

5.4 二元樹的遍歷及建立

便利（Traversal）
- 按照某種次序，將給定數據結構的所有元素，存取且僅存取一次
- 四種遍歷方式
  1. 先序（pre-order）：rLR
  2. 中序（In-order）：LrR
  3. 後序（Post-order）：LRr
  4. 層序（Level-order）：從上到下，從左到右
先序遍歷
- 若二元樹T爲空，則返回——終結條件
- 否則
  - 存取T的根節點r
  - 以先序遍歷r的左子樹——遞回
  - 以先序遍歷r的右子樹——遞回

void preOrder(BinTree T){
   if(!T){
      return;
   }
   printf("%c",T->data);
   preOrder(T->left);
   preOrder(T->right);
}

中序及後序遍歷

void inOrder(BinTree T){
   if(!T){
      return;
   }
   inOrder(T->left);
   printf("%c",T->left);
   inOrder(T->left);
}
void postOrder(BinTree T){
   if(!T){
      return;
   }
   postOrder(T->left);
   postOrder(T->right);
   printf("%c",T->data);
}

//歷遍過程中生成結點
//以輸入先序序列建立二元樹爲例
void create(BinTree &T){
   char ch;
   scanf("%c",&ch);
   if(ch=='#'){
      T=NULL;
      }else{
         T=(BinTreeNode *)malloc(sizeof(BinTreeNode));
         T->data=ch;
         create(T->left);
         create(T->right);
      }

5.5 線索二元樹

問題提出
- 歷遍時，如何直接找到下一個要（上一個已）存取的結點？
- 如何將 $n+1$ 個空指針利用起來
線索二元樹
- 將原本爲空的左、右指針改爲線索（Thread）————該節點在裏邊所得序列中的前驅、後繼指針
  *上述過程稱爲線索化
區分孩子指針和線索指針
! avatar
- 約定：
  - 1Tag==0：left指向左孩子，否則指向前驅
  - rTag==0: right指向右孩子，否則指向後繼

//Pointer爲列舉型別別名
typedef enum Pointer{CHILD,THEAD};

typedef struct Node{
   ElemTyoe data;
   struct Node *left, *right;
   Pointer lTag,rTaag;
}ThreadNode,*ThreadTree;

線索二元樹的遍歷
1. 無需遞回
2. 利用線索直接找到前驅、後繼
3. 若無線索，則利用規則(以中序線索樹爲例)
  1. 首結點：最左的結點
  2. 後繼：左子樹最做的結點
  3. 末節點：最右的結點
  4. 前驅：左子樹最右的結點
二元樹的線索化
1. 在遍歷過程中修改空指針爲線索
2. 用指針p指向當前存取的結點
3. 用指針pre指向存取p之前最後存取的結點——pre是p的前驅
4. 爲方便後續操作，可附設一個頭結點，並建立其與根、首結點

5.6 樹與森林

樹的儲存——雙親表示法
1. 用一維陣列儲存各結點
2. 每個結點存放其父結點在陣列中的下標
3. 優點：找雙親爲 $O(1)$
4. 缺點：找孩子爲 $O(n)$
數的儲存——孩子表示法
1. 與二元樹鏈表類似,但孩子指針有多個
  1. 全部結點的指針數一致————實現簡單，但浪費空間
  2. 每個結點的指針數等於其孩子數—————節省空間，但實現困難
樹的儲存——孩子鏈表
1. 結點的全部孩子組成一個單鏈表
2. 所有單鏈表的頭結點存於一維陣列
3. 找雙親困難：改進–>在頭結點中增加雙親所在下標（帶雙親的孩子鏈表）
樹的儲存——孩子兄弟表示法
1. 結點結構同二叉鏈表
2. 2個指針分別指向首歌孩子、下一個兄弟
森林與二元樹的轉換
1. 森林是多棵樹的集合
2. 約定：多棵樹的根互爲兄弟
樹的遍歷
1. 先序：先存取根、在一次以先序遍歷根的各子根
2. 後序：先一次以後序遍歷跟的各子樹、再存取根
3. 先序：等價於以先序遍歷對應二元樹
4. 後序：等價於以中序遍歷對應二元樹
森林的遍歷
1.
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-Xbe1Fq9r-1597152053688)(imags/樹與森林.jpg)];

5.7 Huffman樹

樹的WPL（weighted path length）
1. 給定n個帶權值的葉結點，構造一棵二元樹
2. $l_i$ 爲從根到葉結點i的路徑長度（即路徑中邊的條數）
3. 樹的 $WPL=\sum_{i=1}^{n}{w_il_i}$
Huffman樹
1. WPL最小的二元樹
2. 最優二元樹，廣泛用於編碼、判定優化等
Huffman樹的構造
1. 初始條件：n個權值 $W={w_1,w_2,...,W_n}$
2. $F={T_1,T_2,...,T_n}$ , $T_i$ 爲僅有一個結點的樹——根的權值爲 $w_i$
3. 重複一下步驟n-1次
  1. 從F中選取2棵根節點權值最小的樹———— $T_i和T_j$
  2. 將 $T_i和T_j$ 作爲新樹T的左、右子樹
  3. T的根節點權值爲 $T_i和T_j$ 的根節點權值之和
  4. 將T加入F並刪除 $T_i和T_j$
    [外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-MxDXbr6W-1597152053689)(imags/Huffman樹.jpg)];
- $WPL=/sum_{i}^{n}w_il_i$ ————權值小的先選，讓其離根較遠
- Huffman樹可能不唯一，但WPL同爲最小
- Huffman樹中沒有度爲1的結點
- n個葉結點的Huffman樹共有 $2n-1$ 個結點

typedef struct{
   int weight;//結點權值
   int left,right,parent;
}HTNode,*HuffmanTree;

HTNode HT[m];//一維陣列存放所有節點
HuffmanTree HT;//陣列首地址

Huffman樹的應用————Huffman編碼
1. 給定字元集中每種字元（葉結點）的出現概率（權值），爲其設計編碼
  1. 儘量使文字的編碼總長度短（變長編碼）————出現概率高的字元，編碼要較短
  2. 解碼是沒有歧義（字首編碼）————任一編碼都不是其它編碼的字首
  - Huffman樹的初衷就是解決上述問題
  1. 左右分支分別編碼爲0、1
  2. 從根到葉結點，連線路徑中各分支的0、1————字首編碼
Huffman樹的應用————判定優化
- 統計某門課的各分數段人數、統計一段英文中各字元的出現次數
  - 儘量是條件的總判定次數少————可能性高的判定條件寫在前面
  - switch語句彙總，各case的編寫順序

第六章圖

6.1 概念和術語

圖
- [外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-eIii0ouF-1597152053690)(imags/數據結構/6.1圖.png)]
- 圖由兩部分組成： $G=(V,E)$
  - V:定點(Vertex)集合————圖中的元素數據
  - E:邊（Edge）的集合————元素間的關係
- 若定點v和w之間有邊：
  - e=(v,w)
  - v和w互爲鄰接點（Adjacent）
無向圖（Undirected Graph，UDG）
- 圖中邊沒有方向：(v,w)<—>(w,v)
有向圖（Directed Graph，DG）
- 圖中的邊有方向：< v,w >與< w,v >不相等
- 有向圖中的邊也稱爲弧（Arc）
- 箭尾依附的頂點————弧尾（Tail）
- 箭頭依附的頂點————弧頭（Head）
- 弧尾鄰接到弧頭，弧頭鄰接自弧尾
完全圖
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-IaPa6XqO-1597152053692)(imags/數據結構/完全圖.png)]
- 邊數達到最大的圖，設圖有n個頂點：
  - UDG：邊數=n(n-1)/2,即有 $C_n^2$
帶權圖
- 每一條邊帶有一個值————標識某種距離或成本
子圖
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-icWjrYvy-1597152053693)(imags/數據結構/子圖.png)]
1. G=(V,E),G’=(V’,E’)
2. V’包含於V，E’包含於E
3. 稱G’爲G的子圖
定點的度（Degree）
- 與頂點v鄰接的邊的數量。對於有向圖：
- 入度：以V爲弧頭的邊的數量
- 出度：以V爲弧尾的邊的數量
路徑（Path）
[外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-0QFiBNCl-1597152053694)(imags/數據結構/度.png)]
- 若幹頂點構成的序列
- 簡單路徑：路徑中不出現重複頂點，如（2,1,3）
- 環：路徑中的首、尾頂點相同（2，1，3，2）
圖VS.樹
1. 樹可以看做圖的特例，但是：
- 樹中有一個特殊的元素————根節點；每個元素的地位是相同的
- 縱向看，樹的元素之間有父子（層級）關係，橫向看，元素之間有左右（先後先後）關係
- 圖的元素之間沒有上下，左右之分，圖中的邊可以沿任一軸旋轉————圖保持不變
- 樹中任意兩個元素之間有唯一的簡單路徑；圖中可能有0或者多條簡單路徑

6.2 儲存與實現

鄰接矩陣
- 以元素A[i][j]表示頂點 $v_i$ 和 $v_j$ 鄰接關係
- [外連圖片轉存失敗,源站可能有防盜鏈機制機製,建議將圖片儲存下來直接上傳(img-sNFXUnFj-1597152053695)(imags/數據結構/圖的儲存與實現.png)];

AHPU__數據結構部分筆記

文章目錄

0.課程簡介

0.1課程意義

學習方法

實踐環境

一.緒論

1.1數據結構是什麼

1.2概念和術語

1.3抽象數據型別

1.4演算法及其設計要求

1.5演算法分析與度量

第二章 線性表

2.1概念及ADT

2.2線性表的順序實現————順序表

2.3 線性表的鏈式實現——鏈表

2.4線性表的應用————多項式

第三章 棧和佇列

3.1棧的定義以及ADT

棧

3.3 棧的應用

3.4 棧與遞回

3.5 佇列的定義及ADT

3.6佇列的實現————回圈佇列

第4章 陣列

4.1 陣列的定義

4.2素組的順序實現

4.3 特殊矩陣的壓縮儲存

4.4稀疏矩陣的壓縮儲存

第5章 樹和二元樹

5.1 概念及術語

5.2 二元樹及其性質

5.3 二元樹的儲存

5.4 二元樹的遍歷及建立

5.5 線索二元樹

5.6 樹與森林

5.7 Huffman樹

第六章 圖

6.1 概念和術語

6.2 儲存與實現

第二章線性表

第三章棧和佇列

第4章陣列

第5章樹和二元樹

第六章圖