16数据机构知识点复习整理

2016秋季学期《数据结构》期末嵬习2016-12-27.数据结构研究的内容是什么？数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。它的主要研究范围如下：数据元素之间固有的逻辑关系一一数据逻辑结构；数据元素及关系在计算机内的表示一一数据存储结构；数数据结构的操作一一算法。.算法性能的度量：时间和空间复杂度，大O表示法的含义。常见的时间复杂度(1)常数阶时间复杂度为常数，不随问题规模n的大小而改变。记T(n)=O(1)o(2)线性阶时间复杂度与问题规模n成线性关系。记T(n)=O(n>如一次for()循环里面做一次简单的加法运算。(3)平方阶和立方阶时间复杂与问题规模n成平方或立方关系。记T(n)=O(n2)或O(n3)(4)对数阶时间复杂度与问题规模n成对数关系，通常以2为底。记T(n尸O(lC2gn)如：voidprint(intn)(inti;for(i=1;i<n;i*=2)printf(%d\t”,i);)对输出语句执行了f(n)次，有2f⑺En,即f(n)<log2n(5)其他时间复杂度还有指数阶O(2n),阶乘阶O(n!)等时间复杂度之间的关系：O(1)二O(log2n)；O(n)；O(nlog2n)；O(n2)；O(n3)；O(2n)；O(n!)：二O(nn).线性表的顺序和链式存储结构各自的特点；1)顺序优缺点a)优点比较简单。可以实现随机存放，存取速度快。每个结点只需存储元素本身信息，不需额外空间。b）缺点需要占用一片连续的存储空间，并且需要事先估计存储空间的大小。如果空间分配得太大，有可能用不完从而造成浪费。如果空间分配得小，又有可能不够用。做插入和删除操作时，需要移动大量的元素，效率较低。2）链式优缺点a）优点不需要占用连续的存储空间，其存储空间是动态分配的，在使用链表前不用事先估计存储空间的大小。在插入和删除操作时，不需要移动大量元素。虽然链表的插入和删除操作的时间复杂度与顺序表的插入和删除操作一样，都是O（n）o但一个是比较操作，一个是移动操作。显然二者所花费的时间不可同日而语。b）缺点操作算法较复杂不能随机存放。一般情况下，查找结点要从头指针开始，遍历链表。需要额外的空间来表示元素间的关系，空间代价较高3）结论a）顺序存储结构比较适合于线性长度不经常发生变化，不经常进行插入和删除操作，经常进行存取和查询操作。b）链式存储结构比较适合于线性表长度不可预知，需要频繁进行插入和删除操作。内存示意图;初始化；1)顺序表//初始化线性表，表的初始最大空间数为sizeboolInitList(List&L,intsize){L.elem=(ElemType*)malloc(sizeof(ElemType)*size);L.maxSize=size;L.length=0;returntrue;}2)链式表//初始化空表---创建表头boolInitList(List&L){L.head=(LNode*)malloc(sizeof(LNode));L.head->next=NULL;L.len=0;returntrue;}//用数组初始化链表boolInitList(List&L,ElemTypedata[],intn){for(inti=n-1;i>=0;i--){LNode*p=(LNode*)malloc(sizeof(LNode));p->elem=data[i];p->next=L.head->next;L.head->next=p;}L.len=n;returntrue;}插入、删除；1)顺序表//定位插入元素：1<=i<=length+1boolListInsert(List&L,inti,ElemTypee){if(i<1||i>L.length+1)returnfalse;if(L.length>=L.maxSize){ElemType*newbase=(ElemType*)realloc(L.elem,(L.maxSize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)returnfalse;L.elem=newbase;L.maxSize+=LISTINCREMENT;)ElemType*q=&(L.elem[i-1]);for(ElemType*p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returntrue;)//定位删除元素：1<=i<=lengthboolListDelete(List&L,inti,ElemType&e);boolListDelete(List&L,inti,ElemType&e){if((i<1)||(i>L.length))returnfalse;ElemType*p=&(L.elem[i-1]);e=*p;ElemType*q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returntrue;)2)链式表//定位插入元素：1<=i<=length+1boolListInsert(List&L,inti,ElemTypee){printf("\n");LNode*p=L.head;if(i<=0&&i>L.len)returnfalse;for(intj=1;j<i;j++){p=p->next;)LNode*q=(LNode*)malloc(sizeof(LNode));q->next=p->next;q->elem=e;p->next=q;returntrue;)//定位删除元素：1<=i<=lengthboolListDelete(List&L,inti,ElemType&e){printf("\n");LNode*p=L.head;LNode*q;if(i<=0&&i>L.len)returnfalse;for(intj=1;j<i;j++){p=p->next;}q=p->next;e=q->elem;p->next=q->next;free(q);returntrue;}时间分析；1）顺序表插入运算最坏情况下时间复杂度为O（n）删除运算最坏情况下时间复杂度为O（n）查找指定元素在顺序表中的位置时间复杂对为O（n）2）链式表插入运算最坏情况下时间复杂度为O（n）删除运算最坏情况下时间复杂度为O（n）4.栈和队列特点；栈的特点是“后进先出”，即后入栈的元素先出栈；队列的特点“先进先出”，即先入队的元素先出队。基本操作（名称）；1）初始化栈2）判断栈是否为空3）入栈4）出栈5）取栈顶元素适用的问题；链式栈；栈的链式存储表示称为链式栈，简称链栈。链式栈中每个元素用一个链结点表示，每个结点由一个数据域和一个指针域组成。同时附设一个指针top,用来指示栈顶元素所在结点的存储位置循环队列（顺序）：队列是限制在一端进行插入，另一端进行删除的线性表。顺序队列：用顺序存储方式实现的队列称为顺序队列。为了解决“假溢出”问题，可以把队列的首尾相连，形成一个环，既允许队列直接从数组中下标最大位置前进到下标最小位置，这就是循环队列。空满的判别：无论队空还是队满，者B存在“front==rear”，即队空和队满的条件相同。区分对空和队满有3种方法：设置一个标志位标志位tag,用于标识前一个操作是入队操作，还是出队操作。初始把标志位tag置为0,执行入队操作后，把标志位置为1;执行出队操作后，把标志位置为00队空：front==rear并且tag==0。队满：front==rear并且tag==1。设置一个计数器当计数器count==0时，表示队空。当计数器count>0并且front==rear时，表示队满。少用一个存储空间队尾指针rear所指的存储空间始终保持为空。当front==rear时，表示队空。当(rear+1)%QUEUESIZE==front时，表示队满。插入删除时mod运算入队：intEnQueue(SqQueue*QDataTypee)(if((Q->rear+1)%QUEUESIZE==Q->front)(printf(“队列已满，不能完成入队操作！\n");return0;)Q->items[Q->rear]=e;Q->rear=(Q->rear+1)%QUEUESIZE;return1;)出队：intDeQueue(SqQueue*QDataType*e)(if(Q->front==Q->rear)(printf(“队列已满，不能完成入队操作！\n");return0;)*e=Q->items[Q->front];Q->front=(Q->front+1)%QUEUESIZE;return1;

