C++线性数据结构链表

2.2线性表

2.2.1线性表的定义及操作定义2-1线性表(Linear-list)是n(n≥0)个数据元素的有限序列（一对一）。记为：

(a1，a2,...,an)

其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。线性表的结构仅涉及诸元素的线性相对位置，即第i个元素ai处在第i-1个元素ai-1的后面和第i+1个元素ai+1的前面，这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。线性表中每个数据元素ai的具体含义，在不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至是其它更复杂的信息。但在同一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。

线性表的逻辑结构：若线性表是非空表，则第一个元素a1无前驱（前件）（只有一个根结点或首结点），最后一个元素an无后继（后件），其它元素ai(1<i<n)均只有一个直接前驱ai-1和一个直接后继ai+1。下面给出几个线性表的例子：

例2-126个大写的英文字母表：(A，B，C，...，Z)

例2-2

某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出：

(200，220，250，300，400，700，1200)

例2-3

某单位职工政治面貌登记表如表2-2所示，每个职工的情况为一条记录，它由职工号、姓名、性别、职称、工龄、政治面貌六个数据项组成。在表2-2中，一个数据元素由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。表2-2职工政治面貌登记表

职工号姓名性别职称工龄政治面貌

000100020003…张忠王平李林…男女男…工程师助工助工…1222…党员团员团员…

线性表是一个相当灵活的数据结构，它的长度可以根据需要增减，操作也比较灵活方便。线性表的基本操作有以下几种：

(1)INITIATE(L)。初始化操作，设定一个空的线性表L。

(2)LENGTH(L)。求表长，求出线性表L中数据元素个数。

(3)GET(L，i)。取元素函数，若1≤i≤LENGTH(L)，则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。

(4)PRIOR(L，elm)。求前趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空元素。

(5)NEXT(L，elm)。求后继函数，若elm的位序小于LENGTH(L)，则函数值为elm的后继，否则为空元素。

(6)LOCATE(L，x)。定位函数，返回元素x在线性表L中的位置。若L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。

(7)INSERT(L，i，x)。插入操作，在线性表L中的第i个位置上插入元素x，运算结果使得线性表的长度增加1。

(8)DELETE(L，i)。删除操作，若1≤i≤LENGTH(L)，删除给定线性表L中的第i个数据元素，使得线性表的长度减1。

(9)EMPTY(L)。判空表函数，若L为空表，则返回布尔值“true”，否则返回布尔值“false”。对线性表还有一些更为复杂的操作，如将两个线性表合并成一个线性表；把一个线性表拆分成两个或两个以上的线性表；重新复制一个线性表；对线性表中的元素按值的大小重新排序等。这些运算都可以通过上述基本运算来实现。

2.2.2线性表的顺序存储结构在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。图2-2线性表顺序存储结构示意图(设每个数据元素占有1个存储单元)

线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。

(1)设有线性表(a1，a2，...，an)，若1个数据元素只占1个存储单元，则这种分配方式如图2-2所示。若用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为：

Loc(ai)=Loc(a1)+(i-1)

其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址或者基地址。

(2)若1个数据元素占d个存储单元，则有

Loc(ai)=Loc(a1)+(i-1)*dLoc(ai+1)=Loc(ai)+d

可见，线性表中每个元素的存储地址是该元素在表中序号的线性函数。只要确定了线性表的起始地址，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

顺序存储结构是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间相邻的逻辑关系。即顺序存储结构线性表的逻辑关系的存储是隐含的。线性表的顺序存储结构通常称为向量(Vector)。可用字母V来表示，用V［i］表示向量V的第i个分量，设向量下界为1，上界为线性表的长度n（i=1~n），则可以用此向量来表示长度为n的线性表。向量的第i个分量V［i］是线性表的第i个数据元素ai在计算机内存中的映像。

在C语言中，向量即一维数组，所以可用一维数组来描述顺序存储结构。#definemaxlen100

typedef

int

datatype;struct

sqlisttp

{

int

elem[maxlen];datatype

elem[maxlen];

intlast;};

其中，

maxlen是线性表的最大长度，它可以根据实际需要而修改。这里假设线性表的数据元素是整数，当然也可以根据需要取其它类型,甚至还可以是一种结构(即每个数据元素有多个数据项)。数据域elem描述了线性表中数据元素占用的数组空间，线性表的各个元素a1，a2，…，an依次存放在一维数组elem的各个分量elem[1]，elem[2]，…，elem[n]中。数据域last指示最后一个数据元素在数组中的相对位置。在这种存储结构中，线性表的某些操作很容易实现。如线性表的长度即为last域的值等。下面着重讨论线性表的插入和删除两种操作。

算法2-1

