数据结构（其二）--线性表
目录
1. 基本概念
2.线性表的基本操作
3.顺序表
（1）.静态分配
（2）.动态分配
（3）.顺序表的插入与删除（以静态分配为例）（示例代码中包含了一下必要的基本函数）
（4）.按位序查找、按值查找
4.链表
（1）.单链表
i.单链表（带头结点）的定义
1. 基本概念
线性表：
（1）.其中的各个元素，数据类型相同。
（2）.元素之间，有次序。
（3）.都有表头元素和表尾元素。
（4）.除了表头表尾，每个元素都可以找到一个直接前驱和直接后继。
2.线性表的基本操作
表的从无到有
InitList(&L)：初始化一个线性表
DestroyList(&L)：销毁
。
ListInsert(&L, i, e)：插入，在表L的第 i 处插入元素 e
ListDelete(&L, i, &e)：删除，将表L的第 i 处元素删除，并用 e 返回该被删除的元素
。
LocateElem(L, e)：按值查找，在表中查找特定关键字e 的元素，返回的是e 的位序，而非下标
GetElem(L, i)：按位查找，获取表中第 i 个元素的值
。
其他常规操作：
Length(L)：求表长度
PrintList(L)：输出表的所有元素
Empty(L)：判断表是否为空，返回true or false
高度概括，即为，创销与增删改查
3.顺序表
以顺序存储方式储存数据的线性表
（1）.静态分配
#define MAX 10
//顺序表（静态分配）
class SqList
{
public:int data[MAX];int length;
};
//初始化
void InitList(SqList &l)
{for(int i = 0 ;i < 10 ;i++){l.data[i] = 0;}l.length = 0;
}
//打印所有元素
void PrintList(SqList &l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数：" << l.data[i] << endl;
}//测验
void test01()
{SqList l;InitList(l);PrintList(l);
}（2）.动态分配
#define InitSize 10
//顺序表（动态分配）
class SqList
{
public:int* data; //指示动态分配数组的指针int MaxSize; //指示最大容量int length; //指示当前长度
};
//初始化顺序表
void InitList(SqList& l)
{l.data = new int[InitSize];l.MaxSize = InitSize;l.length = 0;for (int i = 0; i < l.MaxSize; i++){l.data[i] = 0;}
}
//增长数组空间
void IncreaseSize(SqList& l, int len)
{int* p = l.data; //暂存原数组中的数据l.data = new int[10 + len]; //扩展新的数组for (int i = 0; i < l.length; i++) //将原数据拷贝进新数组中{l.data[i] = p[i];}l.MaxSize = InitSize + len; //修改数组的状态数据delete p; //将p释放
}
//打印所有元素
void PrintList(SqList& l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数：" << l.data[i] << endl;
}void test01()
{SqList l;InitList(l);PrintList(l);
}（3）.顺序表的插入与删除（以静态分配为例）（示例代码中包含了一下必要的基本函数）
//插入
bool ListInsert(SqList& l, int d, int e)
{
if (l.length >= MAX) //首先要判断表是否已满、插入是否合法
{
cout << "插入失败，已达上限" << endl;
return false;
}
if (d < 1 || d > l.length + 1)
{
cout << "插入失败,无直接前驱" << endl;
return false;
}
for (int j = l.length; j >= d; j--) //将插入点之后的元素后移
l.data[j] = l.data[j - 1];
l.data[d - 1] = e; //插入，因为d指的是第几个数，在数组的换算中要减一
l.length++;
return true;
}//删除
bool ListDelete(SqList& l, int d, int &e)
{
if (d < 1 || d >l.length) //判断删除的位置是否合法
return false;
e = l.data[d - 1]; //暂存删除掉的元素
for (int j = d; j < l.length; j++) //将被删除元素之后的元素前移
l.data[j - 1] = l.data[j]; //此处，必须是j = d，j-1被j覆盖，若j = d-1，则下文的覆盖会变为j 被j+1 覆盖，而j+1在最后有可能会超过数组的最大容量
l.length--;
return true;
}
示例代码
#define MAX 10
//顺序表（静态分配）
class SqList
{
public:int data[MAX];int length;
};
//初始化
void InitList(SqList& l)
{for (int i = 0; i < 10; i++){l.data[i] = 0;}l.length = 0;
}
//打印所有元素
void PrintList(SqList& l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数：" << l.data[i] << endl;
}
//存入数据
void InputElem(SqList& l, int e)
{int i = 0;while (i < MAX){if (l.data[i] == 0){l.data[i] = e;l.length++;break;}i++;}
}
//获取顺序表长度
int GetLength(SqList l)
{//cout << l.length << endl;return l.length;
}
//插入
bool ListInsert(SqList& l, int d, int e)
{if (l.length >= MAX) //首先要判断表是否已满、插入是否合法{cout << "插入失败，已达上限" << endl;return false;}if (d < 1 || d > l.length + 1){cout << "插入失败,无直接前驱" << endl;return false;}for (int j = l.length; j >= d; j--) //将插入点之后的元素后移l.data[j] = l.data[j - 1];l.data[d - 1] = e; //插入，因为d指的是第几个数，在数组的换算中要减一l.length++;return true;
}
//删除
bool ListDelete(SqList& l, int d, int &e)
{if (d < 1 || d >l.length) //判断删除的位置是否合法return false;e = l.data[d - 1]; //暂存删除掉的元素for (int j = d; j < l.length; j++) //将被删除元素之后的元素前移l.data[j - 1] = l.data[j]; //此处，必须是j = d，j-1被j覆盖，若j = d-1，则下文的覆盖会变为j 被j+1 覆盖，而j+1在最后有可能会超过数组的最大容量l.length--;return true;
}//查看情况
void CheckList(SqList& l)
{PrintList(l);cout << "当前长度为" << GetLength(l) << endl;
}//测验
void test01()
{SqList l;InitList(l);//输入部分数据InputElem(l, 1);InputElem(l, 2);InputElem(l, 3);InputElem(l, 4);CheckList(l);//开始插入if(ListInsert(l, 3, 6))CheckList(l);//开始删除int a = -1;if (ListDelete(l, 2, a))CheckList(l);
}（4）.按位序查找、按值查找
很简单，不多赘述
//判断d的合法性
bool JugdeD(SqList l, int d)
{if (d < 1 || d > l.length)return false;return true;
}//按位序查找
int GetElem(SqList l, int d)
{if (JugdeD(l, d))return l.data[d - 1];return 0;
}//按值查找
int LocateElem(SqList l, int e)
{for (int i = 0; i < l.length; i++){if (l.data[i] == e) //数组储存的数据，若是类等复杂的数据类型，则需要对等号进行重载return i + 1;}return 0;
}
//其余代码与上文相同
//其中，JugdeD函数可以替换上文插入与删除中对位序合法性的判别————封装4.链表
以链式存储方式储存数据的线性表
（1）.单链表
i.单链表（带头结点）的定义
//单链表
class LNode
{
public:int data; //数据域，存放数据LNode* next; //指针域，指向下一个节点
};
//用using关键字给类起别名，用LinkList指代的是头结点，代表的是整个链表
using LinkList = LNode*;//初始化
bool InitList(LinkList& L)
{L = new LNode();if (L == nullptr) //如果成立，则说明内存不足，分配失败return false;L->next = nullptr;return true;
}ii.插入、删除（带头结点）
不带头结点的，要注意头指针的变动，其他的都雷同。
插入（普通版）
//插入
bool ListInsert(LinkList& L, int i, int e)
{if (i < 1) //判断插入位点是否合法[1]——i值的合法性{cout << "i为负数" << endl;return false;} LNode* p = L; //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的LNode* s = new LNode(); //新的数据储存s->data = e;while (p != nullptr && i != 1) //由头结点起始，开始遍历寻找对应位点{p = p->next;i--;}if (p == nullptr) //判断插入的位点是否合法[2]——i值对应的节点的合法性{cout << "插入位点超出实际长度" << endl;return false;} s->next = p->next; //开始接轨，顺序不能乱p->next = s;return true;
}插入（封装版）
//特定节点的后插操作
bool InsertNextNode(LNode* p, int e)
{if (p == nullptr) {cout << "插入位点超出实际长度" << endl;return false;}LNode* s = new LNode();s->data = e;s->next = p->next;p->next = s;return true;
}
//插入
bool ListInsert(LinkList& L, int i, int e)
{if (i < 1) //判断插入位点是否合法[1]——i值的合法性{cout << "i为负数" << endl;return false;} LNode* p = L; //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的while (p != nullptr && i != 1) //由头结点起始，开始遍历寻找对应位点{p = p->next;i--;}return InsertNextNode(p, e); //被封装了的部分
}