2007-07-15

c实现的double linked list

关键字: 数据结构,list
double_list.h
c 代码
  1. #ifndef __DOUBLE_LIST_H__  
  2. #define __DOUBLE_LIST_H__   
  3. ///////////////////////////////////////////////////   
  4. //用户可以任意修改结构的定义，除了结构名称。   
  5. ///////////////////////////////////////////////////   
  6.   
  7. typedef struct dllElem{   
  8.     int n;   
  9. }dllElem;   
  10.   
  11. int dllElem_equal(const dllElem *,const dllElem*);   
  12.   
  13. ///////////////////////////////////////////////////   
  14. typedef void * dlist_t;   
  15. typedef const void *const_dlist_t;   
  16.   
  17. dlist_t dlist_new();   
  18.   
  19. int dlist_size(const_dlist_t pl);   
  20.   
  21. const dllElem *dlist_index(const_dlist_t pl,int n);   
  22.   
  23. int dlist_is_empty(const dlist_t pl);   
  24.   
  25. int dlist_insert(dlist_t pl, int n,const dllElem *element);   
  26.   
  27. int dlist_remove(dlist_t pl,int n);   
  28.   
  29. int dlist_equal(const_dlist_t first, const_dlist_t second);   
  30.   
  31. const dllElem *dlist_front(const_dlist_t pl);   
  32.   
  33. const dllElem *dlist_back(const_dlist_t pl);   
  34.   
  35. int dlist_push_back(dlist_t pdlist, const dllElem *element);   
  36.   
  37. int dlist_pop_back(dlist_t pdlist);   
  38.   
  39. void dlist_make_empty(dlist_t pl);   
  40.   
  41. void dlist_destroy(dlist_t pl);   
  42.   
  43. void dlist_print(const_dlist_t pl);  
  44.  
  45. #endif   
