首页计算机计算机基础数据结构 01 第一章 绪言.pptx

01 第一章 绪言.pptx

页数:53页文件大小:717.4 KB来源: 数据结构ppt课件

本课件为数据结构第一章绪言,从程序设计一般流程出发说明数据结构的研究对象,结合书目检索、人机对弈、交通灯管理等实例引出线性表、树与图,随后系统讲解数据、数据元素、逻辑结构与存储结构、抽象数据类型等核心术语,并介绍算法的描述方式与效率度量方法。

第一章绪言目录页,列出什么是数据结构、基本概念和术语、算法的描述与算法分析等小节
第一台电子计算机ENIAC照片页,引出第一章绪言中什么是数据结构的问题背景
程序设计一般流程图,展示系统功能分析、建立数学模型、算法设计到编码调试的完整过程
查看本课件的文字版(共 53 页,供检索与复制)

第1页:第一章绪言目录

什么是数据结构基本概念和术语算法的描述和算法分析简介本章小结第一章绪言

第2页:第一台电子计算机ENIAC

1946年,第一台电子计算机ENIACShown here are two women “programming” ENIAC. U.S. Army Photo.第一章绪言§1.1什么是数据结构

第3页:程序设计一般流程

第一章绪言§1.1什么是数据结构系统功能分析建立数学模型抽象算法设计编码调试与测试系统输入/输出数据、功能需求数据对象的表示及之间的关系解决特定问题的具体描述程序设计一般流程程序=数据结构+算法Niklaus Wirth:问题的数学模型处理问题的策略

第4页:数值计算问题求解示例

第一章绪言§1.1什么是数据结构系统功能分析建立数学模型抽象算法设计编码调试与测试程序设计一般流程非数值计算问题数学方程?数值计算问题数值计算问题例已知:长方形游泳池的长len和宽wide,求面积area

  • 建立数学模型:问题涉及的对象:游泳池的长len宽wide,面积area;对象之间的关系:area=len wide——数学模型
  • 设计求解问题的方法
  • 编程main ( ){int len, wide ,area ;
scanf (“%d %d”, &len,&wide);area=len*wide ;printf (“area=%d”,area);}

第5页:例1 书目自动检索系统

登录号:书名:作者名:分类号:出版单位:出版时间:价格:书目卡片书目文件按书名按作者名按分类号索引表例1书目自动检索系统线性表电话号码查询系统学生成绩管理系统职工信息系统等文档管理的数学模型

第6页:例2 人机对弈问题

例2人机对弈问题

第7页:卡斯帕罗夫与深蓝对弈

例2人机对弈问题1996年,卡斯帕罗夫与IBM“深蓝”对弈

第8页:人机对弈的树形结构

……..……..…...…...…...…...例2人机对弈问题树

第9页:例3 多叉路口交通灯:连线

CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题 连线

第10页:多叉路口交通灯:填色

CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题 连线 填色

第11页:多叉路口交通灯:填色过程

CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题

第12页:多叉路口交通灯:填色分组

CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题

第13页:多叉路口交通灯:相位划分

CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题

第14页:多叉路口交通灯的图模型

CEDABABACADBABCBDDADBDCEAEBECED图例3多叉路口交通灯管理问题

第15页:数据结构的定义

数据结构是一门研究非数值计算的程序设计问题中,计算机的操作对象以及它们之间的关系和操作等等的学科。数据结构定义:……..……..…...…...…...…...ABACADBABCBDDADBDCEAEBECED

第16页:数据、数据元素与数据项

§1.2基本概念和术语 数据(data)—所有能输入到计算机中去的描述客观事物的符号 数据元素(data element)—数据的基本单位,也称结点(node)或记录(record) 数据项(data item)—有独立含义的数据最小单位,也称域(field)

第17页:数据结构与逻辑结构

数据元素集合元素间关系集合 数据结构(data structure)—数据元素和数据元素关系的集合Data_Structure = {D, R} 数据的逻辑结构—抽象反映数据元素的逻辑关系 从逻辑关系上描述数据,与数据的存储无关 从具体问题抽象出来的数据模型; 与数据元素本身的形式、内容无关; 与数据元素的相对位置无关。

第18页:数据逻辑结构的分类

数据结构(data structure)—数据元素和数据元素关系的集合Data_Structure = {D, R}

数据的逻辑结构
抽象反映数据元素的逻辑关系数据逻辑结构分为:(
集合)
数据元素间除“同属于一个集合”外,
无其它关系线性结构
一个对一个,如线性表、栈、
队列树形结构
一个对多个,
如树图状结构
多个对多个,如图

第19页:数据的存储结构

