计算机统考重难点班讲义数据结构-第一讲

1、数据结构数据结构重难点串讲重难点串讲讲师：翔高教育一级培训师地点：上海第一章概论第一章概论重难点导航重难点导航v 数据的三个层次：数据、数据元素、数据项数据的三个层次：数据、数据元素、数据项v 数据结构的三要素：逻辑结构、物理（存储）结构数据结构的三要素：逻辑结构、物理（存储）结构以及这种逻辑结构上所定义的操作以及这种逻辑结构上所定义的操作v 类类c语言书写规范语言书写规范v 时间复杂度、最佳（最坏、平均）时间复杂度、频时间复杂度、最佳（最坏、平均）时间复杂度、频度、时间复杂度量级度、时间复杂度量级v 空间复杂度空间复杂度v 两年的统考真题没有直接考察本章的内容，两年的统考真题没有直接考察本章

2、的内容，10年统年统考真题第考真题第42题第三问：说明你算法的时间和空间复题第三问：说明你算法的时间和空间复杂度杂度3v 【例【例1】算法的时间复杂度与】算法的时间复杂度与( )有关。有关。【武汉理工【武汉理工 2007】 a问题规模问题规模 b计算机硬件性能计算机硬件性能 c编译程序质量编译程序质量 d程序设计语言程序设计语言v 解：算法花费的时间与算法中语句的执行次数成正比解：算法花费的时间与算法中语句的执行次数成正比例，算法中哪个语句执行次多，它花费时间就多。一例，算法中哪个语句执行次多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。个算法中的语句执行次数称为语句频度或

3、时间频度。记为记为t(n)，为问题规模。算法的时间复杂度与问题的，为问题规模。算法的时间复杂度与问题的规模有关，与计算机硬件性能，程序设计语言，编译规模有关，与计算机硬件性能，程序设计语言，编译程序质量无关程序质量无关4第二章第二章 线性表线性表5重难点导航重难点导航v 线性表的操作在顺序和链式两种存储结构上实现的线性表的操作在顺序和链式两种存储结构上实现的方法以及各自的特点方法以及各自的特点v 链表是本章学习的重点和难点。要掌握头指针、头链表是本章学习的重点和难点。要掌握头指针、头结点的作用和区别；并且要学会通过画结点图来完结点的作用和区别；并且要学会通过画结点图来完成链表的生成、插入、删除

4、、遍历等操作；成链表的生成、插入、删除、遍历等操作；v 能从时间和空间复杂度两方面综合比较线性表在顺能从时间和空间复杂度两方面综合比较线性表在顺序和链式两种存储结构下的特点序和链式两种存储结构下的特点6重难点剖析线性表的顺序存储结构线性表的线性表的顺序存储结构顺序存储结构是指用一组连续的存储单是指用一组连续的存储单元依次存储线性表中的每个数据元素。元依次存储线性表中的每个数据元素。v 其中，其中，l为每个数据元素所为每个数据元素所占据的存储单元数目。占据的存储单元数目。v 相邻两个数据元素的存储相邻两个数据元素的存储位置计算公式位置计算公式v loc(ai+1)=loc(ai)+lv 线性表中

5、任意一个数据元线性表中任意一个数据元素的存储位置的计算公式素的存储位置的计算公式为：为：v loc(ai+1)=loc(a1)+(i-1)*l存储地址内存单元.da1d+la2d+2la3.d+(i-1)lai.d+(n-1)lan.v 顺序存储结构的特点：顺序存储结构的特点：v （1）利用数据元素的存储位置表示线性表中相邻数）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；储结构（物理结构）一致；v 2）在访问线性表时，可以利用上述给出的数学公式）在访问线性表时，可以利用上述给出的数学公式

6、，快速地计算出任何一个数据元素的存储地址。因，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。储结构。v 在线性表在线性表l中第中第i个数据元素之前插入数据元素个数据元素之前插入数据元素e v int listinsert(sq_list *l,int i,entrytype e) v v if (l-length=list_max

7、_length) return error; /检查是否有剩余空间检查是否有剩余空间v if (il-length+1) return error; /检查检查i值是否合理值是否合理v for (j=l-length-1;j=i-1;i+) /将线性表第将线性表第i个元素个元素之后的所有元素向后移动之后的所有元素向后移动v l.-itemj+1=l-itemj;v l-itemi-1=e; /将新元素的内容放入线性表的第将新元素的内容放入线性表的第i个个位置，位置，v l-length+; v return ok;v 插入算法的分析插入算法的分析v 假设线性表中含有假设线性表中含有n个数据元素

