數(shù)據(jù)結(jié)構(gòu)復(fù)習v3.0_電信二班_煥楠

                                 

電子信息工程13（2）班 吳煥楠

歡迎加QQ1435378192相互學習

歡迎加入學霸交流群293194287

全文用楠妹的口吻編寫，為了增加趣味性

新版特性：追加楠妹語言，以及部分代碼。

感謝電信1班澤銳提出的錯誤（冒泡法那里）

注：僅列出電信專業(yè)考點

第一章考點：算法的效率、復(fù)雜度

時間復(fù)雜度：算法的時間量度，用“O(***)”表示

空間復(fù)雜度：算法所需存儲空間的量度

主要考題，計算某某語句的執(zhí)行次數(shù)（主要是循環(huán)體）。

方法：

1、for(i=x;i<n;i++){a}   

a語句執(zhí)行了n-x次，注意循環(huán)條件中沒有等于號

2、for(i=x;i<=n;i++){a}

a語句執(zhí)行了n-x+1次，注意循環(huán)條件中有等于號，有等號就+1咯

3、for(i=x;i<n;i++)

for(j=y;j<=m;j++){a}

a語句執(zhí)行了(n-x)(m-y+1)次，嵌套循環(huán)時，要算兩者的乘積（前提是兩個循環(huán)的循環(huán)變量無瓜葛）

例題：

1、在下面的程序段的時間復(fù)雜度為（    ）【北京工商大學 2001 一、10（3分）煥楠修改版】

for(i=1;i<n;i++)

for(j=1;j<=n;j++)

      x=x+1;

A． O(2n)       B．O(n)       C．O(n2)         D．O(log2n)  

答案：C

解釋：先算x=x+1;語句執(zhí)行的次數(shù)為次，取最高次項。其實這題直接目測都可以啦，很簡單吧親！

2、計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 _______ 。【南京理工大學2000二、1（1.5分）】

  for(i=l；i<n-l；i++)

     for(j=n;j>=i;j--)

     s;

答案：

解釋：顯然，兩個循環(huán)的循環(huán)變量是有瓜葛滴！根據(jù)楠妹第二定律，只能慢慢推導(dǎo)咯！

• 從第一個循環(huán)for(i=l；i<n-l；i++)可知，i的值是從1一直變到n-2（注意循環(huán)是怎樣退出的，即循環(huán)條件i<n-l不滿足時退出，i=n-2時還可以繼續(xù)執(zhí)行滴。因此i的值去到n-2而已）
• 當i=1，第二條循環(huán)語句變?yōu)?/font>for(j=n;j>=1;j--)，推出s被執(zhí)行(n-1+1)=n次
  
• 當i=2，第二條循環(huán)語句變?yōu)?/font>for(j=n;j>=2;j--)，推出s被執(zhí)行(n-2+1)=n-1次
  
• ……………………………………………………………………………………
  
• 當i=n-2，第二條循環(huán)語句變?yōu)?/font>for(j=n;j>=n-2;j--)，推出s被執(zhí)行(n-(n-2)+1)=3次
  
• 根據(jù)等差數(shù)列求和，s被執(zhí)行次啦
  
  
  3、計算機執(zhí)行下面的語句時，語句x++的執(zhí)行次數(shù)為（n>3）。（廣工—2012年6月28日考題，題目有錯誤，被俺改了哈O(∩_∩)O~~  ）
  for(int  i=0;  i<n; i++)
    for(int  j=0;  j<i-3;  j++)
           x++;
  答案：
  解釋：跟上面那題差不多啦親，繼續(xù)用楠妹第二定律解題
  
  

• 從第一個循環(huán)for(i=l；i<n；i++)可知，i的值是從0一直變到n-1
• 當i=0，第二條循環(huán)語句變?yōu)?/font>for(int j=0;j<-3;j++)，推出x++被執(zhí)行0次
  
• 當i=1，第二條循環(huán)語句變?yōu)?/font>for(int j=0;j<-2;j++)，推出x++被執(zhí)行0次
  
• 當i=2，第二條循環(huán)語句變?yōu)?/font>for(int j=0;j<-1;j++)，推出x++被執(zhí)行0次
  
• 當i=3，第二條循環(huán)語句變?yōu)?/font>for(int j=0;j<0;j++)，推出x++被執(zhí)行1次
  
• 當i=4，第二條循環(huán)語句變?yōu)?/font>for(int j=0;j<1;j++)，推出x++被執(zhí)行2次
  
