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

ID:77367 · 發(fā)表于 2015-4-19 01:41

電子信息工程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日星期五

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

帳號		自動登錄	找回密碼
密碼			立即注冊

久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

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

相關(guān)帖子