线性表是具有相同数据类型的数据元素的有限序列。
特点：
- 元素个数有限；序列中元素排序有先后次序；每个元素都是单个的数据元素；数据类型都相同，并且每个元素都占有相同大小的存储空间；
- InitList(&L) 初始化创建一个空的线性表；Length(L) 返回线性表的长度；LocateElem(L,e) 按值查找，返回给定关键字的元素在表中的位置；GetElem(L,i) 按位查找，返回第i个位置的元素；ListInsert(&L, i, e) 插入元素，在第i个位置插入元素e；ListDelete(&L, i, &e) 删除元素，删除第i个位置的元素并用e返回删除元素的值；PrintList(L) 输出操作，按前后顺序输出现象表中所有元素；Empty(L) 判断线性表是否为空；DestroyList(&L) 销毁线性表，并且释放空间。
2. 顺序表 2.1 顺序表的定义“ & ”说明：即将修改之后的结果“带回来”，如果不使用将只修改当前函数中的变量值。
地址上连续的存储单元依次存线性表中的数据元素，使得逻辑上相邻的元素在物理上也相邻。线性表中的位序是从1开始的。
2.2 线性表创建 2.2.1 静态分配进行静态分配时，数组的大小和元素数量是固定的。并且无法进行修改，在数据过多时可能会溢出。
// 静态分配线性表
#define InitSize 50
#define ElemType int
// 创建SqList类型结构体
typedef struct {
ElemType data[InitSize]; //定义一个数组用来存储元素
int length; // 线性表当前长度
}SqList;
2.2.2 动态分配
如果使用动态分配，即使原来的数据空间占满也可以开辟一个新的空间来替换原来的存储空间。
#define InitSize 50
#define ElemType int
void InitListDy(SqlListDy &L){
// 动态分配一个存储空间
// malloc 函数返回指向开辟的内存空间的指针
// sizeof 函数返回传入参数的大小
L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
L.length = 0;
L.MaxSize = InitSize;
for (int i = 0; i < L.MaxSize; i++)
{
L.data[i] = 0;
}
}
给数组扩容方法
void IncreaseSize(SqlListDy &L, int len){
// 用指针p存储顺序表原先的内存
int *p = L.data;
// 开辟新的空间
L.data = (ElemType *)malloc(L.MaxSize + len * sizeof(ElemType));
// 把原先的值再赋值给新空间
for(int i = 0; i < L.length; i++){
L.data[i] = p[i];
}
// 给最大长度增加len
L.MaxSize += len;
// 释放原先的内存空间
free(p);
}
2.3 线性表的基本操作
2.3.1 获取线性表长度
int Length(SqList L){
return L.length;
}
2.3.2 获取给定元素在表中的位置
因为数组是从零开始而线性表是从一开始的，所以元素在数组中的位置加一就是在线性表中的位置。
int LocateElem(SqList L, ElemType e){
// 遍历线性表
for (int j = 0; j < L.length; j++)
{
// 找到相同的值返回
if(L.data[j] == e){
return j + 1;
}
}
// 找不到相同的值返回0
return 0;
}
2.3.3 返回给定位置中的元素
ElemType GetElem(SqList L, int i){
// 判断i是否符合规则
if(i < 1 || i > L.length){
return 0;
}
return L.data[i - 1];
}
2.3.4 插入元素
插入元素时，要从当前插入位置的元素开始往移动一位。
bool ListInsert(SqList &L,int i, ElemType e){
// 判断i是否符合范围要求
if(i < 1 || i > L.length+1){
return false;
}
// 判断执行插入之后是否会溢出
if(L.length >= InitSize){
return false;
}
// 插入要求不能修改之前的元素序列，即就需要将之前表中位于i之后的元素向后移动
for (int j = L.length; j >= i; j--){
// 将前一个元素赋值给后一个元素
L.data[j] = L.data[j-1];
}
// 因为数组是0开始而线性表是1开始，所以这里要将i-1
L.data[i - 1] = e;
// 线性表长度加一
L.length ++;
return true;
}
2.3.5 删除元素
在删除元素时，要将删除的元素之后的元素往前移动一位。
bool ListDelete(SqList &L, int i, ElemType &e){
// 判断i是否符合范围要求
if(i < 1 || i > L.length+1){
return false;
}
// 判断是否为空表
if(L.length < 1){
return false;
}
// 保存当前位置的元素
e = L.data[i - 1];
// 删除线性表中指定位置的元素时，要将其后面的元素往前移动。
for (int j = i; j < L.length; j++){
L.data[j - 1] = L.data[j];
}
// 线性表长度减一
L.length --;
return true;
}
2.3.6 其他操作
void PrintList(SqList L){
for (int i = 0; i < L.length; i++){
cout << L.data[i] << endl;
}
}
bool Empty(SqList L){
return L.length == 0;
}
void DestroyList(SqList &L){
}
3. 链表
链式存储线性表时，不需要使用连续的存储单元，即逻辑上相邻的元素在物理上不要求相邻，使用“链”建立起元素之间的逻辑关系，在修改时只需要修改指针。
3.1 单链表通过任一存储单元来存储线性表中的数据元素，每个元素中除了存储自身信息之外还要存储指向下一个节点的指针。
缺点：无法进行随机存取。
优点：不需要连续的内存空间。
头节点：在第一实际存储信息之前的节点，可以不存储任何信息也可以存储表长等相关信息。优点：第一个实际存储信息的节点进行处理时与其他节点相同；对空白表和非空表的处理得到了统一（如果不引用头节点，在空表进行添加时要使新的节点作为第一个节点，而不能直接使用head.next = newLNode。）。
下述方法中未特殊声明的都是有头节点的方式来完成的。
3.1.1 定义节点类型及初始化链表element 用来存储当前节点的信息
next 用来存储指向下一节点的指针。
链表节点类型：
typedef struct LNode{
// 定义元素的值
Element element;
// 指向下一个元素的指针
struct LNode *next;
}LNode, *linkedList; // 定义了LNode类型的两个变量，即 LNode 和 linkedList指针
bool InitlinkedList(linkedList &L){
// 创建一个全新的节点指向头节点
L = (linkedList)malloc(sizeof(LNode));
// 给头节点的next赋空
L->next = NULL;
return true;
}
3.1.2 头插法插入
插入的新节点作为新的第一个存储信息的节点。
void List_HeadInsert(linkedList &L, Element e){
// 创建全新的节点
LNode *node = (LNode*)malloc(sizeof(LNode));
node->element = e;
// 前插，使新的节点指向原先真正存放信息的第一个节点。
node->next = L->next;
// 使头节点的next指向当前的新节点。
L->next = node;
}
3.1.3 尾插法插入
插入的新节点作为最后一个节点。
void List_TailInsert(linkedList &L, Element e){
// 创建全新的节点
LNode *node = (LNode*)malloc(sizeof(LNode));
node->element = e;
node->next = NULL;
LNode *OldNoed = L->next;
// 遍历找到最后一个节点
while(OldNoed->next != NULL){
OldNoed = OldNoed->next;
}
OldNoed->next = node;
}
3.1.4 按位查找
LNode* GetElem(linkedList &L, int i){
// 判断位置是否合法
if (i<=0)
{
cout << "传参错误" << endl;
return NULL;
}
int j = 1;
// 根据头节点获取第一个实际存储数据的节点
LNode *node = L->next;
while (node->next != NULL && j < i){
node = node->next;
j++;
}
cout << "----------按位查找结果：" << node->element << "----------"<< endl;
return node;
}
3.1.5 按值查找
LNode* LocateElem(linkedList &L,int e){
LNode* node = L->next;
while (node->next != NULL && node->element != e)
{
node = node->next;
cout << "----------按值查找结果：" << node->element << "----------"<< endl;
}
return node;
}
3.1.6 获取长度
int Length(linkedList &L){
int i = 1;
LNode *node = L->next;
while (node->next != NULL){
i++;
node = node->next;
}
cout << "----------链表的长度为：" << i << "----------"<< endl;
return i;
}
3.1.7 在某个位置插入节点
因为是要找到i的前一个节点，所以要--i。当前方法与下述删除方法都可以在内部调用根据位置获取节点来获取要删除节点的前驱节点。
void ListInert(linkedList &L, int i, Element e){
// 判断位置是否合法
if(i < 1){ return;}
// 创建新节点
LNode *NewNode = (LNode *)malloc(sizeof(Element));
NewNode->element = e;
LNode *Node = L->next;
// 遍历找到第i个节点的前一个节点
int j = 1;
while (j < --i && Node->next != NULL){
j++;
Node = Node->next;
}
NewNode->next = Node->next;
Node->next = NewNode;
}
3.1.8 删除某个节点NewNode->next = Node->next; 将新节点的next指向原先该位置。如图①
Node->next = NewNode; 将第i-1个节点的next指向新节点。如图②，画×是指同时也断开了与ni节点的next指向。
void ListDelete(linkedList &L, int i)
{
// 判断位置是否合法
if (i < 1)
{
return;
}
LNode *Node = L->next;
// 遍历找到第i个节点的前一个节点
int j = 1;
while (j < --i && Node->next != NULL)
{
j++;
Node = Node->next;
}
// 找到要被删除的节点
LNode *p = Node->next;
// 将它的后继节点作为它前驱的后继节点
Node->next = p->next;
free(p);
}
3.2 双链表
