简单数据结构.pptx

简单数据结构,数据结构是程序储存，组织数据的一种方式，是程序中处理数据的基本单位。主要讲解简单的数据结构的基本操作。,线性表,线性表是最简单也是最常用的一种数据结构。例如，C语言中的数组就是线性表应用的一个典型代表。,线性表的基本概念,线性表是由n（n0）个类型相同的数据元素（结点）组成的有限序列。通常线性表的表示形式以及说明如图14.1所示。,线性表的基本概念,线性表的基本概念,线性表的基本操作,线性表的基本操作通过以下函数可以实现，有关于这些函数的形式以及功能如表14-3。,线性表的基本操作,线性表的顺序存储结构,线性表的顺序存储结构的含义如图14.5所示。,线性表的顺序存储结构,线性表的顺序存储结构,顺序表的基本操作,顺序表的基本操作包括初始化、求顺序表的长度、判断顺序表是否为空、清空顺序表、获取顺序表中第i个元素。下面详细讲解这些基本操作。,1.初始化顺序表L,在对顺序表操作之前我们必须先对顺序表初始化。对顺序表的初始化的算法如图14.8所示。,2.求顺序表的长度,求顺序表长度所用到的函数为Length()，该算法的实现如图14.9所示。,3.判断顺序表是否为空,如果顺序表的长度为0，则顺序表为空表。判断顺序表是否为空的算法具体实现如图14.10所示。,4.清空顺序表,清空顺序表也就是删除顺序表中的所有数据元素，清空之后的顺序表的长度length为0。清空顺序表的算法如图14.11所示。,5.获取顺序表中第i个元素,取顺序表数据元素运算是返回顺序表中第i个数据元素，注意i取值范围是1ilength。如果i的取值正确，运算的时间复杂度为O(1)。取顺序表数据元素的算法实现如图14.12所示。,顺序表的插入,对顺序表初始化后，我们需要向顺序表中插入我们所需的数据，然后才能对其进行其它的操作。对顺序表的插入前与插入后数据元素的位置改变如图14.13所示。,顺序表的查找,1.按位置查找元素,顺序表是一种随机存取结构。所以，在顺序表中按位置查找元素非常容易，只有查找位置合法，可直接返回对应的数据元素。 按位置查找元素算法实现如图14.16所示。,2.按值查找元素,按值查找元素是在顺序表中进行的，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的存储位置；如果顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。顺序表按值查找元素算法实现如图14.17所示。,3.顺序表的查找操作效率分析,效率主要是从时间复杂度和空间复杂度来看的，由于现在计算机的内存足够用程序实现，所以我们这里只考虑时间复杂度。按位置查找数据元素的时间复杂度分析如图14.18所示。,3.顺序表的查找操作效率分析,顺序表的删除,如果对顺序表的第i个元素删除操作，那么低i+1个元素以及其后面的元素都会向前移动一个位置，并且顺序表的长度减1，具体算法以及算法分析如图14.20所示。,顺序表的删除,顺序表操作的算法典型案例,线性表的链式存储结构,线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。在链式存储中，结点不仅包含数据元素的基本信息内容，而且包含数据元素之间的逻辑关系，如图14.24所示。,线性表的链式存储结构,线性表的链式存储结构,单链表的基本操作,1初始化链表L,初始化链表主要完成头结点空间的申请和赋值。在以后的算法中不加说明则默认为单链表是带头结点的。初始化链表实现算法如图14.27所示。,2清空链表L,清空操作是指清除单链表中的所有结点使单链表为空，并释放空间。此时，头指针变为空。清空链表实现算法如图14.28所示。,3判链表L是否为空,如果单链表的头指针所指的第一个结点为空，那么单链表就为空，返回1，否则返回0。判断单链表是否为空的算法实现如图14.29所示。,4带头结点的单链表求表长,算法思路：设一个移动指针和计数器k。若所指结点后面还有结点，向后移动，计数器加1。直至循环结束返回k的值就是链表长度。带头结点的单链表求表长算法实现如图14.30。,5不带头结点的单链表,不带头结点的单链表求表长与带头结点的算法思路基本一致。但控制流程的条件有所不同。不带头结点的单链表求表长算法实现如图14.31所示。,5不带头结点的单链表,14.1.11 单链表的插入结点运算,1单链表,单链表的插入运算是将值为x的新结点插入到单链表的第i个结点的位置上。先在单链表中找到第i-1个结点，再在其后插入新结点。单链表插入结点的过程如图14.32所示。,1单链表,单链表的删除结点运算,删除运算是将单链表的第i个结点删去。先在单链表中找到第i-1个结点,再删除其后的结点。删除单链表结点的过程如图14.35所示。,单链表的删除结点运算,单链表的查找结点运算,单链表查找分为按序号查找和按值查找两种。按值查找是指在表中查找其值满足给定值的结点。返回在单链表中首次出现与给定值相等的数据元素的序号；否则，返回一个特殊值表示查找失败。按序号查找比较简单，实际上就是与序号对应相同的元素的值。,1.按序号查找,按序号查找是从链表的第一个元素结点起，判断当前结点序号是否是第i个。若是，则返回该结点的指针，否则继续向下移动，直到走完整个链表为止。没有第个结点时返回空。单链表按序号查找实现算法如图14.37所示。,1.按序号查找,2.按值查找,从链表的第一个元素结点起，判断当前结点其值是否等于待定值，若是，返回该结点的指针，否则继续向下移动，直到走完整个链表为止。找不到时返回空。按值查找实现算法如图14.39所示。,栈,栈是一种线性表的特殊表现形式。日常生活中有很多栈的表现形式，例如：在仓库中储存货物时，先来的放在下面，后来的货物放在上面，而要取出货物时只能先取上面的后取出下面的货物。这里就利用到了本节要讲的栈结构。,栈的定义和基本运算,栈是按照“后进先出”的原则处理数据的，在栈中只能在一端进行操作，该端称为栈顶，另一端称为栈底。如图所示。,栈的定义和基本运算,栈的定义和基本运算,栈的顺序存储,栈和线性表类似，也有两种存储结构：顺序存储与链式存储。顺序存储结构的栈简称为顺序栈。,1.顺序栈结构类型定义,顺序栈结构类型定义如图14.42所示。,2.初始化顺序栈,创建一个空栈，只需要给指示当前栈顶元素位置的变量top赋值为0就可以了。初始顺序栈对应的实现代码如图14.43所示。,2.初始化顺序栈,3.判断栈的状态,在对栈进行操作之前通常需要先判断栈的状态，再决定是否进行操作，例如，入栈钱应先判断栈是否已满，然后再决定是否进行入栈操作，而在出栈时应先判断栈是否已经为空。我们可以用2个函数去解决以上这些问题，如图14.44所示。,3.判断栈的状态,3.判断栈的状态,4.进栈操作,进栈操作之前必须判断栈是否已满，如果未满则插入新元素，并且栈顶位置加1；否则不能进行进栈操作。进栈操作的算法如图14.46所示。,4.进栈操作,5.出栈操作,出栈操作执行前，需要判断栈是否为空，不空时将栈顶元素从栈中取出，栈发生变化。出栈对应的实现代码如图14.47所示。,6.获得栈顶元素,当栈不为空时，根据top指针的位置可直接返回栈顶元素的值，栈不发生任何变化。获取栈顶元素对应的实现算法如图14.48所示。,栈的链式存储,由于数组的局限性很多：容量很难扩充，当数组很大但存储的数据很少时就会造成空间的浪费。链式存储就会避免这种问题。栈的链式存储叫做链栈，是栈的另一种存储结构，所以在逻辑结构上与栈是一致的。链栈的形式如图14.49所示。,栈的链式存储,栈的链式存储,1.链栈的初始化,链栈的初始化就是创建一个空栈，栈顶指针的初值为空并且空栈中元素个数为0，具体算法如图14.51所示。,2.链栈的进栈,因为是链式存储结构所以进栈时不需要判断栈是否为满，这就是优越于顺序栈的地方。直接开辟一个结点的空间，然后把数据元素存储到新开辟的结点的数据域中，再把指针域指向进栈前的栈顶元素。链栈的进栈操作算法如图14.52所示。,2.链栈的进栈,3.链栈的出栈,链栈的出栈同顺序栈的一样，首先也要判断栈是否为空。在栈顶元素出栈后，需要修改栈顶指针top，具体实现如图14.53所示。,3.链栈的出栈,队列,在程序设计中，队列是一种很常用的数据结构，本节介绍队列的特点和操作队列的C语言代码。,队列的定义和基本运算,队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作队列尾*（tail），允许删除的另一端称作队列头（front）。所以队列是依据“先进先出”的原则进行操作的，队列又称FIFO（First In First Out）表。如图14.54所示。,队列的定义和基本运算,非循环队列的顺序存储,对于非循环队列的顺序存储结构示意图如图14.55所示。,非循环队列的顺序存储,1.初始化队列,队列的初始化主要是给指示队头和队尾位置的两变量赋值为0。初始化队列对应的实现代码如图14.57所示。,2.判断队列的状态,我们可以通过对头队尾位置的变量的值，判断队列是否为空、已满。判断队列是否空以及已满的算法如图14.58所示。,3.入队,因为是顺序存储的非循环的队列，所以在入队操作执行前需判断队列是否为满，不满时将值为elem的新的数据元素添加到队尾，队列结构发生变化。入队对应的算法如图14.59所示。,4.出队,与入队操作相反，出队操作就是将对头元素取出。出队操作从队列首部取出对头元素（其实是返回对头元素的指针），然后修改对头head的序号，是其指向后一个元素（这样，原来对头指针指向的元素就不能被访问到了，相当于被删除了）。具体算法如图14.60所示。,4.出队,循环队列的顺序存储,1.循环队列出现的原因,顺序存储的非循环队列，在进行操作时常常会出现“假溢出”情况。什么是“假溢出”呢？如图14.61所示。,1.循环队列出现的原因,2.初始化循环队列,循环队列的初始化和非循环队列的初始化原理相同，都是把队头队尾位置两变量赋值为0，算法以及分析如图14.63所示。,3.判断队列的状态,循环队列的是否是空队列的算法同非循环队列的算法一样这里就不再讲述，下面主要讲解如何判断循环队列已满的算法，如图14.64所示。,4. 循环队列的入队操作,入队操作执行前需判断队列是否为满，不满时将值为x的新的数据元素添加到队尾，队列结构发生变化。因为是头尾相接的循环结构，入队时的队尾指针加1操作修改为：Q-rear=(Q-rear+1)%MAX，入队操作算法以及过程示意图如图14.65所示。,4. 循环队列的入队操作,5.循环队列出队操作,出队操作执行前，需要判断队列是否为空，不空时将队头元素从队列中取出，队列发生变化。出队时的队头指针加1操作修改为：Q-front=(Q-front+1)%MAX，出队算法以及操作过程示意图如图14.66所示。,5.循环队列出队操作,队列的链式存储,队列链式存储结构示意图如图14.67所示。,1.队列的链式存储结构的定义,队列链式存储的结构体定义的具体代码如图14.68所示。,2.判断队列是否为空,对于有头结点的队列，当头指针与尾指针同时指向头结点时队列为