线性表的插入算法。已知线性表的当前状态是(a1，a2，…，ai-1，ai，…，an)，要在第i个位置插入一个元素x，线性表变为(a1，a2，…，ai-1，x，ai，…，an)。其实施步骤为：

(1)

将第n至第i个元素后移一个存储位置；

(2)

将x插入到第i个位置；

(3)

线性表的长度加1。…..a2a1an…..ai+1ai01i-1in-1在线性表的第i个元素之前插入一个新的元素，先移动，后插入。ai-1…..a2a1alast…ai+1aixai-1…..a2a1

aiai+1…alast

alast……ai+1

aix#definemaxlen100struct

sqlisttp{/*定义了sqlisttp型的结构

int

elem[maxlen];/*maxlen=n,elem=a*/

intlast;/*last=length*/};sqlisttp

v;/*定义了sqlisttp型的结构对象v

voidinsert(sqlisttp

v,int

i,int

x){intk;

if(i<1||i>v.last+1)

printf(''插入位置不合适！\n'');

elseif(v.last>=maxlen-1)

printf(''线性表已满！\n''); else {for(k=v.last-1;k>=i-1;k--)

v.elem[k+1]=v.elem[k];

v.elem[i-1]=x;

v.last++; }}

算法2-2

线性表的删除算法。已知线性表的当前状态是(a1，a2，…，ai-1，ai，ai+1，…，an)，若要删除第i个元素ai，则线性表成为(a1，a2，…，ai-1，ai+1，…，an)。具体实施步骤为：

(1)

若i值合法，则将第i+1至第n个位置上的元素依次向前移动一个存储单位；

(2)

将线性表的长度减1。…..a2a1an…..ai+1ai01i-1in-1删除线性表的第i个元素，后面所有元素前移。ai-1…..a2a1alast…ai+1aiai-1…..a2a1

aiai+1…alast删除结点aiai+1…alast#definemaxlen100struct

sqlisttp{

int

elem[maxlen];

intlast;};sqlisttp

v;

voiddelete(sqlisttp

v,int

i){intk;

if(i<1||i>v.last)/*存取v的结构成员last

printf(''删除位置不合适！\n'');

else { for(k=i;k<=v.last-1;k++)

v.elem[k-1]=v.elem[k];

v.last--; }}从上述算法中不难看出，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。

假设在第i个元素之前插入一个新元素的概率为1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，则插入操作中元素的平均移动次数(实际上就是时间复杂度)为：

T=

对于删除操作，假定对长度为n的线性表，在表的任何位置上删除元素的概率是相等的，即等于1/n，则删除操作中元素的平均移动次数(即是时间复杂度)为：

T=

从以上分析可以看出，在顺序存储的线性表中进行插入或删除操作，平均要移动一半的元素，即T(n)=O(n)。当线性表的元素很多，且每个元素的数据项较多时，花费在移动元素上的时间会很长。一般情况下，线性表的顺序存储结构适合于表中元素变动较少的线性表。

2.2.3线性表的链式存储结构线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻的。因此，可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。缺点：

在作插入或删除操作时，需移动大量元素；在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，使存储空间不能得到充分利用；表的容量难以扩充。1．线性链表线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。这样，逻辑上相邻的元素在物理位置上就不一定是相邻的，为了能正确反映元素的逻辑顺序，就必须在存储每个元素ai的同时，存储其直接后继元素的存储位置。为克服线性表顺序存储结构的缺点，引进了另一种存储结构——链式存储结构。这时，存放数据元素的结点至少包括两个域，一个域存放该元素的数据，称为数据域(data)；另一个域存放后继结点在存储器中的地址，称为指针域或链域(next)。这种链式分配的存储结构称为链表。datanext此结构的C语言描述为：struct

node{

intdata;

struct

node

*next;/*定义了指向node类型的结构指针 };typedef

structnodeNODE;

/*重新定义该结构类型的新名字NODE}NODE；数据元素的结点结构如下：一般情况下，链表中每个结点可以包含若干个数据域和指针域。若每个结点中只有一个指针域，则称此链表为线性链表或单链表，否则被称为多链表。例2-4

设有线性表由动物名组成：(cat,horse,monkey,elephant,pig,panda)。

它的物理状态如图2-3所示。当链表采用图2-3来表示时，逻辑上的顺序不易观察，所以经常把链表用图2-4所示的逻辑状态来表示。图2-4线性链表的逻辑状态示意图图2-3线性链表的物理状态示意图

在图2-4中，指针域的值用箭头代替了，线性链表结点的相邻关系用箭头来指示，逻辑结构的表示非常形象、清晰。在此单链表中，head是指向单链表中第一个结点的指针，我们称之为头指针；最后一个元素panda所在结点不存在后继，因而其指针域为“空”(用NULL或∧

表示)。可以看出，用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，因此，这种存储结构为非顺序映像或链式映像。在使用中，我们只关心数据元素的逻辑次序而不必关心它的真正存储地址。通常，我们在单链表第一个元素所在的结点之前附设一个结点——头结点（增加的目的是统一空表与非空表的处理）。头结点的指针域存储第一个元素所在结点的存储位置；头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。若线性表为空表，则头结点的指针域为“空”，如图2-5所示。

图2-5带头结点的单链表

2．线性链表的运算线性链表是线性表的链式存储表示，所以对线性链表的运算与前面所介绍的对线性表的运算相同，只是相应的算法与顺序存储的线性表有所不同。设head为单链表的表头指针。下面主要介绍对带头结点单链表的查找、插入、删除等常用操作的算法。对链表操作时，最基本的操作为插入、删除运算。在讨论插入、删除操作之前，首先要解决插入时的新结点从何处取出，删除后的结点又往何处送的问题。在采用链接分配时，总存在一个可利用的内存空间称为可利用空间表，至于可利用空间表是怎样生成的，可以有不同的方法，这里不再介绍。假设可利用空间表总是可以满足存储要求的。这样，每当要调用新结点时就到这个可利用空间表里去取，删除时就把结点归还给这个可利用空间表。在C语言的编程实现时，申请与释放一结点对应于C语言中两个标准函数malloc(sizeof(NODE))和free(p)。

(1)malloc

是从可利用空间表中调用一新结点，并返回该结点的地址。

(2)free(p)将p指向的结点归还给可利用空间表。为方便起见，以后把指针型变量p所指向的结点称为p结点。

1)单链表的查找由于链表存储结构不是一种随机存取结构，要查找单链表中的一个结点，必须从头指针出发，沿结点的指针域逐个往后查找，直到找到要查找的结点为止。

算法2-3

在带头结点的单链表中找出第i个元素所在的结点。NODE*get(NODE*head,inti){ NODE*p;/*等同于structnode*p

intcounter=1;p=head->next;/*通过指针访问结构的成员时必须使用操作符->while((p!=NULL)&&(counter<i)) { p=p->next; counter++;

}if((p!=NULL)&&(counter=i))/*找到,1<=i<=n*/ returnp;else returnNULL;/*找不到,i>n或i<=0*/}注意（1）需事先定义NULL的具体数值，比如：

