王道数据结构 （3） 单链表 插入节点

 第一步：

先连接后链  

原来 b = p->next 插入新节点后 b=s->next

 s->next = p->next;

第二步：

连接前链

p->next = s 

代码：

/*单链表（含头结点）*/
#include<stdio.h>
#include<stdlib.h>
 

typedef int ElemType;
 
typedef struct LNode{
    ElemType data;  //数据域
    struct LNode *next;  // 指针域
}LNode,*LinkList;
 
LinkList CreateList1(ElemType a[], int n);  //头插法建立单链表
void OutputList(LinkList L); //输出单链表全部元素
int InsertLNode(LinkList L, int i, ElemType e); //在第i个位置插入结点,即在第i-1个结点之后插入新结点

 int Length(LinkList L); //获取单链表长度(不含头结点)
 
void main(){
    LinkList L = NULL;
    ElemType a[] = { 1, 2, 3, 4, 5 };
    ElemType e;
    L = CreateList1(a, 5);
    OutputList(L);
    InsertLNode(L, 6, 6);
    OutputList(L);
    printf("%d
", e);
    OutputList(L);
 
}

int Length(LinkList L){  //获取单链表长度(不含头结点)
    LinkList p = L->next;
    int len = 0;
    while (p){
        len++;
        p = p->next;
    }
    return len;
}
 
LinkList CreateList1(ElemType a[], int n){   //头插法建立单链表
    int i;
    LinkList L = NULL, s = NULL;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
 
    for (i = 0; i < n; i++){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
    return L;
}
 

// 输出所有链表的思路：
// 1.让头节点的next 指向下一个节点 
// 2. 做一个循环 当超出时打断循环 循环内的时候 p 指向下一个 p 是 现在的节点 p=p-> next 节点会向下一个移动
void OutputList(LinkList L){  //输出单链表全部元素
    LinkList p = L->next;
    while (p){
        printf("%d  ", p->data);
        p = p->next;
    }
    printf("
");
}
 

 
int InsertLNode(LinkList L, int i, ElemType e){ //在第i个位置插入结点,即在第i-1个结点之后插入新结点
    if (i<1 || i>Length(L) + 1){
        printf("插入位置错误！
");
        return -1;
    }
    LinkList p = L;  //p始终指向第i-1个结点
    LinkList s = NULL;
    while (--i){
        p = p->next;
    }
    s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
 
    return 1;
}