计算机软件基础：第2章 线性数据结构-1

《计算机软件基础：第2章 线性数据结构-1》由会员分享，可在线阅读，更多相关《计算机软件基础：第2章 线性数据结构-1（31页珍藏版）》请在金锄头文库上搜索。

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

2、G第第2 2章章 线性数据结构线性数据结构 第第2章章 线性数据结构线性数据结构 2.1 基本概念基本概念 2.1.1 数据和数据结构数据和数据结构2.1.2 算法的描述和评价算法的描述和评价2.2 线性表线性表 2.2.1 线性表的定义及操作线性表的定义及操作2.2.2 线性表的线性表的 顺序存储结构顺序存储结构2.2.3 线性表的链式存储结构线性表的链式存储结构2.2.4 循环链表和双向链表循环链表和双向链表2.3 栈和队列栈和队列 2.3.1 栈栈2.3.2 队列队列2.4 串和数组串和数组 2.4.1 串串2.4.2 数组数组习题习题 第第2 2章章 线性数据结构线性数据结构 2.1

3、基基 本本 概概 念念 2.1.1 数据和数据结构数据和数据结构 现代数字计算机原是作为能快速地进行复杂、耗时计算的工具而发明的。随着计算机的发展，在计算机的绝大多数应用中，能够存取、处理大量信息的能力却被认为是计算机的首要特征，而它的计算能力在许多情况下已经几乎被人们忽略了。有位美国学者曾批评说：“计计算算机机”这个词只告诉我们以前能做的事，却未道出它的潜能。有鉴于此，人们常常把计算机称作数据处理机数据处理机。第第2 2章章 线性数据结构线性数据结构 什么是数据？数数据据就是是信息的载体,它可以用计算机表示并加工。 可以看出，数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的

4、初期，由于计算机主要用于数值计算，数据指的就是数值。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如字符、文字、表格、图形、图像、声音等也属于数据的范畴。第第2 2章章 线性数据结构线性数据结构 数数据据元元素素是数据集合中的一个个体，它是数据的基基本本单单位位。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。 数据元素可以是一个数或字符串，也可以由若干数数据据项项（域域、属属性性或或字字段段）组成(数据的最最小小单单位位)。在这种情况下，通常把数数据据元元素素称为记记录录(结结点点、顶顶点点)。如表2-1所示的学生学籍登记表，在这个表

5、中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。第第2 2章章 线性数据结构线性数据结构 表2-1 学生学籍登记表学 号姓 名性 别民 族籍 贯专 业1王 安男汉北京计算机通信2李 华男回河北软 件3张 莉女汉山西计算机应用4张 平女汉广东软 件第第2 2章章 线性数据结构线性数据结构 什么是数据结构？在任何问题中，构成数据的数据元素并不是孤立存在的，它们之间存在着一定的关系以表达不同的事物及事物之间的联系。 数数据据结结构构就是研究数据及数据元素之间关系的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系

6、统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容： 数据的逻辑结构。 数据的存储结构。 数据的运算。第第2 2章章 线性数据结构线性数据结构 1. 数据的逻辑结构数据的逻辑结构 2. 数据的存储结构数据的存储结构 3. 数据的运算：数据的运算： 检索、排序、插入、删除、修改等。检索、排序、插入、删除、修改等。 A . 线性结构线性结构 B . 非线性结构非线性结构A . 顺序存储顺序存储 B . 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面反映数据元素反映数据元素之间的逻辑关之间的逻辑关系系数据元素在计算机数据元素在计

7、算机内部的组织方式内部的组织方式C . 散列结构（散列表）散列结构（散列表）D . 索引结构（索引表）索引结构（索引表）第第2 2章章 线性数据结构线性数据结构 1. 数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为 Data Structure =(D，R) 其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。 根据数据元素之间关系的不同特性，数据结构又可分分为为两两大大类类：线线性性数数据据结结构构和非非线线性性数数据据结结构构。按照这种划分原则，本门课程涉及的所有数据结构如图2-1所示。第第2 2章章

8、 线性数据结构线性数据结构 图2-1 数据结构分类 数据结构线性数据结构非线性数据结构一对一一对一线性表栈队列串数组树图一对多一对多多对多多对多第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构 2数据的存储结构（数据的存储结构（物理结构物理结构） 数数据据的的逻逻辑辑结结构构是从逻辑上来描述数据元素之间的关系的，是独立于计算机的。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究数据元素和数据元素之间的关系如何在计算机

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

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

11、结构线性数据结构 (3) 索索引引存存储储结结构构。在线性表中，数据元素可以排成一个序列：R1、R2、R3、Rn ，每个数据元素Ri在序列里都有对应的位置数据i，这就是元素的索索引引。索引存储结构就是通过数据元素的索引号i来确定数据元素Ri的存储地址。一般索引存储结构的实现方法是建立附加的索索引引表表，索引表里第i项的值就是第i个元素的存储地址。第第2 2章章 线性数据结构线性数据结构 (4) 散散列列存存储储结结构构。这种存储方法就是在数据元素与其在存储器上的存储位置之间建立一个映像关系F。根据这个映像关系F，已知某数据元素就可以得到它的存储地址。即D=F(E)，这里E是要存放的数据元素，D

