阅读:0       作者:严长生

链表的创建,头插法创建单链表(带源码+解析)

头插法创建单链表,即通过不断地将新创建的结点添加到链表的第一个数据结点之前,作为链表新的首个数据结点的方法,创建单链表。

根据链表是否有头结点,头插法插入结点的位置有所不同
  • 若链表存在头结点,头插法需将新结点插入到头结点之后的位置。例如,采用头插法,将数据 {1,2,3} 依次插入到具有头结点的链表中,其插入过程如下图所示:

 
  • 若链表不存在头结点,头插法需将新结点插入到头指针指向的位置。如下图所示:

实现代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//无头结点链表的头插法实现函数
link * creatLink(int * arc, int length) {
    int i;
    //最初状态下,头指针 H 没有任何结点,所以,插入第一个元素,就相当于是创建结点 H
    link * H =(link*)malloc(sizeof(link));
    H->elem = arc[0];
    H->next = NULL;
    //如果采用头插法插入超过 1 个元素,则可添加到第一个结点 H 之前
    for (i = 1; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //插入元素时,首先将插入位置后的链表链接到新结点上
        a->next = H;
        //然后再链接头指针 H
        H = a;
    }
    return H;
}
//有头结点链表的头插法实现函数
link * HcreatLink(int * arc, int length) {
    int i;
    //创建头结点 H,其链表的头指针也是 H
    link * H = (link*)malloc(sizeof(link));
    H->elem = 0;
    H->next = NULL;
    //采用头插法创建链表
    for (i = 0; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //首先将插入位置之后的链表链接到新结点 a 上
        a->next = H->next;
        //将新结点 a 插入到头结点之后的位置
        H->next = a;
    }
    return H;
}
//链表的输出函数
void display(link *p) {
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
int main() {
    int a[3] = { 1,2,3 };
    //采用头插法创建无头结点链表
    link * H = creatLink(a, 3);
    display(H);
    //采用头插法创建有头结点链表
    link * head = HcreatLink(a, 3);
    display(head);
    //使用完毕后,释放即可
    free(H);
    free(head);
    return 0;
}
运行结果:
3 2 1
0 3 2 1

提示:没有 0 的为无头结点的头插法输出结果,有 0 的为有头结点的头插法的输出结果