西安交通大学数据结构复习资料

精心整理第一章绪论1、数据结构的主要研究内容①数据的逻辑结构--数据关系之间的逻辑关系②数据的存储结构--数据的逻辑结构在计算机中的表示2、数据逻辑结构的种类：集合、线性表、树和图的性质和特点。集合结构中的元素是各自独立的，元素之间没有联系线性结构中的元素是一个接一个串联起来的，它有一个头元素和一个尾元素，其余为中间元素；每个中间元素既有前驱元素，又有后继元素在树结构中，树根结点只有后继结点，而没有前驱结点；除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。树结构是图结构的特例，线性结构是树结构的特例。为了区别于线性结构，时常把树结构和图结构称为非线性结构。3、数据结构的二元组定义，能根据给出的二元组来判断数据的逻辑结构类型。集合结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={}线性结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={A,B，B,C，C,D，D,E，E,F，F,G}精心整理树结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={A,B，A,C，A,D，C,E，C,F，D,G}图结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={A,B，A,C，A,G，D,G，D,F，C,E，C,F，G,F}4、了解数据的几种存储结构（物理结构）及它们各自的性质和特点。（1）顺序的方法:将逻辑上相邻的元素存储到物理上相邻的存储位置.常用于线性的数据结构.（2）链式结构：给结点附加一个指针字段,指出其后继节点的位置,即存放结点的存储单元分为两部分:数据项指针项（3）散列（hashing)结构：散列的方法是用结点的关键字值直接计算出结点的存储地址。这个取值函数也称为散列函数。5、数据的逻辑结构、存储结构和总的数据结构之间的关系逻辑结构相同，但存储结构不同，则认为是不同的数据结构。如顺序表和链表具有相同的逻辑结构，但存储结构分别为顺序结构和链表结构6、算法的设计要求有那些，会结合实际的语言设计来说明这些要求1）正确性：对于合法的输入产生符合要求的输出；2）可读性：算法应该易读、便于交流，这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法；3）健壮性：当输入非法时，算法还能做出适当的反应而不会崩溃，如输出错误信息；算法中应该考虑适当的错误处理；精心整理4）效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。7、了解时间复杂度的概念、时间复杂度的度量、时间复杂度的类型，能对实际的程序分析它的时间复杂度。算法的时间复杂度是一个算法运行时间的相对量度。把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用它来衡量一个算法的运行时间性能或称计算性能平均复杂度(TheAverageCase)：所有可能输入.数据集的期望值．最坏情况复杂度(TheWorstCase)：估算最坏情况下时间复杂度的一个上界．这也是通常所指的复杂度．最好复杂度(TheBestCase):在最理想输入情况下的时间复杂度。第二章线性表1、了解并掌握线性表的定义及性质线性表是线性结构的一种表现形式，即是具有相同属性数据元素的一个有限序列，序列中的元素是一个接一个在逻辑上是有序的，序列中元素的个数就是该线性表的长度.存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除起点元素之外，集合中的每个数据元素均只有一个前驱除终点元素之外，集合中每个数据元素均只有一个后继起点元素只有后继没有前驱，终点元素只有前驱没有后继对于线性表中的数据元素ai-1和ai来说，ai-1是ai的直接前驱，ai是ai-1的直接后继。精心整理所有数据元素ai在同一个线性表中必须是相同的数据类型。2、熟悉顺序线性表（顺序存储的线性表）的存储方式及其表单元（简单数据类型和记录数据类型）的定位和计算。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即前驱元素一定存储在后继元素的前面。3、熟悉顺序线性表的插入、删除和查找的算法思想和程序4、了解线性表链接存储的结构和特点假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域（或称为信息域）；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点，从而可以表示数据元素之间的逻辑关系。长度可以任意扩充，存储效率较高；物理存储可以是不连续的；数据元素的逻辑次序可以与其存储的物理次序不一致。插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可5、了解单链表、双向链表和循环链表的结构和特点精心整理通过每个结点的指针域将n个结点按其逻辑顺序链接在一起的结点序列我们就称为链表。如果这一链表中每个结点只有一个指针域，则称该链表为线性链表或单链表，否则则称为双向链表。双向链表是指线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其直接前驱；另一个称为右指针，用以指向其直接后继。循环链表。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NULL”，而是指向头一个结点，成为一个由链指针链结的环。循环链表的特点：只要知道表中任何一个结点的地址，就能查询到表中的任何一个结点。6、了解单链表的结点的类型定义在程序中，L为单链表的头指针，它指向表中第一个结点。若L为“空”(L=NULL)，则所表示的线性表为“空”表，其长度为“零”。除了线性表第一个数据元素作为该链表的头结点外，在某些线性链表存储结构中，还可在单链表第一个结点之前附加一个同结构结点，称为附加头结点。头结点数据域可以不存储任何信息，也可以存储如线性表的长度等类的附加信息；头结点指针域存储指向第一个结点的指针(即第一个元素的存储位置)。那么，指向头结点的指针就是头指针。当头结点的指针域为“空”时，单链表为空链表8、熟悉单链表中结点的定位、插入、删除、查询的算法思想和操作程序9、了解线性表的顺序与链式存储各自的优点、不足与它们适用场合。若线性表的操作主要是查找和读取时，采用顺序存储结构为宜；若线性表的操作主要是插入和删除时，采用链式存储结构为宜。10、了解线性表的顺序与链式存储在不同操作场合下的时间复杂度指标顺序表是随机存储结构，表中任一数据元素都可以通过计算直接得到地址进行存取，时间复杂度为O(1)。在顺序表中进行插入和删除数据元素时，平均要移动近一半的精心整理元素，尤其是当每个数据元素包含的信息量较大时，移动元素所花费的时间就相当可观。动态链表是顺序存储结构，表中的任一结点都需要从头指针起顺链扫描才能取得，时间复杂度为O(n)(n为表长)。但在动态链表中进行插入和删除结点时，不需要移动结点，只需要修改指针。第四章栈和队列1、了解栈的定义及性质栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。2、能给出在特定要求下的进出栈序列以及判断某些出栈序列出现的可能性3、了解栈的顺序存储结构实现，栈顶指针的设置4、了解栈的链接存储结构的实现、栈顶指针的更改5、熟悉栈在顺序和链接存储结构下的进栈、出栈和读取栈顶元素的操作程序6、了解递归算法的特点及递归算法的中止条件，会结合具体程序来分析递归程序的合理性7、了解队列的定义和它的顺序存储结构队列（queue）简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。我们把进行插入的一端称作队尾(rear)，进行删除的一端称作队首(front)。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。精心整理由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序离队，所以又把队列称为先进先出表（firstinfirstout,简称FIFO）。8、了解队列特别是循环队列情况下，队列头指针和尾指针的设置9、了解队列出现“假溢出”现象的原因及解决办法：循环队列的实现（循环头指针和尾指针的计算、循环（和普通）队列长度的计算以及循环队列为空和满的判断方法）第五章树和二叉树1、了解树的定义和树的基本术语：树和结点的度、分支结点和叶子结点、父母结点和孩子结点、结点的层数和树的深度、有序树和无序树等在树形表示法中，结点之间的关系是通过连线表示的，虽然每条连线上都不带有箭头(即方向)，但它并不是无向的，而是有向的，其方向隐含为从上向下或从左向右，即连线的上方或左边结点是下方或右边结点的前驱，下方或右边结点是上方或左边结点的后继。结点的度：树中每个结点具有的非空子树数或者说后继结点数被定义为该结点的度（degree）。树的度：一棵树上所有结点的度的最大值就是这棵树的度。叶子结点：度为零的结点称叶子结点或终端结点。分支结点：度非零的结点称为分支结点或称为非终端结点。孩子结点(child)：某结点子树的根或者说某个结点的后继被称为该结点的孩子结点。双亲结点(parent)：一个结点是它的那些子树的根的双亲结点。兄弟结点(sibling)：同一个双亲的孩子之间互为兄弟。精心整理堂兄弟结点(cousins)：其双亲在同一层但不同的结点互为堂兄弟。子孙结点：每个结点的所有子树中的结点被称为该结点的子孙结点祖先结点：从整个（子）树的根结点到达该结点的路径上经过的所有分支结点结点层次：从根结点开始，根结点为第1层，根结点的孩子为第2层，依此类推1A………..第1层2B3C4D….第2层5E6FG7……...第3层树的深度：树中结点的最大层次。有序树：结点的子树从左到右有序安排。也即树T中各子树T1，T2，…，Tn的相对次序是有意义的。在有序树中，改变了子树的相对次序就变成了另一棵树。无序树：结点的子树顺序任意。2、熟悉树的性质，并能根据这些性质进行相关推理和计算性质1:树中的结点数等于所有结点的度数加1。证明：根据定义：除根结点外，每个结点有一个分支指向。树的总分支数为：性质2：度为k的树中第i层上至多有ki-1个结点（i≥1）。用数学归纳法证明：对于i=1,ki-1=k0=1命题成立。假设第i-1层(i1)命题成立，该层上有ki-2个结点。对于第i层，最多结点数为：ki-2.k=ki-1命题得证。性质3深度为h的k叉树至多有个结点。证明：利用性质2来证明，k叉树的最大结点数为每一层最大结点数之和，则有：11kkhniit1精心整理当一棵k叉树上的结点数等于时，则称该树为满k叉树。性质4：具有n个结点的k叉树的最小深度为：logk(n(k-1)+1)分析：在结点数相同的k叉树中，每一层结点都满，或除最后一层外其余层都满的树，其深度为最小。证明：设k叉树的最小深度为h，则：前h-1层满的k叉树结点数n≤h层都满的k叉树结点数，因此有：上式可变换为：kh-1n(k-1)+1≤kh以k为底取对数可得：h-1logk(n(k-1)+1)≤h即：logk(n(k-1)+1)≤hlogk(n(k-1)+1)+1因k只能为整数，所以：h=logk(n(k-1)+1)因此得到具有n个结点的一般k叉树的最小深度为：logk(n(k-1)+1)注：x表示对x进行向上取整3、熟悉二叉树的定义及基本性质，并能根据这些性质进行相关推理和计算。二叉树(binarytree)是指树的度为2的有序树。它是一种树结构,在计算机领域有着广泛地应用。二叉树的递