線性表的操作講解

1、內(nèi)容提要內(nèi)容提要l了解線性表的定義。了解線性表的定義。l掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)以掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)以及相關(guān)的基本操作算法描述。及相關(guān)的基本操作算法描述。l了解雙向鏈表存儲結(jié)構(gòu)。了解雙向鏈表存儲結(jié)構(gòu)。 第二章第二章 線性表線性表&Knowledge第二章 線性表線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集。線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)，稱為直接前驅(qū)（Immediate Predecessor）。除最后一個外，集合中的每個數(shù)據(jù)元素

2、均只有一個后繼，稱為直接后繼（ Immediate Successor）。2.1 線性表的類型定義一、定義：一個線性表是n個數(shù)據(jù)元素的有限序列niaaaa,21如例： 英文字母表（A,B,C,.Z)是一個線性表例：學(xué)號姓名年齡001張三18002李四19數(shù)據(jù)元素二、線性表的特征：v元素個數(shù)n稱為表長度，n=0，稱為空表v1in時(shí)l ai的直接前驅(qū)是ai1，a1無直接前驅(qū)l ai的直接后繼是ai1，an無直接后繼v元素同構(gòu)，且不能出現(xiàn)缺項(xiàng)三、線性表抽象數(shù)據(jù)類型的定義ADT List 數(shù)據(jù)對象數(shù)據(jù)對象: D= ai | aiElemSet , i = 1,2,.,n, n 0數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: R

3、1= |a i1 ,a iD, i = 1,2,.,n 基本操作：& 符號說明函數(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( ) 線性表初始

4、化：線性表初始化： InitList(&L)InitList(&L)； 構(gòu)造一個空的線性表L，即表的初始化。 求線性表的長度：求線性表的長度：ListLength (L)ListLength (L)； 返回線性表中數(shù)據(jù)元素的個數(shù)，即表長 。 取表中元素：取表中元素：GetElem(L, i,&e)GetElem(L, i,&e)； 取線性表L中的第i個結(jié)點(diǎn)，要求1iListLength(L) 插入操作：插入操作：ListInsert (&L, i, e)ListInsert (&L, i, e)； 在線性表L的第i個位置上插入一個值為e的數(shù)據(jù)元素。(5)(5)刪除操作：刪除操作：ListDel

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

6、)/CopyList(La,&Lb)/應(yīng)用基本操作：實(shí)現(xiàn)應(yīng)用基本操作：實(shí)現(xiàn)CopyList(La,&Lb)CopyList(La,&Lb) InitList(Lb) InitList(Lb)； LenA=ListLength(La);LenA=ListLength(La); for(i=1;i=LenA;i+) for(i=1;i=LenA;i+) GetElem(La,i,e); GetElem(La,i,e); ListInsert(Lb,i,e); ListInsert(Lb,i,e); 課堂練習(xí)：課堂練習(xí)：應(yīng)用基本操作實(shí)現(xiàn)應(yīng)用基本操作實(shí)現(xiàn)CopyList(La,&Lb)CopyList

7、(La,&Lb)例例1:1:設(shè)計(jì)求設(shè)計(jì)求 A = AA = AB B 的算法的算法l分析：建立線性表分析：建立線性表 La、Lb分別表示集合分別表示集合A和和B，將，將Lb中存中存在而在而La中不存在的元素中不存在的元素e插入插入 La中，因此，中，因此，本算法的基本操本算法的基本操作是查找作是查找(比較比較)。算法算法思想思想： 1. 從從Lb中依次取得每個元素中依次取得每個元素e GetElem (Lb, i, e) 2. 判斷該元素判斷該元素e是否在是否在La中存在中存在 LocateElem (La, e) 3.若不存在，則將元素若不存在，則將元素e插入到插入到La中中 ListIns

8、ert (La, i, e)l基于基于邏輯邏輯結(jié)構(gòu)的算法描述：結(jié)構(gòu)的算法描述： void Union( &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); l例例2：巳知線性表：巳知線性表LA和線性表和線性表LB中的數(shù)據(jù)元素按值非遞減中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將有序排列，現(xiàn)要求將LA和和LB歸并為一個新的線性表歸并為一個新的線性表L

