简单数据结构.pptx

《简单数据结构.pptx》由会员分享，可在线阅读，更多相关《简单数据结构.pptx（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性表线性表是最简单也是最常用的一种数据结构。例如，C语言中的数组就是线性表应用的一个典型代表。第1页/共92页线性表的基本概念线性表是由n（n0）个类型相同的数据元素（结点）组成的有限序列。通常线性表的表示形式以及说明如图14.1所示。第2页/共92页线性表的基本概念第3页/共92页线性表的基本概念第4页/共92页线性表的基本操作线性表的基本操作通过以下函数可以实现，有关于这些函数的形式以及功能如表14-3。函数实现功能MakeEmpty(L)将线性表L变为空表Length(L)返回表L的长度，即表中元素个数Get(L,i)获得线性表L中位置i处的元素（1in）Prev(L,i)取i位置数据

2、元素的前趋元素Next(L,i)取i位置数据元素的后继元素Locate(L,x)函数的返回值为数据元素x在L中的位置Insert(L,I,x)在线性表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置Delete(L,p)从表L中删除位置p处的元素IsEmpty(L)如果表L为空表(长度为0)则返回true，否则返回falseClear(L)清除所有元素Init(L)同MakeEmpty(L)，初始化线性表为空Traverse(L)遍历输出所有元素Find(L,x)查找线性表L中元素x首次出现的位置，如果成功返回出现的位置，否则返回0Update(L,x)更新元素Sort

3、(L)对所有元素重新按给定的条件排序rstr(string1,string2)用于字符数组的求string1中出现string2的首地址第5页/共92页线性表的基本操作第6页/共92页线性表的顺序存储结构线性表的顺序存储结构的含义如图14.5所示。第7页/共92页线性表的顺序存储结构第8页/共92页线性表的顺序存储结构第9页/共92页顺序表的基本操作顺序表的基本操作包括初始化、求顺序表的长度、判断顺序表是否为空、清空顺序表、获取顺序表中第i个元素。下面详细讲解这些基本操作。第10页/共92页1.初始化顺序表L在对顺序表操作之前我们必须先对顺序表初始化。对顺序表的初始化的算法如图14.8所示。第

4、11页/共92页2.求顺序表的长度求顺序表长度所用到的函数为Length()，该算法的实现如图14.9所示。第12页/共92页3.判断顺序表是否为空如果顺序表的长度为0，则顺序表为空表。判断顺序表是否为空的算法具体实现如图14.10所示。第13页/共92页4.清空顺序表清空顺序表也就是删除顺序表中的所有数据元素，清空之后的顺序表的长度length为0。清空顺序表的算法如图14.11所示。第14页/共92页5.获取顺序表中第i个元素取顺序表数据元素运算是返回顺序表中第i个数据元素，注意i取值范围是1ilength。如果i的取值正确，运算的时间复杂度为O(1)。取顺序表数据元素的算法实现如图14.

5、12所示。第15页/共92页顺序表的插入对顺序表初始化后，我们需要向顺序表中插入我们所需的数据，然后才能对其进行其它的操作。对顺序表的插入前与插入后数据元素的位置改变如图14.13所示。第16页/共92页顺序表的查找第17页/共92页1.按位置查找元素顺序表是一种随机存取结构。所以，在顺序表中按位置查找元素非常容易，只有查找位置合法，可直接返回对应的数据元素。按位置查找元素算法实现如图14.16所示。第18页/共92页2.按值查找元素按值查找元素是在顺序表中进行的，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的存储位置；如果顺序表中没有与给定值匹配的数据元素，返

6、回一个特殊值表示查找失败。顺序表按值查找元素算法实现如图14.17所示。第19页/共92页3.顺序表的查找操作效率分析效率主要是从时间复杂度和空间复杂度来看的，由于现在计算机的内存足够用程序实现，所以我们这里只考虑时间复杂度。按位置查找数据元素的时间复杂度分析如图14.18所示。第20页/共92页3.顺序表的查找操作效率分析第21页/共92页顺序表的删除如果对顺序表的第i个元素删除操作，那么低i+1个元素以及其后面的元素都会向前移动一个位置，并且顺序表的长度减1，具体算法以及算法分析如图14.20所示。第22页/共92页顺序表的删除第23页/共92页顺序表操作的算法典型案例第24页/共92页线

7、性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。在链式存储中，结点不仅包含数据元素的基本信息内容，而且包含数据元素之间的逻辑关系，如图14.24所示。第25页/共92页线性表的链式存储结构第26页/共92页线性表的链式存储结构第27页/共92页单链表的基本操作第28页/共92页1初始化链表L初始化链表主要完成头结点空间的申请和赋值。在以后的算法中不加说明则默认为单链表是带头结点的。初始化链表实现算法如图14.27所示。第29页/共92页2清空链表L 清空操作是指清除单链表中的所有结点使单链表为空，并释放空间。此时，头指针变为空。清

