数据结构讨论的是数据的逻辑结构

《数据结构讨论的是数据的逻辑结构》由会员分享，可在线阅读，更多相关《数据结构讨论的是数据的逻辑结构（21页珍藏版）》请在金锄头文库上搜索。

1、第第1 1章章 概论概论数据结构讨论的是数据的逻辑结构、存储方式数据结构讨论的是数据的逻辑结构、存储方式 以及相关操作的实现等问题，为学习后续专业课程以及相关操作的实现等问题，为学习后续专业课程 打下基础。本章讲述数据结构的基本概念及相关术打下基础。本章讲述数据结构的基本概念及相关术 语，介绍数据结构、数据类型和抽象数据类型之间语，介绍数据结构、数据类型和抽象数据类型之间 的联系，介绍了算法的特点及算法的时间与空间复的联系，介绍了算法的特点及算法的时间与空间复 杂性。杂性。 1.11.1数据结构数据结构 1.1.11.1.1数据结构数据结构随着计算机软、硬件的发展，计算机的应用范随着计算机软、

2、硬件的发展，计算机的应用范 围在不断扩大，计算机所处理的数据的数量也在不围在不断扩大，计算机所处理的数据的数量也在不 断扩大，计算机所处理的数据已不再是单纯的数值断扩大，计算机所处理的数据已不再是单纯的数值 数据，而更多的是非数值数据。数据，而更多的是非数值数据。需要处理的数据并不是杂乱无章的，它们一定需要处理的数据并不是杂乱无章的，它们一定 有内在的联系，只有弄清楚它们之间的本质的联系有内在的联系，只有弄清楚它们之间的本质的联系 ，才能使用计算机对大量的数据进行有效的处理。，才能使用计算机对大量的数据进行有效的处理。 某电信公司的市话用户信息表格如下图所示：某电信公司的市话用户信息表格如下图

3、所示： 序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王 冬5700123瑶湖大道198700004王 三5700567瑶湖大道200800005江 凡8800129学府大道5035这里序号、用户名、电话号码等项称为基本项，它这里序号、用户名、电话号码等项称为基本项，它 是有独立意义的最小标识单位，而用户住址称为组合项是有独立意义的最小标识单位，而用户住址称为组合项 ，组合项是由一个或多个基本项或组合项组成，是有独，组合项是由一个或多个基本项或组合项组成，是有独 立意义的标识单位，每一行称为一个结点，

4、每一个组合立意义的标识单位，每一行称为一个结点，每一个组合 项称为一个字段。项称为一个字段。使用计算机处理用户信息表中的数据时，必须弄清楚使用计算机处理用户信息表中的数据时，必须弄清楚 下面下面3 3个问题：个问题： 1 1 数据的逻辑结构数据的逻辑结构这些数据之间有什么样的内在联系？这些数据之间有什么样的内在联系？ 除最前和最后两个结点之外，表中所有其它的结点除最前和最后两个结点之外，表中所有其它的结点 都有且仅有一个和它相邻位于它之前的一个结点，也有都有且仅有一个和它相邻位于它之前的一个结点，也有 且仅有一个和它相邻位于它之后的一个结点，这些就是且仅有一个和它相邻位于它之后的一个结点，这些

5、就是 用户信息表的逻辑结构。用户信息表的逻辑结构。2 2 数据的存储结构数据的存储结构 将用户信息表中的所有结点存入计算机时，就必须将用户信息表中的所有结点存入计算机时，就必须 考虑存储结构，使用考虑存储结构，使用C C语言进行设计时，常见的方式是语言进行设计时，常见的方式是 用一个结构数组来存储整个用户信息表，每一个数组元用一个结构数组来存储整个用户信息表，每一个数组元 素是一个结构，它对应于用户信息表中的一个结点。数素是一个结构，它对应于用户信息表中的一个结点。数 据在计算机的存储方式称为存储结构。据在计算机的存储方式称为存储结构。3 3 数据的运算集合数据的运算集合数据处理必涉及到相关的

