数据结构线性表

线性表的定义与基本操作

线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。
若用L命名线性表，则其一般表示为L=(a1,a2,…,ai,ai+1,…an)
表达式中a1是唯一第一个数据元素，又称为表头元素；an是唯一的最后一个数据元素，又称为表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后驱。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆

线性表的基本操作

InitList(&L): 初始化表。构造一个空的线性表。
Length(L): 求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e): 删除操作。删除表中L中第i个位置的元素，并用e返回删除的元素。
PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L): 判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

注意：基本操作的具体实现取决于采用哪种存储结构（见下图）,存储结构不同，算法的实现也不同."&"表示C++语言中的引用调用,在c语言中采用指针也可以达到相同的效果.后续文章中两种方式都会使用.

顺序表

顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为：

#define MaxSize 10  //定义顺序表的最大长度，在声明数组时使用
typedef struct{
    ElemType data[MaxSize];//顺序表的数据元素
    int length;//顺序表的当前长度
}Sqlist;//顺序表的类型定义

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定好，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序奔溃甚至引起其他未知异常。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦存储空间占满，就另外开辟一块更大的存储区间，将原来的元素复制过去，从而达到扩充存储数组空间的目的，而不需要一次性分配很大的空间。
C语言的初始动态分配语句为：

1	L.data = (ElemType)malloc(sizeof(ElemType)InitSize);

C++语言的初始化动态分配语句为：

1	L.data=new ElemType[InitSize];

注意：动态存储并不是链式存储，它同样属于顺序存储，物理结构没有变化，还是和逻辑结构一样保持相邻，只是分配的空间不再是编译器决定，而是运行时分配。

顺序表的特点

随机访问：可通过首地址和元素序号在单位时间O(1)内找到指定的元素。

存储密度高：存储密度高是因为每个结点存储空间指用来存储数据元素，没有别的额外开销。

物理位置相邻：物理位置和逻辑位置一样，保持相邻，因此插入和删除元素需要移动大量元素，比较耗时。这是物理结构相邻的所有数据结构的通病，虽然访问快，但是如果有频繁的增删移动操作，就会效率很低。

顺序表上的基本操作

仅展示查、增、删三种操作，其余的在线性表中较为简单，在后续更复杂的链表中展示。

插入操作

在顺序表L的第i（1<=i<=L.length+1）位插入新元素e。

bool ListInsert(SqList &L, int i, ElemType e) 
{
    if (i<1 || i>L.length + 1)  //判断i要插入的位置是否有效
        return false;
    if (L.length >= MaxSize)   //判断是否超出存储空间
        return false;
    for (int j = L.length; j >= i; j--)  //将第i个元素以及之后的元素后移一位
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;   //在第i位插入元素e
    L.length++;     //顺序表长度加1
    return true;
}

最好情况：在表尾插入（即i=n+1）,原本的元素不移动，时间复杂度为O(1)。

最坏情况：在表头插入（即i=1），所有元素需要后移一位，元素后移语句执行n次，时间复杂度为O(n)。

平均情况：假设Pi(Pi=1/(n+1))是在第i个位置上插入一个结点的概率，则在长度为n的顺序表中插入一个结点时，所需要移动结点的平均次数为n/2，时间复杂度为O(n)。

删除操作

删除顺序表L中第i（1<=i<=L.length）个位置的元素。

bool ListDelete(SqList &L, int i, ElemType& e) 
{
    if (i<1 || i>L.length)  //判断i要插入的位置是否有效
        return false;
    e = L.data[i - 1];     //保存要删除的数据到e
    for (int j = i-1; j <= L.length; ++j)  //将第i个元素以及之后的元素后移一位
        L.data[j] = L.data[j + 1];
    L.length--;     //顺序表长度加1
    return true;
}

时间复杂度与插入一样（平均时间复杂度上，插入始终每一步比删除多一次操作，即插入操作，但是不会引起量级变化，所以平均时间复杂度依旧为O(N)）

按值查找（顺序查找）操作

在顺序表中查找第一个元素值等于e的元素的位置，未查找到返回-1

int LocateElem(SqList L,const ElemType &e) 
{
    int i;
    for (i = 0; i < L.length; ++i) 
    {
        if (L.data[i] == e)
        {
            return i + 1;
        }        
    }
    return -1;
}

