第二章-線性表

1、n理解線性表的理解線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)特性特性n熟練掌握線性表的熟練掌握線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的描述方的描述方法，以及在該存儲結(jié)構(gòu)下的法，以及在該存儲結(jié)構(gòu)下的基本操作基本操作n熟練掌握線性表的熟練掌握線性表的鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)的描述方的描述方法，靈活使用法，靈活使用單鏈表單鏈表、雙鏈表雙鏈表、循環(huán)鏈表循環(huán)鏈表，學會在相應(yīng)存儲結(jié)構(gòu)下實現(xiàn)其各種學會在相應(yīng)存儲結(jié)構(gòu)下實現(xiàn)其各種基本算基本算法法及相關(guān)的時間性能分析及相關(guān)的時間性能分析n一元多項式一元多項式的表示和相加的表示和相加第二章第二章 線性表線性表2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義

2、2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義ADT List 數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai |ai ElemSet, i=1, 2, , n, n 0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1=| ai-1, ai D, i=1, 2, , n 基本操作：基本操作： InitList(&L) 操作結(jié)果：操作結(jié)果：構(gòu)造一個空的線性表構(gòu)造一個空的線性表L DestroyList(&L) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：操作結(jié)果：銷毀線性表銷毀線性表2.1 線性表的類型定義線性表的類型定義 ClearList(&L) 初始條件：線

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

4、返回L中第中第i個元素的值個元素的值 LocateElem( L, e, compare( ) ) 初始條件：線性表初始條件：線性表L已存在，已存在，compare( )是元素判定是元素判定 函數(shù)函數(shù) 操作結(jié)果：操作結(jié)果：返回返回L中第中第1個與個與e滿足關(guān)系滿足關(guān)系compare( )的的 元素的位序元素的位序。若這樣的元素不存在，則。若這樣的元素不存在，則 返回值為返回值為0 PriorElem( L, cur_e, &pre_e ) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：若操作結(jié)果：若cur_e是是L的元素，但不是第一個，則的元素，但不是第一個，則 用用pre

5、_e 返回它的前驅(qū)返回它的前驅(qū)，否則操作失敗，否則操作失敗，pre_e無定義無定義2.1 線性表的類型定義線性表的類型定義NextElem( L, cur_e, &next_e ) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：若操作結(jié)果：若cur_e是是L的元素，但不是最后一個，則的元素，但不是最后一個，則用用next_e返回它的后繼返回它的后繼，否則操作失敗，否則操作失敗，next_e無定義無定義 ListTraverse(L, visit( ) 初始條件：線性表初始條件：線性表L已存在已存在 操作結(jié)果：依次操作結(jié)果：依次對對L的每個元素調(diào)用函數(shù)的每個元素調(diào)用函數(shù)vis

6、it( )。一。一 旦旦visit( )失敗，則操作失敗失敗，則操作失敗2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.1 線性表的類型定義線性表的類型定義2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)邏輯地址邏輯地址數(shù)據(jù)元素數(shù)據(jù)元素存儲地址存儲地址 數(shù)據(jù)元素數(shù)據(jù)元素0k0Loc(k0)k01k1Loc(k0)+ck

7、1ikiLoc(k0)+i*ckin-1kn-1Loc(k0)+(n-1)*ckn-1 線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(jié)構(gòu)示意圖 11) 1(niiisinpE11npi211111ninnEniisniidlinqE1)(nqi12111ninnEnidlLiZhaoQianSunZhouWuZhengWang a1ana2.頭指針頭指針H頭結(jié)點頭結(jié)點H單鏈表結(jié)構(gòu)：單鏈表結(jié)構(gòu)：注意注意頭指針頭指針，頭結(jié)點頭結(jié)點等概念的不同含義。等概念的不同含義。 HHH HH H作業(yè)要求作業(yè)要求本章作業(yè)1、簡述下列概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點（第一個元素、簡述下列概念的區(qū)別：頭指針，頭結(jié)

8、點，首元結(jié)點（第一個元素結(jié)點）。結(jié)點）。2、填空：、填空：（1）在順序表中插入或刪除一個元素，需要平均移動）在順序表中插入或刪除一個元素，需要平均移動_個元素，個元素，具體移動的元素個數(shù)與具體移動的元素個數(shù)與_有關(guān)。有關(guān)。（2）順序表中邏輯上相鄰的元素的物理位置）順序表中邏輯上相鄰的元素的物理位置_緊鄰。單鏈表緊鄰。單鏈表中邏輯上相鄰的元素的物理位置中邏輯上相鄰的元素的物理位置_緊鄰。緊鄰。（3）單鏈表中，除了元首結(jié)點外，任一結(jié)點的存儲位置由）單鏈表中，除了元首結(jié)點外，任一結(jié)點的存儲位置由_指示。指示。（4）在單鏈表中設(shè)置頭結(jié)點的作用是）在單鏈表中設(shè)置頭結(jié)點的作用是_。3、簡答：什么情況下用順

9、序表比鏈表好？、簡答：什么情況下用順序表比鏈表好？本章作業(yè)4、已知、已知L是無表頭結(jié)點的單鏈表，且是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元結(jié)點，也不結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從一下選項中選擇合適的語句序列。是尾元結(jié)點，試從一下選項中選擇合適的語句序列。 A、在、在P結(jié)點后插入結(jié)點后插入S結(jié)點的語句序列是結(jié)點的語句序列是_ B、在、在P結(jié)點后插入結(jié)點后插入S結(jié)點的語句序列是結(jié)點的語句序列是_ C、在表首插入、在表首插入S結(jié)點的語句序列是結(jié)點的語句序列是_ D、在表尾插入、在表尾插入S結(jié)點的語句序列是結(jié)點的語句序列是_（1）P-next=S; (2) P-next=P-next-nex

10、t; (3) P-next=S-next; （4）S-next=P-next; (5) S-next=L; (6) S-NULL; (7) Q=P; （8）while(P-next!=Q) P=P-next; (9) while(P-next!=NULL) P=P-next; (10) P=Q; (11)P=L; (12)L=S; (13)L=P; 5、指出以下算法中的錯誤和低效（即費時）之處，并將其改寫為一個既正確、指出以下算法中的錯誤和低效（即費時）之處，并將其改寫為一個既正確又高效的算法。又高效的算法。 Status Delete K （SqList &a, int i, int k）/本過程從順序存儲結(jié)構(gòu)的線性表本過程從順序存儲結(jié)構(gòu)的線性表a /中刪除第中刪除第i個元素起的個元素起的k個元素個元素 if (i1ka.length) return INFEASIBLE /參數(shù)不合法參數(shù)不合法 else for(count=1;count=i+1; j-) a.elemj-1=a.elemj; a.length-； return OK； /DeleteK6、設(shè)順序表、設(shè)順序表va中的數(shù)據(jù)