《数据结构》-绪论

,从课程性质上讲，“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。,如果说高级语言程序设计课程对学生进行了程序设计（程序抽象）的初步训练的话，那么数据结构课程就是要培养他们的数据抽象能力。,课程内容：,第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章内部排序第十一章外部排序第十二章文件,第一章 绪论,自第一台计算机1946年在美国问世以来，计算机的应用范围大大地扩展，已深入到人类社会的各个领域。与此相应的，计算机加工处理的对象也从纯粹的数值发展到字符、图像、声音等各种具有一定结构的复杂的数据。例如，数值计算到卫星发射等等。因此要设计出一个好的程序（程序执行时间最短，占内存空间最小），必须研究数据的特性以及数据之间存在的关系。这就形成了数据结构这门课程。,第一章 绪论,1.1 什么是数据结构,1.2 基本概念和术语,1.4 算法和算法分析,1.3 抽象数据类型的表示与实现,1.1 什么是数据结构,一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写程序、进行测试、调整直至得到最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。,(数据结构在软件开发中的地位),系统分析,系统设计,系统实现,系统维护,系统设计,例1-1 图书馆的书目检索自动化,“学生”表格,在这类文档管理的数学模型中，计算机处理的对象之间通常存在的是一种最简单的线性关系，这类数学模型可称谓线性的数据结构。,例1-2 计算机和人对奕问题,UNIX文件系统的系统结构图,“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构。,为了设计一个交通信号灯的管理系统，首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。,例1-3 多叉路口交通灯的管理问题,例1-3 多叉路口交通灯的管理问题,根据这个路口的实际情况可以确定13个可能通行方向：AB，AC，AD，BA，BC，BD，DA，DB，DC，EA，EB，EC，ED。可以把AB简写成AB，用一个结点表示 ，在不能同时行驶的结点间画一条连线(表示它们互相冲突)，便可以得到如右图所示的表示。这样得到的表示可以称之为“图” 。,例1-2 多叉路口交通灯的管理问题,E,1,3,1,4,4,1,1,3,2,2,1,1,2,AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC,ED,如果把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”：即求出最少要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。通过上面的分析，我们就获得了该交通管系统的数学模型。,例：田径赛的时间安排问题,跳高,跳远,标枪,铅球,200M,100M,1、任一选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。,通常，这一类的数学模型是一种称谓“图”的数据结构。,描述这类非数值计算的程序设计问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。,简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作的等等的学科。,数据结构作为一门独立的课程在国外是1968年才开始设立的。在这之前，它的某些内容曾经要其它课程，如表处理语言中有所阐述。 1968年美国唐.欧.克努特教授开创了数据结构的最初体系，他所著的“计算机程序设计”第一卷“基本算法”是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 随后，人们开始认为和程序设计实质是对确定问题选择一种好的结构，加上设计一种好的算法。,Algorithm + Data Structures = Programs,程序设计:算法: 数据结构:,为计算机处理问题编制 一组指令集,处理问题的策略,问题的数学模型,结构静力分析计算,例如: 数值计算的程序设计问题, 线性代数方程组, 环流模式方程 (球面坐标系),全球天气预报,数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和