🔑数据结构_第二章：线性表

第二章：线性表

（一）线性表的定义、基本操作概述

1、定义

线性表是具有相同数据类型的n(n>0)个数据元素的有限序列，其中n为表长，n为0时为空表。

若用L命名线性表，则其一般表示为：
$$
L = (a_1, a_2, …, a_i, a_{i+1}, …, a_n)
$$

a1为表头元素，an为表尾元素。
除第一个元素外的每个元素都只有一个直接前驱，除最后一个元素外的每个元素都只有一个直接后驱。

2、线性表的特点

表中的元素个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素每个都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。而顺序表和链表是指存储结构，不要混淆！

2、可以进行的基本操作

①改

创建/初始化线性表：

InitList(&L)：构造一个空的线性表。
销毁/删除线性表：

DestroyList(&L)：销毁表并释放其内存空间。
*更改某个元素的值：

可自定义。

②查

按值查找元素：

LocateElem(L,e)：在表L中查找具有给定关键字值的元素。
按位查找元素：

GetElem(L,i)：获取表L中第第i个元素的值。
求表长：

Length(L)：返回表L中元素的个数。
判空操作：

Empty(L)：若L为空表，返回true，否则返回false。

③增

插入元素：

ListInsert(&L,i,e)：在表L的第i个位序插入元素e。（前插）
特殊情况：
- 在表第一个结点之前插入。
- 在表末尾插入。

④删

删除元素：

ListDelete(&L,i,&e)：删除表L的第i个元素，并用e返回被删元素的值！
特殊情况
- 删除第一个结点
- 删除末尾结点

*注：①基本操作的实现取决于采取哪种存储结构，存储结构不同，算法的实现也不同。
②符号&代表C++语言中的引用，在C语言中用指针也可以达到同样的效果。

（二）线性表的顺序表示——顺序表

1、概念

线性表描述了一种逻辑上的存储关系，而我们用顺序表可以在物理层面实现这种存储方式。所以，顺序表就是逻辑顺序与物理顺序都相同的一种实现线性表的方式。

也是一种随机存储的存储结构。
通常用高级程序设计语言中的数组来描述。

2、特点：

随机访问。
存储密度高，每个节点只存储数据元素。
逻辑上相邻的元素物理上也相邻，所以插入和删除操作可能需要移动大量元素。

3、基本操作

（1）插入

向表中第i个位置插入元素e：

1
2
3

//①判断输入值i是否合法，不合法则返回错误信息终止程序运行，合法则下一步；
//②找到第i个位置的元素，将该元素和它所有后继，由末尾第一个开始依次向后移动一个元素位置；
//③空出来的位置存放e，运行结束。

最好情况：在表尾插入元素，不执行移动，时间复杂度为O(1)。
最坏情况：在表头插入元素，所有元素都被移动一次，时间复杂度为O(n)。
平均时间复杂度：O(n)。

（2）删除

删除表中第i个位置的元素，并返回删掉元素的内容：

1
2
3

//①判断输入值i是否合法，不合法则返回错误信息终止程序运行，合法则下一步；
//②找到第i个位置的元素，将其内容赋值给另一变量m，然后删掉该元素，并将该元素的所有后继，由第一个开始依次向前移动一个元素位置；
//③返回m，运行结束。

最好情况：删除表尾元素，不执行移动，时间复杂度为O(1)。
最坏情况：删除表头元素，所有元素都被移动一次，时间复杂度为O(n)。
平均时间复杂度：O(n)。

（3）按值查找（顺序查找）

for循环遍历，挨个比较值，返回目标元素索引值。

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)。
最坏情况：查找的元素在末尾或不存在，所有元素都要比较一次，时间复杂度为O(n)。
平均时间复杂度：O(2)。

4、代码实现

（1）顺序表的实现——静态分配

#include <cstdio>

//顺序表的静态实现

#define MaxSize 10					//定义全局最大长度
typedef struct{						//定义该结构体为一个顺序表
    //此处的数组类型完全可以根据具体需求自定义
    int data[MaxSize];				//手动定义顺序表的数据域，定义为数组，数组大小不能更改，所以该顺序表是静态分配
    int length;						//手动定义该顺序表的长度标识
}SqList;							//起别名为SqList


