數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

Chapter 1 線性表

線性表的邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)

邏輯定義
    　線性表（Linear List）是由n（n≥0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a₁，a₂，…，a_n組成的有限序列。
   　 ① 數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度（n=0時(shí)稱為空表）。
    　② 將非空的線性表（n＞0）記作：（a₁，a₂，…，a_n）
    　③ 數(shù)據(jù)元素a_i（1≤i≤n）只是個(gè)抽象符號(hào)，其具體含義在不同情況下可以不同。

邏輯結(jié)構(gòu)特征
　　對(duì)于非空的線性表:
    　① 有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a₁，沒(méi)有直接前趨，有且僅有一個(gè)直接后繼a₂；
   　 ② 有且僅有一個(gè)終結(jié)結(jié)點(diǎn)a_n，沒(méi)有直接后繼，有且僅有一個(gè)直接前趨a_n-1；
    　③ 其余的內(nèi)部結(jié)點(diǎn)a_i（2≤i≤n-1）都有且僅有一個(gè)直接前趨a_i-1和一個(gè)a_i+1。

順序存儲(chǔ)結(jié)構(gòu)

順序表

順序表的定義
(1) 順序存儲(chǔ)方法
　    即把線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。
(2) 順序表（Sequential List）
　    用順序存儲(chǔ)方法存儲(chǔ)的線性表簡(jiǎn)稱為順序表（Sequential List）。

結(jié)點(diǎn)a_i 的存儲(chǔ)地址：LOC（a_i）= LOC（a₁）+（i-1）*c   1≤i≤n （每個(gè)結(jié)點(diǎn)所占用存儲(chǔ)空間大小亦相同，占用c個(gè)存儲(chǔ)單元）
順序表上的基本運(yùn)算

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

單鏈表

鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表（Linked List）。
    　鏈表的具體存儲(chǔ)表示為：
　　① 用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）
　　② 鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
單鏈表的運(yùn)算

1、建立單鏈表：（1） 頭插法建表（2） 尾插法建表（3）尾插法建帶頭結(jié)點(diǎn)的單鏈表

2、單鏈表的查找運(yùn)算：（1）按序號(hào)查找（2） 按值查找

3、插入運(yùn)算 4、刪除運(yùn)算
循環(huán)鏈表 循環(huán)鏈表是一種首尾相接的鏈表。

1、循環(huán)鏈表
（1）單循環(huán)鏈表——在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)即可。
（2）多重鏈的循環(huán)鏈表——將表中結(jié)點(diǎn)鏈在多個(gè)環(huán)上。

2、帶頭結(jié)點(diǎn)的單循環(huán)鏈表

3、僅設(shè)尾指針的單循環(huán)鏈表
    　用尾指針rear表示的單循環(huán)鏈表對(duì)開(kāi)始結(jié)點(diǎn)a₁和終端結(jié)點(diǎn)a_n
雙鏈表

雙向鏈表（Double Linked List）
    　雙（向）鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接前趨的指針域prior。
順序表和鏈表的比較

分配方式：

前者：靜態(tài)分配；后者：動(dòng)態(tài)分配

存取方式：

     前者：隨機(jī)存取；后者：順序存取（掃描）

插入或刪除操作：

     前者：需要移動(dòng)近一半的節(jié)點(diǎn)；后者：只需要修改指針

 

Chapter 2棧與隊(duì)列

棧和隊(duì)列是兩種特殊的線性表，它們的邏輯結(jié)構(gòu)和線性表相同，只是其運(yùn)算規(guī)則較線性表有更多的限制，故又稱它們?yōu)?span style="COLOR: red">運(yùn)算受限的線性表

棧

棧的定義及基本運(yùn)算

1、棧的定義
    　棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。
　　(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。
　　(2)當(dāng)表中沒(méi)有元素時(shí)稱為空棧。
　　(3)棧為后進(jìn)先出（Last In First Out）的線性表，簡(jiǎn)稱為LIFO表。

2、棧的基本運(yùn)算
（1）InitStack（S）
    　構(gòu)造一個(gè)空棧S。
（2）StackEmpty（S）
    　判棧空。若S為空棧，則返回TRUE，否則返回FALSE。
（3）StackFull（S）
    　判棧滿。若S為滿棧，則返回TRUE，否則返回FALSE。
注意：
　    該運(yùn)算只適用于棧的順序存儲(chǔ)結(jié)構(gòu)。
（4）Push（S，x）
    　進(jìn)棧。若棧S不滿，則將元素x插入S的棧頂。
（5）Pop（S）
    　退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。
（6）StackTop（S）
    　取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。
順序棧 棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧,它是運(yùn)算受限的順序表。

1、 順序棧的類型定義
  #define StackSize 100 //假定預(yù)分配的棧空間最多為100個(gè)元素
  typedef char DataType;//假定棧元素的數(shù)據(jù)類型為字符
  typedef struct{
      DataType data[StackSize];
      int top;
     }SeqStack;
  注意：
　    ①順序棧中元素用向量存放
    　②棧底位置是固定不變的，可設(shè)置在向量?jī)啥说娜我庖粋€(gè)端點(diǎn)
    　③棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來(lái)指示當(dāng)前棧頂位置