9、C，且，且LC中的元素仍按值非遞減有序排列。中的元素仍按值非遞減有序排列。Init_List (LC) Length_List (LA)& Length_List (LB)判斷：若i所指元素 j所指元素，則將i所指元素插入在LC的k+1前(即LC的表尾)，且i、k的值分別+1;否則，將j所指元素插入在LC的k+1前(即LC的表尾)，且j、k的值分別+1;2.2 線性表的順序表示和實(shí)現(xiàn)一、順序表（Sequential List）1、定義：用一組地址連續(xù)的存儲單元存放一個線性表叫2、元素地址計(jì)算方法：vLOC(ai)LOC(a1)+(i1)*LvLOC(ai+1)LOC(ai) Lv其中：l L

10、一個元素占用的存儲單元個數(shù)l LOC(ai)線性表第i個元素的地址3、順序表的特點(diǎn)：v實(shí)現(xiàn)邏輯上相鄰物理地址相鄰v實(shí)現(xiàn)隨機(jī)存取4、順序表的實(shí)現(xiàn)：可用C語言的一維數(shù)組實(shí)現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號M-1#define List_Init_Size 100typedef int ElemType ; typedef ElemType ET;typedef struct ElemType *elem; /動態(tài)空間基址 int length; /實(shí)際元素個數(shù) int listsize; /當(dāng)前分配的存儲容量 /(以sizeof(ElemType)為單位) SqList; 備用空

11、間聲明結(jié)構(gòu)體類型， SqList 是順序表的類型名動態(tài)申請和釋放內(nèi)存空間L.elem = (ElemType *)malloc(List_Init_Size*sizeof(ElemType); /申請內(nèi)存free(L.elem); /釋放內(nèi)存typedef struct ElemType *elem ; int length ; int listsize ;SqList ; int ListLength_Sq(SqList L) void ClearList_Sq(SqList &L) 訪問順序表L中第3個元素：L.elem2 e=L.elem2; L.elem2=8; GetElem_Sq(

12、SqList L, int i, ElemType &e) 525L5 5個有效數(shù)據(jù)個有效數(shù)據(jù)25個元素存儲空間L L表的基址（數(shù)組名）是表的基址（數(shù)組名）是 L.elemL.elem關(guān)于數(shù)據(jù)類型名StatusStatusStatus是是“狀態(tài)狀態(tài)”的意思，不是的意思，不是C C語言中的關(guān)鍵字，其語言中的關(guān)鍵字，其目的是為了增強(qiáng)算法的目的是為了增強(qiáng)算法的“可讀性可讀性”typedef int Status;typedef int Status;StatusStatus型的數(shù)據(jù)范圍是型的數(shù)據(jù)范圍是: True: True、FalseFalse、OkOk、Error Error #define T

13、rue 1 #define True 1 #define False 0#define False 0Status ListEmpty(SqList L)Status ListEmpty(SqList L)/判斷線性表判斷線性表L L是否為空表是否為空表 if ( L.length = =0)if ( L.length = =0) return True; return True; return False; return False; 順序表基本操作的算法描述順序表基本操作的算法描述/構(gòu)造一個空的線性表構(gòu)造一個空的線性表 L L#define List_Init_Size 10 /#defi

14、ne List_Init_Size 10 /存儲空間的初始分配量存儲空間的初始分配量#define ListIncrement 10 /#define ListIncrement 10 /存儲空間的分配增量存儲空間的分配增量Status Status InitList_Sq( SqList InitList_Sq( SqList & &L)L) L.elem=(ET L.elem=(ET * *) )mallocmalloc(List_Init_Size(List_Init_Size* *sizeofsizeof(ET);(ET); if if (L.elem = = NULL) (L.ele

15、m = = NULL) exitexit(OVERFLOW); (OVERFLOW); / /* *存儲分配失敗存儲分配失敗* */ / L.length=0; L.length=0; / /* * 空表的長度空表的長度 * */ / L.listsize=List_Init_Size; L.listsize=List_Init_Size; / /* * 初始存儲容量初始存儲容量 * */ / returnreturn OK; OK; 添加（添加（1 1，3 3，5 5，7 7，9 9）之后的狀態(tài)：）之后的狀態(tài)：創(chuàng)建空表之后，表創(chuàng)建空表之后，表L L的狀態(tài)如下：的狀態(tài)如下：L.0 010102