8、，在进行插入操作时个数据元素，在进行插入操作时，若假定在，若假定在n+1个位置上插入元素的可能性均等，个位置上插入元素的可能性均等，则平均移动元素的个数为：则平均移动元素的个数为：1n1iis2n1)i(n1n1ev 将线性表将线性表l中第中第i个数据元素删除个数据元素删除v int listdelete(sq_list *l,int i,entrytype *e)v v if (isempty(l) return error; /检测线性表是否为检测线性表是否为空空v if (il-length) return error; /检查检查i值是否合值是否合理理v *e=l-itemi-1; /

9、将欲删除的数据元素内容保留在将欲删除的数据元素内容保留在e所指示的存储单元中所指示的存储单元中v for (j=i;jlength-1;j+) /将线性表第将线性表第i+1个元素个元素之后的所有元素向前移动之后的所有元素向前移动v l-itemj-1=l-itemj;v l-length-;v return ok;v v 删除算法的分析删除算法的分析v 在进行删除操作时，若假定删除每个元素的可能性在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：均等，则平均移动元素的个数为：v 分析结论分析结论v 顺序存储结构表示的线性表，在做插入或删除操作顺序存储结构表示的线性表，在

10、做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。操作时，这一点需要值得考虑。n1idl21ni)(nn1e 线性表的链式存储结构v 线性表的链式存储结构是指用一组任意的存储单元线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容

11、，还要附加一个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有个表示它的直接后继元素存储位置的信息。假设有一个线性表（一个线性表（a,b,c,d），可用下图），可用下图2-2所示的形式所示的形式存储：存储：存储地址内容直接后继存储地址100b120.120c160.144a100.160dnull.首元素位置图图2-2 线性表链式存储结构示意图线性表链式存储结构示意图v 链式存储结构的特点链式存储结构的特点v （1）线性表中的数据元素在存储单元中的存放顺序）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；与逻辑顺序不一定一致；v （2）在对线

12、性表操作时，只能通过头指针进入链表）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。顺序存取方式。v 在在c语言中，实现线性表的链式存储结构的类型定义语言中，实现线性表的链式存储结构的类型定义v typedef strcut node /结点类型结点类型v entrytype item;v struct node *next;v

13、 node;v typedef struct /链表类型链表类型v node *head;v link_list;v 求链表求链表l的长度的长度v int listlength(link_list l)v v node *p;v int len;v for(p=l.head, len=0;p-next=null;v p=p-next,len+);v return(len);v v 在链表在链表l中第中第i个数据元素之前插入数据元素个数据元素之前插入数据元素e v int listinsert(link_list *l,int i,entrytype e) v v node *p,*s;v in

14、t j;v if (ilistlength(l)+1) return error;v s=(node*)malloc(sizeof(node);v if (s=null) return error;v s-item=e;v for (p=l-head,j=0;p&jnext;j+); v /寻找第寻找第i-1个结点个结点v s-next=p-next; p-next=s; /将将s结点插入结点插入v return ok;v v 将链表将链表l中第中第i个数据元素删除，并将其内容保存在个数据元素删除，并将其内容保存在e中。中。v int listdelete(link_list *l,int i

15、,entrytype *e)v v node *p*s;v int j;v if (ilistlength(l) return error; v /检查检查i值的合理性值的合理性v for(p=l-head, j=0;jnext,j+); v /寻找第寻找第i-1个结点个结点v s=p-next; /用用s指向将要删除的结点指向将要删除的结点v *e=s-item; v p-next=s-next; /删除删除s指针所指向的结点指针所指向的结点v free(s);v return ok;v 循环链表v 将链表中最后一个结点的将链表中最后一个结点的next域指向头结点域指向头结点head 双向循

16、环链表v 访问后继结点，只需要向后走一步，而访问前驱结访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。点，就需要转一圈。v 结论：循环链表并不适用于经常访问前驱结点的情结论：循环链表并不适用于经常访问前驱结点的情况。况。v 解决方法：在需要频繁地同时访问前驱和后继结点解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓的时候，使用双向链表。所谓双向链表双向链表。v 双向链表就是每个结点有两个指针域。一个指向后双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。继结点，另一个指向前驱结点。headprioritemnext(a)(b)经典例题分

17、析经典例题分析v 【例【例1】设计一个算法】设计一个算法int increase(linklist *l)，判定带头结点单链表，判定带头结点单链表l是否是递减的，若是是否是递减的，若是返回返回1，否则返回，否则返回0。v 【题目分析】要判断单链表是否递减，只要比较相【题目分析】要判断单链表是否递减，只要比较相邻的两个元素的值。邻的两个元素的值。1. int increase(linklist *l)2. 3. int min； 记录链表中的最小值记录链表中的最小值4. linklist *p，*q； 辅助指针辅助指针5. p=l-next；6. if(p) min=p-data； 因为链表带头

18、结点因为链表带头结点7. q=p-next;8. while(q!=null)249. 10. if(q-datamin)当前元素的值大于其相邻的前一个元当前元素的值大于其相邻的前一个元素的值，则不为降序素的值，则不为降序11. return 0；12. else13. 14. min=q-data；修改最小值修改最小值15. q=q-next；指针后移指针后移16. 17. 18. return 1；19.25第三章第三章 栈、队列和数组栈、队列和数组26重难点导航重难点导航v 栈的定义以及操作栈的定义以及操作v 栈的顺序存储结构以及链式存储结构，以及在这两栈的顺序存储结构以及链式存储结构，

19、以及在这两种结构下实现栈的基本操作；种结构下实现栈的基本操作；v 队列的定义以及操作队列的定义以及操作v 队列的循环、顺序队列以及链式队列存储结构，以队列的循环、顺序队列以及链式队列存储结构，以及在这两种结构下实现队列的基本操作及在这两种结构下实现队列的基本操作v 栈和队列具体应用的典型问题栈和队列具体应用的典型问题27线性表栈和队列都是特殊的线性表：表中数据元素之间存在着线性关系特殊性：对表的插入和删除操作受到了限制栈的顺序表示栈的顺序表示s.stacksize-1543210s.stacksize-1543210s.elems.elems.tops.topa1a2a3a4top指在栈顶元素

20、的位置上空栈： s.top=-1 栈长：s.top1二、链栈二、链栈-不带头结点的单链表不带头结点的单链表a4a3a2a1sep进栈进栈push： p-next=s; s=p;a3a2a1a4s出栈出栈pop：p=s;s=s-next;free(p);判栈空条件：判栈空条件： s=null;p 队列队列 v 队列队列（queue）是限定只能在表的一端进行插入和在）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。另一端进行删除操作的线性表。v 在表中，允许插入的一端称作在表中，允许插入的一端称作“队列尾队列尾(tail)”v 允许删除的另一端称作允许删除的另一端称作“队列头队列头(f

21、ront)”。v 队列又称队列又称fifo（first in first out 的缩写）表。的缩写）表。 队列的存储表示和操作的实现队列的存储表示和操作的实现 链队列链队列 v结构定义结构定义typedef slink queueptr; / 链队列的结链队列的结点结构和单链表相同点结构和单链表相同typedef structqueueptr front; / 队列的头指针队列的头指针queueptr rear; / 队列的尾指针队列的尾指针int length; / 队列元素个数队列元素个数 queue; / 链队列链队列循环队列循环队列v 利用顺序分配存储结构实现队列利用顺序分配存储结构

22、实现队列 v 设立两个指针设立两个指针 front 和和 rear 分别指示分别指示“队头队头”和和“队尾队尾”的位置的位置 v 空队列时，令空队列时，令 front=rear=0 v 头指针始终指向队头元素，而尾指针指向队尾元素的头指针始终指向队头元素，而尾指针指向队尾元素的下一个下一个位置位置 循环队列的结构定义循环队列的结构定义 v typedef struct elemtype *elem;/ 存储空间基址存储空间基址int rear; / 队尾指针队尾指针int front;/ 队头指针队头指针int queuesize;/ 允许的最大存储空间，允许的最大存储空间，以元素为单位以元素

23、为单位 queue; v 循环队列的初始化需要添加一个循环队列的初始化需要添加一个最大容量最大容量的参数的参数 经典例题分析经典例题分析v 【例【例1】若元素】若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是v a. d，c，e，b，f，a bc，b，d，a，e，fv c. b，c，a，e，f，d da，f，e，d，c，bv 【解析】本题考查对堆栈的基本操作。栈的操作必须符合先进后出【解析】本题考查对堆栈的基本操作。栈的操作必须符合

24、先进后出的原则，又要符合题目要求：不允许连续三次进行退栈操作。所以的原则，又要符合题目要求：不允许连续三次进行退栈操作。所以我们可以快速扫描四个选项，如果发现所给序列中出现长度大于或我们可以快速扫描四个选项，如果发现所给序列中出现长度大于或者等于者等于3的连续逆序子序列，则可排除。选项的连续逆序子序列，则可排除。选项d中出现中出现fedcb序列序列，所以正确答案为，所以正确答案为d。当然也可以依次分析四个选项的进出栈操作。当然也可以依次分析四个选项的进出栈操作序列：序列：v a. push, push, push, push, pop, pop, push, pop, pop, push, pop, pop;v b. push, push, push, pop, pop, push, pop, pop, push, pop, push, pop;v c. push, push, pop, push, pop, pop, push, push, pop, push, pop, pop;v d. push, pop, push, push, push, push, push, pop, pop, pop, pop, pop;36v 【例【例2】某队列允许在其两端进行人队操作，但仅允许在一端进行】某队列允许在其两端进行人队操作，但仅允许在一