第三章線性表

1、第三章 線 性 表西南林學(xué)院計(jì)算機(jī)與信息科學(xué)系董躍宇內(nèi)容提要n線性結(jié)構(gòu)的特點(diǎn)n抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)n三種主要存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)n存在唯一的“第一個(gè)”數(shù)據(jù)元素n存在唯一的“最后一個(gè)”數(shù)據(jù)元素n除了第一個(gè)元素外，每個(gè)元素均只有一個(gè)前驅(qū)n除最后一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼線性表的類型定義n線性表是最常見最簡單的一種數(shù)據(jù)結(jié)構(gòu)，是 n 個(gè)數(shù)據(jù)元素的有限序列n線性表中的數(shù)據(jù)元素可以是各種各樣的n線性表中數(shù)據(jù)元素的個(gè)數(shù)叫做線性表的長度，長度為零稱為空表n可對線性表的元素進(jìn)行訪問，還可以進(jìn)行插入和刪除等線性表的類型定義nADT List數(shù)據(jù)對象：D=ai | ai 屬于ElemSet , i=

2、1,2,n,n=0數(shù)據(jù)關(guān)系：R1= | ai-1,ai屬于D,i=2,n基本操作：InitList(L)DestroyList(L)ClearList(L)ListEmpty(L)ListLength(L)GetElem(L,i, e)LocateElem(L,e,compare()PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,&e)ListDelete(&L,i,&e)ListTraverse(L,visit()ADT List數(shù)據(jù)對象數(shù)據(jù)關(guān)系一組數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)程序算法結(jié)構(gòu)?操作線性表的順序表示和實(shí)現(xiàn)ab

3、cdefgabcdefg何謂順序結(jié)構(gòu)？n順序映射邏輯結(jié)構(gòu)中相鄰的元素，在物理結(jié)構(gòu)中亦相鄰n物理結(jié)構(gòu)的組織方式是順序的C語言虛擬機(jī)上順序結(jié)構(gòu)的實(shí)現(xiàn)n靜態(tài)順序結(jié)構(gòu)q簡單講，即采用數(shù)組作為物理存儲(chǔ)結(jié)構(gòu)n動(dòng)態(tài)順序結(jié)構(gòu)q借助內(nèi)存分配函數(shù)獲得連續(xù)的存儲(chǔ)空間作為物理存儲(chǔ)結(jié)構(gòu)靜態(tài)順序存儲(chǔ)7abcdefg動(dòng)態(tài)順序存儲(chǔ)abcdefgelem79順序存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)n操作定義源自數(shù)據(jù)結(jié)構(gòu)本身，操作的實(shí)現(xiàn)細(xì)節(jié)則受制于數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)n以PriorElem(),NextElem(),ListInsert(),ListDelete()為例PriorElem()的實(shí)現(xiàn)abcdefgabcdefgCur_elem:ar

4、ray4array4 不是第一個(gè)元素pri_elem:array4-1NextElem()的實(shí)現(xiàn)abcdefgabcdefgCur_elem:array4array4 不是最后一個(gè)元素next_elem:array4-1ListInsert()的實(shí)現(xiàn)abcdefgabcdefgzListDelete()的實(shí)現(xiàn)abcdefgabcdefg鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)abcdefgnullheadabcdefg0001010000110031014100801102鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的簡單比較abcdefgnullheadabcdefg0001010000110031014100801102abcdefg

5、0009001300170021002500290033鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)n操作定義源自數(shù)據(jù)結(jié)構(gòu)本身，操作的實(shí)現(xiàn)細(xì)節(jié)則受制于數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)n以PriorElem(),NextElem(),ListInsert(),ListDelete()為例NextElem()abcdefgnullheadabcdefgcur_elemcur_elemnextPriorElem()abcdefgnullheadabcdefgcur_elem第四個(gè)第三個(gè)pri_elemListInsert()abcdefgnullheadabcdefgzzListDelete()abcdefgnullheadabcdefg一個(gè)一般性結(jié)論n順序結(jié)構(gòu)簡單清晰，易于實(shí)現(xiàn)隨機(jī)訪問但在插入刪除時(shí)需進(jìn)行大量的數(shù)據(jù)移動(dòng)，效率不佳n鏈