操作系統(tǒng)哈爾濱工程大學(xué)

1、Data StructureData StructurePage 12022-3-19q 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)v了解了解線性表的邏輯結(jié)構(gòu)特性線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)和和鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。表簡(jiǎn)稱為鏈表。v熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作基本操作在這兩在這

2、兩種存儲(chǔ)結(jié)構(gòu)上種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)的實(shí)現(xiàn)。v能夠能夠從時(shí)間和空間復(fù)雜度的角度從時(shí)間和空間復(fù)雜度的角度綜合綜合比較比較線性表線性表兩種存儲(chǔ)結(jié)構(gòu)的不兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合同特點(diǎn)及其適用場(chǎng)合。v結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解。結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解。Data StructureData StructurePage 22022-3-19q 重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)v鏈表鏈表是本章的重點(diǎn)和難點(diǎn)。是本章的重點(diǎn)和難點(diǎn)。v扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針要求，分清鏈表中指針

3、 p p 和結(jié)點(diǎn)和結(jié)點(diǎn) * *p p 之間的對(duì)應(yīng)關(guān)系，區(qū)分之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。雙向鏈表的特點(diǎn)等。q 知識(shí)點(diǎn)知識(shí)點(diǎn)v線性表、順序表、鏈表、有序表線性表、順序表、鏈表、有序表Data StructureData StructurePage 32022-3-19線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中q 存在唯一的一個(gè)被稱做存在唯一的一個(gè)被稱做“第一個(gè)第一個(gè)”的數(shù)據(jù)元素；的數(shù)據(jù)元素；q 存在唯一的一個(gè)被稱做存在唯一的一個(gè)被稱做“最后

4、一個(gè)最后一個(gè)”的數(shù)據(jù)元素；的數(shù)據(jù)元素；q 除第一個(gè)之外，每個(gè)元素都只有一個(gè)前驅(qū)；除第一個(gè)之外，每個(gè)元素都只有一個(gè)前驅(qū)；q 除最后一個(gè)之外，每個(gè)元素都只有一個(gè)后繼。除最后一個(gè)之外，每個(gè)元素都只有一個(gè)后繼。Data StructureData StructurePage 42022-3-19q 是是最常用、最簡(jiǎn)單最常用、最簡(jiǎn)單的一種線性數(shù)據(jù)結(jié)構(gòu)。的一種線性數(shù)據(jù)結(jié)構(gòu)。q 表示方法：表示方法：n n個(gè)數(shù)據(jù)元素的有限序列個(gè)數(shù)據(jù)元素的有限序列。v英文字母英文字母（A A，B B，C C，Z Z）是一個(gè)線性表，表中元素是一個(gè)字母。是一個(gè)線性表，表中元素是一個(gè)字母。v星期星期（星期日，星期一，星期二，（星期日

5、，星期一，星期二，星期六），星期六）是一個(gè)線性表，表中的是一個(gè)線性表，表中的數(shù)據(jù)元素是星期中一天的名稱。數(shù)據(jù)元素是星期中一天的名稱。v同一花色的同一花色的1313張撲克牌張撲克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A)(2,3,4,5,6,7,8,9,10,J,Q,K,A)可以構(gòu)成一個(gè)線性可以構(gòu)成一個(gè)線性表。表。v在稍復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以是由若干個(gè)數(shù)據(jù)項(xiàng)組成的記錄，在稍復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以是由若干個(gè)數(shù)據(jù)項(xiàng)組成的記錄，含有大量記錄的線性表稱為文件。如，一個(gè)學(xué)校的學(xué)生情況登記表。含有大量記錄的線性表稱為文件。如，一個(gè)學(xué)校的學(xué)生情況登記表。學(xué)學(xué) 號(hào)號(hào) 姓姓 名

6、名 性性 別別 年年 齡齡 籍籍 貫貫 970001970001普琪坤普琪坤 男男2121長(zhǎng)沙長(zhǎng)沙970002970002劉然劉然 男男2222岳陽(yáng)岳陽(yáng)970003970003馮靜馮靜 女女2121長(zhǎng)沙長(zhǎng)沙Data StructureData StructurePage 52022-3-19q 一個(gè)線性表中的數(shù)據(jù)元素是屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)一個(gè)線性表中的數(shù)據(jù)元素是屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。據(jù)元素之間存在著序偶關(guān)系。v可將線性表記為可將線性表記為（a a1 1,a,ai-1i-1,a,ai i,a,ai+1i+1,a,an n）。va ai-1i-1是是a ai i的直

7、接前驅(qū)元素，的直接前驅(qū)元素， a ai+1i+1是是a ai i的直接后繼元素。的直接后繼元素。 a a1 1無(wú)直接無(wú)直接前驅(qū)，前驅(qū)，a an n無(wú)直接后繼。無(wú)直接后繼。vi i是數(shù)據(jù)元素是數(shù)據(jù)元素a ai i在線性表中的在線性表中的位序位序。q 線性表的線性表的長(zhǎng)度長(zhǎng)度定義定義為線性表中數(shù)據(jù)元素的個(gè)數(shù)為線性表中數(shù)據(jù)元素的個(gè)數(shù)n n。v當(dāng)當(dāng)n=0n=0時(shí)，為空表。時(shí)，為空表。Data StructureData StructurePage 62022-3-19ADT ADT ListList 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：D= aD= ai i | a | ai iElemSet, i=1,2,nElem

