数据结构

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;

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

存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
线性表的最大存储容量：数组的长度MaxSize。
线性表的当前长度：length。

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

地址计算方法

假设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下标的值返回。

插入操作

如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；
从最后一个元素开始开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
将要插入元素填入位置i出
线性表长+1

删除操作

如果删除的位置不合理，抛出异常
取出删除元素；
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
表长 -1

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

线性表的优缺点：

优点：

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速地存取表中任意位置的元素。缺点
插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量。
容易造成存储空间的“碎片”

链式存储结构

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

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

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

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

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

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

单链表

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

头指针

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
头指针具有标识作用，所以常用头指针冠以链表的名字（指针变量的名字）。
无论链表是否为空，头指针均不为空。
头指针是链表的必要元素。

头结点

头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（但也可以用来存放链表的长度）。
有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
头结点不一定是链表的必须要素。

单链表存储结构

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

获取链表的第i个数据：

声明一个结点p指向链表第一个结点，初始化j从1开始
当j<1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j+1
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，返回结点p的数据

循环链表

words: 2075 tags: c