不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 212|回复: 0

[c/c++] [C数据结构]双向链表

[复制链接]
j2cat 发表于 2018-1-6 18:46:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
DLinkList.h
  1. #ifndef _DLINKLIST_H_
  2. #define _DLINKLIST_H_

  3. typedef struct _tag_dlinklistnode TDLinkListNode;
  4. typedef void DLinkList;

  5. struct _tag_dlinklistnode { //定义双向链表结点
  6.         TDLinkListNode* next; //下一个元素
  7.         TDLinkListNode* pre;  //上一个元素
  8. };

  9. DLinkList* dlink_list_create(void);

  10. void dlink_list_free(DLinkList* list);

  11. void dlink_list_clear(DLinkList* list);

  12. int dlink_list_length(DLinkList* list);

  13. TDLinkListNode* dlink_list_get(DLinkList* list, int pos);

  14. TDLinkListNode* dlink_list_del(DLinkList* list, int pos);

  15. int dlink_list_insert(DLinkList* list, TDLinkListNode* node, int pos);

  16. TDLinkListNode* dlink_list_next(DLinkList* list);

  17. TDLinkListNode* dlink_list_pre(DLinkList* list);

  18. TDLinkListNode* dlink_list_node_get(DLinkList* list, TDLinkListNode* node);

  19. TDLinkListNode* dlink_list_node_del(DLinkList* list, TDLinkListNode* node);

  20. TDLinkListNode* dlink_list_current(DLinkList* list);

  21. TDLinkListNode* dlink_list_reset(DLinkList* list);

  22. #endif