8、Set, i=1,2,n，n=0n=0數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1=aR1=| a| ai-1i-1，a ai iDD，i=1,2,n i=1,2,n 基本操作基本操作： 結(jié)構(gòu)初始化結(jié)構(gòu)初始化 InitList( &L )InitList( &L )操作結(jié)果：構(gòu)造一個(gè)空的線性表操作結(jié)果：構(gòu)造一個(gè)空的線性表 L L 。 銷毀結(jié)構(gòu)銷毀結(jié)構(gòu) DestroyList( &L )DestroyList( &L )初始條件：線性表初始條件：線性表 L L 已存在。已存在。操作結(jié)果：銷毀線性表操作結(jié)果：銷毀線性表 L L 。Data StructureData StructureP

9、age 72022-3-19 引用型操作引用型操作 ListEmpty( L )ListEmpty( L )初始條件：線性表初始條件：線性表L L已存在。已存在。操作結(jié)果：若操作結(jié)果：若 L L 為空表，則返回為空表，則返回 TRUETRUE，否則返回，否則返回 FALSEFALSE。 ListLength( L )ListLength( L )初始條件：線性表初始條件：線性表 L L 已存在。已存在。操作結(jié)果：返回操作結(jié)果：返回 L L 中元素個(gè)數(shù)。中元素個(gè)數(shù)。PriorElem( L, cur_e, &pre_e )PriorElem( L, cur_e, &pre_e )

10、初始條件：線性表初始條件：線性表 L L 已存在。已存在。操作結(jié)果：若操作結(jié)果：若 cur_e cur_e 是是 L L 中的數(shù)據(jù)元素，則用中的數(shù)據(jù)元素，則用 pre_e pre_e 返返 回它的前驅(qū)，否則操作失敗，回它的前驅(qū)，否則操作失敗，pre_e pre_e 無(wú)定義。無(wú)定義。Data StructureData StructurePage 82022-3-19NextElem( L, cur_e, &next_e )NextElem( L, cur_e, &next_e )初始條件：線性表初始條件：線性表 L L 已存在。已存在。操作結(jié)果：若操作結(jié)果：若 cur_e cu

11、r_e 是是 L L 中的數(shù)據(jù)元素，則用中的數(shù)據(jù)元素，則用 next_enext_e 返回它的后繼，否則操作失敗，返回它的后繼，否則操作失敗，next_e next_e 無(wú)定義。無(wú)定義。GetElem( L, i, &e )GetElem( L, i, &e )初始條件：線性表初始條件：線性表 L L 已存在，已存在，1iLengthList(L)1iLengthList(L)。操作結(jié)果：用操作結(jié)果：用 e e 返回返回 L L 中第中第 i i 個(gè)元素的值。個(gè)元素的值。LocateElem( L, e, compare( ) )LocateElem( L, e, compar

12、e( ) )初始條件：線性表初始條件：線性表 L L 已存在，已存在，compare( ) compare( ) 是元素判定函數(shù)。是元素判定函數(shù)。操作結(jié)果：返回操作結(jié)果：返回 L L 中第中第1 1個(gè)與個(gè)與 e e 滿足關(guān)系滿足關(guān)系 compare( ) compare( ) 的的 元素的位序。若這樣的元素不存在，則返回值為元素的位序。若這樣的元素不存在，則返回值為0 0。Data StructureData StructurePage 92022-3-19 加工型操作加工型操作 ClearList( &L )ClearList( &L )初始條件：線性表初始條件：線性表 L

13、L 已存在。已存在。操作結(jié)果：將操作結(jié)果：將 L L 重置為空表。重置為空表。PutElem( &L, i, &e )PutElem( &L, i, &e )初始條件：線性表初始條件：線性表L L已存在，已存在，1iLengthList(L)1iLengthList(L)。操作結(jié)果：操作結(jié)果：L L 中第中第 i i 個(gè)元素賦值同個(gè)元素賦值同 e e 的值。的值。ListInsert( &L, i, e )ListInsert( &L, i, e )初始條件：線性表初始條件：線性表 L L 已存在，已存在，1iLengthList(L)+11iL

14、engthList(L)+1。操作結(jié)果：在操作結(jié)果：在 L L 的第的第 i i 個(gè)元素之前插入新的元素個(gè)元素之前插入新的元素 e e，L L 的長(zhǎng)度的長(zhǎng)度 增增1 1。ListDelete( &L, i, &e )ListDelete( &L, i, &e )初始條件：線性表初始條件：線性表 L L 已存在且非空，已存在且非空，1iLengthList(L)1iLengthList(L)。操作結(jié)果：刪除操作結(jié)果：刪除 L L 的第的第 i i 個(gè)元素，并用個(gè)元素，并用 e e 返回其值，返回其值，L L 的長(zhǎng)的長(zhǎng) 度減度減1 1。 ADT List ADT L

