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