数据结构基本概念

《数据结构基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构的基本概念廖丹liaodan@uestc.edu.cn宽带光纤传输与通信系统技术教育部重点实验室KeyLaboratoryofBroadbandOpticalFiberTransmissionandCommunicationNetworks制作：段景山廖丹主讲：廖丹Outline数据结构定义数据的逻辑结构数据的存储结构算法Outline数据结构定义数据的逻辑结构数据的存储结构算法什么是数据结构NiklausWirth:《算法十数据结构=程序》(Algorithms＋DataStructures＝Programs，Pren

2、tice-Hall，1976)什么是程序？什么是算法？什么是数据结构？数据结构数据结构的概念数据及数据元素的概念数据是客观事物在计算机内的抽象描述数据指一些事实，或一些数，或一些符号集合组成数据的“事实”、“数值”或“符号”称为数据元素数据元素可由若干个数据项组成数据及数据元素例1、学生花名册数据元素数据学生名字的集合每个学生的名字例2、学生成绩表数据数据元素数据项学生成绩的集合每个学生的成绩名字成绩数据结构的概念数据结构的概念数据结构讨论计算机系统中数据的组织形式及其相互关系是相互之间存在一种和多种特定关系的数据元素的集合例：

3、大楼中的电梯电梯在楼层中只能逐层移动例：公司的组织关系楼层间的关系是线性的员工间形成树型关系涉及元素的集合元素间的关系在关系里的操作电梯的运动人员的管理例：用数据结构描述整数I*1、组成整数数据的全部元素的集合II＝{0，±1，±2，±3……}2、I中元素的关系集合RE3、I*的运算集合P，比如算术四则运算4、P中诸运算的运算规则RU，如乘、除法优先于加、减法等I*＝{I，RE，P，RU}数据结构的概念RE＝{……-1<0,0<1,1<2,……}数据结构的概念例：用数据结构的思想分析以下实物：一个十字路口的红绿灯管制包含两部电梯

4、的管理系统一条公交路线成都市公交系统元素关系运算数据结构的概念元素集合元素间的关系运算计算机系统元素在计算机系统里的表示字符？字串？整数？元素间的逻辑关系－－逻辑结构元素在计算机系统中的存储方式，物理空间关系－－存储结构操作指令的集合－－算法数据的逻辑结构与数据的存储结构例：班级里的同学可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。上课时，大家的座次形成存储结构座次（存储结构）可能与逻辑关系有关，也可能无关。数据结构的概念此外，数据的运算也是数据结构不可分割的一个方面Outline数据结构定义数据的逻辑结

5、构数据的存储结构算法数据的逻辑结构数据元素之间关系的描述描述法二元组关系：一般抽象为前驱与后继关系，即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁B＝（K，R）K：元素集合R：元素间关系的集合数据的逻辑结构图示法图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表不管多么复杂的结点，都看作是一个结点有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继KiKhKjKi的前驱Ki的后继数据的逻辑结构研究为什么一个结点是另一个结点的前驱或后继数据的逻辑结构线性结构线性表队列堆栈非线性结构树

6、图集合结构Outline数据结构定义数据的逻辑结构数据的存储结构算法数据的存储结构（物理结构）是数据元素在计算机系统存储器中的存放方式也可以说，是数据逻辑结构在存储器中的存放方式数据的存储结构存储器的特点：由地址连续的单元构成K1K2K3K4数据的存储结构逻辑结构K1K2K3K4K5K6数据的存储结构逻辑结构数据的存储结构思考：为什么数据逻辑结构与物理结构没有完全统一？存储器的特点：由地址连续的单元构成。－－线性关系单元间的线性关系有时不能直接反映复杂的逻辑关系几种物理存储方式顺序存储方法连续顺序地存放数据元素若数据的逻辑结构也

7、是顺序（线性）的，则逻辑结构和物理结构完全统一了连续存放的数据元素可以在内存中容易找到数据的存储结构链接存储方法元素在内存中不一定连续存放在元素中附加指针项，通过指针可以找到关系元素元素＋指针结点元素指针数据的存储结构K1K2K3K4K5K6数据的存储结构逻辑结构索引存储方法为放在内存中的元素建立索引表元素可以离散存放通过查索引表找到需要的元素数据的存储结构散列存储方法结点中设一关键值，利用关键值和相应算式算出结点位置（地址）例：以用户姓名为关键值DJS算式：字母的序号相加04＋10＋19＝33ZXM26＋24＋13＝63数据的

8、存储结构所以，DJS放在33号地址单元ZXM放在63号地址单元小结：数据的逻辑结构与物理结构1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位2、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序