贾攀的流水账

Panmax's Blog

0%

《大话数据结构》阅读笔记

Posted on Valine:

update at 2017-04-12

逻辑结构：指数据对象中数据元素之间的相互关系

1. 集合结构
2. 线性结构
3. 树形结构
4. 图形结构

物理结构：指数据的逻辑结构在计算机中的存储形式

1. 顺序存储结构
2. 链式存储结构

逻辑结构是面相问题的，物理结构是面相计算机的，基本目标就是将数据及其逻辑关系存储到计算机的内存中。

update at 2017-04-13

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

好的算法应该具有正确性、可读性、健壮性、高效率和低存储量的特征

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

update at 2017-04-17

推到大 O 阶：

  1. 用常数 1 取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中，只保留最高阶项。
  3. 如果最高阶项存在且不是 1，则去除与这个项相乘的常数。

得到的结果就是大 O 阶。

update at 2017-04-18

线性表顺序存储结构需要三个属性：

  1. 存储空间的起始位置
  2. 线性表的最大存储容量
  3. 线性表的当前长度

线性表顺序存储结构的优缺点：

优点：

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任一位置的元素

缺点：

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的碎片

update at 2017-04-19

链式结构

为了表示每个数据元素 ai 与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）

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

链表中第一个节点的存储位置叫做头指针

头指针

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

头结点

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

update at 2017-04-20

3.11 顺序结构与单链表结构优缺点

存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

查找

  • 顺序存储结构O(1)
  • 单链表O(n)

插入和删除

  • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
  • 单链表在找出某位置的指针后，插入和删除时间为O(1)

空间性能

  • 顺序存储结构需预分配存储空间，分大了浪费，分小了容易发生上溢
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

结论

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多

3.14 双向链表

线性表的双向链表存储结构

1
2
3
4
5
6
typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
} DulNode, *DuLinkList;

双向链表插入元素

1
2
3
4
s -> prior = p
s -> next = p -> next
p -> next -> prior = s
p -> next = s

双向链表删除元素

1
2
3
p -> prior -> next = p -> next;
p -> next -> prior = p -> prior
free(p);

3.15 回顾总结

线性表的两种结构

4.2 栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）

不含任何数据元素的栈称为空栈，栈又称为后进先出（Last In First Out）的线性表，简称 FIFO 结构。

栈的插入操作叫作进栈，也称压栈、入栈。

栈的删除操作叫做出栈。

4.9 栈的应用 – 四则运算表达式求值

中缀表达式转后缀表达式:

如：9+(3-1)3+10/2 -> 9 3 1 - 3 + 10 2 / +

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是有括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

4.10 队列的定义

队列（queue）是只允许在一段进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

4.12.2 循环队列定义

循环队列满时没我们有两种办法来判断：

  • 办法一是设置一个标志变量 flag，当 front == rear，且 flag == 0 时为队列空，当 front == rear，且 flag = 1 时为队列满。
  • 办法二是当前队列空时，条件就是 front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说队列满时，数组中还有一个空闲单元。如图所示，我们就认为此队列已经满了。

第二种方法，队列满的条件是 (rear+1) % QueueSize == front

计算队列长度公式：(rear-front+Queue) % QueueSize

4.14 总结回顾

对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除时间是 O(n) 的时间复杂度变成了 O(1)。

他们也都可以通过链式存数结构来实现。

5.2 串的定义

串(string)是由零个或多个字符组成的有限序列，又名叫字符串。