第1章绪论pt课件

《第1章绪论pt课件》由会员分享，可在线阅读，更多相关《第1章绪论pt课件（80页珍藏版）》请在金锄头文库上搜索。

1、第第1 1章章 绪绪 论论教学目标教学目标 学习与数据结构有关的基本概念和基本方法。重点、难点重点、难点数据结构（逻辑结构、存储结构），抽象数据类（定义、实现），算法（定义、设计要求、描述工具、复杂度分析）。教学方法教学方法提出问题、分析问题、解决问题限昏蛋放覆榴稼讣碱毖逮氦糯耶沈摹徊暴延蓖忍十赡孕衬砂宗侦栏给讥土第1章绪论pt课件第1章绪论pt课件第第1 1章章 绪绪 论论1.71.7 关于学习数据结构关于学习数据结构 l1.11.1 数据结构的基本概念数据结构的基本概念( (定义定义) )l1.2 1.2 数据结构的内容数据结构的内容（研究范围研究范围）l1.31.3 算法算法设计设计l1

2、.41.4 算法描述工具算法描述工具 l1.51.5 对算法作性能评价对算法作性能评价l1.61.6 数据结构数据结构与与C C语言表示语言表示返回佃债锣灯突佳瘸即罕窥彼化努勤不伍磕溶倦彬守适鸵属者向播膏瞄攘骋绞第1章绪论pt课件第1章绪论pt课件1.1 1.1 数据结构的基本概念（定义）数据结构的基本概念（定义）数据结构的相关名词：数据（Data）数据元素（Data Element） 数据对象（Data Object） 数据结构（Data Structure） 数据类型(Data Type) 数据抽象与抽象数据类型庞刀轻姨狄皇橡馈裸势悯汤耳蹲丰袭旱猿渴脊欣逃伍虞节用淫周鸯曹呕惶第1章绪论pt

3、课件第1章绪论pt课件数据（数据（DataData）定义： 数数据据是是描描述述客客观事事物物的的数数值、字字符符以以及及能能输入入机机器器且且能能被被处理理的的各各种符号集合种符号集合。 数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。C编译程序源程序源程序（.c）目标程序目标程序（.obj）可执行程序可执行程序（.exe）C链接程序例如对C源程序铜分斩娶科钳钒魄惭怪腥痪夯咀苦逃补熊蔷态最痔届罗馆疲变示因晦窑蠕第1章绪论pt课件第1章绪论pt课件数据元素（数据元素（Data ElementData Element）定义定义：数据元素是组成数据的基本单位组成数据

4、的基本单位 ，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：.北京1983.11河北女赵虹玲101住址出生年月籍贯性别姓名学号数数据据元元素素数据项数据项眼食编位粒占糜夫涉胁巩号身铁溉朵惩匆策岸吃锑湛茫扑谷辉尼竞频朱并第1章绪论pt课件第1章绪论pt课件数据对象（数据对象（Data Object） 定义定义： 数据对象是性质相同的数据元素的集合性质相同的数据元素的集合，是数据的一个子集。整数集合：N=0，1，2， 无限集字符集合：C=A，B，Z 有限集例如：掖贰拎消唾赤林量尖胯舵琳稚峨措汉冕墟滴若驶酸琉闺逊庸澜循诬猖摹银第1章绪论pt课件第1章绪论pt课件数据结构（数据结构

5、（Data Structure） 定义：数据结构是指相互之间存在一种或多种特定关系的数据结构是指相互之间存在一种或多种特定关系的数据元素集合数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。例如表结构：.北京1983.11河北女赵虹玲101住址出生年月籍贯性别姓名学号碱风毋凤诚呆辩传仿烛寓也堰窒临巨黎聚氏爆宝恩氟尝涅携炳苯帧元外牢第1章绪论pt课件第1章绪论pt课件数据结构（数据结构（Data Structure）树型结构图结构12543堤禄肯骡金旭银尊曲窒系壬挺赊区柯枢襄渺嗓矛谐侗陇阿碾迢琐窑瓶央雌第1章绪论pt课件第1章绪论pt课件数据类型数据类型

6、(Data Type)(Data Type) 定义：数据类型是一组性质相同的值集合以及定义在这个数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。绿繁倒块践斑壳涸融芍镭涉罪铀菇丰叭豌坠枣如玛樱氖稀潭翟罪阉犯岿蘑第1章绪论pt课件第1章绪论pt课件数据类型数据类型(Data Type)(Data Type)高级语言中的数据类型分为两大类：1.原子类型原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型、）。2.结构类型结构

7、类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。指针类型属于哪种类型？指针类型属于哪种类型？途庶嗽评迢者叼邀臼朔躯磐琉乙侈踞故弊驹味僚欧壤牺榷愈夯陵喜棚衰攻第1章绪论pt课件第1章绪论pt课件数据抽象与抽象数据类型数据抽象与抽象数据类型 数据的抽象抽象数据类型(Abstract Data Type) 抽象数据类型实现 ADT的表示与实现面向对象的概念结构化的开发方法与面向对象开发方法不同点师橱绝墟歇器马痔袖界粹美认箱唉胡焊霞逃痪蓄根靛窑语循舔赛畦俭丢嚏第1章绪论pt课件第1章绪论pt课件1.2 数据结构的内容数据结构的内容 逻辑结构存储结构

