线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。
1.线性表的顺序表示和实现
线性表的顺序表示指的是用一段地址连续的存储单元依次存储线性表的数据元素。特点：逻辑上相邻的数据元素，其物理次序也是相邻的。
和数组不一样，
数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。线性表长度是线性表中数据元素的个数，随着插入和删除的操作，长度会变。所以，这里要区分两个概念，即数组长度和线性表的长度是不一样的。在任意时刻，线性表的长度应该小于等于数组的长度。
(1) 存储方式
因为每个数据元素的类型都相同，所以可以使用一维数组来实现。结构代码如下：
//线性表的顺序存储结构
#define MAXSIZE 20;//存储空间初始分配量为20
typedef int ElemType;//数据类型为int
type struct
{
ElemType data[MAXSIZE];//数组存储数据元素
int length;//线性表长度
}SqList;
顺序存储结构需要三个属性：
- 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量：数组长度MaxSize。
- 线性表的当前长度：length。
(2) 地址计算方法
若每个存储元素占用c个存储单元，那么线性表中元素的位置可以由此计算出：LOC(ai) = LOC(a1)+(i-1)*c
通过这个公式，可随时算出线性表中任意位置的地址，使用相同的时间。它的存取时间性能为
O（1），这一特点的存储结构称之为随机存取结构。
(3) 顺序表的基本操作
1. 获取元素：
#define MAXSIZE 20 //存储空间初始分配量
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType; //ElemType类型根据实际情况而定，这里设为int
Status GetElem(SqList L, int i, ElemType &e){//获取元素
if (L.length == 0 || i<1 || i>L.length){
return ERROR;
}
e = L.data[i - 1];
return OK;
}
2. 插入元素:
在第i（1<= i <=n）个位置插入一个元素时，需从最后一个元素开始一次向后移动一个位置，直至第i个元素
（共n-i+1个元素）。
- 如果插入位置不合理，抛出异常。
- 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量。
- 从最后一个元素开始向前遍历到第i个位置，分别将它们向后移动一个位置。
- 将要插入元素填入位置i处。
- 表长度加1。
Status ListInsert(SqList L, int i, ElemType e){//插入操作
int k;
if (L.length == MAXSIZE){//顺序线性表已满
return ERROR;
}
if (i<1 || i>L.length + 1){//当i不在范围内时
return ERROR;
}
for (k = L.length - 1; k >= i - 1; k--)
{
L.data[k + 1] = L.data[k];
}
L.data[i - 1] = e;//将新元素插入
L.length++;
return OK;
}
3. 删除元素：
删除第i个（1<= i <=n）个元素时需要将第i+1个至第n个元素
（共n-i个元素）依次向前移动一个位置。
- 如果删除位置不合理，抛出异常。
- 取出删除元素。
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置。
- 表长减1。
Status ListDelete(SqList L, int i, ElemType *e){//删除操作
int k;
if (L.length==0){//线性表为空
return ERROR;
}
if (i<1 || i>L.length + 1){//删除位置不正确
return ERROR;
}
*e = L.data[i - 1];
for (k = i; k < L.length; k++)
{
L.data[k - 1] = L.data[k];
}
L.length--;
return OK;
}
(4 )时间复杂度
在存、读数据时，不管是哪个位置，时间复杂度都是O（1）；而插入或删除操作时，时间复杂度都是O（n）。
(5) 优缺点
优点：
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速地存取表中任一位置的元素。
缺点：
- 插入和删除操作需要移动大量元素。
- 当线性表长度变化较大时，难以确定存储空间的容量。
- 造成存储空间的“碎片”。
2. 线性表的链式表示和实现
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素，可以连续，也可以不连续。
(1) 首元结点、头结点、头指针
首元结点：链表中存储第一个数据元素a1的结点。头结点：头结点是首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储域数据元素类型相同的其他附加信息。例如，当数据元素为整数时，头结点的数据域中可存放该线性表的长度。头指针：头指针指向链表中第一个结点的指针。若链表有头结点，则是指向头结点的指针。若链表不设头结点，则头指针为该线性表的首元结点。
(2) 线性表链式存储结构
typedef struct Node{//线性表的单链表存储结构
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;//定义LinkList
(3) 单链表的基本操作的实现
1. 单链表的读取
- 声明一个结点p指向链表第一个结点，初始化j从1开始。
- 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
- 若到链表末尾p为空，则说明第i个元素不存在。
- 否则查找成功，返回结点p的数据。
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType &e)
{
int j;
LinkList p; /* 声明一结点p */
p = L->next; /* 让p指向链表L的第一个结点 */
j = 1; /* j为计数器 */
while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */
{
p = p->next; /* 让p指向下一个结点 */
++j;
}
if ( !p || j>i )
return ERROR; /* 第i个元素不存在 */
e = p->data; /* 取第i个元素的数据 */
return OK;
}
说白了，就是从头开始找，直到第i个元素为止。最好情况的时间复杂度为O（1），最坏情况的时间复杂度为O（n）。
2. 单链表的插入
① s->next = p->next;
② p->next = s;
- 查找结点a(i-1)并由指针p 指向该结点
- 声明一个结点p指向链表第一个结点，初始化j从1开始
- 当j<i-1时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
- 若到链表末尾p为空，则说明第i-1个元素不存在
- 否则查找成功，在系统中新生成一个空结点s
- 将数据元素e赋值为s->data
- 单链表的插入标准语句s->next=p->next;p->next=s;
- 返回成功
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList &L,int i,ElemType e)
{
int j;
LinkList p,s;
p = L;
j = 1;
while (p &&( j < i-1)) /* 寻找第i个结点 */
{
p = p->next;
++j;
}
if (!p ||( j > i-1))
return ERROR; /* 第i个元素不存在 */
s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */
s->data = e;
s->next = p->next; /* 将p的后继结点赋值给s的后继 */
p->next = s; /* 将s赋值给p的后继 */
return OK;
}
3. 单链表的删除
p->next=p->next->next;
- 查找结点a(i-1)并由指针p指向该结点
- 临时保存待删除结点ai的地址在q 中，以备释放。
- 将结点＊p的指针域指向ai的直接后继结点。
*释放ai的空间。
Status ListDelete(LinkList &L,int i,ElemType &e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && (j < i-1)) /* 遍历寻找第i个元素 */
{
p = p->next;
++j;
}
if (!(p->next) ||( j > i-1))
return ERROR; /* 第i个元素不存在 */
q = p->next;
p->next = q->next; /* 将q的后继赋值给p的后继 */
e = q->data; /* 将q结点中的数据给e */
delete q; /* 让系统回收此结点，释放内存 */
return OK;
}
4. 单链表操作的时间复杂度
分析单链表的插入和删除算法，第一步就是遍历查找到第i个元素；第二步就是插入和删除元素。容易看出，它们的
时间复杂度都是O（n），如果在不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O（n）,而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O（n）,接下来只是简单地通过赋值移动指针而已，时间复杂度都是O（1）。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显
5. 创建单链表
（1） 前插法：
- 创建一个只有头结点的空链表。
- 根据待创链表包括的元素个数n, 循环n次执行以下操作：
- 生成一个新结点＊p。
- 输入元素赋值给新结点＊p的数据域。
- 将新结点＊p插入到头结点之后。
void CreateList_H(LinkList &L,int n )
{
//逆序输入n个元素的值，建立带表头结点的单链表L
L ＝ new LNode; // 建立一个带头结点的空链表
L->next = NULL;
for(i=0;i<n;i++)
{
p = new LNode; //生成新结点＊p
cin>> p->data; //输入元素值赋给新结点＊p的数据域
p->next = L -> next;
L->next = p;
}
}
（2） 尾插法：
- 创建一个只有头结点的空链表。
- 尾指针r初始化，指向头结点。
- 根据待创链表包括的元素个数n, 循环n次执行以下操作：
- 生成一个新结点＊p。
- 输入元素赋值给新结点＊p的数据域。
- 将新结点＊p插入到尾结点＊r之后。
4.尾指针r指向新的尾巴结点＊p。
void CreateList_H(LinkList &L,int n )
{
//逆序输入n个元素的值，建立带表头结点的单链表L
L ＝ new LNode; // 建立一个带头结点的空链表
L->next = NULL;
r = L; // 尾指针r指向头结点
for(i=0;i<n;i++)
{
p = new LNode; //生成新结点＊p
cin>> p->data; //输入元素值赋给新结点＊p的数据域
p->next = NULL;
r->next = p;
r = p;
}
}
6. 单链表的整表删除
- 声明一结点p和q
- 将第一个结点赋值给p
- 循环：
- 将下一结点赋值给q
- 释放p
- 将q赋值给p
Status ClearList(LinkList &L)
{
LinkList p,q;
p=L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
delete p;
p=q;
}
L->next=NULL; /* 头结点指针域为空 */
return OK;
}
3. 单链表结构与顺序存储结构优缺点
单链表结构和顺序存储作对比：
(1)
空间性能：
--顺序存储结构需要预分配存储空间，分大了，浪费空间，分小了，容易发生溢出。
--单链表不需要分配存储空间，只要有就可以分配，元素个数不受限制。
(2)时间性能:
--查找： 顺序存储结构O(1),单链表结构O(n)。
--插入和删除:
-- 顺序存储结构需要平均移动表一半的元素 时间为 O(n)。
-- 单链表在计算出某位置的指针后，插入和删除时间为O(1)。
注：单链表，多次操作，第一次插入删除为O(n),之后的都为O(1)；顺序都为O(n)。
(3)存储分配方式：
-- 顺序存储结构用一段连续的存储单元依次存储线性表的数据单元。
-- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
(4)存储密度：
--顺序存储结构不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1。
--单链表需要借助指针来体现元素间的逻辑关系，存储密度小于1。
总结：
- 若线性表需要频繁查找，很少进行插入、删除操作，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如游戏开发中，用户注册的个人信息，除注册时插入数据外，绝大多数是读取，所以应该考虑顺序存储结构。而玩家的武器或装备列表，可能随时增加或减少，这时可以考虑单链表结构。
- 当线性表中的元素个数变化较大或根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而事先知道线性表的大致长度，比如一年12个月，这种用顺序结构效率会高很多。
4. 循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
循环链表解决了一个问题：如何从当中一个结点出发，访问到链表的全部结点。
为使空链表与非空链表处理一致，通常设置一个头结点。
循环链表和单链表的主要差异就在于循环的条件判断上，原来是p->next是否为空，现在是
p->next不等于头结点，则循环未结束。
- 如果用头指针表示循环链表，则需O（n）时间找到最后一个结点。若改用尾指针表示循环链表，此时查找开始结点和终端结点都很方便了。
- 此时若尾指针用rear指示，则查找终端结点时间是O（1），而开始结点，其实就是rear->next->next，其时间复杂也为O（1）。
循环链表的合并：
两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点。然后释放第二个表的头节点。
rearA->next = rearB->next->next;
rearB->next = A->next;
p = rearB->next;
delete p;
5 .双向链表
在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
双向链表的插入删除
插入：
status ListInsert_DuL(DuLinkList &L ,int i,ElemType e)
{
//在带头结点的双向链表L中的第i个位置之前插入元素e
if(!(p=getElem_DuL(L,i))) return ERROR;//在L中确定第i个元素的位置指针p
s = new DuLNode;
s->data = e;
s-> prior = p -> prior;
s-> prior -> next = s;
s -> next = p;
p->prior = s;
return OK;
}
删除：
status ListDelete_DuL(DuLinkList &L ,int i,ElemType e)
{
//删除带头结点的双向链表L中的第i个元素
if(!(p=getElem_DuL(L,i))) return ERROR;//在L中确定第i个元素的位置指针p
p-> prior ->next = p -> next;
p-> next -> prior = p-> prior;
delete p;
return OK;
}
