第02章數(shù)據(jù)結(jié)構(gòu)線性表1

回顧數(shù)據(jù):是客觀事物的符號表示，在計算機科學(xué)中指能輸入計算機并能由計算機程序進行處理的符號總稱。

數(shù)據(jù)元素:是數(shù)據(jù)的基本單位，在程序中通常是作為一個整體來進行考慮和處理的。

數(shù)據(jù)對象:是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

數(shù)據(jù)結(jié)構(gòu):是相互之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)概念1第2章線性表第3章棧和隊列第4章串第5章數(shù)組和廣義表

線性結(jié)構(gòu)

若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。可表示為：（a1,a2,……,an）線性結(jié)構(gòu)的定義：（邏輯、存儲和運算）線性結(jié)構(gòu)的特點：①只有一個首結(jié)點和尾結(jié)點；②除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。線性結(jié)構(gòu)表達式：（a1,a2,……,an）線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型、最常用的是線性表簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是

一對一的第2章線性表1.了解線性結(jié)構(gòu)的特點2.掌握順序表的定義、查找、插入和刪除3.掌握鏈表的定義、查找、插入和刪除4.能夠從時間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點及其適用場合

教學(xué)目標線性表重點：順序表和鏈表上各種基本算法的實現(xiàn)及相關(guān)的時間性能分析難點：線性表應(yīng)用的算法設(shè)計2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)教學(xué)內(nèi)容2.1線性表的定義線性表(LinearList)是具有相同特性的數(shù)據(jù)元素的一個有限序列a1a2an-1an…該序列中所含元素的個數(shù)叫做線性表的長度,用n表示,n≥0。當n=0時,表示線性表是一個空表,即表中不包含任何元素。設(shè)序列中第i(i表示位序)個元素為ai(1≤i≤n)。線性表的一般表示為:

其中a1為第一個元素,又稱做表頭元素,a2為第二個元素,an為最后一個元素,又稱做表尾元素。例如,在線性表

(1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。(a1,a2,…ai,ai+1,…,an)2.1線性表的類型定義定義n(≥0)個數(shù)據(jù)元素的有限序列,記作(a1,…ai-1,ai,ai+1,…,an)其中，ai

是表中數(shù)據(jù)元素，n

是表長度(n=0時稱為空表)邏輯特征n>0時有且僅有一個“第一個”數(shù)據(jù)元素有且僅有一個“最后一個”數(shù)據(jù)元素除第一個數(shù)據(jù)元素外，其它元素有且僅有一個直接前驅(qū)除最后一個數(shù)據(jù)元素外，其它元素有且僅有一個直接后繼（a1,a2,…ai-1，ai,ai＋1

，…,an）線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時稱為數(shù)據(jù)元素線性起點ai的直接前趨ai的直接后繼下標，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長空表線性終點2.1線性表的類型定義例1分析26個英文字母組成的英文表

（A,B,C,D,……,Z）學(xué)號姓名性別年齡班級041810205于春梅女1804級計算機1班041810260何仕鵬男2004級計算機2班041810284王爽女1904級計算機3班041810360王亞武男1804級計算機4班：：：

：：例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性線性表的基本操作1.初始化線性表LInitList(L)2.銷毀線性表LDestoryList(L)3.清空線性表LClearList(L)4.求線性表L的長度ListLength(L)5.判斷線性表L是否為空IsEmpty(L)6.獲取線性表L中的某個數(shù)據(jù)元素內(nèi)容GetElem(L,i,e)7.檢索值為e的數(shù)據(jù)元素LocateELem(L,e)

8.返回線性表L中e的直接前驅(qū)元素PriorElem(L,e)9.返回線性表L中e的直接后繼元素NextElem(L,e)

10.在線性表L中插入一個數(shù)據(jù)元素ListInsert(L,i,e)11.刪除線性表L中第i個數(shù)據(jù)元素ListDelete(L,i,e)(1)初始化線性表InitList(&L):構(gòu)造一個空的線性表L。

(2)銷毀線性表DestroyList(&L):釋放線性表L占用的內(nèi)存空間。線性表的運算

(3)判線性表是否為空表ListEmpty(L):若L為空表,則返回真,否則返回假。

(4)求線性表的長度ListLength(L):返回L中元素個數(shù)。

(5)輸出線性表DispList(L):當線性表L不為空時,順序顯示L中各結(jié)點的值域。

(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))個元素的值。