最好情况：在表头找到（即i=1）,时间复杂度为O(1)。

最坏情况：在表尾插入（即i=n），时间复杂度为O(n)。

平均情况：时间复杂度为O(n)。

线性表的链式表示

逻辑上相邻的元素在物理位置上不一定相邻。
优点：

没有了顺序存储所具有的弱点（也就是说：插入和删除不需要移动元素，而只需要修改指针。）
同时，由于不借助数组实现，在定义链表时，无需指定它的长度。

缺点：
也失去了顺序存储的优点

非随机存取（不能直接找到某个特定序号的结点，需要从表头开始遍历）
存储密度降低（除了存储本身信息外链表还要存储指针）

单链表的定义

线性表的链式存储又称为单链表，它是指通过一组任意的存储单位来存储线性表中的元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素的自身信息外，还需要存放一个指向其后继的指针。

由于逻辑上相邻的元素在物理位置上不一定相邻，那么我们如何确定下一个元素的存储位置呢？
解决办法，增加一个变量。用来存储一个指示其后继位置的指针。
我们把这两部分的信息组成数据元素a的存储映像，称为结点。它包含两个域，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

单链表中结点定义如下：

typedef struct LNode{ //定义单链表节点类型
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode,*LinkList;

头指针
整个链表的存储必须从头指针开始
头指针指示链表中第一个结点的存储位置
同时，由于最后一个数据元素没有直接后继，则单链表中最后一个一个结点的指针为NULL

//头指针定义1
LinkList L;
//头指针定义2
LNode *L;

头结点
在单链表的第一个结点之前附设一个结点，称为头结点。
头结点的数据域可以不存储任何信息，也可以存储如线性表的长度之类的附加信息。
头结点的指向第一个结点的指针（即第一个元素结点的存储位置）
此时，单链表的头指针指向头结点。

空表
含头结点

1 2	LinkList L; L->next==NULL时为空表

不含头结点

1 2	LinkList L; L==NULL时为空表；

单链表上具体操作的实现和时间复杂度

初始化表

构造一个空表

int InitList_Link(LinkList *L){
    *L=(LinkList)malloc(sizeof(LNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->next=NULL;//初始化为空
    return TRUE;//初始化成功
}
时间复杂度为O(1)

根据数组创建单链表

含头结点的单链表

//头插法
int create_HeadInsert(LinkList *L,ElemType a[],int n){
 // InitList_Link(L);
    LNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(LinkList)malloc(sizeof(LNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        s->next=(*L)->next;//让该结点指向第一个结点
        (*L)->next=s;//让头结点指向该结点
    }
}

//尾插法
int create_TailInsert(LinkList *L,ElemType a[],int n){
 // InitList_Link(L);
    LNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){//遍历数组
        s=(LinkList)malloc(sizeof(LNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
        r=s;//r移动到链表尾端
    }
    r->next=NULL;//结束时，最后一个结点的指针域赋值为空
}

不含头结点的单链表

//头插法
int create_HeadInsert(LinkList *L,ElemType a[],int n){
    *L=NULL;
    LNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(LinkList)malloc(sizeof(LNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        if((*L)==NULL){//对第一个结点需要特殊处理
            *L=s;//头指针指向插入结点
            s->next=NULL;//倒序插入，最后一个结点的指针域赋值为NULL
        }else{
            s->next=*(L);//新插入的结点指向第一个结点
            *(L)=s;//头指针指向新的插入节点
        }
    }
}
//尾插法
int create_TailInsert(LinkList *L,ElemType a[],int n){
 // InitList_Link(L);
    (*L)=NULL;
    LNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){//遍历数组
        s=(LinkList)malloc(sizeof(LNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        if((*L)==NULL){//对第一个结点需要特殊处理
            (*L)=s;//头指针指向第一个结点
            r=s;//尾指针移动到最后一个结点
        }else{
            r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
            r=s;//r移动到链表尾端
        }
    }
    r->next=NULL;//结束时，最后一个结点的指针域赋值为空
}

总结

含头结点优点：

使得链表第一个结点的操作和其他位置一样，无需特殊处理。

含头结点缺点：

头结点的数据域一般不存储数据，该空间被浪费。

时间复杂度：

每个结点插入的时间为O(1),设表长为n，所有方式的时间复杂度均为O(n)

求表长

int Length_Link(LinkList L){
    int i=0;//空表返回0
    while (L->next!=NULL){//遍历，直到尾结点，空表不进入循环
        L=L->next;//向后移动一个
        i++;//表长加一
    }
    return i;//返回表长
}

//时间复杂度：设表长为n,时间复杂度为O(n)

插入操作

在表L中的第i个位置上插入指定元素e。

int ListInsert_Link(LinkList *L,int i,ElemType e){
    int j=0;//空表序号为0
    LNode *p=(*L);//p指向头结点
    LNode *s;//s用来指示新创建的结点
    while (p&&j<i-1){//找到被插入序号的前一个位置
       p=p->next;//向后移动一个
       j++; 
    }
    if(!p||i<1) return FALSE;//序号在无效范围内
    s=(LinkList)malloc(sizeof(LNode));//创建一个新结点
    s->data=e;//赋值
    s->next=p->next;//让该结点指向p（插入位置的前一个结点）的下一个结点
    p->next=s; //让p指向该结点  
}

//时间复杂度：在给定的结点后插入新结点的时间复杂度为O(1),查找第i-1个节点的时间复杂度为O(n)
//综上：时间复杂度为O(n)

删除操作

删除表中L中第i个位置的元素，并用e返回删除的元素。

int ListDelete_Link(LinkList *L,int i,ElemType *e){
    int j=0;//空表序号为0
    LNode *p=(*L);//p指向头结点
    LNode *q;//q用来指向被删除的结点
    while (p->next&&j<i-1){//找到要被删除结点的前一个结点
        p=p->next;//向后移动一个
        j++;
    }
    if (!(p->next)||i<1) return FALSE;//序号在无效范围内
    q=p->next;//让q指向被删除的结点
    p->next=q->next;//让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开
    *e=q->data;//把被删除的结点的值返回
    free(q);//释放该结点
    return TRUE; //删除成功
}
//时间复杂度：在给定的结点后删除结点的时间复杂度为O(1),查找第i-1个节点的时间复杂度为O(n)
//综上：时间复杂度为O(n)

按位查找操作

获取表L中第i个位置的元素的值。

int GetElem_List(LinkList L,int i,ElemType *e){
    LNode *p=L; //p指向头结点
    int j=0;//空表序号为0
    while (p&&j<i){//找到第i个位置
        p=p->next;//向后移动一个
        ++j;
    }
    if(!(p)||i<1)  return FALSE; //i不在有效范围内
    *e=p->data; //把第i个结点的值用e返回
    return TRUE;
}
//时间复杂度为O(n)

按值查找操作

在表L中查找具有给定关键字值的元素,返回序号

int LocateElem_List(LinkList L,ElemType e,int *i){
    int j=0;//空表序号为0
    while (L->next!=NULL){//遍历链表
        L=L->next;//向后移动
        j++;//序号加一
        if (L->data.id==e.id){//这里我们只用id来判断元素的值是否相等，假设id唯一
            *i=j;//如果相等，用i返回序号
            return TRUE;//查找成功
        }    
    }
    return FALSE;
}
//时间复杂度为O(n)

销毁表

void DestroyList(LinkList *L){
    while((*L)->next!=NULL) {//遍历链表
    	LNode *p=(*L)->next;//p指示头结点的下一个，要被删除的结点
    	(*L)->next=p->next;//让头结点指向p的下一个，把p从链表断开
    	free(p);//删除p
	}
}
//时间复杂度为O(n)

双链表

单链表结点中只有一个指向其后继结点的指针，使得单链表只能从头结点依次顺序地向后遍历。
要访问某个结点的前驱结点，只能从头开始遍历。
也就是说：访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)

为了克服单链表的上述缺点，引入了双链表。
双链表中有两个指针prior和next，分别指向其前驱结点和后继结点

双链表的定义

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

双链表上具体操作的实现和时间复杂度

使用含头结点的双链表

初始化表

/*初始化*/
int InitList_DLink(DLinkList *L){
    *L=(DLinkList)malloc(sizeof(DNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->prior=NULL;//头结点的prior永远指向NULL
    (*L)->next=NULL;//初始化为空
    return TRUE;//初始化成功
}
//时间复杂度为O(1)

根据数组创建双链表

/*头插法创建双链表*/
int create_HeadInsert(DLinkList *L,ElemType a[],int n){
 // InitList_DLink(L);
    DNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){//由于D头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(DLinkList)malloc(sizeof(DNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        s->next=(*L)->next;//让该结点的后继指向第一个结点
        if((*L)->next!=NULL) (*L)->next->prior=s;//第一个结点的前驱指向该结点
        s->prior=(*L);//让该结点的前驱指向头结点   
        (*L)->next=s;//让头结点指向该D结点（该结点成为第一个结点）
    }
}

/*尾插法创建双链表*/
int create_TailInsert(DLinkList *L,ElemType a[],int n){
 // InitList_DLink(L);
    DNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){//遍历数组
        s=(DLinkList)malloc(sizeof(DNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
        s->prior=r;//该结点的前驱指向r指向的结点
        r=s;//r移动到链表尾端o
    }
    r->next=NULL;//结束时，最后一个结点的指针域赋值为空
}

//每个结点插入的时间为O(1),设表长为n,所有方式的时间复杂度均为O(n)

插入操作

在表L中的第i个位置上插入指定元素e。

/*插入*/
int ListInsert_DLink(DLinkList *L,int i,ElemType e){
    int j=0;//空表序号为0
    DNode *p=(*L);//p指向头结点
    DNode *s;//s用来指示新创建的结点
    while (p&&j<i-1){//找到被插入序号的前一个位置
       p=p->next;//向后移动一个
       j++; 
    }
    if(!p||i<1) return FALSE;//序号在无效范围内
    s=(DLinkList)malloc(sizeof(DNode));//创建一个新结点
    s->data=e;//赋值
    s->next=p->next;//让该结点指向p（插入位置的前一个结点）的下一个结点
    if (p->next!=NULL) p->next->prior=s;//让p的下一个结点的前驱指向该结点
    s->prior=p;//让该结点的前D驱指向p
    p->next=s; //让p指向该结点  
}
//时间复杂度：在给定的结点后插入新结点的时间复杂度为O(1),查找第i-1个节点的时间复杂度为O(n)
//综上：时间复杂度为O(n)

删除操作

删除表中L中第i个位置的元素，并用e返回删除的元素。

/*删除*/
int ListDelete_DLink(DLinkList *L,int i,ElemType *e){
    int j=0;//空表序号为0
    DNode *p=(*L);//p指向头结点
    DNode *q;//q用来指向被删除的结点
    while (p->next&&j<i-1){//找到要被删除结点的前一个结点
        p=p->next;//向后移动一个
        j++;
    }
    if (!(p->next)||i<1) return FALSE;//序号在无效范围内
    q=p->next;//让q指向被删除的结点
    p->next=q->next;//让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开
    if(q->next!=NULL)q->next->prior=p;
    *e=q->data;//把被删除的结点的值返回
    free(q);//释放该结点
    return TRUE; //删除成功
}
//时间复杂度：在给定的结点后删除结点的时间复杂度为O(1),查找第i-1个节点的时间复杂度为O(n)
//综上：时间复杂度为O(n)

其他操作与单链表一样，不展示

循环链表

特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。
既然是环的话，那就不难想象，从表中任意一个结点出发都可以找到表中其他结点。

循环单链表

循环单链表与单链表唯一的区别就是多了一个由尾结点指向头结点的指针。
所以循环链表的操作与单链表基本一致
唯一的差别就是循环的条件不是p或p->next是否为空，而是它们是否等于头指针
($p==L或p->next==L$)。

/*求表长*/
int Length_CLink(CLinkList L){
    int i=0;//空表返回0
    CNode *s=L;
    while (s->next!=L){//遍历，直到尾结点，空表不进入循环
        s=s->next;//向后移动一个
        i++;//表长加一
    }
    return i;//返回表长
}

循环双链表

循环双链表与循环单链表唯一的区别就是多了一个指向前驱的指针。
所以循环双链表的操作与循环单链表也基本一致
就是对结点操作时，需要多操作一步，让p->prior指向前驱结点。

/*插入*/
int ListInsert_CDLink(CDLinkList *L,int i,ElemType e){
    int j=0;//空表序号为0
    CDNode *p=(*L);//p指向头结点
    CDNode *s;//s用来指示新创建的结点
    while (p->next!=(*L)&&j<i-1){//找到被插入序号的前一个位置
       p=p->next;//向后移动一个
       j++; 
    }
    if(p==(*L)||(i-j)>1) return FALSE;//序号在无效范围内
    s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
    s->data=e;//赋值
    s->next=p->next;//让该结点指向p（插入位置的前一个结点）的下一个结点
    p->next->prior=s;//让p的下一个结点的前驱指向该结点
    s->prior=p;//让该结点的前驱指向p
    p->next=s; //让p指向该结点  
}

/*删除*/
int ListDelete_CDLink(CDLinkList *L,int i,ElemType *e){
    int j=0;//空表序号为0
    CDNode *p=(*L);//p指向头结点
    CDNode *q;//q用来指向被删除的结点
    while (p->next!=(*L)&&j<i-1){//找到要被删除结点的前一个结点
        p=p->next;//向后移动一个
        j++;
    }
    if ((p->next)==(*L)||i<1) return FALSE;//序号在无效范围内
    q=p->next;//让q指向被删除的结点
    p->next=q->next;//让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开
    q->next->prior=p;//让删除结点的下一个结点的前驱指向p；
    *e=q->data;//把被删除的结点的值返回
    free(q);//释放该结点
    return TRUE; //删除成功
}

静态链表

众所周知，指针是c语言的灵魂，指针使得链表的实现简单明了起来。但是问题来了，在c语言还没有的时代，又想描述链表，怎么办呢？
这就有了静态链表

静态链表的设计

首先，我们来解决一个最重要的问题，没有指针，怎么表示下一个元素的位置呢？

当时的人们想出来的办法便是，用数组的下标来代替指针。我们把这个数组的下标叫做游标。

第二个问题，当我们要往数组里插入元素时，如何确定数组里哪些分量未被使用，要插到哪个位置上呢？当我们删除一个元素的时候，要把这个删除后已经不存放数据的数组分量链接到哪里去，然后再次被使用呢？

解决办法是将所有未被使用过的以及被删除的分量用一个游标链成一个备用链表。
每当进行插入的使用便从备用链表上取得第一个结点作为待插入的新结点。
反之，在删除时将从链表中删除下来结点链接到备用链表上。

有没有觉得上面的描述特别熟悉，这实际上就是C语言里面malloc函数和free函数做的事情，在静态链表中，我们得自己实现，不过操作起来也不复杂。

最后一个问题，我们现在已经知道了我们把静态链表分为两部分，一部分存放数据，一部分不存放数据，我们称之为备用链表。那么我们如何标识这两部分呢？

解决办法，我们这里把数组下标为0位置的游标用来存放备用链表的第一个元素（也就是数组中第一个不存放数据的元素）的下标
我们这里把数组下标为1的位置游标用来存放第一个数据不为空的元素的下标
这里还有个细节就是我们把游标为0设为这两部分的结束。

静态链表的定义

#define ElemType char//这里我们使用的例子，采取字符
#define MaxSize 10  //链表的最大长度
typedef struct{
    ElemType data;//存储的数据元素
    int next;//游标，用来指示下一个数组分量的下标
}SLinkList[MaxSize];//静态链表

静态链表的操作

初始化

/*初始化*/
int InitSpace_SL(SLinkList space){ 
  int i;
  for (i = 2; i < MaxSize-1; i++){
      space[i].data=' ';
      space[i].next=i+1;
  }
  space[0].next=2;
  space[0].data=' ';
  space[1].next=0;
  space[1].data=' ';
  space[MaxSize-1].next=0;
  space[MaxSize-1].data=' ';
  return TRUE;
}

求表长

/*求表长*/
int ListLength(SLinkList space){
    int length=0;//空表长度为0
    int i=space[1].next;//指向第一个有数据的位置
    while (i!=0){
        length++;
        i=space[i].next;//相当于指针的p=p->next
    }
    return length;
}

主要的操作便是遍历表：
这里的i=space[i].next;相当于指针的p=p->next

总结

尽管我们现在有了单链表，也不再会使用静态链表了，但是它的思想还是挺神奇的。
总的来说，它和单链表很像，插入删除不需要移动元素，所有我们称之为静态链表。
但是它不仅有单链表不能随机存取的缺点，也没有解决连续分配（数组）带来的表长难以确定的问题。