数据结构-第1章课件

2011年春季数据结构和算法DataStructure青岛理工大学通信学院2011年春季数数据结构-第1章课件芯片无所不在的时代日本地震对中国汽车业影响：主要存在问题的是微处理器芯片短缺(日立)芯片无所不在的时代芯片的广泛使用导致编程无所不在普通机床数控机床芯片的广泛使用导致编程无所不在普通机床数控机床您将来到社会做什么？如何生存呢？您将来到社会做什么？如何生存呢？您需要编程序吗？

90%的可能性。

您需要了解程序和相关的实现吗？

100%的可能性。

您需要编程序吗？

90%的可能性。

您需要了解程序和相关课前的话---通信专业学生学习数据结构的意义从实用的角度讲，通信无非是做硬件或做软件，两者都要用到数据结构。因为任何一个系统里都有数据，如何合理有效地组织数据，使系统速度更快，数据访问方式更灵活，这都严重依赖于是否选择了合适的数据结构。从专业课程的角度讲，数据结构的知识点在后继课程中会用到，例如《计算机通信与网络》、《信息论与编码》、《现代通信与技术》等等。从就业的角度，从以往学生的情况来看，从事软件开发是一个比较容易找到工作的出口。课前的话---通信专业学生学习数据结构的意义从实用的角度讲，学时数：32（24＋8）学分：

2教材：严蔚敏、吴伟民，数据结构（C语言版），清华大学出版社，1997年4月第1版和2007年第二版都行参考书：[1]严蔚敏、吴伟民、米宁，数据结构题集（C语言版），清华大学出版社，1999年7月学时数：32（24＋8）师生沟通渠道：许小可Email:xiaokeeie@如何看待不同老师的作用：与时俱进师生沟通渠道：许小可内容安排内容安排考试成绩平时成绩（20%）（考勤、作业）上机+综合程序设计（30%）期末考试（50%）考试成绩平时成绩（20%）课程要求第一层次：每种数据结构的适用性第二层次：每种数据结构和算法的白话实现第三层次：每种数据结构和算法的C语言编程实现思考题：数据结构的学习是否依赖于编程语言？这门课和C语言程序设计的关系是什么？课程要求第一层次：每种数据结构的适用性第1章绪论第2章线性表第3章栈和队列

第4章串第5章数组和广义表第6章树和二叉树

第7章图第9章查找第10章排序目录第1章绪论目录第一章绪论讨论5个问题：1.1什么是数据结构1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4什么是抽象数据类型1.5算法效率的度量第一章绪论讨论5个问题：1.1什么是数据结构1.1什么是数据结构例某人骑自行车从A地先以每小时12千米的速度下坡后，以每小时9千米的速度走平路到B地，共用55分钟.回来时，他以每小时8千米的速度通过平路后，以每小时4千米的速度上坡，从B地到A地共用1.5小时，求A、B两地相距多少千米？答案：设坡路长为x千米，A、B两地相距为y千米，依题意列如下方程组：求解步骤：审题→设未知元→列方程→解方程→检验→作结论建立数学模型设计算法建立数学模型设计算法编程测试调整数值计算问题操作对象：实型、整型、布尔型数据数学模型：数学方程式（计算机的主要操作是解方程）1.1什么是数据结构例某人骑自行车从A地先以每小时12千米1.1.1非数值计算问题例1学生信息管理问题线性1.1.1非数值计算问题例1学生信息管理问题线性人机对弈背景资料卡斯帕罗夫与“深蓝”对弈(右为“深蓝”操作者)“人机对弈”诸宸最终负于紫光之星

