顺序表

顺序表概念和结构

顺序表用一段连续的内存空间存储数据的结构

指针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();
}