数据结构：第2章 线性表

线性表是一种最简单的线性结构第二章线性表

线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。线性结构

是一个数据元素的有序（次序）集2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现

2.3.1线性链表

2.3.2循环链表

2.3.3双向链表2.4一元多项式的表示及相加2.1线性表的类型定义抽象数据类型线性表的定义如下：ADTList{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n

为线性表的表长;

称n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai在线性表中的位序。}

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList

InitList(&L)操作结果：构造一个空的线性表L。初始化操作

结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作:

ListTraverse(L,visit())初始条件：操作结果：线性表L已存在。Visit()为某个访问函数。依次对L中每个元素调用函数标visit()。一旦visit()失败，则操作失败。（遍历线性表）加工型操作

ClearList(&L)PutElem(&L,i,e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

利用上述定义的线性表类型可以实现其它更复杂的操作。

假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。

现要求一个新的集合A＝A∪B。例2-1

要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表

LA中的数据元素插入到线性表LA

中去。上述问题可演绎为：1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)(n表示线性表LA当前长度)操作步骤：

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之La_len=ListLength(La);//求线性表的长度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){若线性表中的数据元素相互之间可以比较，并且数据元素在表中依值非递减或非递增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，则称该为有序表(OrderedList)。有序表则

归并两个“其数据元素按值非递减有序排列”的有序表LA和LB，求得有序表LC也具有同样特性。设

La=(a1,…,ai,…,an),Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)归并得

(c1,…,ck-1)例

2-2k=1,2,…,m+n1．初始化LC为空表；基本操作：2．分别从LA和LB中取得当前元素ai

和bj；3．若ai≤bj，则将ai

插入到LC中，否则将

bj

插入到LC中；4．重复2和3两步，直至LA或LB中元素被取完为止；5．将LA表或LB表中剩余元素复制插入到

LC表中。

//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){//将ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//将bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}voidMergeList(ListLa,ListLb,List&Lc){

//本算法将非递减的有序表La和Lb归并为Lc}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while(i<=La_len){//当La不空时

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//当Lb不空时

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素2.2线性表类型的实现----顺序映象最简单的一种顺序映象方法是：令y的存储位置和x的存储位置相邻。顺序映象——

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址，称作线性表的基地址以“存储位置相邻”表示有序对<ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址顺序映像的C语言描述线性表的静态分配顺序存储结构：#defineLISTSIZE100//存储空间的最大分配量typedefstruct{ElemTypeelem[LISTSIZE];intlength;//当前长度

}Sqlist;

在线性表的静态分配顺序存储结构中，线性表的最多数据元素个数为LISTSIZE，元素数量不能随意增加，这是以数组方式描述线性表的缺点。为了实现线性表最大存储数据元素数可随意变化，可以使用一个动态分配的数组来取代上面的固定长度数组，如下描述。线性表的动态分配顺序存储结构：#defineLIST_INIT_SIZE100//初始分配量#defineLISTINCREMENT10//分配增量typedefstruct{

}SqList;//俗称顺序表ElemType*elem;//存储空间基址int

length;//当前长度int

listsize;//当前分配的存储容量

//(以sizeof(ElemType)为单位)线性表的基本操作在顺序表中的实现InitList(&L)//结构初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//删除元素线性表操作

ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？

(a1,…,ai-1,ai,…,an)改变为a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加(a1,…,ai-1,e,ai,…,an)

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在顺序表L的第i个元素之前插入新的元素e,

//i的合法范围为1≤i≤L.length+1}//ListInsert_Sq

算法时间复杂度为:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;……元素右移if(L.length>=L.listsize)returnOVERFLOW;//当前存储空间已满

if(i<1||i>L.length+1)

returnERROR;

//

插入位置不合法考虑移动元素的平均情况:

假设在第

i个元素之前插入的概率为，

则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：2118307542568721183075例如：ListInsert_Sq(L,5,66)

L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p线性表操作

ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？

(a1,…,ai-1,ai,ai+1,…,an)改变为ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被删除元素之后的元素左移--L.length;//表长减1returnOK;算法时间复杂度为:

