《《数据结构、算法与应用(C++语言描述)》教学课件02线性表》由会员分享，可在线阅读，更多相关《《数据结构、算法与应用(C++语言描述)》教学课件02线性表（57页珍藏版）》请在金锄头文库上搜索。
1、2.1 线性表及其抽象数据类型线性表及其抽象数据类型2.1.1 线性表的基本概念线性表的基本概念2.1.2线性表的抽象数据类型线性表的抽象数据类型n对于一种数据结构，首先要抽象出该数据结构的基本特点和基本操作，然后以抽象数据类型的形式描述出来。本节首先介绍线性表的基本概念和一般需要进行的基本操作，然后根据对线性表的特点及其基本操作的抽象给出线性表的抽象数据类型。2.1 2.1 线性表及其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型2.1.1 线性表的基本概念线性表的基本概念n线性表（Linear List）是一种最常用、最简单的典型线性数据结构，应用非常广泛。
2、线性表是由n(n0)个数据元素组成的一个有限序列，线性表中数据元素的个数n称为线性表的长度。当 n=0时，称为空表。n对于非空线性表，数据元素之间存在一对一的关系，具体特性如下：n第一个数据元素没有前驱n最后一个数据元素没有后继外n其他数据元素都是首尾相接、有且只有一个前驱和后继2.1 2.1 线性表及其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型2.1 线性表及其抽象数据类型线性表及其抽象数据类型2.1.1 线性表的基本概念线性表的基本概念n下面的现实问题都可以归为线性表：1）按学号排序的学生基本情况表；2）按成绩排序的学生成绩表；3）体育比赛日程表；4）按
3、年收入排序的世界首富等等。n线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的关系是线性的。线性表可以表示为：（e1,e2,.,ei,.,en）n其中ei（i=1,2,.,n)是线性表中的数据元素，通常称为线性表中的一个结点。e1称为线性表的首结点，en称为线性表的尾结点。2.1 线性表及其抽象数据类型线性表及其抽象数据类型n创建一个线性表n删除一个线性表n在第k个位置插入一个新元素xn判断线性表是否为空n计算线性表的长度n取第k个元素n修改第k个元素n按关键字x查找指定元素n删除第k个元素n删除由关键字x指定的元素n输出线性表2.1.2 线性表的抽象数据类
4、型线性表的抽象数据类型n根据2.1.1节对线性表及其基本操作的抽象，由于抽象数据类型与线性表的元素类型无关，所以下面的元素类型用T来表示。线性表的抽象数据类型List可以定义如下：ADT List 数据对象D=ei|eiT,i=1,2,n，n0 数据关系R=|ei-1，eiD,i=2,3,n 基本操作P：Create()：创建空表Destroy()：删除表 List&Insert(int k,const T&x)：在第k个位置插入元素x，返回插入后的线性表bool IsEmpty()const：判断表是否为空，表空返回true，表非空返回false2.1 2.1 线性表及其抽象数据类型线性表及
5、其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型2.1.2 线性表的抽象数据类型线性表的抽象数据类型int GetLength()const：返回表中数据元素的个数bool GetData(int k,T&x)：将表中第k个元素保存到x中，不存在则返回falsebool ModifyData(int k,T&x)：将表中第k个元素修改为x，不存在则返回falseint Find(T&x)：返回x在表中的位置，如果x不在表中返回0List&DeleteByIndex(int k)：删除表中第k个元素，并把它保存到x中，返回删除后的线性表List&DeleteByKey(T&x)：删除表
6、中关键字为x的元素，返回删除后的线性表void OutPut()const：输出线性表 ADT List2.1 2.1 线性表及其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型线性表及其抽象数据类型2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 n一种在计算机中存放线性表的最简单的的方法是顺序存储。通常通过定义一个一维数组来实现线性表的顺序存储。n把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储，采用顺序存储结构的线性表简称顺序表。线性表的顺序存储结构有如下特点：n线性表中所有元素所占的存储空间是连续的；n线性表的逻辑顺序与物理顺序一致
7、；n数组中的每一个元素的位置可以用公式来确定。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 2.2.1 线性表的顺序表示线性表的顺序表示2.1.3线性表代码复用实例线性表代码复用实例2.2.2 线性表的实现线性表的实现n由于线性表可能有n个数据元素，也可能是空表。所以，在顺序表类模板的数据成员中，除了用来实现顺序表的动态数组，还有两个int型数据成员MaxSize和length。MaxSize用来标识线性表的最大长度，length用来标识当前线性表的长度。图2-1（a）是线性表顺序结构的示意图，每一个数据元素占k个字节；图2-1（b）是C+模板类中实现的顺序表结构示意图。2.2
8、 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现（a）线性表的顺序存储结构 （b）线性表顺序存储的实现图2-1 线性表的顺序存储结构及其实现数据元素存储地址e1LOC（e1）e2LOC(e1)+ke3LOC(e1)+2k.eiLOC(e1)+(i-1)kenLOC(e1)+(MaxSize-1)k数据元素内存变量内存地址e1element0elemente2element1element+1e3element2element+2.eielementi-1element+i-1enelementMaxSize-1element+
9、MaxSize-1n对于顺序表的Create创建操作和Destroy删除操作，使用C+类的构造函数和析构函数来实现。由于顺序表在插入和删除元素时需要移动元素，下面介绍实现插入和删除元素的算法。n1.1.顺顺序表的插入算法序表的插入算法n图2-2是顺序表在表中第 i 个位置插入新元素x时，操作前后元素结构示意图。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 e1e2ei-1eiei+1ene1e2ei-1xeiei+1en图2-2 顺序表插入操作示意图插入前：插入后：2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 n顺序表插入算法实现步骤如下：顺序表插入算法实现步骤
10、如下：判断插入位置的合理性以及表是否已满；从最后一个元素开始，将每个元素向后移动一个位置，直到第i个位置空闲为止；在第i个位置放入新元素x；将线性表长度加1。n下面分析顺序表插入操作算法的时间复杂度下面分析顺序表插入操作算法的时间复杂度：n则在长度为n的线性表中插入一个元素，总的平均移动元素的次数为：n/2，因此，顺序表插入元素操作算法的平均时间复杂度为O(n)。n2.2.顺序表的删除算法顺序表的删除算法图2-3是顺序表删除第 i 个元素时，操作前后元素结构示意图。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 e1e2ei-1ei+1ene1e2ei-1eiei+1en图2-3
11、 顺序表删除操作示意图删除前：删除后：2.2 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现线性表的顺序存储结构及实现线性表的顺序存储结构及实现 2.2.2 线性表的实现线性表的实现n顺序表删除算法实现步骤如下：顺序表删除算法实现步骤如下：判断删除位置的合理性；从第i+1个元素开始，依次向后直到最后一个元素，将每个元素向前移动一个位置；将线性表长度减1。n下面分析顺序表删除操作算法的时间复杂度下面分析顺序表删除操作算法的时间复杂度：n在长度为n的线性表中删除一个元素，总的平均移动元素的次数为（n-1）/2，因此顺序表删除元素算法的平均时间复杂度为O(n)。2.2 线性表的顺序存储
12、结构及实现线性表的顺序存储结构及实现 n【例2-1】基于顺序表的C+实现代码，解决由简单数据元素构成的顺序表的应用问题。对于一个最多由10个整数构成的线性表，采用顺序存储结构，完成如下操作：依次插入100、200、300、400。显示当前表的相关信息。读取并输出表中第3个元素的值，判断元素100在表中的位置。将100修改为150，删除200和400后，显示当前表的相关信息。n分析：对于由简单数据元素构成的线性表，一般可以直接使用C+语言提供的基本数据类型来描述数据元素，本例中可直接使用int类型。由于要求采用顺序存储结构，下面只需要基于LinearList类模板生成数据类型为int类的模板类对
13、象，就可以直接使用类中提供的相应成员函数解决问题了。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 n【例2-2】由较为复杂的数据元素构成的顺序表应用举例。线性表中每一个数据元素表示一名学生的信息，包括学号、姓名和3门课程（语文、数学、英语）的成绩。对于一个最多由10个这样的数据元素构成的线性表，采用顺序存储结构，进行如下操作：将两个结点插入表中显示当前表的状态将表中第2个元素输出删除表中第2个元素，修改表中第1个元素的信息，显示当前表的状态n分析：根据问题对数据元素的描述，将线性表中的数据元素抽象为一个结点类Node，并定义取数据GetNode()函数和输出数据函数OutPut
14、Node(ostream&out)。2.3 线性表的链式表示方法及实现线性表的链式表示方法及实现n线性表的链式存储结构是用一组任意的存储单元存储线性表中的数据元素，称为线性链表。线性链表中结点的可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。所以，在线性表的链式表示方法中，线性表数据元素的逻辑顺序和物理顺序不一定相同。n线性链表又包括单向链表、循环链表和双向链表。链式存储结构需要借助高级语言中的指针类型来实现。2.3 线性表的链式表示方法及实现线性表的链式表示方法及实现2.3.1 链式存储结构链式存储结构2.3.2单向链表及其基本操作单向链表及其基本操作2.3.3单向链表
15、代码复用实例单向链表代码复用实例2.3.4 线性表的顺序存储与链式存储的比较线性表的顺序存储与链式存储的比较2.3.5 循环链表及其基本操作循环链表及其基本操作2.3.6 双向链表及其基本操作双向链表及其基本操作n数据结构中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。每个结点分为两部分：一部分用于存放数据元素的值，称为数据域；另一部分是指针，用于指向与该结点在逻辑上相连的其他结点，称为指针域。对于线性表，指针域用于指向该结点的前一个或后一个结点（即前驱结点或后继结点）。通过结点的指针域将n个结点按其逻辑结构连接在一起的数据存储结构，称为链式存储结构。2.3 2.3
16、线性表的链式表示方法及实现线性表的链式表示方法及实现2.3.1 链式存储结构链式存储结构 在线性链表中，用一个专门的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的最后一个结点的指针为空（用NULL或0表示），表示链表终止，这样的线性链表称为单向链表。图2-4是单向链表示意图。2.3 2.3 线性表的链式表示方法及实现线性表的链式表示方法及实现2.3.2单向链表及其基本操作单向链表及其基本操作nfirstne1ne2 nei nen NULLnnn图2-4 线性表的单向链式存储 对于链式结构，在第1个结点前面如果增加一个头结点，程序代码会变得简洁，程序运行速度也会提高。所以，链式存储结构一般都采用带有头结点的结构，如图2-5所示。2.3 2.3 线性表的链式表示方法及实现线性表的链式表示方法及实现2.3.2单向链表及其基本操作单向链表及其基本操作nn头结点n头结点n（a）带头结点的非空单向链表 （b）带头结点的空单向链表n图2-5 带头结点的单向链式存储结构nheadnheadn1.1.线性链表的插入算法线性链表的插入算法对于插入元素的操作Insert，
