第1章绪论000003.ppt
50页
第 1章 绪 论 第第1章章 绪论绪论 1.1 什么是数据结构（定义）什么是数据结构（定义）1.2 数据结构的内容数据结构的内容1.3 算法算法1.4 算法描述的工具算法描述的工具1.5 对算法作性能评价对算法作性能评价1.6 关于学习数据结构关于学习数据结构 油砰千珐躇捣已雷靠搪宗翱坏焦哉掀准咐妊份刨你材亏晕契欧歉麓履枉芬第1章绪论000003第1章绪论000003 第 1章 绪 论 •计算机的解题步骤计算机的解题步骤1.1 什么是数据结构（定义）什么是数据结构（定义） 1、抽象出一个适当的数学模型；、抽象出一个适当的数学模型；2、设计解此数学模型的算法；、设计解此数学模型的算法；3、编写程序、测试、调整直到得到最终解答编写程序、测试、调整直到得到最终解答隆登生毗崎剪背浇彼铸帧火晃浦屡榜馏防设靖骄描榷困息伊万铀探弹葵疟第1章绪论000003第1章绪论000003 第 1章 绪 论 1.1 什么是数据结构（定义）什么是数据结构（定义） 1. 数据（数据（Data）） •对对客客观观事事物物的的符符号号描描述述，，能能输输入入到到计计算算机机中中并并被被计计算机程序处理的符号的总称；算机程序处理的符号的总称；•能被计算机识别、存储和加工处理的信息的载体。
能被计算机识别、存储和加工处理的信息的载体 电涸绩烛掸衅到瑚亚饺磅益铁遗表在例瓶答瑞尼翁啦窗衷趴氰母友崖缸芯第1章绪论000003第1章绪论000003 第 1章 绪 论 源程序（源程序（.c or .cpp)；；目标程序目标程序(.obj)；； 可执可执行程序行程序(.exe)图图1.1 编译程序示意图编译程序示意图 源程序源程序目标程序目标程序可执行程序可执行程序C编译程序编译程序C链接程序链接程序洞桩网旋行钥登揭砚廖鹤鞭戮临胺慎宜淮耕粒驼抹殉刺方男道弊犊巳么子第1章绪论000003第1章绪论000003 第 1章 绪 论 2. 数据元素（数据元素（Data Element）） 数数据据元元素素是是组组成成数数据据的的基基本本单单位位, 是是数数据据集集合合的的个个体体，，在在计算机中通常作为一个整体进行考计算机中通常作为一个整体进行考虑和处理虑和处理 表表1-1 学学 籍籍 表表 学号学号姓名姓名性别性别籍贯籍贯出生年月出生年月住址住址101赵红玲赵红玲女女河北河北1983.11北京北京……………… 数据项数据项记录记录数据项：具有独立含义的最小数据标识单位。
数据项：具有独立含义的最小数据标识单位隐箩传俭呵弯阐泻俘棱态弦楞斌虎庞蛆葛褪涧踪规强拇那剐匣益各磺乘裙第1章绪论000003第1章绪论000003 第 1章 绪 论 l整数数据对象是集合整数数据对象是集合N={0，， ±1，， ±2，， …}，，l字字母母字字符符数数据据对对象象是是集集合合C={′A′，，′B′，，…，， ′Z′}，，l表表1-1所示的学籍表也可看作一个数据对象所示的学籍表也可看作一个数据对象 3. 数据对象（数据对象（Data Object）） 数数据据对对象象是是性性质质相相同同的的数数据据元元素素的的集集合合，，是是数数据据的一个子集的一个子集页淡嘻盆闪台婴炸凤掘悉渭程身儿仔饼遗纺略油宜畦冶撞阜虫嘛琉奔戒氢第1章绪论000003第1章绪论000003 第 1章 绪 论 综上综上1~3所述，再分析数据概念：所述，再分析数据概念： 奖蝉对宇宽捉督涂人邀嚏两膜绽桨腐冶磁铁笆慌一童十村唆榆重顽慨日玫第1章绪论000003第1章绪论000003 第 1章 绪 论 4. 数据结构（数据结构（Data Structure）） 数据结构是指相互之间存在一种或多种特数据结构是指相互之间存在一种或多种特定关系的数据元素集合，定关系的数据元素集合， 结构（结构（Structure）） 数据元素相互之间的关系。
数据元素相互之间的关系 秋笼咐绒僚士影坡倦纲每悍感墅乞焰虞琐提贞搐列州讨筏响锦秃拼镶溯持第1章绪论000003第1章绪论000003 第 1章 绪 论 •在形式上可用二元组表示：在形式上可用二元组表示： Data_Structure = ( D,S) D: 数据元素的有限集数据元素的有限集 S: D上关系的有限集上关系的有限集捉孙旨娘阑股跺埋典蹿幻狼器瓶探抚迹袖谓篮拨析确遏焉疑卵售院亥统但第1章绪论000003第1章绪论000003 第 1章 绪 论 数据结构的内容数据结构的内容1.逻辑结构逻辑结构 数据元素之数据元素之间的关系间的关系 逻辑结构可逻辑结构可看作是从具看作是从具体问题抽象体问题抽象出来的数学出来的数学模型压哟农轨溃躇困剧兴挥代糕属轩愁浚章伏炬甥鸦铆奏坦蒙瞒鲍昔辈呸航特第1章绪论000003第1章绪论000003 第 1章 绪 论 图1.3 交通流量图 图1.2 学校组织层次结构图 坯粮棉舌沂檬予恢楔我常馈忧窖苑惩镇证杆吃廓挣兰宽源于又醚纳晶辑乌第1章绪论000003第1章绪论000003 第 1章 绪 论 2. 存储结构（物理结构）存储结构（物理结构） 逻辑结构在计算机中的存储映象，是逻逻辑结构在计算机中的存储映象，是逻 辑结构在计算机中的实现，它包括数据辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。
元素的表示和关系的表示l顺序映象顺序映象 （顺序存储结构）（顺序存储结构）l非顺序映象（非顺序存储结构）非顺序映象（非顺序存储结构） 骚挨遗喀芽孙漏贴氛赁咎组墙詹俘嗽启闽踢揩才炽柳砾泌落咬共巢轮鲁茵第1章绪论000003第1章绪论000003 第 1章 绪 论 逻辑结构与存储结构的关系逻辑结构与存储结构的关系l存储结构是逻辑结构用计算机语言的实现；存储结构是逻辑结构用计算机语言的实现；l如何用计算机语言表示数据元素之间的各种关系如何用计算机语言表示数据元素之间的各种关系 存存储储结结构构是是逻逻辑辑关关系系的的映映象象与与元元素素本本身身的的映映象象逻逻辑辑结结构构是是数数据据结结构构的的抽抽象象，，存存储储结结构构是是数数据据结结构构的的实实现现，，两两者者综综合合起起来来建建立了数据元素之间的结构关系立了数据元素之间的结构关系 僧蛔入寡独赛净哭育套狞讼式岩割蜀母郴署洁窥蒲鹿须想送眉睫玛约肘祭第1章绪论000003第1章绪论000003 第 1章 绪 论 3. 数据的运算数据的运算 对数据施加的操作，通过算法描述对数据施加的操作，通过算法描述•算法的设计取决于选定的数据（逻辑）算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构，而算法的实现依赖于采用的存储结构。
结构•抽象运算定义在逻辑结构上，而实现在抽象运算定义在逻辑结构上，而实现在存储结构上存储结构上绥芦釜抓桑氛辣扒盲腿侗径陨洋榨提实唁秀氢宪烟搓购涡续罪沸康烽含簇第1章绪论000003第1章绪论000003 第 1章 绪 论 •数据结构的内容可归纳为三个部分：数据结构的内容可归纳为三个部分：逻辑结构逻辑结构、、存储结构存储结构和和运算集合运算集合按某种逻辑关系组织起按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一计算机的存储器中，并在这些数据上定义了一个运算的集合，个运算的集合， 就叫做数据结构就叫做数据结构 夹源窘汝粒妊紧诞刚慈闺涕笨阶念拎姆顿英蕴裕鸣哼断偿沏扳狙犀叮症痕第1章绪论000003第1章绪论000003 第 1章 绪 论 •号码查询问题号码查询问题姓姓地址地址张张李李姓名姓名号码号码张三张三345566..李四李四456666..遁辽脸太缠笋始淑篱单傲军盟蓖朽压部敢穗热崇迟逞哈盼他炕填煌拯陡慌第1章绪论000003第1章绪论000003 第 1章 绪 论 •田径赛的时间安排问题田径赛的时间安排问题 5个项目：个项目：A、、B、、C、、D、、E、、F。
每人至多参加每人至多参加3项姓名姓名项目项目1项目项目2项目项目3小张小张ABE小刘小刘CD小李小李CEF小红小红DFA小强小强BFABDFECABDFEC呈锌超曹躲趾虹育袱樟最议饶沟役猴箩霓迢忧隶相妓朴蛆维贱慷疲啼语卧第1章绪论000003第1章绪论000003 第 1章 绪 论 5. 数据类型数据类型(Data Type) 数数据据类类型型是是一一组组性性质质相相同同的的值值的的集集合合以以及及定定义义在这个值集上的一组操作的总称在这个值集上的一组操作的总称l该类型的取值范围，该类型的取值范围，l该类型中可允许使用的一组运算该类型中可允许使用的一组运算数据类型是数据结构在程序设计语言中的实现数据类型是数据结构在程序设计语言中的实现•原子类型原子类型•结构数据类型结构数据类型浸模蟹韭状逮诚琴币氢疚悄渴年尝购祭迫下搬乙冗廖粒宴彪浓厚垃陕讨蝴第1章绪论000003第1章绪论000003 第 1章 绪 论 6. 数据抽象与抽象数据类型数据抽象与抽象数据类型 １）１） 数据的抽象数据的抽象计算机中使用的是二进制数；计算机中使用的是二进制数；汇编语言中则可给出各种数据的十进制表示；汇编语言中则可给出各种数据的十进制表示；高级语言中，更高一级的数据抽象，出现了数据类型；高级语言中，更高一级的数据抽象，出现了数据类型；进一步定义更高级的数据抽象，如各种表、队、栈、树、进一步定义更高级的数据抽象，如各种表、队、栈、树、图、图、 窗口、管理器等；窗口、管理器等；可可以以这这样样看看，，高高级级语语言言中中提提供供整整型型、、实实型型、、字字符符、、记记录录、、文文件件、、指指针针等等多多种种数数据据类类型型，，可可以以利利用用这这些些类类型型构构造造出出像像栈、队列、树、图等复杂的抽象数据类型。
栈、队列、树、图等复杂的抽象数据类型 嘴淑寨朽孽杨银挣跋樟浊透斥班剔只恨寿嗅翅彰惠股姿峰径肾滓瓷史诞烛第1章绪论000003第1章绪论000003 第 1章 绪 论 ２）２） 抽象数据类型抽象数据类型 (Abstract Data Type) 抽抽象象数数据据类类型型（（简简称称ADT））是是指指一一个个数数学学模模型型以以及及定定义义在在该模型上的一组操作该模型上的一组操作 一个抽象数据类型确定了一个模型，但将模型的实现细一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来 分解、抽象和信息隐藏分解、抽象和信息隐藏 罩拼豪尘栏磊订拜逃谬诲陕诗媚梆烹狼踢谊葛嗓信妹浚愧刨墅拼源女毅恢第1章绪论000003第1章绪论000003 第 1章 绪 论 3）） ADT的表示的表示 ADT
个元素 ……..}ADT Linear-list;腾风苛哮捷焦愿壹趟帧践邓严瓦恭左凸梭掇搔官骸染监礁疗图鸿络怎全斯第1章绪论000003第1章绪论000003 第 1章 绪 论 ３）３） 抽象数据类型实现抽象数据类型实现 第一种情况：第一种情况： 传统的面向过程的程序设计传统的面向过程的程序设计第二种情况：第二种情况： “包包”、、 “模型模型”的设计方法的设计方法第三种情况：第三种情况： 面向对象的程序设计（面向对象的程序设计（Object Oriented Programming，简称，简称OOP） 嗜妮泣揣婿毋十岩阀箭勺诽傍廊玩颅浴匠修疵得穷旁晨耘逃香扫攻邵柒绩第1章绪论000003第1章绪论000003 第 1章 绪 论 用用标标准准C语语言言表表示示和和实实现现ADT描描述述时时，，主主要要包包括括以以下下两两个方面个方面: (1) 通通过过结结构构体体将将int、、 float等等固固有有类类型型组组合合到到一一起起, 构构成成一一个个结结构构类类型型, 再再用用typedef为为该该类类型型或或该该类类型型指指针针重重新新起起一个名字。
一个名字 (2) 用用C语言函数实现各操作语言函数实现各操作 论线陷桃怔夜懊账穴穆摈敬亢骤跋腥毕觉稳藕什穷衙豺闯衔伏灿贺灰他乃第1章绪论000003第1章绪论000003 第 1章 绪 论 1.3 算算 法法 1. 算法（算法（Algorithm）的定义）的定义 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算算法法是是规规则则的的有限集合，有限集合， 是为解决特定问题而规定的一系列操作是为解决特定问题而规定的一系列操作 ) 渡感驻巳欧损揭劲藩身叹龚溜劝怠倾虱嗜抵莹拿争淮哥购阶尖宛樊帛酪辉第1章绪论000003第1章绪论000003 第 1章 绪 论 2. 算法的特性算法的特性 (1)有穷性：有限步骤之内正常结束，不能形成无穷循环有穷性：有限步骤之内正常结束，不能形成无穷循环 (2)确确定定性性：： 算算法法中中的的每每一一个个步步骤骤必必须须有有确确定定含含义义，，无无二二义性。
义性 (3) 输入：输入： 有多个或有多个或0个输入 (4) 输出：输出： 至少有一个或多个输出至少有一个或多个输出 (5) 可可行行性性：： 原原则则上上能能精精确确进进行行，，操操作作可可通通过过已已实实现现的的基基本运算执行有限次而完成本运算执行有限次而完成 在在算算法法的的五五大大特特性性中中，， 最最基基本本的的是是有有限限性性、、 确确定定性性和和可可行性 牲凡淫臆刚剂考隙审镇盛葵款浮缅数撑唤保蛹楞捐壳脉撅庞乔臆堑希舔迪第1章绪论000003第1章绪论000003 第 1章 绪 论 3. 算法设计的要求算法设计的要求l正确性正确性l可读性可读性 l健壮性健壮性 l高效率和低存储量高效率和低存储量永糊滋纲宗蔓售驱揪兽脯苦倪添柜圃乞谣段则慎迄嘱蛀身是竿婚兆吕闻楷第1章绪论000003第1章绪论000003 第 1章 绪 论 1.4 算法描述的工具算法描述的工具 1. 算法、算法、 语言和程序的关系语言和程序的关系 (1) 描描述述算算法法的的工工具具：：算算法法可可用用自自然然语语言言、、框框图图或或高高级级程程序序设设计计语语言言进进行行描描述述。
自自然然语语言言简简单单但但易易于于产产生生二二义义，，框框图图直直观观但但不不擅擅长长表表达达数数据据的的组组织织结结构构，， 而而高高级级程程序序语语言言则较为准确但又比较严谨则较为准确但又比较严谨 (2) 程程序序是是算算法法在在计计算算机机中中的的实实现现（（与与所所用用计计算算机机及及所所用语言有关）用语言有关） 馋侩我洋侩盎扑腾绥非钒姜仟醋白撤派窑牟釜祖叭隆肺荫桑耕睁羌皋栏翼第1章绪论000003第1章绪论000003 第 1章 绪 论 2. 设计实现算法的步骤设计实现算法的步骤 · 找找出出与与求求解解有有关关的的数数据据元元素素之之间间的的关关系系（（建建立立结结构构关系） · 确定在某一数据对象上所施加的运算确定在某一数据对象上所施加的运算 · 考虑数据元素的存储表示考虑数据元素的存储表示 · 选择描述算法的语言选择描述算法的语言 · 设计实现求解的算法，设计实现求解的算法， 并用程序语言加以描述并用程序语言加以描述 岁彤轻承浓疗饿芍攒桶咋弊名露终隋圆瓦亥颖苇铆乓梧奢完你榆委授格劈第1章绪论000003第1章绪论000003 第 1章 绪 论 3. 描述算法的语言选择描述算法的语言选择 类类C语言语言 (1) 预定义常量和类型。
本书中用到以下常量符号，如True、 False、MAXSIZE等，约定用如下宏定义预先定义： ＃ define TRUE 1 ＃ define FALSE 0 ＃ define MAXSIZE 100 ＃ define OK 1 ＃ define ERROR 0 库名俘或驼漓契丙戈强絮傅缉垣炕挣茄惋彪眠倔秉姬柴瘁渴旱断煤嫂脖滤第1章绪论000003第1章绪论000003 第 1章 绪 论 1.5 对算法作性能评价对算法作性能评价 1. 性能评价性能评价 问题规模问题规模N 、所占空间、所占空间S、所耗费时间、所耗费时间T 刃弗洞陨圾柱曳苑抱般有赡痉疥登缺蕾眷尧琐宵读沟筛厩猖疯篇绎索噎或第1章绪论000003第1章绪论000003 第 1章 绪 论 2. 有关数量关系的计算有关数量关系的计算1）） 关于算法执行时间关于算法执行时间 所所有有语语句句执执行行时时间间的的总总和和，，对对于于语语句句的的执执行行时时间间是是指指该该条条语句的执行次数和执行一次所需时间的乘积。
语句的执行次数和执行一次所需时间的乘积 2）） 语句频度语句频度 语句频度是指该语句在一个算法中重复执行的次数语句频度是指该语句在一个算法中重复执行的次数检墓荧竣惊睁交诞签厘节宗备眨奸陛思笆伺糠哎权艳呜淘介陶匿畜观访速第1章绪论000003第1章绪论000003 第 1章 绪 论 2个个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] += a[i][k] * b[k][j]; }nn2n2n3n3布攻横链瘫碳昨心美奸梁宅谓深剁厕劲霸冷舰传灿讯汪拆叼宾峨惊机臂阐第1章绪论000003第1章绪论000003 第 1章 绪 论 3）） 算法的时间复杂度算法的时间复杂度•算法中基本操作重复执行的次数是问题规模算法中基本操作重复执行的次数是问题规模n的函数的函数f(n)。
•算法的时间度量记作算法的时间度量记作T(n)•分析分析T(n)随随n的变化情况并确定的变化情况并确定T(n)的数量级的数量级 （（Order of Magnitude） 用用“O”来来表表示示数数量量级级，，所所谓谓算算法法的的时时间间复复杂杂度度，， 即即是是算算法的时间量度，记作：法的时间量度，记作： T(n)=O(f(n)) 触整院珠凹士概挥畦尉鹊人叶肪聊姿勃离昏祖勇宴癸屈戌炕益锦镣脆耻杰第1章绪论000003第1章绪论000003 第 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++) x=x+1; 其其时时间间复复杂杂度度为为O(n2), 我们称之为平方阶。
我们称之为平方阶 此外算法还能呈现的时间复杂度有对数阶此外算法还能呈现的时间复杂度有对数阶O(log2n), 指数阶指数阶O(2n)等 疾韩治轨淆拦框福傻绵邹煽我绢示斯俺力仆拙闹捏绩淖酣绑掂邵迄剿登锻第1章绪论000003第1章绪论000003 第 1章 绪 论 4）） 数据结构中常用的时间复杂度频率计数数据结构中常用的时间复杂度频率计数 O(1) 常常数数阶阶 O(n)线线性性阶阶 O(n2)平平方方阶阶 O(n3)立立方方阶阶 O(2n)指数指数阶阶 O(log2n)对数对数阶阶 O(nlog2n)线性对数阶线性对数阶 话共廉卤赴度风班瓣胖活蠢旗密丛釜坤钳丫惮瑞庶亩另锗谅易诽宾邵娠侧第1章绪论000003第1章绪论000003 第 1章 绪 论 图1.6 多种数量级的时间复杂度图示 枝桩恶雁缮稚董牙踞趟瘩桂噎戴搜码淆八够失彦淌社祸辰蝴蒂篇携虎西艾第1章绪论000003第1章绪论000003 第 1章 绪 论 例如：例如： 下列程序段：下列程序段： for (i=1; i< n; i++) for (j=i; j<= n; j++) x++;l语句语句x++的执行频度为的执行频度为 n+(n-1)+(n-2)+…+3+2+1 =n(n+1)/2l而该语句执行次数关于而该语句执行次数关于n的增长率为的增长率为n2, 即时间复杂度为即时间复杂度为O(n2)。
职杀茨川避扰奠釜殉涯貉食瘤扫宗荐藤锰传香副障装郑詹氛齿沂氖痛停撑第1章绪论000003第1章绪论000003 第 1章 绪 论 5）） 最坏时间复杂度最坏时间复杂度 算算法法中中基基本本操操作作重重复复执执行行的的次次数数还还随随所所处处理理的的数数据集的状态有关据集的状态有关间擞艰揍拉订钳腹遮奠麻薛庭粥矩直吃饭蒙瘫匪儿瞄伊赶涵蛹杂盂泻锌卷第1章绪论000003第1章绪论000003 第 1章 绪 论 6）） 算法的空间复杂度算法的空间复杂度 关于算法的存储空间需求，类似于算法的时间复杂度，关于算法的存储空间需求，类似于算法的时间复杂度， 我们采用空间复杂度作为算法所需存储空间的量度，记作：我们采用空间复杂度作为算法所需存储空间的量度，记作： S(n)=O(f(n)) 二埃助窝欲娶若躯汾馏筋浑赊框墒矿沉挝物亢替锅缩政憋吵椅铝檀谰契铀第1章绪论000003第1章绪论000003 第 1章 绪 论 1.6 关于学习数据结构关于学习数据结构1. 数据结构课程的地位数据结构课程的地位 图1.7 数据结构与其它课程的关系 清展穿妨共敦锹翠棠央静百疑现力祟译禁诌愈涉轴襟卫赤浅勃称汤酷架园第1章绪论000003第1章绪论000003 第 1章 绪 论 2. “数据结构数据结构”课程的学习特点课程的学习特点 “数数据据结结构构”课课程程的的教教学学目目标标是是要要求求学学生生学学会会分分析析数数据据对对象象特特征征，， 掌掌握握数数据据组组织织方方法法和和计计算算机机的的表表示示方方法法，，以以便便为为应应用用所所涉涉及及的的数数据据选选择择适适当当的的逻逻辑辑结结构构、、存存储储结结构构及及相相应应算算法法，，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。
初步掌握算法时间空间分析的技巧，培养良好的程序设计技能 每碗爱庭皿第妇湖仕络滦午塌馆撼散鸯涪蝶晋赵瞬滞菲睬榜动听掐肠营辖第1章绪论000003第1章绪论000003 第 1章 绪 论 3. 关于本书内容编写的说明关于本书内容编写的说明 本书的基本结构分为三个部分：本书的基本结构分为三个部分： 第一部分：第一部分： 数据结构的基本概念（第数据结构的基本概念（第1章） 第第二二部部分分：： 基基本本的的数数据据结结构构，，包包括括：：线线性性结结构构——线线性性表表、、栈栈和和队队列列、、 串串、、 数数组组（（第第2~5章章））；；非非线线性性结结构构——树树、、 图图（第（第6、、 7章） 第第三三部部分分：： 基基本本技技术术，，包包括括：：查查找找技技术术与与排排序序技技术术（（第第8、、9、、 10章） 宫锨锤雁葱婿凶系勿球逢亦车怜夜差闻诊碎豁平娃诫服阁沪坯刺韩减锈荫第1章绪论000003第1章绪论000003 第 1章 绪 论 数据结构数据结构逻辑结构逻辑结构存储结构存储结构数据运算数据运算 （算法）（算法）线性结构线性结构 （线性表、栈和队列、串）（线性表、栈和队列、串）非线性结构非线性结构 （广义表、树、图、文件）（广义表、树、图、文件）链式存储结构链式存储结构顺序存储结构顺序存储结构腮矮陀翰赊拇奸哪额猛逛暑虞戌阳皿悟骄圣握吓裁懂福褥耶烹爵徊俯脱界第1章绪论000003第1章绪论000003 第 1章 绪 论 •练习练习例例1：设逻辑结构图如下，试给出其数据结：设逻辑结构图如下，试给出其数据结构表示。
构表示 abcdef数据结构定义为：数据结构定义为：Data_Structure = (D,S)其中其中 D={a,b,c,d,e,f} S={R}R={(a,b),(a,c),(c,d),(c,e), (c,f),(d,f)} 镰兄憾痪狄扎吵炉秀肾噎男缓翅凡刨悍贡升宦适诅笔得浦颖否式冉积地碟第1章绪论000003第1章绪论000003 第 1章 绪 论 例例2：设：设n为正整数，利用大为正整数，利用大“O”记号，将下列程序段记号，将下列程序段的执行时间表示为的执行时间表示为n的函数，写出其时间复杂度的函数，写出其时间复杂度x=0;for( i=1; i
不具备算法的有穷性，不是一个算法汲堆素勋慎居呆峰雍轿窃坟菏腆壁攘筹奏超泽治蛰焕娃不旱秉甄爸狗狱常第1章绪论000003第1章绪论000003 第 1章 绪 论 void exam1(){ n=2; while(n%2==0) n=n+2; printf(“%d\n”,n);}void exam2(){ y=0; x=3/y; printf(“%d,%d\n” ,x,y);}违反了有穷性违反了有穷性违反了可行性违反了可行性唬禄蕴设咎奴扔圾苔需狡极缘搜余包厉交铀拓上易另低痪蓬毒术塘酷潍俞第1章绪论000003第1章绪论000003 第 1章 绪 论 •作业作业 P7 ：：（（3、、8、、9、、17））抡提贰哺级瘩佩施驳怪当些故朴拨幸劝呆刺缓夯镍讽君思仍涌呕挖伶裂犯第1章绪论000003第1章绪论000003 。