2、 順序棧的基本操作
  前提條件：
    　設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即S-＞data[0]是棧底元素。
（1） 進(jìn)棧操作
    　進(jìn)棧時(shí)，需要將S-＞top加1
  注意：
　    ①S-＞top==StackSize-1表示棧滿
　　②"上溢"現(xiàn)象--當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。
      上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。
（2） 退棧操作
    　退棧時(shí)，需將S-＞top減1
  注意：
　    ①S-＞top<0表示空棧
    　②"下溢"現(xiàn)象——當(dāng)棧空時(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。
      下溢是正常現(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。
順序棧在進(jìn)棧和退棧操作時(shí)的具體變化情況【參見(jiàn)動(dòng)畫(huà)演示】
3、順序棧的基本運(yùn)算
（1） 置棧空
  void InitStack（SeqStack *S）
    {//將順序棧置空
        S->top=-1;
    }
（2） 判棧空
  int StackEmpty（SeqStack *S）
    {
        return S->top==-1;
    }
（3） 判棧滿
  int StackFull（SeqStack *SS）
     {
       return S->top==StackSize-1;
     }
（4） 進(jìn)棧
  void Push（S，x）
     {
       if (StackFull(S))
             Error("Stack overflow"); //上溢，退出運(yùn)行
       S->data[++S->top]=x;//棧頂指針加1后將x入棧
     }
（5） 退棧
  DataType Pop（S）
    {
      if(StackEmpty(S))
           Error("Stack underflow"); //下溢，退出運(yùn)行
      return S->data[S->top--];//棧頂元素返回后將棧頂指針減1
    }

（6） 取棧頂元素
  DataType StackTop（S）
    {
       if(StackEmpty(S))
           Error("Stack is empty");
       return S->data[S->top];
     }
鏈棧 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧。

2、鏈棧的基本運(yùn)算
（1） 置棧空
      Void InitStack(LinkStack *S)
      {
             S->top=NULL;
      }
（2） 判棧空
      int StackEmpty(LinkStack *S)
      {
            return S->top==NULL;
      }
（3） 進(jìn)棧
      void Push(LinkStack *S,DataType x)
      {//將元素x插入鏈棧頭部
            StackNode *p=(StackNode *)malloc(sizeof(StackNode));
            p->data=x;
            p->next=S->top;//將新結(jié)點(diǎn)*p插入鏈棧頭部
            S->top=p;
       }
（4） 退棧
      DataType Pop(LinkStack *S)
      {
            DataType x;
            StackNode *p=S->top;//保存棧頂指針
            if(StackEmpty(S))
                  Error("Stack underflow.");  //下溢
            x=p->data;  //保存棧頂結(jié)點(diǎn)數(shù)據(jù)
            S->top=p->next;  //將棧頂結(jié)點(diǎn)從鏈上摘下
            free(p);
            return x;
       }
（5） 取棧頂元素
      DataType StackTop(LinkStack *S)
       {
            if(StackEmpty(S))
                 Error("Stack is empty.")
             return S->top->data;
        }

隊(duì)列　

隊(duì)列的定義及基本運(yùn)算

1、定義
    　隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表

（1）允許刪除的一端稱為隊(duì)頭（Front）。
　　（2）允許插入的一端稱為隊(duì)尾（Rear）。
　　（3）當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。
　　（4）隊(duì)列亦稱作先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱為FIFO表。
順序隊(duì)列

（1）順序隊(duì)列的定義
 　 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。

（2） 順序隊(duì)列的表示
　　①和順序表一樣，順序隊(duì)列用一個(gè)向量空間來(lái)存放當(dāng)前隊(duì)列中的元素。
　　②由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，設(shè)置兩個(gè)指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素在向量空間中的位置，它們的初值在隊(duì)列初始化時(shí)均應(yīng)置為0。

（3） 順序隊(duì)列的基本操作
　　①入隊(duì)時(shí)：將新元素插入rear所指的位置，然后將rear加1。
　　②出隊(duì)時(shí)：刪去front所指的元素，然后將front加1并返回被刪元素。

2、循環(huán)隊(duì)列
    　為充分利用向量空間，克服"假上溢"現(xiàn)象的方法是：將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（Circular Queue）。
鏈隊(duì)列

1、 鏈隊(duì)列的定義
  　隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。

2、 鏈隊(duì)列的基本運(yùn)算

棧和隊(duì)列的應(yīng)用實(shí)例

棧的應(yīng)用實(shí)例
隊(duì)列的應(yīng)用實(shí)例

 

Chapter 3 串

串及其運(yùn)算

串的基本概念：串（又稱字符串）是一種特殊的線性表，它的每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。
串的基本運(yùn)算

1、求串長(zhǎng)
        int strlen(char *s);//求串s的長(zhǎng)度
    【例】printf("%d",strlen(s1)); //輸出s1的串長(zhǎng)12
2、串復(fù)制
    char *strcpy(char *to,*from)；//將from串復(fù)制到to串中，并返回to開(kāi)始處指針
    【例】strcpy(s3,s1);  //s3="dir/bin/appl",s1串不變
3、聯(lián)接
    char *strcat(char *to,char *from);//將from串復(fù)制到to串的末尾，
                                      //并返回to串開(kāi)始處的指針
    【例】strcat(s3,"/"); //s3="dir/bin/appl/"
            strcat(s3,s2); //s3="dir/bin/appl/file.asm"
4、串比較
    int strcmp(char *s1,char *s2);//比較s1和s2的大小，
   //當(dāng)s1<s2、s1>s2和s1=s2時(shí)，分別返回小于0、大于0和等于0的值
    【例】result=strcmp("baker","Baker");  //result>0
            result=strcmp("12","12");  //result=0
            result=strcmp("Joe","joseph")  //result<0
5、字符定位
    char *strchr(char *s,char c);//找c在字符串s中第一次出現(xiàn)的位置，
                                 //若找到，則返回該位置，否則返回NULL
    【例】p=strchr(s2,'.'); //p指向"file"之后的位置
　　　　　　if(p) strcpy(p,".cpp"); //s2="file.cpp"

串的存儲(chǔ)結(jié)構(gòu)

串的順序存儲(chǔ)：串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配
串的鏈?zhǔn)酱鎯?chǔ)：用單鏈表方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。
串運(yùn)算的實(shí)現(xiàn)