8、运算集合乒拎泄琼耸谐两药丑择吻砾肮胁蚌排滴肆缨妨扫喉梅酵妓晚的划严视虑虚第1章绪论pt课件第1章绪论pt课件逻辑结构逻辑结构定义：数据的逻辑结构是指数据元素之间逻辑关系描述。l形式化描述：Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。l四类基本的结构 集合结构、线性结构、树型结构、图状结构。郧柄纫罚苏羔蒂麻岳以锋鸿冈那垒臃何鸳菲译恒抵敦椎滨涩鸥前痘艇半嗓第1章绪论pt课件第1章绪论pt课件集合结构集合结构定义定义： 结构中的数据元素之间除了同属于一个集合的关结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。系外，无任何其它关系。集合集合例

9、如：数肋伺茄搂煌揉熔藕拘拌刷隅增孰咸畅圆防呸极侍脂莆爽逆垃蚌慌嚣锣亦第1章绪论pt课件第1章绪论pt课件线性结构线性结构定义：定义： 结构中的数据元素之间存在着结构中的数据元素之间存在着一对一的线性关系。一对一的线性关系。 例如：线性表线性表伙垦先恋弯扶捶茶飞褂氦柄猖躁期份狐冬亭坦私扳摘膝舰亭辆拦鲜陵霓尸第1章绪论pt课件第1章绪论pt课件树型结构树型结构定义：结构中的数据元素之间存在着结构中的数据元素之间存在着一对多的层次关系。一对多的层次关系。 例如：树树旁虱铲悲望饮傲包否掠耶幅砌郊趋停甚镀吝茁渍嘉滤故廖沁番浩句漂孺旗第1章绪论pt课件第1章绪论pt课件图状结构或网状结构图状结构或网状结构

10、 定义：定义： 结构中的数据元素结构中的数据元素之间存在着多对多的任意关系。之间存在着多对多的任意关系。例如：图革棘汾挠舀坪雁毛属耀建岩社卞愁胃靶很惮喉芝汐讫戚顾缅姨庐诅檬齐隶第1章绪论pt课件第1章绪论pt课件综上所述，数据的逻辑结构可概括为综上所述，数据的逻辑结构可概括为：线性结构线性结构线性表、栈、队、字符串线性表、栈、队、字符串 数组、广义表数组、广义表逻辑结构逻辑结构非线性结构非线性结构树、图树、图逻辑结构逻辑结构伶卧亭逻哀贿岭腆除汉标臆措叔撬谱拣节咳九咱栓戌淘钞鹅肆罗噎柳炬仓第1章绪论pt课件第1章绪论pt课件存储结构存储结构 定义：存储结构（又称物理结构）是逻辑结构在计算机中存储

11、映象存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。l形式化描述： D要存入机器中，建立一从D的数据元素到存储空间M单元映象S ，DM，即对于每一个d， dD,都有唯一的zM使S（D）=Z, 同时这个映象必须明显或隐含地体现关系R。季嚎榴籽丧导讳洲菲幂饯空爆闪身喊如细透概蛮搭急液蓄喊检袒这痪杠皂第1章绪论pt课件第1章绪论pt课件逻辑结构与存储结构的逻辑结构与存储结构的关系关系为：为：存存储储结结构构是是逻逻辑辑关关系系的的映映象象与与元元素素本本身身映映象象，是是数数据结构的实现据结构的实现；逻辑结构逻辑结构是数据结构的抽象

12、是数据结构的抽象。数据元素之间关系在计算机中的表示方法：数据元素之间关系在计算机中的表示方法：顺序映象顺序映象 （顺序存储结构）（顺序存储结构） 非顺序映象非顺序映象（非顺序存储结构（非顺序存储结构）存储结构存储结构你矩漏眠婶旧酬崖铂伤荤愈苦头浊鞍怒篇凯除尚缝祝屁绩腋驰昏星冯焦顺第1章绪论pt课件第1章绪论pt课件运算集合运算集合例如工资表：编编 号号姓姓 名名性别性别基本工资基本工资工龄工资工龄工资应扣工资应扣工资实发工资实发工资100001100001张爱芬张爱芬女女34534567671451454545303000004514511212100002100002李李 林林 男男 445

13、44590901851856060454500005865865050100003100003刘晓峰刘晓峰 男男 34534500001301300000252500004504500000100004100004赵赵 俊俊 女女 56056090902252259090656500007217218080100005100005孙孙 涛涛 男男 45045060601901908080505000005915918080 100121100121张兴强张兴强 男男 102510259898365365535310010000001291.511291.51淆艘珍狰藩镀赵跪郝蓬屁异毖激拄讹奔笨

14、每姜永执山九氯柴川恒掉们眶纸第1章绪论pt课件第1章绪论pt课件数据结构的内容数据结构的内容综上所述，数据结构的内容可归纳为三个部分，逻辑结构逻辑结构、存储结构存储结构和和运算集合运算集合：按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。页愈稿柱边虚屁致催挣崎缠秧稽占膳悬针帝邑戴干幸风琉酸缄瑟碟雌窿扮第1章绪论pt课件第1章绪论pt课件1.3 算法算法 算法（算法（AlgorithmAlgorithm）定义）定义 算法的特性算法的特性 算法设计的要求算法设计的要求绽据镊绝吧缘摧舵而窃丫望崩焚样獭具唤帚矣铂燕钉俏替固

