2 数据结构相关概念.ppt

《2 数据结构相关概念.ppt》由会员分享，可在线阅读，更多相关《2 数据结构相关概念.ppt（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第2 2章章线性数据结构线性数据结构在此幻灯片插入公司的徽标在此幻灯片插入公司的徽标从从“插入插入”菜单菜单选择图片选择图片找到徽标文件找到徽标文件单击单击“确定确定”重新设置徽标大小重新设置徽标大小单击徽标内任意位置。徽标外部单击徽标内任意位置。徽标外部出现的方框是出现的方框是“调整控点调整控点”使用这些重新设置对象大小使用这些重新设置对象大小如果在使用尺寸调整控点前按下如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维键，则对象改变大小但维持原比例。持原比例。1065865姓名姓名 学号学号 成绩成绩 班级班级李红李红 2001456 95 6 ABCDEFG第第2 2章章

2、线性数据结构线性数据结构数据结构数据结构的地位的地位综合性基础课；综合性基础课；介于数学、计算机硬件与计算机软件之间的核介于数学、计算机硬件与计算机软件之间的核心课程；心课程；不仅是一般程序设计的基础，而且是设计和实不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础统程序和大型应用程序的重要基础算法算法+数据结构数据结构=程序程序第第2 2章章线性数据结构线性数据结构数据结构应用实例数据结构应用实例对弈（树）对弈（树）报童送信最短距离（图）报童送信最短距离（图）哈夫曼编码（哈夫曼树）哈夫曼编码（

3、哈夫曼树）调度（排序）调度（排序）搜索（查找）搜索（查找）第第2 2章章线性数据结构线性数据结构数据结构应用实例数据结构应用实例数字视频监控系统数字视频监控系统摄像机摄像机云台：上、下、左、右云台：上、下、左、右镜头：变焦、聚焦镜头：变焦、聚焦报警器报警器位置、类型、状态位置、类型、状态用户用户基本信息基本信息工作信息工作信息联系信息联系信息日志日志存储线性表树图查找排序第第2 2章章线性数据结构线性数据结构图像处理、分析与机器视觉图像处理、分析与机器视觉(第第3版版)Image Processing,Analysis,and Machine Vision第4章 图像分析的数据结构 69 4.

4、1 图像数据表示的层次 69 4.2 传统图像数据结构 70 4.2.1 矩阵 70 4.2.2 链 72 4.2.3 拓扑数据结构 73 4.2.4 关系结构 73 4.3 分层数据结构 74 4.3.1 金字塔 74 4.3.2 四叉树 75 4.3.3 其他金字塔结构 76 第第2 2章章线性数据结构线性数据结构第第2章章 线性数据结构线性数据结构 2.1 基本概念基本概念 2.1.1 数据和数据结构数据和数据结构2.1.2 算法的描述和评价算法的描述和评价2.2 线性表线性表 2.2.1 线性表的定义及操作线性表的定义及操作2.2.2 线性表的线性表的 顺序存储结构顺序存储结构2.2.

5、3 线性表的链式存储结构线性表的链式存储结构2.2.4 循环链表和双向链表循环链表和双向链表2.3 栈和队列栈和队列 2.3.1 栈栈2.3.2 队列队列2.4 串和数组串和数组 2.4.1 串串2.4.2 数组数组第第2 2章章线性数据结构线性数据结构2.1 基基 本本 概概 念念 2.1.1 数据和数据结构数据和数据结构现代数字计算机原是作为数值计算工具而发明的。随着计算机的发展，在计算机的绝大多数应用中，能够存取、处理大量信息的能力却被认为是计算机的首要特征，而它的计算能力在许多情况下已经几乎被人们忽略了。有位美国学者曾批评说：“计计算算机机”这个词只告诉我们以前能做的事，却未道出它的潜

6、能。有鉴于此，人们常常把计算机称作数据处理机数据处理机。第第2 2章章线性数据结构线性数据结构一.什么是数据？数数据据就是是信息的载体,它可以用计算机表示并加工。可以看出，数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的初期，由于计算机主要用于数值计算，数据指的就是数值。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如字符、文字、表格、图形、图像、声音等也属于数据的范畴。数数据据就就是是对对客客观观事事物物的的符符号号表表示示，是是可可以以被被计计算算机机处理的处理的“原料原料”。第第2 2章章线性数据结构线性数据结构二二.数数据据元元素素是数据集合中的一个个体，