double_list.c
c 代码
  1. #include "double_list.h"  
  2. #include <stdlib.h>  
  3. #include <stdio.h>   
  4.   
  5. /////////////////////////////////   
  6. //实现了数据隐藏   
  7. ////////////////////////////////   
  8.   
  9. typedef struct Node{   
  10.     dllElem element;   
  11.     struct Node *prev;   
  12.     struct Node *next;   
  13. }Node;   
  14.   
  15. typedef struct _dlist_t{   
  16.     Node *head;   
  17.     Node *tail;   
  18.     int size;   
  19. }_dlist_t;   
  20. int dllElem_equal(const dllElem *lelem,const dllElem *relem)   
  21. {   
  22.     if(lelem->n == relem->n)   
  23.         return 1;   
  24.     else  
  25.         return 0;   
  26. }   
  27.   
  28. void dllElem_print(const dllElem *elem)   
  29. {   
  30.     printf("%d",elem->n);   
  31. }   
  32. ///////////////////////////////////////////////////////////////////////////////////   
  33. //以下是私有函数--static--只在文件内部可见   
  34. ///////////////////////////////////////////////////////////////////////////////////   
  35.   
  36. //这个函数看起来可能会非常晦涩，他返回的是一个Node指针，而不是   
  37. //dllElem 指针。   
  38. static Node *dlist_at_n(const_dlist_t pl,int n)   
  39. {   
  40.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  41.     Node *cursor;   
  42.     int i=0;   
  43.   
  44.     if(n > pdlist->size || n < 1)   
  45.         return 0;   
  46.     if(n <= pdlist->size/2)   
  47.     {   
  48.         cursor = pdlist->head;   
  49.         while(i++<n)   
  50.             cursor = cursor->next;   
  51.     }else  
  52.     {   
  53.         cursor = pdlist->tail;   
  54.         n = pdlist->size - n + 1;   
  55.         while(i++<n)   
  56.             cursor = cursor->prev;   
  57.     }   
  58.   
  59.     return cursor;   
  60. }   
  61.   
  62. //////////////////////////////////////////////////////////////////////////////////   
  63.   
  64. dlist_t dlist_new()   
  65. {   
  66.     _dlist_t * pdlist = (_dlist_t *)malloc(sizeof(_dlist_t));   
  67.   
  68.     pdlist -> size = 0;   
  69.     pdlist -> head = (Node *)malloc(sizeof(Node));   
  70.     if (pdlist->head==NULL)   
  71.         return NULL;   
  72.   
  73.     pdlist -> tail = (Node *)malloc(sizeof(Node));   
  74.     if(pdlist -> tail == NULL)   
  75.     {   
  76.         free(pdlist);   
  77.         return NULL;   
  78.     }   
  79.   
  80.     pdlist -> head -> prev = NULL;    
  81.     pdlist -> head -> next = pdlist -> tail;   
  82.   
  83.     pdlist -> tail -> next = NULL;   
  84.     pdlist -> tail -> prev = pdlist -> head;   
  85.   
  86.     return (dlist_t)pdlist;   
  87. }   
  88.   
  89.   
  90. int dlist_size(const_dlist_t pl)   
  91. {   
  92.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  93.     return pdlist->size;   
  94. }   
  95.   
  96.   
  97. const dllElem *dlist_index(const_dlist_t pl,int n)   
  98. {   
  99.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  100.   
  101.     Node * node = dlist_at_n(pdlist,n);   
  102.   
  103.     if(node == NULL)   
  104.         return NULL;   
  105.     else  
  106.         return &(node->element);   
  107. }   
  108.   
  109.   
  110. int dlist_is_empty(const dlist_t pl)   
  111. {   
  112.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  113.   
  114.     if(pdlist->size == 0)   
  115.         return 1;   
  116.     else  
  117.         return 0;   
  118. }   
  119.   
  120.   
  121. int dlist_insert(dlist_t pl, int n,const dllElem *element)   
  122. {   
  123.     _dlist_t *pdlist = (_dlist_t *)pl;   
  124.     Node *latter;   
  125.     Node *former;   
  126.     Node *current;   
  127.   
  128.     if(n != pdlist->size + 1)   
  129.     {   
  130.         latter = dlist_at_n(pdlist,n);   
  131.         if(latter == NULL)   
  132.             return 0;   
  133.     }else  
  134.     {   
  135.         latter = pdlist->tail;   
  136.     }   
  137.   
  138.     former = latter->prev;   
  139.     current= (Node *)malloc(sizeof(Node));   
  140.     if(current ==NULL)   
  141.         return 0;   
  142.   
  143.     current->element = *element;   
  144.     current->next=latter;   
  145.     current->prev=former;   
  146.     former->next = current;   
  147.     latter->prev = current;   
  148.     pdlist->size++;   
  149.     return 1;   
  150. }   
  151.   
  152. int dlist_remove(dlist_t pl,int n)   
  153. {   
  154.     _dlist_t *pdlist = (_dlist_t *)pl;   
  155.     Node * node = dlist_at_n(pdlist,n);   
  156.     if(node == NULL)   
  157.         return 0;   
  158.     node->prev->next=node->next;   
  159.     node->next->prev=node->prev;   
  160.   
  161.     free(node);   
  162.        
  163.     pdlist->size--;   
  164.     return 1;   
  165. }   
  166.   
  167. int dlist_equal(const_dlist_t firstpl,const_dlist_t secondpl)   
  168. {   
  169.     int i=0;   
  170.     const _dlist_t *first = (const _dlist_t *)firstpl;   
  171.     const _dlist_t *second = (const _dlist_t *)secondpl;   
  172.     Node * firstp = first->head;   
  173.     Node * secondp = second->head;   
  174.   
  175.     if(first->size != second->size)   
  176.         return 0;   
  177.   
  178.     while(i++ < first->size)   
  179.     {   
  180.         firstp = firstp->next;   
  181.         secondp = secondp->next;   
  182.         if (!dllElem_equal(&(firstp->element), &(secondp->element)))   
  183.             return 0;   
  184.     }   
  185.     return 1;   
  186. }   
  187.   
  188.   
  189. const dllElem *dlist_front(const_dlist_t pl)   
  190. {   
  191.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  192.     return dlist_index(pl,1);   
  193. }   
  194.   
  195. const dllElem *dlist_back(const_dlist_t pl)   
  196. {   
  197.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  198.     return dlist_index(pl,pdlist->size);   
  199. }   
  200.   
  201.   
  202. int dlist_push_back(dlist_t pl,const dllElem *element)   
  203. {   
  204.     _dlist_t *pdlist = (_dlist_t *)pl;   
  205.     return dlist_insert(pdlist,pdlist->size + 1,element);   
  206. }   
  207.   
  208. int dlist_pop_back(dlist_t pl)   
  209. {   
  210.     _dlist_t *pdlist = (_dlist_t *)pl;   
  211.     return dlist_remove(pdlist,pdlist->size);   
  212. }   
  213.   
  214. void dlist_make_empty(dlist_t pl)   
  215. {   
  216.     _dlist_t *pdlist = (_dlist_t *)pl;   
  217.   
  218.     Node * cursor = pdlist->head->next;   
  219.     Node * next = cursor->next;   
  220.   
  221.     while(cursor != pdlist->tail)   
  222.     {   
  223.         free(cursor);   
  224.         cursor = next;   
  225.         next = cursor->next;   
  226.     }   
  227.     pdlist->size =0;   
  228. }   
  229.   
  230. void dlist_destroy(dlist_t pl)   
  231. {   
  232.     _dlist_t *pdlist = (_dlist_t *)pl;   
  233.     dlist_make_empty(pdlist);   
  234.     free(pdlist->head);   
  235.     free(pdlist->tail);   
  236. }   
  237.   
  238. void dlist_print(const_dlist_t pl)   
  239. {   
  240.     const _dlist_t *pdlist = (const _dlist_t *)pl;   
  241.     Node * cursor = pdlist->head ->next;   
  242.   
  243.     while(cursor != pdlist->tail)   
  244.     {   
  245.         dllElem_print(&(cursor->element));   
  246.         printf("\n");   
  247.         cursor = cursor->next;   
  248.     }   
  249.   
  250. }   
评论
发表评论

您还没有登录，请登录后发表评论

xombat
搜索本博客
存档
最新评论