数据结构期末复习总结.docx

《数据结构期末复习总结.docx》由会员分享，可在线阅读，更多相关《数据结构期末复习总结.docx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结第 1章绪论1. 数据 Data ：是描述客观事物的数字、字符以及全部能输入到运算机中并能被运算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。2. 数据元素 Data Element ：表示一个事物的一组数据称为一个数据元素（结点顶点、 记录）。 数据元素是数据的基本单位。3. 数据项 （ Data Item ）：是数据元素中有独立含义的、不行分割的最小标识单位（字段、 域、属性）。一个数据元素可由如干个数据项组成。4. 数据对象 Data Object ：是性质相同的数据元素的集合,是数据的一个子集。如字符集合 C=A,B,C, 。数

2、据 Data ：是描述客观事物的数字、 字符以及全部能输入到运算机中并能被运算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。数据元素 Data Element：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）。数据元素是数据的基本单位。数据项（ Data Item ）：是数据元素中有独立含义的、不行分割的最小标识单位（字段、域、属性）。一个数据元素可由如干个数据项组成。数据对象 Data Object ：是性质相同的数据元素的集合,是数据的一个子集。如字符集合 C =A,B,C, 。数据的规律结构指数据元素之间的规律关系,用一个数据元素的集合

3、和定义在此集合上的如干关系来表示。四种规律结构：集合、线性结构、树型结构、图状结构。数据结构的形式定义是一个二元组：Data-Structure=D , S其中： D 是数据元素的有限集,S 是 D 上关系的有限集。例 1：设数据规律结构B=（K,R）K=k1, k2, , k9R= , , , 可编辑资料 - - - 欢迎下载精品名师归纳总结有时候关系图不唯独（一般是无向图）数据结构在运算机内存中的储备包括数据元素的储备和元素之间的关系的表示。两种不同的储备结构：次序储备结构和链式储备结构。次序结构：数据元素存放的的址是连续的。链式结构： 数据元素存放的的址是否连续没有要求,用该指针来表示数

4、据元素之间的规律结构关系 。次序储备使用一组连续的内存单元依次存放数据元素,元素在内存中的物理储备次序表达它们的规律次序。通常使用程序设计语言中的数组来实现。可编辑资料 - - - 欢迎下载精品名师归纳总结.链式储备使用如干的址分散的储备单元储备数据元素,规律上相邻的数据元素在物理位置上不肯定相邻。数据元素间的规律关系通过结点间的链接关系来表达。通常使用指针记载直接前驱元素或直接后继元素的储备的址。数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。.初始化。.判定是否空状态。.统计元素的个数。.遍历：按某种次序拜访全部元素,每个元素只被拜访一次。.取值：猎取

5、指定元素值。.置值：设置指定元素值。.插入：增加指定元素。.删除：移去指定元素。.查找：在数据结构中查找满意给定条件的数据元素。.排序：将数据元素.数据操作定义在数据的规律结构上。数据操作的实现依靠于数据的储备结构。.数据结构三方面的关系：数据的规律结构、数据的储备结构及操作这三方面是一个整体例 6：线性表是一种规律结构,如采纳次序储备,可称其为次序表。如采纳链式储备,就可称其为链表。如采纳散列储备,就可称为散列表。.在给定了数据的规律结构和储备结构之后,按定义的操作集合及其操作的性质不同, 也可能导致完全不同的数据结构。.类型（ type）是具有相同规律意义的一组值的集合。.数据类型是指一个

6、类型和定义在这个类型上的操作集合。31数据类型定义了数据的性质、取值范畴以及对数据所能进行的各种操作例 7： Java中整型类型 int 的值集是可编辑资料 - - - 欢迎下载精品名师归纳总结-2 31, -,2,- 1,0,1,2,-,12可编辑资料 - - - 欢迎下载精品名师归纳总结这个值集上的操作集合 +,-,*,/,%,=,=,.=,=可编辑资料 - - - 欢迎下载精品名师归纳总结抽象数据类型 Abstract Data Type ,简称 ADT：是指一个数学模型以及定义在该模型上的一组操作。ADT 的定义仅是一组规律特性描述,与其在运算机内的表示和实现无关。因此,不论 ADT

