參考《數(shù)據(jù)結(jié)構(gòu)與算法分析-c語(yǔ)言描述》一書(shū)
1、抽象數(shù)據(jù)類(lèi)型
抽象數(shù)據(jù)類(lèi)型（abstract data type，ADT）是一些操作的集合。抽象數(shù)據(jù)類(lèi)型是數(shù)學(xué)的抽象艘包，在ADT的定義中根本沒(méi)涉及如何實(shí)現(xiàn)操作的集合，這可以看作模塊化設(shè)計(jì)的補(bǔ)充耀盗。
2想虎、表ADT
我們將處理一般的形如A1，A2叛拷，A3.......AN的表舌厨。這個(gè)表的大小是N，我們稱大小為0的表為空表忿薇。
2.1 鏈表的ADT：
鏈表由一系列不必再內(nèi)存中相連的結(jié)構(gòu)組成裙椭，每一個(gè)結(jié)構(gòu)均包含表元素和指向包含該元素后繼元的結(jié)構(gòu)的指針躏哩，我們稱之為Next指針。最后一個(gè)單元的Next指針指向NULL揉燃。我們通常給鏈表增加一個(gè)表頭節(jié)點(diǎn)（header）扫尺，這個(gè)表頭節(jié)點(diǎn)解決了以下的問(wèn)題：
1、如何在表的最前面插入元素炊汤。
2正驻、刪除第一個(gè)元素，因?yàn)楦淖兞吮淼钠鹗级饲栏幊讨械氖韬鰧?huì)造成表的丟失姑曙。
那么具有表頭的鏈表形式如下圖所示：
帶表頭的鏈表
我們使用結(jié)構(gòu)體來(lái)定義鏈表：
#include <stdio.h>
struct Node;
//將鏈表指針聲明為PtrToNode
typedef sturct Node *PtrToNode;
//將鏈表表頭元素聲明為L(zhǎng)ist
typedef PtrToNode List;
//將鏈表除表頭外的元素聲明為Postion
typedef PtrToNode Position;
//將指定的元素類(lèi)型，聲明為ElementType迈倍，這里是int
typedef int ElementType
struct Node{
ElementType Element;
Position Next;
}
接下來(lái)伤靠，我們實(shí)現(xiàn)一些基本的ADT操作。
鏈表的初始化：
List init()
{
List L;
L = (List)malloc(sizeof(struct Node));
if (L == NULL)
{
printf ("Out of space");
return NULL;
}
L -> Element = -999;
L -> Next = NULL;
return L;
}
鏈表的創(chuàng)建：
List Create(List L){
Position TmpCell;
ElementType X;
Position Cur = L;
printf("請(qǐng)輸入數(shù)字,-1結(jié)束\n");
scanf("%d",&X);
while (X!=-1)
{
TmpCell = (Position)malloc(sizeof(struct Node));
TmpCell -> Element = X;
TmpCell -> Next = NULL;
Cur -> Next = TmpCell;
Cur = TmpCell;
scanf("%d",&X);
}
return L;
}
鏈表的打邮谑荨：
void Print(List L)
{
Position P = L -> Next;
while (P!=NULL){
printf("%4d",P->Element);
P = P -> Next;
}
printf("\n");
}
鏈表的刪除：
void DeleteList(List L){
Position P,Tmp;
P = L -> Next;
L -> Next = NULL;
while (P!=NULL)
{
Tmp = P->Next;
free(P);
P = Tmp
}
}
判斷是否是空表：
int IsEmpty(List L)
{
return L->Next == NULL;
}
判斷當(dāng)前元素是否在鏈表的末尾：
int IsLast(Position P,List L)
{
return P->Next == NULL;
}
鏈表元素的查找：
Position Find(ElementType X,List L)
{
Position P = L -> Next;
while (P!=NULL && P->Element != X)
P = P -> Next;
return P;
}
鏈表元素的刪除：
void Delete2(ElementType X,List L)
{
Position P = L -> Next;
Position Q = L;
while (P!=NULL && P->Element != X)
{
Q = P;
P = P -> Next;
}
if (P!=NULL)
{
Q -> Next = P -> Next;
free(P);
}
}
2.2 雙向鏈表
雙向鏈表
2.3 循環(huán)鏈表
循環(huán)鏈表
2.4 鏈表實(shí)現(xiàn)多項(xiàng)式求和計(jì)算
書(shū)中并沒(méi)有給出具體的實(shí)現(xiàn)，這是小編自己編寫(xiě)的代碼竟宋，望多指點(diǎn)：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node * node;
struct Node{
int Coefficient;
int Exponent;
node Next;
};
//兩個(gè)多項(xiàng)式相加
node add(node head1,node head2)
{
node head = (node)malloc(sizeof(struct Node));
head -> Coefficient = -999;
head -> Exponent = -999;
head -> Next = NULL;
node p1 = head1 -> Next;
node p2 = head2 -> Next;
node cur = head;
//循環(huán)判斷提完，直到一個(gè)鏈表到尾部
while (p1!=NULL && p2!=NULL)
{
//如果p1的指數(shù)大于p2的指數(shù)
if (p1 -> Exponent > p2 ->Exponent)
{
node temp = (node)malloc(sizeof(struct Node));
temp -> Exponent = p1 ->Exponent;
temp -> Coefficient = p1 -> Coefficient;
temp -> Next = NULL;
cur -> Next = temp;
cur = temp;
p1 = p1 -> Next;
}
//如果p2的指數(shù)大于p1的指數(shù)
else if(p1 -> Exponent < p2 ->Exponent)
{
node temp = (node)malloc(sizeof(struct Node));
temp -> Exponent = p2 ->Exponent;
temp -> Coefficient = p2 -> Coefficient;
temp -> Next = NULL;
cur -> Next = temp;
cur = temp;
p2 = p2 -> Next;
}
//如果二者指數(shù)相等
else
{
int sum = p1 -> Coefficient + p2 -> Coefficient;
//求和不為0才可以
if (sum != 0)
{
node temp = (node)malloc(sizeof(struct Node));
temp -> Exponent = p1 -> Exponent;
temp -> Coefficient = sum;
temp -> Next = NULL;
cur -> Next = temp;
cur = temp;
}
p1 = p1 -> Next;
p2 = p2 -> Next;
}
}
//將沒(méi)有循環(huán)完的部分加入到結(jié)果的尾部
if (p1!=NULL)
{
cur -> Next = p1;
}
if (p2 != NULL)
{
cur -> Next = p2;
}
return head;
}
//初始化鏈表
node init()
{
node L;
L = (node)malloc(sizeof(struct Node));
if (L == NULL)
{
printf ("Out of space");
return NULL;
}
L -> Coefficient = -999;
L -> Exponent = - 999;
L -> Next = NULL;
return L;
}
//創(chuàng)建鏈表
node Create(node L){
node TmpCell;
int coef,exp;
node Cur = L;
printf("請(qǐng)輸入數(shù)字系數(shù)和指數(shù)，指數(shù)-1結(jié)束\n");
scanf("%d%d",&coef,&exp);
while (exp!=-1)
{
TmpCell = (node)malloc(sizeof(struct Node));
TmpCell -> Coefficient = coef;
TmpCell -> Exponent = exp;
TmpCell -> Next = NULL;
Cur -> Next = TmpCell;
Cur = TmpCell;
scanf("%d%d",&coef,&exp);
}
return L;
}
//打印鏈表
void Print(node L)
{
node P = L -> Next;
while (P!=NULL){
printf("%dx^%d+",P->Coefficient,P->Exponent);
P = P -> Next;
}
printf("\n");
}
//
int main()
{
node head1 = init();
Create(head1);
Print(head1);
node head2 = init();
Create(head2);
Print(head2);
node head = add(head1,head2);
Print(head);
}
如果你喜歡我寫(xiě)的文章丘侠，可以幫忙給小編點(diǎn)個(gè)贊或者加個(gè)關(guān)注徒欣，我一定會(huì)互粉的！
如果大家對(duì)數(shù)據(jù)結(jié)構(gòu)感興趣蜗字，歡迎跟小編進(jìn)行交流打肝，小編微信為sxw2251，加我要寫(xiě)好備注喲Ｅ膊丁：
我的微信
