第一章数据结构及算法概念

2020-06-28 专业基础►数据结构数据结构 0 评论字数统计: 5.9k(字) 阅读时长: 20(分)

第一章绪论

1.数据结构的基本概念

数据的基本概念

默认情况下，程序中处理的数据都是数据对象。

数据结构定义

数据结构 = 数据对象 + 结构
结构:数据元素之间的关系

数据结构的组成

逻辑结构：数据元素间的逻辑关系
- 逻辑结构的表示
  - 表
  - 二元组
  - 图形
- 逻辑结构的分类
  - 线性结构
  - 树形结构
  - 集合类结构
  - 图结构
存储结构：数据在计算机存储器中的存储方式就是存储结构。
1. 顺序存储结构
  1. 数组
2. 链式存储结构
  1. 链表
数据运算：数据运算是对数据的操作。分为两个阶段：运算描述和运算实现。

注：

同一逻辑结构可以对应多种存储结构。
同样的运算，在不同的存储结构中，其实现过程是不同的。
不同的实现过程的效率是不一样的。

2.算法及其描述

算法的定义及特性

算法的定义：数据元素之间的关系有逻辑关系和物理关系，对应的运算有基于逻辑结构的运算描述和基于存储结构的运算实现。通常把基于存储结构的运算实现的步骤或过程称为算法。
算法的五个特性：
1. 有穷性：在有穷步之后结束，算法能够停机。
2. 确定性：无二义性。
3. 可行性：可通过基本运算有限次执行来实现，也就是算法中每一个动作能够被机械地执行。
4. 有输入
5. 有输出（即存在数据处理过程）
算法的描述：

算法的分析

算法的时间复杂度分析

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作，如+、-、*、/、++和–等）构成的。算法执行时间取决于两者的综合效果。
算法时间复杂度分析流程：
- 算法时间复杂度：
- 简化分析：在算法分析时，计算T(n)时仅仅考虑基本操作的运算次数。
示例：
- 用修正常量得出循环次数
分析技巧：
- 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)。
- 如果有循环，就计算循环的执行次数。（嵌套循环则是内层循环数等于每层循环次数相乘。计算最内层循环则可得出O(n)。）
常见算法时间复杂度
- 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1),也称作常数阶。
- 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。
- 其余常用的算法时间复杂度还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。
各种时间复杂度比较：
最好、最坏和平均时间复杂度分析
- 时间复杂度存在变数的原因在于，循环的控制语句中存在随条件变化而变化的变量。

算法的空间复杂度

空间复杂度：用于量度一个算法在运行过程中临时占用的存储空间大小。（即只考虑算法执行过程中分配的空间）
一般也作为问题规模n的函数，采用数量级形式描述，记作：S(n)=O(g(n))
特殊：若一个算法的空间复杂度为O(1)，则称此算法为原地工作或就地工作算法。

递归算法的时空复杂度

递归算法中，时空复杂度不仅仅是与问题规模有关的函数，它还与控制递归的递归条件有关。（类似一元函数的讨论变为了多元函数）
例题：
求解递归算法的时空复杂度的关键在于根据递归条件写出递归方程组。

第二章线性表

线性表的定义

线性表是一个具有相同特性的数据元素的有限序列。
特性：
- 相同特性：所有元素属于同一数据类型。
- 有限：数据元素个数是有限的。
- 序列：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。
- 结构：除第一个元素无前驱、最后一个元素无后继外，其余每个元素都有唯一前驱和唯一后继元素。
线性表中所含元素的个数叫做线性表的长度。
线性表的逻辑表示：

线性表的顺序存储结构

线性表的顺序存储结构定义

把线性表中元素按照顺序存储的方法存储（即存储位置为一篇连续的空间，如数组）
静态存储顺序表
- 定义：（意味着last是从0开始的）
- 特性：
  - 随机存取
动态存储顺序表：
- 创建动态存储的顺序表：
  - 关键在于数组的长度是根据具体情况来分配的L->elem = (ElemType *)malloc(maxSize*sizeof(ElemType))

线性表在静态顺序存储结构上的基本运算

1. 求某个元素在顺序表中的序号
- 因为数组中计数是从0开始，而实际生活中数数是从1开始，所以需要i + 1
- 控制条件为找到数组的最后一个元素i <= L.last
1. 求序号为i的数据元素值
- 法一：
  - 注意控制条件，i过大或者过小都会超出数组边界，故需i < 1 || i > L->last +1
