数据结构-第一章：线性表

发表于 2023-06-29 更新于 2023-07-08 分类于数据结构

线性表。

线性表的定义和基本操作

线性表的定义

线性表时具有相同数据类型的n个数据元素的有限序列，其中n为表长，n=0时为空表。若用L命名线性表，则其一般表示为$L=(a_1,a_2,…,a_i,…,a_n)$。

每个数据元素所占空间一样大
有次序

$a_1$是表头元素，$a_2$是表为元素。
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的基本操作：

顺序表

顺序表的定义

顺序表：用顺序存储的方式实现线性表。
顺序存储：把逻辑上相邻的元素存储在物理位置上页相邻的存储单元中。

顺序表的实现—静态分配

静态分配使用静态数组定义方式实现，数组长度一旦大小确定就不可再改变。

//顺序表的定义
#define MaxSize 10              //定义最大长度
typeof struct{                   
    ElemType data[MaxSize];     //静态数组存放元素
    int length;                 //顺序表当前长度
}SqList;                        //顺序表类型定义

//初始化一个顺序表
void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++)
        L.data[i]=0             //②将所有数据元素设置为默认初始值（可省略）
    L.length=0                  //③顺序表初始长度为0
}

int main(){
    SqList L;                   //①声明顺序表
    InitList(L);                //初始化顺序表
    //...后续操作
    return 0;
}

如果省略上述代码初始化方法中for循环部分，内存中会有遗留的脏数据。但是只有违规操作才会取到脏数据，所以循环部分可省略。

数组存满后，是无法扩容的，只能放弃治疗。

顺序表的实现—动态分配

动态分配需要定义一个指针指向顺序表的第一个元素。

动态申请和释放空间：malloc/free函数

malloc返回一个指针，需要强制转型为你定义的数据元素类型指针。
malloc函数的参数指明要分配多大的连续内存空间。

1	p=(ElemType )malloc(sizeof(ElemType)InitSize);

代码

#define InitSize 10
typedef struct{
    int *data;                  //指示动态分配数组的指针
    int MaxSize;                //顺序表最大容量
    int length;                 //顺序表当前长度
}SeqList;

void InitList(SeqList &L){
    //用malloc申请连续存储空间
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态数组长度
void IncreaseSize(SeqList &L, int len){
    int *p=L.data;
    L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0; i<L.length; i++){
        L.data[i]=p[i];         //将数组复制到新区域
    } 
    L.MaxSize=L.MaxSize+len;    //增加最大长度
    free(p);                    //释放原空间
}

int main(){
    SqList L;                   //①声明顺序表
    InitList(L);                //②初始化顺序表
    //...加入几个元素
    IncreaseSize(L, 5);         //③
    return 0;
}

在执行①后，会先分配一片空间存储顺序表的指针、最大长度和当前长度这三个变量。

执行②后会在内存申请一片连续空间，同时令顺序表指针指向该片空间的首元素。

执行③时，先令指针p指向原空间，用来保存数据。并开辟一片新的更大的空间。

再令顺序表的指针指向新空间，并将p中的元素复制到新空间中。

然后释放p指向的空间（原数组），然后p指针自动被释放。

可以看出，动态分配的时间开销更大。

顺序表的特点

随机访问：可以在O(1)时间内找到低i个元素
存储密度高，每个节点值存储数据元素
扩容不方便
插入删除操作不方便，需要移动大量元素

顺序表的插入删除

本节以静态分配的代码为例，动态分配也差不多。
即：

#define MaxSize 10              //定义最大长度
typeof struct{                   
    ElemType data[MaxSize];     //静态数组存放元素
    int length;                 //顺序表当前长度
}SqList;

插入

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

代码

bool ListInsert(SqList &L, int i, int 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--)
        L.data[j]=L.data[j-1];  //将第i个元素及之后的元素后移
    L.data[i-1]=e;              //在位置i放入元素e
    L.length++;                 //长度加1
    return true;
}

时间复杂度

最好情况：插入在表尾，O(1)
最坏情况：插入在表头，O(n)
平均情况：假设新元素插入到任一位置的概率相同，即所有位置概率均为$p=\frac{1}{n+1}$，则平均循环次数$=np+(n-1)p+(n-2)p+……+1p=p=\frac{n}{2}$

删除

删除表L中第i个位置上的元素并返回其值。

代码

bool ListDelete(SqList &L, int i, int &e)
{      
    if(i<1||i>L.length)         //判断i的范围是否有效
        return false;           
    e=L.data[i-1]               //将被删除的元素赋给e   
    for(int j=i;j<length;j++)
        L.data[j-1]=L.data[j];  //将第i个元素及之后的元素前移
    L.length--;                 //长度减1
    return true;
}

