数据结构-李春葆版-第一章-数据结构概述

DataStructure第一课数据结构概述数据结构是一门研究非数值性程序设计中计算机操作的对象以及它们的关系和运算等的学科。数据结构在计算机科学中是一门综合性的专业基础课，是介于数学、计算机硬件和软件三者之间的一门核心课程。早期的数据结构被视为图论，特别是表、树、图理论的同义语，后来逐渐扩充到包括网络、集合代数论、格、关系、文件管理（大型文件的组织）等方面。也被称为《离散结构》。1968年美国唐.欧.克努特教授所著《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构及其运算的著作。数据结构课程由此成为一门独立的课程。DataStructure研究数据结构的重要性要设计出好的语言程序，必须研究数据的特性以及数据之间存在的关系。数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。随着软件的发展，人们越来越重视数据结构，认为程序设计的实质就是：对确定的问题选择一种好的数据结构并基于特定数据结构设计出好的算法。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都主要依赖于是否选择了最优的数据结构。学习数据结构课程，主要是学习用计算机实现数据组织和数据处理的方法。DataStructure教材及参考书教材数据结构教程（第3版）李春葆尹为民李蓉蓉等编著，清华大学出版社，2009年参考书数据结构（C语言版）黄国瑜叶乃菁编著，清华大学出版社，2001年数据结构（C语言版）严蔚敏吴伟民编著，清华大学出版社，2007年上机实验实验教材：《数据结构教程（第3版）上机实验指导》李春葆尹为民李蓉蓉等编著，清华大学出版社，2009年软件环境：VC/VC++6.0DataStructure课程学习理论学习54学时掌握基本概念，善于归纳知识点重视算法设计思想、效率分析及算法实现反复理解记忆，做好阶段性总结多做习题实践学习18学时重视上机实验机会，勤思考，多动手多看算法，尝试运行一些典型算法自主设计算法并实现DataStructure课程考评平时成绩（30%）书面作业（10%）上机实验（20%）期末考试（70%）DataStructure课程内容安排数据结构基础部分36学时第1章：绪论3学时第2章：线性表5学时第3章：栈和队列5学时第4章：串3学时第5章：数组和广义表3学时第6章：递归3学时第7章：树和二叉树8学时第8章：图6学时DataStructure课程内容安排数据结构基础应用部分14学时第9章：查找6学时第10章：内排序6学时第11章：外排序2学时数据结构扩展部分4学时第12章：文件2学时第13章：采用面向对象的方法描述算法2学时DataStructure§1.1数据结构概念一、几个基本术语数据（data）：描述客观事物的数、字符、图形、声音等媒体信息。数据元素（dataelement）：数据的基本单位。数据集合中的一个个体。有时一个数据元素可由若干个数据项组成，数据项是数据的最小单位，例如图书管理表的每一行是一本书的信息，称为一个数据元素，其中的每一项（书名、作者等）为一个数据项。DataStructure数据对象（dataobject）：具有相同特性的数据元素的集合，是数据的一个子集。例如：整数的数据对象是集合N=｛0,±1,±2,＋3…｝，字母字符的数据对象是集合C=｛A,B,C,D…..｝等等。数据类型（datatype）：程序设计语言中变量（变量空间受字长（操作平台）影响）所能表示并存储的数据种类。一种数据类型中所有可能元素的集合又称为数据实体。当针对数据值有范围的具体问题时，数据实体也可视为数据对象的子集。（类型—值集、操作集）几个基本术语DataStructure数据结构（datastructure）：大致说来就是数据实体中元素之间的关系，包括数据的表示方法和运算。也就是带有结构的数据元素的集合。从上述三个例子我们看到，被计算机加工的数据元素（如：一本书的信息、棋盘的一个格局、一条可行的通路等）都不是孤立的，它们之间都存在着某种联系，这种相互之间的关系，我们就称之为结构。可用二元组描述数据结构：B=(D,R)D={di|1≤i≤n,n≥0}d表示数据集合中第i个结点或数据元素R={rj|1≤j≤m,m≥0}r是R中的一个关系，是序偶的集合如果数据元素之间的关系都很简单，我们就称之为初等数据结构。此外还包括数据间的逻辑结构、在计算机中的存贮结构（物理结构）等。几个基本术语二、逻辑数据结构类型集合线性结构树形结构图形结构三、数据结构存储类型顺序存储结构1）使用数组描述；2）元素之间的逻辑关系描述不占用存储空间；3）元素具备随机访问特性；4）静态存储结构，不便于修改。链式存储结构1）使用链表描述；2）元素之间的逻辑关系描述需占用存储空间；3）元素不具备随机访问特性；4）动态存储结构，便于修改。索引存储结构1）除存储元素外，还需存储元素的索引表；2）元素具备随机访问特性。哈希（散列）存储结构DataStructure四、数据结构与数据类型的关系数据类型是一个值的集合与定义在该值集上的操作集的总称。简单数据类型：如整数、实数、字符、指针、枚举量等结构数据类型：如数组、结构体等简单数据类型组合数据类型也可被定义为是一种数据结构和基于该数据结构的运算集。数据结构是计算机所处理数据元素的组织形式和相互关系；数据类型是程序设计语言中已实现的数据结构。C/C++中的数据类型：基本数据类型：int、fioat、char指针类型数组类型结构体类型共用体类型自定义类型DataStructure数据结构与数据类型的关系抽象数据类型（AbstractDataType,ADT）指用户进行软件系统设计时，从问题中抽象出的逻辑数据结构和基于逻辑数据结构的运算。抽象数据类型一般包括：数据对象；数据关系；基本运算。可用三元组（D,S,P）表示。抽象数据类型格式定义：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本运算：基本运算的定义}ADT抽象数据类型名抽象数据类型的两个重要特征：数据抽象；数据封装。抽象数据类型需要通过固有数据类型来实现。如C++中的类。DataStructure§1.2算法及其描述一、算法定义针对每个欲解决的问题，我们事先要设计出解决的步骤，算法就是用来说明工作完成的步骤。算法就是一个具有次序、步骤清楚，最后会执行结束的可执行步骤。二、算法必须满足的条件输入：不具有输入数据或具有多个输入数据。输出：具有一个以上的结果输出。定义明确：每一个步骤必须使用明确的语句加以说明。有限的步骤：按照算法所描述的步骤执行，在有限步骤内必须结束。即必须步骤明确地描述出最终结果。有效率的步骤：算法中的每一个步骤必须是基本的指令，能够保证有效执行。三、算法的衡量因素衡量一个算法的好坏，通常要考虑三方面因素：依据算法编制成程序后在计算机中运行所消耗的时间。依据算法编制成程序后在计算机中所占存储量的大小，主要考虑程序运行时所需辅助存储量的大小。其它：是否易读、是否容易转换成任何其他可运行的语言编制的程序、是否容易测试等。四、算法描述方式条列式：逐条列出步骤描述算法图形：流程图、盒图等伪码（PDL语言）：语法和自然语言（如中文、英文等）混杂的形式来描述问题解决的方法。也可称之为类程序语言。程序语句：直接用程序语句描述问题解法。DataStructure图1.1程序流程图DataStructure1.2五、程序结构化与设计风格1、结构化程序设计结构化的程序必须有特定的、被公认的程序编写方式。程序结构化的主要内容就是“模块化”（Modularity）。软件工程学对于程序结构化的定义是：如果一个程序的代码块仅仅通过顺序、选择、循环三种基本控制结构连接，并且每个代码块只有一个入口和一个出口，则称这个程序是结构化的。这种代码块（模块）的功能应该是高内聚低耦合（互相渗透、有交集、公用数据区等）的。结构化程序设计大致分为两种方式：传统的由上而下方式：传统的结构化语言如C、PASCAL、ADA、ALGOL等。面向对象问题的由下而上方式：如Java、C++、C#等等都是面向对象设计的高级语言。每个模块都有隐蔽的内部结构和透明的接口，通用性很强，并且功能独立。2、程序设计风格源程序代码的逻辑简明清晰、易读易懂是好的程序的一个重要标准。要遵循通用的编码风格。程序内部的文档：要求标识符恰当、注解适当、程序视觉组织好等。注释变量命名程序缩排段落数据说明：使用到的变量与数据结构要求有次序，对复杂的数据结构要注解其实现方法和特点等。语句构造：每个语句都应该简单直接，不能为了提高效率而使程序复杂化。输入输出风格：保持输入格式简单；使用数据结束标志（不要指望客户）；明确交互输入的提示和请求；设计良好的输出表和输出标志。效率：主要指处理机时间和存储器容量两个方面。DataStructure§1.2算法分析程序分析的方法：时间分析法、空间分析法一、时间分析法通常以运行时间来分析程序，判断程序的运行效率。分为事前预测和事后测试两种。指令的运行时间除了受到输入的数据总量等主观因素影响外，还会受到软硬件环境等客观因素的影响，比如机器速度、指令集（是否具备某种算法的指令）、指令周期、编译器（软件范畴）的影响，所以，最终我们以程序语句的执行次数（频度-frequencycount）作为时间量度，来做为程序效率分析的标准。1、时间复杂度概念理论上讲，每个程序的运行次数可称为该程序的时间复杂度（Timecomplexity）。从现实来讲，通常只能以一个“概量”来分析程序的运行效率，即渐近的时间复杂度。评价算法的时间性能时，主要标准就是算法的渐近时间复杂度。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数（例如是以相关的数据笔数n为参数的函数式），也称为语句频度或时间频度，用T(n)表示。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n）/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=Ｏ(f(n))，称Ｏ(f(n))为算法的渐进时间复杂度。经常是将渐近时间复杂度O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。2、不同时间频度的复杂度表示算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。如：输入数据的范围（Inputsize）和输入值(Inputvalue)。通常总是考虑在最坏的情况下的时间复杂度，以保证算法的运行时间不会比它更长。在时间频度不相同时，时间复杂度有可能相同。如T(n)=n2+3n+4与T(n)=4n2+2n+1，它们的频度不同，但时间复杂度相同，都为O(n2)。若算法中语句执行次数为一个常数，则时间复杂度为O(1)。实际应用中，除T(n)之外，有关时间效率的描述方式通常还有如下几种表示：最佳状况的时间复杂度（Best-casetimecomplexity）：记做B(n)最坏状况的时间复杂度（Worst-casetimecomplexity）：记做W(n)一般状况的时间复杂度（Every-casetimecomplexity）：记做E(n)E(n)可视为恒定值，不因输入值或输入数据个数而变化平均状况的时间复杂度（Average-casetimecomplexity）：记做A(n)若一般状况的时间复杂度存在，则E(n)=A(n)=W(n)=B(n)3、时间复杂度的等级常见的时间复杂度，按数量级递增排列依次为：常数时间算法：时间复杂度的函数式为“c”（c0），时间复杂度为O(1)，也称为常数阶或常数时间。线性时间算法：时间复杂度的函数式为“an+b”（a0，b=0），时间复杂度为O(n)，也称为线性阶或线性时