//初始化顺序表：将L的n个结点初始化，初始化数据为m
bool initList(SqList &L,int n, int m){
    //判断输入是否合法
    if(n > MaxSize)
        return false;
    //for循环遍历数据与中所有内容赋值为0
    for(int i = 0; i < MaxSize; i++)
        L.data[i] = m;
    //设定顺序表的长度为n（此处的长度指的是存储了内容的有效长度）
    L.length = n;
}


//给表L中第i个位置插入元素e（i为索引值），插入成功返回true，失败返回false
bool insertList(SqList &L,int i,int e){
    //先判断i的值是否合法
    if(i < 0 || i >= L.length){
        printf("输入i不合法！\n");
        return false;
    }
    printf("输入i合法！\n");
    //再插入-------------  L.length = 5, i = 4
    for(int j = L.length-1; j > i; j--){
        L.data[j] = L.data[j+1];
    }
    L.data[i] = e;
    L.length++;
    return true;
}


//删除表L中第i个位置的元素并将删除元素的内容用e返回
int deleteL(SqList &L, int i){
    //先判断i的值是否合法
    if(i < 0 || i >= L.length){
        printf("输入i不合法！\n");
        return false;
    }
    //再删除
    int d = L.data[i];
    for(int j = i; j < L.length-1; j++){
        L.data[j] = L.data[j+1];
    }
    L.length--;
    return d;
}


//按值查找：查询表L中值为8的结点（假设只有一个），查询到则返回其索引值，查不到则返回0
int queryL(SqList L, int i){
    for(int j = 0; j < L.length; j++){
        if(L.data[j] == i)
            return j+1;
    }
    return 0;
}


//按位查找：查找表L中第i（i是索引值）个元素，返回其内容
int lookForWithI(SqList L, int i){
    //判断i值合法性
    if(i < 0 || i >= L.length){
        printf("您输入的i值不合法！\n");
        return 0;
    }
    return L.data[i];
}



int main(){
    //实现一个静态分配的顺序表
    SqList L;

    //初始化顺序表：将L的n个结点初始化，初始化数据为m
    bool initL = initList(L,5,4);
    printf("初始化是否成功？%d\n",initL);
    printf("----------------------------------------\n以下为初始化结果：\n");
    for(int i = 0; i < L.length; i++){
        printf("顺序表的第%d个结点数据：%d\n",i+1,L.data[i]);
    }
    printf("----------------------------------------\n");

    //给表中内容赋值——给表L中第i个位置插入元素e（i为索引值！）
    bool inserL = insertList(L,4,8);
    printf("插入是否成功？%d\n",inserL);
    printf("----------------------------------------\n以下为插入结果：\n");
    for(int i = 0; i < L.length; i++){
        printf("顺序表的第%d个结点数据：%d\n",i+1,L.data[i]);
    }
    printf("----------------------------------------\n");

    //删除表L中第i个元素（i为索引值！）
    int deleteD = deleteL(L, L.length-1);
    printf("删除元素为：%d\n",deleteD);
    printf("----------------------------------------\n以下为删除结果：\n");
    for(int i = 0; i < L.length; i++){
        printf("顺序表的第%d个结点数据：%d\n",i+1,L.data[i]);
    }
    
    
    //按值查找：查询表L中值为4的结点（假设只有一个），查询到则返回其“位序”，查不到则返回0
    int q = NULL;
    q = queryL(L, 8);
    printf("----------------------------------------\n以下为查询结果：\n%d", q);
    
    
    //按位查找，返回内容
    int r = lookForWithI(L, 4);
    printf("----------------------------------------\n以下为按位查询结果：\n%d\n", r);
    
    return 0;
}

（2）顺序表的实现——动态分配

（三）线性表的链式表示——链表

逻辑上相邻，但物理上不相邻的存储方式即为线性表的链式存储。

每个存放数据的结点中有数据域和指针域，除了存放原来的数据，还要存储指向直接后继或直接前驱或其他地方的指针。

