数据结构-单链表（C语言简单实现）

简介

以顺序结构进行数据存储时，它的特点就是可以用一组任意的存储单元存储数据元素，这组存储单元可以是连续的，也可以是不连续的，这些数据可以存在内存未被占用的任意位置。它也是有缺点的，就是在插入和删除时需要移动大量的元素，需要耗费一点时间。

以下是它的一个示意图

想要创建这样的数据结构，首先需要使用结构体先定义一个节点:

typedef struct node
{int data;  // 数据struct node *next;  // 指向下一个节点的地址
}node_t;

然后需要使用结构体定义单链表:

typedef struct list
{struct node *head;  // 头部struct node *tail;  // 尾部
}list_t;

相关函数

• 首先需要定义一个静态函数用于创建节点

static node_t *create_node(int data)
{node_t *pnew = malloc(sizeof(node_t));  // 分配内存空间pnew->data  = data;  // 分配数据pnew->next = NULL;  // 默认指向空return pnew;  // 返回地址
}

• 初始化函数

void list_init(list_t *plist)
{plist->head = create_node(0);  // 为头部创建一个节点plist->tail = create_node(0);  // 为尾部创建一个节点plist->head->next = plist->tail;  // 头部的next指向尾部plist->tail->next = NULL;  // 尾部的next指向NULL
}

• 释放单链表的函数

void list_deinit(list_t *plist)
{node_t *pnode = plist->head;  // 将pnode指向头部// 当pnode非空时，进行循环，说明还有数据while(pnode){node_t *ptmp = pnode->next;  // 备份pnode的nextfree(pnode);  // 释放pnodepnode = ptmp;  // 将之前pnode的next指向现在的pnode}
}

• 遍历单链表

void list_travel(list_t *plist)
{// 遍历: 首先将pnode指向head,直到pnode指向tail结束，pnode每次往后移一位for(node_t *pnode = plist->head; pnode != pnode->tail; pnode = pnode->next){// 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;if(pmid != pnode->tail)printf("%d ", pmid->data);}printf("\n");
}

• 按照顺序添加数据到单链表中

void list_add(list_t *plist, int data)
{// 1. 创建一个新的节点node_t *pnew = create_node(data);// 2. 遍历链表for(node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 当找到比data大的数据，就插入到它后面，或者找到最后都没找到比它大的，就插到最后if(pmid->data > pnew->data || pmid == plist->tail){pfirst->next = pnew;pnew->next = pmid;break;}}
}

• 前插函数(将数据插到最前面)

void list_add_first(list_t *plist, int data)
{// 1. 创建一个新的节点node_t *pnew = create_node(data);// 2. 备份头部的nextnode_t *ptmp = plist->head->next;// 3. 将头部的next指向新节点plist->head->next = pnew;// 4. 将新节点的next指向之前头部指向nextpnew->next = ptmp;
}

• 后插函数(将数据插到最后面)

void list_add_last(list_t *plist, int data)
{// 1. 创建一个新的节点node_t *pnew = create_node(data);// 2. 遍历链表for(node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 当pmid执行plist->tail时，插入if(pmid == plist->tail){pfirst->next = pnew;pnew->next = pmid;break;}}
}

• 删除指定数据所在的节点

void list_del(list_t *plist, int data)
{// 1. 遍历链表for(node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 1.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 1.2 当找到数据相等的，并且此数据不是尾节点，因为尾节点是初始化定义的if(data == pmid->data && pmid != plist->tail){pfirst->next = plast;free(pmid);  // 此时pmid就是要删除的那个节点break;}}
}

示例代码

创建三个文件: list.c、list.h、main.c，实现上面的相关函数

• list.c

