数据结构（第2版）（教育部规划）第2章

第2章线性表2.1线性表逻辑结构2.2

顺序存储结构

2.3

链式存储结构

2.4

单向循环链表

2.5

双向循环链表

2.6

一元多项式的存储与运算

线性结构：在数据元素的非空集中，存在惟一的一个首元素；存在惟一的一个末元素；除首元素外每个元素均只有一个直接前驱；除末元素外每个元素均只有一个直接后续。在许多领域中都有线性结构的概念，在计算机科学中，线性结构也被称为线性表。栈和队列是线性表的特例。2.1线性表的逻辑结构1、定义：一个线性表是n个数据元素的有限序列。2、设Linear_list=(D，R)是一个数据结构，其中

D={a0，a1，…，an-1}D为同类型数据元素集合;i=0，1，…，n-1，并且n≥0;R为关系的集合R={N};N={<ai-1，ai>|ai-1，ai∈D，i=1，2，…，n-1}。线性结构中所有结点，按照它们之间的关系，可以排成一个线性序列：

a0，a1，…，ai-1，ai

，ai+1，…，an-1

3、术语：称a0为“起始结点”，an-1为“终止结点”。ai的前驱为ai-1，后续为ai+1，n为线性表的长度，当n=0时称为空表。

4、例如：alphabet=(a,b,c,…,z)和prime=(2,3,5,7,11,…,97)

alphabet是字母表，其结点是一个英文字母，prime是100以内的素数表，结点是整型数。且只有一个域的线性表，

有多个域的线性表学号姓名性别出生日期所在院系政治面貌9906201钱钢男81/06/01生科院团员9906202张俊强男80/12/21数科院团员9906203李梅女81/04/18地科院团员………………………………

上表中，每一行作为一个结点，结点有六个域：学号、姓名、性别，出生日期，所在院系，政治面貌。

5、线性表的基本操作如下：

(1)存取。存取表中第i个数据元素ai(0≤i≤n-1)。

(2)插入。在表中第i(0≤i≤n-1)个数据元素ai之后插入一个新的数据元素。

(3)删除。删除表中第i个数据元素ai(0≤i≤n-1)。

(4)合并。将二个或二个以上的线性表合并成一个线性表。

(5)分解。将一个线性表拆分成多个线性表。

(6)查找。在线性表中查找满足某种条件的数据元素

2.2顺序存储结构

1、存储结构

(1)定义：用一组地址连续的存储单元依次存放线性表的所有元素。以元素在内存中位置的关系来表示元素之间的逻辑关系，这就是线性表的顺序存储结构。每个数据元素需要占用t个存储单元，并且第一数据元素的存储单元的地址作为连续存储单元的地址，则第i个数据元素的存储位置为：

LOC(ai)=LOC(a0)+i*t

只要有了第一个结点的起始地址，这对表中任意一个结点i(0≤i≤n-1)，都可按相同的速度进行访问，这种存储结构称为“随机存取的数据结构”存储地址内存状态元素在线性表中位序LOC(a0)a0

0LOC(a0)+ta1

1…LOC(a0)+(i-1)tai

i…LOC(a0)+(n-1)tan-1

n-1图2.2线性表顺序存储结构示意

(2)顺序存储结构的表示。可用C语言中的一维数组来表示(但数组不是线性表，数组中存放的是线性表)

#defineMAX100

struct

sqlist

{int

v[MAX];/*线性表的存储空间*/

intlength;/*线性表的当前表长*/

};

typedef

struct

sqlist

SqList;

说明：SqList为线性表类型，它包含两个域，其中：length=n为表长，数组v有MAX个存储单元，下标从0~MAX-1，且n<MAX，用于存储线性表。

(3)例子：如有一个线性表为：(a0,a2,…,an-1)，则线性表在数组中的存储示意图如图2.3所示。V数组下标数组元素内容数组元素的序号0a0

01a1

1…n-1an-1

n-1MAX-1…

