线性表

线性表是n个具有相同特性的数据元素的有限序列。

常见的有：顺序表、链表、栈、队列、字符串....

线性表在逻辑上是线性结构的，即一条连续的直线

但在物理结构上不一定是连续的，其在物理存储时，通常以数组和链式结构的形式存储

顺序表

使用一段地址连续的存储单元依次存储数据元素的线性结构

ps:顺序表就是数组，但在数组基础上，要求数据从头开始且连续存储，不能跳跃或间隔

顺序表存在的缺陷：

1.空间不够需要扩容，而扩容会付出一定代价

①原地扩容：

还是原地址，代价低，至少不需要拷贝原数据
②异地扩容：

已经改变

2.避免频繁扩容：平常空间满了扩2倍，可能会导致一定的空间浪费
如100->200，但实际我们只需要120个空间，浪费80个

3.要求数据从头开始连续存储，那么我们在头部或中间位置插入数据需要挪动数据，效率低

优点：

1.支持随机访问
2.对于有些算法，需要结构支持随机访问，如二分查找，优化后的快排等

下面直接创建顺序表

SeqList.h 头文件

  1、静态顺序表

#define N 1000
typedef int SLDataType;    // 以后需要存储不同类型的数据，可以直接修改typedef struct SeqList
{SLDataType a[N];int size; // 表示数组中存储了多少个数据
}SL;//    接口函数 - 函数名是根据STL风格
void SeqListInit(SL* ps);    //    初始化数组
//    静态：容量给小则不够用，给大则浪费空间
void SeqListPushBack(SL* ps, SLDataType x);    //尾插
void SeqListPopBack(SL* ps);                //尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);                //头删

2、动态顺序表

typedef int SLDataType;    //    动态顺序表
typedef struct SeqList
{SLDataType* a;int size; int capacity;    // 数组实际能存储的空间容量是多少个
}SL;void SeqListInit(SL *ps);    // 形参 是实参的临时拷贝，不会影响实参 - 传值操作//           所以传地址
void SeqListPushBack(SL* ps, SLDataType x);    
void SeqListPopBack(SL* ps);                
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);               

SeqList.c源文件
```

#pragma once
#include "SeqList.h"void SeqListInit(SL*ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}
void SeqListPushBack(SL* ps, SLDataType x)
{//  如果没有空间(0个)或空间不足(满了)if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//  三目操作符 是否等于0，是给4，否则给2倍原空间SLDataType* tmp = (SLDataType * )realloc(ps->a, sizeof(SLDataType) * newcapacity);//    开辟空间if (tmp == NULL){printf("realloc fail\\n");exit(-1);}ps->a = tmp;    //    开辟的空间给结构体ps->capacity = newcapacity;// 开辟的大小给原大小}ps->a[ps->size] = x; // 要传的值给结构体ps->size++;
}void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);

Source.c文件

#include"SeqList.h"void TestSeqList1() 
{SL sl;SeqListInit(&sl);
}
int main()
{TestSeqList1();return 0;
}

注意：传结构体不能传值，必须传址，否则无法修改里面内容（形参是实参的临时拷贝，形参的改变不影响实参）

接下来逐个实现接口函数：

①尾删数据

注意此处，未加判断条件，size–将可以为负值(-1,-2…)

而在–负数后，再增加数据，会造成越界访问


在销毁时会报错

纵上

法1：加上判断条件，空间大于0才可–
法2：断言，小于等于0直接报错

②头插数据

数据向后挪动，空出前面的位置

同尾删数据，未判断大小，若添加数据过多大于有效空间大小，将造成越界访问，报错


多处用到扩容，这里直接封装成函数


若空间满了则扩容

③头删数据

和尾插数据类似
从第二个数据开始一个一个放上去