第1章 绪论(严蔚敏 李冬梅版)

《第1章 绪论(严蔚敏 李冬梅版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*数据结构*编程基础计算机及相关专业考研考博课程计算机等级考试课程程序员考试课程为什么要学习数据结构*课程学习指导1.提前预习、认真听课、按时完成书面及上机作业2.注意先修课程的知识准备离散数学、C语言3.注意循序渐进：基本概念、基本思想、基本步骤、算法设计4.注意培养算法设计的能力理解所讲算法、对此多做思考：若问题要求不同，应如何选择数据结构，设计有效的算法课程特点：内容抽象、概念性强、内容灵活、不易掌握*平时成绩:30%作业、小测验、实验课堂纪律无故迟到：无故旷课：－５上机：玩游戏、上网聊天期末成绩:70%(闭卷笔试)考核方式

2、*教材和参考书教材：《数据结构》978-7-115-23490严蔚敏，李冬梅，人民邮电出版社出版参考书：《数据结构C语言版》，严蔚敏，清华大学出版社《数据结构——用面向对象方法与C++描述》，殷人昆等，清华大学出版社*第1章绪论1.了解数据结构研究的主要内容2.掌握数据结构中涉及的基本概念3.掌握算法、算法的时间复杂度及其分析的简易方法教学目标*1.1数据结构的研究内容1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法与算法分析教学内容*N.沃思（NiklausWirth)教授提出：程序=算法+数据结构电子计算机的主要用

3、途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据1.1数据结构的研究内容*书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表*人机对奕问题树……..……..…...…...…...…...*/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图树*多叉路口交通灯管理问题CEDABABACADBABCBDDADBD

4、CEAEBECED图顶点：一条通路连线：不能同时通行染色：有连线的两个顶点不能具有相同颜色*求解非数值计算的问题：设计出合适的数据结构及相应的算法即：首先要考虑对相关的各种信息如何表示、组织和存储？数据结构的研究内容为：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。*数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关

5、系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。*《数据结构》所处的地位：介于数学、计算机硬件和计算机软件三者之间的一门核心课程北京林业大学信息学院*数据结构在计算机学科中的地位*课程目的能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存贮结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术*1、数据（data)—所有能输入到计算机中去的描述客观事物的符号数值性数据非数值性数据（多媒体信息处理）2、数据元素（d

6、ataelement）—数据的基本单位，也称结点（node）或记录（record）3、数据项（dataitem）—有独立含义的数据最小单位，也称域(field)三者之间的关系：数据>数据元素>数据项例：学生表>个人记录>学号、姓名……1.2基本概念和术语*整数数据对象N={0,1,2,…}学生数据对象学生记录的集合4、数据对象(DataObject)：相同特性数据元素的集合，是数据的一个子集*5、数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构

7、”就是指数据元素之间存在的关系。*数据结构的两个层次：逻辑结构---数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。*划分方法一（1）线性结构----有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串（2）非线性结构----一个结点可能有多个直接前趋和直接后继。例如：树、图逻辑结构*线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数

8、据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构划分方法二*存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系存储结构