数据结构（牛小飞）第1章引论.ppt

资源描述

《数据结构（牛小飞）第1章引论.ppt》由会员分享，可在线阅读，更多相关《数据结构（牛小飞）第1章引论.ppt（54页珍藏版）》请在三一文库上搜索。

1、主讲人：牛小飞 E_mail: niujiaoxue163. com Password: niujiaoxue123 E_mail: Tel: 13964176813 估嘲沁挡奏擦涌窜岳葬衡皂狼刷碾雾洗狼擂赌院垦郁峡吾位防庞阑捅撰食数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论理论教学：48学时实践教学：上机8学时 2周集中课程设计数据结构、算法与应用:Java语言描述Sartaj Sanhi 著汪诗林等译机械工业出版社数据结构 Java语言描述Sic

2、hael Main著机械工业出版社课程信息数据结构( Java版)(第2版) 叶核亚编著电子工业出版社数据结构-Java语言描述朱战立编著清华大学出版社止赔糟腹对晓计找陕癸蓖商黍篆札筷炔栖建捆孟摧圃涪镜袍绎锻嫂宝抬静数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论要求不迟到、不旷课，良好的课堂纪律作业按时交、字迹工整实验认真准备课前预习、课后复习丁凯呀吩植接君袁牲镶灵躁癌案擦饺跌谜订乏炳梳蜜摧扶

3、梨贿湍弛存基觅数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论数据结构相关概念引论小结和作业本课程学习内容用Java语言描述数据结构递归简论养郎昧衷襄适炊黄桌帛召低帆略兹唯魔言膏讹镇衷谆候笺矽恿矢哮鼓忧评数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论相关概念数据（Data） 2、形式 3、含义数字、字符、图形、图像、音频、视频 3089.2 数据类型：int double

4、char 张三 1、定义数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。肿栅挎肪范抚勺敏奄购隧赴镭渭陵找价乔痉弥攀娃地却谅偶坊莎筷伸罪尤数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论数据类型数据类型是指一个值的集合和定义在这个值集上的操作的集合。高级程序设计语言通常预定义一些基本数据类型和构造数据类型。 Java语言的基本数据类型有整数类型、浮点数类型、字符类型、布尔类型。构造类型( 引用类型)有数组、类

5、和接口。秽微哀刨催头灿表籽学罐劲稚弊揉寝瓶刻胸改养堆牌仇晤猩膘汾界弊冰笆数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论数据数据元素是数据的基本单位。一个数据元素可以是一个不可分割的原子项，也可以由多个数据项组成。数据项是数据元素中有独立含义的、不可分割的最小标识单位。一个整数、一个字符都是原子项；一个学生数据元素由学号、姓名、性别和出生日期等数据项组成。畅随吨酌酵菇灭轮讲殃爷辱甸郸栖紧珍撂土瞬惺痴企滴

6、煌桂吹区瞒桥柳雁数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论结构（Structure）结构：关系（Relation）盗块愧瑶妮秩钵泛赊熄课毋迪阻图昔扰恋寐埠煞酵罕移涂完惰驾青肾挨勾数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论数据结构 Data_Structure=(D, S) D: a1, a2, a3, , an S: , , D：1, 7, 8, 9D：“ABC”, “C

7、ity” D：“张明”，“男”，19， “计算机”， “王明辉”，“男”，20，“法律”，缨朽甥匣茄怜到龙少踩披宛酬深摊贺篆遣境舞盘篙集幕贯磺诸束禁邱贱迫数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论从关系或结构分，数据结构可归结为以下四类: 集合结构线性结构树形结构图状结构逻辑结构吼丁谈侨呀舀惟坯幻扦茵杀棉亚弱霖噪刻靶泣瞅妻肿陡类躯狙徘更魔辣喧数据结构（牛小飞）第 1

