数据结构-Chap-2

Data Structure
Study Notes
发布日期:   2023-09-24

数据结构 Chap.2 线性表

线性表的概念

线性表是一种最简单的数据结构，其表现为一系列有顺序的元素集合。
自然，线性表需要满足如下标准：

  • 有 第一元素 与 最后元素
  • 除了第一元素之外，每个元素都有它的 后继 ，除了最后元素之外，每个元素都有它的 前驱 。
  • 同一线性表内的元素必定具有相同的特性。

线性表的相关操作

基本操作

首先，我们来了解一些线性表的基本操作。
它们包括：

  • 初始化: InitList
  • 销毁: DestoryList
  • 判断是否为空: ListEmpty
  • 求长度: ListLength
  • 求指定元素的前驱: PriorElem
  • 求指定元素的后继: NextElem
  • 提取指定元素: GetElem
  • 定位: LocateElem
  • 遍历: ListTraverse
  • 置空: ClearList
  • 改变指定元素的值: PutElem
  • 插入元素: ListInsert
  • 删除元素: ListDelete

这里对定位操作进行些许说明：
该操作的意义为在线性表中找到第一个符合某个条件的元素，并返回其位置。
一般而言，若未找到，则返回-1。

需要明确的是，上述表述仅仅关系了这些操作是 做什么的 ，并没有深究应当如何实现这种操作，具体应当如何实现，应当依靠读者使用的语言，采用的具体结构而定。

上述基础运算也可以构成更进一步的应用，如线性表的有序合并，拆分，排序等。

应用事例

两个线性表 LA 与 LB 的合并

该操作可以分为三步：

  • 从LB中依次取出每个元素
  • 观察LB中取出的元素在LA中是否存在
  • 若不存在，则存入LA中

若写成代码块：

void union(List &LA, List LB){
    LA_len = ListLength(LA);
    LB_len = ListLength(LB);
    for(int i = 1 ; i <= LB_len ; i++){
        GetElem(LB, i, e); //取第i个元素赋予e
        if(!LocateElem(LA, e, equal)){
            ListInsert(LA, LA_len, e); //将e插入LA的最后
        }
    }
}

此处，给出了一个很基础的操作代码块，后续在无必要的情况下，将不会这样详细的给出具体步骤。

回归正题，这个算法需要在遍历LB内每个元素的同时也遍历LA中的每个元素来进行查重，因此我们可以计算出其时间复杂度：
O(ListLength(LA) * ListLength(LB))

线性表的顺序表示

前面讲的内容比较概括性，也相对抽象，以下将具体讲述线性表的表示方法。

什么是顺序表示

顺序表示 正如其名，线性表中的数据结构在内存中的表示也是有顺序的，具体表现为前一个元素紧挨着后一个元素。再简单一点，顺序表示可以通俗的理解为C中的 数组 。

用C语言实现线性表的顺序存储

线性表的初始化：InitList

核心：

L.Elem = (ElemType*)malloc(sizeof(ElemType) * List_Elem_Size);

该算法的时间复杂度为O(1)

线性表的容量扩展：ExtendList

核心：

NewBase = (ElemType*)realloc(sizeof(ElemType) * (List_Elem_Size + Expand_Size));

该算法的时间复杂度为O(1)

线性表的元素定位：LocateElem

核心：

while(i<L.length && (!statment)){
    i++;
}
//定位到符合statment语句的元素
return i;

该算法的时间复杂度为O(ListLength(L))

线性表的元素插入：ListInsert

核心：

for(p = &(L.elem[L.length-1]); p>=q; p--){
    *(p+1) = *p;
}
//将插入位置后方的元素分别向后移动一位
*p = e;
//插入元素e

该算法的时间复杂度为O(ListLength(L))

线性表的删除操作与插入操作类似，在此不再详述。

顺序存储线性表的优劣

顺序存储的优点主要表现在以下两方面：

  • 存储时不需要为了表述元素之间的关系而额外花费内存空间
  • 可以实现元素的随机读取

顺序存储的缺点主要表现在以下两方面：

  • 必须分配连续存储空间给线性表，在内存连续片段较小时，有初始化失败的可能性
  • 在插入 / 删除元素时，需要大量移动元素，造成不便

线性表的链式表示

什么是链式表示

链式表示 ， 每个数据元素单独存储，它们在内存中可以是连续的，也可以是分散的，它们之间的关系通过每个数据元素附带的一个指针域进行连接。说的更具体化一些，即用结构体将指针于数据元素包装在一起，它们链式存储中的一个数据元素。在C语言中常常通过链表表示。

链表

这里需要对 链表 这一概念进行引入。
链表即指代如同上述表达中提及的，一个数据域附带一个指针域形成的结构。其主要分为以下几类：

  • 单链表
  • 双链表
  • 循环链表（单 / 双）
  • 静态链表

让我们先从最基础的单链表讲起

单链表

顾名思义，单链表的连接方式是单向的，即我们只能通过前一个元素的指针域找到它的后继，而无法通过后一个元素找到其前驱。
其通常在C语言中以这样的方式进行结点定义：

