[精选]数据结构 李云清 杨庆红 揭安全 第01章_概论.pptx
《[精选]数据结构 李云清 杨庆红 揭安全 第01章_概论.pptx》由会员分享,可在线阅读,更多相关《[精选]数据结构 李云清 杨庆红 揭安全 第01章_概论.pptx(53页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、李云清李云清 杨庆红杨庆红 揭安全揭安全人民邮电出版社人民邮电出版社第第2版版datastrugmail.datastrugmail.第第2版版什么是数据结构什么是数据结构数据类型和抽象数据类型数据类型和抽象数据类型算法和算法分析算法和算法分析第一章 概述 瑞士著名的计算机科学家瑞士著名的计算机科学家Nicklaus WirthNicklaus Wirth在在19761976年出版了一本书,书名为年出版了一本书,书名为算法算法算法算法+数据结构数据结构数据结构数据结构=程序设程序设程序设程序设计计计计,它正说明了数据结构在程序设计中的作用。程,它正说明了数据结构在程序设计中的作用。程序设计的实
2、质即为计算机处理问题编制一组序设计的实质即为计算机处理问题编制一组 指令指令,首先需要解决两个问题:即算法和数据结构。算法即首先需要解决两个问题:即算法和数据结构。算法即处理问题的策略,而数据结构即为问题的数学模型。处理问题的策略,而数据结构即为问题的数学模型。很多数值计算问题的数学模型通常可用一组线性很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述,而大量或非线性的代数方程组或微分方程组来描述,而大量非数值计算问题的数学模型正是本门课程要讨论的数非数值计算问题的数学模型正是本门课程要讨论的数据结构。据结构。第一章 概述例一、求例一、求 n n 个整数中的最大值
3、。这似乎不成问题,个整数中的最大值。这似乎不成问题,但如果这些整数的值有可能到达但如果这些整数的值有可能到达10101212,那么对,那么对3232位的计位的计算机来说,就存在一个如何表示的问题。算机来说,就存在一个如何表示的问题。例二、交叉路口的红绿灯管理。如今十字路口横例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯,分别控制左拐、直行和竖两个方向都有三个红绿灯,分别控制左拐、直行和右拐,那么如何控制这些红绿灯既使交通不堵塞,又右拐,那么如何控制这些红绿灯既使交通不堵塞,又使流量最大呢?假设要编制程序解决问题,首先要解使流量最大呢?假设要编制程序解决问题,首先要解决一个如
4、何表示的问题。决一个如何表示的问题。例三、煤气管道的铺设问题。如图需为城市的各例三、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道,对小区之间铺设煤气管道,对 n n 个小区只需铺设个小区只需铺设 n-1 n-1 条管线,由于地理环境不同等因素使各条管线所需投条管线,由于地理环境不同等因素使各条管线所需投资不同如图上所标识,如何使投资成本最低?这资不同如图上所标识,如何使投资成本最低?这是一个讨论图的生成树的问题。是一个讨论图的生成树的问题。A AB BH HI IGGC CE ED DF F181812129 979795252565631311010858598986767212
5、145458 83434(a a)城市距离图)城市距离图A AB BH HI IGGC CE ED DF F12129 979793131101021218 83434(b b)联通各城市最小生成树)联通各城市最小生成树以上所举例子中的数学模型正是数据结构要讨论以上所举例子中的数学模型正是数据结构要讨论的问题。因此,简单地说,数据结构是一门讨论的问题。因此,简单地说,数据结构是一门讨论 描述描述现实世界实体的数学模型非数值计算及其上的操现实世界实体的数学模型非数值计算及其上的操作在计算机中如何表示和实现作在计算机中如何表示和实现 的学科。的学科。n n而信息的表示和组织又直接关系到处理信息的而
6、信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及,信息量的增程序的效率。随着计算机的普及,信息量的增加,信息范围的拓宽,使许多系统程序和应用加,信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂。因此,为程序的规模很大,结构又相当复杂。因此,为了编写出一个了编写出一个“好的程序,必须分析待处理好的程序,必须分析待处理的对象的特征及各对象之间存在的关系,这就的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题。是数据结构这门课所要研究的问题。n n 计算机是一门研究用计算机进行信息表示和处计算机是一门研究用计算机进行信息表示和处 理的科学。这里
7、面涉及到两个问题:理的科学。这里面涉及到两个问题:信息的表示信息的表示 信息的处理信息的处理综上所述综上所述1.1数据结构数据结构 1.1.1数据结构 随着计算机软、硬件的开展,计算机的应用范随着计算机软、硬件的开展,计算机的应用范围在不断扩大,计算机所处理的数据的数量也在不围在不断扩大,计算机所处理的数据的数量也在不断扩大,计算机所处理的数据已不再是单纯的数值断扩大,计算机所处理的数据已不再是单纯的数值数据,而更多的是非数值数据。数据,而更多的是非数值数据。需要处理的数据并不是杂乱无章的,它们一定需要处理的数据并不是杂乱无章的,它们一定有内在的联系,只有弄清楚它们之间的本质的联系,有内在的联
8、系,只有弄清楚它们之间的本质的联系,才能使用计算机对大量的数据进行有效的处理。才能使用计算机对大量的数据进行有效的处理。例例4 4 某电信公司的市话用户信息表格如以下图所示:某电信公司的市话用户信息表格如以下图所示:序号用户名电话号码用户住址街道名门牌号00001万方林北京西路165900002吴金平北京西路209900003王 冬瑶湖大道198700004王 三瑶湖大道200800005江 凡学府大道5035 这里序号、用户名、这里序号、用户名、号码等项称为基本项,它是号码等项称为基本项,它是有独立意义的最小标识单位,而用户住址称为组合项,有独立意义的最小标识单位,而用户住址称为组合项,组合
9、项是由一个或多个基本项或组合项组成,是有独立组合项是由一个或多个基本项或组合项组成,是有独立意义的标识单位,每一行称为一个结点,每一个组合项意义的标识单位,每一行称为一个结点,每一个组合项称为一个字段。称为一个字段。使用计算机处理用户信息表中的数据时,必须弄清楚使用计算机处理用户信息表中的数据时,必须弄清楚下面下面3 3个问题:个问题:1 数据的逻辑结构 这些数据之间有什么样的内在联系?这些数据之间有什么样的内在联系?除除最最前前和和最最后后两两个个结结点点之之外外,表表中中所所有有其其它它的的结结点点都都有有且且仅仅有有一一个个和和它它相相邻邻位位于于它它之之前前的的一一个个结结点点,也也有
10、有且且仅仅有有一一个个和和它它相相邻邻位位于于它它之之后后的的一一个个结结点点,这这些些就就是是用户信息表的逻辑结构。用户信息表的逻辑结构。2 数据的存储结构 将将用用户户信信息息表表中中的的所所有有结结点点存存入入计计算算机机时时,就就必必须须考考虑虑存存储储结结构构,使使用用C C语语言言进进行行设设计计时时,常常见见的的方方式式是是用用一一个个结结构构数数组组来来存存储储整整个个用用户户信信息息表表,每每一一个个数数组组元元素素是是一一个个结结构构,它它对对应应于于用用户户信信息息表表中中的的一一个个结结点点。数数据在计算机的存储方式称为存储结构。据在计算机的存储方式称为存储结构。3 数
11、据的运算集合 数据处理必涉及到相关的运算,在上述用户信息表数据处理必涉及到相关的运算,在上述用户信息表中,可以有删除一个用户、增加一个用户和查找某个用中,可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比方删除操户等操作。应该明确指明这些操作的含义。比方删除操作,是删除序号为作,是删除序号为5 5的用户还是删除用户名为王三的用的用户还是删除用户名为王三的用户是应该明确定义的,如果需要可以定义两个不同的删户是应该明确定义的,如果需要可以定义两个不同的删除操作,为一批数据定义的所有运算或称操作构成除操作,为一批数据定义的所有运算或称操作构成一个运算操作集合。一个运
12、算操作集合。对待处理的数据,只有分析清楚上面对待处理的数据,只有分析清楚上面3 3个方面的问个方面的问题,才能进行有效的处理!题,才能进行有效的处理!数数数数据据据据结结结结构构构构就就是是指指按按一一定定的的逻逻辑辑结结构构组组成成的的一一批批数数据据,使使用用某某种种存存储储结结构构将将这这批批数数据据存存储储于于计计算算机机中中,并并在在这些数据上定义了一个运算集合。这些数据上定义了一个运算集合。基于这个二维表格,我们可以在上面执行的操基于这个二维表格,我们可以在上面执行的操 作有:增加一个元素,删除元素,查找元素等。作有:增加一个元素,删除元素,查找元素等。存在的问题:线性查找的效率较
13、低等概率情存在的问题:线性查找的效率较低等概率情况下为况下为n/2n/2。数组存储时插入一个元素与删除一。数组存储时插入一个元素与删除一个元素效率较低。个元素效率较低。解决方法:改变数据存储结构,在新的存储结解决方法:改变数据存储结构,在新的存储结构上开发新的算法。构上开发新的算法。找找9595找找3535例5、旅游交通网络图实际问题:实际问题:如何选择任意两个城市之间的最短路径?如何选择任意两个城市之间的最短路径?建立通信网络时,如何在建立通信网络时,如何在n n个城市之间找到个城市之间找到n-1n-1连连线,使得这线,使得这n-1n-1条连线的和最小。即花费最小的条连线的和最小。即花费最小
14、的代价连通各个城市代价连通各个城市解决方法:解决方法:将城市与城市之间的距离等数据在计算机中采用将城市与城市之间的距离等数据在计算机中采用图型结构组织点与点之间存在多对多的关系。图型结构组织点与点之间存在多对多的关系。上述问题便可转化为图中两点之间的最短距离和上述问题便可转化为图中两点之间的最短距离和图的最小生成树问题。图的最小生成树问题。1.1.2数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构是是数数据据和和数数据据之之间间所所存存在在的的逻逻辑辑关关系,它可以用一个二元组系,它可以用一个二元组B=B=K K,R R来表示,其中来表示,其中K K是数据、即结点的有限集合;是数据、
15、即结点的有限集合;R R是集是集合合K K上关系的有限集合,这里的关系是从集合上关系的有限集合,这里的关系是从集合K K到集到集合合K K的关系,这里一般只涉及到一个关系的逻辑结构。的关系,这里一般只涉及到一个关系的逻辑结构。1.1.2数据的逻辑结构数据的逻辑结构 例例如如,有有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的的父父亲亲,如如果果只只讨讨论论他他们们之之间间所所存存在在的的父父子子关关系系,则则可可以以用用下下面面的的二二元元组组形形式式化
16、地予以表达。化地予以表达。B=B=K K,R R 其中:其中:K=a,b,c,d,eK=a,b,c,d,e R=r R=r r=,r=,逻逻辑辑结结构构的的图图形形表表示示方方式式,对对K K中中的的每每个个结结点点k ki i用用一一个个方方框框表表示示,而而结结点点之之间间的的关关系系用用带带箭箭头头的的线线段段表表示示,这这5 5人之间的逻辑结构用图形的方式表达如以下图人之间的逻辑结构用图形的方式表达如以下图 所示。所示。假设假设k ki iK K,k kj jR R,k r r,则称,则称k ki i是是k kj j的相的相对于关系对于关系r r的前驱结点,的前驱结点,k kj j是是
17、k ki i的相对于关系的相对于关系r r的后继结的后继结点,因为一般只讨论具有一种关系的逻辑结构,即点,因为一般只讨论具有一种关系的逻辑结构,即R=rR=r,所以简称,所以简称k ki i是是k kj j前驱,前驱,k kj j是是k ki i的后继。如果某个的后继。如果某个结点没有前驱结点,称之为开始结点;如果某个结点结点没有前驱结点,称之为开始结点;如果某个结点没有后继结点,称之为终端结点;既不是开始结点也没有后继结点,称之为终端结点;既不是开始结点也不是终端结点的结点称为内部结点。不是终端结点的结点称为内部结点。abcde线性逻辑结构线性逻辑结构二、树型结构二、树型结构 结构中的数据元
18、素之间存在一结构中的数据元素之间存在一对多的关系。对多的关系。125643三、图状结构或网状结构三、图状结构或网状结构 结构中的数据元素之结构中的数据元素之间存在多对多的关系。间存在多对多的关系。12345671.1.3数据的存储结构数据的存储结构 数数据据的的逻逻辑辑结结构构是是独独立立于于计计算算机机的的,它它与与数数据据在在计计算算机机中中的的存存储储无无关关,要要对对数数据据进进行行处处理理,就就必必须须将将数数据据存存储储在在计计算算机机中中。如如果果将将数数据据在在计计算算机机中中无无规规律律地地存存储储,那那么么在在处处理理时时是是非非常常糟糟的的,是是没没有有用用的的。试试想想
19、一一下下,如如果果一一本本英英汉汉字字典典中中的的单单词词是是随随意意编编排排的的,这本字典谁会用!这本字典谁会用!对对于于一一个个数数据据结结构构B=B=K K,R R,必必须须建建立立从从结结点点集集合合到到计计算算机机某某个个存存储储区区域域MM的的一一个个映映象象,这这个个映映象象要要直直接接或或间间接接地地表表达达结结点点之之间间的的关关系系R R。数数据据在在计计算算机中的存储方式称为数据的存储结构。机中的存储方式称为数据的存储结构。数据的存储结构主要有数据的存储结构主要有4 4种。种。数据的存储结构主要有数据的存储结构主要有4 4种。种。1 1 顺序存储顺序存储 顺序存储通常用于
20、存储具有线性结构的数据。将顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域逻辑上相邻的结点存储在连续存储区域MM的相邻的存的相邻的存储单元中,使得逻辑相邻的结点一定是物理位置相邻。储单元中,使得逻辑相邻的结点一定是物理位置相邻。对于一个数据结构对于一个数据结构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,k8 8,k,k9 9 R=r R=r r=kr=,它的顺序存储方式如下图它的顺序存储方式如下图 k1k2k3k6k5k4k7k8k9存储地址 M10011002100310
21、0410051006100710081009特点:用物理相特点:用物理相邻的位置关系表邻的位置关系表示其逻辑关系示其逻辑关系2 2 链式存储链式存储 链式存储方式是给每个结点附加一个指针段,一链式存储方式是给每个结点附加一个指针段,一个结点的指针所指的是该结点的后继的存储地址,因个结点的指针所指的是该结点的后继的存储地址,因为一个结点可能有多个后继,所以指针段可以是一个为一个结点可能有多个后继,所以指针段可以是一个指针,也可以是一个多个指针。指针,也可以是一个多个指针。例,数据的逻辑结构例,数据的逻辑结构B=B=K K,R R 其中其中 K=k K=k1 1,k,k2 2,k,k3 3,k,k
22、4 4,k,k5 5 R=r R=r r=k r=,这是一个线性结构,它的链式存储如下图。这是一个线性结构,它的链式存储如下图。100010011002100310041005100610071008存储地址 info nextk41006k21007k11003k5k31005特点特点:逻辑上相邻逻辑上相邻物理上不一定相物理上不一定相邻。邻。3 3 索引存储索引存储 在线性结构中,设开始结点的索引号为在线性结构中,设开始结点的索引号为1 1,其它结,其它结点的索引号等于其前继结点的索引号加点的索引号等于其前继结点的索引号加1 1,则每一个结,则每一个结点都有唯一的索引号,索引号就是根据结点的
23、索引号点都有唯一的索引号,索引号就是根据结点的索引号确定该结点的存储地址。确定该结点的存储地址。4 4 散列存储散列存储 散列存储的思想是构造一个从集合散列存储的思想是构造一个从集合K K到存储区域到存储区域MM的一个函数的一个函数h h,该函数的定义域为,该函数的定义域为K K,值域为,值域为MM,K K中的中的每个结点每个结点k ki i在计算机中的存储地址由在计算机中的存储地址由h hk ki i确定。确定。1.1.4数据的运算集合数据的运算集合 对于一批数据,数据的运算是定义在数据的逻对于一批数据,数据的运算是定义在数据的逻辑结构之上的,而运算的具体实现就依赖于数据的存辑结构之上的,而
24、运算的具体实现就依赖于数据的存储结构。储结构。数数据据的的运运算算集集合合要要视视情情况况而而定定,一一般般而而言言,数数据据的运算包括插入、删除、检索、输出、排序等。的运算包括插入、删除、检索、输出、排序等。插入:在一个结构中增加一个新的结点。插入:在一个结构中增加一个新的结点。删除:在一个结构删除一个结点。删除:在一个结构删除一个结点。检索:在一个结构中查找满足条件的结点。检索:在一个结构中查找满足条件的结点。输出:将一个结构中所有结点的值打印、输出。输出:将一个结构中所有结点的值打印、输出。排序:将一个结构中所有结点按某种顺序重新排列。排序:将一个结构中所有结点按某种顺序重新排列。在程序
25、设计中,数据和运算是两个不可缺少的因在程序设计中,数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的。从机器指令、汇编语言中的数据没关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念,到现在的面向对象程序设计语言中抽有类型的概念,到现在的面向对象程序设计语言中抽象数据类型概念的出现,程序设计中的数据经历了一象数据类型概念的出现,程序设计中的数据经历了一次次抽象,数据的抽象经历了三个开展阶段。次次抽象,数据的抽象经历了三个开展阶段。1.2数据类型和抽象数据类型数据类型和抽象数据类型从无类型的二进制数到基本
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精选 精选数据结构 李云清 杨庆红 揭安全 第01章_概论 数据结构 安全 01 概论
限制150内