标题: 数据结构复习v3.0_电信二班_焕楠 [打印本页]

---

作者: bibi    时间: 2015-4-19 01:41
标题: 数据结构复习v3.0_电信二班_焕楠

                                 

电子信息工程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;

答案：

解释：显然，两个循环的循环变量是有瓜葛滴！根据楠妹第二定律，只能慢慢推导咯！

• 从第一个循环for(i=l；i<n-l；i++)可知，i的值是从1一直变到n-2（注意循环是怎样退出的，即循环条件i<n-l不满足时退出，i=n-2时还可以继续执行滴。因此i的值去到n-2而已）
• 当i=1，第二条循环语句变为for(j=n;j>=1;j--)，推出s被执行(n-1+1)=n次
  
• 当i=2，第二条循环语句变为for(j=n;j>=2;j--)，推出s被执行(n-2+1)=n-1次
  
• ……………………………………………………………………………………
  
• 当i=n-2，第二条循环语句变为for(j=n;j>=n-2;j--)，推出s被执行(n-(n-2)+1)=3次
  
• 根据等差数列求和，s被执行次啦
  
  
  3、计算机执行下面的语句时，语句x++的执行次数为（n>3）。（广工—2012年6月28日考题，题目有错误，被俺改了哈O(∩_∩)O~~  ）
  for(int  i=0;  i<n; i++)
    for(int  j=0;  j<i-3;  j++)
           x++;
  答案：
  解释：跟上面那题差不多啦亲，继续用楠妹第二定律解题
  
  

• 从第一个循环for(i=l；i<n；i++)可知，i的值是从0一直变到n-1
• 当i=0，第二条循环语句变为for(int j=0;j<-3;j++)，推出x++被执行0次
  
• 当i=1，第二条循环语句变为for(int j=0;j<-2;j++)，推出x++被执行0次
  
• 当i=2，第二条循环语句变为for(int j=0;j<-1;j++)，推出x++被执行0次
  
• 当i=3，第二条循环语句变为for(int j=0;j<0;j++)，推出x++被执行1次
  
• 当i=4，第二条循环语句变为for(int j=0;j<1;j++)，推出x++被执行2次
  
• ……………………………………………………………………………………
  
• 当i=n-1，第二条循环语句变为for(j=n;j<n-4;j++)，推出x++被执行n-4次
  
• 根据等差数列求和，x++被执行次啦
  
  第二章考点：顺序表、链表的插入、删除算法
  
  顺序表的插入：
  思路：
  
  

• 如果插入位置不合理，抛出异常
• 如果顺序表已满，动态增加容量
  
• 从最后一个元素开始向前找到插入位置，并同时把它们后移
  
• 插入
  
• 表长+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;  的理解：   
  
  

• 先把栈顶指针指向的位置放入e
• 栈顶指针指向e的下一个位置
  实质：先赋值，后加加，因为非空栈的栈顶指针始终指向栈顶元素的下一个位置上
  
  
  

              

A2

A1

              

新元素

A2

A1

顺序栈的出栈操作：

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;

}

代码都在 啦，自己背咯 ！

第四章考点：串（堆分配内存）的 连接、赋值

代码都在 啦，自己背咯亲！

第六章考点：二叉树的遍历、赫夫曼编码

二叉树的遍历：（已经定好了从左到右，以下仅对先序作说明，其它两种自己推导啦亲，嘻嘻！）

理解的关键是：递归的思想

先序（先访问根）

• 对于整棵树，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~~
  （注意递归思想的体现）
  
  
  中序（中访问根）
  
  
  后序（后访问根）
  
  
  例题（楠妹出的哟！嘻嘻！）
  亲，已知二叉树的定义如下，编写子函数void nan_mei(BiTree T,int&cnt,int &sum)求该二叉树中所有元素的个数，并求所有元素的和。拜托啦！
  typedefstruct BiTNode
  {
         int data;
         struct BiTNode *lchild,*rchild,;
  }BiTNode,*BiTree;
  
  
  
  答案：
  voidnan_mei (BiTree T , int &cnt , int &sum)  //     注意这里为什么使用引用参数
  {
         cnt=0;                              //       初始化cnt
         sum=0;                             //       初始化sum
         if(T==NULL)
                return;
         cnt++                               //      操作
         sum+=T->data;                       //      操作
         nan_mei(T->lchild);                   //      先序遍历左子树（注意这里递归了）
         nan_mei(T->rchild);                   //      先序遍历右子树（注意这里递归了）
  }
  
  
  
  
  赫夫曼编码
  例题：
  给定一组数列（5,9,36,72,11,12）分别代表字符A,B,C,D,E,F出现的频度，试画出相应的哈夫曼树（要求画出赫夫曼树德构造过程）。（15分）（广工—2012年6月28日考题）
  
  
  答案：
  
  解释：
  1、先把有权值的叶子从小到大排列
  A5   B9  E11   F12   C36  D72
  
  

• 把权值最小的两叶子A B相加作为一个新的结点14
  
  
• 将替换 A B，插入序列中，并从新从小到大排列
  E11    F12   14    C36    D72
  5、把权值最小的两叶子E F相加作为一个新的结点23
  
  6、将替换 E F，插入序列中，并从新从小到大排列
  23    14    C36    D72
  
  

• 把权值最小的两叶子 相加作为一个新的结点37
  
  
• 总之这样做下去啦，烦死楠妹啦，不做了！哼！！！我生气了，不理你了！挂就挂呗！反正你挂又不关我事，嘻嘻。有什么鸟不起的呀！
  
• 最后，赫夫曼树都为你弄好了，编码好简单呀：就把左树枝为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
  
  

                                

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~~

本题的关键是 线性探测再散列方法的使用

说明：

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

          

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次

注：

冒泡法的时间复杂度为：        

快速排序法的时间复杂度为：   

直接插入排序的时间复杂度为：

可见，快速排序法，全球公认最快的排序法。专业排序30年，不要两三百，不要四五百，只要998，对，你没听错，只要998！你就可以拥有全球最快的排序法！赶快拿钱给楠妹吧，嘻嘻！！！（但是不稳定……呜呜呜~~~~(>_<)~~~~ ）

终于写完啦，写了五个小时呀，呜呜！！！认真看哦，(⊙o⊙)哦，(⊙o⊙)哦，(⊙o⊙)哦。。。。亲！不认真看的，打死你打死你打死你，哼哼哼哼！！！

要说再见了，不舍得呀！！！呜呜呜呜呜呜呜！！！O__O”…   ~~~~(>_<)~~~~！！！！

2014年6月6日星期五

于广东某供热大学某实验室

---

欢迎光临 (http://www.51hei.com/bbs/)

Powered by Discuz! X3.1