不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 264|回复: 0

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

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

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

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

x
DCLinkList.h
  1. #ifndef _DCLINKLIST_H_
  2. #define _DCLINKLIST_H_


  3. typedef void DCLinkList;
  4. typedef struct _tag_double_circular_linked_list_node TDCLinkListNode;

  5. struct _tag_double_circular_linked_list_node {
  6.         TDCLinkListNode* pre;
  7.         TDCLinkListNode* next;
  8. };

  9. DCLinkList* dc_linklist_create(void);
  10. void dc_linklist_free(DCLinkList* list);
  11. void dc_linklist_clear(DCLinkList* list);
  12. int dc_linklist_length(DCLinkList* list);
  13. TDCLinkListNode* dc_linklist_get(DCLinkList* list, int pos);
  14. TDCLinkListNode* dc_linklist_del(DCLinkList* list, int pos);
  15. int  dc_linklist_insert(DCLinkList* list, TDCLinkListNode* node, int pos);
  16. TDCLinkListNode*  dc_linklist_node_get(DCLinkList* list, TDCLinkListNode* node);
  17. TDCLinkListNode*  dc_linklist_node_del(DCLinkList* list, TDCLinkListNode* node);
  18. TDCLinkListNode*  dc_linklist_node_next(DCLinkList* list);
  19. TDCLinkListNode*  dc_linklist_node_pre(DCLinkList* list);
  20. TDCLinkListNode*  dc_linklist_node_current(DCLinkList* list);
  21. void dc_linklist_node_reset(DCLinkList* list);

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

  3. typedef struct _tag_double_circular_linked_list {
  4.         TDCLinkListNode header;
  5.         TDCLinkListNode* slider;
  6.         int length;
  7. }TDCLinkList;

  8. DCLinkList* dc_linklist_create(void) {
  9.         TDCLinkList* dcList = (TDCLinkList*)malloc(sizeof(TDCLinkList));
  10.         if (NULL != dcList) {
  11.                 dcList->header.next = NULL;
  12.                 dcList->header.pre = NULL;
  13.                 dcList->slider = NULL;
  14.                 dcList->length = 0;
  15.         }
  16.         return dcList;
  17. }

  18. void dc_linklist_free(DCLinkList* list) {
  19.         free(list);
  20. }
  21. void dc_linklist_clear(DCLinkList* list) {
  22.         TDCLinkList* dcList = (TDCLinkList*)list;
  23.         if (NULL != dcList) {
  24.                 dcList->header.next = NULL;
  25.                 dcList->header.pre = NULL;
  26.                 dcList->slider = NULL;
  27.                 dcList->length = 0;
  28.         }
  29. }
  30. int dc_linklist_length(DCLinkList* list) {
  31.         TDCLinkList* dcList = (TDCLinkList*)list;
  32.         int ret = -1;
  33.         if (NULL != dcList) {
  34.                 ret = dcList->length;
  35.         }
  36.         return ret;
  37. }
  38. TDCLinkListNode* dc_linklist_get(DCLinkList* list, int pos) {
  39.         TDCLinkList* dcList = (TDCLinkList*)list;
  40.         TDCLinkListNode* ret = NULL;
  41.         if (NULL != dcList && 0 <= pos) {
  42.                 TDCLinkListNode* current = (TDCLinkListNode*)dcList;
  43.                 for (int i = 0; i < pos; i++) {
  44.                         current = current->next;
  45.                 }
  46.                 ret = current->next;
  47.         }
  48.         return ret;
  49. }
  50. TDCLinkListNode* dc_linklist_del(DCLinkList* list, int pos) {
  51.         TDCLinkList* dcList = (TDCLinkList*)list;
  52.         TDCLinkListNode* ret = NULL;

  53.         if ((NULL != dcList) && (0 <= pos) && (0 < dcList->length)) {
  54.                 int i;
  55.                 TDCLinkListNode* current = (TDCLinkListNode*)dcList;
  56.                 TDCLinkListNode* next = NULL;
  57.                 for (i = 0; i < pos; i++) {
  58.                         current = current->next;
  59.                 }
  60.                
  61.                 ret = current->next;
  62.                 next = ret->next;
  63.                 if (current == (TDCLinkListNode*)dcList && 0 != dcList->length) {//当current为头结点时,last保存next的前驱结点地址(即尾结点)
  64.                         TDCLinkListNode* last = next->pre;
  65.                         last->next = next;
  66.                 }
  67.                 current->next = next;
  68.                 next->pre = ret->pre;

  69.                 dcList->length--;

  70.                 if (0 == dcList->length) {
  71.                         current->next = NULL;
  72.                         dcList->slider = NULL;
  73.                 }
  74.                 if (dcList->slider == ret) {
  75.                         dcList->slider = next;
  76.                 }
  77.                

  78.         }
  79.         return ret;
  80. }
  81. int  dc_linklist_insert(DCLinkList* list, TDCLinkListNode* node, int pos) {
  82.         TDCLinkList* dcList = (TDCLinkList*)list;
  83.         int ret = (NULL != dcList) && (NULL != node);
  84.         ret = ret && (0 <= pos);

  85.         if (ret) {
  86.                 TDCLinkListNode* current = (TDCLinkListNode*)dcList;
  87.                 TDCLinkListNode* next = NULL;
  88.                 int i;
  89.                 for (i = 0; i < pos && NULL != current->next; i++) {
  90.                         current = current->next;
  91.                 }
  92.                 next = current->next; //保存原本位置的地址;
  93.                 node->next = current->next;
  94.                 current->next = node;
  95.                
  96.                 if (0 == dcList->length) {
  97.                         node->pre = node;
  98.                         node->next = node;
  99.                         dcList->slider = node;
  100.                 }
  101.                 else {
  102.                         if (current == (TDCLinkListNode*)dcList) {
  103.                                 TDCLinkListNode* last = next->pre; //当current为头结点时,last保存next的前驱结点地址(即尾结点)
  104.                                 last->next = node;
  105.                         }
  106.                         node->pre = next->pre;
  107.                         next->pre = node;
  108.                        
  109.                 }
  110.                 dcList->length++;


  111.         }


  112.         return ret;
  113. }
  114. TDCLinkListNode*  dc_linklist_node_get(DCLinkList* list, TDCLinkListNode* node) {
  115.         TDCLinkList* dcList = (TDCLinkList*)list;
  116.         TDCLinkListNode* current = (TDCLinkListNode*)dcList;
  117.         TDCLinkListNode* ret = NULL;

  118.         for (int i = 0; i < dcList->length; i++) {
  119.                 if (current->next == node) {
  120.                         ret = current->next;
  121.                         break;
  122.                 }
  123.                 current = current->next;
  124.         }
  125.         return ret;

  126. }
  127. TDCLinkListNode*  dc_linklist_node_del(DCLinkList* list, TDCLinkListNode* node) {
  128.         TDCLinkList* dcList = (TDCLinkList*)list;
  129.         TDCLinkListNode* current = (TDCLinkListNode*)dcList;
  130.         TDCLinkListNode* ret = NULL;
  131.         int pos;
  132.         for (pos = 0; pos < dcList->length; pos++) {               
  133.                 if (current->next == node) {
  134.                         ret = current->next;
  135.                         break;
  136.                 }
  137.                 current = current->next;
  138.         }
  139.         if (NULL != ret) {
  140.                 dc_linklist_del(list, pos);
  141.         }
  142.         return ret;
  143. }
  144. TDCLinkListNode*  dc_linklist_node_next(DCLinkList* list) {
  145.         TDCLinkList* dcList = (TDCLinkList*)list;
  146.         TDCLinkListNode* next = NULL;
  147.         TDCLinkListNode* current = NULL;
  148.         if (NULL != dcList && NULL != dcList->slider) {
  149.                 current = dcList->slider;
  150.                 next = current->next;
  151.                 dcList->slider = next;
  152.         }
  153.         return next;
  154. }
  155. TDCLinkListNode*  dc_linklist_node_pre(DCLinkList* list) {
  156.         TDCLinkList* dcList = (TDCLinkList*)list;
  157.         TDCLinkListNode* pre= NULL;
  158.         TDCLinkListNode* current = NULL;
  159.         if (NULL != dcList && NULL != dcList->slider) {
  160.                 current = dcList->slider;
  161.                 pre = current->pre;
  162.                 dcList->slider = pre;
  163.         }
  164.         return pre;
  165. }
  166. TDCLinkListNode*  dc_linklist_node_current(DCLinkList* list) {
  167.         TDCLinkList* dcList = (TDCLinkList*)list;
  168.         TDCLinkListNode* current = NULL;
  169.         if(NULL != dcList && NULL != dcList->slider)
  170.                 current = dcList->slider;

  171.         return current;
  172. }
  173. void dc_linklist_node_reset(DCLinkList* list) {
  174.         TDCLinkList* dcList = (TDCLinkList*)list;
  175.        
  176.         if(NULL != dcList)
  177.                 dcList->slider = dcList->header.next;
  178. }
复制代码


回复

使用道具 举报

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

本版积分规则

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

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

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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