(7)定位查找LocateElem(L,e):返回L中第1個值域與e相等的位序。若這樣的元素不存在,則返回值為0。

(8)插入數(shù)據(jù)元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)個元素之前插入新的元素e,L的長度增1。

(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e):刪除L的第i(1≤i≤ListLength(L))個元素,并用e返回其值,L的長度減1。

例2.1假設(shè)有兩個集合A和B分別用兩個線性表LA和LB表示,即線性表中的數(shù)據(jù)元素即為集合中的成員。

編寫一個算法求一個新的集合C=A∪B,即將兩個集合的并集放在線性表LC中。

解:本算法思想是:先初始化線性表LC,將LA的所有元素復(fù)制到LC中,然后掃描線性表LB,若LB的當前元素不在線性表LA中,則將其插入到LC中。算法如下:voidunionList(ListLA,ListLB,List&LC){intlena,lenc,i;ElemTypee;InitList(LC);/*初始化線性表LC*/for(i=1;i<=ListLength(LA);i++) /*將LA的所有元素插入到LC中*/{ GetElem(LA,i,e); ListInsert(LC,i,e);}lenA=ListLength(LA);/*求線性表的長度*/lenB=ListLength(LB);

for(i=1;i<=lenB;i++) { GetElem(LB,i,e);

/*取LB中第i個數(shù)據(jù)元素賦給e*/ if(!LocateElem(LA,e)) ListInsert(LC,++lenC,e); /*LA中不存在和e相同者,則插入到LC中*/ }}

由于LocateElem(LA,e)運算的時間復(fù)雜度為O(ListLength(LA)),所以本算法的時間復(fù)雜度為:O(ListLength(LA)*ListLength(LB))2.2線性表的順序存儲2.2.1線性表的順序存儲—順序表2.2.2順序表基本運算的實現(xiàn)2.2線性表的順序表示和實現(xiàn)線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。簡言之，邏輯上相鄰，物理上也相鄰順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。隨機存取線性表中第一個元素的存儲位置就是指定的存儲位置第i+1個元素(1≤i≤n-1)的存儲位置緊接在第i個元素的存儲位置的后面假定線性表的元素類型為ElemType則每個元素所占用存儲空間大小(即字節(jié)數(shù))為sizeof(ElemType)整個線性表所占用存儲空間的大小為:

n*sizeof(ElemType)其中,n表示線性表的長度。順序表示意圖元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲順序表的存儲LOC(ai+1)=LOC(ai)+lLOC(a

i)=LOC(a1)+(i-1)*l

a1

a2

…a

i………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle線性表邏輯結(jié)構(gòu)順序表存儲結(jié)構(gòu)順序存儲方法：用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過數(shù)組V[n]來實現(xiàn)。688970674078

邏輯序號123456C數(shù)組下標012345陳述問題時用在定義一個線性表的順序存儲類型時,需要定義一個數(shù)組來存儲線線表中的所有元素和定義一個整型變量來存儲線性表的長度由于數(shù)組的下標從0開始，線性表的第i個元素ai存放順序表的第i-1位置上。為了清楚，將ai在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。2.2線性表的順序存儲結(jié)構(gòu)---順序表順序表的特點容量固定1105106107108109110201202203204205206207208209210301302303304305306307308309310101102103104101102103104A班宿舍105106107108109B班宿舍安排A班40人住入宿舍安排B班50人住入宿舍2.2線性表的順序存儲結(jié)構(gòu)---順序表由于線性表中每個元素所占用的空間是相同的，只需按照公式計算便可以快速地訪問指定元素。假設(shè)順序表中第一個元素的位置是Loc，每個數(shù)據(jù)元素所占用的存儲空間為n：順序表的特點訪問速度快2a1a2．．．a(chǎn)i．．．線性存儲空間下標位置01i-1存儲地址LocLoc+nLoc+(i–1)*n建立順序表

其方法是將給定的含有n個元素的數(shù)組的每個元素依次放入到順序表中，并將n賦給順序表的成員。算法如下：

CreateList(SqList&L,ElemTypea[],intn)

/*建立順序表*/

