線性表的操作講解

內(nèi)容提要了解線性表的定義。掌握線性表的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及相關(guān)的基本操作算法描述。了解雙向鏈表存儲(chǔ)結(jié)構(gòu)。

第二章線性表Knowledge第二章線性表線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集。線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)，稱為直接前驅(qū)（ImmediatePredecessor）。除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼，稱為直接后繼（ImmediateSuccessor）。2.1線性表的類型定義一、定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列例：英文字母表（A,B,C,…..Z)是一個(gè)線性表例：數(shù)據(jù)元素二、線性表的特征：元素個(gè)數(shù)n稱為表長(zhǎng)度，n=0，稱為空表1<i<n時(shí)ai的直接前驅(qū)是ai－1，a1無直接前驅(qū)ai的直接后繼是ai＋1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項(xiàng)三、線性表抽象數(shù)據(jù)類型的定義

ADT

List{

數(shù)據(jù)對(duì)象:D={ai|aiElemSet,i=1,2,...,n,n0}

數(shù)據(jù)關(guān)系:

R1={<ai－1,ai>|ai－1,aiD,i=1,2,...,n}

基本操作：&符號(hào)說明函數(shù)參數(shù)是引用型

InitList(&L)

DestroyList(&L)

ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e)

PutElem(&L,i,e) LocateElem(L,e) PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e)

ListInsert(&L,i,e)ListDelete(&L,i,&e) ListTraverse(L,visit())}⑴線性表初始化：

InitList(&L)；

—構(gòu)造一個(gè)空的線性表L，即表的初始化。⑵求線性表的長(zhǎng)度：ListLength(L)；

—返回線性表中數(shù)據(jù)元素的個(gè)數(shù)，即表長(zhǎng)。⑶取表中元素：GetElem(L,i,&e)；

—取線性表L中的第i個(gè)結(jié)點(diǎn)，要求1≤i≤ListLength(L)⑷插入操作：ListInsert(&L,i,e)；

—在線性表L的第i個(gè)位置上插入一個(gè)值為e的數(shù)據(jù)元素。(5)刪除操作：ListDelete(&L,i,&e)；

—在線性表L中刪除位序?yàn)閕的數(shù)據(jù)元素。⑹按值查找：LocateElem(L,e)；

—在L中查找值為e的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在L中的位置。若L中有多個(gè)結(jié)點(diǎn)的值和e相同，則返回首次找到的結(jié)點(diǎn)位置；若L中沒有結(jié)點(diǎn)的值為e，則返回一個(gè)特殊值(如零)表示查找失敗。課后思考：應(yīng)用基本操作實(shí)現(xiàn)刪除線性表La中大于e的所有數(shù)據(jù)元素：DelElems(&L,e)CopyList(La,&Lb){//應(yīng)用基本操作：實(shí)現(xiàn)CopyList(La,&Lb)InitList(Lb)；

LenA=ListLength(La);for(i=1;i<=LenA;i++){GetElem(La,i,e);ListInsert(Lb,i,e);}}課堂練習(xí)：應(yīng)用基本操作實(shí)現(xiàn)CopyList(La,&Lb)例1:設(shè)計(jì)求A=A∪B的算法分析：建立線性表La、Lb分別表示集合A和B，將Lb中存在而La中不存在的元素e插入La中，因此，本算法的基本操作是查找(比較)。算法思想：

1.從Lb中依次取得每個(gè)元素eGetElem(Lb,i,e)2.判斷該元素e是否在La中存在LocateElem(La,e)3.若不存在，則將元素e插入到La中ListInsert(La,i,e)基于邏輯結(jié)構(gòu)的算法描述：

voidUnion(&La,Lb){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：巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。算法思想：1、初始化：設(shè)LC為空表，設(shè)置變量i，j的初值為1，分別指向LA，LB的第一個(gè)DE，設(shè)K表示LC的表長(zhǎng)，初值為0Init_List(LC)2、當(dāng)i≤

Length_List(LA)&&j≤

Length_List(LB)判斷：若i所指元素≤

j所指元素，則將i所指元素插入在LC的k+1前(即LC的表尾)，且i、k的值分別+1;否則，將j所指元素插入在LC的k+1前(即LC的表尾)，且j、k的值分別+1;3、重復(fù)2，直到某個(gè)表LA或LB的元素插入完畢；4、將未插入完的表LA或LB的余下元素，依次插入LC中。2.2

線性表的順序表示和實(shí)現(xiàn)一、順序表（SequentialList）1、定義：用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表叫~2、元素地址計(jì)算方法：LOC(ai)＝LOC(a1)+(i－1)*LLOC(ai+1)＝LOC(ai)＋L其中：L—一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù)LOC(ai)—線性表第i個(gè)元素的地址3、順序表的特點(diǎn)：實(shí)現(xiàn)邏輯上相鄰—物理地址相鄰實(shí)現(xiàn)隨機(jī)存取4、順序表的實(shí)現(xiàn)：可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號(hào)M-1#defineList_Init_Size100typedef

