学习数据结构的意义和作用

《学习数据结构的意义和作用》由会员分享，可在线阅读，更多相关《学习数据结构的意义和作用（6页珍藏版）》请在金锄头文库上搜索。

1、学习数据结构的意义和作用学习数据结构的意义和作用董建寅 罗远 （上海金融学院信息管理系，201209） ） 引言引言 为什么要学习数据结构？数据结构是否是一门纯数学课程？它在专业课程体系中 起什么样的作用？许多学生学完后也茫然一片，为此我们很有必要探讨一下学习数据结 构的意思和作用。众所周知，计算机科学是一门研究数据表示和数据处理的科学。数据 是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科 学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术应用等，都是对数 据进行加工处理的过程。因此，要设计出一个结构好效率高的程序，必须研究数据的特 性及数据间的相互关系

2、及其对应的存储表示，并利用这些特性和关系设计出相应的算法 和程序。 1 学习数据数据结构的意义学习数据数据结构的意义 数据结构是计算机科学与技术专业、计算机信息管理与应用专业，电子商务等专业 的基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类 型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序 设计语言是难以应付当前众多复杂的课题。要想有效地使用计算机、充分发挥计算机的 性能，还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基 础，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程、编译 原理、人工智能、图

3、视学等都是十分有益的。 2 为什么要学习数据结构为什么要学习数据结构 在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使 用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽 象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进 行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方 程组，可以使用迭代算法来求解。 由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者 的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的 扩大和软、硬件的发展，非数值计算问题越

4、来越显得重要。据统计，当今处理非数值计 算性问题占用了 85%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素 之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数 学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举 的就是属于这一类的具体问题。 例 1：图书馆信息检索系统。当我们根据书名查找某本书有关情况的时候；或者根据作者 或某个出版社查找有关书籍的时候，或根据书刊号查找作者和出版社等有关情况的时候， 只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自 动检索。由此，可以在图书馆信息检索系统中建立一张按书

5、刊号顺序排列的图书信息表 和分别按作者、书名、出版社顺序排列的索引表，如图 1.1 所示。由这四张表构成的文件便是图书信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定书名） 对图书馆藏书信息文件进行查询。 诸如此类的还有学生信息查询系统、商场商品管理系统、仓库物资管理系统等。在 这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关 系，这类数学模型可称为线性的数据结构。 图 1.1 图书馆信息检索例 2：八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是 利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状 态。

6、从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个 试探过程形成了一棵隐含的状态树。如图 1.2 所示（为了描述方便，将八皇后问题简化为 四皇后问题） 。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现书刊号书名作者出版社书架编号7-302-02368-3数据结构严蔚敏清华大学p302-419-25-301-00128-1线性代数李志中复旦大学k203-048-17-309-01408-2数据结构蔡子经高校出版社p302-428-55-303-01654-3线性代数赵坚清华大学k205-046-26-506-04314-2离散数学左孝凌复旦大学t-304-

7、056-27-406-03416-1数据结构李有亮上海教育出版社p302-433-47-406-01256-2计算机组成顾浩清华大学w306-224-26-507-014654-1离散数学杨文杰高校出版社t-306-433-57-408-056118-2计算机组成顾浩上海教育出版社w-305-036-6(a)图书信息蔡子经 3顾浩 7，9李志中 2李有亮 6严蔚敏1杨文杰 8左孝凌5赵坚 4(b)作者索引表数据结构1，3，6线性代数2，4离散数学5，8计算机组成7，9(c)书名索引表清华大学1,4,7复旦大学2,5高校出版社3,8上海教育出版社6,9(d)出版社索引表的树也是一种数据结构，它可

8、以应用在许多非数值计算的问题中。例 3：教学计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间， 有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续 的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的 数据结构来表示，如图 1.3 所示。有向图中的每个顶点表示一门课程，如果从顶点 vi到 vj之间存在有向边，则表示课程 i 必须先于课程 j 进行。由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是 诸如线性表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计 算的程序设计问题中所出现的计

9、算机操作对象以及它们之间的关系和操作的学科。图 1.2 四皇后问题中隐含的状态树学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处 理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的 思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。课程编号课程名称先修课程 C1程序设计基础无 c2离散数学C1 C3数据结构C1，C2, C5 C4汇编语言C1 C5C 程序设计语言C1 C6计算机图形学C3，C4，C5 C7接口技术C4 C8数据库原理C3，C10 C9编译原理C4 ,C5 C10操作系统C3c2c1c3c4c5c6c8c

10、7c10c9表示课程之间优先关系的有向图图 1.3 教学计划编排问题的数据结构3 数据结构课程的内容数据结构课程的内容 数据结构与数学、计算机硬件和软件有十分密切的关系，它是介于数学、计算机硬 件和计算机软件之间的一门计算机专业的核心课程，是高级程序设计语言、操作系统、 编译原理、数据库、人工智能、图视学等课程的基础。同时，数据结构技术也广泛应用 于信息科学、系统工程、应用数学以及各种工程技术领域。 数据结构课程重在讨论软件开发过程中的方案设计阶段、同时设计编码和分析阶段 的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实 现的评价与选择。因此，数据结构的内容包括三个

11、层次的五个“要素” ，如图 1.4 所示。数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次；再通过 抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分 成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合使我 们将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过 程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计 任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练地掌握这两 个过程是数据结构课程在专业技能培养方面的基本目标。 结束语：结束语：数据结构作为一门独立的课程

12、在国外是从 1968 年才开始的，但在此之前其有 关内容已散见于编译原理及操作系统之中。20 世纪 60 年代中期，美国的一些大学开始设 立有关课程，但当时的课程名称并不叫数据结构。1968 年美国唐.欧.克努特教授开创了数 据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较 系统地阐述数据的逻辑结构和存储结构及其操作的著作。从 20 世纪 60 年代末到 70 年代 初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容， 人们越来越重视数据结构。从 70 年代中期到 80 年代，各种版本的数据结构著作相继出 现。目前，数据结构的发展并未终结，一方面，

13、面向各专门领域中特殊问题的数据结构 得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观 点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。 参考资料1 数据结构（C 语言版） 严蔚敏 编（著） 清华大学出版社；1997.42 数据结构习题解析与上机实验指导宁正元编（著） 上海交大出版社；2000.113 论文数据结构精品课程建设模式与实践浙江万里学院 杨秀金 汪沁 胡锡伟 等方面层次数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同数据结构的比较及算法分析图 1.4 数据结构课程内容体系4数据结构实用教程徐孝凯（著） ，北京，清华大学出版社，1999 年 12 月第 1 版联系地址与电话 上海金融学院信息管理系 上川路 995 号 邮编 201209 董建寅 电话:13321996712 021-65582883 021-50218739 E_MAIL :