线性表

什么是线性表

线性表一般是由相同的数据类型的若干（n）个数据元素构成的有限序列，如果里面没有元素，则称之为空表。如果用L命名线性表，一般表示为:

$$ L=（a_1,a_2,…,a_i ,a_{i+1},…,a_n) $$

其中用n为表长，当n=0时线性表为一空表。

在式子中，$a_1$是唯一的第一个数据元素，也被称作表头元素。同理$a_n$ 是唯一的最后一个数据元素，也就被称为表尾元素。除第一个元素外，每个元素都有且仅有一个直接前驱，除最后一个元素外，每个元素又有且仅有一个直接后继。故而线性表具有线性有序的逻辑结构。

据此我们很容易就得到了线性表的特点：

• 个数有限
• 逻辑有序
• 每个元素都素单个的数据元素
• 数据类型相同（意味着他们每一个元素都应占用相同大小的存储空间）
• 抽象（无论他们什么内容，线性表都是一种元素之间的逻辑关系）

线性表的每个数据的类型都是相同的，每个元素都应有其前后的对应关系，当然，第一个数据没有前面的元素，最后一个没有后面的数据。

线性表的操作也很简单，创建/初始化一个线性表、销毁一个线性表、将线性表置空、判断线性表是否是空的、线性表元素的个数、返回表中第几个元素的值（按位查找）、返回第一个与传入值相同的值（按值查找）、返回他的下一个值（后继）（除最后一个）、返回他的（前驱）前一个（除第一个）、插入一个值、删除一个值、遍历这个表

很多不同的书籍对于其操作都是是有不同理解的，但是基础操作例如：初始化，删除，置空，插入值，返回值，遍历，查找等，都是不可缺少的，通过组合基本的操作来实现自定义的操作。

线性表的顺序存储结构

顺序表的定义和地址

线性表的顺序存储结构又叫做顺序表，他用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的两个元素，再计算机中的物理位置也相邻。第一个元素存储在顺序表的起始位置。第i个元素的存储位置的下一个也一定是第i+1个元素，那么这个i为元素$a_{i}$在顺序表中的位序。因此，顺序表的特点就是表中元素的逻辑顺序与其存储的物理顺序相同。

对于线性表他的物理地址一般是相邻的，可以很容易地计算其存储位置：
如果每个元素需要n个存储单元，以第一个数据所在位置的存储地址为存储起始位置，则第i+1个元素的地址和第i个元素的存储位置满足下列关系：¹

$$ LOC(a_{i+1})=LOC(a_i)+sizeof(ElemType) $$

类比推算（等差数列也可）得出：

$$ LOC(a_i)=LOC(a_1)+(i-1)*sizeof(ElemType) $$

通过这个公式可以得知，可以随意算出任一位置的地址，他们都是相同的时间，每个数据元素的存储位置和顺序表的表头元素相差一个和位序成正比的常数，所以在存入和取出数据的时候所消耗的时间都是常数的，复杂度即为O(1)，通常把这种特性的结构称之为随机存取结构，故而线性表的顺序存储结构是一种随机存取的存储结构。

通常利用数组描述线性表的顺序存储结构，但是，线性表中元素的位序从1开始，然而数组的元素下表却是从0开始的。

存储结构描述

#define MAXSIZE 20 //先行不熬自打长度
typedef struct
{
    ElemType data[MAXSIZE];//此处的ElemType 可以换成任意一种数据类型(例如：int/float/char)//表中的元素
    int length;//长度
}List;//(线性表)

由此我们能看到，数组data是存储数据的存储位置，他有一个最大的存储容量MAX=20，一个数据用来记录这个表的长度。

这里有个地方就是MAXSIZE是指的是这个数组所占空间长度为20，是预先分配的存储空间长度，而length指的是有数据的长度，也就是表的长度。

当然一维数组可以是静态分配的，也可以是动态分配的。对数组进行静态分配的时候，数组的大小/空间已经事先定义好了，一旦空间满了再加入新的数据就会溢出。