7、它是数据的基基本本单单位位。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。数据元素可以是一个数或字符串，也可以由若干数数据据项项组成(数据的最最小小单单位位)。在这种情况下，通常把数数据据元元素素称为记记录录。如表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。第第2 2章章线性数据结构线性数据结构表2-1 学生学籍登记表学 号姓 名性 别民 族籍 贯专 业1王 安男汉北京计算机通信2李 华男回河北软 件3张 莉女汉山西计算机应用4张 平女汉广东软 件第第

8、2 2章章线性数据结构线性数据结构三三.数据对象数据对象 性质相同的数据元素的集合，数据的子集。如上表中的学生学籍卡中的所有学生纪录。四四.什么是数据结构？什么是数据结构？在任何问题中，构成数据的数据元素并不是孤立存在的，它们之间存在着一定的关系以表达不同的事物及事物之间的联系。所以简单地说，数据结数据结构构就是指同一数据对象中各数据元素间存在的一种或多种特定关系。第第2 2章章线性数据结构线性数据结构五.数据结构数据结构的研究内容的研究内容？它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容：计算机处理非数值

9、计算的问题中的数据元素间的结构关系（逻逻辑辑结结构构）、以及这样的关系在计算机内存中的存储形式（物物理理结结构构存存储储结结构构），和对数据元素及其关系的操作实现（算法）（算法）。第第2 2章章线性数据结构线性数据结构1.数据的逻辑结构数据的逻辑结构 2.数据的存储结构数据的存储结构 3.数据的运算：数据的运算：检索、排序、插入、删除、修改等。检索、排序、插入、删除、修改等。A.线性结构线性结构 B.非线性结构非线性结构A.顺序存储顺序存储 B.链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面反映数据元素反映数据元素之间的逻辑关之间的逻

10、辑关系系数据元素在计算机数据元素在计算机内部的组织方式内部的组织方式C.散列结构（散列表）散列结构（散列表）D.索引结构（索引表）索引结构（索引表）第第2 2章章线性数据结构线性数据结构 1.数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为 Data Structure=(D，R)其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。根据数据元素之间关系的不同特性，数据结构又可分为两大类分为两大类：线性数据结构线性数据结构和非线性数据结构非线性数据结构。第第2 2章章线性数据结构线性数据结构在自然界中，事物之

11、间的关系（逻辑结构）在自然界中，事物之间的关系（逻辑结构）主要有四种表现形式：主要有四种表现形式：集合：元素同属于一个集合集合：元素同属于一个集合线性关系：一个对一个，并非一一对应线性关系：一个对一个，并非一一对应树形关系：一个对多个树形关系：一个对多个图状关系（网状）：多个对多个图状关系（网状）：多个对多个第第2 2章章线性数据结构线性数据结构 2数据的存储结构数据的存储结构 数数据据的的逻逻辑辑结结构构是从逻辑上来描述数据元素之间的关系的，是独立于计算机的。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究数据元素和数据元素之间的关系如何在计算机中表示，这就是数据的存储结

12、构数据的存储结构。计算机的存储器是由很多存储单元组成的，每个存储单元有惟一的地址。数数据据的的存存储储结结构构要讨论的就是数据结构在计算机存储器上的存储映像方法。第第2 2章章线性数据结构线性数据结构 实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。一般来说，数据在存储器中的存储有四种基本的映像方法四种基本的映像方法。(1)顺顺序序存存储储结结构构。这种存储方式主要用于线性数据结构，就是把数据元素按某种顺序放在一块连续的存储单元中。其特特点点是逻辑上相邻的数据元素存储在物理上相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。某些非线性数据结构也可以采用顺序方式存储，例如完全二