{

inti;for(i=0;i<n;i++) L.data[i]=a[i];

L.length=n;

}典型操作的算法實現(xiàn)1.初始化線性表L（參數(shù)用引用）intInitList(SqList&L){L.length=0;//空表長度置0L.listsize=LIST_INIT_SIZE;returnOK;//成功返回OK}1.初始化線性表L（參數(shù)用指針）intInitList(SqList*L){L.length=0;//空表長度置0 L.listsize=LIST_INIT_SIZE;returnOK;//成功返回OK}典型操作的算法實現(xiàn)2.銷毀線性表LvoidDestroyList(SqList&L){if(L.elem)free(L.elem);//釋放存儲空間}3.清空線性表LvoidClearList(SqList&L){L.length=0;//將線性表的長度置為0}4.

求線性表L的長度intGetLength(SqList&L){return(L.length);}5.判斷線性表L是否為空intIsEmpty(SqList&L){if(L.length==0)returnTRUE;/*或return(L.length==0);*/elsereturnFALSE;}6.輸出線性表DispList(L)

該運算當線性表L不為空時,順序顯示L中各元素的值。

voidDispList(SqList&L){ inti; if(IsEmpty(L))return; for(i=0;i<L.length;i++)

輸出L.data[i]; printf("\n");}

7.獲取線性表L中的某個數(shù)據(jù)元素的內(nèi)容//根據(jù)指定位置，獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容intGetElem(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;//判斷i值是否合理，若不合理，返回ERROR

e=L.elem[i-1];

//第i-1的單元存儲著第i個數(shù)據(jù)

returnOK;}查找（根據(jù)指定數(shù)據(jù)查找，返回數(shù)據(jù)所在的位置）

順序查找圖示253457164809

012345data查找

16i253457164809

i253457164809

i253457164809

i查找成功順序查找第1個值域與e相等的元素的位序。若這樣的元素不存在,則返回0。2534571648

01234data查找50i2534571648

i2534571648

i2534571648

i2534571648

i查找失敗查找算法時間效率分析？？？8.在線性表L中查找值為e的數(shù)據(jù)元素intLocateELem(SqList&L,ElemType&e){for(i=0;i<L.length;i++)if(L.elem[i]==e)returni+1;return0;}查找成功的平均比較次數(shù)(pi為各項的查找概率)

若查找概率相等，則

查找不成功數(shù)據(jù)比較n

次查找算法時間效率分析

2512478936141234567892512479989361499插入251247893614251247893614251247893614插第4個結(jié)點之前，移動6－4+1

次插在第i個結(jié)點之前，移動n-i+1

次插入（插在第i個結(jié)點之前）

實現(xiàn)步驟：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?應(yīng)當為：1≤i≤n+1或i=[1,n+1]將第n至第i位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。9.在線性表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e

intListInsert(SqList&L,inti,ElemType&e){if(i<1||i>L.length+1)returnERROR;//檢查i值是否合理

for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//將第i個之后的依次向后移動

L.elem[i-1]=e;//將新元素放入第i個位置

L.length++;returnOK;}若插入在尾結(jié)點之后，則根本無需移動（特別快）；若插入在首結(jié)點之前，則表中元素全部后移（特別慢）；若要考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)，該如何計算？算法時間主要耗費在移動元素的操作上插入算法時間效率分析

…251247893614123456789251247361425124736142512473614刪除刪除（刪除第i個結(jié)點）

刪除第4個結(jié)點，移動6－4

次刪除第i個結(jié)點，移動n-i

次實現(xiàn)步驟：事先需要判斷，刪除位置i是否合法?應(yīng)當有1≤i≤n或i=[1,n]將第i+1至第n位的元素向前移動一個位置；表長減1。10.將線性表L中第i個數(shù)據(jù)元素刪除intListDelete(SqList&L,inti,ElemType&e){if(IsEmpty(L))returnERROR;//檢測是否為空

if(i<1||i>L.length)returnERROR;//檢查i值是否合理

e=L.elem[i-1];//將欲刪除的元素保留在e中

for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j];//依次將第i+1后的元素向前移

L.length--;

returnOK;}若刪除尾結(jié)點，則根本無需移動（特別快）；若刪除首結(jié)點，則表中n-1個元素全部前移（特別慢）；若要考慮在各種位置刪除（共n種可能）的平均移動次數(shù)，該如何計算？算法時間主要耗費在移動元素的操作上刪除算法時間效率分析

