数据结构线性表

数据结构-一线性表

线性表

代码主要参考严蔚敏《数据结构(C语言版)》，有部分改动

线性表的定义

定义

•线性表是具有相同的数据类型的n(n>=0)个数据元素的有限序列，当n=0忖线性表为一个

空表

•用L表示线性表则L=(a1,a2,a3,...,an

oa1为表头元素，an为表尾元素

oa1无直接前驱，an无直接后继

•表中元素个数有限

•表中元素具有逻辑上的顺序，表中元素有先后次序

•表中元素都是数据元素

•表中元素的数据类型都相同，每个元素占的空间大小一致

要点

数据项、数据元素、线性表的关系

线性表由若干个数据元素组成，而数据元素又由若干个数据项组成，数据项是数据的不可分割的最小

单位。

IIII|y四||y|

姓名年一

a三100120

tw111021ctn机i9i

其中姓名，学号等就是数据项

线性表的顺序表示

顺序表的定义

顺序表是指用•组地址连续的存储单元依次存储信息衣中的数据元素，从而使得逻辑相邻的两个元素

在物理位置上也相邻

预先定义（为了代码可以运行）

#defineTrue1

#defineFalse0

#defineOK1

#detmebRKOK0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;

第n个元素的内存地址表示为

LOC(A)+(n-1)*sizeof(ElemType)

假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为

typedefintElemType;#defineMaxSize50typedefstruct{

ElemTypedata[MaxSize];

intlength;}SqList;

一维数组可以是静态分配的，也可以是动态分配的。静态分配后大小和空间都固定了，下面使用动态

分配的形式

typedefintElemType;#defineInitSize100〃黄长度/"必'才〃'沅J^#defineListlncreasement10岷咨天仃福守间

的分配增/typedefstruct{

ElemType'data;

intMaxSize.length;}SeqList;

顺序表的初始化

顺序表的初始化,&是C++的引用，可以使用指针代替

StatuslnitList(SeqList&L){

L.data=(ElemType,)malloc(lnitSize*sizeof(ElemType));

if(!L.data)exit(OVERFLOW);〃存储分配失败

L.length=0;

L.MaxSize=InitSize;

returnOK;

)

顺序表的插入

在顺序表L的第i(1<=i<=L.length+1)个位置插入新元素e,需要将第n个至第i(共n-i+1)个元素

向后移动一个位置【最后一个到倒数第n-i+i个元素向后移动一位】。

StatusListlnsert(SeqList&L,inti.ElemTypee){

ElemType*newbase;

if(i<1||i>L.length+1)〃•割断，虚否合去

returnERROR;

iffL.length>=L.MaxSize)(〃当葡存俺空间已满,可直接返回false

newbase=(ElemType*)realloc(L.data,(L.MaxSize+Listlncreasement)*sizeof(ElemType));

if('newbase){〃存破勿密先败

exit(OVERFLOW);

}

L.data二newbase.〃新*址

L.MaxSize+=Listlncreasement;

)

〃移动元素

for(intj=L.length;j>=i;j-){

L.datafj]=L.dataQ-1];

)

L.data[i-1]=e;Z6

L」ength++”的长度

returnOK;}

最好情况：在表尾插入，时间复杂度为0(1)

最坏情况：在表头插入，时间复杂度为0(n)

平均情况：假设Pi(Pi=1/(n+1))是在第i个位置上插入•个节点的概率，则平均移动次数为

Xi=ln+lpi(n-i+l)=£i=ln4-lln4-l(n-i+l)=ln+ln(n4-l)2=n2

\sum_{i=l}A{n+l}p_i(n-i+1)=\sum_{i=1}A{n+l}\frac{1}{n+l}(n-i+l)=\frac{1}{n+l}\frac{n(n+l)}{2}=\fr

ac{n}{2}i=lZn+lpi(n-i+l)=i=lZn+!n+1l(n-i+l)=n+l12n(n+l)=2n

顺序表的删除

删除顺序表L的第i(1viv=L」ength)个位置的元素，需要将第i+1个至第n(共n-1)个元素依次向前移

动一个位置。

断除施三付

