余莉 1236 首页 > 课程总览 > 信息技术学院 > 数据结构

Presentation on theme: "余莉 1236 首页 > 课程总览 > 信息技术学院 > 数据结构"— Presentation transcript:

1 余莉 1236 yuli110@126.com 首页 > 课程总览 > 信息技术学院 > 数据结构
数 据 结 构 余莉 1236 首页 > 课程总览 > 信息技术学院 > 数据结构

2 算法+数据结构 = 程序设计 首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。
数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。

3 ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest )
怎么学好数据结构？ 学习 看完一个数据结构后用C语言将其实现 一定要开始时自己实现，被卡住了就看一下源码，看看自己被卡在了什么地方 刚开始看时肯定会有些不清楚，因为你是刚学完C语言 运用 google上搜索“某个数据结构 + ACM”,每种数据结构做5题左右 深入 ACM大赛 做项目 ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest )

4 成绩构成 闭卷笔试 总评成绩：平时50%，期末考试50% 平时成绩50% 的构成 考勤(10%) 实验(10%) 作业(10%)
期中测试(20%)

5 第一章 概 论 1.1 数据结构的基本概念和术语 1.2 数据类型和抽象数据类型 1.3 算法和算法分析

6 例1、求 n 个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。
例2、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。 例3、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？这是一个讨论图的生成树的问题。

7 （a）城市距离图 （b）联通各城市最小生成树 A B H I G C E D F 18 12 9 79 52 56 31 10 85 98
67 21 45 8 34 （a）城市距离图 A B H I G C E D F 12 9 79 31 10 21 8 34 （b）联通各城市最小生成树

8 例4 某电信公司的市话用户信息表格如下图所示：
例4 某电信公司的市话用户信息表格如下图所示： 序号 用户名 电话号码 用户住址 街道名 门牌号 00001 万方林 北京西路 1659 00002 吴金平 2099 00003 王 冬 瑶湖大道 1987 00004 王 三 2008 00005 江 凡 学府大道 5035

9 这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位。
使用计算机处理用户信息表中的数据时，必须弄清楚下面3个问题： 逻辑结构 存储机构 运算

10 1 数据的逻辑结构 2 数据的存储结构 这些数据之间有什么样的内在联系？
除最前和最后两个结点之外，表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点，也有且仅有一个和它相邻位于它之后的一个结点，这些就是用户信息表的逻辑结构。 2 数据的存储结构 将用户信息表中的所有结点存入计算机时，就必须考虑存储结构，使用C语言进行设计时，常见的方式是用一个结构数组来存储整个用户信息表。数据在计算机的存储方式称为存储结构。

11 3 数据的运算集合 数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用户等操作。为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。 对待处理的数据，只有分析清楚上面3个方面的问题，才能进行有效的处理！ 数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。

12 找95 找35 基于这个二维表格，我们可以在上面执行的操作有：增加一个元素，删除元素，查找元素等。
存在的问题：线性查找的效率较低(等概率情况下为n/2)。数组存储时插入一个元素与删除一个元素效率较低。 解决办法：改变数据存储结构，在新的存储结构上开发新的算法。 找35 找95

13 1.1.2数据的逻辑结构 数据的逻辑结构是数据和数据之间所存在的逻辑关系，它可以用一个二元组 B=（K，R）
来表示，其中K是数据、即结点的有限集合；R是集合K上关系的有限集合，这里的关系是从集合K到集合K的关系，这里一般只涉及到一个关系的逻辑结构。

14 1.1.2数据的逻辑结构 例如，有5个人，分别记为a,b,c,d ,e,其中a是b的父亲，b是c的父亲，c是d的父亲,d是e的父亲，如果只讨论他们之间所存在的父子关系，则可以用下面的二元组形式化地予以表达。 B=（K，R） 其中：K={a,b,c,d,e} R={r} r={<a, b>,<b,c>, <c, d>,<d,e>}

15 逻辑结构的图形表示方式，对K中的每个结点ki用一个方框表示，而结点之间的关系用带箭头的线段表示，这5人之间的逻辑结构用图形的方式表达如下图所示。
线性逻辑结构 a b c d e 若ki∈K，kj∈ K，<ki ,kj > ∈r，则称ki是kj的相对于关系r的前驱结点，kj是ki的相对于关系r的后继结点。

16 二、树型结构 结构中的数据元素之间存在一对多的关系。
二、树型结构 结构中的数据元素之间存在一对多的关系。 三、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 A B H I G C E D F 18 12 9 79 52 56 31 10 85 98 67 21 45 8 34 （a）城市距离图

