第三章線性表

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

2、1,2,n,n=0數(shù)據(jù)關系：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ù)關系一組數(shù)據(jù)結構數(shù)據(jù)結構程序算法結構?操作線性表的順序表示和實現(xiàn)ab

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

4、ray4array4 不是第一個元素pri_elem:array4-1NextElem()的實現(xiàn)abcdefgabcdefgCur_elem:array4array4 不是最后一個元素next_elem:array4-1ListInsert()的實現(xiàn)abcdefgabcdefgzListDelete()的實現(xiàn)abcdefgabcdefg鏈式存儲結構abcdefgnullheadabcdefg0001010000110031014100801102鏈式存儲結構與順序存儲結構的簡單比較abcdefgnullheadabcdefg0001010000110031014100801102abcdefg

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