数据结构之单链表、双向链表和循环链表

快来打我* 2022-12-14 13:33 301阅读 0赞

链表是一种最为基础的数据结构，需要动态开辟空间，在执行删除或插入操作时效率高。主要分类有：

  • 单链表
  • 双向链表
  • 循环链表
    链表的应用场景：（不需要预先知道数据规模；适应于频繁的删除插入操作。），如：
    内存管理：内存管理是操作系统中一项重要的任务，操作系统必须决定如何为系统中运行的进程分配和回收存储空间。链表能够用来跟踪可分配的内存片段信息。
    其他的数据结构：栈、队列、集合、哈希表和图都要依赖于链表。

单链表

简称链表，由各个数据成员通过一个指针彼此链接起来而组成。每个元素包括两部分：数据成员和一个称为next的指针。只能以一个方向进行遍历，从头到尾。
在这里插入图片描述

  1. //list.h
  2. #pragma once
  3. #ifndef LIST_H
  4. #define LIST_H
  5. #endif // !LIST_H
  7. #include<stdlib.h>
  9. //定义链表元素的结构
  10. typedef struct ListElmt_ {
  12.     void * data;
  13.     struct ListElmt_ *next;
  14. } ListElmt;
  16. //定义链表的结构
  17. typedef struct List_ {
  19.     //size表示链表元素的个数
  20.     int size;
  21.     //match并不是由链表本身使用，而是由从链表数据结构派生而来的新类型所使用。
  22.     int(*match)(const void *key1, const void *key2);
  23.     //destroy是封装之后传递给list_init的析构函数
  24.     void(*destroy)(void *data);
  25.     //指向头结点的指针
  26.     ListElmt *head;
  27.     //指向尾结点的指针
  28.     ListElmt *tail;
  29. }List;
  31. //公共接口
  32. //初始化
  33. void list_init(List *list, void(*destroy)(void *data));
  34. //销毁
  35. void list_destroy(List *list);
  37. //如果插入元素成功则返回0，否则返回-1
  38. /*
  39. 在list指定的链表中element后面插入一个新元素，如果element为空，说明链表为空，新元素插入链表头部
  40. 新元素包含一个指向data的指针，只要该元素在链表中，data所引用的内存空间要保持合法
  41. */
  42. int list_ins_next(List *list, ListElmt *element, const void* data);
  43. /*移除element后的一个元素，data指向已移除中存储的元素
  44. 如果element为NULL，则移除头结点*/
  45. int list_rem_next(List* list, ListElmt * element, void **data);
  47. //int list_size(const List* list);
  48. //
  49. 返回指向链表中头元素的指针
  50. //ListElmt * list_head(const List *list);
  51. 返回指向链表尾元素的指针
  52. //ListElmt * list_tail(const List *list);
  53. 判断是否头结点,尾结点
  54. //int list_is_head(const ListElmt *element);
  55. //int list_is_tail(const ListElmt *element);
  56. //
  57. 返回节点中保存的数据
  58. //void *list_data(const List *element);
  60. #define list_size(list) ((list)->size)
  61. #define list_head(list) ((list)->head)
  62. #define list_tail(list) ((list)->tail)
  63. #define list_is_head(list,element) ((element) == (list)->head?1:0)
  64. #define list_is_tail(element) ((element)->next == NULL ? 1:0)
  65. #define list_data(element) ((element)->data)
  66. #define list_next(element) ((element)->next)
  68. //list.c
  69. #include<stdlib.h>
  70. #include<string.h>
  71. #include"list.h"
  72. //初始化链表
  73. void list_init(List *list, void(*destroy)(void *data)) {
  75.     list->size = 0;
  76.     list->destroy = destroy;
  77.     list->head = NULL;
  78.     list->tail = NULL;
  79.     return;
  80. }
  81. //销毁链表
  82. void list_destroy(List *list) {
  84.     void * data;
  85.     //移除每个元素
  86.     while (list_size(list) > 0)
  87.     {
  89.         if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {
  91.             //调用一个用户分配的函数来释放动态分配的内存
  92.             list->destroy(data);
  93.         }
  94.     }
  95.     //现在无操作被允许，但是要对这个结构进行清零操作，作为预防措施
  96.     memset(list, 0, sizeof(List));
  97.     return;
  99. }
  101. //移除element之后的一个元素
  102. int list_rem_next(List *list, ListElmt *element, void **data) {
  104.     ListElmt *old_element;
  106.     //如果链表为空，则直接返回-1；
  107.     if (list_size(list) == 0) {
  109.         return -1;
  110.     }
  111.     //如果element为空，删除头结点
  112.     if (element == NULL) {
  114.         *data = list->head->data;
  115.         old_element = list->head;
  116.         list->head = list->head->next;
  118.         if (list_size(list) == 1) {
  120.             list->tail = NULL;
  121.         }
  122.     }
  123.     else
  124.     {
  126.         //需要删除的元素在头结点之外
  128.         //如果删除的元素为空，则直接返回
  129.         if (element->next == NULL) {
  131.             return -1;
  132.         }
  134.         *data = element->next->data;
  135.         old_element = element->next;
  136.         element->next = element->next->next;
  138.         //如果删除外element后的节点后，element之后没节点了，说明element成了尾结点
  139.         if (element->next == NULL) {
  141.             list->tail = element;
  142.         }
  143.     }
  145.     //old_element是需要删除的节点,释放他的内存
  146.     free(old_element);
  148.     //调整list的size
  149.     list->size--;
  150.     return 0;
  151. }
  153. //在element之后插入一个元素
  154. int list_ins_next(List *list, ListElmt *element, const void *data) {
  156.     ListElmt * new_element;
  157.     //为该元素分配内存
  158.     new_element = (ListElmt*)malloc(sizeof(ListElmt));
  159.     //如果未分配到内存
  160.     if (new_element == NULL) return -1;
  162.     //需要强制转换，const类型不能转给非const类型
  163.     new_element->data =(void *) data;
  165.     //如果element为空，则把new_element作为头结点
  166.     if (element == NULL) {
  168.         //如果是个空链表
  169.         if (list_size(list) == 0) {
  171.             list->tail = new_element;
  172.         }
  173.         new_element->next = list->head;
  174.         list->head = new_element;
  175.     }
  176.     else
  177.     {
  179.         //如果element为尾结点
  180.         if (element->next == NULL) {
  182.             list->tail = new_element;
  183.         }
  185.         new_element->next = element->next;
  186.         element->next = new_element;
  187.     }
  189.     list->size++;
  190.     return 0;
  191. }

