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

第一章绪 论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、了解时间复杂度的概念、时间复杂度的度量、时间复杂度的类型，能对实际的程序分析它的时间复杂度。算法的时间复杂度是一个算法运行时间的相对量度。把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用它来衡量一个算法的运行时间性能或称计算性能平均复杂度(The Average Case)：所有可能输入.数据集的期望值．最坏情况复杂度 (The Worst Case)：估算最坏情况下时间复杂度的一个上界．这也是通常所指的复杂度．最好复杂度 (The Best Case):在最理想输入情况下的时间复杂度。第二章 线性表1、了解并掌握线性表的定义及性质线性表是线性结构的一种表现形式，即是具有相同属性数据元素的一个有限序列，序列中的元素是一个接一个在逻辑上是有序的，序列中元素的个数就是该线性表的长度.存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除起点元素之外，集合中的每个数据元素均只有一个前驱除终点元素之外，集合中每个数据元素均只有一个后继起点元素只有后继没有前驱，终点元素只有前驱没有后继 对于线性表中的数据元素ai-1和ai来说，ai-1是ai的直接前驱，ai是ai-1的直接后继。所有数据元素ai在同一个线性表中必须是相同的数据类型。2、熟悉顺序线性表（顺序存储的线性表）的存储方式及其表单元（简单数据类型和记录数据类型）的定位和计算。 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即前驱元素一定存储在后继元素的前面。3、熟悉顺序线性表的插入、删除和查找的算法思想和程序4、了解线性表链接存储的结构和特点假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域（或称为信息域）；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点，从而可