17 1.1.3数据的存储结构 数据的逻辑结构是独立于计算机的，它与数据在计算机中的存储无关， 要对数据进行处理，就必须将数据存储在计算机中
对于一个数据结构B=（K，R），必须建立从结点集合到计算机某个存储区域M的一个映象，这个映象要直接或间接地表达结点之间的关系R。数据在计算机中的存储方式称为数据的存储结构。 数据的存储结构主要有4种。

18 1 顺序存储 顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域M的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。 对于一个数据结构B=（K，R） 其中K={k1,k2,k3,k4,k5,k6,k7,k8,k9} R={r} r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,k8>,<k8,k9>} 它的顺序存储方式如图所示:

19 特点：用物理相邻的位置关系表示其逻辑关系
存储地址 M k1 k2 k3 k6 k5 k4 k7 k8 k9 特点：用物理相邻的位置关系表示其逻辑关系 1001 1002 1003 1004 1005 1006 1007 1008 1009

20 2 链式存储 链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。 例，数据的逻辑结构B=（K，R） 其中 K={k1,k2,k3,k4,k5} R={r} r={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>} 这是一个线性结构，它的链式存储如图所示。

21 特点:逻辑上相邻物理上不一定相邻。 存储地址 info next 1000 1001 1002 1003 1004 1005 1006
k4 1006 k2 1007 k1 1003 k5 ∧ k3 1005 1000 1001 1002 1003 1004 1005 1006 1007 1008

22 3 索引存储 在线性结构中，设开始结点的索引号为1，其它结点的索引号等于其前继结点的索引号加1，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号确定该结点的存储地址。 4 散列存储 散列存储的思想是构造一个从集合K到存储区域M的一个函数h，该函数的定义域为K，值域为M，K中的每个结点ki在计算机中的存储地址由h(ki)确定。

23 1.1.4数据的运算集合 对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存储结构。
数据的运算集合要视情况而定，一般而言，数据的运算包括插入、删除、检索、输出、排序等。 插入：在一个结构中增加一个新的结点。 删除：在一个结构删除一个结点。 检索：在一个结构中查找满足条件的结点。 输出：将一个结构中所有结点的值打印、输出。 排序：将一个结构中所有结点按某种顺序重新排列。

24 1.2数据类型和抽象数据类型 在程序设计中，数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段。 从无类型的二进制数到基本数据类型的产生 从基本数据类型到用户自定义类型的产生 从用户自定义类型到抽象数据类型的出现

25 数据类型：在一种程序设计语言中，变量所具有的数据种类。在C语言中：
基本类型：整型、浮点型、字符型 构造类型：数组、结构体、联合、指针、枚举型、自定义 数据对象：某种数据类型元素的集合。 例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…} 英文字符类型的数据对象是{A，B，C，D，E，F，…}

26 抽象数据类型描述的一般形式如下： ADT 抽象数据类型名称 { 数据对象： …… 数据关系： 操作集合： 操作名1： 操作名n：

27 1.3 算法和算法分析 1.3.1算法 为了求解某问题，必须给出一系列的运算规则，这一系列的运算规则是有限的，表达了求解问题方法和步骤，这就是一个算法。 一个算法可以用自然语言描述，也可以用高级程序设计语言描述，也可以用伪代码描述。本书采用C语言对算法进行描述。

28 算法具有五个基本特征： ①有穷性，算法的执行必须在有限步内结束。 ②确定性，算法的每一步骤必须是确定无二义性的。 ③输入， 算法可以有0个或多个输入。 ④输出， 算法一定有输出结果 ⑤可行性，算法中的运算都必须是可以实现的。 算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。

29 1.3.2算法的时间和空间复杂性 一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。

30 评价一个算法的一般作法： （1）合理地选择一个或几个操作作为“标准操作”。 （2）计算量=给定输入下执行标准操作的次数。 事实：一个算法的计算量通常依赖于问题的规模。 为了便于讨论，我们把问题规模假定为n，则算法在问题规模（Size）为n的输入下的计算量为T(n)

31 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，当n趋向无穷大时，我们把时间复杂度T(n)=O(f(n))的数量级（阶）称为算法的渐近时间复杂度。
例2：求两个n阶方阵的乘积C=A*B for(i=0;i<n;++i) for(j=0;j<n;++j) { c[i][j]=0; for(k=0;k<n;++k) c[i][j]+=a[i][k]*b[k][j]; } n n2 n2 n3 n3

32 上述n阶矩阵相乘算法的时间复杂度T（）为算法中所有语句的频度之和： T（n）=2n3+2n2+n 按照O记法，当n趋向无穷大时有：
limT（n）/n3=lim（ 2n3+2n2+n ）/n3=2 这表明，当n充分大时，T（n）和n3之比是一个不等于0的常数，即T（n）和n3是同阶的，所以: T(n)=O(n3) n→ ∞ n→ ∞ 频度：是指该语句重复执行的次数。

33 例3： { ++x；s=0； } 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)，即常量阶。 例4： for（i=1；i<=n；++i） { ++x；s+=x；} 语句频度为：2n　其时间复杂度为：O（n） 即时间复杂度为线性阶。

