数据结构-线性表

数据结构-线性表

本文仅对线性表进行简单叙述，具体实现会专门出教程，并在具体的数据结构后面给出链接。

定义：线性表是具有相同数据类型的n个元素的有限序列

基本操作： 初始化、取值、查找、插入、删除、判空、销毁

线性表的顺序表示-顺序表

我们可以这样定义顺序表

1
2
3
4
5
#define MAXSIZE 100
typedef struct{
    int data[MAXSIZE];  //顺序表的元素(假设类型为int，本文元素均以int为例)
    int lenth; //顺序表的当前长度
}SqList;

当然，如果我们想要通过动态分配的顺序表，只需要让data成为一个指针，并且结构体中存在MaxSize描述当前最大容量即可。

特点：逻辑位置与其存储的物理顺序相同

优点：

  • 可随机访问（取值的时间复杂度为O(1)）
  • 存储密度高

缺点：

  • 插入和删除的时间花费较大

线性表的存储表示-链表

为了避免顺序表插入和删除的线性开销，我们可以允许表不连续存储，于是链表应运而生

我们常常使用头节点head置于链表最前端，其data域无任何东西，优点如下

1.第一个节点存放在头节点的指针域中，与其他节点一样，无需特殊处理

2.对空表和非空表的处理有了统一的标准(head->next是否为空)

单链表

我们可以这样定义一个简单的单链表

1
2
3
4
typedef struct LNode{ //LNode为链表节点
    int data;	//链表节点对应的元素
    struct LNode *next;	//指向下一个链表节点的指针
}*LinkedList;

我们使得*LNode， 即LinkedList来代表链表。

通过结构体指针next, 我们就可以遍历链表的所有元素。

双向链表

我们可以这样定义一个简单的双向链表

1
2
3
4
5
typedef struct LNode{
    int data;
    struct LNode *pre; //指向该节点的前驱
    struct LNode *next //指向该节点的后继
}

循环链表

单链表和双向链表都有其循环形式，结构体形式不需要做出任何改变，我们只需要它最后一个节点的后继是第一个节点即可，这样链表就形成了一个环。

受限线性表: 栈、队列

它们都是一种线性表，只不过对于它们的功能都进行了限制，只能进行线性表的某些功能，这使得它们的特点和用途更加鲜明，功能更简洁。

栈

栈是一种只能在一端进行插入和删除的数据结构。就像我们整齐地放书本一样，我们只允许最后放的书可以被拿走或用新的书放在其上面。这种操作特性被称为”后进先出“

其中，栈的最后一个元素被称作栈顶元素。

栈实现的功能主要有两个：

pop: 弹出栈顶元素

push: 将元素压入栈顶

有时也会实现get top功能，即返回栈顶元素的值，而不弹出。

队列

队列是一种只能在一端进行删除，在另一端进行插入的数据结构。词如其名，正如我们排队一样，存在着”先进先出“的操作特性

队尾：进行插入的一端

队头(队首)：进行删除的一端

enQueue: 入队, 将元素放在队尾

deQueue: 出队, 删除队头元素

栈和队列都是一种逻辑结构，都可以通过顺序存储和链式存储实现。

线性表的推广: 数组

数组是由n个相同类型的数据元素构成的有限序列，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组是线性表的推广。一维数组可视为一个线性表，二位数组可视为其元素是定长数组的线性表，以此类推。

​ 数组一旦被定义，其维界就会确定，只能在该维界内存取元素和修改元素。

对于一维数组，其存储结构关系为:

LOC(ai) = LOC(a0) + i * L

二维数组(i为高维，j为低维):

LOC(aij) = LOC(a0) + i * row + j

多维数组以此类推。