前言

作者建议

• 复习C语言基础知识，若无，改写另一种语言

• 阅读第一遍，从头到尾

• 摘抄

• 阅读算法推导过程，一定要运行代码，调试、断点、逐行运行，观察变量情况来理解算法编写原理

• 阅读完每一章，一定要在理解基础上记忆一些关键东西，最佳效果，不看书做到一点不错默写相关算法

• 阅读完每一章，适当练习

• 附录提供参考书目，各有侧重，建议适当阅读

• 从事工作尽量应用，遗忘回顾本书

第1章 绪

数据结构

image.png

• 相互之间存在一种或多种特定关系的数据元素的集合

• 一门研究非数值计算的程序涉及问题种的操作对象，以及它们之间的关系和操作等相关问题的学科

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

1.4 基本概念和术语

数据

定义

• 描述客观事物的符号

• 计算机中可以操作的对象

• 能被计算机识别，并输入给计算机处理的符号集合

类型

• 整型、实型等数值类型

• 字符及声音、图像、视频等非数值类型

  • 编码手段转成字符数据

本质是符号

前提

• 可以输入到计算机中

• 能被计算机程序处理

数据元素

定义

• 组成数据的、有一定意义的基本单元

• 计算机中通常作为整体处理

• 别名：记录

例子

• 人类中人

• 禽畜类中的牛、马、羊、鸡、猪、狗

数据项

定义

• 若干个数据项组成一个数据元素

  • 人→眼、耳、鼻、嘴、手、脚等

• 数据项是数据不可分割的最小单位

数据对象

定义

• 性质相同的数据元素集合，是数据的子集

• 解释

  • 性质相同

    • 数据元素具有相同数量和类型的数据项

      • 人都有姓名、生日、性别等相同的数据项

  • 实际应用

    • 数据对象称为数据

数据结构

定义

• 相互之间存在一种或多种特定关系的数据元素的集合

1.5 逻辑结构与物理结构

逻辑结构

定义

• 数据对象中数据元素之间的相互关系

分类

集合结构

集合中数据元素除了同属于一个集合外，之间没有其他关系，平等

image.png

线性结构

数据元素一对一

image.png

树形结构

一对多层次

image.png

图形结构

多对多

image.png

示意图表示逻辑结构注意

• 每一个数据元素看作一结点，圆圈表示

• 逻辑关系结点之间连线，有方向则带箭头的连线

物理结构（存储结构）

定义

• 数据的逻辑结构在计算机中的存储形式

分类

顺序存储

image.png

• 数据元素存放地址连续的存储单元，数据间的逻辑关系和物理关系一致

• 排队占位、顺序、数组

链式存储

image.png

• 数据元素放在任意的存储单元里，这组存储单元可以是连续、可以不连续

  • 存储关系不反映逻辑关系，因此需要用指针存放数据元素的地址，通过地址找到相关联数据元素的位置

结构小结

• 逻辑结构是面向问题

• 物理结构面向计算机

• 基本目标是将数据及其逻辑关系存储到计算机内存中

1.6 抽象数据类型

数据类型

定义

• 指一组性质相同的值的集合 及 定义在此集合上的一些操作的总称

C语言分类

原子类型

• 不可以再分解的基本类型

  • 整型、实型、字符型等

结构类型

• 若干类型组成，可分解

  • 整型数组由若干整型数据组成

抽象数据类型

抽象的定义

• 抽取出事物具有的普遍性本质

• 对已有数据类型进行抽象

抽象数据类型定义

• 一个数据模型及定义再该模型上的一组操作

• 仅取决于它的一组逻辑特性，与其计算机内部如何表现和实现无关

意义

在于数据类型的数学抽象特性

例子

• point

  • x\y\z三个整型变量

• 马里奥

  • 前进、后退、上、下、跳、打子弹

体现

程序设计中问题分解、抽象和信息隐藏特性