文档介绍：主要学****内容:
一、什么是数据结构
二、基本概念和术语
三、抽象数据类型的表示与实现
四、算法和算法分析
第一章绪论
数据结构是计算机科学与技术专业的专业基础课,是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此,要想更好地运用计算机来解决实际问题,仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能,还必须学****和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础,对于学****计算机专业的其他课程,如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。
一、课程介绍
二、学****数据结构的目的
计算机解决问题经历的几个步骤:
1、从具体问题中抽象出数学模型
2、确定此数学模型的算法
3、程序设计
4、程序测试与调整
5、得到最终结果
例1-1 学生信息检索系统。当我们需要查找某个学生的有关情况的时候;或者想查询某个专业或年级的学生的有关情况的时候,只要我们建立了相关的数据结构,按照某种算法编写了相关程序,就可以实现计算机自动检索。。
例1-2 计算机和人对弈问题。计算机之所以能和人对弈是因为有人将对弈的策略事先已存入计算机。。
(a)
(b)
(a) 棋盘格局示例; (b)对弈树的局部。
井字棋对弈“树”
例1-3 多叉路口交通灯的管理问题。(a)所示五叉路口,其中C和E为单行道。在路口有13条可行的道路,其中有的可以同时通行,如 AB和EC,而EB和AD不可同时通行。那么,在路口应如何设置交通灯进行车辆的管理呢?(b)中,(a)所示五叉路口上的一条通道,两个圆圈之间的连线表示这两个圆圈表示的两条通路不能同时通行。
A
E
D
B
C
(a)
1
2
3
4
1
1
1
1
1
2
2
3
4
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
(b)
五叉路口交通管理示意图
总结如下:
由以上三个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树、图之类的数据结构。因此,可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
学****数据结构的目的是为了了解计算机处理对象的特性,将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时,通过算法训练来提高学生的思维能力,通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。
数据(Data)是信息的载体,它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料,应用程序处理各种各样的数据。
数据元素(Data Element)是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。例如,学生信息检索系统中学生信息表中的一个记录、人机对弈问题中状态树的一个状态、五叉路口交通灯问题中的一个顶点等,都被称为一个数据元素。
有时,一个数据元素可由若干个数据项(Data Item)组成,例如,学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。
数据对象(Data Object)或数据元素类(Data Element Class)是具有相同性质的数据元素的集合。
例如, 在交通咨询系统的交通网中,所有的顶点是一个数据元素类,顶点A和顶点B各自代表一个城市,是该数据元素类中的两个实例,其数据元素的值分别为A和B。
数据结构(Data Structure)是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中,数据元素之间都不会是孤立的,在它们之间都存在着这样或那样的关系,这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性,通常有下列四类基本的结构:
⑴集合结构。在集合结构中,数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。
⑷图形结构。该结构的数据元素之间存在着多对多的关系,图形结构也称作网状结构。。
⑶树型结构。该结构的数据元素之间存在着一对多的关系。
⑵线性结构。该结构的数据元素之间存在着一对一的关系。