02 程序设计的挑战 数据结构
**看图**
程序设计的挑战
-
利用计算机解决现实生活中的问题
-
生活中的不同个体间存在联系
-
用计算机程序描述生活中个体间的联系
如何用程序描述生活中的个体？
-
数据的概念
-
程序的操作对象，用于描述客观事物
-
-
数据的特点：
-
可以输入到计算机
-
可以被计算机程序处理
数据不仅包括整形、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。 数据必须具备两个前提：（1）可以输入到计算机中；（2）能被计算机程序处理。对于整型、实型等数值类型，可以进行数值计算；而对于字符数据类型，就需要非数值的处理；而声音、图像、视频等可以通过编码的手段变成字符数据来处理。 -
数据中的新概念
-
数据元素
-
组成数据的基本单位
-
-
数据项
-
一个数据元素由若干数据项组成
-
-
数据对象
-
性质相同的元素的集合
-
-
数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称
-
原子类型。其值不可再分的数据类型
-
结构类型。气质可以在分解为若干成分（分量）的数据类型
-
抽象数据类型。抽象数据组织及与之相关的操作
-
数据实例分析
数据结构
数据结构指数据对象中数据元素之间的关系
-
数据元素之间不是独立的
-
存在特定的关系，这些关系即结构
-
-
例如
-
数组中各个元素之间存在固定的线性关系
-
tips：编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。
逻辑结构
物理（存储）结构
数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：
P:(D,S) --> M
存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U´=succ(U)。
P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。
数据的运算
在数据的逻辑结构上定义的操作，它在数据存储结构上实现
常用数据运算的5钟：
-
插入
-
删除
-
修改
-
查找
-
排序
数据结构三方面的关系
数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。
【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。
数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。
【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。
算法与数据的逻辑结构与物理（存储）结构
算法设计——>逻辑结构
算法实现——>物理结构
本参考文献：
1 http://cskaoyan.com/forum.php 王道论坛数据结构资料
2 https://blog.****.net/wq6ylg08/article/details/104982065 数据结构考研:数据、数据元素、数据项、数据对象、数据结构的区别/详细解释(计算机/软件工程/王道论坛)