1 数据结构基本概念
1.1 数据结构分类
1. 逻辑结构
集合结构 数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。
线性结构 数据元素之间存在着一对一的对应关系
树形结构 数据元素之间存在着一对多的对应关系
-
网状结构(图形结构) 数据元素之间存在着多对多的对应关系
一般数据结构可以采用一个二元组来表示DataStructure = (D, R) //D 是数据元素的有限集，R是D上的关系有限集。
2. 存储结构
常见的有顺序存储，链式存储，索引存储和散列存储等。
- 顺序存储 把逻辑上相邻的元素存储在物理位置相邻的存储单元中，通常借助数组来实现
- 链式存储 元素间的逻辑关系通过附设的指针字段来实现
1.2 算法的衡量标准
两个衡量算法效率的重要指标。时间复杂度衡量算法的时间开销，空间复杂度衡量算法的空间开销
1. 时间复杂度
时间复杂度就是求基本语句的运行次数，然后取次数最高的。
百度百科解释
2. 空间复杂度
存储空间包括两个不服：
- 固定部分: 程序代码、常量、简单变量等结构变量所占的空间。
- 可变部分: 这部分与处理的特定数据大小和规模相关。
2 线性数据结构
2.1线性表
线性表是最简单、最基本、最常用的一种线形数据结构。它有两种存储方法：顺序存储和链式存储结构，分别成为顺序表和链表
- 逻辑结构是线性结构
- 数据元素的类型相同
1. 顺序表
线性表的顺序存储结构是指在内存中用地址连续的一块存储空间顺序存放线性表的各个元素。顺序表又称为向量。
只要知道顺序表的首地址和每个元素所占地址但愿的个数就可求出第i个数据元素的地址，这也是顺序表具有按数据元素的序号随机存取的特点。
在一般的程序设计语言中，一位数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过了。
| 按值查找 | 插入操作 | 删除操作
------------ | ------------- | -----------|------
时间复杂度 T(n) | O(n) | O(n) | O(n)
2.2 链表
根据需要，链表可分为单链表、双向链表、循环链表
1. 单链表
每个节点只有一个指向后继元素的指。
为了避免“第一个节点”与其它节点在处理中存在差异，引入了头节点的概念。头节点的数据与无定义，指针域存放的是第一个数据节点的地址，空表时为空。
一个节点(Node)结构如下所示:
| Data | Next |
|---|---|
| 数据域 | 指针域：后继地址信息 |
- 插入元素：
头插入：在链表的头部插入节点建立单链表，每次插入修改新插入的元素指向原来头部指向的节点，头部的指针向新插入的元素。这个方法操作简单，但是插入的顺序与逻辑顺序相反。
尾插入：设定一个指针r记录链表最后一个元素位置的地址，如果插入新元素，原来的最后一个元素指向新元素，指针r记录新元素的地址。
前插入: 在指定元素前插入新元素，时间复杂度O(n)
后插入: 在指定元素后插入新元素，时间复杂度O(1)
删除操作: 前一个元素的指针等于要删除的元素元素指针，需要查找p的前驱，所以时间复杂度O(n)
2. 循环链表
将单链表的结尾Null指针改成变为头指针，其它地方基本没有变。
这样的话就可以从链表的任何地方开始遍历，可以提高一定的操作效率。
3. 双向链表
在每一个节点都设置一个前向指针，在牺牲存储空间的条件下达到在每一个节点都可以任意的访问前一个节点。还可以设置成循环链表。
插入操作时
- p->prior->next = s
- s->prior=p->prior
- p->prior = s
- s->next = p
删除操作时 - p->next->prior = p->prior
- p->prior->next = p->next
4. 静态链表
在不支持动态内存的语言里模拟链表，可以利用一个规模较大的数组。
每个元素的也有Data和Next变量。Next的指针是数组的序号
数组下标|0|1|2|3|4|5|6|7|8|9|10
-|-|-|-|-|-|-|-|-|-|-|-|-|-
Data|4|5|7||2|-1|7|1|9||
Next||a4|a2||a1|a5||a3|||
5. 顺序表和链表的比较
| 顺序表 | 链表 |
|---|---|
| 实现简单(一般可用数组表示) | 实现比较复杂 |
| 物理结构即为逻辑结构 | 额外的链指针存储空间 |
| 可以随机按序号访问O(1) | 只能按顺序访问O(n) |
| 插入删除操作需平均移动一半的元素，大的顺序表效率低 | 不需要移动 |
| 需要预分配大量的空间，可能造成内存浪费 | 动态分配内存 |
选择:
- 长度规模难以估算的不宜使用顺序表
- 经常访问数据元素的不宜使用链表，经常插入删除时不宜使用顺序表d
- 顺序表容易实现
2.3 栈
栈是一种特殊的线性表，其数据元素之间的逻辑结构定义与线性表完全相同，但是其基本操作定义不同于普通的线性表。栈是限制在表的一端进行插入和删除的线性表。
允许插入删除的一端称为栈顶
另一个固定端称为栈底
所以栈是一种后进先出(Last In First Out)的线性表，简称LIFO表。同理也可称为FILO。(就像子弹匣)
1. 顺序栈
栈的定义类似于表，栈中的数据元素用一个预设的足够长度的一位数组来实现,栈底位置可以设置在数组的任一个端点，因为栈底是固定的。而栈顶是随着插入和删除数据而变化的，所以我们用一个始终指向栈顶的下标志top作为栈顶指针，指明当前栈顶的位置。通常使用下标0端设为栈底，称为“向上生长”栈。空栈时，栈顶指针top=-1,入栈的时候+1,出栈的时候-1。
数组出栈操作之后， 可能并没清空出栈的元素，在内存里面，这个值不变，但此时的栈顶指针已经移位，来标志已经出栈。
对于出栈操作，要首先判断是否空栈。同样的，入栈操作要先判断是否栈满。
2. 共享栈
为了解决栈溢出的问题，将同一个程序中的两个栈连接在一起，一个采用“向上生长”，一个采用“向下生长”，将空余的部分连接在一起。以此在一个栈溢出时，占取另一个栈的空余空间来存储。
3. 链栈
用链式存储结构实现的栈称为链栈。链栈一般采用单链表表示，其节点结构也与单链表相同。
2.4 队列
队列是一种“先进先出”的数据结构，即插入在表一端进行，而删除在表另一端进行，这种数据结构称为队列。允许插入的一端叫做队头，允许删除的一端叫做队尾。
队列也是一种操作受限制的线性表，简称先进先出表(FIFO)。
1. 顺序队列
队也有两种存储方式，顺序存储和链式存储。顺序存储的队称为顺序队。因为队的队头和队尾都是活动的，因此，除了队列的数据区外，还有两个数组下标，front和rear分别作为队头和队尾的指针。
约定：队尾指针始终指向队尾元素，队头指针指向队头元素的前一个位置。(这只是便于某些操作并不是唯一的方法)。按此约定：
- 空队时
front = rear - 1 - 在不考虑溢出的情况下，元素入队时队尾指针
rear+1指向新元素 - 在不考虑对空的情况下，队头元素出队时队头指针
front+1 - 队中元素的个数
m = rear - front
当删除操作时，虽然比如有容量为10，满容量情况下，删除了一个元素，因为队头前面删除了但却没有往前移动，所以队尾指针仍然处于第10个元素的位置，这种现象称为假溢出。
2. 循环队
循环队正是为了解决假溢出现象而产生。
将入队时队尾指针操作改成 rear = (rear + 1) % MaxSize这样队尾和队头就会首尾相连了。
但是这样子会出现队空和队满无法判断 (都满足rear = front)
解决方法之一就是少用一个元素，这种情况下，队满的条件是 front = (rear+1)%MaxSize 。 能和队空条件 front = rear 区分开来。
另一种解决方法是附设一个存储队中元素个数的变量如num，当 num=0时队空，当num = MaxSize 时队满。
3. 链队列
链式存储的队列称为链队列。用单链来表示链队列，根据队的FIFO原则，为了操作上的方便，分别需要一个头指针front和尾指针rear。
2.5 串
串是一种特殊的线性表, 它的数据元素仅有一个字符组成。计算机非数值处理的对象经常是字符串数组。
1. 串的顺序存储结构
串是字符型的线性表。一般与顺序表比较相似，称为定长顺序存储结构。
三种判定字符床长度的方法
- 类似顺序表，用一个last指针来指向最后一个字符，这种存储伐存储结构可以直接得到字符串的长度为
last + 1。 - 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如在C语言中字符串“\0”结尾。通过判断"\0"所在位置来判断串的长度。
- 用s[0]存放串的实际长度，串值存放在s[1]~s[MaxSize]，字符的序号和存储位置一致，应用更为方便。
2. 串的链式存储结构
链式存储结构比较适合频繁执行插入和删除操作的程序，但是串中的每个数据元素表较小(一般为1个字节)， 链串存储密度会相当低，所以这不是一种理想的存储结构。
3. 串的堆存储结构
在程序中，参与操作的字符串变量之间的长度相差较大，并且操作中串值的长度变化也较大，所以为串变量预先分配固定大小的空间不尽合理。
堆存储结构的基本思想是：在内存中开辟能存储足够多的串、抵制连续的存储空间作为应用程序中所有串的可利用存储空间，称为堆空间。根据每个串的长度，动态地为每个串在堆空间里申请相应大小的存储区域，这个串顺序存储在所申请的存储区域中，在操作过程中若原空间不够了，可以根据串的实际长度重新申请、拷贝原串值后再释放原空间。
2.6 广义表
广义表是线性表的推广，也称为列表(Lists)。列表的元素不一定全是同一种类型。
- 性质
- 广义表是一种多层次的数据结构(像多数组一样，还可以嵌套数组使用)。
- 广义表可以是递归的表。广义表的元素也可以是自身的字表。
- 广义表可以为其他表所共享(就是多远数组一样，数组元素还可以是其它数组)。
