免费在线亚洲影院,欧美日韩综合一区在线播放

標題: 數(shù)據(jù)結(jié)構(gòu)復(fù)習v3.0_電信二班_煥楠 [打印本頁]

作者: bibi 時間: 2015-4-19 01:41
標題: 數(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ù)為 _______ �！灸暇├砉ご髮W2000二、1（1.5分）】

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

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

答案：

解釋：顯然，兩個循環(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ì)：先賦值，后加加，因為非空棧的棧頂指針始終指向棧頂元素的下一個位置上

新元素

順序棧的出棧操作：

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

{

if(�？�)

return ERROR;

e=*--S.top;

return OK;

}

注意：

判斷�？盏臈l件是：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

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，放入哨兵位置

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

取出77，放入哨兵位置

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

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

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

取出56，放入哨兵位置

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

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

共比較10次

注：

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

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

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

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

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

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

2014年6月6日星期五

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

歡迎光臨 (http://www.torrancerestoration.com/bbs/)