单链表的插入和删除
一、插入操作
按位序插入（带头结点）：
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//在第i 个位置插插入元素e (带头结点)
bool ListInsert(LinkList &L, int i，ElemType e){if( i<1)return false;LNode *p; //指针p指向当前扫描到的结点int j=0; //当前p指向的是第几个结点p = L; //L指向头结点，头结点是第0个结点(不存数据)
while (p!=NULL &&j<i-1){ //循环找到第i-1个结点p=p->next;j++;
}if(p==NULL) //i值不合法return false;
LNode *s = (LNode *)malloc(sizeof( LNode) ) ;
s->data = e;
s->next=p->next;
p->next=s; //将结点s连到p之后
return true; //插入成功
}
注意：上述代码s->next=p->next与p->next=s不能颠倒。
按位序插入（不带头节点）：
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//在第i 个位置插插入元素e (带头结点)
bool ListInsert(LinkList &L, int i，ElemType e){if( i<1)return false;if(i==1){ //插入第一个节点的操作与其他节点操作不同
LNode *s = ( LNode *)malloc(sizeof( LNode) ) ;s->data = e;s->next=L;L=s; //头指针指向新结点return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j=1; //当前p指向的是第几个结点
p = L; // p指向第1个结点（注意:不是头结点)while (p!=NULL &&j<i-1){ //循环找到第i-1个结点p=p->next;j++;
}if(p==NULL) //i值不合法return false;
LNode *s = (LNode *)malloc(sizeof( LNode) ) ;
s->data = e;
s->next=p->next;
p->next=s; //将结点s连到p之后
return true; //插入成功
}
指定节点的后插操作：
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//后插操作:在p结点之后插入元素e
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; //用结点s保存数据元素e
s->next=p->next;
p->next=s; //将结点s连到p之后
return true;
}
指定节点的前插操作：
//前插操作:在p结点之前插入元素e
bool InsertPriorNode (LNode *p,ElemType e)
无法找到他的前驱节点，可以传入头指针
//前插操作:在p结点之前插入元素e
bool InsertPriorNode ( LinkList L,LNode *p,ElemType e)
但如果不能传入头指针上述方法就不能使用，依然无法解决问题。
可以申请一个新的节点s作为p的后继节点，把p中的数据复制到s中再把插入的数据放到p中完成前插操作。如下图所示：
//前插操作:在p结点之前插入元素e
bool InsertPriorNode (LNode *p,ElemType e){if ( p==NULL)return false;LNode *s = ( LNode *)malloc(sizeof( LNode ) ) ;if ( s==NULL) //内存分配失败return false;s->next=p->next;p->next=s; //新结点s 连到p之后s->data=p->data; //将p中元素复制到s中p->data=e; // p中元素覆盖为ereturn true;
}
二、删除操作
按位序删除（带头结点）：
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;bool ListDelete( LinkList &L, int i,ElemType &e){if(i<1)return false;LNode *p; //指针p指向当前扫描到的结点int j=0; //当前p指向的是第几个结点p = L; //L指向头结点，头结点是第0个结点(不存数据)
while (p !=NULL && j<i-1){ //循外找到第i-1个节点p=p->next;j++;
}
if( p==NULL) //i值不合法return false;
if( p->next == NULL) //第i-1个结点之后已无其他结点return false;
LNode *q=p->next; //令q指向被删除结点
e = q->data; //用e返回元素的值
p->next=q->next; //将*q结点从链中“断开
free(q); //释放结点的存储空间
return true; //删除成功
}
指定节点的删除：
//删除指定结点p
bool DeleteNode ( LNode *p)
方法1:传入头指针，循环寻找p 的前驱结点
方法2:类似于结点前插的实现
//删除指定结点p
bool DeleteNode ( LNode *p){if (p==NULL)return false;LNode *q=p->next; //令q指向*p的后继结点p->data=p->next->data; //和后继结点交换数据域p->next=q->next; //将*q结点从链中“断开”free(q); //释放后继结点的存储空间return true;
}