- 法二：
- 二者的区别在于直接返回元素的值还是通过指针传递元素的值。
1. 在顺序表的第i个位置插入数据元素 (1 <= i <= last + 2)
- 控制条件：此时插入位置i的范围要比数组原来的范围增加一，因为数组整体要先增加一个位置，所以有i < 1 || i > L->last + 2.
- 关键的元素后移操作：先在数组末尾增加上一个位置，然后从后往前逐次将第i位起的元素后移，for(k = L->last; k >= i - 1 ; k--) L->elem[k+1] = L->elem[k];
- 末尾别忘了last的更改。
- 算法的时间复杂度：
1. 顺序表删除第i个位置的元素（1 < i < last + 1)
- 先将特殊的情况考虑，再做常规处理：i超出数组的范围和顺序表为空的两种情况。i < 1 || i > L->last + 1和L->last < 0.(i = 0 不行是因为此处的i代表的是实际生活中的计数，而不是数组从零开始的计数)
- 关键的元素前移操作：从第i个元素之后的一个元素开始逐渐前移 for(k = i; k <= L->last; k++) L->elem[k-1] = L->elem[k];，控制条件为k <= L ->last的原因是，此时的k作为数组的下标而不是实际生活中的计数，与last的意义相同了，所以不需要再做元素个数与数组下标之间+1 的转换。
- 算法的时间复杂度：

线性表动态顺序存储结构的算法

二路归并算法
- 将两个非递减顺序表合并为一个有序表，称为二路归并。
- 基本原理：同时遍历两个顺序表，遍历过程中比较元素的大小并存入有序表中，并根据比较结果调整两个顺序表遍历的速度。
- 注意：两表的同时遍历进行结束之后，还要检查是否有哪个表没有遍历完。

线性表的链式存储结构

线性表的链式存储结构的定义

链式存储结构即使用链表存储。使用链表时，每个逻辑结点单独存储，为了表示逻辑关系，每个结点里增加一个指针域。
链表的分类：
- 单链表：每个物理结点里增加一个指向后继结点的指针域。
  - 当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。
- 循环单链表：将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。
  - 从表中任一结点出发均可找到链表中其他结点。
  - 链表中没有空指针域（最后一个结点的空指针域现在指向头结点）
- 双向链表: 每个物理结点增加一个指向后继结点和一个指向前驱结点的指针。
  - 从任一结点出啊发可以快速找到其前驱结点和后继结点。
  - 从任一结点出发可以访问其他任一结点。

单链表

结点类型定义

单独创建一个 LinkList类型的目的是区分普通数据结点和头结点。

建表

头插法建表
- 基本原理：
  - 读取是从前往后，但最终形成的链表顺序是原来数据排列方式的从后往前。
  - 最终的表头是一个不含数据的空结点。
- 算法：
  - 每一个结点（包括头结点）都是现场分配的内存。
  - 头结点的指针域始终指向刚插入的结点（开始为NULL除外）。
  - 每次插入操作需将头结点指针域赋给新结点的指针域，然后头结点指针域指向新结点。这样达到断开头结点与旧结点之间的旧链,而形成头结点与新结点之间新链的效果。
尾插法建表：
- 基本原理：
  - 增加一个移动的尾指针，使其一直指向链表的尾结点（开始时指向头结点）
- 算法：
  - 先使用尾指针，使旧尾结点的指针域指向新结点，然后将尾指针指向新结点。
  - 注意：最后要将尾结点的指针域设置为NULL。

求线性表中第i个位置的数据元素

设置一个移动的指针（最开始指向头结点），在计数（从0开始）的同时，移动指针。
在找到第i个元素之前，用循环移动指针。（注意控制条件：计数变量比i小，且不能超出链表元素数目）

按元素值查找

设置一个移动的指针，从第一个有值域的结点开始查找，每一个元素和所找元素比较，若不相等，则指针向后移。

求带头单链表的长度