16、4 4 12 1 3 5 7 11 0 31010個元素存儲空間個元素存儲空間刪除第刪除第3 3個元素之后的狀態(tài)：個元素之后的狀態(tài)：4 41010L. 1 3 7 9 9 5 7 11 0 31010個元素存儲空間個元素存儲空間是隨機(jī)數(shù)據(jù)也是隨機(jī)數(shù)據(jù)也就是無效數(shù)據(jù)就是無效數(shù)據(jù)順序表的內(nèi)存狀態(tài) 問題：問題：在表的第在表的第1 1個位置插入個位置插入 6 6 之之后，表后，表L L的存儲狀態(tài)如何？的存儲狀態(tài)如何？問題：清空問題：清空L,L,即即 ClearList_Sq(L)ClearList_Sq(L)之后，表之后，表L L的存儲狀態(tài)如何？的存儲狀態(tài)如何？5 51010L. 1 3 5 7 9

17、5 7 11 0 31010個元素存儲空間個元素存儲空間添加（添加（1 1，3 3，5 5，7 7，9 9）之后的狀態(tài)：）之后的狀態(tài)：5 51010L. 1 3 5 7 91010個元素存儲空間個元素存儲空間創(chuàng)建空表之后，表創(chuàng)建空表之后，表L L的狀態(tài)如下：的狀態(tài)如下：L.0 010101010個元素存儲空間個元素存儲空間刪除第刪除第3 3和第和第4 4個元素之后的狀態(tài)：個元素之后的狀態(tài)：3 31010L. 1 3 91010個元素存儲空間個元素存儲空間將隨機(jī)數(shù)據(jù)想將隨機(jī)數(shù)據(jù)想象成空白象成空白順序表的內(nèi)存想象狀態(tài)結(jié)論：凡是定義的結(jié)論：凡是定義的 或或 動態(tài)申動態(tài)申請的空間內(nèi)，都想象為空白。請的

18、空間內(nèi)，都想象為空白。如如: : int x,A900; int x,A900; SqList L; SqList L; ElemType ElemType * *elem;elem;二、順序表的插入操作 定義：順序表的插入是指在第i個（1i n+1）元素之前插入一個新的數(shù)據(jù)元素x，使長度為 n 的線性表niiaaaaa,1,21 變成長度為 n+1 的線性表niiaaxaaa,1,21 需將第i至第n共（ni1)個元素依次后移一個位置。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號

19、i+1nn+1an-1x順序表的插入操作順序表的插入操作在順序表在順序表L L中第中第i i個位置上插入一個新的元素個位置上插入一個新的元素e e, ,形式參數(shù)為：形式參數(shù)為：&L ,i , e&L ,i , e ；算法步驟如下：算法步驟如下：(1)(1)對輸入?yún)?shù)的安全性檢查對輸入?yún)?shù)的安全性檢查: : 插入位置插入位置 i i 應(yīng)落應(yīng)落在表長范圍內(nèi)，即：在表長范圍內(nèi)，即：1 1 i i L.length+1 L.length+1(2)(2)存儲空間的處理：存儲空間的處理：若原表的存儲空間已滿，應(yīng)若原表的存儲空間已滿，應(yīng)追加存儲空間的分配；追加存儲空間的分配；(3)(3)數(shù)據(jù)塊的搬移：數(shù)據(jù)塊

20、的搬移：將表中從將表中從i i到到L.lengthL.length位置上位置上的所有元素依次往后移動一個位置；的所有元素依次往后移動一個位置；(4)(4)在第在第i i個位置上存儲新的元素個位置上存儲新的元素e,e,表長增，即表長增，即+L.lengthL.length 。注意：邏輯位置（序號）注意：邏輯位置（序號）i i 對應(yīng)的存儲下標(biāo)是對應(yīng)的存儲下標(biāo)是i-1i-1。重新分配動態(tài)存儲空間的函數(shù)重新分配動態(tài)存儲空間的函數(shù)realloc(原動態(tài)區(qū)首址，字節(jié)數(shù)原動態(tài)區(qū)首址，字節(jié)數(shù))其功能為：其功能為：(1)(1)申請申請新的動態(tài)存儲空間新的動態(tài)存儲空間( (成功或失敗成功或失敗););(2)(2)