双向链表

链表元素由两个指针链接。每个元素有三部分组成：除了数据成员和next指针外，还有包含一个指向前一个元素的指针prev。为了标识头和尾，将第一个元素的prev指针和最后一个元素的next指针置为NULL。它可以从头到尾，也可以从尾到头遍历整个链表。
在这里插入图片描述

  1. //dlist.h
  2. #pragma once
  3. #ifndef DLIST_H
  4. #define DLIST_H
  6. #include<stdlib.h>
  7. typedef struct DListElmt_ {
  9.     void *data;
  10.     struct DListElmt_ *prev;
  11.     struct DListElmt_ *next;
  12. } DListElmt;
  13. typedef struct DList_ {
  15.     int size;
  16.     int(*match)(const void *key1, const void *key2);
  17.     void(*destroy)(void *data);
  18.     DListElmt *head;
  19.     DListElmt *tail;
  20. } DList;
  21. //公共接口
  22. void dlist_init(DList * list, void(*destroy)(void *data));
  23. void dlist_destroy(DList *list);
  24. int dlist_ins_next(DList *list, DListElmt * element, const void *data);
  25. int dlist_ins_prev(DList *list, DListElmt * element, const void *data);
  26. int dlist_remove(DList *list, DListElmt *element, void **data);
  28. #define dlist_size(list) ((list)->size)
  29. #define dlist_head(list) ((list)->head)
  30. #define dlist_tail(list) ((list)->tail)
  31. #define dlist_is_head(element) ((element)->prev == NULL ? 1:0)
  32. #define dlist_is_tail(element) ((element)->next == NULL ? 1:0)
  33. #define dlist_data(element) ((element)->data)
  34. #define dlist_next(element) ((element)->next)
  35. #define dlist_prev(element) ((element)->prev)
  36. #endif // !DLIST_H
  38. //dlist.c
  39. #include<stdlib.h>
  40. #include<string.h>
  41. #include"dlist.h"
  43. void dlist_init(DList *list, void(*destroy)(void *data)) {
  45.     list->size = 0;
  46.     list->destroy = destroy;
  47.     list->head = NULL;
  48.     list->tail = NULL;
  49.     return;
  50. }
  52. void dlist_destroy(DList *list) {
  54.     void *data;
  55.     while (dlist_size(list)>0)
  56.     {
  58.         if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->destroy != NULL) {
  60.             //调用用户自定义的函数来释放动态分配的数据data
  61.             list->destroy(data);
  62.         }
  63.     }
  64.     memset(list, 0, sizeof(list));
  65.     return;
  66. }
  67. //将元素插入element之后
  68. int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
  70.     DListElmt * new_element;
  72.     //不可能的情况
  73.     if (element == NULL && dlist_size(list) != 0) {
  75.         return -1;
  76.     }
  77.     //为要插入的元素分配内存,内存分配失败返回-1
  78.     if ((new_element = (DListElmt*)malloc(sizeof(DListElmt))) == NULL) {
  80.         return -1;
  81.     }
  82.     new_element->data =(void *) data;
  84.     //如果链表为空,该元素要作为头结点
  85.     if (dlist_size(list) == 0) {
  87.         new_element->prev = NULL;
  88.         new_element->next = NULL;
  89.         list->head = new_element;
  90.         list->tail = new_element;
  91.     }
  92.     else {
  94.         new_element->prev = element;
  95.         new_element->next = element->next;
  96.         element->next = new_element;
  98.         //还要考虑element后为空的情况,插入之后，new_element就变成最后一个了
  99.         if (element->next == NULL) {
  101.             list->tail = new_element;
  102.         }
  103.         else {
  105.             element->next->prev = new_element;
  106.         }
  107.     }
  108.     list->size++;
  109.     return 0;    
  110. }
  111. //在element之前插入
  112. int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
  114.     //先创建一个新元素
  115.     DListElmt * new_element;
  116.     if (element == NULL && dlist_size(list) == 0) {
  118.         return -1;
  119.     }
  120.     //分配内存
  121.     new_element = (DListElmt *)malloc(sizeof(DListElmt));
  122.     if (new_element == NULL) {
  124.         //分配内存失败
  125.         return -1;
  126.     }
  127.     //将数据放入
  128.     new_element->data = (void *)data;
  130.     //如果element为NULL，说明链表为空,也可以用size==0表示,插入的元素为第一个
  131.     if (element == NULL) {
  133.         new_element->next = NULL;
  134.         new_element->prev = NULL;
  135.         list->head = new_element;
  136.         list->tail = new_element;
  137.     }
  138.     else
  139.     {
  141.         new_element->next = element;
  142.         new_element->prev = element->prev;
  143.         //如果该元素是头元素，则新元素应该成为新的头元素
  144.         if (element->prev == NULL) {
  146.             list->head = new_element;
  147.         }
  148.         else {
  150.             element->prev->next = new_element;    
  151.         }
  152.         element->prev = new_element;
  153.     }
  154.     list->size++;
  155.     return 0;
  157. }
  158. //删除元素
  159. int dlist_remove(DList *list, DListElmt * element, void ** data) {
  161.     //如果元素为空，或者链表为空，删除失败
  162.     if (element == NULL || dlist_size(list) == 0)
  163.         return -1;
  164.     *data = element->data;
  166.     //如果该数据是头结点
  167.     if (element->prev == NULL) {
  169.         list->head = element->next;
  170.         //如果链表只有一个元素
  171.         if (element->next == NULL) {
  173.             list->tail = NULL;
  174.         }
  175.         else {
  177.             element->next->prev = NULL;
  178.         }
  179.     }
  180.     else {
  182.         element->prev->next = element->next;
  183.         //如果这个元素是最后一个
  184.         if (element->next == NULL) {
  186.             list->tail = element->prev;
  187.         }
  188.         else {
  190.             element->next->prev = element->prev;
  191.         }
  192.     }
  194.     //释放内存
  195.     free(element);
  196.     list->size--;
  197.     return 0;
  198. }

