一篇看懂链表增删改查（文末附完整文件可直接cv大法调试）
程序员文章站
2022-03-03 08:33:41
...
链表创建及功能实现
QT旧版本没搞明白怎么支持输出中文所以只能拿出散装英语了= =
语法错误勿怪哈~
ps：关于尾指针的一些心得
在头指针创建后，尾指针也创建了（其实都是一个节点指针的变量，只是头指针分配了内存，尾指针没有分配，只是一个指针变量），并指向头指针，这时候只有一个头指针，所以尾指针将指针域设置为NULL，也就是头指针的指针域设置为NULL，当要执行添加操作时，尾指针就像一个帽子，趴在目前最近的节点头上，看到NEW了一个新的节点，就将身下的节点的指针域由NULL改为NEW的节点的地址，然后喊NEW的节点把自己的指针域改为NULL，然后脱离目前这个节点-，跳到NEW的那个节点的头上，完成添加操作。
createList创建链表
//创建链表
PNODE createList()
{
int len; //有效节点的个数
int val; //存放临时数据
PNODE pHead = (PNODE)malloc(sizeof(Node));
if(NULL == pHead)
{
printf("malloc failed \n");
exit(-1);
}
//因为还没有新的节点，这时候尾指针和头指针指向同一个内存
pTail->pNext = NULL;
printf("The len you need is: ");
scanf("%d", &len);
//对链表进行初始化，为所创建的len长度的链表分配内存并赋值
for(int i=0; i<len; i++)
{
//printf里面的%d都是为逗号,后面的值服务的，在输出的时候%d就会替换为逗号后面的值,这里是逗号后面的值给前面的%d
printf("Please enter no.%d segment val: ", i+1);
//scanf这里是输出，是%d的值给后面的val，和printf的方向相反，这里把输入的值传递给变量val
scanf("%d", &val);
//为新节点分配空间
PNODE pNew = (PNODE)malloc(sizeof(NODE));
{
if(NULL == pNew)
{
printf("failed \n");
exit(-1);
}
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
遍历并输出链表内容
//遍历并输出链表内容
void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext;
printf("the value of the whole list now is :");
while(NULL != p->pNext)
{
printf("%d ", p->data);
p = p->pNext;
}
//如果p为尾节点了，就把这最后一个p的数据打印出来然后换行
printf("%d \n \n", p->data);
return;
}
尾部追加
//尾部追加
void append_list(PNODE pHead)
{
int val;
PNODE p = pHead->pNext;
while(NULL != p->pNext)
{
p = p->pNext;
}
//创建一个新的节点
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(pNew == NULL)
{
printf("append failed \n");
}
printf("scanf the data you want to append: ");
//想要给这个变量传值就要取地址，因为这是一个临时变量而非指针
scanf("%d", &val);
pNew->data = val;
//跳出循环时p就指向最后一个节点
p->pNext = pNew;
pNew->pNext = NULL;
return;
}
删除指定位置节点
//删除指定位置（首节点为1）
void delete_list(PNODE pHead)
{
int pos;
int i = 1;
printf("where the position is you want to delete? ");
scanf("%d", &pos);
PNODE q = pHead;
PNODE p = q->pNext;
while(i != pos)
{
q = q->pNext;
p = p->pNext;
i++;
}
if(p->pNext == NULL)
{
printf("the val you delete is: %d \n", p->data);
q->pNext = NULL;
free(p);
}
else
{
printf("the val you delete is: %d \n", p->data);
q->pNext = p->pNext;
free(p);
}
return;
}
指定位置插入节点
void insert_list(PNODE pHead)
{
int pos;
int i = 1;
int val;
PNODE q = pHead;
PNODE p = q->pNext;
printf("where the position is you want to insert? ");
scanf("%d", &pos);
if(pos<1)
{
printf("Failed! Pos must be greater than 0 \n");
}
//当i不等于pos时，这里的i和pos是位置相等的，讲这个判断写在printf和scanf之间是为了能在外界输入pos按下回车后
//如果超过边界了就立即报错，就不进到输入数值的环节了，这样能进入到输入数值那pos就没问题
while(i != pos)
{
q = q->pNext;
p = p->pNext;
//这里是判断是否输入的pos超过了已有数组有效场地的最大值，也就是i
if(p == NULL)
{
printf("Failed! The pos is out of range,positon should beteween 1~%d \n", i);
return;
}
i++;
}
printf("what the val do you want to insert? ");
scanf("%d", &val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->data = val;
//排除了超过边界的pos值输入后，所有的pNew一定都是在pHead和p之间插入的，就算一共有3个元素，pos填3，那pNew就在第三，p指针移到第4
//如果pos填4，则报警
q->pNext = pNew;
pNew->pNext = p;
return;
}
修改指定位置节点的值
//修改指定位置的节点的值
void change_list(PNODE pHead)
{
//q指向首节点（如果首节点不存在则指向NULL）
PNODE q = pHead->pNext;
int pos;
int i = 1;
int val;
printf("Which node do you want to modify the value? ");
scanf("%d", &pos);
if(pos<1)
{
printf("Failed! Pos must be greater than 0 \n");
}
while(i != pos)
{
q = q->pNext;
if(q == NULL)
{
printf("Failed! The pos is out of range,positon should beteween 1~%d \n", i);
return;
}
i++;
}
printf("What the value do you want to set? ");
scanf("%d", &val);
q->data = val;
}
查找指定位置节点的值
void findByPos_list(PNODE pHead)
{
//q指向首节点（如果首节点不存在则指向NULL）
PNODE q = pHead->pNext;
int pos;
int i = 1;
printf("Which node do you want to query the value? ");
scanf("%d", &pos);
if(pos<1)
{
printf("Failed! Pos must be greater than 0 \n");
}
while(i != pos)
{
q = q->pNext;
if(q == NULL)
{
printf("Failed! The pos is out of range,positon should beteween 1~%d \n", i);
return;
}
i++;
}
printf("the value at position %d is: %d \n", i,q->data);
}
完整代码：
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
#include <QCoreApplication>
typedef struct Node
{
int data; //数据域
struct Node * pNext; //指针域
}NODE, *PNODE; //NODE等价于struct Node PNODE等价于struct Node *
//创建链表
PNODE createList();
//遍历链表
void traverse_list(PNODE pHead);
//在链表尾部追加
void append_list(PNODE pHead);
//在指定位置删除节点
void delete_list(PNODE pHead);
//在指定位置插入节点
void insert_list(PNODE pHead);
//修改指定位置节点的值
void change_list(PNODE pHead);
//根据位置查找节点的值
void findByPos_list(PNODE pHead);
int main()
{
PNODE pHead = NULL;
//创建链表时不为0，起码有一个有效节点，不然insert就可能出现插入首节点的问题了
pHead = createList();
traverse_list(pHead);
// append_list(pHead);
// traverse_list(pHead);
// delete_list(pHead);
// traverse_list(pHead);
// insert_list(pHead);
// traverse_list(pHead);
// change_list(pHead);
// traverse_list(pHead);
findByPos_list(pHead);
return 0;
}
//创建链表
PNODE createList()
{
int len; //有效节点的个数
int val; //存放临时数据
PNODE pHead = (PNODE)malloc(sizeof(Node));
if(NULL == pHead)
{
printf("malloc failed \n");
exit(-1);
}
PNODE pTail = pHead; //因为还没有新的节点，这时候尾指针和头指针指向同一个内存
pTail->pNext = NULL;
printf("The len you need is: ");
scanf("%d", &len);
//对链表进行初始化，为所创建的len长度的链表分配内存并赋值
for(int i=0; i<len; i++)
{
//printf里面的%d都是为逗号,后面的值服务的，在输出的时候%d就会替换为逗号后面的值,这里是逗号后面的值给前面的%d
printf("Please enter no.%d segment val: ", i+1);
//scanf这里是输出，是%d的值给后面的val，和printf的方向相反，这里把输入的值传递给变量val
scanf("%d", &val);
//为新节点分配空间
PNODE pNew = (PNODE)malloc(sizeof(NODE));
{
if(NULL == pNew)
{
printf("failed \n");
exit(-1);
}
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
//遍历并输出链表内容
void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext;
printf("the value of the whole list now is :");
while(NULL != p->pNext)
{
printf("%d ", p->data);
p = p->pNext;
}
//如果p为尾节点了，就把这最后一个p的数据打印出来然后换行
printf("%d \n \n", p->data);
return;
}
//尾部追加
void append_list(PNODE pHead)
{
int val;
PNODE p = pHead->pNext;
while(NULL != p->pNext)
{
p = p->pNext;
}
//创建一个新的节点
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(pNew == NULL)
{
printf("append failed \n");
}
printf("scanf the data you want to append: ");
//想要给这个变量传值就要取地址，因为这是一个临时变量而非指针
scanf("%d", &val);
// printf("%d", val);
pNew->data = val;
//跳出循环时p就指向最后一个节点
p->pNext = pNew;
pNew->pNext = NULL;
return;
}
//删除指定位置（首节点为1）
void delete_list(PNODE pHead)
{
int pos;
int i = 1;
printf("where the position is you want to delete? ");
scanf("%d", &pos);
PNODE q = pHead;
PNODE p = q->pNext;
while(i != pos)
{
q = q->pNext;
p = p->pNext;
i++;
}
if(p->pNext == NULL)
{
printf("the val you delete is: %d \n", p->data);
q->pNext = NULL;
free(p);
}
else
{
printf("the val you delete is: %d \n", p->data);
q->pNext = p->pNext;
free(p);
}
return;
}
//插入完成后插入的节点的下标为pos，即在pos为2插入，插入的节点位于2位，原本在2的节点为第3
void insert_list(PNODE pHead)
{
int pos;
int i = 1;
int val;
PNODE q = pHead;
PNODE p = q->pNext;
printf("where the position is you want to insert? ");
scanf("%d", &pos);
if(pos<1)
{
printf("Failed! Pos must be greater than 0 \n");
}
//当i不等于pos时，这里的i和pos是位置相等的，讲这个判断写在printf和scanf之间是为了能在外界输入pos按下回车后
//如果超过边界了就立即报错，就不进到输入数值的环节了，这样能进入到输入数值那pos就没问题
while(i != pos)
{
q = q->pNext;
p = p->pNext;
//这里是判断是否输入的pos超过了已有数组有效场地的最大值，也就是i
if(p == NULL)
{
printf("Failed! The pos is out of range,positon should beteween 1~%d \n", i);
return;
}
i++;
}
printf("what the val do you want to insert? ");
scanf("%d", &val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->data = val;
//排除了超过边界的pos值输入后，所有的pNew一定都是在pHead和p之间插入的，就算一共有3个元素，pos填3，那pNew就在第三，p指针移到第4
//如果pos填4，则报警
q->pNext = pNew;
pNew->pNext = p;
return;
}
//修改指定位置的节点的值
void change_list(PNODE pHead)
{
//q指向首节点（如果首节点不存在则指向NULL）
PNODE q = pHead->pNext;
int pos;
int i = 1;
int val;
printf("Which node do you want to modify the value? ");
scanf("%d", &pos);
if(pos<1)
{
printf("Failed! Pos must be greater than 0 \n");
}
while(i != pos)
{
q = q->pNext;
if(q == NULL)
{
printf("Failed! The pos is out of range,positon should beteween 1~%d \n", i);
return;
}
i++;
}
printf("What the value do you want to set? ");
scanf("%d", &val);
q->data = val;
}
//查找指定位置的节点的值
void findByPos_list(PNODE pHead)
{
//q指向首节点（如果首节点不存在则指向NULL）
PNODE q = pHead->pNext;
int pos;
int i = 1;
printf("Which node do you want to query the value? ");
scanf("%d", &pos);
if(pos<1)
{
printf("Failed! Pos must be greater than 0 \n");
}
while(i != pos)
{
q = q->pNext;
if(q == NULL)
{
printf("Failed! The pos is out of range,positon should beteween 1~%d \n", i);
return;
}
i++;
}
printf("the value at position %d is: %d \n", i,q->data);
}