数据结构：第12章 线性表

1、第12章 线性表,主要内容,线性表的定义 抽象链表类 单链表 循环链表,12.1 线性表的定义,线性表的逻辑结构 线性表的顺序存储表示 线性表的链式存储表示,12.1.1 线性表的逻辑结构,线性表是n=0个数据元素a1，a2an-1，an的有序集合。表中每个元素ai在表中的位置仅取决于元素本身的序号i。当1in时，ai的直接前驱为ai-1，ai的直接后继为ai+1。也就是说，除表中第一个元素a1与最后一个元素an外，其他每个元素ai有且仅有一个直接前驱和一个直接后继；第一个元素a1仅有一个直接后继，最后一个元素an仅有一个直接前驱,上述这种结构的特点是数据元素之间存在一对一的关系，这种特点的数

2、据结构称为线性结构，也称为线性表。 一个线性表可以用一个标识符来命名。例如： L=( a1，a2，a3an-1，an ) 注意：同一线性表中的元素必定具有相同的特性，都属于同一数据对象,线性表中的数据元素在不同情况下可能有不同的具体含义。 如 L1 ( 1.2，-2.3，56，0，45.7 ) L2 ( a，d，c，g，j，l ) 在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成,例如：学生名册： 010501黎明17男 010502王烟18女 010503曲柳17女 010504何旦 旦19男 010505李美16女,12.1.2 线性表的顺序存储方式,在计算机内部可以采用两种不同方

3、法来表示一个线性表，它们分别是顺序表表示法和链表表示法。 顺序表示法的定义； 元素的地址表示； 顺序表示法的优、缺点,顺序表示法的定义,顺序表示法用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构称为线性表的顺序存储结构，并称此时的线性表为顺序表,线性表的顺序表示,最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻,顺序映象,以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,以“存储位置相邻”表示有序对 即：LOC(ai) =

4、 LOC(ai-1) + C 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址,线性表的顺序存储结构示意图,元素的地址表示,假设线性表的每个元素占用C个存储单元，那么，在顺序存储结构中，线性表的第i+1个数据元素ai+1的存储位置与第i个数据元素ai的存储位置之间满足如下关系： LOC(ai+1) = LOC(ai)+C LOC(ai) = LOC(a0)+i*C LOC(a0)为线性表的首地址或基地址,以元素在计算机内存中的“物理位置相邻” 来表示线性表中数据元素之间的逻辑关系， 只要确定了首地址，

5、线性表中任意数据元 素都可以随机存取,顺序表示法的优缺点,优点： 1）存储密度大、空间利用率高； 2）数据元素逻辑位置相邻，物理位置也相邻。可随机存取，所以称为随机存取结构。 缺点： 1）插入和删除时要移动大量的元素； 2）长度较大的线性表须按最大需要的空间来分配存储空间,12.1.3 线性表的链式存储表示,链式存储表示的定义 链式存储表示的实现 链式存储表示的特点,线性表的链式表示,用一组地址任意的存储单元存放线性表中的数据元素,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象,以“结点的序列”表示线性表 称作链表,结点：数据元素的存储

6、映象，由数据域和指针域构成,设ai的存储位置为p,则ai+1的地址q是：q=p-next,链式存储方式,链式存储结构不要求逻辑上相邻的数据元素在物 理位置上也相邻,链表：是用一组地址任意的存储单元存放线性表的各个数据元素，通过保存直接后继的存储位置来表示元素之间的逻辑关系； 所有的数据元素都分别保存在具有相同数据结构的结点中,结点是链表的基本存储单位,结点与数据元素一一对应； 每个结点在链表中使用一块连续的存储空间,而相邻结点之间不必使用连续的存储空间,链式存储表示的特点,逻辑上相邻的元素对应的存储位置是通过指针反映的，不要求物理上相邻。进行插入、删除运算时，只需修改被插入位置指针域。 一般不

