數(shù)據(jù)結(jié)構(gòu)與算法分析：線性表ADT

線性表數(shù)據(jù)結(jié)構(gòu)與算法分析1線性表

2.1

線性結(jié)構(gòu)

2.2線性表ADT的設(shè)計與表示

2.3線性表ADT的應(yīng)用舉例

2數(shù)據(jù)邏輯關(guān)系數(shù)據(jù)元素可存在于非空有限集合中26個英文字母表（A，B，C，…，Z）某校從1978年到1983年各種型號計算機擁有量的變化情況（6，17，28，50，92，188）一個學(xué)校的學(xué)生健康情況登記表姓名學(xué)號性別年齡班級健康狀況張三050101男18計93健康李四050102男19計93一般………………3線性結(jié)構(gòu)的基本特征為:<a0,a1,…,an-1>1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。

線性結(jié)構(gòu)

是一個數(shù)據(jù)元素的有序（次序）集最簡單的線性結(jié)構(gòu)稱為線性表4Lists線性表是由數(shù)據(jù)項組成的一種有限且有序的序列.重要的概念:線性表中的每一個元素都有自己的位置.每一個元素都有一種數(shù)據(jù)類型線性表中不包含任何元素時，稱為空表。當(dāng)前存儲的元素數(shù)目稱為線性表的長度。線性表的開始結(jié)點稱為表頭（head）線性表的結(jié)尾結(jié)點稱為表尾（tail）有序線性表的元素按照值的遞增順序排列，而無序線性表在元素的值與位置之間就沒有特殊的聯(lián)系。我們將如何表示線性表?我們將實現(xiàn)什么操作呢?5線性表

2.1

線性結(jié)構(gòu)

2.2線性表ADT的設(shè)計與表示

2.3線性表ADT的應(yīng)用舉例

6抽象數(shù)據(jù)類型線性表的定義如下：ADTList{

數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n

為線性表的表長;稱n=0

時的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai

在線性表中的位序。}7

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

8線性表ADTtemplate<classElem>classList{public:virtualvoidclear()=0;virtualboolinsert(constElem&)=0;virtualboolappend(constElem&)=0;virtualbool

remove(Elem&)=0;virtualvoidsetStart()=0;virtualvoidsetEnd()=0;virtualvoidprev()=0;virtualvoidnext()=0;virtualint

leftLength()const=0;virtualint

rightLength()const=0;virtualbool

setPos(intpos)=0;virtualbool

getValue(Elem&)const=0;virtualvoidprint()const=0;};910前后的哥們，排隊太久了，離開一會，待會我還站在你們中間哈11線性表實現(xiàn)中的一些概念我們在線性表中將實現(xiàn)對當(dāng)前位置的支持.為了定義當(dāng)前位置的概念，假設(shè)線性表由左、右兩個分離部分組成.

其中任一部分或兩者可以為空.這兩個部分被一個柵欄（fence）分開.<20,23|12,15>12ListADTExamplesList:<12|32,15>MyList.insert(99);Result:<12|99,32,15>Iteratethroughthewholelist:for(MyList.setStart();MyList.getValue(it);

MyList.next())

DoSomething(it);13ListFindFunction//ReturntrueiffKisinlistboolfind(List<int>&L,intK){

intit;for(L.setStart();L.getValue(it); L.next())if(K==it)returntrue;//Founditreturnfalse;//Notfound}14線性表

2.1

線性結(jié)構(gòu)

2.2線性表ADT的設(shè)計與表示

2.3線性表ADT的應(yīng)用舉例

15

假設(shè):有兩個集合A和B，

現(xiàn)要求一個新的集合A＝A∪B。例

16AB171、問題分析和任務(wù)定義分析并確定要處理的對象（數(shù)據(jù)）是什么分析并確定要實現(xiàn)的功能是什么分析并確定處理后的結(jié)果如何顯示通過鍵盤輸入兩組整數(shù)，并分別存儲A和B中A＝A∪B把A中的元素顯示在顯示器上18測試數(shù)據(jù)（11，12，13，14）A（11，10，8）BA∪B

A

（11，12，13，14，10，8）（11，12，13，11）A（11，10，A）Berror192、數(shù)據(jù)類型和系統(tǒng)設(shè)計對問題描述中涉及的操作對象定義相應(yīng)的抽象數(shù)據(jù)類型，并設(shè)計合適的算法兩個集合A和B分別用兩個線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。20virtualvoidinit()const=0;virtualboolappend(constElem&)=0;virtualvoidsetStart()=0;virtualvoidnext()=0;virtualbool

getValue(Elem&)const=0;

Elem

int21程序的流程程序由三個模塊組成：輸入模塊：完成兩個集合的輸入，存入變量La和Lb中。計算模塊：設(shè)計一個求集合并的函數(shù)，void

union(List<int>&La,List<int>&Lb)

，兩個集合作為函數(shù)參數(shù)，計算結(jié)果通過第一個參數(shù)返回。輸出模塊：屏幕上顯示計算的結(jié)果。221．從線性表LB中依次察看每個數(shù)據(jù)元素;2．依值在線性表LA中進行查訪;3．若不存在，則插入之。setstartgetvalue（e）next（）

find（LA，e）setstartgetvalue（e）next（）

append(e)操作步驟：233、編碼實現(xiàn)和靜態(tài)檢查24voidunion(List<int>&La,List<int>&Lb){

intit,k;Statusstatus;for(Lb.setStart();Lb.getValue(it); Lb.next())//從線性表Lb中依次取出數(shù)據(jù)元素{ status=False; for(La.setStart();La.getValue(k); La.next())//從線性表La中依次取出數(shù)據(jù)元素 { if(k==it)status=True;//存在 } if(status!=True){ status=La.append(it);//添加 if(status!=success)break;//添加失敗則退出} }}25要點回顧從問題中的數(shù)據(jù)中發(fā)現(xiàn)其線性特征線性表