13、叉树、多维数组等，具体方法将在后面介绍。第第2 2章章线性数据结构线性数据结构 (2)链链式式存存储储结结构构。链式存储结构可可以以把把逻逻辑辑上上相相邻邻的的两两个个元元素素存存放放在在物物理理上上不不相相邻邻的的存存储储单单元元中中。即即可可用用一一组组任任意意的的存存储储单单元元来来存存储储数数据据元元素素，这这些些存存储储单单元元可可以以是是连连续续的的，也也可可以以是是不不连连续续的的。另外对于非线性数据结构，还可以在线性编址的计算机存储器中表示结点之间的非线性关系。链式存储结构的特特点点就是将将存存放放每每个个数数据据元元素素的的结结点点分分为为两两部部分分：一部分存放数据元素(称

14、为数数据据域域)：另一部分存放指示存储地址的指针(称为指指针针域域)，借助指针表示数据元素之间的关系。第第2 2章章线性数据结构线性数据结构 (3)索索引引存存储储结结构构。在线性表中，数据元素可以排成一个序列：R1、R2、R3、Rn，每个数据元素Ri在序列里都有对应的位置数据i，这就是元素的索索引引。索引存储结构就是通过数据元素的索引号i来确定数据元素Ri的存储地址。一般索引存储结构的实现方法是以若干数据元素为一组，建立特征索引，用索引号来确定存储地址。第第2 2章章线性数据结构线性数据结构 (4)散散列列存存储储结结构构。这种存储方法就是在数据元素与其在存储器上的存储位置之间建立一个映像关

15、系函数F。也就是说，数据元素的存放位置与其元素值呈函数关系。根据这个映像关系F，已知某数据元素就可以得到它的存储地址。即D=F(E)，这里E是要存放的数据元素，D是该数据元素的存储位置。可见，这种存储结构的关关键键是设计这个函数F。但函数F不可能解决数据存储中的所有问题，还应有一套意外事件的处理方法，它们共同实现数据的散列存储结构。第第2 2章章线性数据结构线性数据结构 3.数据的运算数据的运算 数数据据的的运运算算是定定义义在在数数据据逻逻辑辑结结构构上上的的操操作作，每种数据结构都有一个运算的集合。常常用用的的运运算算有检检索索、插插入入、删删除除、更更新新、排排序序等等。运运算算的的具具

16、体体实实现现要在存储结构存储结构上进行。数据的运算是数据结构的一个重要方面。讨论任何一种数据结构时都离不开对该结构上的数据运算及实现算法的讨论。第第2 2章章线性数据结构线性数据结构Tips从数据结构的逻辑结构、存储结构和数据运算三个方面去理解各种数据结构的异同之处及相互间的关系，懂得从定义定义（包括逻辑结构和基本操作）和实现实现（包括存储结构和操作实现）两个层次去分析各种数据结构。第第2 2章章线性数据结构线性数据结构六、数据类型和抽象数据类型六、数据类型和抽象数据类型（一）名词和定义（一）名词和定义数据类型：数据类型：用以刻划程序操作对象的特性，且与数据结构密用以刻划程序操作对象的特性，且

17、与数据结构密切相关。具体来讲，就是程序设计语言中允许的变量类型。切相关。具体来讲，就是程序设计语言中允许的变量类型。原子类型：原子类型：高级语言中数据值不可分解的数据类型。例如高级语言中数据值不可分解的数据类型。例如c语语言中的整型、实型、字符型、枚举型、指针型等言中的整型、实型、字符型、枚举型、指针型等结构类型：结构类型：数据值由若干成分按某种结构组成的可分解的数数据值由若干成分按某种结构组成的可分解的数据类型。例如数组、结构体等据类型。例如数组、结构体等抽象数据类型：抽象数据类型：指一个数学模型以及定义在该模型上的一组指一个数学模型以及定义在该模型上的一组操作。其定义仅取决于它的一组逻辑特

18、性，而与其在计算机操作。其定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。内部如何表示和实现无关。第第2 2章章线性数据结构线性数据结构七、数据逻辑结构的例子七、数据逻辑结构的例子抽象描述抽象描述 Data-Structure=D,RD：数据元素的集合；：数据元素的集合；R：D上关系的集合上关系的集合关键字：数据元素中的某个值是彼此不同的可用关键字：数据元素中的某个值是彼此不同的可用于唯一标识该数据元素的分量于唯一标识该数据元素的分量第第2 2章章线性数据结构线性数据结构例、某单位人事表例、某单位人事表第第2 2章章线性数据结构线性数据结构 每一行都是一个数据元素，工号可以