刚才的代码是一种静态存储的方式，在动态分配的时候，存储数组的空间实在程序执行的时候通过动态存储分配语句分配的，一旦满了，就在开一块更大的空间，原先的数据全部拷贝到新空间中，从而达到扩充数组存储空间的目的，而非为线性表一次性划分所有空间。参考如下代码描述：

#define InitSize 100 //表初始空间100
typedef struct{
    ElemType *data;//动态分配数组的指针
    int MaxSize;//最大容量
    int length;//表长度
}List

在C语言中可以用malloc来获取空间，故而初始定义语句如下：

List L;//定义一个新的顺序表
L.data=(ElemType* )malloc(sizeof(ELemType) * InitSize);

在C++的语句就如下所示：

List L;
L.data= new ElemType[InitSize];

很显然C++更容易懂一些。

书中说，动态分配并不同于链式存储，他依旧具备随机存储的特性。

顺序表的特点很明显：

• 随机访问，首地址+位序就可以在常数时间内找到
• 存储密度很高，不像链式存储需要存储指针域
  缺点也很明显：
• 插入/删除操作需要移动元素。复杂度分析见后
• 需要一块连续的存储空间（不灵活）

顺序表中各种基础操作的实现

笔记约定：全文对于C++写起来更好的代码，我会尽量使用C++语法，比如如下的bool：

#define OK 1
#define ERROR 0
typedef int Status;
//之后把所有bool的地方改成Status,return的值分别为OK 和 ERROR

开始前的准备

//头文件
#include<iostream>
//我们把自定义数据类型(ElemType)设置为int 
#define ElemType int
//顺序表的定义
#define MAXSIZE 20
typedef struct
{
    int data[MAXSIZE];//此处的int 可以换成任意一种数据类型
    int length;
}List;//(线性表)

初始化操作

以动态分配为例

void InitList(List &L){
     L.data = new ElemType[IniSize];//动态分配存储空间
     L.length=0;//静态分配只需要这个就可以，设置当前表长为0
     L.MaxSize=InitSize//初始容量
}

插入操作

//插入操作
 bool ListInsert(List *L,int i,ElemType e)//e还是这个线性表的数据类型
 {
     if(L->length>=MAXSIZE) return false;//表示表满了，应该返回一个false
     if(i<1||i>L->length+1) return false;//此举判断i是否符合插入要求

    for(int k=L->length;k>=i;k--)
    {
         L->data[k]=L->data[k-1];//依次后移
    }
     L->data[i-1]=e;
     L->length++;
     return true;
 }

Warning: 顺序表位序从1 开始，而数组下标从0开始，故而k=L->length就代表着表示这个表的数组最后一个元素的下一个值

复杂度分析：

假设$p_{i}$是在第i个元素之前插入一个元素的概率，$E_{insert}$为长度为n的线性表插入一个元素所需移动元素次数的期望值（平均次数），则有：

$$ E_{insert}=\sum^{n+1}_{i=1}p_i(n-i+1) $$

每个位置插入是等概率的p=1/(n+1)

则：

$$ E_{insert}=\frac{1}{n+1}\sum^{n+1}_{i=1}(n-i+1)=\frac{n}{2} $$

所以，插入算法的平均复杂度为$O(n)$。

也很好理解，最好情况就是移动0次，最坏情况就是移动n次，故而平均次数为n/2。

删除操作

我看书中还要还要返回这个值，可以通过传入一个引用参数传回，不写了。

//删除操作
bool ListDelete(List *L,int i)
{
    //在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.length 
    if((i<1)||(i>L.length)) return false; //i值不合法 
    for(j=i;j<=L.length;j++) L.data[j-1]=L.data[j];
    //被删除元素之后的元素前移
    L.length--; 
    return OK;
}

还要注意刚才的位序和数组下标之间的关系

复杂度分析：

删除和插入都是相似的都在于其时间都在移动元素之上，同理假设所有位置删除的概率为相同，p=1/n，则：

$$ E_{delete}=\frac{1}{n}\sum^n_{i=1}(n-i)=\frac{n-1}{2} $$

因此啊，时间复杂度还是$O(n)$。

再一个就是，删除尾部移动0次，删除头部移动n-1次，平均还是(n-1)/2。