6、运算，在上述用户信息表数据处理必涉及到相关的运算，在上述用户信息表 中，可以有删除一个用户、增加一个用户和查找某个用中，可以有删除一个用户、增加一个用户和查找某个用 户等操作。应该明确指明这些操作的含义。比如删除操户等操作。应该明确指明这些操作的含义。比如删除操 作，是删除序号为作，是删除序号为5 5的用户还是删除用户名为王三的用的用户还是删除用户名为王三的用 户是应该明确定义的，如果需要可以定义两个不同的删户是应该明确定义的，如果需要可以定义两个不同的删 除操作，为一批数据定义的所有运算（或称操作）构成除操作，为一批数据定义的所有运算（或称操作）构成 一个运算（操作）集合。一个运算（操作）集

7、合。 对待处理的数据，只有分析清楚上面对待处理的数据，只有分析清楚上面3 3个方面的问个方面的问 题，才能进行有效的处理！题，才能进行有效的处理！ 数据结构数据结构就是指按一定的逻辑结构组成的一批数据就是指按一定的逻辑结构组成的一批数据 ，使用某种存储结构将这批数据存储于计算机中，并，使用某种存储结构将这批数据存储于计算机中，并 在这些数据上定义了一个运算集合。在这些数据上定义了一个运算集合。1.1.21.1.2数据的逻辑结构数据的逻辑结构 数据的逻辑结构是数据和数据之间所存在的逻辑关数据的逻辑结构是数据和数据之间所存在的逻辑关 系，它可以用一个二元组系，它可以用一个二元组B=B=（K K，R

8、 R）来表示，其中来表示，其中K K是数据、即结点的有限集合；是数据、即结点的有限集合；R R是集是集 合合K K上关系的有限集合，这里的关系是从集合上关系的有限集合，这里的关系是从集合K K到集到集 合合K K的关系，这里一般只涉及到一个关系的逻辑结构的关系，这里一般只涉及到一个关系的逻辑结构 。 例如，有例如，有5 5个人，分别记为个人，分别记为a,b,c,d a,b,c,d ,e,e,其中其中a a是是b b的父亲的父亲 ，b b是是c c的父亲，的父亲，c c是是d d的父亲的父亲, ,d d是是e e的父亲，如果只讨论他的父亲，如果只讨论他 们之间所存在的父子关系，则可以用下面的二元

9、组形式们之间所存在的父子关系，则可以用下面的二元组形式 化地予以表达。化地予以表达。B=B=（K K，R R）其中：其中：K=a,b,c,d,eK=a,b,c,d,eR=r R=rr=, , r=, , 逻辑结构的逻辑结构的图形表示图形表示方式，对方式，对K K中的每个结点中的每个结点k ki i用一用一 个方框表示，而结点之间的关系用带箭头的线段表示个方框表示，而结点之间的关系用带箭头的线段表示 ，这，这5 5人之间的逻辑结构用图形的方式表达如下图人之间的逻辑结构用图形的方式表达如下图 所示所示 。若若k ki iK K，k kj jR R， r r，则称则称k ki i是是k kj j的相

10、对的相对 于关系于关系r r的的前驱结点前驱结点，k kj j是是k ki i的相对于关系的相对于关系r r的的后继结点后继结点 ，因为一般只讨论具有一种关系的逻辑结构，即，因为一般只讨论具有一种关系的逻辑结构，即R=rR=r ，所以简称所以简称k ki i是是k kj j前驱，前驱，k kj j是是k ki i的后继。如果某个结点没的后继。如果某个结点没 有前驱结点，称之为有前驱结点，称之为开始结点开始结点；如果某个结点没有后；如果某个结点没有后 继结点，称之为继结点，称之为终端结点终端结点；既不是开始结点也不是终；既不是开始结点也不是终 端结点的结点称为端结点的结点称为内部结点内部结点。

11、1.1.31.1.3数据的存储结构数据的存储结构 数据的逻辑结构是独立于计算机的，它与数据在数据的逻辑结构是独立于计算机的，它与数据在 计算机中的存储无关，要对数据进行处理，就必须将计算机中的存储无关，要对数据进行处理，就必须将 数据存储在计算机中。如果将数据在计算机中无规律数据存储在计算机中。如果将数据在计算机中无规律 地存储，那么在处理时是非常糟的，是没有用的。试地存储，那么在处理时是非常糟的，是没有用的。试 想一下，如果一本英汉字典中的单词是随意编排的，想一下，如果一本英汉字典中的单词是随意编排的， 这本字典谁会用！这本字典谁会用！对于一个数据结构对于一个数据结构B=B=（K K，R R