链表有四种：单链表、双链表、循环单链表、循环双链表。

是一种非随机存储的存储结构。

优点
1. 插入和删除操作不用移动元素，只需修改指针。
2. 不需要大量连续的存储空间来存储数据。
缺点
1. 失去了顺序表可随机存储的优点，因此查找某个特定结点时需要从头遍历依次查找。
2. 附加指针域，有浪费空间的缺点。

1、单链表

（1）单链表的创建

基于C的伪代码实现：

typedef struct LNode{					//定义单链表节点类型的结构体
    ElemType data;						//定义节点中的数据域
    struct Node *next;					//定义节点中的指针域
}LNode,LinkList;						//所以这就是一个节点

//说明：
//用malloc在内存中任意一处申请一块LNode结构体大小的空间并将返回的void类型指针转化为该结构体类型的指针类型
//使用别名LinkList创建一个LNode结构体类型的指针，接收在内存中新开辟空间的地址
LinkList *p = (LNode *)malloc(sizeof(LNode));
//这样子我们我们就新创建了一个新结点

自己手撸：

不带头结点：

//声明结点结构体
typedef struct LNode{
    int data;
    struct LNode *L;
}LNode, L_Link;

//声明头结点
L_Link initL_withotHeadNode(){
    L_Link L;
    L = NULL;
    return L;
}

带头结点：

//声明结点结构体
typedef struct LNode{
    int data;
    struct LNode *L;
}LNode, L_Link;

//声明头结点
L_Link initL_withHeadNode(){
    L_Link L = (L_Link)malloc(sizeof(LNode));
    //判断空间分配是否成功
    if(L == NULL){
        printf("空间分配未完成，链表创建失败！");
        return L;
    }
    //头结点的数据域和指针域都为空——NULL
    L->data = NULL;
    L->next = NULL;
    return L;
}

判断表是否为空：

//不带头结点：
bool emptyList_withoutHeadNode(L_Link L){
    return (L == NULL);
}

//带头结点：
bool emptyList_withHeadNode(L_Link L){
    return (L->next == NULL);
}

（2）单链表的查找

①按位查找

②按值查找

（3）单链表结点的插入

①前插

将数据e插入到表L的第i（位序）个位置（之前）：

思路1：新建指针p，通过循环遍历使p指向第i-1个结点的位置，然后将新节点插入到p之后。

不带头结点的表：

因为对于不带头结点的表，在表为空时插入第一个结点需要更改头指针，而在其它地方插入都相当于在某个特定节点之后插入，所以需要判断两种情况（以下代码中的第7行）：

L_Link insertL_withoutHeadNode(L_Link L, int i, int e){
    //判断i值合法性
    if(i < 1){
        printf("i值不合法！");
        return L;
    }
    //判断i是否为1，若为1，则创建第一个结点
    if(i == 1){
        L_Link N1 = (L_Link)malloc(sizeof(LNode));
        L = N1;
        N1->next = L;//使新结点指向原来L指向的节点，避免断链。若原本是空表，则N1->next为NULL，即尾结点N1指针域为空，合理！
        N1->data = e;
        return L;
    }
    //i值不为1，则遍历寻找第i-1个位序的结点再插入
     L_Link p = L;
    for(int j = 1; j < i-1; j++){	//注：这里j的初始值为1，那么循环体就要比j = 0少运行一次，因此循环结束p就指向了i-1的位置
        p = p->next;
    }
    //以上循环体也可调用按位查找方法来替换：
    /*
    p = L_Link searchL_num(L, i-1);
    */
    //此时指针p指向第i-1个结点
    //再判断p值，值为空说明位置不存在
    if(p == NULL){
		printf("i值不合法！");
        return L;
    }
    L_Link N1 = (L_Link)malloc(sizeof(LNode));
    N1->next = p->next;
    p->next = N1;
    N1->data = e;
    return L;
}

带头结点的表：

对于带头结点的表，不论在那儿插入都相当于在某个指定节点之后插入，所以不用分情况：