19、作为关键字来抽象出代表每个数据元素的数据值，于是有D=01,02,03,04,05,06,07,08,09D上的关系的集合是若干偶对的集合，其可因关系而异设：R1=r1 R2=r2 R3=r3,r中每个元素为一偶对,x1、x2之间存在关系且x1,x2属于DR1=,第第2 2章章线性数据结构线性数据结构R2=,R3=,第第2 2章章线性数据结构线性数据结构看一下这些关系都构成了什么样的数据逻辑结构结论：相同数据元素的集合，因其关系的不同而构成不同的数据逻辑结构第第2 2章章线性数据结构线性数据结构 2.1.2 算法的描述和评价算法的描述和评价 算算法法是对特定问题求解步骤的一种描述，它是指令的有

20、限序列，其中每一条指令表示一个或多个操作。有时，把运算的实现称之为算法。运运算算是是定定义义在逻逻辑辑结结构构上的操作，是独立于计算机的，而运运算算的的具具体体实实现现则是在计算机上进行的，因此算法要依赖于数据的存储结构存储结构。第第2 2章章线性数据结构线性数据结构算法应具有下述的五个重要特性五个重要特性：1.有有穷穷性性。一个算法必须在执行有穷步后结束，且每一步都能在有限的时间内完成。2.确确定定性性。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得到相同的输出第第2 2章章线性数据结构线性数据结构3.可可行

21、行性性。一个算法必须是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。4.4.输输入入。一个算法应该有零个或多个输入。5.输输出出。一个算法应该有零个或多个输出。第第2 2章章线性数据结构线性数据结构 1.算法的描述算法的描述 算法需要用某种工具来描述，同时，算法可有各种描述方法以满足不同的需求。常常用用的的描描述述方方法法有自然语言描述、伪码描述、流程图描述、类PASCAL语言描述、C语言描述等。教材中使用类Pascal语言作为描述算法的工具。讲课中使用C语言描述。第第2 2章章线性数据结构线性数据结构算法的自然语言描述算法的自然语言描述我们有一串随机数列。我们的目

22、的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”：首先将第一颗豆子放入口袋中。从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。直到最后一颗豆子。最后口袋中的豆子就是所有的豆子中最大的一颗。第第2 2章章线性数据结构线性数据结构流流程程图图描描述述第第2 2章章线性数据结构线性数据结构第第2 2章章线性数据结构线性数据结构第第2 2章章线性数据结构线性数据结构伪码描述伪码描述largest=list1for counter=2 to length(list):if listcou

23、nter largest:largest=listcounterprint largest符号说明:=用于表示赋值。即：右边的值被赋予给左边的变量。Listcounter用于表示数列中的第counter项。例如：如果counter的值是5，那么Listcounter表示数列中的第5项。=用于表示“小于或等于”第第2 2章章线性数据结构线性数据结构 2.算法的评价算法的评价 在算法是“正正确确性性”（+易易读读性性+健健壮壮性性）的前提下，评价算法主要有两个指标两个指标：(1)时时间间复复杂杂度度（性性）：依据算法编制成程序后，在计算机上运行时所消耗的时间。(2)空空间间复复杂杂度度（性性）：依

24、据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。第第2 2章章线性数据结构线性数据结构 要确定实现算法在运行时所所花花的的时时间间和所所占占用用的的存存储储空空间间，最直接的方法就是测测试试，即将依据算法编制的程序在计算机上运行，所得到的结果就是算法运行时所花的时间。这种方法有时也称为事后统计的方法事后统计的方法。另外一种方法就是事事前前分分析析估估算算的的方方法法，这是人们常常采用的一种方法。第第2 2章章线性数据结构线性数据结构 (1)时时间间复复杂杂度度。假定知道算法中每一条语句执行一次所花的平均时间，则有：算法运行所花的时间算法运行所花的时间=语句执行一次所花时间语句执行一

