数据结构复习资料.doc

数据结构（C+版）第一章 绪论（1） 数据结构+算法=程序（2） 数据的逻辑结构：线性表，树，图 等数据结构 。其核心是如何组织待处理数据以及数据之间关系。（3） 数据的存储结构：如何将线性表，树，图等数据结构存储到计算机的存储器中，其核心是如何有效的存储数据以及数据之间的逻辑关系。（4） 常用数据处理技术：包括查找技术，排序技术，索引技术等（5） 数据元素是数据的基本单位，构成数据元素的不可分割的最小单位称为数据项。（6） 数据结构分为以下四类：集合（属于同一集合），线性结构（一对一），树结构（一对多），图结构（多对多）（7） 数据的存储结构又称为物理结构。（8） 抽象数据类型ADT:包括数据元素间的逻辑关系和操作声明（9） 算法必须满足五个重要特性：输入，输出，有穷性，确定性，可行性（10） 算法的描述方法：自然语言，流程图，程序设计语言，伪代码（11）算法的时间复杂度：算法中基本语句的执行次数在渐进意义下的阶，通常用O记号表示。（12）算法的空间复杂度：算法的执行过程中，需要的辅助空间数量。 S(n)=O(f(n) n为问题规模第二章 线性表（1） 线性表简称表，是n(n=0)个具有相同数据元素的有限序列，线性表中数据元素的个数称为线性表的长度。（2） 元素a1无前驱，元素an无后继，其他元素有且仅有一个前驱和一个后继。（3） 线性表的存储结构称为顺序表。（4） 顺序表按位查找算法GetTemplateDataType SeqList :Get (int i) If (ilength) thow “查找位置非法“;Else return datai-1;(5) 顺序表按值查找算法 LocateTemplateInt SeqList:Locate(DataType x) For (i=0;ilength ;i+) If (datai=x) return i+1; Return 0;(6) 顺序表的存储结构单链表1 单链表的遍历算法 PrintListTemplateVoid LinkList:PrintList () p=first-next; while (p!=NULL) Coutdata; P=p-next; 2 单链表的按值查找算法 LocateTemplateInt LinkList:Locate(DataType x) P=frist -next ;count=1;While(p!=NULL) If(p-data =x) return count; P=p-next; Count+;return 0；3 单链表插入算法 InsertTemplateVoid LinkList :Insert(int i;DataType x) P=first;count=0; While (p!=NULL & countnext; Count+i; If（p=NULL）throw“位置;Else S=new Node;s-data=x;s-next=p-next;p-next=s;4 尾插法建立单链表 LinkListTemplateLinkList :LinkList (DataType a, int n) First =new Node; R=first ; For(i=0;idata=ai;r-next=s;r=s;r-next =NULL;第三章 栈和队列（1） 栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底。后进先出事栈的特性。（2） 栈的顺序存储结构顺序栈1 顺序栈入栈算法 PushTemplateVoid SeqStack :Push(DataType x) If (top =StackSize-1) thow “上溢“；data + top=x;2 顺序栈出栈算法 PopTemplate If (top=-1) thow “上溢“；x=datatop-;return x;(3) 栈的链接存储结构链栈栈的链接存储结构称为链栈。1链栈入栈算法 PushTemplate Void LinkStack:Push (DataType x) S=new Node ;s-data=x; S-next=top;top=s;(4) 队列的定义 ：队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。（5）队列的顺序存储结构：循环队列头尾相接的顺序存储结构称为循环队列。重要问题！ 队空和队满的判定： 队空条件 front=rear 队满条件 (rear+1)%QuenueSize=from1 循环队列的入队算法 EnQueueTemplateVoid CirQueue:EnQueue(DataType x) If (rear+1)%QueueSize=front) throw”上溢“； Rear=(rear+1)%QueueSize; Datarear=x;2 循环队列出队算法 DeQueueTemplateDataType CirQueue:DeQueue() If(rear=front) throw “下溢”; Front=(front+1)%QueueSize; Return data front;(6) 队列的链接存储结构称为 链队列。第四章 字符串和多维数组（1）字符串，简称串，是零个或者多个字符组成的有限序列。（2）给定两个字符串S=”s1,s2,.sn”和T=“t1,t2,.tn”,在主串S中寻找子串T的过程称为模式匹配，T称为模式。1朴素的模式匹配算法 BFInt BF(char S,char T ) I=0;j=0;While(Si!=0)&(Tj!=0) If(Si=Tj)i+;j+ Else i=i-j+1;j=0; If (Tj=0) return(i-j+1); Else return 0;第5章 树和二叉树(1) 在树中常将数据元素称为结点。树有且仅有一个称为根的结点。(2) 某结点所拥有的子树的个数称为该结点的度。(3) 树的遍历操作：1前序遍历：访问根结点，按照从左到右的顺序前序遍历根结点的每一棵子树。2后序遍历：按照从左到右的顺序后序遍历根结点的每一棵子树，访问根结点。3层序遍历：从树的第一层开始，自上而下逐层遍历，在同一层，按从左到右的顺序对结点逐个访问。(4) 树的存储结构：双亲表示法，孩子表示法，双亲孩子表示法，孩子兄弟表示法。(5) 二叉树：是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者有一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。斜树（每层只有一个结点）满二叉树（叶子只能出现在最下一层，只有度为0和度为2的结点）完全二叉树（叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左侧连续的位置，如果有度为1的结点，只可能有一个，且该结点只有左孩子。）(6) 二叉树的基本性质：1二叉树的第i层上最多有2的(i-1)次方个结点。（i=1）2在一棵深度为k的二叉树中，最多有2的k次方-1个结点，最少有k个结点。3在一棵二叉树中，如果叶子结点的个数为n0,度为2的结点个数为n2,则 n0=n2+14具有n个结点的完全二叉树的深度为log2 n+1.(7)二叉树的遍历操作：前序遍历，中序遍历（中序遍历根结点的左子树，访问根结点，中序遍历根结点的右子树）后序遍历，层序遍历由二叉树的后序序列和中序序列课唯一缺定一棵二叉树，但是如果只知道二叉树的前序序列和后序序列，则不能唯一确定一颗二叉树。（8）二叉树的存储结构及实现二叉树一般用二叉链表存储：另二叉树的每个结点对应一个链表结点，链表除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。1二叉树的前序遍历递归算法 PreOrderTemplateVoid BiTree:PreOrder(BiNode*bt) If (bt=NULL)return;Else Coutdata; PreOrder(bt-lchild); PreOrder(bt-rchild); 2二叉树中序遍历递归算法 InOrderTemplateVoid BiTree:IneOrder(BiNode*bt) If(bt=NULL)return; Else InOrder(bt-lchild); Coutdata; InOrder(bt-rchild); 3二叉树的后序遍历算法 PostOrderTemplateVoid BiTree : PostOrder(BiTree*bt) If (bt=NULL) return ; Else PostOrder(bt-lchild); PostOrder(bt-rchild); CoutData; (9)层序遍历 非递归队列：设置一个队列存放已访问结点，遍历从二叉树的根结点开始，首先将根指针入队，然后从队头取出一个元素并执行下述操作：访问该指针所指结点，若该指针所指结点的左。右孩子结点非空，则将其左孩子指针和右孩子指针入队。重复执行直到队列为空。（10）二叉树遍历的非递归算法：1前序遍历非递归算法 PreOrderTemplateVoid BiTree:PreOrder(BiTree*bt) Top=-1； While（bt!=NULL|top!=-1） While(bt!=NULL) Coutdata; S+top=bt; Bt=bt-lchild; If(top!=-1) Bt=stop-; Bt=bt-rchild; （11） 树，森林与二叉树的转换：树转换为二叉树： 1加线树中所有相邻兄弟结点之间加一条连线；2去线对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线。3层次调整以根结点为轴心，将树顺时针转动一定得角度，使之层次分明树的前序遍历=二叉树的前序遍历树的后序遍历=二叉树的中序遍历（12）森林的遍历：前序（根）遍历和后序（根）遍历前序遍历森林即为前序遍历森林里的每一棵树；后序遍历森林即为后序遍历森林里的每一棵树。（13）哈夫曼树：也称最优二叉树，给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，将其中带权路径长度最小得二叉树称为哈夫曼树。（14）前缀编码：如果一组编码中任一编码都不是其他任何一个编码的前缀，我们称这组编码为前缀编码。前缀编码保证了编码被解码时不会有多种可能。第六章 图（1）简单图：若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。（2）顶点的度，入度，出度：在无向图中，顶点V的度是指依附于该顶点的边的个数，记为TD（V）。入度是指以该顶点为弧头的弧的个数，记为ID（V）。出度是指以该顶点为弧尾的弧的个数，记为OD（V）。（3）图的遍历操作：深度优先遍历，广度优先遍历。深度优先遍历: 访问顶点V；从V的未被访问的邻接点中选取一个顶点W，从W出发进行深度优先遍历；重复上述两步，直到图中所有和V有路径想通的顶点都被访问到。广度优先遍历：访问顶点V;依次访问V的各个未被访问的邻接点V1,V2,Vk;分别从V1,V2,Vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直到图中所有和V有路径想通的顶点都被访问到。（4）邻接矩阵：图的邻接矩阵存储也称数组表示法，其方法是用一个一唯数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间的邻接关系的二维数组称为邻接矩阵。（5）算法在邻接矩阵存储结构下的实现：1深度优先遍历算法 DFSTraverseTemplate Void MGraph:DFSTraverse(int v) Coutvertexv;visitedv=1; For (j=0;jvertexNum;j+) If (arcvj=1 & visitedj=0)DFSTraverse(j);2 广度优先遍历算法 BFSTraverseTemplate Void MGraph:BFSTraverse(int v) Front =rear=-1; Coutvertexv;visitedv=1; Q+rear=v; While (front!=rear) V=Q+front; For (j=0;jvertexNum;j+) If (arc vj=1 & visitedj=0) Coutvertexj;visitedj=1;Q+rear=j; (6)最小生成树：设G=（V，E）是一个无向联通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中代价最小的生成树称为最小生成树。第七章 查找技术（1）静态查找，动态查找：不涉入插入和删除操作的查找称为静态查找。涉及插入和删除操作的查找称为动态查找。（2）查找结构：面向查找操作的数据结构称为查找结构。线性表：适用于静态查找，主要采用顺序查找技术，折半查找技术。树表：适用于动态查找，主要采用二叉排序树的查找技术。散列表：静态查找和动态查找均适用，主要采用散列技术。（3） 顺序表的顺序查找算法 SeqSearch1Int SeqSearch1(int r,int n,int k) R0=k; I=n;While (ri!=k) i-;retutn i;(4)折半查找：要求线性表中的记录必须按关键码有序，并且必须采用顺序存储。一般只能应用于静态查找。1折半查找非递归算法 BinSearch1Int BinSearch1(int r ,int n, int k) low=1;high=n; while(low=high) mid=(low +high)/2; if (krmid)low=mid+1; else return mid; return 0;2折半查找递归算法 BinSearch2Int BinSearch2(int r ,int low ,int high ,int k) if(lowhigh) return 0; else mid=(low+high) return 0; if (krmid) return BinSearch2(r,mid+1,high,k) ; else return mid; （5）二叉排序树：又称二叉查找树，它或者是一棵空的二叉树，或者是具有以下性质的二叉树：若它的左子树不空，则左子树上所有的结点值均小于根结点的值；若它的右子树不空，则右子树上所有的结点值均大于根结点的值；它的左右子树也都是二叉排序树。（6）二叉排序树查找算法 SesrchBSTB