数据的存储结构(物理结构)
数据的逻辑结构在计算机存储器中的实现存储结构分为:
顺序存储结构
借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构—借助指示元素存储地址的指针表示数据元素间的逻辑关系

第20页:顺序存储结构示意

元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储内容Loc(元素i)=Lo+(i-1)*m顺序存储数据的顺序存储通过分配连续的存储空间来反映数据元素的逻辑相邻关系逻辑上相邻存储位置也相邻

第21页:链式存储结构示意

∧元素41400元素11536元素21350元素3指针存储内容存储地址1400元素11346∧元素41350…….……..…….1536元素21400…….……..…….1350元素31536链式存储数据的链式存储结构通过指针来反映数据元素的逻辑相邻关系“链”——指示逻辑上与之相邻的元素存储位置头指针1346L

第22页:数据类型

数据类型——一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称例C语言中,提供int, char, float, double等基本数据类型,数组、结构体、共用体、枚举等构造数据类型,还有指针、空(void)类型等。用户也可用typedef自己定义数据类型

typedefstruct{ long num;char name[30];char author[20];char publisher[30];float price;}BOOKCARD;BOOKCARDbook1,book2,*p;

第23页:链表结点的数据类型表示

1536元素21400元素11350元素3∧元素4L数据类型表示?

typedefstruct node{int data;struct node*next;}Lnode, *LinkList;Lnodes;LinkListp;

第24页:抽象数据类型ADT

抽象数据类型(Abstract Data Type,ADT)定义:指一个数学模型及定义在该模型上的一组操作 数据抽象仅取决于它的一组逻辑特性,由基本的数据类型及一组相关操作组成,不考虑数据的存储形式和操作的实现算法 数据封装将数据类型及数据类型上的运算捆绑在一起,进行封装,对外部用户隐藏其内部实现细节ADT抽象数据类型名{数据对象:…数据关系:…基本操作:…}ADT抽象数据类型名ADT形式化定义:

第25页:ADT示例:复数定义

ADT示例抽象数据类型复数的定义:ADTComplex{}ADTComplex 教材中算法采用以抽象数据类型为基础的类C语言。数据抽象:不考虑数据的存储形式和操作的实现算法;数据封装:将数据与操作捆绑在一起数据对象:数据关系:基本操作:D={e1,e2|e1,e2均为实数}R={<e1,e2>|e1是复数的实部,e2是复数的虚部}AssignComplex(&Z,v1,v2):构造复数Z,其实部和虚部分别赋以参数v1和v2的值GetReal(Z,&real):用real返回复数Z的实部值GetImag(Z,&Imag):用Imag返回复数Z的虚部值Add(z1,z2,&sum):用sum返回两个复数z1,z2的和值引用

第26页:引用类型Reference

C++等面向对象程序设计语言为简化复杂的指针操作,提供了引用机制(“&”),即为变量起一个别名,引用名与变量享受同等的访问待遇。(*.cpp支持引用) C语言不支持引用类型。(*.c不支持引用)inta=4;int&x=a; 引用(Reference)x与a占用相同的存储空间变量名a引用x(别名)a=10;10x=8;8变量及其引用是同步变化的

第27页:值传递与swap

引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。

voidswap(intx,inty){inttemp;temp=x;x=y;y=temp;}当用执行语句swap(a,b)时:a和b的值没有发生交换…...…...20002008200A2002200420065变量a变量b9变量y变量x(swap)55959COPY值传递变量temp

第28页:地址传递与swap

当用执行语句swap(&a,&b)时:a和b的值发生了交换地址传递

voidswap(int *x,int *y){inttemp;temp=*x;*x=*y;*y=temp;} 引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。…...…...20002008200A2002200420065变量a变量b9指针y指针x(swap)520002002COPY95变量temp

第29页:引用传递与swap

当用执行语句swap(a,b)时:a和b的值发生了交换引用传递

voidswap(int&x,int&y){inttemp;temp=x;x=y;y=temp;}显然,采用引用方式更为简洁方便。所以教材中很多算法都采用引用形式的形参。 引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。…...…...2000200220042006变量a变量b59变量temp(swap)引用x引用y595

第30页:区分引用与取变量地址

voidswap(int&x,int&y){inttemp;temp=x;x=y;y=temp;} 引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。如何区分&是“引用”还是“取变量地址”??&仅在形参及定义部分表示引用引用inta=4;int&x=a;引用inta=5, b=9;swap(&a,&b);取变量地址

第31页:抽象数据类型的表示与实现

抽象数据类型的表示和实现

typedefstruct{floatrealpart;floatimagpart;}complex;//基本操作:用sum返回两个复数z1,z2的和值voidadd(complexz1,complexz2,complex&sum){sum.realpart =z1.realpart +z2.realpart;sum.imagpart =z1.imagpart +z2.imagpart;}——通过固有数据类型(高级编程语言中已实现的数据类型)来实现。复数的定义