获取某个位置元素（按位查找）

按位查找有点脱裤子放屁，其实可以直接根据下标返回值的，这是随机存储特性啊！

bool GetElem(List L,int i,ElemType& e)//此处的e代表我要返回的值，数据类型需要自己去改变
{
    if(L.length==0||i<1||i>L.length) return false;
    *e=L.data[i-1];//这里减一的原因我i传入的应该从1开始计数，而不是像数组一样从0开始计数
    return true;
}//代码用到了Bool类型判断这个函数是否能正常运行

按值查找

//查找
int Locate(List L,ElemType e)
{
    for(int i=0;i<L.length;i++)
    {
        if(L.data[i]==e) return i+1;
    }
    return 0;//没找到    
}

复杂度分析：

查找用ASL（平均查找长度）来进行讨论，假设pi 是查找第i个元素的概率，Ci 为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数，则在长度为n的线性表中，查找成功时的平均查找长度为:

$$ ASL=\sum_{i=1}^0p_iC_i $$

假设每个元素被找到的概率为相同的：

$$ p_i=\frac{1}{n} $$

那么可以简化成：

$$ ASL=\frac{1}{n}\sum_{i=1}^0i=\frac{n+1}{2} $$

故顺序表按值查找算法的平均时间复杂度为O(n)。

还可以这么理解：正好在表头找1次，表尾找n次，平均(n+1)/2。

线性表的链式存储结构

顺序表存储位置很直观/很简单就可以被计算，它可以随机存取表中任意一个元素，但是删除和插入需要移动大量元素，然而链，顾名思义，它使用链来建立元素之间的关系，所以删除和插入都仅需要修改指针，当然也就失去了顺序表随机存取的特性

单链表的定义及其代码描述

线性表的链式存储结构特点是：用一组任意的存储单元来存储线性表的元素（区别于线性表，这组空间可连续，也可不连续），所以，要表示这个元素和他后一个元素之间的相互关系，除了存储他本身的数据外，我们还需要存储一个指示他的后继的信息。这两者共同组成的内容我们称之其为节点，它包括两个域，他存储数据元素信息的域称之为数据域，存储他的后继位置的域称之为指针域。若干个节点链接成为一个链表，则可称之其为线性表的链式存储结构，又因为只包含一个指针域，又称之其为线性链表或单链表。

也就是说啊，这个链式存储结构包含一个数据和一个指向下一个元素的指针，所以，用C/C++的想法来写如下所示:

typedef struct LNode{
    Elemtype data;//数据域，自定义数据类型
    struct LNode *next;//指针域，同时为了保证C语言同样能运行，要声明LNode是一个结构体
}LNode, *LinkList;

单链表可以解决顺序表需要大量连续的存储单元的缺点，但是其比顺序表多出来的指针域，其实也在浪费空间，这是他的一个缺点。单链表各个元素离散地分布在存储空间中，因此它具有非随机存储的存储结构，那也就也意味着，如果要查找特定结点的话，需要从头开始遍历，依次查找

同时，为了方便，单链表一般会引入一个头节点（文学造纸很高：节点/结点傻傻分不清楚），其data不赋值，他的next指向首元结点（就是第一个有数据的结点）。他主要目的就是标识一个链表，指出其起始地址，这个结点也就是头结点。在记录的时候，头节点可以存储一些例如表长的一些信息，当指针域为空（NULL）的时候（尾结点），可以使用“^”表示。

头结点和头指针：无论是否有头结点，头指针一定指向链表的第一个节点，头结点是带头结点的链表的第一个结点，通常数据域为NULL。引入这个所谓的头结点能给我们带来如下好处：

• 第一个结点的一些操作和其他节点的操作一致，参考基本操作实现
• 无论链表是否为空，头指针一定指向了头结点的非空指针（空表的头结点的指针域就为空），因此空与非空表的处理也就得到了统一

单链表的基本操作实现

准备工作（头文件等）

