線性表的操作講解

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

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

3、系: R1= |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(&a

4、mp;L , i , &e)ListTraverse(L, visit( ) 線性表初始化：線性表初始化： 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é)點，要求1iListLength(L) 插入操作：插入操作：ListInsert (&L, i, e)Lis

5、tInsert (&L, i, e)； 在線性表L的第i個位置上插入一個值為e的數(shù)據(jù)元素。(5)(5)刪除操作：刪除操作：ListDelete (&L, i ,&e)ListDelete (&L, i ,&e)； 在線性表L中刪除位序為 i 的數(shù)據(jù)元素。 按值查找：按值查找：LocateElem(L, e)LocateElem(L, e)； 在L中查找值為e的結(jié)點，并返回該結(jié)點在L中的位置。若L中有多個結(jié)點的值和e e相同，則返回首次找到的結(jié)點位置；若L中沒有結(jié)點的值為e e，則返回一個特殊值(如零)表示查找失敗。課后思考：應用基本操作實現(xiàn)課后思考：應用

6、基本操作實現(xiàn)刪除線性表刪除線性表LaLa中大于中大于e e的所有的所有數(shù)據(jù)元素：數(shù)據(jù)元素：DelElems(&L,e)DelElems(&L,e)CopyList(La,&Lb)/CopyList(La,&Lb)/應用基本操作：實現(xiàn)應用基本操作：實現(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

7、,e); GetElem(La,i,e); ListInsert(Lb,i,e); ListInsert(Lb,i,e); 課堂練習：課堂練習：應用基本操作實現(xiàn)應用基本操作實現(xiàn)CopyList(La,&Lb)CopyList(La,&Lb)例例1:1:設計求設計求 A = AA = AB B 的算法的算法l分析：建立線性表分析：建立線性表 La、Lb分別表示集合分別表示集合A和和B，將，將Lb中存中存在而在而La中不存在的元素中不存在的元素e插入插入 La中，因此，中，因此，本算法的基本操本算法的基本操作是查找作是查找(比較比較)。算法算法思想思想： 1. 從從Lb中依次取得每

8、個元素中依次取得每個元素e GetElem (Lb, i, e) 2. 判斷該元素判斷該元素e是否在是否在La中存在中存在 LocateElem (La, e) 3.若不存在，則將元素若不存在，則將元素e插入到插入到La中中 ListInsert (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) L

9、istInsert(La, + +La_len, e); l例例2：巳知線性表：巳知線性表LA和線性表和線性表LB中的數(shù)據(jù)元素按值非遞減中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將有序排列，現(xiàn)要求將LA和和LB歸并為一個新的線性表歸并為一個新的線性表LC，且，且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的

10、值分別+1;2.2 線性表的順序表示和實現(xiàn)一、順序表（Sequential List）1、定義：用一組地址連續(xù)的存儲單元存放一個線性表叫2、元素地址計算方法：vLOC(ai)LOC(a1)+(i1)*LvLOC(ai+1)LOC(ai) Lv其中：l L 一個元素占用的存儲單元個數(shù)l LOC(ai)線性表第i個元素的地址3、順序表的特點：v實現(xiàn)邏輯上相鄰物理地址相鄰v實現(xiàn)隨機存取4、順序表的實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標元素序號M-1#define List_Init_Size 100typedef int ElemType ; typedef Ele

11、mType ET;typedef struct ElemType *elem; /動態(tài)空間基址 int length; /實際元素個數(shù) int listsize; /當前分配的存儲容量 /(以sizeof(ElemType)為單位) SqList; 備用空間聲明結(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 li

12、stsize ;SqList ; int ListLength_Sq(SqList L) void ClearList_Sq(SqList &L) 訪問順序表L中第3個元素：L.elem2 e=L.elem2; L.elem2=8; GetElem_Sq(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)鍵字，其目的是為了增

13、強算法的目的是為了增強算法的“可讀性可讀性”typedef int Status;typedef int Status;StatusStatus型的數(shù)據(jù)范圍是型的數(shù)據(jù)范圍是: True: True、FalseFalse、OkOk、Error Error #define True 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 = =

14、0) return True; return True; return False; return False; 順序表基本操作的算法描述順序表基本操作的算法描述/構(gòu)造一個空的線性表構(gòu)造一個空的線性表 L L#define List_Init_Size 10 /#define List_Init_Size 10 /存儲空間的初始分配量存儲空間的初始分配量#define ListIncrement 10 /#define ListIncrement 10 /存儲空間的分配增量存儲空間的分配增量Status Status InitList_Sq( SqList InitList_Sq( SqLis

