数据结构-第二章-线性表

数据结构

第二章线性表

本章教学目标掌握线性表的逻辑结构及相关概念掌握线性表的两种存储结构:顺序表和链表掌握顺序表上各种基本运算的实现过程掌握链表上各种基本运算的实现过程线性结构的特点存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个之外,数据元素集合中的每个元素均只有一个前驱除最后一个之外,数据元素集合中的每个元素均只有一个后继例如:(a1,a2,a3,…,an-1,an)线性表的类型定义线性表:是n个数据元素的有限序列线性表的长度:线性表中元素的个数抽象数据类型线性表的定义

除了以上定义的基本操作外,还可以有更复杂的操作,如:将两个表合并成一个表;将一个表拆成两个表;复制一个线性表ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}基本操作：

InitList(&L)

操作结果：构造一个空的线性表L。

DestroyList(&L)

初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)

初始条件：线性表L已存在。操作结果：将L重置为空表。

ListEmpty(L)

初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。

Listlenght(L)

初始条件：线性表L已存在。操作结果：返回L中数据元素个数。

GetElem(L,i,&e)

初始条件：线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare())

初始条件：线性表L已存在,compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，若这样的数据元素不存在，则返回值为0。

PriorElem(L,cur_e,&pre_e)

初始条件：线性表L已存在。操作结果：若cur_e

是L中的数据元素，且不是第一，则用pre_e返回它的前驱,否则操作失败,pre_e无定义。NextElem(L,cur_e,&next_e)

初始条件：线性表L已存在。操作结果：若cur_e

是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,i,e)

初始条件：线性表L已存在,1≤i≤ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。

ListDelete(&L,i,&e)

初始条件：线性表L已存在且非空,1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。

ListTraverse(L,visit())

初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADTList线性表的表示(存储结构)顺序表示链式表示线性表的顺序表示和实现把线性表中的所有元素,按照其逻辑顺序依次存储到计算机中的从指定存储位置开始的一块连续的存储空间中.是一种紧凑结构Loc(ai+1)=loc(ai)+sizeof(ElemType)顺序表示意图是一种随机存储的结构通常用数组来描述顺序存储结构顺序表示意图

线性表的动态分配顺序存储结构

#defineLIST_INIT_SIZE100#defineLISTINCREMENT10

typedef

struct{

ElemType*elem;//存储空间起始地址

intlength;//当前元素个数

int

listsize;

//当前分配的存储容量(以

sizeof(ElemType)为单位)

}SqList;顺序表基本运算的实现初始化(构造一个空线性表L)StatusInitList_sq(SqList&L){L.elem=((ElemType)*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;

L.listsize=LIST_INIT_SIZE;returnOK;}顺序表基本运算的实现(2)求长度(返回L中数据元素个数)

int

ListLength(SqListL){return(L.length);}顺序表基本运算的实现(3)显示顺序表

Voiddisplay(SqListL){if(L.length==0)

printf(“空表”);elsefor(j=0;j<L.length;j++)

printf(L.elem[j]);}顺序表基本运算的实现(4)取表中第i个元素

ElemType

GetElem(SqListL,inti,

ElemType&e){if(i<0||i>L.length-1)

printf(“i参数不正确“）;elsee=L.elem[i-1];return(e);}顺序表基本运算的实现(5)按值查找e元素的位序，没找到返回0

int

LocateElem(SqListL,ElemTypee){inti=1;while(i<L.length+1&&L.elem[i-1]!=e)i++;if(i=L.length+1)return(0);elsereturn(i);}顺序表基本运算的实现(6)插入操作(在第i个元素前插入一个元素)StatusListInsert_sq(SqList&L,int

i,ElemTypee){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.listsize){//当前存储空间已满,增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);//q为插入位置插入操作(续）For(p=&(L.elem[L.length-1];p>=q;--p)//插入位置及之后的元素右移

*(p+1)=*p;*q=e;//插入e++L.length;returnOK;}时间复杂度：O(n)顺序表基本运算的实现(7)删除操作(删除第i个元素)StatusListDelete_Sq(SqList&L,inti,ElemType&e){if((i<1)||(i>L.length_Sq(L))returnERROR;p=&(L.elem[i-1]);//被删除元素的位置

e=*p;q=L.elem+L.length-1;//表尾元素的位置

for(++p;p<=q;++p)//被删除元素之后的元素左移

*(p-1)=*p;--L.length;returnOK;}时间复杂度：O(n)顺序表基本运算的实现(8)顺序表的合并VoidMergeList_Sq(SqListLa,SqList

Lb,SqList&Lc)//La和Lb均为元素递增顺序表,

将La和Lb合并为递增顺序表Lc{pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));If(!Lc.elem)exit(OVERFLOW);

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

While(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}While(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素While(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素}顺序表的优缺点优点数据元素可以随机存取占用较少存储空间缺点需要一组地址连续的存储单元在插入或删除操作时，需移动大量元素。线性表的链式表示和实现线性链表的结点数据元素ai的存储映像,包括两个域：数据域和指针域n个结点链结成一个链表单链表（线性链表）：只包含一个指针域头结点：单链表的第一个结点之前附设的一个结点最后一个结点的指针为“空”（NULL）数据元素之间的逻辑关系是由结点中的指针指示的。数据域指针域数据域指针域线性表链式存储结构示意图线性表的单链表存储结构

typedef

struct

Lnode{

ElemTypedata;

struct

Lnode*next;}Lnode,*LinkList;headd

^

cba链表的基本运算(1)创建单链表

voidCreateList_L(LinkListL,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);p->next=L->next;//将p插入表头结点L后

L->next=p;}}问题:如果要将新结点插入到链表尾，如何改算法？链表的基本运算(2)求长度（头结点不计在内）