图2.3线性表顺序存储结构示意

2、顺序存储结构下的操作(1)插入insert(L,x,i)：在线性表L中第i(0≤i≤n-1)个数据元素ai之后插入一个新的数据元素x。插入前线性表长度为n，线性表为

(a0，…，ai，ai+1，…，an-1)

插入后线性表长度为n+1，线性表为

(a0，…，ai，x，ai+1，…，an-1)下标01ii+1n-1MAX-1

Va0a1…aiai+1…an-1…

下标01ii+1i+2nMAX-1

Va0a1…aixai+1…an-1…

线性表中数据元素的插入前后如下图所示

算法2.1

顺序存储结构下线性表插入算法：

在表中第i(0≤i≤n-1)个元素后插入一个新元素

/*在L->v[i]之后插入x，同时修改表的长度L->length*/

int

SqList_Insert(SqList*L,int

i,intx)

{intj;

if(i<0||i>=L->length)return(0);/*0表示操作失败*/

for(j=L->length-1;j>=i+1;j--)L->v[j+1]=L->v[j];

L->v[i+1]=x;L->length++;return(1);/*1表示操作成功*/}2.删除delete(L,i)

删除表L中第i个数据元素ai(0≤i≤n-1)，删除前线性表长度是n，线性表为

(a0,…,ai-1,ai,ai+1,…,an-1)

删除后线性表长度为n-1，线性表为

(a0,…,ai-1,ai+1,…,an-1)

下标01i-1ii+1n-1MAX-1

a0a1…ai-1aiai+1…an-1…

下标01i-1in-2MAX-1

a0a1…ai-1ai+1…an-1…

线性表中数据元素的删除前后如下图所示

算法2.2顺序存储结构下线性表删除算法：

删除线性表中第i个元素。

/*删除L->v[i]，同时修改表的长度*/

int

delete(SqList*L,inti)

{intj;

if(i<0||i>=L->length)return(0);/*0表示操作失败*/

for(j=i+1;j<L->length;j++)L->v[j-1]=L->v[j];

L->length--;

return(1);/*1表示操作成功*/

}

3、效率分析通过对算法2.1和2.2分析可知，在插入、删除时，算法执行时间的长短是由结点的移动次数决定的，因此可以用结点移动次数度量这两个算法的时间复杂度。而结点移动的次数取决于插入和删除的位置i。最坏情况是i=0，即插入和删除是v[0]中的元素，结点的移动次数是n和n-1，所以，插入和删除算法的最坏时间复杂度是O(n)。最好情况是插入和删除的位置是n-1，即插入和删除的是v[n-1]中的元素，这时，无需移动结点，所以，在插入和删除中，平均移动结点的次数是(n-1)/2，因而，它们的平均时间复杂度也是O(n)，这里假定线性表在任何位置上插入和删除是等概率的。2.3链式存储结构

1、概念线性表的顺序存储结构中，当进行插入和删除操作时，存在大量数据元素移动。为此考虑采用另一种存储结构——链式存储结构。在链式存储结构中，数据元素的存储单元是不连续的。每个元素除存储自身信息外，还需存储其后继元素的信息。每个元素的存储映象称为结点。

表示数据元素内容的部分被称为数据域(data)；表示直接后继元素存储地址的部分被称为指针或指针域（next）。在C语言中，存储每个数据元素的结点结构描述如下：

struct

lnode{intdata;

struct

lnode*next;};

typedef

struct

lnode

LNode;

例如，一个线性表：(a,b,c,d),存储结构如图2.6所示。headd^

cba

链表从首指针head开始，指向链表中第一个结点的存储位置。同时，由于最后一个元素没有直接后继，所以线性表中最后一个结点的指针为“空”(NULL，用^表示)，而当head为NULL时，head所指向的线性表为空表，其表长n=0。

带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。

例如，一个线性表：

(a0，…，ai-1，ai，ai+1，…an-1)

