数据结构第一讲

1、1数据结构数据结构 考研大纲解读 历年考题分布 课程分析及复习方法指导 线性结构部分内容串讲与习题讲解4大纲解读之大纲解读之考查目标考查目标1.掌握数据结构的基本概念、基本原理和掌握数据结构的基本概念、基本原理和基本方法。基本方法。 2.掌握数据的逻辑结构、存储结构及基本掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。间复杂度与空间复杂度的分析。 3.能够对数据结构基本原理和方法进行问能够对数据结构基本原理和方法进行问题的分析与求解，题的分析与求解，具备采用具备采用C或或C+或或 JAVA语言设计与实现算法的能力

2、语言设计与实现算法的能力。 5大纲解读之大纲解读之考查内容考查内容线性表线性表栈、队列和数组栈、队列和数组树与二叉树树与二叉树图图查找查找内部排序内部排序6考研大纲解读考研大纲解读历年考题分布历年考题分布课程分析及复习方法指导课程分析及复习方法指导线性结构部分内容串讲与习题讲解线性结构部分内容串讲与习题讲解7历年考试各模块所占分值历年考试各模块所占分值8考研大纲解读考研大纲解读历年考题分布历年考题分布课程分析及复习方法指导课程分析及复习方法指导线性结构部分内容串讲与习题讲解线性结构部分内容串讲与习题讲解9数据结构课程的特点数据结构课程的特点1模块性强，易于整体把握模块性强，易于整体把握 优势优

3、势栈、队列和数栈、队列和数组组线性表线性表树和二叉树树和二叉树图图排序技术排序技术查找技术查找技术第一单元第一单元 基本数据结构基本数据结构第二单元第二单元 常用数据处理常用数据处理技术技术102、主线清晰，易于梳理记忆、主线清晰，易于梳理记忆主线支线逻辑结构存储结构基本操作作实现应用定义基本术语性质逻辑关系存储思想存储结构定义基于某种存储结构插 入 、 删 除和 查 找 等 算法性能分析某种数据结构的一种或多种典型应用11查找查找查找技术主要讨论了各种经典的查找方法，查找技术主要讨论了各种经典的查找方法，每种查找方法都是每种查找方法都是按照相同的主线按照相同的主线展开。展开。（对于动态查找需

4、要讨论插入和删除操作）（对于动态查找需要讨论插入和删除操作） 查找结构查找算法查找性能分析12排序排序排序技术主要讨论了各种经典的内部排序排序技术主要讨论了各种经典的内部排序方法，每种排序方法都是方法，每种排序方法都是按照相同的主线按照相同的主线展开。展开。 基本思想排序过程排序算法性能分析13数据结构课程复习的不利之处数据结构课程复习的不利之处1.知识丰富，容易混淆知识丰富，容易混淆2.算法灵活，不易把握算法灵活，不易把握3.抽象性强，不易理解抽象性强，不易理解 14考题特点考题特点1.突出基础知识突出基础知识 单项选择题主要考核基础知识，包括基本概念、基单项选择题主要考核基础知识，包括基本

5、概念、基本技术和基本方法的运用，这部分涉及的范围广、涵盖本技术和基本方法的运用，这部分涉及的范围广、涵盖的信息量大。的信息量大。 （1）进行全面系统、细致的复习；）进行全面系统、细致的复习； （2）做大量的习题。只有这样才能熟练掌握相关知识，）做大量的习题。只有这样才能熟练掌握相关知识，加快做题速度。加快做题速度。152.重视基本技术方法的理解和应用重视基本技术方法的理解和应用 数据结构的考研试题中靠死记硬背的很少。选择数据结构的考研试题中靠死记硬背的很少。选择题的计算量增大、复杂性增大、灵活性增大，因此，题的计算量增大、复杂性增大、灵活性增大，因此，在复习时一定要注意深刻理解基本技术和方法。

