引入

前面我们学习了如何找到和读取单链表中的数据，今天我们继续看看，如何在单链表中插入数据元素。

单链表中插入元素

我们既然知道，元素内存储的是数据域和指针域，一个指着另一个，呈链性存储。那么如果要在这样的链表中插入一个元素该如何处理呢？

在链表中插入元素

其实也就是

  • S 结点存储的地址，改成 P 存储的地址
  • P 存储的地址改成 S 结点的地址
  • S-> next = P->next
  • P->next = S

我们看一下图

思考一下

这两句代码的顺序可不可以点到过来？

  • S-> next = P->next
  • P->next = S

改成

  • P->next = S
  • S-> next = P->next

也就是先让 p->next 等于 S 的地址
然后在把 S->next 赋值为 P->next

答案肯定是不行的！
因为 p->next 指向的是 p 的下一个元素
如果先让 p->next 指向 S 的地址
那么谁也不知道 p 的下一个元素的地址了
所以顺序一定不要错！先新再旧！
先让插入的等于原来的，再改原来的等于新插入的。

插入数据的算法思路

我们清楚了该如何插入数据之后，我们来看看这个算法

  • **指向：**声明结点 p 指向链表头结点。
  • **遍历：**初始化 j 从1开始，当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j++。
  • **失败：**若到链表末尾 p 为空，则说明第 i 个元素不存在。
  • 成功： 查找成功，在系统中生成一个空节点 S
  • 将数据元素 e 赋值给 s->data
  • 将空结点的指针指向上一个结点的 next
  • 将上一个结点的 next 指向该空结点的位置
  • 返回成功

代码实现

C语言动态生成单链表，然后在第二个元素插入元素，再输出所有元素。

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Student)

struct Student{
    int num;
    char name[20];
    float score;
    struct Student * next;
};

struct Student * create(void){
    struct Student *a,*b,*head;
    a=b=(struct Student*)malloc(LEN);
    printf("请输入学生信息：\n");
    scanf("%d %s %f",&a->num , a->name , &a->score);
    int n=0;
    while(a->num!=0){
        n=n+1;
        if(n==1){
            head=a;
        }else{
            b->next=a;
            b=a;
        }
        a=(struct Student*)malloc(LEN);
        scanf("%d %s %f",&a->num , a->name , &a->score);
    }
    b->next=NULL;
    return head;
}

void print(struct Student *p){
    while(p!=NULL){
        printf("第%d号%s的成绩是：%3.1f\n",p->num,p->name,p->score);
        p=p->next;
    }
}

void stu_insert(struct Student * p , int i){
    struct Student *new_P;
    int j=1;
    while(j<i-1){
        p=p->next;
        j++;
    }
    new_P=(struct Student *)malloc(LEN);
    new_P->num=999;
    new_P->score=99.9;
    new_P->next = p->next;
    p->next=new_P;
}

int main(){
    struct Student *stu_p;
    stu_p=create();
    stu_insert(stu_p,2);
    print(stu_p);
    return 0;
}

伪代码实现

#define ERROR 0
#define OK 1
typedef int Elemtype
struct Node{
Elemtype data;
struct Node * next;
};
//构建单链表
typedef struct Node* LinkList;

status ListInsert(LinkList L , int i , Elemtype e){
int j=1;
LinkList p, s;
p = L;
//p 指向 L
while ( p && j<i){
p=p-> next;
j++;
}
//遍历链表找到插入位置
if(!p || j>i){
return ERROR;
}

s=(LinkList)malloc(sizeof(Node));
// 创建新结点
s->data = e;
// 将数据域赋值
s-next=p->next;
p->next=s;
//将指针域赋值，先把新的等于老的，再把老的指向新的
return OK;
}

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。