21、將原動態(tài)區(qū)的數(shù)據(jù)將原動態(tài)區(qū)的數(shù)據(jù)拷貝拷貝到新動態(tài)區(qū)到新動態(tài)區(qū); ;(3)(3)釋放釋放原動態(tài)存儲區(qū)原動態(tài)存儲區(qū); ;(4)(4)返回返回新存儲區(qū)首地址（無類型）。新存儲區(qū)首地址（無類型）。用途：當(dāng)原動態(tài)存儲區(qū)不夠用時(shí)，追加動態(tài)存儲用途：當(dāng)原動態(tài)存儲區(qū)不夠用時(shí)，追加動態(tài)存儲區(qū)；區(qū)；順序表的插入操作算法描述之一順序表的插入操作算法描述之一Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; /i值不合法值不合法 if (L.length = L.listsize) /當(dāng)前存儲空間已滿，增加分配當(dāng)

22、前存儲空間已滿，增加分配 p=(p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) );); if (p=NULL) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 L.elem=p; /新的基地址新的基地址 L.listsize+=ListIncrement; /增加存儲容量增加存儲容量 for ( j=L.length ; j=i ; -j ) L.elemj=L.elemj-1; /移動元素

23、移動元素 L.elemj=e ; /插入新元素插入新元素 +L.length ; /表長增表長增1 return OK; Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; if (L.length = L.listsize) p=( p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) );); if (

24、p=NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; q=&(L.elemi-1); /* q=L.elem+(i-1) 為插入位置為插入位置 */ for (p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; /*移動元素移動元素*/ *q=e ; /*插入新元素插入新元素*/ +L.length ; /*表長增表長增1*/ return OK; 順序表的插入操作算法描述之二順序表的插入操作算法描述之二順序表插入操作的算法評價(jià)順序表插入操作的算法評價(jià)v設(shè) Pi 是在第 i 個元素之前插入一個

25、元素的概率，則在長度為n的線性表中插入一個元素時(shí)，所需移動的元素次數(shù)的平均次數(shù)為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認(rèn)為三、順序表的刪除操作 定義：線性表的刪除是指將第i（1i n）個元素刪除，使長度為n的線性表niiaaaaa,1,21 變成長度為n-1的線性表niiaaaaa,11,21 需將第i+1至第n共（ni)個元素依次前移一個位置。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號i+1n-1nanai+2 順序表的刪除操作順序

26、表的刪除操作刪除順序表刪除順序表L L中第中第i i個位置上的元素，將刪除的元素值賦給個位置上的元素，將刪除的元素值賦給e e。形式參數(shù)為：形式參數(shù)為：&L, i, &e&L, i, &e 算法步驟如下：算法步驟如下：(1)(1)對輸入?yún)?shù)的安全性檢查對輸入?yún)?shù)的安全性檢查: : 刪除位置刪除位置 i i 應(yīng)落在表長范應(yīng)落在表長范圍內(nèi)，即：圍內(nèi)，即：1 1 i i L.lengthL.length ；(2)(2)取出刪除的元素值賦給取出刪除的元素值賦給e e ；(3)(3)數(shù)據(jù)塊的搬移數(shù)據(jù)塊的搬移：將表：將表L L中從中從i+1i+1到到L.lengthL.length位置上的所位置上的所有元

27、素往前移動一個位置；有元素往前移動一個位置；(4)(4)表長減表長減：-L.length-L.length 。順序表的刪除操作算法描述一順序表的刪除操作算法描述一Status ListDelete_Sq(SqList &L , int i , ET &e) if (iL.length) return ERROR; /i值不合法值不合法 e=L.elemi-1; /被刪除元素的值賦給被刪除元素的值賦給e for( j=i ; jL.length; j+) L.elemj-1=L.elemj; /移動元素移動元素 -L.length; /表長減表長減1 return OK; 順序表的刪除操作算法描

