据结构 李云清杨庆红揭安全
李云清 杨庆红 揭安全
第1章概论 数据结构讨论的是数据的逻辑结构、存储方式 以及相关操作的实现等问题,为学习后续专业课程 打下基础。本章讲述数据结构的基本概念及相关术 语,介绍数据结构、数据类型和抽象数据类型之间 的联系,介绍了算法的特点及算法的时间与空间复 杂性
第1章 概论 数据结构讨论的是数据的逻辑结构、存储方式 以及相关操作的实现等问题，为学习后续专业课程 打下基础。本章讲述数据结构的基本概念及相关术 语，介绍数据结构、数据类型和抽象数据类型之间 的联系，介绍了算法的特点及算法的时间与空间复 杂性
1.1数据结构 1.1.1数据结构 随着计算机软、硬件的发展,计算机的应用范 围在不断扩大,计算机所处理的数据的数量也在不 断扩大,计算机所处理的数据已不再是单纯的数值 数据,而更多的是非数值数据。 需要处理的数据并不是杂乱无章的,它们一定 有内在的联系,只有弄清楚它们之间的本质的联系, 才能使用计算机对大量的数据进行有效的处理
1.1数据结构 1.1.1数据结构 随着计算机软、硬件的发展，计算机的应用范 围在不断扩大，计算机所处理的数据的数量也在不 断扩大，计算机所处理的数据已不再是单纯的数值 数据，而更多的是非数值数据。 需要处理的数据并不是杂乱无章的，它们一定 有内在的联系，只有弄清楚它们之间的本质的联系， 才能使用计算机对大量的数据进行有效的处理
某电信公司的市话用户信息表格如下图所示 用户住址 序号 用户名电话号码 街道名 刁J牌号 00001 万方林3800235北京西路 1659 这里序号、用户名、电话号码等项称为基本项,它 是有独立意义的最小标识单位,而用户住址称为组合项, 组合项是由一个或多个基本项或组合项组成,是有独立 意义的标识单位,每一行称为一个结点,每一个组合项 称为一个字段。 使用计算机处理用户信息表中的数据时,必须弄清楚 下面3个问题
某电信公司的市话用户信息表格如下图所示： 序号 用户名 电话号码 用户住址 街道名 门牌号 00001 万方林 3800235 北京西路 1659 00002 吴金平 3800667 北京西路 2099 00003 王 冬 5700123 瑶湖大道 1987 00004 王 三 5700567 瑶湖大道 2008 00005 江 凡 8800129 学府大道 5035 这里序号、用户名、电话号码等项称为基本项，它 是有独立意义的最小标识单位，而用户住址称为组合项， 组合项是由一个或多个基本项或组合项组成，是有独立 意义的标识单位，每一行称为一个结点，每一个组合项 称为一个字段。 使用计算机处理用户信息表中的数据时，必须弄清楚 下面3个问题：
1数据的逻辑结构 这些数据之间有什么样的内在联系? 除最前和最后两个结点之外,表中所有其它的结点 都有且仅有一个和它相邻位于它之前的一个结点,也有 且仅有一个和它相邻位于它之后的一个结点,这些就是 用户信息表的逻辑结构。 2数据的存储结构 将用户信息表中的所有结点存入计算机时,就必须 考虑存储结构,使用C语言进行设计时,常见的方式是 用一个结构数组来存储整个用户信息表,每一个数组元 素是一个结构,它对应于用户信息表中的一个结点。数 据在计算机的存储方式称为存储结构
1 数据的逻辑结构 这些数据之间有什么样的内在联系？ 除最前和最后两个结点之外，表中所有其它的结点 都有且仅有一个和它相邻位于它之前的一个结点，也有 且仅有一个和它相邻位于它之后的一个结点，这些就是 用户信息表的逻辑结构。 2 数据的存储结构 将用户信息表中的所有结点存入计算机时，就必须 考虑存储结构，使用C语言进行设计时，常见的方式是 用一个结构数组来存储整个用户信息表，每一个数组元 素是一个结构，它对应于用户信息表中的一个结点。数 据在计算机的存储方式称为存储结构
3数据的运算集合 数据处理必涉及到相关的运算,在上述用户信息表 中,可以有删除一个用户、增加一个用户和查找某个用 户等操作。应该明确指明这些操作的含义。比如删除操 作,是删除序号为5的用户还是删除用户名为王三的用 户是应该明确定义的,如果需要可以定义两个不同的删 除操作,为—批数据定义的所有运算(或称操作)构成 一个运算(操作)集合。 对待处理的数据,只有分析清楚上面3个方面的问 题,才能进行有效的处理 数据结构就是指按一定的逻辑结构组成的一批数据 使用某种存储结构将这批数据存储于计算机中,并在 这些数据上定义了一个运算集合
3 数据的运算集合 数据处理必涉及到相关的运算，在上述用户信息表 中，可以有删除一个用户、增加一个用户和查找某个用 户等操作。应该明确指明这些操作的含义。比如删除操 作，是删除序号为5的用户还是删除用户名为王三的用 户是应该明确定义的，如果需要可以定义两个不同的删 除操作，为一批数据定义的所有运算（或称操作）构成 一个运算（操作）集合。 对待处理的数据，只有分析清楚上面3个方面的问 题，才能进行有效的处理！ 数据结构就是指按一定的逻辑结构组成的一批数据， 使用某种存储结构将这批数据存储于计算机中，并在 这些数据上定义了一个运算集合
1.1.2数据的逻辑结构 例如,有5个人,分别记为a,b,c,d,e,其中a是b的父亲 b是c的父亲,c是的父亲d是e的父亲,如果只讨论他们 之间所存在的父子关系,则可以用下面的二元组形式化 地予以表达。 B=(KR) 其中:K={abcd,e} R={ r={,,,}
1.1.2数据的逻辑结构 数据的逻辑结构是数据和数据之间所存在的逻辑关 系，它可以用一个二元组 B=（K，R） 来表示，其中K是数据、即结点的有限集合；R是集 合K上关系的有限集合，这里的关系是从集合K到集 合K的关系，这里一般只涉及到一个关系的逻辑结构。 例如，有5个人，分别记为a,b,c,d ,e,其中a是b的父亲， b是c的父亲，c是d的父亲,d是e的父亲，如果只讨论他们 之间所存在的父子关系，则可以用下面的二元组形式化 地予以表达。 B=（K，R） 其中：K={a,b,c,d,e} R={r} r={,, ,}
逻辑结构的图形表示方式,对K中的每个结点k用 个方框表示,而结点之间的关系用带箭头的线段表示 这5人之间的逻辑结构用图形的方式表达如下图所示。 b 若k∈K,k=R,火kk>∈r,则称k是的相对 于关系的前驱结点,k是k的相对于关系的后继结点 因为一般只讨论具有一种关系的逻辑结构,即R={ 所以简称k是k前驱,k是k的后继。如果某个结点没有 前驱结点,称之为开始结点;如果某个结点没有后继 结点,称之为终端结点;既不是开始结点也不是终端 结点的结点称为内部结点
逻辑结构的图形表示方式，对K中的每个结点ki用一 个方框表示，而结点之间的关系用带箭头的线段表示， 这5人之间的逻辑结构用图形的方式表达如下图 所示。 若ki∈K，kj∈R， ∈r，则称ki是kj的相对 于关系r的前驱结点，kj是ki的相对于关系r的后继结点， 因为一般只讨论具有一种关系的逻辑结构，即R={r}， 所以简称ki是kj前驱，kj是ki的后继。如果某个结点没有 前驱结点，称之为开始结点；如果某个结点没有后继 结点，称之为终端结点；既不是开始结点也不是终端 结点的结点称为内部结点
1.1.3数据的存储结构 数据的逻辑结构是独立于计算机的,它与数据在 计算机中的存储无关,要对数据进行处理,就必须将 数据存储在计算机中。如果将数据在计算机中无规律 地存储,那么在处理时是非常糟的,是没有用的。试 想一下,如果一本英汉字典中的单词是随意编排的, 这本字典谁会用 对于一个数据结构B=(K,R),必须建立从结点 集合到计算机某个存储区域M的一个映象,这个映象 要直接或间接地表达结点之间的关系R。数据在计算 机中的存储方式称为数据的存储结构 数据的存储结构主要有4种
1.1.3数据的存储结构 数据的逻辑结构是独立于计算机的，它与数据在 计算机中的存储无关，要对数据进行处理，就必须将 数据存储在计算机中。如果将数据在计算机中无规律 地存储，那么在处理时是非常糟的，是没有用的。试 想一下，如果一本英汉字典中的单词是随意编排的， 这本字典谁会用！ 对于一个数据结构B=（K，R），必须建立从结点 集合到计算机某个存储区域M的一个映象，这个映象 要直接或间接地表达结点之间的关系R。数据在计算 机中的存储方式称为数据的存储结构。 数据的存储结构主要有4种
数据的存储结构主要有4种 存储地址M 1顺序存储 1001 002 逻辑上相邻的结点存情在在续行情区M的m 储单元中,使得逻辑相邻的结点一定是物理0k 对于一个数据结构B=(K,R) 1007k 1008k 其中K={k1k2k3k4k3 k6, k, k8, k9} 009k R={ r={,) 它的顺序存储方式如图所示
数据的存储结构主要有4种。 1 顺序存储 顺序存储通常用于存储具有线性结构的数据。将 逻辑上相邻的结点存储在连续存储区域M的相邻的存 储单元中，使得逻辑相邻的结点一定是物理位置相邻。 对于一个数据结构B=（K，R） 其中K={k1 ,k2 ,k3 ,k4 ,k5 ,k6 ,k7 ,k8 ,k9 } R={r} r={,,,,,,,} 它的顺序存储方式如图所示