




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1数据结构与算法
2
○学习的目的:为了分析待处理的对象的特性以及各处理对象之间的存在关系。
概述2.1学习目的因此,简单说来,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
3
2.1.1数据结构对数据处理的重要性数据结构可描述为Group=(D,R)学生成绩查询学号姓名成绩9861109张卓1009861107刘忠赏959861103胡孝臣86交通路灯问题4
数据:所有能输入到计算机中并能被计算机程序处理的符号集合.数据元素:
数据的基本单位,也称结点或记录.数据结构:
相互间存在一种或多种特定关系的数据元素的集合.
基本概念5
数据结构:由某一数据对象及该对象中所有数据成员之间的关系组成。记为:
Data_Structure={D,R}
其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。
数据结构数据结构是一门研究数据组织、存储和运算的一般方法的学科。6
1.数据的逻辑结构
2、数据的存储结构3、数据的运算:检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储
B.链式存储线性表栈队树形结构图形结构2.1.2数据结构研究的三个主要问题:7
集合:数据元素之间属于一个集合,别无其他关系.
线性结构:结构中的数据元素存在一个对一个的关系.
树结构:结构中的数据元素存在一个对多个的关系.
图结构:结构中的数据元素存在多个对多个的关系.1234数据的逻辑结构8
树形结构例子——结点间具有分层次的连接关系HBCDEFGA9
1423
D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213
D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}
图形结构例子——结点间的连结是任意的10
元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储内容Loc(元素i)=Lo+(i-1)*m数据的顺序存储11
1536元素21400元素11346元素3∧元素41345存储地址存储内容指针
1345元素1
1400
1346元素4∧
…….
……..
…….
1400元素2
1536
…….
……..
…….
1536元素3
1346h数据的链式存储12
하도급건설기술자배치관리
程序=算法+数据结构
程序设计的实质是选择一个好的数据结构,设计一个好的算法。算法取决于描述实际问题的数据结构。13
2.1.3算法的基本概念
1算法:是对特定问题求解步骤的一种描述。算法的四个特性:有穷性确定性可行性有输出14
12Voidexam1(){n=2;while(n%2==0)n=n+2;printf(“%d\n”,n);}Voidexam2(){y=0;x=5/y;printf(“%d%d”,x,y);}15
评价算法:正确性、易读性、健壮性、运行时间及占用空间。
正确性:正确与否可读性:容易阅读健壮性:容错处理效率和低存储量需求:
和算法执行时间相关的因素有:1)算法所用“策略”;2)算法所解问题的“规模”;3)编程所用“语言”;4)“编译”的质量;5)执行算法的计算机的"速度"。16
for(i=1;i<=n;i++)/*n+1*/for(j=1;j<=n;j++)/*n*(n+1)*/{c[i][j]=0;/*n2*/for(k=1;k<=n;k++)/*n2(n+1)*/c[i][j]=c[i][j]+a[i][k]*b[k][j];/*n3*/}T(n)=2n3+3n2+2n+1两个n阶矩阵相乘的算法2算法的复杂度:时间复杂度:评估算法的时间增长趋势。影响运行时间的因素:语句执行的次数(频度)
执行每行语句所需的时间(与算法无关)T(n)=2n3+3n2+2n+1当n趋向充分大时,T(n)/n3的值趋于常数算法时间复杂度表示为T(n)=O(n3)17
当问题的规模n趋于无穷大时,把时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度(有时简称为时间复杂度)。
严格的数学定义为:若T(n)和f(n)是定义在正整数集合上的两个函数,当存在两个正的乘数C和n0时,使得对所有的成立,则都有这时称T(n)的时间复杂度为f(n)数量级。18
例:x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)for(j=1;j<=n;j++)//n*ny++;一般情况下,对步进循环语句只需考虑循环体中语句的执行次数,而忽略循环体中步长加1、终值判断、控制转移等成分。时间复杂度是以算法中频度最大的语句来衡量。19
voidselect_sort(inta[],intn)
{
//将a中整数序列重新排列成自小至大有序的整数序列。
for(i=0;i<n-1;++i){
j=i;
for(k=i+1;k<n;++k)
if(a[k]<a[j])j=k;
if(j!=i){w=a[j];a[j]=a[i];a[i]=w;}}
}20
例:x=1;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;21대한주택공사Ⅰ
1
2如果算法的执行时间是一个与问题规模n无关的常数,则算法的时间复杂度为常数阶,记作T(n)=O(1)。空间复杂度:指算法中所需的辅助空间单元。交换i和j的内容。Temp=i;i=j
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 水泥购销合同协议
- 环保水处理项目合作框架协议
- 学校食堂蔬菜采购合同
- 股份制企业的合同文书规范与管理
- 蔬菜种植合作的协议书(3篇)
- 两人合作合同
- 环保产业技术创新与应用合同
- 公司股权分配合同协议年
- 派遣合同就业协议书
- 人才委托协议
- 2025年2级注册计量师专业实务真题附答案
- 2025年春季学期教导处工作计划及安排表
- 果实品质评价体系建立与应用-深度研究
- 人教版小学六年级下册音乐教案全册
- 12J201平屋面建筑构造图集(完整版)
- 20CS03-1一体化预制泵站选用与安装一
- (完整版)四年级上册数学竖式计算题100题直接打印版
- 数理统计考试试卷及答案解析
- 排水沟施工合同电子版(精选5篇)
- 《酒店品牌建设与管理》课程教学大纲
- 大气商务企业培训之团队合作的重要性PPT模板
评论
0/150
提交评论