intElemType;typedefElemTypeET;typedef

struct{ElemType*elem; //動(dòng)態(tài)空間基址

intlength; //實(shí)際元素個(gè)數(shù)

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

//(以sizeof(ElemType)為單位)

}SqList;

備用空間聲明結(jié)構(gòu)體類型，

SqList是順序表的類型名動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存空間L.elem=(ElemType*)malloc(List_Init_Size*sizeof(ElemType));//申請(qǐng)內(nèi)存free(L.elem);//釋放內(nèi)存typedefstruct{

ElemType*elem;

int

length;

int

listsize;

}SqList;

intListLength_Sq(SqListL){……}voidClearList_Sq(SqList&L){……}訪問順序表L中第3個(gè)元素：L.elem[2]e=L.elem[2];L.elem[2]=8;…GetElem_Sq(SqListL,inti,ElemType&e){……}525L5個(gè)有效數(shù)據(jù)25個(gè)元素存儲(chǔ)空間L表的基址（數(shù)組名）是L.elem關(guān)于數(shù)據(jù)類型名Status★Status是“狀態(tài)”的意思，不是C語(yǔ)言中的關(guān)鍵字，其目的是為了增強(qiáng)算法的“可讀性”★typedefintStatus;★Status型的數(shù)據(jù)范圍是:True、False、Ok、Error #defineTrue1 #defineFalse0 StatusListEmpty(SqListL){ //判斷線性表L是否為空表

if(L.length==0)returnTrue;returnFalse;}順序表基本操作的算法描述//構(gòu)造一個(gè)空的線性表L#defineList_Init_Size10//存儲(chǔ)空間的初始分配量#defineListIncrement10//存儲(chǔ)空間的分配增量Status

InitList_Sq(SqList&L){L.elem=(ET*)malloc(List_Init_Size*sizeof(ET));

if(L.elem==NULL)

exit(OVERFLOW);/*存儲(chǔ)分配失敗*/L.length=0;/*空表的長(zhǎng)度*/L.listsize=List_Init_Size;/*初始存儲(chǔ)容量*/

returnOK;}添加（1，3，5，7，9）之后的狀態(tài)：創(chuàng)建空表之后，表L的狀態(tài)如下：L.010244121357110310個(gè)元素存儲(chǔ)空間刪除第3個(gè)元素之后的狀態(tài)：410L.

1

3

7

9

957110310個(gè)元素存儲(chǔ)空間是隨機(jī)數(shù)據(jù)也就是無效數(shù)據(jù)順序表的內(nèi)存狀態(tài)

問題：在表的第1個(gè)位置插入6之后，表L的存儲(chǔ)狀態(tài)如何？問題：清空L,即ClearList_Sq(L)之后，表L的存儲(chǔ)狀態(tài)如何？510L.

1

3

5

7

957110310個(gè)元素存儲(chǔ)空間添加（1，3，5，7，9）之后的狀態(tài)：510L.

1

3

5

7

910個(gè)元素存儲(chǔ)空間創(chuàng)建空表之后，表L的狀態(tài)如下：L.01010個(gè)元素存儲(chǔ)空間刪除第3和第4個(gè)元素之后的狀態(tài)：310L.

1

3

910個(gè)元素存儲(chǔ)空間將隨機(jī)數(shù)據(jù)想象成空白順序表的內(nèi)存想象狀態(tài)結(jié)論：凡是定義的或動(dòng)態(tài)申請(qǐng)的空間內(nèi)，都想象為空白。如:intx,A[900];SqListL;ElemType*elem;二、順序表的插入操作

定義：順序表的插入是指在第i個(gè)（1in+1）元素之前插入一個(gè)新的數(shù)據(jù)元素x，使長(zhǎng)度為

n的線性表

變成長(zhǎng)度為

n+1的線性表