#defineNULL-1

（2）上述算法的平均时间复杂度为：

T(n)=O(n)。

2)单链表的插入设有线性表(a1，a2，...，ai-1，ai，...，an)，用带头结点的单链表存储，头指针为head，要求在线性表中第i个元素ai之前插入一个值为x的元素，线性表变为(a1，a2，…，ai-1，x，ai，…，an)。

插入前单链表的逻辑状态如图2-6所示。

图2-6带头结点单链表的逻辑状态

为插入数据元素x，

(1)

首先要生成一个数据域为x的新结点s；

(2)

然后确定插入位置，即找到ai之前的元素

ai-1，并使指针p指向之；

(3)

最后改变链接，将x插在ai-1与ai之间，修改结点p和结点s的指针域。即

s->next=p->next；p->next=s。插入结点s后单链表的逻辑状态如图2-7所示。图2-7在单链表中插入结点S

算法2-4voidinsert(NODE*head,inti,intx){ NODE*p,*s;

intj=0; p=head; while((p!=NULL)&&(j<i-1)) { p=p->next; j++; }

if((p==NULL)||(j>i-1))

printf(''i值不合法\n'');/*找不到,i>n或i<=0*/ else { s=(NODE*)malloc(sizeof(NODE));/**/ s->data=x;/**/ s->next=p->next;/**/ p->next=s;/**/ } }

如果事先告之p指针所指的位置，则这种在p指针后插入一个元素算法的时间复杂度T(n)=O(1)，否则平均时间复杂度T(n)=O(n)。

3)单链表的删除删除操作和插入操作一样，

(1)首先要搜索单链表以找到指定删除结点的前趋结点(假设为p)；

(2)然后改变链接，即只要将待删除结点的指针域内容赋予p结点的指针域即可。设有线性表(a1，a2，...，ai-1，ai，ai+1，...，an)，用带头结点的单链表存储，删除前的逻辑状态如图2-8所示。

删除元素ai所在的结点之后，单链表的逻辑状态如图2-9所示。图2-8带头结点的单链表图2-9在单链表中删除一个结点算法2-5voiddelete(NODE*head,inti){ NODE*p,*s;

intj=0; p=head; while((p->next!=NULL)&&(j<i-1)) {p=p->next; j++;}

if((p->next==NULL)||(j>i-1))

printf(“i值不合法\n”);/*找不到,i>n或i<=0*/ else {s=p->next; p->next=s->next; free(s); } }