#include "list.h"// 定义分配节点内存函数
static node_t *create_node(int data)
{node_t *pnew = malloc(sizeof(node_t));pnew->data = data;pnew->next = NULL;return pnew;
}// 初始化
void list_init(list_t *plist)
{// 1. 给首尾分配内存plist->head = create_node(0);plist->tail = create_node(0);// 2. 头指向尾plist->head->next = plist->tail;// 3. 尾指向空plist->tail->next = NULL;
}// 释放
void list_deinit(list_t *plist)
{// 1. 取到单链表的头部node_t *pnode = plist->head;// 2. 当头部不为空的时候，说明还有数据，继续循环while (pnode){// 2.1 备份pnode->nextnode_t *ptmp = pnode->next;// 2.2 释放pnodefree(pnode);// 2.3 重新指定pnode是ptmppnode = ptmp;}
}// 遍历数据单链表
void list_travel(list_t *plist)
{for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 创建三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 判断pmid是有效节点if (pmid != plist->tail){printf("%d ", pmid->data);}}printf("\n");
}// 按顺序添加数据到单链表中
void list_add(list_t *plist, int data)
{// 1. 创建新的节点node_t *pnew = create_node(data);// 2. 遍历单链表for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 创建三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 判断当找到pmid的数据大于等于data或者找到最后都没找到比data大的，就插到最后if (pmid->data >= pnew->data || pmid == plist->tail){// 2.2.1 放在pmid后面,pfirst的前面pfirst->next = pnew;pnew->next = pmid;break;}}
}// 前插函数
void list_add_first(list_t *plist, int data)
{// 1. 创建新的节点node_t *pnew = create_node(data);// 2. 备份头部的nextnode_t *ptmp = plist->head->next;// 3. 将头部的next指向新的节点plist->head->next = pnew;// 4. 将新的节点next指向之前头部的nextpnew->next = ptmp;
}// 后插函数
void list_add_last(list_t *plist, int data)
{// 1. 创建新的节点node_t *pnew = create_node(data);// 2. 遍历节点，找到tail前面的节点for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 2.1 创建三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 2.2 当pmid==tail时，说明pfirst是tail前面的节点if (pmid == plist->tail){// 2.2.1 将pfirst的next指向pnewpfirst->next = pnew;// 2.2.2 将pnew的next执行tail(pmid)pnew->next = pmid;break;}}
}// 删除指定数字所在所在的节点
void list_del(list_t *plist, int data)
{// 1. 遍历单链表for (node_t *pnode = plist->head; pnode != plist->tail; pnode = pnode->next){// 1.1 三个游标node_t *pfirst = pnode;node_t *pmid = pfirst->next;node_t *plast = pmid->next;// 1.2 当找到数据相等的，并且此数据不是尾节点，因为尾节点是初始化定义的if (data == pmid->data && pmid != plist->tail){// 1.2.1 将pfirst的next指向plastpfirst->next = plast;// 1.2.2 释放pmidfree(pmid);break;}}
}

• list.h声明单链表的相关函数和定义节点和单链表

#ifndef __LIST_H
#define __LIST_H#include <stdio.h>
#include <stdlib.h>// 定义节点
typedef struct node
{int data;struct node *next;
} node_t;// 声明单链表的结构体
typedef struct list
{node_t *head; // 保存头节点的地址node_t *tail; // 保存尾节点的地址
} list_t;extern void list_init(list_t *plist);
extern void list_deinit(list_t *plist);
extern void list_travel(list_t *plist);
extern void list_add(list_t *plist, int data);
extern void list_add_first(list_t *plist, int data);
extern void list_add_last(list_t *plist, int data);
extern void list_del(list_t *plist, int data);#endif

• main.c主函数使用单链表

#include "list.h"int main(void)
{// 1. 创建单链表list_t list;// 2. 初始化单链表list_init(&list);// 3. 插入三个数据10 30 20printf("插入三个数据10 30 20,结果应该排好顺序的: ");list_add(&list, 10);list_add(&list, 30);list_add(&list, 20);// 4. 循环遍历输出单链表list_travel(&list);// 5. 在头部插入一个15printf("在头部插入15: ");list_add_first(&list, 15);// 6.遍历输出单链表list_travel(&list);// 7. 在尾部插入一个1printf("在尾部插入一个1: ");list_add_last(&list, 1);// 8. 遍历输出list_travel(&list);// 9. 删除一个20printf("删除一个20: ");list_del(&list, 20);// 10. 遍历输出list_travel(&list);// 11. 释放整个链表list_deinit(&list);return 0;
}