• ……………………………………………………………………………………
  
• 當i=n-1，第二條循環(huán)語句變?yōu)?/font>for(j=n;j<n-4;j++)，推出x++被執(zhí)行n-4次
  
• 根據(jù)等差數(shù)列求和，x++被執(zhí)行次啦
  
  第二章考點：順序表、鏈表的插入、刪除算法
  
  順序表的插入：
  思路：
  
  

• 如果插入位置不合理，拋出異常
• 如果順序表已滿，動態(tài)增加容量
  
• 從最后一個元素開始向前找到插入位置，并同時把它們后移
  
• 插入
  
• 表長+1
  在順序表L的第i個位置之前插入元素e
  
  
  （楠妹語言）
  int ListInsert_Sq(SqList&L,int i,ElemType e)
  {
         if(插入位置不合理)
                return 0;
         if(空間不足)
         {
                申請空間;
                if(空間申請失敗)
                       return 0;
                else
                {
                       讓順序表首地址指針指向新位置;
                       更新表的大小;
                }
         }
         else
         {
                把從第i個到最后一個元素之間的所有元素逐個后移一個位置;
                把元素e存儲在第i個位置;
                表長增一;
                return 1;
         }
  }
  
  （代碼自己看書 ）
  
  順序表的刪除：
  思路：
  
  

• 如果刪除位置不合理，拋出異常
• 取出刪除元素
  3、從刪除元素位置開始向后到最后一個元素，并同時把它們前移
  4、表長-1
  
  
  （楠妹語言）
  int ListDelete_Sq(SqList&L,int i,ElemType &e)
  {
         if(刪除位置不合理)
                return 0;
         把第i個位置到的數(shù)據(jù)放入e;
         把從第i+1個打掃最后一個元素逐個前移一個位置;
         表的長度減一;
         return 1;
  }
  （代碼自己看書 ）
  
  
  單鏈表的插入：
  思路：
  
  

• p指向鏈表的第一個結(jié)點，初始化j從1開始
• 當j<i時，遍歷鏈表，讓指針p向后移動，不斷指向下一結(jié)點，j++
  
• 如果鏈表末尾為空，說明第i個元素不存在；否則存在，此時生成一個空結(jié)點s
  
• 把數(shù)據(jù)e賦值給s->data
  
• 插入的核心語句：s->next=p->next;   p->next=s;
  
  插入的核心語句：s->next=p->next;  p->next=s;的理解
  
  s->next=p->next;的作用是把結(jié)點s的next指針指向結(jié)點p的下一個結(jié)點
  p->next=s; 的作用是把結(jié)點p的next指針指向結(jié)點s
  最終實現(xiàn)了先把結(jié)點p和結(jié)點p的下一個結(jié)點之間的直接前后驅(qū)關(guān)系斷開，然后把結(jié)點s放在它們之間。
  
  楠妹提醒：兩句位置不可以調(diào)轉(zhuǎn)！！！納尼！！！！不懂問妹哈。
  
  （代碼自己看書 ）
  
  
  單鏈表的刪除：
  思路：
  
  

• p指向鏈表的第一個結(jié)點，初始化j從1開始
• 當j<i時，遍歷鏈表，讓指針p向后移動，不斷指向下一結(jié)點，j++
  
• 如果鏈表末尾為空，說明第i個元素不存在；否則存在
  
• 刪除的核心語句：p->next=q->next;
  
• 把q結(jié)點的數(shù)據(jù)賦值給e，作為返回
  
• 釋放q結(jié)點
  
  刪除的核心語句：p->next=q->next;的理解
  
  p->next=q->next; 的作用是把結(jié)點p的next指針，直接指向結(jié)點p的下兩個（注意）結(jié)點
  
  最終實現(xiàn)了把結(jié)點p和結(jié)點q，結(jié)點q和結(jié)點q->next直接前后驅(qū)關(guān)系斷開，而直接使結(jié)點p和結(jié)點q->next構(gòu)成直接前后驅(qū)關(guān)系！                           (*^__^*) 嘻嘻……
  
  （代碼自己看書 ）
  
  
  第三章考點：順序棧、循環(huán)隊列的入出、初始化
  本章注意點：
  一、順序棧
  1、棧只能在棧頂進出，后進先出
  2、棧空的條件是：S.top==S.base
  3、棧滿的條件是：S.top- S.base>=S.stacksize
  4、非空棧的棧頂指針始終指向棧頂元素的下一個位置上
  
  二、循環(huán)隊列
  1、循環(huán)隊列只能在對頭刪除，只能在隊尾插入，先進先出
  2、循環(huán)隊列滿的條件是：(Q.rear+1)%MAXQSIZE==Q.front
  3、循環(huán)隊列空的條件是：Q.rear==Q.front
  
  順序棧的入棧操作：（楠妹語言）
  
  StatusPush(SqStack &S,SElemType e)
  {
         if(棧滿了)
         {
                增加棧的容量;
                if(增加容量失敗)
                       exit OVERFLOW;
                棧頂指針移動;
                棧的大小增加;
         }
         把棧頂指針指向的位置放入e;
         棧頂指針指向e的下一個位置;
         return OK;
  }
  
  
  入棧操作語句  *S.top++=e;  的理解：   
  
  