7、的内部结构如何变化, 只要其数学特性不变, 都不影响其外部使用。ADT 的形式化定义是三元组：ADT=D, S, P其中： D 是数据对象, S 是 D 上的关系集, P 是对 D 的基本操作集。ADT 的一般定义形式是： ADT 数据对象： 数据关系： 基本操作： ADT 例 8： 复数抽象数据类型描述如下：ADT Complex double real,imag;Complexdouble real, double imag;Complex addComplex c; Complex subComplex c;1、算法定义：一个算法（algorithm ）是一个有穷规章的集合,其规章确定一

8、个解决某一特定类型问题的操作序列（D.Knuth）。算法的规章必需满意以下5 个特性： 有穷性： 一个算法必需总是在执行有穷步之后终止,且每一步都在有穷时间内完成。 确定性：算法中每一条指令必需有准确的含义。不存在二义性。且算法只有一个入口和可编辑资料 - - - 欢迎下载精品名师归纳总结一个出口。 可行性： 一个算法是能行的。 即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入： 一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。 输出： 一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。2、算法设计目标 正确性 健壮性 高时间效率 高空间效率 可读

9、性可编辑资料 - - - 欢迎下载精品名师归纳总结3、算法描述自然语言描述伪码描述传统流程图描述程序设计语言描述（本课程选Java）可编辑资料 - - - 欢迎下载精品名师归纳总结4、算法与数据结构.算法建立在数据结构之上,对数据的操作需用算法来描述。.算法设计依靠数据的规律结构,算法实现依靠数据的储备结构。.实现一种抽象数据类型,需要挑选合适的储备结构。求解同一问题可能有很多不同的算法,如何去评判这些算法的优劣？主要考虑如下三点：A. 执行算法所耗费的时间。B. 执行算法所耗费的储备空间,其中主要考虑帮助储备空间。C. 算法应易于懂得,易于编码,易于调试等等。1、时间代价分析算法的时间效率指

10、算法的执行时间随问题规模的增长而增长的趋势,通常采纳时间复杂度来度量算法的时间效率 ,用大 O 表示法来记 :Tn=Ofn例 1void fun+x; s=0 ;将 x 自增看成是基本操作,就语句频度为,即时间复杂度为1 。假如将 s=0 也看成是基本操作,就语句频度为,其时间复杂度仍为1,即常量阶。一个简洁语句的时间复杂度为1。例 2fori=1; i=n; +i+x;s+=x ;语句频度为： 2n ,其时间复杂度为： n ,即为线性阶。一个循环的时间复杂度为n。例 3fori=1; i=n; +i可编辑资料 - - - 欢迎下载精品名师归纳总结forj=1; j=n; +j+ x;s +=

11、 x;语句频度为： 2n2 ,其时间复杂度为： On2 ,即为平方阶。定理：如 An=a m n m+ a m-1 n m-1 + +a1n+a0 是一个 m 次多项式,就 An=On m例 4两个 n 阶方阵的乘法fori=1 , i=n; +i forj=1; j=n; +jcij=0 ;fork=1; k=n; +k cij+=aik*bkj ;由于是一个三重循环,每个循环从1 到 n,就总次数为：n n n=n3时间复杂度为3Tn= n 例 5fori=2;i=n;+iforj=2;j=i-1;+j+x;ai,j=x;语句频度为：1+2+3+ +n-2=1+n-2 n-2/2=n-1n