28、述二順序表的刪除操作算法描述二Status ListDelete_Sq(SqList &L , int i , ET &e) if (iL.length) return ERROR; /i值不合法值不合法 p=&(L.elemi-1; ) /p為被刪除元素的位置為被刪除元素的位置 e=*p; /被刪除元素的值賦給被刪除元素的值賦給e q=L.elem+L.length-1; /q為表尾元素的位置為表尾元素的位置 for ( +p; p=q; +p) *(p-1)=*p; /移動元素移動元素 -L.length; /表長減表長減1 return OK; 順序表刪除操作的算法評價(jià)順序表刪除操作的算

29、法評價(jià)v設(shè)Qi 是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：niideinQE1)( nOnTninnEnQnidei121)(11則若認(rèn)為故在順序表中插入或刪除一個元素時(shí)，平均約移動表中一半元素，當(dāng)n很大時(shí)，效率很低。順序表的定位操作順序表的定位操作算法要求：在順序表算法要求：在順序表L中，查找第中，查找第 1 個值與數(shù)值個值與數(shù)值 e 相等的元素的位序。若找到，返回其在相等的元素的位序。若找到，返回其在L中的位中的位序，否則，返回序，否則，返回0；算法描述：算法描述： int LocateElem_Sq(SqList L , ET e) 請?zhí)顚?/p>

30、算法描述請?zhí)顚懰惴枋觯?算法分析：基本操作是什么？時(shí)間復(fù)雜度是多少？算法分析：基本操作是什么？時(shí)間復(fù)雜度是多少？Status GetElem_Sq(SqList L , int i , ET &e) if (iL.length|!L.elem) return ERROR; e=L.elemi-1; return OK;算法轉(zhuǎn)換為C語言子程序的規(guī)則：引用型改為指針型Status GetElem_Sq(SqList L , int i , ET *e) if (iL.length |!L.elem) return ERROR; *e=L.elemi-1; return OK;順序表的取值操作順序

31、表的取值操作順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)v優(yōu)點(diǎn)l邏輯相鄰，物理相鄰l可隨機(jī)存取任一元素l存儲空間使用緊湊v缺點(diǎn)l插入、刪除操作需要移動大量的元素l預(yù)先分配空間需按最大空間分配，利用不充分l表容量難以擴(kuò)充1編寫程序?qū)崿F(xiàn)順序表的下列基本操作：編寫程序?qū)崿F(xiàn)順序表的下列基本操作： (1)初始化順序表初始化順序表La。 (2)將將La置為空表。置為空表。 (3)銷毀銷毀La。 (4)在在La中插入一個新的元素。中插入一個新的元素。 (5)刪除刪除La中的某一元素。中的某一元素。 (6)在在La中查找某元素，若找到，則返回它在中查找某元素，若找到，則返回它在La中第一中第一次出現(xiàn)的位置，否則返

32、回次出現(xiàn)的位置，否則返回0。 (7)打印輸出打印輸出La中的元素值。中的元素值。上機(jī)上機(jī)作業(yè)作業(yè)11順序表基本操作（順序表基本操作（2 2學(xué)時(shí)）學(xué)時(shí)）能力培養(yǎng)：通過實(shí)現(xiàn)順序表的基本操作和具體的函數(shù)定義，掌能力培養(yǎng)：通過實(shí)現(xiàn)順序表的基本操作和具體的函數(shù)定義，掌握程序的輸入、編輯、調(diào)試和運(yùn)行過程。握程序的輸入、編輯、調(diào)試和運(yùn)行過程。PracticeEngineering2 2編寫程序完成下面的操作：編寫程序完成下面的操作：(1)(1)構(gòu)造兩個順序線性表構(gòu)造兩個順序線性表LaLa和和LbLb，其元素都按值非遞減順序排列。，其元素都按值非遞減順序排列。(2)(2)實(shí)現(xiàn)歸并實(shí)現(xiàn)歸并LaLa和和LbLb得

33、到新的順序表得到新的順序表LcLc，LcLc的元素也按值非遞減順的元素也按值非遞減順序排列。序排列。(3)(3)假設(shè)兩個順序線性表假設(shè)兩個順序線性表LaLa和和LbLb分別表示兩個集合分別表示兩個集合A A和和B B，利用，利用union_Squnion_Sq操作實(shí)現(xiàn)操作實(shí)現(xiàn)A=A A=A B B。上機(jī)上機(jī)作業(yè)作業(yè)11順序表基本操作（續(xù)）順序表基本操作（續(xù)）能力培養(yǎng)：訓(xùn)練學(xué)生通過順序表的一些基本操作來解決實(shí)際問能力培養(yǎng)：訓(xùn)練學(xué)生通過順序表的一些基本操作來解決實(shí)際問題的能力。題的能力。EngineeringPractice2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表鏈?zhǔn)酱鎯Φ奶攸c(diǎn)：v用一組任意的存儲單元

