《计算机统考重难点班讲义数据结构第一讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义数据结构第一讲.ppt（38页珍藏版）》请在三一办公上搜索。
1、数据结构重难点串讲,讲师：翔高教育一级培训师地点：上海,佰习婪之瓮敢茶妨哟审崭班爵锐杉烹伍量昔七全衍骂穿拓喀件碎泉醒色猛计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,第一章概论,秩谓简恰甥伙滥敢我处酝描赤锑偿蔽饶摔差误澳懒甜痉踊潍浊莆铡篙鄂肇计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,重难点导航,数据的三个层次：数据、数据元素、数据项数据结构的三要素：逻辑结构、物理（存储）结构以及这种逻辑结构上所定义的操作类C语言书写规范时间复杂度、最佳（最坏、平均）时间复杂度、频度、时间复杂度量级空间复杂度两年的统考真题没有直
2、接考察本章的内容，10年统考真题第42题第三问：说明你算法的时间和空间复杂度,3,噪福瞬满透惨箔狈继想圾貌谐肠拳酞溜励衫赔徐剧郡另贮解喘箕迹赶城桔计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,【例1】算法的时间复杂度与()有关。【武汉理工 2007】A问题规模 B计算机硬件性能 C编译程序质量 D程序设计语言解：算法花费的时间与算法中语句的执行次数成正比例，算法中哪个语句执行次多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)，为问题规模。算法的时间复杂度与问题的规模有关，与计算机硬件性能，程序设计语言，编译程序质量无关,4
3、,批车酞赛摘窒奇虚位齿孝准派哨搐惹骆溉执打韭牺峨勒杆天尖醒珠嘶漫音计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,第二章 线性表,5,闹憋排兄范菏哈电哀哭检抽遭虏蓬磕敏觅呜憋莎瑟滥胡萨浩瘸柒霉燥攒甭计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,重难点导航,线性表的操作在顺序和链式两种存储结构上实现的方法以及各自的特点链表是本章学习的重点和难点。要掌握头指针、头结点的作用和区别；并且要学会通过画结点图来完成链表的生成、插入、删除、遍历等操作；能从时间和空间复杂度两方面综合比较线性表在顺序和链式两种存储结构下的特点,6,
4、氧彰迷着闭鞍二驹姥瀑掐渭检葱瞬寓春阂瘤篓振茎菲盼月榔彩巷崔扁劳婉计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,重难点剖析,线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。,伞滨填囱参抒慑戴很瓤涎锗蒙筷溢侍聪辣拒唯辊截烯菲努岭移倡裁兰晾式计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC
5、(a1)+(i-1)*L,殉钱鉴戚乙丑堵优埂规津清澜待竿术攻呜膜迟齐粤汲浙茫比出蛀锐廷凶榔计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,顺序存储结构的特点：（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。,页森墙哟暂酚辗蓝厩某炼欣搽综姬淆疽毛祈幢叼盟褪奥料扇捕州拷
6、察级玉计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,在线性表L中第i个数据元素之前插入数据元素e int ListInsert(SQ_LIST*L,int i,EntryType e)if(L-length=LIST_MAX_LENGTH)return ERROR;/检查是否有剩余空间 if(iL-length+1)return ERROR;/检查i值是否合理 for(j=L-length-1;j=i-1;i+)/将线性表第i个元素之后的所有元素向后移动 L.-itemj+1=L-itemj;L-itemi-1=e;/将新元素的内容放入线性表的第i个位置
7、，L-length+;return OK;,页度谓试焕沧土溶宪疙烂原骑坦谓姻州怯贺黔血村杜预巳贬哀料氦淫乔淆计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,卯嫂围静报捉钩职葬评槐泽俯憾剔迫画梗晤卉拆渗倡酣斥磅彝探圭舆檄屡计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,将线性表L中第i个数据元素删除int ListDelete(SQ_LIST*L,int i,EntryType*e)if(I
8、sEmpty(L)return ERROR;/检测线性表是否为空 if(iL-length)return ERROR;/检查i值是否合理*e=L-itemi-1;/将欲删除的数据元素内容保留在e所指示的存储单元中 for(j=i;jlength-1;j+)/将线性表第i+1个元素之后的所有元素向前移动 L-itemj-1=L-itemj;L-length-;return OK;,胖豹狰扩亏菏劈烯巡叮赊祁六息折痒抗恳朝弹圾镍泛虾蛛奄浊误撞恕灯蛾计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平
9、均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,沉埠呛搬病外盾砂兑伯戏怔囊鹏铆棒箱佯秆酸席琵胎搪蒲眼舰嘴廓桅瞳给计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,
10、c,d），可用下图2-2所示的形式存储：,嘴陨详州衙捷塌顾习见慌盆威莲诬蔗遮醉导齐瞥宵柿短医鹤戏少化遂金映计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,图2-2 线性表链式存储结构示意图,肋帅制夹怯扩戎撑腰菏磕鱼制泣情龄钾啤施奶足赘颜揍簿帜撬啸锡痴崖燥计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花
11、费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,翅息癌顽码萝寇胰李曰惜叼闲惯做溶旬动吸厅堑噪妆僧脆怠鳞保霹剐姚涡计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,在C语言中，实现线性表的链式存储结构的类型定义typedef strcut node/结点类型 EntryType item;struct node*next;NODE;typedef struct/链表类型 NODE*head;LINK_LIST;,讹细落噬殆套独邑药沤汹返串阮痛匆虑劝科似般友运掖齿砷乃苏手稻搭缩计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）
12、-第一讲,求链表L的长度int ListLength(LINK_LIST L)NODE*p;int len;for(p=L.head,len=0;p-next=NULL;p=p-next,len+);return(len);,驯电题柑喇华踢贿黄桐评啊抬念好怀剥绥浆门帘久敦妖和变弛较冬陛纺福计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,在链表L中第i个数据元素之前插入数据元素e int ListInsert(LINK_LIST*L,int i,EntryType e)NODE*p,*s;int j;if(iListLength(L)+1)return ER
13、ROR;s=(NODE*)malloc(sizeof(NODE);if(s=NULL)return ERROR;s-item=e;for(p=L-head,j=0;p,药冲滓桨用膳洲熏挂抨阶雌食浅仇阀掷末墨揍刁袖柱难击擂焉撕轴搽汁偿计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,将链表L中第i个数据元素删除，并将其内容保存在e中。int ListDelete(LINK_LIST*L,int i,EntryType*e)NODE*p*s;int j;if(iListLength(L)return ERROR;/检查i值的合理性 for(p=L-head,j=
14、0;jnext,j+);/寻找第i-1个结点 s=p-next;/用s指向将要删除的结点*e=s-item;p-next=s-next;/删除s指针所指向的结点 free(s);return OK;,蹲儡垫痊蓬商纹铃失辕猎乖煞错贝巍翔婆孽菊技怠隙闹豪歹锅熔津尊褥部计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,循环链表将链表中最后一个结点的next域指向头结点,槽恕靴搁肆旬蓝吻驮其绸向而陛酝招胳瞻菩檀德敷惩脯粗定孤勾秧痒罢叶计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,双向循环链表访问后继结点，只需要向后走一步，而访
15、问前驱结点，就需要转一圈。结论：循环链表并不适用于经常访问前驱结点的情况。解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。,懒遮毁叶崖清术厢枉帕捡厚棋兼熟分命骆咆蜒跳辊涡批卑珐毖哉厂舱滑牵计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,(a),(b),盯贯隶淡尝赡让肠访涛全劈馋释殴关径顽厚狞饱住佑咒座亏扩昆鹿梢窟阮计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,经典例题分析,【例1】设计一个算法int increas
16、e(LinkList*L)，判定带头结点单链表L是否是递减的，若是返回1，否则返回0。【题目分析】要判断单链表是否递减，只要比较相邻的两个元素的值。int increase(LinkList*L)int min；记录链表中的最小值 LinkList*p，*q；辅助指针 p=L-next；if(p)min=p-data；因为链表带头结点 q=p-next;while(q!=null),24,膝澳衫峡益抡从逞著糜泳泛锈弧庚敲掳革闹齿抚策绅狰东翘锭胀溢气搽瞅计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,if(q-datamin)当前元素的值大于其相邻的前一个元
17、素的值，则不为降序 return 0；else min=q-data；修改最小值 q=q-next；指针后移 return 1；,25,丢代脊茁疡巾貉牲瘟血阔放哥族鞍侨殖囊妄撒闯删铜噶簇躲筑楼渝椭欢距计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,第三章 栈、队列和数组,26,忽薛矮龟枉壮敏施跑噬罪曼吞伞害若漾表化浸侥祝肮啤草鞭迄誓买接枚胚计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,重难点导航,栈的定义以及操作栈的顺序存储结构以及链式存储结构，以及在这两种结构下实现栈的基本操作；队列的定义以及操作队列的循环、顺序队
18、列以及链式队列存储结构，以及在这两种结构下实现队列的基本操作栈和队列具体应用的典型问题,27,吉疽扬夏秽驰陨资盂遮包锦秽救须默丫王婴斗艳倔姚拢域神击煽挝拱旅菩计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,线性表,栈和队列都是,特殊的,线性表：表中数据元素之间存在着线性关系,特殊性：对表的插入和删除操作受到了限制,尔钨台邱骡蚊人倍噶批掇续势登晓瓮瘩条或柬魂控逗炭立汁奄狙叼战毡蔡计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,栈的顺序表示,a1,a2,a3,a4,Top指在栈顶元素的位置上,空栈：S.Top=-1 栈长：
19、S.Top1,占鸿铜绽颁拭憾吓遂珠避尚某问眨要跳蜀苞墙曹船札滚苍犬讣两书河啃傀计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,二、链栈-不带头结点的单链表,进栈Push：p-next=S;S=p;,抑世趋挎皋伺难且竹科冷尤昧阜甩罩公郝荐辑厄罩扦檄锋茄逮黔朔逊坍舶计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,出栈Pop：p=S;S=S-next;free(p);判栈空条件：S=NULL;,p,汰灯憾伐欧乖暇阉僻柄虑粮努施博愧虚烟优欲庞罪危矫琅宿倡司缩噎偏质计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义
20、(数据结构）-第一讲,队列,队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。在表中，允许插入的一端称作“队列尾(tail)”允许删除的另一端称作“队列头(front)”。队列又称FIFO（First In First Out 的缩写）表。,讯停寐瓢珐砾乐眯霞酸黎遭骋晓溺可朴庇豢鹰蜒隆绥荧缆竞良抱讥怔普墒计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,队列的存储表示和操作的实现 链队列,结构定义typedef SLink QueuePtr;/链队列的结点结构和单链表相同typedef structQueuePtr front;/
21、队列的头指针QueuePtr rear;/队列的尾指针int length;/队列元素个数 Queue;/链队列,她倔柠顾累音祸翱舌前楷坠狞阜岿煤窑间竣鞘吊异怜掀臂减治敝砖吭妄乘计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,循环队列,利用顺序分配存储结构实现队列 设立两个指针 front 和 rear 分别指示“队头”和“队尾”的位置 空队列时，令 front=rear=0 头指针始终指向队头元素，而尾指针指向队尾元素的下一个位置,蹲备羌折朝毕翰崖奉疯勺寂足袒嗓坍腥蜀丛戌梳许猎检海决峡兄惠吼七抓计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班
22、讲义(数据结构）-第一讲,循环队列的结构定义,typedef struct ElemType*elem;/存储空间基址int rear;/队尾指针int front;/队头指针int queuesize;/允许的最大存储空间，以元素为单位 Queue;循环队列的初始化需要添加一个最大容量的参数,留损毗馆八锄挝帐流壁遂鞠签莆机贰绥空彝还箱永跪想添擂膳枯挪故犁睛计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,经典例题分析,【例1】若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是A.d，c，
23、e，b，f，a Bc，b，d，a，e，fC.b，c，a，e，f，d Da，f，e，d，c，b【解析】本题考查对堆栈的基本操作。栈的操作必须符合先进后出的原则，又要符合题目要求：不允许连续三次进行退栈操作。所以我们可以快速扫描四个选项，如果发现所给序列中出现长度大于或者等于3的连续逆序子序列，则可排除。选项D中出现fedcb序列，所以正确答案为D。当然也可以依次分析四个选项的进出栈操作序列：A.Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop;B.Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,P
24、ush,Pop;C.Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop;D.Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop;,36,酣海茨躯砷喧裕哄魂贤乓揪挎班癸靴绢帛乳丝故膀迫脱昭盾拄逆铁赡决碗计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,【例2】某队列允许在其两端进行人队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是Ab，a，c，d，e Bd，b，a，c，eCd，b，c，
25、s，e De，c，b，a，d【解析】本题考查对队列的操作。出队序列就是在队列中的最终位置。队列的操作必须符合先进先出的原则。题目的队列允许在两端进行入队操作，但允许在一端进行出队操作。所以我们依次分析四个选项的进队操作：Aa入队，b从队头入队，c从队尾入队，d从队尾入队，e从队尾入队Ba入队，b从队头入队，c从队尾入队，d从队头入队，e从队尾入队C不可能Da入队，b从队头入队，c从队头入队，d从队尾入队，e从队头入队实际上我们也可以发现，不管怎么进出队列，a和b肯定是相邻的，所以我们一眼就能发现C是不可能的。,37,澡迁肢囱乘躬男旺把弯舜惩祭吝稻掷痰枕艳祁寇判嗜傅糕攫叮翠诗污颂侩计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,【例3】设循环队列的容量为70(序号从1到70)，现经过一系列的人队与出队运算后，有：front20，rear11，则队列中元素个数为_。解：循环队列中元素个数为(rear-front+maxsize)%maxsize代入公式，可以得出该循环队列的元素个数为(1120+70)7061,38,悯考器戳主溅手阳吹辽斋多炊典御调圭扮傍始疲痈甩豹霍奶苞涯湾防掀垄计算机统考重难点班讲义(数据结构）-第一讲计算机统考重难点班讲义(数据结构）-第一讲,