12、是该数据元素的存储位置。可见，这种存储结构的关关键键是设计这个函数F。但函数F不可能解决数据存储中的所有问题，还应有一套意外事件的处理方法，它们共同实现数据的散列存储结构。以后要介绍的哈希表，就是散列存储结构的一个实例。第第2 2章章 线性数据结构线性数据结构 3. 数据的运算数据的运算 数数据据的的运运算算是定义在数据逻辑结构上的操作，每种数据结构都有一个运算的集合。常常用用的的运运算算有检索、插入、删除、更新、排序等。运运算算的的具具体体实实现现要在存储结构上进行。 数据的运算是数据结构的一个重要方面。讨论任何一种数据结构时都离不开对该结构上的数据运算及实现算法的讨论。 第第2 2章章 线

13、性数据结构线性数据结构 2.1.2 算法的描述和评价算法的描述和评价 算算法法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。有时，把运算的实现称之为算法。运运算算是是定定义义在逻逻辑辑结结构构上的操作，是独立于计算机的，而运运算算的的具具体体实实现现则是在计算机上进行的，因此算法要依赖于数据的存储结构存储结构。 作为算法应具有下述的五个重要特性五个重要特性： (1) 有有穷穷性性。一个算法必须在执行有穷步后结束，且每一步都能在有限的时间内完成。第第2 2章章 线性数据结构线性数据结构 (2) 确确定定性性。算法中每一条指令必须有确切的含义，读者理解时不会

14、产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得到相同的输出。 (3) 可可行行性性。一个算法必须是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。 (4) 输入输入。一个算法应该有零个或多个输入。 (5) 输出输出。一个算法应该有一个或多个输出。第第2 2章章 线性数据结构线性数据结构 1. 算法的描述算法的描述 算法需要用一种工具来描述，同时，算法可有各种描述方法以满足不同的需求。 常常用用的的描描述述方方法法有自然语言描述、伪码描述、流程图描述、类PASCAL语言描述、C语言描述等。本课程中使用C语言作为描述算法的工具。第第2

15、2章章 线性数据结构线性数据结构 2. 算法的评价算法的评价 在算法是“正正确确性性”（ + 易易读读性性 + 健健壮壮性性）的前提下，评价算法主要有两个指标两个指标： (1) 时时间间复复杂杂度度（性性）：依据算法编制成程序后，在计算机上运行时所消耗的时间。 (2) 空空间间复复杂杂度度（性性）：依据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。第第2 2章章 线性数据结构线性数据结构 要确定实现算法在运行时所所花花的的时时间间和所所占占用用的的存存储储空空间间，最直接的方法就是测测试试，即将依据算法编制的程序在计算机上运行，所得到的结果就是算法运行时所花的时间。这种方法有时也称

16、为事事后后统统计计的的方方法法。同一算法在不同档次的计算机上运行所花的时间肯定不同，这取决于计算机系统的速度。 另外一种方法就是事事前前分分析析估估算算的的方方法法，这是人们常常采用的一种方法，下面将详细讨论之。第第2 2章章 线性数据结构线性数据结构 (1) 时时间间复复杂杂度度。假定知道算法中每一条语句执行一次所花的平均时间，则有： 算法运行所花的时间算法运行所花的时间= = 语句执行一次所花的时间语句执行一次所花的时间 语句执行次数语句执行次数 其中语句执行一次所花的平均时间取决于计算机系统中硬件、软件等环境因素，而一个算法中语句的执行次数一般来说是确定的。因此，对于事前分析估算方法，我

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

18、，O(nlogn)，O(n2)，O(n3)，O(2n)，这里，n表示问题的规模。第第2 2章章 线性数据结构线性数据结构 例如，在下列三个程序段中： (1) +x；s = 0； T(n)= O(1) (2) for ( i = 1；i=n；+i ) (常量阶常量阶) +x；s += x； T(n)= O(n) (3) for ( j = 1；j=n； +j ) (线性阶线性阶) for ( k = 1；k=n；+k ) T(n)= O(n2) +x；s +=x； (平方阶平方阶) 含基本操作“x增1”的语句的频度分别为1，n和n2 ，则这三个程序段的时间复杂度分别为O(1)，O(n)和O(n2

19、)，它们分别称为常量阶、线性阶和平方阶。第第2 2章章 线性数据结构线性数据结构 需要指出的是，有些算法的基本操作的频频度度不仅仅依赖于问题的规模n，还取决于它所处理的输入数据集的状态i，即T(n,i)。对于这一类算法，一般按每种情况发生的概率求出其数学期望值作为算法的平平均均时时间间复复杂杂度度，或者按最坏情况下基本操作的执行频度得出算法最最坏坏情情况况下下的的时时间间复复杂杂度度，以此作为该算法的时间复杂度。第第2 2章章 线性数据结构线性数据结构 (2) 空空间间复复杂杂度度。一个算法的实现所占用的存储空间大致有这样三个方面三个方面： 其其一一是指令、常数、变量所占用的存储空间； 其二其

20、二是输入数据所占用的存储空间； 其其三三是算法执行时必需的辅辅助助空空间间。前两种空间是计算机运行时所必须的。因此，把算法在执行时所需的辅辅助助空空间间的的大大小小作为分析算法空间复杂度的依据。第第2 2章章 线性数据结构线性数据结构 与算法时间复杂度的表示一致，也用辅助空间大小的数数量量级级来表示算法的空间复杂度，仍然记为：S(n)=O(f(n)。常见的几种空间复杂度有：O(1)，O(n)，O(n2)，O(n3)等。 事实上，一个问题的算法实现，时时间间复复杂杂度度和空空间间复复杂杂度度往往是相相互互矛矛盾盾的，要降低算法的执行时间就要以使用更多的空间为代价，要节省空间就可能要以增加算法的执行时间作为代价，两者很难兼顾。因此，只能根据具体情况有所侧重。