首页  思维导图  详情

数据结构

2020-07-08 13:48:39   0  举报





仅支持查看

AI智能生成

数据结构描述

数据结构

作者其他创作

大纲/内容

基本概念

数据

数据：数据是信息的载体，是描述客观事物的属性的数，字符以及所有能够输入计算机的中并被 计算机程序识别和处理的符号的集合。

数据元素

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可若干个数据项组成。

数据项：是构成数据元素的不可分割的最小单位。

例如：学记录就是一个数据元素，它由学号，姓名，性别等数据构成

数据对象

定义

是性质相同的数据元素的集合，是数据的一个子集

例如

字符集合c={‘a’，‘v’，'c'}

数据类型

定义

数据类型是一个值的集合和定义此集合上一组操作的总称

数据类型包括

原子类型：其值不可再分的数据类型

结构类型：其值可以在分解为若干个成分的数据类型

抽象数据类型（ADT）

定义

抽象数据组织和与之相关的操作

详细解释

指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 因此，不论ADT的内部结构如何变化，只要其数学特性不变都不影响其外部使用。

ADT=（D,S,P） 其中（D数据对象，S数据关系，P是D的基本操作集）这样的三元组来表示抽象数据类型。

定义形式

ADT<抽象数据类型名>{        数据对象：<数据对象的定义>        数据关系：<数据关系的定义>        基本操作：<基本操作的定义> }ADT<抽象数据类型名>

其中的数据对象和数据关系的定义用伪码描述

基本操作的定义是： <基本操作名>（<参数表>） 初始条件：<初始条件描述> 操作结果：<操作结果描述>

初始条件：描述操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息

操作结果：描述操作正常完成之后，数据结构的变化状态和应返回的结果

数据结构和数据类型，对象的差别

数据结构不仅要描述数据类型的数据对象，还要描述数据对象各元素之间的互相关系

数据结构

定义

是相互之间存在一种或多种特定关系的数据元素的集合

注意

在任何问题中，数据元素都不是孤独存在的，而是在它们之间存在着某种关系 。这种数据元素互相之间的关系称为结构（Structure）

特点

<ul><li>数据结构包括三方面的内容（存储结构，逻辑结构，数据的运算） </li><li>其中数据的逻辑结构和存储结构是密不可分的两个方面 </li><li>算法的设计取决于选定的逻辑结构，算法的实现依赖于所采用的存储结构 </li></ul>

数据结构的三方面

逻辑结构

定义

为处理问题方便而认为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构 别的知识点：数据元素之间的关系可以是代表某种含义的自然关系

集合：结构中的数元素之间除了“通属于一个集合”的关系外，无其他关系，类似数学上的集合

线性结构：结构中的数据元素之间只存在一对一的关系。比如排队

图片

树形结构：结构中的数据元素之间存在一对多的关系。比如家族族谱

图片

图状结构或网状结构：结构中的数据元素之间存在多对多的关系，比如地图

图片

子主题

存储结构（物理结构，映像）

说明：存储结构是指数据结构在计算机中的表示（又称位映像），也称为物理结构。它包括        数据元素的表示和关系的表示，数据的存储结构是逻辑结构用计算机语言的实现，它依        赖于计算机语言。        数据的存储结构。主要有：顺序存储，链式存储，索引存储和散列存储

解释

物理结构应该正确反映逻辑关系 肉体---灵魂

存储关系

顺序存储结构

定义

存储的物理位置相邻（物理位置即信息在计算机中的位置。）

用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系）

图片

链式存储结构

定义

存储的物理位置未必相邻，通过计入相邻元素的物理位置来找到相邻元

在每个数据元素中增加一个存放另一个元素地址的指针（pointer），用该指针来表示数据元素之间的逻辑关系

图片

索引存储：类似于目录，以及可以联系操作系统的文件和系统章节来理解

散列存储：通过关键字直接计算出元素的物理地址

数据的运算

数据的常见运算包括

建立（create）一个数据结构

消除（Destroy）一个数据结构

从一个数据结构中删除（Delete）一个数据元素

把一个数据元素插入（insert）到一个数据结构中

对一个数据结构进行访问（Access）

