数据结构B 总学时:48理论学时:36上机学时:12 采用教材: 《数据结构-使用C语言》 陈一华等编 电子科技大学出版社
数据结构B 总学时: 48 理论学时：36 上机学时：12 采用 教材: 《数据结构----使用C语言》 陈一华等编 电子科技大学出版社
第一章绪论 1.1数据结构课程的形成和发展 什么是数据结构? 当前,计算机的应用已渗透到社会活动的各个领 域。在使用计算机的初期,其应用还局限于科学计算, 也就是大量用于数值计算。如果计算机仅只能用于数 值计算,恐怕其普及程度不会象今天这样广泛,计算 机应用领域的不断扩大,以至进入普通的百姓家庭, 是因为随着计算机硬件和软件技术的不断提高,而更 多地用于控制、管理及数据处理等非数值计算的领域, 与此相应,计算机加工处理的对象由纯粹的数值发展 到字符、表格、图象、声音等各种具有一定结构的数
第 一 章 绪 论 1 . 1 数据结构课程的形成和发展 什么是数据结构? 当前，计算机的应用已渗透到社会活动的各个领 域。在使用计算机的初期，其应用还局限于科学计算， 也就是大量用于数值计算。如果计算机仅只能用于数 值计算，恐怕其普及程度不会象今天这样广泛，计算 机应用领域的不断扩大，以至进入普通的百姓家庭， 是因为随着计算机硬件和软件技术的不断提高，而更 多地用于控制、管理及数据处理等非数值计算的领域， 与此相应，计算机加工处理的对象由纯粹的数值发展 到字符、表格、图象、声音等各种具有一定结构的数
据。为编出一个“好”的程序,必须分析待处理对象的 性及各待处理对象之间存在的关系。在这种背景下,就 形成了“数据结构”这门学科。 当用计算机解决一个具体问题时,一般要经过下面 几个步骤: 1根据需解决的具体问题抽象出一个适当的数学模 型,也称建模。 2设计一个适合于计算机执行的解此数学模型的算 法 3.根据算法,编写程序,并对所编程序进行调试 直至获得最终解答
据。为编出一个“好”的程序，必须分析待处理对象的 特 性及各待处理对象之间存在的关系。在这种背景下，就 形成了“数据结构”这门学科。 当用计算机解决一个具体问题时，一般要经过下面 几个步骤： 1 .根据需解决的具体问题抽象出一个适当的数学模 型，也称建模。 2 .设计一个适合于计算机执行的解此数学模型的算 法。 3 .根据算法， 编写程序， 并对所编程序进行调试 直至获得最终解答
在上述三个步骤中,建模是首要的也是关键的一步 其实质是分析问题,从中提取操作的对象,并找出这些 操作对象之间含有的关系,然后用数学语言加以描述。 在此,数学模型的这一含义已被扩充,所为数学模 型并非一定要用数学方程如线性方程组、微分方程等数 学解析式来表达,更多的非数值计算问题无法用数学方 程式来描述,需用其它方式加以描述,统称为数学模型 在数据结构这一学科中,常采用表、树、图等数学 模型来抽象需解决的具体问题,下面用三个例子加以说 明 例1图书馆的书目检索系统自动化问题
其实质是分析问题，从中提取操作的对象，并找出这些 操作对象之间含有的关系，然后用数学语言加以描述。 在此，数学模型的这一含义已被扩充，所为数学模 型并非一定要用数学方程如线性方程组、微分方程等数 学解析式来表达，更多的非数值计算问题无法用数学方 程式来描述，需用其它方式加以描述，统称为数学模型 在数据结构这一学科中，常采用表、树、图等数学 模型来抽象需解决的具体问题，下面用三个例子加以说 明。 例1. 图书馆的书目检索系统自动化问题。 在上述三个步骤中，建模是首要的也是关键的一步
001高等数学樊映川|S01 ■■■ 002理论力学罗远祥L01 003高等数学华罗庚S01 004线性代数栾汝书S02 高等数学001,003, 樊映川|001, 理论力学002, ■■ 「华罗庚003,- 线性代数_004, ■■■ 栾汝书004,· ■■■ L1002, ■■■ S001,003
001 高等数学 樊映川 S01 ┅ 002 理论力学 罗远祥 L01 ┅ 003 高等数学 华罗庚 S01 ┅ 004 线性代数 栾汝书 S02 ┅ ￤ ￤ ￤ ￤ ￤ 高等数学 001 ，003 ， ┅ 理论力学 002 ， ┅ 线性代数 004 ， ┅ ￤ ￤ 樊映川 001 ， ┅ 华罗庚 003 ， ┅ 栾汝书 004 ， ┅ ￤ ￤ L 002 ， ┅ S 001 ，003 ， ┅ ￤ ￤
在例1中,有四张二维表构成的文件是图书馆书目检索 系统自动化问题的数学模型,在这类问题中计算机处 理的对象之间通常存在着的是一种最简单的线性关系 这类数学模型可称作为线性的数据结构。 例2.大学的行政结构问题。 某大学 学院1 学院2- 学院N 系11系12 系21 系N1 专业A专业B 1班
在例1中，有四张二维表构成的文件是图书馆书目检索 系统自动化问题的数学模型，在这类问题中计算机处 理的对象之间通常存在着的是一种最简单的线性关系 这类数学模型可称作为线性的数据结构。 例2. 大学的行政结构问题。 某大学 学院1 学院2 ┅ ┅ 学院N ￤ 系11 系12 ┅ 系21 ┅ ┅ 系N1 ┅ 专业A 专业B ┅ 1班 ┅
例2的行政结构可用树型结构来表示,类似于例2的非 数值计算问题均可用称作为“树”的数学模型来表示, “树”也是一种数据结构。 例3.若干个地点间的交通问题 C A
例2的行政结构可用树型结构来表示，类似于例2的非 数值计算问题均可用称作为“树”的数学模型来表示， “树”也是一种数据结构。 例3. 若干个地点间的交通问题 B C D A E F G H I J K
例3表示的若干个地点间的交通问题所对应的数学模型 是一种称作为“图”的数据结构。 可见,描述上面三例的非数值计算问题的数学模 型不再是我们通常所熟悉的数学方程,而是诸如表、 树、图之类的数据结构。因此, 数据结构是一门研究非数值计算的程序设计问题 中计算机的操作对象以及它们之间的关系和操作等等 的学科。 1.2数据结构与算法 数据结构与算法是两个互相关联的问题,为了解 两者间的关系,必须先了解一些基本概念。 1.2.1基本概念和术语
是一种称作为“图”的数据结构。 可见，描述上面三例的非数值计算问题的数学模 型不再是我们通常所熟悉的数学方程，而是诸如表、 树、图之类的数据结构。因此， 数据结构是一门研究非数值计算的程序设计问题 中计算机的操作对象以及它们之间的关系和操作等等 的学科。 1 . 2 数据结构与算法 数据结构与算法是两个互相关联的问题，为了解 两者间的关系，必须先了解一些基本概念。 1 . 2 . 1 基本概念和术语 例3表示的若干个地点间的交通问题所对应的数学模型
数据(data):是客观事物的符号表示,在计算机科学 中是指所有能被计算机所接受并被计算机程序所处理的 符号的总称 数据的含义极为广泛.例如,一个用数值分析方法 解代数方程的程序,其处理的对像是实数;一个编译程 序或文字处理程序的处理对像是字符串;而图像、声音 等都可通过编码而归于数据的范畴 数据元素 data element):是组成数据的基本单位 数据元素在计算机程序中通常作为一个整体进行考 虑和处理.例如,一本书的书目信息作为一个数据元素 在数据库语言中,常被当作一条记录进行考虑和处理 个数据元素可由若干个数据项 data item)组成, 例如,书目信息中的每一项如书名、作者名、出版社等
数据(data): 是客观事物的符号表示, 在计算机科学 中是指所有能被计算机所接受并被计算机程序所处理的 符号的总称. 数据的含义极为广泛. 例如, 一个用数值分析方法 解代数方程的程序, 其处理的对像是实数; 一个编译程 序或文字处理程序的处理对像是字符串; 而图像、声音 等都可通过编码而归于数据的范畴. 数据元素(data element): 是组成数据的基本单位. 数据元素在计算机程序中通常作为一个整体进行考 虑和处理. 例如, 一本书的书目信息作为一个数据元素 在数据库语言中, 常被当作一条记录进行考虑和处理. 一个数据元素可由若干个数据项(data item)组成, 例如, 书目信息中的每一项如书名、作者名、出版社等
均为一个数据项 数据项( data item):是数据的不可分割的最小单位 数据对像( data object):是同一种数据类型(或称性质相 同)的数据元素的集合,是数据的一个子集 例如,整数数据对像是整数类型数据的集合,即 N={0,±1,±2,…},字母字符的数据对像是集合C=“A, B Z 数据结构( data structure):数据元素之间存在的相互关系 根据数据元素之间关系的不同特性,通常有下列四种基本 结构: (1)集合:结构中的数据元素之间除了“同属于一个集合”的 关系外,无其它关系.和数学中的集合概念一致 (2)线性结构:结构中的数据元素之间存在一个对一个的关 系 (3)树型结构:结构中的数据元素之间存在一对多的关系
均为一个数据项. 数据项(data item): 是数据的不可分割的最小单位. 数据对像(data object): 是同一种数据类型(或称性质相 同)的数据元素的集合, 是数据的一个子集. 例如, 整数数据对像是整数类型数据的集合, 即 N = 0,1,2, ,字母字符的数据对像是集合C={‘A’, ‘B’ ,…, ’Z’}. 数据结构(data structure): 数据元素之间存在的相互关系. 根据数据元素之间关系的不同特性, 通常有下列四种基本 结构: (1)集合: 结构中的数据元素之间除了“同属于一个集合”的 关系外, 无其它关系. 和数学中的集合概念一致. (2)线性结构: 结构中的数据元素之间存在一个对一个的关 系. (3)树型结构: 结构中的数据元素之间存在一对多的关系