单链表的插入操作（全）
1 在指定位序插入数据
第一步
主要执行操作：查找
先查找所要插入位置的前一个元素
具体方法：根据链表的特点-每一个节点都需要一个数据域和指针域
所以只需从头节点遍历到所要插入数据的的前一个节点即可
后面的showList函数也用的这种方法
第二步
主要执行操作：插入
创建一个新节点s（名称无所谓）给s的数据域赋值为e（e即你所要插入的数据） 代码如下演示
2 在指定位置后插入数据
第一步 和1操作只有一个地方不一致，只需把查找的代码中i-1 变为 i 即可
第二步
和1的第二部操作一致
3 在指定位置前插入数据
第一种方法
可以根据每个节点都有一个指针域来处理
即通过从头节点遍历到所要插入节点的前一个节点
时间复杂度为O(n) 问题规模n为插入的位序
第二种方法
我们换一种思路 即交换所要插入节点和所要插入节点前的节点的值
即可完成插入 时间复杂度为O(1) 比第一种更省时，方便，简洁试试
代码如下：
s->next = p->next;
p->next = s; // 新节点s连到p节点之后
s->data = p->data; // 利用交换数据来插入节点
p->data = e;
add:
如果想直接在节点插入的话把上面那部分代码修改下面代码即可：
int ListInsertPriorNode(LNode* p, int e) // 在指定元素前面进行插入操作
{
if (p == NULL)
{
cout << "你所插入的节点不存在" << endl;
exit(0);
}
LNode* s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
if (s == NULL)
{
cout << "内存分配失败" << endl;
exit(0);
}
s->next = p->next;
p->next = s; // 新节点s连到p节点之后
s->data = p->data; // 利用交换数据来插入节点
p->data = e;
return e; // 返回插入的元素
}
完整代码如下：
#include<iostream>
#include<stdio.h> // malloc函数头文件
using namespace std;
typedef struct LNode
{
int data; // 数据域
LNode* next; // 节点域
}LNode,*LinkList;
void InitList_Head(LinkList& L, int n) // 初始化单链表
{
L = (LNode*)malloc(sizeof(LNode)); // 创建节点
if (L == NULL)
{
cout << "创建节点失败" << endl;
exit(0); // 退出程序
}
L->next == NULL; // 链表设空
cout << "请输入数据" << endl;
LNode* s;
LNode* r; // 尾指针
r = L; // 把L赋给r
for (int i = 1; i <= n; i++)
{
s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
scanf_s("%d", &(s->data)); // 创建新节点
r->next = s; // 尾插法初始化链表
r = s;
}
r->next = NULL; //尾节点指向空节点
}
int ListInsert(LinkList& L, int i, int e) // 在指定位置上插入数据
{
if (i < 1)
{
cout << "您所插入的位置不存在" << endl;
exit(0);
}
LNode* p; // 指向p指向当前扫描到的节点
int j = 0; // 当前p指向的第几个节点 计数
p = L; // L指向头结点
while (p != NULL && j < i- 1) // 找到所插入节点i的前一个节点
{
p = p->next;
j++;
}
if (p == NULL) // i值不合法
{
exit(0);
}
LNode* s ;
s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
s->data = e; // 赋值
s->next = p->next;
p->next = s; // 把s节点连在p节点之后
return e; // 返回所插入的数据
}
int ListInsertNext(LinkList &L, int i, int e) // 指定节点的后插操作
{
if (i < 1)
{
cout << "插入位置不合法" << endl;
exit(0);
}
LNode* p; // 指向p指向当前扫描到的节点
int j = 0; // 当前p指向的第几个节点 计数
p = L; // L指向头结点
while (p != NULL && j < i ) // 找到所插入节点i节点
{
p = p->next;
j++;
}
if (p == NULL) // i值不合法
{
exit(0);
}
LNode* s;
s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
s->data = e; // 赋值
s->next = p->next;
p->next = s; // 把s节点连在p节点之后
return e; // 返回所插入的数据
}
int ListInsertPriorNode(LinkList& L, int i, int e)
{
if (i < 1)
{
cout << "插入位置不合法" << endl;
exit(0);
}
LNode* p; // 指向p指向当前扫描到的节点
int j = 0; // 当前p指向的第几个节点 计数
p = L; // L指向头结点
while (p != NULL && j < i) // 找到所插入节点i节点
{
p = p->next;
j++;
}
if (p == NULL) // i值不合法
{
exit(0);
}
LNode* s;
s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
s->next = p->next;
p->next = s; // 新节点s连到p节点之后
s->data = p->data; // 利用交换数据来插入节点
p->data = e;
return e; // 返回插入的元素
}
void showList(LinkList& L)
{
LNode* p;
p = (LNode*)malloc(sizeof(LNode)); // 创建新节点p
p = L->next;
while (p != NULL) // 遍历
{
cout << p->data << endl;
p = p->next;
}
}
int main()
{
LinkList L; // 创建一个单链表
InitList_Head(L, 5); // 表中有五个数据
//int a = ListInsert(L,3,4); // 指定位序插入
//cout << "插入的数据为" << a << endl;
//int b = ListInsertNext(L, 3, 5); // 指定位序后插入
//cout << "插入的数据为" << b << endl;
int c = ListInsertPriorNode(L, 3, 2); // 指定位序前插入
cout << "插入的数据为" << c << endl;
showList(L);
}