计算机软件技术基础徐士良第2章.ppt
文本预览下载声明
第2章 基本数据结构及其运算 第2章 基本数据结构及其运算 2.1 数据结构的基本概念 2.2 线性表及其顺序存储结构 2.3 线性链表及其运算 2.4 数组 2.5 树与二叉树 2.6 图 2.1 数据结构的基本概念 2.1.1 两个例子 2.1.2 什么是数据结构 2.1.3 数据结构的图形表示 2.1.4 线性数据结构与非线性数据结构 数据结构三个方面的问题: (1)数据的逻辑结构 (2)数据的存储结构 (3)对各种数据结构进行的运算 目的:提高数据处理的效率 提高数据处理的速度 尽量节省计算机存储空间 2.1.1 两个例子 例 无序表的顺序查找 35 16 78 85 43 29 33 21 54 46 有序表的对分查找 16 21 29 33 35 43 46 54 78 85 数据元素在表中的排列顺序对查找效率是有很大影响。 例 学生情况登记表以学号为顺序排列 结论: 在对数据进行处理时, 可以根据所做的运算不同, 将数据组织成不同的形式, 以便于做该种运算, 从而提高数据处理的效率。 2.1.2 什么是数据结构 数据结构是指相互有关联的数据元素集合。 现实世界中客观存在的一切个体都可以是数据元素。 描述一年四季的季节名 春,夏,秋,冬 可以作为季节的数据元素; 表示数值的各个数 18,11,35,23,16,… 可以作为数值的数据元素; 表示家庭成员的各成员名 父亲,儿子,女儿 可以作为家庭成员的数据元素。 前后件关系是数据元素之间的一个基本关系,但前后件关系所表示的实际意义是随具体对象的不同而不同。 一般来说,数据元素之间的任何关系都可以用前后件关系来描述。 1.数据的逻辑结构 是指反映数据元素之间逻辑关系的数据结构。 (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的逻辑结构有两个要素: 数据元素的集合D; 反映D中各数据元素之间的前后件关系R。 数据结构可以表示成 B=(D,R) 其中B表示数据结构。 为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。 设a与b是D中的两个数据,则二元组 (a,b) 表示a是b的前件,b是a的后件。 例如 B=(D,R) D={春,夏,秋,冬} R={(春,夏),(夏,秋),(秋,冬)} 家庭成员数据结构 B=(D,R) D={父亲,儿子,女儿} R={(父亲,儿子),(父亲,女儿)} n维向量 X=(x1,x2,…,xn) 也是一种数据结构。即 X=(D,R) D={x1,x2,…,xn} R={(x1,x2),(x2,x3),…,(xn-1,xn)} m×n的矩阵是一个数据结构。即 A=(D,R) D={A1,A2,…,Am} R={(A1,A2),(A2,A3),…,(Ai,Ai+1),…,(Am-1,Am)} 其中Ai=(ai1,ai2,…,ain),i=1,2,…,m Ai=(Di,Ri) Di={ai1,ai2,…,ain} Ri={(ai1,ai2),(ai2,ai3),…,(aij,ai,j+1),…,(ai,n-1,ain)} 2.数据的存储结构(数据的物理结构) 数据的逻辑结构在计算机存储空间中的存放形式。 常用的存储结构有: 顺序、链接、索引等存储结构。 采用不同的存储结构,其数据处理的效率是不同的。 2.1.3 数据结构的图形表示 数据集合D中的每一个数据元素用中间标有元素值的方框表示(数据结点,结点) 用一条有向线段从前件结点指向后件结点。 一年四季数据结构的图形表示 家庭成员间辈份关系数据结的图形表示 用图形表示数据结构B=(D,R) D={di |1≤i≤7}={d1,d2,d3,d4,d5,d6,d7} R={(d1,d3),(d1,d7),(d2,d4),(d3 ,d6) ,(d4 ,d5 ) } 2.1.4 线性数据结构与非线性数据结构 线性结构: (1)有且只有一个根结点; (2)每一个结点最多有一个前件, 也最多有一个后件。 线性结构又称线性表。 不是线性结构的数据结构特例 如果一个数据结构不是线性结构, 则称之为非线性结构 2.2 线性表及其顺序存储结构 2.2.1 线性表及其运算 2.2
显示全部