2 软件技术基础-数据结构基本概念

CompanyLogo河南理工大学§1.1数据结构的基本概念1.1.1什么是数据结构早期计算机仅仅用于简单的计算决定计算机的效率—运算速度输入输出的数据量小数据元素之间的关系简单不需数据结构计算机应用扩展后大量的非数值运算决定计算机的效率-CPU速度及数据之间的关系结构输入输出的数据量大数据元素之间的关系复杂需要数据结构描述数据之间的关系ModernEducationalTechnologyCenterofHPU计算机解一个有关数值计算的具体问题的步骤：建立数学模型的实质是：分析实际问题，寻找包含在问题中的操作对象，以及这些对象之间的关系，并用数学的语言对这些操作对象和其间的关系加以描述，这就是该问题的数学模型。建立数学模型设计解模算法编程调试输出结果数值计算问题中的数学模型通常可用数学方程来描述，但是更多的非数值计算的问题却无法用数学方程来描述其数学模型。ModernEducationalTechnologyCenterofHPU例1学生成绩查询学号姓名班级数学物理电路C语言1王小蔷971501879086842张洁971501808186903许晓路971501918890874李晔97150193889285┇┇┇┇┇┇┇姓名学号王小蔷1张洁2许晓路3李晔4┇┇班级学号9715011,2,3,…97150240,41,42,…┇┇这三张查询表就是学生成绩查询的数学模型，各元素间存在线性关系，因此这种数学模型称为线性数据结构。ModernEducationalTechnologyCenterofHPU例2人机对奕问题（五子棋）对奕的过程是在一定的对奕规则和取胜策略下进行的，因此为使计算机能够灵活对奕必须事先将对奕的规则、以及对奕过程中可能出现的情况和相应的策略都存入计算机。在人机对奕过程中，计算机操作的对象是对奕过程中可能出现的棋局状态（称为格局）。cbaModernEducationalTechnologyCenterofHPU联想一下，若将一局棋从开始到结束可能出现的格局都画出来，可以得到下面一张图：因此，对奕问题中的数学模型就是以各种格局为元素的一种“树”结构。可以看出这种树结构中元素的关系不是简单的线性关系，它是另一种典型的数据结构，称为“树结构”。ModernEducationalTechnologyCenterofHPU由此，至少要四种颜色的交通灯才能满足保证交通秩序的要求。例3利用交通灯进行多叉路口的交通管理问题本题中可以用一个圆圈表示一条通路，两个通路之间的矛盾关系用对应两个圆圈的连线表示（圆圈称为顶点、连线称为边），则设置交通灯的问题可以等价为对圆圈的染色问题。要求：每个顶点染一种颜色。相连的顶点不能染相同的颜色。总色类最少。用计算机来解决这类问题时，要处理的问题是诸如顶点和边这样的元素，数据结构中称这种为图结构，于是这类问题的数学模型就是“图”这种数据结构。ModernEducationalTechnologyCenterofHPU由此我们可以这样来定义数据结构：它是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。ModernEducationalTechnologyCenterofHPU数据(data)：对客观事物的符号表示，在计算机中是指所有能输入到计算机中被计算机程序处理的符号的总称。整数，实数，字符串；图象声音编码→数据数据元素(dataelement)：数据的基本单位（也称数据结点）通常作为一个整体考虑，代表一定的特征。一个数据元素可由若干个数据项组成。数据项(dataItem)：一个数据元素可以由若干个数据项组成，它是数据的不可分割的最小单位。一、几个概念基本概念和述语ModernEducationalTechnologyCenterofHPU例、学生花名册数据元素数据学生名字的集合每个学生的名字例、学生成绩表数据数据元素数据项学生成绩的集合每个学生的成绩名字成绩ModernEducationalTechnologyCenterofHPU数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据对象(dataobject)：性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N={0,1,2,3…...}字母数据对象是集合C={a,b,c,d…...}任何问题中，数据元素都不是孤立存在的，而是在它们之间存在某种关系，这种数据元素相互之间的关系称为结构(structure)ModernEducationalTechnologyCenterofHPU例：家庭成员数据结构可以表示成：F=(C,R)C={父亲，儿子，女儿}R={(父亲，儿子)，(父亲，女儿)，(儿子，女儿)}用形式化描述：数据结构是一二元组：Data_Structure=(K,R)其中：K是数据元素的有限集合，R是K上关系的有限集。ModernEducationalTechnologyCenterofHPU例：用数据结构描述整数I*1、组成整数数据的全部元素的集合II＝{0，±1，±2，±3……}2、I中元素的关系集合RE3、I*的运算集合P，比如算术四则运算4、P中诸运算的运算规则RU，如乘、除法优先于加、减法等I*＝{I，RE，P，RU}RE＝{……-10,01,12,……}ModernEducationalTechnologyCenterofHPU元素集合元素间的关系运算计算机系统元素在计算机系统里的表示字符？字串？整数？元素间的逻辑关系－－逻辑结构元素在计算机系统中的存储方式，物理空间关系－－存储结构操作指令的集合－－算法ModernEducationalTechnologyCenterofHPU数据结构包括数据的逻辑结构，数据在计算机系统中的存储结构和数据操作的集合把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度小结ModernEducationalTechnologyCenterofHPU直接前驱、直接后继：在数据结构中的任意一个元素与之相邻且在它之前的元素称为该元素的直接前驱，同理与之相邻且在它之后的元素称为该元素的直接后继。名称解释ModernEducationalTechnologyCenterofHPU二、数据的逻辑结构逻辑结构：数据元素之间在形式上所呈现的关系。线性结构：定义。典型的线性结构有线性表，如：学生成绩表。线性结构ModernEducationalTechnologyCenterofHPU非线性结构：定义。典型的非线性结构为图结构，而树是一种特殊的非线性结构。树结构图结构ModernEducationalTechnologyCenterofHPU三、数据的存储结构（物理结构）物理结构：数据结构在计算机中的表示（或映象）。它包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中不同的表示方法得到不同的存储结构：1、顺序存储结构：定义。多用于线性结构的存储。各元素之间的逻辑关系是通过存储单元(物理位置)的相邻的关系来反映的。地址100130160190存储单元王小蔷张洁许晓路李晔┇ModernEducationalTechnologyCenterofHPU、链式存储结构：定义。元素间的逻辑关系是由指针来反映的。地址P4300P1P2存储单元(许晓路,P1)┇(王小蔷,P2)┇(李晔,P3)┇(张洁,P4)┇ModernEducationalTechnologyCenterofHPU、索引存储：在存储(即可是顺序存储，也可是链接存储)元素的同时，还建立附加的索引表，索引表中每一项称为索引项，索引项的一般形式是：（关键字，地址）关键字是能唯一标识一个元素的数据项。ModernEducationalTechnologyCenterofHPU元素可以离散存放通过查索引表找到需要的元素索引表1234索引号0300030103020303030403050306030703080309K1K2K3K4ModernEducationalTechnologyCenterofHPU、散列存储：没有附加的索引表，从数据元素中直接计算出存储地址，根据元素的关键字直接计算出该元素的存储地址，即在数据元素的字段中有一个或几个字段的值，通过某一散列函数唯一地确定该元素的存储地址。例：以用户姓名为关键值算式字母的序号相加DJSZXM04＋10＋19＝3326＋24＋13＝63所以，DJS放在33号地址单元ZXM放在63号地址单元ModernEducationalTechnologyCenterofHPU四、数据操作数据结构中常见的操作：遍历：查看数据结构中的所有数据元素。插入：添加新的元素到一个数据结构中。删除：将指定元素从数据结构中去掉。更新：修改数据结构中的某个数据元素。查找：在数据结构中寻找满足条件的数据元素。排序：将数据结构中的数据元素按指定的顺序排列。加工型操作：插入、删除、更新、排序访问型操作：遍历、查找ModernEducationalTechnologyCenterofHPU注意数据的逻辑结构，数据的存储结构和数据的操作是一个整体，共同构成数据结构。数据操作（指某种算法）的设计取决于选定的数据逻辑结构;数据操作的实现,取决于选定的存储结构。同一逻辑结构不同的存储结构是不同的数据结构。同一逻辑结构、存储结构中,不同的操作也是不同数据结构。ModernEducationalTechnologyCenterofHPU语言的数据类型见“C语言复习”。ModernEducationalTechnologyCenterofHPU定义：算法是对特定问题求解步骤的一种描述。它是指令的有限序列其中每一条指令表示一个或多个操作。1.1.4算法ModernEducationalTechnologyCenterofHPU算法的五个特性：有穷性：一个算法必须总是（对于合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性：算法中的每一条指令，必须有确切含义，读者不会产生二义性，且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性：一个算法是可行的，即算法中描述的操作