[数据结构考研][2][线性表]

2019-12-25 数据结构数据结构 Comments

第 2 章线性表

digraph demo{
    线性表->顺序存储[dir=none];
    线性表->链式存储[dir=none];
    链式存储->单链表[dir=none];
    链式存储->双链表[dir=none];
    链式存储->循环链表[dir=none];
    链式存储->静态链表[dir=none];
    单链表->指针实现[dir=none];
    双链表->指针实现[dir=none];
    循环链表->指针实现[dir=none];
}

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

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

若用 $L$ 命名线性表，则其一般表示为

L=(a_1,a_2,...,a_n)

线性表的逻辑特性

除第一个元素外，每个元素有且仅有一个直接前驱
除最后一个元素外，每个元素有且仅有一个直接后继

线性表的特点有

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

注意: 线性表是一种逻辑结构，表示元素之间的一对一的相邻关系，顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要混淆

2.1.2 线性表的基本操作

数据结构的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作
其他较复杂的操作可以通过基本操作来实现

线性表的主要操作

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$ 所占的内存空间

2.2 线性表的顺序表示

2.2.1 顺序表的定义

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

顺序表的特点是表中元素的逻辑顺序与其物理顺序相同

顺序表支持随机访问，即通过首地址和元素序号可在时间 $O(1)$ 内找到指定的元素

顺序表的存储密度高，每个节点除了数据元素外，不存储其他多余的值

顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素

2.2.2 顺序表上基本操作的实现

1 插入操作

Status ListInsert(SqList *l, int i, ElemType e){
    if(i < 0 || i > l->length){
        return ERROR;
    }
    if(l->length >= l->listsize && OVERFLOW == ReAllocList(l)){
            return OVERFLOW;
    }
    for(int j = l->length - 1; j >= i; j --){
        l->elem[j+1] = l->elem[j]; 
    }
    l->elem[i] = e;
    l->length++;
    return OK;
}

插入操作的时间复杂度

最好情况: 在表尾插入，元素不需要后移，时间复杂度为 $O(1)$
最坏情况: 在表头插入，元素整体都后移，时间复杂度 $O(n)$
平均情况: 时间复杂度为 $O(n)$

\sum_{i=1}^{n+1}p_i(n-i+1)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{n}{2}

2 删除操作

//删除元素
Status ListDelete(SqList *l, int i, ElemType *e){
    if(i < 0 || i > l->length){
        e = NULL;
        return ERROR;
    }
    *e = l->elem[i];
    printf("before: %d\n", e->id);
    for(int j = i; j < l->length - 1; j ++){
        l->elem[j] = l->elem[j+1];
    }
    l->length--;
    printf("after: %d\n", e->id);
    return OK;
}

删除操作的时间复杂度

最好情况: 删除表尾元素( $i=n$ )，无须移动元素，时间复杂度为 $O(1)$
最坏情况: 删除表头元素( $i=1$ )，需要移动所有元素，时间复杂度为 $O(n)$
平均情况: 时间复杂度为 $O(n)$

3 按值查找

//按值查找元素
Status LocateElem(SqList *l, ElemType e, int *locate){
    for(int i = 0; i < l->length; i++){
        if(l->elem[i].id == e.id){
            *locate = i;
            return OK;
        }
    }
    *locate = -1;
    return NOSUCHELEM; 
}

按值查找的时间复杂度

最好情况: 查找的元素就在表头，仅需比较 $1$ 次，时间复杂度为 $O(1)$
最坏情况: 查找的元素在表尾，需比较 $n$ 次，时间复杂度为 $O(n)$
平均情况: 时间复杂度为 $O(n)$

\sum_{i=1}^{n}p_i\times{i}=\sum_{i=1}^{n}\frac{1}{n}\times{i}=\frac{n+1}{2}

2.3 线性表的链式表示

链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻

它通过"链"建立起数据元素之间的逻辑关系，因此对于线性表的插入、删除不需要移动元素，而只需要修改指针

2.3.1 单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素

为了建立数据元素之间的线性关系，对每个链表节点，除存放元素本身的信息外，还需要存放一个指向其后继的指针

单链表中节点类型的描述

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode

非随机存储

由于单链表的元素是离散地分布在存储空间中的
所以单链表是非随机存取的存储结构
不能直接找到表中某个特定的节点

头指针和头节点

通常用头指针来标识一个单链表
为了操作方便，在单链表第一个节点之前附加一个节点，称为头节点。头节点的数据域可以不设任何信息，也可以记录表长等相关信息

头节点和头指针的区别

不管带不带头节点，头指针始终指向链表的第一个节点
而头节点是带头节点的链表中的第一个节点，节点内通常不存储信息

引入头节点之后的优点

由于开始节点的位置被存在头节点的指针域中，所以在链表的第一个位置上的操作与在表的其他位置上的操作一致，无须进行特殊处理
无论链表是否为空，其头指针都指向头节点的非空指针

2.3.2 单链表上基本操作的实现

1 插入操作

Status ListInsert(LinkedList *l, int i, ElemType e){
    printf("ListInsert: %d %d %s\n", i, e.id, e.name);
    if(i < 0 || i > l->length){
        return ERROR;
    }
    LNode *curr = l->head;
    for(int j = 0; j < i; j ++){
        curr = curr->next; 
    }
    LNode *p = (LNode *)malloc(sizeof(LNode));
    p->elem = e;
    printf("AfterInsert: %d %s\n", p->elem.id, p->elem.name);
    p->next = curr->next;
    curr->next = p;
    l->length++;
    return OK;
}

