辽宁城建设计院有限公司网站,网站转微信小程序,ps设计网站首页界面,华星建设集团网站本期我们来实现数据结构的顺序表#xff08;这个之前写过一次#xff0c;不过本期和之前可能会略有不同#xff0c;但大体相同#xff09;#xff0c;大家可以看一下我们之前完成的顺序表 (6条消息) 顺序表及其多种接口的实现_顺序表类中实现接口方法_KLZUQ的博客-CSDN博客…本期我们来实现数据结构的顺序表这个之前写过一次不过本期和之前可能会略有不同但大体相同大家可以看一下我们之前完成的顺序表 (6条消息) 顺序表及其多种接口的实现_顺序表类中实现接口方法_KLZUQ的博客-CSDN博客 目录
顺序表的结构
顺序表的初始化
顺序表的销毁
尾插
尾删
打印顺序表的元素
扩容
头插
头删
任意位置插入
任意位置删除
查找
realloc相关知识
完整代码 我们继续用工程化的写法来保证好的代码习惯 顺序表的结构
我们仍然是先写出顺序表的结构
typedef int SLDataType;
#define INIT_CAPACITY 10 //初始容量
typedef struct SeqList {SLDataType* a;int size;//有效数据个数 int capacity;//空间容量
}SL; 因为顺序表大小的原因开多了浪费开少了不够用所以我们需要定义一些变量来帮助我们对顺序表的大小进行调整
顺序表的初始化
void SLInit(SL* ps) {//初始化assert(ps);ps-a (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps-a NULL) {perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}
初始化参数我们需要传顺序表这个结构体的指针然后使用malloc开辟空间给顺序表这个空间就是我们用来存储数据的同时我们要判断是否开辟成功失败时我们用perror来返回错误信息即可开辟成功后我们将有效数据个数置0容量置为我们设置的初始容量
第一行的断言是因为我们传入的是顺序表这个结构体的指针是不可能为空的所以需要断言而顺序表里的内容是否为空是由size来进行决定的
顺序表的销毁
void SLDestory(SL* ps) {//销毁assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}
顺序表的销毁我们free的是ps-a而不是直接free掉ps然后我们将ps置为空即可
尾插
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);if (ps-size ps-capacity) {//扩容SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2*sizeof(SLDataType));if (tmp NULL) {perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}ps-a[ps-size] x;
}
尾插前我们需要对容量进行判断如果不够就需要先扩容我们这里扩容扩二倍接着把数据放入数组里即可我们的size是从0开始的也就是说size的位置是我们当前存放数据最后一个的下一个位置
尾删
void SLPopBack(SL* ps)//尾删
{assert(ps);//严格的判断//assert(ps-size0);//温柔的判断if (ps-size 0) {return;}ps-size--;
}
因为是顺序表我们使用size来控制当前数据个数所以直接size-1即可我们不需要将这里的数据置为0因为没有必要而且我们也不能释放空间因为这是数组是连续的空间当然在删除数据前我们要先判断数组是否为空这里我们有两种方法一种是用assert直接断言另一种是当作无事发生更推荐assert一些
打印顺序表的元素
有了尾插尾删我们需要对程序进行测试所以我们对顺序表的元素进行打印
void SLPrint(SL* ps) {//打印assert(ps);for (int i 0; i ps-size; i) {printf(%d-, ps-a[i]);}printf(NULL\n);
}
扩容
我们在写头插时发现插入都需要先判断是否需要扩容所以我们把扩容代码提取出来封装为一个函数方便后续使用
void SLCheckCapaicty(SL* ps)//扩容
{assert(ps);if (ps-size ps-capacity) {//扩容SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2 * sizeof(SLDataType));if (tmp NULL) {perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}
}
头插
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapaicty(ps);int end ps-size - 1;while (end0) {ps-a[end 1] ps-a[end];--end;}ps-a[0] x;ps-size;
}
头插的效率不高需要挪动后续所有元素如果有n个元素我们要插入n个元素时间复杂度就是n^2了而尾插n个数据的数据复杂度是n这是非常恐怖的比如我们要插入1w个数据那么头插就是1w*1w了而尾插是1w所以我们要避免使用头插
头删
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps-size 0);int begin 1;while (begin ps-size) {ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
如果size为0那么顺序表为空不能进行删除删除时我们只需将a[0]之后的元素向前挪动即可接着size-1同样的头删的效率也很低时间复杂度也是n^2所以我们也要少用头删
任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{assert(ps);assert(pos0 posps-size);SLCheckCapaicty(ps);int end ps-size - 1;while (endpos) {ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}
如果我们想在顺序表中间某个位置插入就可以使用该函数因为是插入所以也需要先判断是否需要扩容另外我们传入的pos是位置所以要符合顺序表元素的个数所以要断言一下下面的插入代码和头插几乎一样
任意位置删除
void SLErase(SL* ps, int pos)//任意位置删除
{assert(ps);assert(pos 0 pos ps-size);int begin pos 1;while (begin ps-size) {ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
这里的断言和任意位置插入稍有不同我们发现posps-szie而不能等于而且我们不需要检查size是否大于0因为pos会间接检查因为size不可能为负数而pos要大于等于0
查找
int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i 0; i ps-size; i) {if (ps-a[i] x) {return i;}}return -1;
}
任意位置的插入和删除一般是配合查找来使用的查找返回的是下标找不到时返回-1
realloc相关知识
最后我们在补充一点其他的只是我们的顺序表扩容时使用了realloc函数而realloc函数分配空间扩容会分为两种一种是原地扩容另一种是异地扩容原地扩容就是将当前位置的后续空间使用权也分配给我们而异地扩容则是新找了一块空间将使用权分配给我们然后把原来的空间使用权归还给操作系统当我们扩容小的时候一般是原地扩容但是当扩容次数较多时后续空间会不足就会进行异地扩容找一块更大的空间给我们异地扩容的效率是比原地扩容低很多的异地扩容不仅要找一块新的空间还要把原空间里的数据给拷贝过来再释放原空间
完整代码
最后在这里附上全部代码
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLDataType;
#define INIT_CAPACITY 10 //初始容量
typedef struct SeqList {SLDataType* a;int size;//有效数据个数 int capacity;//空间容量
}SL;void SLInit(SL* ps);//初始化
void SLDestory(SL* ps);//销毁
void SLPrint(SL* ps);//打印
void SLPushBack(SL* ps,SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPopBack(SL* ps);//尾删
void SLPopFront(SL* ps);//头删
void SLCheckCapaicty(SL* ps);//扩容
void SLInsert(SL* ps, int pos, SLDataType x);//任意位置插入
void SLErase(SL* ps, int pos);//任意位置删除
int SLFind(SL* ps, SLDataType x);//查找 #include SeqList.hvoid SLInit(SL* ps) {//初始化assert(ps);ps-a (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps-a NULL) {perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}void SLCheckCapaicty(SL* ps)//扩容
{assert(ps);if (ps-size ps-capacity) {//扩容SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2 * sizeof(SLDataType));if (tmp NULL) {perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;}
}void SLPrint(SL* ps) {//打印assert(ps);for (int i 0; i ps-size; i) {printf(%d-, ps-a[i]);}printf(NULL\n);
}void SLDestory(SL* ps) {//销毁assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapaicty(ps);ps-a[ps-size] x;
}
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapaicty(ps);int end ps-size - 1;while (end0) {ps-a[end 1] ps-a[end];--end;}ps-a[0] x;ps-size;
}
void SLPopBack(SL* ps)//尾删
{assert(ps);//严格的判断assert(ps-size0);//温柔的判断/*if (ps-size 0) {return;}*/ps-size--;
}
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps-size 0);int begin 1;while (begin ps-size) {ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i 0; i ps-size; i) {if (ps-a[i] x) {return i;}}return -1;
}void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{assert(ps);assert(pos0 posps-size);SLCheckCapaicty(ps);int end ps-size - 1;while (endpos) {ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}
void SLErase(SL* ps, int pos)//任意位置删除
{assert(ps);assert(pos 0 pos ps-size);int begin pos 1;while (begin ps-size) {ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
以上就是本期全部内容希望大家可以有所收获
如有错误还请指正
