天天看點
傳回

C語言連結清單各類操作實作

連結清單是實作表結構的一種實作方式，連結清單允許資料節點在記憶體中不連續存儲,進而避免了線性表在插入和删除操作中表的部分或者全部需要整體移動的線性開銷。連結清單由一系列在記憶體中不連續的存在的結構組成，結構見圖1，每個結構均含有表元素和指向包含該元素後繼元的結構的指針，一般稱之為Next指針，連結清單最後一個元素的Next指針指向NULL。

C語言連結清單各類操作實作

本文代碼基于Mark Allen Weiss編著的資料結構和算法分析一書，編譯平台為Visual Studio 2013。

連結清單的各類操作包括建立連結清單、判斷連結清單是否為空、删除連結清單、插傳入連結表、輸對外連結表、排序、反序等。

我們首先從定義連結清單結構開始，其中我們定義了name為學生的結構體，PtrToNode是一個指向結構體節點的指針，同理Position和LinkedList，該定義隻是為了更加清晰地表示其代表的含義。

struct student;  
typedef struct student *PtrToNode; //PtrToNode is the pointer of the LinkedList
typedef PtrToNode Position;  
typedef PtrToNode LinkedList;  
struct student  
{  
    int num;  
    Position next;  
};

建立連結清單：我們建立的連結清單結構沒有頭結點，程式中head是表頭位置，p2是倒數第一個結構的指針，p1用來擷取輸入端的資訊。

Position CreateNode(void)  
{  
    Position head;  
    Position p1 = NULL;  
    Position p2 = NULL;  
    n = 0;  
    p1 = (Position)malloc(LEN);  
    p2 = p1;  
    if (p1 == NULL)  
    {  
        printf("Cann't create now ,Please try again in a moment");  
        return NULL;  
    }  
    else  
    {  
        head = NULL;  
        printf("Please input the %d node's number:", n + 1);  
        scanf("%d %f", &(p1->num)); //第一個輸入值 
    }  
    while (p1->num != 0)//我們把輸入的num為0作為輸入結束的标志 
    {  
        n += 1;  
        if (n == 1)  
        {  
            head = p1;//第一個元素獲得位址資訊 
            p2->next = NULL;  
        }  
        else  
        {  
        p2->next = p1;  //此處代碼疊代地輸傳入連結表值
    }  
    p2 = p1;//此處是和p2->next = NULL;一起作用的  
    p1 = (Position)malloc(LEN); //開拓記憶體單元
    printf("Please input the %d node's number:", n + 1);  
    scanf("%d %f", &(p1->num));  
    }  
    p2->next = NULL;     //加上尾指針  
    free(p1);            //釋放p1記憶體單元 
    p1 = NULL;  
    return head;  
}

為了能夠更好地觀察到我們的輸入資料是否被正确地識别并存儲在連結清單中，我們設計一個列印程式Print來對連結清單元素進行輸出。

void Print(Position head)  
{  
    Position p;  
    p = head;  
    if (head != NULL)  
    {  
        printf("head is %o \n", head);  
        int num = 1;  
        do  
        {  
            printf("the %dth node is %o  %d  %o\n", num, p, p->num, p->next);  
            num++;  
            p = p->next;  
        } while (p != NULL);  
    }  
}

在學習過程中發現反序輸對外連結表比較有意思，用遞歸實作的代碼非常簡潔，比某刷題寶典的解決方案簡潔，歡迎大家讨論指正，目前還沒有考慮代碼的robust。

void PrintReverse(Position head)
{  
    Position p;  
    p = head;  
    if (head != NULL)  
    {  
        if (p->next != NULL)  
        {     
            PrintReverse(p->next);  
            printf("%d  \n", p->num);  
        }  
        else  
            printf("%d\n", p->num);  
    }  
}

判斷連結清單是否為空和将連結清單清空的代碼。

LinkedList MakeEmpty(LinkedList L)  
{  
    if (L != NULL)  
        DeleteLinkedList(L);  
    L = (Position)malloc(LEN);  
    if (L == NULL)  
        printf("Out of memory");  
    L->next = NULL;  
    return L;  
}  

int IsEmpty(LinkedList L)  
{  
    return L->next == NULL;  
}  
void DeleteLinkedList(LinkedList L)  
{  
    Position P, Tmp;  
    P = L->next;/* Header assumed */
    L->next = NULL;  
    while (P != NULL)  
    {  
        Tmp = P->next;  
        free(P);  
        P = Tmp;  
    }  
}