时间复杂度: $O(n)$

扩展: 对某节点的前插操作

前插操作是指在某节点的前面插入一个新节点，与后插操作相反
要找到插入节点的前驱节点，然后对这个节点执行后插操作

2 删除操作

Status ListDelete(LinkedList *l, int i, ElemType *e){
    if(i < 0 || i > l->length){
        e = NULL;
        return ERROR;
    }
    LNode *curr = l->head;
    for(int j = 0; j < i; j ++){
        curr = curr->next; 
    }
    *e = curr->next->elem;//[正确写法]
    printf("Delete: %d %s\n",e->id, e->name);
    curr->next = curr->next->next;
    l->length--;
    return OK;
}

时间复杂度: $O(n)$

扩展:删除节点*p

可以将其后继节点的值赋予其自身，然后删除后继节点
这样可以让时间复杂度为 $O(1)$

3 按序号查找操作

//按位置查找元素
Status GetElem(LinkedList *l, int i, ElemType *e){
    if(i < 0 || i > l->length){
        e = NULL;
        return ERROR;
    }
    LNode *curr = l->head->next;
    for(int j = 0; j < i; j ++){
        curr = curr->next; 
    }
    *e = curr->elem;
    return OK;
}

时间复杂度 $O(n)$

4 按值查找操作

Status LocateElem(LinkedList *l, ElemType e, int *locate){
    LNode *curr = l->head;
    int i = 0;
    while(curr->next != NULL){
        curr = curr->next;
        if(curr->elem.id == e.id){
            *locate = i;
            return OK;
        }
        i ++;
    }
    *locate = -1;
    return NOSUCHELEM;
}

时间复杂度: $O(n)$

2.3.3 双链表

双链表节点中有两个指针prior和next分别指向前驱节点和后继节点

2.3.4 循环链表

1 循环单链表

循环单链表和单链表的区别是，表中最后一个节点的指针不是NULL，而是改为指向头节点，从而整个链表形成一个环

有时对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅设尾指针，从而效率更高，对表头和表尾进行操作都是 $O(1)$

2 循环双链表

略

2.3.5 静态链表

静态链表是借助数组来描述线性表的链式存储结构

节点也有数据域data和指针域next，但是，这里的指针是节点的相对地址(数组下标)

静态链表结构类型如下

#define MAXSIZE 50
typedef struct{
    ElemType data;
    int next;
}SLinkedList[MAXSIZE];

静态链表以next == -1为结束标志

总体来说，静态链表没有单链表使用起来方便

2.3.6 顺序表和链表的比较

1 存取方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素

2 逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻

采用链式存储时，逻辑上相邻的元素，其物理存储位置不一定相邻

3 查找、插入和删除操作

按值查找操作

顺序表无序时，两者的时间复杂度都为 $O(n)$
顺序表有序时，可用折半查找，顺序表时间复杂度为 $O(log_2n)$

按位置查找

顺序表为 $O(1)$
链表为 $O(n)$

插入和删除

链表的插入和删除只需要修改相关节点的指针域；而顺序表平均需要移动半个表长的元素
但是由于链表的每个节点都带有指针域，因而在存储空间上要比顺序存储代价大，存储密度不够大

4 空间分配动态存储

顺序表在静态存储分配情形下，一旦存储空间装满就不能扩充。在动态存储分配下，虽然存储空间可以扩充，但需要移动大量元素，效率很低
链式存储的节点空间只在需要时申请分配，灵活高效

5 如何选择存储结构

基于存储考虑
- 难以估计线性表的长度和存规模时，不宜采用顺序表
基于运算考虑
- 若经常做的运算是按序号访问数据元素，则显然顺序表优于链表
- 若插入和删除操作较多，建议使用链表，因为不需要大量移动元素
基于环境考虑

本文链接： https://t0ugh.biz/2019/12/25/数据结构考研-2-线性表/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

T0UGH

学生&编程爱好者

[数据结构考研][2][线性表]

第 2 章线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

2.1.2 线性表的基本操作

2.2 线性表的顺序表示

2.2.1 顺序表的定义

2.2.2 顺序表上基本操作的实现

1 插入操作

2 删除操作

3 按值查找

2.3 线性表的链式表示

2.3.1 单链表的定义

2.3.2 单链表上基本操作的实现

1 插入操作

2 删除操作

3 按序号查找操作

4 按值查找操作

2.3.3 双链表

2.3.4 循环链表

1 循环单链表

2 循环双链表

2.3.5 静态链表

2.3.6 顺序表和链表的比较

1 存取方式

2 逻辑结构与物理结构

3 查找、插入和删除操作

4 空间分配动态存储

5 如何选择存储结构

T0UGH学生&编程爱好者

[数据结构考研][2][线性表]

第 2 章 线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

2.1.2 线性表的基本操作

2.2 线性表的顺序表示

2.2.1 顺序表的定义

2.2.2 顺序表上基本操作的实现

1 插入操作

2 删除操作

3 按值查找

2.3 线性表的链式表示

2.3.1 单链表的定义

2.3.2 单链表上基本操作的实现

1 插入操作

2 删除操作

3 按序号查找操作

4 按值查找操作

2.3.3 双链表

2.3.4 循环链表

1 循环单链表

2 循环双链表

2.3.5 静态链表

2.3.6 顺序表和链表的比较

1 存取方式

2 逻辑结构与物理结构

3 查找、插入和删除操作

4 空间分配动态存储

5 如何选择存储结构

T0UGH学生&编程爱好者

第 2 章线性表