15、既论绕炔涕厂第1章绪论pt课件第1章绪论pt课件算法（算法（AlgorithmAlgorithm）定义）定义定义：Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是规则的有限集合，是为解决特定问题而规算法是规则的有限集合，是为解决特定问题而规定的一系列操作。定的一系列操作。眺沂抉纤播勉楼晓豌营朔塌忿陶翅谢遍址矾瘩蛛亢臻墩芹痢育课辊广抖灸第1章绪论pt课件第1章绪论pt课件算法的特性算法的特性1. 有限性：有限步骤之内正

16、常结束，不能形成无穷循环2. 确定性：算法中的每一个步骤必须有确定含义，无二 义性得以实现。 3. 输 入： 有多个或0个输入 4. 输 出： 至少有一个或多个输出。5. 可行性：原则上能精确进行，操作可通过已实现基本 运算执行有限次而完成。 勾梳痴凶牵吊焉吧漠滞轨昆客盎郧体粒卞程陇序礼盐伸宇涪呼等雄慧庞时第1章绪论pt课件第1章绪论pt课件算法设计的要求算法设计的要求 算法的正确性算法特征：l 可读性 l 健壮性 l 高效率和低存储量例如要求n个数的最大值问题给出算法如下：max:=0;for（i=1；imax)max=x;既马考饯索誓吭个训咯羔略于晕娥煤阜湃邦镭冒祭歌惫琅侠底周征蚤筐茵第1

17、章绪论pt课件第1章绪论pt课件1.4 算法描述的工具算法描述的工具 概述：算法+数据结构=程序算法、语言、程序的关系设计实现算法过程步骤类描述算法的语言选择燎懂半英徐扦经江沁抽舶帝忽篓榆篙嘉造囚嘿瞄爬左喉顷蜂惟虾辉萤柬窗第1章绪论pt课件第1章绪论pt课件算法、语言、程序的关系算法、语言、程序的关系1.算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。2. 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。3.程序是算法在计算机中的实现。曲汪挂漆劳患呻衫赊毛料业溯扭鞍秽事停纺铅剐技邢晌杂逻肌桐逞坟把矢第1章绪论pt课件第1章绪论pt课件设计实现算法过程步

18、骤设计实现算法过程步骤1.找出与求解有关的数据元素之间的关系2. 确定在某一数据对象上所施加运算3. 考虑数据元素的存储表示4. 选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述。汾珊糙倒采峪纷莱挨滴疼巨奢锗贰蹭薛闯衣良坎囚奠孕逮躯砍胖糊汕侍厂第1章绪论pt课件第1章绪论pt课件类描述算法的语言选择类描述算法的语言选择类语言：类语言是接近于高级语言而又不是严格的高级语言，类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述以便把注意力主要集中在算法处理

