数据结构（C++语言描述）.pptx

第一章绪论;数据结构

算法

C++部分概念;数据：外界信息进入计算机后，统称为数据。

一般分为数值和非数值型。

数据元素：是数据处理的最小单位，是一个数据个体。

如处理某窗口前的队列，队列中所有人的信息称数据，

每个人的信息称数据元素。;数据结构：有限个、类型相同、相互之间具有一定制约关系的数据元素

组成的集合。

如某窗口前的队列，有限/类型相同/你先我后关系。

几种典型结构：

;数据结构研究内容：（以队列为例）

逻辑关系（逻辑结构）+基本操作（关系操作）

------来源于生活实践，和计算机无关。

存储实现（物理结构）------数据及数据关系在内存中的存储。

基本操作的实现------某种存储处理下各种基本操作的实现。

典型应用------这种数据结构在生活实践中的典型应用。;指类型相同的一组元素和元素间的关系。根据关系不同，可分为以下几种：

集合关系：不同元素除了同属于一个集合，相互间无其他制约关系。

线性关系：元素间呈现你先我后的顺序，是一种一对一的关系。

树形关系：元素间呈现一对多的关系。

图关系：元素间呈现多对多的关系。;?;具有某种关系的数据在生活实践中表现出的几种功能相对独立的数据处理（操作）。

它和数据的逻辑结构紧密相关，它来源于现实生活中关系自身的特点。

无论哪种逻辑结构，基本操作都可分为五大类：

构造类、属性类、数据操纵类、遍历类和典型应用类。;构造类：在内存中建立这种数据结构。如一个队列，有存储空间，无或有若干元素。

属性类：对元素及元素之间关系的各类查询。属于东瞧瞧、西看看，不影响元素值及元素关系。如在线性结构中查询值为X的元素是否存在，队列中队首是谁。

数据操纵类：对元素或元素关系有改变的操作。如插入或删除某个元素，一般修改可以视作在同一位置上先删除一个旧元素后再插入一个新元素，因此不再讨论修改。

遍历类：对结构中的每个元素访问且只访问一遍。因其重要且有时又较复杂，常常是其他操作的基础，如遍历树结构、图结构中的元素，所以特意把遍历操作从属性类中单独拿出来研究。

典型应用类???每种结构独特的应用。不同结构其典型应用各不相同，如线性结构可以解决队列问题、图结构可以解决两个城市间最短路径问题。;数据结构在内存中的表示。

数据要得到处理首先必须进入内存。内存中不仅要存储数据元素的值，还要存储元素间的关系。

任何一种数据结构基本操作的设计取决于其逻辑结构，但基本操作的实现完全依赖其存储结构。

元素及其关系在内存中用什么结构存储适合，原则是存储方式要有利于基本操作的实现。;顺序存储：

用一块连续的空间存储数据，借助空间地址上的有序性存储元素间的关系。顺序存储的结构以下称顺序结构。

高级语言中，数组是地址连续的空间，有助于实现顺序结构。

链式存储：

元素可以各自存储在独立的空间中，不要求不同数据存储的内存空间连续，元素间的关系附带存储在数据各自占据的独立空间中。

数据结构的链式存储也称链式结构。;存储数据及其关系的目的就是为了处理。

基本操作实现方法以存储方法为基础。如果是顺序结构，操作实现就是对数组做各种不同的操作；如果是链式结构，操作实现就是对链表做各种不同的操作。

同一种操作虽然在顺序结构和链式结构中具体实现方法不同，但目标都要符合ADT对基本操作定义的条件和结果。

如果某种存储方式下，基本操作不易实现，说明存储方式不好，可以考虑放弃这种存储方法。;数据结构

算法

C++部分概念;算法具有5个特性：

确定性：每一步有确定的含义，没有二义性。

有穷性：每一步在有限的时间内完成，整个算法必须在有限步之后完成。

可行性：每一步都是经过有限次基本操作可以完成，自身没有复杂的算法。

有输入：一个算法可以有零个或者若干个输入作为解决问题的已知条件。

有输出：有零个或者若干个输出作为算法运行结果。;正确性：准确反映并能满足具体问题的要求。

可读性：可供人们阅读的容易程度。

健壮性：对各种不同的输入都要有相应的反应

时间效率：算法的执行时间。

空间效率：算法执行期间所需要的最大内存空间。;比如：选最大桔子问题，体育课排队，5个数字的加法。

正确的方式：计算思维，具体从编程语言出发。

具体编程语言：输入、输出、赋值、两两比较、算术和逻辑运算，循环、函数（递归）等。

如冒泡排序，选择排序的设计思想

;算法的执行时间是指依据算法编制的程序运行时所消耗的时间。

度量方法有运行后度量和运行前分析。

运行后度量：指根据不同算法事先编制好的程序和同样的测试数据，在程序运行时借助机器的计时功能进行计时。当不同程序运行结束时，分别记录实际的运行时间并进行比较。

运行前分析：指在算法设计后，在实现程序运行前，根据几个方面的影响因素对算法的执行时间进行分析。;机器的运算速度：根据主频和字长。