页数:53页文件大小:717.4 KB来源: 数据结构ppt课件
本课件为数据结构第一章绪言,从程序设计一般流程出发说明数据结构的研究对象,结合书目检索、人机对弈、交通灯管理等实例引出线性表、树与图,随后系统讲解数据、数据元素、逻辑结构与存储结构、抽象数据类型等核心术语,并介绍算法的描述方式与效率度量方法。
什么是数据结构基本概念和术语算法的描述和算法分析简介本章小结第一章绪言
1946年,第一台电子计算机ENIACShown here are two women “programming” ENIAC. U.S. Army Photo.第一章绪言§1.1什么是数据结构
第一章绪言§1.1什么是数据结构系统功能分析建立数学模型抽象算法设计编码调试与测试系统输入/输出数据、功能需求数据对象的表示及之间的关系解决特定问题的具体描述程序设计一般流程程序=数据结构+算法Niklaus Wirth:问题的数学模型处理问题的策略
第一章绪言§1.1什么是数据结构系统功能分析建立数学模型抽象算法设计编码调试与测试程序设计一般流程非数值计算问题数学方程?数值计算问题数值计算问题例已知:长方形游泳池的长len和宽wide,求面积area
scanf (“%d %d”, &len,&wide);area=len*wide ;printf (“area=%d”,area);}登录号:书名:作者名:分类号:出版单位:出版时间:价格:书目卡片书目文件按书名按作者名按分类号索引表例1书目自动检索系统线性表电话号码查询系统学生成绩管理系统职工信息系统等文档管理的数学模型
例2人机对弈问题
例2人机对弈问题1996年,卡斯帕罗夫与IBM“深蓝”对弈
……..……..…...…...…...…...例2人机对弈问题树
CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题 连线
CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题 连线 填色
CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题
CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题
CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题
CEDABABACADBABCBDDADBDCEAEBECED图例3多叉路口交通灯管理问题
数据结构是一门研究非数值计算的程序设计问题中,计算机的操作对象以及它们之间的关系和操作等等的学科。数据结构定义:……..……..…...…...…...…...ABACADBABCBDDADBDCEAEBECED
§1.2基本概念和术语 数据(data)—所有能输入到计算机中去的描述客观事物的符号 数据元素(data element)—数据的基本单位,也称结点(node)或记录(record) 数据项(data item)—有独立含义的数据最小单位,也称域(field)
数据元素集合元素间关系集合 数据结构(data structure)—数据元素和数据元素关系的集合Data_Structure = {D, R} 数据的逻辑结构—抽象反映数据元素的逻辑关系 从逻辑关系上描述数据,与数据的存储无关 从具体问题抽象出来的数据模型; 与数据元素本身的形式、内容无关; 与数据元素的相对位置无关。
数据结构(data structure)—数据元素和数据元素关系的集合Data_Structure = {D, R}
元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储内容Loc(元素i)=Lo+(i-1)*m顺序存储数据的顺序存储通过分配连续的存储空间来反映数据元素的逻辑相邻关系逻辑上相邻存储位置也相邻
∧元素41400元素11536元素21350元素3指针存储内容存储地址1400元素11346∧元素41350…….……..…….1536元素21400…….……..…….1350元素31536链式存储数据的链式存储结构通过指针来反映数据元素的逻辑相邻关系“链”——指示逻辑上与之相邻的元素存储位置头指针1346L
数据类型——一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称例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;1536元素21400元素11350元素3∧元素4L数据类型表示?
typedefstruct node{int data;struct node*next;}Lnode, *LinkList;Lnodes;LinkListp;抽象数据类型(Abstract Data Type,ADT)定义:指一个数学模型及定义在该模型上的一组操作 数据抽象仅取决于它的一组逻辑特性,由基本的数据类型及一组相关操作组成,不考虑数据的存储形式和操作的实现算法 数据封装将数据类型及数据类型上的运算捆绑在一起,进行封装,对外部用户隐藏其内部实现细节ADT抽象数据类型名{数据对象:…数据关系:…基本操作:…}ADT抽象数据类型名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的和值引用
C++等面向对象程序设计语言为简化复杂的指针操作,提供了引用机制(“&”),即为变量起一个别名,引用名与变量享受同等的访问待遇。(*.cpp支持引用) C语言不支持引用类型。(*.c不支持引用)inta=4;int&x=a; 引用(Reference)x与a占用相同的存储空间变量名a引用x(别名)a=10;10x=8;8变量及其引用是同步变化的
引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。
voidswap(intx,inty){inttemp;temp=x;x=y;y=temp;}当用执行语句swap(a,b)时:a和b的值没有发生交换…...…...20002008200A2002200420065变量a变量b9变量y变量x(swap)55959COPY值传递变量temp当用执行语句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当用执行语句swap(a,b)时:a和b的值发生了交换引用传递
voidswap(int&x,int&y){inttemp;temp=x;x=y;y=temp;}显然,采用引用方式更为简洁方便。所以教材中很多算法都采用引用形式的形参。 引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。…...…...2000200220042006变量a变量b59变量temp(swap)引用x引用y595voidswap(int&x,int&y){inttemp;temp=x;x=y;y=temp;} 引用常用于函数形参中,采用引用型形参时,可实现数据的双向传递。如何区分&是“引用”还是“取变量地址”??&仅在形参及定义部分表示引用引用inta=4;int&x=a;引用inta=5, b=9;swap(&a,&b);取变量地址抽象数据类型的表示和实现
typedefstruct{floatrealpart;floatimagpart;}complex;//基本操作:用sum返回两个复数z1,z2的和值voidadd(complexz1,complexz2,complex&sum){sum.realpart =z1.realpart +z2.realpart;sum.imagpart =z1.imagpart +z2.imagpart;}——通过固有数据类型(高级编程语言中已实现的数据类型)来实现。复数的定义//预定义常量和类型
#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus; 抽象数据类型的表示和实现——通过固有数据类型(高级编程语言中已实现的数据类型)来实现。§1.3算法的描述和算法分析简介
§1.3算法的描述和算法分析简介 算法的评价—衡量算法优劣的标准正确性:1、程序中不含语法错误;2、程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果;可读性:1、算法应该易于人的理解;2、晦涩难读的算法易于隐藏较多错误而难以调试。健壮性: 1、指当输入数据非法时,算法恰当的做出反应或进行相应处理,而不是产生莫名其妙的输出结果。2、处理出错的方法,不是中断程序,而是返回一个表示错误或错误性质的值,以便进行处理 正确性(correctness) 可读性(readability) 健壮性(robustness) 效率
算法设计重要性例1:在有序表中查找给定值例2:百钱买百鸡问题算法描述与算法分析
例:数组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次查找成功方法二:折半查找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
方法二:折半查找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
方法二:折半查找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
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在数组中下标;若查找失败,返回00 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
百钱买百鸡问题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);循环层数太多百钱买百鸡问题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);每层循环次数太多百钱买百鸡问题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);}能否用一层循环?百钱买百鸡问题100元钱买100只鸡,母鸡每只5元,公鸡每只3元,小鸡3只1元,问共可以买多少只母鸡、多少只公鸡、多少只小鸡?
if(k%3 = = 0&&5*i+3*j+k/3 = =100)printf(“%d,%d,%d\n”, i,j,k);1.
时间复杂度: 同一问题可用不同算法解决,各种算法中,语句执行次数越多,则该算法耗费的时间越长。 一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。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 ++;112nn2时间耗费T(n) = 4+ 6n+ 2n2 当n充分大时,T(n)与n2在数量级上相同,记T(n)=O(n2)2n+1n+1n*(n+1)执行次数时间复杂度:算法耗用时间相对问题规模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))
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)例: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];}时间复杂度:基本操作重复执行的次数的阶数(算法耗用时间的增长率) (渐近)空间复杂度: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)……
掌握数据结构、算法的基本概念及术语本章小结了解算法的时间复杂度和空间复杂度分析End
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}