目录
1.了解数据结构
什么是数据结构？
为什么要进行数据管理？
2.顺序表
顺序表概要解析：
顺序表的分类：
- 静态顺序表
- 动态顺序表
差别和使用优先度：
1.创建顺序表
1.1顺序表分为静态顺序表和动态顺序表
// 设定类型为一个全新名字，方便后续更改
typedef int SLDataType;
// 静态顺序表
#define N 100
typedef struct SeqList
{
SLDataType arr[N];//创建数组储存数据
int size; //有效数据的数量
}SL;
// 动态顺序表
typedef struct SeqList
{
SLDataType* arr;//动态的空间，创建指针变量
int size; //有效数据的数量
int capacity; //空间的大小容量
}SL;1.2顺序表的初始化
void SLInit(SL* ps);// 顺序表的初始化
void SLInit(SL* ps)
{
ps->arr = NULL; //将顺序表指针置为NULL
ps->size = ps->capacity = 0;//将其他数据置为0
}
// 顺序表的销毁
void SLDestroy(SL* ps)
{
if (ps->arr) //判断ps->arr是否为NULL,如果不为NULL,说明空间需要释放
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}1.3顺序表的销毁
void SLDestroy(SL* ps);// 顺序表的销毁
void SLDestroy(SL* ps)
{
if (ps->arr) //判断ps->arr是否为NULL,如果不为NULL,说明空间需要释放
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}1.4顺序表的打印
void SLPrint(SL* ps);// 顺序表的打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}1.5顺序表的扩容
void SLCheckCapacity(SL* ps);// 顺序表的扩容
void SLCheckCapacity(SL* ps)
{
// 判断容量是否够用
if (ps->capacity == ps->size)
{
//执行扩容
//检验原先的容量，如果有在原先容量*2，没有的话就先分配4。
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
// 为了防止空间申请失败返回NULL,先用临时变量tmp接收
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
//申请失败提前返回
if (tmp == NULL)
{
printf("perror realloc!");
return;
}
//申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}1.6顺序表的头插，尾插
1.6.1头插
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);//断言防止传入空指针
// 插入之前判断空间容量是否够
SLCheckCapacity(ps);
//进行头插
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=ps->arr[2]
}
ps->arr[0] = x;
ps->size++;
}
1.6.2尾插
void SLPushBack(SL* ps, SLDataType x);void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);//断言防止传入空指针
// 插入之前判断空间容量是否够
SLCheckCapacity(ps);
//进行尾插
ps->arr[ps->size++] = x;
}
1.7顺序表的头删，尾删
1.7.1头删
void SLPopFront(SL* ps);//头删
void SLPopFront(SL* ps)
{
assert(ps);//断言防止传入空指针
//防止顺序表没有数据可以删除
assert(ps->size);
//进行头删操作
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//ps->arr[size-2]=ps->arr[size-1]
}
ps->size--;
}
1.7.2尾删
void SLPopBack(SL* ps);//尾删
void SLPopBack(SL* ps)
{
assert(ps);//断言防止传入空指针
//防止顺序表没有数据可以删除
assert(ps->size);
//进行尾删操作
ps->size--;
}
1.8顺序表在指定位置之前插入，删除数据
1.8.1 插入数据
void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);//断言防止传入空指针
//判断插入的数据是否合法
if (pos >= 0 && pos <= ps->size)
{
// 插入之前判断空间容量是否够
SLCheckCapacity(ps);
//插入数据
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];//ps->arr[pos+1]=ps->arr[pos];
}
ps->arr[pos] = x;
ps->size++;
}
}
1.8.2 删除数据
void SLErase(SL* ps, int pos);//在指定位置之前删除数据
void SLErase(SL* ps, int pos)
{
assert(ps);//断言防止传入空指针
//判断删除的数据是否合法
if (pos >= 0 && pos < ps->size)
{
// 删除数据
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//ps->[size-2]=ps->arr[size-1]
}
ps->size--;
}
}
1.9顺序表数据的查找
int SLFind(SL* ps, SLDataType x); // 1.9顺序表数据的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);//断言防止传入空指针
//遍历顺序表
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;//返回下标
}
}
// 没有找到
return -1;//返回一个不存在的下标
}测试代码：
#include "SeqList.h"
void SLText01()
{
SL sl;
//初始化
SLInit(&sl);
//打印
//SLPrint(&sl);
//增删查改
//头插
//SLPushFront(&sl, 1);
//SLPushFront(&sl, 2);
//SLPushFront(&sl, 3);
//SLPushFront(&sl, 4);
//SLPrint(&sl);// 4 3 2 1
//头删
/*SLPopFront(&sl);
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);*/
//尾插
//SLPushBack(&sl, 1);
//SLPushBack(&sl, 2);
//SLPushBack(&sl, 3);
//SLPushBack(&sl, 4);
//SLPrint(&sl);// 1 2 3 4
//尾删
//SLPopBack(&sl);
//SLPopBack(&sl);
//SLPopBack(&sl);
//SLPopBack(&sl);
//SLPrint(&sl);
在指定位置之前插入数据
//SLPushFront(&sl, 1);
//SLPushFront(&sl, 2);
//SLPushFront(&sl, 3);
//SLPushFront(&sl, 4);
//SLPrint(&sl);// 4 3 2 1
//SLInsert(&sl, 4, 6);
//SLPrint(&sl);// 4 3 2 6 1
//在指定位置之前删除数据
//SLPushFront(&sl, 1);
//SLPushFront(&sl, 2);
//SLPushFront(&sl, 3);
//SLPushFront(&sl, 4);
//SLPrint(&sl);// 4 3 2 1
//SLErase(&sl, 2);
//SLPrint(&sl);// 4 3 1
// 1.9顺序表数据的查找
//SLPushFront(&sl, 1);
//SLPushFront(&sl, 2);
//SLPushFront(&sl, 3);
//SLPushFront(&sl, 4);
//printf("顺序表中有：");
//SLPrint(&sl);// 4 3 2 1
//int find = SLFind(&sl, 6);
//if (find > 0)
//{
// printf("找到了！下标是：%d\n", find);
//}
//else
//{
// printf("没有找到！\n");
//}
//销毁
SLDestroy(&sl);
}
int main()
{
SLText01();
return 0;
}