6、在复习时一定要注意深刻理解基本技术和方法。 因此，在做大量习题的同时，对相关的方法进行因此，在做大量习题的同时，对相关的方法进行归纳对比，加深对基本方法和技术的理解，达到举一归纳对比，加深对基本方法和技术的理解，达到举一反三的境界。反三的境界。 163.重视算法设计能力重视算法设计能力 算法设计类试题往往多方面考核数据结构算法设计类试题往往多方面考核数据结构的运用能力和算法设计能力，所以考生平时就的运用能力和算法设计能力，所以考生平时就要注意这方面的训练。要注意这方面的训练。 （1）选择结构）选择结构 （2）用位码描述算法）用位码描述算法 （3）设计）设计“好算法好算法”17复习方法复习方法一

7、、只抓重点的复习方法一、只抓重点的复习方法二、循序渐进的复习方法二、循序渐进的复习方法 第一阶段：全面复习所有考核知识点。第一阶段：全面复习所有考核知识点。 第二阶段：做习题强化理解和记忆。第二阶段：做习题强化理解和记忆。 第三阶段：反复练习，深刻理解，灵活运用。第三阶段：反复练习，深刻理解，灵活运用。 第四阶段：背诵重点内容。第四阶段：背诵重点内容。18考研大纲解读考研大纲解读历年考题分布历年考题分布课程分析及复习方法指导课程分析及复习方法指导线性结构部分内容串讲与习题讲解线性结构部分内容串讲与习题讲解19线性结构串讲部分线性结构串讲部分 绪论绪论 线性表线性表 栈、队列和数组栈、队列和数组

8、200 绪论绪论1. 数据结构数据结构基本概念基本概念：数据、数据元素、数据项、数据对：数据、数据元素、数据项、数据对象、数据结构、数据的逻辑结构、数据的存储结构、数象、数据结构、数据的逻辑结构、数据的存储结构、数据类型、抽象数据类型。据类型、抽象数据类型。2. 算法和算法分析算法和算法分析：算法定义、算法的特性、算法的描述：算法定义、算法的特性、算法的描述方法、算法的时间复杂度、算法的空间复杂度。方法、算法的时间复杂度、算法的空间复杂度。 3. 递归算法设计：递归算法设计： 递归分为间接递归和直接递归。我们主要讨论直接递归分为间接递归和直接递归。我们主要讨论直接递归。递归。 递归模型：递归模

9、型：递归出口递归出口+递归体递归体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）算法的时间复杂度与什么有关？）算法的时间复杂度与什么有关？