15、t & &L)L) L.elem=(ET L.elem=(ET * *) )mallocmalloc(List_Init_Size(List_Init_Size* *sizeofsizeof(ET);(ET); if if (L.elem = = NULL) (L.elem = = NULL) exitexit(OVERFLOW); (OVERFLOW); / /* *存儲分配失敗存儲分配失敗* */ / L.length=0; L.length=0; / /* * 空表的長度空表的長度 * */ / L.listsize=List_Init_Size; L.listsize=

16、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 0101024 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個元素存儲空間個元素存儲空間是隨機數(shù)據(jù)也是隨機數(shù)據(jù)也就是無效數(shù)據(jù)就是無效數(shù)據(jù)順序表的內(nèi)存狀態(tài) 問題：問題：在表的

17、第在表的第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 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個元素存儲空間個

18、元素存儲空間刪除第刪除第3 3和第和第4 4個元素之后的狀態(tài)：個元素之后的狀態(tài)：3 31010L. 1 3 91010個元素存儲空間個元素存儲空間將隨機數(shù)據(jù)想將隨機數(shù)據(jù)想象成空白象成空白順序表的內(nèi)存想象狀態(tài)結(jié)論：凡是定義的結(jié)論：凡是定義的 或或 動態(tài)申動態(tài)申請的空間內(nèi)，都想象為空白。請的空間內(nèi)，都想象為空白。如如: : int x,A900; int x,A900; SqList L; SqList L; ElemType ElemType * *elem;elem;二、順序表的插入操作 定義：順序表的插入是指在第i個（1i n+1）元素之前插入一個新的數(shù)據(jù)元素x，使長度為 n 的線性表nii

19、aaaaa,1,21 變成長度為 n+1 的線性表niiaaxaaa,1,21 需將第i至第n共（ni1)個元素依次后移一個位置。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號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ù)的安全性

20、檢查: : 插入位置插入位置 i i 應落應落在表長范圍內(nèi)，即：在表長范圍內(nèi)，即：1 1 i i L.length+1 L.length+1(2)(2)存儲空間的處理：存儲空間的處理：若原表的存儲空間已滿，應若原表的存儲空間已滿，應追加存儲空間的分配；追加存儲空間的分配；(3)(3)數(shù)據(jù)塊的搬移：數(shù)據(jù)塊的搬移：將表中從將表中從i i到到L.lengthL.length位置上位置上的所有元素依次往后移動一個位置；的所有元素依次往后移動一個位置；(4)(4)在第在第i i個位置上存儲新的元素個位置上存儲新的元素e,e,表長增，即表長增，即+L.lengthL.length 。注意：邏輯位置（序號）

21、注意：邏輯位置（序號）i i 對應的存儲下標是對應的存儲下標是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)將原動態(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ū)首地址（無類型）。用途：當原動態(tài)存儲區(qū)不夠用時，追加動態(tài)存儲用途：當原動態(tài)存儲區(qū)不夠用時，追加動態(tài)存儲區(qū)；區(qū)；順序表的插入操作

22、算法描述之一順序表的插入操作算法描述之一Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; /i值不合法值不合法 if (L.length = L.listsize) /當前存儲空間已滿，增加分配當前存儲空間已滿，增加分配 p=(p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) );); if

23、(p=NULL) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 L.elem=p; /新的基地址新的基地址 L.listsize+=ListIncrement; /增加存儲容量增加存儲容量 for ( j=L.length ; j=i ; -j ) L.elemj=L.elemj-1; /移動元素移動元素 L.elemj=e ; /插入新元素插入新元素 +L.length ; /表長增表長增1 return OK; Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR;

