1.线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。是广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串……
线性表逻辑上线性结构，但在物理结构上并不一定连续，通常以数组和链式结构形式存储。
2.顺序表
2.1概念及结构
顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
分类：
1.静态顺序表：使用定长数组存储
缺点：不能灵活控制存储大小
#pragma once//防止头文件被重复包含 //等价于 //ifndef _SEQLIST_H_ //define _SEQLIST_H_ #include<stdio.h> #include<string.h> //增强程序可维护性 #define MAX_SIZE 100 typedef int SQDataType; //静态的 struct SeqList { SQDataType a[MAX_SIZE]; int size; }; /*typedef struct SeqList { SQDataType a[MAX_SIZE]; int size; }SL; */ //动态的 typedef struct SeqList { SQDataType*a; int size;//有效数据的个数 int capacity;//容量 }SL; typedef struct SeqList SL; //初始化接口函数 void SeqListInit(SL*ps); //endif
2.动态顺序表：使用动态开辟的数组存储
2.2接口实现
3.实现动态顺序表
1.SeqList.h:头文件，结构、常量的定义，接口函数的申明
2.test.c:用于动态顺序表功能的测试
3.SeqList.c:接口函数的实现
3.1结构的定义
1.data指针：指向动态开辟空间
2.size变量：记录当前有效数据的个数
3.capacity变量：记录当前容量
typedef struct SeqList { SLDataType* a; int sz;// 表示数组中存储了多少个数据 int capacity;// 数组实际能存数据的空间容量是多大 }SL;
当有效数据个数size和capacity相等时，说明当前顺序表空间已满，需要进行扩容。
3.2 接口函数
增删查改等功能我们会封装成函数，而当我们调用时，就会对接到对应函数，所以我们称这些函数为接口函数。
void SeqListInit(SL* ps);// 初始化 void SeqListCheckCapacity(SL* ps);// 检查增容 void SeqListPushBack(SL* ps, SLDataType x);// 尾插 void SeqListPopBack(SL* ps);// 尾删 void SeqListPushFront(SL* ps, SLDataType x);// 头插 void SeqListPopFront(SL* ps);// 头删 void SeqListPrint(SL* ps);// 打印 void SeqListDestory(SL* ps);// 销毁 int SeqListFind(SL* ps, SLDataType x);// 查找 void SeqListInsert(SL* ps, int pos, SLDataType x);// 指定下标位置插入 void SeqListErase(SL* ps, int pos);// 指定下标位置删除 void SeqListModify(SL* ps, int pos, int x);// 修改
命名风格与C++标准库类似
3.2.1 初始化
顺序表在进行操作之前，需要先将其内容进行初始化，防止之后操作时出错。
void SeqListInit(SL* ps);
void SeqListInit(SL* ps) { assert(ps); ps->a = NULL;// 置空 ps->sz = 0; ps->capacity = 0;// 初始大小和容量设定为0 }
注意参数不能为结构体（SL s1），因为实参传参时会形成一份临时拷贝，叫做形参。当我们在函数中对形参的内容进行修改时，不会影响到实参，所以需要传地址（SL *ps）。
3.2.2 检查增容
当顺序表插入数据时：
1.顺序表没有空间
2.空间不够，需要扩容
3.空间足够，插入数据
void SeqListCheckCapacity(SL* ps) { assert(ps); // 顺序表没有空间or顺序表空间不足 if (ps->sz == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; // realloc在起始地址为空指针时，和malloc一样效果 //空间不足，扩两倍 SLDataType* tmp = (SLDataType*)realloc(ps->a, capacity *2* sizeof(SLDataType)); //如果扩容失败，打印扩容失败 if (tmp == NULL) { printf("realloc fail\n"); exit(-1);//结束程序 } else { ps->a = tmp; ps->capacity = newcapacity; } } }
3.2.3 打印
在每次操作后，可以打印出顺序表，观察操作情况：
void SeqListPrint(SL* ps);// 打印
void SeqListPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->sz; i++) { printf("%d ", ps->a[i]); } }
3.2.3 尾插
void SeqListPushBack(SL* ps, SLDataType x)
void SeqListPushBack(SL* ps, SLDataType x) { assert(ps); SeqListCheckCapacity(ps);// 检查增容 ps->a[ps->sz] = x;// 在尾部插入 ps->sz++; }
3.2.5 头插
void SeqListPushBack(SL* ps, SLDataType x)
void SeqListPushFront(SL* ps, SLDataType x) { assert(ps); SeqListCheckCapacity(ps);// 检查增容 //挪动数据.保证原来数据不被覆盖 int end=ps->sz-1; while(end>=0)//一直挪动0下标 { ps->a[end+1]=ps->a[end]; end--; } ps->a[0]=x; ps->sz++; }
3.2.6 头删
void SeqListPopFront(SL* ps);
void SeqListPopFront(SL* ps) { assert(ps->sz > 0);// 暴力处理，sz为0时，不能头删 // 挪动数据 int start = 1; while (start <= ps->sz - 1) { ps->a[start - 1] = ps->a[start]; start++; } // memmove(ps->a, ps->a + 1, (ps->sz - 1) * sizeof(SLDataType)); // 这样也可以，将1下标开始的元素，向前移动sz-1个单位 // 但是并不推荐，还是自己动手实现比较好 ps->sz--; }
