1.线性表的定义
线性表：零个或多个数据元素的有限序列。
线性列表，包括顺序列表和链表
序列表（实际上是一个数组）中元素的地址是连续的。
链表中节点的地址不连续，通过指针连接。
2.线性表的抽象数据类型
线性表的抽象数据类型定义如下：
ADT线性表（List）
数据
线性表的数据对象集合为{a1,a2,....,an}，每个元素的类型为。 其中，除第一个元素a1外，每个元素都有且仅有一个直接前驱元素，除最后一个元素an外，每个元素都有且仅有一个直接后继元素。 数据元素之间的关系是一对一的关系。
(*L)：创建空线性表的初始化操作。
(L)：如果线性表为空，则返回true，否则返回false。
(*L)：清除线性表。
(L,i,*e)：返回线性表L中第i个位置元素到e。
(L,e)：在线性表L中搜索等于给定值e的元素。 如果查找成功，则返回该元素在表中的序号； 否则返回0表示失败。
(*L,i,e)：在线性表的第i个位置插入元素e。
(*L,i,*e)：删除线性列表L中的第i个元素，并使用e返回其值
(L)：返回线性表L的元素数量。
(L)：打印线性表
对于不同的应用，线性表的基本操作是不同的，以上操作是最基本的。
对于实际问题中涉及到的更复杂的线性表运算，完全可以使用这些基本运算的组合来实现。
3、线性表的顺序存储
1. 顺序存储定义
序列表一般使用数组来实现。 其实就是在内存中找到一个起始地址，然后以占位符的形式占据一定的连续内存空间，然后将相同数据类型的数据元素依次放置在这个空的空间中。 ，指定数组大小有两种方式，一种是静态分配，一种是动态扩展。
与序列表相关的操作与数组相关，一般是移动数组元素。
2.如何实现顺序存储
结构
我们直接看序列表的模板类的代码：
常量整数 = 100;
班级
:
(){=0;} //无参构造函数
(a[],int n); //带参数的构造方法
~(){} //析构函数
int (){ ;} //线性表长度
获取（int i）； //按位查找
整数（x）； //按值搜索
无效（int i，x）； //插入
(int i); //删除
空白 （）; //遍历
:
数据[]; //序列表是使用数组实现的
整数； //存储顺序表的长度
};
序列表的封装需要三个属性：
存储空间的起始位置。数组数据的存储位置就是线性表存储空间的存储位置。
线性表最大存储容量.数组长度
线性表的当前长度。
注意：数组的长度与线性表当前的长度不同。 数组的长度是存储线性表的存储空间的总长度，初始化后一般不会改变。 线性列表的当前长度是线性列表中元素的数量，该长度会发生变化。
下面我们来实现序列表的各个功能：
构造参数：
创建一个长度为n的序列表，需要将给定的数组元素作为线性表的数据元素传入序列表，并以传入的元素个数作为序列表的长度。
::(a[],int n)
if(n>) 抛出“错误”；
for(int i=0;i
数据[i]=a[i]；
=n;
按位搜索
按位查找的时间复杂度为O(1)O(1)。
::获取(int i)
if() 抛出“错误”；
否则数据[i-1]；
按值查找
按值搜索需要按顺序比较序列列表中的元素。
整数::(x)
for(int i=0;i
if(数据[i]==x) i+1;
0;
插入
在插入过程中，需要注意元素移动的方向。 您必须从最后一个元素开始移动。 如果表已满，就会发生溢出； 如果插入位置不合理，就会出现位置异常。
无效 ::(int i, x)
if(>=) 抛出“”；
if(+1) 抛出“”；
for(int j=;j>=i;j--)
数据[j]=数据[j-1]；
数据[i-1]=x；
++;
删除
注意算法中元素的移动方向。 移动元素之前必须先取出已删除的元素。 如果表为空，就会发生下溢。 如果删除位置不合理，就会出现删除位置异常。 ·
::（整数我）
整数x；
if(==0) 抛出“”；
if() 抛出“”；
x = 数据[i-1]；
for(int j=i;j
数据[j-1] = 数据[j]；
--;
X;
遍历
按下标按顺序输出每个元素
空白 ：：（）
for(int i=0;i
）抛出“错误”；
for(int i=0;i
数据[i]=a[i]；
=n；
::获取(int i)
if() 抛出“错误”；
否则数据[i-1]；
整数::(x)
for(int i=0;i
if(数据[i]==x) i+1;
0;
无效 ::(int i, x)
if(>=) 抛出“”；
if(+1) 抛出“”；
for(int j=;j>=i;j--)
数据[j]=数据[j-1]；
数据[i-1]=x；
++;
::（整数我）
整数x；
if(==0) 抛出“”；
if() 抛出“”；
x = 数据[i-1]；
for(int j=i;j
数据[j-1] = 数据[j]；
--;
X;
空白 ：：（）
for(int i=0;i
= 空；
头插入法构造单链表
头插入方式是每次将新申请的节点插入到头节点后面
::(a[], int n)
首先=新节点；
第一个->下一个= NULL；
for (int i = 0; i < n; i++)
节点 *s = 新节点；
s->数据 = a[i];
s->下一个=第一个->下一个；
第一个->下一个 = s;
尾部插入法构造单链表
尾插法是每次将新申请的节点插入到终端节点后面
::(a[], int n)
首先=新节点；
节点 *r = 第一个；
for (int i = 0; i < n; i++)
节点 *s = 新节点；
s->数据 = a[i];
r->下一个=s；
r = s；
r->下一个=NULL；
析构函数
单链表类中的节点是使用new申请的，释放时不能自动释放。 因此，析构函数必须释放单链表中的节点空间。
::~()
而（第一个！= NULL）
节点* q = 第一个；
第一个=第一个->下一个；
q;
计算长度
单链表中无法直接求出长度，所以我们只能扫描一次单链表，所以时间复杂度为O(n)O(n)
整数::()
节点* p = 第一个->下一个；
整数计数=0；
而（p！= NULL）
p = p->下一个；
计数++；
数数;
按位搜索
即使知道单链表中的节点位置，也无法直接访问它。 需要从头指针开始向下一一查找。 平均时间性能为 O(n)O(n)。 单链表是一种顺序访问结构。
::获取(int i)
节点* p = 第一个->下一个；
整数计数=1；
while (p != NULL && 计数
p = p->下一个；
计数++；
if (p == NULL) 抛出“”；
否则p->数据；
按值查找
单链表中按值查找的实现方法与顺序表类似。 链表中的元素按顺序进行比较，平均时间性能为O(n)O(n)。
整数::(x)
节点 *p = 第一个->下一个；
整数计数=1；
而（p！= NULL）
if (p->data == x) 计数；
p = p->下一个；
计数++；
0;
插入
在单链表的插入过程中，需要注意分析表头、表中、表尾三种情况。 由于单向链表取头结点，因此这三种情况的操作语句是相同的。 不需要特殊处理，时间复杂度为O(n )O(n)
无效 ::(int i, x)
节点 *p = 第一个；
整数计数=0；
while (p != NULL && 计数
p = p->下一个；
计数++；
if (p == NULL) 抛出“”；
别的 {
节点 *s = 新节点；
s->数据=x；
s->下一个 = p->下一个；
p->下一个=s；
删除
删除时需要注意表尾的特殊情况。 此时，虽然被删除的节点不存在，但其前驱节点却存在。 因此，只有当被删除节点的前驱节点存在且不是终端节点时，才能判断被删除节点的存在，时间复杂度为O(n)O(n)。
::（整数我）
节点 *p = 第一个；
整数计数=0；
while (p != NULL && 计数
p = p->下一个；
计数++；
if (p == NULL || p->next == NULL) 抛出 "";
别的 {
节点 *q = p->下一个；
int x = q->数据；
p->下一个=q->下一个；
X;
遍历
遍历单链表的时间复杂度是O(n)O(n)。
空白 ：：（）
节点 *p = 第一个->下一个；
而（p！= NULL）
接下来计算数据；
完整代码示例（可以找到更完整的数据结构示例）：
#
使用标准；
节点
数据;
节点*下一个；
};
班级
:
();
(a[], int n);
〜（）；
int();
获取（int i）；
整数（x）；
无效（int i，x）；
(int i);
空白 （）;
:
节点*第一个；
};
::()
首先=新节点；
第一个->下一个= NULL；
::(a[], int n)
首先=新节点；
第一个->下一个= NULL；
for (int i = 0; i < n; i++)
节点 *s = 新节点；
s->数据 = a[i];
s->下一个=第一个->下一个；
第一个->下一个 = s;
::~()
而（第一个！= NULL）
节点* q = 第一个；
第一个=第一个->下一个；
q;
整数::()
节点* p = 第一个->下一个；
整数计数=0；
而（p！= NULL）
p = p->下一个；
计数++；
数数;
::获取(int i)
节点* p = 第一个->下一个；
整数计数=1；
while (p != NULL && 计数
p = p->下一个；
计数++；
if (p == NULL) 抛出“”；
否则p->数据；
整数::(x)
节点 *p = 第一个->下一个；
整数计数=1；
而（p！= NULL）
if (p->data == x) 计数；
p = p->下一个；
计数++；
0;
无效 ::(int i, x)
节点 *p = 第一个；
整数计数=0；
while (p != NULL && 计数
p = p->下一个；
计数++；
if (p == NULL) 抛出“”；
别的 {
节点 *s = 新节点；
s->数据=x；
s->下一个 = p->下一个；
p->下一个=s；
::（整数我）
节点 *p = 第一个；
整数计数=0；
while (p != NULL && 计数
p = p->下一个；
计数++；
if (p == NULL || p->next == NULL) 抛出 "";
别的 {
节点 *q = p->下一个；
int x = q->数据；
p->下一个=q->下一个；
X;
空白 ：：（）
节点 *p = 第一个->下一个；
而（p！= NULL）
接下来计算数据；
int main()
p;
p.(1, 6)；
p.(2, 9)；
p.();
p.(2, 3)；
p.();
库特
