数据结构-实现静态顺序表

实现

首先需要一个.c文件和一个.h文件，在.c文件中定义结构体与声明函数，在.h文件中实现顺序表基本操作及单元测试。

头文件实现如下：

定义一个结构体类型，其中成员变量有数据与顺序表大小。

（这里自定义类型是为了在实现中方便我们不用每次都写struct）

  1 #pragma once
  2 
  3 #include <stddef.h>
  4 #define SeqListMaxSize 100
  5 #define SeqListType char
  6 typedef struct SeqList{
  7     SeqListType data[SeqListMaxSize];
  8     size_t size;
  9 }SeqList;

我的顺序表实现了以下功能：

初始化
尾插
尾删
头插
头删
读取任意位置元素
修改任意位置元素
查找指定元素的下标
在任意位置插入元素
在任意位置删除元素

初始化

初始化顺序表不需要对顺序表中成员置0，只需要将大小置0即可。

要对指针进行空指针判断，以防非法输入。

  4 void SeqListInit(SeqList *seqlist)
  5 {
  6     //初始化顺序表
  7     if(NULL==seqlist)
  8     {
  9         return;
 10     }
 11     seqlist -> size=0;
 12 }

结果如下：

这里写图片描述

尾插尾删

尾插尾删顾名思义在顺序表尾部进行删除和插入操作。

尾插：将顺序表大小自增一，将插入的元素放入新开辟的空间。

尾删：将顺序表大小自减一，将最后一个要删除的元素丢弃。

注意：

尾插时要判断顺序表是否已经满了。尾删时要判断顺序表是否已经空了。

代码：

 void SeqListPushBack(SeqList *seqlist,SeqListType value)
 14 {
 15     //尾插
 16     if(NULL==seqlist)
 17     {
 18         return;
 19     }
 20     if(seqlist->size>=SeqListMaxSize)
 21     {
 22         return;
 23         //顺序表已经满了
 24     }
 25     ++seqlist->size;
 26     seqlist->data[seqlist->size-1]=value;
 27 }
 28 void SeqListPopBack(SeqList *seqlist)
 29 {
 30     //尾删
 31     if(NULL==seqlist)
 32     {   
 33         return;
 34     }
 35     if(seqlist->size==0)
 36     {   
 37         return;
 38         //顺序表为空
 39     }
 40     --seqlist->size;
 41 }

这里写图片描述

头插头删

头插：在顺序表头部插入元素

思路：顺序表大小自增一，将顺序表中所有已有元素依次向后挪一位，就会将下表为0的位置空出来，再将value赋给这个位置。

这里写图片描述

头删：在顺序表头部删除元素

思路：将位置2的元素移至位置1，覆盖掉第一个元素的值，以此类推，顺序表大小自减一。

注意：头插时要判断顺序表是否已经满了，头删时要判断顺序表是否已经空了。

代码：

 49 void SeqListPushFront(SeqList *seqlist,SeqListType value)
 43 {
 44     if(NULL==seqlist)
 45     {
 46         return;
 47     }
 48     if(seqlist->size>=SeqListMaxSize)
 49     {
 50         return;
 51         //顺序表已经满了
 52     }
 53     ++seqlist->size;
 54     size_t i=seqlist->size-1;
 55     for(;i>=1;i--)
 56     {
 57         seqlist->data[i]=seqlist->data[i-1];
 58     }
 59     seqlist->data[0]=value;
 60 
 61 }
 62 void SeqListPopFront(SeqList *seqlist)
 63 {
 64     if(NULL==seqlist)
 65     {
 66         return;
 67     }
 68     if(seqlist->size==0)
 69     {
 70         return;
 71         //顺序表已经空了
 72     }
 73     size_t i=0;
 74     for(;i<=seqlist->size-1;i++)
 75     {
 76         seqlist->data[i]=seqlist->data[i+1];
 77     }
 78     --seqlist->size;
 79 }

这里写图片描述

读取修改任意位置元素

读取思路：首先判断顺序表是否为空，并且判断pos的合法输入，返回下标为pos的值。这里我采用了输出型参数的写法，用一个指针来接受测试用例中的value的地址，将该下标的值保存在这个地址里，保证函数调用结束形参被释放，该指针指向不改变。不需要返回改值，而使用返回值纯粹的判断该函数是否调用成功。

返回值判断：

成功就返回该元素下标；

失败则返回0；

