2007-07-15

c实现的vector

关键字: 数据结构,vector
vector.h
c 代码
  1. #ifndef __VECTOR_H__   
  2. #define __VECTOR_H__   
  3.   
  4. /////////////////////////////////////   
  5. //   
  6. typedef struct vecElem{   
  7.     int n;   
  8. }vecElem;   
  9.   
  10. int vecElem_equal(const vecElem * plelem, const vecElem *prelem);   
  11.   
  12. void vecElem_print(const vecElem * pelem);   
  13.   
  14. /////////////////////////////////////   
  15. typedef void *vector_t;   
  16.   
  17. typedef const void *const_vector_t;   
  18.   
  19. vector_t vector_new();   
  20.   
  21. void vector_make_empty(vector_t vec);   
  22.   
  23. void vector_destroy(vector_t vec);   
  24.   
  25.   
  26. int vector_size(const_vector_t vec);   
  27.   
  28. int vector_is_empty(const_vector_t vec);   
  29.   
  30. int vector_equal(const_vector_t lvec, const_vector_t rvec);   
  31. //成功返回1，失败返回0；   
  32.   
  33. int vector_resize(vector_t vec, int n, const vecElem *val);   
  34.   
  35. int vector_reserve(vector_t vec, int n);   
  36.   
  37.   
  38. const vecElem *vector_index(const_vector_t vec, int n);   
  39.   
  40. const vecElem *vector_front(const_vector_t vec);   
  41.   
  42. const vecElem *vector_back(const_vector_t vec);   
  43.   
  44.   
  45. int vector_insert(vector_t vec, int n, const vecElem *);   
  46.   
  47. int vector_remove(vector_t vec, int n);   
  48.   
  49. int vector_pop_back(vector_t vec);   
  50.   
  51. int vector_push_back(vector_t vec, const vecElem *pelem);   
  52.   
  53.   
  54. void vector_print(const_vector_t vec);   
  55.   
  56. #endif   