人机对弈背景资料卡斯帕罗夫与“深蓝”对弈(右为“深蓝”操作者例2人机对奕问题树………………………………非数值计算问题例2人机对奕问题树………………非数值计算问题非数值计算问题例3田径赛时间安排问题例3田径赛时间安排问题问题：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如表1所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。表1非数值计算问题例3田径赛时间安排问题例3田径赛时间安排（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边（3）某选手比赛的项目必定有边相连（不能同时比赛）AEBFDCAEBFDC图表3表2解法：（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目（3）某选手比赛的项目必定有边相连A1.1.2数据结构学科定义数学软件硬件数据结构是一门学科，它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系（数学模型）和操作等等。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。1.1.2数据结构学科定义数学软件硬件数据结构是一门学科，它1.1.3术语简介:数据、数据元素、数据项数据(data)——对客观事物的符号表示，所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目，是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据>数据元素>数据项1.1.3术语简介:数据、数据元素、数据项数据(data)—1.1.4基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的

集合，表示为：Data_Structure=（D,R）元素有限集关系有限集（数值或非数值）数据对象(dataobject)---是性质相同的数据元素的集合，是数据的一个子集。例如，字母字符对象是集合C={‘A’,’B’,…,’Z’}结构是指同一数据元素类型中各元素之间存在的关系的集合。1.1.4基本概念数据结构是相互之间存在一种或多种特定关系的数据结构是带结构的数据元素的集合.思考：数据结构和算法之间的关系数据结构是带结构的数据元素的集合.思考：数据结构和算法之间的例在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

数据结构示例例在2行3列的二维数组{a1,a2,a3,a4,a1.2学习数据结构的意义选择合适的数据结构解决应用问题程序设计=好算法+好结构例学生信息查询问题

计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。索引表1.2学习数据结构的意义选择合适的数据结构解决应用问题程序设1.3数据结构涵盖的内容1.3数据结构涵盖的内容集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性逻辑结构可细分为4类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。解释1：什么叫数据的逻辑结构？集合结构：仅同属一个集合非线性线性逻辑结构可细分为4类：（1）S=(D,R)

D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。课堂练习（1）S=(D,R)解：上述表达式可用图形表示为：b课堂练习（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}解：上述表达式可用图形表示为：

d1d5d2d4d3该结构是非线性的。课堂练习（2）S=(D,R)

解释2：什么叫数据的存储结构？

答：存储结构（亦称物理结构），是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。“数据元素”的映像？“关系”的映像？解释2：什么叫数据的存储结构？答：存储结构（亦称物理结用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=数据元素的映象方法：从黑客帝国说起数据元素的映象方法：从黑客帝国说起数据结构-第1章课件隐喻黑客帝国讲了个啥事呀？那盗梦空间呢？隐喻黑客帝国讲了个啥事呀？存储结构可分为4大类：顺序、链式、索引、散列顺序存储结构——借助元素在存储器中的相对位 置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表 示数据元素间的逻辑关系关系的映象方法：（表示x,y的方法）存储结构可分为4大类：顺序、链式、索引、散列顺序存储结构——元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=L0+（i-1)*m顺序存储元素n……..元素i……..元素2元素1LoLo+mLo+(1536元素21400元素11346元素3∧元素41345h

链式存储

1536元素21400元素11346元素3∧元素41345答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构答：在数据的逻辑结构上定义的操作算法。最常用的数据运算有51.4什么是抽象数据类型1.4.1数据类型与抽象数据类型的区别？1.4.2抽象数据类型如何定义？1.4.3抽象数据类型如何表示和实现？

讨论：抽象数据类型和C伪码是学习数据结构的工具1.4什么是抽象数据类型1.4.1数据类型与抽象数据数据类型—高级语言中指数据变量的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;1.4.1数据类型与抽象数据类型的区别数据类型—高级语言中指数据变量的取值范围及其上可进行的操作的【例】从键盘输入两个整数，输出它们的和。

#include<stdio.h>main() { inta,b,c,d;//a,b,c,d是四个整型变量，分别 对应于内存中一块16bit的区 域，取值范围为-215~215-1；

printf("输入两个整数：");scanf("%d%d",&a,&b);c=a+b;//”+”和”-”是int型变量的操作；

d=a-b;printf("和=%d\n",c); }【例】从键盘输入两个整数，输出它们的和。1.4.1数据类型与抽象数据类型的区别数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。但是范畴更广，包括用户在设计软件系统时自己定义的数据类型，可用于软件复用。抽象的意义在于数据类型的数学抽象特性。1.4.1数据类型与抽象数据类型的区别数据类型：是一个值1.4.2抽象数据类型如何定义抽象数据类型可以用以下的三元组来表示：