25、次所花时间 语句执行次数语句执行次数对于事前分析估算方法，我们讨论的目标集中在确定语句的执行频度上，即把算法的语语句句执执行频度行频度作为衡量一个算法时间复杂度的依据。第第2 2章章线性数据结构线性数据结构 在实际分析中，关注的是频频度度的的数数量量级级，即按重复执行次数最多的语句确定算法的时间复杂度。引入符号“O”来表示这种数量级，算法的时间复杂度记作：T(n)=O(f(n)它表示随问问题题规规模模n的增大，算法执行时间的增长率和函数f(n)的增长率相同，称作算法的渐渐近近时时间间复杂度复杂度，简称时间复杂度时间复杂度。按数量级递增次序排列，常常见见的的几几种种时时间间复复杂杂度度有：O(1

26、)，O(logn)，O(n)，O(nlogn)，O(n2)，O(n3)，O(2n)，这里，n表示问题的规模。第第2 2章章线性数据结构线性数据结构数组元素相加数组元素相加执行次数int sum(int arr,int n)int i,total=0;1 for(i=0;in;i+)n+1 total+=arri;nreturn total;12n+3第第2 2章章线性数据结构线性数据结构矩阵相加矩阵相加执行次数void add(int a,int b,int c,int n,int n)for(int i=0;i n;i+)n+1 for(int j=0;j n;j+)n(n+1)cij=ai

27、j+bijn22n2+2n+1第第2 2章章线性数据结构线性数据结构矩阵相乘矩阵相乘 执行次数void mul(int a,int b,int c,int n)int i,j,k,sum;1 for(i=0;i n;i+)n+1 for(j=0;j n;j+)n(n+1)sum=0;n2 for(k=0;k n;k+)n2(n+1)sum=sum+aik*bkj;n3 cij=sum;n2 2n3+4n2+2n+2第第2 2章章线性数据结构线性数据结构複雜度等級複雜度等級1.O(1)：常數時間(constant time)2.O(log n)：次線性時間(sub-linear)3.O(n)：線

28、性時間(linear)4.O(n log n)5.O(n2)：平方時間(quadratic)6.O(n3)：立方時間(cubic)7.O(2n)：指數時間(exponential)8.O(n!)：階乘時間(factorial)如果n足夠大時1 log n n n log n n2 n3 2n n!第第2 2章章线性数据结构线性数据结构 需要指出的是，有些算法的基本操作的频频度度不仅仅依赖于问题的规模n，还取决于它所处理的输入数据集的状态i，即T(n,i)。对于这一类算法，一般按每种情况发生的概率求出其数学期望值作为算法的平平均均时时间间复复杂杂度度，或者按最坏情况下基本操作的执行频度得出算法最

29、最坏坏情情况况下下的的时时间间复复杂杂度度，以此作为该算法的时间复杂度。第第2 2章章线性数据结构线性数据结构 (2)空空间间复复杂杂度度。一个算法的实现所占用的存储空间大致有这样三三个个方方面面：其其一一是指令、常数、变量所占用的存储空间；其其二二是输入数据所占用的存储空间；其其三三是算法执行时必需的辅辅助助空空间间。前两种空间是计算机运行时所必须的。因此，把算法在执行时所需的辅辅助助空空间间的大小的大小作为分析算法空间复杂度的依据。第第2 2章章线性数据结构线性数据结构 与算法时间复杂度的表示一致，也用辅助空间大小的数数量量级级来表示算法的空间复杂度，仍然记为：S(n)=O(f(n)。常见

30、的几种空间复杂度有：O(1)，O(n)，O(n2)，O(n3)等。事实上，一个问题的算法实现，时时间间复复杂杂度度和空空间间复复杂杂度度往往是相相互互矛矛盾盾的，两者很难兼顾。因此，只能根据具体情况具体分析。第第2 2章章线性数据结构线性数据结构小结（实践出真知）小结（实践出真知）对数据结构的初学者最难之处是经过学习之后，虽然能看懂看懂教材上的算法，但当自己动手设计算法解决实际问题时无从下手，除了掌握必要的方法之外，这一问题必须通过学生多练习多练习多动手多动手，培养自己的程序设计经验和素质来解决，因此要求学生必须认真对待算法设计型的习题，通过多做这类习题来理解、消化和巩固所学的知识，提高分析问题、解决问题的能力分析问题、解决问题的能力以及编程能力以及编程能力。设计较难算法的方法和步骤是：首先明确算法要解决的问题目标问题目标，选择合适的数据结构数据结构，确定在所选的数据结构上必须有哪些操作，写出抽象的算法算法，然后确定存储结构存储结构，对抽象算法中每个操作逐步求精地写出最终的程序。