10、A. 问题规模问题规模 B.计算机性能特征计算机性能特征 C. 编译程序的质量编译程序的质量 D.程序设计语言程序设计语言（3）下面算法的时间复杂度是多少？）下面算法的时间复杂度是多少？ int fact(int n) if(nnext=p;p-next=p-next32adc bi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheadaheadaheada第第1 1步步: :建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入

11、到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后33 尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单, ,但生成的链表但生成的链表中结点的次序和原数组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致, ,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上, ,为此必须增加一为此必须增加一个尾指针个尾指针r,r,使

12、其始终指向当前链表的尾结点。使其始终指向当前链表的尾结点。 采用尾插法建表的算法如下采用尾插法建表的算法如下: :34 先找到最后一个结点（尾结点），假如是先找到最后一个结点（尾结点），假如是q，执行以，执行以下操作：下操作：q-next=p;p-next=NULL;35adc bi=0 i=1 i=2 i=3head头结点头结点b采用尾插法建立单链表的过程采用尾插法建立单链表的过程36插入结点示意图插入结点示意图37删除结点示意图删除结点示意图38双链表中插入结点示意图双链表中插入结点示意图39删除结点示意图删除结点示意图 在 双 链 表在 双 链 表中删除一个中删除一个结点的过程结点的过程

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

14、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 ! = NULLDBA真题演练43真题演练真题演练44（1）设计思想）设计思想Step

15、1:分别求出分别求出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指向同一结点，指

16、向同一结点，则该结点即为所求的共同后缀的起始位置。则该结点即为所求的共同后缀的起始位置。45算法实现算法实现typedef struct Node char data; struct Node *next;SNODE; /定义结点类型SNODE *findList(SNODE *str1,SNODE *str2) int m,n; SNODE *p,*q; m=listlen(str1); /求str1的长度 O(m) n=listlen(str2); /求str2的长度 O(n)46/*下面三个循环是让下面三个循环是让p,q所指向的链表等长，所指向的链表等长，下面三个循环的时间复杂度下面三个

17、循环的时间复杂度O(max（m,n）) */ for(p=str1;mn;m-) p=p-next; for(q=str2;mn;m-) q=q-next; while(p-next!=Null & p-next!=q-next) /找到共同后缀的起点找到共同后缀的起点 p=p-next; q=q-next; return p-next;47求链表长度的函数求链表长度的函数int listLen(SNODE *head) int len=0; while(head-next!=NULL) len+; head=head-next; return len; 48时间复杂度时间复杂度很容易

18、得出算法的时间复杂度是：很容易得出算法的时间复杂度是： O（m+n）49栈和队列栈和队列栈的定义栈的定义：栈是一种只能在表的一端进行栈是一种只能在表的一端进行插入或删除操作的线性表。插入或删除操作的线性表。栈的相关术语：栈的相关术语：栈底栈底 栈顶栈顶 出栈出栈 入栈入栈 栈的主要特性：栈的主要特性：后进先出（后进先出（LIFO)在栈的操作中，若后进栈的在栈的操作中，若后进栈的元素先出栈，那么在它之前进元素先出栈，那么在它之前进栈的元素一定以栈的元素一定以逆序逆序形式出栈。形式出栈。50栈的顺序存储结构（类似于顺序表）栈的顺序存储结构（类似于顺序表） 4 4 要素要素 栈的链式存储结构（单链表

19、）栈的链式存储结构（单链表） 4 4要素要素 栈空条件：栈空条件：top=basetop=base 栈满条件：栈满条件：top-base=stacksizetop-base=stacksize 进栈进栈e e操作：将操作：将e e放在放在toptop处处,top+;,top+; 退栈操作：退栈操作：top-top-后将后将toptop处的值赋给处的值赋给e;e; 栈空条件：栈空条件：s-next=NULLs-next=NULL 栈满条件：不存在栈满条件：不存在 进栈进栈e e操作：将包含操作：将包含e e的结点插入到头结点之后的结点插入到头结点之后 （即单链表的头插法）（即单链表的头插法） 退

20、栈操作：将首元结点的值赋给退栈操作：将首元结点的值赋给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

21、-i C. n-i+1 D. 不确定3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） 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 BDC53真题演练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.

22、递归调用 B. 括号匹配 C. 表达式求值 D. A，6. 表达式a*(b+c)-d的后缀表达式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcdBDB54队列的顺序存储结构（类似于顺序栈）队列的顺序存储结构（类似于顺序栈） 队列的链式存储结构（单链表）队列的链式存储结构（单链表）队列知识小结队列知识小结溢出溢出假溢出假溢出u 队空条件：队空条件：front=rearfront=rearu 队满条件：队满条件：( (rear+1)%MaxSize=frontrear+1)%MaxSize=frontu 进队进队e e操作：将操作：将e e放在放在rea

23、rrear处处,rear=(rear+1)%MaxSize,rear=(rear+1)%MaxSizeu 出队操作：取出出队操作：取出frontfront处元素处元素e;front=(front+1)%MaxSizee;front=(front+1)%MaxSizeu 队空条件：队空条件：front=rearfront=rearu 队满条件：不存在队满条件：不存在u 进队进队e e操作：将包含操作：将包含e e的结点插入到单链表尾的结点插入到单链表尾u 出队操作：删除单链表的表头结点出队操作：删除单链表的表头结点4 要素要素4 要素要素注意只有一个注意只有一个元素的情况元素的情况55真题演练1

24、. 栈的特点是（ ）,队列的特点是（ ）,栈和队列都是（ ）。若进栈序列为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依次

