首先记录一下线性表的概念：
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串。
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
2. 动态顺序表：使用动态开辟的数组存储。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?基本操作及其实现：
typedef int SLDataType; // 顺序表的动态存储
typedef struct SeqList
{
? SLDataType* array; // 指向动态开辟的数组
? size_t size ; // 有效数据个数
? size_t capicity ; // 容量空间的大小
}SeqList;//1. 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 对顺序表进行初始化
void SeqListInit(SeqList* ps, int initCapacity)
{
assert(ps);
initCapacity = initCapacity <= 0 ? 3 : initCapacity;
ps->array = (int*)malloc(initCapacity*sizeof(DataType));
if (NULL == ps->array)
{
assert(0);
return;
}
ps->capacity = initCapacity;
ps->size = 0;
}// 2.检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
void CheckCapacity(SeqList* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
// 1. 计算新空间的大小
int newCapacity = ps->capacity * 2;
// 2. 扩容
int* temp = (int*)malloc(sizeof(DataType)*newCapacity);
if (NULL == temp)
{
assert(0);
return;
}
memcpy(temp, ps->array, ps->size*sizeof(DataType));
free(ps->array);
ps->array = temp;
ps->capacity = newCapacity;
//或用realloc函数
/*
ps->array = (int*)realloc(ps->array, sizeof(DataType)*newCapacity);
if (NULL == ps->array)
{
assert(0);
return;
}
ps->capacity = newCapacity;
*/
}
}// 3.顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
void SeqListPushBack(SeqList* ps, DataType data)
{
assert(ps);
// 0. 必须要保证顺序表中有足够的空间才可以插入，否则就需要扩容 （第二个函数）
CheckCapacity(ps);
// 1. 将data插入到最后一个元素的下一个位置---size的位置
ps->array[ps->size] = data;
ps->size++;
}// 4.顺序表尾删
void SeqListPopBack(SeqList* psl);
void SeqListPopBack(SeqList* ps)
{
if (SeqListEmpty(ps))
{
return;
}
ps->size--;
}// 5.顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
void SeqListPushFront(SeqList* ps, DataType data)
{
assert(ps);
// 0. 检测空间是否足够 （第二个函数）
CheckCapacity(ps);
// 1. 将顺序表中所有的元素整体往后搬移一个位置(注意：从后往前来搬移)
for (int pos = ps->size - 1; pos >= 0; --pos)
{
ps->array[pos+1] = ps->array[pos];
}
// 2. 将data插入到顺序表的0号位置
ps->array[0] = data;
// 3. 有效元素个数增加一个
ps->size++;
}// 6.顺序表头删
void SeqListPopFront(SeqList* psl);
void SeqListPopFront(SeqList* ps)
{
if (SeqListEmpty(ps))
{
return;
}
for (int pos = 1; pos < ps->size; pos++)
{
ps->array[pos-1] = ps->array[pos];
}
ps->size--;
}// 7.顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
int SeqListFind(SeqList* ps, DataType data)
{
assert(ps);
for (int i = 0; i < ps->size; ++i)
{
if (ps->array[i] == data)
return i;
}
return -1;
}// 8.顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
void SeqListInsert(SeqList* ps, int pos, DataType data)
{
assert(ps);
if (pos < 0 || pos > ps->size)
{
printf("pos位置非法!!!");
return;
}
CheckCapacity(ps);
for (int i = ps->size - 1; i >= pos; i--)
{
ps->array[i+1] = ps->array[i];
}
ps->array[pos] = data;
ps->size++;
}//9. 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
void SeqListErase(SeqList* ps, int pos)
{
assert(ps);
if (pos < 0 || pos >= ps->size)
{
printf("pos位置非法!!!");
return;
}
for (int i = pos + 1; i < ps->size; i++)
{
ps->array[i-1] = ps->array[i];
}
ps->size--;
}// 10.顺序表销毁
void SeqListDestory(SeqList* psl);
void SeqListDestory(SeqList* ps)
{
assert(ps);
if (ps->array)
{
free(ps->array);
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
}// 11.顺序表打印
void SeqListPrint(SeqList* psl);
void PrintSeqList(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->array[i]);
}
printf("\n");
}// 12.检测顺序表是否为空
int SeqListEmpty(SeqList* ps)
int SeqListEmpty(SeqList* ps)
{
?? ?return 0 == ps->size;
}// 13.获取顺序表中有效元素个数
int SeqListSize(SeqList* ps)
int SeqListSize(SeqList* ps)
{
return ps->size;
}// 14.获取顺序表的容量
int SeqListCapacity(SeqList* ps)
int SeqListCapacity(SeqList* ps)
{
return ps->capacity;
}顺序表存在的一些问题：
- 插入和删除元素时要移动大量元素，效率较低；
- 扩容时很有可能造成空间浪费，例如现有100个元素，需要增加5个，现以2倍的形式来进行扩充，则会扩充至200个元素，浪费了95个数据空间；
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。