课程笔记--数据结构

以下内容为结合教材内容的个人理解，笔记内容也会随着课程进度随时更新和勘误，如有错误敬请在评论区中指出～

第一章 绪论

1.1 数据结构的研究内容

数据结构是一门研究“非数值”计算的程序设计问题中计算 机的操作对象以及它们之间的关系和操作等的学科。

1.2 基本概念和术语

• 数据：客观事物的符号表示，例如数字、文字、图像
• 数据元素：数据的基本单位，又称元素、结点、记录
• 数据项：组成数据元素、有独立含义的不可分割的最小单位。
• 数据对象：是性质相同的数据元素的集合，不一定是全集。
• 数据结构：存在“关系”的“数据元素”的集合，即Data Structure。分为逻辑与物理结构
  • 逻辑结构：包括四种基本结构：集合、线性结构、树形结构、图状结构，本别是：无对应关系、一对一的关系、一对多的关系、多对多的关系。他们同属一个集合，除了线性结构外，均属于非线性结构。线性结构包括多个特殊的逻辑结构，例如栈与队列等等。
  • 存储结构：数据对象在计算机中的存储表示称为数据的存储结构，也称物理结构。存储现在计算机内部的数据又可以称为结点。有两种不同的存储结构：
    • 顺序存储结构：用存储器相对位置来表示元素间的逻辑关系，例如第50个元素一定在0号元素地址的50个单位空间的后面。因此元素存储是一大片连续的存储空间。
    • 链式存储结构：利用指针实现，无需占用一大块连续的存储空间，仅需要在每一个的结点中附加继元素的指针地址即可。
• 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。
• 抽象数据类型（ADT）：是指用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。例如C语言中的struct。

1.4 算法和算法分析

• 算法：是指对特定问题求解步骤的一种描述，是为了解决某类问题而规定的一个有限长的操作序列。
• 算法的重要特性：有穷性、确定性、可行性、输入、输出。
• 评价算法的标准：正确性、可读性、健壮性、高效性。
• 对于算法高效性的评价标准：时间复杂度、空间复杂度。
  • 时间复杂度的重要概念：
    • 问题规模：是指算法求解问题输入量的多少，一般使用整数n表示。
    • 执行时间T(n)：指其所有语句执行时间的总和
    • 语句的频度f(n)：一条语句的重复执行次数
  • 时间复杂度的重要结论：$T(n)=所有语句的f(n)之和\times执行一次所需要的时间$
  • 时间复杂度的定义：$T(n)=O(f(n))$
  • 时间复杂度的分析：找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)，取其数量级用符号O表示即可。
  • 最好、最坏和平均时间复杂度：例如在查找元素时元素所在的前后位置会影响时间复杂度，我们称在最好的情况下的时间复杂度为最好时间复杂度，反之为最坏时间复杂度。平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。
  • （空间复杂度不讲不考）空间复杂度的概念：分析关于算法的存储空间需求，例如在逆序排列数组元素的算法设计上，设计了两种算法方式，一种是循环n/2次，根据交换每次循环的首尾元素达到逆序；另一种是新开辟一个同样长度的数组，逆序循环一次进行复制到新数组元素中。两种算法中，第一种只是用了一个临时变量用于交换元素，不受问题规模n的影响，我们称之为空间复杂度O(1)；而另一种需要开辟新的长度为n的数组，空间复杂度则为O(n)

第二章 线性表

2.1 线性表的定义和特点

• 线性表：n(n>=0)个数据类型相同的元素构成的有限序列，相邻数据元素之间存在着序偶关系，分为直接前驱与直接后继。
• 线性表的两种存储方式：分为顺序存储（顺序表）、链式存储（链表）

2.4 线性表的顺序表示和实现

• 将线性表中元素存储在一组连续的内存单元中，称顺序表，是一种随机存储结构
• 顺序表的相关操作：
  • 初始化：为顺序表动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址，后将表的length设置为0。
  • 取值：判断第n个数是否合法（即不小于最小的，不大于最大的），随后直接取出对应数值
  • 按值查找：从头开始依次查找，若发现数值相等直接return
    • 算法分析：时间主要耗费在比较上，比较次数取决于查找元素的位置。
    • 平均查找长度：在查找时为确定元素在顺序表中的位置，和给定值进行比较的数据元素个数的期望值。公式：$ASL=\sum_{i=1}^n {p_i}{C_i}$，${p_i}$：查找第i个元素的概率；${C_i}$找到表中其关键字与给定值相等的第i个记录时，给定值已进行过比较的关键字个数；n：线性表的长度。
    • 平均时间复杂度：当查找的元素是顺序表第一个时，${C_i}$为1，最后一个时${C_i}$为n，设每个元素被查到的概率是$p_i=\frac {1} {n}$,则线性表按值查找算法的平均查找长度ASL为：$ASL= \frac {1} {n} \sum_{i=1}^{n}i=\frac{n+1}{2}$，则线性表按值查找算法的平均时间复杂度为O(n)。
  • 插入：末尾插入直接赋值，顺序表中间插入需先把后面的元素依次后挪，随后再插入并赋值length。
    • 算法分析：时间主要耗费在移动元素上，而移动元素的个数取决于插入元素的位置。
    • 移动元素的平均次数：设列表长度为n，$E_{ins}= \sum_{i=1}^{n+1}p_i(n-i+1)=\frac {1}{n+1} \sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2}$
  • 删除：末尾删除直接减去length，中间删除直接将后续的元素前挪，并减去对应的length。
    • 算法分析：时间主要耗费在移动元素上，而移动元素的个数取决于删除元素的位置。
    • 删除元素的平均次数：设列表长度为n，$E_{del}= \sum_{i=1}^{n+1}p_i(n-i+1)=\frac {1}{n+1} \sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2}$
• 顺序表小结：顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观地公式来表示。但是涉及到元素改变时，移动元素的次数较多，时间被大量浪费。

2.5 线性表的链式表示和实现

• 用一组任意的存储单元来存储线性表的数据元素，每个结点包括数据域和指针域，若每个结点只有一个指针域，则称为单链表，指针域存放的是下一个元素的指针（即内存地址），当此结点为尾结点时，指针域设置为空。
• 单链表的逻辑状态：
• 有一种单链表的特殊形态：带头结点的单链表。头结点的数据域可以存一些例如length的信息，也可以不存储信息，指针域指向列表的第一个结点。这样做可以更加方便的处理链表信息。