L_Link insertL_withHeadNode(L_Link L, int i, int e){
    //判断i值合法性
    if(i < 1){
        printf("i值不合法！");
        return L;
    }
    L_Link p = L;
    //挪指针
    for(int j = 0; j < i-1; j++){
        p = p->next;
    }
    //此时p指向i-1个结点
    //再判断指针位置是否存在
    if(p == NULL){
		printf("i值不合法！");
        return L;
    }
    L_Link N1 = (L_Link)malloc(sizeof(LNode));
    N1->next = p->next;
    p->next = N1;
    N1->data = e;
    return L;
}

思路二：以上方法都需要先循环遍历到第i-1个结点的位置，甚是啰嗦！

新思路：新节点直接插到第i个节点后面，然后交换新节点和第i个结点的数据，效果也是一样的：

②后插

将数据e插入到表L的第i个元素之后。

思路：

有关链表的增删改查所有手撸源码：

懒得整理了，就这样看吧：

#include <cstdio>
#include <cstdlib>

//链表的代码实现

//单链表

//定义结构体为一个链表的结点，多个结构体（结点）连在一起就是链表
typedef struct LNode{
    int data;                   //每个节点都有数据域
    struct LNode *next;         //每个节点都有指向下个结点的指针
}LNode, *L_Link;


//初始化单链表（不带头结点）
bool initL_withoutHead(L_Link &L){
    L = NULL;                   //空表，暂时还没有任何结点
    return true;
}


//初始化单链表（带头结点）
bool initL_withHead(L_Link &L){
    //分配一个头结点
    L = (LNode *)malloc(sizeof(LNode));
    //判断分配是否成功
    if(L == NULL)
        return false;
    //头结点的指针域为空，即头节点后没有结点
    L->next = NULL;
    //头结点的数据域也为空
    L->data = NULL;
    return true ;
}


//判断链表是否为空
//不带头结点：
bool emptyList_withoutHeadNode(L_Link L){
    return (L == NULL);
}
//带头结点：
bool emptyList_withHeadNode(L_Link L){
    return (L->next == NULL);
}


//插入（带头结点的表）：在表L的第i（i是位序）个位置插入元素e（e是数据域内要存的内容而不是结点）
L_Link insertL_withHeadNode(L_Link L, int i, int e){
    //判断i值合法性
    if(i < 1){
        printf("i值不合法！");
        return L;
    }
    L_Link p = L;
    //挪指针
    for(int j = 0; j < i-1; j++){
        p = p->next;
    }
    //此时p指向i-1个结点
    //再判断指针位置是否存在
    if(p == NULL){
        printf("i值不合法！");
        return L;
    }
    L_Link N1 = (L_Link)malloc(sizeof(LNode));
    N1->next = p->next;
    p->next = N1;
    N1->data = e;
    return L;
}


//插入（已初始化的不带头结点的表）
L_Link insertL_withoutHeadNode(L_Link L, int i, int e){
    //判断i值合法性
    if(i < 1){
        printf("i值不合法！");
        return L;
    }
    //判断i是否为1，若为1，则创建第一个结点
    if(i == 1){
        L_Link N1 = (L_Link)malloc(sizeof(LNode));
        L = N1;
        N1->next = L;//使新结点指向原来L指向的节点，避免断链。若原本是空表，则N1->next为NULL，即尾结点N1指针域为空，合理！
        N1->data = e;
        return L;
    }
    //i值不为1，则遍历寻找第i个位序的结点再插入
    L_Link p = L;
    for(int j = 1; j < i-1; j++){	//注：这里j的初始值为1，那么循环体就要比j = 0少运行一次，因此循环结束p就指向了i-1的位置
        p = p->next;
    }
    //以上循环体也可调用按位查找方法来替换：
    /*
    p = L_Link searchL_num(L, i-1);
    */
    //此时指针p指向第i-1个结点
    //再判断p值，值为空说明位置不存在
    if(p == NULL){
        printf("i值不合法！");
        return L;
    }
    L_Link N1 = (L_Link)malloc(sizeof(LNode));
    N1->next = p->next;
    p->next = N1;
    N1->data = e;
    return L;
}


