数据结构第一讲.ppt

《数据结构第一讲.ppt》由会员分享，可在线阅读，更多相关《数据结构第一讲.ppt（70页珍藏版）》请在三一办公上搜索。

1、1,数据结构,主讲 任洪庆,2,第一讲,3,本次内容,考研大纲解读历年考题分布课程分析及复习方法指导线性结构部分内容串讲与习题讲解,4,大纲解读之考查目标,1.掌握数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够对数据结构基本原理和方法进行问题的分析与求解，具备采用C或C+或 JAVA语言设计与实现算法的能力。,5,大纲解读之考查内容,线性表栈、队列和数组树与二叉树图查找内部排序,6,考研大纲解读历年考题分布课程分析及复习方法指导线性结构部分内容串讲与习题讲解,7,历年考试各模块所占分值,8,考

2、研大纲解读历年考题分布课程分析及复习方法指导线性结构部分内容串讲与习题讲解,9,数据结构课程的特点,1模块性强，易于整体把握,优势,10,2、主线清晰，易于梳理记忆,11,查找,查找技术主要讨论了各种经典的查找方法，每种查找方法都是按照相同的主线展开。（对于动态查找需要讨论插入和删除操作）,12,排序,排序技术主要讨论了各种经典的内部排序方法，每种排序方法都是按照相同的主线展开。,13,数据结构课程复习的不利之处,1.知识丰富，容易混淆2.算法灵活，不易把握3.抽象性强，不易理解,14,考题特点,1.突出基础知识 单项选择题主要考核基础知识，包括基本概念、基本技术和基本方法的运用，这部分涉及的

3、范围广、涵盖的信息量大。（1）进行全面系统、细致的复习；（2）做大量的习题。只有这样才能熟练掌握相关知识，加快做题速度。,15,2.重视基本技术方法的理解和应用 数据结构的考研试题中靠死记硬背的很少。选择题的计算量增大、复杂性增大、灵活性增大，因此，在复习时一定要注意深刻理解基本技术和方法。因此，在做大量习题的同时，对相关的方法进行归纳对比，加深对基本方法和技术的理解，达到举一反三的境界。,16,3.重视算法设计能力 算法设计类试题往往多方面考核数据结构的运用能力和算法设计能力，所以考生平时就要注意这方面的训练。（1）选择结构（2）用位码描述算法（3）设计“好算法”,17,复习方法,一、只抓重

4、点的复习方法二、循序渐进的复习方法 第一阶段：全面复习所有考核知识点。第二阶段：做习题强化理解和记忆。第三阶段：反复练习，深刻理解，灵活运用。第四阶段：背诵重点内容。,18,考研大纲解读历年考题分布课程分析及复习方法指导线性结构部分内容串讲与习题讲解,19,线性结构串讲部分,绪论 线性表 栈、队列和数组,20,0 绪论,1.数据结构基本概念：数据、数据元素、数据项、数据对象、数据结构、数据的逻辑结构、数据的存储结构、数据类型、抽象数据类型。2.算法和算法分析：算法定义、算法的特性、算法的描述方法、算法的时间复杂度、算法的空间复杂度。3.递归算法设计：递归分为间接递归和直接递归。我们主要讨论直接

5、递归。递归模型：递归出口+递归体,21,例 分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;,解：上述算法中基本操作是语句i=i*2，设其频度为T(n)，则有：2T(n)n即T(n)log2n=O(log2n)。所以，该程序段的时间复杂度为O(log2n)。,22,例题,（1）以下哪个术语和存储结构无关？A.循环队列 B.链表 C.哈希表 D.栈（2）算法的时间复杂度与什么有关？A.问题规模 B.计算机性能特征 C.编译程序的质量 D.程序设计语言（3）下面算法的时间复杂度是多少？int fact(int n)if(n=1)return 1;return n*fact(n-

6、1);A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2),23,线性表,24,1.一般线性表 线性表：具有相同特性的数据元素的一个有限序列。不是集合。,逻辑结构,25,（1）顺序表,typedef struct ElemType elemMaxSize;/*存放顺序表元素*/int length;/*存放顺序表的长度*/SqList;,动态,typedef struct ElemType*elem;/*存放顺序表元素*/int length;/*存放顺序表的长度*/int listsize;/*已申请空间的个数*/SqList;,静态,26,顺序表基本运算的实现,插入数据元素

7、算法：元素移动的次数不仅与表长n有关；插入一个元素时所需移动元素的平均次数 n2。平均时间复杂度为O(n)。,27,删除数据元素算法:元素移动的次数也与表长n有关。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。,28,（2）链表,定义单链表结点类型:typedef struct LNode ElemType data;struct LNode*next;/*指向后继结点*/LinkList;,29,定义双链表结点类型:typedef struct DNode ElemType data;struct DNode*prior;/*指向前驱结点*/str

