欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標(biāo)題: 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)v3.0_電信二班_煥楠 [打印本頁]
作者: bibi    時(shí)間: 2015-4-19 01:41
標(biāo)題: 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)v3.0_電信二班_煥楠
                                 
電子信息工程13（2）班 吳煥楠
歡迎加QQ1435378192相互學(xué)習(xí)
歡迎加入學(xué)霸交流群293194287
全文用楠妹的口吻編寫，為了增加趣味性
新版特性：追加楠妹語言，以及部分代碼。
感謝電信1班澤銳提出的錯(cuò)誤（冒泡法那里）
注：僅列出電信專業(yè)考點(diǎn)
第一章考點(diǎn)：算法的效率、復(fù)雜度
時(shí)間復(fù)雜度：算法的時(shí)間量度，用“O(***)”表示
空間復(fù)雜度：算法所需存儲(chǔ)空間的量度
主要考題，計(jì)算某某語句的執(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)時(shí)，要算兩者的乘積（前提是兩個(gè)循環(huán)的循環(huán)變量無瓜葛）
例題：
1、在下面的程序段的時(shí)間復(fù)雜度為（    ）【北京工商大學(xué) 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ù)為次，取最高次項(xiàng)。其實(shí)這題直接目測都可以啦，很簡單吧親！
2、計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為 _______ 。【南京理工大學(xué)2000二、1（1.5分）】
  for(i=l；i<n-l；i++)
     for(j=n;j>=i;j--)
     s;
答案：
解釋：顯然，兩個(gè)循環(huán)的循環(huán)變量是有瓜葛滴！根據(jù)楠妹第二定律，只能慢慢推導(dǎo)咯！
              
  
  
  
  
  
                                       
  
  
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
實(shí)質(zhì)：先減減，后刪除，因?yàn)榉强諚５臈ｍ斨羔樖冀K指向棧頂元素的下一個(gè)位置上
循環(huán)隊(duì)列的入隊(duì)：
Status EnQueue(SqQueue &Q,QElemType e)
{
       if((Q.rear+1)%MAXQSIZE==Q.front)         //判斷隊(duì)列是否滿了
              return ERROR;
       Q.base[Q.rear]=e;                         //e入隊(duì)
       Q.rear=(Q.rear+1)%MAXQSIZE;           //防止越界
       return OK;
}
循環(huán)隊(duì)列的出隊(duì)：
Status DeQueue(SqQueue &Q,QElemType &e)
{
       if(Q.rear==Q.front)                        //判斷隊(duì)列是否空
              return ERROR;
       e=Q.base[Q.front];                        //e出隊(duì)
       Q.front=(Q.front+1)%MAXQSIZE;           //保證循環(huán)
       return OK;
}
代碼都在 啦，自己背咯 ！
第四章考點(diǎn)：串（堆分配內(nèi)存）的 連接、賦值
代碼都在 啦，自己背咯親！
第六章考點(diǎn)：二叉樹的遍歷、赫夫曼編碼
二叉樹的遍歷：（已經(jīng)定好了從左到右，以下僅對先序作說明，其它兩種自己推導(dǎo)啦親，嘻嘻！）
理解的關(guān)鍵是：遞歸的思想
先序（先訪問根）
                                
  
  
  
  
  
  
  
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
注意：
平均查找長度的計(jì)算， ，記住公式啦， O(∩_∩)O~~
本題的關(guān)鍵是 線性探測再散列方法的使用
說明：
i為沖突的次數(shù)，每一次的key都是第一次算出來那個(gè)喲！
          
  
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、因此，最終的排序?yàn)椋?/div>
        
  
21
  
  
23
  
  
56
  
  
77
  
共比較10次
注：
冒泡法的時(shí)間復(fù)雜度為：        
快速排序法的時(shí)間復(fù)雜度為：   
直接插入排序的時(shí)間復(fù)雜度為：
可見，快速排序法，全球公認(rèn)最快的排序法。專業(yè)排序30年，不要兩三百，不要四五百，只要998，對，你沒聽錯(cuò)，只要998！你就可以擁有全球最快的排序法！趕快拿錢給楠妹吧，嘻嘻！！！（但是不穩(wěn)定……嗚嗚嗚~~~~(>_<)~~~~ ）
終于寫完啦，寫了五個(gè)小時(shí)呀，嗚嗚！！！認(rèn)真看哦，(⊙o⊙)哦，(⊙o⊙)哦，(⊙o⊙)哦。。。。親！不認(rèn)真看的，打死你打死你打死你，哼哼哼哼！！！
要說再見了，不舍得呀！！！嗚嗚嗚嗚嗚嗚嗚！！！O__O”…   ~~~~(>_<)~~~~！！！！
2014年6月6日星期五
于廣東某供熱大學(xué)某實(shí)驗(yàn)室





歡迎光臨 (http://www.raoushi.com/bbs/) Powered by Discuz! X3.1