一、插入操作
（一）按位序插入（带头结点）
ListInsert(&L,i,e)：插入操作。在表L的第i个位置上插入指定元素e。- 找到第i-1个结点，将新结点插入其后
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;
//1.malloc申请新的结点空间
LNode *s = (LNode *)malloc(sizeof(LNode));
//2.将参数e存入新结点里面
s -> data = e;
//3.将s指向新结点e的next指针指向p结点next指向的位置
s -> next = p -> next;
//4.将p结点的next指针指向新的结点
p -> next = s; //将结点s连到p之后
return true;//插入成功
}
- 分析：
①、如果i=1（插在表头）
- 注意：要先复制p结点next曾经指向的位置，然后再让p结点next指向新的结点。顺序不能颠倒。
- ②、如果i=3（插在表中）
while(p!=NULL && j<i-1){
//循环找到第2个结点
p = p -> next;
j++;
}
- ③、如果i=5（插在表尾）
- ④、如果i=6（i > Length）
- 运行动态图:
（二）按位序插入（不带头结点）
ListInsert(&L,i,e)：插入操作。在表L的第i个位置上插入指定元素e。- 找到第i-1个结点，将新结点插入其后。
- 不存在“第0个”结点，因此i=1时需要特殊处理。
- ②、如果i>1…
1. 指定结点的后插操作
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
if(p==NULL)
return false;
//1.malloc申请空间
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s == NULL) //内存分配失败
return false;z
//2.将数据元素e填到新结点当中
s -> data = e; //用结点s保存数据元素e
//3.将p的next指向下一个元素赋值给新数据元素e的next指向下一个元素
s -> next = p -> next;
//4.将p的next指向新数据元素e
p -> next = s; //将结点s连接到p之后
return true;
}
2. 指定结点的前插操作
- 如何找到p结点的前驱结点？
（1）通过传入头指针的方式实现
（2）通过复制插入位置的结点方式实现
二、删除操作
（一）按位序删除（带头结点）
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。- 找到第 i-1 个结点，将其指针指向第i+1个结点，并释放第i个结点
- 头结点可以看作“第0个”结点
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; //删除成功
}
- 删除的结点如果i=4：
（二）指定结点的删除
//删除指定结点 p
bool DeleteNode(LNode *p)
- 删除结点p，需要修改其前驱结点的 next 指针
1. 传入头指针，循环寻找 p 的前驱结点
- 动态运行图：
- 如果p是最后一个结点：
转载：https://blog.csdn.net/qq_44096670/article/details/116103278
查看评论