线性表
定义
具有相同的数据类型的几个数据元素的有限序列，其中n为表长，当n=0时线性表是空表，如下：
图
线性表的基本操作（创销、增删改查）
- InitList(&L)：初始化表，构造空的线性表L，分配内存空间
- DestroyList(&L)：销毁操作，销毁线性表，并释放空间
- ListInsert(&L,i,e)：插入
- ListDelete(&L,i,e)：删除
- LocateElem(L,e)：按值查找
- GetElem(L,e)：按位查找
- &L：取L的地址
什么时候传入引用&？ --对参数的修改结果需要"带回来"
顺序表
逻辑上相邻，物理(地址)上也相邻
顺序存储：逻辑上相邻的元素存在地址相邻的区域内，每个元素占的空间都相等
Q：如何判断一个数据元素的大小
A：sizeof(x),x是数据类型，注意sizeof是C语言32个关键字之一
静态分配
动态分配
动态申请和释放内存空间
malloc：开辟一片存储空间，返回一个空的指针
L.data=(ElemType *)malloc(sizeof(ElemType) *Initsize)
ElemType *：强制转型你定义的元素指针
例如：data的数据类型为int，则ElemType也应转为int类型
顺序表的特点
- 随机访问
- 存储密度高
- 扩展容量难
初始化顺序表
typedef struct { int *data;//指示动态分配数组的指针 int MaxSize;//顺序表的最大容量 int lenght;//顺序表的当前长度 } SeqList; void InitList(SeqList &L) { //使用malloc申请一片连续的存储空间：sizeof(int)=4Byte L.data = (int *)malloc(InitSize * sizeof(int)); L.lenght = 0; L.MaxSize = InitSize; }
顺序表的插入删除查找
插入
//插入 bool ListInsert(SeqList &L, int i, int e) { if (i < 1 || i > L.lenght + 1) { return false; } if (L.lenght > InitSize) { return false; } for (int j = L.lenght; j >= i; j--) { L.data[j] = L.data[j - 1]; } L.data[i - 1] = e; L.lenght++; return true; }
1.传入L，注意这里的L使用了😉&，所以是传入L的本身，而不是它的复制品
2.使用了一个for循环，让第i-1个元素之后的所有元素，都向后移动一位，同时也能逆向找到插入次序i
for (int j = L.lenght; j >= i; j--) {L.data[j] = L.data[j - 1];}
3.插入元素值，L.data[i - 1] = e;
删除
//删除 bool ListDelete(SeqList &L, int i, int &e) { printf("%d\n", i); if (i < 1 || i > L.lenght) { printf("%d", L.lenght); return false; } e = L.data[i - 1]; for (int j = i; j < L.lenght; j++) { L.data[j - 1] = L.data[j]; } L.lenght--; return true; }
查找
