C語言之實作單鏈表的基本操作

目錄

1、鏈表節點的定義

2、鏈表基操Function的宣告

3、鏈表基操Function的定義與實作

3.1 單鏈表的創建（頭插法）

3.2 單鏈表的創建（尾插法）

3.3 有序單鏈表的創建

3.4 單鏈表的遍歷

3.5 在單鏈表中查找元素

3.6 在單鏈表中的指定位置后插入元素

3.7 在單鏈表中洗掉特定元素

3.8 兩個有序單鏈表合并的問題

總結

1、鏈表節點的定義

單鏈表節點的定義只需要有資料域和指標域即可，資料域用來存盤節點資料的，指標域是用來存盤后繼節點的地址的（沒有它，那你這還能叫鏈表嘛！），定義代碼如下：

typedef int Status;     //狀態碼資料型別
typedef int ElemType;      //資料元素資料型別
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;        //結構體鏈表指標

2、鏈表基操Function的宣告

單鏈表的基操function無非就是創建、洗掉、插入、查詢、遍歷這幾個基本操作，這里我就簡單的將創建、遍歷、插入、查詢這幾個function實作一下（我這里都是帶“哨兵”的單鏈表哦！）

//創建單鏈表（頭插法）
void CreateListHead(LinkList *L, int n);
//創建單鏈表(尾插法)
void CreateListTail(LinkList *L, int n);
//插入節點
//洗掉節點
//查詢特定節點
Status Find_List_Node(LinkList L, ElemType data);
//遍歷單鏈表
void DisplayList(LinkList L);
//創建特定有序鏈表(頭插法)
void CreateOrderListH(LinkList *L, int n, int array[]);
//創建特定有序鏈表(尾插法)
void CreateOrderListT(LinkList *L, int n, int array[]);
//合并兩個有序單鏈表
LinkList MergeTwoList(LinkList l1, LinkList l2);

這里面我加入了面試中常考的一個問題，就是“合并兩個有序單鏈表的操作”問題，在LinkList MergeTwoList(LinkList l1, LinkList l2)中有展示如何實作的！

3、鏈表基操Function的定義與實作

3.1 單鏈表的創建（頭插法）

首先我們來實作一下單鏈表的創建function，單鏈表的創建分為頭插法和尾插法這兩種（記住，我這里可是帶頭結點的單鏈表哦！），我們先說說頭插法吧！

頭插法呢！就是將一個一個節點插入到頭結點的后繼位置，也就是把每個新插入的節點放置在頭結點（哨兵節點）的后繼位置處！只要明白這一點，那實作起來，就和玩泥巴一樣，首先你需要創建一個P結點,并且讓它的指標域指向NULL，（怕他搞事情，所以最好指向空）這個P節點就是一個保姆，用來照顧我們新建的節點的資料和指標，我們為傳進來的頭結點分配記憶體空間，然后創建新節點，為其分配data(亂數即可)，并把P節點的next指標域指向頭結點的后繼即可（head->next）;具體的代碼實作如下

//創建單鏈表（頭插法）
void CreateListHead(LinkList *L, int n)
{
    LinkList p; int i;
    //srand(time(0));       //初始化亂數種子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;     //建立一個帶頭結點的單鏈表
    for(i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));      //生成新的節點
        p->data = rand() % 100 + 1;     //生成100以內的亂數
        p->next = (*L)->next;
        (*L)->next = p;     //插入到表頭
    }
}

3.2 單鏈表的創建（尾插法）

咱們再來看看尾插法是怎么操作的呢？尾插法啊！就是將新節點插入到單鏈表的尾巴處，那么？我們如何得知哪里是單鏈表的尾巴處呢？這里我們放置一個“小兵”，這個小兵啥都不干，就是幫咱們記錄“單鏈表的尾巴”在哪里，找到尾巴了，把新節點插入到尾巴后面，此時咱們的小兵指向的不在是單鏈表的尾巴了，我們需要讓小兵往后挪一個節點（更新小兵的指向），這樣小兵又再次的指向單鏈表的尾巴了！依次反復即可！當你插入完了以后，別忘了，讓你的小兵指向空哈（不然他要搞事情的啊！）；具體的實作代碼如下哈！

//創建單鏈表(尾插法)
void CreateListTail(LinkList *L, int n)
{
    LinkList p, r; int i;
    //srand(time(0));     //初始化亂數種子
    *L = (LinkList)malloc(sizeof(Node));        //L為整個線性表
    r = *L;     //r為指向尾部的節點
    for(i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));     //生成新的節點
        p->data = rand() % 100 + 1;     //隨機生成100以內的數字
        r->next = p;        //將表尾終端節點的指標指向新節點
        r = p;      //將當前的新節點定義為表尾終端節點
    }

    r->next = NULL;     //表示當前鏈表結束
}

3.3 有序單鏈表的創建

這個有序單鏈表的創建，我是用的順序存盤結構資料來存盤節點的資料的，我們只需要將上面的function修改一丟丟即可使用啊！也就是多加一個陣列形參即可！具體的實作代碼如下：

