《数据结构与算法》第2章-线性表

数据结构与算法

〔C++语言版〕第2章线性表线性表的类型定义根本概念线性表是由n〔n≥0〕个类型相同的数据元素组成的有限序列，通常表示为L=(a1,…,ai–1,ai,ai+1,…,an)。其中，L为线性表名称，ai为组成该线性表的数据元素，ai–1领先于ai，ai领先于ai+1，称ai–1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,…,n–1时，ai有且仅有一个直接后继；当i=2,3,…,n时，ai有且仅有一个直接前驱。线性表的长度就是线性表中元素的个数n〔n≥0〕。当n=0时，称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素。称i为数据元素ai在线性表中的位序。线性表的类型定义例如，某大学生命科学学院的学生名册可视为一个线性表，如图2.1所示，表中每个数据元素由学号、姓名、性别、年龄、院名称、系名称等数据项组成。从图2.1可以看出，学生名册线性表是一个相当灵活的数据结构，它的长度可根据需要增长或者缩短，即对线性表的数据元素不仅可访问，还可进行插入、删除等操作。线性表的类型定义抽象数据类型描述ADTLinearList{数据集合：D={ai|ai/ElemSet,i=1,2,…,n,n≥0}数据关系：R={<ai-1,ai>|ai-1,ai/D,i=2,…,n}数据操作：Init_List(&L)//初始化线性表,引用参数,操作对象本身输入：空。输出：构造一个空的线性表L。Destroy_List(&L)//撤销线性表输入：线性表L。输出：撤销线性表L。Clear_List(&L)//清空线性表输入：线性表L。输出：线性表L重置为空表。线性表的类型定义List_Empty(L)//判断线性表是否为空输入：线性表L。输出：假设线性表L为空表，那么返回TRUE，否那么返回FALSE。List_Length(L)//求线性表的长度输入：线性表L。输出：线性表L中数据元素个数。Get_Elem(L,i,&e)//取线性表中第i个数据元素的值输入：线性表L，1≤i≤ListLength(L)。输出：用e返回线性线L中第i个数据元素的值。LocateElem(L,e,compare())//返回给定值在线性表中的位置输入：线性表L，compare()是数据元素相等判定函数。输出：线性表L中第1个与e满足相等关系的数据元素的位序。假设这样的数据元素不存在，那么返回值为0。线性表的类型定义Prev_Elem(L,cur_e,&pre_e)//返回当前元素的前一个元素值输入：线性表L。输出：假设cur_e是线性表L的数据元素，且不是第一个，那么用pre_e返回它的直接前驱元素；否那么操作失败，pre_e无定义。Next_Elem(L,cur_e,&next_e)//返回当前元素的后一个元素值输入：线性表L。输出：假设cur_e是线性表L的数据元素，且不是最后一个，那么用next_e返回它的直接后继元素；否那么操作失败，next_e无定义。线性表的类型定义Insert_List(&L,i,e)//在线性表的第i个位置之前插入数据元素输入：线性表L，1≤i≤ListLength(L)+1。输出：在线性表L中第i个位置之前插入新的数据元素e，线性表L的长度加1。Delete_List(&L,i,&e)//删除线性表中第i个数据元素输入：线性表L非空，1≤i≤ListLength(L)。输出：删除L中第i个数据元素，并用e返回其值，线性表L的长度减1。Traverse_List(L,visit())//遍历线性表输入：线性表L。输出：依次对线性表L的每个数据元素调用visit()进行访问。一旦visit()失败，那么操作失败。}ADTLinearList线性表的类型定义线性表抽象类线性表的类型定义异常类NoMem和OutOfBounds如果分配内存失败，应引发一个异常。有时异常可能由new引发，而有时那么需要编程者来引发。为了在所有情形下都能引发一个异常，本节定义一个异常类NoMem，非法操作将会简单地引发一个类型为NoMem的异常。另外，在删除操作中，为了从一个表中删除第k个元素，需要先确认表中包含第k个元素，然后再删除这个元素。如果表中不存在第k个元素，那么应出现一个越界异常，定义为OutOfBounds，每当正在执行的函数中任何一个参数超出所期望的范围时，就引发这种类型的异常。线性表的类型定义线性表的顺序存储结构根本概念线性表的顺序表示线性表的顺序表示，是指用一组地址连续的存储单元依次存储线性表中的数据元素。设a1的存储地址为Loc(a1)，每个数据元素占用d个字节存储单元，那么第i个数据元素的地址为Loc(ai)=Loc(ai)+(i–1)×d，1≤i≤n，如下图：线性表的顺序存储结构Loc(a1)通常称作线性表的起始位置或基地址。只要确定了存储线性表的起始位置，线性表中任一个数据元素都可随机存取。因此，线性表的顺序存储结构是一种随机存取的存储结构。线性表的这种机内表示称为线性表的顺序存储结构或顺序映射。通常，称这种存储结构的线性表为顺序表，其特点是以数据元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。线性表的顺序存储结构线性表的动态分配顺序存储结构的描述线性表的长度可变，而且最大存储空间随问题的不同而不同，因此需要动态地分配线性表的空间。在C++语言中，可用动态分配的一维数组来表示，描述见如下程序：线性表的顺序存储结构线性表的顺序存储结构根本操作线性表的初始化、查找和输出线性表的顺序存储结构线性表的顺序存储结构插入和删除操作插入操作。线性表的插入操作是指在线性表的第i–1个数据元素和第i个数据元素之间插入一个新的数据元素b，其结果是使长度为n的线性表(a1,…,ai–1,ai,…,an)变成长度为n+1的线性表(a1,…,ai–1,b,ai,…,an)，并且数据元素ai–1和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也相邻，因此需将第i～n〔共n–i+1〕个元素向后移动一个位置，才能反映这个逻辑关系的变化。如下图，为了在线性表的第4个和第5个元素之间插入值为25的数据元素，那么需要将第5～8个元素依次往后移动一个位置。线性表的顺序存储结构注意，在插入操作期间，可能出现两类异常：第一类异常发生的情形是没有正确指定插入点，如在插入新元素之前，表中元素个数少于k–1个，或者k＜0，在这种情形下，引发一个OutOfBounds异常；当表已经满时，会发生第二类异常，此时数组中没有剩余的空间来容纳新元素，因此将引发一个NoMem异常。Insert操作的时间复杂度为O(length–k)线性表的顺序存储结构删除操作删除操作。与线性表的插入运算相反，线性表的删除操作是使长度为n的线性表(a1,…,ai–1,ai,ai+1,…,an)变为长度为n–1的线性表(a1,…,ai–1，ai+1,…,an)，并且数据元素ai–1、ai和ai+1之间的逻辑关系也会发生变化，需要把第i+1～n个元素〔共n–i个元素〕依次向前移动一个位置来反映这个变化。如下图，为了删除第4个元素，需要将第5～8个元素依次向前移动一个位置。下图程序中给出了删除操作的C++代码。线性表的顺序存储结构线性表的顺序存储结构时间复杂度分析从上述算法可见，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要消耗在移动元素上，而移动元素的个数取决于插入或删除元素的位置。假设pi是在第i个元素之前插入一个元素的概率，那么在长度为n的线性表中插入一个元素时所需移动元素次数的期望值为不失一般性，假设在线性表的任何位置插入元素都是等概率的，即pi=1/(n+1)，上式可化简为线性表的顺序存储结构对于删除过程，假设qi是删除第i个元素的概率，那么在长度为n的线性表中删除一个元素时所需移动元素次数的期望值为同样假设是等概率的情况，即qi=1/(n+1)，那么有由此可见，在顺序存储结构的线性表中插入或删除一个数据元素，平均约需移动表中一半元素。假设表长为n，那么上面的插入算法和删除算法的时间复杂度均为O(n)。线性表的顺序存储结构以下是一个使用类LinearList的C++程序，它假定之前的程序均存储在LinearList.h之中，且异常类定义位于文件exception.h之中。该例如完成以下操作：创立一个大小为5的整数线性表L；输出该表的长度〔为0〕；在第0个元素之后插入2；在第一个元素之后插入6和8〔至此，线性表为2，6，8〕；寻找并输出第一个元素〔为2〕；输出当前表的长度〔为3〕；删除并输出第一个元素。线性表的顺序存储结构线性表的顺序存储结构该程序执行的结果如下：例2-1

试利用数组来实现线性表的插入、删除、定位操作。例2-1

例2-2一个线性表中的元素按元素值非递减有序排列，试设计算法删除表中多余的值相同的元素。算法一：例2-2算法二：线性表的链式存储结构线性链表线性链表的定义

线性链表是指用一组任意的存储单元存储线性表的数据元素〔这组存储单元可以是连续的，也可以是不连续的〕，通过存储数据元素信息的数据域和直接后继存储位置的指针域构成数据元素ai的存储映射，即结点〔node〕，如以下图所示。n个结点ai〔1≤i≤n〕链接成一个链表，即为线性表(a1,a2,…,an)的链式存储结构。由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。线性表的链式存储结构例如，以下图所示为一个科研团队成员的姓名线性表〔孙强，刘萍，张亮，李明，王冰，钱广，崔齐，吴英〕的线性链表存储结构，整个链表的存取由头指针H开始进行，它指向链表中第一个结点的存储位置，线性链表中最后一个结点的指针为“空”〔NULL〕。线性表的链式存储结构线性表的单链表存储结构的类定义以下程序定义了LinkNode和LinearListLink类，链表对象是线性表抽象类LinearList的派生类，代表整个线性链表，它需要记录首结点的地址和链表中当前结点个数等有关链表的信息，并针对其设置有关操作。线性表的链式存储结构线性表的链式存储结构LinearListLink<T>定义为LinkNode<T>的一个友类，所以LinearListLink<T>可访问LinkNode<T>的所有成员〔包括是私有成员〕。公共成员函数Length、Find、Delete和Insert由抽象类LinearList继承而来。假设L是LinearListLink型变量，那么L可作为一个单链表的头指针，它指向链表中的第一个结点。假设L为空〔L=NULL〕，那么表示线性表为“空”，线性表的长度为0。有时，在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可不存储任何信息，也可存储线性表长度等附加信息；头结点的指针域存储指向第一个结点的指针〔即第一个元素结点的存储位置〕。线性表的链式存储结构线性表的带头结点的单链表存储结构示意图如下图为单链表的一般表示法。线性表的链式存储结构根本操作以下程序给出了析构函数的代码，它的时间复杂度为O(n)，其中n为链表的长度。接下来的程序中的代码分别实现了Length操作和Find操作。Length的时间复杂度为O(n)，Find的时间复杂度为O(k)。Output的时间复杂度为O(n)，它要求对于类型T必须定义<<操作。线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构单链表的插入和删除运算假设要在线性表的两个数据元素X和Y之间插入一个数据元素Z，p为单链表存储结构中指向结点的指针，如以下图〔a〕所示。为插入数据元素Z，首先要生成一个数据域为Z的结点，然后插入到单链表中。根据单链表的逻辑定义，还需修改结点X中的指针域，令其指向结点Z，而结点Z中的指针域应指向结点Y。插入后的单链表如以下图〔b〕所示。线性表的链式存储结构假设s为指向结点Z的指针，那么插入结点操作可以用语句描述如下：s->next=p->next;p->next=s;反之，如以下图所示在线性表中删除元素Y时，仅需修改结点X中的指针域来实现链表中逻辑关系的变化即可。设p为指向结点的指针，那么删除结点操作可用语句描述如下：p->next=p->next->next;可见，在单链表中插入或删除一个结点时，仅需修改指针而无须移动元素。以下程序为Insert和Delete的实现，时间复杂度均为O(n)。因为在第i个结点之前插入一个新结点或删除第i个结点，都需要先找到第i–1个结点，即修改指针的结点，所以它的时间复杂度为O(n)。线性表的链式存储结构成员函数Insert的算法实现：线性表的链式存储结构成员函数Delete的算法实现：例2-3定义和建立单链表，并在链表上实现根本的建空表、查找、定位、求表长、插入、删除、置空运算。结点结构定义：例2-3建表算法：例2-3例2-3例2-3插入算法：例2-4试设计算法逆置一个用带头结点的链表表示的线性表。算法描述如下：线性表的链式存储结构静态链表线性表的链式存储结构如上描述的链表中，数组的一个分量表示一个结点，同时用游标〔指示器cur〕代替指针指示结点在数组中的相对位置，如以下图所示。数组的第0个分量可看成头结点，其指针域指示链表的第一个结点。以下图〔b〕展示了〔a〕所示线性表在插入数据元素“孙晋”之后的状况，〔c〕那么展示了〔a〕所示线性表在删除数据元素“郑彬”之后的状况。为了和指针型描述的线性链表相区别，这种用数组描述的链表称为静态链表，它适合在不设“指针”类型的高级程序设计语言中使用，虽然预先需要分配一个较大的空间，但在进行线性表的插入和删除操作时不需要移动元素，仅需修改指针，因此仍具有链式存储结构的主要优点。线性表的链式存储结构线性表的链式存储结构循环链表循环链表〔circularlinkedlist〕是一种表中最后一个结点的指针域指向头结点，整个链表形成一个环形的链式存储结构，因此从表中任一结点出发均可找到表中其他结点。如下图为单链的循环链表。循环链表的操作和线性链表根本一致，差异在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。线性表的链式存储结构双向链表在需要频繁地同时访问前驱和后继结点时，可采用另一种链表结构，即双向链表。所谓双向链表，就是每个结点都有两个指针域，一个指向直接后继结点，另一个指向直接前驱结点，以下图给出了结点结构和表结构。线性表的链式存储结构双向链表的类定义：线性表的链式存储结构线性表的链式存储结构在双向链表中，假设p为指向表中某结点的指针，那么显然有p->next->prior=p->prior->next=p。对双向链表进行插入和删除时需同时修改两个方向的指针，它们的算法描述和线性表的操作有很大的不同。以下图2.16分别显示了插入和删除结点时指针修改的情况。而以下程序分别对应插入和删除操作，两者时间复杂度均为O(n)。线性表的链式存储结构插入算法：线性表的链式存储结构删除算法：例2-5双向链表的定义及插入和删除操作算法。在双向链表中，每个结点的指针域有两个，一个左指针llink，一个右指针rlink，至少一个数据域data，如下图。双向链表可以是循环的，也可以不是循环的。对于双向链表〔循环链表〕，假设p指向表中任一结点，那么有p=p->llink->rlink=p->rlink->llink。双向循环链表的定义及插入和删除一个结点的算法如下。例2-5结点结构定义：删除一个结点：例2-5插入一个结点：线性表的链式存储结构顺序表和链表的比较线性表的应用——多项式相加与Josephus问题多项式表示设一元n次多项式的通用形式为Pn(x)=++…+，其中pi是指数为ei的项的非零系数，且满足0≤e1＜e2＜…＜em＝n，上述情况可考虑采用一个长度为m且每个元素有两个数据项〔系数项和指数项〕的线性表Pn(x)：((p1,e1),(p2,e2),…,(pm,em))来存储，这样将大大节省空间。在实际应用程序中，假设只对多项式进行“求值”等不改变多项式的系数和指数的运算，那么采用类似于顺序表的顺序存储结构即可，否那么应采用链式存储表示。本节将主要讨论如何利用线性链表的根本操作来实现一元多项式的运算。线性表的应用——多项式相加与Josephus问题由上图中的两个链表表示的多项式相加得到的“和多项式C”链表如以下图所示。线性链表类型适用于一般的线性表，而表示一元多项式的应该是有序链表。线性表的应用——多项式相加与Josephus问题多项式的类定义：线性表的应用——多项式相加与Josephus问题线性表的应用——多项式相加与Josephus问题多项式类的几种构造函数以及析构函数的定义：线性表的应用——多项式相加与Josephus问题线性表的应用——多项式相加与Josephus问题多项式相加多项式相加算法：线性表的应用——多项式相加与Josephus问题例2-6Josephus问题，设有n个人围坐一圈。从第s人开始进行1到m报数，数到第m个人出列。然后，再从出列的下一个人重新开始报数，数到第m个人再出列。如此反复，直到所有的人全部出列为止。现要求按出列次序得出n个人的顺序表。现以n=8，s=1，m=4为例，用图说明报数出列的过程，如下图。图中用s1作为浮动的指针，指向每次报数的起始位置。小圆圈内的数字为报数出列的人员，由图得到n个人按次序报数出列的人员顺序为④⑧⑤②①③⑦⑥。例2-6例2-6为了用计算机求解，设想有一组1～n的整数作为待报数的序列。将它们置于数组p中。当p[i]报数出列时，为了节省空间，可将p[i]从数组中删除并暂存在另一个存储单元w中，且将p[i+1]～p[n]都向前移动一个位置。再将原保存在w中的p[i]值置于p[n]中，如以下图所示；下次再对剩下的n–1个元素进行上述操作，再将报数出列的元素置于p[n–1]中；……；如此反复，直至只剩下一个元素时，就将其保存在p[1]中原处。此时p中保存了报数出列的序列元素的逆序，最后再将p数组中的元素逆转，即得到了按次序报数出列人员的顺序表。例2-6如何确定每次报数出列的位置？由上图可见，由于元素出列后，后面的元素都要向前挪动一个位置，因此，本次报数的出列位置也就是下次报数的起始位置，s1有双重含义。因为报数是首尾连续进行的，所以可用取模的方法；由这次报数的起始位置推算得到下次的报数位置，即是本次报数的出列位置。设i为每次参加报数的人数，那么列出位置可由下式推算而得：s1←(s1+m–1)ModiJosephus问题算法如下。①赋初值s1←s。②报数出列，循环i以–1为步长，从n到2重复执行：〔a〕求“出列”位置s1←(s1+m–1)Modi;ifs1=0thens1←i；〔b〕出列w←p[i]；〔c〕元素前移：循环j以1为步长，从s1到i–1重复执行；p[j]←p[j+1]；(d)令出列元素于报数序列之尾p[i]←w；③逆转出列的序列，循环k以i为步长，从i到i/2重复执行：〔a〕w←p[k]；〔b〕p[k]←p[n–k+1]；〔c〕p[n–k+1]←w。〔注：i/2为不大于i/2的最大整数。〕④输出已出列的序列，算法结束〔具体程序请读者自己完成〕。本章总结学习要点本章主要介绍线性表的概念及其逻辑结构形式定义；顺序和链式两类存储结构的描述及实现方法；在线性表的顺序和链式两类存储结构上，如何进行数据元素的插入、删除、定位、表的归并、集合等根本运算，线性表顺序与链式实现的时空性能比较，以