复制代码
DLinkList.c
  1. #include "DLinkList.h"
  2. #include <malloc.h>

  3. typedef struct _tag_dlinklist { //定义双向链表
  4.         TDLinkListNode header;      //节点
  5.         TDLinkListNode* slider;     //游标 指向节点
  6.         int length;
  7. }TDLinkList;

  8. //创建双向链表
  9. DLinkList* dlink_list_create(void) {
  10.         TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));
  11.         if(NULL != ret){
  12.                 ret->header.next = NULL;
  13.                 ret->header.pre = NULL;
  14.                 ret->slider = NULL;
  15.                 ret->length = 0;
  16.         }
  17.         return ret;
  18. }

  19. void dlink_list_free(DLinkList* list) {
  20.         free(list);
  21. }

  22. void dlink_list_clear(DLinkList* list) {
  23.         TDLinkList *dlist = (TDLinkList*)list;
  24.         if (NULL != dlist) {
  25.                 dlist->length = 0;
  26.                 dlist->header.next = NULL;
  27.                 dlist->header.pre = NULL;
  28.                 dlist->slider = NULL;
  29.         }
  30. }

  31. int dlink_list_length(DLinkList* list) {
  32.         TDLinkList *dlist = (TDLinkList*)list;
  33.         int ret = -1;
  34.         if (NULL != dlist) {
  35.                 ret = dlist->length;
  36.         }
  37.         return ret;
  38. }

  39. TDLinkListNode* dlink_list_get(DLinkList* list, int pos) {
  40.         TDLinkList* dlist = (TDLinkList*)list;
  41.         TDLinkListNode* ret = NULL;
  42.         if ((NULL != dlist) && (0 <= pos) && (pos < dlist->length)) {  //检查合法性, 链表地址不为空, pos位置是否非法
  43.                 TDLinkListNode* current = (TDLinkListNode*)dlist;          //current指向链表的header
  44.                 for (int i = 0; i < pos; i++) {
  45.                         current = current->next;
  46.                 }
  47.                 ret = current->next;
  48.         }

  49.         return ret;
  50. }

  51. TDLinkListNode* dlink_list_del(DLinkList* list, int pos) {
  52.         TDLinkList* dlist = (TDLinkList*)list;
  53.         TDLinkListNode* ret = NULL;
  54.         if ((NULL != dlist) && (0 <= pos) && (pos < dlist->length)) { //检查合法性, 链表地址不为空, pos位置是否非法
  55.                 TDLinkListNode* current = (TDLinkListNode*)dlist;
  56.                 TDLinkListNode* next = NULL;
  57.                 for (int i = 0; i < pos; i++) {
  58.                         current = current->next;
  59.                 }
  60.                 ret = current->next; //ret指向要删除的节点
  61.                 next = ret->next;    //next指向要删除节点的下一个节点
  62.                 current->next = next; //从链表中剔除ret节点
  63.                 if (NULL != next) {  //检查该位置是否为NULL 链表末尾
  64.                         next->pre = current; //该节点的pre指向ret的上一个结点
  65.                         if (current == (TDLinkListNode*)dlist) { //判断当前节点是否是头节点
  66.                                 next->pre = NULL; //current为头节点则next为首节点,首节点的pre重置为空
  67.                         }
  68.                 }
  69.                 if (dlist->slider == ret) { //判断链表头中游标是否指向删除的节点
  70.                         dlist->slider = next;   //指向下一个元素
  71.                         if (NULL == dlist->slider && NULL != ret->pre) { //再判断游标指向是否为空(ret为最后一个节点时),并且ret不是首节点
  72.                                 dlist->slider = ret->pre; //把前一个节点赋值给游标
  73.                         }
  74.                 }
  75.                 dlist->length--;
  76.         }

  77.         return ret;
  78. }


  79. int dlink_list_insert(DLinkList* list, TDLinkListNode* node, int pos) {
  80.         TDLinkList* dlist = (TDLinkList*)list;
  81.         int ret = (NULL != dlist) && (0 <= pos); //判断合法性
  82.         ret = ret && (NULL != node);

  83.         if (ret) {
  84.                 TDLinkListNode* current = (TDLinkListNode*)dlist; //指向头节点
  85.                 TDLinkListNode* next = NULL;

  86.                 for (int i = 0; i < pos && NULL != current->next; i++) {
  87.                         current = current->next;
  88.                 }

  89.                 next = current->next;
  90.                 current->next = node;
  91.         node->next = next;
  92.                 if (NULL != next) { //判断是否为空(如果node插在末尾 后面没有元素则next为NULL)
  93.                         next->pre = node;
  94.                 }

  95.                 node->pre = current;
  96.                 if (0 == dlist->length ) { //判断插入前是否为空链, 游标指向第一个元素
  97.                         dlist->slider = node;
  98.                 }
  99.                 if (current == (TDLinkListNode*)dlist) { //如果node插入位置是首节点 则前驱置空
  100.                         node->pre = NULL;
  101.                 }

  102.                 dlist->length++;
  103.         }

  104.         return ret;

  105. }

  106. TDLinkListNode* dlink_list_next(DLinkList* list) {
  107.         TDLinkList* dlist = (TDLinkList*)list;
  108.         TDLinkListNode* ret = NULL;
  109.         if (NULL != dlist && NULL != dlist->slider) {
  110.                 ret = dlist->slider;
  111.                 dlist->slider = ret->next;
  112.         }
  113.         return ret;
  114. }

  115. TDLinkListNode* dlink_list_node_get(DLinkList* list, TDLinkListNode* node) {
  116.         TDLinkList* dlist = (TDLinkList*)list;
  117.         TDLinkListNode* ret = NULL;
  118.         if ((NULL != dlist) && (NULL != node)) {
  119.                 TDLinkListNode* current = (TDLinkListNode*)dlist;
  120.                 int i;
  121.                 for (i = 0; i < dlist->length; i++) {
  122.                         
  123.                         if (node == current->next) {
  124.                                 ret = current->next;
  125.                                 break;
  126.                         }
  127.                         current = current->next;
  128.                 }
  129.         }
  130.         return ret;
  131. }

  132. TDLinkListNode* dlink_list_node_del(DLinkList* list, TDLinkListNode* node) {
  133.         TDLinkList* dlist = (TDLinkList*)list;
  134.         TDLinkListNode* ret = NULL;
  135.         if ((NULL != dlist) && (NULL != node)) {
  136.                 TDLinkListNode* current = (TDLinkListNode*)dlist;
  137.                 int i;
  138.                 for (i = 0; i < dlist->length; i++) {
  139.                         
  140.                         if (node == current->next) {
  141.                                 ret = current->next;
  142.                                 break;
  143.                         }
  144.                         current = current->next;
  145.                 }

  146.                 if (NULL != ret) {
  147.                         dlink_list_del(dlist, i);
  148.                 }

  149.         }
  150.         return ret;
  151. }

  152. TDLinkListNode* dlink_list_current(DLinkList* list) {
  153.         TDLinkList* dlist = (TDLinkList*)list;
  154.         TDLinkListNode* ret = NULL;
  155.         if (NULL != dlist) {
  156.                 ret = dlist->slider;
  157.         }
  158.         return ret;
  159. }

  160. TDLinkListNode* dlink_list_reset(DLinkList* list) {
  161.         TDLinkList* dlist = (TDLinkList*)list;
  162.         TDLinkListNode* ret = NULL;
  163.         if (NULL != dlist) {
  164.                 dlist->slider = dlist->header.next;
  165.                 ret = dlist->slider;
  166.         }
  167.         return ret;
  168. }

  169. TDLinkListNode* dlink_list_pre(DLinkList* list) {
  170.         TDLinkList* dlist = (TDLinkList*)list;
  171.         TDLinkListNode* ret = NULL;
  172.         if (NULL != dlist && NULL != dlist->slider) {
  173.                 ret = dlist->slider;
  174.                 dlist->slider = ret->pre;
  175.         }
  176.         return ret;
  177. }