12、-2/2 =n 2-3n+2时间复杂度为 On2,即此算法的时间复杂度为平方阶。例 6： int n=8, count=0;for int i=1; i=n; i*=2for int j=1; j=n; j+ count+;循环次数为。时间复杂度为 Onlog2n。例 7： int n=8, count=0;for int i=1; i=n; i*=2for int j=1; j=i; j+ count+;总的循环次数为。时间复杂度为 On。以下六种运算算法时间的多项式是最常用的。其关系为：O1O nOnOn nOn2On3指数时间的关系为：O2nOn.0 时,将非空的线性表记作：a0, a1

13、, an-1线性表的次序表示指的是一组的址连续的储备单元依次储备线性表的数据元素。用次序储备实现的线性表称之为次序表。线性表的规律次序与物理次序一样。.次序表是一种随机存取结构。通常采纳数组储备数据元素。.设线性表的每个元素需占用c 个储备单元。可编辑资料 - - - 欢迎下载精品名师归纳总结public boolean isEmpty/ 时间复杂度 O1 return this.len = 0;public int length/ 时间复杂度 O1 return this.len;public T getint i/ 时间复杂度 O1 ifi=0 & i =0 & i0str += this

14、.element0.toString; forint i = 1; i this.len; i +str += ,“” + thise.lementi.toString;return str +“ ”;.两个线性表相等是指,它们长度相同并且各对应元素相等。.链式储备：用一组任意的储备单元储备线性表中的数据元素。储备链表中结点的一组任意的储备单元可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。.链表中结点的规律次序和物理次序不肯定相同。可编辑资料 - - - 欢迎下载精品名师归纳总结.链表中的结点结构：数据域和的址域n 个结点构成的链表表示为a0, a1, ., an-1.

15、链表中每个结点只含一个的址域,又称为线性链表或单链表。.每个结点有两个的址域的线性链表称为双链表。.单链表是由表头唯独确定,因此单链表可以用头指针的名字来命名。头结点的作用是,使全部链表（包括空表）的头指针非空,就对单链表的插入、删除操作不需要区分操作位置。头结点中不储备数据。头插入和头删除操作不会转变head 指针总结 次序表和链表的比较（1） 直接拜访元素的性能可编辑资料 - - - 欢迎下载精品名师归纳总结次序表能够直接拜访数据元素,即只要给出次序表底层数组element 的下标就可以拜访数组中的任何一个数据元素。（随机存取）而链表中不能随机的直接拜访大多数元素,只能从链表的第一个结点开

16、头,沿着链的方向,依次查找后续结点,直至到达所需拜访的结点。（次序存取）（2） 储备空间的利用由于需要估量次序表底层数组element 的大小（次序表的容量） ,因此次序表存在储备空间的铺张问题。次序表在进行插入操作时,要判定次序表是否为满。假如满,就需要扩充容量。 而链表每插入一个结点,就向系统申请一个储备单元,只要系统资源足够,系统就会为该结点安排储备空间。（3） 储备密度储备密度 （ Storage Density）是指结点数据本身所占的储备量和整个结点结构所占的储备量之比,即：（结点数据本身所占的储备量）（整个结点所占的储备总量）次序表的全部空间都用来存放数据元素,因此储备密度=1。而

17、链表中每个结点都要包含其后继结点或者前驱结点的链,因此储备密度=0） 个相同类型的数据元素a0,a1,。an-1 组成的有限序列, 记为：a0,a1, an-1。 其中, n 为数据元素的个数,称为栈的长度。n=0 时,为空栈。.栈的溢出： 当栈满时进栈运算称为“上溢” 。 当栈空时退栈运算称为“下溢” 。可编辑资料 - - - 欢迎下载精品名师归纳总结 栈上溢是一种出错状态,应当设法防止之。而下溢就可能是正常现象,通常下溢用来作为程序掌握转移的条件。.由于栈是运算受限的线性表,因此线性表的储备结构对栈也适应。.栈的次序储备结构简称为次序栈（ Sequential Stack）,它是运算受限的

