線性表--基本概念
一翘贮、定義
線性表（List）：由零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列。
注意：
- 首先它是一個(gè)序列，也就是說(shuō)元素之間是有個(gè)先來(lái)后到的士葫，即元素之間是有順序的。
- 若元素存在多個(gè)送悔，則第一個(gè)元素?zé)o前驅(qū)慢显，而最后一個(gè)元素?zé)o后繼，其他元素都有且只有一個(gè)前驅(qū)和后繼放祟。
- 另外鳍怨，線性表強(qiáng)調(diào)是有限的，事實(shí)上無(wú)論計(jì)算機(jī)發(fā)展到多強(qiáng)大跪妥，它所處理的元素都是有限的鞋喇。
如果用數(shù)學(xué)語(yǔ)言來(lái)進(jìn)行定義，可如下：
若將線性表記為（a1,…,ai-1,ai,ai+1,…an）,則表中ai-1領(lǐng)先于ai,ai領(lǐng)先于ai+1,稱ai-1是ai的直接前驅(qū)元素,ai+1是ai的直接后繼元素眉撵。
所以線性表元素的個(gè)數(shù)n(n>=0)定義為線性表的長(zhǎng)度侦香，當(dāng)n=0時(shí)，稱為空表纽疟。
二罐韩、抽象數(shù)據(jù)類型
數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。
例如很多編程語(yǔ)言的整型污朽，浮點(diǎn)型散吵，字符型這些指的就是數(shù)據(jù)類型。
來(lái)源：在計(jì)算機(jī)中蟆肆，內(nèi)存也不是無(wú)限大的，你要計(jì)算入1+1=2這樣的整型數(shù)字的加減乘除運(yùn)算炎功，顯然不需要開辟很大的內(nèi)存空間。
而如果要計(jì)算1.23456789+2.987654321這樣帶大量小數(shù)的蛇损，就需要開辟比較大的空間才存放的下赁温。
于是計(jì)算機(jī)的研究者們就考慮，要對(duì)數(shù)據(jù)類型進(jìn)行分類股囊，分出多種數(shù)據(jù)類型來(lái)適合各種不同的計(jì)算條件差異。
例如在C語(yǔ)言中毁涉，按照取值的不同，數(shù)據(jù)類型可以分為兩類：
- 原子類型：不可以再分解的基本類型贫堰，例如整型、浮點(diǎn)型其屏、字符型等喇勋。
- 結(jié)構(gòu)類型：由若干個(gè)類型組合而成偎行，是可以再分解的，例如整型數(shù)組是由若干整型數(shù)據(jù)組成的蛤袒。
抽象：是指抽取出事物具有的普遍性的本質(zhì)熄云。它要求抽出問(wèn)題的特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具體事物的一個(gè)概括妙真。抽象是一種思考問(wèn)題的方式缴允，它隱藏了繁雜的細(xì)節(jié)。
抽象數(shù)據(jù)類型（Abstract Data Type珍德，ADT）：是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作练般。
- 抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)锈候。
- 比如1+1=2這樣一個(gè)操作薄料，在不同CPU的處理上可能不一樣，但由于其定義的數(shù)學(xué)特性相同泵琳，所以在計(jì)算機(jī)編程者看來(lái)摄职，它們都是相同的。
- “抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性获列。
- 抽象數(shù)據(jù)類型不僅僅指那些已經(jīng)定義并實(shí)現(xiàn)的數(shù)據(jù)類型琳钉，還可以是計(jì)算機(jī)編程者在設(shè)計(jì)軟件程序時(shí)自己定義的數(shù)據(jù)類型。
- 例如一個(gè)3D游戲中蛛倦，要定位角色的位置，那么總會(huì)出現(xiàn)x,y,z三個(gè)整型數(shù)據(jù)組合在一起的坐標(biāo)啦桌。我們就可以定義一個(gè)point的抽象數(shù)據(jù)類型溯壶，它擁有x,y,z三個(gè)整型變量及皂，這樣我們就可以方便的對(duì)一個(gè)角色的位置進(jìn)行操作。
描述抽象數(shù)據(jù)類型的標(biāo)準(zhǔn)格式：
ADT 抽象數(shù)據(jù)類型名
Data
數(shù)據(jù)元素之間邏輯關(guān)系的定義
Operation
操作
endADT
三且改、線性表的抽象數(shù)據(jù)類型
定義：
ADT 線性表（List）
Data
線性表的數(shù)據(jù)對(duì)象集合為{a1,a2,…,an}验烧，每個(gè)元素的類型均為DataType。
其中又跛，除第一個(gè)元素a1外碍拆，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除了最后一個(gè)元素an外慨蓝，每一個(gè)元素有且只有一個(gè)直接后繼元素感混。
數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系。
Operation
InitList(*L): 初始化操作礼烈，建立一個(gè)空的線性表L弧满。
ListEmpty(L): 判斷線性表是否為空表，若線性表為空此熬，返回true庭呜，否則返回false。
ClearList(*L): 將線性表清空犀忱。
GetElem(L,i,*e): 將線性表L中的第i個(gè)位置元素值返回給e募谎。
LocateElem(L,e): 在線性表L中查找與給定值e相等的元素，如果查找成功阴汇，返回該元素在表中序號(hào)表示成功数冬；否則，返回0表示失敗鲫寄。
ListInsert(*L,i,e): 在線性表L中第i個(gè)位置插入新元素e。
ListDelete(*L,i,*e): 刪除線性表L中第i個(gè)位置元素戳玫，并用e返回其值未斑。
ListLength(L): 返回線性表L的元素個(gè)數(shù)。
endADT
對(duì)于不同的應(yīng)用府阀，線性表的基本操作是不同的芽突，上述操作是最基本的，
對(duì)于實(shí)際問(wèn)題中涉及的關(guān)于線性表的更復(fù)雜操作田巴，完全可以用這些基本操作的組合來(lái)實(shí)現(xiàn)。
例：實(shí)現(xiàn)兩個(gè)線性表A壹哺、B的并集操作，即要使得集合A=A∪B截珍。
分析：我們只需要循環(huán)遍歷集合B中的每個(gè)元素岗喉，判斷當(dāng)前元素是否存在A中隧饼，若不存在，則插入A中即可诞丽。
綜合分析拐格，我們需要運(yùn)用到幾個(gè)基本的操作組合即可：
ListLength(L);
GetElem(L,i,*e);
LocateElem(L,e);
ListInsert(*L,i,e);
實(shí)現(xiàn)代碼：
// La表示A集合，Lb表示B集合懂衩。
void unionL(List *La, list Lb)
{
int La_len, Lb_len, i;
ElemType e;
La_len = ListLength(*La);
Lb_len = ListLength(Lb);
for( i=1; i <= Lb_len; i++ )
{
GetElem(Lb, i, &e);
if( !LocateElem(*La, e) )
{
ListInsert(La, ++La_len, e);
}
}
}