线性表、栈和队列

《线性表、栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表、栈和队列线性表、栈和队列知识点2.1线性表2.1.1线性表的抽象数据类型2.1.2线性表运算分类2.1.3线性表的存储结构2.2顺序表－向量2.2.1STL中的向量2.2.2向量的抽象数据类型2.3链表2.3.1单链表2.3.2双链表2.3.3循环链表2.4栈2.4.1栈的引入2.4.2STL中的栈2.4.3顺序栈的实现2.4.4链式栈的实现2.4.5栈的应用－计算表达式的值2.4.6栈与递归2.5队列2.5.1队列的引入2.5.2STL中的队列2.5.3队列的应用－BFS的实现2.5.4顺序队列的实现2.5.5链式队列的实现2.5.6顺序队列与链式队列的

2、比较本章和下一章介绍线性逻辑结构。本章讨论几种常用的线性数据结构(统称为线性表)：顺序表（也称为向量，是用顺序结构实现的线性表），类似于C/C++语言中的数组，实现了封装、提供了丰富的功能。链表（用链式结构实现的线性表）：链式结构的线性表，在结点中附件指针域来表达结点之间的前驱/后继关系。单链表；双链表；循环链表：循环单链表，循环双链表。栈：访问受限的线性表，插入元素和弹出元素都限制在表的一端(栈顶)。队列：访问受限的线性表，只允许在表的一端(队列尾)进入结点，在表的另一端(队列头)移出结点。2.1线性表线性表是一类线性（区别于树型结构和图结构）数据结构，它有多种存储结

3、构和应用方法，从而可以细分为顺序表、链表、队列、栈等。“线性表”是从逻辑结构的角度来描述数据结构的，它主要有两种存储结构：顺序存储结构和链式存储结构。2.1.1线性表的抽象数据类型线性表：直观地讲，线性表的特点是它的所有结点可以排列成一个线性序列，n0→n1→n2→…→nk。在线性表中：有唯一的开始结点，它没有前驱；其他结点都有唯一的前驱结点。有唯一的末尾结点，它没有后继；其他结点都有唯一的后继结点。除开始结点和末尾结点外，其他结点称为中间结点，中间结点有唯一的前驱和后继。可以从离散数学的角度对线性表进行严格定义(略)。例2.1：线性表的抽象数据类型以下是线性表的抽象数

4、据类型，不同的线性表有不同的实现方式。#include#include//assert函数需要用到的头文件templateclassList{public:List();//构造函数~List();//析构函数voidappend(constELEM&item);//在表尾增加一个元素//插入一个元素，使之成为第index个元素voidinsert(constELEM&item,intindex);voidremove(intindex);//删除第index个元素intsearch(ELEMdata);

5、//查找数据data查找结点，返回其位置boolisempty();//判断线性表是否为空boolisfull();//判断线性表是否满voidoutput();//输出所有元素的值private:intSize;//线性表中当前结点个数intLength;//线性表的长度};2.1.2线性表运算分类典型的运算：增(加)、删(除)、查(找)、(修)改。2.1.3线性表的存储结构线性表的存储结构：如何开辟存储空间，各结点存储空间的联系，如何实现等。线性表的存储结构主要有两种：定长的顺序存储结构。特点是线性表结点可以按地址相邻的顺序存储在一片连续的存储空间中，线性表的固定长

6、度限制了线性表结点个数变化不能超过该固定长度。变长的线性存储结构。具体形式有链式存储结构，动态数组等。在链式存储结构中，各结点的存储空间动态申请和释放，通过指针域来表达结点的前驱/后继关系。动态数组：定长数组的变形，当结点个数超出最大限度时，重新申请更长的数组（new和delete运算符）。2.2顺序表－向量顺序表(sequentiallist)又称为向量(vector)，它采用定长的一维数组存储结构。向量的主要特性：元素的类型相同。元素顺序地存储在一块有连续地址的存储空间中，每一个元素按其顺序有唯一的索引值，又称下标值，用它可以方便地访问元素内容。顺序表类似于C/C+

7、+语言中的数组，将各种操作封装一个类。2.2.1STL中的向量标准模板库，StandardTemplateLibrary,STL。教材1.7节。STL提供了3种通用实体：容器、迭代器和算法。可以直接使用STL中的实体来求解问题。但掌握用程序实现各种数据结构也是应该具备的能力。STL中的容器容器是一种数据结构，用来存储结点。不同类型的容器在其内部以不同的方式组织结点。STL中常用的容器有：vector：向量。stack：栈。queue：队列。priority_queue：优先队列。STL中的容器是用类模板实现的。STL中的容器提供了丰富的成