数据结构期末复习总结课件.ppt

《数据结构期末复习总结课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章小结掌握数据、数据元素、数据对象、数据结构的定义，四类基本结构。数据（data)—是对信息的一种符号表示。在计算机科学中所有能输入到计算机中去的描述客观事物的符号。如整数，实数，文字，声音，图象等。数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）。一个数据元素可由若干个数据项组成。在计算机程序中通常作为一个整体进行考虑和处理。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构（datastructure)—是相互之间存在一种或多种特定关系的数

2、据元素的集合。数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。根据数据元素间关系的基本特性，有四种基本数据结构集合——数据元素间除“同属于一个集合”外，无其它关系.线性结构——结构中的数据元素之间存在一对一的关系。(一个对一个，如线性表、栈、队列)树形结构——结构中的数据元素之间存在一对多的关系。(一个对多个，如树)图状结构或网状结构——结构中的数据元素之间存在多对多的关系。多个对多个，如图数据结构的逻辑表示与物理存储->逻辑结构与存储结构“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。数

3、据结构在计算机中的表示称为物理结构。又称存储结构。有顺序存储结构和链式存储结构抽象数据类型定义；抽象数据类型：一个数学模型以及定义在该模型上的一组操作。掌握算法的定义及特性，算法设计的要求算法：是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性。算法的五个特性：有穷性一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；确定性算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任

4、何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。输出一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。算法设计的要求1、正确性2、可读性3、健壮性4、效率与低存储量需求效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。掌握算法的渐近时间

5、复杂度和空间复杂度的意义与作用及计算方法语句的频度指的是该语句重复执行的次数。学会计算语句重复执行的次数。重点掌握算法的5个特性，算法好坏衡量标准，给出一个算法，分析时间复杂度，语句频度第二章小结线性表(LinearList)：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)其中ai是属于某一个数据对象的数据元素。线性表的逻辑特征是：线性表中所有元素的性质是相同的，即具有相同数据类型。在非空的线性表，有

6、且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表的运算：基本运算：1.存取：存取或更新表中某个数据元素。2.插入：在表的两个确定的元素之间插入一个新元素。3.删除：删除表中某个数据元素。4.查找：查找表中满足某种条件的数据元素。如找出某个数据项具有给定值的数据元素。复杂运算：5.合并：把两个线性表合并成一个线性表。6.分解：把一个线性表拆分成多个线性表

7、。7.排序：按一个或多个数据项值的递增或递减次序重新排列表中数据元素。最基本的运算有：查找、插入和删除。顺序表—把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里.这组连续的存储单元称为向量。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。线性表中第i+1个数据元素的存储位置LOC(ai+1)：LOC(ai+1)=LOC(a1)+L*i线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L通常称LOC(a1)为线性表的开始地址。顺序存储结构的特点

8、：表中逻辑上相邻的数据元素存储在相邻的存储位置。即以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。要访问第i个数据元素，就可以直接计算出ai的存储位置LOC(ai)因此，是一种随机存取的存储结构。适合很少进行插入和删除，但要求以