让人不顺眼的顺序表

顺序表的本质：数组

此篇实现顺序表

一、基本框架

1. 初始设置

#include 
#include 
#include 
 
typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType* a;  //存数据
	int size;       //大小
	int capacity;   //容量
}SL;

 

2. 函数实现概览

void SLInit(SL* ps);
 
void SLDestroy(SL* ps);
 
void SLPrint(SL* ps);
 
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
 
int SLFind(SL* ps, SLDataType x);   //此处返回的是下标，所以返回类型是int
 
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

二、函数实现

1. 初始化

void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

 

2. 销毁

void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}

 

3. 打印

注意检查是否为空

void SLPrint(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
		printf("ݴӡ\n");
	else
	{
		for (int i = 0; i < ps->size; i++)
		{
			printf("%d ", ps->a[i]);
		}
		printf("\n");
	}
}

 

4. 检查函数

此函数可以不包含在头文件中，因为只在SeqList.c文件中使用

void CheckCap(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newCap = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCap*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCap;
	}
}

为什么我看顺序表不顺眼，就是因为每一次插入数据都要检查容量是否足够，内存小了要扩容，而没有用上的空间就会被浪费，烦不烦？！

5. 尾插头插

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCap(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

头插前还得将后面的元素往后调，真服了~

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCap(ps);
	for (int i = ps->size ; i > 0; --i)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}

 

6. 尾删头删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

头删完之后还得将后面的元素往前调，麻烦！

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}

7. 查找

遍历就完事了

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			break;
	}
	return i;
}

8. 插入消除

与前面的函数类似

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos > 0 && pos <= ps->size);  //保证位置合法
 
	CheckCap(ps);
	for (int i = ps->size-1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos > 0 && pos < ps->size);
 
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

虽然顺序表有很多的缺点，但也不是一无是处，比如找尾的速度是比链表快的。

所以任何事情都要辩证看待呀，不要一叶障目不见泰山。

三、代码汇总

SeqList.h

#include 
#include 
#include 
 
typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
}SL;
 
void SLInit(SL* ps);
void SLDestroy(SL* ps);
 
void SLPrint(SL* ps);
 
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
 
int SLFind(SL* ps, SLDataType x);
 
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

SeqList.c

#include "SeqList.h"
 
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
 
void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}
 
void SLPrint(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
		printf("ݴӡ\n");
	else
	{
		for (int i = 0; i < ps->size; i++)
		{
			printf("%d ", ps->a[i]);
		}
		printf("\n");
	}
}
 
void CheckCap(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newCap = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCap*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCap;
	}
}
 
 
 
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCap(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
 
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCap(ps);
	for (int i = ps->size ; i > 0; --i)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}
 
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}
 
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}
 
 
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			break;
	}
	return i;
}
 
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos > 0 && pos <= ps->size);
 
	CheckCap(ps);
	for (int i = ps->size-1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->size++;
}
 
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos > 0 && pos < ps->size);
 
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}