數(shù)據(jù)結(jié)構(gòu)(線性表)總結(jié)課件

第二章線性表第二章線性表12.1

線性表的類型定義2.3線性表類型的實現(xiàn)

鏈?zhǔn)接诚?.4一元多項式的表示2.2線性表類型的實現(xiàn)

順序映象2.1線性表的類型定義2.3線性表類型的實現(xiàn)2.42線性結(jié)構(gòu)的基本特征為:1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最后元素”；3．除最后元素之外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)

是一個數(shù)據(jù)元素的有序（次序）集線性表是一種最簡單的線性結(jié)構(gòu)線性結(jié)構(gòu)的基本特征為:1．集合中必存在唯一的一個“第一元素”32.1線性表的類型定義2.141線性表的邏輯結(jié)構(gòu)線性表(LinearList)：由n(n≧)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）1線性表的邏輯結(jié)構(gòu)線性表(LinearList)5姓名學(xué)號性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….例3、學(xué)生健康情況登記表如下：姓名學(xué)號性別年齡健康情況王小林790631男186綜合上述例子，我們可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內(nèi)部結(jié)點ai(2≦i≦n-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。抽象數(shù)據(jù)類型線性表的定義為：P19

綜合上述例子，我們可看出線性表的邏輯特征是：7抽象數(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在線性表中的位序。}抽象數(shù)據(jù)類型線性表的定義如下：ADTList{數(shù)據(jù)對象8

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

}ADTList基本操作：結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作引用型操作加工型9

InitList(&L)操作結(jié)果：構(gòu)造一個空的線性表L。初始化操作InitList(&L)操作結(jié)果：構(gòu)造一個空的線性表L10

結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：操作結(jié)果：線性表L已存在。銷毀線性表L。結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：線11ListEmpty(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())引用型操作:ListEmpty(L)ListLength(L)P12

ListEmpty(L)初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）ListEmpty(L)初始條件：線性表L已存在。若L13ListLength(L)初始條件：操作結(jié)果：線性表L已存在。返回L中元素個數(shù)。（求線性表的長度）ListLength(L)初始條件：線性表L已存在。返回14

PriorElem(L,cur_e,&pre_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。（求數(shù)據(jù)元素的前驅(qū)）PriorElem(L,cur_e,&pre_e)15NextElem(L,cur_e,&next_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數(shù)據(jù)元素的后繼）NextElem(L,cur_e,&next_e)初16GetElem(L,i,&e)

初始條件：

操作結(jié)果：線性表L已存在，且1≤i≤LengthList(L)。用

e返回L中第i

個元素的值。（求線性表中某個數(shù)據(jù)元素）GetElem(L,i,&e)初始條件：線性表L已17LocateElem(L,e,compare())初始條件：操作結(jié)果：線性表L已存在，e為給定值，

compare()是元素判定函數(shù)。返回L中第1個與e滿足關(guān)系compare()的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數(shù)）LocateElem(L,e,compare())18

ListTraverse(L,visit())初始條件：操作結(jié)果：線性表L已存在，Visit()為某個訪問函數(shù)。依次對L的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。（遍歷線性表）ListTraverse(L,visit())初始條件19加工型操作

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

加工型操作ClearList(&L)PutElem(20ClearList(&L)初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。（線性表置空）ClearList(&L)初始條件：線性表L已存在。將L21PutElem(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在，且1≤i≤LengthList(L)。L中第i個元素賦值同e的值。（改變數(shù)據(jù)元素的值）PutElem(&L,i,&e)初始條件：線性表L已22

ListInsert(&L,i,e)初始條件：操作結(jié)果：線性表L已存在，且1≤i≤LengthList(L)+1。在L的第i個元素之前插入新的元素e，L的長度增1。（插入數(shù)據(jù)元素）ListInsert(&L,i,e)初始條件：線性23ListDelete(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在且非空，

1≤i≤LengthList(L)。刪除L的第i個元素，并用e返回其值，L的長度減1。（刪除數(shù)據(jù)元素）ListDelete(&L,i,&e)初始條件：線性表L24利用上述定義的線性表可以實現(xiàn)其它更復(fù)雜的操作例2-2例2-3例2-1利用上述定義的線性表例2-2例2-3例2-125

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

現(xiàn)要求一個新的集合A＝A∪B。例2-1

假設(shè):有兩個集合A和B分別用兩個線性表LA和26要求對線性表作如下操作：擴大線性表LA，將存在于線性表LB中而不存在于線性表

LA中的數(shù)據(jù)元素插入到線性表LA

中去。上述問題可演繹為：要求對線性表作如下操作：上述問題可演繹為：271．從線性表LB中依次察看每個數(shù)據(jù)元素;2．依值在線性表LA中進行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)操作步驟：1．從線性表LB中依次察看每個數(shù)據(jù)元素;2．依值在線性表LA28

GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給e

if(!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++){}}//unionGetElem(Lb,i,e);//取Lb中29

已知一個非純集合B，試構(gòu)造一個純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。仍選用線性表表示集合。例2-2已知一個非純集合B，試構(gòu)造一個純集合A，使30集合B集合A從集合B取出物件放入集合A要求集合A中同樣物件不能有兩件以上因此，算法的策略應(yīng)該和例2-1相同集合B集合A從集合B取出物件放入集合A因此，算法的31voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}//union

GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給e

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之for(i=1;i<=Lb_len;i++){}InitList(La);//構(gòu)造(空的)線性表LAvoidunion(List&La,ListLb)32若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，則稱該線性表為有序表(OrderedList)。試改變結(jié)構(gòu)，以有序表表示集合。若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中33例如：（2，3，3，5，6，6，6，8，12）對集合B而言，

值相同的數(shù)據(jù)元素必定相鄰；對集合A而言，

數(shù)據(jù)元素依值從小至大的順序插入。因此，數(shù)據(jù)結(jié)構(gòu)改變了，解決問題的策略也相應(yīng)要改變。例如：對集合B而言，對集合A而言，因此，數(shù)據(jù)結(jié)構(gòu)改變34voidpurge(List&La,ListLb)

{InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

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

}}//purge

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ù)元素，則插入之voidpurge(List&La,ListLb)35voidMergeList(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);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);voidMergeList(ListLa,ListL36

//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;}//La和Lb均非空，i=j=1,k37

while(i<=La_len){//當(dāng)La不空時GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//當(dāng)Lb不空時GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素while(i<=La_len){//382.2線性表類型2.2線性表類型39最簡單的一種順序映象方法是：

令y的存儲位置和x的存儲位置相鄰。順序映象——

以x的存儲位置和y的存儲位置之間某種關(guān)系表示邏輯關(guān)系<x,y>。最簡單的一種順序映象方法是：順序映象——以x的存儲位置40

用一組地址連續(xù)的存儲單元

依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址稱作線性表的基地址用一組地址連續(xù)的存儲單元a1a2…41以“存儲位置相鄰”表示有序?qū)?lt;ai-1，ai>即：LOC(ai)=LOC(ai-1)+C

一個數(shù)據(jù)元素所占存儲量↑所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置LOC(ai)=

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

↑基地址以“存儲位置相鄰”表示有序?qū)?lt;ai-1，ai>所有數(shù)據(jù)元素的42順序映像的C語言描述typedefstruct{

}SqList;//俗稱順序表#defineLIST_INIT_SIZE80//線性表存儲空間的初始分配量#defineLISTINCREMENT10//線性表存儲空間的分配增量ElemType*elem;//存儲空間基址int

