计算机三级数据库知识点

数据结构1.基本概念数据是信息的载体，是对客观事物的符号表示，是计算机程序加工的“原料”。数据不仅包括整数、实数、字符串，还包括图像和声音等。数据元素是组成数据的基本单位，在计算机程序里往往作为一个整体进行考虑和处理，数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可以成为字段、域、属性）组成。数据项是具有独立含义的最小标识单位，是数据元素的基本组成部分，不可再分的数据单元。举例：一个学生的基本信息数据作为数据元素，而描述学生信息的学号、姓名、性别、班级等为数据项。数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括数据的逻辑结构、数据的存储结构和数据的运算（操作集合），这三方面是一个整体，孤立地去理解一个方面，而不注意它们之间的的联系是不可取的。逻辑结构是数据间的逻辑关系。基本结构有集合、线性结构、树形结构、图状结构（网状结构）。包括两大类：线性结构（线性表，队列，栈，字符串，数组，广义表）；非线性结构（树和图）。存储结构可以用顺序、链接、索引和散列存储方法得到。数据类型是指一个值的集合以及在这些值上定义的一组操作的总称。按“值”是否可分解，可将数据类型划分为两类：原子类型（不可再分）和结构类型（可以再次分解）。时间代价（时间效率）就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。指标为时间复杂度。空间代价（空间效率）就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。度量为空间复杂度。2.线性表：最简单、最基础的数据结构，数据元素之间是一对一的关系均匀性：一表元素属于同一集合，相同的数据类型；有序性：相邻元素存在序偶关系；有限性：元素个数有限，为表长。线性表是由n(n>=0)个数据元素（结点）a1,a2,…an组成的有限序列。n为数据元素个数，即表的长度。元素的线性逻辑关系：有且只有一个开始结点（表头结点a1）；有且只有一个终端结点（表尾结点an）。每个结点只有一个前驱结点（除表头）和一个后继结点（除表尾）。基本存储结构：顺序存储结构和链式存储结构。顺序表：将数据元素按其逻辑顺序依次存放在内存中一组地址连续的存储单元中，依次相邻。特点是：在线性表中逻辑关系相邻的数据元素在计算机内存物理位置也相邻。插入：在具有n个元素的线性表第i个元素之前插入一个新元素，必须把从n到第i个之间的元素依次往后移动一个位置，空出第i个位置放新元素，表长变为n+1。删除：从具有n个元素的线性表中删除第i个元素，就必须把从第i+1个到第n个之间的元素依次往前移动一个位置，以覆盖前一个位置上的内容，表长变为n-1。**顺序表插入和删除操作的时间复杂度均为O(n)。优点是表中元素可通过下标进行直接访问，查询效率高（存储密度为100%）；缺点是插入、删除操作不方便，需要移动元素。为静态分布必须事先估计表长，过大或者过小可能造成存储空间浪费或出现溢出。适合一旦建立长度将很少改变的应用。链式存储结构有线性链表、循环链表、双向链表。可动态存储也可静态存储。线性链表：每个元素的存储单位称为结点，至少包括两个域：存储元素信息的数据域和存储其后继元素存储位置的指针域。表中元素之间的逻辑关系通过结点指针体现，存储位置不要求相邻。存储密度小于1，无需事先估计存储空间。线性链表是动态地进行存储分配的一种结构，可以根据需要开辟内存单元。包含了申请、使用、释放内存空间三个步骤，实现存储空间的动态分配。插入算法的关键是要找到插入的位置，并且标记所插入位置的前驱结点，很明显这样比较次数为i-1次；其次是修改指针的次序：先执行new→next=p→next后，执行p→next=new。删除算法步骤：根据给定的参数从头结点出发找到要删除的结点的前驱～修改指针从链表中删除指定结点，即p→next=p→next→next～释放被删除结点的存储空间。循环链表与单向链表一样，也是链式存储结构，不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。带头结点的单循环链表中，判断空链表的条件是head==head->next.仅设尾指针的单循环链表中，判断空链表的条件为rear==rear->next.双向链表既可以用来表示线性结构，也可以用来表示非线性结构，其每个结点包括三个域：一个数据域和两个指针域，一个指向它的前趋，另一个指向它的后继。在双向链表中，若d是指向表中任一结点的指针，则有llink(rlink(d))=rlink(llink(d))=d.表示当前结点的后继结点的前驱是自身，当前结点前驱结点的后继结点也是自身。3.栈和队列（两种操作受限的特殊类型的线性表）栈是一种插入、删除只能在表的一端进行的线性表。插入元素称为入栈，删除元素称为出栈。在栈中，允许插入和删除的一端叫栈顶，不允许插入和删除的一端叫栈底，位置固定。满足后进先出的原则。特殊的线性表，适用线性存储结构，有顺序存储和链式存储。队列在两个方向都有限制，插入只能在表的一端进行（只入不出），而删除只能在表的另一端进行（只出不进），允许插入的一端称队尾（rear），允许删除的一端称队头（front），队列的操作原则是先进先出。当队伍中没有元素时，称之为空队列，队列的插入操作称之为入队，删除操作称之为出队。4.数组数组是由类型相同的数据元素构成的有序集合。行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。计算二维数组的地址：Loc(i,j)=Loc(0,0)+(行标*i+j)*L数组特征：数组中的元素在内存中是连续存放的～同一数组的所有元素具有相同的数据类型。一般程序设计中，数组必须先定义后使用，有数组的名称，数组的维数和各维类型，数组元素的数据类型。数组是一种静态结构，一旦定义之后其元素的个数和数据类型就确定了，所需的存储空间也就确定了。主要操作有：取特定位置的元素值及对特定位置的元素进行赋值，不需要线性表中的插入和删除操作。数组的存储有两种形式：一是按行存储方式，也叫行优先存储；另一种是列存储方式，也叫列优先存储。大多数采用行存储。串（字符串）是一种特殊的线性表，它的字符序列由零个或多个字符组成。a=’’称为空串，长度为0.求子串序列号：用index(a,sb)表示子串sb在串a中的序号。稀疏矩阵可用一个三元组（i,j,value）表示，将这些三元组按某种次序排成一个线性表。5.树形结构（一种非常重要的非线性结构，元素之间有分支关系并且有层次关系）树是n个结点的有限集合，是一类非线性结构。树的表现形式还有嵌套集合的形式、广义表的形式和凹入表示法的形式。树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度。树的定义具有递归性，即一棵树是由根和若干棵子树构成的，而子树又可以由更小的子树构成。只能有一个根结点。特点：层次关系，分支关系，树中无环路存在。根结点没有直接前驱，除根结点之外其余结点均有一个且只有一个直接前驱。结点可以有零个或者多个后继结点。度为0的结点称为叶子或终端结点，度不为0的结点称为非终端结点或分支结点。树内各结点的度的最大值称为树的度。结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。树中结点的最大层次称为树的深度，从一结点到叶结点的最长路径称为该结点的高度。森林是m棵互不相交的树的集合。（对树中每个结点而言，其子树的集合即为森林）二叉树又是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且其子树有左右子树之分，次序不能随意颠倒。与树的主要区别就是要区分左子树还是右子树。二叉树的性质：a.在二叉树的第i层至多有2^(i-1)个结点(i>=1).b.深度为k的二叉树至多有2^k-1个结点(k>=1).c.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1.d.具有n个结点的完全二叉树的深度为【log2n】+1f.。。。满二叉树：一棵深度为k且有2^k-1个结点的二叉树。完全二叉树：深度为k,有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时。二叉树存储结构：顺序存储结构和链式存储结构。顺序存储结点的逻辑关系通过结点的编号准确的表示出来，适用于完全二叉树，即方便访问又节省存储空间。对于一般二叉树需要增设虚结点，转化为完全二叉树存储，虚结点不存在却占用空间造浪费。而链式存储表中结点结构包括三个部分：数据域，左指针域，右指针域。两个指针分别存储左右孩子的结点的存储地址。不存在时相应指针域的值为空。二叉树上任一结点的左子树深度减去右子树的差值称为该结点的平衡因子，任意结点左右子树的深度之差的绝对值<=1,称为平衡二叉树。二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；遍历二叉树：就是按照指定规则或者某条搜索路径访问树中每一个结点，且每个结点均被并且仅被访问一次。要求不破坏原来的数据结构。就是将非线性的二叉树中结点排列在一个线性序列上的过程。均为先左后右的规律可有：先（根）序遍历、中（根）序遍历和后（根）序遍历哈夫曼树：执行路径最短（算法效率最高）的二叉树，又称最优二叉树。为带权路径长度最短。～在叶子结点数目相同的二叉树中，完全二叉树或者满二叉树不一定是最优二叉树，最优二叉树也不一定是深度最小的二叉树。基本思想是让权值最大的叶子离根最近。6.排序排列：是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和尾部排序。内部排序是指在排序的过程中，记录全部存放在计算机的内存里，并且在内存里调整记录之间的相对位置，没有进行、外存数据交换。外存排序为大文件排序，即待排序记录存储在外存储器上。待排序记录无法一次性装入内存，需多次数据交换。当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序结果不一定唯一。当待排序记录中存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方式是稳定的，否则为不稳定的。其中冒泡、插入、基数、归并属于稳定排序，选择、快速、希尔、堆属于不稳定排序。插入排序：分直接插入排序和希尔排序。直接插入排序：顺序的将待排序的纪录按照关键字的大小插入到已排序的纪录子序列的恰当位置。共需要n-1趟插入过程就可以将初始的n个记录排序成按照关键字大小排列的有序序列。操作：前两个比较排序，第三个按照大小直接插入前两个排好的序列中形成三个的序列，第四个再根据大小直接插入前三个排好的序列中……最后直到最后一个记录排好，完成。算法的事件复杂度为O（n^2）,空间复杂度来看，只需要一个记录大小的辅助空间。（平稳）希尔排序：又称缩小增量排序，先将整个待排序的纪录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录作一次直接插入排序。时间复杂度介于O（nlogn）和O（n^2）之间，（不平稳）冒泡排序：将相邻记录的关键字进行比较，若前面记录的关键字大于（或小于）后边记录的关键字，则将他们交换位置。有n个记录，需要n-1趟，每趟排序从最后一个记录开始。操作：找出最大（或最小的）为初始关键字，再每趟一个依次按顺序排列，未排列的数据不改变原来顺序直接写在后边。时间复杂度为O（n^2），记录的移动交换次数较多，时间性能不如插入排序。（稳定）快速排序：目前已知的常用排序算法中最快的排序方法。通过不断的比较关键字大小，以某一个记录为枢轴（支点），将待排序序列分成两个部分。其中一个部分满足所有关键字都大于或者等于支点记录的关键字，另一部分都小于等于。完成一次划分。对各部分不断划分，直到整个序列按关键字排序为止。平均时间复杂度为O（nlogn）。（不稳定）选择排序：每一趟排序在待排序的序列中选出关键字最小（最大）的记录，再放在子序列的恰当位置。分简单选择排序和堆排序。简单选择排序：先从全部n个待排序的序列中选出关键字最小（最大）的记录并将它和序列中的第一个记录进行交换位置；然后从n-1个不包括第一个位置上的记录中选择关键字最小（最大）的记录并将它和序列中的第二个记录进行交换位置；第i趟从n-i+1个不包括第一个位置上的记录中选择关键字最小（最大）的记录并将它和序列中的第i个记录进行交换位置。如此反复经过n-1趟选择得有序序列。时间复杂度为O（n^2）。（不稳定）堆排序：n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤n），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的