O(ListLength(L))p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//删除位置不合法元素左移考虑移动元素的平均情况:

假设删除第

i个元素的概率为

,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)

p2.3线性表类型的实现----链式映象一、单链表二、结点和单链表的C语言描述三、线性表的操作在单链表中的实现四、其它形式的链表

用一组地址任意的存储单元存放线性表中的数据元素。一、单链表以元素(数据元素的映象)

+指针(指示后继元素存储位置)=结点

(表示数据元素或数据元素的映象)以“结点的序列”表示线性表

称作链表

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针头结点

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针空指针线性表为空表时，头结点的指针域为空

typedefstructLNode{ElemTypedata;//数据域

structLnode*next;//指针域

}LNode,*LinkList;

二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针三、单链表操作的实现GetElem(L,i,e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)

//生成含n个数据元素的链表L

线性表的操作

GetElem(L,i,&e)在单链表中的实现:211830754256∧pppj123

因此，查找第i个数据元素的基本操作为：移动指针，比较j和i

单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

令指针p

始终指向线性表中第j

个数据元素

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&j<i){p=p->next;++j;}//

顺指针向后查找，直到p指向第i个元素

//

或p为空if(!p||j>i)

returnERROR;//第i个元素不存在e=p->data;//取得第i个元素returnOK;ai-1

线性表的操作

ListInsert(&L,i,e)

在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>eaiai-1

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L为带头结点的单链表的头指针，本算法

//在链表中第i个结点之前插入新的元素e

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第i-1个结点if(!p||j>i-1)

returnERROR;//

i大于表长或者小于1s=newLNode;

//生成新结点if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-1

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pqStatusListDelete_L(LinkList&L,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i个结点，并令p指向其前趋q=p->next;p->next=q->next;

//删除并释放结点e=q->data;delete(q);returnOK;if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理操作ClearList(&L)在链表中的实现:voidClearList(&L){//将单链表重新置为一个空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListdelete(p);算法时间复杂度：O(ListLength(L))如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤(头插法)：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；ananan-1四、依次类推，直至输入a1为止。voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i){p=newLNode;

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;//插入}尾插法建表

头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

linklistcreater(){charch;linklisthead;lnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(lnode*)malloc(sizeof(lnode));p–>data=ch;if(head=NULL)head=p;elser–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。

如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。其算法如下：linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r;r=head;while((ch=getchar())!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}

上述算法里动态申请新结点空间时未加错误处理，可作下列处理：

p=(listnode*)malloc(sizeof(listnode));if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上算法的时间复杂度均为O(n)。

最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an1.循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。四、其它形式的链表

在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next)—>next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。例、在设尾指针的单循环链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。

linklistconnect(linklistA，linklistB){linklistp=A—>next;A—>next=(B—>next)—>next;free(B—>next);B—>next=p;A=B;return(A);}2.双向链表typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}

DuLNode,*DuLinkList;双向循环链表空表非空表a1a2…...an双向链表的操作特点：“查询”和单链表相同“插入”和“删除”时需要同时修改两个方向上的指针。ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入ai-1删除aiai+1p->next=p->next->next;p->next->prior=p;pai-12.4一元多项式的表示在计算机中，可以用一个线性表来表示:P=(p0,p1,…，pn)一元多项式但是对于形如S(x)=1+3x10000–2x20000的多项式，上述表示方法是否合适？

一般情况下的一元稀疏多项式可写成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指数为ei

的项的非零系数，

0≤e1<e2<┄<em=n可以下列线性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）

P999(x)=7x3-2x12-8x999例如:可用线性表

((7,3),(-2,12),(-8,999))表示ADTPolynomial{

数据对象：

数据关系：抽象数据类型一元多项式的定义如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数

}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n

且ai-1中的指数值＜ai中的指数值

}

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)

基本操作：操作结果：输入

m项的系数和指数，建立一元多项式

P。初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。

PolynLength(P)

AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)