单链表的插入
单链表的插入可以分为按位序插入和指定结点的前插和后插
按位序插入
按位序插入，则在链表的第i位插入一个结点，由于链表是物理结构为链式存储的线性表，其存储内存不连续，依靠结点中元素数据中的指针数据指向下一结点，因此要插入一个结点到第i个位置，只需要找到第i-1个元素，将其指针数据给插入结点的指针数据，并将自己的指针数据更新为指向i即可。
/*功能：单链表在第i个位序插入一个结点输入：L->单链表结构体i->插入到第i个位序e->要插入的数据输出：flase：插入失败true ：插入成功说明：该函数的插入方式适用于有头结点的单链表
*/bool ListInsert(LinkList &L,int i,ElemType e){if(i<1) //判断i是否有效return false; //i无效，插入失败LNode *p=NUll; //当前结点int j=0; //当前结点是第几个位置p=L; //初始化当前节点为头结点while(p!=NULL && j<i-1){ //遍历找到第i-1个结点p=p->next;j++;}if(p==NULL) //i不合法return flase; //i不合法，删除失败LNode *s=(LNode *)malloc(sizeof(LNode));//申请插入结点空间if(s==NULL) //判断空间申请状况return false; //空间申请失败，插入失败s->data=e; //将数据e给插入结点s->next=p->next; //将i-1结点的next给插入结点p->next=s; //i-1的next指针指向插入结点return true; //插入成功
}
如果没有头结点，则无法找到第i-1个结点，因此要对i=1时进行特别处理
/*功能：单链表在第i个位序插入一个结点输入：L->单链表结构体i->插入到第i个位序e->要插入的数据输出：flase：插入失败true ：插入成功说明：该函数的插入方式适用于没有头结点的单链表，对于i=1时需要特殊处理
*/bool ListInsert(LinkList &L,int i,ElemType e){if(i<1) //判断i是否在有效return false; //i无效，插入失败if(i==1){ //在第一个位置插入结点LNode *s=(LNode *)malloc(sizeof(LNode));//申请插入结点空间if(s==NULL) //判断空间申请状况return false; //空间申请失败，插入失败s->data=e; //将数据e给插入结点s->next=L; //将L指向的结点指针给新结点L=s; //L指向新结点return true; //插入成功}LNode *p=NUll; //当前结点int j=1; //当前结点是第几个位置p=L; //初始化p指向第一个结点while(p!=NULL && j<i-1){ //遍历找到第i-1个结点p=p->next;j++;}if(p==NULL) //i不合法return flase; //i不合法，删除失败LNode *s=(LNode *)malloc(sizeof(LNode));//申请插入结点空间if(s==NULL) //判断空间申请状况return false; //空间申请失败，插入失败s->data=e; //将数据e给插入结点s->next=p->next; //将i-1结点的next给插入结点p->next=s; //i-1的next指针指向插入结点return true; //插入成功
}
指定结点后插操作
将指定节点的原有的指针数据给插入结点，并更新现在的指针数据指向插入结点
/*功能：单链表在指定结点后插入一个结点输入：*p->指定的结点指针e->要插入的数据输出：flase：插入失败true ：插入成功说明：
*/
bool InsertNextNode(LNode *p,ElemType e){if(p==NULL) //判断插入结点合法性return false; //结点不合法，插入失败LNode *s=(LNode *)malloc(sizeof(LNode));//申请插入结点空间if(s==NULL) //判断空间申请状况return false; //空间申请失败，插入失败s->data=e; //将数据e给插入结点s->next=p->next; //将i-1结点的next给插入结点p->next=s; //i-1的next指针指向插入结点return true; //插入成功
}
/*功能：单链表在指定结点后插入一个结点输入：*p->指定的结点指针*s->要插入的结点输出：flase：插入失败true ：插入成功说明：
*/
bool InsertNextNode(LNode *p,LNode *s){if(p==NULL) //判断插入结点合法性return false; //结点不合法，插入失败s->next=p->next; //将i-1结点的next给插入结点p->next=s; //i-1的next指针指向插入结点return true; //插入成功
}
指定节点前插操作
在结点后插入很简单，只需要将该结点的next指针给新结点，同时更新该结点的next指针指向新结点。但要在指定结点前插入一个结点，需要找到该结点的前驱结点，又因为单链表不能逆向，因此需要遍历链表。我们也可以通过另一种方法，不找前驱结点，不改变前驱结点的next，而将新结点插入到指定结点的后面，再将指定结点与插入的新结点的所有数据交换，玩一手偷天换日。
/*功能：单链表在指定结点前插入一个结点输入：*p->指定的结点指针e->要插入的数据输出：flase：插入失败true ：插入成功说明：
*/
bool InsertPriorNode(LNode *p,ElemType e){if(p==NULL) //判断插入结点合法性return false; //结点不合法，插入失败LNode *s=(LNode *)malloc(sizeof(LNode));//申请插入结点空间if(s==NULL) //判断空间申请状况return false; //空间申请失败，插入失败s->data=p->data; //将p的数据给新结点p->data=e; //将要被插入的数据给ps->next=p->next; //将p的next给新结点p->next=s; //将p的next指针指向新结点/*此时新结点的所有内容与p结点完成互换，最终完成偷天换日*/return true;//插入成功
}
/*功能：单链表在指定结点后插入一个结点输入：*p->指定的结点指针*s->要插入的结点输出：flase：插入失败true ：插入成功说明：
*/
bool InsertPriorNode(LNode *p,LNode *s){if(p==NULL) //判断插入结点合法性return false; //结点不合法，插入失败ElemType temp=s->data; //创建临时变量temp暂存新结点的数据s->data=p->data; //将指定结点数据给新结点p->data=temp; //将新结点的数据换给指定结点s->next=p->next; //将指定结点的next指针给新结点p->next=s; //将指定节点的next指针指向新结点return true; //插入成功
}
