C語言如何實現頭插法建立單鏈表

更新時間：2022年07月13日 10:13:37 作者：nefu_lmy

這篇文章主要介紹了C語言實現頭插法建立單鏈表的方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

首先要明確一點，利用頭插法建立出來的單鏈表的輸出都是逆序的（就是和你的輸入順序反著來的）然后就是要明確生成的新結點是一個個加在某個結點的前面的（這個結點不一定是頭結點，下面的代碼是插在p的前頭），這就是頭插法。

怎么將結點一個個插入在某個結點前面呢？

下面的圖可以比較詳細的展示出來：

至少對我來說挺詳細的哈

p->next=head->next; //一開始 head->next=NULL；?
head->next=p;//然后將p指針指向head結點指向的下一個結點

以下是圖像展示：

然后再在頭結點的后面插入新的結點

再執(zhí)行一遍上面的代碼，然后head后面就連上了新的結點，p原本指向的結點前面也增加了一個新的結點，然后p就指向新加入的結點了。

以下是圖像展示：

注！：要先寫p->next=head->next，然后才能寫head->next=p；因為如果先寫head->next=p，然后再寫head->next=p->next，結果就會變成head->next原本要指的是插入的結點，然后又p->next=head->next，那 head->next最后指向的就不是要插入的結點了，變成了p要指向的下一個結點，而p->next一開始就是NULL。

也就是說，新的節(jié)點根本就沒連上去，p的前面根本沒有插入新的結點，head->next也一直是NULL。（這段看不懂就不看了）

然后就是不斷地重復上述過程，在頭節(jié)點和新插入的節(jié)點之間建立聯系，同時在新插入的節(jié)點和上一個插入的節(jié)點之間建立聯系，最終得到一個完整的單鏈表。

以下是代碼展示：

#include <bits/stdc++.h>
 
using namespace std;
//利用頭插法建立的單鏈表輸出都是逆序的
typedef struct node
{
    int data;//數據域，存放數據
    struct node *next;//指針域，存放指針，存放后繼結點的信息
}no;//no是結構體的名字 
 
int main()
{
    no *head,*tail,*p;
    head=new no;
    head->next=NULL;
    tail=head;
    int n;
    cin>>n;
    while(n)
    {
        p=new no;
        p->data=n;
        p->next=head->next;//第一次的時候p->next指的是NULL，
        //再往后，指的就是頭結點后面的結點
        head->next=p;//指針p也可以向前移動的哦，不一定就是要向后移動
        cin>>n;
    }
    p=head->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return 0;
}

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: