阅读:0       作者:严长生

链表节点的插入,链表插入节点

向现有链表中插入结点,根据插入位置的不同,可分为以下 3 种情况:
  1. 插入到链表的头部,作为新的链表中第一个存有数据的结点(又称为”首元结点”);
  2. 插入到链表中某两个结点之间的位置;
  3. 插入到链表的最末端的位置;
使用头插法和尾插法可分别解决第 1 和第 3 种情况,但是无法解决第 2 种情况,所以本节给大家一段通用代码,可有效解决所有链表结点插入的问题。

无论插入结点位于链表的哪一位置,都可分为两步处理:
  1. 将新结点的 next 指针指向插入位置后的结点;
  2. 将插入位置前的结点的 next 指针指向该插入结点;
所以,实现结点插入的关键是:在链表中找到新结点要插入的位置,即找到插入位置的上一个结点和下一个结点。找到后,按照以上 2 步即可实现链表的插入。

使用通用代码实现结点插入的前提是:链表中要含有头结点,否则在链表头部插入结点时会出错。

链表插入结点的通用代码(带有详细解析)

#include <stdio.h>
#include <stdlib.h>
typedef struct Link{
    int  elem;
    struct Link *next;
}link;
link * initLink();
//链表插入的函数,p是链表,elem是插入的结点的数据域,add是插入的位置
link * insertElem(link * p,int elem,int add);
void display(link *p);
int main() {
    //初始化链表(1,2,3,4)
    printf("初始化链表为:\n");
    link *p=initLink();
    display(p);

    printf("在第4的位置插入元素5:\n");
    p=insertElem(p, 5, 4);
    display(p);
    return 0;
}
link * initLink(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点,用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}
link * insertElem(link * p,int elem,int add){
    link * temp=p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp=temp->next;
    }
    //创建插入结点c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向链表中插入结点
    c->next=temp->next;
    temp->next=c;
    return  p;
}
void display(link *p){
    link* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null,就执行输出语句。
    while (temp->next) {
        temp=temp->next;
        printf("%d",temp->elem);
    }
    printf("\n");
}
运行结果:
初始化链表为:
1234
在第4的位置插入元素5:
12354