数据结构(C语言版)第二版

所需积分/C币:46 2018-12-16 18:22:19 38.58MB PDF
141
收藏 收藏
举报

数据结构 C语言版 第二版 电子书,非常适合新手使用。 早期的计算机主要用于数值计算,现在,计算机主要用于非数值计算,包括处理字符、表格和图像等具有一定结构的数据。这些数据内容存在着某种联系,只有分清楚数据的内在联系,合理地组织数据,才能对它们进行有效的处理,设计出高效的算法。
第】章 绪论 早期的计算机主要用于数值计算,现在,计算机主要用于非数值计算,包括处理字符、表格 和图像等具有一定结构的数据。这些数据内容存在着某种联系,只有分清楚数据的内在联系,合 理地组织数据,才能对它们进行有效的处理,设计出高效的算法。如何合理地组织数据、高效地 处理数据,这就是“数据结构”主要研究的问题。本章简要介绍有关数据结构的基本概念和算法 分析方法。 11数据结构的研究内容 计算机主要用于数值计算时,一般要经过如下几个步骤:首先从具体问题抽象出数学模型 然后设计一个解此数学模型的算法,最后编写程序,进行测试、调试,直到解决问题。在此过程 中寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间的关系,然 后用数学语言加以描述,即建立相应的数学方程。例如,用计算机进行全球天气预报时,就需要 求解一组球面坐标系下的二阶椭圆偏微分方程;预测人口增长情况的数学模型为常微分方程。求 解这些数学方程的算法是计算数学研究的范畴,如高斯消元法、差分法、有限元法等算法。数据 结构主要研究非数值计算问题,非数值计算问题无法用数学方程建立数学模型,下面通过三个实 例加以说明 【例1.1】学生学籍管理系统。 高等院校教务处使用计算机对全校的学生情况作统一管理。学生的基本信息,包括学生的学 号、姓名、性别、籍贯、专业等,如表1.1所示。每个学生的基本情况按照不同的顺序号,依次 存放在“学生基本信息表”中,根据需要对这张表进行查找。每个学生的基本信息记录按顺序号 排列,形成了学生基本信息记录的线性序列,呈一种线性关系。 表1.1 学生基本信息表 学号 姓名 性别 籍贯 专业 060214201 杨阳 男 安徽 计算机科学与技术 060214202 薛林 男 福建 计算机科学与技术 060214215 王诗萌 女 吉林 计算机科学与技术 060214216 冯子晗 女 山东 计算机科学与技术 诸如此类的线性表结构还有图书馆的书目管理系统、库存管理系统等。在这类问题中,计算 数据结构(C语言版)(第2版) 机处理的对象是各种表,元素之间存在简单一对一的线性关系,因此这类问题的数学模型就是各 种线性表,施加于对象上的操作有查找、插入和删除等。这类数学模型称为“线性”的数据结构。 【例12】人机对弈问题。 计算机之所以能和人对弈是因为已经将对弈的策略在计算机中存储好。由于对弈的过程是在 定规则下随机进行的,所以,为使计算机能灵活对弈,就必须把对弈过程中所有可能发生的情 况及相应的对策都加以考虑。以最简单的井字棋为例,初始状态是一个空的棋盘格局。对弈开始 后,每下一步棋,则构成一个新的棋盘格局,且相对于上一个棋盘格局的可能选择可以有多种形 式,因而整个对弈过程就如同图1.1所示的“一棵倒长的树”。在这棵“树”中,从初始状态(根) 到某一最终格局(叶子)的一条路径,就是一次具体的对弈过程。 人机对弈问题的数学模型就是如何用树结构表示棋盘和棋子等,算法是博弈的规则和策略。 诸如此类的树结构还有计算机的文件系统、一个单位的组织机构等。在这类问题中,计算机处理 的对象是树结构,元素之间是一对多的层次关系,施加于对象上的操作有查找、插入和删除等。 这类数学模型称为“树”的数据结构。 【例1.3】最短路径问题。 从城市A到城市B有多条线路,但每条线路的交通费不同,那么,如何选择一条线路,使得 从城市A到城市B的交通费用最少呢?解决的方法是,可以把这类问题抽象为图的最短路径问 题。如图1.2所示,图中的顶点代表城市,有向边代表两个城市之间的通路,边上的权值代表两 个城市之间的交通费。求解A到B的最少交通费用,就是要在有向图中A点(源点)到达B点 (终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。 区 60 30 20 幽 图1.1井字棋的对弈树 图1.2最短路径问题 彐第1章绪论 最短路径问题的数学模型就是图结构,算法是求解两点之间的最短路径。诸如此类的图结构 还有网络工程图和网络通信图等,在这类问题中,元素之间是多对多的网状关系,施加于对象上 的操作依然有查找、插入和删除等。这类数学模型称为“图”的数据结构。 从上面三个实例可以看出,非数值计算问题的数学模型不再是数学方程,而是诸如线性表 树和图的数据结构。因此,简单地说,数据结构是一门研究非数值计算程序设计中的操作对象, 以及这些对象之间的关系和操作的学科。 20世纪60年代初期,“数据结构”有关的内容散见于操作系统、编译原理等课程中。1968 年,“数据结构”作为一门独立的课程被列人美国一些大学计算机科学系的教学计划,同年,著名 计算机科学家D. E. Knuth教授发表了《计算机程序设计艺术》第一卷《基本算法》。这是第一本较 系统地阐述“数据结构”基本内容的著作。之后,随着大型程序和大规模文件系统的出现,结构化 程序设计成为程序设计方法学的主要研究方向,人们普遍认为程序设计的实质就是对所处理的问题选 择一种好的数据结构,并在此结构基础上施加一种好的算法,著名科学家 Wirth教授的《算法+数据 结构=程序》正是这种观点的集中体现。 目前,数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算 机硬件(特别是编码理论、存储装置和存取方法等)的硏究范围,而且和计算机软件的硏究有着 密切的关系,无论是编译程序还是操作系统都涉及数据元素在存储器中的分配问题。在研究信息 检索时也必须考虑如何组织数据,以使查找和存取数据元素更为方便。因此,可以认为数据结构 是介于数学、计算机硬件和软件三者之间的一门核心课程。 有关“数据结构”的研究仍不断发展,一方面,面向各专门领域中特殊问题的数据结构正在 研究和发展;另一方面,从抽象数据类型的观点来讨论数据结构,已成为一种新的趋势,越来越 被人们所重视。 1.2基本概念和术语 下列概念和术语将在以后各章节中多次出现,本节先对这些概念和术语赋予确定的含义。 121数据、数据元素、数据项和数据对象 数据(Data)是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号 的总称。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、 图像、声音及动画等通过特殊编码定义后的数据。 数据元素( Data element)是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。 在有些情况下,数据元素也称为元素、记录等。数据元素用于完整地描述一个对象,如前一节示 例中的一名学生记录,树中棋盘的一个格局(状态),以及图中的一个顶点等。 数据项( Data Item)是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生 基本信息表中的学号、姓名、性别等都是数据项。 数据对象( Data Object)是性质相同的数据元素的集合,是数据的一个子集。例如:整数数 据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={A’,B',…,Z',a',“b’,…, z”},学生基本信息表也可以是一个数据对象。由此可以看出,不论数据元素集合是无限集(如 整数集),或是有限集(如字母字符集),还是由多个数据项组成的复合数据元素(如学生表)的 二数据结构(C语言版)(第2版)三 集合,只要集合内元素的性质均相同,都可称之为一个数据对象。 12.2数据结构 数据结构( Data structure)是相互之间存在一种或多种特定关系的数据元素的集合。换句话 说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 数据结构包括逻辑结构和存储结构两个层次。 1.逻辑结构 数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此, 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据的逻辑结构有两个要素:一是数据元素;二是关系。数据元素的含义如前所述,关系是 指数据元素间的逻辑关系。根据数据元素之间关系的不同特性,通常有四类基本结构,如图1.3 所示。它们的复杂程度依次递进 集合结构 线性结构 o 树结构 图结构 图1.3四类基本逻辑结构关系图 下面四种结构中所举的示例是以某班级学生作为数据对象(数据元素是学生的学籍档案记 录),来分别考察数据元素之间的关系。 (1)集合结构 数据元素之间除了“属于同一集合”的关系外,别无其他关系。例如,确定一名学生是否为 班级成员,只需将班级看做一个集合结构。 (2)线性结构 数据元素之间存在一对一的关系。例如,将学生信息数据按照其入学报到的时间先后顺序进 行排列,将组成一个线性结构。 (3)树结构 数据元素之间存在一对多的关系。例如,在班级的管理体系中,班长管理多个组长,每位组 长管理多名组员,从而构成树形结构。 (4)图结构或网状结构 数据元素之间存在多对多的关系。例如,多位同学之间的朋友关系,任何两位同学都可以是 朋友,从而构成图状结构或网状结构。 其中集合结构、树结构和图结构都属于非线性结构。 线性结构包括线性表(典型的线性结构,如例1.1中的学生基本信息表)、栈和队列(具有特 第1章绪论 殊限制的线性表,数据操作只能在表的一端或两端进行)、字符串(也是特殊的线性表,其特殊性 表现在它的数据元素仅由一个字符组成)、数组(是线性表的推广,它的数据元素是一个线性表) 广义表(也是线性表的推广,它的数据元素是一个线性表,但不同构,即或者是单元素,或者是 线性表)非线性结构包括树(具有多个分支的层次结构)和二叉树(具有两个分支的层次结构) 有向图(一种图结构,边是顶点的有序对)和无向图(另一种图结构,边是顶点的无序对)。这几 种逻辑结构可以用一个层次图描述,如图1.4所示。 数据的逻辑结构 线性结构 非线性结构 线性表 树结构 图结构 一般线性表特殊线性表线性表的推广 树二叉树有向图无向图 线性表栈与队列字符串数组广义表 图14几种逻辑结构层次图 2.存储结构 数据对象在计算机中的存储表示称为数据的存储结构,也称为物理结构。把数据对象存储到 计算机时,通常要求既要存储各数据元素的数据,又要存储数据元素之间的逻辑关系,数据元素 在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构,分别是顺序存储结 构和链式存储结构。 (1)顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,通常借助 程序设计语言的数组类型来描述。 对于前面的“学生基本信息表”,假定每个结点(学生记录)占用50个存储单元,数据从0 号单元开始由低地址向高地址方向存储,对应的顺序存储结构如表12所示。 表12 顺序存储结构 地址 学号 姓名 性别 籍贯 专业 060214201 杨阳 安徽 计算机科学与技术 50 060214202 薛林 100 060214215 王诗萌 男男女女 福建 计算机科学与技术 吉林 计算机科学与技术 150 060214216 冯子晗 山东 计算机科学与技术 (2)链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中,而链式存储结构,无需占 用一整块存储空间。但为了表示结点之间的关系,需要给每个结点附加指针字段,用于存放后继 元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。 假定给前面的“学生基本信息表”中的每个结点附加一个“下一个结点地址”,即后继指针字 数据结构(C语言版)(第2版 段,用于存放后继结点的首地址,则可得到如表1.3所示的链式存储结构。从表中可以看出,每 个结点占用两个连续的存储单元,一个存放结点的信息,另一个存放后继结点的首地址。 表1.3 链式存储结构 地址 学号 姓名 性别 籍贯 专业 后继结点的首地址 0 060214201 杨阳 安徽计算机科学与技术 100 50 060214216 冯子晗 山东计算机科学与技术 100 060214202 薛林 男女男女 福建 计算机科学与技术 150 150 060214215 王诗萌 吉林计算机科学与技术 50 为了更清楚地反映链式存储结构,可采用更直观的图示来表示,如“学生基本信息表”的链 式存储结构可用如图1.5所示的方式表示。 060214201 060214202 060214215 060214216 杨阳 薛林 王诗萌 冯子晗 男 男 女 女 安徽 福建 吉林 山东 计算机科学与技术 计算机科学与技术 计算机科学与技术 计算机科学与技术 图1.5链式存储结构示意图 12.3数据类型和抽象数据类型 1.数据类型 数据类型( Data Type)是高级程序设计语言中的一个基本概念,前面提到过顺序存储结构可 以借助程序设计语言的数组类型描述,链式存储结构可以借助指针类型描述,所以数据类型和数 据结构的概念密切相关。 一方面,在程序设计语言中,每一个数据都属于某种数据类型。类型明显或隐含地规定了数 据的取值范围、存储方式以及允许进行的运算,数据类型是一个值的集合和定义在这个值集上的 组操作的总称。例如,C语言中的整型变量,其值集为某个区间上的整数(区间大小依赖于不 同的机器),定义在其上的操作为加、减、乘、除和取模等算术运算;而实型变量也有自己的取值 范围和相应运算,比如取模运算是不能用于实型变量的。程序设计语言允许用户直接使用的数据 类型由具体语言决定,数据类型反映了程序设计语言的数据描述和处理能力。C语言除了提供整 型、实型、字符型等基本类型数据外,还允许用户自定义各种类型数据,例如数组、结构体和指 针等。 2.抽象数据类型 抽象就是抽取出实际问题的本质。在计算机中使用二进制数来表示数据,在汇编语言中则可 给出各种数据的十进制表示,它们是二进制数据的抽象,使用者在编程时可以直接使用,不必考 虑实现细节。在高级语言中,则给出更高一级的数据抽象,出现了数据类型,如整型、实型、字 符型等,可以进一步利用这些类型构造出线性表、栈、队列、树、图等复杂的抽象数据类型。 抽象数据类型( Abstract Data Type,ADT)一般指由用户定义的、表示应用问题的数学模型 6 第1章绪论 以及定义在这个模型上的一组操作的总称,具体包括三部分:数据对象、数据对象上关系的集合 以及对数据对象的基本操作的集合。 抽象数据类型的定义格式如下: ADT抽象数据类型名{ 数据对象:〈数据对象的定义〉 数据关系:〈数据关系的定义〉 基本操作:〈基本操作的定义 }ADT抽象数据类型名 其中,数据对象和数据关系的定义采用数学符号和自然语言描述,基本操作的定义格式为 基本操作名(参数表) 初始条件:〈初始条件描述〉 操作结果:〈操作结果描述〉 基本操作有两种参数:赋值参数只为操作提供输人值;引用参数以“&”打头,除可提供输 人值外,还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件,若 初始条件为空,则省略。“操作结果”说明了操作正常完成之后,数据结构的变化状况和应返回的 结果。 13抽象数据类型的表示与实现 运用抽象数据类型描述数据结构,有助于在设计一个软件系统时,不必首先考虑其中包含的 数据对象,以及操作在不同处理器中的表示和实现细节,而是在构成软件系统的每个相对独立的 模块上定义一组数据和相应的操作,把这些数据的表示和操作细节留在模块内部解决,在更高的 层次上进行软件的分析和设计,从而提高软件的整体性能和利用率。 抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现,将数 据和操作封装在一起,使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据 从而实现了信息隐藏。在C++中,我们可以用类的声明表示抽象数据类型,用类的实现来实现 抽象数据类型。因此,C++中实现的类相当于数据的存储结构及其在存储结构上实现的对数据 的操作。 抽象数据类型和类的概念实际上反映了程序或软件设计的两层抽象:抽象数据类型相当于在 概念层(或称为抽象层)上描述问题,而类相当于在实现层上描述问题。此外,C++中的类只是 个由用户定义的普通类型,可用它来定义变量(称为对象或类的实例)。因此,在C++中,最 终是通过操作对象来解决实际问题的,所以我们可将该层次看做是应用层。例如,main程序就可 看做是用户的应用程序。 由此可以看出,最终表示和实现抽象数据类型,最好用面向对象的方法,比如用C++语言的 类描述比较方便、有效,但本课程大都在大学低年级开设,用C语言的描述方法更符合学生的实 际情况。另外,由于实际问题千变万化,数据模型和算法也形形色色,因此抽象数据类型的设计 和实现,就不可能像基本数据类型那样规范和一劳永逸。本书所讨论的数据结构及其算法主要是 面向读者的,故采用介于伪码和C语言之间的类C语言作为描述工具。这使得数据结构与算法的 数据结构(C语言版)(第2版 描述与讨论简明清晰,不拘泥于C语言的细节,又容易转换成C或C++程序。 夲书采用的类C语言精选了C语言的一个核心子集,同时做了若干扩充修改,增强了语言的 描述功能,以下对其做简要说明 (1)预定义常量及类型: //函数结果状态代码 #define oK 1 #define error 0 #define OVERFLOW -2 / Status是函数返回值类型,其值是函数结果状态代码。 typedef int status; (2)数据结构的表示(存储结构)用类型定义( typedef)描述;数据元素类型约定为 ElemType, 由用户在使用该数据类型时自行定义。 (3)基本操作的算法都用如下格式的函数来描述 函数类型函数名(函数参数表 //算法说明 语句序列 }//函数名 当函数返回值为函数结果状态代码时,函数定义为 Status类型。为了便于描述算法,除了值 调用方式外,增加了C++语言引用调用的参数传递方式。在形参表中,以“&”打头的参数即为 引用参数。传递引用给函数与传递指针的效果是一样的,形参变化实参也发生变化,但引用使用 起来比指针更加方便、高效。 4)内存的动态分配与释放。 使用new和 delete动态分配和释放内存空间 分配空间指针变量=new数据类型; 释放空间 delete指针变量; (5)赋值语句 简单赋值变量名=表达式; 串联赋值变量名1=变量名2==变量名n=表达式; 成组赋值(变量名1,,,变量名n)=(表达式1,,表达式n) 结构赋值结构名1=结构名2; 结构名=(值1,值2,.,值n); 条件赋值变量名=条件表达式?表达式T:表达式F; 交换赋值变量名1<-->变量名2; (6)选择语句: 条件语句1if(表达式)语句 条件语句2if(表达式)语句; else语句 开关语句 switch(表达式) case值1:语句序列1; break; case值2:语句序列2; break; 8

...展开详情
试读 127P 数据结构(C语言版)第二版
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
世上我最好123 这个资源不错,挺好的!
2020-12-22
回复
ldx19670128 严版数据结构, 大家注意,按需求下载。内容不错的,就是网上其它地方有免费的
2020-02-12
回复
  • GitHub

    绑定GitHub第三方账户获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    数据结构(C语言版)第二版 46积分/C币 立即下载
    1/127
    数据结构(C语言版)第二版第1页
    数据结构(C语言版)第二版第2页
    数据结构(C语言版)第二版第3页
    数据结构(C语言版)第二版第4页
    数据结构(C语言版)第二版第5页
    数据结构(C语言版)第二版第6页
    数据结构(C语言版)第二版第7页
    数据结构(C语言版)第二版第8页
    数据结构(C语言版)第二版第9页
    数据结构(C语言版)第二版第10页
    数据结构(C语言版)第二版第11页
    数据结构(C语言版)第二版第12页
    数据结构(C语言版)第二版第13页
    数据结构(C语言版)第二版第14页
    数据结构(C语言版)第二版第15页
    数据结构(C语言版)第二版第16页
    数据结构(C语言版)第二版第17页
    数据结构(C语言版)第二版第18页
    数据结构(C语言版)第二版第19页
    数据结构(C语言版)第二版第20页

    试读结束, 可继续阅读

    46积分/C币 立即下载 >