需將第i至第n共（n－i＋1)個(gè)元素依次后移一個(gè)位置。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1an-1x順序表的插入操作在順序表L中第i個(gè)位置上插入一個(gè)新的元素e,●形式參數(shù)為：&L,i,e

；●算法步驟如下：

(1)對(duì)輸入?yún)?shù)的安全性檢查:

插入位置i應(yīng)落在表長(zhǎng)＋１范圍內(nèi)，即：1iL.length+1

(2)存儲(chǔ)空間的處理：若原表的存儲(chǔ)空間已滿，應(yīng)追加存儲(chǔ)空間的分配；

(3)數(shù)據(jù)塊的搬移：將表中從i到L.length位置上的所有元素依次往后移動(dòng)一個(gè)位置；

(4)在第i個(gè)位置上存儲(chǔ)新的元素e,表長(zhǎng)增１，即++L.length

。注意：邏輯位置（序號(hào)）i對(duì)應(yīng)的存儲(chǔ)下標(biāo)是i-1。重新分配動(dòng)態(tài)存儲(chǔ)空間的函數(shù)realloc(原動(dòng)態(tài)區(qū)首址，字節(jié)數(shù))★其功能為：(1)申請(qǐng)新的動(dòng)態(tài)存儲(chǔ)空間(成功或失敗);(2)將原動(dòng)態(tài)區(qū)的數(shù)據(jù)拷貝到新動(dòng)態(tài)區(qū);(3)釋放原動(dòng)態(tài)存儲(chǔ)區(qū);(4)返回新存儲(chǔ)區(qū)首地址（無類型）?！镉猛荆寒?dāng)原動(dòng)態(tài)存儲(chǔ)區(qū)不夠用時(shí)，追加動(dòng)態(tài)存儲(chǔ)區(qū)；順序表的插入操作算法描述之一StatusListInsert_Sq(SqList&L,inti,ETe){

if

(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，增加分配

p=(ET*)realloc(L.elem,(L.listsize+ListIncrement)*sizeof(ET));if(p==NULL)exit(OVERFLOW);//存儲(chǔ)分配失敗

L.elem=p;//新的基地址

L.listsize+=ListIncrement;//增加存儲(chǔ)容量

}

for(j=L.length;j>=i;--j)L.elem[j]=L.elem[j-1];//移動(dòng)元素

L.elem[j]=e;//插入新元素

++L.length;//表長(zhǎng)增1

returnOK;}StatusListInsert_Sq(SqList&L,inti,ETe){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.listsize){p=(ET*)realloc(L.elem,(L.listsize+ListIncrement)*sizeof(ET));

if(p==NULL)exit(OVERFLOW);L.elem=p;L.listsize+=ListIncrement;}q=&(L.elem[i-1]);/*q=L.elem+(i-1)為插入位置*/

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;/*移動(dòng)元素*/*q=e; /*插入新元素*/++L.length;/*表長(zhǎng)增1*/returnOK;}順序表的插入操作算法描述之二順序表插入操作的算法評(píng)價(jià)設(shè)Pi是在第

i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：三、順序表的刪除操作

定義：線性表的刪除是指將第i（1in）個(gè)元素刪除，使長(zhǎng)度為n的線性表

變成長(zhǎng)度為n-1的線性表

需將第i+1至第n共（n－i)個(gè)元素依次前移一個(gè)位置。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號(hào)i+1n-1nanai+2

順序表的刪除操作刪除順序表L中第i個(gè)位置上的元素，將刪除的元素值賦給e。●形式參數(shù)為：&L,i,&e

●算法步驟如下：

(1)對(duì)輸入?yún)?shù)的安全性檢查:刪除位置i

應(yīng)落在表長(zhǎng)范圍內(nèi)，即：1iL.length

；

(2)取出刪除的元素值賦給e；

(3)數(shù)據(jù)塊的搬移：將表L中從i+1到L.length位置上的所有元素往前移動(dòng)一個(gè)位置；

(4)表長(zhǎng)減１：--L.length