34、存儲線性表的數(shù)據(jù)元素v利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素v每個結(jié)點(diǎn)，除存儲元素ai本身信息外，還需存儲其直接后繼元素ai+1的地址信息v結(jié)點(diǎn)（Node）l數(shù)據(jù)域：元素本身信息l指針域：指示直接后繼的存儲位置數(shù)據(jù)域 指針域結(jié)點(diǎn)ZHAOQIANSUNLIZHOUWUZHENGWANGH例： 線性表 (ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針2、實(shí)現(xiàn)：typedef struct Node

35、ElemType data; struct Node *next;LNode , *LinkList;/Lnode是結(jié)點(diǎn)類型名，/ LinkList是結(jié)點(diǎn)指針類型名 LinkList L; 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)的指針域生成一個LNode型新結(jié)點(diǎn)：p = ( LNode * ) malloc (sizeof( LNode ); 或：p = ( LinkList ) malloc (sizeof( LNode );系統(tǒng)回收p結(jié)點(diǎn)：free(p)一、線

36、性鏈表一、線性鏈表1、定義：每個結(jié)點(diǎn)中只含一個指針域的鏈表叫，也叫單鏈表 (Single Linked List)頭結(jié)點(diǎn)：在單鏈表第一個結(jié)點(diǎn)前附設(shè)加一個結(jié)點(diǎn)叫頭結(jié)點(diǎn)：在單鏈表第一個結(jié)點(diǎn)前附設(shè)加一個結(jié)點(diǎn)叫頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空表。頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空表。La1a2頭結(jié)點(diǎn)an .L空表頭指針頭指針 L 是是LinkList類型，頭結(jié)點(diǎn)是類型，頭結(jié)點(diǎn)是Lnode類型類型 非空表：非空表： 空表：空表： 注意：注意：頭結(jié)點(diǎn)的位序?yàn)轭^結(jié)點(diǎn)的位序?yàn)? 0，它不是線性表中的元素，它不是線性表中的元素，頭結(jié)點(diǎn)的數(shù)據(jù)域可用于存儲線性表的長度頭結(jié)點(diǎn)的數(shù)據(jù)域可用于存儲線性表的長度。單鏈表是非隨機(jī)存

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

38、* L data=0;*/ L next = NULL; return OK; 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(1) L L 必須必須是引用型是引用型構(gòu)造一個空的單鏈表的算法描述構(gòu)造一個空的單鏈表的算法描述1. 指針指針p在鏈表上依次滑動：在鏈表上依次滑動：p=head; while (p next!=NULL) p=p next; 2. 前驅(qū)指針前驅(qū)指針 q 和當(dāng)前指針和當(dāng)前指針 p在鏈表上同步滑動：在鏈表上同步滑動： q=head ; p=q next; while(p) q=p ; p=q next; 例例1：int ListLength_L( LinkList L) /求線性表的長度求線性

39、表的長度 p=L; j=0; while(p next!=NULL) 或或 while(p next) +j; p=p next; return(j);例例2： Status PriorElem_L (LinkList L, ET e, ET &pre) q=L; p=q next; while(p & p data!=e) q=p;p=q next; 例例3： Status NextElem_L(LinkList L,ET e, ET &next)單鏈表算法中的關(guān)鍵步驟的算法描述單鏈表算法中的關(guān)鍵步驟的算法描述單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算查找查找在單鏈表在單鏈表L中，中，讀取讀取第第i個

40、元素的值賦給參數(shù)個元素的值賦給參數(shù)e Status GetElem_L (LinkList L, int i, ElemType &e) p=L next ; j=1; /j為計(jì)數(shù)器為計(jì)數(shù)器 while (p&j i) 或或if (p= = NULL| j i) /第第i個元素不存在個元素不存在 return ERROR; e = p data; /取出第取出第i個元素的值賦給個元素的值賦給e return OK; 時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(n) 問題：在順序表中問題：在順序表中GetElem_Sq時(shí)間復(fù)雜度是多少？時(shí)間復(fù)雜度是多少？在單鏈表在單鏈表L L中的第中的第i i個結(jié)點(diǎn)之前個結(jié)

