亲宝软件园·资讯

展开

c语言之单向链表

linuxcszl 人气:1
# 0x00 什么是链表 链表可以说是一种最为基础的数据结构了,而单向链表更是基础中的基础。链表是由一组元素以特定的顺序组合或链接在一起的,不同元素之间在逻辑上相邻,但是在物理上并不一定相邻。在维护一组数据集合时,就可以使用链表,这一点和数组很相似。但是,链表有着数组所不具有的优势。一方面,链表在执行插入删除操作时拥有更高的效率;另一方面,链表是在堆区动态的开辟存储空间,而大多数的数据在编译时大小并不能确定,因此这种动态开辟空间的特性也可以说是链表的一个优点。 # 0x01 链表的应用 - 多项式计算 - 滚动列表 - 邮件列表 - 文件的链式分配 - 内存管理 …… # 0x02 单向链表初见 ![](https://img2018.cnblogs.com/blog/1369260/202002/1369260-20200229181412525-2109733226.png) 就像图像所示,单向链表各个元素之间通过一个指针先后链接起来。每个元素包含两个部分,分别是数据域和指针域。前一个元素通过next指针指向后一个元素,链表的开始的元素为链表头,即head指针所指,链表结束的元素为链表尾,尾部元素的next指针指向NULL。可见,单向链表为线性结构。 若想访问链表中的一个元素,我们只能从链表的头部开始,顺着指针指向逐查找。如果从链表头移动到指定的元素,而这时候我们又想访问当前元素之前的某个元素,这时候只能从头在次遍历链表。这相比数组能够通过下标直接访问要麻烦的多,不过我们应该根据不同的应用场景选择数组还是链表,它们只有在对的地方才能发挥出巨大的威力。 # 0x03 单向链表的操作 ### 0x00 链表结构 ```c typedef struct node//链表元素的结构 { void *data;//节点中的数据域,设置为无类型指针,数据类型大小由使用者定义 struct node *next;//指向下一节点的指针 }Node; typedef struct list//链表的结构 { int size;//链表中节点个数 void (*destroy)(void *data);//由于链表节点中的数据是用户自定义的,故需要调用者提供释放空间的函数 void (*print_data)(const void *data);//同,由用户自定义打印数据的函数 int (*match)(const void *key1, const void *key2);//同,由用户自定义数据的比较方式 Node *head;//记录链表的头部位置 Node *tail;//记录链表的尾部位置 }List; ``` 示意图如下: ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305143043069-1827148655.png) ### 0x01 接口 下面是链表操作函数的接口,以及简单介绍: ```c extern void list_init(List *list, void (*destroy)(void *data), void (*print_data)(const void *data), \ int (*match)(const void *key1, const void *key2));//初始化一个链表 extern int list_ins_head(List *list, const void *data);//链表的插入,将节点从头部插入 extern int list_ins_tail(List *list, const void *data);//链表的插入,将节点从尾部插入 extern int list_ins_sort(List *list, const void *data);//链表的插入,插入后链表是一个有序的链表 extern void* list_search(List *list, const void *data);//在链表中查找指定数据,若找到返回数据的地址 extern void* list_remove(List *list, const void *data);//在链表中删除指定数据,若找到删除节点并将数据地址返回 extern void list_reverse(List *list);//将链表逆置 extern void list_sort(List *list);//将链表按照一定方式排序 extern void print_list(List *list);//打印链表 extern void list_destroy(List *list);//删除整个链表 #define list_size(list) (list->size) //返回链表节点个数 ``` ### 0x02 list_init 使用list_init函数初始化一个链表,以便链表的其他操作。 ```c void list_init(List *list, void (*destroy)(void *data), void (*print_data)(const void *data), \ int (*match)(const void *key1, const void *key2)) { list->size = 0;//初始时,链表没有节点,设置为0 list->head = NULL;//头和尾置空 list->tail = NULL; list->match = match;//初始化链表的成员函数 list->destroy = destroy; list->print_data = print_data; return; } ``` ### 0x03 list_ins_head 使用list_ins_head函数,在链表的头部插入数据。示意图如下: ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305183853015-418080773.png) 从示意图可以看出,单向链表的部插入逻辑非常简单。仔细观察,标绿的部分代码有重复,可以优化 ```c /*在链表的头部插入数据*/ int list_ins_head(List *list, const void *data) { Node *new_node = (Node *)calloc(1, sizeof (Node)); //创建插入的节点 if(new_node == NULL) return -1; new_node->data = (void *)data;//关联节点与数据 /* if(list_size(list) == 0)//链表为空时,插入节点 { list->tail = new_node; new_node->next = NULL; list->head = new_node; } else //链表非空时将节点插入头部 { new_node->next = list->head; list->head = new_node; } */ if(list_size(list) == 0)//链表为空时,插入节点 list->tail = new_node; new_node->next = list->head; list->head = new_node; list->size ++;//维护链表size属性 return 0; } ``` ### 0x04 list_ins_tail 使用list_ins_tail函数,在链表的尾部插入数据,示意图如下: ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305185352040-1195936900.png) ```c /*在链表的尾部插入数据*/ int list_ins_tail(List *list, const void *data) { Node *new_node = (Node *)calloc(1, sizeof (Node)); //创建插入的节点 if(new_node == NULL) return -1; new_node->data = (void *)data;//关联节点与数据 if(list_size(list) == 0) list->head = new_node; else list->tail->next = new_node; list->tail = new_node; new_node->next = NULL; list->size ++; return 0; } ``` ### 0x05 list_ins_sort 使用list_ins_sort函数,进行链表的有序插入。 链表的有序插入大致可以分为两种情况: 其一,链表为空时直接插入; 其二,链表非空时,在此时又分为三种小情况; 1. 在链表头部插入 2. 在链表中部插入 3. 在链表尾部插入 链表为空时,操作方法和头尾部插入类似。链表非空时,我们需要先寻找到插入位置,然后在将数据插入链表。 在此之前我们已经了解了如何在链表的头部和尾部插入元素,那么,现在唯一需要处理的便是 **在链表中部插入节点** ,这是链表插入操作的核心。 ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305203819541-20109594.png) 注意:在链表中部插入节点时,必须得到前一节点的位置,即图中指向蓝色节点的指针p_pre. 插入节点的逻辑了解后,处理在非空链表情况下插入节点就清晰多了。 ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305202631739-978793271.png) ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305204216744-14371590.png) ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305204239271-78049757.png) ```c /*在链表的有序插入数据*/ int list_ins_sort(List *list, const void *data) { Node *new_node = (Node *)calloc(1, sizeof (Node)); //创建插入的节点 if(new_node == NULL) return -1; new_node->data = (void *)data;//关联节点与数据 if(list_size(list) == 0)//链表为空时,插入节点 { list->tail = new_node; new_node->next = NULL; list->head = new_node; } else//链表非空 { Node *p_cur = list->head; Node *p_pre = list->head; while(p_cur != NULL && list->match(new_node->data, p_cur->data) > 0)//查找链表的插入位置 { p_pre = p_cur; p_cur = p_cur->next; } if(p_cur != NULL)//插入位置在头部和中间时 { if(p_cur == list->head)//插入位置在头部 { new_node->next = list->head; list->head = new_node; } else//位置在链表中间 { new_node->next = p_pre->next; p_pre->next = new_node; } } else//插入位置在链表尾部 { list->tail->next = new_node; list->tail = new_node; new_node = NULL; } } list->size ++; return 0; } ``` ### 0x06 list_search 使用list_search函数,查找链表中与数据匹配的节点,并返回节点指针。 此处查找逻辑与list_ins_sort中的查找逻辑基本类似,不做赘述。 ```c /*查找链表中与数据匹配的节点,并返回节点指针*/ void* list_search(List *list, const void *data) { if(list_size(list) == 0) { printf("list is empty\n"); return NULL; } else { Node *p_cur = list->head; while(p_cur != NULL && list->match(p_cur->data, data) != 0)//查找数据在链表中的位置 p_cur = p_cur->next; if(p_cur != NULL)//找到返回数据地址,否则返回NULL return p_cur->data; else return NULL; } } ``` ### 0x07 list_remove 使用list_remove函数,删除节点,并将节点中的数据返回,交由用户处理。 此处查找逻辑与list_ins_sort中的查找逻辑基本类似,不做赘述。 和插入节点中分为头部、中部尾部类似,删除也分为头中尾部。 **删除头部节点** ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305214038071-1513107059.png) 不过删除头部节点时需要注意一点,就是当链表仅有一个节点时,我们需要维护一下tail指针。 **删除中部节点** ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305215112498-8656871.png) **删除尾部节点** ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305220159642-1770737888.png) 注意:代码中将中部与尾部的删除进行了合并。 ```c /*删除指定数据的节点*/ void* list_remove(List *list, const void *data) { void *old_data = NULL; Node *p_cur = list->head; Node *p_pre = list->head; while (p_cur != NULL && list->match(p_cur->data, data) !=0) { p_pre = p_cur; p_cur = p_cur->next; } if(p_cur != NULL && list->match(p_cur->data, data) ==0)//删除位置在头部和中间时 { if(p_cur == list->head)//删除位置在头部 { list->head = p_cur->next; if(p_cur->next == NULL) list->tail = NULL; } else//中部时或尾部 { p_pre->next = p_cur->next; if(p_cur->next == NULL)//判断是否为尾部 list->tail = p_pre; } old_data = p_cur->data; free(p_cur); list->size --; } return old_data; } ``` ### 0x08 list_reverse 使用list_reverse函数将链表逆置。 逆置过程: ![](https://img2020.cnblogs.com/blog/1369260/202003/1369260-20200305222758130-79867425.png) 观察可以发现,逆置的过程本质上就是将原来的链表逐个摘下头节点,插入逆置后的链表的头部 ```c void list_reverse(List *list) { if(list_size(list) != 0) { Node *p_pre = list->head; Node *p_cur = list->head->next; list->head->next = NULL; list->tail = list->head; while(p_cur!= NULL) { p_pre = p_cur; p_cur = p_cur->next; p_pre->next = list->head; list->head = p_pre; } } return; } ``` ### 0x09 list_sort 使用list_sort函数对链表进行排序,此处使用选择排序法。 ```c void list_sort(List *list) { if(list_size(list) != 0) { Node *p_i = list->head; while(p_i->next != NULL) { Node *p_min = p_i; Node *p_j = p_min->next; while (p_j != NULL) { if(list->match(p_min->data, p_j->data) > 0) p_min = p_j; p_j = p_j->next; } if(p_min != p_i) { void *data = p_i->data; p_i->data = p_min->data; p_min->data = data; } p_i = p_i->next; } } return; } ``` ### 0x10 print_list和list_destroy ```c void print_list(List *list) { if(list->head == NULL)//链表为空 { printf("list is empty\n"); } else //链表非空 { Node * p_cur = list->head; while (p_cur) { list->print_data(p_cur->data); p_cur = p_cur->next; } } return; } ``` ```c void list_destroy(List *list) { Node *p_cur = list->head; while (p_cur != NULL) { list->head = list->head->next; list->destroy(p_cur->data);//释放节点中的数据 free(p_cur);//释放节点 p_cur = list->head; } memset(list, 0, sizeof (List)); return; } ```

加载全部内容

相关教程
猜你喜欢
用户评论