继学会线性表头插法和尾插法之后，本篇文章将会学会插入和删除的方法，并详细介绍小细节。
单链表的插入
单链表插入的前提是链表已经建立好
单链表第i个数据插入结点的算法思路:
声明一个结点p指向链表第一个结点，初始化j从1开始
-
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
p指针后移 若遍历到链表末尾p为空，则说明第i个元素不存在
-
否则查找成功，在系统中生成一个空结点s
生成结点s 将数据元素e赋值给s->data
单链表的插入标准语句s->next = p->next;p->next = s
-
返回成功
插入成功的状态
具体代码如下:
Status ListInsert(Node *head,int i,int e)
{
Node *p;
int j =1;
p = head;
if(p && j<i-1) //若p结点不为空且j<i-1即插入元素前一个元素
{
p = p->next;//遍历p
j++;
}
if(!p || j>i) //p结点为空
{
return ERROR;
}
Node *s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
单链表的删除
单链表第i个数据删除结点的算法思路:
声明一个结点p指向链表第一个结点，初始化j从1开始
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，将欲删除的结点p->next赋值给q
单链表的删除标准语句p->next = q->next
将q结点中的数据赋值给e，作为返回 。这一步有三种方法，具体后面会讲
释放q结点
-
返回成功
删除完成
具体代码如下:
Status ListDelete(Node *head,int i,int *e)
{
Node *p,*q;
p = head;
int j=1;
if(p && j<i-1)
{
p = p->next;
++j;
}
if(!p || j>i)
{
return ERROR;
}
q = p->next;
*e = q->data;
p->next = q->next;
free(q);
return OK;
}
刚练习到这个地方的时候，没有返回删除的元素。最后尝试把删除的元素返回回来，却发现出现错误，就针对这一点把删除操作的元素返回过程进行详细的深究和学习。
方法一 参数e用整形表示
Status ListDelete(Node *head,int i,int e)
{
Node *p,*q;
p = head;
int j=1;
if(p && j<i-1)
{
p = p->next;
++j;
}
if(!p || j>i)
{
return ERROR;
}
q = p->next;
e = q->data;
cout << e <<endl;
p->next = q->next;
free(q);
return OK;
}
int main()
{
int e;
num = 5;
cout<<"删除第二个位置的元素:";
ListDelete(head,2,e);
Output(head);
}
e作为整型时只能在子函数中输出。
方法二 在主函数中为e指针创建一个内存空间
Status ListDelete(Node *head,int i,int *e)
{
Node *p,*q;
p = head;
int j=1;
if(p && j<i-1)
{
p = p->next;
++j;
}
if(!p || j>i)
{
return ERROR;
}
q = p->next;
*e = q->data;
p->next = q->next;
free(q);
return OK;
}
int main()
{
int *e;
num = 5;
e = (int *)malloc(sizeof(num));
cout<<"删除第二个位置的元素:";
ListDelete(head,2,e);
Output(head);
cout << *e <<endl;
}
最后输出的是*e表示输出值而不是地址，指针的值不会随着子函数的结束而销毁或改变
image.png
图片中输出的这三个值分别是&e, e, *e 的值
方法三 参数e使用指针类型
Status ListDelete(Node *head,int i,int *e)
{
Node *p,*q;
p = head;
int j=1;
if(p && j<i-1)
{
p = p->next;
++j;
}
if(!p || j>i)
{
return ERROR;
}
q = p->next;
*e = q->data;
p->next = q->next;
free(q);
return OK;
}
int main()
{
int *e;
int num = 5;
e = #
cout<<"删除第二个位置的元素:";
ListDelete(head,2,e);
Output(head);
cout << *e <<endl;
}
这种方法中很容易犯的一个错误是在主函数中定义一个指针变量e之后没有赋值即e = &num，即没有给指针变量指定内存空间。因为指针本身是没有空间的，所以在传参之后就找不到地址导致程序输出有问题。
附上三种在子函数中改变数值的方法
void fact(int *e){
*e = 100;
}
int main(){
// 第一种方式
int a;
int *b = &a;
fact(b);
cout << *b << endl;
// 第二种方式
int c;
fact(&c);
cout << c << endl;
// 第三种方式
int *d;
d = (int*)malloc(sizeof(int));
fact(d);
cout << *d << endl;
free(d); // malloc 之后要记得 free，要不然会有内存泄露
}
