基于顺序表的通讯录实现——顺序表功能实现
经过上一篇文章我们对顺序表有了一个初步的认识，下面我们将通过C语言实现顺序表的功能，包括： 增加数据 删除数据 查找数据 修改数据
可以把顺序表看作一种特殊的数组，我们下面将要进行的操作是基于
数组 数组操作 动态内存管理等基本功能实现的
1 初始化与销毁
这里我们用“ SLDataType”来代替传统的int char等关键字，这样以后，就可以避免在修改变量类型的时候，进入"地狱模式"。
1.1 初始化
void SLInit(SL* ps) { assert(ps);//断言检测是否为空指针 ps->a = NULL;//初始化 ps->size = ps->capacity = 0;//初始化 }
注意这里我们使用的是“传址操作”，这样可以在原有基础上修改数据信息。
1.2 销毁
void SLDestroy(SL* ps) { assert(ps);//断言检测是否为空指针 free(ps->a);//释放顺序表数据空间 ps->size = ps->capacity = 0;//销毁归零 ps->a = NULL;//避免“野指针” }
注意这里我们使用的是“传址操作”，这样可以在原有基础上修改数据信息。
初始化和销毁的操作比较简单，不在做详细阐释。观察代码即可。
2 头部插入与删除
2.1 头部插入
void SLPushFront(SL* ps, SLDataType x) { assert(ps);//断言检测是否为空指针 //判断空间是否足够,不够则扩容 SLCheckCapacity(ps); //空间足够，历史数据后移一位 for (size_t i = ps->size; i > 0; i--){ ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; ps->size++; }
这里我们插入的时候需要考虑空间是否足够
于是我们单独分装一个函数进行容量判断
2.1.1检查容量
void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity){ //三目操作符，为零设为 4，反之为原来空间的2倍 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //开辟空间 SLDataType* tmp = (SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType)); //检查开辟是否成功 if (tmp == NULL){ perror("realloc fail!"); return; } ps->a = tmp;//转移新空间 ps->capacity = newcapacity;//设置新容量 } }
我们一行一行的解读
1 首先判断原顺序表是否为空，如果为空则设置为四个容量，反之为原来二倍
倍数原则上可以设置为任意大小，这里之所以设置为二倍，是因为这样利用率最高
2 然后开辟空间
我们重温一下realloc函数
2.1.2 插入数据
头部插入只需在检查容量之后，依次移动顺序表数据即可，再将数据插入到头部即可，类似数组操作。
注意“size”代表新的空间大小，而不是需要增加的空间大小
开辟完空间即可进行对顺序表的扩容
插入完成之后不要忘记将 size 加 1
2.2 头部删除
void SLPopFront(SL* ps) { assert(ps);//断言检测是否为空指针 assert(!SLIsEmpty(ps));//断言检测指针指向是否为空数据。 for (int i = 0; i < ps->size - 1 ; i++) { ps->a[i] = ps->a[i + 1]; // a[size-2]=a[size-1] （模拟最后一次操作） } ps->size--; }
头部删除非常简单，将顺序表中的数据从第二个依次向前覆盖即可。
2.2.1 检测数据是否为空
bool SLIsEmpty(SL* ps) { assert(ps); //这样子是不对的，这里只能判断空间是否足够 //return ps->size == ps->capacity; return ps->size == 0; }
使用断言即可，切记不要用“ps->size == ps->capacity”这样只能判断空间是否足够
3 尾部插入与删除
尾部操作相对于头部更加简单
3.1 尾部插入
void SLPushBack(SL* ps, SLDataType x) { assert(ps);//断言检测是否为空指针 SLCheckCapacity(ps);//判断空间是否足够,不够则扩容 ps->a[ps->size++] = x; }
检查空间之后，进行赋值即可。
3.2 尾部删除
void SLPopBack(SL* ps) { assert(ps);//断言检测是否为空指针 assert(!SLIsEmpty(ps));//断言检测指向是否为空数据。 ps->size--; }
在断言并检测数据之后，将size减1即可，这里不需要将删除的数据进行处理，避免出现数据类型的不符合。
4 指定位置插入与删除
指定位置的插入与删除需要一步“查找”目标数据操作，才可以进行精准操作。
当然也可以不进行“操作”，直接对位置进行修改。
4.1 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps);//断言检测是否为空指针 SLCheckCapacity(ps);//判断空间是否足够,不够则扩容 if (pos >= 0 && pos < ps->size)//防止越界操作 { for (int i = ps->size; i > pos; i--) { ps->a[i] = ps->a[i - 1];//a[pos+1]=a[pos] } ps->a[pos] = x; ps->size++; } else assert(pos);//越界进行停止 }
pos是要修改的位置，再检测容量和检测pos是在合理范围内之后，即可进行移动插入操作。
如果要精准插入到一个数据之前则需要对pos进行操作。
4.1.1 查找数据
pos = SLFind(SL, 5)//举例 “5” //函数内部 int SLFind(SL* ps, SLDataType x) { assert(ps);//断言检测是否为空指针 for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) return i;//找到返回偏移量 i else continue; } return -1;//没找到 }
这样便可以进行准确插入。
4.2 指定位置删除
void SLErase(SL*ps,int pos) { assert(ps);//断言检测是否为空指针 if (pos >= 0 && pos < ps->size) { for (int i = pos; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; //a[size-2]=a[size-1]（模拟最后一次操作） } ps->size--; } else assert(pos); }
删除较为简单，对pos位置进行覆盖操作即可。注意size减1。
5 打印顺序表
打印操作十分简单，与打印数组类似。
5.1 打印顺序表
void SLPrint(SL* ps) { assert(ps);//断言检测是否为空指针 int i = 0; //依次打印数据即可 for (i = 0; i < ps->size; i++) { printf("%2d", ps->a[i]); } printf("\n"); }
由于我们这里展示的是最简单的顺序表。所以打印十分简单。
6 结束语
顺序表的功能我们已经实现，我们使用的是最简单的顺序表，所以整个过程看起来没有困难。在下一篇文章中我们将进行通讯录的实现。
在通讯录里，顺序表的类型不在是简单的" int ",而是结构体类型。
下面给出通讯录的基本功能供大家参考预习。
