參考《數(shù)據(jù)結構與算法分析-c語言描述》一書

1、抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（abstract data type，ADT）是一些操作的集合。抽象數(shù)據(jù)類型是數(shù)學的抽象，在ADT的定義中根本沒涉及如何實現(xiàn)操作的集合，這可以看作模塊化設計的補充。

2、表ADT

我們將處理一般的形如A1，A2，A3.......AN的表。這個表的大小是N，我們稱大小為0的表為空表。

2.1 鏈表的ADT：

鏈表由一系列不必再內(nèi)存中相連的結構組成，每一個結構均包含表元素和指向包含該元素后繼元的結構的指針，我們稱之為Next指針。最后一個單元的Next指針指向NULL。我們通常給鏈表增加一個表頭節(jié)點（header），這個表頭節(jié)點解決了以下的問題：
1、如何在表的最前面插入元素。
2、刪除第一個元素，因為改變了表的起始端，編程中的疏忽將會造成表的丟失。
那么具有表頭的鏈表形式如下圖所示：

帶表頭的鏈表

我們使用結構體來定義鏈表：

#include <stdio.h>

struct Node;
//將鏈表指針聲明為PtrToNode
typedef sturct Node *PtrToNode;
//將鏈表表頭元素聲明為List
typedef PtrToNode List;
//將鏈表除表頭外的元素聲明為Postion
typedef PtrToNode Position;
//將指定的元素類型，聲明為ElementType，這里是int
typedef int ElementType
struct Node{
    ElementType Element;
    Position Next;
}

接下來，我們實現(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("請輸入數(shù)字,-1結束\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;
}

鏈表的打?。?/p>

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;
}

判斷當前元素是否在鏈表的末尾：

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 鏈表實現(xiàn)多項式求和計算

書中并沒有給出具體的實現(xiàn)，這是小編自己編寫的代碼，望多指點：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node * node;

struct Node{
    int Coefficient;
    int Exponent;
    node Next;
};

//兩個多項式相加
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)判斷，直到一個鏈表到尾部
    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;
        }
    }
    //將沒有循環(huán)完的部分加入到結果的尾部
    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("請輸入數(shù)字系數(shù)和指數(shù)，指數(shù)-1結束\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);    
}

如果你喜歡我寫的文章，可以幫忙給小編點個贊或者加個關注，我一定會互粉的！
如果大家對數(shù)據(jù)結構感興趣，歡迎跟小編進行交流，小編微信為sxw2251，加我要寫好備注喲?。?/p>

我的微信