第32页:预定义常量和类型

//预定义常量和类型

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus; 抽象数据类型的表示和实现——通过固有数据类型(高级编程语言中已实现的数据类型)来实现。

第33页:算法及其特性

§1.3算法的描述和算法分析简介

算法(algorithm)
解决某一特定问题的具体步骤的描述,是指令的有限序列
有穷性
算法必须在执行有限步骤后结束
确定性
算法每一步骤必须是确切定义的,不能产生二义性
可行性
算法是能行的
输入
算法有零个或多个输入
输出
算法有一个或多个输出

第34页:算法的评价标准

§1.3算法的描述和算法分析简介 算法的评价—衡量算法优劣的标准正确性:1、程序中不含语法错误;2、程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果;可读性:1、算法应该易于人的理解;2、晦涩难读的算法易于隐藏较多错误而难以调试。健壮性: 1、指当输入数据非法时,算法恰当的做出反应或进行相应处理,而不是产生莫名其妙的输出结果。2、处理出错的方法,不是中断程序,而是返回一个表示错误或错误性质的值,以便进行处理 正确性(correctness) 可读性(readability) 健壮性(robustness) 效率

第35页:算法设计重要性

算法设计重要性例1:在有序表中查找给定值例2:百钱买百鸡问题算法描述与算法分析

第36页:顺序查找

例:数组a中存放从小到大排好序的n个整数,查找给定值k在数组中下标;若查找失败,返回0方法一:顺序查找int search(int a[],int n,int k){ int i=0;

while(a[i]!=k && i<n)i++;if(i>=n) return(0);else return(i);}找64iiiiiii0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 13 19 21 37 56 64 75 80 88 92 100 111 120 125最多比较n次查找成功

第37页:折半查找过程(一)

方法二:折半查找0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 13 19 21 37 56 64 75 80 88 92 100 111 120 125找37lowhighmid例:数组a中存放从小到大排好序的n个整数,查找给定值k在数组中下标;若查找失败,返回0

第38页:折半查找过程(二)

方法二:折半查找0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 13 19 21 37 56 64 75 80 88 92 100 111 120 125找37lowhighmid例:数组a中存放从小到大排好序的n个整数,查找给定值k在数组中下标;若查找失败,返回0

第39页:折半查找过程(三)

方法二:折半查找0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 13 19 21 37 56 64 75 80 88 92 100 111 120 125找37lowhighmid例:数组a中存放从小到大排好序的n个整数,查找给定值k在数组中下标;若查找失败,返回0

第40页:折半查找算法

lowhighmid查找成功73115913610141204812最多比较 log2n +1次方法二:折半查找0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 13 19 21 37 56 64 75 80 88 92 100 111 120 125找37int search(int a[],int n,int k){ int low,high,mid,found;low=0; high=n-1; found=0;

while((low<=high)&&(found==0)){mid=(low+high)/2;if(k>a[mid]) low=mid+1;else if(k==a[mid]) found=1;else high=mid-1;}if(found==1) return(mid);else return(0);}例:数组a中存放从小到大排好序的n个整数,查找给定值k在数组中下标;若查找失败,返回0

第41页:顺序查找与折半查找比较

0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 13 19 21 37 56 64 75 80 88 92 100 111 120 125n比较次数顺序查找折半查找例:数组a中存放从小到大排好序的n个整数,查找给定值k在数组中下标;若查找失败,返回0

第42页:百钱买百鸡:三重循环

百钱买百鸡问题100元钱买100只鸡,母鸡每只5元,公鸡每只3元,小鸡3只1元,问共可以买多少只母鸡、多少只公鸡、多少只小鸡?方法1——用三重循环:

for(i=0; i<=100; i++)for(j=0; j<=100; j++)for(k=0; k<=100;k++){}求解:设母鸡、公鸡、小鸡各为x, y, z只。则有:x + y + z = 1005x + 3y + z/3 = 100只需要解出本方程就可以得到答案。循环次数=101*101*101即约一百万次if(k%3 = = 0&&i+j+k= =100&&5*i+3*j+k/3 = =100)printf(“%d,%d,%d\n”, i,j,k);循环层数太多

第43页:百钱买百鸡:二重循环

百钱买百鸡问题100元钱买100只鸡,母鸡每只5元,公鸡每只3元,小鸡3只1元,问共可以买多少只母鸡、多少只公鸡、多少只小鸡?方法2——用二重循环:z=100-x-yfor(i=0; i<=100; i++)