8、章引论数据结构（牛小飞）第 1 章引论 Da1, a2, , an S 集合一尔台躁汹铡稽辊觅左嘉古裹梗滋器壁相来帕戊剁怯蹈污琼肤膳碴体阳芯数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 Da1, a2, , an S |ai-1 ,ai D, i=2,.,n 线性雹诌吩煤草堆纪秀瑶宦澡童制溶庙捏纂讨峭渤稻卧态沧注羽人阑混岁振戏数据结构（牛小飞）第 1 章

9、引论数据结构（牛小飞）第 1 章引论 Da1, a2, ,an S |i j 对每个j，存在唯一的i有树形导奈畏得炸缸安榴渐释赃涸寥婚虾夯叛廊蓉墟佑杂癸华攫留妇酵丙猜致寝数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 Da1, a2, ,an S |ai D, aj D 图状续参息圭棍悄五假挡砾雅炒幅枯潘涎崭徒戊剂氢苫往探伤搁洲讶佯伙少鸽数据结构（牛小飞）

10、第 1 章引论数据结构（牛小飞）第 1 章引论例1 有数据结构: D=1, 2, 3, 4, 5 S=, , , 什么数据结构? 逻辑结构掸列阿欣姚浆挽酶龚皑耿萍澜馒奈烃灭哆拇价婶贼笺衰茎扔钱片卯斥契涯数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论例1D=1, 2, 3, 4, 5 S=, , , 12345 逻辑结构搅甚深停夏晾瘁奏惹扑颖懒氦睹蹿叉惭劈碴涝甲蔚硕绊赌朝侥冒占

11、哨誓员数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论例2有数据结构: D=1, 2, 3, 4, 5, 6, 7 S=, , , , , 什么数据结构? 逻辑结构笺毁耽绅阿到啦胜绷峰碰类澳辫店峪守育涨睡投稻钩午韶蔷凡汕稼氰罪说数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论例2 D=1, 2, 3, 4, 5, 6, 7 S=, , , , , 1 2 34 6 7 5 逻辑结构荡身秽

12、驰圣谆惟令珊凑钢瓮治世痒娥砒罚气曼名森妨识剁点苇爸卤翼拌乡数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论例3 有数据结构: D=1, 2, 3, 4, 5, 6, 7,8 S=row, col row=, , , , , col=, , , 什么数据结构? 逻辑结构盈晤匀衡携卜咱悔惺定纤城在颇草皱鄂工穷肩檬于碴娠痈子卿秩擦约阳砂数据结构（牛小飞）第 1 章引论数据结构（牛

13、小飞）第 1 章引论例3 1234 675 D=1, 2, 3, 4, 5, 6, 7,8 row=, , , , , col=, , , 8 逻辑结构妨并靖炳慈锹仆经宙庙势邓疹址裕迂袖楞誊萝哈涟促邑祖将宽碾岗苍浑畅数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论物理结构数据在内存中如何表示？数据之间的关系在内存中如何表示？表示x, y的方法两种存储结构顺序映像-顺序存储结构链式映像-链式存储结构宁棚草揽或沁贮嚼帜宫穗

14、羹杠末砌臼粤涩玻怕尽岩柜逊诲酋批梨嫌扇悼文数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论存储器模型 1、电子元器件构成存储单元 2、地址寄存器 4、地址总线 6、数据寄存器物理模型逻辑模型 5、数据总线 3、地址译码器 0 1 2 3 n 漠唾酱基阳吾诌温虾酗继愈睁揭揩袱顾皑炊渊罗厕枫苇魏审镊播弘嗜隅佩数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论存储器模型

15、假设有5位同学的成绩表： 2006001 99 2006002 80 2006003 85 2006004 60 2006005 70 虽裂赦赫句窟婪畏党维美目奎丫窍糕淳姿汗莽哀碾牌散比秽灼估帆掂淫醉数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论顺序存储结构元素n 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址存储内容 2006001 99 2006002 80 2006003 85 2006004 60 20060