41、點(diǎn)之前插入元素插入元素e e的操作步驟：的操作步驟： (1)(1)尋找第尋找第i-1i-1個結(jié)點(diǎn)；個結(jié)點(diǎn)； /O(n)/O(n) (2) (2)測試已知量的合法性；測試已知量的合法性；/O(1)/O(1) (3) (3)申請一個新結(jié)點(diǎn)，并給其數(shù)據(jù)域賦值為申請一個新結(jié)點(diǎn)，并給其數(shù)據(jù)域賦值為e e； / O(1)/ O(1) (4) (4)新結(jié)點(diǎn)插入到單鏈表新結(jié)點(diǎn)插入到單鏈表L L中的第中的第i i個結(jié)點(diǎn)之前。個結(jié)點(diǎn)之前。/O(1)/O(1) 該算法的時(shí)間復(fù)雜度是：該算法的時(shí)間復(fù)雜度是：O(n)O(n)單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算插入插入pai-1aies s next=p next ; p

42、next = s ; Status ListInsert_L (LinkList &L, int i, ElemType e) p=L; j=0; /j為計(jì)數(shù)器為計(jì)數(shù)器 while (p& ji1) 或者或者if (p= =NULL | ji1) return ERROR; /i大于表長大于表長+1或者或者i小于小于1 s = ( LinkList ) malloc ( sizeof ( Lnode ) ); /申請新結(jié)點(diǎn)申請新結(jié)點(diǎn)s if (s = NULL) exit (OVERFLOW); s data=e; s next=p next ; / 在在 p結(jié)點(diǎn)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)之后插入新結(jié)

43、點(diǎn)s p next = s ; return OK;單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算插入插入在單鏈表在單鏈表L L中刪除第中刪除第i i個結(jié)點(diǎn)，并由個結(jié)點(diǎn)，并由e e返回其值的操作步驟：返回其值的操作步驟： (1)(1)尋找第尋找第i-1i-1個結(jié)點(diǎn)；個結(jié)點(diǎn)； /O(n)/O(n) (2) (2)測試已知量的合法性；測試已知量的合法性； /O(1)/O(1) (3) (3)刪除第刪除第i i個結(jié)點(diǎn)，并取出數(shù)據(jù)域的值賦給個結(jié)點(diǎn)，并取出數(shù)據(jù)域的值賦給e e；/ O(1)/ O(1) (4) (4)釋放第釋放第i i個結(jié)點(diǎn)的存儲空間。個結(jié)點(diǎn)的存儲空間。/O(1)/O(1) 該算法的時(shí)間復(fù)雜度是：該算

44、法的時(shí)間復(fù)雜度是：O(n)O(n)單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算刪除刪除pai-1aiai+1p next = q next;qStatus ListDelete_L (LinkList &L, int i, ElemType &e) p=L; j=0; /j為計(jì)數(shù)器為計(jì)數(shù)器 while (p next & ji1 ) /i大于表長或者大于表長或者i小于小于1 return ERROR; q=pnext; /q指向要刪除的結(jié)點(diǎn)指向要刪除的結(jié)點(diǎn)ai p next=q next ; / 刪除刪除結(jié)點(diǎn)結(jié)點(diǎn)ai e=q data; free(q); /釋放釋放結(jié)點(diǎn)結(jié)點(diǎn)ai的存儲空間的存儲空間 ret