24、if (L.length = L.listsize) 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; q=&(L.elemi-1); /* q=L.elem+(i-1) 為插入位置為插入位置 */ for (p=&(L.elemL.length

25、-1); p=q; -p) *(p+1)=*p; /*移動元素移動元素*/ *q=e ; /*插入新元素插入新元素*/ +L.length ; /*表長增表長增1*/ return OK; 順序表的插入操作算法描述之二順序表的插入操作算法描述之二順序表插入操作的算法評價順序表插入操作的算法評價v設 Pi 是在第 i 個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認為三、順序表的刪除操作 定義：線性表的刪除是指將第i（1i n）個元素刪除，使長度為n的線性表

26、niiaaaaa,1,21 變成長度為n-1的線性表niiaaaaa,11,21 需將第i+1至第n共（ni)個元素依次前移一個位置。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標01i-1n-2in-112i元素序號i+1n-1nanai+2 順序表的刪除操作順序表的刪除操作刪除順序表刪除順序表L L中第中第i i個位置上的元素，將刪除的元素值賦給個位置上的元素，將刪除的元素值賦給e e。形式參數(shù)為：形式參數(shù)為：&L, i, &e&L, i, &e 算法步驟如下：算法步驟如下：(1)(1)對

27、輸入?yún)?shù)的安全性檢查對輸入?yún)?shù)的安全性檢查: : 刪除位置刪除位置 i i 應落在表長范應落在表長范圍內(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位置上的所位置上的所有元素往前移動一個位置；有元素往前移動一個位置；(4)(4)表長減表長減：-L.length-L.length 。順序表的刪除操作算法描述一順序表的刪除操作算法描述一Status ListDelete_Sq(SqList &L

28、, 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; 順序表的刪除操作算法描述二順序表的刪除操作算法描述二Status ListDelete_Sq(SqList &L , int i , ET &e) if (iL.length) return ERROR; /i值不合法值不

29、合法 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; 順序表刪除操作的算法評價順序表刪除操作的算法評價v設Qi 是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：niideinQE1)( nOnTninnEnQnidei121)(11則若認為故在順

30、序表中插入或刪除一個元素時，平均約移動表中一半元素，當n很大時，效率很低。順序表的定位操作順序表的定位操作算法要求：在順序表算法要求：在順序表L中，查找第中，查找第 1 個值與數(shù)值個值與數(shù)值 e 相等的元素的位序。若找到，返回其在相等的元素的位序。若找到，返回其在L中的位中的位序，否則，返回序，否則，返回0；算法描述：算法描述： int LocateElem_Sq(SqList L , ET e) 請?zhí)顚懰惴枋稣執(zhí)顚懰惴枋觯?算法分析：基本操作是什么？時間復雜度是多少？算法分析：基本操作是什么？時間復雜度是多少？Status GetElem_Sq(SqList L , int i , ET

31、 &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;順序表的取值操作順序表的取值操作順序存儲結(jié)構(gòu)的優(yōu)缺點順序存儲結(jié)構(gòu)的優(yōu)缺點v優(yōu)點l邏輯相鄰，物理相鄰l可隨機存取任一元素l存儲空間使用緊湊v缺點l插入、刪除操作需要移動大量的元素l預先分配空間需按最大空間分

32、配，利用不充分l表容量難以擴充1編寫程序?qū)崿F(xiàn)順序表的下列基本操作：編寫程序?qū)崿F(xiàn)順序表的下列基本操作： (1)初始化順序表初始化順序表La。 (2)將將La置為空表。置為空表。 (3)銷毀銷毀La。 (4)在在La中插入一個新的元素。中插入一個新的元素。 (5)刪除刪除La中的某一元素。中的某一元素。 (6)在在La中查找某元素，若找到，則返回它在中查找某元素，若找到，則返回它在La中第一中第一次出現(xiàn)的位置，否則返回次出現(xiàn)的位置，否則返回0。 (7)打印輸出打印輸出La中的元素值。中的元素值。上機上機作業(yè)作業(yè)11順序表基本操作（順序表基本操作（2 2學時）學時）能力培養(yǎng)：通過實現(xiàn)順序表的基本操作

