第1章：数据结构与算法

本章目标

了解数据结构
了解算法的设计原则

本章内容

程序设计

什么是程序设计：

程序设计=算法+数据结构

程序设计：为计算机处理问题编制一组指令集

算法：处理问题的策略

数据结构：问题的数学模型

程序设计的实质：

对实际问题选择一个好的数据结构，加之设计一个好的算法。

数据处理的种类

数值数据：整数/实数。

非数值数据：图形/图像/声音。

数值计算

通常可以用一组线性或非线性的代数方程组或微分方程组来描述。

问题：

已知：游泳池的长 len 和宽 wide，求面积 area

分析：

建模型
- 问题涉及的对象:长len，宽wide，面积area
- 对象之间的关系:area = len * wide
设计求解问题的方法
编程

public void GetArea()
{
    Console.WriteLine("请输入长：");
    int len=int.Parse( Console.ReadLine());
    Console.WriteLine("请输入宽：");
    int wide = int.Parse(Console.ReadLine());

    int area=len*wide;

    Console.WriteLine("面积是："+area);
}

非数值计算

对具有一定关系的数据进行组织、管理

示例：学籍档案管理

示例：人机博弈

常用术语

数据
- 是信息的载体，是计算机操作的对象的总称
- 所有能被输入到计算机中，且能够被计算机识别、存储、计算（处理）的符号集合
数据元素
数据项
关键字
数据对象
- 是具有相同特征的数据元素的集合
- 是数据的子集
数据结构
- 相互之间存在一定关系的数据元素的集合
- 不同的“关系”构成不同的“结构”
- 是相互之间存在着某种逻辑关系的数据元素的集合

数据结构

数据结构的研究问题
- 非数值数据之间的数据关系
- 如何表示、如何存储、如何处理
数据结构的地位
- 计算机科学中的一门综合性专业基础课
- 介于数学、计算机硬件、计算机软件之间的一门核心课程
数据结构主要包括
- 逻辑结构
- 存储结构
- 数据运算

提示：

通常习惯说的数据结构一般就是指的逻辑结构

逻辑结构

是指从逻辑关系上描述数据
与数据的存储无关，且独立于语言
又称“抽象结构”
逻辑结构按照数据元素之间的相互关系分为
- 线性结构
  - 指有且仅有一个开始结点和一个终端结点，所有结点都最多只有一个直接前驱和直接后继
  - 常见的线性结构：
    - 线
    - 性表栈
- 非线性结构
  - 指一个结点可能有多个直接前驱和直接后继
  - 常见的非线性结构
    - 树
    - 图

存储结构

存储结构
- 是指数据元素及其关系在计算机存储时如何表示
- 依赖于语言
- 又称为“物理结构”
数据的存储结构要能够正确反映数据元素之间的逻辑关系
按数据结构在计算机内存储方式划分
- 顺序存储结构
  - 把逻辑上相邻的元素存储在物理位置相邻的存储单元中
  - 元素间的逻辑关系由存储单元的相邻关系来体现
- 链式存储结构
  - 对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示
  - 特点:依次,未必连续
- 散列存储结构
  - 通过构造散列函数，用函数的值来确定元素存放的地址
  - 元素ai 的地址 = Hash(ai)
- 索引存储结构
  - 使用附加的索引表
  - 索引表中的每一项称为索引项