数据结构（1）
第一章 数据结构
一、计算机求解问题的一般步骤
1).编写解决实际问题的程序的一般过程
-
如何用数据形式描述问题？------即由问题抽象出一个适当的数学模型；
-
问题所涉及的数据量大小及数据之间的关系；
-
如何在计算机中存储数据及体现数据之间的关系？
-
处理问题时需要对数据作何种运算？
-
所编写的程序的性能是否良好？
2).为什么学？学什么？学习目标？
-
学习数据结构就是要
-
学会高效地利用计算机，有效地存储、组织、传递和转换数据；
-
掌握各类数据结构功能、表示、实现和基本操作接口；
-
理解各类基本算法与不同数据结构之间的内在联系；
-
了解各类数据结构适用的应用环境；
-
灵活地选用各类基本算法及对应的数据结构，解决实际问题；
-
二.数据结构
1).数据结构的定义
-
程序设计：为计算机处理问题编制一组指令集
-
算法：处理问题的策略
-
叔觉得组织与操作
数据集+关系+操作
2).数据结构的基本概念
数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’ , ’B’ , ’C,…}。
3).数据结构研究的主要内容
-
概括的说：
数据结构是一门研究“非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作”的学科。
-
具体的说：
-数据结构主要研究数据之间有哪些结构关系，如何表示，如何存储，如何处理。
4).数据结构的逻辑结构
-
数据的逻辑结构
——描述数据间的逻辑关系
-
四类逻辑结构
-
①集合关系
-
②线性关系
-
③树型关系
-
④图型关系
-
-
数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。
① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
② 线性结构：结构中的数据元素之间存在一对一的关系。
③ 树型结构：结构中的数据元素之间存在一对多的关系。
④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
5).数据的存储结构（物理结构）
-
数据的存储结构
—— 逻辑结构在存储器中的映象
-
存储结构包含以下两个方面：
-
“数据元素“的映像
-
“关系“的映像
-
1.存储结构
(1). 顺序存储
用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
(2). 链式存储
在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。
6).逻辑结构和存储结构（物理结构）的关系
-
数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
-
数据结构的三个组成部分：
1. 逻辑结构： 数据元素之间逻辑关系的描述
2. 存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
3. 数据操作： 对数据要进行的运算。
7).数据结构的运算
数据结构的主要运算包括：
⑴ 建立(Create)一个数据结构；
⑵ 消除(Destroy)一个数据结构；
⑶ 从一个数据结构中删除(Delete)一个数据元素；
⑷ 把一个数据元素插入(Insert)到一个数据结构中；
⑸ 对一个数据结构进行访问(Access)；
⑹ 对一个数据结构(中的数据元素)进行修改(Modify)；
⑺ 对一个数据结构进行排序(Sort)；
⑻ 对一个数据结构进行查找(Search)。
三 .数据类型
-
数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。
-
数据类型是和数据结构密切相关的一个概念。 在C语言中数据类型有：基本类型和构造类型。
-
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
1).抽象数据类型
抽象数据类型(Abstract Data Type ，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。
ADT的一般定义形式是：
ADT <抽象数据类型名>{
数据对象： <数据对象的定义>
数据关系： <数据关系的定义>
基本操作： <基本操作的定义>
} ADT <抽象数据类型名>
– 其中数据对象和数据关系的定义用伪码描述。
– 基本操作的定义是：
<基本操作名>(<参数表>)
初始条件： <初始条件描述>
操作结果： <操作结果描述>
初始条件：描述操作执行之前数据结构和参数应满足的条件; 若不满足，则操作失败，返回相应的出错信息。
操作结果：描述操作正常完成之后，数据结构的变化状况和应返回的结果。
ADT特征
特征一：数据抽象
用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
特征二：数据封装
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节
2).抽象数据类型与算法
抽象数据类型带给算法设计的好处有：
（1）算法顶层设计与底层实现分离；
（2）算法设计与数据结构设计隔开，允许数据结构自由选择；
（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；
（4）用抽象数据类型表述的算法具有很好的可维护性；
（5）算法自然呈现模块化；
（6）为自顶向下逐步求精和模块化提供有效途径和工具；
（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
嵌入式系统软件中数据结构的特点
1. 数据规模小
2. 采用简单的数据结构
3. 采用RAM资源占用比较少的算法
4. 采用程序代码简单的算法
原文地址：https://blog.csdn.net/m0_71616132/article/details/143650686
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！