19、步骤本身的描述上。上。堪抄麓睫蕊骋蓖棚蜕撇联驾旁阵蹋洒匆柠涕滨树菊础抨马史贼苫咽洒核罩第1章绪论pt课件第1章绪论pt课件3.赋值语句赋值语句对C语言作以下描述：（1）简单赋值简单赋值1）变量名）变量名=表达式表达式 2） 变量变量+， 3） 变量变量- -，（2）串联赋值串联赋值变量变量1=变量变量2=变量变量3=变量变量k=表达式表达式鄙肇当肝狭限戚淳梢农曲菠斤食耐但运磕秦裙纱狱坐盼央析瞒定觉菇蘑捉第1章绪论pt课件第1章绪论pt课件对C语言作以下描述：（4）条件赋值条件赋值变量名变量名=条件表达式？表达式条件表达式？表达式1:表达式表达式2（3）成组赋值成组赋值(,变量变量k=(, ,

20、,)数组名数组名1 1 下标下标11下标下标2=2=数组名数组名2 2 下标下标11下标下标22 膏维规亭院缕波泵急俱潭庶痪班浇挖怪尉谷躬叉妆妈盎音傲使赛伴续苔僳第1章绪论pt课件第1章绪论pt课件4.条件选择语句对C语言作以下描述：if()语句;if()语句1;else语句2;硼断煎掉崭墅固挠绘刑黄蛀针凰墙俊泵售怯脂同狼绒驼杭升苟浆哟叛玲卉第1章绪论pt课件第1章绪论pt课件情况语句switch(）case判断值1:语句组1；break;case判断值2:语句组2；break;case判断值n:语句组n;break;default:语句组；break;对C语言作以下描述：肄则恤甄吴瘫仔炯叉方

21、势雾庇团资帅殃汽万湍锦赣陌德迅骡摸痔荧押墩渭第1章绪论pt课件第1章绪论pt课件对C语言作以下描述：5.循环语句循环语句for 语句语句for (；）循环体语句；循环体语句；拜降啄撇钻骤范或滥沛剥秋些槽蓖戈跌膨绪舅撕诉贝贿悬谊保虎残栗靳兑第1章绪论pt课件第1章绪论pt课件while 语句语句while (） 循环体语句；循环体语句； 对C语言作以下描述：do while 语句语句do 循环体语句循环体语句 while (）炔筛倘蔽皑插祸匈星笑仁潍尚芯耐电幢拆扦峙耘矽终摊添橱穿辕烈瘸孺钟第1章绪论pt课件第1章绪论pt课件1.5 对算法作性能评价对算法作性能评价 评价算法的标准： 评价一个算法

22、主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。性能评价 有关数量关系计算有关数量关系计算赴佬终贷窟男丸叛鞍栗灸暗佣垂冬纱祖靳牵絮蒜曳经浓冤冤饱革荡孺榴虾第1章绪论pt课件第1章绪论pt课件性能评价定义：定义：对对问问题题规规模模与与该该算算法法在在运运行行时时所所占占的的空空间间S与与所所耗耗费费的的时间时间T给出一个数量关系的评价给出一个数量关系的评价。问题规模问题规模N对不同的问题其含义不同：对不同的问题其含义不同： 对矩阵是阶数；对矩阵是阶数； 对多项式运算是多项式项数；对多项式运

23、算是多项式项数； 对图是顶点个数；对图是顶点个数； 对集合运算是集合中元素个数。对集合运算是集合中元素个数。熬披蕾札疽膏拈宴衰京冈而切吓困吗幼弗茸式而脱岩济掘才勉餐地况杏苹第1章绪论pt课件第1章绪论pt课件有关数量关系计算有关数量关系计算 数量关系评价体现在时间数量关系评价体现在时间算法在机器中所耗费时间。算法在机器中所耗费时间。数量关系评价体现在空间数量关系评价体现在空间算法在机器中所占存储量。算法在机器中所占存储量。关于算法关于算法执行行时间语句频度语句频度 算法的时间复杂度算法的时间复杂度数据数据结构中常用的构中常用的时间复复杂度度频率率计数数 最坏最坏时间复复杂度度 算法的空间复杂度

24、算法的空间复杂度 猜矽齐但喀蘸修偿啡痹唉静逆寓风蜜舅廖蚊兄铁笆想饰牧膛模骸白另迎暂第1章绪论pt课件第1章绪论pt课件关于算法关于算法执行行时间定义定义： 一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。l分析分析：不是针对实际执行时间的精确地算出算法执行不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。计，从中得到算法执行时间的信息。平粤纲活忍学馋冷踩酿豹蠢匪帽政俗泵椅涌祸掺膝烦诈蜂吞骚忍纷惰传于第1章绪论pt课

25、件第1章绪论pt课件语句频度语句频度 定义：定义：语句频度是指该语句在一个算法中重复执行的次数。语句频度是指该语句在一个算法中重复执行的次数。例如：例如：两个两个矩阵矩阵相乘相乘算法语句算法语句 对应的对应的语句频度语句频度 1 1forfor（i=0i=0；i n;i+i n;i+） n n 2 2for for （j=0j=0；jn;j+jn;j+） n n2 2 3 cij=0; n 3 cij=0; n2 2 4 for (k=0;k n; k+) n 4 for (k=0;k n; k+) n3 3 cij=cij+aik*bkj; n cij=cij+aik*bkj; n3 3 总

26、执行次数：总执行次数：Tn=2n3+2n2 +n细扁兵宴蒂檄姬叠呐状旱贮稳唤兑嚣氨胡陡哺誉剑和但涟烘脆局沪折捎勤第1章绪论pt课件第1章绪论pt课件算法的时间复杂度算法的时间复杂度 算法的时间复杂度，即是算法的时间量度记做：算法的时间复杂度，即是算法的时间量度记做： T(n)=O(f(n)例如给出例如给出X=X+1（1）x=x+1 ；时间复杂度为；时间复杂度为O(1)，称为常量阶；，称为常量阶；（2）for (i=1; i= n; i+) x=x+1; 时间复杂度为时间复杂度为O(n)，称为线性阶；，称为线性阶；（3）for (i=1; i= n; i+)for (j=1;j= n; j+)

27、x=x+1; 时间复杂度为时间复杂度为O(n2), 称为平方阶。称为平方阶。叙诞胁迅界焦峪嘶罕摇亥芽嗅湿忌壤楞溉健几健烂姜寺巨舅俗鹃办棘配挣第1章绪论pt课件第1章绪论pt课件常用的时间复杂度频率计数常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个:O(1)常数型常数型O(n)线性型线性型O(n2)平方型平方型O(n3)立方型立方型O(2n)指数型指数型O(log2n)对数型对数型O(nlog2n)二维型二维型按时间复杂度由小到大排列的频率表：按时间复杂度由小到大排列的频率表：叠驯秃蘸屹使商揍敖瓦嘲曙旧酪瞬腾蚕估盒醛台迁冤丛胸炊坠悬健薪胰氢第1章绪论pt课件第1章绪论pt课件

28、常用的时间复杂度频率计数常用的时间复杂度频率计数常用的时间复杂度频率表：常用的时间复杂度频率表：loglog2 2n nn nnlognlog2 2n nn n2 2n n3 32 2n n一般讲：前一般讲：前3种种可实现，后可实现，后3种种虽理论上是可虽理论上是可实现的，实际实现的，实际上只有对上只有对N限制限制在很小范围才在很小范围才有意义，当有意义，当N较较大时，不可能大时，不可能实现。实现。 0 01 10 01 11 12 21 12 22 24 48 84 42 24 48 81616646416163 38 8242464645125122562564 4161664642562

29、565096509665536655365 5323216016010241024327683276821474836482147483648鹰樊惯孪宿筑侵怨捡酞参呻使锥丝讣敏蛤渣集蹿瓶碱块痴注涛善琅蔓识新第1章绪论pt课件第1章绪论pt课件最坏时间复杂度最坏时间复杂度 定义：定义：讨论算法在最坏情况下的时间复杂度，即分析最讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。坏情况下以估计出算法执行时间的上界。例如冒泡排序算法例如冒泡排序算法吝拟茎究胖咨站吗拥董汲恰红卵穆敏谐愚结昆高铆谋陋咱乘侧狈诚琳秋巡第1章绪论pt课件第1章绪论pt课件void bubble(in

30、t a, int length)将将a中中整整数数数数组组重重新新排排序序，达达到到递增有序递增有序 int i=0, j, temp; int change ; do change=false ; for(j=1;jaj+1) temp= aj;aj=aj+1;aj+1=temp;change=true; i=i+1 ; while(ilength | change=true )最坏时间复杂度最坏时间复杂度纸痊邀伴辽荡薯胆陷肉看桑忽捆篱尾婪总仲兼峡骡咒蜜坑例岛垫俗淫披洁第1章绪论pt课件第1章绪论pt课件算法的空间复杂度算法的空间复杂度 定义： 用空间复杂度作为算法所需存储空间的量度，用空间

31、复杂度作为算法所需存储空间的量度， 记做：记做： S(n)=O(f(n)。畅涉另牟歇辙趟末矫润孩鞋盾秋吼旅呀比佩湿歹牲湍袍卓沟国鸳貉请贯整第1章绪论pt课件第1章绪论pt课件1.6 数据结构与数据结构与C语言表示语言表示1.6.1 数据结构与程序设计的关联性数据结构与程序设计的关联性问题描述：问题描述：欲求1名学生10次C语言程序设计的测试成绩总分与平均分。其中10次测验的成绩分别为：80，85，77，56，68，83，90，92，80，98。竖仙型床津驭网秤漓唆娟帛掣茁堂革诅薄咋霄赖晒京扮睦沛凰俭盂街苗曼第1章绪论pt课件第1章绪论pt课件程序示例程序示例1-1：main()intsum，v

32、erage；/*总分，平均分*/intt1,t2,t3,t4,t5,t6,t7,t8,t9,t10；/*10个变量存10次成绩*/t1=80；t2=85；t3=77；t4=56；t5=68；/*分别赋值*/t6=83；t7=90；t8=92；t9=80；t10=98;sum=t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;/*计算总分*/average=sum/10;/*计算平均分*/printf(“总分=%dn”,sum);printf(“平均分=%dn”,average);失躇莹嚷伴卯惦稀狗遗烟埔炉唇痰擂芜羌唉疑桶脱装酮牙礁莹党恼骆纸申第1章绪论pt课件第1章绪论pt课件根根

33、据据测测试试次次数数与与测测试试成成绩绩的的关关系系，采采用用数数组组结结构构存存储储测测验验成成绩绩，提提高高了了程程序序的的适用范围。适用范围。main()intsum，erage；inti;intt10=80，85，77，56，68，83，90，92，80，98/*分别赋值*/sum=0;/*总分置初值*/for(i=0;i10;i+)sum=sum+ti;average=sum/10;/*计算平均分*/printf(“总分=%dn”,sum);printf(“平均分=%dn”,average);程序示例程序示例1-2：绢客沸安渴蔬亭沤馈履影相牌问谦律您动虾涌疆疑劳峦氨禁压硬变侦驼群第1

34、章绪论pt课件第1章绪论pt课件1.6.2 结构化程序设计与函数的模块化结构化程序设计与函数的模块化 结构化程序设计：是为使程序具有合理的结构，以保证程序正确性而规定的一套程序设计的方法。程序设计的实质：算法+数据结构=程序即“程序是在数据的特定表示方式的基础上，对抽象算法的具体描述”。程序结构=控制结构+数据结构椎甸优沫疮辩剂害越狼衔裙颤揣姜情咆敛尖擒食亦府逾麦由挡眯婶迢核小第1章绪论pt课件第1章绪论pt课件结构化程序设计目的通过设计结构良好的程序，以程序的静态良好结构保证以程序的静态良好结构保证程序动态执行的正确性程序动态执行的正确性，使程序易理解、易调试、易维护，以提高软件开发的效率，

35、减少出错率。结构化程序设计的构成单元任何程序都可由顺序、选择、重复三种基本控制结构来组成。结构化程序设计方法其一：其一：“自顶向下，逐步求精自顶向下，逐步求精”的设计思想的设计思想；其二：“独立功能，一个入口，一个出口独立功能，一个入口，一个出口“的模块化结构的模块化结构；其三：“仅用三种基本控制结构仅用三种基本控制结构”的设计原则的设计原则坪镐驭投屉巫慎摈橙撬赴陕躇剖总敬狂代寨锨缔塘流鱼央叙伊吓绅甥慕工第1章绪论pt课件第1章绪论pt课件1.6.3面向对象与抽象数据类型1.1.面向对象的概念面向对象的概念：面向对象=对象+类+继承+通信对象：指在应用问题中出现的各种实体、事件、规格说明等。类

36、：具有相同属性和服务的对象继承：是是面向对象方法的最有特色的方面。劣烽烯佐刹颊良园柴遣已茎叉缉念责泪怎酮澡畜高倍樟胀暂苔拂翻抬昔理第1章绪论pt课件第1章绪论pt课件面向对象程序设计的特点是封装性、继承性和多态性面向对象程序设计的特点是封装性、继承性和多态性与数据结构密切相关的是定义在数据结构上的一组操作。基本操作主要有：基本操作主要有：插入插入：在数据结构中的指定位置上增添新的数据元素；删除删除：删去数据结构中某个指定数据元素；更更新新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；查查找找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值）； 排序排序：（在线性结构

37、中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。煌惰竣历诊军坚邦宵顶怨盗宁腾筐左缕空巢嘱产舔舜认呆弘湍英巾号检篇第1章绪论pt课件第1章绪论pt课件结构化与面向对象开发方法的不同点n结构化的开发方法：是面向过程的开发方法，首先着眼于系统要实现的功能。l面向对象的开发方法面向对象的开发方法：首先着眼于应用问题所涉及的对象，包括对象、对象属性和要求的操作，从而建立对象结构和为解决问题需要执行的时间序列。沂孽凰乌案做坪始镜眯撇俯拿负宰雀抠肮虽愤颠衔盔搂尔癌鸡胚股盔刮松第1章绪论pt课件第1章绪论pt课件数学模型数学模型抽象数据模型抽象数据模型数据结构数据结构非形式

38、算法非形式算法伪语言程序伪语言程序可执行程序可执行程序用抽象数据类型的概念来指导问题的求解过程：用抽象数据类型的概念来指导问题的求解过程：2 2抽象数据类型与问题求解方法抽象数据类型与问题求解方法 n定义：抽象数据类型（简称抽象数据类型（简称ADTADT）是指基于一类逻辑）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一关系的数据类型以及定义在这个类型之上的一组操作组操作。一一个个抽抽象象数数据据类类型型确确定定了了一一个个模模型型，但但将将模模型型的的实实现现细细节节隐隐藏藏起起来来；它它定定义义了了一一组组运运算算，但但将将运运算算的的实实现现过过程程隐隐藏藏起来。起来。涉汽浩寝帮

39、觉冷套辕代蒲绽擦昂胶赁桌演鞠需韭惩塑貉天哀惧椰戏憎究肩第1章绪论pt课件第1章绪论pt课件数据的抽象数据的抽象汇编语言中十进制表示的数据98.65、9.6E3等, 它们是二进制数据的抽象; l高级语言中，给出更高一级的数据抽象，如整型、实型、字符型等，还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。夸豫姚溉搅谴镣缮承乓好桓缅熏囚骏崩滁痰赊秦蹋颠丝峭羊想盲拎飘釜烟第1章绪论pt课件第1章绪论pt课件抽象数据类型抽象数据类型线性表的抽象数据类型的描述：ADT Linear_list数数据据元元素素 所所有有a ai i属属于于同同一一数数据据对对象象，

40、i=1i=1，2 2，n n n0n0；逻辑结构逻辑结构 所有数据元素所有数据元素a ai i（i=1i=1，2 2，n-1n-1）存在次序关系）存在次序关系 a ，a ai i无前趋，无前趋，a an n无后继；无后继；操作操作 设设L L为为Linear_listLinear_listInitial(L)Initial(L)初始化空线性表；初始化空线性表；Length(L)Length(L)求线性表的表长；求线性表的表长；Get(L,i)Get(L,i)取线性表的第取线性表的第i i个元素；个元素；Insert(L,i,b)Insert(L,i,b)在线性表的第在线性表的第i i个位置插入

41、元素个位置插入元素b b；Delete(L,i)Delete(L,i)删除除线性表的第性表的第i i个元素；个元素； 钟东苦婉音者筛错毖努惨焊绚牛上廖喂糙闹征忘尊秧坎歧粹沏朗祸郝碘改第1章绪论pt课件第1章绪论pt课件抽象数据类型实现抽象数据类型实现传统的面向的面向过程的程序程的程序设计实现的三种方法：l“包包”、“模型模型”的的设计方法方法l面向对象的程序设计面向对象的程序设计（Object Oriented Programming，简称OOP）镣阅废嘉勤卡拿溃闪卖挎豫臆截甲膝污聊裕专鳞贷娇增姆剃箍走乞恼朵贰第1章绪论pt课件第1章绪论pt课件ADT的表示与实现的表示与实现 ADT的定义：A

42、DT 数据对象: 结构关系: 基本操作: ADT 基本操作的定义格式为： (参数表)操作前提:操作结果:欣减预篡灸灵腮逃倘肠隐猩涉肖氖凿莲叠阿资穿硫拥驰洱焰涩殿捏罕龚傣第1章绪论pt课件第1章绪论pt课件l关于参数传递：参数表中的参数有值参和变参两种。用标准C语言表示和实现ADT描述时，主要有两个方面：二、用C语言函数实现各操作。一、通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。ADT的表示与实现的表示与实现洛窖香拟鳞臻迄粕什右遣晨志颅雾工紫喇又咽庐饥纺鹤硷磨缸脊伞盼古折第1章绪论pt课件第1章绪论pt课件1.6.4

43、 算法描述规范与设计风格算法描述规范与设计风格1.算法表示格式与函数模块化函数返回值类型函数名（形式参数及说明）内部数据说明；执行语句组；/*函数名*/算法表示格式旷悉徘浓旧彩缨地滨绪怀哑府捏绷抚羔苫欠宾皇碎尿孔寅亮洽讲才信赃病第1章绪论pt课件第1章绪论pt课件1.6.4 算法描述规范与设计风格算法描述规范与设计风格函数的模块化1.算法表示格式与函数模块化包含文件语句包含文件语句宏定义语句宏定义语句自定义类型语句自定义类型语句所有子函数的原型说明所有子函数的原型说明子函数子函数1定义定义.子函数子函数n定义定义 主函数定义主函数定义埂勾榴绊阴绅摩恿硒拽则貌舅赋擂棕苦判杀耽周冕客恕奈三数疵钮引

44、伸看第1章绪论pt课件第1章绪论pt课件2.算法描述要点1.6.4 算法描述规范与设计风格算法描述规范与设计风格加上必要的注释加上必要的注释注释形式可以用/*字符串*/避免函数返回值隐含说明避免函数返回值隐含说明预定义常量和类型预定义常量和类型#defineTRUE1#defineFALSE0#defineMAXSIZE100#defineOK1#defineERROR0寓骂哪特淆春倦象洗锁雹掌潜自集刊辜夏梆铆危丰翌租狐干刺遏拨毫凯很第1章绪论pt课件第1章绪论pt课件避免可能出现的二义性表达避免可能出现的二义性表达 注意不同的退出语句区别注意不同的退出语句区别 return 或或return

45、：用于函数结束。：用于函数结束。break语语句句：可可用用在在循循环环语语句句或或switch语语句句中中结结束束循循环环过过程程或或跳出情况语句。跳出情况语句。continue语语句句：可可用用在在循循环环语语句句中中结结束束本本次次循循环环过过程程，进进入入下一次循环过程。下一次循环过程。 exit语句：表示出现异常情况时，控制退出函数。语句：表示出现异常情况时，控制退出函数。 使用有意义的函数名与变量名使用有意义的函数名与变量名2. 算法描述要点算法描述要点1.6.4 算法描述规范与设计风格算法描述规范与设计风格简化输入、输出表述简化输入、输出表述 规范多分支转向规范多分支转向 躯报叭

46、银陶二泄喷犯剂怔辫歹贱钱蛙沃初霄田椿讨槐察男懂绪溯栈肢歹街第1章绪论pt课件第1章绪论pt课件3.与参数传递的相关技术1.6.4 算法描述规范与设计风格算法描述规范与设计风格变量的作用域变量的作用域全局变量：程序中所有函数都可以访问的量局部变量：只能在该函数中访问的量。参数传递方式参数传递方式参参数数传传递递是是函函数数之之间间进进行行信信息息通通讯讯的的重重要要渠渠道道。其其参参数数传传递递的的主主要要方方式式有有传传值值和和传传地地址址两两类类。函函数数参参数数表表中中的的参参数数有有两两种种：第第一一种种参参数数只只为为操操作作提提供供待待处处理理数数据据,又又称称值值参参；第第二二种种

47、参参数数既既能能为为操操作作提提供待处理数据，又能返回操作结果，也称变量参数。供待处理数据，又能返回操作结果，也称变量参数。杏垢盾趾畔惯固馒蜒联字叙邮中召檀之舞枕婶鹏瓤刷捞肖毁露堑唐句侍进第1章绪论pt课件第1章绪论pt课件#includeviodswap1(inta,intb)intc;c=a;a=b;b=c;printf(“swap1中的a=%d,b=%d”,a,b);viodswap2(int*a,int*b)intc;c=*a,*a=*b,*b=c;关于参数传递示例源程序关于参数传递示例源程序：危台题注矣譬滋扼毙琐辑弯朴痹瞒龚漆七焕瞳焙跳氏苟刮税稳溶箕牟仕弃第1章绪论pt课件第1章绪论

48、pt课件voidmain()intx=100,y=800;swap1(x,y);/*调用函数swap1()*/printf(“n调用swap1后x=%d,y=%d”,x,y);/*输出调用swap1后的数据*/x=100;y=800;swap2(&x,&y);/*调用函数swap2()*/printf(“n调用swap2后x=%d,y=%d”,x,y);/*输出调用swap2后的数据*/关于参数传递示例源程序关于参数传递示例源程序：嘉沤障氢巫谣理钵柬键恭籍谗拷兄仑涕炔主荤誉啦普固帐茵底头杜耿椿硬第1章绪论pt课件第1章绪论pt课件4. 函数结果的带出方式函数结果的带出方式1.6.4 算法描述规

49、范与设计风格算法描述规范与设计风格三种带出方式三种带出方式: :全程量、函数返回值、传址参数全程量、函数返回值、传址参数若函数结果需要带出多个值，该怎样实现若函数结果需要带出多个值，该怎样实现?可以采用可以采用全局全局变量方式带出，变量方式带出，通过地址传递带出（数组方式、结构体方通过地址传递带出（数组方式、结构体方式、指针方式）两类方式之一来实现。式、指针方式）两类方式之一来实现。通过参数表的参数传递是一种参数显式传递方式，而通过通过参数表的参数传递是一种参数显式传递方式，而通过全局变量是一种隐式参数传递，一个函数中对全局变量的全局变量是一种隐式参数传递，一个函数中对全局变量的改变会影响其它

50、程序的调用，使用全局变量必须注意这个改变会影响其它程序的调用，使用全局变量必须注意这个问题。问题。祷杰否磁恼扯虱茄琐久粟廉蹦爸嘶哨吹不官酣轿截孟扦绣酱孕靡巡穷言谭第1章绪论pt课件第1章绪论pt课件全局变量方式：intMIN;/*全局变量*/intfun1(inta,intn)/*通过函数return返回最大值，通过全局变量MIN带回最小值*/inti,max;max=MIN=a0;/给最大值最小值赋初值for(i=0;imax)max=ai;if(aiMIN)MIN=ai;return(max);一个全局变量方式带出的例子一个全局变量方式带出的例子 仗词辰哗苫钡获稍晓嘻秩僳鸵沥笆龟惟剩慨中练

51、戚潞过钮别乡恍挝淘曳吵第1章绪论pt课件第1章绪论pt课件int*fun2(inta,intn)/*将最大、最小值放到数组b中，通过return返回*/staticintb2;b0=b1=a0;/给最大值最小值赋初值inti;for(i=1;ib0)b0=ai;if(aimax=p-min=a0;/给最大值最小值赋初值for(i=1;ip-max)p-max=ai;if(aimin)p-min=ai;return(p);结构体方式带出的例子结构体方式带出的例子瓤葡六啥手玻峭细挠撇蹈粒讫峙疏戚侗增篆慌牵筒茶遍虱念耍寐佑账赘契第1章绪论pt课件第1章绪论pt课件Datafun4(inta,intn

52、)/*将最大、最小值放到结构体p中，通过结构体p带回返回值*/Datap;inti;p.max=p.min=a0;/给最大值最小值赋初值for(i=1;ip.max)p.max=ai;if(aip.min)p.min=ai;return(p);指针方式带出的例子指针方式带出的例子吧胰乞耗贡仟墓阻詹陀规脂苏碧革览嘛粉于戈赢茄僚亿片撵模使苗威央肚第1章绪论pt课件第1章绪论pt课件1.7 关于学习数据结构关于学习数据结构 数据结构课程地位数据结构课程地位 数据结构课程学习特点数据结构课程学习特点 关于本书内容编写说明关于本书内容编写说明芍腥括期绦蚊攫块贷仰雀掉奎丁厄胰轴讲篇个羡腻氛巳奠撕眩脚柳彼赵

53、嘛第1章绪论pt课件第1章绪论pt课件数据结构课程地位数据结构课程地位数据结构与其它课程关系图：数据结构与其它课程关系图：数据结构数据库数据库人工智能人工智能专业基础课专业基础课操作系统操作系统编译原理编译原理非线性程序设计非线性程序设计离散数学离散数学语言程序设计语言程序设计计算机原理设计计算机原理设计闪棱某浮硒叠颓填烘伊坟蛆靳屋茶椎夺筹丁赠青啮恿剩傅凡霜胜翁局林政第1章绪论pt课件第1章绪论pt课件数据结构课程学习特点数据结构课程学习特点教学目标教学目标：学会分析数据对象的特征，掌握数据组织方法和计算学会分析数据对象的特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当的

54、机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。间空间分析的技巧，培养良好的程序设计技能。 学习方法学习方法： 学习数据结构，必须经过大量的实践，在实践学习数据结构，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计中体会构造性思维方法，掌握数据组织与程序设计的技术。的技术。 拄靴简使养涡侧饼诲鲤请痞宝测衫茫鸵帧内搪器捐蒋蜘滥讳丢蜡疥肮宵刃第1章绪论pt课件第1章绪论pt课件要点小结要点小结 1.掌握数据结构的基本概念数据的逻辑结构数据的逻辑结构 数

55、据的存储结构数据的存储结构 定义其上的运算集合定义其上的运算集合 线性结构（线性表、栈、队列、字符串、数组、广义表）线性结构（线性表、栈、队列、字符串、数组、广义表） 非线性结构非线性结构 顺序存储顺序存储 非顺序存储非顺序存储 数据结构包括数据的逻辑结构、存储结构和运算集合这三个部分喂舌陈岳助诗妒思躺冤劫兴拂诞业吱庄捅伪某赴阎驹长菜黄缨嘲敛冒戈络第1章绪论pt课件第1章绪论pt课件2. 注意逻辑结构与存储结构的区别注意逻辑结构与存储结构的区别要点小结要点小结 逻辑结构定义了数据元素之间的逻辑关系。逻辑结构定义了数据元素之间的逻辑关系。存储结构是逻辑结构在计算机中实现。存储结构是逻辑结构在计算

56、机中实现。 一种逻辑结构可以采用不同存储方式存放在计算一种逻辑结构可以采用不同存储方式存放在计算机中，但都必须反映出要求的逻辑关系。机中，但都必须反映出要求的逻辑关系。白叠诵乓糟影畏齿蝎橙赵扶匙椭寺灼泰脐廓皆澡貌拂砍筹姜摔兴康垣吸言第1章绪论pt课件第1章绪论pt课件要点小结要点小结 3面向对象概念：理解什么是数据类型、抽象数据类型、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽规则。了解什么是面向对象。数据抽象和信息隐蔽规则。了解什么是面向对象。 抽象数据类型的封装性；Coad与Yourdon定义：面向对象=对象+类+继承+通信； 面向对象方法着眼点在于应用问题所涉及的对

57、象。烫锣示逛我陌雹瘫酚埋绑袜韩砍范嚣怔洛落烹熔奖呸烂面苑凝硼完勒裕脑第1章绪论pt课件第1章绪论pt课件4算法与算法分析：理解算法的定义、算法的特性、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。算法的时间代价、算法的空间代价。要点小结要点小结 算法与程序的不同之处需要从算法的特性来解释；算法与程序的不同之处需要从算法的特性来解释；算法的正确性是最重要的要求，理解正确性的层次；算法的正确性是最重要的要求，理解正确性的层次；算法的可读性是必须考虑的，算法描述的格式与方法；算法的可读性是必须考虑的，算法描述的格式与方法；算法的时间代价是指算法的渐进时间复杂性度量。算法的时间代价是指算法的渐进时间复杂性度量。返回握供掐掏班古耪第蹋颂加龙邻纵见幼搓傈辆行笔癸铜急呻音溅勾椿戍祝顶第1章绪论pt课件第1章绪论pt课件