25、通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A 6 B. 4 C. 3 D. 23. 用单链表表示的链式队列的队头在链表的（ ）位置。 A链头 B链尾 C链中BACCFCA564. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改5. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。 A(rear-front+m)%m Brear-front+1 C(front-re

26、ar+m)%m D(rear-front)%m6. 循环队列存储在数组A0.m中，则入队时对于rear的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 真题演练DAD577 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 8. 最大容量为n的循环队列，队尾指针是rear，队

27、头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front真题演练BB58(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

28、-c1)*k 以数组以数组Ac1.d1,c2.d2 为例为例60 特殊矩阵的主要形式有：特殊矩阵的主要形式有：（1）对称矩阵）对称矩阵（2 2）上三角矩阵下三角矩阵上三角矩阵下三角矩阵（3）对角矩阵）对角矩阵它们都是它们都是方阵方阵,即行数和列数相同。即行数和列数相同。611 对称矩阵的压缩存储 若一个n阶方阵A=(aij)nn中的元素满足性质：aij=aji 0i,jn-1且且ij则称A为对称矩阵，如下图所示。对称矩阵示例对称矩阵示例1 5 1 3 73 0 2 5 17 0 6 1 35 0 8 0 01 8 9 2 6A= a0,0 a1,0 a1,1 a2,0 a2,1 a2,2 an

29、-1,0 an-1,1 an-1,n-1A=62 对称矩阵中的元素对称矩阵中的元素关于主对角线对称关于主对角线对称，因此，让每一，因此，让每一对对称元素对对称元素aij和和aji(ij)分配一个存储空间，则分配一个存储空间，则n2个元素压缩个元素压缩存储到存储到n(n+1)/2个存储空间，能节约近一半的存储空间。个存储空间，能节约近一半的存储空间。 不失一般性，假设按不失一般性，假设按“行优先顺序行优先顺序”存储下三角形存储下三角形(包包括对角线括对角线)中的元素。中的元素。 设用一维数组设用一维数组(向量向量)B0n(n+1)/2-1存储存储n阶对称矩阵，阶对称矩阵，如下图所示。为了便于访问

30、，必须找出矩阵如下图所示。为了便于访问，必须找出矩阵A中的元素的下中的元素的下标值（标值（i,j）和向量）和向量Bk的下标值的下标值k之间的对应关系。之间的对应关系。Ba0,0 a1,0 a1,1 a2,0 a2,1 a2,2 an-1,0 an-1,n-1K 0 1 2 3 n(n-1)/2 n(n+1)/2-1对称矩阵的对称矩阵的压缩存储示例压缩存储示例63 若若ij：ai, j在下三角形中，直接保存在在下三角形中，直接保存在B中。中。ai, j之前的之前的i-1行共有元素个数：行共有元素个数： 1+2+i=i (i+1)/2 而在第而在第i行上，行上，ai j之前恰有之前恰有j个元素，因

31、此，元素个元素，因此，元素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 64 n2个元素个元素 n(n+1)/2个元素个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bkk=i(i+1)/2+ j ijj(j+1)/2+ i ij65 根据上述的下标对应关系，对于矩阵中的任意元根据上

32、述的下标对应关系，对于矩阵中的任意元素素aij，均可在一维数组，均可在一维数组B中唯一确定其位置中唯一确定其位置k；反之，；反之，对所有对所有k=0,1,2, ,n(n+1)/2-1，都能确定，都能确定Bk中的元素中的元素在矩阵中的位置在矩阵中的位置(i, j)。 称称B0n(n+1)/2-1为为n阶对称矩阵阶对称矩阵A的压缩存储。的压缩存储。2 三角矩阵三角矩阵 以主对角线划分，三角矩阵有以主对角线划分，三角矩阵有上三角上三角和和下三角下三角两两种。种。 上三角矩阵的下三角（不包括主对角线）中的元素上三角矩阵的下三角（不包括主对角线）中的元素均为常数均为常数c(一般为一般为0)。下三角矩阵正好相反，它的主对。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。角线上方均为常数，如图所示。66A0,0 a0,1 a0,n-1c a1,1