对一个数据结构（中的数据元素）进行修改（Modify）

对一个数据结构进行排序（Sort）

对一个数据结构进行查找（Search）

算法和算法的复杂度

算法

说明：算法是对问题求解步骤的描述，通过有限序列的指令来实现，其中的每个指令表示一个或多个操作

算法的描述

算法可以使用自然语言描述；使用形式语言描述；使用计算机语言描述

算法和程序不同的概念

一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止，意味着不是所有的计算机程序都是算法

算法的五大特性

有穷性

有限步之后结束，不会出现无限循环

确定性

不存在二义性，算法的每个步骤被精确定义，且一个算法只有一个入口和一个出口

可行性

一个算法是能行的，即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现

输入

能被计算机处理的各类型数据，如数字，音频，图像等等

输出

一至多个程序输出结果

图片

好的算法的标准

正确性（Correctness）

算法应满足具体问题的需求

可读性（Readability）

算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改

健壮性（Robustness）

算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果

通用性（Generality）

算法应具有一般性，即算法的处理结果对于一般的数据集合都成立

效率与存储需求

效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题规模有关

算法的复杂度

时间复杂度

定义

它用来衡量算法随着问题规模增大，算法执行时间增长的快慢

计算方法

T(n)=o(f(n)),大O记法，f(n)是算法中基本运算的频度，一般考虑最坏情况下的时间复杂度

时间复杂度是问题规模的函数：记作T(n)，时间复杂度主要分析T(n)的数量 

取算法时间增长最快的那个函数项，把它的系数改为1.

时间复杂度快慢的分析

从图中，可以看出：随着问题规 模的增大（横坐标），所需时间 的增长率（斜率）差别很大。 ----- 而且，这种差距随着问题规模的 增大而显著的增大 --- 我们关心的就是算法的增长规模 的速度。

常用的时间复杂度大小关系

案例

单个循环

例题1：求出程序的时间复杂度？

时间分析

该函数执行了3n+6个语句

假设每个语句执行时间一致，均为常数t。则总时间T=（3n+6）*t

随着问题规模n的增大，总时间的增长率与n的增长率一致，所以复杂度为O(n).

结论

复杂度是关于增长率的，所以可以直接忽视常函数

一般可以直接关注循环段基本操作语句（示例中的sum=sum+i）的执行次数。

答案解析

例题2：求出程序的时间复杂度？

答案解析

多个循环

例题1，求出程序的时间复杂度？

分析

两个循环体是独立的采用加法规则。

答案

例题2.求出程序的时间复杂度？

分析

两个循环体是嵌套的，采用乘法规则

答案 

子主题

空间复杂度

定义

它用来衡量算法随着问题规模增大，算法辅助空间的增长的快慢

辅助空间：除了存储算法本身的指令，常数，变量和输入数据外，                  还需要存储对数据操作的存储单元。

公式

空间复杂度S(n)指算法运行过程中所使用的辅助空间的大小

S(n)=O(g(n))或S(n)=O(f(n))

考试中以，O(1),O(n)较多

算法的原地工作

值算法所需的辅助空间是常量，即O（1）

线性表（顺序存储）

图片解释

食堂同学排队

、

线性表的定义

图片

线性表是具有相同数据类型的n(n>=0)个数据元素的有序有限序列

当n=0时，称为空表

当n>0时，将非空的线性表记作：a1称为线性表的第一（首）结点，an称为线性表的最后一个（尾）结点

线性表中第一个元素称为表头元素，最后一个称为表尾元素

除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继

线性表的逻辑结构

线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表达符号

线性表的中结点可以是单值元素（每个元素只有一个数据项）

例如：26个英文字母组成的字母表（A,B,C,....,Z）            一副扑克牌（1,2,3，......,k）

线性表中的结点可以使记录型元素，每个元素函有多个数据项 每个项为结点的一个域。每个元素有一个可以唯一标识每个结点的 数据项组，称为关键字

若线性表中的结点是按值（或按关键字值）由小或大（或由大到小）排列的，称线性表是有序的

线性表是一种相关灵活的数据结构，其长度可根据需要增长或缩短

线性表的数据元素可以访问，插入和删除

线性表的抽象数据类型定义