18、线性表。因此,可用数组来实现次序栈。.由于栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端 点。栈顶位置是随着进栈和退栈操作而变化的,一般需用一个整型变量top 。栈的次序储备结构及操作实现public class SeqStack implements Stack/ 次序栈类,实现栈接口Object element;/ 储备栈数据元素的数组int top;/ 栈顶元素下标留意： element 数组储备栈的数据元素。top 表示当前栈顶元素的下标。经典实现：（1）栈的初始化public SeqStackint size/ 构造容量为 size 的空栈this.elemen

19、t = new ObjectMath.abssize; this.top= -1;public SeqStack/ 构造默认容量的空栈this64;（2） 判读栈是否为空public boolean isEmpty/ 判定栈是否空,如空返回truereturn this.top=-1;.判读栈是否为满？本实现采纳与次序表同样的处理：当容量不够时,就将数组容量扩充一倍。（3） 入栈public void pushT x/ 元素 x 入栈,空对象不能入栈if x=nullreturn;/ 空对象不能入栈if this.top=element.length-1 /如栈满,就扩充栈容量Object t

20、emp = this.element;/ 重新申请一个容量更大的数组this.element = new Objecttemp.length*2;for int i=0; itemp.length; i+/ 复制数组元素, On this.elementi = tempi;this.top+; this.elementthis.top = x;可编辑资料 - - - 欢迎下载精品名师归纳总结（4） 出栈栈不空时,取走 top 位置处栈顶元素, top 减 1,下一位置数据元素作为新的栈顶元素public T pop/ 出栈,返回栈顶元素,如栈空返回nullreturn this.top= -1

21、 . null : T this.elementthis.top -;（5） 获得栈顶数据元素栈不空时,猎取 top 位置处栈顶元素,此时数据元素未出栈,top 值不变public T get / 取栈顶元素,未出栈,如栈空返回nullreturn this.top=-1 . null : Tthis.elementthis.top;/ 次序栈类,最终类,实现栈接口,T 表示元素类型public final class SeqStackimplements Stackprivate SeqList list;/ 次序表public SeqStackint capacity / 构造栈publi

22、c SeqStack/ 构造空栈public boolean isEmpty/ 判空public void pushT x/x 入栈public T peek/ 返回栈顶（未出栈）public T pop/ 出栈,返回栈顶元素.栈的链式储备,称为链栈。.链式栈的基本运算同次序栈,定义也同线性表的链表定义,它是对链表实现的简洁化（由于它只是对链表的头部操作）。.可用单链表实现链栈。.它的元素只能在表头进行插入和删除。在链式储备结构中,不需要给出表头结点（head ）,由于其中惟一的已知条件是栈顶指针top ,它是指向链式栈的第一个结点（相当于头指针） 。. 栈的各种运算比链式储备的一般线性表运算

23、实现时要便利得多,主要缘由是栈的各种运算只能在栈的一端操作,栈是特别的线性表,我们只要考虑对线性表的一端操作的情形,并且只能在一端插入删除（栈顶）. 而线性表除此之外 （不限定一端插入删除） ,仍需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作,懂得时,我们可以把栈的入出栈运算当作线性表的一端进行插入删除的特例即可。链式栈实现（经典实现）栈的链式储备结构及操作实现public class LinkedStack implements Stackprivate Node top;（1） 栈的初始化可编辑资料 - - - 欢迎下载精品名师归纳总结public LinkedStack/ 构

24、造空栈this.top=null;（2） 判读栈是否为空public boolean isEmpty/ 判定栈是否空,如空返回truereturn this.top=null;（3） 入栈public void pushT x/ 元素 x 入栈,空对象不能入栈if x.=nullthis.top = new Nodex, this.top;/ 头插入, x 结点作为新的栈顶结点（4） 出栈public T pop/ 出栈,返回栈顶元素,如栈空返回nullif this.top=nullreturn null;T temp = this.top.data;/ 取栈顶结点元素this.top =