Chapter 4 多維數(shù)組

多維數(shù)組和廣義表是一種復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特征是：一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和多個(gè)直接后繼。

多維數(shù)組

多維數(shù)組

多維數(shù)組
1、數(shù)組（向量）——常用數(shù)據(jù)類型
    　一維數(shù)組（向量）是存儲(chǔ)于計(jì)算機(jī)的連續(xù)存儲(chǔ)空間中的多個(gè)具有統(tǒng)一類型的數(shù)據(jù)元素。
    　同一數(shù)組的不同元素通過(guò)不同的下標(biāo)標(biāo)識(shí)。（a₁,a₂,…,a_n)
2、二維數(shù)組
    　二維數(shù)組A_mn可視為由m個(gè)行向量組成的向量，或由n個(gè)列向量組成的向量。

矩陣的壓縮存儲(chǔ)

矩陣的存儲(chǔ)

1、矩陣的二維數(shù)組描述
    　矩陣用二維數(shù)組描述時(shí)，存儲(chǔ)的密度為1。可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單。
2、矩陣的壓縮存儲(chǔ)
   　 矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。
特殊矩陣

1．對(duì)稱矩陣
（1）對(duì)稱矩陣
    　在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)： a_ij=a_ji 0≤i，j≤n-1則稱A為對(duì)稱矩陣

（2）三角矩陣的劃分
    　以主對(duì)角線劃分，三角矩陣有上三角矩陣和下三角矩陣兩種。
①上三角矩陣　如下圖(a)所示，它的下三角(不包括主角線)中的元素均為常數(shù)c。
②下三角矩陣　與上三角矩陣相反，它的主對(duì)角線上方均為常數(shù)c，如下圖(b)所示。

（3）對(duì)角矩陣
    　所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零的矩陣為對(duì)角矩陣。
稀疏矩陣 設(shè)矩陣A_mn中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)(即s<<m×n)，則稱A為稀疏矩陣。