//后插操作：在指定结点p的后面插入元素e
bool insert_behind(L_Link &P, int e){
    //判断位置合法性
    if(P == NULL){
        printf("后插操作：结点p不合法！\n");
        return false;
    }
    L_Link s = (L_Link)malloc(sizeof(LNode));
    s->data = e;
    s->next = P->next;
    P->next = s;
    return true;
}


//前插操作01：在指定结点p的前面插入元素e
bool insert_front_01(){
    /*
     * 思路：传入头指针和p结点，依次遍历找到p和p之前结点的位序，再插入
     * 缺点：时间复杂度为O(n)！费时费力，不建议使用！
     */
    return true;
}


//前插操作02：在指定结点p的前面插入元素e（e为数据域的值而不是结点）
bool insert_front_02(L_Link P, int e){
    /*
     * 思路二：先插到后面，再交换二者的值，结果等同于前插
     * 优点：时间复杂度为O(1)！
     */
    //实现：
    //先插到后面：
    insert_behind(P, e);
    //再交换二者的值
    P->next->data = P->data;
    P->data = e;
    return true;
}


//前插操作03：在指定结点P的前面插入结点S
bool insert_front_03(L_Link P, L_Link S){
    //先插到后面：
    S->next = P->next;
    P->next = S;
    //再交换二者的值
    int temp = P->data;
    P->data = S->data;
    S->data = temp;
    return true;
}


//删除操作——按位序删除结点（只探讨带头结点的情况），并用e保存删除的数据
bool deleteL(L_Link &L, int i, int &e){
    /*
     * 核心思路：将目标元素i的直接后继的数据域赋值给i，删除i的直接后继，效果也是删除了i位的结点
     * 如果目标元素是最后一个元素，那就只能循环遍历
     */
    //先定位
    int j = 0;
    L_Link p = L;
    while(j <= i){
       p = p->next;
       j++;
    }
    if(p == NULL){
        printf("删除操作：i值不合法！\n");
        return false;
    }
    //先判断目标结点是否是末尾结点
    if(p->next == NULL){
        //是末尾节点，循环找p的直接前驱
        L_Link p_pre = L;
        for(int jj = 0; jj < j-1; jj++){
            p_pre = p_pre->next;
        }
        e = p->data;
        p_pre->next = p->next;
        free(p);
        return true;
    }
    //不是末尾节点，直接操作
    e = p->data;
    p->data = p->next->data;
    p->next = p->next->next;
    free(p);
    return true;
}


//单链表的查找（带头结点）

//按位查找，返回第i个元素（i为位序）
LNode* GetElemById(L_Link L, int i){
    //判断i值合法性
    if(i < 1){
        printf("按位查找：i值不合法！");
        return NULL;
    }
    L_Link p;
    for(int j = 0; p!=NULL && j<i; j++){
        p = p->next;
    }
    return p;
}


//按值查找：找到数据域==e的结点并返回
LNode* GetElemByData(L_Link L, int e){
    L_Link p = L->next;
    while(p!=NULL && p->data!=e){
        p = p->next;
    }
    return p;
}


//求表长
int L_length(L_Link L){
    int len = 0;
    L_Link p = L;
    while(p!=NULL){
        p = p->next;
        len++;
    }
    return len;
}


//单链表的建立——将一些数据转换为链表的形式储存
//尾插法
/*
 * 思路：创建链表的同时创建一个尾指针，新建结点到尾部时直接调用尾指针定位，方便又快捷
 */
//实现：
LNode * creatList_inTail(){
    //创建空表（带一个头结点）
    L_Link L = (L_Link)malloc(sizeof(LNode));
    L->next = NULL;
    L->data = NULL;
    //创建尾指针
    L_Link L_tail = L;
    //循环创建节点
    int x = NULL;
    scanf("请输入要存储的数据（输入999完成输入）：%d", x);
    while(x!=999){
        L_Link q = (L_Link)malloc(sizeof(LNode));
        q->data = x;
        q->next = NULL;
        L_tail->next = q;
        L_tail = q;
        //手动控制循环结束
        scanf("请输入要存储的数据（输入999完成输入）：%d", x);
    }
    return L;
}