12、），），必须建立从结点必须建立从结点 集合到计算机某个存储区域集合到计算机某个存储区域MM的一个映象，这个映象的一个映象，这个映象 要要直接或间接直接或间接地表达结点之间的关系地表达结点之间的关系R R。数据在计算数据在计算 机中的存储方式称为数据的存储结构。机中的存储方式称为数据的存储结构。数据的存储结构主要有数据的存储结构主要有4 4种。种。数据的存储结构主要有数据的存储结构主要有4 4种。种。1 1 顺序存储顺序存储顺序存储通常用于存储具有线性结构的数据。将顺序存储通常用于存储具有线性结构的数据。将 逻辑上相邻的结点存储在连续存储区域逻辑上相邻的结点存储在连续存储区域MM的相邻的存的相邻

13、的存 储单元中，使得逻辑相邻的结点一定是物理位置相邻储单元中，使得逻辑相邻的结点一定是物理位置相邻 。 对于一个数据结构对于一个数据结构B=B=（K K，R R）其中其中K=kK=k1 1,k ,k2 2,k ,k3 3,k ,k4 4,k ,k5 5,k ,k6 6,k ,k7 7,k ,k 8 8,k ,k9 9 R=r R=r r=,它的顺序存储方式如图所示它的顺序存储方式如图所示 2 2 链式存储链式存储链式存储方式是给每个结点附加一个指针段，一链式存储方式是给每个结点附加一个指针段，一 个结点的指针所指的是该结点的后继的存储地址，因个结点的指针所指的是该结点的后继的存储地址，因 为一

14、个结点可能有多个后继，所以指针段可以是一个为一个结点可能有多个后继，所以指针段可以是一个 指针，也可以是一个多个指针。指针，也可以是一个多个指针。 例，数据的逻辑结构例，数据的逻辑结构B=B=（K K，R R）其中其中 K=kK=k1 1,k ,k2 2,k ,k3 3,k ,k4 4,k ,k5 5 R=r R=rR=,这是一个线性结构，它的链式存储如图所示。这是一个线性结构，它的链式存储如图所示。 3 3 索引存储索引存储在线性结构中，设开始结点的索引号为在线性结构中，设开始结点的索引号为1 1，其它结，其它结 点的索引号等于其前继结点的索引号加点的索引号等于其前继结点的索引号加1 1，则

15、每一个结，则每一个结 点都有唯一的索引号，索引号就是根据结点的索引号点都有唯一的索引号，索引号就是根据结点的索引号 确定该结点的存储地址。确定该结点的存储地址。 4 4 散列存储散列存储散列存储的思想是构造一个从集合散列存储的思想是构造一个从集合K K到存储区域到存储区域MM 的一个函数的一个函数h h，该函数的定义域为该函数的定义域为K K，值域为值域为MM，K K中的中的 每个结点每个结点k ki i在计算机中的存储地址由在计算机中的存储地址由h(h(k ki i) )确定。确定。 1.1.41.1.4数据的运算集合数据的运算集合 对于一批数据，数据的运算是定义在数据的逻对于一批数据，数据

16、的运算是定义在数据的逻 辑结构之上的，而运算的具体实现就依赖于数据的存辑结构之上的，而运算的具体实现就依赖于数据的存 储结构。储结构。 数据的运算集合要视情况而定，一般而言，数据数据的运算集合要视情况而定，一般而言，数据 的运算包括插入、删除、检索、输出、排序等。的运算包括插入、删除、检索、输出、排序等。插入：在一个结构中增加一个新的结点。插入：在一个结构中增加一个新的结点。删除：在一个结构删除一个结点。删除：在一个结构删除一个结点。检索：在一个结构中查找满足条件的结点。检索：在一个结构中查找满足条件的结点。输出：将一个结构中所有结点的值打印、输出。输出：将一个结构中所有结点的值打印、输出。排序：将一个结构中所有结点按某种顺序重新排列。排序