数据结构.第1章绪论--2010

《数据结构.第1章绪论--2010》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法课程编号：08T1031010英文译名：DATASTRUCTUREandALGORITHMS总学时：40/8授课对象：计算机科学与技术本科生先修课程：高等数学、集合与图论、C程序设计课程要求：必修课课程分类：技术基础授课教师：张岩/李秀坤答疑地点：综合楼403/格物楼203办公电话：86413213/86403146E-mail：zhangy@hit.edu.cnlixiukun@hit.edu.cn数据结构与算法教学目的:(1)学会分析和研究计算机处理的数据对象的特性,掌握常用数据结构内在的逻辑关系、在机内的存储表示,掌握常用数

2、据结构上的运算操作的动态性质和执行算法.(2)能够为实际应用选择适当的数据结构、存储结构和相应算法；(3)初步掌握算法性能的分析方法。参考书目1.[美]SartajSahni著，汪诗林孙晓东等译：《数据结构、算法与应用》C++语言描述，机械工业出版社，2000年1月2.高质量C++/C编程指南http://man.chinaunix.net/develop/c&c++/c/c.htm#_Toc520634058计算机系列课程之间的联系计算机概论与上机操作（对21世纪公民要求）程序设计与算法语言（BASIC、FORTRAN、PASCAL、C语言等）计算机组成原理（介

3、绍计算机的共性）微机原理及应用（特定机型介绍，如PC机或单片机）工业控制之路数据处理之路汇编语言程序设计数据结构单片机技术/微机接口操作系统软件技术基础数据库理论计算机网络软件工程计算机网络数据结构涵盖的内容数据结构与算法一、数据结构是怎样产生的？数值处理早期科学计算控制非数值计算管理及数据处理例如：在城市交通运输中，从A点到B点有很多条道路，每条道路的长度不同，拥挤程度不同，要选择一条最快的线路到达目的地，该如何选择？再比如：图书馆有成千上万的图书资料，该如何进行管理才能使我们可以快速查找到需要的资料。数据结构与算法城市人口问题，怎样保存这些

4、人口的资料信息，才能使快速查找到所需要查找的人。以上都是典型的非数值问题。思考：1.如何在计算机内部描述这些非数值问题？2.采用什么样的算法可以快速、有效地完成问题的求解？对于不同的处理对象，要想设计出高质量的程序，就必须研究如何组织数据和处理数据，根据问题的要求及数据元素之间的特性，确定相应的存储结构和算法，这些都是数据结构研究的内容。数据结构就是研究这类非数值处理的程序设计问题。数据结构与算法二、选择合适数据结构解决应用问题1．计算机处理问题的分类（1）数值计算问题在计算机发展初期，人们使用计算机主要是处理数值计算问题。【例】线性方程的求解该类问题涉及的运算对象是

5、简单的整型、实型或布尔型数据。程序设计者的主要精力集中于程序设计的技巧，无须重视数据结构。（2）非数值性问题据统计，当今处理非数值性问题占用了90%以上的机器时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。数据结构与算法因此，解决此类问题的关键已不再是分析数学和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。2．非数值问题求解著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出：算法+数据结构=程序数据结构：是指数据的逻辑结构和存储结构算法：是对数据运算的描述程序设计的实质是对实际问题选择一种好的数据结构，加之设

6、计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。数据结构与算法【例】电话号码查询问题。编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项：姓名和电话号码。快的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是找遍整个表均没有找到为止。若这张表是按姓氏排列的，则可另造一张姓氏索引表，采用如下图所示的存储结构。因此，在

7、这种新的结构上产生的查找算法就更为有效。数据结构与算法数据结构与算法【例】田径赛的时间安排问题。假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛。现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。现在要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。（1）为了能较好地解决这个问题，首先应该选择一个合适的数据结构来表示它。表示该问题的数据结构模型图如下图。数据结构与算法显然同一个选手选择的几个项目是不能在同一时间内比赛的，因此该选手选择的项目中应该两两