带头结点的链表（空表）如下图所示：

2、链式存储结构下的操作

注意：在链式存储结构下，增加一个结点需要向系统申请，申请方法为

p=(LNode*)malloc(sizeof(LNode))；删除一个结点时，要将已删除的结点的存储空间释放，释放的方法为：

free(p)(1)建立链表

生成一个结点p，将其作为头结点(head=p)。然后，依次建立新结点p，将其数据域置入相应的值，并将其链接到链表的尾部，且tail始终指向链表最后一个结点。最后，将尾指针所指结点的指针域赋“空”(NULL)。用C语言描述的算法如下。

算法2.3

建立有n个结点的线性单链表的算法。/*建立带有头接点，且数据元素为1到n的单链表，首指针为head*/

LNode*LinkList_Create(intn)

{LNode*head,*p,*tail;/*tail指向尾节点*/

inti;head=tail=(LNode*)malloc(sizeof(LNode));

for(i=1,j<=n;i++){p=(LNode*)malloc(sizeof(LNode));

p->data=i;tail->next=p;tail=p;}tail->next=NULL;

return(head)；

}

(2)插入结点

要在如图2.9所示线性表的两个数据元素y和z之间插入一个数据元素a，已知p指向线性链表的结点y，q指向要插入的新结点，插入的过程如下：

q=(LNode*)malloc(sizeof(LNode))；

q->data=’a’；

q->next=p->next；

p->next=q；

插入前后的线性链表变化如下：

算法2.4

在具有头结点的线性单链表中插入算法。

/*在线性链表的第i个结点之前插入一个结点x*/

int

LinkList_Insert(LNode*head，intx，inti){LNode*q，*p;intj；

if(i<=0)return(0);/*非法*/

/*定位：寻找第i-1个结点*/

for(p=head,j=0;(p!=NULL)&&(j<i-1);j++)

p=p->next;

if(p==NULL)return(0);/*i越界*/

q=(LNODE*)malloc(sizeof(LNODE));

q->data=x；

/*在结点*p之后插入结点*newp*/q->next=p->next；p->next=q；

return(1)}

3.删除结点

在图2.8所示的线性表中，删除y所在的结点，删除的方法是：使指针p指向要删除结点的前驱(y所在的结点)；将p的指针域指向要删除结点的后继结点；将要删除的结点释放。删除过程如下：

q=p->link;p->link=q->link;free(q);

只要修改指针域的指针，就可实现删除操作。删除前后的线性链表变化如图2.10所示。

图2.10算法2.5在具有头结点的线性单链表中删除算法。

/*在线性链表中，删除第i个结点*/

int

LinkList_Delete(LNode*head，inti){LNODE*p,*q；intj；

if(i<=0)return(0);/*非法*/

/*定位：寻找第i-1个结点*/

for(p=head,j=0;(p!=NULL)&&(j<i-1);j++)

p=p->next;

if(p==NULL)return(0);/*i越界*/

/*删除结点*p之后的结点*q*/q=p->next；p->next=q->next；free(q)；

return(1)；

}

(3)应用

例2.1

对给定的两个递增有序线性表a和b进行合并，要求合并后仍然是一个递增有序表，并要求算法的时间复杂度为O(n+m)，n与m分别为线性表的长度，可采用“平移指针，一次扫描”的方法。分析：设两个指针La和Lb分别指向两个线性表开始，对指针所指结点的数据域作比较，并选出较小的一个，将其从原链表中取出插入到新表Lc的表尾，然后该指针后移；重复直到其中一个表结束。最后，将尚未结束表直接链接到新表的尾部。链表带有头结点，算法如下。

算法2.6

将两个递增有序单链表合并成递增单链表的算法

/*依次比较La和Lb中的各个结点，卸下数据元素较小的结点，将其增添为Lc的末结点*/

