目录
一、按位序插入
1.带头结点
LinkInsert(&L,i,e)：插入操作，在表L中的第i个位置插入指定元素e。（找到第i-1个结点，将新结点插入其后）
注：头结点可以看作“第0个”结点
-
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
false;
//插入成功
-
}
分四种情况讨论
① i = 1（将元素插在第一个位置），时间复杂度O(1)
1）j = 0，不执行while循环
2）p指向头结点
3）开辟一块新的结点空间s，将参数e存入到新结点s中
4）s指向结点的指针指向p所指向结点的指针
5）p指向结点的指针重新指向到新结点s
注：4)5)不能写反，原因是会造成后面的内容丢失，使s结点自己指向自己
②i = 3（将元素插在第三个位置），时间复杂度O(n)
1)执行while循环，j=2
2)p指向第i-1个结点，同3）4）5）
③插在表尾，时间复杂度O(n)
1）执行whle循环，j = i - 1
2）p指向最后一个结点，同3）4）5）
注：此时s指向结点的指针为NULL
④i > Length时
p指向的是NULL，插入失败
2.不带头结点
-
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;
-
int j =
1;
-
p = L;
-
while(p !=
NULL && j < i -
1){
-
p = p->next;
-
j++;
-
}
-
if(p ==
NULL)
-
return
false;
-
LNode *s = (LNode *)
malloc(
sizeof(LNode));
-
s->data = e;
-
s->next = p->next;
-
p->next = s;
-
return
false;
-
}
分三种情况讨论
①i = 1
1）因为无头结点，所以要先开辟一块结点空间，将参数e存入到新结点s中
2）s指向结点的指针指向L，L指向s
注：如果不带头结点，则插入、删除第一个元素时，需要更改头指针L
②i > 1...
和带结点的操作一样
注：j初始为1，表示p刚开始指向的是第一个结点
二、指定结点的后插操作
-
//后插操作：在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->next = p->next;
-
p->next = s;
-
return
true;
-
}
思路：
1）先开辟一块结点空间
2）将参数存入到新结点中
3）s指向结点的指针指向p所指向结点的指针
4）p指向结点的指针重新指向到新结点s
三、指定结点的前插操作
-
//前插操作：在p结点之前插入元素e
-
bool InsertPriorNode(LNode *p,ElemType e){
-
if(p ==
NULL)
-
return
false;
-
LNode *s = (LNode *)
malloc(
sizeof(LNode))l
-
if(s ==
NULL)
-
return
false;
-
s->next = p->next;
-
p->next = s;
-
s->data = p->data;
-
p->data = e;
-
return
true;
-
}
由于不知道p的前驱结点信息，所以思路如下：
1）先开辟一块结点空间s
2）s指向结点的指针指向p所指向的指针
3）p所指向的指针指向s
4）复制p中元素到s
5）p中元素覆盖为e
四、按位序删除（带头结点）
-
bool ListDelete(LinkList &L,int i,ElemType &e){
-
if(i <
1)
-
return
false;
-
LNode *p;
-
int j =
0;
-
p = L;
-
while(p !=
NULL && j < i -
1){
-
p = p->next;
-
j++;
-
}
-
if(p ==
NULL)
-
return
false;
-
if(p->next ==
NULL)
-
return
false;
-
LNode *q = p->next;
//令q指向被删除结点
-
e = q->data;
//用e返回元素的值
-
p->next = q->next;
//将*q结点从链中断开
-
free(q);
//释放结点的存储空间
-
return
true;
//删除成功
-
}
思路：
①头结点看作第0个结点
②新建指针q指向p所指向的指针
③将q指向的结点中元素赋值给e
④p结点的指针指向q所指向的指针
⑤释放q
五、指定结点的删除
-
//删除指定结点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;
-
}
思路：
①先使q指向p的后继结点
②将q值赋给p
③p结点的指针指向q结点指向的指针（可能指向一个结点，也有可能是NULL）
④释放q
注：如果p是最后一个结点，只能寻找p的前驱
六、总结
转载：https://blog.csdn.net/qq_40310148/article/details/105713772