34 例5 for（i=1；i<=n；++i）
　　　　for（j=1；j<=n；++j） { ++x；s+=x；} 语句频度为：2n2　其时间复杂度为：O(n2) 即时间复杂度为平方阶。 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0 是一个m次多项式，则A(n)=O(nm )

35 以下六种计算算法时间的多项式是最常用的。其关系为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3) 指数时间的关系为： O(2n)<O(n!)<O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。

36 O(Log n) 如果在一个大小为n循环中，循环变量按照一个常量C的进行倍数的递增或递减，这个循环的复杂度就为O(Log  n). for (int i = 1; i <=n; i *= c) {       // some O(1) expressions  }  for (int i = n; i > 0; i /= c) {

37 下面的表格给出了一些具体函数的O()的表示，如图所示。
f(n) O(g(n)) 量级 35 O(1) 常数阶 2n+7 O(n) 线性阶 n2+10 O(n2) 平方阶 2n3+n O(n3) 立方阶

38 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：
void bubble-sort(int a[]，int n) for(i=n-1,change=1;i>1 && change;--i) { change=0; for(j=0;j<i;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=1;} } 最好情况：0次 （原有数据有序时）

39 算法的时间复杂性不仅和问题的规模大小有关，还与问题数据的初始状态有关。 这样就有了算法在最好、最坏以及在平均状态下的时间复杂性的概念。
最坏情况：1+2+3+…+n-1=n(n-1)/2 平均时间复杂度为:O(n2) 算法的时间复杂性不仅和问题的规模大小有关，还与问题数据的初始状态有关。 这样就有了算法在最好、最坏以及在平均状态下的时间复杂性的概念。 ①算法在最好情况下的时间复杂性是指算法计算量的最小值。 ②算法在最坏情况下的时间复杂性是指算法计算量的最大值。 ③算法的平均情况下的时间复杂性是指算法在所有可 能的情况下的计算量经过加权计算出的平均值。

40 平均情况和最坏情况 Best Case Running Time: 同样的输入规模，不同的数据分布情况下，最快情况的运行时间。
Worst Case Running Time: 同样的输入规模，不同的数据分布情况下，最慢或运行步数最多时的运行时间。 Average Case Running Time: 同样的输入规模，不同的数据分布情况下，平均所需的运行时间，通常指概率平均或期望值 。

41 算法的存储空间需求 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n)) 其中n为问题的规模(或大小) 本书在对算法进行分析时，会用到如下两个记号： x：表示不大于x的最大整数； x：表示不小于x的最小整数。

42 习题1： 1.2 数据结构涉及哪几个方面？ 1.5 数据结构的存储方式有哪几种？

43 1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。
（1）i++; （2）for(i=0;i<n;i++) if (a[i]<x)x=a[i]; （3）for(i=0;i<n;i++) for(j=0;j<n;j++) printf("%d",i+j); （4）for (i=1;i<=n-1;i++) { k=i; for(j=i+1;j<=n;j++) if(a[j]>a[j+1]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; } （5）for(i=0;i<n;i++) {++x;s=s+x;}

44 预备实验：C语言知识回顾 输入n个整数，输出其中与平均值最接近的元素的值及下标。
要求定义下面功能函数，并在main函数中调用这些函数实现题目要求的功能： 1.double getAvg(int a[],int n) 功能：求数组a中n个数的平均值。 2.int getIndex(int a[],int n, double x) 功能：获取与x的值最接近的数组元素的下标。

45 任务2 若有一文本文件records.txt中已存储学生身高表，每个学生信息包括学号和身高两个数据项，编程要求从文件获取学生身高表后，按身高从低到高的顺序排序后在屏幕上打印学生身高表。 要求定义下面功能函数，并在main函数中调用这些函数实现题目要求的功能： 1. int getRecs(STUDENTS s[ ]); 功能：从文件records.txt 中读数据到结构体数组s中，并返回人数n。 2. void sort(STUDENTS s[ ],int n); 功能：对结构体数组s按身高从低到高排序。