顯然，順序表的空間復(fù)雜度S(n)=O(1)（沒有占用輔助空間）查找、插入、刪除算法的平均時間復(fù)雜度為O(n)（1）利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)一致順序表（順序存儲結(jié)構(gòu)）的特點這種存取元素的方法被稱為隨機存取法（2）在訪問線性表時，可以快速地計算出任何一個數(shù)據(jù)元素的存儲地址。因此可以粗略地認為，訪問每個元素所花時間相等

設(shè)計一個算法,將x插入到一個有序(從小到大排序)的線性表(順序存儲結(jié)構(gòu)即順序表)的適當位置上,并保持線性表的有序性。

解:先通過比較在順序表L中找到存放x的位置i,然后將x插入到L.data[i]中,最后將順序表的長度增1。練習voidInsert(SqList&L,ElemTypex){inti=0,j;

while(i<L.length&&L.data[i]<x) i++;

for(j=L.length-1;j>=i;j--) L.data[j+1]=L.data[j];L.data[i]=x;L.length++;}查找插入位置元素后移一個位置a0…ai-1ai…an-1……邏輯位序

1

ii+1nMaxSize

設(shè)計一個算法,將兩個元素有序(從小到大)的順序表合并成一個有序順序表。

求解思路:將兩個順序表進行二路歸并。

例題歸并到順序表r中←k記錄r中元素個數(shù)

1(i=0)2(j=0)

將1(i=1)插入r(k=1)3(i=1)2(j=0)將2(j=1)插入r(k=2)3(i=1)4(j=1)將3(i=2)插入r(k=3)5(i=2)4(j=1)將4(j=2)插入r(k=4)5(i=2)10(j=2)將5(j=3)插入r(k=5)

將q中余下元素插入r中。

順序表p：1

3

5i順序表q：2

4

10

20j順序表r：1

kSqList*merge(SqList*p,SqList*q){SqList*r;inti=0,j=0,k=0;while(i<p.length&&j<q.length){ if(p.data[i]<q.data[j]) {r.data[k]=p.data[i]; i++;k++; } else {r.data[k]=q.data[j]; j++;k++; }}

while(i<p.length) {r.data[k]=p.data[i]; i++;k++; }while(j<q.length){r.data[k]=q.data[j]; j++;k++; } r.length=k;/*或p.length+q.length*/ return(r);}線性表的應(yīng)用－－線性表合并（算法2.1）問題描述：假設(shè)利用兩個線性表La和Lb分別表示兩個集合A和B,現(xiàn)要求一個新的集合

A=ABLa=(7,5,3,11)Lb=(2,6,3)La=(7,5,3,11,2,6).依次取出Lb中的每個元素，執(zhí)行以下操作：

在La中查找該元素如果找不到，則將其插入La的最后線性表合并－－操作步驟voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);

}}線性表合并（算法2.1）問題描述：

已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列,現(xiàn)要求將La和Lb歸并為一個新的線性表Lc,且Lc中的數(shù)據(jù)元素仍按值非遞減有序排列.La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,

2,

4,6,7,8,8,10,11).有序表合并（算法2.2）(1)Lc為空表(2)

依次從La或Lb中“摘取”元素值較小的結(jié)點插入到Lc表的最后，直至其中一個表變空為止(3)繼續(xù)將La或Lb其中一個表的剩余結(jié)點插入在Lc表的最后有序表合并－－操作步驟voidMergeList(ListLa,ListLb,List&Lc){

InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){

GetElem(La,i,ai);

GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}有序表合并（算法2.2）(1)創(chuàng)建一個空表Lc(2)

依次從La或Lb中“摘取”元素值較小的結(jié)點插入到Lc表的最后，直至其中一個表變空為止(3)繼續(xù)將La或Lb其中一個表的剩余結(jié)點插入在Lc表的最后有序的順序表合并－－操作步驟voidMergeList(SqListLa,SqListLb,SqList&Lc)ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;/*不用InitList()創(chuàng)建空表Lc*/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)/*表La和表Lb均非空*/{if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;/*插入La的剩余元素*/while(pb<=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;/*插入Lb的剩余元素*/}有序的順序表合并（算法2.7)T(n)=S(n)=O(n)#defineN10intmax(inta[]);voidmain(){ inta[10]; inti,m; for(i=0;i<N;i++)

輸入a[i]; m=max(a);

