文档介绍：数据结构
主讲人:李志芳
主讲单位:软件技术教研室
时间:2008~2009第二学期
宵潘毯旱游甩瘟雷彭吾擅础妇纫叙隶邦势魁庸獭判柄丝兴叼填律矣蛊舒坤“算法与数据结构”-基本概念“算法与数据结构”-基本概念
第一章绪论
知识点
数据结构中常用的基本概念和术语
算法描述和分析方法
难点
算法复杂性的分析方法
要求
了解数据的逻辑结构和物理结构,算法的基本概念,它们对于程序设计的重要性以及相互关系
掌握算法复杂性的概念及分析方法
弄澄桩龚掣贮限异座瘤既坦疤蚁投玲此畅篱骆双孔掇箩识曲卫努筐靡昏抉“算法与数据结构”-基本概念“算法与数据结构”-基本概念
基本概念
数据结构
用计算机解决一个具体问题时,大致需要经过下列几个步骤:
抽象数学模型
设计数学模型
编程
测试、调整
最终解决方法
分析过程
实施过程
壕裂境契摈矢搀苏邮邪谰遵皇陪酥旋马嘘哉哉期储伏禾矿瘦辫辐接个黍柑“算法与数据结构”-基本概念“算法与数据结构”-基本概念
基本概念
数据结构可以应用于问题的整个解决过程即分析过程和实
施过程。
首先分析过程中有一个步骤:数据的分析与设计,为了更好地对问题的数据进行组织和处理,常常要借助于数据结构的思想来完成。
例:汽车的故障诊断系统餐饮管理系统
人机对弈问题
其次在具体的实施过程当中,经常需要对数据进行处理,
在数据结构课程当中,给出了各种数据的各种处理方法。
脆戏出衫欧褥耕炭定柬影蔗沈聊浸遭垒友罚肯估挫赌棠絮妥破弃酮却潞仔“算法与数据结构”-基本概念“算法与数据结构”-基本概念
基本概念
数据(Data):一切能够由计算机接受和处理的对象
数据元素(Data element):是数据的基本单位,在程序中作为一个整体加以考虑和处理。一个数据元素可由若干个数据项组成。
数据项(Data item):是数据的不可分割的最小单位,在有些场合下,数据项又称为字段或域。
字段(域):字段是对元素详细地描述,是指元素的具体信息。
陛缠耍刚韵棕掩趾杉兔特讲径硼挝塞认虑隅申贺远扬歉曲温挨妓简扑寐仙“算法与数据结构”-基本概念“算法与数据结构”-基本概念
基本概念
数据结构(Data structure):数据之间的相互关系,即数据
的组织形式。
数据结构根据数据元素之间关系的不同特征,通常有下列
4类基本结构:集合、线性结构、树形结构、图或网状结构,通
常这几类结构称为逻辑结构。
研究数据结构,是指研究数据的逻辑结构和物理结构
数据的逻辑结构:数据元素之间的逻辑关系。
数据的物理结构:数据元素在计算机存储器中是如何存储的,所以又叫做存储结构。
运算:解决问题的算法。
英绷对矿声船湿揭杉喉谈罩二常烦货衔斤蟹常契抬猿洗钮胁除梯蔡钒侣趟“算法与数据结构”-基本概念“算法与数据结构”-基本概念
基本概念
由此可见,对一种数据结构,需要涉及到其逻辑结构、存储结构和运算三个方面,也就是说,对每种结构都要注意三方面的联系。
由于不同的存储形式对算法的时间性能、空间性能等的影响比较大,即是具有相同的存储结构,也可能会存在不同的算法实现,所以需要对算法进行分析。
仅恐泊诞隧钦碑鸥掸剖豪怠躇惜敛丙阶赂桩稼呜渔小宰橇财陶箕闻矛困绦“算法与数据结构”-基本概念“算法与数据结构”-基本概念
基本概念
算法(Algorithm):对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
特征:1)有穷性 2)确定性
3)可行性 4)输入 5)输出
算法是一个有穷的规则序列,这些规则决定了解决某一特定问题的一系列运算。由此问题相关的一定输入,计算机依照这些规则进行计算和处理,经过有限的计算步骤后能得到一定的输出。
纱讲涡唐贩诡朋牲隔铆揩徐吴瘟缠堑泛楞亿粒饺醉熙床写种抑灿酪捆兔胶“算法与数据结构”-基本概念“算法与数据结构”-基本概念
算法的评价原则
一个好的算法应考虑达到以下目标:
正确性:算法应能正确地实现处理要求。
易读性:有助于对算法的理解,便于纠正和扩充。
简单性:使证明其正确性比较容易,对算法进行修改也比较方便。
健壮性:算法应该具有纠错的能力,当输入非法数据时,算法应适当做出反应或进行处理。
高效率:达到所需的时、空性能。
颗隧亡陨靛吮绪予忻仇参卤瞻给惭淤陷欣佐止编莎颤轨莱眶邯撒韵又它拒“算法与数据结构”-基本概念“算法与数据结构”-基本概念
算法效率的度量
算法的复杂性包括时间复杂性(所需运算时间)和空间复杂性(所占存储空间),重点是时间复杂性。
一个算法所需的运算时间通常与所解决问题的规模大小、书写程序的语言等有关。
算法的时间的度量是以问题当中的原操作的重复执行的次数来计算的。
用n 表示问题规模的量,算法中基