资源描述：
《第2章 常用数据结构及其运算12》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章常用数据结构及其运算石油工程学院概述图查找排序第二章常用的数据结构及其运算树与二叉树数组线性表——栈线性表——顺序表线性表——队列线性表——链表2.72.92.82.12.22.32.52.62.42.10数据处理是指对数据集合中各元素以各种方式进行运算，包括插入、删除、查找、更改、分析。数据处理效率指的是：（1）数据处理速度；（2）数据处理过程中占用的计算机存储空间2.1数据结构概述数据处理的关键问题是：合理组织大量数据元素在计算机中的存储关系，以提高数据处理效率，节省计算机存储空间。2.1数据结构概述数据结构作为一门学科，主要研究以下问题：（1）数据集合中各数据
2、元素之间固有的逻辑关系，即数据的逻辑结构；（2）各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。2.1.2数据结构的基本概念和术语数据(Data):所有能被计算机处理的符号的集合。数据元素(DataElement):是数据的基本单位，也称之为结点(node)或记录(record),在计算机程序中通常作为一个整体进行考虑和处理。如数据集合N={1,2,3,4,5}中1-5均为数据元素。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。个人书库数据元素数据对象(DataObject)：性质相同的数据元素的集合。是数据的一个子
3、集。数据对象可以是有限的，也可以是无限的。例:整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}数据结构(DataStructure)：是指带有结构的数据元素的集合。结构:数据元素之间存在的关系。集合论方法定义结构S为一个二元组：S=(D，R)其中：D是数据元素的非空有限集，R是定义在D上关系的非空有限集。如n维向量的数据元素集合为D={x1,x2,…,xn}，D上的关系R={,,…,},即为线性表。2.1.2数据结构的基本概念和术语2.1.2数据结构的基本概念和术
4、语数据的逻辑结构：数据元素及其关系的数学特性(逻辑关系)。通常用前后件关系（或直接前驱与直接后继关系）描述,如一年四季，家庭成员等。数据类型(Datatype)：在一种程序设计语言中，变量所具有的数据种类。在C中数据类型：基本类型和构造类型;基本类型：整型、浮点型、字符型;构造类型：数组、结构、联合、指针、枚举型、自定义。数据的物理结构(存储结构)：是逻辑结构在计算机中的存储表示(映象)。也就是具体实现。分为顺序存储结构、链式存储结构。逻辑结构与物理结构必然一致吗？算法：是解决某一特定类型问题的有限运算序列，其实现必须借助程序设计语言提供的数据类型及其运算。算法是解题方案
5、的准确而完整的描述。数据结构与算法算法的基本特性：(1)有穷性：一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。(2)确定性：每一步必须是明确的，不存在二义性。(3)可行性：每一个步骤必须能够实现，可以通过基本运算执行有限次来实现，结果能够达到预期目的。算法的两个基本要素：一是对数据对象的运算和操作，二是算法的控制结构。由顺序、选择、循环组合而成。程序=算法+数据结构程序设计的核心是算法，处理的对象是数据。评价算法优劣的标准：时间复杂度和空间复杂度算法的时间复杂度指执行算法所需要的计算工作量。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,算
6、法的时间量度记作:T(n)=O(f(n))称作算法的渐近时间复杂度,简称时间复杂度。时间复杂度函数：常量型：O(1)多项式型：O(n),O(n2),……O(nk)对数型：O(log2n),O(nlog2n)指数型：O(2n)，O(en)2.1.2数据结构的基本概念和术语空间复杂度指执行算法需要的内存空间。包括算法程序所占空间、初始数据所占存储空间、算法执行过程中需要的额外空间。S(n)=O(f(n))时间与空间是一对矛盾，要节约空间往往要消耗较多的时间，反之亦然。目前，内存空间足够，应重点考虑时间。intx=10,y=20;intt;t=x;x=y;y=t;printf(
7、"%d%d",x,y);intx=10,y=20;x+=y;y=x-y;x-=y;printf("%d%d",x,y);2.1.2数据结构的基本概念和术语(1)枚举法用于解决"是否存在"或"有多少种可能"等类型的问题。基本思想：根据所提出的问题，列举出所有可能的情况，从中找出能满足给定条件的解。特点:算法简单,运算量大.常用算法：(2)归纳法用于解决有某种规律的问题。归纳法是通过列举少量的特殊情况，经过分析，最后找出一般的的关系。归纳法在算法设计中应用很广，最常见的便是递推和递归。（3）回溯法基本思想就是试探：当算法从