例题

假设：有两个集合A和B分别用两个线性表LA和LB表示，即线性表中的数据元素即为集合中的           成员。现要求一个新的集合A=AUB。

操作分析：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去

操作步骤： 1.从线性表LB中依次察看每个数据元素 2.依值在线性表LA中进行查访 3.若不存在，则插入

答案

顺序表的图片总结

线性表的顺序存储结构

图片

依次输入

定义

是一组地址连续的存储单元（比如c语言中的数组），依次存储线性表中 的数据元素。顺序存储的线性表也叫顺序表 -- 地址连续：存储器每个存储单元都有编号，这个编号就是地址

存储位置

通过这个公式，可以计算出顺序表中任一个元素的位置，而且所需的时间都 是相同的，即时间复杂度O(1),即随机存取

顺序存储操作

静态建表

首先要在存储器中划分出“一个区域”，而且是连续的，那么这块存储空间必须 有首地址和大小；最后我们要将表中各个元素对号入座，那就要知道有多少元素 ，也就是表的长度。

顺序建表的三个部分

存储空间的起始位置

顺序表最大存储容器

顺序表当前的长度

建表方法

typedef 代表着给后面的变量类型起别名

ElemType是数据结构的书上为了说明问题而用的一个词。它是element type（“元素的类型”）的简化体。　因为数据结构是讨论抽象的数据结构和算法的，一种结构中元素的类型不一定是整型、字符型、浮点型或者用户自定义类型，为了不重复说明，使用过程中用“elemtype”代表所有可能的数据类型，简单明了的概括了整体。在算法中，除特别说明外，规定ElemType的默认是int型

SqList定义顺序表

struct表示创建结构体

动态建表

其实存储空间（数组）还可以动态分配，也就是存储数组的空间是在程序执行过程中通过动态 分配语句来分配。

建表方法

第一步           这里不在开数组

第二步

注意：动态分配并不是链式存储，同样还是属于           顺序存储结构，只是分配的空间大小可以          运行时决定。

插入

插入流程

在顺序表L的第i(1<i<L.lengh+1)个位置插入新元素e。如果i的输入不合法， 则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的所有 元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入 成功返回true

算法思路

算法思路： <ol><li>判断i的值是否正确 </li><li>判断表长是否超过数组长度 </li><li>从后向前到第i个位置，分别将这些元素都向后移动一位 </li><li>将该元素插入位置i并修改表长 </li></ol>

bool是布尔类型它只是true和false两种值，分别表示真和假

插入操作的性能

最好情况：在表尾插入（即i=n+1），元素后移语句将不执行                 ，时间复杂度为O(1).

最坏情况：在表头插入（即i=1），元素后移语句将执行n次，                  时间复杂度为O(n).

平均情况：假设pi（pi=1/（n+1））是在第i个位置上插入一个                  结点的概率，则在长度为n的线性表中插入一个结点                   是所需移动结点的平均次数为2/n

删除

删除流程

删除顺序表L中第i（1<i<L.length）个位置的元素，成功则返回true， 并将删除的元素用引用变量e返回，否则返回false。

算法思路

算法思路： 1.判断i的值是否正确 2.取删除的元素 3.将被删除元素后面的所有元素都依次向前移动一位 4.修改表长

删除操作的性能

最好情况：删除表尾巴元素（即i = n），无需移动元素，时间复杂度为O（1）.

最坏情况：删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O（n）。