length;//當(dāng)前長度int

listsize;//當(dāng)前分配的存儲容量

//(以sizeof(ElemType)為單位)順序映像的C語言描述typedefstruct{#43線性表的基本操作在順序表中的實現(xiàn)InitList(&L)//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素線性表的基本操作在順序表中的實現(xiàn)InitList(&L)441.初始化操作Status

InitList_Sq(SqList&L)

{//構(gòu)造一個空的線性表

}//InitList_Sq算法時間復(fù)雜度：O(1)L.elem=(ElemType*)malloc(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;1.初始化操作算法時間復(fù)雜度：O(1)L.elem=(E452.查找操作（或定位操作）例如：順序表23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可見，基本操作是：將順序表中的元素逐個和給定值e相比較。2.查找操作（或定位操作）2375413846

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0}//LocateElem_Sq

O(ListLength(L))算法的時間復(fù)雜度為：i=1;//i的初值為第1元素的位序p=L.elem;

//p的初值為第1元素的存儲位置while

(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;(*compare)(*p++,e)intLocateElem_Sq(SqListL,E473.插入操作線性表操作

ListInsert(&L,i,e)的實現(xiàn)：首先分析:插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？3.插入操作首先分析:插入元素時，48

(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加(a1,…,ai-1,ai,…,an)改變?yōu)閍49

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//在順序表L的第i個元素之前插入新的元素e,

//i的合法范圍為1≤i≤L.length+1}//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;……元素右移StatusListInsert_Sq(SqList&50if(L.length>=L.listsize){

//當(dāng)前存儲空間已滿，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲分配失敗

L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存儲容量}if(i<1||i>L.length+1)returnERROR;

//插入位置不合法if(L.length>=L.listsize){512118307542568721183075例如：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;p211830754256872152考慮移動元素的平均情況:假設(shè)在第i個元素之前插入的概率為，

則在長度為n的線性表中插入一個元素所需移動元素次數(shù)的期望值為：若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：考慮移動元素的平均情況:假設(shè)在第i個元素之前插入534.刪除操作線性表操作

ListDelete(&L,i,&e)的實現(xiàn)：首先分析：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？4.刪除操作首先分析：刪除元素時，54

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,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,ai+1,…,an55StatusListDelete_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;

//刪除位置不合法元素左移StatusListDelete_Sqfor(++p;56考慮移動元素的平均情況:假設(shè)刪除第i個元素的概率為,則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為：若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：考慮移動元素的平均情況:假設(shè)刪除第i個元素的概率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)

p2118307542568721582.3線性表類型2.3線性表類型59一、單鏈表二、結(jié)點和單鏈表的C語言描述三、線性表的操作在單鏈表中的實現(xiàn)四、一個帶頭結(jié)點的單鏈表類型五、其它形式的鏈表六、有序表類型一、單鏈表二、結(jié)點和單鏈表的C語言描述三、線性表的操作在60

用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。一、單鏈表以元素(數(shù)據(jù)元素的映象)

+指針(指示后繼元素存儲位置)=結(jié)點

(表示數(shù)據(jù)元素或數(shù)據(jù)元素的映象)以“結(jié)點的序列”表示線性表

稱作鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。一61

以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點

a1a2…...an^頭指針頭指針

有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針?？罩羔樉€性表為空表時，頭結(jié)點的指針域為空以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地62

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

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

二、結(jié)點和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針TypedefstructLNode{二、結(jié)63三、單鏈表操作的實現(xiàn)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ù)元素的鏈表三、單鏈表操作的實現(xiàn)GetElem(L,i,e)64L線性表的操作

GetElem(L,i,&e)在單鏈表中的實現(xiàn):211830754256∧pppj123L線性表的操作211830754256∧ppp65

因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較j和I。

單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素。令指針p始終指向線性表中第j個數(shù)據(jù)元素。因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較66

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;StatusGetElem_L(LinkListL,67ai-1

線性表的操作

ListInsert(&L,i,e)

在單鏈表中的實現(xiàn)：

有序?qū)?lt;ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1ai-1線性表的操作ListInsert(&L,i,68因此，在單鏈表中第i個結(jié)點之前進行插入的基本操作為:

找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第i個結(jié)點之前插入元素，修改的是第i-1個結(jié)點的指針。因此，在單鏈表中第i個結(jié)點之前進行插入的基本操作69StatusListInsert_L(LinkListL,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大于表長或者小于1StatusListInsert_L(LinkList70s=(LinkList)malloc(sizeof(LNode));

//生成新結(jié)點s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sps=(LinkList)malloc(sizeof71線性表的操作ListDelete(&L,i,&e)在鏈表中的實現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1線性表的操作ListDelete(&L,i,&e)在鏈72

在單鏈表中刪除第

i個結(jié)點的基本操作為:找到線性表中第i-1個結(jié)點，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq在單鏈表中刪除第i個結(jié)點的基本操作為:找到線性表中73StatusListDelete_L(LinkListL,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;free(q);returnOK;StatusListDelete_L(LinkList74操作ClearList(&L)在鏈表中的實現(xiàn):voidClearList(&L){//將單鏈表重新置為一個空表

while(L->next){

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

}}//ClearListfree(p);算法時間復(fù)雜度：O(ListLength(L))操作ClearList(&L)在鏈表中的實現(xiàn):void75如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配76例如：逆位序輸入n個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。操作步驟：一、建立一個“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入；ananan-1四、依次類推，直至輸入a1為止。例如：逆位序輸入n個數(shù)據(jù)元素的值，操作步驟：一、建立一個77voidCreateList_L(LinkList&L,intn){//逆序輸入n個數(shù)據(jù)元素，建立帶頭結(jié)點的單鏈表}//CreateList_L算法的時間復(fù)雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

//先建立一個帶頭結(jié)點的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值p->next=L->next;L->next=p;//插入}voidCreateList_L(LinkList&L,78四、一個帶頭結(jié)點的線性鏈表類型typedefstructLNode{//結(jié)點類型ElemTypedata;

structLNode*next;}*Link,*Position;StatusMakeNode(Link&p,ElemTypee);

//分配由p指向的值為e的結(jié)點，并返回OK，//若分配失敗，則返回ERRORvoidFreeNode(Link&p);

//

釋放p所指結(jié)點鏈表類型{（略）}；鏈表基本操作；（從略）四、一個帶頭結(jié)點的線性鏈表類型typedefstruct79

1.雙向鏈表五、其它形式的鏈表typedefstructDuLNode{ElemTypedata;

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

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;1.雙向鏈表五、其它形式的鏈表typedefstruc80最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表a1a2…...an2.循環(huán)鏈表和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表81雙向循環(huán)鏈表空表非空表a1a2…...an雙向循環(huán)鏈表空表非空表a1a282雙向鏈表的操作特點：“查詢”和單鏈表相同?！安迦搿焙汀皠h除”時需要同時修改兩個方向上的指針。雙向鏈表的操作特點：“查詢”和單鏈表相同?！安迦搿焙汀皠h83ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入ai-1aies->next=p->next;p84ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-1ai-1刪除aiai+1p->next=p->next-85六、有序表類型ADT

Ordered_List{

數(shù)據(jù)對象:

S={xi|xiOrderedSet，i=1,2,…,n,n≥0}集合中任意兩個元素之間均可以進行比較數(shù)據(jù)關(guān)系:R={<xi-1,xi>|xi-1,xi

S,

xi-1≤xi,i=2,3,…,n}回顧例2-2的兩個算法六、有序表類型ADTOrdered_List{集合中數(shù)據(jù)86

LocateElem(L,e,&q,int(*compare)(ElemType,ElemType))初始條件：有序表L已存在。操作結(jié)果：若有序表L中存在元素e，則q指示L中第一個值為e的元素的位置，并返回函數(shù)值TRUE；否則q指示第一個大于e的元素的前驅(qū)的位置，并返回函數(shù)值FALSE。

基本操作：…………Compare是一個有序判定函數(shù)LocateElem(L,e,&q,基本87(12,23,34,45,56,67,78,89,98,45)例如:若e=45,則q指向

若e=88,則q指向表示值為88的元素應(yīng)插入在該指針?biāo)附Y(jié)點之后。(12,23,34,45,56,67,78,88voidunion(List&La,ListLb){//Lb為線性表

InitList(La);//構(gòu)造(空的)線性表LA

La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給e

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之}}//union算法時間復(fù)雜度：O(n2)voidunion(List&La,ListLb)89voidpurge(List&La,ListLb){//Lb為有序表InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

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

}}//purge

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ù)元素，則插入之算法時間復(fù)雜度：O(n)voidpurge(List&La,ListLb)902.4一元多項式的表示2.4一元多項式的表示91在計算機中，可以用一個線性表來表示:P=(p0,p1,…，pn)1.一元多項式的線性表表示但是對于形如

S(x)=1+3x10000–2x20000的多項式，上述表示方法是否合適？在計算機中，可以用一個線性表來表示:1.一元多項式的線性表表92

一般情況下的一元稀疏多項式可寫成

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

是指數(shù)為ei

的項的非零系數(shù)，

0≤e1<e2<┄<em=n可以下列線性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）一般情況下的一元稀疏多項式可寫成可以下列線性表表示：93

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

((7,3),(-2,12),(-8,999))表示P999(x)=7x3-2x12-8x999例94ADTPolynomial{

數(shù)據(jù)對象：

數(shù)據(jù)關(guān)系：2.抽象數(shù)據(jù)類型一元多項式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)

}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n且ai-1中的指數(shù)值＜ai中的指數(shù)值

}ADTPolynomial{2.抽象數(shù)據(jù)類型一元多項式的95

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)基本操作：操作結(jié)果：輸入m項的系數(shù)和指數(shù)，建立一元多項式P。初始條件：一元多項式P已存在。操作結(jié)果：銷毀一元多項式P。初始條件：一元多項式P已存在。操作結(jié)果：打印輸出一元多項式P。CreatPolyn(&P,m)96

PolynLength(P)

AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)……}ADTPolynomial初始條件：一元多項式P已存在。操作結(jié)果：返回一元多項式P中的項數(shù)。初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相加運算，即：Pa=Pa＋Pb，并銷毀一元多項式Pb。PolynLength(P)初始97-1A703198517^-1B81227-98^-1C70111227517^3.一元多項式相加實例與規(guī)則-1A703198q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^q-1pa703199設(shè)p,q分別指向A,B中某一結(jié)點，p,q初值是第一結(jié)點比較p->exp與q->expp->exp<q->exp:p結(jié)點是結(jié)果多項式中的一項，p后移,q不動p->exp>q->exp:q結(jié)點是結(jié)果多項式中的一項，將q插在p之前,q后移,p不動p->exp=q->exp:系數(shù)相加0：從A表中刪去p,釋放p,q，p,q后移0：修改p系數(shù)域,釋放q，p,q后移直到p或q為NULL若q==NULL，結(jié)束若p==NULL，將B中剩余部分連到A上即可運算規(guī)則設(shè)p,q分別指向A,B中某一結(jié)點，p,q初值是第一結(jié)點比較p1004.一元多項式的實現(xiàn)：typedefstruct{//項的表示

floatcoef;//系數(shù)

intexpn;//指數(shù)}

term,ElemType;typedefOrderedLinkListpolynomial;//用帶表頭結(jié)點的有序鏈表表示多項式結(jié)點的數(shù)據(jù)元素類型定義為:4.一元多項式的實現(xiàn)：typedefstruct{101StatusCreatPolyn(polynomail&P,intm){

//輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P}//CreatPolynInitList(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);//設(shè)置頭結(jié)點的數(shù)據(jù)元素for(i=1;i<=m;++i){//依次輸入m個非零項}returnOK;scanf(e.coef,e.expn);if(!LocateElem(P,e,(*cmp)()))

if(!InsAfter(P,e))returnERROR;注意:1.輸入次序不限;2.指數(shù)相同的項只能輸入一次。StatusCreatPolyn(polynomail102StatusAddPolyn(polynomial&Pc,polynomial&Pa,polynomial&Pb){

//利用兩個多項式的結(jié)點構(gòu)成“和多項式”Pc=Pa＋Pb……

if(DelAfter(Pa,e1))a=e1.expnelsea=MAXE;

if(DelAfter(Pb,e2))b=e2.expnelseb=MAXE;while(!(a=MAXE&&b=MAXE)){……}……}//AddPolynStatusAddPolyn(polynomial&103switch(*cmp(e1,e2)){case-1:{//

多項式PA中當(dāng)前結(jié)點的指數(shù)值小

……break;}case0:{

//

兩者的指數(shù)值相等

e1.coef=a.coef+b.coef;

if(a.coef!=0.0)InsAfter(Pc,e1);

……break;

}

case1:{

//多項式PB中當(dāng)前結(jié)點的指數(shù)值小

……break;}}switch(*cmp(e1,e2)){104本章小結(jié)1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。2.熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實現(xiàn)。3.能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。本章小結(jié)1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性105習(xí)

題

二

1．什么是順序存儲結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯Y(jié)構(gòu)？2．線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)各有什么特點？3．設(shè)線性表中數(shù)據(jù)元素的總數(shù)基本不變，并很少進行插入或刪除工作，若要以最快的速度存取線性表中的數(shù)據(jù)元素，應(yīng)選擇線性表的何種存儲結(jié)構(gòu)？為什么?4．線性表的主要操作有哪些？5．簡述數(shù)組與順序存儲結(jié)構(gòu)線性表的區(qū)別和聯(lián)系。6．順序表和鏈表在進行插入操作時，有什么不同？7．畫出下列數(shù)據(jù)結(jié)構(gòu)的圖示：①順序表②單鏈表③雙鏈表④循環(huán)鏈表8．試給出求順序表長度的算法。9．若順序表A中的數(shù)據(jù)元素按升序排列，要求將x插入到順序表中的合適位置，以保證表的有序性，試給出其算法。10．試將一個無序的線性表A=(11,16,8,5,14,10,38,23)轉(zhuǎn)換成一個按升序排列的有序線性表（用鏈表實現(xiàn)）。習(xí)題二

1．什么是順序存儲結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯Y(jié)構(gòu)？106第二章線性表第二章線性表1072.1

線性表的類型定義2.3線性表類型的實現(xiàn)

鏈?zhǔn)接诚?.4一元多項式的表示2.2線性表類型的實現(xiàn)