5.字符串匹配的KMP算法next[j]函数：模式用T="t0ti...tk...tj-ktj*+i...tj-itj"中”toti...tkJ称为模式前缀“tjjtj』如..tj」”称为模式后缀。-1,j=0next[j]=mmax{k|0<k<j且"t0tl...tkJ=''tjJitjj^^...tjJ''},当前集合非空时nextval[j]函数「-1nextval[j]函数「-1,nex(j]由[」]=next[k]0设S为主审,,j=0,tj=tk,tj=tk，其他式用，i为指向主审当前比较字符的指针，j为指向模式用当前字符的指针，且初始时i=j=0。在匹配过程中，若si=tj,则i和j增一，继续比较；若si#sj(匹配失败)，则i不变，j向右滑动到next[j]值后进行下一趟比配；若j滑动0,则i增一，进入下一趟匹配。重复以上过程，直至i大于等于主用S的长度，或j大于等于模式用T的长度为止。6.二叉树与树：二叉树、完全二叉树的基本性质：性质1：非空二叉树的第i(i±1)层上最多有27个结点性质2:深度为h的非空二叉树最多有2h-1个结点性质3:在任意非空二叉树中，若度为0(叶子结点)的结点数为no,度为2的结点数位n2，则.=n2+1成立。性质4:具有n(n>0)个结点的完全二叉树的深度h=[log2n_+1性质5:对于具有n个结点的完全二叉树，如果按照从第1层、第2层、，第1log2n1+1层的次序，且每层从左到右的次序对结点进行编号，则编号为i的结点有以下性质。.若i>1,则编号为i的结点的双亲结点编号为|i/2;当i=1时，编号为i的结点为二叉树的跟结点，没有双亲结点2,若2iwn,则编号为i的结点的左孩子结点的编号为2i;若2i〉n,则编号为i的结点没有左孩子结点。3,若2i十1wn,则编号为i的结点的右孩子结点的编号为2i+1;若2i+1〉n,则编号为i的结点没有右孩子结点。二叉链表的遍历算法（先序、中序、后序、层次）【理解递归结构】先序遍历：若二叉树非空，则按以下次序进行遍历（RACFDBEG.访问根结点；.先序遍历根结点的左子树；.先序遍历根结点的右子树；中序遍历，若二叉树非空，则按以下次序进行遍历（CFADRGEB）.中序遍历根结点的左子树.访问跟结点.中序遍历根结点的右子树后序遍历，若二叉树非空，则按以下次序进行遍历（FCDAGEBR.后序遍历根结点的左子树.后序遍历根结点的右子树.访问跟结点Huffman树的应用Huffman编码哈弗曼树是最优二叉树，是带权路径长度最短的树，它在压缩编码和数据通信领域应用非常广泛。二叉树、树与森林的转换堆结构一一完全二叉树（适合顺序存储）【插入删除时的sift调整】.图邻接矩阵和邻接表的表示法图的遍历：DFSBFS（层次）【理解老鼠迷宫问题实为图的DFS和BR3最小生成树：KruskalPrim最短路径：Dijkstra、Floyd拓扑排序和关键路径【事件的最早、最晚发生时间；活动的最早和最晚开始时间】直观理解：BFSPrim