数据结构

2021-02-07, updated 2021-09-12

线性表

抽象数据类型定义:

ADT 线性表(List)

Data
    线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。其中除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitList(*L): 初始化操作,建立一个空的线性表L
    ListEmpty(L): 判断线性表是否为空表,若线性表为空,返回true,否则返回false。
    ClearList(*L): 将线性表清空。
    GetElem(L, i, *e): 将线性表L中的第i个位置元素值返回给e。
    LocateElem(L, e): 在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号,表示成功;否则,返回0表示失败。
    ListInsert(*L, i, e): 在线性表L中第i个位置插入新元素e。
    ListDelete(*L, i, *e): 删除线性表L中第i个位置元素,并用e返回其值。
    ListLength(L): 返回线性表L的元素个数。
endADT

线性表有两种物理存储结构:顺序存储结构和链式存储结构 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

物理上的存储方式事实上就是在内存中找个初始地址,然后通过占位的形式,把一定的内存空间给占了,然后把相同数据类型的数据元素依次放在这块空地中。

顺序存储结构

结构代码:

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length; // 线性表当前长度
} SqList;

顺序存储结构封装需要三个属性:

注意,数组的长度与线性表的当前长度需要区分一下:数组的长度是存放线性表的存储空间的总长度,一般初始化后不变。而线性表的当前长度是线性表中元素的个数,是会变化的。

地址计算方法

假设ElemType占用的是c个存储单元(字节),那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是(LOC表示获得存储位置的函数):LOC(ai+1)=LOC(ai)+c

所以对于第i个数据元素ai的存储位置可以由a1推算得出:LOC(ai)=LOC(a1)+(i-1)*c

通过这个公式,我们可以随时计算出线性表中任意位置的地址,不管它是第一个还是最后一个,都是相同的时间。那么它的存储时间性能当然就为O(1),我们通常称为随机存储结构。

获取元素操作

实现GetElem的具体操作,即将线性表L中的第i个位置元素值返回。就程序而言我们只需要把数组第i-1下标的值返回。

插入操作

删除操作

插入和删除操作时间复杂度 最好的情况:O(1) 最坏的情况:O(n) 平均情况:O((n-1)/2) 简化为O(n)

线性表的优缺点:

优点:

链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以在内存中未被占用的任意位置。

比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址(指针)。

也就是说除了存储其本身的信息外,还需要存储一个指示其直接后继的存储位置的信息。

我们把存储数据元素信息的域成为数据域,把存储直接后继位置的域成为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像,称为结点(Node)。

n个结点链接成一个链表,即为线性表(a1,a2,a3,…,an)的链式存储结构。

因为此链表的每个结点中只包含一个指针域,所以叫做单链表。

单链表

对于线性表来说,总得有个头有个尾,链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针,最后一个结点指针为空(NULL)。

  1. 头指针
  1. 头结点

单链表存储结构

typedef struct Node
{
    ElemType data;  // 数据域
    struct Node* Next;  // 指针域
} Node;
typedef struct Node* LinkList;

获取链表的第i个数据:

循环链表

words: 2075 tags: c