第1章 [兼容模式]new

《第1章 [兼容模式]new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法上海大学通信与信息工程学院2014年9月第1章绪论教材及参考书目教材数据结构与算法，郭龙源等编，清华大学出版社参考书数据结构及应用算法教程，严蔚敏等编清华大学出版社数据结构（C语言版），严蔚敏等编清华大学出版社2014年9月1日3本章主要内容111.1学习数据结构与算法的意义1.2数据结构1.3抽象数据类型141.4算法1.5算法分析2014年9月1日41111.1学习数据结构与算法的意义1111.1.1学习数据结构的意义1.1.2学习算法的意义2014年9月1日51111.1.1学习数据结构的意义数据

2、结构为研究非数值计算问题提供了数据的表示与操作途径。数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂课题的。要想有效地使用计算机，充分发挥计算机的功能，还必须学习和掌握好数据结构的有关知识。扎实地打好“数据结构”这门课程的基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程及人工智能等都是十分有益的。2014年9月1日61121.1

3、.2学习算法的意义学习和研究算法可以明确分析所得到的算法的好坏，寻找能满足要求的较优算法，从而更加高效地解决问题。学习算法设计的方法和算法分析的技术后，可以帮助我们设计较好的算法，分析算法的优、缺点，从而找出解决某一问题的最好方法。2014年9月1日71121.2数据结构1211.2.1数据结构概述1221.2.2基本概念和相关术语2014年9月1日81211.2.1数据结构概述数据结构是在整个计算机科学与技术领域中广泛使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分构成？以什么方式构成？呈现什么样的结构？数

4、据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映数据之间的逻辑关系，而物理上的数据结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式。1221.2.2基本概念和相关术语数据(data)是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据分为两类：数值型数据(主要用于数学计算等)：整型、实型、布尔型等非数值型数据：文字、图形、图像、音频和视频等，文献检索、金融管理、商业系统等数据处理1221.2.2基本概念和相关术语数据元素(dataele

5、ment)(dataelement)是数据的基本单位。一个数据元素可由不可分割的若干个数据项(dataitem)组成。如数据集合NN{={11，2，3，4，5}5}中整数1至5均为数据元素数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。数据元素有时也称元素、结点、记录、顶点等数据对象(dataobject)是性质相同的数据元素的集合，是数据的一个子集如大写字母字符的数据对象是集合：C{‘A’C={‘A’，‘’‘B’，...，‘’}‘Z’}1221.2.2基本概念和相关术语数据类型：程序设计

6、语言中允许的变量类型基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等结构类型：变量值可分，如数组、结构体等1221.2.2基本概念和相关术语数据结构(datastructure)是指相互之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间总是存在联系的。把某一数据对象及该数据对象中所有数据成员之间的关系组成的实体叫做数据结构。数据结构有以下4种基本结构（逻辑结构）：(1)集合结构：数据元素之间存在着“属于同一个集合”的关系(2)线性结构：数据元素之间存在着“一对一”的关系(3)树形结构：数

7、据元素之间存在着“一对多”的关系(4)图形结构：数据元素之间存在着“多对多”的关系集合结构线性结构树形结构图形结构1221.2.2基本概念和相关术语数据结构的形式定义为Data_Structure=(D,R)其中，D是数据元素的有限集；R是D上关系的有限集例：图1.3(a)(b)例1：linearity=(D,R)，其中D＝{12345678910}{1,2,3,4,5,6,7,8,9,10}R={r}r={<72><21><16><610><108><84><45>{<7,2>,<2,1>,<1,6>,<6,10>,<1

8、0,8>,<8,4>,<4,5>,<5,3>,<3,9>}1221.2.2基本概念和相关术语例5：设：B=((,)D,R)其中D={A,B,C,D,E}R={(1,2),(2,3),(3,4)}问：能否构成数据结构？不能关系R不在D上1221.2.2基本概念和相关术语例2：Tree=((,)D,R)，其