闲着无聊，实现个C的vector

albcamus

It is really a stupid idea. C没有办法对[]进行重载，光这一点就不能叫vector。倘若朋友们也无聊的话，一起看看吧。

vector.h文件：

1. typedef int ElementType;
   
2. 
   
3. #ifndef _VECTOR_H
   
4. #define _VECTOR_H
   
5. 
   
6. typedef struct vector{
   
7.         ElementType *array;
   
8.         int size;
   
9.         int resv;
   
10. } vector;
    
11. 
    
12. typedef vector *vectorp;
    
13. 
    
14. 
    
15. void Initialize(vectorp vp);
    
16. 
    
17. int IsEmpty(vectorp vp);
    
18. 
    
19. int Size(vectorp vp);
    
20. 
    
21. int Capacity(vectorp vp);
    
22. 
    
23. void Reserve(vectorp vp,int n);
    
24. 
    
25. ElementType At(vectorp vp,int i);
    
26. 
    
27. void Assign(vectorp vp,int i,ElementType elem);
    
28. 
    
29. void Swap(vectorp vp,int i,int j);
    
30. 
    
31. ElementType Front(vectorp vp);
    
32. 
    
33. ElementType Back(vectorp vp);
    
34. 
    
35. void Clear(vectorp vp);
    
36. 
    
37. void PushBack(vectorp vp,ElementType elem);
    
38. 
    
39. void PopBack(vectorp vp);
    
40. 
    
41. void Delete(vectorp vp);
    
42. 
    
43. #endif

复制代码

vector.c文件：

1. #include <stdio.h>;
   
2. #include <stdlib.h>;
   
3. #include <assert.h>;
   
4. #include <string.h>;
   
5. 
   
6. #include "vector.h"
   
7. 
   
8. 
   
9. 
   
10. void Initialize(vectorp vp)
    
11. {
    
12.         vp->;array = NULL;
    
13.         vp->;size = 0;
    
14.         vp->;resv = 0;
    
15. }
    
16. 
    
17. int IsEmpty(vectorp vp)
    
18. {
    
19.         return vp->;size == 0 ;
    
20. }
    
21. 
    
22. int Size(vectorp vp)
    
23. {
    
24.         return vp->;size;
    
25. }
    
26. 
    
27. int Capacity(vectorp vp)
    
28. {
    
29.         return vp->;resv;
    
30. }
    
31. 
    
32. void Reserve(vectorp vp,int n)
    
33. {
    
34.         if(n <= vp->;resv)
    
35.                 return;
    
36.         else
    
37.         {
    
38.                 if(vp->;resv == 0)
    
39.                         vp->;array = NULL;
    
40.                 if( (vp->;array = realloc
    
41.                         (vp->;array,sizeof(ElementType)*n) ) == NULL)
    
42.                 {
    
43.                         printf("Out of space!!\n");
    
44.                         exit(1);
    
45.                 }
    
46.                 vp->;resv = n;
    
47.         }
    
48. }
    
49. 
    
50. ElementType At(vectorp vp,int i)
    
51. {
    
52.         if((i < 0)||(i >;= vp->;size))
    
53.         {
    
54.                 printf("WARNING:At() be invoked to return an element OUT OF RANGE...\n");
    
55.                 return 0;//to avoid warning
    
56.         }
    
57. 
    
58.         return vp->;array[i];
    
59. }
    
60. 
    
61. void Assign(vectorp vp,int i,ElementType elem)
    
62. {
    
63.         if((i < 0)||(i >;= vp->;size))
    
64.         {
    
65.                 printf("WARNING:Assign() be invoked to assign an element OUT OF RANGE...\n");
    
66.                 return;
    
67.         }
    
68. 
    
69.         vp->;array[i] = elem;
    
70. }
    
71. 
    
72. void Swap(vectorp vp,int i,int j)
    
73. {
    
74.         if( (i<0)||(j<0)||(i>;=vp->;size)||(j>;=vp->;size) )
    
75.         {
    
76.                 printf("Swap() be invoked to access elements OUT OF RANGE...\n");
    
77.                 return;
    
78.         }
    
79. 
    
80.         if(i == j)
    
81.                 return;
    
82.         ElementType tmp = vp->;array[i];
    
83.         vp->;array[i] = vp->;array[j];
    
84.         vp->;array[j] = tmp;
    
85. }
    
86. 
    
87. ElementType Front(vectorp vp)
    
88. {
    
89.         assert(!IsEmpty(vp));
    
90.         return vp->;array[0];
    
91. }
    
92. 
    
93. ElementType Back(vectorp vp)
    
94. {
    
95.         assert(!IsEmpty(vp));
    
96.         return vp->;array[vp->;size - 1];
    
97. }
    
98. 
    
99. void Clear(vectorp vp)
    
100. {
     
101.         realloc(vp->;array,0);
     
102.         Initialize(vp);
     
103. }
     
104. 
     
105. void PushBack(vectorp vp,ElementType elem)
     
106. {
     
107.         if(vp->;size == vp->;resv)
     
108.                 Reserve(vp,vp->;resv + 10);
     
109. 
     
110.         vp->;array[vp->;size] = elem;
     
111.         vp->;size += 1;
     
112. }
     