輸出"themaxnumberis:"m;}intmax(intb[]){inti,n;n=b[0];for(i=1;i<N;i++) if(n<b[i])n=b[i];returnn;}練習：求10個整數(shù)的最大數(shù)練習：將數(shù)組中n個整數(shù)按相反的順序存放#include<iostream.h>#defineN10voidsub(intb[]){ inti,j,temp,m; m=N/2; for(i=0;i<m;i++){j=N-1-i;temp=b[i]; b[i]=b[j];b[j]=temp; } return;}voidmain(){ inta[10],i; for(i=0;i<N;i++) cin>>a[i]; sub(a); for(i=0;i<N;i++) cout<<a[i];}順序表的優(yōu)缺點缺點：在插入、刪除某一元素時，需要移動大量元素浪費存儲空間屬于靜態(tài)存儲形式，數(shù)據(jù)元素的個數(shù)不能自由擴充鏈表為克服這一缺點優(yōu)點：存儲密度大（結(jié)點本身所占存儲量/結(jié)點結(jié)構(gòu)所占存儲量）可以隨機存取表中任一元素單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表其他

2.3線性表的鏈式表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)鏈式存儲結(jié)構(gòu)結(jié)點在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰線性表的鏈式表示又稱為非順序映像或鏈式映像。特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結(jié)點

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結(jié)點2.3線性表的鏈式存儲結(jié)構(gòu)在鏈式存儲中,每個存儲結(jié)點不僅包含有所存元素本身的信息(稱之為數(shù)據(jù)域)而且包含有元素之間邏輯關(guān)系的信息,即前驅(qū)結(jié)點包含有后繼結(jié)點的地址信息,這稱為指針域這樣可以通過前驅(qū)結(jié)點的指針域方便地找到后繼結(jié)點的位置,提高數(shù)據(jù)查找速度。2.3.1線性表的鏈式存儲—鏈表一般地,每個結(jié)點有一個或多個這樣的指針域。若一個結(jié)點中的某個指針域不需要任何結(jié)點,則僅它的值為空,用常量NULL表示。鏈表定義結(jié)點-數(shù)據(jù)元素的存儲映像，包括數(shù)據(jù)域和指針域（其信息稱為指針或鏈）頭指針-鏈表存取的開始；空(NULL)-最后一個結(jié)點的指針

2.3.1線性鏈表數(shù)據(jù)域指針域LI43QIAN13SUN1WANGNULLWU37ZHAO7ZHENG19ZHOU25存儲地址1713192531374331頭指針ZHAOQIANSUNLIZHOUWUZHENGWANG^H線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針鏈表定義

typedefstructLNode{

ElemTypedata;

//數(shù)據(jù)域

structLNode*next;

//后向指針域

}LNode,*LinkList;2.3.1線性鏈表例畫出26個英文字母表的鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)：（a,b,…,y,z）aheadb/\z……各結(jié)點由兩個域組成：數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼結(jié)點的存儲位置指針數(shù)據(jù)與鏈式存儲有關(guān)的術(shù)語1、結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成2、鏈表：n個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結(jié)構(gòu)a1heada2an……h(huán)ead循環(huán)鏈表示意圖：3、單鏈表、雙鏈表、循環(huán)鏈表：

結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表有兩個指針域的鏈表，稱為雙鏈表首尾相接的鏈表稱為循環(huán)鏈表4、頭指針、頭結(jié)點和首元結(jié)點

頭指針頭結(jié)點首元結(jié)點a1heada2…infoan^頭指針是指向鏈表中第一個結(jié)點的指針首元結(jié)點是指鏈表中存儲第一個數(shù)據(jù)元素a1的結(jié)點頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息例：一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。7ZHAOH31∴頭指針的值是31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無頭結(jié)點②有頭結(jié)點討論1.如何表示空表？有頭結(jié)點時，當頭結(jié)點的指針域為空時表示空表非空表 空表0ana0headhead^表頭結(jié)點第一個結(jié)點討論2.在鏈表中設(shè)置頭結(jié)點有什么好處？⒈便于首元結(jié)點的處理首元結(jié)點的地址保存在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作和其它位置一致，無須進行特殊處理;⒉便于空表和非空表的統(tǒng)一處理無論鏈表是否為空，頭指針都是指向頭結(jié)點的非空指針，因此空表和非空表的處理也就統(tǒng)一了。

討論3.頭結(jié)點的數(shù)據(jù)域內(nèi)裝的是什么？

