1.线性表

1.2 线性表是什么？

线性表使具有 相同数据类型的n（n≥0）个 数据元素的 有限序列，其中n为 表长，当n=0时线性表是一个 空表。若用L命名线性表，则一般表示为

$$
L = (a_1,a_2,…,a_i,…,a_n)
$$

概念：

$a_i$是线性表中的“第i个”元素线性表中的 位序
$a_1$是 表头元素；$a_n$是 表尾元素
除第一个元素外，每个元素有且仅有一个 直接前驱；除最后一个元素外，每个元素有且仅有一个 直接后驱

1.2 线性表的基本操作

InitList(&L): 初始化表。构建一个空的线性表L，分配内存空间
DestoryList(&L): 销毁操作。销毁线性表，并 释放线性表L所占用的 内存空间
ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e
ListDelete(&L,i,&e)：删除操作。删除表L中国的第i个位置的元素，并用e返回删除元素的值
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
GetElem(i)：按位查找操作。获取表L中第i个位置的元素的值

其他常用操作：
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值
Empty(L)：判空操作。若L为空表，则返回true，否则返回false

Tips:

对数据的操作（记忆思路） —> 创销、增删改查
C语言函数的定义 —> <返回值类型> 函数名(<参数1类型>参数1,<参数2类型>参数2,…)
实际开发中，可根据实际需求定义其他的基本操作
函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）
什么时候要传入引用“&” —> 对参数的修改结果需要“带回来”

2.顺序表

2.1 顺序表是什么？

顺序表–用 顺序存储的方式实现线性表顺序存储。把 逻辑上相邻的元素存储在 物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2.2 顺序表的实现

静态分配(存储空间是静态的；容量不可变)

# define MaxSize 10         //定义最大长度
typedef struct {          
  ElemType data[MaxSize];   //用静态的“数组”存放数据元素
  int length;               //顺序表当前长度
}SqList;                    //顺序表类型的定义

void InitList(SqList &L){
  L.length = 0;
}

int main(){
  SqList L;
  InitList(L);
}

动态分配

# include <stdlib.h>
# define InitSize 10         //定义顺序表初始长度
typedef struct {          
  int *data;           //指示动态分配数组的指针
  int MaxSize               //表示表的最大容量
  int length;               //顺序表当前长度
}SeqList;                    //顺序表类型的定义

void InitList(SeqList &L){
  //用malloc函数申请一片连续的存储空间
  L.data = (int *)malloc(InitSize*sizeof(int));
  L.length = 0;
  L.MaxSize = InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
  int *p = L.data;
  L.data = (int *)malloc((L.maxsize + len)*sizeof(int));
  for (int i=0; i<L.length; i++){
    L.data[i] = [i];
  }
  L.MaxSize = L.MaxSize + len;
  free(p);
}
int main(){
  SeqList L;
  InitList(L);
}