• 先把棧頂指針指向的位置放入e
• 棧頂指針指向e的下一個位置
  實質(zhì)：先賦值，后加加，因為非空棧的棧頂指針始終指向棧頂元素的下一個位置上
  
  
  

              

A2

A1

              

新元素

A2

A1

順序棧的出棧操作：

Status Push(SqStack &S,SElemType &e)     //注意這里為什么要用引用參數(shù)，不懂問楠妹哈

{

       if(棧空)

              return ERROR;

       e=*--S.top;

       return OK;

}

注意：

判斷棧空的條件是：S.top==S.base

e=*--S.top; 的理解：

先讓棧頂指針指向棧頂元素，然后賦值給e

實質(zhì)：先減減，后刪除，因為非空棧的棧頂指針始終指向棧頂元素的下一個位置上

循環(huán)隊列的入隊：

Status EnQueue(SqQueue &Q,QElemType e)

{

       if((Q.rear+1)%MAXQSIZE==Q.front)         //判斷隊列是否滿了

              return ERROR;

       Q.base[Q.rear]=e;                         //e入隊

       Q.rear=(Q.rear+1)%MAXQSIZE;           //防止越界

       return OK;

}

循環(huán)隊列的出隊：

Status DeQueue(SqQueue &Q,QElemType &e)

{

       if(Q.rear==Q.front)                        //判斷隊列是否空

              return ERROR;

       e=Q.base[Q.front];                        //e出隊

       Q.front=(Q.front+1)%MAXQSIZE;           //保證循環(huán)

       return OK;

}

代碼都在 啦，自己背咯 ！

第四章考點：串（堆分配內(nèi)存）的 連接、賦值

代碼都在 啦，自己背咯親！

第六章考點：二叉樹的遍歷、赫夫曼編碼

二叉樹的遍歷：（已經(jīng)定好了從左到右，以下僅對先序作說明，其它兩種自己推導(dǎo)啦親，嘻嘻！）

理解的關(guān)鍵是：遞歸的思想

先序（先訪問根）

• 對于整棵樹，A是根，先訪問它，后訪問左子樹BDGH，再訪問右子樹CEFI
• 對于樹BDGH，B是根，先訪問它，后訪問左子樹DGH，再訪問右子樹（空樹）
  
• 對于樹DGH，D是根，先訪問它，后訪問左子樹G，再訪問右子樹H
  
• 對于整棵樹，左子樹BDGH訪問完啦，再訪問右子樹CEFI
  
• 對于樹CEFI，C是根，先訪問它，后訪問左子樹EI，再訪問右子樹F
  
• 對于樹EI，E是根，先訪問它，后訪問左子樹（空樹），再訪問右子樹I
  
• 對于樹CEFI，左子樹EI訪問完啦，再訪問右子樹F
  
• 對于整棵樹，左子樹BDGH訪問完啦，右子樹CEFI也訪問完啦親O(∩_∩)O~~
  （注意遞歸思想的體現(xiàn)）
  
  
  中序（中訪問根）
  
  
  后序（后訪問根）
  
  
  例題（楠妹出的喲！嘻嘻！）
  親，已知二叉樹的定義如下，編寫子函數(shù)void nan_mei(BiTree T,int&cnt,int &sum)求該二叉樹中所有元素的個數(shù)，并求所有元素的和。拜托啦！
  typedefstruct BiTNode
  {
         int data;
         struct BiTNode *lchild,*rchild,;
  }BiTNode,*BiTree;
  
  
  
  答案：
  voidnan_mei (BiTree T , int &cnt , int &sum)  //     注意這里為什么使用引用參數(shù)
  {
         cnt=0;                              //       初始化cnt
         sum=0;                             //       初始化sum
         if(T==NULL)
                return;
         cnt++                               //      操作
         sum+=T->data;                       //      操作
         nan_mei(T->lchild);                   //      先序遍歷左子樹（注意這里遞歸了）
         nan_mei(T->rchild);                   //      先序遍歷右子樹（注意這里遞歸了）
  }
  
  
  
  
  赫夫曼編碼
  例題：
  給定一組數(shù)列（5,9,36,72,11,12）分別代表字符A,B,C,D,E,F出現(xiàn)的頻度，試畫出相應(yīng)的哈夫曼樹（要求畫出赫夫曼樹德構(gòu)造過程）。（15分）（廣工—2012年6月28日考題）
  
  
  答案：
  
  解釋：
  1、先把有權(quán)值的葉子從小到大排列
  A5   B9  E11   F12   C36  D72
  
  

