1、第二章第二章線 性 表 第二章 線性表（Linear List）內容提要 線性表的類型定義 線性表的順序表示和實現 線性表的鏈式表示和實現 一元多項式的表示及相加a1a2ai-1aiai+1an-1an 線性表的定義：線性表的定義：線性表是線性表是n個元素（個元素（n0）的有限序列。可記為）的有限序列。可記為L=(a1,a2,.,ai,ai+1,.,an), 示意為：示意為： 2.1 線性表的類型定義終端結點終端結點(表尾結點表尾結點,尾結點尾結點)起始結點起始結點(表頭結點表頭結點,首首元結點元結點)稱：稱：ai-1是是ai的的直接前趨直接前趨（有時簡稱前趨） ai+1是是ai的的直接后繼直

2、接后繼（有時簡稱后繼） ai-1aiai+1 2.1 線性表的類型定義線性表的性質：線性表的性質：8 線性表是線性表是n(n0)n(n0)個結點的有限序列，個結點的有限序列，n n稱為表長；稱為表長；8 n=0n=0的表稱為空表的表稱為空表; ;8 數據元素呈線性關系數據元素呈線性關系, , 當線性表非空時，必存在唯當線性表非空時，必存在唯一的稱為一的稱為“第一個第一個”的數據元素的數據元素; ;也必存在唯一的也必存在唯一的稱為稱為“最后一個最后一個”的數據元素；的數據元素；8 除除a a1 1沒有前趨外，其他結點有且僅有一個直接前驅；沒有前趨外，其他結點有且僅有一個直接前驅；8 除除a an

3、 n沒有后繼外，其他結點有且僅有一個直接后繼沒有后繼外，其他結點有且僅有一個直接后繼 2.1 線性表的類型定義抽象數據類型線性表的定義ADT List 數據對象數據對象：D=ai|aiElemSet,i=1,2,.,n,n0 數據關系數據關系：R1=|ai-1,aiD,i=2,.,n 基本操作：基本操作： InitList(&L) 操作結果：構造一個空的線性表操作結果：構造一個空的線性表L DestroyList(&L) 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：若操作結果：若L為空表，則返回為空表，則返回TRUE,否則返回否則返回FALSE。 ClearList(&L)

4、初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：將操作結果：將L重置為空表。重置為空表。 2.1 線性表的類型定義抽象數據類型線性表的定義ListEmpty(L) 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：若操作結果：若L為空表，則返回為空表，則返回TRUE,否則返回否則返回FALSE。ListLength(L) 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：返回操作結果：返回L中數據元素個數中數據元素個數GetElem(L,i,&e) 初始條件：線性表初始條件：線性表L已存在，已存在，1iListLength(L)。 操作結果：用操作結果：用