#include<iostream>
using namespace std;
typedef int Elemtype;//设置自定义类型为int
//引入定义
typedef struct LNode{
    Elemtype data;//数据域，自定义数据类型
    struct LNode *next;//指针域，同时为了保证C语言同样能运行，要声明LNode是一个结构体
}LNode, *LinkList;

初始化(Init)

bool InitLinkList(LinkList &L)//传入一个地址
{
    L=new LNode;//创建一个新的结点
    L->next=NULL;//或L->next=nullptr;
    return true;
    /*
    //不带头结点的初始化
    L=NULL:
    retrun true;
    */
}

求表长

//计算结点个数
int Length (LinkList L)
{
    int len = 0;
    LNode *p = L;
    while(p->next!=NULL)
    {
        p=p->next;
        len++;
    }
    retunr len;
}

时间复杂度O(n)，注意此代码为带头结点求个数，如果不带头结点那么就是判断while(p!=NULL)了；

获取某个位置的值（按位查找）

bool GetElem(LinkList L,int i,Elemtype &e)
{
    LNode *p=L->next;
    int j=1;//头结点是第0，那么第一个结点就是第一个。
    while(p&&j<i)//这一步想要让这个p到达i位置，直接判(p)就是指p不为NULL
    {
        p=p->next;
        j++;
    }
    if(!p||j>i) return false;//i值不可以大于0，或者当p一定到头了，但是还是没有取到i，也要返回false，!p就是p为NULL
    e=p->data;//取i结点的数据
    return true;
}

注意本代码中是带头节点的链表

此代码复杂度分析：

还是按照我们的，还是假设每一个被取值的概率相等，每次取值都需要执行i-1次p=p->next，根据之前的公式:

$$ ASL=\frac{1}{n}\sum^n_{i=1}(i-1)=\frac{n-1}{2} $$

由此单链表的取值算法复杂度为O(n)。

按值查找

LNode *LOCATE(LinkList L,Elemtype e)//查找第一个值等于e的函数
{
    LNode* p=L->next;
    while(p&&p->data!=e) p=p->next;
    return p;//如果没找到我们就返回NULL，这串代码执行到最后没找，会到达p=NULL;
}

算法复杂度同上，仍为O(n)。

插入结点

bool ListInsert(LinkList &L,int i,Elemtype e)
{
    LNode *p=L;
    int j=0;
    while(p->next&&(j<i-1))
    {
        p=p->next;
        j++;
    }
    if(!p||j>i-1) return false;//这种情况就是i<1和i的值超过了链长
    LNode *s=new LNode;
    s->data=e;
    s->next=p->next; //操作1
    p->next=s; //操作2
    return true;
}

注意代码操作顺序，操作1和2不可颠倒位置互换。

此代码复杂度类似于获取某个位置的值（按位查找）的算法，因为都要找到i这个位置，复杂度为O(n)。

删除结点

bool ListDelete(LinkList &L,int i)
{
    LinkList p = L;
    int j = 0;
    while ((p->next) && (j < i - 1))
    {
        p = p->next;
        j++;
    }
    if (!(p->next) || (j > i - 1))//删除位置不合理就要返回一个不正确的值
    {
        return false;
    }
    LinkNode *s = p->next;//保存需要被删除的节点，方便后面的释放
    p->next = s->next;
    free(s);
    return true;
}

类似插入算法，复杂度为O(n)。

头插/尾插法建立单链表

创建单链表，这个思路就是，当我们输入一个数据，新建一个节点，数据域就是我们输入的数据，指针域指向后继，当然，创建单链表还分为前插法和后插法，前插法顾名思义，当我创建了一个新的结点想要插入链表的时候，（头节点）L->next=新的结点，他的指针域指向上一个结点，后插法相反，代码示例：

void CREATE_H(LinkList &L,int n)//前插n个元素
{
    L=new LNode;
    L->next=NULL;
    for(int i=0;i<n;i++)
    {
        p=new LNode;
        std::cin>>p->data;//输入数据域
        p->next=L->next;
        L-next=p;//更改头节点指向
    }
}

复杂度分析：每个结点插入的时间为O(1)，但是需要插入n个元素，总的时间也是O(n)。这种情况插入的顺序可能和输入顺序不符，可以用来实现链表逆置。