順序映象2.1線性表的類型定義2.3線性表類型的實現(xiàn)2.4108線性結(jié)構(gòu)的基本特征為:1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最后元素”；3．除最后元素之外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)

是一個數(shù)據(jù)元素的有序（次序）集線性表是一種最簡單的線性結(jié)構(gòu)線性結(jié)構(gòu)的基本特征為:1．集合中必存在唯一的一個“第一元素”1092.1線性表的類型定義2.11101線性表的邏輯結(jié)構(gòu)線性表(LinearList)：由n(n≧)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）1線性表的邏輯結(jié)構(gòu)線性表(LinearList)111姓名學(xué)號性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….例3、學(xué)生健康情況登記表如下：姓名學(xué)號性別年齡健康情況王小林790631男18112綜合上述例子，我們可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內(nèi)部結(jié)點ai(2≦i≦n-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。抽象數(shù)據(jù)類型線性表的定義為：P19

綜合上述例子，我們可看出線性表的邏輯特征是：113抽象數(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在線性表中的位序。}抽象數(shù)據(jù)類型線性表的定義如下：ADTList{數(shù)據(jù)對象114

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

}ADTList基本操作：結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作引用型操作加工型115

InitList(&L)操作結(jié)果：構(gòu)造一個空的線性表L。初始化操作InitList(&L)操作結(jié)果：構(gòu)造一個空的線性表L116

結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：操作結(jié)果：線性表L已存在。銷毀線性表L。結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：線117ListEmpty(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())引用型操作:ListEmpty(L)ListLength(L)P118

ListEmpty(L)初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）ListEmpty(L)初始條件：線性表L已存在。若L119ListLength(L)初始條件：操作結(jié)果：線性表L已存在。返回L中元素個數(shù)。（求線性表的長度）ListLength(L)初始條件：線性表L已存在。返回120

PriorElem(L,cur_e,&pre_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。（求數(shù)據(jù)元素的前驅(qū)）PriorElem(L,cur_e,&pre_e)121NextElem(L,cur_e,&next_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數(shù)據(jù)元素的后繼）NextElem(L,cur_e,&next_e)初122GetElem(L,i,&e)

初始條件：

操作結(jié)果：線性表L已存在，且1≤i≤LengthList(L)。用

e返回L中第i

個元素的值。（求線性