自考~数据结构笔记体会(超级详细可做专业考试条).doc
《自考~数据结构笔记体会(超级详细可做专业考试条).doc》由会员分享,可在线阅读,更多相关《自考~数据结构笔记体会(超级详细可做专业考试条).doc(87页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、.自考数据结构笔记(详尽版)感谢热心自考人:liuii322 笔记特点笔记特点:图例丰富,超级详细,几乎涵盖本课程所有要求掌握的知识点,。用于复习和做小条概论- 学习数据结构的意义.5 概论- 算法的描述和分析(一).5 线性表 - 链式存储结构- 单链表的运算(一).14 三 栈和队列 - 栈 - 栈的定义及基本运算.22 三栈和队列 - 队列 - 队列的定义及基本运算.25 三栈和队列 - 队列 - 顺序队列.25 栈和队列 - 队列 - 链队列.26 三栈和队列 - 栈和队列的应用实例 - 栈的应用实例(一).27 四串的基本概念(一).30 图 - 图的概念(一).63 图 - 图的存
2、储结构 - 邻接矩阵表示法.67 图 - 图的遍历 - 深度优先遍历(一).72 图 - 图的遍历 - 广度优先遍历 (一).75 图 - 生成树和最小生成树 - 生成树.77 图 - 生成树和最小生成树 - 最小生成树(一).79 图 - 最短路径 (一).82 图 - 拓扑排序 (一).84 排序 - 排序基本概念 (一).86 排序 - 插入排序 - 直接插入排序(一).87 排序 - 插入排序 - 直接插入排序(二).88 排序 - 插入排序 - 希尔排序.89 排序 - 交换排序 - 冒泡排序(一).90 排序 - 交换排序 - 快速排序 (一).92 排序 - 选择排序 - 堆排序
3、(一).96 排序 - 归并排序(一).98 排序 - 分配排序 - 基数排序.101 排序 - 各种内部排序方法的比较和选择(一).102 查找 - 查找的基本概念.103 查找-线性表的查找-顺序查找.104 查找 - 线性表的查找 - 二分查找(一).105 查找 - 线性表的查找 - 分块查找.107 查找 - 树上的查找 - 二叉排序树(一).109 查找 - 树上的查找 - 树.114 查找 - 散列技术 - 散列表的概念.121 查找 - 散列技术 - 散列函数的构造方法.122 文件 - 文件的基本概念(一).123 文件 - 顺序文件.125 文件 - 索引文件(一).126
4、 文件 - 索引顺序文件 - ISAM 文件(一).127 文件 - 索引顺序文件 - VSAM 文件 (一).130 文件 - 散列文件.131 文件 - 多关键字文件 - 多重表文件.132.文件 - 多关键字文件 - 倒排文件.133概论概论-基本概念和术语基本概念和术语数据数据:数据:指能够被计算机识别、存储和加工处理的信息载体。数据元素数据元素:就是数据的基本单位,在某些情况下,数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构数据结构:指的是数据之间的相互关系,即数据的组织形式。1数据结构一般包括以下三方面内容:数据结构一般包括以下三方面内容: 数据元
5、素之间的逻辑关系,也称数据的逻辑结构数据的逻辑结构;数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据元素及其关系在计算机存储器内的表示称数据的存储结构数据的存储结构; 数据的运算数据的运算,即对数据施加的操作。数据的运算定义在数据的逻辑结构上,每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。(1)逻辑结构逻辑结构:表中每一行是一个数据元素(或记录、结点),由学号、姓名等数据项组成。
6、数据元素之间的逻辑关系是:对表中任一个结点,与它相邻且在它前面的结点称直接前趋直接前趋最多只有一个; (2)存储结构存储结构:该表的存储结构是指用计算机语言如何表示结点之间的这种关系,即表中的结点是顺序邻接地存储在一片连续的单元之中,还是用指针将这些结点链接在一起?2数据的逻辑结构分类:数据的逻辑结构分类:逻辑结构简称为数据结构。 (1)线性结构线性结构:逻辑特征是:若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前 趋和一个直接后继。 线性表,栈栈,队列队列,串等都是线性结构。串等都是线性结构。(2)非线性结构非线性结构:逻辑特征是:一个结点可能有多个直接
7、前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 3数据的四种基本存储方法数据的四种基本存储方法(1)顺序存储方法:该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构 ,通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。(如数组)(2)链接存储方法:该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称链式存储结构,通常借助于程序语言的
8、指针类型描述。(3)索引存储方法:该方法通常在储存结点信息的同时,还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项,则该索引表称之为稠密索引稠密索引。若一组结点在索引表中只对应一个索引项,则该索引表称为稀疏索引稀疏索引。索引项的一般形式是:(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置;稀疏索引中索引项的地址指示一组结点的起始存储位置。(4)散列存储方法:根据结点关键字直接计算出该结点存储地址。 四种存储方法可单独使用也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法,可以得到不同的存储结构。
9、同一逻辑结构采用不同的存储方法,可以得到不同的存储结构。4数据结构三方面的关系:数据结构三方面的关系:数据的逻辑结构、存储结构及数据的运算这三方面是一个整体。存储结构是数据结构不可缺少的一个方面:同一逻辑结构的不同存储结构可冠不同数据结构名称来标识。 【例例】线性表是一种逻辑结构,用顺序方法的存储表示,称其为顺序表;用链式存储方法,称为链表;用散列存储方法,称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后,按定义的运算集合及其运算的性质不同,也可能导致完全不同的数据结构。数据类型数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可
10、以看作是程序设计语言中已实现的数据结构。按按“值值“是否可分解,可将数据类型划分为两类:是否可分解,可将数据类型划分为两类:原子类型:原子类型:其值不可分解。通常是由语言直接提供。结构类型:结构类型:其值可分解为若干个成分(或称为分量)。抽象数据类型(简称抽象数据类型(简称 ADT):是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型,它独立于具体实现。它的优点优点是将数据和操作封装在一起,使得用户程序只能通过在 ADT里定义的某些操作来访问其中的数据,从而实现信息隐藏。ADT 和类的概念实际上反映了程序或软件设计的两层
11、抽象:ADT 相当于是在概念层(或称为抽象层)上描述问题,而类相当于是在实现层上描述问题。不采用 ADT 的形式来描述数据结构 概论概论- - 学习数据结构的意义学习数据结构的意义 1 计算机处理问题的分类计算机处理问题的分类 (1)数值计算问题 (2)非数值性问题 .2非数值问题求解非数值问题求解 瑞士计算机科学家沃思教授曾提出: 算法+数据结构=程序 数据结构是数据的逻辑结构和存储结构,算法是对数据运算的描述 概论概论- - 算法的描述和分析算法的描述和分析( (一一) ) 数据的运算通过算法(Algorithm)描述 1算法算法 :非形式地说,算法是任意一个良定义的计算过程。它以一个或多
12、个值作为输入,并产生一个或多个值作为输出。(1)一个算法可以被认为是用来解决一个计算问题的工具。 (2)一个算法是一系列将输入转换为输出的计算步骤。 2算法的描述算法的描述 ;一个算法可以用自然语言、计算机程序语言或其它语言来说明,惟一的要求是该说明必须精确地描述计算过程。 描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。算法分析算法分析 算法分析的目的是(评价算法的效率)算法分析的目的是(评价算法的效率)1评价算法好坏的标准:评价算法好坏的标准:首先应是“正确“的。此外主要考虑三点: 执行算法所耗费的时间;执行算法所耗费的存储空间,主要考虑辅助存储空间;算法应易于理解,易于编码,易
13、于调试等。 算法的效率算法的效率分为时间效率和空间效率真3算法的时间性能分析算法的时间性能分析 (1)算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度)语句执行一次所需时间的乘积。【例】求两个 n 阶方阵的乘积 C=AB,其算法如下: # define n 100 / n 可根据需要定义,这里假定为 100 void MatrixMultiply(int Aa,int B nn,int Cnn) int i ,j ,k; (1) for(i=0; in;j+) n+1 (2) for (j=0;jn;j+) n(n+1) (3) Cij=0; n 2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自考 数据结构 笔记 体会 超级 详细 专业 考试
限制150内