其中每一個(gè)非零元素所在的行號(hào)、列號(hào)和值組成一個(gè)三元組(i，j，a_ij)，并由此三元組惟一確定。

稀疏矩陣進(jìn)行壓縮存儲(chǔ)通常有兩類方法：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

Chapter 5 廣義表

廣義表

廣義表的概念：廣義表(Lists，又稱列表)是線性表的推廣。即廣義表中放松對(duì)表元素的原子限制，容許它們具有其自身結(jié)構(gòu)。

廣義表是n(n≥0)個(gè)元素a₁，a₂，…，a_i，…，a_n的有限序列。
  其中：
    　①a_i--或者是原子或者是一個(gè)廣義表。②廣義表通常記作：Ls=( a₁，a₂，…，a_i，…，a_n)。③Ls是廣義表的名字，n為它的長(zhǎng)度。④若a_i是廣義表，則稱它為Ls的子表。

Chapter 6 樹(shù)

樹(shù)的概念

概念 樹(shù)的遞歸定義：
      樹(shù)(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹(shù)，否則它滿足如下兩個(gè)條件：
(1)有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；
(2)其余的結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的子集T_l，T₂，…，T_m，其中每個(gè)子集本身又是一棵樹(shù)，并稱其為根的子樹(shù)(Subree)。

1、樹(shù)的表示：

（1）樹(shù)形圖表示（2）嵌套集合表示法（3）凹入表表示法（4）廣義表表示法

2、樹(shù)結(jié)構(gòu)的基本術(shù)語(yǔ)：

（1）結(jié)點(diǎn)的度(Degree) 樹(shù)中的一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱為該結(jié)點(diǎn)的度(Degree)。一棵樹(shù)的度是指該樹(shù)中結(jié)點(diǎn)的最大度數(shù)。度為零的結(jié)點(diǎn)稱為葉子(Leaf)或終端結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。根結(jié)點(diǎn)又稱為開(kāi)始結(jié)點(diǎn)。

（2）孩子(Child)和雙親(Parents) 樹(shù)中某個(gè)結(jié)點(diǎn)的子樹(shù)之根稱為該結(jié)點(diǎn)的孩子(Child)或兒子，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親(Parents)或父親。同一個(gè)雙親的孩子稱為兄弟(Sibling)。

（3）路徑（path） 若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列k₁，k₂，…，k_i，使得k_i是k_i+1的雙親(1≤i<j)，則稱該結(jié)點(diǎn)序列是從k_l到k_j的一條路徑(Path)或道路。路徑的長(zhǎng)度指路徑所經(jīng)過(guò)的邊(即連接兩個(gè)結(jié)點(diǎn)的線段)的數(shù)目，等于j-1。

（4）祖先(Ancestor)和子孫(Descendant) 若樹(shù)中結(jié)點(diǎn)k到k_s存在一條路徑，則稱k是k_s的祖先(Ancestor)，k_s是k的子孫(Descendant)。

（5）結(jié)點(diǎn)的層數(shù)(Level)和樹(shù)的高度（Height）根的層數(shù)為1， 其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的高度(Height)或深度(Depth)。

（6）有序樹(shù)(OrderedTree)和無(wú)序樹(shù)(UnoderedTree) 若將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)看成是從左到右有次序的(即不能互換)，則稱該樹(shù)為有序樹(shù)；否則稱為無(wú)序樹(shù)。

（7）森林(Forest) 森林(Forest)是m(m≥0)棵互不相交的樹(shù)的集合。

二叉樹(shù)

二叉樹(shù)的定義

1.二叉樹(shù)的遞歸定義
    　二叉樹(shù)(BinaryTree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
二叉樹(shù)的性質(zhì)

性質(zhì)1 二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為2^i-1(i≥1)。

性質(zhì)2 深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)(k≥1)。

性質(zhì)3 在任意-棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n₀，度為2的結(jié)點(diǎn)數(shù)為n₂，則n_o=n₂+1。

滿二叉樹(shù)和完全二叉樹(shù)是二叉樹(shù)的兩種特殊情形。

滿二叉樹(shù)(FullBinaryTree) 一棵深度為k且有2^k-1個(gè)結(jié)點(diǎn)的二又樹(shù)稱為滿二叉樹(shù)。

完全二叉樹(shù)(Complete BinaryTree) 若一棵二叉樹(shù)至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)稱為完全二叉樹(shù)。

