kx-00003-顺序表的实现

  1 #include "mySList.h"
  2 
  3 
  4 
  5 
  6 status sList_init(mySList* plist, int capacity)
  7 {
  8     if (plist == NULL)
  9     {
 10         return ERROR;
 11     }
 12     if (capacity < 1)
 13     {
 14         capacity = CAPACITY;
 15     }
 16     plist->capacity = capacity;    //< 分配初始容量
 17     plist->size = 0;
 18     int csize = sizeof(etype) * plist->capacity;
 19     plist->pbase = (etype*)malloc(csize);
 20     if (plist->pbase == NULL)
 21     {
 22         return OVERFLOW;    //< 分配空间失败
 23     }
 24     return OK;
 25 }
 26 
 27 
 28 void sList_clear(mySList* plist)
 29 {
 30     if (plist == NULL || plist->pbase == NULL)
 31     {
 32         return;
 33     }
 34     plist->size = 0;
 35 }
 36 
 37 
 38 void sList_destroy(mySList* plist)
 39 {
 40     if (plist == NULL || plist->pbase == NULL)
 41     {
 42         return;
 43     }
 44     free(plist->pbase);
 45     plist->pbase = NULL;
 46     plist->capacity = 0;
 47     plist->size = 0;
 48 }
 49 
 50 
 51 
 52 void sList_output(const mySList* plist, myOpFunType* op)
 53 {
 54     if (plist == NULL || plist->pbase == NULL)
 55     {
 56         return;
 57     }
 58     printf("pbase=%p,capacity=%d,size=%d\n", plist->pbase, plist->capacity, plist->size);
 59     printf("[");
 60     for (int i = 0; i < plist->size; ++i)
 61     {
 62         op((void*)(&plist->pbase[i]));
 63         if (i + 1 == plist->size)
 64         {
 65             break;
 66         }
 67         printf(",");
 68     }
 69     printf("]\n===================================================\n");
 70 }
 71 
 72 
 73 int sList_size(const mySList* plist)
 74 {
 75     if (plist == NULL || plist->pbase == NULL)
 76     {
 77         return -1;
 78     }
 79     return plist->size;
 80 }
 81 
 82 
 83 int sList_capacity(const mySList* plist)
 84 {
 85     if (plist == NULL || plist->pbase == NULL)
 86     {
 87         return -1;
 88     }
 89     return plist->capacity;
 90 }
 91 
 92 
 93 status sList_epmty(const mySList* plist)
 94 {
 95     if (plist == NULL || plist->pbase == NULL)
 96     {
 97         return ERROR;
 98     }
 99     return (plist->size == 0) ? TRUE : FALSE;
100 }
101 
102 status sList_full(const mySList* plist)
103 {
104     if (plist == NULL || plist->pbase == NULL)
105     {
106         return ERROR;
107     }
108     return (plist->size == plist->capacity) ? TRUE : FALSE;
109 }
110 
111 
112 status sList_expand(mySList* plist, int inc)
113 {
114     if (plist == NULL || plist->pbase == NULL)
115     {
116         return ERROR;
117     }
118     int c = plist->capacity * DOUBLE;
119     int total = (plist->capacity + inc < c) ? c : (plist->capacity + inc);
120     etype* pNew = NULL;
121 
122 #if 1    // 用realloc，更方便
123     pNew = (etype*)realloc(plist->pbase, sizeof(etype) * total);
124     if (pNew == NULL)
125     {
126         return OVERFLOW;
127     }
128 #endif 
129 
130 #if 0    // 用malloc与memmove，自己实现
131     pNew = (etype*)malloc(sizeof(etype) * total);
132     if (pNew == NULL)
133     {
134         return OVERFLOW;
135     }
136 
137     /*
138         for (int i = 0; i < plist->capacity; i++)
139         {
140             pNew[i] = plist->pbase[i];
141         }// 用malloc会发出缓冲区可能溢出的警告
142     */
143     memmove(pNew, plist->pbase, sizeof(etype) * (plist->capacity));
144     free(plist->pbase);
145 #endif // 0
146 
147     plist->pbase = pNew;
148     plist->capacity = total;
149     return OK;
150 }//性能时高时低，性能低时是因为表满，需要扩容，将数据拷贝，导致的性能降低
151 
152 
153 
154 
155 // 00-按位置插入元素x,pos为下标
156 status sList_insert(mySList* plist, int index, etype x)
157 {
158     if (plist == NULL || plist->pbase == NULL)
159     {
160         return ERROR;
161     }
162     if (index < 0 || index>plist->size)// 可插入的位置取值为[0,size]任一位置
163     {
164         return ERR_PARA;        // 参数pos不符合要求
165     }
166     int ret = plist->capacity == plist->size;    //< 表满
167     if (ret && OK != sList_expand(plist, 3))
168     {
169         return OVERFLOW;
170     }// 表满且扩容失败
171 
172     for (int i = plist->size; i > index; --i)
173     {
174         plist->pbase[i] = plist->pbase[i - 1];
175     }    // i的含义是旧元素被移至新位置的范围[pos+1,size]，空出了pos位置
176     plist->pbase[index] = x;
177     ++plist->size;
178     return OK;
179 }
180 
181 
182 status sList_push_back(mySList* plist, etype x)
183 {
184     if (plist == NULL || plist->pbase == NULL)
185     {
186         return ERROR;
187     }
188     int ret = plist->capacity == plist->size;
189     if (ret && OK != sList_expand(plist, 3))
190     {
191         return OVERFLOW;
192     }
193     plist->pbase[plist->size++] = x;
194     return OK;
195 }
196 
197 
198 status sList_push_front(mySList* plist, etype x)
199 {
200     if (plist == NULL || plist->pbase == NULL)
201     {
202         return ERROR;
203     }
204     int ret = plist->capacity == plist->size;
205     if (ret && OK != sList_expand(plist, 3))
206     {
207         return OVERFLOW;
208     }
209 
210     for (int i = plist->size; i > 0; --i)
211     {
212         plist->pbase[i] = plist->pbase[i - 1];
213     }
214     plist->pbase[0] = x;
215     plist->size++;
216     return OK;
217 }
218 
219 
220 status sList_append(mySList* plist, etype pdata[], int n)
221 {
222     if (plist == NULL || plist->pbase == NULL)
223     {
224         return ERROR;
225     }
226     if (n < 1)
227     {
228         return ERR_PARA;
229     }
230     int inc = plist->size + n - plist->capacity;
231     if (inc > 0 && (OK != sList_expand(plist, inc)))
232     {
233         return OVERFLOW;
234     }
235     for (int i = 0; i < n; ++i)
236     {
237         plist->pbase[i + plist->size] = pdata[i];
238     }
239     plist->size += n;
240     return OK;
241 }
242 
243 
244 status sList_remove(mySList* plist, int index)
245 {
246     if (plist == NULL || plist->pbase == NULL)
247     {
248         return ERROR;
249     }
250     if (plist->size == 0)
251     {
252         return FALSE;
253     }// 表空，不可删除
254     if (index<0 || index>plist->size - 1)
255     {
256         return ERR_PARA;
257     }// index参数不符合要求
258     for (int i = index + 1; i < plist->size; ++i)
259     {
260         plist->pbase[i - 1] = plist->pbase[i];
261     }// i的含义是被移动元素的下标范围[pos+1,size-1]
262     plist->size--;
263     return OK;
264 }
265 
266 
267 status sList_pop_back(mySList* plist)
268 {
269     if (plist == NULL || plist->pbase == NULL)
270     {
271         return ERROR;
272     }
273     if (plist->size == 0)
274     {
275         return FALSE;
276     }// 表空，不可删除
277     plist->size--;
278     return OK;
279 }
280 
281 status sList_pop_front(mySList* plist)
282 {
283     if (plist == NULL || plist->pbase == NULL)
284     {
285         return ERROR;
286     }
287     if (plist->size == 0)
288     {
289         return FALSE;
290     }// 表空，不可删除
291     for (int i = 1; i < plist->size; ++i)
292     {
293         plist->pbase[i - 1] = plist->pbase[i];
294     }
295     plist->size--;
296     return OK;
297 }
298 
299 
300 
301 status sList_locate(const mySList* plist, etype key)
302 {
303     if (plist == NULL || plist->pbase == NULL)
304     {
305         return ERROR;
306     }
307     int pos = -1;
308     for (int i = 0; i < plist->size; ++i)
309     {
310         if (key == plist->pbase[i])
311         {
312             pos = i;
313             break;
314         }
315     }
316     return pos;
317 #if 0    // while循环实现
318     int pos = plist->size - 1;
319     while (pos > -1 && plist->pbase[pos] != key)
320     {
321         --pos;
322     }
323     return pos;
324 #endif // 0
325 }// 返回值为key所在下标，可能范围为[-1,size-1]，-1表示找不到
326 
327 
328 
329 status sList_find(const mySList* plist, etype key)
330 {
331     if (plist == NULL || plist->pbase == NULL)
332     {
333         return ERROR;
334     }
335 
336 #if 0    // 方法一：
337     int pos = plist->size - 1;
338     while (pos > -1 && plist->pbase[pos] != key)
339     {
340         --pos;
341     }
342     return (pos > -1 ? TRUE : FALSE);
343 #endif 
344 
345     // 方法二：
346     return (sList_locate(plist, key) > -1) ? TRUE : FALSE;
347 }// 返回值为-1，0，1，即ERROR,TRUE,FALSE

显示结果如下：