《数据结构复习纲要.doc》由会员分享，可在线阅读，更多相关《数据结构复习纲要.doc（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构期末复习要点！ 数据结构复习要点第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。第3章：1.概念:栈、队列和循环队列;2.栈和队列的初始化、插入和删除算法；3.栈、队列和循环队列的空、满条件。第5章：数组、三元组和十字链表的定义第6章：1.各种定义；2.二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3.树和森林的存储、遍历以及与二叉树的相互转换；4.Huffman树的构造。第7章：1.图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2.最小生成树、关键路径和最短路的算法实现。第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。第10章：1
2、.基本排序算法(冒泡、简单选择、直接插入)的编程；2.其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3.各种排序的稳定性。第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。作业：2.2,2.3,2.6,2.7,2.8,2.15,2.19,2.20第3章：1.概念:栈、队列和循环队列;2.栈和队列的初始化、插入和删除算法；3.栈、队列和循环队列的空、满条件。作业：3.1,3.6,3.11,第5章：数组、三元组和十字链表的定义第6章：1.各种定义；2.二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3.树和森林的存储、遍历以及与二叉树的相互转换；4.
3、Huffman树的构造。作业：6.5,6.6,6.14,6.19,6,23,6.26,6.27,6.28,6.37,6.38,6,47第7章：1.图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2.最小生成树、关键路径和最短路的算法实现。作业：7.1,7.7,7.11,7.13第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。作业：9.9,9.11,9.14,第10章：1.基本排序算法(冒泡、简单选择、直接插入)的编程；2.其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3.各种排序的稳定性。作业：10.1,10.3第一章绪论第二节基本概念和术语1.3抽象数据类型的表示与实
4、现类C语言的简要说明例1-7抽象数据类型Triplet的表示与实现1.4算法和算法分析算法 算法(Algorithm)就是对特定问题求解步骤的一种合理的描述。它有如下特征：有穷性；确定性；可行性。当然需要输入初始条件-输入，和操作结果-输出。算法设计的要求 1.正确性；2.可读性；3.健壮性； 4.高效率性和低存储性1.4算法和算法分析算法效率的度量时间和空间的度量 衡量一个算法的效果（好坏），最广泛采用的标准主要是看这个算法解决问题所花费的时间长短，当然一般还要看所需要的存储空间。但是一个算法执行所花费的时间既与计算机的速度有关，也与要求解的实例有关。为了客观公正，必需要一个通用的标准。这个
5、标准就是找一个参变量-问题的规模(Size),即一个实例按二进制编码输入到计算机的编码长度，也就是所占存储的大小。问题的规模通常用整数量n表示。一般情况是数据元素的大小假定为1个单位，这样问题的规模n就是数据元素的个数(大部分情况都是这样)。为了便于比较同一问题的不同算法或者分析一个问题的算法复杂性，通常的做法是，从算法中选取几种对于所研究的问题来说是基本操作的原操作，以该基本算法重复执行的次数作为算法的时间度量。这个度量一般是n的某个函数f(n)，算法的时间复杂度记作T(n)=O(f(n).如：时间复杂度分为最坏情况、最好情况和平均情况下的时间复杂度。空间复杂度是衡量一个算法所需存储空间尺度
6、，记作S(n)=O(f(n).2.3线性表的链式表示和实现线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单、直观的公式来表示。然而,这种存储结构的弱点是:在作插入或删除操作时,需移动大量数据元素，特别是当数据元素本身的大小比较大时尤为如此。线性表的链式存储结构-它不再要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表可随机存取的优点（即查找不是很方便）。2.3.1线性链表线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以
7、是不连续的)。因此,对每个数据元素来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素的存储映像,称为结点(node)。它包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。带头结点的单链表：即在单链表的第一的结点之前附设一个不存储任何信息的结点，这个结点称为头结点。3.单链表的删除操作4.查找、插入和删除算法的时间复杂度算法2.8,2.9和2.10的复杂度均为O(n)因为要操作第i个结点，必须首先要找到第i-1个结点。2.3.2循环链表 3.1栈（后进先出表、LIFO表）3.1.1抽象的数据类型的定
8、义3.1.2栈的表示和实现循环链表(circularlinkedlist)是另一种形式的链式存储结构.它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。2.3.3双向链表第一章的作业 2.2,2.4,2.6,2.7,2.8 2.15,2.212.4一元多项式的表示和实现两个多项式相加的算法3.4队列队列(queue)是一种先进先出(firstinfirstout,缩写为FIFO)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫队尾(Rear),删除的一端叫队头(Front).队列的
9、链式表示和实现-链队列本章的作业第3.33.43.133.28题第4章串(string，或字符串)串也就是字符串。计算机上的非数值处理的对象基本上是字符串数据。在事务处理程序中,顾客的姓名和地址以及货物的名称、产地和规格等一般是作为字符串处理的。又如信息检索系统、文字编辑程序、问答系统、自然语言翻译系统以及音乐分析程序等,都是以字符串数据作为处理对象的。对字符串数据的处理比处理整数和浮点数要复杂得多。4.1串类型的定义串(string，字符串)是由零个或多个字符组成的有限序列,一般记为S=abcdef.其中,S是串的名,用单引号括起来的字符序列是串的值,字符可以是字母、数字、汉字或其他字符;串
10、中字符的数目称为串的长度。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称作主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。称两个串是相等的当且仅当这两个串的值相等。也就是说,只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。零个字符的串称为空串(nullstring),它的长度为零。4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.3串的模式匹配算法串(string，字符串)是由零个或多个字符组成的有限序列.串中任意个连续的字符组成的子序列称为该串
11、的子串(模式串),包含子串的串相应地称作主串。子串的定位操作通常称做串的模式匹配。如果主串中有子串，则称匹配成功；否则匹配失败或叫匹配不成功。4.3.1求子串位置的定位函数Index(S,T,pos)intIndex(SStringS,SStringT;intpos)succ=0;for(i=pos;(i0&jT0)succ=i;returnsucc;以上算法的时间复杂性最好情况：O(n+m)最坏情况：O(n*m)4.3.2模式匹配的一种改进算法 -KMP算法这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的,因此人们称它为克努特一莫里斯一普拉特操作(简称为K
12、MP算法)。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。4.4串的操作应用举例4.4.1文本编辑4.4.2建立词索引表4.4.3程序和文章的编译4.4.4文本文件的压缩4.4.5复习基本内容包括：数据类型的定义，三种存储表示（定长顺序存储结构、块链存储结构、堆分配存储结构）和各种基本操作的实现；串的模式匹配算法。学习要点：主要围绕基本内容展开。第3和4章的作业题第3.33.43.133.28题第4.44.74.174.25题第5章数组和广义表数组是同学们已经很熟悉的一种数据类型,几乎所有的程序设计语言都把数组类型设定为固有类型。广义表也是线性表的一种推广，它的每一项不光是单个的元素，也可以是一个子广义表。如D=(),(a),(b,c),(a,b,c),(a,(b,c)数组和广义表可以看成是线性表在下述含义上的扩展:表中的数据元素本身也是一个数据结构。本章讨论它们的定义和实现。5.1数组的定义二维数组5.2数组的顺序表示和实现由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动。因此,采用顺序存储结构表示数组是自然的事了。由于存储单元是一维的结构,而数组是个多维的结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题，即按照什么样的次序来存储数组元素。对二维数组，一般有行优先和列优先两种方式。