8、uct DNode*next;/*指向后继结点*/DLinkList;,30,单链表基本运算的实现,重点：（1）头插法建表和尾插法建表算法，它是很多算法设计的基础；（2）查找、插入和删除操作。,31,头插法建表 该方法从一个空表开始,读取字符数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表的核心语句如下:,L-next=p;p-next=p-next,32,i=0,i=1,i=2,i=3,head,采用头插法建立单链表的过程,head,head,head,head,第1步:建头结点,第2步:i0,新建a结点,插入到

9、头结点之后,第3步:i1,新建d结点,插入到头结点之后,第4步:i2,新建c结点,插入到头结点之后,第5步:i3,新建b结点,插入到头结点之后,33,尾插法建表 头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下:,34,先找到最后一个结点（尾结点），假如是q，执行以下操作：q-next=p;p-next=NULL;,35,i=0,i=1,i=2,i=3,head,头结点,采用尾插法建立单链表的过程,36,插入结点

10、示意图,37,删除结点示意图,38,双链表中插入结点示意图,39,删除结点示意图,在双链表中删除一个结点的过程如右图所示:,40,顺序表和链表在存储和操作上的优缺点比较如下：,41,如果最常用的操作是取第i个结点及其前驱，最节省时间的存储方式是（）A）单链表 B）双向链表C）单循环链表 D）顺序表2 对线性表，在下列情况下应当采用链表表示的是（）A）经常需要随机地存取元素B）经常需要进行插入和删除操作C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变 3 链表不具备的特点是（）A）可随机访问任意一个结点 D）所需空间与其长度成正比 B）插入和删除不需要移动任何元素 C）不必事先估计存

11、储空间,D,B,A,真题演练,42,4 与单链表相比，双向链表的优点之一是（）。A）插入、删除操作更加简单 B）可以随机访问C）可以省略表头指针或表尾指针 D）顺序访问相邻结点更加灵活 5 在带头结点的单链表head 为空的判定条件是（）A)head=NULL B)head next=NULL C)head next=head D)head!=NULL 6.不带头结点的单链表head 为空的判定条件是（）A)head=NULL B)head next=NULL C)head next=head D)head!=NULL,D,B,A,真题演练,43,真题演练,44,（1）设计思想,Step 1:

12、分别求出str1和str2的长度m和n;Step 2:对齐两个表的表尾，令p和q分别指向两个表的表头结点，若m=n,则使p指向第m-n+1个结点，反之，则使q指向链表中的n-m+1个结点（使p和q所指的结点到表尾的长度相等），这样其中有一个指向的就是开始位置。Step 3:反复将指针p和q同步向后移动，并判断他们是否指向同一结点。若p和q指向同一结点，则该结点即为所求的共同后缀的起始位置。,45,算法实现,typedef struct Node char data;struct Node*next;SNODE;/定义结点类型SNODE*findList(SNODE*str1,SNODE*str

13、2)int m,n;SNODE*p,*q;m=listlen(str1);/求str1的长度 O(m)n=listlen(str2);/求str2的长度 O(n),46,/*下面三个循环是让p,q所指向的链表等长，下面三个循环的时间复杂度O(max（m,n）)*/for(p=str1;mn;m-)p=p-next;for(q=str2;mn;m-)q=q-next;while(p-next!=Null,47,求链表长度的函数,int listLen(SNODE*head)int len=0;while(head-next!=NULL)len+;head=head-next;return len

14、;,48,时间复杂度,很容易得出算法的时间复杂度是：O（m+n）,49,栈和队列,栈的定义：栈是一种只能在表的一端进行插入或删除操作的线性表。栈的相关术语：栈底 栈顶 出栈 入栈 栈的主要特性：后进先出（LIFO),在栈的操作中，若后进栈的元素先出栈，那么在它之前进栈的元素一定以逆序形式出栈。,栈的顺序存储结构（类似于顺序表）4 要素 栈的链式存储结构（单链表）4要素,栈空条件：top=base 栈满条件：top-base=stacksize 进栈e操作：将e放在top处,top+;退栈操作：top-后将top处的值赋给e;,栈空条件：s-next=NULL 栈满条件：不存在 进栈e操作：将包

15、含e的结点插入到头结点之后（即单链表的头插法）退栈操作：将首元结点的值赋给e并将该结点删除,栈的知识回顾,51,括号匹配问题数值转换迷宫问题表达式求值问题 如何化表达式为后缀式 如何对后缀式表达式求值,栈的应用,52,真题演练,1.一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定 B.n-i+1 C.i D.n-i2 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是()。A.i B.n-i C.n-i+1 D.不确定3.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序

16、列？（）A.5 4 3 6 1 2 B.4 5 3 2 1 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6,B,D,C,53,真题演练,4.输入序列为ABC，可以变为BCA时，经过的栈操作为（）A.push,pop,push,pop,push,pop B.push,push,pop,push,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop5.栈在（）中应用。A.递归调用 B.括号匹配 C.表达式求值 D.A，6.表达式a*(b+c)-d的后缀表达式是()。Aabcd*+-B.abc+*d-C.abc

