数据结构与算法分析第一章绪论

《数据结构与算法分析第一章绪论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1第一章绪论教学内容：1.1数据结构的原则1.2抽象数据类型和数据结构1.3问题、算法和程序学习要求：理解、掌握算法的基本概念和简单的算法分析、数据和数据结构的基本概念、数据的逻辑结构和存储结构的基本概念及其性质和两种结构之间的关系。2引言二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。3计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数

2、值发展到一般的符号，进而发展到具有一定结构的数据。4在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。51.1数据结构的原则数据结构：一类数据的表示及其相关操作学习数据结构的必要性计算机功能强大更复杂

3、的问题更复杂的问题更大的计算量工作越复杂越偏离人们的日常经验故：必须有一种数据结构来组织各种复杂的数据。任何一种数据项集合都必须具备查询、排序、修改的功能，如果选择一个好的数据结构和算法将会对程序的运行时间产生巨大的影响。一、为什么要学习数据结构？1、什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构7程序的主要目标是存储信息和检索信息,而基础是信息表示.程序设计核心目标：（１）设计一种容易理解、编码和调试的算法　　　　（软件工程原理）（２）设计一种能有效利用计算机资源的算法（数据结

4、构和算法）程序简明清晰（简洁）程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法→数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。软件=程序+文档（软件工程的观点）2、电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。（1）数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的

5、技巧。（2）非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述12例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表13例2人机对奕问题树……..……..…...…...…...…...14例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图例4:电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方

6、式决定了查找（算法）的效率。例5:田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。例6：田径赛的时间安排问题姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M跳高跳远标枪铅球200M100M1、任一选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。（1）设用如下六个不同的代号代表不同的项目：跳高跳远标

7、枪铅球100米200米ABCDEF（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。解法如下：姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛总结：求解非数值计算的问题主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系

8、和操作的学科。二、数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。《数据