性質(zhì)4  具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)  該方法是把二叉樹(shù)的所有結(jié)點(diǎn)按照一定的線性次序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。結(jié)點(diǎn)在這個(gè)序列中的相互位置還能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲(chǔ)二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子。

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷 遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。

一棵非空的二叉樹(shù)由根結(jié)點(diǎn)及左、右子樹(shù)這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：
    　（1）訪問(wèn)結(jié)點(diǎn)本身(N)，（2）遍歷該結(jié)點(diǎn)的左子樹(shù)(L)，（3）遍歷該結(jié)點(diǎn)的右子樹(shù)(R)。

三種遍歷的命名
    　根據(jù)訪問(wèn)結(jié)點(diǎn)操作發(fā)生位置命名：
　　① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))——訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。
　　② LNR：中序遍歷(InorderTraversal) ——訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中(間)。
 　　③ LRN：后序遍歷(PostorderTraversal)——訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后

遍歷序列：1．遍歷二叉樹(shù)的執(zhí)行蹤跡　三種遞歸遍歷算法的搜索路線相同（如下圖虛線所示）。  

二叉鏈表的構(gòu)造

線索二叉樹(shù)

線索二叉樹(shù)

n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針（這種附加的指針?lè)Q為"線索"）。

ltag和rtag是增加的兩個(gè)標(biāo)志域，用來(lái)區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。

線索二叉樹(shù)中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。

線索化：按某種次序?qū)⒍鏄?shù)線索化的實(shí)質(zhì)是：按該次序遍歷二叉樹(shù)，在遍歷過(guò)程中用線索取代空指針。

線索二叉樹(shù)的運(yùn)算：

1．   查找某結(jié)點(diǎn)*p在指定次序下的前趨和后繼結(jié)點(diǎn)

2．遍歷線索二叉樹(shù)

樹(shù)和森林

樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換

（1）將樹(shù)轉(zhuǎn)換為二叉樹(shù)
    　樹(shù)中每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子(長(zhǎng)子)和一個(gè)右鄰的兄弟。按照這種關(guān)系很自然地就能將樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)：
　　①在所有兄弟結(jié)點(diǎn)之間加一連線；
　　②對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其長(zhǎng)子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線。

（2）將一個(gè)森林轉(zhuǎn)換為二叉樹(shù)
 具體方法是：
　　① 將森林中的每棵樹(shù)變?yōu)槎鏄?shù)
　　② 因?yàn)檗D(zhuǎn)換所得的二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)均為空，故可將各二叉樹(shù)的根結(jié)點(diǎn)視為兄弟從左至右連在一起，就形成了一棵二叉樹(shù)。

（3）把二叉樹(shù)轉(zhuǎn)換到樹(shù)和森林

方式是：若結(jié)點(diǎn)x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，…，都與y用連線連起來(lái)，最后去掉所有雙親到右孩子的連線。
樹(shù)的存儲(chǔ)結(jié)構(gòu)

1、   雙親鏈表表示法：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針parent，惟一地表示任何-棵樹(shù)。

2、   孩子鏈表表示法：孩子鏈表表示法是為樹(shù)中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。

3、  孩子兄弟鏈表表示法 : 在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域leftmostchild和rightsibling，即可得樹(shù)的孩子兄弟鏈表表示。
樹(shù)和森林的遍歷

樹(shù)的遍歷

1．樹(shù)T的前序遍歷定義：若樹(shù)T非空，則：①訪問(wèn)根結(jié)點(diǎn)R；②依次前序遍歷根R的各子樹(shù)T₁，T₂，…，T_k。

2．樹(shù)T的后序遍歷定義：若樹(shù)T非空，則：①依次后序遍歷根T的各子樹(shù)T_l，T₂，…，T_k；②訪問(wèn)根結(jié)點(diǎn)R。

森林的兩種遍歷方法

1．前序遍歷森林
    若森林非空，則：①訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；②前序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的各子樹(shù)所構(gòu)成的森林③前序遍歷除第一棵樹(shù)外其它樹(shù)構(gòu)成的森林。

2．后序遍歷森林
　　若森林非空，則:①后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的各子樹(shù)所構(gòu)成的森林；②訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；③后序遍歷除第一棵樹(shù)外其它樹(shù)構(gòu)成的森林。

哈夫曼樹(shù)及其應(yīng)用

最優(yōu)二叉樹(shù)
哈夫曼編碼

posted on 2008-11-24 16:44 isabc 閱讀(4295) 評(píng)論(8)  編輯 收藏 引用 所屬分類: C++基礎(chǔ)