第2章線性表1-定義與順序表示

1、李俊亭李俊亭數(shù)據(jù)結(jié)構(gòu)與算法- 定義與順序表示邏輯結(jié)構(gòu)唯一邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一存儲結(jié)構(gòu)不唯一運(yùn)算的實現(xiàn)依賴運(yùn)算的實現(xiàn)依賴于存儲結(jié)構(gòu)于存儲結(jié)構(gòu)第第2 2章章 線性表線性表第第3 3章章 棧和隊列棧和隊列第第4 4章章 串串第第5 5章章 數(shù)組和廣義表數(shù)組和廣義表 線性結(jié)構(gòu)線性結(jié)構(gòu)在數(shù)據(jù)元素的非空有限集中，有且僅有一個開在數(shù)據(jù)元素的非空有限集中，有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個直接前趨和一個直接后繼。一個直接前趨和一個直接后繼。可表示為可表示為：（：（a1 , a2 , , an） 線性結(jié)構(gòu)的特點(diǎn)：線性結(jié)構(gòu)的特點(diǎn)：（邏輯

2、、存儲（邏輯、存儲和運(yùn)算）和運(yùn)算）（a1, a2, ai-1，ai, ai1 ，, an）1. 線性表的定義：線性表的定義：是是n個數(shù)據(jù)元素的有限序列個數(shù)據(jù)元素的有限序列n=0時稱為時稱為數(shù)據(jù)元素數(shù)據(jù)元素線性起點(diǎn)線性起點(diǎn)ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總個為元素總個數(shù)，即表長數(shù)，即表長空表空表線性終點(diǎn)線性終點(diǎn) （ A, B, C, D, , Z）學(xué)號學(xué)號姓名姓名性別性別年齡年齡班級班級2004011810205于春梅于春梅女女 182004級信管級信管01班班2004011810260何仕鵬

3、何仕鵬男男 182004級信管級信管02班班2004011810284王王 爽爽女女 182004級信管級信管01班班2004011810360王亞武王亞武男男 182004級信管級信管02班班： ：例例2 分析學(xué)生情況登記表分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性元素間關(guān)系是線性數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性元素間關(guān)系是線性同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性線性表的抽象數(shù)據(jù)類型的定義：線性表的抽象數(shù)據(jù)類型的定義： ADT List 數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai|aiElemset,i=1,2,n,n0 數(shù)據(jù)