ADT=（D，R，P）ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集1.4.2抽象数据类型如何定义抽象数据类型可以用以下的三ADT有两个重要特征:数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。ADT有两个重要特征:数据抽象用ADT描述例如，抽象数据类型复数的定义：

数据对象：

D＝{e1,e2｜e1,e2∈RealSet}

数据关系：

R1＝{<e1,e2>|e1是复数的实数部分

|e2是复数的虚数部分}ADTComplex{例如，抽象数据类型复数的定义：数据对象：ADT基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。基本操作：AssignComplex(&Z,v1

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplexGetImag(Z,&ImagPart)Add假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果假设:z1和z2是上述定义的复数则Add(z1,z2,1.4.3抽象数据类型如何表示和实现但上机时要用具体语言实现，如C或C++等抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用类C语言（介于伪码和C语言之间）作为描述工具。其描述语法汇总在教材P10-11上。思考1：数据结构的学习依赖于编程语言吗？思考2：哪门语言是最好的编程语言？1.4.3抽象数据类型如何表示和实现但上机时要用具体语言提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。提示：1.5算法效率的度量1.5.1什么是算法？如何评判算法的好坏？1.5.2时间复杂度和空间复杂度如何表示？1.5.3计算举例讨论：1.5算法效率的度量1.5.1什么是算法？如何评判1.5.1什么是算法？如何评判一个算法的好坏？常用时间复杂度来衡量算法的基本特性：算法评价指标：有穷性、确定性、可行性、输入、输出正确性、可读性、健壮性、效率与低存储量需求常用空间复杂度来衡量程序设计的实质：好算法＋好结构

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。4个层次例1.4、例1.51.5.1什么是算法？如何评判一个算法的好坏？常用时间复例1.4一个不是算法的例子(1)begin(2)n<=0(3)n=n+1(4)repeat(3)(5)end例1.5一个不超过100次计数的算法(1)begin(2)n<=0(3)n=n+1(4)ifn=100do(5),elserepeat(3)(5)outputn(6)end例1.4一个不是算法的例子例1.5一个不超过10用依据该算法编制的程序在计算机上执行所消耗的时间来度量。算法效率：1.事后统计：利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。

缺点：必须先运行依据算法编制的程序。所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。2.事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度用依据该算法编制的程序在计算机上执行所消耗的时间来度量。算法设解决一个问题的规模为n（比如排序问题中，n表示待排序元素的个数；在矩阵运算中，n表示矩阵的阶数；在图的遍历中，n表示图中的顶点数），那么算法的时间量度可记为T(n).当n不断变化时,T(n)也会不断变化,但有时我们想知道它变化时呈什么规律.一般情况下,

T(n)与算法中简单操作执行次数之和f(n)成正比。注：O（）为渐近符号，表示T(n)与f(n)是同数量级函数。可记作：T(n)=O(f(n))1.5.2时间复杂度和空间复杂度如何表示？设解决一个问题的规模为n（比如排序问题中，n表示待排序元素的3n+2=O(n)因为3n+24nforn26*2n+n2=O(2n)因为6*2n+n2

7*

2nforn4例：渐进符号（O）的形式定义：当且仅当存在一个正的常数M，使得对所有的

nn0

，有|x(n)||Mf(n)|，则：x(n)=O(f(n))3n+2=O(n)因为3n+24n什么是同数量级函数？若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。例如，若T(n)=n(n+1)/2,则有1/4≤T(n)/n2≤1，故可以说，辅助函数f(n)=n2是Ｔ(n)的同数量级函数。什么是同数量级函数？若有某个辅助函数f(n),使得当n趋近于注：空间复杂度S(n)按数量级递增顺序也与上表类似。复杂度高复杂度低时间复杂度T(n)按数量级递增顺序为：1.5.2时间复杂度和空间复杂度如何表示？多项式阶注：空间复杂度S(n)按数量级递增顺序也与上表类似。复杂度1.5.3计算举例该算法的运行时间由程序中所有简单语句的频度（即该语句重复执行的次数）之和构成。解：分析：显然，语句①的频度是1。设语句2的频度是g(n)，则有：算法的时间复杂度由嵌套最深层语句的频度决定例1：分析以下程序段的时间复杂度。i=1;①while(i<=n)i=i*2;②即g(n)≤log2n，取最大值g(n)=log2n所以该程序段的时间复杂度T(n)=1+g(n)=1+log2n=

O(log2n)1.5.3计算举例该算法的运行时间由程序中所有简单语句例2分析以下程序段的时间复杂度 for(i=1;i<n;i++) {y=y+1; for(j=0;j<=(2*n);j++) x++; }/*1*//*2*/例2分析以下程序段的时间复杂度/*1*//分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：则该程序段的时间复杂度： T(n)=分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语

空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n))我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。

数据结构-第1章课件时间和空间复杂性之间的关系：用空间来换时间，这是并发信号处理的核心思想。

数据结构-第1章课件本章小结数据结构课程——数据结构＋算法＝程序，涉及数学、计算机硬件和软件。数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。数据结构内容——数据的逻辑结构、存储结构和基本运算

数据结构学习工具——抽象数据类型和伪码（类C）算法效率指标——时间效率和空间效率第1章结束本章小结数据结构课程——数据结构＋算法＝程序，涉及数学、计

2011年春季数据结构和算法DataStructure青岛理工大学通信学院2011年春季数数据结构-第1章课件芯片无所不在的时代日本地震对中国汽车业影响：主要存在问题的是微处理器芯片短缺(日立)芯片无所不在的时代芯片的广泛使用导致编程无所不在普通机床数控机床芯片的广泛使用导致编程无所不在普通机床数控机床您将来到社会做什么？如何生存呢？您将来到社会做什么？如何生存呢？您需要编程序吗？

90%的可能性。

您需要了解程序和相关的实现吗？

100%的可能性。

您需要编程序吗？

90%的可能性。

您需要了解程序和相关课前的话---通信专业学生学习数据结构的意义从实用的角度讲，通信无非是做硬件或做软件，两者都要用到数据结构。因为任何一个系统里都有数据，如何合理有效地组织数据，使系统速度更快，数据访问方式更灵活，这都严重依赖于是否选择了合适的数据结构。从专业课程的角度讲，数据结构的知识点在后继课程中会用到，例如《计算机通信与网络》、《信息论与编码》、《现代通信与技术》等等。从就业的角度，从以往学生的情况来看，从事软件开发是一个比较容易找到工作的出口。课前的话---通信专业学生学习数据结构的意义从实用的角度讲，学时数：32（24＋8）学分：

2教材：严蔚敏、吴伟民，数据结构（C语言版），清华大学出版社，1997年4月第1版和2007年第二版都行参考书：[1]严蔚敏、吴伟民、米宁，数据结构题集（C语言版），清华大学出版社，1999年7月学时数：32（24＋8）师生沟通渠道：许小可Email:xiaokeeie@如何看待不同老师的作用：与时俱进师生沟通渠道：许小可内容安排内容安排考试成绩平时成绩（20%）（考勤、作业）上机+综合程序设计（30%）期末考试（50%）考试成绩平时成绩（20%）课程要求第一层次：每种数据结构的适用性第二层次：每种数据结构和算法的白话实现第三层次：每种数据结构和算法的C语言编程实现思考题：数据结构的学习是否依赖于编程语言？这门课和C语言程序设计的关系是什么？课程要求第一层次：每种数据结构的适用性第1章绪论第2章线性表第3章栈和队列

第4章串第5章数组和广义表第6章树和二叉树

第7章图第9章查找第10章排序目录第1章绪论目录第一章绪论讨论5个问题：1.1什么是数据结构1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4什么是抽象数据类型1.5算法效率的度量第一章绪论讨论5个问题：1.1什么是数据结构1.1什么是数据结构例某人骑自行车从A地先以每小时12千米的速度下坡后，以每小时9千米的速度走平路到B地，共用55分钟.回来时，他以每小时8千米的速度通过平路后，以每小时4千米的速度上坡，从B地到A地共用1.5小时，求A、B两地相距多少千米？答案：设坡路长为x千米，A、B两地相距为y千米，依题意列如下方程组：求解步骤：审题→设未知元→列方程→解方程→检验→作结论建立数学模型设计算法建立数学模型设计算法编程测试调整数值计算问题操作对象：实型、整型、布尔型数据数学模型：数学方程式（计算机的主要操作是解方程）1.1什么是数据结构例某人骑自行车从A地先以每小时12千米1.1.1非数值计算问题例1学生信息管理问题线性1.1.1非数值计算问题例1学生信息管理问题线性人机对弈背景资料卡斯帕罗夫与“深蓝”对弈(右为“深蓝”操作者)“人机对弈”诸宸最终负于紫光之星

人机对弈背景资料卡斯帕罗夫与“深蓝”对弈(右为“深蓝”操作者例2人机对奕问题树………………………………非数值计算问题例2人机对奕问题树………………非数值计算问题非数值计算问题例3田径赛时间安排问题例3田径赛时间安排问题问题：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如表1所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。表1非数值计算问题例3田径赛时间安排问题例3田径赛时间安排（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边（3）某选手比赛的项目必定有边相连（不能同时比赛）AEBFDCAEBFDC图表3表2解法：（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目（3）某选手比赛的项目必定有边相连A1.1.2数据结构学科定义数学软件硬件数据结构是一门学科，它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系（数学模型）和操作等等。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。1.1.2数据结构学科定义数学软件硬件数据结构是一门学科，它1.1.3术语简介:数据、数据元素、数据项数据(data)——对客观事物的符号表示，所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目，是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据>数据元素>数据项1.1.3术语简介:数据、数据元素、数据项数据(data)—1.1.4基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的

集合，表示为：Data_Structure=（D,R）元素有限集关系有限集（数值或非数值）数据对象(dataobject)---是性质相同的数据元素的集合，是数据的一个子集。例如，字母字符对象是集合C={‘A’,’B’,…,’Z’}结构是指同一数据元素类型中各元素之间存在的关系的集合。1.1.4基本概念数据结构是相互之间存在一种或多种特定关系的数据结构是带结构的数据元素的集合.思考：数据结构和算法之间的关系数据结构是带结构的数据元素的集合.思考：数据结构和算法之间的例在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

数据结构示例例在2行3列的二维数组{a1,a2,a3,a4,a1.2学习数据结构的意义选择合适的数据结构解决应用问题程序设计=好算法+好结构例学生信息查询问题

计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。索引表1.2学习数据结构的意义选择合适的数据结构解决应用问题程序设1.3数据结构涵盖的内容1.3数据结构涵盖的内容集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性逻辑结构可细分为4类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。解释1：什么叫数据的逻辑结构？集合结构：仅同属一个集合非线性线性逻辑结构可细分为4类：（1）S=(D,R)

D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。课堂练习（1）S=(D,R)解：上述表达式可用图形表示为：b课堂练习（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}解：上述表达式可用图形表示为：

d1d5d2d4d3该结构是非线性的。课堂练习（2）S=(D,R)

解释2：什么叫数据的存储结构？

答：存储结构（亦称物理结构），是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。“数据元素”的映像？“关系”的映像？解释2：什么叫数据的存储结构？答：存储结构（亦称物理结用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=数据元素的映象方法：从黑客帝国说起数据元素的映象方法：从黑客帝国说起数据结构-第1章课件隐喻黑客帝国讲了个啥事呀？那盗梦空间呢？隐喻黑客帝国讲了个啥事呀？存储结构可分为4大类：顺序、链式、索引、散列顺序存储结构——借助元素在存储器中的相对位 置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表 示数据元素间的逻辑关系关系的映象方法：（表示x,y的方法）存储结构可分为4大类：顺序、链式、索引、散列顺序存储结构——元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=L0+（i-1)*m顺序存储元素n……..元素i……..元素2元素1LoLo+mLo+(1536元素21400元素11346元素3∧元素41345h

链式存储

1536元素21400元素11346元素3∧元素41345答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构答：在数据的逻辑结构上定义的操作算法。最常用的数据运算有51.4什么是抽象数据类型1.4.1数据类型与抽象数据类型的区别？1.4.2抽象数据类型如何定义？1.4.3抽象数据类型如何表示和实现？

讨论：抽象数据类型和C伪码是学习数据结构的工具1.4什么是抽象数据类型1.4.1数据类型与抽象数据数据类型—高级语言中指数据变量的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;1.4.1数据类型与抽象数据类型的区别数据类型—高级语言中指数据变量的取值范围及其上可进行的操作的【例】从键盘输入两个整数，输出它们的和。

#include<stdio.h>main() { inta,b,c,d;//a,b,c,d是四个整型变量，分别 对应于内存中一块16bit的区 域，取值范围为-215~215-1；

printf("输入两个整数：");scanf("%d%d",&a,&b);c=a+b;//”+”和”-”是int型变量的操作；

d=a-b;printf("和=%d\n",c); }【例】从键盘输入两个整数，输出它们的和。1.4.1数据类型与抽象数据类型的区别数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。但是范畴更广，包括用户在设计软件系统时自己定义的数据类型，可用于软件复用。抽象的意义在于数据类型的数学抽象特性。1.4.1数据类型与抽象数据类型的区别数据类型：是一个值1.4.2抽象数据类型如何定义抽象数据类型可以用以下的三元组来表示：

ADT=（D，R，P）ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集1.4.2抽象数据类型如何定义抽象数据类型可以用以下的三ADT有两个重要特征:数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。ADT有两个重要特征:数据抽象用ADT描述例如，抽象数据类型复数的定义：

数据对象：

D＝{e1,e2｜e1,e2∈RealSet}

数据关系：

R1＝{<e1,e2>|e1是复数的实数部分

|e2是复数的虚数部分}ADTComplex{例如，抽象数据类型复数的定义：数据对象：ADT基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。基本操作：AssignComplex(&Z,v1

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplexGetImag(Z,&ImagPart)Add假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果假设:z1和z2是上述定义的复数则Add(z1,z2,1.4.3抽象数据类型如何表示和实现但上机时要用具体语言实现，如C或C++等抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用类C语言（介于伪码和C语言之间）作为描述工具。其描述语法汇总在教材P10-11上。思考1：数据结构的学习依赖于编程语言吗？思考2：哪门语言是最好的编程语言？1.4.3抽象数据类型如何表示和实现但上机时要用具体语言提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。提示：1.5算法效率的度量1.5.1什么是算法？如何评判算法的好坏？1.5.2时间复杂度和空间复杂度如何表示？1.5.3计算举例讨论：1.5算法效率的度量1.5.1什么是算法？如何评判1.5.1什么是算法？如何评判一个算法的好坏？常用时间复杂度来衡量算法的基本特性：算法评价指标：有穷性、确定性、可行性、输入、输出正确性、可读性、健壮性、效率与低存储量需求常用空间复杂度来衡量程序设计的实质：好算法＋好结构

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。4个层次例1.4、例1.51.5.1什么是算法？如何评判一个算法的好坏？常用时间复例1.4一个不是算法的例子(1)begin(2)n<=0(3)n=n+1(4)repeat(3)(5)end例1.5一个不超过100次计数的算法(1)begin(2)n<=0(3)n=n+1(4)ifn=100do(5),elserepeat(3)(5)outputn(6)end例1.4一个不是算法的例子例1.5一个不超过10用依据该算法编制的程序在计算机上执行所消耗的时间来度量。算法效率：1.事后统计：利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。

缺点：必须先运行依据算法编制的程序。所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。2.事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言