線性表（福建教師招考信息技術(shù)算法和程序部分）課件

第二章線形表第二章線形表11、線性表(LinearList)：定義：由n(n≧0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。記作：L=(a1，a2，…ai-1，ai，ai+1，…an)其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機(jī)擁有量的變化情況。（6，17，28，50，92，188）1、線性表(LinearList)：定義：2例3、學(xué)生健康情況登記表如下：例4、一副撲克的點數(shù)（2，3，4，…，J，Q，K，A）姓名學(xué)號性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….例3、學(xué)生健康情況登記表如下：姓名學(xué)號性3線性表——元素及元素之間的關(guān)系為線性線性：（1）有且僅有一個開始節(jié)點（該節(jié)點只有一個后繼節(jié)點，沒有前趨節(jié)點）（2）有且僅有一個結(jié)束節(jié)點（該節(jié)點只有一個前趨節(jié)點，沒有后繼節(jié)點）（3）除首節(jié)點，其余節(jié)點有且僅有一個前趨k1k2k3k4k1k2k3（4）除尾節(jié)點，其余節(jié)點有且僅有一個后繼數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進(jìn)行的。線性表——元素及元素之間的關(guān)系為線性（1）有且僅有一個開始4線性表的類型定義抽象數(shù)據(jù)類型線性表的定義

ADTList{數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

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

{結(jié)構(gòu)銷毀} DestroyList(&L) 初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表L。

{引用型操作} ListEmpty(L) 初始條件：線性表L已存在。 操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。 ListLength(L) 初始條件：線性表L已存在。 操作結(jié)果：返回L中元素個數(shù)。線性表的類型定義抽象數(shù)據(jù)類型線性表的定義ADTList5ADTList

GetElem(L,i,&e) 初始條件：線性表L已存在，1≤i≤LengthList(L) 操作結(jié)果：用e返回L中第i個元素的值。 LocateElem(L,e,compare()) 初始條件：線性表L已存在，compare()是元素判定函數(shù)。 操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的元素的位序。若這樣的元素不存在，則返回值為0。 PriorElem(L,cur_e,&pre_e) 初始條件：線性表L已存在。 操作結(jié)果：若cur_e是L的元素，但不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。 NextElem(L,cur_e,&next_e) 初始條件：線性表L已存在。 操作結(jié)果：若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼， 否則操作失敗，next_e無定義。 ListTraverse(L,visit()) 初始條件：線性表L已存在。 操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADTList GetElem(L,i,&e)6ADTList {加工型操作} ClearList(&L) 初始條件：線性表L已存在。 操作結(jié)果：將L重置為空表。 PutElem(L,i,&e) 初始條件：線性表L已存在，1≤i≤LengthList(L) 操作結(jié)果：L中第i個元素賦值同e的值。 ListInsert(&L,i,e) 初始條件：線性表L已存在，1≤i≤LengthList(L)+1 操作結(jié)果：在L的第i個元素之前插入新的元素e，L的長度增1。 ListDelete(&L,i,&e) 初始條件：線性表L已存在且非空，1≤i≤LengthList(L) 操作結(jié)果：刪除L的第i個元素，并用e返回其值，L的長度減1。}ADTListADTList {加工型操作}7舉例假設(shè)線性表L=(23,56,89,76,18),i=3,x=56,y=88,則對L的一組操作及結(jié)果如下：ListLength(L)//所得結(jié)果為5GetElem(L,i,&e)//所得結(jié)果為89PriorElem(L,x,&pre_e)//所得結(jié)果為23NextElem(L,x,&next_e) //所得結(jié)果為89LocateElem(L,x,equal) //所得結(jié)果為2ListInsert(&L,i,y)//所得結(jié)果為(23,56,88,89,76,18)ListDelete(&L,i+1,&e) /所得結(jié)果為(23,56,88,76,18)89舉例假設(shè)線性表L=(23,56,89,76,18),8如何實現(xiàn)線性表的其它操作例2-1利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=A∪B。設(shè)計思想： 擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。分下列三步進(jìn)行：1．從線性表LB中依次取得每個數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在，則插入之。如何實現(xiàn)線性表的其它操作例2-1利用兩個線性表LA9A=A∪B算法描述：//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中voidUnion(List&La，ListLb){ //求線性表的長度La-len=ListLength(La);Lb-len=ListLength(Lb);for(i=1;i<=Lb-len;i++){

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

//La中不存在和e相同的數(shù)據(jù)元素，則插入之 if(!LocateElem(La，e，equal)) ListInsert(La，++La-en，e); }}//UnionA=A∪B算法描述：10A=A∪B時間復(fù)雜度分析：GetElem取遍Lb表元素需Lb_len=ListLength(Lb)次；循環(huán)體內(nèi)的Locate操作平均需ListLength(La)次 最壞情況為：ListLength(La)總的時間復(fù)雜度： O[ListLength(Lb)*ListLength(La)]A=A∪B時間復(fù)雜度分析：11例2-1-2已知一個非純集合B，試構(gòu)造集合A，要求集合A中只包含集合B中所有值不相同的數(shù)據(jù)元素。設(shè)計思想：解法一： 同上例，分別以線性表LA和LB表示集合A和B，則首先初 始化線性表LA為空表，之后的操作和例2-1完全相同。解法二： 仍以線性表表示集合。只是求解之前先對線性表LB中的 數(shù)據(jù)元素進(jìn)行排序，即線性表LB中的數(shù)據(jù)元素依其值從 小到大有序排列，則值相同的數(shù)據(jù)元素必相鄰。則上述 操作中的第二步就不需要進(jìn)行從頭至尾的查詢。

例2-1-2已知一個非純集合B，試構(gòu)造集合A，要求集合A12A=Bvoidpurge(List&La,ListLb){//已知線性表Lb中的數(shù)據(jù)元素依值非遞減有序排列，現(xiàn)構(gòu)造線性表La，//使La中只包含Lb中所有值不相同的數(shù)據(jù)元素 InitList（La）；//初始化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(ListEmpty(La)||!equal(en，e)) ListInsert(La,++La_len,e); //La中不存在和e相同的數(shù)據(jù)元素，則插入之 en=e;//en，La中的已插入元素 }//for}//purgeA=Bvoidpurge(List&La,List13A=B時間復(fù)雜度分析：GetElem取遍Lb表元素需Lb_len=ListLength(Lb)次；解法一: 循環(huán)體內(nèi)的Locate操作平均需ListLength(Lb)次 故時間復(fù)雜度為：O(ListLength2(LB))；

解法二的時間復(fù)雜度： 循環(huán)體內(nèi)的基本操作與表長無關(guān) 故時間復(fù)雜度為： O(ListLength(Lb))A=B時間復(fù)雜度分析：14C=A∪B例2-2巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。設(shè)計思想：1、LC為空表，用來存放LA和LB的元素2、表LA和LB的元素逐一進(jìn)行比較取小者放入表LC中3、插入表LA或表LB中剩余的元素C=A∪B例2-2巳知線性表LA和線性表LB中的15算法描述：//已知線性表La和Lb中的元素按值非遞減排列。//歸并La和Lb得到新的線性表Lc，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)) { //La和Lb均非空 GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai<=bj) { ListInsert(Lc,++k,ai); ++i; } else { ListInsert(Lc,++k,bj); ++j; } }算法描述：//已知線性表La和Lb中的元素按值非遞減排列16C=A∪B

while

(i<=La_len) { GetElem(La,i++,ai); ListInsert(Lc,++k,ai); }

while(j<=Lb_len) { GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj); }}//MergeListC=A∪B while(i<=La_len17C=A∪B時間復(fù)雜度分析：該算法中包含了三個WHILE語句，其中，第一個處理了某一張表的全部元素和另一張表的部分元素；后兩個WHILE循環(huán)只可能有一個執(zhí)行，用來完成將未歸并到LC中的余下部分元素插入到LC中?！安迦搿笔枪懒繗w并算法時間復(fù)雜度的基本操作，其語句頻度為：

