抽象數(shù)據(jù)類型 （abstract data type惭等，ADT）
抽象數(shù)據(jù)類型是一些操作的集合蟋滴。抽象數(shù)據(jù)類型是數(shù)學(xué)中的定義蜒简，在ADT中颗味，我們不關(guān)心操作是如何被實(shí)現(xiàn)的嫁蛇。因此芬膝，這可以看做是模塊化的擴(kuò)充慧起。
例如表惩淳，樹，圖和它們的操作一起可以看做是抽象數(shù)據(jù)類型蹦疑，就想整數(shù)西雀，實(shí)數(shù)和布爾變量是數(shù)據(jù)類型一樣。整數(shù)必尼，實(shí)數(shù)和布爾變量有它們的操作蒋搜，抽象數(shù)據(jù)類型也有它們自己的操作。
表 ADT
我們將形如A1判莉，A2豆挽，A3，...券盅，An的一列數(shù)稱為表帮哈。
表的大小：表中的元素的個(gè)數(shù)稱為表的大小锰镀，大小為0的表稱為空表娘侍。
對(duì)于除空表外，我們稱Ai+1是Ai的后繼泳炉，Ai-1是Ai的前驅(qū)憾筏，其中表的第一個(gè)元素A1不定義前驅(qū)，最后一個(gè)元素An不定義后繼花鹅。
表的數(shù)組實(shí)現(xiàn)
對(duì)于表的所有操作都可以通過數(shù)組來實(shí)現(xiàn)氧腰，數(shù)組使得PrintList和Find以線性的時(shí)間執(zhí)行，而FindIndex則花費(fèi)常數(shù)的執(zhí)行時(shí)間刨肃。然而古拴，插入和刪除的代價(jià)是昂貴的，例如在第一個(gè)元素位置插入真友，需要將后面的所有元素往后移一個(gè)位置出來黄痪，同理刪除也是如此。因此這兩種操作的最壞情況是O(N)盔然。平均來看桅打，這兩種運(yùn)算都要移動(dòng)表的一半的元素，仍然需要線性時(shí)間愈案。
因?yàn)椴迦牒蛣h除的運(yùn)行時(shí)間是如此的慢挺尾，而且表的大小還需要事先知道，所以簡單數(shù)組一般不用來實(shí)現(xiàn)表的結(jié)構(gòu)刻帚。
鏈表
為了避免插入和刪除的線性開銷潦嘶，我們需要運(yùn)行表可以不連續(xù)存儲(chǔ)涩嚣，否則表的部分或全部需要整體移動(dòng)崇众，而如圖表達(dá)了鏈表的一般想法掂僵。
在鏈表中，每個(gè)結(jié)構(gòu)均包含有表元素和指向包含包含該元素后繼元素的結(jié)構(gòu)的指針顷歌，我們稱之為next指針锰蓬，最后一個(gè)元素的next指針指向null，ANSI C規(guī)定NULL為0眯漩。
程序設(shè)計(jì)細(xì)節(jié)
為了更方便的實(shí)現(xiàn)鏈表中的操作芹扭，我們通常會(huì)增加一個(gè)頭結(jié)點(diǎn)，并將它指向第一個(gè)元素赦抖。
//鏈表的結(jié)構(gòu)
struct Node;
typedef struct Node *ptrToNode ;
typedef ptrToNode List ;
typedef ptrToNode Position;
struct Node{
? ? ElementType Element;
? ? Position Next;
};
//判斷表是否為空
int IsEmpty(List L){
? ? return L->Next == NULL;
}
//判斷當(dāng)前是否為鏈表的末尾
int IsLast(Position P,List L){
? ? return P->Next == Null;
}
//查找函數(shù)
Position Find(Element X,List L){
? ? Position P;
? ? P = L->Next;
? ? while(P != NULL && P->Element != X){
? ? ? ? P = P->Next;
? ? }
? ? return P;
}
//刪除元素
void Delet(ElementType X,List L){
? ? Position P, TempNode;
? ? P = FindPrevious(X, L);
? ? if(!IsLast(P,L)){
? ? ? ? TempNode = P->Next;
? ? ? ? P->Next = TempNode->Next;
? ? ? ? free(TmpNode);
? ? }
}
//查找某元素的前一個(gè)元素
Position FindPrevious(ElementType X,List L){
? ? Position P;
? ? P = L;
? ? while(P->Next != NULL && P->Next->Element != X){
? ? ? ? P = P->Next;
? ? }
? ? return P;
}
//插入元素
void Insert(ElementType X,List L,Position P){
? ? Position TempNode ;
? ? TempNode = malloc(sizeof(struct Node));
? ? if(TempNode == NULL){
? ? ? ? printf("malloc error")舱卡；
? ? ? ? return ;
? ? }
? ? TempNode->Element = x;
? ? TempNode->Next = P->Next;
? ? p->Next = TempNode;
}
//刪除鏈表
void DeleteList(List L){
? ? Position P,Tmp;
? ? p = L->Next;
? ? L->Next = NULL;\
? ? while(p != NULL){
? ? ? ? Tmp = P->Next;
? ? ? ? free(p);
? ? ? ? p = Tmp;
? ? }
}
雙鏈表
當(dāng)涉及到倒序掃描鏈表時(shí)，雙鏈表就非常方便了队萤。雙鏈表和單鏈表的區(qū)別就是：雙鏈表中存在兩個(gè)指針域轮锥，一個(gè)指向當(dāng)前元素的前驅(qū)，另一個(gè)指向當(dāng)前元素的后繼要尔。有了雙向鏈表舍杜，可以不用在訪問當(dāng)前元素的前一個(gè)元素了，不過赵辕，雙鏈表方便的同時(shí)既绩，增加了空間的開銷。
循環(huán)鏈表
讓最后的單元指向第一個(gè)單元構(gòu)成循環(huán)还惠，這樣的鏈表被稱為循環(huán)鏈表饲握。它既可以有表頭，也可以沒有表頭（若有表頭吸重，則最后一個(gè)元素指針指向表頭）互拾。
案例實(shí)戰(zhàn)
一元多項(xiàng)式
我們可以用表來定義模擬一元多項(xiàng)式的抽象數(shù)據(jù)類型。對(duì)于大多數(shù)系數(shù)非零的多項(xiàng)式嚎幸，我們可以采用一個(gè)簡單的數(shù)組來進(jìn)行存儲(chǔ)颜矿，數(shù)組的下標(biāo)表示多項(xiàng)式的次冪，下標(biāo)的值表示多項(xiàng)式的系數(shù)嫉晶。但是對(duì)于系數(shù)相差較大骑疆，大部分的系數(shù)為0的多項(xiàng)式，采用數(shù)組將會(huì)浪費(fèi)極大的空間替废。下面我們就采用數(shù)組的方法來定義多項(xiàng)式的抽象數(shù)據(jù)類型箍铭。
typddef struct{
? ? int CoeffArray[ MaxDegree + 1 ];
? ? int HighPower;
}* Polynomial;
//多項(xiàng)式初始化為0
void ZeroPolynomial(Polynomial Poly){
? ? int i;
? ? for( i=0; i <= MakDegree; i++){
? ? ? ? Poly->CoeffArray[i] = 0;
? ? }
? ? Poly->HighPower = 0;
}
//兩個(gè)多項(xiàng)式相加
void AddPolynomial(const Polynomial poly1, const Polynomial poly2, Polynomial polysum){
? ? int i;
? ? ZeroPolynomial(polysum);
? ? polysum->HighPower = Max(poly1->HighPower，poly2->HighPower);
? ? for( i = polysum->HighPower; i>=0; i--){
? ? ? ? polysum->CoeffArray[i] = poly1->CoeffArray[i] + poly2->CoeffArray[i];
? ? }
}
//兩個(gè)多項(xiàng)式的乘法
void MultPolynomial(const Polynomial poly1, const Polynomial poly2, Polynomial polymult){
? ? int i,j;
? ? ZeroPolynomial(polymult);
? ? polymult->HighPower = poly1->HighPower + poly2->HighPower;
? ? if(polymult->HighPower > MaxDegree){
? ? ? ? printf("MaxDegree ERROR");
? ? }else{
? ? ? ? for( i=0; i <= poly1->HighPower; i++ ){
? ? ? ? ? ? for( j=0; poly2->HighPower; j++){
? ? ? ? ? ? ? ? polysum->CoeffArray[i+j] = poly1->CoeffArray[i] * poly2->CoeffArray[i];
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
