计算机统考重难点班讲义(数据结构)-第一讲.ppt
数据结构重难点串讲,讲师：翔高教育一级培训师地点：上海,第一章概论,重难点导航,数据的三个层次：数据、数据元素、数据项数据结构的三要素：逻辑结构、物理（存储）结构以及这种逻辑结构上所定义的操作类C语言书写规范时间复杂度、最佳（最坏、平均）时间复杂度、频度、时间复杂度量级空间复杂度两年的统考真题没有直接考察本章的内容，10年统考真题第42题第三问：说明你算法的时间和空间复杂度,3,【例1】算法的时间复杂度与()有关。【武汉理工 2007】A问题规模 B计算机硬件性能 C编译程序质量 D程序设计语言解：算法花费的时间与算法中语句的执行次数成正比例，算法中哪个语句执行次多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)，为问题规模。算法的时间复杂度与问题的规模有关，与计算机硬件性能，程序设计语言，编译程序质量无关,4,第二章 线性表,5,重难点导航,线性表的操作在顺序和链式两种存储结构上实现的方法以及各自的特点链表是本章学习的重点和难点。要掌握头指针、头结点的作用和区别；并且要学会通过画结点图来完成链表的生成、插入、删除、遍历等操作；能从时间和空间复杂度两方面综合比较线性表在顺序和链式两种存储结构下的特点,6,重难点剖析,线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。,其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L,顺序存储结构的特点：（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。,在线性表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个位置，L-length+;return OK;,插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,将线性表L中第i个数据元素删除int ListDelete(SQ_LIST*L,int i,EntryType*e)if(IsEmpty(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;,删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2-2所示的形式存储：,图2-2 线性表链式存储结构示意图,链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,在C语言中，实现线性表的链式存储结构的类型定义typedef strcut node/结点类型 EntryType item;struct node*next;NODE;typedef struct/链表类型 NODE*head;LINK_LIST;,求链表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 ERROR;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=0;jnext,j+);/寻找第i-1个结点 s=p-next;/用s指向将要删除的结点*e=s-item;p-next=s-next;/删除s指针所指向的结点 free(s);return OK;,循环链表将链表中最后一个结点的next域指向头结点,双向循环链表访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。结论：循环链表并不适用于经常访问前驱结点的情况。解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。,(a),(b),经典例题分析,【例1】设计一个算法int increase(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)当前元素的值大于其相邻的前一个元素的值，则不为降序 return 0；else min=q-data；修改最小值 q=q-next；指针后移 return 1；,25,第三章 栈、队列和数组,26,重难点导航,栈的定义以及操作栈的顺序存储结构以及链式存储结构，以及在这两种结构下实现栈的基本操作；队列的定义以及操作队列的循环、顺序队列以及链式队列存储结构，以及在这两种结构下实现队列的基本操作栈和队列具体应用的典型问题,27,线性表,栈和队列都是,特殊的,线性表：表中数据元素之间存在着线性关系,特殊性：对表的插入和删除操作受到了限制,栈的顺序表示,a1,a2,a3,a4,Top指在栈顶元素的位置上,空栈：S.Top=-1 栈长：S.Top1,二、链栈-不带头结点的单链表,进栈Push：p-next=S;S=p;,出栈Pop：p=S;S=S-next;free(p);判栈空条件：S=NULL;,队列,队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。在表中，允许插入的一端称作“队列尾(tail)”允许删除的另一端称作“队列头(front)”。队列又称FIFO（First In First Out 的缩写）表。,队列的存储表示和操作的实现 链队列,结构定义typedef SLink QueuePtr;/链队列的结点结构和单链表相同typedef structQueuePtr front;/队列的头指针QueuePtr rear;/队列的尾指针int length;/队列元素个数 Queue;/链队列,循环队列,利用顺序分配存储结构实现队列 设立两个指针 front 和 rear 分别指示“队头”和“队尾”的位置 空队列时，令 front=rear=0 头指针始终指向队头元素，而尾指针指向队尾元素的下一个位置,循环队列的结构定义,typedef struct ElemType*elem;/存储空间基址int rear;/队尾指针int front;/队头指针int queuesize;/允许的最大存储空间，以元素为单位 Queue;循环队列的初始化需要添加一个最大容量的参数,经典例题分析,【例1】若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是A.d，c，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,Push,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，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,