LNode*LinkList_Merge(LNode*La,LNode*Lb){LNode*pa,*pb,*pc,*Lc;/*pc指向链表Lc中的尾结点*/

Lc=La;/*Lc的头结点是原La的头结点*/pa=La->next;pb=Lb->next;pc=Lc;

while(pa!=NULL&&pb!=NULL)

if(pa->data<=pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next;}

if(pa!=NULL)pc->next=pa;/*若La链表还有剩余结点*/elsepc->next=pb;/*若Lb链表还有剩余结点*/

free(Lb);return(Lc);}例2.2下面是一个求线性链表逆序的算法。通过新建一个链表，依次将原链表中结点卸下，插入到新链表的表首。算法如下:算法2.7

线性链表的逆序。/*建一个新表，依次将原链表的首结点*p卸下，插入到新表的首部*/LNODE*LinkList_Reverse(LNODE*head)

{LNODE*NewHead,*p;/*NewHead为新表表头指针*/

NewHead=(LNODE*)malloc(sizeof(LNODE));

NewHead->next=NULL;

while(head->next!=NULL){p=head->next;head->next=p->next;//卸下

p->next=NewHead->next;NewHead->next=p;}//插入

free(Head);return(NewHead);}例2.3一个有序表合并的示例，有两个递增有序线性表a和b，合并后仍然是一个有序表，但要求递减有序，并要求算法的时间复杂度为O(n+m)，n与m分别为线性表的长度。设两个指针分别指向两个线性表开始，对指针所指结点的数据域作比较，并选出较小的一个，将其从原链表中取出插入到新表的表首，然后该指针后移；重复直到其中一个表结束，再将尚未结束表的元素依次取出插入新表的表首。为减少首指针的变化，采用带有头结点的链表。算法见书上。2.4单向循环链表

1、定义：单向链表中最后一个结点的指针域指向首结点，整个链表形成一个环。如图2.11所示为单向循环链表

2、操作：单向循环链表的操作和线性链表基本一致，差别仅在于算法中的循环结束条件不是p或者p->link是否为NULL，而是它们是否等于首指针。有时在循环链表中设立尾指针而不设立首指针，可以使某些操作简化。(b)空表

(a)链表的逻辑状态例2.3约瑟夫回环问题是一个典型的循环单链表的应用，即：n个数据元素构成一个环，从环中任意位置开始计数，计到k将该元素从表中取出，重复上述过程，直至表中只剩一个元素(猴子选大王问题)。用C语言描述的约瑟夫回环算法如下:算法2.8

解约瑟夫回环问题算法。

struct

ringnode

/*定义一个结构*/{intcode;struct

ringnode*next;};

typedef

struct

ringnode

RingNode;main()/*主函函数*/{RingNode*head=create(20);/*设n=20*/

printf("%d\n",josph(head,7));/*设k=7*/}/*将n个元素构成一个没有头结点的循环链表，首指针是head，计数从首结点开始*/

RingNode*create(intcount)/*创建一个无特殊头结点循环链表*/{RingNode*head,*p,*tail;inti;

for(i=1;i<=count;i++){p=(RingNode*)malloc(sizeof(RingNode));p->code=i;

if(i==1)head=tail=p;else{tail->next=p;tail=p;}}tail->next=head;

return(head);}

int

josph(RingNode*head,intk)/*约瑟夫回环算法*/{inti;RingNode*p,*pre;/*pre是*p的直接前驱*/p=head;

while(head->next!=head){for(i=1;i<k;i++){pre=p;p=p->next;}/*计数*/

/*准备删除*p*/

if(p==head)head=p->next;/*若删除*head，必须让head指向下一个节点*/pre->next=p->next;free(p);p=pre->next;}

return(head->code);/*返回链表中惟一结点的code值*/

}2.5双向循环链表

定义：在双向链表中，每一个结点至少3个域，data为结点的数据域，rlink为右方向指针域，指向结点的直接后续，llink为左方向指针域，指向结点的直接前驱。另外，使表首结点的左方向指针(llink)指向表尾结点，并使表尾结点的右方向指针(rlink)指向表首结点。这时就构成双向循环链表，用C描述：

