【原】数据结构提高：链表

文章目录

题目

请用 c 语言自己实现单项链表的增删改查功能

代码

创建链表

使用结构体定义节点类型：

typedef struct _LINKNODE
{
int id; //数据域
struct _LINKNODE* next; //指针域
}link_node;

编写函数：link_node* init_linklist()
建立带有头结点的单向链表，循环创建结点，结点数据域中的数值从键盘输入，以 -1 作为输入结束标志，链表的头结点地址由函数值返回.

typedef struct _LINKNODE {
int data;
struct _LINKNODE* next;
}link_node;

link_node* init_linklist() {
// 创建头结点指针
link_node *head = NULL;
// 给头结点分配内存
head = (link_node*)malloc(sizeof(link_node));
if (head == NULL) {
return NULL;
}
head->data = -1;
head->next = NULL;

//保存当前节点 p_current用于后续插入操作
link_node* p_current = head;

//循环向链表中插入节点
while (1) {
printf("please input data:\n");
scanf("%d", &data);
//如果输入-1，则退出循环
if (data == -1) {
break;
}
//给新节点分配内存
link_node* newnode = (link_node*)malloc(sizeof(link_node));
if (newnode == NULL) {
break;
}
//给节点赋值
newnode->data = data;
newnode->next = NULL;
//新节点入链表，也就是将节点插入到最后一个节点的下一个位置
p_current->next = newnode;
//更新辅助指针 p_current
p_current = newnode;
}
return head;
}

遍历链表

编写函数：void foreach_linklist(link_node* head)

顺序输出单向链表各项结点数据域中的内容：

//遍历链表
void foreach_linklist(link_node* head) {
if (head == NULL) {
return;
}
//赋值指针变量
link_node* p_current = head->next;
while (p_current != NULL) {
printf("%d ", p_current->data);
p_current = p_current->next;
}
printf("\n");
}

插入节点

编写函数: void insert_linklist(link_node* head,int val,int data).
在指定值后面插入数据 data,如果值 val 不存在，则在尾部插入。

//在值 val 前插入节点
void insert_linklist(link_node* head, int val, int data) {
if (head == NULL) {
return;
}
//两个辅助指针
link_node* p_prev = head;
link_node* p_current = p_prev->next;
while (p_current != NULL) {
if (p_current->data == val) {
break;
}

p_prev = p_current;
p_current = p_prev->next;
}
//如果 p_current 为 NULL，说明不存在值为 val 的节点
if (p_current == NULL) {
printf("不存在值为%d 的节点!\n", val);
return;
}
//创建新的节点
link_node* newnode = (link_node*)malloc(sizeof(link_node));
newnode->data = data;
newnode->next = NULL;
//新节点入链表
newnode->next = p_current;
p_prev->next = newnode;
}

删除节点

编写函数: void remove_linklist(link_node* head,int val)
删除第一个值为 val 的结点.

//删除值为 val 的节点
void remove_linklist(link_node* head, int val) {
if (head == NULL) {
return;
}
//辅助指针
link_node* p_prev = head;
link_node* p_current = p_prev->next;
//查找值为 val 的节点
while (p_current != NULL) {
if (p_current->data == val) {
break;
}
p_prev = p_current;
p_current = p_prev->next;
}
//如果 p_current 为 NULL，表示没有找到
if (p_current == NULL) {
return;
}
//删除当前节点： 重新建立待删除节点(p_current)的前驱后继节点关系
p_prev->next = p_current->next;
//释放待删除节点的内存
free(p_current);
}

销毁链表

编写函数 : void destroy_linklist(link_node* head)
销毁链表，释放所有节点的空间.

//销毁链表
void destroy_linklist(link_node* head) {
if (head == NULL) {
return;
}
//赋值指针
link_node* p_current = head;
while (p_current != NULL) {
//缓存当前节点下一个节点
link_node* p_next = p_current->next;
free(p_current);
p_current = p_next;
}

}