设置一个移动的指针（开始指向头结点），设置一个计数变量(开始设为0表示头结点的序号为0，不算在数据结点的个数中），每移动一次指针，计数变量加一。
结束的控制条件：最后一个结点的指针域为NULL。

在链表的第i个位置插入数据元素

查找算法和头插法创建链表算法的结合。

删除链表的第i个位置的数据元素

查找到第i-1个结点，利用它的指向后继结点的指针域（所以结束查找的条件是找到第i-1个元素或者当前结点的指针域为NULL），来删除第i个结点。
使用free()来删除一个结点。

合并两个有序链表为一个有序链表

占用其中一个链表来合并
- 基本原理类似二路归并算法
- 设置两个可移动指针，指向原来两个链表的数据元素。
- 新链表头指针指向原来某个链表的头结点，以此来占用该链表的空间。
合并为一个全新的链表
- 所不同的是每一次插入都需要重新分配空间，故采用尾插法重新建立一个链表。
- 最后没有遍历完的结点，需要使用循环来插入新链表中。
- 注意最后新链表尾结点的指针域要置为NULL。

循环单链表

找到尾结点的条件变为：p->next = L。
结点类型：同单链表

初始化循环单链表

形参为指向头结点指针的指针。
最开始时，头结点即为尾结点，故头结点的指针域指向自己。

创建循环单链表

使用尾插法创建循环链表
最后要将尾结点的指针域设为头结点。

循环单链表的合并

传入两个循环单链表的头指针
- 找尾结点的循环：while(p->next != LA) p = p->next;
- 第一个链表的尾结点的指针域设为第二个链表的第一个数据结点（不是头结点），第二个链表的尾结点的指针域设为第一个链表的头结点。
传入两个循环单链表的尾指针
- 先找到两个链表的头结点，在修改各自尾结点的指针域。

双向链表

结点类型定义

建立双向链表

头插法建表
- 头结点刚创立时前后驱指针域都设为空(*L)->prior = (*L)->next = NULL;
- 新插入结点的前驱指针域设为头结点，后驱指针域设为原来头结点后原第一个数据结点。s->next = (*L)->next; s->prior = *L
- 原第一个数据结点的前驱指针需修改为新插入结点(*L)->next->prior = s;,头结点的后驱指针域设为新插入结点(*L)->next = s;
- 头插法的共性是建成的线性表是逆序的；
- 注意：传入函数的是指向头结点指针的指针，又有->的优先级高于*，所以需使用（*L）。
尾插法建表
- 设立一个可移动的尾指针，始终指向当前的尾结点；
- 最后注意将尾结点的后驱指针域设为NULL
- 相较头插法，只需修改两个结点的三个指针域，修改较少。
建表的变式：逆置双向链表
- 本质是头插法的运用;
- 需要新设两个可移动指针来扫描原来的链表。

在第i个位置插入数据元素

本质是头插法
查找第i-1个结点即为尾插法

删除第i个结点

可以找到第i个结点，也可以找第i-1结点；
只需修改两个指针；

循环双向链表

找到尾结点的条件变为了：L->next = L
判断循环链表是否对称相等的算法
- 设置两个可移动指针分别从链表头尾扫描向中间
- 数据结点数目不同，扫描完是两个扫描指针的相对位置不同。为奇数时，最后两个结点指向同一个数据结点p == q;为偶数时，最后两个扫描指针相邻p->next == q或者p == q->prior

线性表的应用

一元多项式的运算

基本原理（一元稀疏多项式的线性表表示）
单链表储存一元多项式的结点定义
创建一元多项式单链表存储的算法
- 尾插法创建
- 需要申请一个空的头结点
两个一元多项式相加的算法
- 默认即将要相加的两个一元多项式是按照次数从小到大排好序的。
- 从头开始遍历，将指数较小的存入新表，两个的指数相等时系数相加后存入新表。
- 采用头插法创建相加后的新表

线性表经典题目

1.删除顺序表中值为x的元素

先找到第一个值为x的元素
之后将其后面值不为x的元素逐个前移
最后修改last的值。因为在移动最后一个元素后，i还加了1，所以L->last = i-1

2.带头结点单链表就地逆置

将原来链表的头结点分离出来。
遍历原来链表的数据结点，然后用头插法插入分离出来的头结点中，从而实现就地逆置。

3.以第一个元素为标准将数据元素分为两边

p1为固定指针，始终指向第一个结点，方便其它结点与第一个结点比较大小。
pre、p、q为一套移动指针，其中p指向当前扫描到的与第一个结点比较大小的结点,q指向当前结点的下一个结点，pre指向当前结点的前一个结点。
pre的作用是当需要把当前结点移走时，能够使其它两个结点能够连起来。pre->next = p->next。
q的作用一方面是使p能够持续进行扫描，另一方面使在中间结点被移走的情况下协同pre建立边上两个结点的联系。

4.存放一个二进制数的链表

二进制的加法关键在于找到第一个值为0的位，然后进行01的互换（怪不得计算机要用二进制，确实好操作）
链表实现加法有两种情况，第一种是，不需增加位数，直接01互换即可；第二种是位数需进一位，此时需要增加一个新结点。
q指针的作用是扫描链表;r指针的作用是指向为最后一个值域为1的结点，若没有则指向头结点；temp指针的作用是在需要新增一个结点时，指向原来的第一个数据结点，以便与新增结点建立连接。

第三章限定性线性表-栈与队列

栈

定义

栈与队列都是特殊的线性表，是操作受限的线性表，称为限定性线性表。
特点：先进后出（FILO:first in last out）或后进先出（LIFO:last in first out）
- 线性表可以在任意位置插入、删除，而栈只允许在栈顶进行插入或者删除操作，故称为操作受限。
典例：

第九章内排序

9.1 排序的概念

排序的定义

所谓排序，是整理表中的记录，使之按关键字递增（或递减）有序排列。

内排序与外排序

在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。

内排序

内排序的分类

基于比较的排序算法
1. 插入排序
2. 交换排序
3. 选择排序
4. 归并排序
不基于比较的排序算法
1. 基数排序

?->基于比较的内排序的时间复杂度

最好的平均时间复杂度： $O(nlog_2(n))$
最好情况是排序序列正序，此时时间复杂度： $O(n)$

内排序算法的稳定性

如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

正序与反序

若待排序的表中元素已按关键字排好序，称此表中元素为正序；
反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反，称此表中元素为反序。
有一些排序算法与初始序列的正序或反序有关，另一些排序算法与初始序列的情况无关。

内排序数据的组织

待排序顺序表的数据元素类型定义：

typedef struct
{
    KeyType key; //关键字项
    InfoType data; //其它数据项
}RecType; // 排序的记录类型定义

9.2 插入排序

概述

基本原理：将无序区的元素逐个插入有序区（局部有序）
分类：
1. 直接插入排序
2. 折半插入排序
3. 希尔排序

1.直接插入排序

基本原理：插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，如此重复，直至完成序列排序。
算法分析：
1. 从序列第一个元素开始，该元素可以认为已经被排序（即有序区第一个元素）
2. 取出下一个元素，设为待插入元素（即放入临时区：因为需要在有序区中插入一个元素，所以有序区得扩充一格，而临时区既能放置未找到位置的新入元素，又能为之后有序区元素的后移提供操作空间），在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。
3. 重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素。
4. 重复2，3步骤，完成排序。（得有两个循环嵌套）
实例演示：
1. 默认序列的第一个元素12已经被排序
2. 取下一元素 15，从后往前与已排序序列一次比较，15插入12 之后，已排序序列为[12，15]。
3. 取下一元素9，重复2步骤，将9插12 之前，已排序序列为[9，12，15]。
4. 循环上述操作，直至最后一个元素24，插入合适位置，完成排序。

直接插入排序代码（c)

