顺序表概念和结构
顺序表用一段连续的内存空间存储数据的结构
指针dys指向动态开辟的空间, capacity记录容量, size记录数据个数
顺序表的实现
SeqList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* dys;
int capacity; // 容量
int size; // 数据个数
}SL;
// 初始化
void SLInit(SL* ps);
// 销毁
void SLDestroy(SL* ps);
// 打印
void SLPrint(SL* ps);
// 尾插
void SLPushBack(SL* ps, SLDataType data);
// 尾删
void SLPopBack(SL* ps);
// 头插
void SLPushFront(SL* ps, SLDataType data);
// 头删
void SLPopFront(SL* ps);
// 查找
int SLFind(SL* ps, SLDataType x);
// pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// pos位置删除数据
void SLErase(SL* ps, int pos);
SeqList.c
#include "SeqList.h"
// 初始化
void SLInit(SL* ps)
{
assert(ps);
SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * 5);
if (NULL == tmp)
{
perror("SLInit::malloc");
return;
}
ps->dys = tmp;
ps->capacity = 5;
ps->size = 0;
}
// 销毁
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->dys);
ps->dys = NULL;
ps->capacity = 0;
ps->size = 0;
}
// 打印
void SLPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->dys[i]);
}
printf("\n");
}
// 检查容量
void CheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->dys, sizeof(SLDataType) * ps->capacity * 2);
if (NULL == tmp)
{
perror("CheckCapacity::realloc");
return;
}
ps->dys = tmp;
ps->capacity *= 2;
}
}
// 尾插
void SLPushBack(SL* ps, SLDataType data)
{
assert(ps);
CheckCapacity(ps);
ps->dys[ps->size] = data;
ps->size++;
}
// 尾删
void SLPopBack(SL* ps)
{
assert(ps);
// 如果数据个数为0,不能再删除
assert(ps->size);
ps->size--;
}
// 头插
void SLPushFront(SL* ps, SLDataType data)
{
assert(ps);
CheckCapacity(ps);
int sz = ps->size;
while (sz)
{
ps->dys[sz] = ps->dys[sz - 1];
sz--;
}
ps->dys[0] = data;
ps->size++;
}
// 头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
int begin = 1;
while (begin < ps->size)
{
ps->dys[begin - 1] = ps->dys[begin];
begin++;
}
ps->size--;
}
// 查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->dys[i] == x)
{
return i;
}
}
return -1;
}
// pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType data)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->dys[end + 1] = ps->dys[end];
end--;
}
ps->dys[pos] = data;
ps->size++;
}
// pos位置删除数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(ps->size);
assert(pos >= 0 && pos < ps->size);
int begin = pos;
int end = ps->size - 1;
while (begin < end)
{
ps->dys[begin] = ps->dys[begin + 1];
begin++;
}
ps->size--;
}
test.c
#include "SeqList.h"
void t1()
{
// 测试初始化, 销毁
SL sl;
SLInit(&sl);
SLDestroy(&sl);
}
void t2()
{
// 测试打印，尾插，尾删
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
/*SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPushBack(&sl, 6);*/
SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
}
void t3()
{
// 测试头插, 头删
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushFront(&sl, 3);
SLPushFront(&sl, 4);
SLPushFront(&sl, 5);
SLPopFront(&sl);
SLPrint(&sl);
}
void t4()
{
// 测试查找，pos插入,删除
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
/*SLInsert(&sl, 0, 6);
SLInsert(&sl, 6, 7);
SLInsert(&sl, SLFind(&sl,3), 8);
SLPrint(&sl);*/
SLErase(&sl, SLFind(&sl, 3));
SLPrint(&sl);
}
int main()
{
//t1();
//t2();
//t3();
t4();
}