平均情况：假设pi(i = 1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点                 时所需移动结点的平均次数为(n-1)/2.                 平均时间复杂度为O（n）

顺序存储优缺点

优点

存储密度大：不需要为表中元素之间的逻辑关系增加额外存储空间

随机存取：可以快速存取表中任意位置的元素

缺点

插入和删除操作需要移动大量元素

对存储空间要求高，会产生存储空间“碎片”进而浪费空间

插入元素可能发生”溢出“

需要连续的存储空间

线性表的链式存储结构

链式存储定义

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立 起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要 存放一个指向其后继的指针。

图片解释

头指针

通常用“头指针”来标识一个单链表，例如Linllist L那么头指针L就代指一个单链表

头结点

单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以 记录表长等数据信息。头结点的指针域指向线性表的第一个元素结点。

为什么设置头结点

1.处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点操作与其它结点的操作就统一了

2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了

头结点和头指针的区别

不管带不带头结点，头指针始终指向链表的第一个结点。

头结点是带头直接点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理

单链表

图片解释

单链表的存储方式

单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素，数据可以在内存中任何允许的空间 和角落进行存储，这样就可以将碎片空间利用起来

单链表的操作

单链表的建立

头插法建立单链表

图片解释

建立新的结点分配内存空间，将新结点插入到当前链表的表头

公式

特点

头插法建立单链表，读入数据的顺序与生成的链表中结点的顺序是相反的

尾插法建立单链表

图片解释

建立新的结点分配内存空间，将新结点插入到当前链表的表尾

建表公式

特点

尾插法建立单链表，读入数据的顺序与生成的链表中结点的顺序是相同的

查找结点

按序号查找结点

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到 找到第i个结点为止，否则返回最后一个结点指针域NULL

按值查找结点

从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若 某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没 有这样的结点，则返回NULL。

链表的结点插入

插入方法

插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的是否合理，然后 找到待插入位置的前驱结点，即第i-1结点，再在其后插入新结点。

算法思路

取指向插入位置的前驱结点的指针    公式：p=GetElem(L,i-1);

令新结点*s的指针域指向*p的后继结点      公式：s->next = p->next;

令结点*p的指针域指向新插入的结点*s     公式：p->next=s;

删除结点

删除方法

删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后 检查表中第i-1个结点，即被删结点的前驱结点，再将其删除

算法思路

第一步：P=GetElem(L,i-1);                        取指向删除位置的前驱结点的指针

第二步：q=p->next;                              取指向删除位置的指针

第三步：p->next = q->next;                    p指向结点的后继指向被删除结点的后继

第四步：free(q);                                           释放删除结点

双链表

单链表和双链表的区别和相同

单链表是单向指针，而双链表是双向指针

双链表在建表上是两个指针（单链表是一个）分别是前驱指针，和后驱指针。

在其他方面是相同的

图片解释

双链表的操作

插入

第一步 s->next = p->next;

第二步： p ->next ->prior = s;

第三步：s->prior = p;

第四步：p->next = s;

删除

第一步：p ->next = q - >next;

第二步：q ->next ->prior = p;

第三步：free(q);

静态链表

定义

静态链表是借组数组来描述线性表的链式存储结构，结点 也有数据域data和指针域next，与前面所讲的链表中的指 针链表不同的是，这里的指针是结点的相对地址（数组下 标），又称游标。

建表方法

静态链表仍然包含数据和“指针域”（数组下标），又称游标。

特点

数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。链表最后一个元素的指针域值为-1

优点

静态链表虽然是数组存储的，但对静态链表的插入，删除操作与 动态链表（动态分配内存的方式）相同，只需要修改指针，而不 需要移动元素。

循环链表

循环单链表

定义

从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

循环链表和循环单链表的区别

循环链表中的最后一个指针不是NULL，而改为指向头节点，从而整个链表形成一个环

单链表

循环单链表

特点

从任何一个结点出发都能访问到链表的每一个元素

有时对单链表的操作是在表头和表尾进行的，此时可以对循环单链表不设头指针而仅设尾指针，从而提高效率 -- 原因：循环链表如果设置头指针那么访问表尾要一个一个移过去，如果设置尾指针访问就可以直接访问表头

判断循环单链表是否为空？

判断表是否为空条件不是头结点的后继指针是否为空，而是它是否等于头指针

循环双链表

定义

从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

循环双链表和双链表的区别

循环双链表区别于双链表就是首尾结点构成环

双链表

循环双链表

特点

在循环链表L中，尾结点的后继指针指向表头结点，头节点的前驱指针指向表尾结点

当循环双链表为空表时，其头结点的prior域和next域都等于L

一元多项式

栈和队列

栈

栈（Stack）的定义

只允许在一端进行插入或删除操作的线性表

栈的图片

栈包含

栈顶

栈中允许进行插入和删除的那一端

栈底

固定的，不允许进行插入和删除的另一端

空栈

当表中没有元素时称为空栈

栈的特点

栈是受限的线性表，所以自然具有线性关系。通过一维数组来存储栈

栈中元素后进行的必须先出去，即后进先出或先进后出（Last In First Out）

栈的抽象数据类型定义

ADT Stack{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n } 约定an端为栈顶，a1端为栈底。

栈的基本操作

InitStack( &S ) 操作结果：构造一个空栈S。 DestroyStack ( &S ) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack( &S ) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty( S ) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 StackLength( S ) 初始条件：栈S已存在。 操作结果：返回S的数据元素个数，即栈的长度。 GetTop( S, &e ) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push( &S, e ) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop( &S, &e ) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse( S, visit() ) 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

顺序栈

为什么叫顺序栈

栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫顺序栈。

建立顺序栈公式

1.Top值不能超过MaxSize 2.空栈的判定条件通常定位top == -1，满栈的判定条件通常为top == MaxSize-1，    栈中数据元素个数为top+1

建立栈的两种方式

通过根据数组是否可以根据需要增大，可以分为静态顺序栈和动态顺序栈

静态顺序栈

特点

实现简单，但不能根据需求扩大栈的存储空间

操作特点

使用一个静态的一位数组

栈底固定不变的，栈顶则随着进栈和退栈操作而变化，用一个整形变量top (称为栈顶指针)来指示当前栈顶位置。

用top = 0表示栈空的初始状态，每次top指向栈顶的数组中的存储位置。

结点进栈

首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到 栈顶（top所指的当前位置)

