编者前言
数据结构，计算机存储数据的方式。程序加载到内存中，计算机执行指令，拿数据运算，拿一丢数据和拿一段数据的成本是一样的，顺序表在物理空间上是连续的，有较好的缓存命中率，还可以快速的通过下标访问；不过需要动态扩容，在中间插入删除需要挪动数据不方便。因此有了栈，专业的在尾部插入和删除。
算法，解决问题的方法；既然是方法就有好有坏，确定好坏的方法是时间复杂度，和空间复杂度。空间复杂度，需要要额外开辟多少空间，常见的有O(N),和O（1),递归的栈空间可以循环利用，是O（N）。时间复杂度常见的有：
顺序表的初始化，销毁和打印
初始化
typedef int DataForm;
typedef struct SeqList
{
DataForm* arr;//指向动态开辟的数组，随时准备扩容
int size;
int cap;
}SL;
void SeqListInit(SL* psl)
{
assert(psl);
psl->arr = NULL;
psl->cap = 0;
psl->size = 0;
}
销毁
void SeqListDestory(SL* psl)
{
assert(psl);
if (psl->arr)
{
free(psl->arr);
psl->arr = NULL;
}
psl->cap = psl->size = 0;
}
打印
void SeqListPrint(SL* psl)
{
int i = 0;
while (i < psl->size)
{
printf("%d ", psl->arr[i]);
++i;
}
printf("\n");
}
顺序表的尾部插入，尾部删除，头部插入，头部删除
尾部插入
void SeqListPushBack(SL* psl, DataForm x)
{
assert(psl);
CheckCap(psl);
psl->arr[psl->size] = x;
psl->size++;
}
void CheckCap(SL* psl)
{
assert(psl);
if (psl->size==psl->cap)
{
int newcap = psl->cap == 0 ? 3 : 2 * psl->cap;
DataForm* p = (DataForm*)realloc(psl->arr, newcap * sizeof(DataForm));
if (p == NULL)
{
printf("Realloc Failed\n");
exit(-1);
}
else
{
psl->arr = p;
}
psl->cap = newcap;
}
}
尾部删除
void SeqListPopBack(SL* psl)
{
assert(psl);
assert(psl->size > 0); 防止一直删除
if (psl->size>0)
{
psl->size--;
}
}
头部插入
void SeqListPushFront(SL* psl, DataForm x)
{
assert(psl);
CheckCap(psl);
int i = psl->size;
while (i > 0)
{
psl->arr[i] = psl->arr[i - 1];
--i;
}
psl->arr[0] = x;
psl->size++;
}
头部删除
void SeqListPopFront(SL* psl)
{
assert(psl);
assert(psl->size > 0);
int i = 0;
while (i<psl->size-1)
{
psl->arr[i] = psl->arr[i + 1];
++i;
}
psl->size--;
}
顺序表给定坐标的插入，删除，查找
插入
void SeqListInsrt(SL* psl, size_t pos, DataForm x)
{
assert(psl);
assert(pos >= 0);
CheckCap(psl);
int i = psl->size;
for (i = psl->size; i > pos; i--)
{
psl->arr[i] = psl->arr[i - 1];
}
psl->arr[pos] = x;
psl->size++;
}
删除
void SeqListEarse(SL* psl, size_t pos)
{
assert(psl);
assert(pos >= 0);
if (pos = psl->size)
{
psl->size--;
}
else
{
for (size_t i = pos; i < psl->size - 1; i++)
{
psl->arr[i] = psl->arr[i + 1];
}
psl->size--;
}
}
查找
返回该值的下标
int SeqListFind(SL* psl, DataForm x)
{
assert(psl);
int i = 0;
for ( i = 0; i < psl->size; i++)
{
if (psl->arr[i] == x)
{
return i;
}
}
return -1;
}
栈的创建，初始化，销毁
创建
typedef int Dat;
typedef struct Stack
{
Dat* a;
int top;
int cap;
}SK;
初始化
void SKIinit(SK* ps)
{
assert(ps);
ps->a = NULL;
ps->cap = ps->top = 0;
}
销毁
void SKDty(SK* ps)
{
assert(ps);
if (ps->a)
{
free(ps->a);
}
ps->a = NULL;
ps->cap = ps->top = 0;
}
入栈，出栈
入栈
void SKPush(SK* ps, Dat x)
{
assert(ps);
if (ps->top == ps->cap)
{
int newcap = ps->cap == 0 ? 3 : 2 * ps->cap;
SK* p = (SK*)realloc(ps->a, sizeof(SK) * newcap);
if (p == NULL)
{
printf("malloc failed\n");
exit(-1);
}
ps->a = p;
ps->cap = newcap;
}
ps->a[ps->top] = x;
ps->top++;
}
出栈
void SKPop(SK* ps)
{
assert(ps);
ps->top--;
}
是否空栈，元素个数，栈顶元素
是否空栈
bool SKEmy(SK* ps)
{
assert(ps);
return ps->top == 0;
}
元素个数
int SKSize(SK* ps)
{
assert(ps);
return ps->top;
}
栈顶元素
Dat SKTop(SK* ps)
{
assert(ps);
assert(!SKEmy(ps));
return ps->a[ps->top-1];
}
编者寄语
应该没问题吧，就算有问题也没人看的出来吧…