4、關(guān)系：數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n 基本操作：基本操作： InitList(l) 操作結(jié)果：構(gòu)造一個空的線性表L DestroyList(&l) 初始條件：線性表已存在 操作結(jié)果：銷毀線性表L ClearList(&l) 初始條件：線性表已存在 操作結(jié)果：置線性表L為空表 ListEmpty(L) 初始條件：線性表已存在 操作結(jié)果：若線性表L為空表，則返回TRUE，否則返回FALSE ListLenght(L) 初始條件：線性表已存在 操作結(jié)果：返回線性表L數(shù)據(jù)元素個數(shù) GetElem(L,i,&e) 初始條件：線性表已存在（1iListLenght(

5、L)） 操作結(jié)果：用e返回線性表L中第i個數(shù)據(jù)元素的值 locatElem(L,e,comare() 初始條件：線性表已存在,comare()是數(shù)據(jù)元素判定函數(shù) 操作結(jié)果：返回線性表L中第1個與e滿足關(guān)系comare()的數(shù)據(jù)元素的位序 PriorElem(L,cur_e,&pre_e) 初始條件：線性表已存在 操作結(jié)果：若cur_e是線性表L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義 NextElem(L,cur_e,&) 初始條件：線性表已存在 操作結(jié)果：若cur_e是線性表L的數(shù)據(jù)元素，且不是第最后一個，則用next_e返回它的后

6、繼，否則操作失敗，next_e無定義 ListInsert(&L,i,e) 初始條件：線性表已存在（1iListLenght(L)+1） 操作結(jié)果：在線性表L中第i個數(shù)據(jù)元素之前插入新元素e，L長度加1 ListDelete(&L,i,&e) 初始條件：線性表已存在（1iListLenght(L)） 操作結(jié)果：刪除線性表L中第i個數(shù)據(jù)元素，用e返回其值，L長度減1 ListTraverse(L,visit() 初始條件：線性表已存在 操作結(jié)果：依次對線性表L的每個數(shù)據(jù)元素調(diào)用visit()函數(shù)，一旦visit()失敗，則操作失敗 ADT List線性表的順序表示又稱為線

7、性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或或順序映像順序映像。順序存儲定義：順序存儲定義： 把邏輯上相鄰的數(shù)據(jù)元素存儲在把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。2.2.1 順序表的表示1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（他元素存放位置亦可求出（利用數(shù)組下標(biāo)利用數(shù)組下標(biāo)）。）。計算方法是：計算方法是： 設(shè)首元素設(shè)首元素a1的存放地址的存放地址為為LOC(a1)（稱為稱為首地址首地址），設(shè)

8、每個元素占用存儲空間（地址長），設(shè)每個元素占用存儲空間（地址長度）為度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地存放地址址為：為： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L一個一維數(shù)組，下標(biāo)的范圍是到

9、一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的，每個數(shù)組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是，則，則 的第一個字節(jié)的地址是的第一個字節(jié)的地址是 113因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址計算通式為：地址計算通式為：LOC(ai) = LOC(a1) + L *（i-1）線性表的順序存儲結(jié)構(gòu)定義（靜態(tài)）#define MAXSIZE 100typedef struct ElemType elemMAXSIZE; int length;SqLi

10、st;數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：初始化、插入、刪除、初始化、插入、刪除、查找、排序、修改查找、排序、修改 1）初始化： InitList_Sq(SqList &L) L.elem = (ElemType*)malloc(LIST_INIT_SIZE* sizeof(ElemType) if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize = LIST_INIT_SIZE; return OK;2)2)插入插入 在線性表的第在線性表的第i i個位置個位置前前插入插入一個元素一個元素實現(xiàn)步驟：實現(xiàn)步驟： 將第將第n至第至

11、第i 位的元素向后移動一個位置；位的元素向后移動一個位置； 將要插入的元素寫到第將要插入的元素寫到第i個位置；個位置； 表長加表長加1。注意：注意：事先應(yīng)判斷事先應(yīng)判斷: 插入位置插入位置i 是否合法是否合法?表是表是否已滿否已滿? 長度為n的線性表變?yōu)殚L度為n+1的線性表 （a1,a2,ai-1,ai,an）（a1,a2,ai-1,x,ai,an）程序：ListInsert_sq(SqList &l,int i,elemtype x)if (il.length) return(ERROR);if(l.length=MAXSIZE) return(OVERFLOW);for(j=l.l

12、ength;j=i;j-) l.elemj=l.elemj-1;l.elemj=x;l.length+;return(OK);實現(xiàn)步驟：實現(xiàn)步驟：l將第將第i +1至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置；l表長減表長減1。注意：注意：事先需要判斷，事先需要判斷，刪除位置刪除位置i 是否合法是否合法?3)3)刪除刪除 刪除刪除線性表的第線性表的第i i個位置上的元素個位置上的元素 使：長度為n的線性表變?yōu)殚L度為n-1的線性表。（a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an）ListDelete_sq(Sqlist &L，int

13、 i, ElemType &e) if(iL.length) return ERROR; for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj; L.length-; 時間效率分析時間效率分析: 插入算法花費(fèi)的時間，主要在于循環(huán)中元素的后移。但是，插入的位置是不固定的，當(dāng)插入位置i=1時，全部元素都得移動，需n次移動，當(dāng)i=n時，不需移動元素，故在i位置插入時移動次數(shù)為n-i+1。 刪除算法花費(fèi)的時間，主要在于循環(huán)中元素的前移.但是，刪除的位置是不固定的，當(dāng)刪除位置i=1時，全部元素都得移動，需n-1次移動，當(dāng)i=n時，不需移動元素，故在i位置刪除時移動

14、次數(shù)為n-i-1.假定在表中任意位置插入、刪除元素都是等假定在表中任意位置插入、刪除元素都是等概率的，概率的，插入概率插入概率p(i)=1/(n+1) ，刪除概率，刪除概率q(i)=1/n ，則：，則：插入操作時間效率（平均移動次數(shù)）插入操作時間效率（平均移動次數(shù)） 2) 1(11) 1(1111ninninpEniniiis刪除操作時間效率（平均移動次數(shù)）刪除操作時間效率（平均移動次數(shù)） 21)(1)(11ninninqEniniidl顯然，順序表的顯然，順序表的空間空間復(fù)雜度復(fù)雜度S(n)=O(1)S(n)=O(1)（沒有占用輔助空間）（沒有占用輔助空間）線性表線性表順序存儲結(jié)構(gòu)特點(diǎn)順序存儲結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰；個元素在物理存儲位置上也相鄰；優(yōu)點(diǎn)：優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素可以隨機(jī)存取表中任一元素O(1)；存儲空；存儲空間使用緊湊間使用緊湊缺點(diǎn)：缺點(diǎn)：在插入，刪除某一元素時，需要移動大量在插入，刪除某一元素時，需要移動大量元素元素O(n); ;預(yù)先分配空間需按最大空間分配，預(yù)先分配空間需按最大空間分配，利用不充分利用不充分; ;表容量難以擴(kuò)充表容量難以擴(kuò)充為克服這一缺點(diǎn)，我們引入另