33、和具體的函數(shù)定義，掌能力培養(yǎng)：通過實現(xiàn)順序表的基本操作和具體的函數(shù)定義，掌握程序的輸入、編輯、調(diào)試和運行過程。握程序的輸入、編輯、調(diào)試和運行過程。PracticeEngineering2 2編寫程序完成下面的操作：編寫程序完成下面的操作：(1)(1)構(gòu)造兩個順序線性表構(gòu)造兩個順序線性表LaLa和和LbLb，其元素都按值非遞減順序排列。，其元素都按值非遞減順序排列。(2)(2)實現(xiàn)歸并實現(xiàn)歸并LaLa和和LbLb得到新的順序表得到新的順序表LcLc，LcLc的元素也按值非遞減順的元素也按值非遞減順序排列。序排列。(3)(3)假設兩個順序線性表假設兩個順序線性表LaLa和和LbLb分別表示兩個集合

34、分別表示兩個集合A A和和B B，利用，利用union_Squnion_Sq操作實現(xiàn)操作實現(xiàn)A=A A=A B B。上機上機作業(yè)作業(yè)11順序表基本操作（續(xù)）順序表基本操作（續(xù)）能力培養(yǎng)：訓練學生通過順序表的一些基本操作來解決實際問能力培養(yǎng)：訓練學生通過順序表的一些基本操作來解決實際問題的能力。題的能力。EngineeringPractice2.3 線性表的鏈式表示和實現(xiàn)線性表鏈式存儲的特點：v用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素v利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素v每個結(jié)點，除存儲元素ai本身信息外，還需存儲其直接后繼元素ai+1的地址信息v結(jié)點（Node）l數(shù)據(jù)域：元素

