《数据结构》第二版教材

所需积分/C币:44 2019-01-20 14:32:31 980KB PDF
收藏 收藏
举报

这是数据结构第二版(C语言版)的教材pdf文档,可供初学者学习,答疑解惑
数据结构 1.1学习数据结构的意义 数据结构是计算机软件和计算机应用专业的核心课程之一,在众多的计算机系统软件和 应用软件中都要用到数据结构。因此,仅掌握几种计算机语言难以应付众多复杂的课题,要 想有效地使用计算机,还必须学习数据结构的有关知识。 在计算机发展初期,人们使用计算机主要是处理数值计算问题,所涉及的运算对象一般 是整型、实型或逻辑型等一些简单的数据类型,因此,程序设计人员的主要精力集中于程序 设计的技巧上,而不是数据的组织和存储上。但随着计算机应用领域的不断扩大和软、硬件 的发展“非数值性问题”越来越显得重要。据统计,当今处理非数值型问题占用了%以 的杋器时间,如图书资料査询、电话号码的自动管珥、交通通道规划、博弈游戏等问题, 这类问题涉及到的数据结构更为复杂,数据元素之间的相互关系一般无法用数学方程式加以 描述。因此,解决此类问题的关键已不再是分析数学和计算方法,而是必须建立相应的数据 结构来进行描述,分析问题中所用到的数据是如何组织的,研究数据之间的关系如何,进而 改计处合适的数据结构,才能有效地解决问题。 【例】职工信息管理 个单位要对所有职工的基本情况进行管理,必须要经常了解职工的各种信息,包括经 常查询职工的编号、姓名、性别、以及月收入等情况,并对整个单位的情况作统计、汇总 工作。如何利用计算机来辅助管理这些信息呢?显然,应先考虑如何对整个单位每个职⊥的 信息进行有效的组织,并考虑如何将这些信息存入计算机中,利用计算杌进行有效的处理。 一般可以建立一个花名册对每位职工的信息进行编排,即组织这些信息如图所示, 花名册中每个职工的信息可由编号、姓名、性别、性别、年龄、月收入等项目组成,占表的 行。这时侯整个化名册就枃成了—个数据结构,或者称整个花名册就是一个数据结构,而 把表中的每一行看作一个结点或一个元素、一个记录,它由编号、姓名、性别、年龄、月收 入等项目组成,从而整张表构成了一个关于职工花名册的数学模型,此时的花名册就是一张 所谓的线性表,此时计算机就可以按某个特定要求对其进行操作。表中的结点和结点之间是 种简单的线性关系。表中有且仅有一个结点为表头(第一个结点),有且仅有一个结点为 表尾(最坏一个结点);对表中任一结点,与它相邻且在它前面的结点最多只有一个,这就 是上述花名册的逻辑结构。当考虑上述花名册表中的数据用计算札进行计算或处理时,就先 要涉及到这些结点如何在计算机中的存储表示的问题,也就是存储结构问题。对于这样的花 名册表,有可能是调入一些职工必须增加新的结点,而某些职工调离时又必须将这些相应结 点从表中删除掉。究竟如何进入插入、删除、修改、查找,这就是数据的运算问题,只有弄 清这些问题后,才能有效地使用花名册这个数据结构,有效地解决该单位职工基本信息的计 算札辅助管理的问题。 【例】电话号码查询问题 假定要编写·个某个城市或单位的私人电话号码。对任意给出的·个姓名,若该人有电话号 码,则要迅速地找到其电话号码;否则指岀该人没有电话号码。解决此问题首先要构造一张 电话号码登记表,表中每个结点存放两个数据项:姓名和电话号码。要写出好的査找算法, 取决于这张表的结构及存储方式。最简单的方法是将表中结点顺序地存储在计算机中,查找 时从头开始依次查对姓名,直到找出正确的姓名或是找遍整个表均没有找到为止。这种查找 数据结构 算法对于一个不大的单位或许是可行的,但对一个有成千上万私人电话的城市就不实用了 然而,若这张表是按姓氏排列的,则我们可以另造一张姓氏索引表,采用如图所示的存 储结构。那么査找过程是先在索引表中查对姓氏,然后根据索引表中的地址到电话号码登记 表中核查姓名,这样查找登记表就无须查找其它姓氏的名字了。因此,在这种新的结构上产 生的查找算法就更为有效。 鋁号姓名 桦别饴铃|月收入 张三 男 980 李四 女 28 之囗 王五 勇 34 赵六 男 43 950 图职工花名册表 姓名 电话号码 张三 姓氏地址 四 图电话号码查询问题的索引存储 【例1.3】教学计划编排问题 个教学计划包含许多课程,而在这些课程之间,有些又必须按规定的先后次序进行 而有些又没有次序要求。即有些课程之间有先修和后续的关系,如图所示。在有向图中 的每个顶点衣示门课程,如果从顶点到之间存在有向边< 则表示误程 必须先修于课程进行。 课程编号 课程名称 先修课程 计算机文化基础 无 数据结构 汇编语言 语言设计 计算机图形学 接口技术 数据库原理 编译原理 操作系统 ()计算机专业的课程设计 数据结构 C3 C1 TI ()表示课程之间优先关系的有向图 图教学计划编排问题的数据结构 由以上个例子可见,描述这类非数值计算问题的数学模型不在是数学方程,而是诸如 表、树、图之类的数据结构。这也是数据结构的研究对象,所以数据结构课程实际上是一门 硏究非数值计算问题的程序设计问题中所出现的计算机操作对象以及它们之间的关系和运 算操作等的一门学科 学习数据结构的目的是为了了解计算机处理对象的特性,将实际问题中所涉及的处理对 象在计算机中表小岀来并对它们进行处理。与此同时,通过算法训练来提高学生的思维能力, 通过稈序设计的技能训练来提高学生的综合应用能力和专业素质。 1.2数据结构的基本概念 数据() 数据是一切能被计算机识别、存储和加工处理的对象,是对客观事务的符号表示,是信 息的载体,也就是说数据是对有效地输入到计算机中并能被计算机程序处理的符号的总称 随着计算机技术的发展,数据这ˉ观念的含义越来越广泛,它既可以是像整数、实数、复数 这样的数值数据,又可以是像字符、文字、表格、图形、图像、声音这样的非数值数据。 数据元素( 数据元素是数据处理的基本单位,在计算机程序中要作为一个整体来考虑和处理。也就 是说,数据元素被认为是运算的基本单位,并且具有完整确定的实际意义。在不同条件下, 数据元素又可称为元素、顶点、记录等。例如上面职上花名册中的每个人的信息就是一个数 据元素。 数据项( 数据项是具有独立含义的标识单位,是数据不可分割的最小单位。例如将一个学生的整 体情况作为一个数据元素,而学生信息中的每一项如“学号”“姓名”“年龄”等作为一个 数据项。数据项有名和值之分,数据项名是·个数据项的名称标识,用变量来定义,而数据 项值这是它的可能取值。例如“张三”是数据项“姓名”的一个取值。数据项有一定的类型, 数据结构 它由数据项值来硝定。 数据对象( 数据对象是由只有相同性质的数据元素组成的集合。数据元素是数据对象的一个实例。 也称为数据元素类( )。在某个具体问题中,数据元素都具有相同的性质 (元素值不一定相等),属于同一数据对象,数据元素是数据对象的一个实例。例如,在教 学计划编排问题中,所有的课程是个数据对象,而课程和各自代表门具体的课程, 是该数据对象的两个实例,其数据元素的值分别为和 数据结构( 数据结构是指相互之间具有一定关系的数据元素的集合。在仟何问题中,数据元素之间 都不会是孤立的,在它们之间都存在着这样或那样的关系,这种数据元素之间的关系就称为 结构。 1.3数据结构的分类 硏究数据结构是指硏究数据的逻辑结构和物理结构。 数据的逻辑结构 数据的逻辑结构是指数据之间所有的内在关系,它可以看成是从只体问题中抽象出来 的数学模型,如数组中各元素的先后次序等 根据数据结构中各数据元素间逻辑关系的不同,可将数据结构分为以下三类: .线性结构 该结构中的数据元素之间存在着一对一的先后次序关系。 树形结构 该结构中的数据元素之间存在着一对多的关系 图形结构 该结构中的数据元素之间存在着多对多的关系,图形结构也称为网状结构 以上三种结构又叫分为线性结构和非线性结构两大类,其中树形结构和图肜结枃合称为 非线性结构。 数据的存储结构 数据的存储结构又称为物理结构,它是指数据数据及其关系在计算机存储器中的存储 式,是逻辑结构在计算杋中的具体实现,既包括存储数据本身的数据信息,也包括存储数据 之问的关系 数据元素在计算机中主要有以下四种不同的存储结构: 顺序存储( 该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点间的逻辑关系 由存储单元的邻接关系来体现。 链状存储( 该方法不要求逻辑上相邻的结点在物理位置上也相邻,也就是说数据元素可以存储在任 数据结构 意位置。当然,为了实现数据元素之间逻辑关系,就必须通过一些附加手段来实现这种相互 关系,般通过指针来实现 索引存储( 该方法通常在存储结点信息的同时,建立附加的索引表。索引表中由多个索引项组成, 索引项的一般形式为关键字、地址等。其中,关键字是指可唯一标识一个结点的数据项。 散列存储 该方法是依据结点的关键字直接计算出该结点的存储地址,而后将结点按某种方式存入 该地址的一种存储方法。 般说来,以上四种基本的存储方法,既可以单独使用,又可以组合起来使用。同一逻 辑结构采用不同的存储方法,也可以得到不同的存储结构。选择何种存储结构来存储表示相 应的逻辑结构就要视具体问题的要求而定。 4算法及其描述 算法( )是程序设计的精髓,程序设计的实质就是构造解决问题的算法。它 与数据结构的关系切,在算法设计时先要确定相应的数据结构,而在讨论数据结构时也必 然会涉及到相应的算法。算法的改计取决于数据的逻辑结构,算法的实现取决于数据的物理 结构。著名的瑞士计算机科学家 所提出的公式:算法十数据结构一程序,就深刻揭 示了算法和数据结构之间的关系。对实际问题选择了一和好的数据结构之后,还得有一个好 的算法,才可更好地求解问题 1.4.1算法的特性 算法是指在冇限的时间范围内,为解决某一问题而采取的方法和步骤的准确完整的描 述,它是个有穷的规则序列,这些规则决定了解决某特定问题的·系列运算。 一个算法应该具备以下特征: 有穷性 个算法应包含有限个操作步骤。即一个算法在执行若干个操作步骤之后应该能够结 束,并且每一步都要在合理时间内完成。 .确定性 算法中的每一个步骤必须有确切的含义,无二义性,在任何情况下,对」相同的输入只 能得出相同的输出。 可行性 算法中的炣一个步骤都应该是能够通过已经实现的基本运算的有限次执行得以实现 输入 输入指的是在算法执行时,从外界取得必要的数据。一个算法可以有一个或一个以上的 输入,也可以没有输入。 .输出 数据结构 输出指的是算法对输入数据处理后的结果。一个算法可以有一个或一个以上的输出,没 有输出的算法是无意义的。 算法的含义与程序非常相似,但又有区别。一个程序不一定满足有穷性。另一方面,程 序中的指令必须是机器可执行的,而算法中的指令则无此限制。算法代表了对问题的解,而 稈序则是算法在计算机上的特定实现。一个算法若用程序设计语言来描述,就成为一个程序 要设计一个好的算法,除了满足以上五个条件外通常还有考虑以下几个方面 正确。算法的执行结果应该满足预先规定的功能和性能的要求。 可读。一个算法应该思路清晰、结构清楚、简单易慬。 健壮。当接收到不合法输入时,算法应有适当的处理机制,以避免造成严重后果 高效。在解决问题的前提下,算法应该有效地使用存储空间,且有较高的时间效率, 1.4.2算法的描述 为了措述一个算法,可以有多种不同的表示方法。例如有自然语言表示法、流稈图、 图、类高级程序设计语言,也可以直接使用某种高级语言来描述。 自然语言 用自然语言来描述算法,其优点是简单且便于人们对算法的阅读,但这种方法不够严谨, 容易产生歧义性。对于大型的复杂算法,用自然语言很难清楚、准确地描述出来 流程图 流程图是算法的图形描述工具,它是用一些几何图形表示各种类型的操作。美国国家标 准化协会规定了些常用的流程图符号,如图所示。 图流程图符号 图袤小程序的开始或结束;佟表小程序的输入或输出操作;图表小条件 选择,有一个入口,两个出口以供选择;图表示稈序中的处理功能,框内可注明銜要 功能;图表示子程序、子模块等;图中的直线表示控制流,箭头表示流程的方向 图是流程图间断处的连接符号。 流程图独立于仼何一种程序设计语言,它具有直观、清晰、易」掌握的特点,由丁其 中的转冋过于任意,带来了许多副作用,现已趋向消亡。 图 1973年,美国学者Nas和 Shneiderman提出了一种符合结构化程序设计原则的 数据结构 图形描述工具N-S图,它完全除去了流程图中容易出问题的流程线,全部算法写在一个 矩形框内,在该框内可以包含其他从属于它的框。 N-S图中规定了五种基本图形构件,如图1.5所小。 图1.5a为顺序型,表示按顺序先执行A操作,再执行B操作;图1.5b为选择型, 表示若条件P成立,执行A操作,否则执行B操作;图1.5c为多分支选择型,P为控 制条件,根据P的取值,相应地执行其值所对应的操作;图1.5d为当型循环,先判断 循环控制条件P的取值,再决定是否执行S;图1.5e为直到型循环,先执行S,再判 断循环控制条件P的取值。 成立 直到成立 图15N-S图基本格式 类高级程序设计语言 用流稈图或图描述算法,是为了满足人们阅读和交流算法的需要,一个真正能在 计算机上运行的算法,必须要严格地按照某和编程语言的语法规则来编写 本书采用类高级语言米描述算法。类高级语言与程序设计语言类似,它包括髙级程序设 计语言中的基木语法成分,但忽略了高级程序设计语言中的一些严格的话法規则与描述细 节,因此它比高级程序设计语言吏容易描述和被人理解。用类高级语言描述的算法,虽不能 在计算机上直接运行,但简单清晰,不拘泥于髙级程序设计语言的细节,容易编写和阅读。 冋时经过简单的修改,就可以在计算机上运行。因此,用这种方法来措述算法是比较合适的, 在数据结构的算法描述中被广泛应用 木书将采用类语言来描述算法,它是标准语言的简化。 1.5算法评价 般地,求解同问题往往有多种不同的算法,这就产生了如何评价算法优劣的问题 通过对算法的评价,一方血可以从解决同一问趣的不冋算法中区分相对优劣,选择较为合适 的一种,一方面也有助于设计人员考虑对现有算法进行改进或设计出新的算法。 数据结构 1.5.1算法评价的一般原则 要设计一个“好”的算法,首先要保证选用的算法是正确的,除此以外,还应考虑如卜 几个方面: 执行该算法所耗费的时间。 执行该算法所耗费的存储空间,其中上要考虑辅助存储空间。 该算法应便于理解,易于编码、调试等。 当然我们希望选择一个所占存储空间小、运行时间短、其他性能也好的算法。但在实际 没计中,上述要求往往是相互矛盾的,要节约算法的执行时间经常要以牺牲更多的存储空间 为代价;而为了节约算法所占的存储空间又可能以更多的执行时间为代价。因此必须根据实 际问题出发,根据具体情況而有所侧重 另外,要将一个算法转换成程序并在计算机上执行,其运行所需要的时间还取决于下列 因素 计算机哽件的速度。 书写程序的高级语言。实现语言的级别越高,其执行效率就越低。 问题的规模。例如,求的阶乘和求的阶乘所需要的执行时间当然是不同的 因此,根据算法的绝对执行时间米评价算法的优劣是不合适的。为此,可以将上述各种 与计算杋相关的软、硬件因素都桷定下来,这样个特定算法的运行L作量的大小就只依赖 于问趣的规模(通常用正整数来表小),或者说它是问题规模的函数。 1.5.2算法复杂性分析 评价一个算法优劣的重要依据是看这个算法执行需要占用多少机器资源。而在各种机尜 资源中,时间和空间是两个最主要的方面。因此,在进行算法评价时,人们最关心的就是该 算法在运行时所要耗费的时间代价和算法中数据结构所占用的空间代价。在这里我们分别称 为时间复杂性(所需运行时间)和空间复杂性(所占存储空间)。 时间复杂性( 个程序的时间复杂性是指程序从开始到结束所需要的时间 个算法所需的运算时间通常与所解决问题的规模人小有关。通常,我们用作为表示 问题规模的量。例如,树的问题中是树的顶点数;排序问题中为所需排序元素的个数等 我们经常把算法运行所需的时间表示为的函数,记为 大部分情况下要准确地计算是很困难的,我们往往研究所谓的“渐进吋间复杂性”, 即当逐渐増大时的极限情况。一般把这种算法的渐进复杂性简称为时间复杂性。为了 便于分析,时间复杂性常用数量级的形式来表示,记为 。其中人写字母为 (数量级)的第一个字母,为函数形式,如 用数量级的形式表示,当为多项式时,可只取其最高次幂,且其系数也可省略。 如

...展开详情
试读 127P 《数据结构》第二版教材
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    一个资源只可评论一次,评论内容不能少于5个字
    再见柳成荫 连个封面都没……我想要刘大有版本的,这……
    2020-07-11
    回复
    HiterLeo 比较清楚的pdf版本 不过发现这本书好薄啊 才将近两百页2333
    2020-02-24
    回复
    上传资源赚积分,得勋章
    最新推荐
    《数据结构》第二版教材 44积分/C币 立即下载
    1/127
    《数据结构》第二版教材第1页
    《数据结构》第二版教材第2页
    《数据结构》第二版教材第3页
    《数据结构》第二版教材第4页
    《数据结构》第二版教材第5页
    《数据结构》第二版教材第6页
    《数据结构》第二版教材第7页
    《数据结构》第二版教材第8页
    《数据结构》第二版教材第9页
    《数据结构》第二版教材第10页
    《数据结构》第二版教材第11页
    《数据结构》第二版教材第12页
    《数据结构》第二版教材第13页
    《数据结构》第二版教材第14页
    《数据结构》第二版教材第15页
    《数据结构》第二版教材第16页
    《数据结构》第二版教材第17页
    《数据结构》第二版教材第18页
    《数据结构》第二版教材第19页
    《数据结构》第二版教材第20页

    试读已结束,剩余107页未读...

    44积分/C币 立即下载 >