int main{
    SqList L;
    InitList(L);
    //...插入几个关键元素
    ListDelete(L,3,e);
    printf("%d",e);
    return 0;
}

时间复杂度

最好情况：删除表尾，O(1)
最坏情况：删除表头，O(n)
平均情况：假设新元素插入到任一位置的概率相同，即所有位置概率均为$p=\frac{1}{n+1}$，则平均循环次数$=np+(n-1)p+(n-2)p+……+1p=p=\frac{n}{2}$

顺序表的查找

按位查找

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

代码

实际上无论静态分配还是动态分配，代码都一样。

1
2
3

ElemType GetElem(SqList L,int i){
    return L,data[i-1];
}

时间复杂度

随机存取：O(1)

按值查找

在表L中查找具有给定关键字值的元素。

代码

int LocateElem(SqList L,ElemType e){
    for(int i=0;i<L.length;i++>)
        if(L.data[i]==e)        //①
            return i+1;         //返回位序，查找成功
    return 0;                   //退出循环，查找失败
}

注意，①处使用==是因为变量是基本类型变量，如果是结构体，需要自定义方法判断是否相等。但一般考研时若无明确要求，使用==即可。

时间复杂度

最好情况：所找元素在表头：O(1)
最坏情况：所找元素在表尾：O(n)
平均情况：假设新元素插入到任一位置的概率相同，即所有位置概率均为$p=\frac{1}{n+1}$，则平均循环次数$=np+(n-1)p+(n-2)p+……+1p=p=\frac{n}{2}$

链表

单链表的定义

单链表的节点除了存放数据元素外，还需要存储指向下一个节点的指针。

优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，存储指针耗费空间

struct LNode{                   //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素
    sturct LNode *next;         //指针指向下一个节点
}LNode,*LinkList                //第一种表示方式重点在于节点，第二种重点在于整个链表（头指针）

单链表的两种定义方式

一般使用带头结点的链表。

不带头结点

//初始化
bool InitList(LinkList &L){
    L=NULL;                     //去除脏数据
    return true;
}

//判断是否为空
bool Empty(LinkList L){
    return (L==NULL);
}

void test(){
    LinkList L;                 //声明一个指向单链表的指针
    InitList(L);
    //...
}

带头结点

//初始化
bool InitList(LinList &L){
    L=(LNode *) malloc(sizeof(LNode));  //分配一个头节点
    if(L==NULL)                 //内存不足，分配失败
        return false;
    L->next=NULL;               //头节点之后无节点
    return true;
}

//判断是否为空
bool Empty(LinkList L){
    return (L->next==NULL);
}

void test(){
    LinkList L;                 //声明一个指向单链表的指针
    InitList(L);
    //...
}

头指针！=头结点

单链表的插入删除

单链表的按位序插入

带头结点

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

插入的操作主要为：

先找到（通过p结点实现“找到”）第i-1（这里以i=2为例）个结点。
申请一个新结点，并令新结点指向第i个结点。
再将第i-1个结点的后继结点指向新结点。

即完成插入操作。

代码实现为：

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;                   //指针p指向当前扫描到的结点
    int j=0;                    //当前p指向的是第几个结点
    p=L;                        //L指向头结点
    while(p!=NULL && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)                 //i值不合法
        return false;
    //以上操作为找到第i-1个结点
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p-next=s;
    return true;
}

平均时间复杂度：O(n)

不带头结点

思路与带头结点的没有区别，只是当i=1是需要特别处理。
代码为：

//初始化
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;                    //头指针指向新结点
        return true;
    }
    LNode *p;
    int j=1;
    p=L;                        //L指向第一个结点，注意不是头结点
    while(p!=NULL && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    //以上操作为找到第i-1个结点
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p-next=s;
    return true;
}

后插操作

给定结点，在结点后插入数据。

//初始化
bool InsertNextNode(LNode &p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)                 //内存分配失败
        return false;           
    s->data=e;
    s->next=p->next;
    p-next=s;
    return true;
}

可以发现，基本与插入操作类似，同时插入操作也可以改写为：

//初始化
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;                   //指针p指向当前扫描到的结点
    int j=0;                    //当前p指向的时第几个结点
    p=L;                        //L指向头结点
    while(p!=NULL && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)                 //i值不合法
        return false;
    //以上操作为找到第i-1个结点
    return InsertNextNode(p, e);
}

前插操作

给定结点，在结点前插入数据e。
两种方法：

从头结点逐步遍历
“偷梁换柱”
第一种方法时间复杂度高，效率低。所以采用第二种方法。

主要思路为：

申请新结点，并令其作为给定结点的后继节点
令复制给定结点的数据元素至新结点
令给定结点的值为e

代码为：

bool InsertPriorNode(LNode &p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)  
        return false;   
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true    
}

另一种写法：