vector.c --
c 代码
  1. #include "vector.h"   
  2. #include    
  3. #include    
  4. #include    
  5.   
  6. ///////////////////////////////////////////   
  7. //用户可以自己修改具体实现   
  8. int vecElem_equal(const vecElem * plelem, const vecElem *prelem)   
  9. {   
  10.     if (plelem ->n == prelem ->n)   
  11.         return 1;   
  12.     else  
  13.         return 0;   
  14. }   
  15.   
  16. void vecElem_print(const vecElem * pelem)   
  17. {   
  18.     if (pelem)   
  19.         printf("%d",pelem->n);   
  20. }   
  21.   
  22. ///////////////////////////////////////////////   
  23. #define CAPACITY 12   
  24. #define MULTIPLE 2   
  25.   
  26. typedef struct _vector_t{   
  27.     vecElem *data;   
  28.     int size;   
  29.     int capacity;   
  30. }_vector_t;   
  31.   
  32. vector_t vector_new()   
  33. {   
  34.     _vector_t * pv = (_vector_t *)malloc(sizeof(_vector_t));   
  35.     if (pv == NULL)   
  36.         return NULL;   
  37.            
  38.     pv->data = (vecElem *)malloc(sizeof(vecElem) * CAPACITY);   
  39.     if(pv->data == NULL)   
  40.     {   
  41.         free(pv);   
  42.         return NULL;   
  43.     }   
  44.     pv->capacity = CAPACITY;   
  45.     pv->size = 0;   
  46.   
  47.     return (vector_t)pv;   
  48.        
  49. }   
  50.   
  51. void vector_make_empty(vector_t vec)   
  52. {   
  53.     _vector_t *pv = (_vector_t *)vec;   
  54.   
  55.     if (pv->size > 0)   
  56.     {   
  57.         free(pv->data);   
  58.         pv->size = 0;   
  59.     }   
  60. }   
  61.   
  62. void vector_destroy(vector_t vec)   
  63. {   
  64.     _vector_t *pv = (_vector_t *)vec;   
  65.   
  66.     if (pv)   
  67.     {   
  68.         vector_make_empty(pv);   
  69.         free(pv);   
  70.     }   
  71. }   
  72.   
  73.   
  74. int vector_size(const_vector_t vec)   
  75. {   
  76.     const _vector_t * pv = (const _vector_t *)vec;   
  77.   
  78.     return pv -> size;   
  79. }   
  80.   
  81. int vector_is_empty(const_vector_t vec)   
  82. {   
  83.     const _vector_t *pv = (const _vector_t *)vec;   
  84.   
  85.     if (pv->size == 0)   
  86.         return 1;   
  87.     else    
  88.         return 0;   
  89. }   
  90.   
  91.   
  92. int vector_equal(const_vector_t lvec, const_vector_t rvec)   
  93. {   
  94.     const _vector_t *first = (const _vector_t *)lvec;   
  95.     const _vector_t *second = (const _vector_t *)rvec;   
  96.     int i;   
  97.     if (first->size != second->size)   
  98.         return 0;   
  99.   
  100.     if(first == second)   
  101.         return 1;   
  102.   
  103.     for(i = 0; i < first->size; i++)   
  104.         if (!vecElem_equal(first->data+i, second->data+i))   
  105.             return 0;   
  106.     return 1;   
  107. }   
  108.   
  109. //如果新的size 小于0，或者要填充的val指向NULL,那么resize出现错误，   
  110. //返回0， 其他情况，将val指向的结构拷贝到增加的单元中，但如果新的size   
  111. //小于原来的size,只将size改变就可以了，然后返回1；   
  112. int vector_resize(vector_t vec, int n, const vecElem *val)   
  113. {   
  114.     _vector_t *pv = (_vector_t *)vec;   
  115.     int i;   
  116.     int step = n - pv->size;   
  117.   
  118.     if(n < pv->size && n >= 0)   
  119.     {   
  120.         pv->size = n;   
  121.         return 1;   
  122.     }else if(n < 0)   
  123.         return 0;   
  124.   
  125.     if (!val)   
  126.         return 0;   
  127.   
  128.     if(n > pv->capacity)   
  129.         vector_reserve(pv, n * MULTIPLE);   
  130.   
  131.     for(i=0; i< step; i++)   
  132.     {   
  133.         vector_push_back(pv, val);   
  134.     }   
  135.     return 1;   
  136.   
  137. }   
  138.   
  139. int vector_reserve(vector_t vec, int n)   
  140. {   
  141.     _vector_t *pv = (_vector_t *)vec;   
  142.     vecElem *oldArray;   
  143.   
  144.     if(n < pv->size)   
  145.         return 0;   
  146.   
  147.     if(pv->capacity == 0)   
  148.         pv->data=(vecElem *)malloc(sizeof(vecElem) * n);   
  149.     else{   
  150.         oldArray = pv->data;   
  151.         pv->data =(vecElem *)malloc(sizeof(vecElem) * n);   
  152.         if(pv->data==NULL)   
  153.             return 0;   
  154.         memcpy(pv->data,oldArray,sizeof(vecElem)*(pv->capacity));   
  155.         free(oldArray);   
  156.     }   
  157.     pv->capacity=n;   
  158.        
  159.     return 1;   
  160. }   
  161.   
  162. const vecElem *vector_index(const_vector_t vec, int n)   
  163. {   
  164.     const _vector_t *pv = (const _vector_t *)vec;   
  165.   
  166.     if(n > pv->size || n<1)   
  167.         return NULL;   
  168.     else  
  169.         return pv->data+n-1;   
  170. }   
  171.   
  172.   
  173. const vecElem *vector_front(const_vector_t vec)   
  174. {   
  175.     return vector_index(vec, 1);   
  176. }   
  177.   
  178. const vecElem *vector_back(const_vector_t vec)   
  179. {   
  180.     const _vector_t *pv = (const _vector_t *)vec;   
  181.     return vector_index(vec, pv->size);   
  182. }   
  183.   
  184.   
  185. int vector_insert(vector_t vec, int n, const vecElem *newdata)   
  186. {   
  187.     _vector_t *pv = (_vector_t *)vec;   
  188.     int ret;   
  189.   
  190.     if(n > pv->size +1 || n < 1)   
  191.         return 0;   
  192.   
  193.     if(pv->size >= pv->capacity)   
  194.     {   
  195.         if(pv->capacity == 0)   
  196.             ret = vector_reserve(pv,CAPACITY);   
  197.         else  
  198.             ret = vector_reserve(pv,pv->capacity * MULTIPLE);   
  199.            
  200.         if(ret == 0)   
  201.             return 0;   
  202.     }   
  203.        
  204.   
  205.     if(n != pv->size + 1 )   
  206.         memmove(pv->data+n,pv->data+n-1,sizeof(vecElem)*(pv->size-n+1));   
  207.   
  208.     pv->data[n-1] = *newdata;   
  209.     pv->size++;   
  210.   
  211.     return 1;   
  212. }   
  213.   
  214.   
  215. int vector_remove(vector_t vec, int n)   
  216. {   
  217.     _vector_t *pv = (_vector_t *)vec;   
  218.     if(n > pv->size || n < 1)   
  219.         return 0;   
  220.        
  221.     if(n != pv->size)   
  222.         memmove(pv->data+n-1,pv->data+n,sizeof(vecElem)*(pv->size-n));   
  223.        
  224.     pv->size--;   
  225.     return 1;   
  226. }   
  227. int vector_pop_back(vector_t vec)   
  228. {   
  229.     _vector_t *pv = (_vector_t *)vec;   
  230.   
  231.     return vector_remove(pv, pv->size);   
  232.        
  233. }   
  234. int vector_push_back(vector_t vec, const vecElem *pelem)   
  235. {   
  236.     _vector_t *pv = (_vector_t *)vec;   
  237.   
  238.     return vector_insert(pv,pv->size + 1,pelem);   
  239. }   
  240.   
  241. void vector_print(const_vector_t vec)   
  242. {   
  243.     const _vector_t *pv = (const _vector_t *)vec;   
  244.     int i;   
  245.         printf("vector:\n");   
  246.         printf("size is :%d\n",pv->size);   
  247.         printf("capacity is: %d\n",pv->capacity);   
  248.     for(i =0;isize;i++)   
  249.     {   
  250.   
  251.         vecElem_print(pv->data+i);   
  252.         printf("\n");   
  253.     }   
  254. }   
评论
发表评论

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

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