• 把權(quán)值最小的兩葉子A B相加作為一個新的結(jié)點14
  
  
• 將替換 A B，插入序列中，并從新從小到大排列
  E11    F12   14    C36    D72
  5、把權(quán)值最小的兩葉子E F相加作為一個新的結(jié)點23
  
  6、將替換 E F，插入序列中，并從新從小到大排列
  23    14    C36    D72
  
  

• 把權(quán)值最小的兩葉子 相加作為一個新的結(jié)點37
  
  
• 總之這樣做下去啦，煩死楠妹啦，不做了！哼！！！我生氣了，不理你了！掛就掛唄！反正你掛又不關(guān)我事，嘻嘻。有什么鳥不起的呀！
  
• 最后，赫夫曼樹都為你弄好了，編碼好簡單呀：就把左樹枝為0，右樹枝為1，寫出編碼
  如A 的編碼為：0100
  
  
  第九章考點：哈希表、折半查找
  
  
  哈希表例題：
  
  設(shè)有一組關(guān)鍵字{14,,20,63,96,29,54}，采用哈希函數(shù)：H（key）=key mod 15 ，表長為16，用開放地址法的線性探測再散列方法解決沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，給出每個元素的查找次數(shù)，并計算查找成功的平均查找長度。（15分）（廣工—2012年6月28日考題）
  
  
  答案：
  0  1     2   3   4    5    6   7   8    9   10  11   12  13   14  15
  
  

                                

63

20

96

54

14

29

H(14) = 14 mod 15 = 14

H(20) = 5

H(63) = 3

H(96) = 6

H(29) = 14 H1= (14+1)mod 16 = 15

H(54) = 9

平均查找長度  ASL=(1*5 + 2*1)/6 =7/6

注意：

平均查找長度的計算， ，記住公式啦， O(∩_∩)O~~

本題的關(guān)鍵是 線性探測再散列方法的使用

說明：

i為沖突的次數(shù)，每一次的key都是第一次算出來那個喲！

• 如果，則為線性探測再散列
• 如果，則為二次探測再散列
• 如果 為偽隨機序列，則為偽隨機探測再散列
  解釋：老師講過，不解釋了哦！不懂上Q問我。嘻嘻。
  
  
  
  折半查找例題：
  在有序表(6,12,16,27,28,36,38,48,56,60,67)中，用折半法查找關(guān)鍵值58，需做的關(guān)鍵值比較次數(shù)為。（廣工—2012年6月28日考題）
  
  
  
  答案：3次
  解釋：
  
  

• 分一半，以36為中心，58和36比較，58>36
• 有序表變?yōu)?8,48,56,60,67（注意從中心的下一個元素開始）
• 再分一半，以56為中心，58和56比較，58>56
  
• 有序表變?yōu)?0,67
• 剩下兩個，沒得再分一半啦親，此時比較58和60,58<60，但是60左邊木有了，嗚嗚~~~~(>_<)~~~~ ，因此58不在有序表中，查找結(jié)束，一共比較3次親O(∩_∩)O~~
  
  
  
  第十章考點：交換排序（冒泡法、快速排序法）、直接插入排序
  
  冒泡法例題（楠妹出的，嘻嘻）：（版本1.0和2.0中有錯）
  親，你快點幫人家從小到大排列序列 56  23 77  21 ，要求用冒泡法，并且求比較次數(shù)啦親
  
  答案：
  第一輪比較：
  1、56和23比較，56>23，56和23交換位置，序列變?yōu)椋?/font>
  23  56 77  21
  
  2、56和77比較，56<77，56和23不交換位置，序列變?yōu)椋?/font>
  23  56 77  21
  
  3、77和21比較，77>21，77和21交換位置，序列變?yōu)椋?/font>
  23  56 21  77
  
  第二輪比較：
  1、23和56比較，23<56，不交換
  
  2、56和21比較，56>21，交換，序列變?yōu)椋?/font>
  23  21 56  77
  
  3、56和77比較，56<77，不交換
  
  第三輪比較：
  1、23和21比較，23>21，交換，序列變?yōu)椋?/font>
  
  

