版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1線性表是一種最簡單的線性結(jié)構(gòu)第二章線性表2.1 線性表及其基本運算2.2 線性表的順序存儲結(jié)構(gòu)2.3 線性表的鏈式存儲結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、物理結(jié)構(gòu),以及它們之間的相互關(guān)系;定義與之相適應(yīng)的運算;設(shè)計相應(yīng)的算法;分析算法的效率。32.1線性表的邏輯結(jié)構(gòu)2.3線性表類型的實現(xiàn)
鏈式映象2.4一元多項式的表示2.2線性表類型的實現(xiàn)
順序映象42.1線性表及其基本運算
一、線性表(linear_list)線性表是n個數(shù)據(jù)元素的有限序列,記為:
L=(a1,a2,…,an)
數(shù)據(jù)元素之間的關(guān)系是:
ai-1領(lǐng)先于ai,ai領(lǐng)先于ai+1。稱ai-1是ai的直接前驅(qū)元素;ai+1是ai的直接后繼元素。除a1外,每個元素有且僅有一個直接前驅(qū)元素,除an外,每個元素有且僅有一個直接后繼元素。線性表中數(shù)據(jù)元素的個數(shù)n(n>=0)稱為線性表的長度,當n=0時,稱為空表。6(a1,a2,…ai-1,ai,ai+1
,…,an)數(shù)據(jù)元素線性起點ai的直接前趨ai的直接后繼下標,是元素的序號,表示元素在表中的位置n為元素總個數(shù),即表長線性終點7【例1】26個英文字母組成的字母表
(A,B,C、…、Z)【例2】某校從2000年到2005年各種型號的計算機擁有量的變化情況()。
(150,236,321,400,500,600)數(shù)據(jù)元素ai(1≤i≤n)只是個抽象符號,其具體含義在不同情況下可以不同。8【例3】學(xué)生健康情況登記表。姓名學(xué)號性別年齡
健康情況王小林790631
男18
健康陳紅790632
女20
一般劉建平790633
男21
健康張立立790634
男17
神經(jīng)衰弱……..……..…….…….…….92.線性表邏輯結(jié)構(gòu)特征(非空有限集)(1)集合中必存在唯一的一個“第一元素”;(2)集合中必存在唯一的一個“最后元素”(3)除最后元素在外,均有唯一的后繼;(4)除第一元素之外,均有唯一的前驅(qū)。線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序(次序)集103.抽象數(shù)據(jù)類型線性表的定義ADTList{
數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n
為線性表的表長;
稱n=0
時的線性表為空表。}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1,a2,...,ai,...,an),
稱i為ai在線性表中的位序。}11
基本操作:
結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作
引用型操作
加工型操作
}ADTList12
InitList(&L)操作結(jié)果:構(gòu)造一個空的線性表L。初始化操作13
結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件:線性表L已存在。銷毀線性表L。操作結(jié)果:14ListEmpty(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())引用型操作15加工型操作
ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)
INITIATE(L)
初始化操作 設(shè)定一個空的線性表LLENGTH(L)
求長度函數(shù)值為L中數(shù)據(jù)元素的個數(shù)GET(L,i)
取元素函數(shù)1<=i<=LENGTH(L)時返回L中第i個數(shù)據(jù)元素,否則為空元素NULL。i稱為該數(shù)據(jù)元素在L中的位序PRIOR(L,elm)
求前驅(qū)函數(shù)
elm為L中的一個數(shù)據(jù)元素,若它的位序大于1,則函數(shù)值為elm前驅(qū),否則為NULLNEXT(L,elm)
求后繼函數(shù) 若elm的位序小于表長,則函數(shù)值為elm的后繼,否則為NULLLOCATE(L,x)
定位函數(shù)給定值x,若x不在表中,則返回0,否則,返回x在表中第一次出現(xiàn)時的位序INSERTE(L,i,b)前插操作在第i個元素之前插入新元素b,i的取值范圍為:1<=i<=n+1;i=n+1表示在表尾插入,n為表長DELETE(L,i)
刪除操作刪除線性表L中的第i個元素,1<=i<=nEMPTY(L)
判空表函數(shù) 若L為空表,則返回布爾值“true”,否則返回布爾值“false”CLEAR(L)
表置空操作 將L置為空表183.組合基本運算,實現(xiàn)復(fù)雜運算
例
2-2(構(gòu)造A)例
2-3(歸并A.B)例
2-1(A=A∪B)19
假設(shè):有兩個集合A和B分別用兩個線性表LA和LB表示,即:線性表中的數(shù)據(jù)元素即為集合中的成員。現(xiàn)要求一個新的集合A=A∪B?!纠?-1】
20
要求對線性表作如下操作:擴大線性表LA,將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。上述問題可演繹為:211.從線性表LB中依次察看每個數(shù)據(jù)元素;2.依值在線性表LA中進行查訪;3.若不存在,則插入之。GetElem(LB,i)→e
LocateElem(LA,e,equal())
ListInsert(LA,n+1,e)操作步驟:22
GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()))
ListInsert(La,++La_len,e);
//La中不存在和e相同的數(shù)據(jù)元素,則插入之voidunion(List&La,ListLb){La_len=ListLength(La);//求線性表的長度
Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}}//union23
已知一個非純集合B,試構(gòu)造一個純集合A,使A中只包含B中所有值各不相同的數(shù)據(jù)元素。仍選用線性表表示集合【例
2-2】24集合B集合A從集合B
取出物件放入集合A要求集合A中同樣物件不能有兩件以上因此,算法的策略應(yīng)該和例2-1相同25voidpurge(List&La,ListLb){
La_len=ListLength(La);Lb_len=ListLength(Lb);}//purge
GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()))
ListInsert(La,++La_len,e);
//La中不存在和e相同的數(shù)據(jù)元素,則插入之for(i=1;i<=Lb_len;i++){}InitList(La);//構(gòu)造(空的)線性表LA26若線性表中的數(shù)據(jù)元素相互之間可以比較,并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列,即ai≥ai-1
或ai≤ai-1(i=2,3,…,n),則稱該線性表為有序表(OrderedList)。試改變結(jié)構(gòu),以有序表表示集合。27例如:(2,3,3,5,6,6,6,8,12)對集合B而言,
值相同的數(shù)據(jù)元素必定相鄰對集合A而言,
數(shù)據(jù)元素依值從小至大的順序插入因此,數(shù)據(jù)結(jié)構(gòu)改變了,解決問題的策略也相應(yīng)要改變。28voidpurge_order(List&La,ListLb)
{InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度
for(i=1;i<=Lb_len;i++){
}}//purge_order
GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給eif(ListEmpty(La)||!equal(en,e))
{
ListInsert(La,++La_len,e);en=e;}
//La中不存在和e相同的數(shù)據(jù)元素,則插入之29則
歸并兩個“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB,求得有序表LC也具有同樣特性。設(shè)
La=(a1,…,ai,…,an)
Lb=(b1,…,bj,…,bm)
Lc=(c1,…,ck,…,cm+n)【例
2-3】k=1,2,…,m+n301.初始化LC為空表;基本操作:2.分別從LA和LB中取得當前元素ai
和bj;3.若ai≤bj,則將ai
插入到LC中,否則將
bj插入到LC中;4.重復(fù)2和3兩步,直至LA或LB中元素被取完為止;5.將LA表或LB表中剩余元素復(fù)制插入到
LC表中。31
//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;}32voidMergeList(ListLa,ListLb,List&Lc){
InitList(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);}//merge_listwhile((i<=La_len)&&(j<=Lb_len))
{//La和Lb均不空}while(i<=La_len)
//若La不空while(j<=Lb_len)//若Lb不空33
while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
}
//插入La表中剩余元素
while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
}
//插入Lb表中剩余元素342.2線性表的順序表示和實現(xiàn)351.定義:用一組地址連續(xù)的存儲單元
依次存放線性表中的數(shù)據(jù)元素。
a1a2
…ai-1ai
…an線性表的起始地址,稱作線性表的基地址2.2.1線性表的順序存儲結(jié)構(gòu)362.實現(xiàn):可用C/C++的一維數(shù)組實現(xiàn)a1a2an01n-112n內(nèi)存單元數(shù)組下標元素序號m-1373.結(jié)點ai
的存儲地址
以“存儲位置相鄰”表示有序?qū)?lt;ai-1,ai>
即:LOC(ai)=LOC(ai-1)+C
一個數(shù)據(jù)元素所占存儲量↑所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置。
LOC(ai)=LOC(a1)+(i-1)×C
↑基地址38【例1】一個大小為10的一維數(shù)組A,每個數(shù)組元素用相鄰的8個字節(jié)存儲。假設(shè)存儲數(shù)組元素A[0]的第一個字節(jié)的地址是1020,則A[6]的第一個字節(jié)的地址是
1068LOC(a6)=LOC(a1)+8*(6-0)=1020+8×(6-0)=1068解:地址計算通式為:LOC(ai)=LOC(a1)+L*(i-1)39#defineMAXNUM
<順序表最大元素個數(shù)>typedefstruct{
}Sqlist;4.順序存儲結(jié)構(gòu)(1)靜態(tài)分配的順序存儲結(jié)構(gòu)Elemtypeelem[MAXNUM];intlength;40靜態(tài)順序表:lengthelem[MAXNUM]3265896例如:MAXNUM=1241(2)動態(tài)分配的順序存儲結(jié)構(gòu)※typedefstruct{
}SqList;//俗稱順序表const
intLIST_INIT_SIZE=80;//線性表存儲空間的初始分配量ElemType*elem;//存儲空間基址int
listsize;//當前分配的存儲容量intlength;
//當前長度42動態(tài)順序表*elemlengthlistsize例如:742000H2000H472000H3578432.2.2順序表的基本操作InitList(&L)//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i,&e)//刪除元素//(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))//free(T)StatusListCreate_Sq(SqList&L,intn)44預(yù)定義常量和類型://函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;45StatusInitList_Sq(SqList&L){//構(gòu)造一個空的線性表
}//InitList_Sq算法時間復(fù)雜度:O(1)L.elem=new
ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;1.初始化動態(tài)分配內(nèi)存設(shè)置順序表的大小46例如:在順序表中查找元素23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p2.查找元素47
int
LocateElem_Sq(SqListL,ElemTypee){
//
在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素,
//若存在,則返回它的位序,否則返回0}//LocateElem_Sq
O(ListLength(L))算法的時間復(fù)雜度為:i=1;
//i的初值為第1元素的位序p=L.elem;
//p的初值為第1元素的存儲位置while(i<=L.length&&(*p++!=e))++i;if(i<=L.length)returni;elsereturn0;48線性表操作
ListInsert(&L,i,e)的實現(xiàn):首先分析:插入元素時,線性表的邏輯結(jié)構(gòu)發(fā)生什么變化?3.插入元素49
(a1,…,ai-1,ai,…,an)改變?yōu)?/p>
(a1,…,ai-1,e,ai,…,an)a1a2
…ai-1ai
…ana1a2
…ai-1
…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加1502118307542568721183075例如: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*q=e;實現(xiàn)步驟:移動元素插入元素51L.length>=L.listsize//當前存儲空間已滿,不能插入i<1||i>L.length+1//
插入位置不合法
事先應(yīng)判斷:插入位置i是否合法?表是否已滿?注意:52算法思想:1、進行合法性檢查:
1<=i<=L.length+12、檢查線性表是否已滿
3、將第n個至第i個元素逐一后移一個單元4、在第i個位置處插入新元素5、將表的長度加1.53
StatusListInsert_Sq(SqList&L,inti,ElemTypee){
//
在順序表L的第i個元素之前插入新的元素e,}//ListInsert_Sq
算法時間復(fù)雜度為: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(i<1||i>L.length+1)returnERROR;元素右移if(L.length>=L.listsize
)returnOVERFLOW;54考慮移動元素的平均情況:
假設(shè)在第
i個元素之前插入的概率為,
則在長度為n的線性表中插入一個元素所需移動元素次數(shù)的期望值為:
若假定在線性表中任何一個位置上進行插入的概率都是相等的,則移動元素的期望值為:55線性表操作
ListDelete(&L,i,&e)的實現(xiàn):首先分析:刪除元素時,線性表的邏輯結(jié)構(gòu)發(fā)生什么變化?4.刪除元素56
(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>
(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少1a1a2
…ai-1ai
ai+1
…ana1a2
…ai-1
572118307542568721183075L.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)p實現(xiàn)步驟:移動元素58(L.length=0)//當前存儲空間為空,不能刪除(i<1)||(i>L.length)//
刪除位置不合法
事先應(yīng)判斷:刪除位置i是否合法?表是否為空?注意:59算法思想:1、進行合法性檢查:
1<=i<=L.length2、檢查線性表是否為空
3、將第i+1個至第n個元素逐一前移一個單元4、將表的長度減1.60StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;//
刪除元素--L.length;//表長減1returnOK;算法時間復(fù)雜度為:
O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;元素左移if(L.length==0)returnERROR;61考慮移動元素的平均情況:
假設(shè)刪除第
i個元素的概率為
,則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為:若假定在線性表中任何一個位置上進行刪除的概率都是相等的,則移動元素的期望值為:62typedefintElemType;
StatusListCreate_Sq(SqList&L,intn){//創(chuàng)建順序表}//ListCreate_SqreturnOK;for(inti=1;i<=n;++i){ cin>>x; L.elem[i-1]=x; ++L.length; }5.創(chuàng)建順序表632.2.3利用上述定義的順序結(jié)構(gòu)可以實現(xiàn)其它更復(fù)雜的操作例
2-5(逆置順序表)例
2-6(調(diào)整順序)例
2-4(歸并A、B)64則
歸并兩個“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB,求得有序表LC也具有同樣特性。(用順序表實現(xiàn))設(shè)
La=(a1,…,ai,…,an)
Lb=(b1,…,bj,…,bm)
Lc=(c1,…,ck,…,cm+n)【例
2-4】k=1,2,…,m+n65LA=(1,3,4,9,10)LB=(2,5,6,7,8)LC=(1,2,3,4,5,6,7,8,9,10)Legth=5
Legth=5
Legth=10例如:6613942567PaPa_lastPb_lastPbLaLb8LcPc1234567810910算法思路ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pa_last=La->elem+La->length-1;pb=Lb->elem;pb_last=Lb->elem+Lb->length-1;Lc->listsize=Lc->length=La->length+Lb->length;if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;pa<=pa_last&&pb<=pb_last
第二步歸并(將剩余元素插入到Lc末尾)第一步歸并結(jié)束第二步歸并結(jié)束67
while((i<LA.length)&&(j<LB.length)) if(LA.elem[i]<=LB.elem[j]){
LC.elem[k]=LA.elem[i]; i++;k++; } else{
LC.elem[k]=LB.elem[j]; j++;k++;}
voidMerge_sq(SqList&LC,SqListLA,SqListLB){
i=0,j=0,k=0;
LC.length=LA.length+LB.length;68
while(j<LB.length){ LC.elem[k]=LB.elem[j]; j++;k++;
}
while(i<LA.length){ LC.elem[k]=LA.elem[i]; i++;k++;
}
}//Merge_sq69設(shè)有一個順序表A,包含n個數(shù)據(jù)元素。編寫一個算法,將順序表A逆置,只允許在原表的存儲空間外再增加一個附加的工作單元。【例2-5】70LA=(21,62,8,9,11,25,20)
LA=(20,25,11,9,8,62,21)逆置后:
i逆置前:
j附加單元tempLA=(20,62,8,9,11,25,21)
temp=LA(i);LA(i)=LA(j);LA(j)=temp
i
j71
temp=L.elem[i];L.elem[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;
for(i=0;i<m;++i){}voidinvert_sq(SqList&L)
{
n=L.length;i=0,m=n/2;}//invert_sq72設(shè)有一個順序表A,包含n個數(shù)據(jù)元素。調(diào)整順序表A,使其左邊的所有元素均小于0,使其右邊的所有元素均大于0?!纠?-6】73LA=(-62,-8,-25,20,9,8,21)調(diào)整前:LA=(21,-62,8,9,-8,-25,20)
iLB=()xy調(diào)整后:LB=(21)yxLA=(21,-62,8,9,-8,-25,20)
iLB=(-6221)yxLA=(21,-62,8,9,-8,-25,20)
i與0比較74
if(LA.elem[i]<0){ LB.elem[x]=LA.elem[i];x++;}//前置
else{LB.elem[y]=LA.elem[i]; y--; }for(i=0;i<n;i++)voidadjust_sq(SqList&LA)
{
InitList_Sq(LB);
n=LA.length;x=0;y=n-1;}//adjust_sqfor(i=0;i<n;++i)LA.elem[i]=LB.elem[i];DestroyList(LB);75優(yōu)點:邏輯相鄰,物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點:插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配,利用不充分表容量難以擴充順序存儲結(jié)構(gòu)的優(yōu)缺點762.3.1單鏈表2.3.2單向循環(huán)鏈表2.3.3雙鏈表2.3.4雙向循環(huán)鏈表2.3線性表的鏈式存儲結(jié)構(gòu)771.概述用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。2.3.1單鏈表以元素(數(shù)據(jù)元素的映象)
+指針(指示后繼元素存儲位置)=結(jié)點數(shù)據(jù)域指針域結(jié)點結(jié)構(gòu)數(shù)據(jù)域:元素本身信息指針域:指示直接后繼的存儲位置78ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針79
以線性表中第一個數(shù)據(jù)元素
的存儲地址作為線性表的地址,稱作線性表的頭指針。頭結(jié)點
a1a2…...an^頭指針頭指針
有時為了操作方便,在第一個結(jié)點之前虛加一個“頭結(jié)點”,以指向頭結(jié)點的指針為鏈表的頭指針??罩羔樢浴敖Y(jié)點的序列”表示線性表
稱作鏈表h空表^單鏈表的一般圖示法80上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式:①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別:①無頭結(jié)點②有頭結(jié)點81
typedefstructLNode{ElemTypedata;//數(shù)據(jù)域
structLnode*next;//指針域
}LNode,*LinkList;
2.結(jié)點和單鏈表的C語言描述LinkListL;//L為單鏈表的頭指針數(shù)據(jù)域指針域結(jié)點結(jié)構(gòu)823.單鏈表的運算GetElem(L,i,e)//取第i個數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)
//生成含n個數(shù)據(jù)元素的鏈表83(1)單鏈表元素的讀取GetElem(L,i,&e)L1p5^j=1假設(shè)i=2j<ij=j+1=2j=i找到?。?!84L1p5^j=1j<ij=j+1=2j<i假設(shè)i=4j=j+1=3j<i=∧沒找到?。?!非法位置85L1p5^j=1j>i假設(shè)i=0沒找到?。?!非法位置86
StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點的鏈表的頭指針,以e返回第i個元素}//GetElem_L算法時間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個結(jié)點,j為計數(shù)器while(p&&j<i){p=p->next;++j;}//
順指針向后查找,直到p指向第i個元素
//
或p為空if(!p||j>i)
returnERROR;//第i個元素不存在e=p->data;//取得第i個元素returnOK;循環(huán)條件分析:
p=L->next;j=1;while(p&&j<i){p=p->next;++j;}兩個條件有6種組合:1.P=NULLANDj<i空表且i>1或i>表長+1,異常,返回NULL2.P=NULLANDj=i空表且i=1或i=表長+1,異常,返回NULL3.P=NULLANDj>i空表且i<1,異常,返回NULL4.P!=NULLANDj<i繼續(xù)循環(huán)5.P!=NULLANDj=i確定第i個結(jié)點,正常出循環(huán)6.P!=NULLANDj>ii<1,異常,返回NULL88
(2)插入操作
ListInsert(&L,i,e)xsbapabps->next=p->next;p->next=s;插入前插入后89
因此,在單鏈表中第i個結(jié)點之前進行插入的基本操作為:
找到線性表中第i-1個結(jié)點(定位),然后修改其指向后繼的指針。算法思路:在鏈表中插入結(jié)點只需要修改指針。但同時,若要在第i個結(jié)點之前插入元素,修改的是第i-1個結(jié)點的指針。90StatusListInsert_L(LinkList&L,inti,ElemTypee){
//L為帶頭結(jié)點的單鏈表的頭指針,
//在鏈表中第i個結(jié)點之前插入新的元素e
}//LinstInsert_L算法的時間復(fù)雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)
{p=p->next;++j;}
//
尋找第i-1個結(jié)點if(!p||j>i-1)
returnERROR;//
i大于表長或者小于191s=new
LNode;
//生成新結(jié)點s->data=e;s->next=p->next;p->next=s;//插入returnOK;92(3)刪除操作ListDelete(&L,i,&e)cabpq=p->next;qp->next=q->next;deleteq;93
在單鏈表中刪除第
i個結(jié)點的基本操作為:找到線性表中第i-1個結(jié)點,修改其指向后繼的指針。算法思路:94StatusListDelete_L(LinkList&L,inti,ElemType&e){
//刪除以L為頭指針(帶頭結(jié)點)的單鏈表中第i個結(jié)點
}//ListDelete_L算法的時間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}
//尋找第i個結(jié)點,并令p指向其前趨if(!(p->next)||j>i-1)
returnERROR;//刪除位置不合理q=p->next;p->next=q->next;
//刪除并釋放結(jié)點e=q->data;deleteq;returnOK;95(4)清空操作ClearList(&L)voidClearList(&L){//將單鏈表重新置為一個空表
while(L->next){
p=L->next;L->next=p->next;
}}//ClearListDeletep;算法時間復(fù)雜度:O(ListLength(L))96(5)如何從線性表得到單鏈表?鏈表是一個動態(tài)的結(jié)構(gòu),它不需要預(yù)分配空間,因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。97頭插法思路:^Ldatanextpdatanextpp->next=L->nextL->next=p(1)建立一個“空表”;(2)輸入數(shù)據(jù)元素an,建立結(jié)點并插入;(3)輸入數(shù)據(jù)元素an-1,建立結(jié)點并插入;(4)依次類推,直至輸入a1為止。逆位序輸入該方法生成鏈表的結(jié)點次序與輸入順序相反。98voidCreateList_L(LinkList&L,intn){//逆序輸入n個數(shù)據(jù)元素,建立帶頭結(jié)點的單鏈表}//CreateList_L算法的時間復(fù)雜度為:O(Listlength(L))L=newLNode;L->next=NULL;
//先建立一個帶頭結(jié)點的單鏈表for(i=n;i>0;--i){p=newLNode;
cin>>
p->data;//輸入元素值
p->next=L->next;L->next=p;//插入}99尾插法思路(正位序輸入):^Ldatanextppdatanextp->next=L->nextL->next=pp->next=L->next->nextL->next->next=pL->next->next->.......->next???100尾插法思路:^Ldatanextpspdatanextp->next=s->nexts->next=p注意:
⒈采用尾插法建表,生成的鏈表中結(jié)點的次序和輸入順序一致。
⒉必須增加一個尾指針s,使其始終指向當前鏈表的尾結(jié)點。101voidCreateList_L(LinkList&L,intn){//正序輸入n個數(shù)據(jù)元素,建立帶頭結(jié)點的單鏈表}//CreateList_L算法的時間復(fù)雜度為:O(Listlength(L))L=newLNode;L->next=NULL;S=L;//
建立帶頭結(jié)點/尾指針的單鏈表for(i=1;i<=n;++i){p=newLNode;
cin>>
p->data;//輸入元素值
p->next=S->next;S->next=p;S=p;//插入}102則
歸并兩個“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB,求得有序表LC也具有同樣特性。(用單鏈表實現(xiàn))設(shè)
La=(a1,…,ai,…,an)
Lb=(b1,…,bj,…,bm)
Lc=(c1,…,ck,…,cm+n)【例
2-7】鏈表的應(yīng)用。k=1,2,…,m+n103算法分析:搜索:需要兩個指針搜索兩個鏈表;比較:比較結(jié)點數(shù)據(jù)域中數(shù)據(jù)的大??;插入:將兩個結(jié)點中數(shù)據(jù)小的結(jié)點插入新鏈表。1043
5
8
11^
2
6
7
12^9
Pa、Pb用于搜索La和Lb,Pc指向新鏈表當前結(jié)點LaLbPbPaLcPc=∧不需要重建結(jié)點空間,只要修改指針即可105voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){//合并兩個有序表
}//MergeList_Lpa=La->next;pb=Lb->next;//p指向第一個結(jié)點
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;}
106假如x=3y=6算法思路:138459L^Pqqq【例2-8】設(shè)計一個算法,要求刪除線性表中介于x和y之間的數(shù)據(jù)。107voiddel_LQ(LinkListL,intx,inty){}//del_LQp=L;while(p->next){if(p->next->data>=x&&p->next->data<=y) {
q=p->next; p->next=q->next; delete(q); } else p=p->next;}線性表鏈式存儲結(jié)構(gòu)的特點:(1).
邏輯上相鄰的元素,其物理位置不一定相鄰;元素之間的鄰接關(guān)系由指針域指示。(2).鏈表是非隨機存取存儲結(jié)構(gòu);對鏈表的存取必須從頭指針開始。(3).鏈表是一種動態(tài)存儲結(jié)構(gòu);鏈表的結(jié)點可調(diào)用new()申請和delete()釋放。(4).插入刪除運算非常方便;只需修改相應(yīng)指針值。109單鏈表的特點:1.它是一種動態(tài)結(jié)構(gòu),整個存儲空間為多個鏈表共用。2.指針占用額外存儲空間。3.在鏈表中,元素的“位序”概念淡化,結(jié)點的“位置”概念加強。4.不能隨機存取,查找速度慢,但是插入、刪除操作很方便。1101.定義:最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表,使鏈表構(gòu)成環(huán)狀。a1a2…...an
帶頭結(jié)點的單循環(huán)鏈表h空表2.3.2單向循環(huán)鏈表111特點:從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點,提高查找效率。單循環(huán)鏈表a1a2…...an
帶頭結(jié)點的單循環(huán)鏈表112typedefstructLNode{
ElemTypedata; structLNode*next;}LNode,*CircleLinkList;2.存儲結(jié)構(gòu)(和單鏈表相同)113與單鏈表基本一致,它們僅在循環(huán)終止條件上有所不同。3.基本操作單鏈表:p==NULL或p->next==NULL循環(huán)鏈表:p==L或p->next==L114頭插法LdatanextpdatanextpL->next=p;(1)單向循環(huán)鏈表創(chuàng)建p->next=L->next;115頭插法voidCreatListF(CircleLinkList&L){
}//CreatListFcharch;
L=newLNode;//頭指針
L->next=L;
//鏈表開始為空
ch=getchar();//讀入第1個字符
while(ch!='\n'){
p=newLNode;//生成新結(jié)點
p->data=ch;
p->next=L->next;L->next=p;
ch=getchar();
//讀入下一字符
}
116尾插法Ldatanextprpdatanextp->next=Lr->next=p;117尾插法voidCreatListR(CircleLinkList&L){
}//CreatListR
L=newLNode;//頭指針
L->next=L;
//鏈表開始為空
r=L;//設(shè)置尾指針初值
ch=getchar();//讀入第1個字符
while(ch!='\n'){
p=newLNode;
p->data=ch;
p->next=L;//將新結(jié)點插到r之后
r->next=p;
r=p;//尾指針指向新表尾
ch=getchar();
//讀入下一字符
}//endwhile118(2)單向循環(huán)鏈表元素的讀取L1p5j=1假設(shè)i=2j<ij=j+1=2j=i找到?。?!119L1p5j=1j<ij=j+1=2j<i假設(shè)i=4j=j+1=3j<i=L沒找到!??!120L1p5j=1j>i假設(shè)i=0沒找到?。?!121xsbapabps->next=p->next;p->next=s;插入前插入后(3)單向循環(huán)鏈表的插入(同單鏈表)122cabpq=p->next;qp->next=q->next;deleteq;(4)單向循環(huán)鏈表的刪除(同單鏈表)1232.3.3雙向鏈表∧∧L空雙向鏈表:非空雙向鏈表:∧L∧ABbcapp->prior->next=p=p->next->prior;priordatanext124結(jié)構(gòu)定義typedefstructDBLNode{ElemTypedata;
//數(shù)據(jù)域
structDBLNode*prior;
//指向前驅(qū)的指針域
structDBLNode*next;
//
指向后繼的指針域}DBLNode,*DBLinkList;priordatanext1252.3.4雙向循環(huán)鏈表L空雙向循環(huán)鏈表:非空雙向循環(huán)鏈表:LABbcapp->prior->next=p=p->next->proir;1261.結(jié)構(gòu)定義typedefstructDBLNode{ElemTypedata;
//數(shù)據(jù)域
structDBLNode*prior;
//指向前驅(qū)的指針域
structDBLNode*next;
//
指向后繼的指針域}DBLNode,*DBLinkList;priordatanext1272.雙向循環(huán)鏈表的操作InitDBList(&DL)LocateDBList(DL,i)LocateDBNode(DL,key)InsertDBNode(&DL,i,x)DeleteDBNode(&DL,inti)CreateDBList(&DL)128voidInitDblList(DBLinkList&DL)
{//初始化雙向循環(huán)鏈表
}//InitDblListDL=newDBLNode;if(DL==NULL){cout<<"存儲分配錯!\n";exit(1); }DL->prior=DL->next=DL;
//表頭結(jié)點的鏈指針指向自己(1)初始化雙向循環(huán)鏈表129DBLNode*LocateDBList(DBLinkListDL,inti)
{//按位查找
}//LocateDBListp=DL->next;
j=1;while(p!=DL&&j<i){ p=p->next;j++; } if(p==DL||j>i)returnNULL; elsereturnp;(2)在雙向循環(huán)鏈表中按位查找130DBLNode*LocateDBNode(DBLinkListDL,ElemTypekey)
{//按值查找
}//LocateDBNodep=DL->next;
while(p!=DL&&key!=p->data) p=p->next; if(p==DL)returnNULL; elsereturnp;(3)在雙向循環(huán)鏈表中按值查找131(4)雙向循環(huán)鏈表的前插操作算法voiddinsertbefor(DBLNode*p,ElemTypex){
q=newDBLNode;q—>data=x;
//數(shù)據(jù)域
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;}算法時間復(fù)雜度為:
O(1)xqbaP132intInsertDblNode(DBLinkList&DL,inti,ElemTypex)
{//前插法
}//InsertDblNodep=LocateDBList(DL,i);//指針定位于插入位置if(!p)returnERROR;q=newDBLNode;//分配結(jié)點q->data=x;q->prior=p->prior;q->next=p;//插入結(jié)點p->prior->next=q; p->prior=q;133(5)雙向鏈表的后插操作算法voi
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024屆上海市寶山區(qū)行知實驗高三考前熱身數(shù)學(xué)試題試卷
- 初中物理“光的反射”說課稿
- 5年中考3年模擬試卷初中道德與法治九年級下冊10中考道德與法治真題分項精練(十)
- 食品發(fā)酵工藝學(xué)
- 人教版八年級下冊音樂教案(全冊)
- 《品篆刻之美》課件 2024-2025學(xué)年人美版(2024)初中美術(shù)七年級上冊
- 冷鏈糕點配送協(xié)議
- 咖啡廳衛(wèi)生間裝修合同樣本
- 辦公樓精裝修工程設(shè)計協(xié)議
- 國際物流合作居間協(xié)議
- 2024至2030年中國維生素D滴劑行業(yè)市場深度研究及發(fā)展趨勢預(yù)測報告
- 2024年中國全屋定制行業(yè)市場調(diào)查、產(chǎn)業(yè)鏈全景及市場需求規(guī)模預(yù)測報告
- 中國體育奧林匹克運動會發(fā)展歷史講解課件模板
- 物品抵押的借款協(xié)議樣本
- 桶裝飲用水生產(chǎn)清洗消毒技術(shù)規(guī)范
- 《成人四肢血壓測量的中國專家共識(2021)》解讀
- 2024年初中語文文化知識競賽試題及答案
- 2024-2030年中國風(fēng)力渦輪機服務(wù)(GWS)行業(yè)市場發(fā)展趨勢與前景展望戰(zhàn)略分析報告
- 油建工人安全技術(shù)操作規(guī)程培訓(xùn)資料樣本
- 初中化學(xué)人教版九上4.1 愛護水資源(課件)
- 2024年公務(wù)員(國考)之行政職業(yè)能力測驗真題附參考答案(完整版)
評論
0/150
提交評論