如果事先告之p指针所指的位置，则这种在p指针后删除一个元素算法的时间复杂度T(n)=O(1)，否则平均时间复杂度T(n)=O(n)。

4)动态建立单链表的算法要对单链表进行操作，首先要掌握怎样建立单链表。链表是一种动态存储结构，所需的存储空间只有在程序执行malloc之后，才可能申请到一个可用结点空间；free(p)的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统应需求即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。动态建立线性表的链式存储结构有两种基本方法，分别适用于不同的场合。可根据所建链表结点的顺序要求选择采用一种方法。

单链表建立方法一：反向建立链表（头插法）。

思想：若线性表的元素已顺序存放在一维数组A[N]中，建表方法是从线性表的最后一个元素开始，从后向前依次插入到当前链表的第一个结点之前。算法2-6#defineNm/*m为链表中数据元素的个数,如m=10*/intA[N]; NODE*creatlink1(){ NODE*head,*s;

inti; head=(NODE*)malloc(sizeof(NODE));/*生成头结点*/ head->next=NULL;/*置空表*/ for(i=N-1;i>=0;i--)/*插入10个数据*/

{ s=(NODE*)malloc(sizeof(NODE));/*生成新结点*/ s->data=A[i];/*将输入数据放入新结点数据域*/ s->next=head->next;/*新结点与原首结点链接*/ head->next=s;/*将新结点插入到表头*/ } returnhead;/*返回单链表头指针*/}算法的时间复杂度为：T(n)=O(n)

单链表建立方法二：正向建立单链表（尾插法）。

思想：依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点之后。图B新结点*s插入到单链表head的尾上算法2-7NODE*creatlink2(){ NODE*head,*p,*s;

intnum; head=(NODE*)malloc(sizeof(NODE));/*生成头结点*/

scanf(“%d”,&num);/*读入第一个结点值*/ p=head;/*头指针=尾指针*/ while(num!=0)/*输入为0为输入结束符*/

{ s=(NODE*)malloc(sizeof(NODE));/*生成新结点*/ s->data=num;/*新结点上填入输入值*/ p->next=s;/*新结点*s插入到尾结点*p之后*/ p=s;/*尾指针p指向新的表尾*/

scanf(“%d”,&num);/*读入下一个结点值*/ } p->next=NULL;/*将尾结点的指针置空*/ returnhead;/*返回单链表头指针*/}算法的时间复杂度：T(n)=O(n)

3.线性链表算法示例

例2-5

求不带头结点的头指针为head的单链表中的结点数目。解：

intlength(NODE*head) {NODE*p;

intj; p=head; j=0;while(p!=NULL) { p=p->next; j++; } returnj;}算法的平均时间复杂度：T(n)=O(n)

例2-6

设计算法：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序。解：voiddisA(NODE*A,NODE*B){ NODE*r,*p,*q; B=(NODE*)malloc(sizeof(NODE)); /*建立单链表B的头结点*/ r=B; p=A->next; while((p!=NULL)&&(p->next!=NULL))

{ q=p->next; p->next=q->next; r->next=q; r=q; p=p->next; } r->next=NULL; p->next=NULL;}

例2-7

已知两个不带头结点的单链表A、B分别表示两个集合，其元素递增有序。试设计算法求出A与B的交集C。要求C另外开辟存储空间，并同样以元素值递增的带头结点的单链表形式存储。解：voidintersectionset(NODE*A,NODE*B,NODE*C){ NODE*r,*p,*q,*s; C=(NODE*)malloc(sizeof(NODE)); r=C; p=A; q=B; while((p!=NULL)&&(q!=NULL)) { if(p->data<q->data)

p=p->next; elseif(p->data>q->data) q=q->next; elseif(p->data==q->data) { s=(NODE*)malloc(sizeof(NODE)); s->data=p->data;r->next=s; r=s; p=p->next; q=q->next; } } r->next=NULL;}

2.2.4循环链表和双向链表

1.循环链表

如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。图2-10循环单链表

循环链表一般设表头结点，这样链表将永不为空，这将使空表和非空表的逻辑状态及运算统一起来。循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。与单链表比较，循环链表有以下特点：

(1)

在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。

(2)

循环单链表的空表判定条件是：

head->next=head。

2．双向链表前面讨论的链式存储结构中只有一个指示直接后继的指针域，所以从某结点出发只能顺指针往后查找其它结点。若要查找结点的直接前趋，则应从头指针出发(或在循环单链表中从p结点出发)一直往后找，直到结点q满足q->next=p，那么q是p的前趋结点。为克服链表这种单向性的缺点，为有更大的灵活性来操作线性链表，可采用双向链表存储结构。在每个结点上增加另一个指向线性表中每个元素的前趋结点的指针域prior，就得到双向链表。其结点的结构如