NI 19217 授课教师: 联络电话: Email
授课教师： 联络电话： Email:
数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实 际问题时,就要涉及到数据的表示及数据的处理,而数据表示及数据处理正是数据结构 课程的主要研究对象,通过这两方面内容的学习,为后续课程,特别是软件方面的课程 扌打下了厚实的知识基础,同时也提供了必要的技能训练。因此,数据结构课程在计算机 应用专业中具有举足轻重的作用 本课程的任务是:在基础方面,要求学生掌握常用数据结构 的基本概念及其不同的实现方法:在技能方面,通过系统 学习在不同存储结构上现不的算,对算法度 计的方式和技巧有所体会 ◆学业基础:本课程的先修课程为离散数学和高级语」 言程序设计。学习本课程必须具备高级语言程序设计 比如 Pascal语言或C语言)的基础知识与基本技能。它 的后续课程有操作系统和数据库原理等。 ◆进度安排:总学时108,其中课堂讲授72学时,实 验教学36学时。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实 际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构 课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程 打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机 应用专业中具有举足轻重的作用。 本课程的任务是： 在基础方面，要求学生掌握常用数据结构 的基本概念及其不同的实现方法；在技能方面，通过系统 学习能够在不同存储结构上实现不同的运算，并对算法设 计的方式和技巧有所体会。 学业基础：本课程的先修课程为离散数学和高级语 言程序设计。学习本课程必须具备高级语言程序设计 (比如Pascal语言或C语言)的基础知识与基本技能。它 的后续课程有操作系统和数据库原理等。 进度安排：总学时108，其中课堂讲授72学时，实 验教学36学时
第一章绪论 1教学内容:11数据结构的概念 1.2抽象数据类型 1.3算法和算法分析。 2教学目的:(1领会数据、数据元素和数据项的概念及其相互间的关系 (②清楚数据结构的逻辑结构、存储结构的联系与区别,以及在数据结构上施加的运算及其实现 (3)理解抽象数据类型的概念; (4)掌握进行简单算法分析的方法 3.教学重点:(①)数据、数据元素、数据项: (2)逻辑结构和数据结构在概念上的联系与区别 (3)存储结构及其三个组成部分 4)抽象数据类型和数据抽象 (5)评价算法优劣的标准及方法 4.教学难点:(区别算法与程序 (2)逻辑结构、存储结构的联系与区别; (3)抽象数据类型与数据抽象; (4)算法的时间复杂度分析。 5学时安排:3学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 3 ⒈教学内容：1.1 数据结构的概念； 1.2 抽象数据类型； 1.3 算法和算法分析。 ⒉教学目的：⑴领会数据、数据元素和数据项的概念及其相互间的关系； ⑵清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现； ⑶理解抽象数据类型的概念； ⑷掌握进行简单算法分析的方法。 ⒊教学重点：⑴数据、数据元素、数据项； ⑵逻辑结构和数据结构在概念上的联系与区别； ⑶存储结构及其三个组成部分； ⑷抽象数据类型和数据抽象； ⑸评价算法优劣的标准及方法。 ⒋教学难点：⑴区别算法与程序； ⑵逻辑结构、存储结构的联系与区别； ⑶抽象数据类型与数据抽象； ⑷算法的时间复杂度分析。 ⒌学时安排： 3学时 第一章 绪论
11数据结构的概念 为什么要学习数据结构 有关概念和术语 数据结构课程的内容 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 4 1.1 数据结构的概念 为什么要学习数据结构 有关概念和术语 数据结构课程的内容
1.1.1为什么要学习数据结构 在计算机发展的初期,人们使用计算机的目的主要是处理数值计算问题。当我们 使用计算机来解决一个具体问题时,一般需要经过下列几个步骤:首先要从该具体问 题抽象出一个适当的数学模型,然后设计或选择一个解此数学模型的算法,最后编出 程序进行调试、测试,直至得到最终的解答。例如,求解梁架结构中应力的数学模型 的线性方程组,该方程组可以使用迭代算法来求解。 由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据,所以程序设计 者的主要精力是集中于程序设计的技巧上,而无须重视数据结构。随着计算机应用领 域的扩大和软、硬件的发展,非数值计算问题越来越显得重要。据统计,当今处理非 数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂, 数据元素之间的相互关系一般无法用数学方程式加以描述。因此,解决这类问题的关 键不再是数学分析和计算方法,而是要设计出合适的数据结构,才能有效地解决问题。 例1 例2 例3 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 1.1.1 为什么要学习数据结构 在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们 使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问 题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出 程序进行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型 的线性方程组，该方程组可以使用迭代算法来求解。 由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计 者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领 域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非 数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂， 数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关 键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。 例1 例2 例3
例1学生信息检索系统 当我们需要查找某个学生的有关情况 的时候:或者想查询某个专业或年级的学 记录号学号姓名性别专业 年级 980001吴承志男计算机科学与技术98级 生的有关情况的时候,只要我们建立了相 298000李淑芳女信息与计算科学98级 39901刘丽女数学与应用数学99级 关的数据结构,按照某种算法编写了相关 49902张会友男信息与计算科学99级 程序,就可以实现计算机自动检索。由此 5990303石宝国男计算机科学与技术99级 6000801何文颖女计算机科学与技术200级 可以在学生信息检索系统中建立一张按学 7000802赵胜利男数学与应用数学2000级 号顺序排列的学生信息表和分别按姓名、 800803崔文靖男信息与计算科学200级 9010601刘丽女计算机科学与技术2001级 专业、年级顺序排列的索引表,由这四张 10010602魏永鸣男数学与应用数学2001级 (a)学生信息表 表构成的文件便是学生信息检索的数学模 型,计算机的主要操作便是按照某个特定 崔文靖8 计算机科学与技术1,5,6,9 信息与计算科学2,4,8 要求(如给定姓名)对学生信息文件进行 李淑芳 2 数学与应用数学 3,7,10 查询 刘 (c)专业索引表 石宝国 魏永鸣 6,7,8 10 赵胜利 1,2,3 张会有 99级 4,5 (b)姓名索引表 (d)年级索引表 图1.1学生信息查询系统中的数据结构 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 例1 学生信息检索系统 当我们需要查找某个学生的有关情况 的时候；或者想查询某个专业或年级的学 生的有关情况的时候，只要我们建立了相 关的数据结构，按照某种算法编写了相关 程序，就可以实现计算机自动检索。由此， 可以在学生信息检索系统中建立一张按学 号顺序排列的学生信息表和分别按姓名、 专业、年级顺序排列的索引表，由这四张 表构成的文件便是学生信息检索的数学模 型，计算机的主要操作便是按照某个特定 要求（如给定姓名）对学生信息文件进行 查询。 （b）姓名索引表 崔文靖 8 何文颖 6 李淑芳 2 刘 丽 3，9 石宝国 5 魏永鸣 10 吴承志 1 赵胜利 7 张会有 4 2000级 6，7，8 2001级 9，10 98级 1，2，3 99级 4，5 计算机科学与技术 1，5，6，9 信息与计算科学 2，4，8 数学与应用数学 3，7，10 记录号 学号 姓名 性别 专 业 年 级 1 980001 吴承志 男 计算机科学与技术 98级 2 980002 李淑芳 女 信息与计算科学 98级 3 990301 刘 丽 女 数学与应用数学 99级 4 990302 张会友 男 信息与计算科学 99级 5 990303 石宝国 男 计算机科学与技术 99级 6 000801 何文颖 女 计算机科学与技术 2000级 7 000802 赵胜利 男 数学与应用数学 2000级 8 000803 崔文靖 男 信息与计算科学 2000级 9 010601 刘 丽 女 计算机科学与技术 2001级 10 010602 魏永鸣 男 数学与应用数学 2001级 （a）学生信息表 （c）专业索引表 （d）年级索引表 图 1.1 学生信息查询系统中的数据结构
例2八皇后问题 ◆在八皇后问题中,处理过程不是根 据某种确定的计算法则,而是利用试 探和回溯的探索技术求解。为了求得 合理布局,在计算机中要存储布局的 当前状态。从最初的布局状态开始, 步步地进行试探,每试探一步形成 个新的状态,整个试探过程形成了 棵隐含的状态树。如图1.2所示(为 了描述方便,将八皇后问题简化为四 皇后问题) 回溯法求解过程实质上就是一个遍 历状态树的过程。在这个问题中所出 现的树也是一种数据结构,它可以应 用在许多非数值计算的问题中。 图1.2四皇后问题中隐含的状态树 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 在八皇后问题中，处理过程不是根 据某种确定的计算法则，而是利用试 探和回溯的探索技术求解。为了求得 合理布局，在计算机中要存储布局的 当前状态。从最初的布局状态开始， 一步步地进行试探，每试探一步形成 一个新的状态，整个试探过程形成了 一棵隐含的状态树。如图1.2所示（为 了描述方便，将八皇后问题简化为四 皇后问题）。 回溯法求解过程实质上就是一个遍 历状态树的过程。在这个问题中所出 现的树也是一种数据结构，它可以应 用在许多非数值计算的问题中。 例2 八皇后问题
例3教学计划编排问题 课程编号 课程名称 先修课程 计算机导论 无 ◆一个教学计划包含许多课程, 数据结构 汇编语言 在教学计划包含的许多课程之间, C程序设计语言 有些必须按规定的先后次序进行, 计算机图形学 接囗技术 ccccccc 有些则没有次序要求。即有些课程 Cy数据库原理 编译原理 之间有先修和后续的关系,有些课 操作系统 〔a)计算机专业的课程设置 程可以任意安排次序。这种各个课 程之间的次序关系可用一个称作图 的数据结构来表示,如图13所示 有向图中的每个顶点表示一门课程 如果从顶点W到M之间存在有向边 ,则表示课程必须先于课 程j进行 〔b)表示课程之间忧先关系的有向图 图13教学计划编排问题的数据结构 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 例3 教学计划编排问题 一个教学计划包含许多课程， 在教学计划包含的许多课程之间， 有些必须按规定的先后次序进行， 有些则没有次序要求。即有些课程 之间有先修和后续的关系，有些课 程可以任意安排次序。这种各个课 程之间的次序关系可用一个称作图 的数据结构来表示，如图1.3所示。 有向图中的每个顶点表示一门课程， 如果从顶点vi到vj之间存在有向边 ，则表示课程i必须先于课 程j进行
由以土三个例子可见,描述这类非数值计算问 题的数学模型不再是数学方程,而是诸如表、树、 图之类的数据结构,因此,可以说数据结构课程0 主要是研究非数值计算的程序设计问题中所出现 的计算机操作对象以及它们之间的关系和操作的 学科。 学习数据结构的目的是为了了解计算机处理对 象的特性,将实际问题中所涉及的处理对象在计 算机中表示出来并对它们进行处理。与此同时, 通过算法训练来提高学生的思维能力,通过程序 设计的技能训练来促进学生的综合应用能力和专 业素质的提高。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 • 由以上三个例子可见，描述这类非数值计算问 题的数学模型不再是数学方程，而是诸如表、树、 图之类的数据结构。因此，可以说数据结构课程 主要是研究非数值计算的程序设计问题中所出现 的计算机操作对象以及它们之间的关系和操作的 学科。 • 学习数据结构的目的是为了了解计算机处理对 象的特性，将实际问题中所涉及的处理对象在计 算机中表示出来并对它们进行处理。与此同时， 通过算法训练来提高学生的思维能力，通过程序 设计的技能训练来促进学生的综合应用能力和专 业素质的提高
11.2有关概念和术语 ◆数据(Data)是信息的载体,它能够 有时,一个数据元素可由若 被计算机识别、存储和加工处理。它是 计算机程序加工的原料,应用程序处理 干个数据项( Data item)组成, 各种各样的数据。计算机科学中,所谓 例如,学籍管理系统中学生信 数据就是计算机加工处理的对象,它可 息表的每一个数据元素就是 以是数值数据,也可以是非数值数据。 个学生记录。它包括学生的学 数值数据是一些整数、实数或复数,主 号、姓名、性别、籍贯、出生 要用于工程计算、科学计算和商务处理 年月、成绩等数据项。这些数 等;非数值数据包括字符、文字、图形、 图像、语音等 初等项,如学生的性别、籍贯 ◆数据元素( Data element)是数据的 等,这些数据项是在数据处理 基本单位。在不同的条件下,数据元素 时不能再分割的最小单位;另 又可称为元素、结点、顶点、记录等。 种叫做组合项,如学生的成 例如,学生信息检索系统中学生信息表 绩,它可以再划分为数学、物 中的一个记录、八皇后问题中状态树的 理、化学等更小的项。通常, 个状态、教学计划编排问题中的一个 在解决实际应用问题时是把每 个学生记录当作一个基本单位 顶点等,都被称为一个数据元素。 进行访问和处理的。 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 1.1.2 有关概念和术语 数据（Data）是信息的载体，它能够 被计算机识别、存储和加工处理。它是 计算机程序加工的原料，应用程序处理 各种各样的数据。计算机科学中，所谓 数据就是计算机加工处理的对象，它可 以是数值数据，也可以是非数值数据。 数值数据是一些整数、实数或复数，主 要用于工程计算、科学计算和商务处理 等；非数值数据包括字符、文字、图形、 图像、语音等。 数据元素（Data Element）是数据的 基本单位。在不同的条件下，数据元素 又可称为元素、结点、顶点、记录等。 例如，学生信息检索系统中学生信息表 中的一个记录、八皇后问题中状态树的 一个状态、教学计划编排问题中的一个 顶点等，都被称为一个数据元素。 有时，一个数据元素可由若 干个数据项（Data Item）组成， 例如，学籍管理系统中学生信 息表的每一个数据元素就是一 个学生记录。它包括学生的学 号、姓名、性别、籍贯、出生 年月、成绩等数据项。这些数 据项可以分为两种：一种叫做 初等项，如学生的性别、籍贯 等，这些数据项是在数据处理 时不能再分割的最小单位；另 一种叫做组合项，如学生的成 绩，它可以再划分为数学、物 理、化学等更小的项。通常， 在解决实际应用问题时是把每 个学生记录当作一个基本单位 进行访问和处理的