8、空链表实现算法如图14.28所示。第30页/共92页3判链表L是否为空如果单链表的头指针所指的第一个结点为空，那么单链表就为空，返回1，否则返回0。判断单链表是否为空的算法实现如图14.29所示。第31页/共92页4带头结点的单链表求表长算法思路：设一个移动指针和计数器k。若所指结点后面还有结点，向后移动，计数器加1。直至循环结束返回k的值就是链表长度。带头结点的单链表求表长算法实现如图14.30。第32页/共92页5不带头结点的单链表不带头结点的单链表求表长与带头结点的算法思路基本一致。但控制流程的条件有所不同。不带头结点的单链表求表长算法实现如图14.31所示。第33页/共92页5不带头结

9、点的单链表第34页/共92页14.1.11 单链表的插入结点运算第35页/共92页1单链表 单链表的插入运算是将值为x的新结点插入到单链表的第i个结点的位置上。先在单链表中找到第i-1个结点，再在其后插入新结点。单链表插入结点的过程如图14.32所示。第36页/共92页1单链表第37页/共92页单链表的删除结点运算删除运算是将单链表的第i个结点删去。先在单链表中找到第i-1个结点,再删除其后的结点。删除单链表结点的过程如图14.35所示。第38页/共92页单链表的删除结点运算第39页/共92页单链表的查找结点运算单链表查找分为按序号查找和按值查找两种。按值查找是指在表中查找其值满足给定值的结点

10、。返回在单链表中首次出现与给定值相等的数据元素的序号；否则，返回一个特殊值表示查找失败。按序号查找比较简单，实际上就是与序号对应相同的元素的值。第40页/共92页1.按序号查找按序号查找是从链表的第一个元素结点起，判断当前结点序号是否是第i个。若是，则返回该结点的指针，否则继续向下移动，直到走完整个链表为止。没有第个结点时返回空。单链表按序号查找实现算法如图14.37所示。第41页/共92页1.按序号查找第42页/共92页2.按值查找从链表的第一个元素结点起，判断当前结点其值是否等于待定值，若是，返回该结点的指针，否则继续向下移动，直到走完整个链表为止。找不到时返回空。按值查找实现算法如图14

11、.39所示。第43页/共92页栈栈是一种线性表的特殊表现形式。日常生活中有很多栈的表现形式，例如：在仓库中储存货物时，先来的放在下面，后来的货物放在上面，而要取出货物时只能先取上面的后取出下面的货物。这里就利用到了本节要讲的栈结构。第44页/共92页栈的定义和基本运算栈是按照“后进先出”的原则处理数据的，在栈中只能在一端进行操作，该端称为栈顶，另一端称为栈底。如图所示。第45页/共92页栈的定义和基本运算第46页/共92页栈的定义和基本运算操作名称函数名称初始条件操作结果初始栈Init_Stack(&S)栈S不存在创建一个空栈判栈空Stack_Empty(S)栈S存在返回栈是否为空入栈Push

12、(&S,value)栈S存在栈S的top加1，在栈顶插入value判栈满Stack_Full(S)栈S存在返回栈是否为满出栈Pop(&S)栈S存在栈S的top减1，删除栈顶元素,返回出栈元素读栈顶元素Get_Top(S)栈不为空返回栈顶元素的值第47页/共92页栈的顺序存储栈和线性表类似，也有两种存储结构：顺序存储与链式存储。顺序存储结构的栈简称为顺序栈。第48页/共92页1.顺序栈结构类型定义顺序栈结构类型定义如图14.42所示。第49页/共92页2.初始化顺序栈创建一个空栈，只需要给指示当前栈顶元素位置的变量top赋值为0就可以了。初始顺序栈对应的实现代码如图14.43所示。第50页/共9

13、2页2.初始化顺序栈第51页/共92页3.判断栈的状态在对栈进行操作之前通常需要先判断栈的状态，再决定是否进行操作，例如，入栈钱应先判断栈是否已满，然后再决定是否进行入栈操作，而在出栈时应先判断栈是否已经为空。我们可以用2个函数去解决以上这些问题，如图14.44所示。第52页/共92页3.判断栈的状态第53页/共92页3.判断栈的状态第54页/共92页4.进栈操作进栈操作之前必须判断栈是否已满，如果未满则插入新元素，并且栈顶位置加1；否则不能进行进栈操作。进栈操作的算法如图14.46所示。第55页/共92页4.进栈操作第56页/共92页5.出栈操作出栈操作执行前，需要判断栈是否为空，不空时将栈

14、顶元素从栈中取出，栈发生变化。出栈对应的实现代码如图14.47所示。第57页/共92页6.获得栈顶元素当栈不为空时，根据top指针的位置可直接返回栈顶元素的值，栈不发生任何变化。获取栈顶元素对应的实现算法如图14.48所示。第58页/共92页栈的链式存储由于数组的局限性很多：容量很难扩充，当数组很大但存储的数据很少时就会造成空间的浪费。链式存储就会避免这种问题。栈的链式存储叫做链栈，是栈的另一种存储结构，所以在逻辑结构上与栈是一致的。链栈的形式如图14.49所示。第59页/共92页栈的链式存储第60页/共92页栈的链式存储第61页/共92页1.链栈的初始化链栈的初始化就是创建一个空栈，栈顶指针