void InsertSort(RecType R[],int n)
{
   int i,j;
   RecType temp；

   for(i = 1; i < n; i++){
      temp = R[i]; // 将取出的无序区元素放入临时区
      j = i - 1;   // 找到有序区最后一个元素
      while(j >= 0 && R[j] > temp){
         R[j + 1] = R[j];
         j--;
      } //从后往前逐个扫描有序区元素，直到找到比新入元素小或者相等的元素，同时将比新入元素大的元素这个往后移一位
      R[j] = temp; //将新入元素插入扫描找到的元素之后
   }
}

性能分析
- 时间复杂度：
  - 最好的情况（正序排列）：比较 $n-1$ 次（每个元素只与自己前面的元素比一次，而第一个元素没有前面的元素），时间复杂度为 $O(n)$
  - 最坏的情况（反序排列）：比较 $n(n-1)/2$ 次（每个元素需与自己前面所有元素比一次），时间复杂度 $O(n^2)$
  - 平均时间复杂度： $O(n^2)$
- 空间复杂度：
  - 只有一个临时元素，故空间复杂度为 $O(1)$
- 算法稳定性：
  - 直接插入排序是稳定的排序算法

2.折半插入排序（二分插入排序）

本文链接： http://www.zestaken.top/post/专业基础/数据结构/第一章数据结构及算法概念/index.html

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

Zestaken计算机小白一枚

吾好梦中读书~

第一章 数据结构及算法概念

第一章 绪论