单向链表
（1）单向链表的基本了解
先是定义一个单向链表的节点结构体：
typedef struct Node{
int data;
struct Node *pNext;
}NODE, *PNODE;
那么整个结构体可以抽象成下图：
其中，一个空链表就只有一个头节点（在本篇文章中头节点用于数据的存储，只用于作为索引，当然，你也可以将它和普通节点一样存放数据等）：
而n个节点的链表如下（这里n=3）：
（2）增删改查
① 增——在尾部增加节点
② 增——在中间插入一个节点
③ 增——在链表头部插入一个节点
与“在中间插入一个节点”同样原理，所以这里省略过程：
④ 删——删除尾部节点
⑤ 删——删除中间节点
⑥ 删——删除第一个节点
⑦ 改
略。
⑧ 查
略。
（3）单向链表程序示例
注：程序仅作参考，不考虑严谨性。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node{
int data;
struct Node *pNext;
}NODE, *PNODE;
PNODE create_List(void);
int destory_list(PNODE pHead);
int list_is_empty(PNODE pHead);
int list_length(PNODE pHead);
int insert_node_to_list_head(PNODE pHead, PNODE node);
int insert_node_to_list_by_position(PNODE pHead, int position, PNODE node);
int insert_node_to_list_tail(PNODE pHead, PNODE node);
void remove_list_first_node(PNODE pHead);
void remove_list_node_by_position(PNODE pHead, int position);
void remove_list_tail_node(PNODE pHead);
int midify_list_node(PNODE pHead, int position, int val);
void show_all_list_node(PNODE pHead);
int main()
{
PNODE pHead = NULL; /* 先定义一个头结点 */
NODE tmpNode;
int ret, pos, val;
pHead = create_List();
if(pHead == NULL){
printf("创建链表失败！\n");
return -1;
}
char ch;
while(1){
printf("------------------------------------\n"
"a) 添加节点到链表头部\n"
"b) 添加节点到链表尾部\n"
"c) 添加节点到链表指定位置\n"
"d) 删除链表第一个节点\n"
"e) 删除链表最后一个节点\n"
"f) 删除链表指定位置的节点\n"
"g) 修改节点内容\n"
"h) 查看链表长度\n"
"i) 查看链表内容\n"
"z) 退出\n"
"请输入你的选择: "
);
scanf("%c", &ch); getchar();
switch(ch){
case 'a':
printf("请输入新增节点的值：");
scanf("%d", &tmpNode.data); getchar();
ret = insert_node_to_list_head(pHead, &tmpNode);
if(ret){
printf("插入节点失败！\n");
break;
}
printf("操作成功！\n");
break;
case 'b':
printf("请输入新增节点的值：");
scanf("%d", &tmpNode.data); getchar();
ret = insert_node_to_list_tail(pHead, &tmpNode);
if(ret){
printf("插入节点失败！\n");
break;
}
printf("操作成功！\n");
break;
case 'c':
printf("请输入节点插入的位置：");
scanf("%d", &pos);
printf("请输入新增节点的值：");
scanf("%d", &tmpNode.data); getchar();
ret = insert_node_to_list_by_position(pHead, pos, &tmpNode);
if(ret){
printf("插入节点失败！\n");
break;
}
printf("操作成功！\n");
break;
case 'd':
remove_list_first_node(pHead);
printf("操作成功！\n");
break;
case 'e':
remove_list_tail_node(pHead);
printf("操作成功！\n");
break;
case 'f':
printf("请输入需要删除的节点位置：");
scanf("%d", &pos); getchar();
remove_list_node_by_position(pHead, pos);
break;
case 'g':
printf("请输入需要修改的节点位置：");
scanf("%d", &pos); getchar();
printf("请输入修改后的值：");
scanf("%d", &val); getchar();
midify_list_node(pHead, pos, val);
break;
case 'h':
printf("链表长度：%d\n", list_length(pHead));
break;
case 'i':
show_all_list_node(pHead);
break;
case 'z':
destory_list(pHead);
return 0;
default:
printf("输入有误！请重新输入...\n");
break;
}
}
return 0;
}
PNODE create_List(void)
{
PNODE tmp = NULL;
tmp = (PNODE)malloc(sizeof(NODE));
if(tmp == NULL){
printf("分配节点内存失败！\n");
return NULL;
}
memset(tmp, 0, sizeof(*tmp));
return tmp;
}
int destory_list(PNODE pHead)
{
/* 将"第一个"释放掉，释放掉之后又生成新的"第1个" */
while(pHead->pNext){
remove_list_first_node(pHead);
}
/* 头节点也要释放掉 */
free(pHead);
}
int list_is_empty(PNODE pHead)
{
if(pHead->pNext)
return 0;
else
return 1;
}
int list_length(PNODE pHead)
{
PNODE tmp = pHead;
int length = 0;
while(tmp->pNext){
length++;
tmp = tmp->pNext;
}
return length;
}
int insert_node_to_list_tail(PNODE pHead, PNODE pNode)
{
PNODE tmp = pHead;
/* 找到尾节点 */
while(tmp->pNext){
tmp = tmp->pNext;
}
/* 在堆里分配一块内存，用于存放新节点 */
PNODE pNew = (PNODE)malloc(sizeof(NODE));
memcpy(pNew, pNode, sizeof(NODE));
/* 原来的尾节点指向新节点 */
tmp->pNext = pNew;
/* 确保新的尾节点的指针为NULL */
pNew->pNext = NULL;
return 0;
}
int insert_node_to_list_by_position(PNODE pHead, int position, PNODE pNode)
{
PNODE tmp = pHead;
int i = 0;
/* 找出需要插入的前一个位置 */
while(tmp->pNext && i < position-1){
tmp = tmp->pNext;
i++;
}
/* 如果链表没有那么长则返回 */
if(tmp->pNext == NULL || i < position-1){
printf("链表长度不够!\n");
return -1;
}
PNODE pNew = (PNODE)malloc(sizeof(NODE));
memcpy(pNew, pNode, sizeof(NODE));
pNew->pNext = tmp->pNext;
tmp->pNext = pNew;
return 0;
}
int insert_node_to_list_head(PNODE pHead, PNODE pNode)
{
#if 1
PNODE pNew = (PNODE)malloc(sizeof(NODE));
memcpy(pNew, pNode, sizeof(NODE));
pNew->pNext = pHead->pNext;
pHead->pNext = pNew;
return 0;
#else
return remove_list_node_by_position(pHead, 1, pNode);
#endif
}
void remove_list_first_node(PNODE pHead)
{
/* 如果是空的链表则不需要操作 */
if(list_is_empty(pHead)){
printf("空链表，无需操作！\n");
return;
}
/* 将头节点指向第1个节点先保存起来 */
PNODE tmp = pHead->pNext;
/* 将头节点指向第1个节点的下一个节点 */
pHead->pNext = pHead->pNext->pNext;
/* 释放刚才保存的tmp节点 */
free(tmp);
}
void remove_list_node_by_position(PNODE pHead, int position)
{
PNODE tmp = pHead;
PNODE tofree = NULL;
int i = 0;
/* 如果是空的链表则不需要操作 */
if(list_is_empty(pHead)){
printf("空链表，无需操作！\n");
return;
}
/* 找出需要删除的前一个位置 */
while(tmp->pNext && i < position-1){
tmp = tmp->pNext;
i++;
}
/* 如果链表没有那么长则返回 */
if(tmp->pNext == NULL || i < position-1){
printf("链表长度不够!\n");
return;
}
/* 将要释放的节点先保存起来 */
tofree = tmp->pNext;
/* 指向下一个节点的下一个节点 */
tmp->pNext = tmp->pNext->pNext;
/* 释放资源 */
free(tofree);
}
void remove_list_tail_node(PNODE pHead)
{
int i = 0;
int length = list_length(pHead);
PNODE tmp = pHead->pNext;
if(length >= 2){
/* 先找到倒数第2个节点 */
while(tmp->pNext && i < length-2){
tmp = tmp->pNext;
i++;
}
/* 将倒数第1个节点释放 */
free(tmp->pNext);
/* 将倒数第2个节点的指针指向NULL */
tmp->pNext = NULL;
}
else{
/* 只有一个节点，那同时也是头节点；同时也能处理空链表 */
remove_list_first_node(pHead);
}
}
int midify_list_node(PNODE pHead, int position, int val)
{
int i = 0;
PNODE tmp = pHead;
if(position > list_length(pHead)){
printf("链表长度不够!\n");
return -1;
}
/* 找出需要修改的位置 */
while(i < position){
tmp = tmp->pNext;
i++;
}
tmp->data = val;
return 0;
}
void show_all_list_node(PNODE pHead)
{
/* 从第一个节点开始而不是头节点 */
PNODE tmp = pHead->pNext;
printf("链表数据如下: \n");
while(tmp != NULL){
printf("%d\n", tmp->data); /* 打印节点的数据 */
tmp = tmp->pNext; /* 切换到下一个节点 */
}
}
转载：https://blog.csdn.net/weixin_44498318/article/details/115917861
查看评论