结点出栈

首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。 若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。

栈的类型定义

#define MAX_STACK_SIZE 100 //栈初始向量大小 #typedef int ElemType; typedef struct sqstack {     ElemType satack_array[MAX_STACK_SIZE]； //栈不存在时栈底为空     int top;            int bottom； }Sqstack; ---------------------------------------------------------------------------------

栈的初始化

SqStack Init_Stack(void) {      SqStack S;      S.bottom = S.top = 0;      return(s); }  ------------------------------------------------------------------------------------

元素进栈

Status Push(SqStack S,ElemType e)//使数据元素e进栈成为新的栈顶 {     if (S.top == MAX_STACk_SIZE-1)     return ERROR; //栈满，返回错误标识符     S.top++; //栈顶指针加1     S.stack_array[S.top]=e; //e称为新的栈顶     return OK; //进栈成功 }  ----------------------------------------------------------------------------------

元素出栈

Status Pop(SqStack S,ElemType *e)//弹出栈顶元素 {       if(S.top == 0) //判断栈是否为空            return ERROR; //栈空返回错误       *e = S.stack_array[S.top];       S.top --;       return OK; }

动态顺序栈

特点

可以根据需要增大栈的存储空间，但实现稍微复杂

操作步骤

采用动态的一维数组来存储栈

用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。 用top（称为栈顶指针）指示当前栈顶位置

用top = bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置

结点进栈

首先将数据元素保存到栈顶（top所指向的当前位置），  然后执行top加1，使top指向栈顶的下个存储位置

结点出栈

首先执行top减1，top指向栈顶元素的存储位置，然后将栈顶元素取出

动态栈的变化图

栈的实现

#define STACK_SIZE 100      //栈初始向量大小 #define STACK INCREMENT 10 //存储空间分配增量 #typedef int ElemType; typedef struct sqstack {     ElemType *bottom;              //栈不存在时栈底为空     ElemType *top;                    //栈顶指针     int stacksize;                        //当前已分配空间，以元素为单位 }Sqstack; ------------------------------------------------------------------------------

栈的初始化

Status Init_Stack(void) {      SqStack S;      S.bottom = (ElemType*)malloc(STACK_SIZE)*sizeof(ElemType);      if (! s.bottom) return ERROR;      S.top = S.bottom;      /*栈空时栈顶和栈底指针相同*/      S.stacksize = STACK_SIZE;      return OK; }  -----------------------------------------------------------------------------

元素进栈