比較重要的連結清單操作——删除Position DeleteNode(int X, LinkedList L)，連結清單的删除操作首先需要找到删除節點前一個節點的位置，将該節點的指針指向删除節點的下一個節點即可，需要注意的是如果删除的節點是表頭的話，将表頭的指針指向下一節點即可。

Position DeleteNode(int X, LinkedList L)  
{  
    LinkedList p1, p2;  
    if (L == NULL)  
    {  
        printf("List is empty\n");  
        return L;  
    }  
    p2 = FindPrevious(X, L);  
    p1 = p2->next;  
    //p1 = p1->next;  
    if (p1->num == X)  
    {  
        if (p1 == L)  
        {  
            L = p1->next;  
        }  
        else  
        {  
            p2->next  = p1->next;  
        }  
        free(p1);  
        p1 = NULL;  
    }  
    return L;  
}  
Position FindPrevious(int X, LinkedList L)  
{  
    Position P;  
    P = L;  
    while (P->next != NULL && P->next->num != X)  
    {  
    P = P->next;  
    }  
    return P;  
}

以及插入操作——void Insert(int X, LinkedList L, Position P)，插入操作的隻需要将插入位置前一節點的指針指向目前節點，目前節點的指針指向後一節點即可。

void Insert(int X, LinkedList L, Position P)  
{  
    Position TmpCell;  
    TmpCell = (Position)malloc(LEN);  
    if (TmpCell == NULL)  
        printf("out of space!\n");  
    TmpCell->num = X;  
    TmpCell->next = P->next;  
    P->next = TmpCell;  
    n += 1;  
}

相應的還有查找。

Position Find(int X, LinkedList L)  
{  
    LinkedList P = L;  
    while (P->num != X && P->next != NULL)  
    {  
        P = P->next;  
    }  
    return P;  
}

排序, 此處排序使用的是簡單的冒泡排序，之後會有一篇文詳細介紹和比較各種排序算法的原理和效率。

Position BubbleSortList(LinkedList L)  
{  
    LinkedList p1;  
    LinkedList p, p2;  
    p1 = (Position)malloc(LEN);  
    p1->next = L;   //此處增加一個節點，放在第一個節點的前面
    //主要是為了利于比較，因為本設計中采用的單連結清單沒有頭結點。
    L = p1;  
    for (Position endpt = NULL; endpt != L; endpt = p)  
    {  
        for (p = p1 = L; p1->next->next != endpt; p1 = p1->next)  
        {  
            if (p1->next->num > p1->next->next->num)  
            {  
                p2 = p1->next->next;  
                p1->next->next = p2->next;  
                p2->next = p1->next;  
                p1->next = p2;  
                p = p1->next->next;  
            }  
        }  
    }  
    p1 = L;  
    L = L->next;  
    free(p1);  
    p1 = NULL;  

   return L;  
 }

當然還有非常鬧心的反轉，個人在實作反轉代碼時，發現反轉的邏輯非常别扭，先貼代碼。p1是反序連結清單的表頭，p2是未反序連結清單的表頭，p作為中間變量儲存未反序的連結清單的表頭。

Position Reverse(LinkedList L){  
    Position p1,p2,p;  
    p1 = NULL;  
    p2 = L;  
    while (p2!=NULL)  
    {  
        p = p2->next;   //用于存儲反序節點之後未反序的連結清單内容
        p2->next = p1;  //将已經反序好的連結清單接在反序節點上
        p1 = p2;        //p1存儲已經反序好的連結清單 
        p2 = p;         //p2重新獲得未反序的連結清單内容  
    }  
    L = p1;  
    return L;     
}

接下來用詭異的大圖來分析一下反轉是如何實作的。第一次反轉，A1節點成為了連結清單的表尾節點，p2是未反序連結清單的表頭。

C語言連結清單各類操作實作

第二次反轉，相信大家根據while循環中的四行代碼能把結果推出來。

C語言連結清單各類操作實作
資料結構和算法分析 資料結構 連結清單 c語言
上一篇: Apache 2.0.63 + Svn 1.4.2 版本控制伺服器
下一篇: iOS開發--Swift 基于MVC設計模式的簡單的tableViewDemo

繼續閱讀