25、this.top.next;/ 删除栈顶结点return temp;（5） 获得栈顶元素public T get/ 取栈顶元素,未出栈,如栈空返回nullreturn this.top=null . null : this.top.data;链式栈实现（基于单链表）/ 链式栈类,最终类,实现栈接口,T 表示数据元素的数据类型public final class LinkedStack implements Stackprivate SinglyList list;/ 使用单链表（第 2 章）储备栈元素public LinkedStack/ 构造空栈this.list = new SinglyL

26、ist;/ 构造空单链表public boolean isEmpty/ 判定栈是否空,如空返回true可编辑资料 - - - 欢迎下载精品名师归纳总结return this.list.isEmpty;public void pushT x/ 元素 x 入栈,空对象不能入栈this.list.insert0, x;/ 单链表头插入元素xpublic T peek/ 返回栈顶元素（未出栈） 。如栈空返回nullreturn this.list.get0;public T pop/ 出栈,返回栈顶元素。如栈空返回nullreturn this.list.remove0;/ 如栈不空,单链表头删除,返

27、回删除元素public String toString/ 返回栈全部元素的描述字符串,形式为“,”return this.getClass.getName+ +this.list.toString;次序栈和链式栈的比较.实现链式栈和次序栈的操作,都是需要常数时间,即时间复杂度为O（ 1）。主要两者从空间和时间两个方面考虑： 初始时,次序栈必需说明一个固定的长度,当栈不够满时,造成一些空间的铺张,而链式栈的长度可变就是长度不需要预先设定,相对比较节约空间, 但是在每个结点中,设置了一个指针域,从而产生了结构开销。 当需要多个栈共享时, 次序储备中可以充分利用次序栈的单向延长性。可以使用一个数组储

28、备两个栈,使每个栈从各自的端点向中间延长,这样铺张的空间就会削减。 但这种情形只有当两个栈的空间需求有相反的需求时,这种方法才有效。也就是说,最好一个栈增长,一个栈缩短。反之,假如两个栈同时增长,就可能比较简洁造成栈的溢出。假如多个次序栈共享空间,就可能需要大量的数据移动, 造成时间的开销增大。 而链式栈由于储备的不连续性,一般不存在栈满的问题,所以一般不需要栈的共享。.【例3】使用栈运算算术表达式值算术表达式有三种表示方法： ,如 A+B,称为中缀 infix 表示。 ,如 +AB 称为前缀 prefix 表示。 ,如 AB+,称为后缀 postfix 表示。中缀表达式： 1+2*3-4+5

29、其对应的后缀表达式为1234-*+5+习题 中缀表达式如下,写出后缀表达式。可编辑资料 - - - 欢迎下载精品名师归纳总结A+B*C-D*E+F/G+H-I+J*K【习题解答】 ABCDEF+*G/-H+*+IJ+K*. 队列的定义： 队列 Queue也是一种运算受限的特别线性表。其插入和删除操作分别在线性表的两端进行（只答应在表的一端进行插入,而在另一端进行删除） 。答应删除的一端称为队头 front ,答应插入的一端称为队尾 rear 。 当队列中没有元素时称为空队列。 在空队列中依次加入元素 a1,a2, an 之后, a1 是队头元素, an 是队尾元素。明显退出队列的次序也只能是

30、a1,a2, an , 也就是说队列的修改是依先进先出的原就进行的,例如：排队购物。 先进入队列的成员总是先离开队列。因此队列亦称作先进先出 First In First Out的线性表,简称 FIFO表。队列的操作： 一般情形下,入队enqueue 操作又称为队列的插入。 出队 dequeue 操作又称为队列的删除。队列的数据元素： 队列的数据元素和线性表的数据元素完全相同,即队列的数据元素是n（ n=0）个相同类型的数据元素a0,a1,。an-1 组成的有限序列, 记为：a0,a1, an-1。 其中, n 为数据元素的个数,称为队列的长度。n=0 时,为空队列。 队列的溢出： 队列在次序