bool InsertPriorNode(LNode &p, LNode *s){
    if(p==NULL || s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    ElemType temp=p->data;
    p->data=s->data;
    s->data=temp;
    return true  
}

时间复杂度为O(1)。

按位序删除（带头结点）

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

先找到第i-1（此处假设i=1）个结点
令其结点指针指向i的下一个个结点

使用free函数释放第i个结点

bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1)
        return false;
    LNode *p;                   //指针p指向当前扫描到的结点
    int j=0;                    //当前p指向的是第几个结点
    p=L;                        //L指向头结点
    while(p!=NULL && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)                 //i值不合法
        return false;
    //以上操作为找到第i-1个结点
    if(p->next==NULL)           //第i-1个结点后无其他结点
        return false;
    LNode *q=p->next;           //令q指向被删除结点
    e=q->data;                  
    p->next=q->next;            //将*q结点从链中断开
    free(q);                    //释放空间
    return true;
}

平均时间复杂度：O(n)

指定结点的删除

给定指定结点，在L中删除它。
同样也是两种方法：

从头结点遍历
“偷梁换柱”

一般采用第二种方法。

先将其后继结点的值赋给自身
再令该节点的指针指向后继节点的后继节点

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q=p->next;           //令q指向被删除结点                  
    p->data=q->data;            //和后继节点交换数据域
    p->next=q->next;            //将*q结点从链中断开
    free(q);                    //释放空间
    return true;
}

时间复杂度：O(1)

但如果要删除的p结点是链表中的最后一个结点，只能用第一种方法删除，时间复杂度为O(n)。

单链表的查找

只讨论带头结点的链表。

按位查找

找到L中第i个元素。

LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;                   //指向当前扫描到的结点
    int j=0;                    //当前p指向第几个节点
    p=L;
    while(p!=NULL && j<i){
        p=p->next;
        j++;
    }
    return p;
}

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

这样，按位插入和按位删除可以修改为：

//按位查找
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p=GetElem(L,i-1);
    return InsertNextNode(p,e);
}

//按位删除
bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1)
        return false;
    LNode *p=GetElem(L,i-1);
    if(p==NULL)                 //i值不合法
        return false;
    if(p->next==NULL)           //第i-1个结点后无其他结点
        return false;
    LNode *q=p->next;           //令q指向被删除结点
    e=q->data;                  
    p->next=q->next;            //将*q结点从链中断开
    free(q);                    //释放空间
    return true;
}

按值查找

给定值找到对应的结点。

LNode * GetElem(LinkList L,ElemType e){
    LNode *p = L->next;
    while(p!=NULL && p->data!=e) //假设是int类型才能用“!=”
        p=p->next;
    return p;
}

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

求表的长度

int Length(LinkList L){
    int len=0;
    LNode *p=L;
    while(p->next!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

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

单链表的建立

如果提供多个数据元素，将它们存到一个单链表里，需要如何实现？

初始化一个单链表
每次取一个数据元素，插入到表尾/表头

只讨论带头结点的情况。

尾插法

可以按以下步骤操作：

初始化单链表
设置变量length记录链表长度
while循环调用ListInsert插入至尾部，每次插入后length++

但时间复杂度为O(n²)，效率太低。

最好的方法是设置一个表尾指针，每次在表尾结点调用后插操作。

首先建立头结点，并创建两个指针。指针r为表尾指针
为s结点开辟新空间以放置要插入的元素
令r结点（尾结点）指向新结点
令r指针指向s指针，即更新尾结点

LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LinkList *)malloc(sizeof(LNode));    //①建立头结点
    LNode *s,*r=L;              //①r为表尾指针
    scanf("%d",&x);      
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));   //②
        s->data=x;              //②
        r->next=s;              //③令表尾结点与新结点连接
        r=s;                    //④r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next=NULL;               //表尾结点置空
    return L;               
}

头插法

可按以下步骤操作：

初始化单链表
while循环调用InsertNextNode

LinkList List_HeadInsert(LinkList &L){
    int x;
    L=(LinkList *)malloc(sizeof(LNode));    //建立头结点
    L->next=NULL;               //排除脏数据可能，这里与尾插法不一样，要注意
    LNode *s;             
    scanf("%d",&x);      
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;             
        s->next=L->next;        //令新结点与头结点后连接
        L->next=s;              //令头结点与新结点连接
        scanf("%d",&x);
    }
    return L;               
}

注意，头插法多了L->next=NULL这一句，是为了避免出现脏数据的情况。如果头结点存在脏数据，会出现最终结果指向神秘的空间，是错误的。

注意：链表的原地逆置与头插法类似。

双链表

单链表在寻找结点之前的数据时十分不方便，因此提出了双链表的定义，即在单链表的基础上再添加一个指针，指向该结点的前驱结点。

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode,*DLinklist;

