|
电子信息工程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空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
