C语言数据结构 - 链表(双向链表实现)

傷城~ 2023-10-10 18:43 91阅读 0赞
  1. #include <stdlib.h>
  2. typedef int bool;
  3. #define TRUE 1
  4. #define FALSE 0
  5. // 节点值类型(初始默认为int,后期可以改为需要的类型)
  6. typedef int E;
  7. // 链表节点结构体
  8. typedef struct ListNode {
  9. E ele; // 节点值
  10. struct ListNode *prev; // 前驱节点
  11. struct ListNode *next; // 后继节点
  12. } Node;
  13. // 链表结构体
  14. typedef struct List {
  15. Node *head; // 头节点
  16. Node *tail; // 尾节点
  17. int size; // 链表长度
  18. } LinkedList;
  19. /*!
  20. * 初始化链表
  21. * @return 链表指针
  22. */
  23. LinkedList *init() {
  24. // 申请内存
  25. LinkedList *list = (LinkedList *) malloc(sizeof(LinkedList));
  26. // 申请内存失败
  27. if (list == NULL) {
  28. return NULL;
  29. }
  30. // 初始化链表成员
  31. list->head = NULL;
  32. list->tail = NULL;
  33. list->size = 0;
  34. return list;
  35. }
  36. /*!
  37. * 释放链表
  38. * @param list 链表
  39. */
  40. void destroy(LinkedList* list) {
  41. Node* cur = list->head;
  42. // 释放链表各个节点的内存
  43. while(cur != NULL) {
  44. Node* tmp = cur->next;
  45. free(cur);
  46. cur = tmp;
  47. }
  48. // 释放链表结构体内存
  49. free(list);
  50. }
  51. /*!
  52. * 插入元素
  53. * @param list 链表
  54. * @param index 插入位置
  55. * @param ele 元素值
  56. * @return 操作结果
  57. */
  58. bool add(LinkedList *list, int index, E ele) {
  59. // 注意:越界位置中尾巴位置list->size可以插入
  60. if (index < 0 || index > list->size) {
  61. return FALSE;
  62. }
  63. // 申请内存,创建一个新节点
  64. Node *node = (Node *) malloc(sizeof(Node));
  65. // 申请内存失败
  66. if (node == NULL) {
  67. return FALSE;
  68. }
  69. // 初始化节点
  70. node->ele = ele;
  71. node->prev = NULL;
  72. node->next = NULL;
  73. if (list->size == 0) {
  74. // 空链表插入
  75. list->head = node;
  76. list->tail = node;
  77. } else if (index == 0) {
  78. // 头插
  79. node->next = list->head;
  80. list->head->prev = node;
  81. list->head = node;
  82. } else if (index == list->size) {
  83. // 尾插
  84. list->tail->next = node;
  85. node->prev = list->tail;
  86. list->tail = node;
  87. } else {
  88. // 中间位置插入
  89. Node *cur = list->head;
  90. for (int i = 0; i < index; i++) {
  91. cur = cur->next;
  92. }
  93. Node *prevIndexNode = cur->prev;
  94. prevIndexNode->next = node;
  95. node->prev = prevIndexNode;
  96. Node *nextIndexNode = cur;
  97. node->next = nextIndexNode;
  98. nextIndexNode->prev = node;
  99. }
  100. // 节点数+1
  101. list->size++;
  102. return TRUE;
  103. }
  104. /*!
  105. * 删除元素
  106. * @param list 链表
  107. * @param index 指定删除位置
  108. * @return 被删除的元素的地址(注意:返回值是特地开辟了一块内存来存储的,因此使用完该返回值,需要注意释放内存,避免内存泄露)
  109. */
  110. E *delete(LinkedList *list, int index) {
  111. // 越界位置不能删除
  112. if (index < 0 || index >= list->size) {
  113. return NULL;
  114. }
  115. // 指向将被删除节点
  116. Node *removeNode;
  117. if (list->size == 1) {
  118. // 单节点链表删除唯一节点
  119. removeNode = list->head;
  120. list->head = NULL;
  121. list->tail = NULL;
  122. } else if (index == 0) {
  123. // 头删
  124. removeNode = list->head;
  125. list->head = list->head->next;
  126. list->head->prev = NULL;
  127. } else if (index == list->size - 1) {
  128. // 尾删
  129. removeNode = list->tail;
  130. list->tail = list->tail->prev;
  131. list->tail->next = NULL;
  132. } else {
  133. // 中间位置删除
  134. Node *cur = list->head;
  135. for (int i = 0; i < index; i++) {
  136. cur = cur->next;
  137. }
  138. removeNode = cur;
  139. Node *prev = cur->prev;
  140. Node *next = cur->next;
  141. prev->next = next;
  142. next->prev = prev;
  143. }
  144. // 链表节点个数-1
  145. list->size--;
  146. // 申请一块内存用于存放被删除节点的值
  147. E *p = (E *) malloc(sizeof(E));
  148. *p = removeNode->ele;
  149. // 释放被删除节点的空间
  150. free(removeNode);
  151. return p;
  152. }
  153. /*!
  154. * 修改元素
  155. * @param list 链表
  156. * @param index 指定修改位置
  157. * @param ele 元素值
  158. * @return 操作结果
  159. */
  160. bool set(LinkedList *list, int index, E ele) {
  161. // 越界位置无法操作
  162. if (index < 0 || index >= list->size) {
  163. return FALSE;
  164. }
  165. // 找到index位置的节点cur
  166. Node *cur = list->head;
  167. for (int i = 0; i < index; i++) {
  168. cur = cur->next;
  169. }
  170. // 修改节点值
  171. cur->ele = ele;
  172. return TRUE;
  173. }
  174. /*!
  175. * 查找元素
  176. * @param list 链表
  177. * @param index 查找位置
  178. * @return 指定位置的元素值
  179. */
  180. E *get(LinkedList *list, int index) {
  181. // 越界位置无法操作
  182. if (index < 0 || index >= list->size) {
  183. return NULL;
  184. }
  185. // 找到index位置的节点cur
  186. Node *cur = list->head;
  187. for (int i = 0; i < index; i++) {
  188. cur = cur->next;
  189. }
  190. // 返回元素值
  191. return &cur->ele;
  192. }

发表评论

表情:
评论列表 (有 0 条评论,91人围观)

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

相关阅读