双链表的初始化（带头结点）

//初始化
bool InitDLinkList(DLinklist &L){
    L=(DNode *) malloc(sizeof(DNode));  //分配一个头结点
    if(L==NULL)
        return false;
    L->prior=NULL;                  //头结点的prior永远指向NULL
    L->next=NULL;                   //头结点后暂无结点
    return true;
}
//判断是否为空
bool Empty(DLinklist L){
    return L->prior==NULL;
}

void testDLinkList(){
    DLinklist L;
    InitDLinkList(L);
    //...后续代码
}

双链表的插入

假设插入的结点为s，插入在p节点后，p不为尾结点。

先令s结点指向p结点的后继结点
再令s结点为p结点后继结点的前驱结点
再令p结点作为s结点的前驱结点
再令s结点作为p结点的后继结点

bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    if(p->next!=NULL)               //如果p结有后继结点，考虑特殊情况
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

前插操作可以通过后插操作实现：在给定结点的前驱结点使用后插操作。

双链表的删除

假设删除p结点的后继结点q，p不为尾结点。

先令p后继指针指向q结点的后继结点
再令q结点的后继结点的前驱指针指向p结点
释放q结点

bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q=p->next;
    if(q==NULL)                     //p为尾结点，无后继
        return false;
    p->next=q->next;
    if(q->next!=NULL)               //q结点不是尾结点
        q->next->prior=p;
    free(q);
    return true;
}

这样，利用删除操作就可以销毁一个双链表。

void DestroyList(DLinkList &L){
    while(L->next!=NULL){
        DeletNextNode(L);
    }
    free(L);                        //释放头结点
    L=NULL;                         //头指针指向NULL
}

双链表的遍历

后向遍历

while(p!=NULL){
    //...对p的操作
    p=p->next;
}

前向遍历

while(p!=NULL){
    //...对p的操作
    p=p->prior;
}

//跳过头结点
while(p->prior!=NULL){
    //...对p的操作
    p=p->prior;
}

双链表不可随机存取，按位查找和按值查找都只能用遍历实现。时间复杂度为O(n)。

循环链表

循环单链表

最后一个结点的指针指向头结点。
从一个结点出发可以找到其它任一结点。

初始化

//初始化
bool InitList(LinList &L){
    L=(LNode *) malloc(sizeof(LNode));  //分配一个头结点
    if(L==NULL)                 //内存不足，分配失败
        return false;
    L->next=L;                  //头结点next指向头结点
    return true;
}

//判断是否为空
bool Empty(LinkList L){
    return (L->next==L);
}

//判断是否为表尾
bool isTail(LinkList L, LNode *p){
    return (p->next==L);
}

循环单链表的改进

从头结点找到尾部，时间复杂度为O(n)
从尾部找到头部，时间复杂度为O(1)

因此，如果需要频繁对链表的头部或尾部进行操作，可以令头指针L指向表尾。但每次插入删除元素时要记得更改头指针指向。

循环双链表

表头节点的prior指向表尾结点，表尾结点的next指向头结点。

循环双链表的初始化

//初始化
bool InitList(DLinList &L){
    L=(LNode *) malloc(sizeof(LNode));  //分配一个头结点
    if(L==NULL)                 //内存不足，分配失败
        return false;
    L->prior=L;                 //头结点的prior指向头结点
    L->next=L;                  //头结点next指向头结点
    return true;
}

//判断是否为空
bool Empty(DLinkList L){
    return (L->next==L);
}

//判断是否为表尾
bool isTail(DLinkList L, DNode *p){
    return (p->next==L);
}

循环双链表的插入与删除

//插入
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

//删除
bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q=p->next;
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}

即在非循环的双链表上，不必再考虑表尾结点这一特殊情况。

静态链表

单链表的结点在内存中时分散存储的，而静态链表则是分配一整片连续的内存空间，各个结点集中安置。

静态链表中的每个结点包含数据元素和指向下一个结点的数组下标（游标）
0号节点充当头结点
最后一个结点的游标为-1
设黑色每个数据元素为4B，每个游标为4B（每个结点8B），起始地址为addr，游标为i，则下一个数据元素的存放地址即为addr+8*i

静态链表的定义

#define MaxSize 10
struct Node{
    ElemType data;
    int next
}

void testSLinkList(){
    struct Node a[MaxSize];
    //...后续代码
}

或者，也可：

#define MaxSize 10
typedef struct{
    ElemType data;
    int next
}SLinkList[MaxSize];

void testSLinkList(){
    SLinkList a;
    //...后续代码
}

静态链表的基本操作

可以简单实现，不赘述。

静态链表的特点

优点：增删操作不需要大量移动元素
缺点：不能随机存取，容量不可变

顺序表和链表的对比

---------------------本文结束---------------------