int SeqListGetValue(SeqList *seqlist,size_t pos,SeqListType *value)
136 {
137     if(seqlist==NULL)
138     {
139         return 0;
140     }
141     if(pos>=seqlist->size)
142     {
143         return 0;
144     }
145     *value = seqlist->data[pos];
146     return 1;
147 
148 }

这里写图片描述

修改思路：判断顺序表是否为空，判断pos的合法输入，将value直接

赋值给下标为pos。

返回值判断：

成功返回1；

失败返回0；

149 int SeqListSet(SeqList* seqlist, size_t pos, SeqListType value)
150 {
151     if(seqlist==NULL)
152     {
153         return 0;
154     }
155     if(pos>=seqlist->size)
156     {
157         return 0;
158     }
159     seqlist->data[pos]=value;
160     return 1;
161 }

这里写图片描述

查找指定元素的下标

思路：遍历顺序表找到该元素返回该元素的下标。

返回值判断：

成功返回该元素下标。

失败返回-1；（下标不可能出现-1，所以用-1表示失败）

162 size_t SeqListFind(SeqList* seqlist, SeqListType value)
163 {
164     if(seqlist==NULL)
165     {
166         return;
167     }
168     size_t i = 0;
169     for(;i<seqlist->size;i++)
170     {
171         if(seqlist->data[i]==value)
172             return i;
173     }
174     if(i>=seqlist->size)
175     {
176         return (size_t)-1;
177     }
178 }

这里写图片描述

任意位置插入删除元素

插入思路：首先顺序表大小自增一，在插入下标处之后的所有元素依次向后移一位，将value复制给空出来的下标为pos处。

144 void SeqListInsert(SeqList *seqlist,size_t pos,SeqListType value)
145 {
146     if(NULL==seqlist)
147     {
148         return;
149     }
150     if(seqlist->size>=SeqListMaxSize)
151     {
152         return;
153         //顺序表已经满了
154     }
155     if(pos<0||pos>=seqlist->size)
156     {
157         return;
158         //非法的pos输入
159     }
160     else if(pos==0)
161     {
162         SeqListPushFront(seqlist,value);
163     }
164     else
165     {
166         ++seqlist->size;
167         size_t i=seqlist->size-1;
168         for(;i>pos;i--)
169         {
170             seqlist->data[i]=seqlist->data[i-1];
171         }
172         seqlist->data[pos]=value;
173     }
174 }

删除思路：定位下标为pos的位置，将该位后的所有元素一次向前挪一位覆盖前一个元素的值，直到将最后一位空出，再将顺序表大小减一。

175 void SeqListErase(SeqList *seqlist,size_t pos)
176 {
177     if(NULL==seqlist)
178     {
179         return;
180     }
181     if(seqlist->size==0)
182     {
183         return;
184         //顺序表已经空了
185     }
186     if(pos<0||pos>=seqlist->size)
187     {
188         return;
189         //非法的pos输入
190     }
191     size_t i=pos;
192     for(;i<seqlist->size-1;i++)
193     {
194         seqlist->data[i]=seqlist->data[i+1];
195     }
196     --seqlist->size;
197 }

这里写图片描述

新增功能

删除顺序表中指定的值, 如果存在重复元素, 只删除第一个
删除顺序表中所有的指定的值,.
要实现一个时间复杂度为 O(N) 的优化版本
判定顺序表是否为空
获取顺序表元素个数
冒泡排序
冒泡排序(回调函数)
折半查找

Remove

删除顺序表中的某个元素，出现多次只删除一次。

最简单的思路是我们通过该元素只调用find函数，返回值该元素下标，在调用erase函数按下标删除。不需要我们构想新思路写新的代码，用已有的代码就能实现我们的新功能。

179 void SeqListRemove(SeqList* seqlist, SeqListType to_delete)
180 {
181     if(seqlist==NULL)
182     {
183         return;
184     }
185     if(seqlist->size==0)
186     {
187         return;
188     }
189     size_t i=0;
190     i = SeqListFind(seqlist,to_delete);
191     SeqListErase(seqlist,i);
192 }

这里写图片描述

RemoveAll

删除顺序表中重复出现的某个元素，重复出现全部删除。

时间复杂度O（n^2）：

193 void SeqListRemoveAll(SeqList* seqlist, SeqListType to_delete)
194 {
195     //O(n^2)
196     if(seqlist==NULL)
197     {
198         return;
199     }
200     if(seqlist->size==0)
201     {
202         return;
203     }
204 
205     size_t pos;
206     while(1)
207     {
208         pos=SeqListFind(seqlist,to_delete);
209         if(pos==-1)
210         {
211             break;
212         }
213         SeqListErase(seqlist,pos);
214     }
215 }

时间复杂度O（n）：

216 void SeqListRemoveAllEX(SeqList *seqlist,SeqListType to_delete)
217 {
226     size_t i=0;
227     for(;i<seqlist->size;i++)
228     {
229         if(seqlist->data[i]==to_delete)
230         {
231             SeqListErase(seqlist,i);
232             i--;
233         }
234     }
235 }

这里写图片描述

Size

返回该顺序表的个数。

236 size_t SeqListSize(SeqList *seqlist)
237 {
238     if(seqlist==NULL)
239     {
240         return;
241     }
242     size_t i=0;
243     size_t count=0;
244     for(;i<seqlist->size;i++)
245     {
246         count++;
247     }
248     return count;
249 }

其实这里直接在函数内部返回seqlist->size就可以了。

这里写图片描述

Empty

返回该顺序表是否为空。

为空，返回值为1；

不为空，返回值为0；

250 size_t SeqListEmpty(SeqList *seqlist)
251 {
252     if(seqlist==NULL)
253     {
254         return;
255     }
256     if(seqlist->size==0)
257     {
258         return 1;
259     }
260     return 0;
261 }

这里写图片描述

BubbleSort

一个普通版本的冒泡排序。

268 void SeqListBubbleSort(SeqList *seqlist)
269 {
270     if(seqlist==NULL)
271     {
272         return;
273     }
274     size_t i = 0;
275     size_t j = 0;
276     int flag = 0;
277     for(i=0;i<seqlist->size-1;i++)
278     {
279         for(j=0;j<seqlist->size-i-1;j++)
280         {
281             if(seqlist->data[j]>seqlist->data[j+1])
282             {
283                 Swap(&seqlist->data[j],&seqlist->data[j+1]);
284                 flag++;
285             }
286         }
287         if(!flag)
288         {
289             break;
290         }
291     }
292 }

这里写图片描述

BubbleSortEX

一个通用版本的冒泡排序，使用回调函数通过函数指针，达到我们想要降序或是升序排序的目标。

294 int Greater(SeqListType a,SeqListType b)
295 {
296     return a > b? 1 : 0;
297 }
298 int less(SeqListType a,SeqListType b)
299 {
300     return a < b? 1 : 0;
301 }
302 void SeqListBubbleSortEX(SeqList *seqlist,Cmp cmp)
303 {
304     if(seqlist==NULL)
305     {
306         return;
307     }
308     size_t i = 0;
309     size_t j = 0;
310     for(i=0;i<seqlist->size-1;i++)
311     {
312         for(j=0;j<seqlist->size-i-1;j++)
313         {
314             if(cmp(seqlist->data[j],seqlist->data[j+1]))
315             {
316                 Swap(&seqlist->data[j],&seqlist->data[j+1]);
317             }
318         }
319     }
320 }

这里写图片描述

BinarySearch

实现对顺序表的二分查找。

335 size_t SeqListBinarySearch(SeqList *seqlist,SeqListType value)
336 {
337     if(seqlist==NULL)
338     {
339         return;
340     }
341     size_t left=0;
342     size_t right=seqlist->size-1;
343     while(left<=right)
344     {
345         size_t mid=left+(right-left)/2;
346         if(value<seqlist->data[mid])
347         {
348             right=mid-1;
349         }
350         else if(value>seqlist->data[mid])
351         {
352             left=mid+1;
353         }
354         else
355         {
356             return mid;
357         }
358     }
359 }

这里写图片描述

注意事项

对顺序表删除时要对顺序表进行空顺序表判断。
对删除表插入时要对顺序表进行满顺序表判断。
每次都要对指针进行判空处理。
对pos进行范围检测，防止非法的pos值输入。
对表中元素进行删除时，测试对空表的删除。
尽量避免在实现函数内打印。在测试用例中可以体现返回值的判断。

原文链接：https://blog.csdn.net/mxrrr_sunshine/article/details/79518213

实现

初始化

尾插尾删

头插头删

读取修改任意位置元素

查找指定元素的下标

任意位置插入删除元素

新增功能

Remove

RemoveAll

Size

Empty

BubbleSort

BubbleSortEX

BinarySearch

注意事项

你可能也喜欢