45、urn OK;單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算刪除刪除逆位序輸入n個元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表L。算法評價(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動態(tài)建立單鏈表的算法動態(tài)建立單鏈表的算法逆向建立逆向建立Void CreateList_L (LinkList &L, int n)/建立一個帶頭結(jié)點(diǎn)的單鏈表建立一個帶頭結(jié)點(diǎn)的單鏈表L L=( LinkList ) malloc ( sizeof ( Lnode ) ); /L指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn) L next = NULL; for ( i=n; i0; -

46、i ) p=( LinkList ) malloc ( sizeof ( Lnode ) ); /p為新結(jié)點(diǎn)為新結(jié)點(diǎn) scanf(&p data); /為結(jié)點(diǎn)為結(jié)點(diǎn)p的數(shù)據(jù)域賦值的數(shù)據(jù)域賦值 p next=L next ; /為結(jié)點(diǎn)為結(jié)點(diǎn)p的指針域賦值的指針域賦值 Lnext=p; /將結(jié)點(diǎn)將結(jié)點(diǎn)p插入到表頭插入到表頭 動態(tài)建立單鏈表的算法動態(tài)建立單鏈表的算法逆向建立逆向建立單鏈表特點(diǎn)它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間，分配的空間連續(xù)與否均可指針占用額外存儲空間不能隨機(jī)存取，查找速度慢，便于插入、刪除操作線性表的順序存儲和鏈?zhǔn)酱鎯Σ僮魃系谋容^順序存儲順序存儲鏈?zhǔn)酱鎯︽?/p>

47、式存儲循環(huán)控制變量循環(huán)控制變量下標(biāo)變量下標(biāo)變量i指針變量指針變量p初始化初始化i=0；p=head; 或或p=head-next;循環(huán)條件循環(huán)條件idata） （p-next）下一對象下一對象i+;p=p-next;1編寫程序?qū)崿F(xiàn)單鏈表的下列基本操作：編寫程序?qū)崿F(xiàn)單鏈表的下列基本操作： (1)初始化單鏈表初始化單鏈表La。 (2)在單鏈表在單鏈表La中插入一個新結(jié)點(diǎn)。中插入一個新結(jié)點(diǎn)。 (3)刪除單鏈表刪除單鏈表La中的某一個結(jié)點(diǎn)。中的某一個結(jié)點(diǎn)。 (4)在單鏈表在單鏈表La中查找某結(jié)點(diǎn)并返回其位置。中查找某結(jié)點(diǎn)并返回其位置。 (5)打印輸出單鏈表打印輸出單鏈表La中的結(jié)點(diǎn)元素值。中的結(jié)點(diǎn)元素

48、值。2構(gòu)造兩個帶有表頭結(jié)點(diǎn)的有序單鏈表構(gòu)造兩個帶有表頭結(jié)點(diǎn)的有序單鏈表La、Lb，編寫程序?qū)?，編寫程序?qū)崿F(xiàn)將現(xiàn)將La、Lb合并成一個有序單鏈表合并成一個有序單鏈表Lc。上機(jī)上機(jī)作業(yè)作業(yè)22單鏈表基本操作（單鏈表基本操作（2 2學(xué)時(shí)）學(xué)時(shí)）能力培養(yǎng)：掌握對單鏈表的一些基本操作和具體的函數(shù)定義，能力培養(yǎng)：掌握對單鏈表的一些基本操作和具體的函數(shù)定義，通過實(shí)現(xiàn)兩個有序表歸并，訓(xùn)練單鏈表的一些基本操作。通過實(shí)現(xiàn)兩個有序表歸并，訓(xùn)練單鏈表的一些基本操作。EngineeringPractice二、循環(huán)鏈表 (Circular Linked List)v循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成一

49、個環(huán)狀v特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高了查找效率v循環(huán)鏈表操作與單鏈表基本一致，循環(huán)結(jié)束條件不同l單鏈表單鏈表L：p next = =NULLl循環(huán)鏈表循環(huán)鏈表L：p next = = Lv非空循環(huán)鏈表非空循環(huán)鏈表v空循環(huán)鏈表空循環(huán)鏈表頭5836L頭L僅設(shè)尾指針的兩循環(huán)鏈表的鏈接僅設(shè)尾指針的兩循環(huán)鏈表的鏈接AB存儲池存儲池p Void *Connect( LinkList &A, LinkList &B) LinkList *p; pA-next; A-nextB-next-next; free(B-next); B-nextp; 僅設(shè)尾指針的兩循環(huán)鏈表的鏈接算法僅設(shè)尾指針的兩循環(huán)鏈表的鏈接算法三、雙向鏈表（Double Linked List）單鏈表具有單向性的缺點(diǎn),所以引入雙向鏈表。v結(jié)點(diǎn)定義typedef stru