软件技术基础VIP免费

软件技术基础制作主讲段景山段景山数据结构的基本概念数据结构的基本概念段景山第一篇数据结构第一章数据结构的基本概念数据结构数据结构数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构算法算法段景山数据结构11数据结构的概念数据结构的概念1.1数据及数据元素的概念数据数据是客观事物在计算机内的抽象描述是客观事物在计算机内的抽象描述数据数据指一些事实，或一些数，或一些符号集合指一些事实，或一些数，或一些符号集合组成数据的“事实”、“数值”或“符号”组成数据的“事实”、“数值”或“符号”称称为数据元素为数据元素数据元素可由若干个数据元素可由若干个数据项数据项组成组成段景山数据及数据元素例例11、学生花名册、学生花名册数据元素数据元素数据数据学生名字的集合学生名字的集合每个学生的名字每个学生的名字例例22、学生成绩表、学生成绩表数据数据数据元素数据元素数据项数据项学生成绩的集合学生成绩的集合每个学生的成绩每个学生的成绩名字名字成绩成绩段景山数据结构的概念1.2、数据结构的概念数据结构讨论计算机系统中数据的组织形式及其相互关系是相互之间存在一种和多种特定关系的数据元素的集合例：大楼中的电梯例：大楼中的电梯电梯在楼层中只能逐层移动电梯在楼层中只能逐层移动例：公司的组织关系例：公司的组织关系楼层间的关系是线性的楼层间的关系是线性的员工间形成树型关系员工间形成树型关系涉及涉及元素的集合元素的集合元素间的关系元素间的关系在关系里的操作在关系里的操作电梯的运动电梯的运动人员的管理人员的管理段景山例：用数据结构描述整数I*1、组成整数数据的全部元素的集合II＝{0，±1，±2，±3……}2、I中元素的关系集合RE3、I*的运算集合P，比如算术四则运算4、P中诸运算的运算规则RU，如乘、除法优先于加、减法等I*＝{I，RE，P，RU}数据结构的概念RERE＝＝{……-1<0,0<1,1<2,……}{……-1<0,0<1,1<2,……}段景山数据结构的概念元素集合元素集合元素间的关系元素间的关系运算运算计计算算机机系系统统元素在计算机系统里的表示元素在计算机系统里的表示字符？字串？整数？字符？字串？整数？元素间的逻辑关系－－逻辑结构元素在计算机系统中的存储方式，物理空间关系－－存储结构操作指令的集合－－算法段景山数据的逻辑结构与数据的存储结构数据的逻辑结构与数据的存储结构例：班级里的同学可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。上课时，大家的座次形成存储结构座次（存储结构）可能与逻辑关系有关，也可能无关。数据结构的概念段景山逻辑结构逻辑结构小结：小结：数据结构包括数据的数据结构包括数据的逻辑结构逻辑结构，数据在计算机系，数据在计算机系统中的统中的存储结构存储结构和数据和数据操作操作的集合的集合把数据以一定的把数据以一定的逻辑结构逻辑结构组织起来，以适当的方组织起来，以适当的方式式存储存储在计算机系统的存储器里，其最终目的是在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理为了有效处理数据，提高数据处理运算运算速度（教速度（教材材P3)P3)存储结构存储结构算法算法数据结构的概念要素要素目标目标三个要素都与我们所要实现的目标相关三个要素都与我们所要实现的目标相关有效处理数据有效处理数据提高数据处理提高数据处理运算运算速度速度段景山22、数据的逻辑结构、数据的逻辑结构数据元素之间关系的描述数据元素之间关系的描述2.1、描述法二元组关系：一般抽象为前驱与后继关系，即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁B＝（K，R）K：元素集合R：元素间关系的集合数据的逻辑结构段景山2.2、图示法图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表不管多么复杂的结点，都看作是一个结点有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继KiKhKjKi的前驱Ki的后继数据的逻辑结构研究为什么一个结点是研究为什么一个结点是另一个结点的前驱或后继另一个结点的前驱或后...