113. 
     
114. void PopBack(vectorp vp)
     
115. {
     
116.         assert(!IsEmpty(vp));
     
117.         bzero( (ElementType *)(&(vp->;array[vp->;size - 1])),
     
118.                                 sizeof(ElementType) );
     
119.         vp->;size --;
     
120. 
     
121. }
     
122. 
     
123. void Delete(vectorp vp)
     
124. {
     
125.         realloc(vp->;array,0);
     
126.         Initialize(vp);
     
127.         
     
128. }
     

复制代码

main.c文件，验证一下使用有没有问题：

1. #include <stdio.h>;
   
2. #include <stdlib.h>;
   
3. #include <string.h>;
   
4. #include <assert.h>;
   
5. 
   
6. #include "vector.h"
   
7. 
   
8. int main(int argc,char** argv)
   
9. {
   
10.         int s1,s2;
    
11.         s1 = 11;
    
12.         s2 = 22;
    
13. 
    
14.         vector vc;
    
15.         Initialize(&vc);
    
16. 
    
17.         Reserve(&vc,10);
    
18.         int i ;
    
19.         for(i = 0; i < 10; i++)
    
20.                 PushBack(&vc,s1);
    
21.         for(i = 0; i < 10; i++)
    
22.         {
    
23.                 printf("vc[%d] is %d\n",i,At(&vc,i));
    
24.         }
    
25. 
    
26.         printf("\n");
    
27. 
    
28.         Assign(&vc,2,s2);
    
29.         printf("after assign vc[2]:\n");
    
30.         printf("vc[2] is %d\n",At(&vc,2));
    
31. 
    
32.         printf("\n");
    
33.         Swap(&vc,1,2);
    
34.         printf("after swap vc[1] and vc[2]:\n");
    
35.         printf("vc[2] is %d\n",At(&vc,2));
    
36. 
    
37.         printf("size of vc is %d\n",Size(&vc));
    
38.         PopBack(&vc);
    
39.         PopBack(&vc);
    
40.         printf("after popback twice,size of vc is %d\n",Size(&vc));
    
41. 
    
42. 
    
43. 
    
44.         Delete(&vc);
    
45.         return 0;
    
46. }
    

复制代码

converse

1. 
   
2. typedef struct vector{
   
3.         ElementType *array;
   
4.         int size;
   
5.         int resv;
   
6. } vector;
   
7. 
   
8. typedef vector *vectorp;
   

复制代码

直接这样就可以了:

1. 
   
2. typedef struct vector{
   
3.         ElementType *array;
   
4.         int size;
   
5.         int resv;
   
6. } vector, *vectorp;
   

复制代码

albcamus

是啊。原来我在vector.h中少写了一个分号，编译时出现下列错误：

gcc -Wall -g main.c vector.c
main.c: In function `Swap':
main.c:9: warning: `main' is usually a function
等等。。。

我担心是类型定义的问题，又担心是不是哪里用错输入法了，要不然怎么编译器老说胡话！！狂找两天，才发现少了个分号

yuxh

1、Reserve函数中realloc之后不对vp->;resv 赋值可能会内存泄漏吧？
2、Clear函数中直接Initialize，不先做个free？
3、Delete函数也是同样
4、PopBack最好把最后一个值返回出来吧？

converse

给你一个建议,这是我得血和泪得经验教训得来的:
写代码的时候,写一个函数就进行测试,不要写了一大段才来一个main函数测试,可能其中出现了问题无从查找.如果要做到写一个函数就测试一个的话,那么就要确定函数之间的依赖的关系,在依赖关系中最底层的最早测试,确认无误再测试上面调用了这个函数的函数...依此类推.

我曾经一下写了1000行左右的程序,最后出错无从查找,惨就一个字.

albcamus

原帖由 "yuxh" 发表：
1、Reserve函数中realloc之后不对vp->;resv 赋值可能会内存泄漏吧？
2、Clear函数中直接Initialize，不先做个free？
3、Delete函数也是同样
4、PopBack最好把最后一个值返回出来吧？

您真是眼光犀利！！2，3谨按所指正改过。谢谢
第一条为什么要对vp->;resv赋值呢？还请赐教
第四条试了STL的vector，也是void的，因为提供了Front和Back函数，就没有再用popback返回元素了。

yuxh

调两次Reserve就有问题
第2次vp->;array = NULL; 赋值了
还有，没看到你什么时候给vp->;resv赋值呀？它的值一直=0？

albcamus

原帖由 "yuxh" 发表：
调两次Reserve就有问题
第2次vp->;array = NULL; 赋值了
还有，没看到你什么时候给vp->;resv赋值呀？它的值一直=0？

vp->;resv竟然忘了，惶窘啊！
那个vp->;array = NULL，我是这么想的：如果resv为0,就让vp->;array = NULL,这样调用realloc时就相当于调用malloc；如果resv不为0,那就说明已经realloc过至少一次了，此时再realloc就没问题。

您看这样行吗？

yuxh

只要给vp->;resv赋值了就可以，我看了有些开源代码里就是差不多这样做的