。順序表的刪除操作算法描述一StatusListDelete_Sq(SqList&L,inti,ET&e){if(i<1||i>L.length)returnERROR;//i值不合法

e=L.elem[i-1];//被刪除元素的值賦給efor(j=i;j<L.length;j++)L.elem[j-1]=L.elem[j];//移動(dòng)元素

--L.length;//表長(zhǎng)減1

returnOK;}順序表的刪除操作算法描述二StatusListDelete_Sq(SqList&L,inti,ET&e){if(i<1||i>L.length)returnERROR;//i值不合法

p=&(L.elem[i-1];)//p為被刪除元素的位置

e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//q為表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p; //移動(dòng)元素

--L.length;//表長(zhǎng)減1returnOK;}順序表刪除操作的算法評(píng)價(jià)設(shè)Qi

是刪除第i個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個(gè)元素時(shí)，平均約移動(dòng)表中一半元素，當(dāng)n很大時(shí)，效率很低。順序表的定位操作●算法要求：在順序表L中，查找第1

個(gè)值與數(shù)值e

相等的元素的位序。若找到，返回其在L中的位序，否則，返回0；●算法描述：

intLocateElem_Sq(SqList

L

,ET

e){

請(qǐng)?zhí)顚懰惴枋觯?/p>

}●算法分析：基本操作是什么？時(shí)間復(fù)雜度是多少？StatusGetElem_Sq(SqListL,inti,ET&e){

if(i<1||i>L.length||!L.elem)returnERROR;

e=L.elem[i-1];returnOK;}●算法轉(zhuǎn)換為C語(yǔ)言子程序的規(guī)則：引用型改為指針型StatusGetElem_Sq(SqListL,inti,ET*e){if(i<1||i>L.length||!L.elem)returnERROR;

*e=L.elem[i-1];returnOK;}順序表的取值操作順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充1．編寫程序?qū)崿F(xiàn)順序表的下列基本操作：(1)初始化順序表La。(2)將La置為空表。(3)銷毀La。(4)在La中插入一個(gè)新的元素。(5)刪除La中的某一元素。(6)在La中查找某元素，若找到，則返回它在La中第一次出現(xiàn)的位置，否則返回0。(7)打印輸出La中的元素值。上機(jī)作業(yè)1——順序表基本操作（2學(xué)時(shí)）能力培養(yǎng)：通過實(shí)現(xiàn)順序表的基本操作和具體的函數(shù)定義，掌握程序的輸入、編輯、調(diào)試和運(yùn)行過程。PracticeEngineering2．編寫程序完成下面的操作：(1)構(gòu)造兩個(gè)順序線性表La和Lb，其元素都按值非遞減順序排列。(2)實(shí)現(xiàn)歸并La和Lb得到新的順序表Lc，Lc的元素也按值非遞減順序排列。(3)假設(shè)兩個(gè)順序線性表La和Lb分別表示兩個(gè)集合A和B，利用union_Sq操作實(shí)現(xiàn)A=AB。上機(jī)作業(yè)1——順序表基本操作（續(xù)）能力培養(yǎng)：訓(xùn)練學(xué)生通過順序表的一些基本操作來解決實(shí)際問題的能力。EngineeringPractice2.3

線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)結(jié)點(diǎn)，除存儲(chǔ)元素ai本身信息外，還需存儲(chǔ)其直接后繼元素ai+1的地址信息結(jié)點(diǎn) （Node）數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域指針域結(jié)點(diǎn)ZHAOQIANSUNLIZHOUWUZHENGWANG^H例：線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針2、實(shí)現(xiàn)：typedefstructNode{

ElemType

data;structNode*next;}LNode,*LinkList; //Lnode是結(jié)點(diǎn)類型名，

//LinkList是結(jié)點(diǎn)指針類型名

LinkListL;LNode*p;datanextL結(jié)點(diǎn)(*p)(*p)表示p所指向的結(jié)點(diǎn)(*p).datap

data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).nextp

next表示p指向結(jié)點(diǎn)的指針域生成一個(gè)LNode型新結(jié)點(diǎn)：p=(LNode*)malloc(sizeof(LNode));

或：p=(LinkList)malloc(sizeof(LNode));系統(tǒng)回收p結(jié)點(diǎn)：free(p)一、線性鏈表1、定義：每個(gè)結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫單鏈表(SingleLinkedList)頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)加一個(gè)結(jié)點(diǎn)叫～頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空表。La1a2頭結(jié)點(diǎn)an^…...L空表^★頭指針L是LinkList類型，頭結(jié)點(diǎn)是Lnode類型非空表：空表：

注意：頭結(jié)點(diǎn)的位序?yàn)?，它不是線性表中的元素，頭結(jié)點(diǎn)的數(shù)據(jù)域可用于存儲(chǔ)線性表的長(zhǎng)度?！飭捂湵硎欠请S機(jī)存取的存儲(chǔ)結(jié)構(gòu)

