|
電子信息工程13（2）班 吳煥楠 歡迎加QQ1435378192相互學習 歡迎加入學霸交流群293194287 全文用楠妹的口吻編寫，為了增加趣味性 新版特性：追加楠妹語言，以及部分代碼。 感謝電信1班澤銳提出的錯誤（冒泡法那里） 注：僅列出電信專業考點 第一章考點：算法的效率、復雜度 時間復雜度：算法的時間量度，用“O(***)”表示 空間復雜度：算法所需存儲空間的量度 主要考題，計算某某語句的執行次數（主要是循環體）。 方法： 1、for(i=x;i<n;i++){a} a語句執行了n-x次，注意循環條件中沒有等于號 2、for(i=x;i<=n;i++){a} a語句執行了n-x+1次，注意循環條件中有等于號，有等號就+1咯 3、for(i=x;i<n;i++) for(j=y;j<=m;j++){a} a語句執行了(n-x)(m-y+1)次，嵌套循環時，要算兩者的乘積（前提是兩個循環的循環變量無瓜葛） 例題： 1、在下面的程序段的時間復雜度為（ ）【北京工商大學 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;語句執行的次數為  次，取最高次項。其實這題直接目測都可以啦，很簡單吧親！ 2、計算機執行下面的語句時，語句s的執行次數為 _______ 。【南京理工大學2000二、1（1.5分）】 for(i=l；i<n-l；i++) for(j=n;j>=i;j--) s; 答案： 解釋：顯然，兩個循環的循環變量是有瓜葛滴！根據楠妹第二定律，只能慢慢推導咯！ 如果插入位置不合理，拋出異常 - 如果順序表已滿，動態增加容量
- 從最后一個元素開始向前找到插入位置，并同時把它們后移
- 插入
- 表長+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個位置到的數據放入e;
把從第i+1個打掃最后一個元素逐個前移一個位置;
表的長度減一;
return 1;
}
（代碼自己看書 ）
單鏈表的插入：
思路：
p指向鏈表的第一個結點，初始化j從1開始 - 當j<i時，遍歷鏈表，讓指針p向后移動，不斷指向下一結點，j++
- 如果鏈表末尾為空，說明第i個元素不存在；否則存在，此時生成一個空結點s
- 把數據e賦值給s->data
- 插入的核心語句：s->next=p->next; p->next=s;
插入的核心語句：s->next=p->next; p->next=s;的理解
s->next=p->next;的作用是把結點s的next指針指向結點p的下一個結點
p->next=s; 的作用是把結點p的next指針指向結點s
最終實現了先把結點p和結點p的下一個結點之間的直接前后驅關系斷開，然后把結點s放在它們之間。
楠妹提醒：兩句位置不可以調轉！！！納尼！！！！不懂問妹哈。
（代碼自己看書 ）
單鏈表的刪除：
思路：
p指向鏈表的第一個結點，初始化j從1開始 - 當j<i時，遍歷鏈表，讓指針p向后移動，不斷指向下一結點，j++
- 如果鏈表末尾為空，說明第i個元素不存在；否則存在
- 刪除的核心語句：p->next=q->next;
- 把q結點的數據賦值給e，作為返回
- 釋放q結點
刪除的核心語句：p->next=q->next;的理解
p->next=q->next; 的作用是把結點p的next指針，直接指向結點p的下兩個（注意）結點
最終實現了把結點p和結點q，結點q和結點q->next直接前后驅關系斷開，而直接使結點p和結點q->next構成直接前后驅關系！ (*^__^*) 嘻嘻……
（代碼自己看書 ）
第三章考點：順序棧、循環隊列的入出、初始化
本章注意點：
一、順序棧
1、棧只能在棧頂進出，后進先出
2、棧空的條件是：S.top==S.base
3、棧滿的條件是：S.top- S.base>=S.stacksize
4、非空棧的棧頂指針始終指向棧頂元素的下一個位置上
二、循環隊列
1、循環隊列只能在對頭刪除，只能在隊尾插入，先進先出
2、循環隊列滿的條件是：(Q.rear+1)%MAXQSIZE==Q.front
3、循環隊列空的條件是：Q.rear==Q.front
順序棧的入棧操作：（楠妹語言）
StatusPush(SqStack &S,SElemType e)
{
if(棧滿了)
{
增加棧的容量;
if(增加容量失敗)
exit OVERFLOW;
棧頂指針移動;
棧的大小增加;
}
把棧頂指針指向的位置放入e;
棧頂指針指向e的下一個位置;
return OK;
}
入棧操作語句 *S.top++=e; 的理解：
順序棧的出棧操作： Status Push(SqStack &S,SElemType &e) //注意這里為什么要用引用參數，不懂問楠妹哈 { if(棧空) return ERROR; e=*--S.top; return OK; } 注意： 判斷棧空的條件是：S.top==S.base e=*--S.top; 的理解： 先讓棧頂指針指向棧頂元素，然后賦值給e 實質：先減減，后刪除，因為非空棧的棧頂指針始終指向棧頂元素的下一個位置上 循環隊列的入隊： 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; } 循環隊列的出隊： 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; //保證循環 return OK; } 第四章考點：串（堆分配內存）的 連接、賦值 代碼都在 啦，自己背咯親 ！ 第六章考點：二叉樹的遍歷、赫夫曼編碼 二叉樹的遍歷：（已經定好了從左到右，以下僅對先序作說明，其它兩種自己推導啦親，嘻嘻！） 理解的關鍵是：遞歸的思想 先序（先訪問根）
- 總之這樣做下去啦，煩死楠妹啦，不做了！哼！！！我生氣了，不理你了！掛就掛唄！反正你掛又不關我事，嘻嘻。有什么鳥不起的呀！
- 最后，赫夫曼樹都為你弄好了，編碼好簡單呀：就把左樹枝為0，右樹枝為1，寫出編碼
如A 的編碼為：0100
第九章考點：哈希表、折半查找
哈希表例題：
設有一組關鍵字{14,,20,63,96,29,54}，采用哈希函數：H（key）=key mod 15 ，表長為16，用開放地址法的線性探測再散列方法解決沖突。要求：對該關鍵字序列構造哈希表，給出每個元素的查找次數，并計算查找成功的平均查找長度。（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~~本題的關鍵是 線性探測再散列方法的使用 說明： i為沖突的次數，每一次的 key都是第一次算出來那個喲 ！ 如果，則為線性探測再散列 如果，則為二次探測再散列 如果 為偽隨機序列，則為偽隨機探測再散列 解釋：老師講過，不解釋了哦！不懂上Q問我。嘻嘻。
折半查找例題： 在有序表(6,12,16,27,28,36,38,48,56,60,67)中，用折半法查找關鍵值58，需做的關鍵值比較次數為。（廣工—2012年6月28日考題）
答案：3次 解釋：
分一半，以36為中心，58和36比較，58>36 有序表變為38,48,56,60,67（注意從中心的下一個元素開始） - 再分一半，以56為中心，58和56比較，58>56
有序表變為60,67 - 剩下兩個，沒得再分一半啦親，此時比較58和60,58<60，但是60左邊木有了，嗚嗚~~~~(>_<)~~~~ ，因此58不在有序表中，查找結束，一共比較3次親O(∩_∩)O~~
第十章考點：交換排序（冒泡法、快速排序法）、直接插入排序
冒泡法例題（楠妹出的，嘻嘻）：（版本1.0和2.0中有錯）
親，你快點幫人家從小到大排列序列 56 23 77 21 ，要求用冒泡法，并且求比較次數啦親
答案：
第一輪比較：
1、56和23比較，56>23，56和23交換位置，序列變為：
23 56 77 21
2、56和77比較，56<77，56和23不交換位置，序列變為：
23 56 77 21
3、77和21比較，77>21，77和21交換位置，序列變為：
23 56 21 77
第二輪比較：
1、23和56比較，23<56，不交換
2、56和21比較，56>21，交換，序列變為：
23 21 56 77
3、56和77比較，56<77，不交換
第三輪比較：
1、23和21比較，23>21，交換，序列變為：
23 56 77
2、23和56比較，不交換
3、56和77比較，不交換
排序完啦，嘻嘻，好開心！O(∩_∩)O~~ 并且比較次數為3輪，每一輪3次，共9次！
快夸夸楠妹吧！！(*^__^*) 嘻嘻……
解釋：
冒泡法排序的思路就是不斷地相間元素比較，交換
每一次必然是石沉大海，最大一個必然去了最后，比較小的慢慢向前浮上來，所以叫楠妹冒泡法！
冒泡法排序的比較輪數為： 元素個數-1
推薦大家看看這個視頻：
http://v.ku6.com/show/T4wLiqzZ9PCOFbmcjPDuew...html?ptag=vsogou
快速排序法例題（楠妹出的）：
親，你快點幫人家從小到大排列序列 56 23 83 77 21 89 11 ，要求用快速排序法，并且求比較次數啦親
答案：
選取56作為參考元素，23 21 11比56小，都放在56的左邊；83 77 89比56大，都放在56的右邊 - 原序列變為23 21 11 56 83 77 89
- 以下分別對序列23 21 11、83 77 89遞歸使用快速排序法
- 對于序列23 21 11，選取23作為參考元素,21 11比23小，都放在23的左邊
- 序列23 21 11變為21 11 23
對于序列21 11遞歸使用快速排序法，選取21作為參考元素，11比21小，放在21的左邊（只有一個元素11，這層遞歸結束） - 對于序列83 77 89，選取83作為參考元素，77比83小，放在83的左邊，89比83大，放在83的右邊
序列83 77 89變為77 83 89（因為左右各只有一個元素，這層遞歸結束） 排序完成啦，！比較次數為6次。 直接插入排序例題（楠妹出的）： 親，你快點幫人家從小到大排列序列 56 23 77 21 ，要求用插入排序法，并且求比較次數啦親
1、取出21，放入哨兵位置
2、21和56比較，21小于56，21取代56的位置，記錄全部后移 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的位置，記錄全部后移 10、56和21比較，56大于21，56和23比較，56大于23，56和56比較，56等于56，故56留在原來位置 11、因此，最終的排序為： 共比較10次 注： 冒泡法的時間復雜度為： 快速排序法的時間復雜度為： 直接插入排序的時間復雜度為： 可見，快速排序法，全球公認最快的排序法。專業排序30年，不要兩三百，不要四五百，只要998，對，你沒聽錯，只要998！你就可以擁有全球最快的排序法！趕快拿錢給楠妹吧，嘻嘻！！！（但是不穩定……嗚嗚嗚~~~~(>_<)~~~~ ） 終于寫完啦，寫了五個小時呀，嗚嗚！！！認真看哦，(⊙o⊙)哦，(⊙o⊙)哦，(⊙o⊙)哦。。。。親！不認真看的，打死你打死你打死你，哼哼哼哼！！！ 要說再見了，不舍得呀！！！嗚嗚嗚嗚嗚嗚嗚！！！O__O”… ~~~~(>_<)~~~~！！！！ 2014年6月6日星期五 于廣東某供熱大學某實驗室
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
