电子信息工程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日星期五 于广东某供热大学某实验室
|