5、e返回返回L中第中第i個數據元素的值個數據元素的值LocateElem(L,e,compare() 初始條件：線性表已存在，初始條件：線性表已存在，compare()是數據元素判定函數。是數據元素判定函數。 操作結果：返回操作結果：返回L中第中第1個與個與e滿足關系滿足關系compare()的數據元素的數據元素的位序。若這樣的數據元素不存在，則返回值為的位序。若這樣的數據元素不存在，則返回值為0。 2.1 線性表的類型定義抽象數據類型線性表的定義PriorElem(L,cur_e,&pre_e) 初始條件：線性表初始條件：線性表L已存在。已存在。 操作結果：若操作結果：若cur_e是是L的數據

6、元素，且不是第一個，則用的數據元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，返回它的前驅，否則操作失敗，pre_e無定義。無定義。NextElem(L,cur_e,&next_e) 初始條件：線性表已存在。初始條件：線性表已存在。 操作結果操作結果:若若cur_e是是L的數據元素，且不是最后一個，則用的數據元素，且不是最后一個，則用next_e返回它的后繼，否則操作失敗，返回它的后繼，否則操作失敗，next_e無定義。無定義。ListInsert(&L,i,e) 初始條件：線性表初始條件：線性表L已存在，已存在，1iListLength(L)+1。 操作結果：在操作結果：在L中

7、第中第i個位置之前插入新的數據元素個位置之前插入新的數據元素e,L的長度的長度加加1。 2.1 線性表的類型定義抽象數據類型線性表的定義ListDelete(&L,i,&e) 初始條件：線性表初始條件：線性表L已存在且非空，已存在且非空，1iListLength(L)。 操作結果：刪除操作結果：刪除L的第的第i個數據元素，并用個數據元素，并用e返回其值返回其值,L的長度減的長度減1。ListTraverse(L,visit() 初始條件：線性表初始條件：線性表L已存在已存在 操作結果：依次對操作結果：依次對L的每個數據元素調用函數的每個數據元素調用函數visit()。一旦。一旦visit()失

8、敗，則操作失敗。失敗，則操作失敗。ADT List; 2.1 線性表的類型定義 通過對上述基本運算的組合調用，可以實現對線性表的復雜運算。 2.1 線性表的類型定義某種基本運算某種基本運算（黑箱）（黑箱）abcxy輸入數據輸入數據輸出數據輸出數據例：求兩個線性表La和Lb的并集 La = La U Lb ( 要求：“就地運算”，運算結果仍存放在La中, Lb銷毀) 算法思想： 從頭至尾取出從頭至尾取出Lb的每一個元素的每一個元素bi； 檢測檢測bi在在La中是否已經存在？中是否已經存在？ 若不存在，則將若不存在，則將bi插在插在La的的表尾位置表尾位置，成為，成為La的新的新表尾；若存在，則不

9、插。表尾；若存在，則不插。LbLa 2.1 線性表的類型定義算法實現：void Union(List &La,List &Lb)/求線性表求線性表La和和Lb的并集的并集 La_len=ListLength(La); /求求La的表長的表長 while(!EmptyList(Lb) /當當Lb還有元素還有元素 ListDelete(Lb, 1, e);/刪除刪除Lb的表頭元素賦給的表頭元素賦給e if(!LocateElem(La,e) ListInsert(La, +La_len, e); /如果如果La中不存在和中不存在和e相等的元素，將相等的元素，將e插在插在La的表尾的表尾 /whil

10、eDestroyList(Lb); /銷毀銷毀Lb/Union 2.1 線性表的類型定義例：求兩個線性表La和Lb的交集 La = La Lb 要求：“就地運算”,銷毀Lb。 算法思想： 對對La中的每個元素中的每個元素ai，檢測，檢測ai在在Lb中是否已經存中是否已經存在。若不存在，則將在。若不存在，則將ai 從從La表中刪除。表中刪除。LBLA 2.1 線性表的類型定義算法實現：void Intersect(List &La, List &Lb)/求兩個線性表的交集：求兩個線性表的交集：La=LaLbi=1; while(i=ListLength(La) GetElem(La, i, ai

11、); /讀讀ai if(!LocateElem(Lb, ai) ListDelete(La, i, e); /如果如果Lb中不存在和中不存在和ai相等的元素，則刪除相等的元素，則刪除La中中ai else i+; / while DestroyList(Lb); /銷毀銷毀Lb /Intersect 2.1 線性表的類型定義例：已知非純集合B，構造純集合A，A中只含B中所有值各不相同的成員 算法思想： 初始化一個新的空表初始化一個新的空表La。從表頭開始，逐個刪除。從表頭開始，逐個刪除Lb的每個元素的每個元素bi；判斷；判斷La中是否存在中是否存在bi，若不存在，若不存在，則將則將bi插在插在

12、La的表尾。最后銷毀集合的表尾。最后銷毀集合B。 2.1 線性表的類型定義算法實現：void Purge(List &La, List &Lb)/構建構建Lb的純集合的純集合LaInitList(La); La_len=0; /創(chuàng)建空表創(chuàng)建空表La while(!EmptyList(Lb) /當當Lb還有元素還有元素 ListDelete(Lb, 1, e);/刪除刪除Lb的表頭元素賦給的表頭元素賦給e if(!LocateElem(La,e) ListInsert(La, +La_len,e);/如果如果La中不存在和中不存在和e相等的元素，將相等的元素，將e插在插在La的表尾的表尾/whi

13、leDestroyList(Lb); /銷毀銷毀Lb/Union 2.1 線性表的定義例：判斷兩個集合La和Lb是否相等（算法2.3）“集合相等集合相等”：集合中元素個數相同；集合中元素個數相同；每個元素一一對應；每個元素一一對應；但元素的排列次序不一定相同但元素的排列次序不一定相同算法思想： 首先檢查兩個表的長度，如果不相等，則能得出兩個集合不首先檢查兩個表的長度，如果不相等，則能得出兩個集合不相等的結論，結束算法。相等的結論，結束算法。 建立建立LaLa的副本的副本LcLc；檢測；檢測LbLb中的每個元素中的每個元素b bi i，如果，如果b bi i在在LcLc中不中不存在，則能得出不相

14、等的結論；存在，則能得出不相等的結論； 如果如果b bi i在在LcLc中存在，則將中存在，則將LcLc中與中與b bi i相等元素刪去。上步中如相等元素刪去。上步中如果每個果每個b bi i都存在于都存在于LcLc中，則兩個集合相等。中，則兩個集合相等。 銷毀銷毀LcLc。 2.1 線性表的定義算法實現：bool isequal( List La, List Lb) /判斷集合判斷集合La和和Lb是否相等是否相等La_len=ListLength(La); /求求La表長表長 Lb_len=ListLength(Lb);/求求Lb表長表長 if(La_len!=Lb_len) return

15、FALSE; InitList (Lc); /初始化初始化Lcfor(i=1;i=La_len;i+) /建立建立La的副本的副本LcGetElem(La, i, ai); ListInsert(Lc,i,ai); /未完，接下頁未完，接下頁 2.1 線性表的定義 /續(xù)上頁續(xù)上頁 found=TRUE； /輔助變量輔助變量found用來作為查找標志用來作為查找標志for(k=1;k=Lb_len & found; k+)GetElem(Lb, k, e); /讀取讀取Lb中第中第k個元素個元素ei=LocateElem(Lc,e);if(i=0) found=FALSE; /e在在Lc中不存在

16、中不存在,改標志改標志else ListDelete(Lc,i,e); /存在，存在，Lc中刪除中刪除e/for DestroyList(Lc);return found;思考其它算法？（一定要建立La的副本Lc嗎？） 2.1 線性表的定義例：將兩個有序線性表La和Lb歸并成一個線性表Lc ( “異地運算”，運算結果放在第三個線性表Lc中 ) 算法思想： 設設La和和Lb中的元素都是非遞減有序排列。中的元素都是非遞減有序排列。 分別從頭至尾逐個讀取分別從頭至尾逐個讀取La和和Lb中的每個元素中的每個元素ai和和bj；比較兩個元素的大小：如果；比較兩個元素的大小：如果aibj，則將，則將ai插入

17、插入Lc的表尾，的表尾，i+；反之將；反之將bj插入插入Lc的表尾的表尾, j+; 直至一個表被掃描完，另一個表中的剩余元素一一插直至一個表被掃描完，另一個表中的剩余元素一一插入入Lc的表尾。的表尾。 2.1 線性表的定義La35811Lb268911 15 20Lcijk235688911111520 2.1 線性表的定義算法實現：算法實現：void MergeList ( List La, List Lb, List &Lc) /將有序線性表將有序線性表La和和Lb歸并成有序線性表歸并成有序線性表Lci = j = 1; k=0; InitList (Lc); /初始化初始化 La_len

18、=ListLength(La);Lb_len=ListLength(Lb);/求表長求表長 while (i=La_len & j=Lb_len) /La和和Lb均非空均非空 GetElem(La, i, ai); GetElem(Lb, j, bj);/讀讀ai和和bj if(ai=bj)ListInsert(Lc, +k, ai ); i+; else ListInsert(Lc, +k, bj); j+; while(i=La_len) /La中剩余元素一一插入中剩余元素一一插入Lc GetElem(La,i+,ai); ListInsert(Lc, +k, ai);while(j=Lb

19、_len) /Lb中剩余元素一一插入中剩余元素一一插入LcGetElem(Lb,j+, bj); ListInsert(Lc, +k, bj);/ MergeList 2.1 線性表的定義第二章 線性表本章內容提要 2.1 線性表的定義 2.2 線性表的順序表示和實現順序表 2.3 線性表的鏈式表示和實現鏈表 2.4 線性表的應用舉例一元多項式的表示與實現2.2 線性表的順序表示和實現順序表c用一組用一組地址連續(xù)地址連續(xù)的空間存放線性表的數據元素。各的空間存放線性表的數據元素。各元素按其邏輯次序依次存放；元素按其邏輯次序依次存放；c采用順序存儲結構存儲的線性表又稱為采用順序存儲結構存儲的線性表

20、又稱為順序表順序表；c順序表的特點：順序表的特點： 邏輯上相鄰的元素，物理位置上也相鄰；邏輯上相鄰的元素，物理位置上也相鄰； 元素之間的邏輯關系通過物理位置的先后來體現元素之間的邏輯關系通過物理位置的先后來體現 2.2 線性表的順序表示和實現順序表元素物理地址的計算:LOC(ai+1)=LOC(ai)LLOC(ai)=LOC(a1)(i-1)L a1a2ai-1aiai+1anL0C(a1)L0C(ai)L 2.2 線性表的順序表示和實現順序表順序存儲結構的類型定義：const LIST_INIT_SIZE=100; /線性表的初始存儲空間線性表的初始存儲空間const LISTINCREME

21、NT=10; /線性表的增量空間線性表的增量空間typedef struct ElemType*elem;/基地址指針基地址指針 intLength;/線性表的長度線性表的長度 intListsize;/線性表的存儲容量線性表的存儲容量 /為為listsize*sizeof(ElemType)SqList; 2.2 線性表的順序表示和實現順序表a1a2ai-1aiai+1an01i-2i-1in-1L.elemL.elem+L.length-1L.elem+L.listsize-1L.length空閑空間空閑空間L.listsize順序表存儲結構示意圖SqList L; 2.2 線性表的順序表

22、示和實現順序表listsizelengthelem線性表的基本運算在順序表上的實現： 初始化空順序表：Status InitList_sq(SqList &L) L.elem = new ElemType LIST_INIT_SIZE ;if(!L.elem) return OVERFLOW; /存儲分配失敗存儲分配失敗L.Length = 0;L.listsize = LIST_INIT_SIZE;return OK; /InitList_sq 2.2 線性表的順序表示和實現順序表線性表的基本運算在順序表上的實現： 查找元素操作(定位函數)：int LocateElem(SqList &L,

23、 ElemType e) p=L.elem; i=1;while(i=L.length & *p+!=e) i+;return i=L.length ? i : 0;時間復雜度：時間復雜度：O(n) 2.2 線性表的順序表示和實現順序表讀表元操作：Status GetElem(Sqlist L, int i, ElemType &e) if(iL.length) return ERROR; /i非法非法 e=*(L.elem + i - 1); return OK; 對于順序存儲結構而言，讀表元非常容易，因為元對于順序存儲結構而言，讀表元非常容易，因為元素的邏輯位置與物理下標存在簡單的線性關系

24、。時間復素的邏輯位置與物理下標存在簡單的線性關系。時間復雜度是雜度是O(1)O(1)級的級的。 所以說，順序表是一種順序存儲，隨機存取的結構/e=L.elemi-1; 2.2 線性表的順序表示和實現順序表線性表的基本運算在順序表上的實現： 銷毀線性表：void DestroyList(SqList &L) /釋放順序表釋放順序表L所占的空間所占的空間delete L.elem;L.listsize=L.length=0; 2.2 線性表的順序表示和實現順序表a1a2 ai-101i-2i-1in-1n插入操作（前插）：8 插入后必須保證邏輯上相鄰的元素物理上也相鄰插入后必須保證邏輯上相鄰的元素

25、物理上也相鄰8 合法的插入位置合法的插入位置i有有n1個值，個值，i1.n+1e向右移一位anai+1ai 2.2 線性表的順序表示和實現順序表插入操作算法思想：1. 檢查插入位置檢查插入位置i是否合法：是否合法：1in1，共有，共有n+1個合法插入位置；個合法插入位置；2. 檢查數組中是否有空閑的空間放新元素。如果沒檢查數組中是否有空閑的空間放新元素。如果沒有，將數組增加有，將數組增加ListIncrement個結點個結點3. 將將an至至ai逐個右移一位逐個右移一位 /注意不是注意不是ai至至an4. 新元素新元素e放入下標為放入下標為i1的單元的單元5. 修改表長：修改表長：L.leng

26、th+必須大量移動元素2.2 線性表的順序表示和實現順序表Status ListInsert(SqList &L, int i, ElemType e) /將元素將元素e e插入到順序表插入到順序表L L的第的第i i個元素之前個元素之前 if(iL.length+1) return ERROR; / i/ i非法非法 if(L.length=L.listsize) /需要擴展數組需要擴展數組 newsize=L.listsize+LISTINCREMENT; newbase=(ElemType *)realloc(L.elem, newsize*sizeof(ElemType); if(!n

27、ewbase) exit(OVERFLOW); /擴展失敗擴展失敗 L.elem=newbase; L.listsize+=LISTINCREMENT; /end if /未完，接下頁未完，接下頁( (續(xù)前）續(xù)前） q=L.elem+i-1; /令令q指向指向ai for( p=L.elem+L.length-1; p=q; p-) /改其它類型的控制變量也可以改其它類型的控制變量也可以 *(p+1)=*p; /右移一位右移一位 *q=e; /將將e放入第放入第i個元素的位置上個元素的位置上 L.length +; return OK; /ListInsert /q=&L.elemi-1;插入

28、操作的時間性能分析：8在第在第 i 個元素之前插入新元素需要移動個元素之前插入新元素需要移動 n-i+1個元個元素素(1in+1) ；8設在第設在第 i個元素之前插入新元素的概率為個元素之前插入新元素的概率為pi；8做一次插入操作所需移動元素次數的期望值做一次插入操作所需移動元素次數的期望值(平均次平均次數數)為：為：8 如果在任何位置上做插入操作的概率相等，如果在任何位置上做插入操作的概率相等， 即即pi1/(n+1)，則，則) 1(11inpniiinsE2) 1(1111ninnniinsE 2.2 線性表的順序表示和實現順序表a1a2 ai-101i-2i-1n-2n-1刪除操作： 必

29、須保證刪除后邏輯上相鄰的元素物理上也相鄰必須保證刪除后邏輯上相鄰的元素物理上也相鄰向左移一位anaiai+1 2.2 線性表的順序表示和實現順序表刪除操作的算法：1. 檢查插入位置檢查插入位置 i 是否合法，是否合法，1in，n個刪除位個刪除位置；置；2. 將將ai+1至至an逐個左移一位逐個左移一位 /而不是而不是an至至ai+13. 修改表長：修改表長：L.length-也必須大量移動元素 2.2 線性表的順序表示和實現順序表Status ListDelete(SqList &L, int i, ElemType &e) /刪除順序表的第刪除順序表的第 i i 個元素，用個元素，用e e返

30、回被刪元素的值返回被刪元素的值if(iL.length) return ERROR; /i/i非法非法p=&(L.elemi1);/令指針令指針p p指向指向a ai i，p=L.elem+i-1;p=L.elem+i-1;e=*p;for(p+;p=L.elem+L.length-1; p+) *(p-1)=*p; /a/ai+1i+1a an n左移一位左移一位 L.length- ; /表的長度減表的長度減1 1return OK; /ListDelete /ListDelete 2.2 線性表的順序表示和實現順序表刪除操作的時間性能分析：8 刪除第刪除第 i (1in)個元素需要移動個

31、元素需要移動ni個元個元素；素；8 設刪除第設刪除第 i個元素個元素的概率為個元素個元素的概率為qi；做一次刪除操作所需移動元素次數的期望值做一次刪除操作所需移動元素次數的期望值(平平均次數均次數)為：為：8如果在任何位置上做刪除操作的概率都相等，如果在任何位置上做刪除操作的概率都相等， 即即qi1/n，則，則)(1inqniidelE21)(11ninnnidelE 2.2 線性表的順序表示和實現順序表銷毀順序表：Status DestroyList(SqList &L) /銷毀順序表銷毀順序表deleteL.elem; /釋放動態(tài)數組空間釋放動態(tài)數組空間L.listsize=0; L.le

32、ngth=0; return OK; /DestroyList/DestroyList 2.2 線性表的順序表示和實現順序表順序表其他運算舉例：逆置順序表逆置前：逆置前：(a1,a2,.,ai-1,ai,a1+1,.,an-1,an)逆置后：逆置后：(an,an-1,.,ai+1,ai,ai-1,.,a2,a1) 2.2 線性表的順序表示和實現順序表逆置順序表演示am01m-2m-1mn-2n-1an-1a2am-1am18 初始時在表頭和表尾各設一個指針初始時在表頭和表尾各設一個指針i i和和j j；8 互換互換i i、j j所指的元素；所指的元素；8 i+; j-;i+; j-;8 重復執(zhí)

33、行，直至重復執(zhí)行，直至i i和和j j相遇相遇。ijana12.2 線性表的順序表示和實現順序表void Invert ( ElemType *E，int s， int t ) /將數組將數組E E自下標自下標s s至下標至下標t t之間的元素逆置之間的元素逆置 while(st) Es+ Et- ; void InvertSqList( SqList &L ) /將順序表將順序表L L中的所有元素逆置中的所有元素逆置 Invert(L.elem, 0, L.length-1);2.2 線性表的順序表示和實現順序表順序表其他運算舉例：前m個元素與后n個元素互換其中，m+n=L.Length。初

34、態(tài)：a1a2.am-1amb1b2.bn-1bn01m-2m-1mm+1m+n-1移動后：b1b2.bn-1bna1a2.am-1am01n-2n-1nn+1m+n-101 m-2m-1m m+1 m+n-1b1b2.bn-1bn-1amam-1.a2a1方法1： O(m*n)2.2 線性表的順序表示和實現順序表逆置逆置a1a2.am-1amb1b2.bn-1bn01m-2m-1mm+1m+n-1逆置amam-1.a2a1bnbn-1.b2b101m-2m-1mm+1m+n-1b1b2.bn-1bna1a2.am-1am01m-2m-1mm-1n-2n-1方法2： T(n) = 3m/2 +

35、3n/2 + 3(m+n)/2 = 3(m+n) = O(m+n)2.2 線性表的順序表示和實現順序表前m個元素與后n個元素互換方法2void Exchange ( SqList L, int m ) /將順序表將順序表L L中前中前m m個元素與后個元素與后L,lengthL,lengthm m個元素互換位置個元素互換位置Invert ( L.elem, 0, m-1 );Invert ( L.elem, m, L.length-1 );Invert ( L.elem, 0, L.length-1 );2.2 線性表的順序表示和實現順序表順序表其他運算舉例：用順序表實現purgevoid p

36、urge(SqList &A, SqList &B)/已知已知A為空順序表，為空順序表，B可能為非純順序表可能為非純順序表/將順序表將順序表B中所有不同值的元素插入中所有不同值的元素插入A（純表）中，然后銷毀（純表）中，然后銷毀B A.elem0=B.elem0; A.length=1; for(i=1;iB.length;i+) e=B.elemi; j=0; while(jnext=NULL;return OK;2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表L讀表元操作：Status GetElem (LinkList L, int i, ElemType &e) /L是帶頭結點的單鏈表

37、，讀是帶頭結點的單鏈表，讀L的第的第i個元素，用個元素，用e返回其值返回其值p=L-next; j=1; /指針指針p指向指向a1while(p & jnext; j+; /指針指針p右移右移i1次次if(!p|ji)return ERROR; /i非法非法 !p：i太大太大,ji：i太小太小e=p-data; return OK； /GetElem O(n)不能根據不能根據i i算出算出a ai i的地址，直接讀。只能從頭結點開始一個一個的地址，直接讀。只能從頭結點開始一個一個向后摸。這是一種向后摸。這是一種隨機存儲，順序存取的結構。的結構。2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表求

38、表長：int ListLength ( LinkList L ) / L是帶頭結點的單鏈表是帶頭結點的單鏈表p=L-next; n=0;while(p) n+; p=p-next;return (n); /ListLength O(n)2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表插入操作：Status ListInsert( LinkList &L, int i, ElemType e ) / L/ L是帶頭結點的單鏈表是帶頭結點的單鏈表, ,在在a ai i之前插入新結點之前插入新結點e e1. 指針指針p從頭結點開始，從頭結點開始，“摸摸”到到ai-1;2. 檢查檢查i的合法性的合法性

39、;3. 為新結點申請空間為新結點申請空間s;4. 修改指針：修改指針：s-next=p-next; p-next=s;epesa1ai1aianL2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表Status ListInsert( LinkList &L, int i, ElemType e ) / L/ L是帶頭結點的單鏈表是帶頭結點的單鏈表, ,在在a ai i之前插入新結點之前插入新結點e e p=L; j=0; /p/p指向頭結點，指向頭結點，j j是計數器是計數器 while(p & jnext; j+; /找指向找指向a ai-1i-1的的p p if (!p | ji-1) re

40、turn ERROR;/i/i非法非法,i,i大于表長或大于表長或i1idata=e; s-next=p-next; p-next=s; /修改指針修改指針 return OK; / ListInsert / ListInsert O(n)O(n) 特點：特點：不需要大量移動元素，只需修改指針。雖然時間復雜不需要大量移動元素，只需修改指針。雖然時間復雜度也是度也是O(n)O(n)，但時間是消耗在指針運動上。，但時間是消耗在指針運動上。Status ListInsert( LinkList &L, int i, ElemType e ) / L/ L是是不帶不帶頭結點的單鏈表頭結點的單鏈表, ,

41、在在a ai i之前插入新結點之前插入新結點e e if（idata=e; s-next=L; L=s; else p=L; j=0; /p/p指向頭結點，指向頭結點，j j是計數器是計數器 while(p & jnext; j+; / /令令p p指向指向a ai-1i-1 if(!p) return ERROR; /i /i太大，非法太大，非法 s=new Lnode；s-data=e; s-next=p-next; p-next=s; /修改指針修改指針 return OK; / ListInsert O(n) / ListInsert O(n) Status ListInsert1(

42、LinkList &L, LNode *p, LNode *s ) /L/L是不帶頭結點的單鏈表是不帶頭結點的單鏈表, ,將將s s所指的結點插在所指的結點插在p p所指的結點所指的結點之前之前 if(!L) return ERROR; /L/L是空表是空表 if(p=L) /* *p p是首元結點，特殊處理是首元結點，特殊處理 s-next=L; L=s; else q=L; while(q-next & q-next!=p) q=q-next; / / 找找p的前驅結點指針的前驅結點指針q if(q-next=NULL) return ERROR; /p/p不存在不存在 s-next=p;

43、 q-next=s; /修改指針修改指針 /else/else return OK; / ListInsert1 O(n)/ ListInsert1 O(n) 刪除操作:Status ListDelete( LinkList L, int i, ElemType &e ) / L/ L是是帶頭結點帶頭結點的單鏈表的單鏈表, ,刪除刪除a ai i，用參數，用參數e e帶回被刪結點的值帶回被刪結點的值1. 指針指針p從頭結點開始，從頭結點開始，“摸到摸到”ai-1;2.修改指針域：修改指針域： q=p-next; p-next=q-next; free(q); a1ai1aiai+1Lpq2.3

44、 線性表的鏈式表示和實現 線性鏈表線性鏈表Status ListDelete( LinkList L, int i, ElemType &e ) / L / L是是帶頭結點帶頭結點的單鏈表的單鏈表, ,刪除刪除a ai i，用參數，用參數e e帶回被刪結點的值帶回被刪結點的值 p=L; j=0; /p/p指向頭結點，指向頭結點，j j是計數器是計數器 while(p & jnext; j+; /p/p指向指向a ai-1i-1 if (!p | ji-1) return ERROR; / i / i非法非法 q=p-next; e=q-data; p-next=q-next; free(q);

45、 /修改指針修改指針 return OK; / ListInsert O(n) / ListInsert O(n) 特點：特點：也也不需要大量移動元素，只需修改指針。時間復雜度也不需要大量移動元素，只需修改指針。時間復雜度也是是O(n)O(n)，是消耗在指針運動上。，是消耗在指針運動上。2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表 舉例：創(chuàng)建單鏈表兩種處理方法：1. 頭插法： 插入點始終在表頭位置，被插元素總是新的表頭（逆序創(chuàng)建）； 2. 尾插法： 插入點始終在表尾位置，被插元素總是新的表尾（正序創(chuàng)建） 。2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表頭插法建單鏈表插入a1插入a2插入a

46、n初態(tài)：插入了a1后:插入了a2后:插入了an后:操作簡單，但鏈表操作簡單，但鏈表結點的排列次序剛結點的排列次序剛好與輸入次序相反好與輸入次序相反La1La2La1ana2a1L2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表ana2a1Les頭插時執(zhí)行的語句：(1) s-next=L-next；(2) L-next=s；2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表頭插法算法：void CreatList1( LinkList &L，int n ) /逆位序輸入逆位序輸入n n個元素的值，建立帶結點的單鏈表個元素的值，建立帶結點的單鏈表L L L=new LNode; /申請頭結點申請頭結

47、點 L-next=NULL; for(i=n;i0;i-) scanf(&e); /從鍵盤輸入一個元素值從鍵盤輸入一個元素值 s=(LNode*)malloc(sizeof(LNode); /申請新結點申請新結點 s-data=e; s-next=L-next; L-next=s; /插入鏈表插入鏈表 / for/ for / Head_Insert;/ Head_Insert;2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表尾插法建單鏈表插入a1插入a2插入an初態(tài)：初態(tài)：插入了插入了a1后后:插入了插入了a2后后:插入了插入了an后后:La1La1La2a1a2anL需要增設一個尾指針需要

48、增設一個尾指針r r，操作的方便程度不如頭操作的方便程度不如頭插法。但鏈表的順序與插法。但鏈表的順序與輸入順序一致。輸入順序一致。r r r r 2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表a1an-1anLes尾插時執(zhí)行的語句：(1) s-next=NULL(2) r-next=s(3) r=sr2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表尾插法算法：void CreateList2( LinkList &L，int n ) /從鍵盤正序輸入從鍵盤正序輸入n n個元素值，按尾插法創(chuàng)建帶頭結點的單鏈表個元素值，按尾插法創(chuàng)建帶頭結點的單鏈表L L L=new LNode; L-next=

49、NULL; /定義頭結點定義頭結點 r=L; /r /r是是L L的尾指針的尾指針 for(i=n;i0;i-) scanf(&e); /從鍵盤輸入一個元素值從鍵盤輸入一個元素值 s=new LNode; /申請新結點申請新結點 s-data=e; s-next=NULL; r-next=s; /將將s s插入鏈表尾插入鏈表尾 r=s; /修改尾指針修改尾指針 / for/ for /CreateList2/CreateList22.3 線性表的鏈式表示和實現 線性鏈表線性鏈表a3a2a1a4Lpa1逆置單鏈表方法1：用頭插法重組單鏈表2.3 線性表的鏈式表示和實現 線性鏈表線性鏈表void

50、ReverseLinkList1 ( LinkList &L ) / L / L是帶頭結點的單鏈表。用頭插法逆置是帶頭結點的單鏈表。用頭插法逆置L L p=L-next; /p /p指向指向a1a1 L-next=NULL; / /剝離頭結點剝離頭結點 while (p) q=p-next ; /用輔助指針用輔助指針q q“拽住拽住”p p的后繼的后繼 p-next=L-next ; L-next=p ; /將當前待插入鏈表中的首結點將當前待插入鏈表中的首結點* *p p插入插入L L中，成為中，成為L L的首結點的首結點 p=q ; /p,q/p,q后移后移 / while/ while /

51、ReverseLinkList1/ReverseLinkList12.3 線性表的鏈式表示和實現 線性鏈表線性鏈表方法2：將所有結點的next指針逆轉void ReverseLinkList2 ( LinkList &L ) / L/ L是帶頭結點的單鏈表的頭指針；是帶頭結點的單鏈表的頭指針；p p、q q、r r是三個輔助指針是三個輔助指針/在掃描鏈表的過程中進行逆置操作在掃描鏈表的過程中進行逆置操作 if ( !L-next ) return; /空表空表 p=L-next; q=p-next; /原表中，原表中，* *p p為為* *q q的前驅的前驅 p-next=NULL; /a /

52、a1 1的的nextnext置空指針，剝離頭結點置空指針，剝離頭結點 while (q) r=q-next ; /修改修改q-nextq-next之前，保存之前，保存q-nextq-next到到r r q-next=p ; /逆置表中，逆置表中，* *q q為為* *p p的前驅的前驅 p=q ; q=r ; /參與掃描的指針都需后移參與掃描的指針都需后移 L-next=p; /ReverseLinkList2 /ReverseLinkList22.3 線性表的鏈式表示和實現 線性鏈表線性鏈表靜態(tài)鏈表表示2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表 除了可以用前面的方法實現鏈表（動態(tài)鏈表）

53、外，有時，也可以用一維數組來描述線性鏈表靜態(tài)鏈表）。 其類型說明如下： #define MAXSIZE 1000 type struct ElemType data; int cur; component , SLinklistMAXSIZE; SLinklist s; /s為結構類型的數組，標識靜態(tài)鏈表2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表 設數組s的第i個元素s i 表示鏈表的第k個結點，則si.data存儲ak，si.cur指示ak+1在數組中的下標位置。 s0可看作頭結點，其指針域s0.cur指示鏈表的第一個結點的位置。如：L=(11,5,-12,25)，其靜態(tài)鏈表示意為:0

54、111122533-12442505MAXSIZE=8670為表尾標記為表尾標記備用空間備用空間2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表若在L的第2個元素之前插入新元素50,即L=(11,50,5,-12,25)，插入后的靜態(tài)鏈表示意為:0111152533-124425055026750插入到備用空插入到備用空間中，同時添加間中，同時添加指針指針cur,并修改并修改前驅結點的指針前驅結點的指針cur。2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表在L=(11,50,5,-12,25)上刪除第4個元素-12，刪除后的靜態(tài)鏈表示意為:0111152543-1244250550267刪除

55、刪除-12，需修改，需修改前驅結點的前驅結點的cur，同時被刪除的數同時被刪除的數組元素空間組元素空間s3和和s6、s7一塊一塊成為新的備用空成為新的備用空間間靜態(tài)鏈表的操作實現2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表在靜態(tài)鏈表中實現線性表的操作和動態(tài)鏈表相似，以整型游標i代替動態(tài)指針p，i=si.cur操作類似于指針的后移(p=p-next)。 靜態(tài)鏈表的插入和刪除操作同樣不需要移動元素，僅需修改游標（指針），所以靜態(tài)鏈表仍具有鏈式存儲結構的主要優(yōu)點，而且指針的修改也與動態(tài)單鏈表中的插入和刪除算法類似。 所不同的是，需由用戶自己實現malloc()和free()這兩個函數。 靜態(tài)鏈表

56、的操作實現2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表 為了辨明數組中那些元素空間未被使用，可以將所有未被使用過以及被刪除的元素空間用游標鏈成一個備用的鏈表，每當進行插入時，便可從備用鏈表上取得第一個結點作為待插入的新結點； 反之，在刪除時將從鏈表中刪除下來的結點鏈接到備用鏈表上。 靜態(tài)鏈表的操作實現2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表 舉例 在靜態(tài)鏈表中實現定位操作:int LocateElem(SLinklist s,ElemType e) /在靜態(tài)單鏈表s中查找第1個值為e的元素，返回它在s/中的位置，若找不到，返回0。 i=s0.cur; /取得表中第一個結點的位置 w

57、hile( i & si.data != e) i=si.cur; /在表中順鏈查找 return i; /LocateElem靜態(tài)鏈表的操作實現2.3 線性表的鏈式表示和實現 靜態(tài)鏈表靜態(tài)鏈表 舉例 P33 例2-32.3 線性表的鏈式表示和實現線性鏈表循環(huán)鏈表雙向鏈表2.3 線性表的鏈式表示和實現 循環(huán)鏈表2.3.2 循環(huán)鏈表 a1a2an-1anhead單鏈表單鏈表 在普通單鏈表中，從某個結點開始，沿著向在普通單鏈表中，從某個結點開始，沿著向后鏈，不能遍歷完線性表的全部結點后鏈，不能遍歷完線性表的全部結點。p2.3 線性表的鏈式表示和實現 循環(huán)鏈表 a1a2an-1anhead單鏈表 a

58、1a2an-1anhead帶頭結點的循環(huán)單鏈表a1a2an-1anhead不帶頭結點的循環(huán)單鏈表p2.3 線性表的鏈式表示和實現 循環(huán)鏈表 在循環(huán)單鏈表中，從任意一個結點出發(fā)，沿著在循環(huán)單鏈表中，從任意一個結點出發(fā)，沿著向后鏈能夠訪問到表中的所有元素；向后鏈能夠訪問到表中的所有元素； 對循環(huán)鏈表的操作與普通單鏈表基本相同，只對循環(huán)鏈表的操作與普通單鏈表基本相同，只是判表空和判斷表尾元素的條件有所不同是判表空和判斷表尾元素的條件有所不同: 判斷表尾：p-next = head 判斷表空：head-next = head2.3 線性表的鏈式表示和實現 循環(huán)鏈表帶頭結點的循環(huán)單鏈表 head空表：h

59、ead-next=head a1a2an-1anheada1a2an-1anheadp表尾結點：p-next=head空表：head=NULL表尾結點：p-next=headp2.3 線性表的鏈式表示和實現 循環(huán)鏈表 a1a2an-1anrear用尾指針引導的循環(huán)單鏈表這種循環(huán)鏈表真不錯，訪問表頭和表尾都很方便 a1a2an-1anhead頭結點：rear-next結點an：rear結點a1: rear-next-next用頭指針引導的循環(huán)單鏈表能直接訪問表頭，但不能直接訪問表尾例：將兩個循環(huán)單鏈表合并成一個循環(huán)單鏈表 a1a2an-1anRa b1b2bm-1bmRbvoid connect

60、( LinkList &Ra, LinkList Rb ) q=Rb-next; Rb-next=Ra-next; Ra-next=q-next; Ra=Rb; free(q); q2.3 線性表的鏈式表示和實現線性鏈表循環(huán)鏈表雙向鏈表2.3 線性表的鏈式表示和實現2.3.3 雙向鏈表priordatanext指向前驅指向后繼 在單鏈表中，通過向后鏈可以直接訪問一個結點的后繼，但是不能直接訪問到一個結點的前驅，只能從頭結點開始逐個向后摸。為了能直接訪問前驅，可以在每個結點上增加一個指向前驅的指針域prior。2.3 線性表的鏈式表示和實現 雙向鏈表priordatanext雙向鏈表的結點類型定