StatusListDelete(SeqList&L,inti.ElemType&e){

if(i<1||i>L.length)returnERROR;〃判断删除位置是否合法

e=L.data[i-1];

〃依次前移，把第i个元素覆盖，相当于是删除

for(intj=i；j<L.length;j++){

L.data[j-1]=L.data[j];

}

Uength--;〃长度减一

returnOK;

最好情况：在表尾删除，时间复杂度为0(1)

最坏情况：在表头删除，时间复杂度为。(n)

平均情况：假设Pi(Pi=1/(n))是删除在第i个位置上•个节点的概率，则平均移动次数为

£i=ln+lpi(n-l)=Xi=ln+lln(n-i)=lnn(n-l)2=n-12

\sum_{i=1}A{n+1}p_i(n-1)=\sum_(i=1)A{n+l}\frac{1}{n}(n-i)=\frac{1}{n}\frac{n(n-l)J{2}=\frac{n-l}{2

}i=IZn+1pi(nT尸1=iZn+lnl(n-i)=n12n(n-l)=2n-l

按值至找

查找第•个与e相等的元素，并返回其位序。

intLocateElem(SeqList&L,Elem-ypee){

for(inti=0;i<L.length;i++i{

if(L.datafi]==e){

return下标为i的元素公则位序为i+1

}

}

returnERROR；/3'找久我}

平均情况：

£i=In+Ipixi=j=]n+11nxi=1nn(n+1)2=n+12\sum_{i=l}A{n+l}p_i\times

i=\sum_{i=l}A{n+l}\frac{1}{n)\timesi=\frac{I}{n}\frac{n(n+1)|{2}=\frac{n+1}{2}i=lZn+lpi

xi=i=lZn+1n1xi=n12n(n+1)=2n+1

顺序表例题

1、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除的元素的值，空出的位由最后

一个元素来填补，若顺序表为空则显示出错误并退出运行。

boolListMinElem(SeqList&L,ElerType&e){

if(L.length<1){

returnfalse;

)

intpos;

e=L.data[O];

for(inti=0;i<L.length;i++){

if(L.data[i]<e){

e=L.data[i];

pos=i;

}

)

L.datafpos]=L.data[L.length-1];〃用最后一个元素的值填充最小元素的位*

LJength-;〃长度减一相当于鬻除了最后一个元素

returntrue;}

2、设计一个高效算法，将顺序表L的所有元素逆置，要求算:法的空间复杂度为0(1)

voidListReverse(SeqList&L){

ElemTypetemp;

for(inti=0;i<L.length12;i+*){

temp=L.datafi];〃禄)蜀面的元京

L.data[i]=L.data[L.length•1T"

L.data[L.length-1-i]=temp;

))

3、对长度为n的顺序表L,编写一•个时间复杂度为0(n),空间复杂度为0(1)的算法，该算法删除

线性表中所有值为X的元素,

voidListDeleteX(SeqList&L.ElemTypex){

intk=0记录L不等于x的元素的个数

for(inti=0;i<L.length;i++){

if(L.data[i]!=x){

L.data[k]-L.data[lJ:^W-

K+*〃长度增加

L.length=k、〃将最后的不等于x的个数JK值给L.lengt埒

线性表的链式表示

链表的定义

用一组任意的存储单元存储线性表的数据元素（地址不连续），因为地址不连续，所以链表的数据结

构中需要存放下一个节点的地址，所以通常一个结点有两个部分（数据域和指针域）

链表的数据结构

数据域指针域

一般形式

般而耍个头结点来访问整个链表，头结点的数据域般不存数据。

typedefstructLNode{

ElemTypedata;

structLNodevnext;}LNode;

链表的初始化

StatuslnitLinkList(LinkList&L){

L(LinkList)malloc(sizeof(LNode));

if(!L)exit(OVERFLOW);

returnOK;}

链表的插入

插入时先将要插入的节点P的指针域赋值为上一个节点S的指针域,

P->next=S->next;

S->next=P;

插入

)

if(!P||j>i-1)return田KR;〃!P是判断是否超出表的长度,

LinkListS=(LinkList)malloc(s泛eof(LNode));

if(!S)exit(OVERFLOW);

S->data=e;

S->next=P->next;

P->next=S;

returnOK;}

链表的删除

同插入一样，先找到第i-1个元素位置.，然后用一个变量S保存要删除的节点，再将P的next指向

P的next的next；然后用free(S)释放掉删除元素的空间

HI除

P.

••痴ta;

StatusListDelete_L(LinkList&L,inti.ElemType&e){

〃魏除第i个位遭的元素

LinkListp=L,q;

intj=0;

while(p->next&&j<\X){〃p~>next指向第一个元素,j处于第0个元素的位*,为了找到第/

p=p->next:

j++；

)

if(!(p->next)||j>i-1)returnERROR;/■邂''欧劭看不■合厚

q=p->next;

p->next=q->next;

e=q->data;

free(q);

returnOK;}

头插法建立单链表

voidCreateList_L(LinkList&L,intn){

是个数

L=(LinkList)malloc(sizeof(LNode));

if(!L)exit(OVERFLOW);

L->next=NULL;

for(inti=n;i>0;i-){

LinkListp=(LinkList)m4loc(sizeof(LNode));〃窗笆济与、

if(!p)exit(OVERFLOW);

scanf("%d",&p->data);砥取公

p->next=L->next;

L->next=p;〃新结点插入到表头

})

尾插法

StatusListlnsertTail_L(LinkList&_,ElemTypee){

LinkListp=L;

while(p->next!=NULL)p=p->next;，忸到菱后一

LinkListnewNode=(LinkList)malloc(sizeof(LNode));

if(!newNode)exit(OVERFLOW);

newNode->data=e;

newNode->next=NULL;

p->next=newNode;〃插入到最后

returnOK;}

链表的合并

了解

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){

"己知隼鞋表La,Lb的元素按值非递减排列

〃归并La,Lb得到Lc也按值非递减排列

LinkListpa.pb.pc;

pa=La->next;

pb=Lb->next;

Lc=pc=La;

while(pa&&pb){

if(pa->data<=pb->datai{

pc->next=pa;pc=pa;pa=pa->next;

}else{

pc->next=pb;pc=pb;pb=pb>next;

)

pc->next=pa?pa：插入剩下的片段

}

free(Lb);}

双向链表

在单链表的基础上增加了一个指向前一个W点的指针域。

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;}DuLNode,*DuLinkList;

双向链表应用-约瑟夫算法

/include<iostream>usingnamespacestd;constintN=20;typedefstructnode{

intid;

structnode'next;

structnode-preJNode,rpNode;

〃创建一个约瑟夫环并获取到他的头结点。

pNodeRingConstruct(intn){

pNodehead,p,q;〃head为头登i点

head=(pNode)malbc(sizeof(Node));雁建第一个好点

head->id=1;//ID%1

p=head;

for(inti=2;i<=n;i++){〃创建n-1个结点,

q=(phode)malloc(sizeof(Node));

q->id=i;

p->next=q;

q->pre=p;

p=p->next;

)

p->next=最后一个结点的next域连接到头结点

head->pre=p;〃头结点的pre域连接A展结点

returnhead;}

〃传入报数的次数序号，返回此次报送的上限,简单来说就是报几次数。相当于每个人手里拿了一个号码牌

bounMachine(intorder){

intboundList[4]={3,5,7,13};

returnboundList((order-1