//創建特定有序鏈表(頭插法)
void CreateOrderListH(LinkList *L, int n, int array[])
{
    LinkList p; 
    int i;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for(i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = array[i];
        p->next = (*L)->next;
        (*L)->next = p;     //插到表頭
    }
}
//創建特定有序鏈表(尾插法)
void CreateOrderListT(LinkList *L, int n, int array[])
{
    LinkList r,p;
    int i;
    (*L) = (LinkList)malloc(sizeof(Node));
    r = (*L);
    for(i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = array[i];
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

3.4 單鏈表的遍歷

單鏈表的遍歷還是蠻簡單的！你要是不會，99%是因為你沒有搞懂指標哦！那就好好看看指標再來看哈！代碼如下：

//遍歷單鏈表
void DisplayList(LinkList L)
{
    LinkList p;     //宣告一節點
    p = L->next;    //讓p指向L的第一個節點
    for(;p != NULL; p = p->next)
    {
        printf("%d ",p->data);
    }
    printf("\n");
}

是不是so easy！呢？所以說，你要是看不懂，那就好好的敲敲腦袋瓜！面壁思過去（hhhhhh）

3.5 在單鏈表中查找元素

這個也比較簡單，菜哥就不講了！直接貼代碼！看不懂的都去給我面壁思過哈！

//查詢特定節點元素
Status Find_List_Node(LinkList L, ElemType data)
{
    LinkList p; int j;
    p = L->next;
    for(j = 1; p != NULL; p = p->next, j++)
    {
        if(data == p->data)
        {
            break;
        }
        else
            continue;
    }
    p->next = NULL;
    return j;
}

3.6 在單鏈表中的指定位置后插入元素

在單鏈表中的指定位置后面插入元素，這個操作不難，大概思路就是這樣的，遍歷鏈表，搜尋到對應位置的節點，用個“保姆”指標存入插入的data，并將“保姆”指標的指標域存入特定位置節點后繼的地址，然后再將特定位置節點的指標域存入“保姆”指標的地址即可！具體操作代碼如下：

//在特定位置插入節點
void InsertListElem(LinkList *L, int n, ElemType data)
{
    LinkList me, pre; int i = 1;
    pre = (*L)->next;
    if(pre == NULL)
        printf("LinkList is NULL!\n");
    else
    {
        for(; i < n; i++)
        {
            pre = pre->next;
        }
        me = (LinkList)malloc(sizeof(Node));
        me->data = data;
        me->next = pre->next;
        pre->next = me;
    }
}

3.7 在單鏈表中洗掉特定元素

在單鏈表中洗掉特定元素，這個不難，大概思路就兩步，第一是在鏈表中遍歷，找到特定元素對應的節點，二是把該節點從鏈表中踢出去，并且要釋放該節點的記憶體空間（不然會出現記憶體溢位的問題哦！），好啦！廢話不多說，直接上代碼哈！

//在單鏈表中洗掉指定元素
Status DeleteListElem(LinkList *L, ElemType data)
{
    LinkList me, bonne;
    me = (*L);
    while(me->next != NULL)
    {
        if(me->data == data)
        {
            bonne->next = me->next;
            free(me);
            return OK;
        }
        else
        {
            bonne = me;
            me = me->next;
        }
    }
    return ERROR;
}

3.8 兩個有序單鏈表合并的問題

好好聽講哦！這個面試經常愛考的呦！大概的思路就是比較，往后挪，然后再比較，等誰先挪完了，基本上就可以結束了！（下面這個按照從小到大的順序哈）

如圖所示呢！L1，L2為兩個有序的單鏈表（帶頭結點哦！），L3呢是我們新建的一個頭結點，用來連接合并后的結果，首先比較L1的第一個節點的data與L2第一個節點的data，若L1的小于L2的 ，則將L3的頭結點指向L1的第一個節點，同時將L3往后挪一個位置，然后再進行比較，比較到最后，誰先到結尾，那么就直接將沒有到結尾的，把他后面的節點統統接到L3的尾巴后面即可！具體的操作代碼如下：

//合并兩個有序單鏈表
LinkList MergeTwoList(LinkList l1, LinkList l2)
{
    LinkList preHead = (LinkList)malloc(sizeof(Node));
    LinkList prev = preHead,list1 = l1->next, list2 = l2->next;
    while(list1 != NULL && list2 != NULL)
    {
        if(list1->data <list2->data)
        {
            prev->next = list1;
            list1 = list1->next;
        }
        else{
            prev->next = list2;
            list2 = list2->next;
        }

        prev = prev->next;
    }
    // 合并后 l1 和 l2 最多只有一個還未被合并完，我們直接將鏈表末尾指向未合并完的鏈表即可
    prev->next = list1 == NULL ? list2 : list1;

    return preHead->next;
}

總結

完了，講完了，菜哥講學結束！

對啦！博主是一個又菜又愛玩的人哦！大家喜歡的請多多點贊！同時文中有講的不足之處，歡迎大家在底下評論，菜哥都會看的哦！