在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間沒有固定的聯(lián)系，每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的指針域中。在單鏈表中，要取得第i個(gè)數(shù)據(jù)元素必須從頭結(jié)點(diǎn)出發(fā)尋找。頭5836^L頭^LStatusInitList_L(LinkList&L){L=(LinkList)malloc(sizeof(Lnode));if(L==NULL)exit(OVERFLOW);

/*Ldata=0;*/Lnext=NULL; returnOK;}

★時(shí)間復(fù)雜度：O(1)L必須是引用型構(gòu)造一個(gè)空的單鏈表的算法描述1.指針p在鏈表上依次滑動(dòng)：p=head;while(pnext!=NULL){p=pnext;}2.前驅(qū)指針q和當(dāng)前指針p在鏈表上同步滑動(dòng)：

q=head;p=qnext;

while(p){q=p;p=qnext;}

例1：intListLength_L(LinkListL)//求線性表的長(zhǎng)度

{p=L;j=0;

while(pnext!=NULL)

或while(pnext)

{++j;p=pnext;}

return(j);}例2：StatusPriorElem_L(LinkListL,ETe,ET&pre){q=L;p=qnext;

while(p&&pdata!=e)

{q=p;p=qnext;}…}例3：

StatusNextElem_L(LinkListL,ETe,ET&next){…}單鏈表算法中的關(guān)鍵步驟的算法描述單鏈表的基本運(yùn)算—查找★在單鏈表L中，讀取第i個(gè)元素的值賦給參數(shù)eStatus

GetElem_L(LinkListL,inti,ElemType&e) {p=Lnext;j=1; //j為計(jì)數(shù)器

while(p&&j<i) //查找第i個(gè)元素

{p=pnext;++j;}if(!p||j>i)或if(p==NULL||j>i)

//第i個(gè)元素不存在

returnERROR;e=pdata;

//取出第i個(gè)元素的值賦給e

returnOK;}

★時(shí)間復(fù)雜度為：O(n)

★問題：在順序表中GetElem_Sq時(shí)間復(fù)雜度是多少？★在單鏈表L中的第i個(gè)結(jié)點(diǎn)之前插入元素e的操作步驟：

(1)尋找第i-1個(gè)結(jié)點(diǎn)； //O(n)(2)測(cè)試已知量的合法性； //O(1)(3)申請(qǐng)一個(gè)新結(jié)點(diǎn)，并給其數(shù)據(jù)域賦值為e；//O(1)(4)新結(jié)點(diǎn)插入到單鏈表L中的第i個(gè)結(jié)點(diǎn)之前。//O(1)

★該算法的時(shí)間復(fù)雜度是：O(n)單鏈表的基本運(yùn)算—插入pai-1aies

snext=pnext;

pnext=s;

StatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=0; //j為計(jì)數(shù)器

while(p&&j<i－1) //尋找第i－1個(gè)結(jié)點(diǎn)，令p指向它

{p=pnext;++j;}if(!p||j>i－1) 或者if(p==NULL||j>i－1)returnERROR; //i大于表長(zhǎng)+1或者i小于1s=(LinkList)malloc(sizeof(Lnode));//申請(qǐng)新結(jié)點(diǎn)sif(s==NULL)exit(OVERFLOW);sdata=e;

snext=pnext;

//在p結(jié)點(diǎn)之后插入新結(jié)點(diǎn)s

pnext=s;

returnOK;}單鏈表的基本運(yùn)算—插入★在單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，并由e返回其值的操作步驟：

(1)尋找第i-1個(gè)結(jié)點(diǎn)； //O(n)(2)測(cè)試已知量的合法性； //O(1)(3)刪除第i個(gè)結(jié)點(diǎn)，并取出數(shù)據(jù)域的值賦給e；//O(1)(4)釋放第i個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。//O(1)

★該算法的時(shí)間復(fù)雜度是：O(n)單鏈表的基本運(yùn)算—?jiǎng)h除pai-1aiai+1pnext=qnext;qStatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=0; //j為計(jì)數(shù)器

while(pnext&&j<i－1)//尋找第i－1個(gè)結(jié)點(diǎn)，由p指向它

{p=pnext;j++;}if(!(pnext)||j>i－1)//i大于表長(zhǎng)或者i小于1returnERROR;q=pnext; //q指向要?jiǎng)h除的結(jié)點(diǎn)aipnext=qnext;

//刪除結(jié)點(diǎn)aie=qdata;free(q); //釋放結(jié)點(diǎn)ai的存儲(chǔ)空間

returnOK;}單鏈表的基本運(yùn)算—?jiǎng)h除★逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表L?！锼惴ㄔu(píng)價(jià)：T(n)＝O(n)L頭結(jié)點(diǎn)an^0L頭結(jié)點(diǎn)an-10an^a2…...L頭結(jié)點(diǎn)an-10an^La1a2頭結(jié)點(diǎn)an^…...0L頭結(jié)點(diǎn)0^動(dòng)態(tài)建立單鏈表的算法—逆向建立VoidCreateList_L(LinkList&L,intn)//建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表L{L=(LinkList)malloc(sizeof(Lnode));//L指向頭結(jié)點(diǎn)

Lnext=NULL;

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode));//p為新結(jié)點(diǎn)

scanf(&pdata); //為結(jié)點(diǎn)p的數(shù)據(jù)域賦值

pnext=Lnext;

//為結(jié)點(diǎn)p的指針域賦值

Lnext=p;//將結(jié)點(diǎn)p插入到表頭

}}

動(dòng)態(tài)建立單鏈表的算法—逆向建立★單鏈表特點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用不需預(yù)先分配空間，分配的空間連續(xù)與否均可指針占用額外存儲(chǔ)空間不能隨機(jī)存取，查找速度慢，便于插入、刪除操作線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)操作上的比較順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)循環(huán)控制變量下標(biāo)變量i指針變量p初始化i=0；p=head;或p=head->next;循環(huán)條件i<n(表長(zhǎng)length)P!=NULL處理對(duì)象a[i]*p（p->data）（p->next）下一對(duì)象i++;p=p->next;1．編寫程序?qū)崿F(xiàn)單鏈表的下列基本操作：(1)初始化單鏈表La。(2)在單鏈表La中插入一個(gè)新結(jié)點(diǎn)。(3)刪除單鏈表La中的某一個(gè)結(jié)點(diǎn)。(4)在單鏈表La中查找某結(jié)點(diǎn)并返回其位置。(5)打印輸出單鏈表La中的結(jié)點(diǎn)元素值。2．構(gòu)造兩個(gè)帶有表頭結(jié)點(diǎn)的有序單鏈表La、Lb，編寫程序?qū)崿F(xiàn)將La、Lb合并成一個(gè)有序單鏈表Lc。上機(jī)作業(yè)2——單鏈表基本操作（2學(xué)時(shí)）能力培養(yǎng)：掌握對(duì)單鏈表的一些基本操作和具體的函數(shù)定義，通過實(shí)現(xiàn)兩個(gè)有序表歸并，訓(xùn)練單鏈表的一些基本操作。EngineeringPractice二、循環(huán)鏈表(CircularLinkedList)循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成一個(gè)環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高了查找效率循環(huán)鏈表操作與單鏈表基本一致，循環(huán)結(jié)束條件不同單鏈表L：pnext==NULL循環(huán)鏈表L：pnext==L非空循環(huán)鏈表空循環(huán)鏈表頭5836L頭L僅設(shè)尾指針的兩循環(huán)鏈表的鏈接AB存儲(chǔ)池p①②③④Void*Connect(LinkList&A,LinkList&B){LinkList*p;p＝A->next;A->next＝B->next->next;free(B->next);B->next＝p;}

僅設(shè)尾指針的兩循環(huán)鏈表的鏈接算法三、雙向鏈表（DoubleLinkedList）單鏈表具有單向性的缺點(diǎn),所以引入雙向鏈表。結(jié)點(diǎn)定義typedefstructDuLNode{ElemType data;structDuLNode*prior,*next;}DuLNode,*DuLinkList;priordatanextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABaiai+1ai-1pp

prior

next=p=p

next

proir;★算法評(píng)價(jià)：T(n)=O(n)eSaiai-1P★插入操作★算法描述StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_DuL(L,i)))//確定第i個(gè)元素的位置指針preturnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnError;sdata=e;sprior=pprior; ppriornext=s;snext=p;pprior=s;returnOK;}

sprior=pprior;

ppriornext=s;snext=p;pprior=s;aiai+1ai-1P★刪除操作★算法評(píng)價(jià)：T(n)=O(n)ppriornext=pnext;p

next

prior=p

prior;★算法描述StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_DuL(L,i)))//確定第i個(gè)元素的位置指針preturnERROR;e=pdata;ppriornext=pnext;pnextprior=pprior;