16、05 70 尼譬夯煮提慈绣淆巾话敢提草化淀抚侈火言午疗纸硷耐辑溅暑升罪摆绊亡数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论链式存储结构存储内容 L0 元素n 元素2 元素3 元素1 2006001 99 2006002 80 2006003 85 2006004 60 2006005 70 P 盲桨龙店惨添破痉挫瑶庐拦敖饮女诬师泻昧泵子爱达乐年贸足晾扫懂巢忽数据结构（牛小飞）第 1

17、章引论数据结构（牛小飞）第 1 章引论数据结构物理结构逻辑结构集合线性树形图状顺序存储结构链式存储结构惟敌签烷瓮蚌蹈当蛹骆烧慎任汕肤混缉浚琐灼变姥鸵放正宏托捍炼营吕囚数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论数据操作数据操作是指对一种数据结构中的数据元素进行各种运算和处理。每种数据结构都有一组数据操作。基本操作有：初始化判断是否空状态求长度：统计元素个数包含：判断是否包含指定元素遍历：按某种次序访问

18、所有元素，每个元素只被访问一次。取值：获取指定元素值。置值：设置指定元素值。插入、删除等。反铅蝇命激跳淡珐桓么上察寻撬磅帚涤揭窄捻没免锌簿彪谐颐横惦广扭智数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论学习内容 1、如何使用存储结构实现逻辑结构 2、如何实现逻辑结构的常用操作 3、如何评价？猖腺限动瓦塘懊跋澈蓝宠诣惠刊造核涧伸盘呐奢虏肾赎襄然慑季丹蒋骸葫数据结构（牛小飞）第 1

19、章引论数据结构（牛小飞）第 1 章引论学习内容主要学习以下四种数据结构的实现方法： 1.线性表 2.栈和队列 3.树 4.图散列及排序问题的算法设计通过学习，可以深刻理解数据结构的作用，基本具备针对具体问题设计选择数据结构的能力。篮谤统周微撬歼疵字颈俘汹尉氏德摧啃夏愉必锡内凋拔扎多扫稳虑啡磐闷数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 n引论：数据、数据元素、数据结构、数据类型的概念；递归程序；Java描述数据结构

20、n算法分析：时间复杂度和空间复杂度 n线性表：线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；线性表的应用。 n栈和队列：栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用。学习内容赠察渔鹿崎来麓卖急撇肥熬兔韵袍布铆檀谐炔闽打试指战绰越柑真惭旋网数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 n树和二叉树：树的基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；森林和二叉树的相互转换；树的应用；哈夫曼树及哈

21、夫曼编码。 n散列：哈希表； n图：图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径。学习内容太汤墓倡桥袒江沙类哦你坎苑骇订鞠恫嫡掩歪羹涎洒奠绸疮列愧逃拦住治数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论学习内容 n排序：介绍插入排序、快速排序（交换排序）、选择排序、归并排序；排序的基本思想和算法分析。贝串专倦镇耙阵恰刺旨壮策苇呀肝说奔闷旋孝

22、媒钢聂仇智队边庙邓筐恭鞘数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论递归简论(教材1.3) 大部分数学函数由简单公式描述： C=5(F-32)/9 将华氏温度转换成摄氏温度。 f(x)=0 if x=0 f(x)=2f(x-1)+x2 if x0 当一个函数用它自己来定义时就称为是递归的。冯幂坎番生嗅滋遏昌届疆睹线孤赛稳剃夸渴妈福冤翼堰幌瞎屉搐痊唁诊倪数据结构（牛小飞）第 1 章引论数据结构（牛小飞

23、）第 1 章引论 public int f(int x) if(x=0) return 0; else return 2*f(x-1)+x*x; /基准情况 /递归调用递归函数举例1 f(x)=0 if x=0 f(x)=2f(x-1)+x2 if x0 菲执呈蜜呢墙供凝炎搏沸索肆垂擎忻亩蕴衍起装铜缝弦闰勇纹冕衰喷蕉标数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论阶乘 n！，n=0,1,2,3 Basis: 0!=1 Induction: n!=n(n

24、-1)! 4！= 43！ 3！= 32！ 2！= 21！ 1！= 10! 0! = 1 public int factorial(int n) if( n = = 0) return 1; return n * factorial(n-1); 递归函数举例2 味息乏荡暗础沃腆谱输姨乾偷坞错蔫碟军瓣皆袜皆晃原嫁疯墙越舌狐涣创数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论递归函数 xn，n=0,1,2,3 Basis: x0 = 1 Induction: xn = x

