算法与数据结构.

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

1、算法与数据结构11．课程学时总学时:36学时2．本课程主要参考书[1]宁正元等.算法与数据结构（第二版）.清华大学出版社[2]漆涛等.算法与数据结构（C++版）.电子工业出版社课前简介2课前简介3．学习成绩考核方法期末考试占70%平时(课堂作业+出勤）占30%4.教师信息任课教师：刘玲E-mail:381677848@qq.com3课程内容第一章绪论第二章常用算法第三章线性表第四章栈与队列第五章树与二叉树第六章图与网第七章检索及基本算法第八章排序及基本算法41.1什么是数据结构1.2基本概念和术语1.3算法和

2、算法分析第1章绪论51.1什么是数据结构一、计算机的主要用途早期：主要用于数值计算(关键是列数学方程，输入输出都是数值，如根据半径求圆面积等)。后来：处理逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)，如人机博弈、各种管理系统等。6二、什么是程序？NiklausWirth：Programs=Algorithm+DataStructures程序:算法:数据结构:计算机处理问题的指令集处理问题的策略问题的数学模型1.1什么是数据结构例如：计算机和人对弈算法：?模型：?对弈的规则和策略棋盘及

3、棋盘的格局7《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科(记忆)。三、《数据结构》研究的范畴1.1什么是数据结构8一、数据与数据结构1.数据：是对客观事物的符号表示，是所有能被输入到计算机中且能被计算机处理的符号的集合(如字母、汉字、数字等)。2.数据元素：是数据的基本单位，具有完整确定的实际意义。也是数据结构中讨论的基本单位(如一个学生记录)。具有相同特性的数据元素的集合称为数据对象(如全班同学的学生记录)。1.2基本概念和术语93.数据项：是构成数据元素的

4、项目，是具有独立含义的最小标识单位，是数据结构中讨论的最小单位(如学号、姓名、性别等)。三者之间的关系：数据项组成数据元素∈数据学号、…个人记录通讯录一、数据与数据结构1.2基本概念和术语104.数据结构：带结构的数据元素的集合。一、数据与数据结构1.2基本概念和术语相同的数据+不同的结构不同的数据结构！不同的数据+相同的结构不同的数据结构！115.数据的逻辑结构(理解)集合结构：仅同属一个集合线性结构:一对一（1:1)树形结构:一对多（1:n)网状结构:多对多(m:n)非线性线性逻辑结构可细分为4类(记

5、忆)：指数据元素之间的(内在的、本质的)逻辑上的关系，它与数据的存储无关，独立于计算机。一、数据与数据结构1.2基本概念和术语12存储结构可分为4大类：例：要存储一个整数对<60,79>，有两种存储方式：顺序、链式、索引、散列79030260030004150302600300041579法1：地址内容法2：地址内容2字节是数据元素及其逻辑结构在存储器内的表示(或映像)。依赖于计算机。6.数据的物理结构/存储结构(理解)一、数据与数据结构1.2基本概念和术语136.数据的物理结构/存储结构数据元素及其逻辑结构

6、在存储器内的映像“数据元素”的映象？“逻辑结构”(用x,y>表示)的映象？一、数据与数据结构1.2基本概念和术语用二进制位串表示数据元素，如：(321)10=(501)8=(101000001)2A=(101)8=(001000001)214①顺序映象：以相对的存储位置表示后继关系②链式映象:以附加信息(指针)表示后继关系yxxy6.数据的物理结构/存储结构一、数据与数据结构1.2基本概念和术语x,y157.数据结构的形式定义数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元

7、素的有限集，S是D上逻辑关系的有限集。一、数据与数据结构1.2基本概念和术语简言之，数据对象及其上的关系称为数据结构16二、抽象数据类型数据类型：是一个值的集合和定义在此集合上的一组操作(相当于运算符或操作符)的总称。注意：不同类型的变量，其所能取的值的范围不同，所能进行的运算不同。如：-9不能作开方运算！1.2基本概念和术语ADT与DS的关系如同int与-9的关系。17二、抽象数据类型(AbstractDataType，简称ADT)ADT是指一个数学模型(DS)以及定义在此数学模型上的一组操作(运算)。1.

8、定义：ADT可用三元组表示：ADT=（D，S，P）数据对象D上的关系集D上的基本操作集1.2基本概念和术语抽象数据类型和数据类型实质上是一个概念(基本数据类型由系统提供存储及运算的实现。ADT由程序员提供，属于用户自定义数据类型)182.定义格式数据对象：D＝{………….}数据关系集合：R＝{…………}基本操作集合P：……ADT类型名{}ADT类型名基本操作定义格式：基本操作名(参数表)初始条件：<