int

ListLength(LinklistL){n=0;p=L->next;while(p!=NULL){n++;p=p->next;}return(n);}链表的基本运算(3)取第i个元素

statusGetElem_L(Linklist

L,int

i,ElemType&e){LinklistP=L->next;

intj=1;while(P&&j<i){P=P->next;++j;}if(!P||j>i)returnERROR;e=P->data;returnOK;}链表的基本运算(4)显示操作

voiddisplay(LinklistL)//显示L的所有元素

{intn=ListLength(L);

LinklistP=L->next;if(n==0)

printf(“空表/n”);elseif(n==1)printf(P->data);else{for(i=1;i<n;i++){printf(P->data);P=P->next;}

printf(P->data);}}链表的基本运算(5)插入结点

StatusListInsert_L(LinkList&L,inti,ElemTypee){//在第i个元素前插入一个元素

p=L;j=0;while(p&&j<i-1){p=p->next;++j}//找第i-1个结点

if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));//生成新结点

s->data=e;s->next=p->next;//插入L中

p->next=s;returnOK;}链表的基本运算(6)删除结点StatusListDelete_L(LinkList&L,int

i,ElemType&e){//删除第i个结点P=L;j=0;While(p->next&&j<i-1){//寻找第i-1个结点

p=p->next;++j;}If(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;//删除结点e=q->data;free(q);ReturnOK;}链表的基本运算(7)有序表合并(表元素按值非递减排列)voidMergeList_L(LinkListLa,LinkListLb,LinkList

Lc){pa=La->next;pb=Lb->next;

Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;

free(Lb);}链表的基本运算(8)有序表求交集(表元素按值非递减排列)voidIntersectionList_L(LinkListLa,LinkListLb,LinkList

Lc){pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data==pb->data){pc=pa;pa=pa->next;}elseif(pa->data<pb->data){pc->next=pa->next;free(pa);pa=pc->next;}elsepb=pb->next;}

有序表求交集(续）

pc->next=NULL;

while(pa){pc=pa;pa=pa->next;free(pc);}

pb=Lb;//从Lb头结点开始

while(pb){pc=pb;pb=pb->next;free(pc);}}链表的基本运算(9)有序表求差集voidSubList_L(LinkListLa,LinkListLb,LinkList

Lc){pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data==pb->data){pc->next=pa->next;free(pa);pa=pc->next;}elseif(pa->data<pb->data){pc=pa;pa=pa->next;}elsepb=pb->next;}有序表求差集（续）pb=Lb;while(pb)//从Lb头结点开始

{pc=pb;pb=pb->next;free(pc);}}线性表的静态链表存储结构

#defineMAXSIZE1000

typedef

struct{ElemTypedata;//数据元素

intcur;//下一个结点在链表中的相对位置（位序）

}Component,SLinkList[MAXSIZE];例：

SlinklistS;s[0]:头结点；

s[0].cur:指示第一个结点在数组中的位置,设i=s[0].cur,则:s[i].data存储线性表的第一个数据元素;k=s[i].cur:s[i]下一个结点的位置动态链表：用指针描述的链表静态链表：用数组描述的链表静态链表操作示例

int

LocateElem_SL(SLinkListS,ElemTypee){//定位操作

i=S[0].cur;while(i&&S[i].data!=e)i=S[i].cur;returni;}其他形式链表循环链表（circularlinkedlist)表中最后一个结点的指针域指向头结点与非循环链表的操作基本相同，只是对表尾的判断作了改变。P->next=h;双向链表（doublelinkedlist)每个结点中有两个指针域，一个指向直接后继，另一个指向直接前驱便于向前查找双向链表的存储结构

typedef

struct

DuLNode{

struct

DuLNode*prior;

struct

DuLNode*next;}DuLNode,*DuLinkList;head双链表的基本操作插入操作算法statusListInsert_DuL(DULinkList&L,inti,ElemTypee)//在第i个元素前插入元素e{if(!(p=GetElemP_Dul(L,i))//p为第i个元素结点

returnERROR;//p=Nullif(!(s=(DuLinkList)malloc(sizeof(DuLnode)))returnERROR;//存储申请失败

s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK}DuLNode

GetElemP_DuL(DuLinkListL,inti){P=L->next;j=1;while(P&&j<i){P=P->next;j++;}if(!P||j>i)returnNULL;returnP;}双链表的基本操作(2)删除操作算法StatusListDelete_DuL(DuLinklist&L,inti,ElemType&e)//e保留要删除的元素