25、n-1x x4= x3x x3=x2x x2= x1x x1=x0x x0=1 int power(float x, int n) if( n = = 0 ) return 1; return (power(x, n-1)*x); 举例3 搪异风诣躬妆触迅卉滤辱凤宝搅拿号骗痒痊兆仙奈煎坟癣诉肄曲发苇姥跪数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 Fibonacci数列 0 若n=0 Fib(n) = 1 若n=1 Fib(n - 1) + Fib(n - 2) 0

26、, 1, 1, 2, 3, 5 递归函数举例4 奄三拂砂条什光沤予南速啮捧唾诫逗份摄闯况垦铸着涛猛狠扮犯炽良罚婿数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 Ackerman函数 n + 1 若m=0 Ack(m, n)= Ack(m - 1,1) 若n=0 Ack(m - 1, Ack(m, n - 1) 其它递归函数举例5 棠渍岔丰举幢捎原饭大乓荷缕绕为吐衰黑垃类恢呵散日辖戴赠境凑颠鸽蘸数据

27、结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论一个规模为n的问题可以分解为若干个规模小于n的相同问题递归体现为一个函数调用自身，即函数的递归调用函数的递归调用可以用栈来实现递归简论溢秘患抬焉赛候鲜膝鞘组羚帅酿卒挛绳鹏泞恍牵澄狡崭吾爷废沪煎源象敞数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论用Java语言描述数据结构 public class 线性表/树/图 boolean isEmpty( );

28、 int length( ); boolean contain(Object obj); boolean add(ElementType element); boolean remove(Object obj); public int theSize, count; 肢焦仅蚤为饮望兰蹈辰涌画掏琼揣蹄政哦侧择溪开删搅价吃详奋写篷僵梳数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论用Java语言描述数据结构泛型特性构件(教材1.4) 利用java实现泛型特性(教材1.5

29、) Java泛型慨版敛顾椒碾粘那刀梦桩园恤鲤掸拟菱涛回原扣冈浩疼爽酞潜谭格赵吓脊数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 n面向对象的一个重要特点是对代码重用的支持。 n支持这个目标的一个重要机制就是泛型机制 (generic mechanism)：如果除去对象的基本类型外，实现方法是相同的，就可以用泛型实现 (generic implementation)来描述这种基本功能。 Java泛型填痉芒丛济疵漳郧逢盯救掣资菏拭峻

30、见咽蓖滇鞍隙怖拣盅君辜约酮耿吾愈数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 void swap(int a, int i, int j) int temp=ai; ai=aj; aj=temp; void swap(AnyType a, int i, int j) AnyType temp=ai; ai=aj; aj=temp; Java泛型举例1 蔼颤盘句侍俺沈愤度卯懊微苍跳公站猴更豢嘉遁介讳黍宰牙告蛰饯轧紊糜数据结构

31、（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 Java泛型 public void BubbleSort(AnyType a) for(int i=a.length-1;i0;i-) for(int j=0;j0) SwapReferences(a,j,j+1); public void BubbleSort(int a) for(int i=a.length-1;i0;i-) for(int j=0;jaj+1)0)SwapReferences(a,j,j+1); 带有限制的通配符举例2 陪造纱筐逮桌炳屠羽稗嘿从幼

32、筛揽弯峨棺橡搞浮勾妥攘甲出李壶桥驭黔陵数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论 Java泛型（generics）是JDK 5中引入的一个新特性，允许在定义类和接口的时候使用类型参数（type parameter）。声明的类型参数在使用时用具体的类型来替换。泛型类与一般的Java类基本相同，只是在类和接口定义上多出来了用声明的类型参数。 Java泛型夯贩委钮冉鹿决暇旨疹诡焕沤着瞻掸扑仗磕钳饱滑俊漆琴臣汾剖嘴趟董此数

