1.1 数据结构的研究内容
早期的计算机主要用于数值计算,一般要经过如下几个步骤:首先从问题抽象出数学模型,然后设计一个算法,最后编写程序,进行测试、调试,直到解决问题。
寻找数学模型的实质是分析问题,建立相应的数学方程。
现在的计算机主要用于非数值计算,非数值计算问题无法用数学方程建立数学模型。
【例1】学生信息管理系统
学号 | 姓名 | 性别 | 籍贯 | 专业 |
---|---|---|---|---|
20050112 | 张三 | 男 | 浙江 | 软件工程 |
20050113 | 李四 | 男 | 上海 | 软件工程 |
20050114 | 王五 | 男 | 安徽 | 软件工程 |
在这类问题中,计算机处理的对象是各种表,元素之间的关系,这类问题的数学模型就是各类线性表。
由上例可以看出,非数值计算问题的数学模型不再是数学方程,而是线性表等数据结构。
因此,数据结构是一门研究非数值计算程序设计中的操作对象以及这些对象之间关系和操作的学科。
形成阶段:20世纪60年代初期,“数据结构”有关的内容散见于操作系统、编译原理等课程中,1968年,“数据结构”被列入美国一些大学计算机科学系的教学计划。
之后,随着大型程序与大规模文件系统的出现,人们普遍认为程序设计的实质就是对所处理的问题选择一种好的数据结构,并在此基础上设计好的算法。
Wirth教授提出:算法+数据结构=程序
发展阶段:数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。
70年代后期,我国高校陆续开设该课程。
可以认为数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。