頭結(jié)點的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，但此結(jié)點不能計入鏈表長度值。頭結(jié)點的數(shù)據(jù)域H（1）結(jié)點在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰鏈表（鏈式存儲結(jié)構(gòu)）的特點（2）訪問時只能通過頭指針進入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，所以尋找第一個結(jié)點和最后一個結(jié)點所花費的時間不等這種存取元素的方法被稱為順序存取法優(yōu)點數(shù)據(jù)元素的個數(shù)可以自由擴充插入、刪除等操作不必移動數(shù)據(jù)，只需修改鏈接指針，修改效率較高鏈表的優(yōu)缺點缺點存儲密度小存取效率不高，必須采用順序存取，即存取數(shù)據(jù)元素時，只能按鏈表的順序進行訪問（順藤摸瓜）鏈表的優(yōu)缺點練習1.鏈表的每個結(jié)點中都恰好包含一個指針。2.順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。3.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。4.線性表若采用鏈式存儲時，結(jié)點之間和結(jié)點內(nèi)部的存儲空間都是可以不連續(xù)的。5.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型×

×

×

×

×

由于順序表中的每個元素至多只有一個前驅(qū)元素和一個后繼元素,即數(shù)據(jù)元素之間是一對一的邏輯關(guān)系,所以當進行鏈式存儲時,一種最簡單也最常用的方法是:在每個結(jié)點中除包含有數(shù)據(jù)域外,只設(shè)置一個指針域,用以指向其后繼結(jié)點,這樣構(gòu)成的鏈接表稱為線性單向鏈接表,簡稱單鏈表；如何實現(xiàn)？通過指針來實現(xiàn)單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3freefirst(b)經(jīng)過一段運行后的單鏈表結(jié)構(gòu)帶頭結(jié)點單鏈表示意圖

在線性表的鏈式存儲中,為了便于插入和刪除算法的實現(xiàn),每個鏈表帶有一個頭結(jié)點,并通過頭結(jié)點的指針惟一標識該鏈表。

在單鏈表中,由于每個結(jié)點只包含有一個指向后繼結(jié)點的指針所以當訪問過一個結(jié)點后,只能接著訪問它的后繼結(jié)點,而無法訪問它的前驅(qū)結(jié)點

單鏈表非空表空表單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名若頭指針名是L，則把鏈表稱為表L

typedefstructLnode{ElemTypedata;//數(shù)據(jù)域

structLNode*next;//指針域}LNode,*LinkList;

//*LinkList為Lnode類型的指針單鏈表的存儲結(jié)構(gòu)定義初始化單鏈表StatusInitList_L(LinkList&L){

//構(gòu)造一個空的線性表Lif(!L)returnOVERFLOW;L.next=NULL;returnOK;}銷毀單鏈表StatusDestroyList_L(LinkList&L){LinkListp;while(L){p=L;L=L.next;free(p);}returnOK;}單鏈表基本運算的實現(xiàn)

1.建立單鏈表先考慮如何建立單鏈表。假設(shè)我們通過一個含有n個數(shù)據(jù)的數(shù)組來建立單鏈表。建立單鏈表的常用方法有如下兩種:

(1)頭插法建表該方法從一個空表開始,讀取字符數(shù)組a中的字符,生成新結(jié)點。將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:從一個空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中將該新結(jié)點插入到鏈表的前端單鏈表的建立（頭插法）abcdi=0i=1i=2i=3∧head采用頭插法建立單鏈表的過程heada∧headba∧headcba∧headdcba∧第1步:建頭結(jié)點第2步:i＝0,新建a結(jié)點,插入到頭結(jié)點之后第3步:i＝1,新建d結(jié)點,插入到頭結(jié)點之后第4步:i＝2,新建c結(jié)點,插入到頭結(jié)點之后第5步:i＝3,新建b結(jié)點,插入到頭結(jié)點之后單鏈表的建立p.data=anp.data=an-1L.next=pp.next=L.nextvoidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L.next=NULL;for(i=0;i<n;i++){s.data=a[i];s.next=L.next; /*將s插在原開始結(jié)點之前,頭結(jié)點之后*/L.next=s;}}

(2)尾插法建表頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點插到當前鏈表的表尾上,為此必須增加一個尾指針r,使其始終指向當前鏈表的尾結(jié)點。采用尾插法建表的算法如下:bcdai=0i=1i=2i=3head頭結(jié)點adcb∧b采用尾插法建立單鏈表的過程voidCreateListR(LinkList*&L,ElemType