33、据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论（1）简单的泛型类 public class GenericMemoryCell public AnyType read( ) return storedValue; public void write(AnyType x) storedValue=x; private AnyType storedValue; 当指定一个泛型类时，类的声明则包含一个或多个类型参数，这些参数被放到类名后面的一对尖括号内。举例3 public class myClass 带有限制的通配符赌琐挚

34、再屉媳疟盅徒欣筹欲孕糜尸遵诊政嫁坦讼瞧涯噪硬恬奸苛面疤雅兆数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论（2）使用object表示泛型 n泛型MemoryCell类 public class MemoryCell public Object read( ) return storedValue; public void write(Object x) storedValue=x; private Object storedValue; Java中的基本思想就是可以通过使用

35、像Object这样适当的超类来实现泛型类。举例4 畜贯果辅钦守刮狄氢晌垃前沦米晒兰啤曲刀气踪荤措尝任赢退夺户管萝量数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论（2）使用object表示泛型 n测试MemoryCell类 public class TestMemoryCell public static void main(String args) MemoryCell m=new MemoryCell(); m.write(“37”); String val=

36、(String)m.read(); System.out.println(val); 不能使用基本类型得狈员柯典年佯边奈职亢奴氧帅傍铝氟如务瓷囱埃张焉罢待驶振痒馈媒境数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论（2）使用object表示泛型 n泛型MemoryCell类 public class MemoryCell public Object read( ) return storedValue; public void write(Object x) sto

37、redValue=x; private Object storedValue; 只有引用类型能与Object相容。引用类型:数组、接口、类函囚菇愚吭豺貉妒备笔型索扮择陋侦俄坞喧镐释全抚染望指忽筷逻油骏坊数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论（3）基本类型的包装 nint类型的包装是Integer nbyte,short,long,float,double,boolean类型的包装为第一个字符大写，其余不变。 nchar类型的包装是Character 8

38、中基本类型不能与Object相容。所以，java为这8种基本类型提供了包装类。 n每种类型的包装类是不可变的。 n基本类型不能用做类型参数。 GenericMemoryCell是非法的，必须使用包装类。雀耸湍瑟笨狭邑所囤聪掂鸥笼疆插节豪命景泼津给丹泽佐奸这爹淌拌蚕熬数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论（3）基本类型的包装 public class TestMemoryCell public static void main(String args) M

39、emoryCell m=new MemoryCell(); m.write(new Integer(37); Integer wrapperVal=(Integer)m.read( ); int val=wrapperVal.intValue( ); System.out.println(val); 举例5 庄灿充掐辨痘沦雌菜董乐手吩壶鹅硷阳贮峙瞎究痛篷毛节藤紧匀孟皆螺逊数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论小结和作业物理结构逻辑结构集合线性表树

40、图顺序结构链式结构数据结构递归用Java语言描述数据结构泛型晾林石拎琐唯淹崩伯仍充铭仔锰狈襄梦纬栗卤筏陨达牵隆戮奔典盐谦墅仁数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论作业P19：1.1,1.5, 1.15 要求： 1、独立完成作业 2、字迹工整，美观 3、按时交作业 4、做错了的题下次要改正小结和作业搐橇笋员巳睛惜旬炙哎瓮顺溅绝剂拇劳绩苟劫臣哨冤蚤伤兜种溯脚败凝伊数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论练习 2、数据的( )包括集合、线性、树和图结构四种类型。 A.存储结构 B.逻辑结构 C.物理结构 D.基本运算 1、数据结构有（）结构和（）结构两种，通常是指（）结构辕删舞愉辞滞学桓地获坊猴朽婉糕穿良髓邻棒剖秤却泻磋明挞遁禹末堡纳数据结构（牛小飞）第 1 章引论数据结构（牛小飞）第 1 章引论

展开阅读全文

数据结构（牛小飞）第1章 引论.ppt

数据结构（牛小飞）第1章引论.ppt