LENGTH（LA）+LENGTH（LB）該算法的時間復(fù)雜度為：

O（LENGTH（LA）+LENGTH（LB））若LA和LB的元素個數(shù)為同數(shù)量級n，則該算法的時間復(fù)雜度為: O(n)C=A∪B時間復(fù)雜度分析：18線性表的順序表示和實現(xiàn)一、線性表的順序存儲結(jié)構(gòu)順序表：——線性表的順序存儲結(jié)構(gòu)把線性表的結(jié)點按邏輯順序（順序）依次存放在一組地址連續(xù)的存儲單元里。1、線性表的地址計算： 假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置（首地址）。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+l線性表的第i個數(shù)據(jù)元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(i-1)*l線性表的順序表示和實現(xiàn)一、線性表的順序存儲結(jié)構(gòu)19存儲示意：存儲示意：20線性表的順序存儲用數(shù)組實現(xiàn)線性表（順序存儲、順序表）線性表元素：a1、a2、a3、a4....數(shù)組元素：a[0]、a[1]、a[2]、a[3]線性關(guān)系：a1a2a3a4數(shù)組下標(biāo)大小注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是l.data[i-1]。線性表的順序存儲用數(shù)組實現(xiàn)線性表（順序存儲、順序表）線性關(guān)系21ElemType*getElem(intpos);//若1<=pos<=cursize,則返回指示第pos個元素//的位置;否則返回NULL

intLocation(ElemType&e);//返回其值和e所指元素值相同的數(shù)據(jù)元素在線性//表中的序號，若不存在這樣的數(shù)據(jù)元素，則返回0

//modification

voidclearList(void);StatusputElem(intpos,constElemType&e);//若1<=pos<=cursize,則修改線性表中第pos個數(shù)//據(jù)元素的值，并且返回OK;否則不進(jìn)行修改并返//回ERRORStatusInsert(intpos,constElemType&e);//若1<=pos<=cursize+1,則插入元素e在線性表//中第pos個數(shù)據(jù)元素之前，并且返回OK;否則不//進(jìn)行插入并返回ERRORStatus*Delete(intpos,ElemType&e);//若1<=pos<=cursize,則刪除并返回指示第pos//個數(shù)據(jù)元素的位置，否則返回NULL}

classSqList{

private

constMAXLISTSIZE=100

protectedElemType*elemPtr;

intcursize;

public//constructorSqList(intsize=MAXLISTSIZE);//destructor~SqList(){delete[]elemPtr;}

//accessmethod

intEmpty(void)const;{return(cursize==0)}

intLength(void)const;{returncursize}使用C++進(jìn)行定義線性表的順序存儲：ElemType*getElem(intpos);cl22線性表的順序表示和實現(xiàn)2、動態(tài)存儲：分配策略：預(yù)分配一段空間，固定長度設(shè)定增量當(dāng)線性表空間滿，則按增量增加空間，動態(tài)調(diào)整3、數(shù)據(jù)類型：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefstruc{ ElemType*elem; intlength; intlistsize;}SqList;使用數(shù)組來描述線性表的順序表示和實現(xiàn)2、動態(tài)存儲：使用數(shù)組來描述23二、基本操作的實現(xiàn)：1、初始化——IniList_Sq(SqList&L見P23算法2.32、插入操作：ListInset(L,i,e)3、刪除操作：deleteList(Sqlist*L，inti)二、基本操作的實現(xiàn)：24構(gòu)造函數(shù)（初始化）SqList::SqList(intsize){

//構(gòu)造一個空的順序表size=(size>MAXLISTSIZE)?MAXLISTSIZE:size;elemPtr=newElemType[size];cursize=0;}構(gòu)造函數(shù)（初始化）SqList::SqList(int25插入示意：插入示意：26插入運算插入運算問題描述以a1開始的線性表中在第i個元素前插入一個新元素new_node。a1a2ai-1aian……a1a2ai-1newnodeai+1ai……anai+1插入運算插入運算a1a2ai-1aian……a1a2ai-127插入運算從ai開始向后移動從an開始向前每個元素向后移一格a1a2ai-1aiai+1......anaiaiaiaia1a2ai-1aiai+1…anan…ai+1aifor(j=i;j<L.length;j++){L.elem[j+1]=L.elem[j];}for(j=L.length;j>i;j--){L.elem[j+1]=L.elem[j];}newnode插入運算從ai開始向后移動a1a2ai-1aiai+1...28算法思想：①進(jìn)行合法性檢查，1<=i<=n+1；②利用線性表是否已滿；③將第n個至第i個元素逐一后移一個單元；④在第i個位置處插入新元素；⑤將表的長度加1。算法思想：29StatusListInsert_Sq(Sqlist&L，inti，ElemTypee){//在順序線性表L中第i個位置之前插入新的元素e//i的合法值為1≤i≤ListLength_Sq(L)+1if(i<1||i>L.length+1) returnERROR;//i值不合法 if(L.length>=L.ListSize) exit(overflow);for(i=L.length-1;i>=I-1;i--)L.elem[i+1]=L.elem[i];L.elem[I-1]=x;l.length++;}StatusListInsert_Sq(Sqlist30刪除示意：刪除示意：31anai刪除運算刪除運算問題描述：刪除第i個元素算法實現(xiàn)分析a1a2ai…anai－1a1a2ai－1ai+1…ananai+1anai刪除運算刪除運算a1a2ai…anai－1a1a2a32刪除運算算法實現(xiàn)分析從an開始向前逐個元素向前移動從ai＋1開始向后逐個元素向前移動a1a2ai+1ai…anai-1anananfor(i=L.length-1;i>i;i--){L.elem[i-1]=L.elem[i];}a1a2ai-1aiai+1…anfor(i=i;i<L.length-1;i++){L.elem[i]=L.elem[i+1];}刪除運算算法實現(xiàn)分析a1a2ai+1ai…anai-1ana33算法思想：①進(jìn)行合法性檢查，i是否滿足1<=i<=n；②判線性表是否已空，v.last=0；③將第i+1至第n個元素逐一向前移一個位置；④將表的長度減1。算法思想：34StatusListDelete_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;35考慮移動元素的平均情況:假設(shè)刪除第

i個元素的概率為,

則在長度為n

的線性表中刪除一個元素所需移動元素次數(shù)的期望值為：若假定在線性表中任何一個位置上進(jìn)行刪除的概率都是相等的，則移動元素的期望值為：考慮移動元素的平均情況:假設(shè)刪除第i個元素的概率36p2118307542568721183075L.length-10ppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)pp211830754256872137

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)利用順序表類實現(xiàn)線性表的其它操作intLocateElem_Sq(SqListL,E38例如：順序表23754138546217L.elemL.length=7L.listsizee=38pppppi12341850p可見，基本操作是，將順序表中的元素逐個和給定值e相比較。例如：順序表237541385439集合歸并：#include<iostream.h>#includeSqList.hSqListmerge(Sqlist&a,SqList&b){ElemType*ai,*bj;

intm=a.Length();

intn=b.Length();SqListc(m+n);

inti=1;

intj=1;

intk=c.Length();

while((i<=m)&&(j<=n)){ai=a.getElem(i);bj=b.getElem(j);

switch(compare(*ai,*bj)){

case–1:

case0:c.Insert(++k,ai);i++;

break;

case1:c.Insert(++k,bj);j++;

break;

default:;}//switch}//while利用順序表類實現(xiàn)線性表的其它操作集合歸并：while((i<=m)&&(j<=n))40while(i<=m){ai=a.getElem(i++);c.Insert(++k,ai);}while(j<=n){bj=b.getElem(j++);c.Insert(++k,bj);}returnc;}//mergewhile(i<=m)41線性表的鏈?zhǔn)酱鎯︽溄哟鎯Φ木€性表（鏈表）的定義1、鏈表的引入數(shù)組結(jié)構(gòu)的缺點:（1）在插入、刪除時要移動大量的結(jié)點（2）表的大小固定。 預(yù)先在申明數(shù)組時指定，無法更改原因：存放的連續(xù)性突破離散存放用指針來表示元素之間的關(guān)系。線性表的鏈?zhǔn)酱鎯︽溄哟鎯Φ木€性表（鏈表）的定義42線性表的鏈?zhǔn)酱鎯τ面湵韺崿F(xiàn)線性表（非連續(xù)存儲）線性表元素：a1、a2、a3、a4....鏈表鏈點線性關(guān)系：a1a2a3a4指針域，指針關(guān)系線性表的鏈?zhǔn)酱鎯τ面湵韺崿F(xiàn)線性表（非連續(xù)存儲）線性表元素：a43鏈表的定義1鏈表的定義結(jié)點datalink元素域指針域元素域（數(shù)據(jù)元素域）：存放一個數(shù)據(jù)元素。指針域（關(guān)系域）：存放指向下一個元素的指針 ——元素間的關(guān)系。元素域+指針域=結(jié)點（鏈點）鏈表的定義1鏈表的定義datalink元素域指針域元素域（44

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

+指針(指示后繼元素存儲位置)=

結(jié)點

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

稱作鏈表一、單鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。以45頭指針以線性表中第一個數(shù)據(jù)元素

的存儲地址作為線性表的地址，稱作線性表的頭指針頭結(jié)點a1a2…...an^頭指針

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

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

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

LinkListL；//L為單鏈表的頭指針二、結(jié)點和單鏈表的描述TypedefstructLNode{Lin47classNode{protected:ElemTypedata;//數(shù)據(jù)域Node*next;//指針域public://constructorNode(constElemTypeitem,Node*ptr=NULL);

//destructor~Node(void){}//accessmethodNode*nextNode(void)const;{returnnext;}//返回結(jié)點的后繼ElemType*info(void)const;{returndata;}//返回結(jié)點數(shù)據(jù)域的值//modificationmethodvoidinsertAfter(Node*p);//插入后繼結(jié)點Node*deleteAfter(void);//刪除并返回后繼結(jié)點};

//Node類的實現(xiàn)Node::Node(constElemTypeitem,Node*ptr=NULL){data=item;next=ptr;}voidNode::insertAfter(Node*p){//插入后繼結(jié)點

p>next=next;next=p;}Node*Node::deleteAfter(void){//刪除并返回后繼結(jié)點

Node*s=next;next=s>next;

returns;}classNode{//Node類的實現(xiàn)48L線性表的操作

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

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

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

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,51ai-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,52因此，在單鏈表中第i個結(jié)點之前進(jìn)行插入的基本操作為:

找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針?？梢?，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第i個結(jié)點之前插入元素，修改的是第i-1個結(jié)點的指針。因此，在單鏈表中第i個結(jié)點之前進(jìn)行插入的基本操作53StatusListInsert_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(LinkList54s=newLNode;

//生成新結(jié)點s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sps=newLNode;eai-1aiai-1sp55線性表的操作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)在鏈56

在單鏈表中刪除第

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

e=q->data;free(q);pq在單鏈表中刪除第i個結(jié)點的基本操作為:找到線性表中57StatusListDelete_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(LinkList58操作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):void59如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配60例如：逆位序輸入n個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。操作步驟：1、建立一個“空表”；2、輸入數(shù)據(jù)元素an，建立結(jié)點并插入；3、輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入；ananan-14、依次類推，直至輸入a1為止。如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。例如：操作步驟：1、建立一個“空表”；2、輸入數(shù)據(jù)元素an，61voidCreateList_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,62回顧2.1節(jié)中三個例子的算法，看一下當(dāng)線性表分別以順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)實現(xiàn)時，它們的時間復(fù)雜度為多少？回顧2.1節(jié)中三個例子的算法，看一下當(dāng)線性表分別以順序存63voidunion(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,equal())

ListInsert(La,++La_len,e);

}//for}//union控制結(jié)構(gòu)：基本操作：for循環(huán)GetElem,LocateElem和ListInsert當(dāng)以順序映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為:

O(ListLength(La)×ListLength(Lb))

當(dāng)以鏈?zhǔn)接诚駥崿F(xiàn)抽象數(shù)據(jù)類型線性表時為:

O(ListLength(La)×ListLength(Lb))例2-1算法時間復(fù)雜度

voidunion(List&La,ListLb)64voidpurge(List&La,ListLb){

InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);

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

GetElem(Lb,i,e);

if(ListEmpty(La)||

!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

}//for}//purge控制結(jié)構(gòu)：基本操作：for循環(huán)GetElem和ListInsert當(dāng)以順序映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為:

O(ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥崿F(xiàn)抽象數(shù)據(jù)類型線性表時為:

O(ListLength2(Lb))例2-2算法時間復(fù)雜度voidpurge(List&La,ListLb)65voidMergeList(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;}

}……控制結(jié)構(gòu)：基本操作：三個并列的while循環(huán)GetElem,ListInsert當(dāng)以順序映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為:

O(ListLength(La)+ListLength(Lb))當(dāng)以鏈?zhǔn)接诚駥崿F(xiàn)抽象數(shù)據(jù)類型線性表時為:

