1.线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构
线性表在逻辑上是线性结构，连续的一条线。
物理结构上并不一定是连续的。
线性表在物理结构上存储时，一般以数组和链式结构的形式存储
常见线性表：顺序表，链表
顺序表
无头链表
2.顺序表
2.1 概念和结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。
一般情况下采用数组存储元素，便于完成数据的增删查改。
顺序表分为两种：静态顺序表，动态顺序表
1.静态顺序表：使用规定长度的数组存储元素
数组长度不能进行改变
2.动态顺序表：使用动态开辟的数组存储元素
数组空间不够，可以进行扩容
默认扩容2倍，扩容一次扩多，浪费；扩少，频繁扩容，影响效率
2.2 接口实现
接口就是规定要程序做什么，但不在其中实现
动态顺序表的实现
定义数据类型和结构体
typedef int LSdatatype; typedef struct List { LSdatatype* a; int count;//顺序表中数据个数 int capacity;//顺序表容量 }LS;
初始化顺序表
必须通过指针才能改变结构体的内容，所有接口都需要传址，而不是传值
//初始化顺序表 void LSinit(LS* ps); void LSinit(LS* ps) { //需要进行判断，如果是空指针直接结束程序 assert(ps); ps->a = NULL; ps->count = 0; ps->capacity = 0; }
尾插
在进行尾插时，需要考虑内存是否充足，否则就会出现问题。由于在整个程序中，还有其他功能需要判断内存是否充足，所有便将其独立为函数。
void Checkcapacity(LS* ps) { //检查容量 if (ps->count == ps->capacity) { int newcapacity = ps->capacity; //如果容量为0，则赋值为4个int的容量； //若不为零，则扩容二倍 newcapacity == 0 ? 4 : 2 * ps->capacity; //为了避免内存开辟失败而将指针置为空，便创建临时变量tmp LSdatatype* tmp = (LSdatatype*)realloc(ps->a, newcapacity * sizeof(int)); if (tmp == NULL) { perror("realloc"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } }
对于realloc函数一般的理解是扩容，但这里就直接拿来开辟内存，是否由问题呢
答案是：没有问题
再一次地仔细地观察realloc函数的定义
如果返回值为空指针，则 realloc函数与 malloc函数类似
所有以后如果遇到类似的情况也不妨使用 realloc函数，更加的高效。
尾插
//尾插 void LSpushback(LS* ps, LSdatatype x); void LSpushback(LS* ps, LSdatatype x) { assert(ps); //判断容量 Checkcapacity(ps); ps->a[ps->count] = x; ps->count++; }
尾 插数据 1，2，3，4，监视如下
头插
//头插 void LSpushfront(LS* ps, LSdatatype x); void LSpushfront(LS* ps, LSdatatype x) { assert(ps); //检查容量 Checkcapacity(ps); int end = ps->count - 1; //挪动数据，从后往前挪 while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->count++; }
头插数据 5，监视如下
尾删
//尾删 --最简单直接将指针ps->a向前移动 void LSpopback(LS* ps); void LSpopback(LS* ps, LSdatatype x) { assert(ps); //温柔的检查 if (ps->count == 0) { return; } 暴力的检查 //assert(ps->count > 0); ps->count--; }
数组删除数据不需要将数据清空，直接向前移动下标即可
如果数据都已经被删完，还继续删除数据的话，便会使内存崩溃，所有需要进行检查，有两个检查方式：温柔和暴力。
将数组第一个数据进行删除，监视如下
查找顺序表中的数据
//查找顺序表中的数据 找不到返回-1 int LSfind(LS* ps, LSdatatype* x); int LSfind(LS* ps, LSdatatype* x) { assert(ps); int i = 0; for (i = 0; i < ps->count; i++) { if (ps->a[i] == x) { return i; } } return -1; }
在 pos位置 插入指定数据
//插入指定数据 void LSinsert(LS* ps, size_t pos, LSdatatype* x); void LSinsert(LS* ps, size_t pos, LSdatatype* x) { assert(ps); //相等时表示尾插 assert(pos<=ps->count) Checkcapacity(ps); size_t end = ps->count; while (pos < end) { ps->a[end] = ps->a[end-1]; end--; } ps->a[pos] = x; ps->count++; }
由于pos和end的类型不同，循环条件的不同，可能会造成程序死循环
循环条件为 pos <= end时
这里虽然end 的 数值是负数，但在与pos 进行比较时，会转化为无符号整形，一个相当大的数值，程序便会进入死循环。
删除 pos位置 的数据
//删除数据 void LSerase(LS* ps, size_t pos); void LSerase(LS* ps, size_t pos) { assert(ps); assert(pos < ps->count - 1); size_t begin = pos; while (begin < ps->count - 1) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->count--; }
修改 pos 位置 的数据
//修改数据 void LSmodify(LS* ps, size_t pos, LSdatatype x); void LSmodify(LS* ps, size_t pos, LSdatatype x) { assert(ps); assert(pos < ps->count); ps->a[pos] = x; }
销毁顺序表
//销毁顺序表 //既然申请空间，在程序结束时便需要销毁空间 void LSdestory(LS* ps); void LSdestory(LS* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->count = 0; }
2.3 顺序表的问题及思考
1.头部，中间的数据插入或删除，需要挪动数据，时间复杂度为O(N)
2.增容需要开辟空间，有可能是原地增容，也有可能是异地增容。如果是异地增容需要拷贝数据，释放旧空间，消耗时间
3.即使是2倍扩容，也会存在一定的空间浪费
解决以上问题，就需要引出下面的链表
3.链表
3.1 链表的概念和结构
概念：链表是一种物理结构上连续存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
逻辑结构
物理结构
链式结构在逻辑上是连续的，在物理上却不是
结点一般是从堆上申请的
从堆上申请的空间可能会连续