struct

dlnode

{intdata;

struct

dlnode*llink,*rlink;

};

typedef

struct

dlnode

DuLinkNode;

图2.13所示，为带表头结点的双向循环链表的空表和非空表。

操作：在双向循环链表的操作中，可以十分方便的找到结点的前驱和后继，故在对链表的遍历中只需要一个搜索指针p，无须保存结点的前驱。插入和删除时要修改两个方向的指针，每个方向链表的操作过程与单链表相同。图2.13插入和删除方法

1．插入在p所指的结点之后插入q所指的结点的过程如下：

q->rlink=p->rlink;q->llink=p;

p->rlink=q;(q->rlink)->llink=q;2．删除删除p所指的结点的过程如下：

(p->llink)->rlink=p->rlink;

(p->rlink)->llink=p->llink;

free(p);

由于在双向循环链表中，各结点的位置是等价的，没有特殊的首尾结点，所以上述插入、删除算法对任意位置的结点都是相同的。2.6一元多项式的存储与运算

1.在数学上，一个一元多项式Pn(x)可以记为

Pn(x)=anxn+an-1xn-1+…+a1x+a0它由n+1个系数惟一确定。

2.在计算机里，它可以用一个线性表P来表示为

P=(a0,a1,…,an-1,an)

每一项的指数i隐含在其系数ai的序号里。

3.Qm(x)是一元m次多项式，用线性表Q来表示为

Q=(b0,b1,…,bm-1,bm)设m<n4.Rn(x)=Pn(x)+Qm(x)可用线性表R表示为

R=(a0+b0,a1+b1,…,am+bm,am+1,…,an-1,an)5.另一种表示方法。线性表中每一个结点既存放该项系数，又存放该项指数，而对于系数为零的项不存放。一元多项式可以写成：

P=p1xe1+p2xe2+…+pm-1xem-1+pmxem

其中，pi是指数为ei的项的非零系数，并且满足

0≤e1<e2<…<em-1<em=n

则可用如下所示的线性表：

P=((p1,e1),(p2,e2),…,(pm-1,em-1),(pm,em))

确定惟一的多项式Pn(x)。6.一元多项式的存储结构。为了运算方便，采用线性链表作为多项式的存储结构为例，当用线性链表来表示多项式时，每个结点设三个域，即系数域、指数域、指针域。类型定义用C语言描述如下：

struct

polynode

{int

coef;/*系数域*/

intindex;/*指数域*/

struct

polynode*next;};typedef

struct

polynode

PolyNode;7.两个多项式的加法运算规则是：指数相同的项相加。相加j结果不为零，则构成为“和多项式”中的一项；若和为零，则“和多项式”中没有该项；指数不相同的项复抄到“和多项式”中。多项式的相加操作和有序表的合并基本上相同，也是采用“平移指针，一次扫描”的算法。设两个指针pa和pb分别指向两个多项式链表，比较它们所指结点的指数域：(1)若pa->index<pb->index，则pa结点应是“和多项式”中的一项，并令pa指针后移。(2)若pa->index>pb->index，则*pb结点应是“和多项式”中的一项，将pb结点插入在pa结点之前，pb指针后移。(3)若pa->index==pb->index，则将两个结点的系数域相加，当和不为零时用该值代替原pa结点的系数，释放*pb结点，pb指针后移；反之，当和为零时“和多项式”中没有该项，在两个多项式链表中删除当前的结点，并将它们释放，pa和pb指针后移。这里采用带有头结点的多项式链表，它们的首结点分别是La和Lb，相加算法用C语言描述如下：

8.算法2.9

两个多项式相加算法。/*将Lb为头指针的多项式链表合并到以La为头指针的多项式链表中*/voidpolyadd(PolyNode*La,PolyNode*Lb){PolyNode*pa,*pre_pa;/**pre_pa