31、储备时,常常显现“假溢出 ”现象,解决“假溢出”现象的方法有很多种,但通常采纳循环队列方式储备。 使用次序表,出队效率低。因此不使用次序表作为队列的成员变量。次序循环队列：.现在解决“假溢出”比较好的解决方案是使用循环向量,储备在循环向量中的队列称为循环队列（Circular Quene ）。.将次序队列设计成在规律上首尾相接的循环结构,就可循环使用次序队列的连续储备单元。可编辑资料 - - - 欢迎下载精品名师归纳总结.循环队列的操作：.假设数组的空间是m,只要在入、出队列时,将队首和队尾的指针对m 做求模运算即可实现队首和队为指针的循环,即队首和队尾指针的取值范畴是0 到 m-1 之间。队

32、空： front = rear队满： front = rear + 1 % maxSize 或另外设一个标志以区分队空、队满入队 :rear = rear + 1 % maxSize出队 :front = front + 1 % maxSize;求队长 : rear - front + maxSize%maxSize链式队列的基本概念： 定义链队列的储备结构基本和线性表的定义相同,它是对链表实现的简洁化。 队列的各种运算比链式储备的一般线性表运算实现时要便利得多,主要缘由是队列的各种运算只能在队列的两端操作。.队列是特别的线性表,我们只要考虑对线性表的两端操作的情形, 并且只能一端插入（队首）

33、 ,另一端删除（队尾） 。.而线性表除此之外（不限定一端插入、一端删除）,仍需要考虑中间的结点的插入、删除、查询等操作。.懂得时,我们可以把队列的入、出队运算当作线性表两端进行插入删除的特例即可。.于是,一个链队列由头指针和尾指针唯独确定。.使用单链表,入队效率低。.单链表设计,增加尾指针。.以不带头结点的单链表实现链式队列。.队列的应用 （一）合并两个队列. 假设有两个队列,要求将两个队列合并到一起,合并时交替使用两个队列中的元素,并把剩余的队列中的元素添加在最终,将产生的新队列返回。 （二）模拟客户服务系统 （三） 主机与外部设备之间速度不匹配的问题. 以主机和打印机为例来说明,主机输出数

34、据给打印机打印,主机输出数据的速度比打印机打印的速度要快得多,如直接把输出的数据送给打印机打印,由于速度不匹配,明显是不行的。所以解决的方法是设置一个打印数据缓冲区,主机把要打印输出的数据依此写如到这个缓冲区中,写满后就暂停输出,继而去做其它的事情,打印机就从缓冲区中根据先进先出的原就依次取出数据并打印,打印完后再向主机发出恳求,主机接到恳求后再向缓冲区写入打印数据, 这样利用队列既保证了打印数据的正确,又使主机提高了效率。第 5 章 数组和广义表.数组是数据结构的基本结构形式,它是一种次序式的结构,数组是储备同一类型数据的数据结构。.数组是次序储备的随机存取结构,数组是其他数据结构实现次序储

35、备的基础。.使用数组时需要定义数组的大小和储备数据的数据类型。.数组分为一维数组和多维数组。数组的维数是由数组下标的个数确定的：可编辑资料 - - - 欢迎下载精品名师归纳总结.一个下标称为一维数组.一个下标以上的数组称为多维数组.从这个意义上讲, 确定了对于数组的一个下标总有一个相应的数值与之对应的关系。或者说数组是有限个同类型数据元素组成的序列.数组是二元组 的一个集合。.一维数组具有线性表的结构,但操作简洁,一般不进行插入和删除操作,只定义给定下标读取元素和修改元素的操作。.声明的格式一般是： = new 。 如： int element = new int5;一维数组的储备一维数组的数据储备根据次序储备,规律的址和物理的址都是连续的。假如已知第一个数据元素的的址loca 0,就第 i 个元素的的址 locai为： Loca i= Loca0 i c.数组安排内存空间的方式有2 种： 静态数组：声明时给出数组元素个数。当程序开头运行时,数组即获得系统 安排的一块的址连续的内存空间。静态数组所占用的内存空间由系统自动治理。int 3 = 1,2,3; 动态数