7、预先分配好足够的存储空间以备使用，当有元素插入时，需临时分配一个空的结点空间，填上信息，插入到线性链表中；当某个结点不再使用时，应将其存储空间释放。 不足之处：每个结点设有一个指针域，存储空间的开销较大,12.2 抽象链表类,线性链表的实现 抽象链表类的定义 抽象链表类中典型成员函数的实现,链式存储的实现,数据元素的存储结构结点 结点 (表示 数据元素的映象) = 元素 + 指针(指示后继元素的存储位置,如果结点中只包含一个指针域，称为单链表,链表是动态数据结构，通过指针（链）将结点链接在一起。结点包括两部分：数据信息和链接结点的指针；结点分为表头结点和表结点； 指向链表表头结点的指针(表头指

8、针，也称为头指针)； 表头结点(链表的第一个结点)，一般不存放数据元素的信息； 表结点（数据结点，也称为结点，保存数据信息,链表结点与组成,线性链表的相关术语,表头指针：存放线性链表中第一个结点的存储地址； 空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针； 表头结点：线性链表的第一数据元素结点前面的一个附加结点，称为头结点。头结点不保存数据。 带表头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表,链表的图示,template class ListNode public: ListNode( ) next = Null;/无参数，构造一个空结点 L

9、istNode(const type /结点的指针域,链表结点类的定义,获取表头指针； 求链表的长度； 寻找第i个数据元素； 根据关键字值求数据元素在链表中的位置； 插入数据元素； 修改数据元素的值； 删除数据元素,链表的常用操作,12.2.2 抽象链表类的定义,线性链表有3种：单链表、循环链表与双向链表； 抽象出上述三种线性链表的相同点（结点、指针和相同操作），建立一个抽象链表类，再由此抽象链表类派生出新的链表类（单链表和循环链表）； 采用类模板机制； 增加表头结点，统一空表和非空表的操作,抽象链表类定义,template /抽象类链表的定义 class ablist public: Lis

10、tNode*GetHead( ) /获得表头结点指针 return head; /取出链表中的第i个元素 type Get(int i,抽象链表类定义,将链表中第i个结点元素值设置为x bool Set(type x, int i); /寻找数据元素值为value的结点地址 ListNode*Find1(type value); /寻找链表中第i个结点元素的地址 ListNode*Find(int i,void MakeEmpt( ); /将链表置为空表 /纯虚函数，取得结点n的下一个结点位置 virtual ListNode *GetNext (ListNode,纯虚函数，将链表中第i个结点

11、删去 virtual int Remove(int i)=0; /纯虚函数，将元素值为value的结点删去 virtual int Remove(type value)=0; protected: /链表的数据成员：头指针和表长 ListNode *head; int length;,12.2.3 抽象链表成员函数的实现,设置函数：将第i个结点数据元素值设为x。 template bool ablist:Set(type x, int i) ListNode *p = Find(i); /寻找第i个结点位置 if(p=NULL|p=head) /i值不合法或为空表，返回false return

12、 false; else p-data=x; /修改第i个结点的数据元素值 return ture;,取值函数：返回第i个结点的数据元素值。 template type ablist:Get(int i) /寻找指向第i个结点位置 ListNode *p=Find(i); assert (p /返回第i个结点的数据元素值,清空链表：用q指向第一个结点，当链表不空时，循链逐个删除，仅保留表头结点。 template void ablist:MakeEmpty() ListNode *q=head-next; int i=1; /链表不空，所以至少有一个结点 while(i+ next=q-nex

13、t; delete q; /循链逐个删除，仅保留表头结点 q=head-next; length=0;,搜索数据元素值为value的结点 template ListNode*ablist:Find1(type value) ListNode *p=head-next; int i=1; /循环条件包含空链表的情况 while (i+ data!=value) p=p-next; /循链找数据元素值value的结点 return p;,定位函数：返回链表中第i个元素结点的地址 template ListNode*ablist:Find(int i) if(ilength) return NULL

14、; if(i=0) return head; /i=0时返回表头结点的地址 ListNode*p=head-next; /让检测指针p指向表 中第1个结点 int j=1; while(p!=NULL /返回第i个结点地址,12.3 单链表,单链表的定义 单链表类的定义 单链表常用成员函数的实现 单链表举例：一元多项式加法,12.3.1 单链表的定义,单链表的定义 带表头结点的单链表,单链表的定义,单链表用一组任意的存储单元来存储线性表的各个数据元素，这些存储单元可以是连续的，也可以是不连续的； 为了表示线性表中每个元素与其直接后继元素之间的逻辑关系，单链表由一个个结点组成，每个结点作为数据元

15、素的存储结构，包含数据域（data）和指针域（next）两部分,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针,空指针,线性表为空表时， 头结点的指针域为空,线性表的n个数据元素对应的n个结点通过链接方式链接成一个链表，每个结点只有一个指针域，所以称为单链表。 可以将线性表（a1，a2，a3.an-1，an）直观地表示成用指针相链接的结点序列,整个单链表可以由一个称为头结点的head来指出，标明单链表的首地址； 当链表为空时，head =NULL； 单链表可

16、以由头结点指针唯一确定； 链表中任意结点的存储位置都可以从head开始，通过对链表进行遍历得到； 设p指向元素ai，则元素ai+1的地址q是： q=p-next,带表头结点的单链表,为了算法设计的方便，往往为每一个链表加上一个表头结点,不含数据结点的空链表,带头结点的单向链表,空表,怎样判断带头结点的单向链表是否为空表？ 如果：head-next = NULL 成立，则为空表。 等价： 如果：head-next != NULL 成立，则不是空表,不带头结点的单向链表,怎样判断不带头结点的单向链表是否为空表？ 如果：head = NULL 成立，则为空表。 等价： 如果：head != NULL

17、 成立，则不是空表,结点之间的基本关系,a3,a4,a2,a5,p,p-next,q,r,s,q,则下列关系成立,r-next,s,q,next-next,p,next-next-next,通过当前结点 p 要访问下一个结点，则指向下一个结点的指针为： p-next 通过当前结点 p 要访问下一个结点的下一个： p-next-next,12.3.2 单链表类的定义,单链表是简单的链表，可以直接从抽象链表类派生出来，定义如下： class List：public ablist public： List（） /构造函数，建立一个空链表 head = new ListNode ；length = 0

18、； /构造函数，用于通过一个现有链表建立新链表 List（List delete head; /将链表置空 /将新元素插入在链表中第i个位置 bool Insert(type value, int i); type Remove(int i); /将链表中第i个结点删去 type Remove1(type value); /删去表中值为value 的结点 /取得结点n的下一个结点位置 ListNode *GetNext(ListNode,List,说明： （1） 定义了两个构造函数, 一个用来构造一个空链表，仅生成一个头结点（头结点数据域中可以为空，也可以来放一些和链表相关的数据），并将表头h

19、ead初始化为NULL；另一个是利用一个现有链表建立新链表；析构函数用来回收元素结点所占的内存,说明： （2） 对于在抽象链表中定义三个纯虚函数：Insert（type，int）、Remove（int）、Remove1（type）。在单链表中，应给出其具体实现，用来实现链表的插入、删除操作； （3） 重载了二个运算符，赋值运算符用于同类型链表赋值，输出运算符用于输出一个链表；还有一个拷贝函数用于同类型单链表的拷贝,12.3.3 单链表常用成员函数实现,在第i个位置插入一个新结点 删除链表指定位置i处的结点 删除数据元素为value的结点 拷贝链表 取得结点n的下一个位置 重载赋值运算符* 重载

20、输出运算符,在单链表第i个位置插入一个新结点,基本原理: 寻找插入点的前一个位置i-1; 若为空表，应将表尾指针指向新结点; 从内存中申请一个新的空结点，将数据信息置于新结点的数据域内,插入新结点步骤,链接后面指针 p-next = q-next,链接前面指针 q-next = p,定位 指针 q 指向第 i-1 个结点，指针 p 指向需要插入的结点,template bool List:Insert(type value，int i) ListNode *q=Find(i-1); /定位插入点的前一位置 if(q=NULL) return false; /i值不合理，返回false /创建新

21、元素结点 ListNode *p= new ListNode (value,p-next); assert(p); p-next=q-next; q-next=p; length+; return true;,删除指定位置i处的结点,利用Find(i-1)函数找到第i-1个元素结点； 保留被删结点的数据值，重新拉链(摘链)； 若被删结点为表尾结点时，修改表尾指针; 最后应释放被删结点的内存空间; 将链表长度减1,在链表中删除第 i 个结点（基本原理,摘链 p-next = q-next,释放 q节点 delete q,定位 指针 p 指向第 i-1 个结点，指针 q 指向被删除的结点,temp

22、late type List:Remove(int i) /p定位于第i-1个元素结点 ListNode *p=Find(i-1), *q; assert(p,删除元素值为value的结点,循链寻找数据值为value的前一结点； 若已至表尾，且其值不为value，返回NULL； 否则，重新拉链，将此结点断开（摘链）； 若被删结点为表尾结点时，应修改表尾指针； 回收被删结点的内存空间，将链表长度减1,template type List:Remove1(type value) ListNode *q，*p=head; /循链寻找数据值为value的前一结点 while(p-next!=NULL,

23、拷贝链表：将链表l拷贝给当前链表对象,算法： 判断链表l是否为空，若链表l为空，返回； 若不空，为当前链表头结点分配存储空间； 将链表l头结点内容复制给当前链表头结点； 循链进行结点间的赋值； 赋值过程为：建立一个新结点、给结点赋值、将其链接到当前链表表尾，将当前链表指针p后移，再将链表l指针q后移,template List,为当前链表头结点分配存储 head=new ListNode; if(!head) return *this; /若分配失败，返回 head-data=(l.head)-data; /将链表1头结点内容 复制给当前链表头结点 head-next=NULL; r=NULL

24、; p=head; / p指向当前链表头 /将q指向链表1的第二个结点 q=l.head-next,while(q) /从第二个结点至链尾进行结点间的赋值 r=new ListNode; /建立一个新结点 if(!r) return *this; /失败，返回 r-data=q-data; /给结点赋值 r-next=NULL; p-next=r; /将新结点链接到当前链表头结点后面 p=p-next; /当前链表指针后移，p指向第一个结点 q=q-next; /链表1指针后移 return *this;,template /函数模板 ListNode * List:GetNext(ListN

25、ode,取得结点n的下一个位置GetNext,12.3.5 单链表举例,其存储结构可以用顺序存储结构，也可以用单链表,一元多项式的表示及相加,12.3.5 单链表举例,如果在线性链表中仅存储系数非零的那些项，则多项式中的每个系数非零项对应一个具有三个域的链表结点，结点的结构如下,coef存放系数， exp存放指数， next域存放指向下一项所在结点的指针,12.3.5 单链表举例,假设Bm(x)为一元m阶多项式， An(x)为一元n阶多项式，则Bm(x)与An(x)的相加运算 Cn(x)= An(x) +Bm(x)，用线性表表示为： C=(an, an-1, , am+1, am+bm, am

26、-1+bm-1, , a0+b0) 式中，假设nm,12.3.5 单链表举例,一元多项式加法运算 两个多项式中所有指数相同的项对应的系数相加，若系数和不为零，则构成“和多项式”中的一项，而将所有指数不相同的那些项复制到“和多项式”中,算法中可设置两个活动指针变量p和q，它们分别沿着A链表与B链表依次访问链表中的结点，p的初值为A，q的初值为B，即分别指向各自链表的第一个结点,算法的核心： 比较p和q所指结点的exp域的值。 若相同，则将两结点的系数域值相加，若相加的结果不为0，则把这个结果和相应指数分别存入C链表中新分配的空结点的系数域和指针域； 若p与q所指的结点指数不同，先将指数较低的哪一

27、项复制到C链表中，然后将p或者q移向下一个结点； 重复上述步骤，当p=NULL（或q=NULL）时，就将B链表（或A链表）中剩余的部分复制到C链表中，直到p、q均为空时算法结束,12.4 循环链表,循环链表（带有头结点的单向环表） 最后一个结点的指针域的指针又指回第一个结点（头结点）的链表,a1 a2 . an,与单向链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点,判断为是否空表的条件： h-next = h,12.4 循环链表,循环链表的特点 从一个结点可找到链表中的任意一个结点； 判断是否为表尾结点的条件：p-next = h。 有时，用表尾指

28、针表示循环链表,Josephus问题,n个人围坐在一圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此反复直到所有的人全部出列为止。Josephus问题是：对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。 现以n=8，s=1，m=4为例，问题的求解过程如下列图所示。图中s1指向开始报数位置，带圆圈的是本次应出列人员。若初始顺序为n1，n2，n3，n4，n5，n6，n7，n8，则问题的解为n4，n8，n5，n2，n1，n3，n7，n6,c) n4 n8 n5 (d) n4 n8 n5 n2,a) n4 (b) n4 n8,e

29、) n4 n8 n5 n2 n1 (f) n4 n8 n5 n2 n1 n3,g) n4 n8 n5 n2 n1 n3 n7 (h) n4 n8 n5 n2 n1 n3 n7 n6,步骤： 1. 建立顺序表：利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表 2. 出列：从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程，直到Josephus表中的所有元素都删除,顺序表方式实现,循环链表方式实现,步骤 1. 建立循环单链表2. 寻找第s个结点，输出并删除第m个节点,本章小结,1.了

30、解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表,2. 熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现,3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合,动态申请内存操作符 new,new 类型名T（初值列表） 功能：在程序执行期间，申请用于存放T类型对象的内存空间，并依初值列表赋以初值。 结果值：成功：T类型的指针，指向新分配的内存。失败：0（NULL,动态存储,new的语法,例：int *s; s=new int; 若用new分配的类型为数组，需要在类型名后缀上数组的大小; 例: int *p=new int10; 或 int *p; p=new int10; 若创建多维数组，必须提供所有维的大小; 例： int *q=new int234,动态存储,释放内存操作符delete,delete 指针P 功能：释放