• 23  56  77
  
  2、23和56比較，不交換
  
  3、56和77比較，不交換
  
  排序完啦，嘻嘻，好開心！O(∩_∩)O~~  并且比較次數(shù)為3輪，每一輪3次，共9次！
  快夸夸楠妹吧！！(*^__^*) 嘻嘻……
  
  解釋：
  冒泡法排序的思路就是不斷地相間元素比較，交換
  每一次必然是石沉大海，最大一個必然去了最后，比較小的慢慢向前浮上來，所以叫楠妹冒泡法！
  冒泡法排序的比較輪數(shù)為： 元素個數(shù)-1
  
  推薦大家看看這個視頻：
  http://v.ku6.com/show/T4wLiqzZ9PCOFbmcjPDuew...html?ptag=vsogou
  
  快速排序法例題（楠妹出的）：
  親，你快點幫人家從小到大排列序列 56  23 83  77  21 89  11 ，要求用快速排序法，并且求比較次數(shù)啦親
  
  
  答案：
  
  

• 選取56作為參考元素，23  21  11比56小，都放在56的左邊；83  77  89比56大，都放在56的右邊
• 原序列變?yōu)?/font>23 21 11 56 83 77 89
  
• 以下分別對序列23 21 11、83 77 89遞歸使用快速排序法
  
• 對于序列23 21 11，選取23作為參考元素,21 11比23小，都放在23的左邊
  
• 序列23 21 11變?yōu)?/font>21 11 23
  
• 對于序列21 11遞歸使用快速排序法，選取21作為參考元素，11比21小，放在21的左邊（只有一個元素11，這層遞歸結(jié)束）
• 對于序列83 77 89，選取83作為參考元素，77比83小，放在83的左邊，89比83大，放在83的右邊
  
• 序列83 77 89變?yōu)?7 83 89（因為左右各只有一個元素，這層遞歸結(jié)束）
• 排序完成啦，！比較次數(shù)為6次。
  直接插入排序例題（楠妹出的）：
  親，你快點幫人家從小到大排列序列 56  23 77  21 ，要求用插入排序法，并且求比較次數(shù)啦親
  
  
  1、取出21，放入哨兵位置
  
  
  

          

21

56

23

77

21

2、21和56比較，21小于56，21取代56的位置，記錄全部后移

          

21

56

23

77

• 取出77，放入哨兵位置
  
  
  

          

77

21

56

23

77

5、77和21比較，77大于21，77與56比較，77大于56，77與23比較，77大于23，77與77比較，77等于77，故77留在原來位置  

6、取出23，放入哨兵位置

          

23

21

56

23

77

7、23和21比較，23大于21，23與56比較，23小于56，23取代56的位置，記錄全部后移

          

21

23

56

77

• 取出56，放入哨兵位置
  
  
  

          

56

21

23

56

77

10、56和21比較，56大于21，56和23比較，56大于23，56和56比較，56等于56，故56留在原來位置

11、因此，最終的排序為：

        

21

23

56

77

共比較10次

注：

冒泡法的時間復(fù)雜度為：        

快速排序法的時間復(fù)雜度為：   

直接插入排序的時間復(fù)雜度為：

可見，快速排序法，全球公認最快的排序法。專業(yè)排序30年，不要兩三百，不要四五百，只要998，對，你沒聽錯，只要998！你就可以擁有全球最快的排序法！趕快拿錢給楠妹吧，嘻嘻！！！（但是不穩(wěn)定……嗚嗚嗚~~~~(>_<)~~~~ ）

終于寫完啦，寫了五個小時呀，嗚嗚！！！認真看哦，(⊙o⊙)哦，(⊙o⊙)哦，(⊙o⊙)哦。。。。親！不認真看的，打死你打死你打死你，哼哼哼哼！！！

要說再見了，不舍得呀！！！嗚嗚嗚嗚嗚嗚嗚！！！O__O”…   ~~~~(>_<)~~~~！！！！

2014年6月6日星期五

于廣東某供熱大學某實驗室