{if(!P=GetElemP_DuL(L,i)))returnERRORe=P->data;P->prior->next=P->next;P->next->prior=P->prior;free(P);returnOK;}链表存储结构小结优点不需要一大块地址连续的存储单元在插入或删除元素时，不需要移动大量元素。采用动态链表不需要固定最大长度。缺点占用较大存储空间不可以随机访问数据元素链表的存储结构不唯一线性表的应用

一元多项式的表示及操作一元多项式的线性表示

(1)

Pn(x)=P0+P1x+P2x2+……+Pnxn

其中：

P0，P1，

P2，……Pn可能为0

线性表P=（P0，P1，

P2，……Pn）

(2)Pn(x)=P1xe1+P2xe2+……+Pmxem

其中：

P1，

P2，

……Pm不为00≤e1<e2<……<em=n

线性表P=((P1,e1),(P2,e2),……(Pm,em))例1：

P(x)=1+2x+7x2+8X3+5x4+10x5

(1)

P=(1,2,7,8,5,10)(2)P=((1,0),(2,1),(7,2),(8,3),(5,4),(10,5))例2：

P(x)=8+3x4+5x10

(1)P=(8,0,0,0,3,0,0,0,0,0,5)(2)P=((8,0),(3,4),(5,10))一元多项式的存储表示顺序表链表注意：链表方式灵活，一般采用链表方式例：P(x)=3+4x3+15x5+9x8P

-130

43

155

98Λ

抽象数据类型一元多项式的定义ADTPolynomial{

数据对象：D={ai|ai

TermSet,i=1,2,…m,m≥0,TermSet为(实数，整数）形式}数据关系：R1={<ai-1,ai>|ai-1,aiD}基本操作：

Createpolyn(&P,m);

PrintPolyn(P);

AddPolyn(&Pa,&Pb);

SubtractPolyn(&Pa,&Pb);

MultiplyPolyn(&Pa,&Pb);}抽象数据类型Polynomial的实现

typedef

struct{floatcoef;

int

expn;}term,ElemType;

typedef

LinkListpolynomial;

//基本操作原型说明

voidCreatPolyn(polynomial&P,intm);voidPrintPolyn(polynomialP);

int

PolynLength(polynomialP);voidAddPolyn(polynomial&Pa,polynomial&Pb);voidSubtractPolyn(polynomial&Pa,polynomial&Pb);voidMultiPolyn(polynomial&Pa,polynomial&Pb);基本操作的算法描述比较两个多项式项

int

cmp(terma,termb){if(a.expn>b.expn)return1;if(a.expn=b.expn)return0;if(a.expn<b.expn)return-1;}基本操作的算法描述(2)创建一个多项式

creatpolyn(Polynomial&P,intm){P=(Polynomial)malloc(sizeof(Lnode))Q=P;(&P->data).coef=0;(&P->data).expn=-1;//建立头结点

for(i=1;i<=m;i++){L=(polynomial)malloc(sizeof(Lnode))

scanf((&L->data).coef);

scanf((&L->data).expn);P->next=L;P=L;}L->next=NULL;P=Q;}

基本操作的算法描述(3)两个多项式相加

voidAddPolyn(polynnomial&Pa,polynnomial&Pb){ha=Pa;hb=Pb;

qa=Pa->next;

qb=Pb->next;while(qa&&qb){a=qa->data;b=qb->data;

switch(*cmp(a,b)){case–1://a.expn<b.expnha=qa;qa=qa->next;//ha始终为qa前驱

break;case0://a.expn=b.expnsum=a.coef+b.coef;if(sum!=0){(&qa->data).coef=sum;ha=qa;qa=qa->next;

FreeNode(qb);qb=NextPos(Pb,hb);}else{//sum=0;

DelFirst(ha,qa);FreeNode(qa);

DelFirst(hb,qb);FreeNode(qb);

qb=NextPos(Pb,hb);

qa=NextPos(pa,ha);}break;

case1://a.expn>b.expn

InsFirst(ha,qb);//在ha后插入qb

DelFirst(hb,qb);

//在Pb中删去已插入Pa中的qb

qb=NextPos(Pb,hb);ha=NextPos(pa,ha);break;}//switch-end}//while-endif(!ListEmpty(Pb))Append(Pa,qb);//Pa链接Pb的剩余结点

freeNode(hb);//释放Pb的头结点（位置始终未变）}补充例题

假设顺序表：

C.elem[]=(a1,a2,…,am,b1,b2,…,bn)

设计算法：将C中元素的两部分互换为：

C1.elem[]=(b1,b2,…,bn,a1,a2,…,am)

算法思路将C中两部分元素互换可以通过元素的逆置来实现。先将C中所有元素逆置，使之成为

C1.elem=(bn,bn-1…,b1,am,…,a2,a1)，然后将(bn,bn-1…,b1)逆置为(b1,b2,…,bn)，将(am,…,a2,a1)逆置为(a1,a2,…,am)，这样便得到最终结果：

C1.elem[]=(b1,b2,…,bn,a1,a2,…,am)。voidchange(SqList&L,intn,intm){reverse(L,0,m+n-1);

rever