Status Push(SqStack S,ElemType e) {     if (S.top-S.bottom>=S.stacksize-1)//判断栈是否满了     { //栈满的话就添加新的空间            S.bottom=(ElemType *)realloc((S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType));//栈满，追加存储空间            if(!S.bottom)                  return ERROR;            S.top = S.bottom + S.stacksize;            S.stacksize+=STACKINCREMENT;     }    *S.top = e;    S.top++;//栈顶指针加1，e成为新的栈顶    return OK; } --------------------------------------------------------------------------------

元素出栈

Status Pop(SqStack S,ElemType *e) {//弹出栈顶元素           if (S.top == S.bottom) //判断栈是否为空           return Error;//栈空返回失败标记           S.top--;           e = *S.top;           return ok; //操作成功就返回ok }

链式栈

定义

栈的链式存储的结构称为链栈

特点

插入删除的操作只能在表头位置进行

链栈的基本操作

栈的结点类型

typedef stuct Stack_Node {     ElemType data;     struct Stack_Node *next; }Stack_Node; ----------------------------------------------------------------------

栈的初始化

#Stack_Node *Init_Link_Stack(void) {      Stack_Node *top;      top = (Stack_Node*)malloc(Sizeof(Stack_Node)); //动态分配空间      top ->next =NULL;      return(top); }

元素进栈

------------------------------------------------------------------------------------------ Status push(Stack_Node *top,ElemType e) {      Stack_Node *p;      p=(Stack_Node*)malloc(sizeof(Stack_Node));      if(!p)           return ERROR; //申请新结点失败，返回错误标志     p->data = e;     p->next = top -> next;     top ->next = p;     return OK; }  ----------------------------------------------------------------------------------------

元素出栈

Stauts Pop(Stack_Node *top,ElemType *e) //将栈顶元素出栈 {       Stack_Node *p;       ElemType e;       if (top ->next ==NUll)           return ERROR; //栈空返回错误标志      p = top->next;      e = p->data; //取栈顶元素      top ->next = p ->next; //修改栈顶指针      free(p);     return OK; }

共享栈

为什么要使用共享栈

顺序栈的存储空间的大小需要事先开辟好，很多时候对每个栈各自单独 开辟存储空间的利用率不如将各个栈的存储空间共享

队列

定义

是一种先进先出（first in first out）简称（FIFO) 的线性表。只允许在表的一端进行插入而另一端删除

队首

允许进行删除的一端称为队首

队尾

允许进行插入的一端称为队尾

队列的抽象数据类型

ADT Queue{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n } 约定a1为队列头，an为队列尾。

队列的基本操作

InitQueue( &Q ) 操作结果：构造一个空队列Q。 ---------------------------------- DestroyQueue ( &Q ) 初始条件：队列Q已存在。 操作结果：销毁队列Q。 ---------------------------------- ClearQueue ( &Q ) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 ---------------------------------- QueueEmpty( Q ) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 ----------------------------------  QueueLength( Q ) 初始条件：队列Q已存在。 操作结果：返回Q的数据元素个数，即队列的长度。 -------------------------------------- GetHead( Q, &e ) 初始条件：队列Q已存在且非空。 操作结果：用e返回Q的队头元素。 ----------------------------------------- EnQueue( &Q, e ) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 --------------------------------------------------- DeQueue( &Q, &e ) 初始条件：队列Q已存在且非空。 操作结果：删除Q的队头元素，并用e返回其值。

注意点

顺序队列会出现“假溢出”现象

顺序队列

图片

操作步骤

设立一个队首指针front。一个队尾指针rear，分别指向队首和队尾元素

初始化

front = rear =0

入队

将新元素插入rear所指的位置，然后rear加1

出队

删去front所指的元素，然后加1并返回被删元素

队列为空

front =rear

对满

rear = MAX_QUEUE_SIZE

静态队列

类型定义

define MAX_QUEUE_SIZE 100 typedef struct queue { ElemType Queue_array[MAX_QUEUE_SIZE] int front;                     //定义的队首指针 int rear;                      //定义的队尾指针 }SqQueue;

动态队列

循环队列

特点

循环队列可以充分的分配空间，除非向量真的被队列元素全部占用否则不会上溢

图片

注意点

rear所指的单位始终为空

循环队列为空

front =rear

循环队列满 

(rear +1)%MAX_QUEUE_SIZE ==front

基本操作