自考02331数据结构重点总结

自考 02331 数据结构重点总结(最终修订)第一章 概论1、瑞士计算机科学家沃思提出：算法+数据结构=程序。算法就是对数据运算得描述，而数据结构包括逻辑结构与存储结构。由此可见，程序设计得实质就是针对实际问题选择一种好得数据结构与设计一个好得算法，而好得算法在很大程度上取决于描述实际问题得数据结构。WxxVGK7。2、数据就是信息得载体。数据元素就是数据得基本单位。一个数据元素可以由若干个数据项组成，数据项就是具有独立含义得最小标识单位。数据对象就是具有相同性质得数据元素得集合。QQqWgAF。3、数据结构指得就是数据元素之间得相互关系，即数据得组织形式。数据结构一般包括以下三方面内容：数据得逻辑结构、数据得存储结构、数据得运算① 数据得逻辑结构就是从逻辑关系上描述数据，与数据元素得存储结构无关，就是独立于计算机得。数据得逻辑结构分类: 线性结构与非线性结构。线性表就是一个典型得线性结构。栈、队列、串等都就是线性结构。数组、广义表、树与图等数据结构都就是非线性结构。RGCak6Y。② 数据元素及其关系在计算机内得存储方式，称为数据得存储结构（物理结构）。数据得存储结构就是逻辑结构用计算机语言得实现，它依赖于计算机语言。③ 数据得运算。最常用得检索、插入、删除、更新、排序等。4、数据得四种基本存储方法: 顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言得数组描述。（2）链接存储：通常借助于程序语言得指针来描述。（3）索引存储：索引表由若干索引项组成。关键字就是能唯一标识一个元素得一个或多个数据项得组合。（4）散列存储：该方法得基本思想就是：根据元素得关键字直接计算出该元素得存储地址。5、算法必须满足 5 个准则：输入，0 个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令得含义都明确；可行性，算法就是可行得。GlVU3P1。算法与程序得区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定得符号语言来描述。目前常用得描述算法语言有两类：类 Pascal 与类 C。GuYWUCS。6、评价算法得优劣：算法得"正确性"就是首先要考虑得。此外，主要考虑如下三点：① 执行算法所耗费得时间，即时间复杂性；② 执行算法所耗费得存储空间，主要就是辅助空间，即空间复杂性；③ 算法应易于理解、易于编程，易于调试等，即可读性与可操作性。cS01B7...