复制代码
main.c
  1. #include "DLinkList.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <malloc.h>

  5. typedef struct _tag_value {
  6.         TDLinkListNode header;
  7.         int v;
  8. }Value;

  9. int main(void) {
  10.         DLinkList* dlist = dlink_list_create();
  11.         if (NULL == dlist) {
  12.                 return -1;
  13.         }
  14.         Value v1;
  15.         Value v2;
  16.         Value v3;
  17.         Value v4;
  18.         Value v5;

  19.         v1.v = 1;
  20.         v2.v = 2;
  21.         v3.v = 3;
  22.         v4.v = 4;
  23.         v5.v = 5;

  24.         //dlink_list_insert(dlist, (TDLinkListNode*)&v1, dlink_list_length(dlist));
  25.         //dlink_list_insert(dlist, (TDLinkListNode*)&v2, dlink_list_length(dlist));
  26.         //dlink_list_insert(dlist, (TDLinkListNode*)&v3, dlink_list_length(dlist));
  27.         //dlink_list_insert(dlist, (TDLinkListNode*)&v4, dlink_list_length(dlist));
  28.         //dlink_list_insert(dlist, (TDLinkListNode*)&v5, dlink_list_length(dlist));

  29.         dlink_list_insert(dlist, (TDLinkListNode*)&v1, 0);
  30.         dlink_list_insert(dlist, (TDLinkListNode*)&v2, 0);
  31.         dlink_list_insert(dlist, (TDLinkListNode*)&v3, 0);
  32.         dlink_list_insert(dlist, (TDLinkListNode*)&v4, 0);
  33.         dlink_list_insert(dlist, (TDLinkListNode*)&v5, 0);

  34.         printf("dlist length: %d\n\n", dlink_list_length(dlist));
  35.         Value* pv = NULL;
  36.         for (int i = 0; i < dlink_list_length(dlist); i++) {
  37.                 pv = (Value*)dlink_list_get(dlist, i);
  38.                 printf("%d\n",pv->v);
  39.         }
  40.         printf("\n");
  41.         //int n = dlink_list_length(dlist);
  42.         //for (int i = 0; i < n; i++) {
  43.         //        pv = (Value*)dlink_list_del(dlist, dlink_list_length(dlist)-1);
  44.         //        printf("i: %d, -> %d\n", i, pv->v);
  45.         //}
  46.         while (dlink_list_length(dlist)) {
  47.                 pv = (Value*)dlink_list_current(dlist);
  48.                 printf("dlist value = %d\n", pv->v);
  49.                 dlink_list_node_del(dlist, (TDLinkListNode*)pv);       
  50.         }
  51.         printf("dlist length : %d \n", dlink_list_length(dlist));
  52.         dlink_list_free(dlist);
  53.         system("pause");
  54.         return 0;
  55. }
复制代码



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-6-21 16:42

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表