O(ListLength2(La)+ListLength2(Lb))例2-3算法時間復(fù)雜度voidMergeList(ListLa,ListL66用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題：

改進(jìn)鏈表的設(shè)置：1．單鏈表的表長是一個隱含的值；

1．增加“表長”、“表尾指針”和“當(dāng)前位置的指針”三個數(shù)據(jù)域；2．在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點的“位置”概念加強(qiáng)。2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。用上述定義的單鏈表實現(xiàn)線性表的操作時，改進(jìn)鏈表的設(shè)置：167四、一個帶頭結(jié)點的線性鏈表類型typedefstructLNode{//結(jié)點類型ElemTypedata;

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

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

//

釋放p所指結(jié)點四、一個帶頭結(jié)點的線性鏈表類型typedefstruct68typedefstruct

{//鏈表類型

Linkhead,tail;

//分別指向頭結(jié)點和

//最后一個結(jié)點的指針

intlen;

//指示鏈表長度

Linkcurrent;

//指向當(dāng)前被訪問的結(jié)點//的指針，初始位置指向頭結(jié)點}LinkList;typedefstruct{//鏈表類型69鏈表的基本操作:{結(jié)構(gòu)初始化和銷毀結(jié)構(gòu)}StatusInitList(LinkList&L);

//構(gòu)造一個空的線性鏈表L，其頭指針、

//

尾指針和當(dāng)前指針均指向頭結(jié)點，

//

表長為零。StatusDestroyList(LinkList&L);

//銷毀線性鏈表L，L不再存在。O(1)O(n)鏈表的基本操作:{結(jié)構(gòu)初始化和銷毀結(jié)構(gòu)}StatusIni70{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//

求表長StatusPrior(LinkListL);

//改變當(dāng)前指針指向其前驅(qū)StatusNext(LinkListL);

//改變當(dāng)前指針指向其后繼ElemTypeGetCurElem(LinkListL);

//返回當(dāng)前指針?biāo)笖?shù)據(jù)元素O(1)O(1)O(n)O(1)O(1){引用型操作}StatusListEmpty(Link71

StatusLocatePos(LinkListL,inti);

//改變當(dāng)前指針指向第i個結(jié)點StatusLocateElem(LinkListL,ElemTypee,

Status(*compare)(ElemType,ElemType));

//若存在與e滿足函數(shù)compare()判定關(guān)系的元

//素，則移動當(dāng)前指針指向第1個滿足條件的

//元素的前驅(qū)，并返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());

//

依次對L的每個元素調(diào)用函數(shù)visit()O(n)O(n)O(n)StatusLocatePos(LinkListL72

{加工型操作}StatusClearList(LinkList&L);

//重置L為空表StatusSetCurElem(LinkList&L,ElemTypee);

//更新當(dāng)前指針?biāo)笖?shù)據(jù)元素StatusAppend(LinkList&L,Links);

//在表尾結(jié)點之后鏈接一串結(jié)點StatusInsAfter(LinkList&L,Elemtypee);

//將元素e插入在當(dāng)前指針之后StatusDelAfter(LinkList&L,ElemType&e);

//刪除當(dāng)前指針之后的結(jié)點

O(1)O(n)

O(s)

O(1)

O(1){加工型操作}StatusC73StatusInsAfter(LinkList&L,ElemTypee){

//若當(dāng)前指針在鏈表中，則將數(shù)據(jù)元素e插入在線性鏈

//表L中當(dāng)前指針?biāo)附Y(jié)點之后,并返回OK;//否則返回ERROR。}//InsAfterif(!L.current)returnERROR;

if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;

if(L.tail=L.current)L.tail=s;L.current=s;returnOK;StatusInsAfter(LinkList&L,74StatusDelAfter(LinkList&L,ElemType&e){

//若當(dāng)前指針及其后繼在鏈表中，則刪除線性鏈表L中當(dāng)前//指針?biāo)附Y(jié)點之后的結(jié)點，并返回OK;否則返回ERROR。}//DelAfterif(!(L.current&&L.current->next))

returnERROR;q=L.current->next;L.current->next=q->next;if(L.tail=q)L.tail=L.current;e=q->data;FreeNode(q);returnOK;StatusDelAfter(LinkList&L,75

例一StatusListInsert_L(LinkListL,inti,ElemTypee){

//在帶頭結(jié)點的單鏈線性表L的第i個元素之前插入元素e}//ListInsert_L

利用上述定義的線性鏈表如何完成線性表的其它操作？if(!LocatePos(L,i-1))returnERROR;

//i值不合法，第i-1個結(jié)點不存在if(InsAfter(L,e))returnOK;//完成插入else

returnERROR;例一利用上述定義的線性鏈表如何完成76StatusMergeList_L(LinkList&Lc,LinkList&La,LinkList&Lb，int(*compare)(ElemType,ElemType))){

//歸并有序表La和Lb,生成新的有序表Lc,

//并在歸并之后銷毀La和Lb,

//compare為指定的元素大小判定函數(shù)……}//MergeList_L例二StatusMergeList_L(LinkList&L77if(!InitList(Lc))returnERROR;//存儲空間分配失敗while(!(a=MAXC&&b=MAXC)){

//La或Lb非空}……LocatePos(La,0);LocatePos(Lb,0);

//

當(dāng)前指針指向頭結(jié)點if(DelAfter(La,e))a=e;//取得La表中第一個元素aelsea=MAXC;//MAXC為常量最大值if(DelFirst(Lb,e))b=e;//取得Lb表中第一個元素belseb=MAXC;//a和b為兩表中當(dāng)前比較元素DestroyList(La);DestroyList(Lb);

//銷毀鏈表La和LbreturnOK;if(!InitList(Lc))returnER78

if((*compare)(a,b)<=0){

//a≤bInsAfter(Lc,a);

if(DelAfter(La,e1))a=e1;

elsea=MAXC;}else{

//a＞bInsAfter(Lc,b);

if(DelAfter(Lb,e1))b=e1;

elseb=MAXC;

}if((*compare)(a,b)<=0){79

1.雙向鏈表typedefstructDuLNode{ElemTypedata;

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

structDuLNode*prior;

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

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;五、其它形式的鏈表1.雙向鏈表typedefstructDuLNod80最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表a1a2…...an和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。2.循環(huán)鏈表最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表81雙向循環(huán)鏈表空表非空表a1a2…...an雙向循環(huán)鏈表空表非空表a1a282雙向鏈表的操作特點：“查詢”和單鏈表相同“插入”和“刪除”時需要同時修改兩個方向上的指針。雙向鏈表的操作特點：“查詢”和單鏈表相同“插入”和“刪除83ai-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-85ADT

Ordered_List{

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

S={xi|xiOrderedSet，i=1,2,…,n,n≥0}集合中任意兩個元素之間均可以進(jìn)行比較數(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ù)關(guān)系:R=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ù)基本操作：……Locat87(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在計算機(jī)中，可以用一個線性表來表示:P=(p0,p1,…，pn)但是對于形如

S(x)=1+3x10000–2x20000的多項式，上述表示方法是否合適？一元多項式在計算機(jī)中，可以用一個線性表來表示:但是對于形如一元多項式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)系：抽象數(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{抽象數(shù)據(jù)類型一元多項式的定義95

CreatPolyn(&P,m)

DestroyPolyn(&P)

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