东莞理工成大计算机科学与技术本科数据结构复习整理

第一章：绪论1.2基本概念和术语1.数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。P42.数据元素（dataelement）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项(dataitem)组成。数据项是数据的不可分割的最小单位。P43.数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集。P44.数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是鼓励存在的，而是在他们之间存在某种关系，这种数据元素相互之间的关系称为结构(structure).根据数据元素之间的关系不同，通常有下列4种基本结构：（1）集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；（2）线性结构：结构中的数据元素之间存在一个对一个的关系；（3）树形结构：结构中的数据元素之间存在一个对多个的关系；（4）图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。P55.数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D,S);其中：D是数据元素的有限的有限集，S是D上关系的有限集。P56.结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。P67.数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫位(bit)。在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素，通常这个位串为元素（element）或结点(node)。当数据元素由若干数据项组成时，位串中对于各个数据项的子位串称为数据域(datafield)。因此，元素或结点可以看成是数据元素在计算机中的映射。P61.3抽象数据类型的表示与实现1.4算法和算法分析1.算法(algorithm)是对特定问题求解的一种描述，他是指令的有限序列，其中每一条指令表示一个或多个操作；P132.算法的5个重要特性：(1)有穷性；(2)确定性；(3)可行性；(4)输入；(5)输出；P133.算法的设计的要求：(1)正确性；(2)可读性；(3)健壮性；(4)效率与低存储量需求；P134.时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))；它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度(asymptotictimecomplexity)，简称时间复杂度。P155.空间复杂度：作为算法所需存储空间的量度，记作：S(n)=O(f(n))；其中n为问题的规模(或大小)。P17----------------------------------------------------------------------------------------------------------------------第二章：线性表2.1线性表的类型定义1.线性结构的特点：在数据元素的非空有限集中，(1)存在唯一的一个被称做”第一个”的数据元素；(2)存在唯一的一个被称做”最后一个”的数据元素；(3)除第一个之外,集合中的每一个数据元素均只有一个前驱；(4)除最后一个外，集合中每个数据元素均只有一个后继。P182.线性表(linear_list)是最常用且最简单的一种数据结构。P183.在稍复杂的线性表中，一个数据元素可以由若干个数据项(item)组成。这种情况下，常把数据元素称为记录(record)，含有大量记录的线性表又称为文件(file)。P184.抽象数据类型线性表的定义P195.线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。P216.线性表的顺序表示的算法P247线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。为了表示每个数据元素(ai)与其直接后继数据元素(ai+1)之间的逻辑关系，对数据元素(ai)来说，除了存储本身的信息之外，还需要存储一个指示其直接后继的信息(直接后继的存储位置)。这两部分信息组成数据元素(ai)的存储映射，称为结点(node)。它包含两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点（ai（1=i=n）的存储映像）链接成一个链表，即为线性表(a1,a2,…,an)的链式存储结构。又由于链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。有时我们在单链表的第一个结点存储如线性P278.单链表的算法P28~319.循环链表(circularlinkedlist)是另一种形式的链式存储结构。他的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。P3510.双向链表：结构中有两个指针域，其中一个指向直接后继，另一个指向直接前趋。P3511.双向链表算法:P36~37----------------------------------------------------------------------------------------------------------------------第三章：桟和队列1.桟和队列是两种重要的线性结构。从数据结构角度看，桟和队列也是线性表，其特殊性在于桟和队列的基本操作时线性表操作的子集，他们是操作受限的线性表，因此，可称为限定性的数据结构。P442.桟(stack)是限定仅在表尾进行插入或删除的线性表。因此，对桟来说，表尾端有其特殊含义，称为桟顶(top)，相应地，表头称为桟底(bottom)。不含元素的空表称为空桟。桟又称为后进先出(lastinfirstout)的线性表(简称LIFO结构)。顺序桟，即桟的顺序存储结构是利用一组地址连续的存储单元依次存放自桟底到桟顶的数据元素，同时附设指针top指示桟顶元素在顺序桟中的位置。通常的习惯做法是以top=0表示空战。P443.桟的算法:P46~474.队列(queue)是一种先进先出(firstinfirstout缩写为FIFO)的线性表，它只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做队尾(rear)，允许删除的一端则成为队头(front)。P585.队列的算法：P61~62----------------------------------------------------------------------------------------------------------------------第四章：串1.串(String)(或字符串)是由零个或多个字符组成的有限序列，一般记为s=’a1a2’，（n=0）。其中，s是串的名，用单引号括起来的字符序列是串的值；ai(1=i=n)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串(nullstring)，他的长度为零。P702.串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序列号称为该字符在串中的位置。由一个或多个空格组成的串’’称为空串(blankstring，请注意：此处不是空串)，用符号¢来表示’空串’。P713.串的抽象数据类型的定义和算法：P714.子串的定位操作通常称为串的模式匹配(其中T称为模式串)，是各种串处理中的重要的操作之一。P79----------------------------------------------------------------------------------------------------------------------第五章：数组和广义表1.数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。P902.抽象数据类型数组的定义：P903.数组一旦定义，他的维数和维界就不能改变，因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再变动。因此，采用顺序存储结构表示数组是自然的事情了。P914.数组的算法：P93~955.有时为了节省存储空间，可以对在矩阵中有许多值相同的元素或是零的举证进行压缩存储。所谓压缩存储是指：为多个相同的元只分配一个存储空间；对零元不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。6.广义表：是线性表的推广。也有人称其为列表(lists，用复数形式表示以示与统称的表list的区别)。7.广义表的抽象数据类型：P1078.广义表的存储结构：P109----------------------------------------------------------------------------------------------------------------------第六章：数组和广义表1.树形结构是一类重要的非线性数据结构。其中以树和二叉树最为常用。P1182.树的抽象数据类型的定义：P1183.树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了书的固有特性。P1204.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的字树称为结点的度(Degree)。度为0的结点称为叶子(Leaf)或终端结点。度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树种的任一结点都称为该结点的子孙。P1205.结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某个结点在第l层，则其子树的根就在l+1层。其双亲在同一层的结点互为堂兄弟。其中结点的最大层次称为树的深度(Depth)或高度。如果将树种的结点的各子树看成从左至右是有次序的(即不能交换)，则称为该树为有序树，否则称为无序树。P1206.森林(Forest)是m（m=0）棵树不相交的书的集合。对树种每个结点而言，其子树的集合即为深林。由此，也可以森林和树相互递归的定义来描述书。P1217.二叉树(BinaryTree)是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树种不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。P1218.二叉树的抽象数据类型：P1219.二叉树的性质：性质一：在二叉树的第i层上至多只有2i+1个结点(i=1)。