1、课程内容：计算机软件的基础知识数据结构课时安排：数据结构32学时 上机8学时教材：实用数据结构与算法设计 庄晋林等参考书：数据结构 严蔚敏 清华目目 录录 1.1 数据结构的发展史及地位数据结构的发展史及地位1.2 数据结构的定义数据结构的定义1.3 数据类型数据类型1.4 算法及算法分析算法及算法分析数据结构数据结构:是介于数学、计算机硬件和计算机软件三者之间是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。的一门核心课程。数学硬件软件数据数据结构结构 数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计问题中计的程序设计问题中计算机的操作对象以及它们之间的关系和操作等
2、等的学科。算机的操作对象以及它们之间的关系和操作等等的学科。1.2 数据结构的定义数据结构的定义学号 姓名 性别 籍贯 电 话 通 讯 地 址 01 张三 男 长沙 8639000 麓山南路 327 号 02 李四 男 北京 23456789 学院路 435 号 03 王五 女 广州 30472589 天河路 478 号 04 赵六 男 上海 41237568 南京路 1563 号 05 钱七 女 南京 5013472 南京大学 06 刘八 女 武汉 61543726 武汉大学 07 朱九 男 昆明 4089651 云南大学 08 孙十 女 杭州 6154372 西湖路 635 号 图 1-1
3、 学生数据表 1、线性表示例、线性表示例例例1 1 书目自动检索系统书目自动检索系统书目文件书目文件按书名按书名按作者名按作者名按分类号按分类号索引表索引表线性表线性表例例2 2 人机对奕问题人机对奕问题树树.什么是数据结构？什么是数据结构？答答:(见见教材教材P6)是相互之间存在一种或多种特相互之间存在一种或多种特定定关系关系的的数据元素数据元素的集合，表示为：的集合，表示为：（数值或非数值数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：亦可表示为：S（D,R）或或 B=（K,R）元
4、素有限集元素有限集关系有限集关系有限集1.2.2 基本概念及术语基本概念及术语 1、数据、数据(data)所有能被计算机识别、存储和处理的符号所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息的集合（包括数字、字符、声音、图像等信息）。）。2、数据元素、数据元素(data element)是数据的是数据的基本基本单位，具有完整单位，具有完整确定的实际意义确定的实际意义(又称元素、结点，顶点、记录等）。又称元素、结点，顶点、记录等）。数据项数据项(data item)构成数据元素的项目。是具有独立构成数据元素的项目。是具有独立含义的含义的最小最小标识单位（又称字段、域、
5、属性标识单位（又称字段、域、属性 等）。等）。术语：术语：数据、数据元素、数据项、数据对象数据、数据元素、数据项、数据对象三者之间的关系：数据三者之间的关系：数据 数据元素数据元素 数据项数据项例：例：班级通讯录班级通讯录 个人记录个人记录 姓名、年龄姓名、年龄4、数据结构、数据结构(data structure)数据结构有逻辑结构和物理结构之分。数据结构有逻辑结构和物理结构之分。物理结构是一种逻辑结构在存储器中的存储方式，存物理结构是一种逻辑结构在存储器中的存储方式，存储方式有顺序、链接、索引、散列等多种，所以一种逻辑储方式有顺序、链接、索引、散列等多种，所以一种逻辑结构可以采用多种物理结构
6、存储。结构可以采用多种物理结构存储。通常所说的通常所说的数据结构数据结构就是指就是指逻辑结构。逻辑结构。3、数据对象数据对象(data object)性质相同的数据元素的集合性质相同的数据元素的集合,是数据的一个子集。是数据的一个子集。什么叫数据的逻辑结构？什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是它与数据的存储无关，是独立于计算机独立于计算机的。逻辑结构可细的。逻辑结构可细分为分为4类：类：集合结构：集合结构：仅同属一个集合仅同属一个集合线性结构线性结构:一对一（一对一（1:1)树树
7、 结结 构构:一对多（一对多（1:n)图图 结结 构构:多对多多对多 (m:n)非线性非线性线线 性性什么叫数据的物理结构？什么叫数据的物理结构？答：物理结构亦称答：物理结构亦称存储结构存储结构，是数据的逻辑结构在计，是数据的逻辑结构在计算机存储器内的表示（或映像）。它算机存储器内的表示（或映像）。它依赖于计算机依赖于计算机。存储结构可分为存储结构可分为4大类：大类：顺序、链式、索引、散列顺序、链式、索引、散列元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m
8、顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 1400 1400 1346 1346 元素元素4 4 .1400 1400 元素元素2 2 1536 1536 .1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h什么是数据的运算？什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。答：在数据的逻辑结构上定义的操作算法。在数据的在数据的存储结构上实现存储结构上实现。最常用的数据运算有最常用的数据运算有5种：种：插入、删除、修
9、改、查找、排序插入、删除、修改、查找、排序1.3 数据类型数据类型 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？抽象数据类型如何定义？抽象数据类型如何定义？3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？讨论：讨论：1、数据类型与抽象数据类型的区别？、数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特征它与数据类型实质上是一个概念，但其特征是是使用与实现分离使用与实现分离，实行，实行封装
10、封装和和信息隐蔽信息隐蔽（独立于计算机）。（独立于计算机）。2、抽象数据类型如何、抽象数据类型如何定义定义？抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示：ADT=（D，S，P）数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象：数据数据关系关系：基本基本操作操作 ：ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式3、抽象数据类型如何、抽象数据类型如何表示和实现表示和实现？抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注注1：它有些类似它有些
11、类似C C语言中的语言中的结构（结构（struct)struct)类型类型，但增加了相关的但增加了相关的服务服务。注注2：教材中用的是教材中用的是类类C C语言（介于伪码和语言（介于伪码和C C语言之语言之间）作为描述工具。间）作为描述工具。但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等1.4 算法和算法分析算法和算法分析1.什么是算法？如何评判一个算法的好坏？什么是算法？如何评判一个算法的好坏？2.时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？3.计算举例计算举例讨论：讨论：程序设计实质好算法好结构程序设计实质好算法好结构答：算法是解决某一特
12、定类型问题的答：算法是解决某一特定类型问题的有限运算序列有限运算序列。是一系。是一系列输入转换为输出的列输入转换为输出的计算步骤计算步骤。常用常用时间复杂度时间复杂度来衡量来衡量1.什么是算法？如何评判一个算法的好坏？什么是算法？如何评判一个算法的好坏？算法有算法有5个基本特性：个基本特性：算法评价有算法评价有5个指标：个指标：有穷性、确定性、可行性、输入和输出有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性、健壮性运行时间、占用空间、正确性、健壮性和可读性和可读性常用常用空间复杂度空间复杂度来衡量来衡量例：分析以下程序段的时间复杂度。例：分析以下程序段的时间复杂度。i=1;whi
13、le(i=n)i=i*2;该算法的运行时间由程序中所有语句的该算法的运行时间由程序中所有语句的频度频度（即该语（即该语句重复执行的次数）句重复执行的次数）之和之和构成。构成。解：解：分析：分析：显然，语句显然，语句的频度是的频度是1。设语句。设语句2的频度是的频度是f(n)，则有：，则有：nnf)(2即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)算法的时间复杂度是由算法的时间复杂度是由嵌套最深层嵌套最深层语句的频度决定的。语句的频度决定的。3、空间复杂性（、空间复杂性（Spac
14、e Complexity）算法运行中占用空间包括算法本身占用，输入输出数据算法运行中占用空间包括算法本身占用，输入输出数据占用和运行中的临时占用。占用和运行中的临时占用。同一个问题，算法不同，运行中的临时空间不同，即空同一个问题，算法不同，运行中的临时空间不同，即空间复杂性不同。间复杂性不同。C只考虑在运行中为局部变量分配的存贮空间的大小，只考虑在运行中为局部变量分配的存贮空间的大小，一般也以数量级表示。一般也以数量级表示。时间复杂度时间复杂度T(n)按数量级递增顺序为：按数量级递增顺序为：注注1：O（）为渐近符号（）为渐近符号。注注2：空间复杂度空间复杂度S(n)按数量级递增顺序也与上按数量
15、级递增顺序也与上表类同。表类同。复杂度高复杂度高复杂度低复杂度低渐进符号渐进符号（O）的定义：）的定义：当且仅当存在一个正的常当且仅当存在一个正的常数数C C，使得对所有的，使得对所有的 n n n n0 0 ，有，有 f(n)f(n)C Cg(n)g(n)，则则f(n)=f(n)=O O(g(n)(g(n)3n+2=O(n)/*3n+2 4n for n 2*/3n+3=O(n)/*3n+3 4n for n 3*/100n+6=O(n)/*100n+6 101n for n 10*/10n2+4n+2=O(n2)/*10n2+4n+2 11n2 for n 5*/6*2n+n2=O(2n)/*6*2n+n2 7*2n for n 4*/例：例：
