前言
本文重点讲述顺序表的增删查改，有喜欢的老铁留下你们的三连！！
文章目录
1.顺序表创建
1.1静态顺序表
#define N 100
typedef int SLDataType;
struct SeqList//静态顺序表，N的值可能太小不够用，可能太大浪费空间
{
SLDatatype SLDate[N];
int size;
};
对顺序表进一步改善那就是动态版本的顺序表啦！
1.2动态顺序表
typedef struct SeqList
{
SLDataType* SLData;//指向动态数组的指针
int size;//数据个数
int capacity;//容量
}SL;
2.顺序表所需的功能函数
void SLprint(SL* s);//打印顺序表
void SLCheckcapacity(SL* s);//检查容量
void SLInit(SL* s);//初始化
void SLPushBack(SL* s, SLDataType x);//尾插
void SLPopBack(SL* s);//尾删
void SLPushFront(SL* s, SLDataType x);//头插
void SLPopFront(SL* s);//头删
void SeqListInsert(SL* s, size_t pos, SLDataType x);// 顺序表在pos位置插入x
void SeqListErase(SL* s, size_t pos);// 顺序表删除pos位置的值
void SeqListDestory(SL* s);//销毁顺序表
3.功能函数的实现（重点）
3.1初始化
void SLInit(SL* s)
{
s->SLData = NULL;
s->size = 0;
s->capacity = 0;
}
3.2尾插
思路：在顺序表最后一个数据后面直接添加数据
void SLPushBack(SL* s, SLDataType x)//尾插
{
assert(s);
SLCheckcapacity(s);
s->SLData[s->size] = x;
s->size++;
}
3.3头插
思路：先将所有数据向后移一位，然后向第一位空间赋值
void SLPushFront(SL* s, SLDataType x)//头插
{
assert(s);
SLCheckcapacity(s);
int end = s->size-1;
while (end >= 0)
{
s->SLData[end + 1] = s->SLData[end];
--end;
}
s->SLData[0] = x;
s->size++;
}
3.4尾删
思路：我们可以直接减少数据个数来达到尾删
void SLPopBack(SL* s)//尾删
{
assert(s);
assert(s->size>0);//确保数据大于0
s->size--;
}
3.5头删
思路：所有数据向前移一位覆盖第一位，达到头删的目的
void SLPopFront(SL* s)
{
assert(s);
assert(s->size > 1); //确保数据大于1
for (int i = 0; i < s->size-1; i++)
{
s->SLData[i] = s->SLData[i + 1];
}
s->size--;
}
3.6在下标为pos的位置插入x
思路：将pos后面的所有数据后移
void SeqListInsert(SL* s, int pos, SLDataType x)// 顺序表在pos位置插入x,pos不能是size_t类型
{
assert(s);
assert(pos <= s->size && pos >= 0);
SLCheckcapacity(s);
int end = s->size-1;
while (end >=pos)//有符号类型和无符号类型时所有的操作数都自动转换为无符号类型
{
s->SLData[end+1]=s->SLData[end] ;
--end;
}
s->SLData[pos] = x;
s->size++;
}
3.6.1 改进头插和尾插
void SLPushFront(SL* s, SLDataType x)//头插
{
SeqListInsert(s, 0, x);
}
void SLPushBack(SL* s, SLDataType x)//尾插
{
SeqListInsert(s, s->size, x);
}
3.7删除下标为pos的数据
思路：将pos后面的所有数据前移
void SeqListErase(SL* s, size_t pos)// 顺序表删除pos位置的值
{
assert(s);
assert(pos <= s->size && pos >= 0);
for (int i = pos; i < s->size-1; i++)
{
s->SLData[i] = s->SLData[i+1];
}
s->size--;
}
3.7.1改进头删和尾删
void SLPopFront(SL* s)
{
SeqListErase(s, 0);
}
void SLPopBack(SL* s)//尾删
{
SeqListErase(s, s->size-1);
}
3.8销毁顺序表
void SeqListDestory(SL* s)
{
free(s);
s->size = 0;
s->SLData = NULL;
s->capacity = 0;
}
4.函数总汇：
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void SLInit(SL* s)
{
s->SLData = NULL;
s->size = 0;
s->capacity = 0;
}
void SLCheckcapacity(SL* s)
{
if (s->capacity == s->size)
{
int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
SLDataType* tmp = realloc(s->SLData, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
perror(tmp);
}
s->SLData = tmp;
s->capacity = newcapacity;
}
}
void SLprint(SL* s)
{
assert(s);
for (int i = 0; i < s->size; i++)
{
printf("%d ", s->SLData[i]);
}
printf("\n");
}
void SLPushBack(SL* s, SLDataType x)//尾插
{
/*assert(s);
SLCheckcapacity(s);
s->SLData[s->size] = x;
s->size++;*/
SeqListInsert(s, s->size, x);
}
void SLPushFront(SL* s, SLDataType x)//头插
{
//assert(s);
//SLCheckcapacity(s);
//int end = s->size-1;
//while (end >= 0)
//{
// s->SLData[end + 1] = s->SLData[end];
// --end;
//}
//s->SLData[0] = x;
//s->size++;
SeqListInsert(s, 0, x);
}
void SLPopBack(SL* s)//尾删
{
//assert(s);
//assert(s->size>0);//确保数据大于0
//s->size--;
SeqListErase(s, s->size-1);
}
void SLPopFront(SL* s)
{
//assert(s);
//assert(s->size > 1); //确保数据大于1
//for (int i = 0; i < s->size-1; i++)
//{
// s->SLData[i] = s->SLData[i + 1];
//}
//s->size--;
SeqListErase(s, 0);
}
void SeqListInsert(SL* s, int pos, SLDataType x)// 顺序表在pos位置插入x,pos不能是size_t类型
{
assert(s);
assert(pos <= s->size && pos >= 0);
SLCheckcapacity(s);
int end = s->size-1;
while (end >=pos)//有符号类型和无符号类型时所有的操作数都自动转换为无符号类型
{
s->SLData[end+1]=s->SLData[end] ;
--end;
}
s->SLData[pos] = x;
s->size++;
}
void SeqListErase(SL* s, size_t pos)// 顺序表删除pos位置的值
{
assert(s);
assert(pos <= s->size && pos >= 0);
for (int i = pos; i < s->size-1; i++)
{
s->SLData[i] = s->SLData[i+1];
}
s->size--;
}
int SLFind(SL* s, SLDataType x)
{
assert(s);
for (int i = 0; i < s->size; i++)
{
if (s->SLData[i] == x)
{
return i;
}
}
}
void SeqListDestory(SL* s)
{
free(s);
s->size = 0;
s->SLData = NULL;
s->capacity = 0;
}
