数据结构和算法 -- 1.概论

1.1问题求解

• 编写计算机程序的目的

解决实际的应用问题

• 问题抽象

分析和抽象任务需求，建立问题模型

• 数据抽象

确定恰当的数据结构表示数学模型

• 算法抽象

在数据模型的基础上设计合适的算法

• 数据结构+算法，进行程序设计

模拟和解决实际问题

1.2 什么是数据结构

结构:实体+关系

数据结构:

1.png

• 按照逻辑关系组织起来的 一批数据
• 按一定的存储方法把它存 储在计算机中
• 在这些数据上定义了一个 运算的集合

数据结构的逻辑组织 也是逻辑关系

• 线性结构
  • 线性表(表，栈，队列，串等)
• 非线性结构
  • 树(二叉树，Huffman树，
    二叉检索树等)
  • 图(有向图，无向图等)

图>=(包含)树>=(包含)二叉树>=(包含)线性表

数据结构的存储结构

顺序结构和链接结构适用在内存结构中。

索引结构和散列结构适用在外存与内存交互结构

• 顺序结构

  在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构

  • 随机存取表中元素
  • 插入和删除操作需要移动元素

• 链接存储

  在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点

  • 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
  • 逻辑上相邻的节点物理上不必相邻
  • 插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
  • 查找结点时链式存储要比顺序存储慢。
  • 每个结点是由数据域和指针域组成。

• 索引存储

  除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

  索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。在数据表中，就是用索引键来进行存储与检索的。

• 散列存储

  散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

抽象数据类型

简称ADT (Abstract Data Type),定义了一组运算的数学模型,与物理存储结构无关,使软件系统建立在数据之上(面向对象).

模块化的思想的发展,隐藏运算实现的细节和内部数据结构,软件复用,ADT 不关心存储细节

抽象数据类型ADT

• 抽象数据结构二元组 <数据对象D，数据操作P>
• 先定义逻辑结构，再定义运算
  • 逻辑结构:数据对象及其关系
  • 运算:数据操作

1.3 算法

算法的特性

• 通用性
• 有效性
• 有效性
• 有穷性

基本算法分类

• 穷举法. 顺序找K值
• 回溯、搜索. 八皇后、树和图遍历
• 递归分治 二分找 K 值、快速排序、归并排序
• 贪心法 Huffman 编码树、最短路 Dijkstra 算法、最小生成树 Prim 算法
• 动态规划 最短路 Floyd 算法

1.4 算法复杂性分析

算法渐进分析:大O表式法

T(n)=O(f(n))
其中，T(n)就是算法的时间复杂度；问题规模为n,f(n)表示执行与算法优劣和问题规模有关的执行数；O()表示一种运算符号，和+-*/类似。作用就是去除其他项，包括与最高项相乘的常数，只保留最高项，比如f(n)=2n^{2+1,O(f(n))=O(n}2)