对于没有头结点的头插法，还啊哟注意，每次插入新节点后，都需要将他的地址赋值给L

void CREATE_T(LinkList &L,int n)//后插法
{
    L=new LNode;
    L->next=NULL;
    LNode *r=L;
    for(int i=0;i<n;i++)
    {
        p=new LNode;
        std::cin>>p->data;//输入数据域
        p->next=NULL;
        r->next=p;
        r=p;//更改头节点指向
    }
}

复杂度分析：如果L是尾指针，那么就是和上面同样的分析思路。

双向链表

双向链表他有个直接前驱和后继，这样他的指针域就包含了两个指针，一个前驱，一个后继，其他和正常链表无差别。但是要注意的是，他的头节点的指针域指向的是第一个元素，而不是第一个元素的前驱。删除的时候，需要修改4个指针。

代码描述如下所示：

typedef struct DNode{
    ElemType data;//数据域
    struct DNode *prior,* next;//前驱/后继
}

在双向链表中，有些操作（如ListLength、GetElem和LocateElem等）仅需涉及一个方向的 指针，则它们的算法描述和线性链表相同，但在插入、删除时有很大的不同，在双向链表中进 行插入、删除时需同时修改两个方向上的指针，在插入节点时需要修改4个指针，在删除节点时需要修改两个指针。两者的时间复杂度均为O(n)。

插入操作：

//将s结点插入到p之后
s->next=p->next;//s插入p的后面
p->next->prior=s;//p的下一个结点的前驱指向待插入结点s
s->prior=p;//s前指于p
p->next=s;//p指向s

顺序不唯一，但不任意，比如p->next指向s这步，一定要在s->next=p->next。

删除操作：

//删除q
p->next=q->next;
q->next->prior=p;
free(q);

循环链表

循环链表是另外一种链式的存储结构，他的最后一个结点指向头节点，这样构成了一个环，差别在于，以前我们需要判结束，直接P->next==NULL就是结尾了，现在变成了p->next==L才是结束。

循环单双链表的基本操作和各自的操作是相同的，而且还不需要判定是否在表尾。

循环链表还可以设置头尾指针，这样无论尾插还是头插法都只需要O(1)复杂度。

静态链表

静态链表是用数组描述的线性表的链式存储结构，结点也有数据域和指针域，这里的指针域指的是在数组的相对地址，也称作游标。描述如下：

#define MAXSIZE 50//最大值
typedef struct{
    ElemType data;//数据域
    int next;//指针域
}SLinkList[MAXSIZE]；

next == -1时为结束标志。

顺序表和链表之间的性能分析

全文参考：[1]严蔚敏,李冬梅,吴伟民.数据结构(C语言版) [J].计算机教育, 2012(12):1.DOI:CNKI:SUN:JYJS.0.2012-12-017.

（1）存储空间的分配顺序表的存储空间必须预先分配，元素个数有一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。 基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。

（2）存储密度的大小
链表的每个节点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指 示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个节点结构所占用的存储量之比，即：

$$ 存储密度=\frac{数据元素本身占有的存储量}{节点结构占用的数据量} $$

存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。如果每个元素数据域占据的空间较小，则指针的结构性开销就占用了整个节点的大部 分空间，这样存储密度较小。例如，若单链表的节点数据均为整数，指针所占用的空间和整型 量所占用的相同，则单链表的存储密度为0.5。因此，如果不考虑顺序表中的空闲区，则顺序表 的存储空间利用率为100%，而单链表的存储空间利用率仅为50%。基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

时间性能的比较

（1）存取元素的效率，顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号i，都可以在O(1)时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n)，即取值操作的效率低。基于此，若线性表的主要操作是和元素位置紧密相关的一类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。

（2）插入和删除操作的效率，对于链表，在确定插入或删除的位置后，插入或删除操作无须移动数据，只需要修改指针，时间复杂度为O(1)。而对于顺序表，进行插入或删除时，平均要移动表中近一半的节点， 时间复杂度为O(n)。尤其是当每个节点的信息量较大时，移动节点的时间开销就相当可观。基于此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。