15、的初值为空并且空栈中元素个数为0，具体算法如图14.51所示。第62页/共92页2.链栈的进栈因为是链式存储结构所以进栈时不需要判断栈是否为满，这就是优越于顺序栈的地方。直接开辟一个结点的空间，然后把数据元素存储到新开辟的结点的数据域中，再把指针域指向进栈前的栈顶元素。链栈的进栈操作算法如图14.52所示。第63页/共92页2.链栈的进栈第64页/共92页3.链栈的出栈链栈的出栈同顺序栈的一样，首先也要判断栈是否为空。在栈顶元素出栈后，需要修改栈顶指针top，具体实现如图14.53所示。第65页/共92页3.链栈的出栈第66页/共92页队列在程序设计中，队列是一种很常用的数据结构，本节介绍队列

16、的特点和操作队列的C语言代码。第67页/共92页队列的定义和基本运算队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作队列尾*（tail），允许删除的另一端称作队列头（front）。所以队列是依据“先进先出”的原则进行操作的，队列又称FIFO（First In First Out）表。如图14.54所示。第68页/共92页队列的定义和基本运算操作名称函数名称初始条件操作结果初始化队列Init_Queue(&Q)队列S不存在创建一个空的队列判队列空Queue_EmptyQ)队列Q存在返回队列是否为空入队In_Queue(&S,value)队列Q存在队

17、列的reart加1判队列满Queue_Full(S)队列Q存在返回队列是否为满出队Out_Queue(&S)队列Q存在队列Q的front减1，返回并删除队尾元素 读队头元素Get_Top(S)队列不为空返回队头元素的值第69页/共92页非循环队列的顺序存储对于非循环队列的顺序存储结构示意图如图14.55所示。第70页/共92页非循环队列的顺序存储第71页/共92页1.初始化队列队列的初始化主要是给指示队头和队尾位置的两变量赋值为0。初始化队列对应的实现代码如图14.57所示。第72页/共92页2.判断队列的状态我们可以通过对头队尾位置的变量的值，判断队列是否为空、已满。判断队列是否空以及已满的

18、算法如图14.58所示。第73页/共92页3.入队因为是顺序存储的非循环的队列，所以在入队操作执行前需判断队列是否为满，不满时将值为elem的新的数据元素添加到队尾，队列结构发生变化。入队对应的算法如图14.59所示。第74页/共92页4.出队与入队操作相反，出队操作就是将对头元素取出。出队操作从队列首部取出对头元素（其实是返回对头元素的指针），然后修改对头head的序号，是其指向后一个元素（这样，原来对头指针指向的元素就不能被访问到了，相当于被删除了）。具体算法如图14.60所示。第75页/共92页4.出队第76页/共92页循环队列的顺序存储第77页/共92页1.循环队列出现的原因顺序存储的

19、非循环队列，在进行操作时常常会出现“假溢出”情况。什么是“假溢出”呢？如图14.61所示。第78页/共92页1.循环队列出现的原因第79页/共92页2.初始化循环队列循环队列的初始化和非循环队列的初始化原理相同，都是把队头队尾位置两变量赋值为0，算法以及分析如图14.63所示。第80页/共92页3.判断队列的状态循环队列的是否是空队列的算法同非循环队列的算法一样这里就不再讲述，下面主要讲解如何判断循环队列已满的算法，如图14.64所示。第81页/共92页4.循环队列的入队操作入队操作执行前需判断队列是否为满，不满时将值为x的新的数据元素添加到队尾，队列结构发生变化。因为是头尾相接的循环结构，入

20、队时的队尾指针加1操作修改为：Q-rear=(Q-rear+1)%MAX，入队操作算法以及过程示意图如图14.65所示。第82页/共92页4.循环队列的入队操作第83页/共92页5.循环队列出队操作出队操作执行前，需要判断队列是否为空，不空时将队头元素从队列中取出，队列发生变化。出队时的队头指针加1操作修改为：Q-front=(Q-front+1)%MAX，出队算法以及操作过程示意图如图14.66所示。第84页/共92页5.循环队列出队操作第85页/共92页队列的链式存储队列链式存储结构示意图如图14.67所示。第86页/共92页1.队列的链式存储结构的定义队列链式存储的结构体定义的具体代码如

21、图14.68所示。第87页/共92页2.判断队列是否为空对于有头结点的队列，当头指针与尾指针同时指向头结点时队列为空；对于无头结点的队列，当头指针与尾指针的指针域为空时，此时队列为空，如图14.69所示。第88页/共92页3.入队操作链队列的入队操作在队尾添加一个新结点，尾指针rear指向新的结点，队列结构发生变化。入队对应的实现代码如图14.70所示。第89页/共92页4.出队操作出队操作执行前，需要判断队列是否为空，不空时将队头元素从队列中取出，并改变队头指针指向，队列发生变化。出队对应的实现代码如图14.71所示。第90页/共92页小结本章主要讲解基本概念以及对数据结构的基本操作，在这里重点是掌握线性表，栈，队列的基本操作。第91页/共92页感谢您的观看！第92页/共92页