15、istData StructureData StructurePage 102022-3-19算法思想：逐一取出算法思想：逐一取出LBLB中的元素，判斷是否在中的元素，判斷是否在LALA中，若不在中，若不在, ,則插之。則插之。void unin(List &Lavoid unin(List &La，List Lb)List Lb) La_len=(ListLength(La); La_len=(ListLength(La); Lb_len=(ListLength(Lb); Lb_len=(ListLength(Lb); for(i=1; i=Lb_len; i+) for(i

16、=1; i=Lb_len; i+) GetElem(Lb,i,e); GetElem(Lb,i,e); if (!LocateElem(La,e,equal) if (!LocateElem(La,e,equal) ListInsert(La,+La_len,e); ListInsert(La,+La_len,e); /La /La 中不存在和中不存在和e e 相同的元素，則插入之相同的元素，則插入之 /union/union算法的時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度：O O（ListLength(LA) ListLength(LA) ListLength(LB)ListLength(LB)）1 12

17、 23 34 45 56 67 7Data StructureData StructurePage 112022-3-19算法思想：將算法思想：將LALA、LBLB兩表中的元素逐一按序加入到一個(gè)新表兩表中的元素逐一按序加入到一個(gè)新表LCLC中。中。void MergeList(List La, List Lb, List &Lc)void MergeList(List La, List Lb, List &Lc) InitList(Lc); InitList(Lc); i=j=1; k=0; i=j=1; k=0; /i/i，j j，k k分別指向分別指向LaLa，LbLb，L

18、cLc La_len=(ListLength(La); La_len=(ListLength(La); Lb_len=(ListLength(Lb); Lb_len=(ListLength(Lb); while (i=La_len)&(j=Lb_len) while (i=La_len)&(j=Lb_len) /La/La和和LbLb均非空均非空 GetElem(La,i,aGetElem(La,i,ai i); GetElem(Lb,j,b); GetElem(Lb,j,bj j);); if(a if(ai i=b=bj j)ListInsert(Lc,+k,a)ListI

19、nsert(Lc,+k,ai i);+i;);+i; else ListInsert(Lc,+k,b else ListInsert(Lc,+k,bj j);+j;);+j; 1 12 23 34 45 56 67 78 89 91010Data StructureData StructurePage 122022-3-19 while (i=La_len) while (i=La_len) /La/La還有元素還有元素 GetElem(La,i+,aGetElem(La,i+,ai i); ListInsert(Lc,+k,a); ListInsert(Lc,+k,ai i);); whil

20、e (j=Lb_len) while (j=Lb_len) /Lb/Lb還有元素還有元素 GetElem(Lb,j+,bGetElem(Lb,j+,bj j); ListInsert(Lc,+k,b); ListInsert(Lc,+k,bj j);); /MergeList/MergeList算法的時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度：O(ListLength(LA)+ListLength(LB)O(ListLength(LA)+ListLength(LB)11111212131314141515161617171818Data StructureData StructurePage 132022-

21、3-19q 用用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。v可用可用一維數(shù)組一維數(shù)組來(lái)描述。來(lái)描述。v假設(shè)線性表的每個(gè)元素需占用假設(shè)線性表的每個(gè)元素需占用l l個(gè)存儲(chǔ)單元，則數(shù)據(jù)元素的存儲(chǔ)位個(gè)存儲(chǔ)單元，則數(shù)據(jù)元素的存儲(chǔ)位置：置： LOC(aLOC(ai+1i+1)=LOC(a)=LOC(ai i)+l)+l 一般地，存貯位置：一般地，存貯位置： LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *l lvLOC(aLOC(a1 1) )是線性表的第一個(gè)數(shù)據(jù)元素是線性表的第一個(gè)數(shù)據(jù)元素a a1 1的存儲(chǔ)位

22、置，稱做線性表的的存儲(chǔ)位置，稱做線性表的起起始位置始位置或或基地值基地值。Data StructureData StructurePage 142022-3-19存儲(chǔ)地址存儲(chǔ)地址 內(nèi)存狀態(tài)內(nèi)存狀態(tài) 元素位序元素位序 b ba a1 11 1b+lb+la a2 22 2b+(i-1)b+(i-1)* *l l a ai i i i b+(n-1)b+(n-1)* *l l a an n n n 空閑空閑Data StructureData StructurePage 152022-3-19q 邏輯上相鄰邏輯上相鄰物理地址相鄰。物理地址相鄰。q 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。只要確定了存儲(chǔ)線性表的起始位隨

23、機(jī)存取的存儲(chǔ)結(jié)構(gòu)。只要確定了存儲(chǔ)線性表的起始位 置，線性表中的任一數(shù)據(jù)元素可隨機(jī)存取。置，線性表中的任一數(shù)據(jù)元素可隨機(jī)存取。Data StructureData StructurePage 162022-3-19#define LIST_INIT_SIZE 100#define LIST_INIT_SIZE 100/線性表存儲(chǔ)空間的初始分配量線性表存儲(chǔ)空間的初始分配量#define LISTINCREAMENT 10 #define LISTINCREAMENT 10 /線性表存儲(chǔ)空間的分配增量線性表存儲(chǔ)空間的分配增量type structtype struct ElemType ElemTy

24、pe * *elemelem; ; /存儲(chǔ)空間基地址存儲(chǔ)空間基地址 int int lengthlength; ; /當(dāng)前長(zhǎng)度當(dāng)前長(zhǎng)度 int int listsizelistsize; ; /當(dāng)前分配的存儲(chǔ)容量當(dāng)前分配的存儲(chǔ)容量 SqListSqList；Data StructureData StructurePage 172022-3-19Data StructureData StructurePage 182022-3-19q 初始化操作初始化操作算法思想：構(gòu)造一個(gè)空表。設(shè)置表的起始位置、表長(zhǎng)及可用空間。算法思想：構(gòu)造一個(gè)空表。設(shè)置表的起始位置、表長(zhǎng)及可用空間。Status InitLi

25、st_Sq(SqList &L)Status InitList_Sq(SqList &L) /構(gòu)造一個(gè)空的線性表構(gòu)造一個(gè)空的線性表 L.elem=(ElemType L.elem=(ElemType * *)malloc(LIST_INIT_SIZE)malloc(LIST_INIT_SIZE* *sizeof(ElemType);sizeof(ElemType); If(!L.elem) exit(OVERFLOW); If(!L.elem) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 L.length=0; L.length=0; /空表長(zhǎng)度為空表長(zhǎng)度為0

26、0 L.listsize= LIST_INIT_SIZE; L.listsize= LIST_INIT_SIZE; /初始存儲(chǔ)容量初始存儲(chǔ)容量 return OK;return OK;/InitList_Sq/InitList_SqData StructureData StructurePage 192022-3-19算法思想：在第算法思想：在第i i個(gè)位置上插入一個(gè)新元素，將第個(gè)位置上插入一個(gè)新元素，將第n n至第至第i i（共（共n-i+1n-i+1）個(gè)元素）個(gè)元素 逐一向后移動(dòng)一個(gè)位置。逐一向后移動(dòng)一個(gè)位置。 在長(zhǎng)度為在長(zhǎng)度為n n的表（的表（a a1 1，a a2 2，a an n）中

27、插入一個(gè)新的元素）中插入一個(gè)新的元素b b，使，使 表變成長(zhǎng)度為表變成長(zhǎng)度為n+1n+1的表（的表（a a1 1，bb，a ai i，a an n）。）。Data StructureData StructurePage 202022-3-19q 判判i i值的合法性，值的合法性，1i1i表長(zhǎng)表長(zhǎng)+1+1；q 判表的空間滿否？若滿則增加分配（動(dòng)態(tài)分配）判表的空間滿否？若滿則增加分配（動(dòng)態(tài)分配）q 從表長(zhǎng)從表長(zhǎng)n n到到i i，依次后移；，依次后移；q 將將e e插入第插入第i i個(gè)位置，表長(zhǎng)度增個(gè)位置，表長(zhǎng)度增1 1。Data StructureData StructurePage 212022

28、-3-19Status ListInsert_Sq(SqList &L, int i, ElemType e )/在順序表在順序表L中第中第i個(gè)位置之前插入新的元素個(gè)位置之前插入新的元素e，i的合法值為的合法值為1iListLength_Sq(L)+11iListLength_Sq(L)+1if (iL.length+1) return ERROR; /i值不合法值不合法 if (L.length=L.listsize) /當(dāng)前存儲(chǔ)空間已滿，增加分配當(dāng)前存儲(chǔ)空間已滿，增加分配newbase=(ElemType *)realloc(L.elem,(L.listsize+ LISTINCR

29、EMENT)sizeof(ElemType);if(!newbase)exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗L.elem=newbase; /新基地址新基地址L.listsize+= LISTINCREMENT; /增加存儲(chǔ)容量增加存儲(chǔ)容量 q=&(L.elemi-1); / q為插入位置為插入位置for (p=&(L.elemL.length-1) ; p=q ; -p) *(p+1)=*p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q=e; / 插入插入e+L.length;/ 表長(zhǎng)增表長(zhǎng)增1return OK;/ListInsert_Sq

30、Data StructureData StructurePage 222022-3-19q 設(shè)設(shè)P Pi i是在第是在第i i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為為n n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：平均次數(shù)為：11(1)nisiiEP ni 11iPn若 認(rèn) 為 插 入 的 概 率 相 同 ， 即111(1)12nisinEninTnOn則 在順序表中插入一個(gè)元素時(shí)，平均移動(dòng)表的一半元在順序表中插入一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)素，當(dāng)n n很大時(shí)，很大時(shí)，效率很低效率很低

31、。Data StructureData StructurePage 232022-3-19算法思想：刪除第算法思想：刪除第i i個(gè)元素，將第（個(gè)元素，將第（i+1i+1）至第）至第n n（共（共n-in-i）個(gè)元素逐一向前）個(gè)元素逐一向前 移動(dòng)一個(gè)位置。移動(dòng)一個(gè)位置。Data StructureData StructurePage 242022-3-19q判判i i值的合法性，值的合法性，1i1i表長(zhǎng)表長(zhǎng)n n。q從從i+1i+1到表長(zhǎng)到表長(zhǎng)n n，依次前移。，依次前移。q表長(zhǎng)度減表長(zhǎng)度減1 1。Data StructureData StructurePage 252022-3-19Statu

32、s ListDelete_Sq(SqList &L, int i, ElemType &e )/在順序表L中刪除第i個(gè)元素，并用e返回其值，i的合法值為1iListLength_Sq(L)if (iL.length) return ERROR; /i值不合法p=&(L.elemi-1); / p為被刪除元素位置 e=*p; / 被刪除元素的值賦給eq= L.elem+ L.length-1; / 表尾元素的位置for (+p; p=q ; +p) *(p-1)=*p; / 被刪除元素之后的元素左移-L.length;/ 表長(zhǎng)減1return OK;/ListDelete

33、_SqData StructureData StructurePage 262022-3-19q 設(shè)設(shè)Q Qi i是刪除第是刪除第i i個(gè)元素的概率，則在長(zhǎng)度為個(gè)元素的概率，則在長(zhǎng)度為n n的線性表中刪的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為：除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為：1()ndeiiEQ ni1iQn若 認(rèn) 為 刪 除 的 概 率 相 同 ， 即111()2ndeinEninTnOn則 在順序表中刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元在順序表中刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)素，當(dāng)n n很大時(shí)，很大時(shí)，效率很低效率很低。Data StructureData S

34、tructurePage 272022-3-19q 優(yōu)點(diǎn)優(yōu)點(diǎn)v邏輯相鄰，物理相鄰。邏輯相鄰，物理相鄰。v可隨機(jī)存取任一元素?？呻S機(jī)存取任一元素。v存儲(chǔ)空間使用緊湊。存儲(chǔ)空間使用緊湊。q 缺點(diǎn)缺點(diǎn)v插入、刪除操作需要移動(dòng)大量的元素。插入、刪除操作需要移動(dòng)大量的元素。v預(yù)先分配空間需按最大空間分配，利用不充分。預(yù)先分配空間需按最大空間分配，利用不充分。v表容量難以擴(kuò)充。表容量難以擴(kuò)充。Data StructureData StructurePage 282022-3-19q 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：v用一組用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素任意的存儲(chǔ)單元存儲(chǔ)線

35、性表的數(shù)據(jù)元素。（這組存儲(chǔ)單。（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）元可以是連續(xù)的，也可以是不連續(xù)的）v利用利用指針指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素。實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素。v每個(gè)數(shù)據(jù)元素每個(gè)數(shù)據(jù)元素a ai i，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息。信息。v數(shù)據(jù)元素的映象用一個(gè)結(jié)點(diǎn)來(lái)表示。數(shù)據(jù)元素的映象用一個(gè)結(jié)點(diǎn)來(lái)表示。數(shù)據(jù)域數(shù)據(jù)域：元素本身信息：元素本身信息指針域指針域：指示直接后繼的存儲(chǔ)位置：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域數(shù)據(jù)域 指針域指針域結(jié)點(diǎn)結(jié)點(diǎn)Data StructureData Struct

36、urePage 292022-3-19LILIQIANQIANSUNSUNWANGWANGWUWUZHAOZHAOZHENGZHENGZHOUZHOU存儲(chǔ)地址存儲(chǔ)地址1 17 713131919252531313737434343131NULLNULL3771925數(shù)據(jù)域數(shù)據(jù)域指針域指針域31H頭指針ZHAOQIANSUNLIZHOUWUZHENGWANGH數(shù)據(jù)之間的數(shù)據(jù)之間的邏輯關(guān)系由邏輯關(guān)系由結(jié)點(diǎn)中的指結(jié)點(diǎn)中的指針指示針指示最后結(jié)點(diǎn)最后結(jié)點(diǎn)Data StructureData StructurePage 302022-3-19q 單鏈表單鏈表v鏈表中的每一個(gè)結(jié)點(diǎn)中鏈表中的每一個(gè)結(jié)點(diǎn)中只包含

37、一個(gè)指針域只包含一個(gè)指針域的稱為單鏈表。的稱為單鏈表。q 單鏈表的存儲(chǔ)結(jié)構(gòu)單鏈表的存儲(chǔ)結(jié)構(gòu)typedef struc LNodetypedef struc LNodeElemTypeElemType data; data; struct LNode struct LNode * *nextnext；LNode, LNode, * *LinkListLinkList；q 頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)。ha1a2頭結(jié)點(diǎn)頭結(jié)點(diǎn)an .h空表空表Data StructureData StructurePage 312022-3-19q 查找查找vL

38、 L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，當(dāng)?shù)跒閹ь^結(jié)點(diǎn)的單鏈表的頭指針，當(dāng)?shù)趇 i個(gè)元素存在時(shí)，其值賦給個(gè)元素存在時(shí)，其值賦給e e并返回并返回OKOK，否則返回，否則返回ERRORERROR。v算法思想：設(shè)置一個(gè)指針變量指向第一個(gè)結(jié)點(diǎn)，然后，讓該指針變算法思想：設(shè)置一個(gè)指針變量指向第一個(gè)結(jié)點(diǎn)，然后，讓該指針變 量逐一向后指向，直到第量逐一向后指向，直到第i i個(gè)元素。個(gè)元素。Status GetElem_L(LinkList L, int i, ElemType e)p=Lnext; j=1; /初始化，初始化，p指向第一個(gè)結(jié)點(diǎn)，指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器為計(jì)數(shù)器while(p & ji)

39、return ERROR; /第第i個(gè)元素不存在個(gè)元素不存在e=pdata; /取第取第i個(gè)元素個(gè)元素return OK;/GetElem_LData StructureData StructurePage 322022-3-19算法思想：算法思想：v生成生成x x結(jié)點(diǎn)結(jié)點(diǎn)vx x的指針指向的指針指向b b。va a的指針指向的指針指向x xpabxssnext=pnext;pnext=s；可否交換兩個(gè)指針的修改次序？可否交換兩個(gè)指針的修改次序？Data StructureData StructurePage 332022-3-19 Status ListInsert_L(LinkList&a

40、mp;L, int i, ElemType e)/在帶頭結(jié)點(diǎn)的單鏈表在帶頭結(jié)點(diǎn)的單鏈表L中第中第i個(gè)位置前插入元素個(gè)位置前插入元素ep=L; j=0; /i-1的有效位置從的有效位置從0開(kāi)始開(kāi)始while(p & ji-1) return ERROR; /i小于小于1或者大于表長(zhǎng)或者大于表長(zhǎng)s=(LinkList)malloc(sizeof(LNode); sdata=e; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)snext=p-next; pnext=s;/插入插入L中中return OK;/ ListInsert_L Data StructureData StructurePage 342022-3

41、-19算法思想：算法思想：v就是要讓就是要讓a a的指針直接指向的指針直接指向c c，使，使b b從鏈表中脫離。從鏈表中脫離。v釋放釋放b b所分配的資源。所分配的資源。pabcpnext=pnextnextpnext=pnextnext；Data StructureData StructurePage 352022-3-19 Status ListDelete_L(LinkList&L, int i, ElemType &e)/在帶頭結(jié)點(diǎn)的單鏈表在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第中，刪除第i個(gè)元算，并由個(gè)元算，并由e返回其值返回其值p=L; j=0; /i-1的有效位置從的有效位

42、置從0開(kāi)始開(kāi)始while(p-next & jnext) | ji-1) return ERROR; /刪除位置不合理刪除位置不合理q=p-next; p-next=q-next; /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)e=q-next; free(q); /釋放結(jié)點(diǎn)釋放結(jié)點(diǎn)return OK;/ ListDelete_LData StructureData StructurePage 362022-3-19q 設(shè)線性表設(shè)線性表n n個(gè)元素已存放在數(shù)組個(gè)元素已存放在數(shù)組a a中，建立一個(gè)單鏈表，中，建立一個(gè)單鏈表，h h為頭指針。為頭指針。h頭結(jié)點(diǎn)頭結(jié)點(diǎn)an h頭結(jié)點(diǎn)頭結(jié)點(diǎn)an-1an a2.h頭結(jié)點(diǎn)頭結(jié)

43、點(diǎn)an-1an ha1a2頭結(jié)點(diǎn)頭結(jié)點(diǎn)an .h頭結(jié)點(diǎn)頭結(jié)點(diǎn)Data StructureData StructurePage 372022-3-19 void CreateList_L(LinkList &L, int n)/逆位序輸入逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈表L。L=(LinkList) malloc (sizeof(LNode);L-next=NULL; /建一個(gè)帶頭結(jié)點(diǎn)的單鏈表建一個(gè)帶頭結(jié)點(diǎn)的單鏈表for (i=n; i0 ; -i ) p= (LinkList) malloc (sizeof(LNode); /生成新結(jié)點(diǎn)生成

44、新結(jié)點(diǎn)scanf(&p-data); /輸入元素值輸入元素值p-next=L-next; L-next =p;/插入到表頭插入到表頭/ CreateList_LData StructureData StructurePage 382022-3-19q 算法思想：算法思想：v設(shè)立設(shè)立三個(gè)指針三個(gè)指針papa、pbpb和和pcpc分別用來(lái)指向兩個(gè)有序鏈分別用來(lái)指向兩個(gè)有序鏈表和合并表的當(dāng)前元素。表和合并表的當(dāng)前元素。v比較兩個(gè)表的當(dāng)前元素的大小，將比較兩個(gè)表的當(dāng)前元素的大小，將小的元素鏈接到小的元素鏈接到合并表合并表中，即，讓合并表的當(dāng)前指針指向該元素，中，即，讓合并表的當(dāng)前指針指向該元素

45、，然后，然后，修改指針修改指針。v在歸并兩個(gè)鏈表為一個(gè)鏈表時(shí)，在歸并兩個(gè)鏈表為一個(gè)鏈表時(shí)，不需要另建新表的不需要另建新表的結(jié)點(diǎn)空間結(jié)點(diǎn)空間，而只需將原來(lái)兩個(gè)鏈表中結(jié)點(diǎn)之間的關(guān)，而只需將原來(lái)兩個(gè)鏈表中結(jié)點(diǎn)之間的關(guān)系解除，重新建立關(guān)系。系解除，重新建立關(guān)系。Data StructureData StructurePage 392022-3-19void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)/已知單鏈表已知單鏈表La和和Lb的元素按非遞減排列，歸并的元素按非遞減排列，歸并La和和Lb得到新的非遞減單鏈表得到

46、新的非遞減單鏈表 Lc 。pa=La-next; pb=Lb-next;Lc=pc=La; /用用La的頭結(jié)點(diǎn)作為的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)的頭結(jié)點(diǎn)while (pa & pb) if (pa-datadata)pc-next=pa; pc=pa; pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; /插入剩余段插入剩余段free(Lb); /釋放釋放Lb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn)/ MergeList_LData StructureData StructurePage 402022-3-19q 它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存

47、儲(chǔ)空間為多個(gè)鏈表共用。它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用。q 不需預(yù)先分配空間。不需預(yù)先分配空間。q 指針占用額外存儲(chǔ)空間。指針占用額外存儲(chǔ)空間。q 不能隨機(jī)存取，查找速度慢。不能隨機(jī)存取，查找速度慢。q 插入、刪除操作的速度快。插入、刪除操作的速度快。Data StructureData StructurePage 412022-3-19q 表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀。，使鏈表構(gòu)成環(huán)狀。q 特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提 高查找效率。高查找效率。q 操作與單鏈表基

48、本一致，判表尾條件不同。操作與單鏈表基本一致，判表尾條件不同。v單鏈表單鏈表p p或或p-next=NULLp-next=NULLv循環(huán)鏈表循環(huán)鏈表p p或或p-next=hp-next=hhh空表空表Data StructureData StructurePage 422022-3-19q 雙向鏈表中，結(jié)點(diǎn)有兩個(gè)指針域，分別指向前驅(qū)和后繼。雙向鏈表中，結(jié)點(diǎn)有兩個(gè)指針域，分別指向前驅(qū)和后繼。q 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)typedef struct DuLNode typedef struct DuLNode ElemType ElemType data;data; struct DuLNode str

49、uct DuLNode * *prior;prior; struct DuLNode struct DuLNode * *next;next; DuLNode, DuLNode, * *DuLinklist;DuLinklist;priordatanextData StructureData StructurePage 432022-3-19L L空雙向循環(huán)鏈表：空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表： L LA AB Bbcapp-prior-next= p= p-next-proir;Data StructureData StructurePage 442022-3-19q 雙

50、指針使得雙向循環(huán)鏈表中，雙指針使得雙向循環(huán)鏈表中，前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的查找前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的查找更為方便、快捷更為方便、快捷。NextElemNextElem和和PriorElemPriorElem的執(zhí)行時(shí)間為的執(zhí)行時(shí)間為O(1)O(1)。q 僅需涉及僅需涉及一個(gè)方向的指針的操作和單鏈表的操作相同一個(gè)方向的指針的操作和單鏈表的操作相同。q 插入和刪除插入和刪除需同時(shí)需同時(shí)修改兩個(gè)方向的指針修改兩個(gè)方向的指針。Data StructureData StructurePage 452022-3-19xSbaP s=(DuLinkList)malloc(sizeof(DuLNode); s-dat

51、a=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;思考：四個(gè)思考：四個(gè)指針的修改指針的修改順序可否任順序可否任意改變？意改變？Data StructureData StructurePage 462022-3-19 Status ListInsert_DuL(DuLinkList&L, int i, ElemType e)/在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中第中第i個(gè)位置前插入元素個(gè)位置前插入元素e /i的合法值為的合法值為1i表長(zhǎng)+1if (!(p=GetElemP_DuL(L,i)/在在L中確定第中

52、確定第i個(gè)元素的指針個(gè)元素的指針preturn ERROR; /p=NULL,即第即第i個(gè)元素不存在個(gè)元素不存在if(!(s=(DuLinkList)malloc(sizeof(DuLNode) return ERROR; /申請(qǐng)空間失敗申請(qǐng)空間失敗s-data=e; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)s-prior=p-prior; p-prior-next=s;s-next=p; p-prior=s; /插入插入L中中return OK;/ ListInsert_DuL Data StructureData StructurePage 472022-3-19bcaPp-prior-next=p-nex

53、t;p-next-prior=p-prior;free(p);Data StructureData StructurePage 482022-3-19 Status ListDelete_DuL(DuLinkList&L, int i, ElemType &e)/在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中，刪除第中，刪除第i個(gè)元算，并由個(gè)元算，并由e返回其值返回其值 /i的合法值為的合法值為1i表長(zhǎng)if (!(p=GetElemP_DuL(L,i)/在在L中確定第中確定第i個(gè)元素的指針個(gè)元素的指針preturn ERROR; /p=NULL,即第即第i個(gè)元素不存在個(gè)元

54、素不存在e=p-data; p-prior-next=p-next;p-next-prior=p-prior; /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)free(p); /釋放結(jié)點(diǎn)釋放結(jié)點(diǎn)return OK;/ ListDelete_DuLData StructureData StructurePage 492022-3-19一元多項(xiàng)式的表示：一元多項(xiàng)式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表可用線性表P P表示表示200001000231)(xxxS但對(duì)但對(duì)S(x)S(x)這樣的多項(xiàng)式浪費(fèi)空間這樣的多項(xiàng)式浪費(fèi)空間一般一般emmnxPxPxPxPee2121)(其中其中為非零系

55、數(shù)）（iPemee210用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表表示用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表表示emPePePm，2121其存儲(chǔ)結(jié)構(gòu)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用單鏈表。其存儲(chǔ)結(jié)構(gòu)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用單鏈表。Data StructureData StructurePage 502022-3-19coefexpnext17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多項(xiàng)式相加一元多項(xiàng)式相加單鏈表的結(jié)點(diǎn)定義單鏈表的結(jié)點(diǎn)定義Da

56、ta StructureData StructurePage 512022-3-19q 從第一個(gè)結(jié)點(diǎn)開(kāi)始檢測(cè)。從第一個(gè)結(jié)點(diǎn)開(kāi)始檢測(cè)。q 比較指數(shù)：比較指數(shù)：vA中指數(shù)小中指數(shù)小，A后移一個(gè)結(jié)點(diǎn)。后移一個(gè)結(jié)點(diǎn)。v指數(shù)相等指數(shù)相等，則系數(shù)相加。，則系數(shù)相加。若結(jié)果不為若結(jié)果不為0，則更新，則更新A中域值，并保留中域值，并保留A中該結(jié)點(diǎn)。中該結(jié)點(diǎn)。若結(jié)果為若結(jié)果為0，則刪掉，則刪掉A中該結(jié)點(diǎn)。中該結(jié)點(diǎn)。釋放釋放B中結(jié)點(diǎn)，并后移一個(gè)結(jié)點(diǎn)。中結(jié)點(diǎn)，并后移一個(gè)結(jié)點(diǎn)。vA中指數(shù)大中指數(shù)大，將，將B中結(jié)點(diǎn)插入中結(jié)點(diǎn)插入A中該結(jié)點(diǎn)之前，中該結(jié)點(diǎn)之前，AB各后移一個(gè)結(jié)點(diǎn)。各后移一個(gè)結(jié)點(diǎn)。q 連接連接B中可能剩余的

57、結(jié)點(diǎn)于中可能剩余的結(jié)點(diǎn)于A。q 釋放釋放B的表頭。的表頭。相加算法相加算法Data StructureData StructurePage 522022-3-19q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7

58、-9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 Data StructureData StructurePage 532022-3-19q 線性表是線性表是n(n0)n(n0)個(gè)數(shù)據(jù)元素的序列，通常寫成個(gè)數(shù)據(jù)元素的序列，通常寫成 （a a1 1,a,ai-1i-1,a,ai i,a,ai+1i+1,a,an n）q 線性表中除了第一個(gè)和最后一個(gè)元素之外，都線性表中除了第一個(gè)和最后一個(gè)元素之外，都只有一個(gè)前只有一個(gè)前驅(qū)和一個(gè)后繼驅(qū)和一個(gè)后繼。q 線性表中每個(gè)元素都有自己確定的位置，

59、即線性表中每個(gè)元素都有自己確定的位置，即“位序位序”。q n=0n=0時(shí)的線性表稱為時(shí)的線性表稱為“空表空表”，在，在寫線性表的操作算法時(shí)一寫線性表的操作算法時(shí)一定要考慮你的算法對(duì)空表的情況是否也正確定要考慮你的算法對(duì)空表的情況是否也正確。Data StructureData StructurePage 542022-3-19q 順序表順序表v是線性表的順序存儲(chǔ)結(jié)構(gòu)的一種別稱。是線性表的順序存儲(chǔ)結(jié)構(gòu)的一種別稱。v特點(diǎn)特點(diǎn)是以是以“存儲(chǔ)位置相鄰存儲(chǔ)位置相鄰”表示兩個(gè)元素之間的前驅(qū)、后繼關(guān)系。表示兩個(gè)元素之間的前驅(qū)、后繼關(guān)系。v優(yōu)點(diǎn)優(yōu)點(diǎn)是可以隨機(jī)存取表中任意一個(gè)元素。是可以隨機(jī)存取表中任意一個(gè)元素

60、。v缺點(diǎn)缺點(diǎn)是每作一次插入或刪除操作時(shí)，平均來(lái)說(shuō)必須移動(dòng)表中一半是每作一次插入或刪除操作時(shí)，平均來(lái)說(shuō)必須移動(dòng)表中一半元素。元素。v常應(yīng)用于常應(yīng)用于主要是為查詢而很少作插入和刪除操作，表長(zhǎng)變化不大主要是為查詢而很少作插入和刪除操作，表長(zhǎng)變化不大的線性表的線性表。 Data StructureData StructurePage 552022-3-19q 鏈表鏈表v是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的別稱。是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的別稱。v特點(diǎn)特點(diǎn)是以是以“指針指針”指示后繼元素，因此線性表的元素可以存儲(chǔ)在存指示后繼元素，因此線性表的元素可以存儲(chǔ)在存儲(chǔ)器中任意一組存儲(chǔ)單元中。儲(chǔ)器中任意一組存儲(chǔ)單元中。v優(yōu)點(diǎn)優(yōu)點(diǎn)是便于進(jìn)行插入和刪除操作。是便于進(jìn)行插入和刪除操作。v缺點(diǎn)缺點(diǎn)是不能進(jìn)行隨機(jī)存取，每個(gè)元素的存儲(chǔ)位置都存放在其前驅(qū)元是不能進(jìn)行隨機(jī)存取，每個(gè)元素的存儲(chǔ)位置都存放在其前驅(qū)元素的指針域中，為取得表中任意一個(gè)數(shù)據(jù)元素都必須從第一個(gè)數(shù)據(jù)素的指針域中，為取得表中任意一個(gè)數(shù)據(jù)元素都必須從第一個(gè)數(shù)據(jù)元素起查詢。元素起查詢。v由于它是一種動(dòng)態(tài)分配的結(jié)構(gòu)，由于它是一種動(dòng)態(tài)分配的結(jié)構(gòu)，結(jié)點(diǎn)的存儲(chǔ)空間可以隨用隨取結(jié)