35、本身信息l指針域：指示直接后繼的存儲位置數(shù)據(jù)域 指針域結(jié)點ZHAOQIANSUNLIZHOUWUZHENGWANGH例： 線性表 (ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針2、實現(xiàn)：typedef struct Node ElemType data; struct Node *next;LNode , *LinkList;/Lnode是結(jié)點類型名，/ LinkList是結(jié)點指針類型名 LinkList

36、L; LNode *p;datanextL結(jié)點(*p)(*p)表示p所指向的結(jié)點(*p).datap data表示p指向結(jié)點的數(shù)據(jù)域(*p).nextp next表示p指向結(jié)點的指針域生成一個LNode型新結(jié)點：p = ( LNode * ) malloc (sizeof( LNode ); 或：p = ( LinkList ) malloc (sizeof( LNode );系統(tǒng)回收p結(jié)點：free(p)一、線性鏈表一、線性鏈表1、定義：每個結(jié)點中只含一個指針域的鏈表叫，也叫單鏈表 (Single Linked List)頭結(jié)點：在單鏈表第一個結(jié)點前附設加一個結(jié)點叫頭結(jié)點：在單鏈表第一個結(jié)點

37、前附設加一個結(jié)點叫頭結(jié)點指針域為空表示線性表為空表。頭結(jié)點指針域為空表示線性表為空表。La1a2頭結(jié)點an .L空表頭指針頭指針 L 是是LinkList類型，頭結(jié)點是類型，頭結(jié)點是Lnode類型類型 非空表：非空表： 空表：空表： 注意：注意：頭結(jié)點的位序為頭結(jié)點的位序為0 0，它不是線性表中的元素，它不是線性表中的元素，頭結(jié)點的數(shù)據(jù)域可用于存儲線性表的長度頭結(jié)點的數(shù)據(jù)域可用于存儲線性表的長度。單鏈表是非隨機存取的存儲結(jié)構(gòu)單鏈表是非隨機存取的存儲結(jié)構(gòu) 在單鏈表中，任何兩個元素的存儲位置之間在單鏈表中，任何兩個元素的存儲位置之間沒有固定的聯(lián)系，每個元素的沒有固定的聯(lián)系，每個元素的存儲位置存儲位

38、置都包含在都包含在其其直接前驅(qū)結(jié)點的指針域中直接前驅(qū)結(jié)點的指針域中。 在單鏈表中，要取得第在單鏈表中，要取得第 i 個數(shù)據(jù)元素必須個數(shù)據(jù)元素必須從頭從頭結(jié)點結(jié)點出發(fā)尋找。出發(fā)尋找。頭5836 L頭L Status InitList_L (LinkList &L) L=( LinkList ) malloc ( sizeof ( Lnode ) ); if (L= =NULL) exit (OVERFLOW); /* L data=0;*/ L next = NULL; return OK; 時間復雜度：時間復雜度：O(1) L L 必須必須是引用型是引用型構(gòu)造一個空的單鏈表的算法描述構(gòu)

39、造一個空的單鏈表的算法描述1. 指針指針p在鏈表上依次滑動：在鏈表上依次滑動：p=head; while (p next!=NULL) p=p next; 2. 前驅(qū)指針前驅(qū)指針 q 和當前指針和當前指針 p在鏈表上同步滑動：在鏈表上同步滑動： q=head ; p=q next; while(p) q=p ; p=q next; 例例1：int ListLength_L( LinkList L) /求線性表的長度求線性表的長度 p=L; j=0; while(p next!=NULL) 或或 while(p next) +j; p=p next; return(j);例例2： Status

40、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)鍵步驟的算法描述單鏈表的基本運算單鏈表的基本運算查找查找在單鏈表在單鏈表L中，中，讀取讀取第第i個元素的值賦給參數(shù)個元素的值賦給參數(shù)e Status GetElem_L (LinkList L, int i, ElemType &e) p=L

41、 next ; j=1; /j為計數(shù)器為計數(shù)器 while (p&j i) 或或if (p= = NULL| j i) /第第i個元素不存在個元素不存在 return ERROR; e = p data; /取出第取出第i個元素的值賦給個元素的值賦給e return OK; 時間復雜度為：時間復雜度為：O(n) 問題：在順序表中問題：在順序表中GetElem_Sq時間復雜度是多少？時間復雜度是多少？在單鏈表在單鏈表L L中的第中的第i i個結(jié)點之前個結(jié)點之前插入元素插入元素e e的操作步驟：的操作步驟： (1)(1)尋找第尋找第i-1i-1個結(jié)點；個結(jié)點； /O(n)/O(n) (2)

42、 (2)測試已知量的合法性；測試已知量的合法性；/O(1)/O(1) (3) (3)申請一個新結(jié)點，并給其數(shù)據(jù)域賦值為申請一個新結(jié)點，并給其數(shù)據(jù)域賦值為e e； / O(1)/ O(1) (4) (4)新結(jié)點插入到單鏈表新結(jié)點插入到單鏈表L L中的第中的第i i個結(jié)點之前。個結(jié)點之前。/O(1)/O(1) 該算法的時間復雜度是：該算法的時間復雜度是：O(n)O(n)單鏈表的基本運算單鏈表的基本運算插入插入pai-1aies s next=p next ; p next = s ; Status ListInsert_L (LinkList &L, int i, ElemType e)

43、p=L; j=0; /j為計數(shù)器為計數(shù)器 while (p& ji1) 或者或者if (p= =NULL | ji1) return ERROR; /i大于表長大于表長+1或者或者i小于小于1 s = ( LinkList ) malloc ( sizeof ( Lnode ) ); /申請新結(jié)點申請新結(jié)點s if (s = NULL) exit (OVERFLOW); s data=e; s next=p next ; / 在在 p結(jié)點結(jié)點之后插入新結(jié)點之后插入新結(jié)點s p next = s ; return OK;單鏈表的基本運算單鏈表的基本運算插入插入在單鏈表在單鏈表L L中刪除

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

45、ext;qStatus ListDelete_L (LinkList &L, int i, ElemType &e) p=L; j=0; /j為計數(shù)器為計數(shù)器 while (p next & ji1 ) /i大于表長或者大于表長或者i小于小于1 return ERROR; q=pnext; /q指向要刪除的結(jié)點指向要刪除的結(jié)點ai p next=q next ; / 刪除刪除結(jié)點結(jié)點ai e=q data; free(q); /釋放釋放結(jié)點結(jié)點ai的存儲空間的存儲空間 return OK;單鏈表的基本運算單鏈表的基本運算刪除刪除逆位序輸入n個元素的值，建立帶表頭結(jié)點的單

46、鏈表L。算法評價：T(n) O(n)L頭結(jié)點an 0L頭結(jié)點an-10an a2.L頭結(jié)點an-10an La1a2頭結(jié)點an .0L頭結(jié)點0動態(tài)建立單鏈表的算法動態(tài)建立單鏈表的算法逆向建立逆向建立Void CreateList_L (LinkList &L, int n)/建立一個帶頭結(jié)點的單鏈表建立一個帶頭結(jié)點的單鏈表L L=( LinkList ) malloc ( sizeof ( Lnode ) ); /L指向頭結(jié)點指向頭結(jié)點 L next = NULL; for ( i=n; i0; -i ) p=( LinkList ) malloc ( sizeof ( Lnode )

47、 ); /p為新結(jié)點為新結(jié)點 scanf(&p data); /為結(jié)點為結(jié)點p的數(shù)據(jù)域賦值的數(shù)據(jù)域賦值 p next=L next ; /為結(jié)點為結(jié)點p的指針域賦值的指針域賦值 Lnext=p; /將結(jié)點將結(jié)點p插入到表頭插入到表頭 動態(tài)建立單鏈表的算法動態(tài)建立單鏈表的算法逆向建立逆向建立單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預先分配空間，分配的空間連續(xù)與否均可指針占用額外存儲空間不能隨機存取，查找速度慢，便于插入、刪除操作線性表的順序存儲和鏈式存儲操作上的比較順序存儲順序存儲鏈式存儲鏈式存儲循環(huán)控制變量循環(huán)控制變量下標變量下標變量i指針變量指針變量p初始化初始化i

48、=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é)點。中插入一個新結(jié)點。 (3)刪除單鏈表刪除單鏈表La中的某一個結(jié)點。中的某一個結(jié)點。 (4)在單鏈表在單鏈表La中查找某結(jié)點并返回其位置。中查找某結(jié)點并返回其位置。 (5)打印輸出單鏈表打印輸出單鏈表La中的結(jié)點元素值。中的結(jié)點元素值。2構(gòu)造兩個帶有表頭結(jié)點的有序單鏈表構(gòu)造兩個帶有表頭結(jié)點的有序單鏈表La、Lb

49、，編寫程序?qū)?，編寫程序?qū)崿F(xiàn)將現(xiàn)將La、Lb合并成一個有序單鏈表合并成一個有序單鏈表Lc。上機上機作業(yè)作業(yè)22單鏈表基本操作（單鏈表基本操作（2 2學時）學時）能力培養(yǎng)：掌握對單鏈表的一些基本操作和具體的函數(shù)定義，能力培養(yǎng)：掌握對單鏈表的一些基本操作和具體的函數(shù)定義，通過實現(xiàn)兩個有序表歸并，訓練單鏈表的一些基本操作。通過實現(xiàn)兩個有序表歸并，訓練單鏈表的一些基本操作。EngineeringPractice二、循環(huán)鏈表 (Circular Linked List)v循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成一個環(huán)狀v特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高了查找效率v循環(huán)鏈表操

50、作與單鏈表基本一致，循環(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僅設尾指針的兩循環(huán)鏈表的鏈接僅設尾指針的兩循環(huán)鏈表的鏈接AB存儲池存儲池p Void *Connect( LinkList &A, LinkList &B) LinkList *p; pA-next; A-nextB-next-next; free(B-next); B-nextp; 僅設尾指針的兩循環(huán)鏈表的鏈接算法僅設尾指針的兩循環(huán)鏈表的鏈接算法三、雙向鏈表（Double Linked List）單鏈表具有單向性的缺點,所以引入雙向鏈表。v