循环链表

在这里插入图片描述
在这里插入图片描述
循环链表可以是单向的也可以是双向的。区分一个链表是不是循环链表只要看它有没有尾部元素即可。
在循环链表中，最后一个元素指向头元素，而不是NULL；如果是双向的循环链表，它的头元素的prev要指向最后一个元素，而不是NULL。

  1. //clist.h
  2. #pragma once
  3. #ifndef CLIST_H
  4. #define CLIST_H
  5. #include<stdlib.h>
  6. typedef struct CListElmt_ {
  8.     void *data;
  9.     struct CListElmt_ *next;
  10. } CListElmt;
  11. typedef struct Clist_ {
  13.     int size;
  14.     int(*match)(const void *key1, const void *key2);
  15.     void(*destroy)(void *data);
  16.     CListElmt *head;
  17. } CList;
  19. //公共接口
  20. void clist_init(CList *list, void(*destroy)(void *data));
  21. void clist_destroy(CList *list);
  22. int clist_ins_next(CList *list, CListElmt *element, const void *data);
  23. int clist_rem_next(CList *list, CListElmt *element, void **data);
  25. #define clist_size(list) ((list)->size)
  26. #define clist_head(list) ((list)->head)
  27. #define clist_data(element) ((element)->data)
  28. #define clist_next(element) ((element)->next)
  29. #endif // !CLIST_H
  31. #include<stdlib.h>
  32. #include<string.h>
  33. #include"clist.h"
  35. void clist_init(CList *list, void(*destroy)(void *data)) {
  37.     list->size = 0;
  38.     list->head = NULL;
  39.     list->destroy = destroy;
  40.     return;
  41. }
  42. void clist_destroy(CList *list) {
  44.     void *data;
  45.     while (clist_size(list)>0)
  46.     {
  48.         if (clist_rem_next(list, list->head, (void **)&data) == 0 && list->destroy !=NULL) {
  50.             list->destroy(data);
  51.         }
  52.     }
  53.     memset(list, 0, sizeof(CList));
  54.     return;
  55. }
  56. int clist_ins_next(CList *list, CListElmt *element, const void*data) {
  58.     CListElmt * new_element;
  59.     if ((new_element = (CListElmt *)malloc(sizeof(CListElmt))) == NULL) {
  61.         return -1;
  62.     }
  63.     new_element->data = (void *)data;
  64.     //如果链表为空
  65.     if (clist_size(list) == 0) {
  67.         list->head = new_element;
  68.         list->head->next = new_element;
  69.     }
  70.     else {
  72.         new_element->next = element->next;
  73.         element->next = new_element;
  74.     }
  75.     list->size++;
  76.     return 0;
  77. }
  78. int clist_rem_next(CList *list, CListElmt *element, void ** data) {
  80.     CListElmt * old_element;
  81.     if (clist_size(list) == 0) {
  83.         return -1;
  84.     }
  85.     //如果只有一个元素
  86.     if (clist_size(list) == 1) {
  88.         list->head = NULL;
  89.         old_element = element;
  90.     }
  91.     else {
  93.         old_element = element;
  94.         element->next = element->next->next;
  95.         if (old_element == clist_head(list)) {
  97.             list->head = old_element->next;
  98.         }
  99.     }
  101.     free(old_element);
  102.     list->size--;
  103.     return 0;
  104. }

发表评论

表情：
评论列表 （有 0 条评论，301人围观）

还没有评论，来说两句吧...

相关阅读