单链表的插入操作(全)

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);
}