17、*+d-D.-+*abcd,B,D,B,队列的顺序存储结构（类似于顺序栈）队列的链式存储结构（单链表）,队列知识小结,溢出假溢出,队空条件：front=rear 队满条件：(rear+1)%MaxSize=front 进队e操作：将e放在rear处,rear=(rear+1)%MaxSize 出队操作：取出front处元素e;front=(front+1)%MaxSize,队空条件：front=rear 队满条件：不存在 进队e操作：将包含e的结点插入到单链表尾 出队操作：删除单链表的表头结点,4 要素,4 要素,注意只有一个元素的情况,55,真题演练,1.栈的特点是（）,队列的特点是（）,栈

18、和队列都是（）。若进栈序列为1,2,3,4 则（）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（）是一个出队列序列。,:A.先进先出 B.后进先出 C.进优于出 D.出优于进:A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构,:A.3,2,1,4 B.3,2,4,1 C.4,2,3,1 D.4,3,2,1 F.1,2,3,4 G.1,3,2,42.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,

19、e1则栈S的容量至少应该是()。A 6 B.4 C.3 D.23.用单链表表示的链式队列的队头在链表的（）位置。A链头 B链尾 C链中,B,A,C,C,F,C,A,56,4.用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改5.假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m6.循环队列存储在数组A0.m中，则入队时对于rear的操作

20、为（）。A.rear=rear+1 B.rear=(rear+1)mod(m-1)C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1),真题演练,D,A,D,57,7 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和 5 B.2和4 C.4和2 D.5和1 8.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MOD n=front B.rear=front Crear+1=front

21、 D.(rear-l)MOD n=front,真题演练,B,B,58,(1)数组的定义 具有相同类型数据元素的有限序列,数组和稀疏矩阵,59,(2)数组的存储结构,以行序为主序:LOC(ai,j)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*k,以列序为主序 LOC(ai,j)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k,以数组Ac1.d1,c2.d2 为例,特殊矩阵的主要形式有：（1）对称矩阵（2）上三角矩阵下三角矩阵（3）对角矩阵它们都是方阵,即行数和列数相同。,1 对称矩阵的压缩存储 若一个n阶方阵A=(aij)nn中的元素满足

22、性质：aij=aji 0i,jn-1且ij则称A为对称矩阵，如下图所示。,对称矩阵中的元素关于主对角线对称，因此，让每一对对称元素aij和aji(ij)分配一个存储空间，则n2个元素压缩存储到n(n+1)/2个存储空间，能节约近一半的存储空间。不失一般性，假设按“行优先顺序”存储下三角形(包括对角线)中的元素。设用一维数组(向量)B0n(n+1)/2-1存储n阶对称矩阵，如下图所示。为了便于访问，必须找出矩阵A中的元素的下标值（i,j）和向量Bk的下标值k之间的对应关系。,若ij：ai,j在下三角形中，直接保存在B中。ai,j之前的i-1行共有元素个数：1+2+i=i(i+1)/2 而在第i行

23、上，ai j之前恰有j个元素，因此，元素ai,j与其保存在向量B中时的下标值k之间的对应关系是：k=i(i+1)/2+j ij 若ij：则aij是在上三角矩阵中。因为ai,j=aj,i，在向量B中保存的是aji。依上述分析可得：k=j(j+1)/2+i ij,n2个元素 n(n+1)/2个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bk,k=,i(i+1)/2+j ij,j(j+1)/2+i ij,根据上述的下标对应关系，对于矩阵中的任意元素aij，均可在一维数组B中唯一确定其位置k；反之，对所有k=0,1,2,n(n+1)/2-1，都能确定Bk中的元素在矩阵中的位置(

24、i,j)。称B0n(n+1)/2-1为n阶对称矩阵A的压缩存储。2 三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主对角线）中的元素均为常数c(一般为0)。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量B0.n(n+1)/2中，其中常数c存放在向量的最后一个分量中即Bn(n+1)/2。上三角矩阵元素ai j保存在向量B中时的下标值k与（i,j）之间的对应关系是：,上三角矩阵：,k=,ij时,ij时,如同对称矩阵中存储i j时的情况,下三角矩

25、阵：,k=,ij时,ij时,如同对称矩阵中存储i j时的情况,上述各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。,70,真题演练,（1）二维数组A按行顺序存储，其中每一个元素占一个存储单元。若A11的存储地址为420，A33的存储地址为446，则A55的存储地址为：A.472 B.471 C.458 D.457（2）设有一个10阶的对称矩阵A，采用压缩存储方式，以行为主序存储，a11为第一个元素，其存储地址为1，每一个元素占一个地址空间，则a85的地址为：A.13 B.33 C.32 D.40,A,B,