//头插法
/*
 * 思路：把尾插法中的尾指针改成头指针
 */
//实现：
L_Link creatList_inHead(){
    L_Link L = (L_Link)malloc(sizeof(LNode));
    L->next = NULL;
    L->data = NULL;
    int x = NULL;
    scanf("请输入要存储的数据（输入999完成输入）：%d", x);
    while(x!=999){
        L_Link q = (L_Link)malloc(sizeof(LNode));
        q->data = x;
        q->next = L->next;
        L->next = q;
        scanf("请输入要存储的数据（输入999完成输入）：%d", x);
    }
    return L;
}
//！！！注！！！采用该方法创建的链表，其存储的数据是与我们输入的数据的顺序相反的，效果就是倒置！


int main(){
    //先声明一个要指向单链表第一个结点的指针L
    L_Link L;
    //初始化
    //增删改查......
    return 0;
}

单链表的判空：判断指针L是否为NULL，是则为空。

2、双链表

双链表就是每个节点都带有两个指针（域）的结点，第一个指针prior指向前一个结点，第二个next指针指向直接后继结点。

解决了单链表无法逆向检索的缺点。

以下讨论的都是带头结点的链表：

（1）初始化

//定义结点结构体
typedef struct doubleList{
    //一个数据域两个指针域
    int data;
    struct doubleList *prior, *next;
}DList, D_Link;

//初始化
D_Link initDList(){
    
}

3、循环单链表

4、循环双链表

5、静态链表

其实就是结构体数组，在内存中申请了一块连续的大空间，用来存放n个结构体结点。每个节点有数据域和游标/指针域。

6、顺序表和链表的比较

（1）逻辑结构

都属于线性表，都是线性结构。

（2）物理结构

顺序表
- 优点：支持随机存储，存储密度高。
- 缺点：大片连续存储空间分配不方便，改变容量不方便。
链表
- 优点：离散的小空间分配方便，改变容量也方便。
- 缺点：不可随机存取，存储密度低。

（3）基本操作总结对比

增、删、改(创销)、查

	增	删	改——创	改——销	查	时间复杂度
顺序表	定位到数组的目标序列，插入值，更改表长	定位到数组的目标序列，删除值，更改表长	①静态分配：创建结构体，结构体属性有两个——数据域和长度标识，数据域为一个数组，用来存放数据；②动态分配：	逐项遍历数组元素并删除，最后更改表长标识	按值查找——逐项遍历对比；按位查找——随机访问	O(n)，主要来自移动元素
链表	先新建结点，再将节点插入其中。①单链表只能从头至尾循环遍历；②双链表可逆向遍历；③链表可任意遍历	先定位到目标节点，再清除数据域，然后更改前后指针，最后释放空间	先创建头指针，如果带头结点就把头指针指到头结点，不带头结点就把头指针指向第一个结点或自身	逐项遍历到尾结点，删除节点属性/数据域，更改前后指针，释放空间	①先判断是否是第一个结点或尾结点；②否，则循环遍历寻找目标	O(n)，主要来自于查找目标元素

🔑数据结构_第二章：线性表

🔑数据结构_第二章：线性表

第二章：线性表

（一）线性表的定义、基本操作概述

1、定义

2、线性表的特点

2、可以进行的基本操作

①改

②查

③增

④删

（二）线性表的顺序表示——顺序表

1、概念

2、特点：

3、基本操作

（1）插入

（2）删除

（3）按值查找（顺序查找）

4、代码实现

（1）顺序表的实现——静态分配

（2）顺序表的实现——动态分配

（三）线性表的链式表示——链表

1、单链表

（1）单链表的创建

（2）单链表的查找

①按位查找

②按值查找

（3）单链表结点的插入

①前插

②后插

2、双链表

（1）初始化

3、循环单链表

4、循环双链表

5、静态链表

6、顺序表和链表的比较

（1）逻辑结构

（2）物理结构

（3）基本操作总结对比

（四）章节练习题