快捷導(dǎo)航

C語言如何實(shí)現(xiàn)頭插法建立單鏈表

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

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

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

怎么將結(jié)點(diǎn)一個(gè)個(gè)插入在某個(gè)結(jié)點(diǎn)前面呢？

下面的圖可以比較詳細(xì)的展示出來：

至少對(duì)我來說挺詳細(xì)的哈

p->next=head->next; //一開始 head->next=NULL；?
head->next=p;//然后將p指針指向head結(jié)點(diǎn)指向的下一個(gè)結(jié)點(diǎn)

以下是圖像展示：

然后再在頭結(jié)點(diǎn)的后面插入新的結(jié)點(diǎn)

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

以下是圖像展示：

注！：要先寫p->next=head->next，然后才能寫head->next=p；因?yàn)槿绻葘慼ead->next=p，然后再寫head->next=p->next，結(jié)果就會(huì)變成head->next原本要指的是插入的結(jié)點(diǎn)，然后又p->next=head->next，那 head->next最后指向的就不是要插入的結(jié)點(diǎn)了，變成了p要指向的下一個(gè)結(jié)點(diǎn)，而p->next一開始就是NULL。

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

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

以下是代碼展示：

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

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: