数据结构--顺序表的实现（c语⾔实现）
最近终于开始学数据结构了，开个坑记录⼀下
⾸先，顺序表是⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。在数组上完成数据的增删查改。
顺序表⼀般可以分为：
1.静态顺序表：使⽤定长数组存储。
2.动态顺序表：使⽤动态开辟的数组存储。
我实现的就是⼀个动态顺序表。
⾸先要思考这个⿁东西要能做什么，增删查改这肯定是必须的了，其他的接⼝我依次列出：
//初始化
void SeqListInit(SL *ps);
//破坏顺序表
void SeqListDestory(SL *ps);
//头插
void SeqListPushFront(SL *ps, SeqListDataType data);
//头删
void SeqListPopFront(SL *ps);
//尾插
c语言listinsert函数
void SeqListPushBack(SL *ps, SeqListDataType data);
/
/尾删
void SeqListPopBack(SL *ps);
//任意位置插⼊
void SeqListInsert(SL *ps,int pos, SeqListDataType data);
//任意位置删除
void SeqListErase(SL *ps,int pos);
//扩容
void SeqListExpan(SL *ps);
//打印
void SeqListPrint(const SL *ps);
//查
void SeqListFind(SL *ps, SeqListDataType data);
虽然看着很多，但仔细⼀想，头部插⼊删除和尾部插⼊删除都只需要调⽤任意位置插⼊删除就⾏了。
我们⾸先先新建三个⽂件：
这张图中，第⼆个⽂件⽤来提供头⽂件及所有的宏定义，函数声明，第⼀个⽂件⽤来实现函数的功能，⽽test.c则⽤来测试函数是否有问题。
⼀个顺序表结构，其中需要⼀个变量记录元素个数，需要⼀个变量记录容量，还需要⼀个数组存储数据，当个数等于容量时，我们就扩容，达到动态存储的功能。
⾸先为了后期维护，我们把顺序表中的数组⾥变量通过宏定义设置为SeqListDataType，如下：
typedef int SeqListDataType;
接着设置⼀个初始容量为
#define CAPACITY_INIT 4
这之后可以先做出⼀个顺序表结构体出来
//顺序表
typedef struct SeqList
{
SeqListDataType *array;//⽤于存放数据
int size;//元素个数
int capacity;//容量
} SL;
再接下来跟上⼀堆函数声明，这个MySeqList.h就做完了
MySeqList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#define CAPACITY_INIT 4
typedef int SeqListDataType;
//顺序表
typedef struct SeqList
{
SeqListDataType *array;//⽤于存放数据
int size;//元素个数
int capacity;//容量
} SL;
//初始化
void SeqListInit(SL *ps);
//破坏顺序表
void SeqListDestory(SL *ps);
//头插
void SeqListPushFront(SL *ps, SeqListDataType data);
//头删
void SeqListPopFront(SL *ps);
/
/尾插
void SeqListPushBack(SL *ps, SeqListDataType data);
//尾删
void SeqListPopBack(SL *ps);
//任意位置插⼊
void SeqListInsert(SL *ps,int pos, SeqListDataType data);
//任意位置删除
void SeqListErase(SL *ps,int pos);
//扩容
void SeqListExpan(SL *ps);
//打印
void SeqListPrint(const SL *ps);
//查
void SeqListFind(SL *ps, SeqListDataType data);
下⼀步要做的就是⼀⼀实现各个接⼝的功能了，我们最好实现⼀个就测试⼀下，否则到最后来测试出现bug会⾮常难。初始化
void SeqListInit(SL *ps)
{
//开辟空间
ps->array =(int*)malloc(CAPACITY_INIT *sizeof(SeqListDataType));
//开辟失败就简单点，直接埋了程序qwq
if(ps->array ==NULL)
{
printf("%s\n",strerror(errno));
exit(-1);
}
//初始化个数
ps->size =0;
// 初始化容量
ps->capacity = CAPACITY_INIT;
}
扩容
扩容要在什么时候扩呢？答的好！每次插⼊元素都要判断⼀次容量是否满了，满了就扩容，那我们先把扩容写出来。
void SeqListExpan(SL *ps)
{
//数组容量是上⼀次的两倍
ps->array =(SeqListDataType *)realloc(ps->array,2* ps->capacity *sizeof(SeqListDataType));
if(ps->array ==NULL)
{
printf("%s\n",strerror(errno));
exit(-1);
}
//别忘了这个也要扩⼤⼀倍
ps->capacity = ps->capacity *2;
}
接下来是
任意位置的增加删除
void SeqListInsert(SL *ps,int pos, SeqListDataType data) {
assert(ps !=NULL);
//位置为0就是头插，位置为ps->size就是尾插
assert((pos >=0)&&(pos <= ps->size));
//判断容量是否⾜够
if(ps->size >= ps->capacity)
{
SeqListExpan(ps);
}
int end = ps->size -1;
while(end >= pos)
{
ps->array[end +1]= ps->array[end];
end--;
}
ps->array[pos]= data;
ps->size++;
}
void SeqListErase(SL *ps,int pos)
{
assert(ps !=NULL);
assert((pos >=0)&&(pos < ps->size));
int begin = pos +1;
while(begin <= ps->size -1)
{
ps->array[begin -1]= ps->array[begin];
begin++;
}
ps->size--;
}
测试⼀下
初始化没问题！
扩容没问题！
那⽴刻写⼀个打印函数测试这个增删有没有问题(打印函数真简单)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。