数据结构课件ch01_绪论-2014

《数据结构课件ch01_绪论-2014》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法n课程编号：SC03100110n授课学时：48（2至14周，周4学时，2次）n实验学时：12（第6/8/10/12周，3学时/1次）n课程分类：专业（技术）基础n答疑地点：格物楼203，每周1次n课程资源：qhttp://cms.hit.edu.cnn考核形式：q笔试70%+作业10%+实验20%n主讲教师：李秀坤q联系方式：电话13796628867qemail:lixiukun@hit.edu.cn数据结构与算法第1章绪论数据结构与算法教学目的:(1)学会分析和研究计算机处理的数据对象的特性,掌握常 用数据结构内在的逻辑关系、在机内的存储表示

2、,掌握 常用数据结构上的运算操作的动态性质和执行算法. (2)能够为实际应用选择适当的数据结构、存储结构和相应算法；(3)初步掌握算法性能的分析方法。参考书目n[美]SartajSahni著，汪诗林孙晓东等译：《数据结构、算法与应用》C++语言描述，机械工 业出版社，2000年1月n高质量C++/C编程指南http://man.chinaunix.net/develop/c&c++/c/c.htm#_Toc520634058数据结构的创始人—Donald.E.Knuth1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28 岁任副教授。30岁时

3、，加盟斯坦福大 学计算机系，任教授。从31岁起，开 始出版他的历史性经典巨著：TheArtofComputerProgramming他计划共写7卷，然而出版三卷之后， 已震惊世界，使他获得计算机科学界 的最高荣誉图灵奖，此时，他年仅36 岁。主要内容Ø1.1数据结构的定义Ø1.2数据结构的抽象形式Ø1.3算法定义Ø1.4算法性能分析与度量Ø本章小结思考统计总n表1是5次C语言序计算这5次测测试1.1数据结构的定义ü信息是客观世界在人脑中的反映ü数据是信息的载体ü怎样在计算机中存储和组织数据？n程序设计的实质是什么?q数据表示：将数据存储在计算机中q数据处理：处理

4、数据，求解问题q数据结构问题起源于程序设计n数据结构随着程序设计的发展而发展q1.无结构阶段：在简单数据上作复杂运算 q2.结构化阶段：数据结构＋算法＝程序 q3.面向对象阶段：（对象＋行为）＝程序n数据结构的发展并未终结…….n客观世界与计算机世界的关系ü计算机科学是研究信息表示和信息处理的科学。ü信息在计算机内是用数据表示的。ü用计算机解决实际问题的实质可以用下图表示：映象机器世界客观世界概念世界映象（客观问题）抽象（存储表示）(逻辑模型)实现映象模拟客观世界与计算机的关系例1学籍管理问题——表结构完成什么功能?各表项之间是什么关系？学号姓名性别出生日期政治

5、面貌0001王晓东男1990/09/02团员0002李明远男1989/12/25党员0003张蔷薇女1991/03/26团员……………例2人机对弈问题——树结构如何实现对弈?各格局之间是什么关系？1210 75164例3教学计划编排问题——图结构如何表示课程之间的先修关系？编号课程名称先修课C1高等数学无C3C5C2计算机导论无C1C3离散数学C1C4程序设计C1,C2C4C7C5数据结构C3,C4C2C6计算机原理C2，C4C7数据库原理C4,C5,C6C6例4坐船问题（改编自湖南省信息学省队选拔赛试题）ü某高校有n个学生去公园划船； ü一只船最多坐2个人；ü

6、出于娱乐目的，大家决定同船的2个人要么同姓要么同名；ü每个人都必须上船，且一人不能上多只船； ü问最少需要几只？基本概念：数据(Data):Ø数据是信息的载体，是描述客观事物的数、字符、 以及所有能输入到计算机中，被计算机程序识别和处 理的符号的集合。ü数值性数据ü非数值性数据数据元素(DataElement):ü数据的基本单位，在计算机程序中常作为一个整体进行考虑和处理。ü有时一个数据元素可以由若干数据项 (DataItem)组成。数据项是具有独立含义的最小标识单位。ü数据元素又称为元素、结点、记录。数据对象(DataObject):n数据的子集，具有相同性质

7、的数据成员（数据元素）的集合。N={0,±1,±2,…}u整数数据对象u学生数据对象数据对象中所有成员之间存在某种关系，n如学生按学号的排序；按性别的分类等。数据成员及其之间关系，是数据结构研究n的主要内容。什么是数据结构数据以及数据之间的相互关系，即计算机 中存储和组织数据的形式。通常可以用一个二元组来表示。或写成DS=。其中D是数据集合（数据对象），R是D中数据元素之间所存在的关系的有限集合。数据结构（技术）就是根据各种不同的数据 集合和数据元素之间的关系，研究如何表示、存 储和操作（查找、插入、删除、修改、排序）这些数据的技术。N个网站

8、之间的连通关系12123