for(j=0; j<=100; j++){}求解:设母鸡、公鸡、小鸡各为x, y, z只。则有:x + y + z = 1005x + 3y + z/3 = 100只需要解出本方程就可以得到答案。循环次数=101*101即约一万次k=100–i–j ;if(k%3 = = 0&&5*i+3*j+k/3 = =100)printf(“%d,%d,%d\n”, i,j,k);每层循环次数太多

第44页:百钱买百鸡:缩小循环范围

百钱买百鸡问题100元钱买100只鸡,母鸡每只5元,公鸡每只3元,小鸡3只1元,问共可以买多少只母鸡、多少只公鸡、多少只小鸡?方法3——用二重循环:钱100元,母鸡5元1只,所以x<=20,同样,y<=33求解:设母鸡、公鸡、小鸡各为x, y, z只。则有:x + y + z = 1005x + 3y + z/3 = 100只需要解出本方程就可以得到答案。循环次数=21*34=714for(i=0; i<=20; i++)

for(j=0; j<=33; j++){k=100–i–j ;if(k%3 = = 0&&5*i+3*j+k/3 = =100)printf(“%d,%d,%d\n”, i,j,k);}能否用一层循环?

第45页:百钱买百鸡:一重循环

百钱买百鸡问题100元钱买100只鸡,母鸡每只5元,公鸡每只3元,小鸡3只1元,问共可以买多少只母鸡、多少只公鸡、多少只小鸡?

方法4
用一重循环:合并方程得到:14*x+8*y = 200简化为: 7*x+4*y=100所以有:x<=14,且x必为4的倍数求解:设母鸡、公鸡、小鸡各为x, y, z只。则有:x + y + z = 1005x + 3y + z/3 = 100只需要解出本方程就可以得到答案。循环次数=4for(i=0; i<=14; i+=4){}j = (100–7*i)/4;k=100–
i
j ;
if(k%3 = = 0&&5*i+3*j+k/3 = =100)printf(“%d,%d,%d\n”, i,j,k);

第46页:算法时间效率度量方法

1.

事后统计
编写程序之后利用计算机计时功能,用一组或多组相同的统计数据区分缺点: 必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣 算法时间效率度量方法:2.
事前分析估计
程序在计算机上运行所消耗的时间取决于: 算法策略 问题规模 程序语言 编译质量 计算机速度显然,同一算法用不同的语言、不同的编译程序、在不同的计算机上运行,
效率不同
所以使用“绝对时间”单位衡量算法效率不合适

第47页:语句频度与时间频度

时间复杂度: 同一问题可用不同算法解决,各种算法中,语句执行次数越多,则该算法耗费的时间越长。 一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。T(n)= ∑语句执行次数×该语句执行时间≈∑语句执行次数 该方法可独立于机器的软件、硬件系统来分析算法在效率方面的优劣

第48页:时间复杂度计算示例

例x = 0;y = 0;

for ( k = 0; k < 2*n; k ++ )x ++;for ( i = 0; i < n; i++ )for ( j = 0; j < n; j++ )y ++;112nn2时间耗费T(n) = 4+ 6n+ 2n2 当n充分大时,T(n)与n2在数量级上相同,记T(n)=O(n2)2n+1n+1n*(n+1)执行次数

第49页:大O表示法与运算法则

时间复杂度:算法耗用时间相对问题规模n的增长率,一般指基本操作重复执行的次数的阶数 加法规则与乘法规则1、O(f(n))+O(g(n)) = max{O(f(n)),O(g(n)) }2、O(f(cn)) = O(f(n)),c是正整数3、O(f(n))*O(g(n)) = O(f(n)*g(n)) 大O表示法:T(n)=O(f(n))

第50页:时间复杂度的求和取阶

T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n)例x = 0; y = 0;

for ( k = 0; k < 2*n; k ++ )x ++;for ( i = 0; i < n; i++ )for ( j = 0; j < n; j++ )y ++;频度最大语句重复执行次数的阶数= T1(n)+T2(n)+T3(n)= O(max( 1, n, n2) )= O(n2)

第51页:矩阵相乘的复杂度

例:n×n矩阵相乘for(i=1;i<=n;i++)

for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}

第52页:时间复杂度与空间复杂度

时间复杂度:基本操作重复执行的次数的阶数(算法耗用时间的增长率) (渐近)空间复杂度:S(n)=O(f(n))辅助存储空间增长率 常用时间复杂度: O(1)-----常量型 O(n)、O(n2)、O(n3)------多项式型 O(log2n)、O(nlog2n)-------对数型 O(2n)、O(en)------指数型O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)……

第53页:第一章本章小结

掌握数据结构、算法的基本概念及术语本章小结了解算法的时间复杂度和空间复杂度分析End

顶部目录