算法和算法分析

《算法和算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构第一章绪论Introduction计算机学院霍红卫第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求HuoHongwei21.1什么是数据结构例1图书馆的书目检索系统自动化问题001高等数学樊映川S01…002理论力学罗远祥L01…003高等数学华罗庚S01…004线性代数滦如书S02…!!!!!高等数学001,003,…樊映川001,…L002,…理论力学002,…华罗庚003,…S001,003,…线性代数004,…滦如书004,…

2、!!!!!!图书目录文件示例HuoHongwei31.1什么是数据结构例2计算机和人对弈问题ô×ô×ô××ô(a)ô×ô×ôôô××××××××ô×ô×ô×ô×ô×(b)井字棋对弈树(a)井字棋对弈树(b)对弈树的局部HuoHongwei41.1什么是数据结构例3多叉路口交通灯的管理问题ABC1ACAD11DBABCBDB122EDADBDCA331EA2EB(a)4ECED41(b)五叉路口交通管理示意图(a)五叉路口(b)表示通路的图HuoHongwei51.2基本概念和术语•数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号

3、的总称。•数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。•一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。•数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。•数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。HuoHongwei61.2基本概念和术语•数据之间的相互关系称为逻辑结构。•数据的逻辑结构是独立于计

4、算机的，对数据元素之间的逻辑关系的描述。从集合的观点，它们可以形式地用一个二元组B=（D，R）表示，其中D是数据元素的集合，R是D上关系的集合。•按集合的观点，数据的逻辑结构有两个要素：一是数据元素；二是关系。HuoHongwei71.2基本概念和术语通常分为四类基本结构：–集合结构中的数据元素除了同属于一种类型外，别无其它关系。–线性结构结构中的数据元素之间存在一对一的关系。–树型结构结构中的数据元素之间存在一对多的关系。–图状结构或网状结构结构中的数据元素之间存在多对多的关系。HuoHongwei81.2基本概念和术语数据的逻辑结构按关系分为线性结构（关系是线性的）和非线性结构（

5、关系是非线性的）。数据的逻辑结构线性结构非线性结构文件结构线性表树型结构网状结构一般线性表特殊线性表线性表推广树二叉树有向图无向图线性表栈和队串数组广义表HuoHongwei91.2基本概念和术语•数据的物理结构–是指数据的逻辑结构在计算机中的映象，即存储表示。映象包括数据元素的映象和数据关系的映象。数据元素的映象是结点，即在计算机内用一结点表示一个数据元素（结点是数据结构讨论的基本单位）。关系的映象有两种，顺序映象和非顺序映象。HuoHongwei101.2基本概念和术语•数据结构主要指逻辑结构和物理结构•顺序存储结构与非顺序存储结构–顺序存储机构是逻辑上相邻的数据元素存锗在物理位

6、置上相毗邻的存储单元里，元素的关系由存储单元的邻接关系来体现。–非顺序存储结构是数据元素可以在计算机内任意位置上存放（它不要求逻辑上相邻的元素在物理位置上也相邻)，它们的逻辑关系用指针来链接。所以非顺序存储结构又叫链式存储结构。链式存储结构将数据元素存放的存储单元分为两个部分，分别存放数据和指针，称为数据域和指针域。HuoHongwei111.4算法和算法分析•算法：是对特定问题求解步骤的一种描述。算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：–有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。–确定性算法中每一条指令必须有确切的

7、含义。不存在二义性。且算法只有一个入口和一个出口。–可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。–输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。–输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。HuoHongwei121.4算法和算法分析•算法评价标准–正确性——合理的数据输入下，在有限的运行时间内得出正确的结果。–健壮性——对不合理的数据输入的反应和处理能力。–可读性——