struct Node{
    ElemType Elem;
    Node* next;
}

我们可以得知，只要得知第一个结点，就可以通过每个结点指针域中的指针得知其下一个结点，从而实现链表的一系列操作，因此，我们一般称单链表的第一个结点为 头结点 。

注：有时为了方便，头结点的数据域中不进行存储。

单链表的操作

单链表的元素提取：List_GetElem

不同于顺序存储，链式存储在提取元素时必须通过头结点分部向后寻找指定位置的元素。

核心：

void List_GetElem (Node* L, int place, ElemType &e){
    p = L->next;
    for(int i=1; i<place; i++){
        p = p->next;
    }
    e = p->Elem;
}

该算法的时间复杂度为O(ListLength(L))

单链表的元素插入：List_Insert

同样，链式存储的元素插入与顺序存储差异极大。
我们需要先找到插入位置的前一个元素，这之后只需要改变这个元素与被插入元素的指针域即可。

核心：

void List_Insert(Node* L, int place, ElemType e){
    Node* new_node = (Node*) malloc(sizeof(Node));
    //链表的每次插入都需要手动创建一个新结点
    p = L->next;
    for(int i=1; i<place-1; i++){
        p = p->next;
    }
    new_node->ElemType = e;
    new_node->next = p->next;
    p->next = new_node;
}

该算法的时间复杂度为O(ListLength(L))

单链表的元素删除相比元素插入仅仅多了一个free（释放内存）的操作，即将删除的结点释放掉，这里不再详述。

单链表的置空操作：ClearList

与删除操作类似。

核心：

void ClearList(Node* L){
    while(L->next){
        Node* p = L->next;
        L->next = p->next;
        free(p);
    }
    L->next = NULL;
}

该算法的时间复杂度为O(ListLength(L))

单链表的改进

从上述应用中我们可以看出，单链表的运用很依赖于链表本身的一些特殊结点与位置，那我们不妨改进一下单链表，单独为它设置一个结构体，用于存储这些特殊的位置和个数。

sruct List{
    Node* Head, Tail;
    int length;
}

通过这种定义，我们可以清晰的明确一个链表的头、尾结点，以及其元素总个数。

单链表：注意事项

可以看到，在以上操作中，我们在函数内对单链表进行操作，往往不会直接使用其头结点，而是单独定义一个指针，再通过移动这个指针来操作链表内的元素。
这是因为，如果直接对头结点的Head指针进行移动，由于函数的参数是Head的地址，因此在函数中你对Head的每一次移动都是永久性的，函数结束后Head指针的地址并不会还原，你会丢失前面的元素。
因此，请务必注意这一点。

其他形式的链表

双链表

双链表 是对单链表的改进，其相比于单链表，一个数据元素占用的内存更大，这是因为它不仅仅能通过一个元素找到它的后继，同时也能找到它的前驱。

我们常常这样定义一个双链表的结点：

struct DuNode{
    ElemType elem;
    //数据域
    DuNode* prior;
    DuNode* next;
    //指针域
}

如上，我们通过prior来指向元素的前驱，通过next来指向元素的后继。

由于指针域的增加，对一个双向链表进行操作时的指针域更改会更加复杂一些，但道理总归相似，请读者自行类比即可。
需要特殊说明的是，双向链表在进行插入、删除操作时，需要更改其前驱的next指针，也需要更改其后继的prior指针。

循环链表

循环链表 是将链表最后一个元素指向了这个链表的头结点，从而实现了让这个链表首尾相接的效果。
此时，判断元素是否是最后一个元素的依据也不是其后继是不是 NULL ，而变成了是不是头结点。

静态链表

静态链表 是在某些没有指针这个设定的高级语言中应用的，它通常这样定义一个结点：

struct StaticNode{
    ElemType elem;
    int cur;
}

上述链表是通过数组来实现的，数组中的一个元素就是一个结点，同时其通过游标cur来表示其结点在链表中的位次。
这种链表通过游标来指示其下一个元素的位置，如：

S[0].cur //这就是链表的第1个元素所在的下标位置
S[1].cur //这是链表第2个元素所在的下标位置

虽然这种链表仍然需要一个相对较大的存储空间，但其在插入 / 删除元素时，仍然只需要改变指针，而不用移动元素，因此其仍然具备链式存储结构的主要优点。

这种链表的顺链查找通常会这样写：

i = S[0].cur; //S[0]相当于头结点
while(i && S[i].data != e){
    i = S[i].cur;
}
return i;

链式存储的优劣

链式存储的优势体现在：

  • 插入 / 删除时，无需大量移动元素
  • 不需要一大块连续的存储空间
  • 扩充表的规模很容易

链式存储的主要劣势：

  • 无法随机访问表内元素，访问时间长短与元素在表内的位置相关。

至此，关于线性表的大致内容梳理完成。

这篇博文就到这里~

文章作者: MUG-chen
文章链接: http://mug-chen.github.io/posts/56162.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 MUG-chen !
Data Structure
  目录