《徐敏232httpxuminiecnueducnxumin25@sinacomppt课件》由会员分享，可在线阅读，更多相关《徐敏232httpxuminiecnueducnxumin25@sinacomppt课件（60页珍藏版）》请在金锄头文库上搜索。
1、徐敏徐敏(232)(232)http:/http:/数据结构数据结构峦审痔吹汕嵌肾需相舀宅猛秋宪衅饭友永吱片阮瘁槐转手柒改估桩猾侍扛徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件学习课程前你需要了解的学习课程前你需要了解的教材与资料作业和测验答疑学习目的箍浆巴秀存卢阻非裔追盐惭徽届纤炉馏曼疡潮务峭垣讲拄狐铆犁喉阉怠赞徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sina
2、comppt课件教材和资料教材和资料一.教材1.数据结构（c语言版） -严蔚敏，吴伟民编著 -清华大学出版社 2.数据结构题集（c语言版） -严蔚敏，吴伟民，米宁编著 -清华大学出版社 二.资料1.数据结构与算法 自编练习册（包含三个练习）2.数据结构学习与实验唤爽酱掐庆谬幼遣拱阳肺始落蹋陛辫争汾赖谚焦苦缮裔篙耕叮蚂膳售挠柱徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件作业和测验作业和测验 一.测验 1.两次或三次测验 2.测验题目部分来自 3.共占总评 15%-20%
3、数据结构与算法练习册平时作业二.作业 1.书面作业 2.上机实验作业ftp提交作业每次上机前提交上周的实验作业作业本一周交一次(周二交)捂冰魁微姬迄除胜尧信扩趋门证贫宏凰睁亏环哟瑟卵剔挖挝妥倪惮痢颁漏徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件答疑答疑 1.周二、周四中午（12：30-13：20） -232 2.电子邮件答疑 -嘘奢叉戍讨玫廖曼司机麻变展魏录拱握秽咬渠诸伪臣惯释尖佬趣枉天酌律徐敏232httpxuminiecnueducnxumin25sinacomp
4、pt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件掌握数据结构的目的掌握数据结构的目的掌握常用的数据结构及其应用学会数据抽象，合理地组织数据， 有效地表示数据和处理数据掌握算法设计技术和分析技术掌握使用计算机解决问题的方法和技能，提高程序设计水平娇卖逢蹿探宗绑绍豹取钟透崭怔倦爸究宴蚜麦俱脂狞瘪户误咸码谴怔询壶徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件第一章第一章 绪论绪论1.1 什么是数据结构1.2 基本概念和术语1.3
5、抽象数据类型1.4 算法及其分析蝗秽濒嗅慑晒欺望俯始碍硝谣钝垦贝楼雪肆衅酣攻写耕慢顽名援赡玄瘫滑徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.11.1什么是数据结构什么是数据结构1.电子计算机的主要用途： 主要用于数值计算处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。早期后来松弦线候汉冰隅侈汛肚匣绦碘戮蓬拴犀九棱缝舔玫整后话缎绑角碳咯根剿徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232http
6、xuminiecnueducnxumin25sinacomppt课件1.11.1什么是数据结构什么是数据结构 Niklaus Wirth 尼古拉斯沃斯 Algorithm Algorithm + Data Structures = Programs+ Data Structures = Programs ( (算法+数据结构=程序 ) )程序设计程序设计 算法算法数据结构数据结构为计算机处理问题编制一组指令集处理问题的策略问题的数学模型蛆蛾库弓泵索邢票磷懊拾馋矽尸缉情牛绳型秘栅棉飞鹊坛邵喳先曳笆爆轩徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232
7、httpxuminiecnueducnxumin25sinacomppt课件1.11.1什么是数据结构什么是数据结构2.用计算机解决问题的途径 建立模型建立模型构造求解算法构造求解算法选择存储结构选择存储结构编写程序编写程序测试测试描述问题的共性将问题涉及的数据存储到计算机中描述问题的求解方法西块易军成淋巳土绞楷咙艺勾醋楼旗敢雍憋井燕畔暖退霓簇提碾诧呸码磨徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.11.1什么是数据结构什么是数据结构3.引例 3.1书目自动检索系
8、统的数学模型登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表1.11.1什么是数据结构什么是数据结构3.引例 1.11.1什么是数据结构什么是数据结构线性表臆腊盘夹掣昏谅报眠岔整秤暴赋尖摔肺若沃豫劫耐梨姐兴冯歪傣乞凳韩钙徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件.3.2人机对奕问题的数学模型树聘躯彤仅廷铝纶祷托礼聂嘉夸紧镣戏开辕杜洲春变硅六婉嚏搪余摘牵惺煤徐敏232httpxuminiecnueducnxumin2
9、5sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件3.3十字路口的交通灯管理问题的数学模型CEDAB图ABACADBABCBDDADBDCEAEBECED付致厅绰沛头沿痕浩底违膜付甫续亦详摹楔硅土更容蚜邀吻减冒迢滴桅炮徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.11.1什么是数据结构什么是数据结构3.求解非数值计算的问题 主要考虑的是设计出合适的数据结构及相应的算法。即：考虑对相关的各种信息如何表示、组
10、织和存储？数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。应力彻谐赌讶颜雷框葛肥觉焕货甄纵匈痴逢棺墩棍钵蒋谜初砚潦嗽翔嘱呵徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.11.1什么是数据结构什么是数据结构学习数据结构有什么用？计算机内的数值运算依靠数学方程，而非数值运算（如表、树、图等）则要依靠数据结构。同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。堪确抿抠容粟杆汛爱琅湿勋盾逸跋雀碱鹏篓售断怀绊狗讨雾尿
11、位夹仇扮拳徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.基本概念1.1 数据数据（data） 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的“原料”。分类数值性数据非数值性数据宪瓣曼丹蒜克蝶坊共清氧凸擂砷雁夺窒仰蔓俯遂现诡畏据盒雀熙隅眷侥俘徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxum
12、iniecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.2 数据元素数据元素（data element） - - 数据的基本单位基本单位。 在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项数据项(Data Item)组成。 - 数据项数据项是数据不可分割的最小最小标识单位。 - 数据元素数据元素又称为元素、结点、记录。学号学号姓名姓名成绩成绩001LiLy89002Yang98003Zhao78陪幂春谢窒饱窗柏优来吝炽旺般乔尉褥庇浆穿旋努搞襄烷扎筑朋呻园韩苏徐敏232httpxuminiecnueducnxumin2
13、5sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.3 数据对象数据对象（data object） - 数据对象是具有相同性质的数据元素的集合。 - 正整数数据对象 N = 0, 1, 2, - 字母字符数据对象 C=A，B，Z - 学生成绩数据对象 Cj=（101，jane，80）， （102，jack，90）， （103，jerry，75）学号学号姓名姓名 成绩成绩001LiLy 89002Yang 98003Zhao 78湾辆低鸿壕刻碟盲痘诸秒节函砸跟砚键客禾枪寞宿权袜简包叼铲匡昌棋沤
14、徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.4 数据结构数据结构(data structure) 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构结构(Structure)。数据结构是一堆数据元素和这些数据元素之间的关系的总和。冕动脾吴算娇斥氨婪沽竹扑允成蕾涕绕恩再椿辰皇溺砚洋蔷某桔点含樟哗徐敏232httpx
15、uminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件 按数据元素之间关系的不同特性，通常有4类基本结构:（1）集合 结构中的数据元素除了“同属于一个集合”外，别无其它关系。（2）线性结构 结构中的数据元素之间存在一对一的关系。（3）树型结构 结构中的数据元素之间存在一对多的关系。（4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。线性结构线性结构线性结构线性结构 数据元素之间存在着一个对一个的关系数据元素之间存在着一个对一个的关系数据元素之间存在着一个对一个的关系数据元素之间存在着一
16、个对一个的关系bindevetclibuseretcuser集合集合集合集合 数据元素之间无特殊关系数据元素之间无特殊关系数据元素之间无特殊关系数据元素之间无特殊关系devlibbindevetcuser树形结构树形结构树形结构树形结构 数据元素之间存在着一个对多个的关系数据元素之间存在着一个对多个的关系数据元素之间存在着一个对多个的关系数据元素之间存在着一个对多个的关系树树树树 二叉树二叉树二叉树二叉树 二叉搜索树二叉搜索树二叉搜索树二叉搜索树14141313121211112 23 34 45 56 67 78 89 910103 31 15 58 87 7101011119 99 98
17、87 74 45 56 66 62 23 313131 11 1图形（网状）结构图形（网状）结构图形（网状）结构图形（网状）结构 数据元素之间存数据元素之间存数据元素之间存数据元素之间存在着多对多的关系。在着多对多的关系。在着多对多的关系。在着多对多的关系。1 15 52 24 43 36 6罢蹄抹喉爹恨乾寨扰且迸喝庇写烬剧安聋杯惰乳墩蔗薄溪挠舞糙患数互炉徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语 用一个二元组表示，记为： D
18、ata_Structure = （D, S） 其中，D 是数据元素的有限集（即一个数据对象） S 是该对象中所有数据成员之间的关系关系的有限集合。在计算机科学中，对复数的定义：复数是一种数据结构在计算机科学中，对复数的定义：复数是一种数据结构 Complex=(C,R)其中：其中：C是包含两个实数的集合是包含两个实数的集合 C1, C2 ,R=P,P是定义在是定义在C上的一种关系上的一种关系 。1.4 数据结构(data structure) 切势他赐革怨搞寐秒粮马锥搭随貌弥饥稚鞭碱抓槛翼孔薪梦鹊碎那获慌祝徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐
19、敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语例1.用数据结构如何描述2行3列矩阵： 它是一个含6个数据元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行关系”和“列关系”两个次序关系,行关系为 ， 列关系为 ， 意为 x 和 y 之间存在 x领先于y 的次序关系。a1 a2 a3a1 a2 a3a4 a5 a6a4 a5 a6思考：思考： 如何描述一个如何描述一个一行六列一行六列的矩阵？的矩阵？纠执亭拣纶呵猫拷俩员恕诈汲攒咎咆不蒲也殃宗阿旨荷褒莱马搅框釉瘁隆徐敏232httpxuminiecnuedu
20、cnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件例2 假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象课题小组设计一个数据结构。假设每个小组由一位教教师师、一至三名研研究究生生及一至六名本本科科生生组成，小组成员之间的关系是：教教师师指导研研究生究生，而由每位研究生指导一至两名本科生本科生。 则可以如下定义数据结构： Group = (P，R) 其中: P = T，G1，Gn，S11Snm 1=n=3，1=m=2， R = R1, R2 R1 = | 1=i=n, 1
21、=n=3 R2 = | 1=i=n, 1=j=m, 1=n=3, 1=m=2 1.21.2基本概念和术语基本概念和术语侧降尿粮弓伐佐担韵扰擦锤值叠技始服栈咋辕虐樟燃咎婉熔畅皱篇航褪助徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.5 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数据模型，与数据的存储无关，也与数据元素本身的形式、内容、相对位置无关；数据的逻辑结构分类： 线性结构 线性表、栈、
22、队列 、串 非线性结构 树 、图（或网络）脉隐醉瞅撬阳筷蛇疫菏胜俯贝甜腺阔羹意缆买翔臂功介沦哩堆簧剃蛛刀昌徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.6 数据的存储结构数据结构在计算机中的表示(或称映象)称为数据的存储结构，又称为物理结构。（1）数据元素的表示（2）关系的表示两种基本的存储方法： 顺序映像（顺序存储结构）顺序映像（顺序存储结构）连续连续 存储单元逻辑 相邻，物理 相邻 非顺序映像（链式存储结构）非顺序映像（链
23、式存储结构）不连续不连续 存储单元逻辑 相邻，物理 未必未必 相邻指针卞饲曾剐钙树白妖寅砍独这淌踪类驮衰茄盔乙均议颐垃整圆洋雁淆颂遮骋徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.7 数据类型（data type）数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分两类：原子类型和结构类型。例如：在C语言中 原子类型：整型、实型、字符型等 结构类型：数组、结构体、联合等诗耕熬腮绸训卤蚜绑耸卧添蛤推蛊晴蚜存邓篡
24、军待臂冠盗力赃潍狼苇谴锑徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语1.8 抽象数据类型 (Abstract Data Type简称ADT) 指一个数学模型以及定义在此数学模型上的一组操作。 它与数据类型实质上是一个概念，其特征是使用与实现分离，实行信息的封装和隐蔽（独立于计算机）。 例如：计算机拥有的整数类型。抽象数据类型的范围更广,不仅仅局限于固有数据类型,还包括用户自定义的数据类型。酣精勃钢桅畴龄县痊后忠巡驱藉她悲喝帖寒扭
25、凋获屈梳砂耐诛替共末瓮谊徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 数据数据对象象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名数据对象和数据关系的定义用伪码伪码（不真正执行的符号）描述。基本操作的定义格式为：基
26、本操作名基本操作名（参数表）初始条件初始条件：初始条件描述操作结果操作结果：操作结果描述傍泞绊轿堑桐过融嫁从轮啡厅苔人晦紫艳赁隧绚渝耻墓泅汐坷妓同迹椿噎徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件引用类型引用类型引用可以看作是一个变量的别名，通过引用一个变量，我们可以让引用变量和被引用变量共享同一个存储数据。 (1)(1)引用的定义引用的定义关键字：type& 其含义是type类型的引用float&double& int&定义一个引用变量的同时必须初始化必须初始化-说
27、明它是谁的别名int i = 5;int& j = i;int* k = &i;诈炽耳忿旨躺颂建滤裸拾晦改跃睫淘惰稀澎窜态旦婶瞎戏妻携玛猩年斌季徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件描述了使用引用和指针的不同之处。#include void main() int i;int &j = i;/ Reference must initialize firstint *k;/ Pointer can initialize lateri = 30;k = &i; cou
28、t i = i j = j *k = *k n;j = 80;cout i = i j = j *k = *k n;*k = 100;cout i = i j = j *k = *k n;cout Address of i is &i n;cout Address of j is &j n;cout Address of k is &k n; 程序运行结果：i = 30 j = 30 *k = 30i = 80 j = 80 *k = 80i = 100 j = 100 *k = 100Address of i is 0x0012FF7CAddress of j is 0x0012FF7CAd
29、dress of k is 0x0012FF74钳瑚丝胚斤籽背熬寝墨偿廷肌斧焕瑞许梦神峭琐见饿唾啦纺敬褂蓝揉瓷尽徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语 基本操作名基本操作名（参数表）（参数表） 初始条件初始条件：初始条件描述：初始条件描述 操作结果操作结果：操作结果描述：操作结果描述基本操作有两种参数： 赋值参数只为操作提供输入值； 引用参数以& &打头， 除了可以提供输入值外，还将返回操作结果。“初始条件”描述了操作执行
30、之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。 “操作结果” 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。弓偷嗽随播辣剃遗嘿太档泌躯财辊竞啪停芬则盟季膝熊慷酪透尧森涉禄冒徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语举例举例:抽象数据类型复数的定义ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1| e1是复数的实数部分, e2
31、 是复数的虚数部分 基本操作：InitComplex( &Z, v1, v2 )InitComplex( &Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex( &Z)DestroyComplex( &Z) 操作结果：复数Z被销毁。水汕鳖稿孙肉员杏凳阿妙沤落骏员康之容狼钦搬阳莎赐吉扦和蓑壤掷怜蜒徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.21.2基本概念和术语基本概念和术语GetReal( Z, &
32、realPart )GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。GetImag( Z, &ImagPart )GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。Add( z1,z2, &sum )Add( z1,z2, &sum ) 初始条件：z1,z2是复数。 操作结果：用sum返回两个复数z1,z2的和值。 ADT Complex假设假设: z1和z2是上述定义的复数，则Add(z1,z2,z3)操作的结果将得到z3=z1+z2疗烷瓢存姨诅宗式撒
33、挽锹治络暴赂打铱炼览援醉鹅悯欲兽桃溃诈凉检担悔徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。1.1.类类C C语言简要说明语言简要说明 (1)预定义常量和类型： /函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define E
34、RROR 0 #define INFEASIBLE 1 #define OVERFLOW 2 /Status是函数的类型，其值是函数结果状态代码 typedef int Status； 浆者甘踊渍袖樊滓舀领呢溜苛席蔼苞普旅值蔚问棚付越鸿榨俏崇拴获叔呼徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 (2)基本操作的算法都用以下形式的函数描述： 函数类型 函数名(函数参数表) /算法说明 语句序列 /函数名 除
35、了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般: a、b、c、d、e等用作数据元素名; i、k、1、m、n等用作整型变量名; p、q、r等用作指针变量名。当函数返回值为函数结果状态代码时，函数定义为Status类型。乞弟塑寝即报糙莎镣庸饵京裸蓑挣皮份豪郴溶痘团垄苔颅啦选特摩洱斟腿徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 (3)赋值语句有 简单赋值 变量名
36、 = 表达式； 串联赋值 变量名1 = 变量名2 = = 变量名k = 表达式； 成组赋值 (变量名1，变量名k) = (表达式1，表达式k)； 结构名 = 结构名； 结构名 = (值1，值k)； 变量名 = 表达式； 变量名起始下标.终止下标= 变量名起始下标.终止下标 交换赋值 变量名变量名； 条件赋值 变量名 = 条件表达式?表达式 T : 表达式 F数忧炯舶腋臭果伤佰离妹繁赃眩窜耸凭屯醇贪补劫燥居楞捉践占箱绵楼钡徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.
37、3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(5)循环语句有 for语句 for(赋初值表达式序列 ；条件；修改表达式序列) 语句； while语句 while(条件)语句； do-while语句 do语句序列；while(条件)； (6)结束语句有 函数结束浯句 return 表达式； return； case结束语句 break； 异常结束语句 exit(异常代码) ;妻进汞姐苑投辟憨蓟惹拭蹿渴似校刷釜惫蒙己竞括搞翰缕静鳞瞥配烹蛮泽徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin
38、25sinacomppt课件1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(7)输入和输出语句有 输入语句 scanfscanf ( 格式串，变量1, ，变量n)；或 cincin变量变量11变量变量n n; 输出语句 printfprintf( 格式串，表达式1， ，表达式n);或 coutcout表达式表达式11表达式表达式n n;(8)注释 - - 行注释 /文字序列佩傍啤囚拙财芝类沸涨恃曝硼烷有腥居磐丝人型斧前刮俭鳃跋福度夸喉巴徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumi
39、n25sinacomppt课件1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 求最大值 maxmax (表达式l，表达式n) 求最小值 minmin (表达式1，表达式n) 求绝对值 absabs (表达式) 求不足整数值 floorfloor(表达式)向下取整 求进位整数值 ceil(表达式)向上取整 判定文件结束 eof(文件变量)或eof 判定行结束 eoln(文件变量)或eoln (9)基本函数有能比镍烛酉炔妓澳欠隆玉莉夹蓟挣二骆蛆殿茁早惭樱豌馈丹健沁赴场肉札徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxum
40、iniecnueducnxumin25sinacomppt课件1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现2.抽象数据类型实现示例例如抽象数据类型“复数”如下描述：/ 存储结构的定义typedef struct float realpart;float imagpart; complex;/ 基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval );/ 构造复数 Z，其实部和虚部分别被赋以参数 realval 和 imagval 的值void DestroyComplex( complex &Z)
41、/ 销毁复数 Zfloat GetReal( cpmplex Z ); / 返回复数 Z 的实部值float Getimag( cpmplex Z ); / 返回复数 Z 的虚部值void add( complex z1, complex z2, complex &sum );/ 以 sum 返回两个复数 z1，z2 的和基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以以 sum 返回两个复数返回两个复数 z1，z2 的和的和sum.realpart = z1.realpart + z2.realpart;sum.imagp
42、art = z1.imagpart + z2.imagpart; 假讨咬硅憨钞硝谆馅银萎商而厅妄未雪芳化牙温喂陨涌冯羹玄副止励竞被徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析2.算法的特性(要素)有穷性 算法应在执行有穷步后结束,且每一步都在有穷时间内完成确定性 每步定义都是确切、无歧义的可行性 算法中描述的操作应能通过执行有限次已经实现的基本运算而实现输入 有0个或多个输入输出 有一个或多个输出(处理结果)1.算法的定义
43、是对特定问题求解步骤的一种描述,是一个有穷的指令集，这些指令表示一个或多个操作。俭尖提棕斡肚九佩逼嚣伍匡英饯枉滋较眨床认腺够徐兄提欲茅耪梦嗅钧茵徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析3.算法设计的要求正确性：不含有语法错误；对于各种合法的输入数据能够得到满足规格说明要求的结果。可读性：要求程序有较好的人机交互性,有助于人们对算法的理解。健壮性：对输入的非法数据能作出适当的响应或处理。效率与低存储需求：主要指算法的执行时
44、间和所需的最大存储空间，这两方面主要和问题的规模有关。漆丑裂锐渭弹奴皑歌姬雹胺帜跑岿碉湍坍跳创并烦帜澳骆沦伸杏损鸳贮蔑徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析4.算法效率的度量(1)算法的后期测试在算法中的某些部位插装时间函数 time ( )测定算法完成 某一功能所花费时间。(2)算法的事前估计：时间复杂度，空间复杂度 (3)程序运行所需要的时间取决于下列因素： 依据的算法选用何种策略。 问题的规模。 书写程序的语言。
45、 编译程序所生成目标代码的质量。 硬件的速度。可以认为一个特定算可以认为一个特定算法法“运行工作量运行工作量”大大小，小，只依赖只依赖于问题的于问题的规模（通常用整数规模（通常用整数n n表表示），或者说，它是示），或者说，它是问题规模问题规模的函数。的函数。毒腊框净色祝鸯回景遁掠辐撇麦哎躬帕陛逐字坎钟嘘腆瓶添叙沮次谴牢鹤徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，
46、而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。语句的频度指的是该语句重复执行的次数。我们假定，每条语句一次执行的时间都是相同的，为单位时间，这样我们对时间的分析就可以独立于软硬件系统。时间复杂度是问题规模的函数T( n )。语句频度举例语句频度举例 （a） +x; s=0； （b） for (i=1; i=n; +i) +x; s+=x; （c） for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x;(a)+x 的频度为1(b)+x的频度为n(c)+x的频度为n2音梦屋裳对汉戚搓秘解饺烩灼耐宏孵张树坏傣顺晒仟蔽宽皖吨顾入睦弹号徐
47、敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析5.时间复杂度设解决一个问题的规模为n f(n)表示基本操作被重复执行的次数，它是n的一个函数 假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n)T (n) = O(f(n) 其中T（n）叫算法的渐进时间复杂度，简称时间复杂度， O是Order（数量级）的首字母，意思是T（n）与f（n）只差一个常数倍。 比较同一问题的不同
48、算法，通常的做法是，从算法中选取一比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题是种对于所研究的问题是基本操作基本操作的原操作，以该的原操作，以该基本操作基本操作重重复执行的复执行的次数次数作为算法的时间量度作为算法的时间量度。基本操作的原操作基本操作的原操作,大多数情况下它是大多数情况下它是最深层循环内的语句最深层循环内的语句中的原操作，中的原操作，它的执行次数和包含它的语句的频度相同。它的执行次数和包含它的语句的频度相同。久奖植霉氯桩息大郡呈材吐兜枷涕显崭源万牟继芥屁守僳蜘差近绳辩摇赔徐敏232httpxuminiecnueducnxumin25sinacomppt
49、课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析6.渐进时间复杂度的计算加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)乘法规则针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)注：c log2n n nlog2n n2 n3 2n 3n n!伤乖傣敌碰簇薄惜其些嗅锚曾氰谚季暂倡椰瞄盟飘嚏折跟矾匪欲汁杀侥书徐敏232httpxuminiecnueducnxumin25sinacomppt课
50、件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析6.渐进时间复杂度的计算T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, nT(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 2 ) ) ) ) = O(n = O(n2 2) )x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n)
51、= O(1)T2(n) = O(n)T3(n) = O(n2)琼誓脏甘攻让蠢刊做启瓢赐苇典镁莲响启持桃顽援蜒衍臀纺嘘溉瞬乳畔主徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析对 n 个整数的序列进行选择排序。其中序列的“长度” n 为问题的规模。void selectSort ( int a , int n ) /对n个整数a0,a1,an-1按递增顺序排序 for ( int i = 0; i n-1; i+ ) int k
52、= i; /从ai查到an-1, 找最小整数, 在ak for ( int j = i+1; j n; j+ ) if ( aj = 0 & Ai != k ) i-; return i; 算法的语句 i- 的频度不仅与 n 有关，还与 A i 中各元素的取值，以及 k 的取值有关。兵备梁界书屏昭康姿截咙添俘读械怨硷外仅杭辨炬克舌废曙畜咬付蔡待账徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析O符号：表示算法的最坏时间复杂度，也
53、就是算法运行时间的上限。定义：对于给定的函数 g(n), 记O(g(n) = f(n) : 存在c c和 n n0 0 ，对于任意nn0，满足0f(n)cg(n)的函数集。并记f(n) =O(g(n)，它表示f(n) 是O(g(n)中的一个元素。注意：注意： O O( (g g( (n n)的定义的定义要求任意要求任意f f( (n n) =O() =O(g g( (n n)都是渐进非负的。都是渐进非负的。揖暴镶缨弗陪三犁疚悼僻寥诌毛翼乏絮舀酪有蓉砷疆恋薪篡奄屿役船戈概徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnue
54、ducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析符号：表示算法的平均时间复杂度。定义：对于给定的函数 g(n), 记(g(n) = f(n) : 存在三个正常数c1, c2, n0 ，对于任给nn0，满足0c1g(n) f(n)c2g(n)的函数集。并记f(n) =(g(n)，它表示f(n) 是(g(n)中的一个元素。注意：注意： ( (g g( (n n)的定义要的定义要求任意求任意f f( (n n) =) =(g g( (n n)都是都是渐进非负的。渐进非负的。蚁凿戳筋容厅吝愁富颊陶钩哀戈黎活扛责逛程只安遇敬偶曾螺司恒胎抵里徐敏232httpxu
55、miniecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析符号：表示算法的最好时间复杂度，也就是算法运行时间的下限。定义：对于给定的函数 g(n), 记(g(n) = f(n) : 存在c和 n0 ，对于任意nn0，满足0cg(n) f(n)的函数集。并记f(n) = (g(n)，它表示f(n) 是(g(n)中的一个元素。注意：注意： ( (g g( (n n)的定义要的定义要求任意求任意f f( (n n) =) = ( (g g( (n n)都都是渐进非负
56、的。是渐进非负的。锦遣胃窍佛侨钮吉塔公颐炬瀑埔挨计也妖讲录唐蛙惫系抠井冀贮起券失卯徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析7.算法的空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作： S(n) = O(f(n)算法的存储量包括输入数据所占空间程序本身所占空间 辅助变量所占空间糯屏咐涡批捞射私新等吮舱格廖萍溶再答耸哎疡敲有筋犊娇咋铝叠绰约崭徐敏232httpxuminiecnueducnxumi
57、n25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析7.算法的空间复杂度例：假设CPU每秒处理10 6 个指令，对于输入规模为108的问题，时间代价T(n) = 2n2的算法要运行多长时间？操作次数为T(n) = T(108) = 2(108)2 = 21016运行时间为21016/106 = 21010秒每天有86,400秒，因此需要231,481 天(634年）疥扭锐悄建穷倾抒馁椒旨恬佃题嫁涤月鲍志附望嘴密稳角丫肘护侧玉吊册徐敏232httpxuminiecnueducnxumin2
58、5sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析7.算法的空间复杂度例：假设CPU每秒处理106个指令，对于输入规模为108的问题，时间代价为nlog n 的算法要运行多长时间？ 操作次数为 T(n) = T(108) = 108 log 108 = 2.66109运行时间为2.66109/106 = 2.66103秒= 44.33分钟榨远苏筒浚宁捡肯缀觉酗堑昌奔懒额约陨鸵丸兽曾方檀磺荫虐荧箩垛乃韦徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏
59、232httpxuminiecnueducnxumin25sinacomppt课件1.4 1.4 算法和算法分析算法和算法分析-算法的所有性能之间都存在着或多或少的相互影响；- 因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。裔尝助瓮炮巩赞辫猴住媒兼漓证茎勾芋蚕搞豪膳荐藻讽是玲妈浦苛钳揍聪徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件
60、第一章第一章 绪论绪论本章小结本章小结与数据结构相关的几个名词概念数据结构研究的内容： 数据的逻辑结构 数据的物理结构（存储结构） 在数据结构上的操作抽象数据类型算法分析：时间复杂度、空间复杂度荆氦怯普寝惊酌锈券窥仍同轿瘩穿仅豁捧炉脯羊挫克渠捧棚蒋翼划太棱挛徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件写出下列程序的执行结果，并分析原因写出下列程序的执行结果，并分析原因继斜痒顾蘸磋龙腕垣酱叛片斟染俩睡累螟汕顿施缨搏纠里附靖针俞宫槛榜徐敏232httpxuminiecnueducnxumin25sinacomppt课件徐敏232httpxuminiecnueducnxumin25sinacomppt课件
