线性表——顺序表

一：线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

二：顺序表

1：概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

1：静态顺序表

静态顺序表：使用定长数组存储元素

#pragma once //为了避免同一个头文件被包含(include)多次//静态顺序表:使用定长数组存储元素.(不太实用)
// Max太小了不够用 太大了怕浪费
#define Max 10
//定长数组不只是int类型的,
//因此用结构体来方便修改其他数据类型
typedef int SLDataType;//顺序表SL的DataType
typedef struct SeqList
{//int a[Max];//定长数组SLDataType a[Max];size_t size;//记录数组中的有效数据
}SL;

静态顺序表一般不太实用 我们经常用的是动态顺序表

2：动态顺序表

动态顺序表：使用动态开辟的数组存储

2：动态顺序表的代码实现

1：结构

//结构
typedef int SLDataType;//顺序表SL的DataType
typedef struct SeqList
{SLDataType* a;//定义一个指针指向动态开辟的数组size_t size;//记录数组中的有效数据(指向最后数据的下一个位置)size_t capcity;//空间容量的大小
}SL;

2：接口实现

1：初始化

将有效数据个数和容量都初始化为0,并将指针指空

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

2：释放内存

释放顺序表的空间,并将指针指空,容量和数据个数置0 (只有在数组不为空的情况下才会销毁)

void SLDestroy(SL* ps)
{//if (ps->a != NULL)if (ps->a)//非0为真{free(ps->a);ps->a = NULL;ps->size = ps->capcity = 0;}		
}

3：检查容量

在增加数据的时候，首先需要判断顺序表的容量是否够用，如果不够用就需要增容。

每次扩容扩成原来容量二倍的原因：

• 如果一次扩多了，会造成空间的浪费
• 扩的少了在增加数据的时候就需要频繁扩容，降低了程序的效率。realloc函数扩容存在原地扩容和异地扩容俩种情况，如果是异地的话无疑会更加增加扩容的成本，需要花费更多时间。
• 综合考虑俩种因素，扩成原来的二倍是比较合理的

我们知道，开辟动态空间使用的是malloc或者calloc函数，而realloc是用来扩容的，而我们这里仅使用realloc既实现开辟，又实现扩容。-

仅用realloc不用malloc的原因：

• malloc仅在初始化后容量为0的时候开辟动态空间使用，之后的扩容都是使用到realloc，如果分情况写就会比较冗余
• realloc同样可以实现malloc的功能，当传给realloc的指针是空指针NULL的时候，realloc的功能和malloc是一样的，所以我们在初始化时也是将管理数据的指针设为空指针的

void SLCheckCapacity(SL* ps)
{assert(ps);//扩容if (ps->size == ps->capcity)//如果越界了或者为NULL{//一般2倍扩容//如果是0,则空间为4个(随机)int newCapcity = ps->capcity * 2 == 0 ? 4 : ps->capcity * 2;//空间容量应当将个数*字节//realloc:返回新开的数组空间的地址,可能第一次为NULL,也有可能接收失败//因此用tmp变量接收SLDataType* tmp = realloc(ps->a, newCapcity * sizeof(SLDataType));if (tmp == NULL){perror("realloc is fail");exit(-1);//异常终止返回-1,正常结束返回0}ps->a = tmp;ps->capcity = newCapcity;}
}

4：尾插

在数组尾部插入数据,首先要考虑扩容问题,再插入数据,同时元素个数增加

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//防止数组越界ps->a[ps->size] = x;ps->size++;
}

5：尾删

删除数组尾部的数据,同时元素个数减小,要考虑数组为空不能删的情况

void SLPopBack(SL* ps)
{//温柔的检查//if (ps->size == 0) //{//	return;//}//暴力检查assert(ps->size > 0);//为真就通过运行,为假就结束运行了ps->size--;
}

6：头插

在数组尾部插入数据,首先要考虑扩容问题,再将数组的每个元素依次向后移动一位，再在第一个位置插入数据即可,同时元素个数增加

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//从最后一个数据开始依次向后挪动一位数据进行覆盖int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;//头部插入数据ps->size++;
}

7：头删

void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);//从第一个元素开始删int begin = 0;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}//或者从第二个元素开始删/*int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}*/ps->size--;
}

8：顺序表在任意位置(pos)插入x

//任意位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{//防止越界assert(ps);assert(pos >= 0 && pos <= ps->size);//检查容量SLCheckCapacity(ps);//从最后一个数据到目标位置结束开始依次向后挪动一位数据覆盖int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;//在pos处插入数据ps->size++;
}

9：顺序表在任意位置(pos)删除x

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

10：在顺序表中查找指定值

//查找指定值
int SLFind(SL* ps, SLDataType x, int begin)
{assert(ps);for (int i = begin; i < ps->size; ++i){if (ps->a[i] == x){return i;//找到直接返回下标}}//查找不到，返回-1return -1;
}

3：接口优化

1：尾插尾删优化

尾插

void SLPushBack(SL* ps, SLDataType x)
{//在下标为size的位置插入数据(末尾元素的下一个)SLInsert(ps, ps->size, x);
}

尾删

void SLPopBack(SL* ps)
{//删除下标为size-1的数据(末尾元素)SLErase(ps, ps->size - 1);
}

2：头插头删优化

头插

void SLPushFront(SL* ps, SLDataType x)
{	//在下标为0的位置插入数据(首元素)SLInsert(ps, 0, x);
}

头删

void SLPopFront(SL* ps)
{//删除下标为0的数据(首元素)SLErase(ps, 0);
}

具体代码可见：https://gitee.com/calcium-oxide-2411/test_c