C语言实现vector结构
1. 使用说明
本例vector结构以单链表方式实现,结合了stack与queue结构:pop_front+push_front使用方式为stack;pop_front+push_back使用方式是queue。
首尾插入和顶部弹出是运行效率最高的,此外还实现了任意位置的插入、移除和访问功能。
带有返回值的函数:返回值如果是void*类型,则NULL代表执行失败;如果是int类型,则0为成功,-1为失败。
2. 代码实现
vector_c.h
1 #ifndef __VECTOR_C_H 2 #define __VECTOR_C_H 3 4 typedef 5 struct unidirectional_node 6 { 7 void* p_data; 8 struct unidirectional_node* p_next; 9 }STRUCT_UD_NODE, 10 * P_STRUCT_UD_NODE; 11 12 typedef 13 struct vector_c 14 { 15 unsigned int count; 16 P_STRUCT_UD_NODE p_first; 17 P_STRUCT_UD_NODE p_last; 18 }STRUCT_VECTOR_C, 19 * P_STRUCT_VECTOR_C; 20 21 P_STRUCT_VECTOR_C 22 f_vector_construct(void); 23 24 void 25 f_vector_push_back(P_STRUCT_VECTOR_C const p_vec, void* const p_data); 26 27 void 28 f_vector_push_front(P_STRUCT_VECTOR_C const p_vec, void* const p_data); 29 30 void* 31 f_vector_pop_front(P_STRUCT_VECTOR_C const p_vec); 32 33 int 34 f_vector_data_insert(P_STRUCT_VECTOR_C const p_vec, void* const p_data, const unsigned int index); 35 36 void* 37 f_vector_data_remove(P_STRUCT_VECTOR_C const p_vec, const unsigned int index); 38 39 void* 40 f_vector_data_access(P_STRUCT_VECTOR_C const p_vec, const unsigned int index); 41 42 int 43 f_vector_data_index(P_STRUCT_VECTOR_C const p_vec, void* const p_data, unsigned int* const p_index); 44 45 void 46 f_vector_destroy(P_STRUCT_VECTOR_C const p_vec); 47 48 #endif // !__VECTOR_C_H
vector_c.c
1 #include "vector_c.h" 2 #include <stdlib.h> 3 4 #pragma warning(disable:6011) 5 6 P_STRUCT_VECTOR_C f_vector_construct(void) 7 { 8 P_STRUCT_VECTOR_C p_ret_vec = (P_STRUCT_VECTOR_C)malloc(sizeof(STRUCT_VECTOR_C)); 9 p_ret_vec->count = 0; 10 p_ret_vec->p_first = NULL; 11 p_ret_vec->p_last = NULL; 12 return p_ret_vec; 13 } 14 15 void innf_add_first_node(P_STRUCT_VECTOR_C const p_vec, void* const p_data) 16 { 17 p_vec->p_first = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 18 p_vec->p_first->p_data = p_data; 19 p_vec->p_first->p_next = NULL; 20 p_vec->p_last = p_vec->p_first; 21 p_vec->count = 1; 22 } 23 24 void* innf_remove_last_node(P_STRUCT_VECTOR_C const p_vec) 25 { 26 void* p_ret_data = p_vec->p_first->p_data; 27 free(p_vec->p_first); 28 p_vec->p_first = NULL; 29 p_vec->p_last = NULL; 30 p_vec->count = 0; 31 return p_ret_data; 32 } 33 34 void f_vector_push_back(P_STRUCT_VECTOR_C const p_vec, void* const p_data) 35 { 36 switch (p_vec->count) 37 { 38 case 0: 39 innf_add_first_node(p_vec, p_data); 40 return; 41 } 42 P_STRUCT_UD_NODE p_node = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 43 p_node->p_data = p_data; 44 p_node->p_next = NULL; 45 p_vec->p_last->p_next = p_node; 46 p_vec->p_last = p_node; 47 p_vec->count++; 48 } 49 50 void f_vector_push_front(P_STRUCT_VECTOR_C const p_vec, void* const p_data) 51 { 52 switch (p_vec->count) { 53 case 0: 54 innf_add_first_node(p_vec, p_data); 55 return; 56 } 57 P_STRUCT_UD_NODE p_node = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 58 p_node->p_data = p_data; 59 p_node->p_next = p_vec->p_first; 60 p_vec->p_first = p_node; 61 p_vec->count++; 62 } 63 64 void* f_vector_pop_front(P_STRUCT_VECTOR_C const p_vec) 65 { 66 switch (p_vec->count) { 67 case 0: 68 return NULL; 69 case 1: 70 return innf_remove_last_node(p_vec); 71 } 72 void* p_ret_data = p_vec->p_first->p_data; 73 P_STRUCT_UD_NODE p_node = p_vec->p_first->p_next; 74 free(p_vec->p_first); 75 p_vec->p_first = p_node; 76 p_vec->count--; 77 return p_ret_data; 78 } 79 80 int f_vector_data_insert(P_STRUCT_VECTOR_C const p_vec, void* const p_data, const unsigned int index) 81 { 82 switch (index) { 83 case 0: 84 f_vector_push_front(p_vec, p_data); 85 return 0; 86 } 87 if (index == p_vec->count) { 88 f_vector_push_back(p_vec, p_data); 89 return 0; 90 } 91 else if (index > p_vec->count) { 92 return -1; 93 } 94 P_STRUCT_UD_NODE p_node = p_vec->p_first; 95 for (unsigned int i = 0 ; i < index - 1; i++) { 96 p_node = p_node->p_next; 97 } 98 P_STRUCT_UD_NODE p_node_next = p_node->p_next; 99 p_node->p_next = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 100 p_node->p_next->p_data = p_data; 101 p_node->p_next->p_next = p_node_next; 102 p_vec->count++; 103 return 0; 104 } 105 106 void* f_vector_data_remove(P_STRUCT_VECTOR_C const p_vec, const unsigned int index) 107 { 108 switch (p_vec->count) { 109 case 0: 110 return NULL; 111 } 112 switch (index) { 113 case 0: 114 return f_vector_pop_front(p_vec); 115 } 116 if (index >= p_vec->count) { 117 return NULL; 118 } 119 P_STRUCT_UD_NODE p_node = p_vec->p_first; 120 for (unsigned int i = 0; i < index - 1; i++) { 121 p_node = p_node->p_next; 122 } 123 P_STRUCT_UD_NODE p_node_next = p_node->p_next->p_next; 124 void* p_ret_data = p_node->p_next->p_data; 125 free(p_node->p_next); 126 p_node->p_next = p_node_next; 127 p_vec->count--; 128 return p_ret_data; 129 } 130 131 void* f_vector_data_access(P_STRUCT_VECTOR_C const p_vec, const unsigned int index) 132 { 133 switch (p_vec->count) { 134 case 0: 135 return NULL; 136 } 137 if (index >= p_vec->count) { 138 return NULL; 139 } 140 P_STRUCT_UD_NODE p_node = p_vec->p_first; 141 for (unsigned int i = 0; i < index; i++) { 142 p_node = p_node->p_next; 143 } 144 return p_node->p_data; 145 } 146 147 int f_vector_data_index(P_STRUCT_VECTOR_C const p_vec, void* const p_data, unsigned int* const p_index) 148 { 149 P_STRUCT_UD_NODE p_node = p_vec->p_first; 150 for (unsigned int i = 0; i < p_vec->count; i++) { 151 if (p_node->p_data == p_data) { 152 *p_index = i; 153 return 0; 154 } 155 } 156 return -1; 157 } 158 159 void f_vector_destroy(P_STRUCT_VECTOR_C const p_vec) 160 { 161 if (p_vec == NULL) { 162 return; 163 } 164 while (p_vec->count != 0) { 165 f_vector_pop_front(p_vec); 166 } 167 free(p_vec); 168 }
3. 代码测试
source.c
1 #include "vector_c.h" 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 #pragma warning(disable:6011) 6 7 int main(int argc, char** argv) 8 { 9 P_STRUCT_VECTOR_C p_vector = f_vector_construct(); 10 const unsigned int arr_size = 10; 11 int* arr = (int*)malloc(sizeof(int) * arr_size); 12 printf("arr: "); 13 for (unsigned int i = 0; i < arr_size; i++) { 14 *(arr + i) = i * 2; 15 printf("%d ", *(arr + i)); 16 } 17 printf("\nvector push back all\n"); 18 for (unsigned int i = 0; i < arr_size; i++) { 19 f_vector_push_back(p_vector, arr + i); 20 } 21 printf("access vector data\n"); 22 for (unsigned int i = 0; i < p_vector->count; i++) { 23 printf("%d ", *(int*)f_vector_data_access(p_vector, i)); 24 } 25 printf("\nvector push front all\n"); 26 for (unsigned int i = 0; i < arr_size; i++) { 27 f_vector_push_front(p_vector, arr + i); 28 } 29 for (unsigned int i = 0; i < p_vector->count; i++) { 30 printf("%d ", *(int*)f_vector_data_access(p_vector, i)); 31 } 32 printf("\ninsert to half\n"); 33 f_vector_data_insert(p_vector, &p_vector->count, p_vector->count / 2); 34 for (unsigned int i = 0; i < p_vector->count; i++) { 35 printf("%d ", *(int*)f_vector_data_access(p_vector, i)); 36 } 37 printf("\nremove half: %d\n", *(int*)f_vector_data_remove(p_vector, p_vector->count / 2)); 38 for (unsigned int i = 0; i < p_vector->count; i++) { 39 printf("%d ", *(int*)f_vector_data_access(p_vector, i)); 40 } 41 printf("\nvector pop front all\n"); 42 while (p_vector->count != 0) { 43 printf("%d ", *(int*)f_vector_pop_front(p_vector)); 44 } 45 printf("\n"); 46 f_vector_destroy(p_vector); 47 free(arr); 48 return 0; 49 }
运行结果:
arr: 0 2 4 6 8 10 12 14 16 18
vector push back all
access vector data
0 2 4 6 8 10 12 14 16 18
vector push front all
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
insert to half
18 16 14 12 10 8 6 4 2 0 21 0 2 4 6 8 10 12 14 16 18
remove half: 20
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
vector pop front all
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
原文地址:http://www.cnblogs.com/eternalmoonbeam/p/16815954.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性