算法与数据结构知识点总结.docx

算法与数据结构知识点总结算法与数据结构知识点总结4学习目标1.熟练掌握基本的数据结构2.理解相关操作的算法实现3.掌握算法的复杂度分析方法4.领会从数据结构的设计和实现角度优化解决实际问题的思想4相关术语&基础知识1.数据、数据元素数据：对客观事物的符号表示，所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：组成数据的、具有意义的基本单位，计算机中通常作为整体处理。2.数据项组成数据的不可分割的最小单位3.数据对象性质相同的数据元素的集合，是数据的子集4.逻辑结构数据对象中数据元素之间的逻辑关系；是从操作对象抽象出来的数学模型5.物理结构（存储结构）数据元素逻辑关系在计算机中的表示（映像）；包括数据元素的表示和逻辑关系的表示；关系到数据操作的实现6.数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。7.抽象数据类型（ADT）是指一个数据模型以及定义在该模型上的一组操作。三要素：数据元素、逻辑关系、操作8.算法的设计原则正确性、可读性、健壮性、高效率与低存储量9.算法效率的度量10.常见结构的时间复杂度（1）顺序结构 O(1)（2）分支结构 O(1)（3）循环结构的时间复杂度 = 循环体内语句的频度(重复执行次数)11.时间复杂度的计算时间复杂度的简化求解步骤step 1. 定位最深层循环step 2. 由内向外逐层计算循环体的执行频度step 3. 只保留最高阶项step 4. 去掉最高阶项系数得到的结果即为时间复杂度的大O阶。12.时间复杂度的大小关系13.影响空间复杂度的因素（1）程序本身所占空间（2）输入数据所占空间（3）辅助变量所占空间若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。4对知识掌握的四种程度1.了解：选择题2.理解：知道原理，题里可能有拐弯的地方3.掌握：算法语句填空4.熟练掌握：整.个.算.法.PS：以下，“要求”会展开详细内容；若无必要，“考点”不展开详细内容。一、线性表=考点：1.线性表的逻辑结构和各种存储表示方法2.定义在逻辑结构上的各种基本运算（知道名字即可）InitList（*L）操作结果：初始化一个空的线性表L。DestroyList（*L）初始条件：线性表L 已经存在。操作结果：销毁线性表L。ClearList（*L）初始条件：线性表L 已经存在。操作结果：将L 清空为空表。ListEmpty（L）初始条件：线性表L 已经存在。操作结果：若L 为空返回true，否则返回false。ListLength（L）初始条件：线性表L 已经存在。操作结果：返回线性表L 的元素个数。GetElem（L，i，*e）初始条件：线性表L 已经存在，i1, ListLength ( L )。操作结果：将L 中第i 个位置的元素返回给e。LocateElem（L，e，compare ( )）初始条件：线性表L 已经存在。操作结果：在L 中查找与给定值e 满足关系compare ( ) 的元素，无参数compare()默认为相等关系，找到后返回其第一个元素的位序，查找失败返回0。ListInsert（L，i，e）初始条件：线性表L 已经存在，i1, ListLength ( L )+1。操作结果：在L 中第i 个位置插入新元素e，L 的长度加1。ListDelete（L，i，*e）初始条件：线性表L 已经存在且非空，i1, ListLength ( L )。操作结果：删除L 中第i 个位置元素，并用e 返回其值，L 的长度减1。3.在各种存储结构上如何实现这些基本运算4.各种基本运算的时间复杂性=要求：1.理解两种存储结构各自的特点、优缺点、适用范围2.熟练掌握顺序表和单链表上建表、插入、删除、查找操作的算法实现及相关的复杂度分析顺序表建表Status ListCreat(SqList * L) /*从屏幕逐位读入数据生成顺序表*/ int n , i;printf(请输入顺序表L 的数据个数：n) ;scanf(%d, &n) ;if (n MAXSIZE)printf(n 数据个数过长，请不要超过%d！n,MAXSIZE);return ERROR;else if(n0)printf(n输入不合法n);return ERROR;for(i=0 ; i n ; i+) printf(data%d = , i) ;scanf(%d,&(*L).datai);(*L).length=n;printf(n) ;return OK;时间复杂度：O(n)插入/* 初始条件：线性表L 已经存在，i1, ListLength ( L ) */* 操作结果：将L 中第i 个位置插入新元素e，L 长度加1 */int ListInsert SqList L, int i , ElemType eint k;if ( L.length = MAXSIZE) /*顺序表已满*/return ERROR;if ( i L.length + 1 ) /* i 不合法 */return ERROR；if ( i =i-1; k- )L.data k+1 = L.data k; /* 从后向前逐位后移 */L.data i-1 = e; /* 插入新元素e */L.length+;return OK;时间复杂度：最好O(1) 最坏O(n) 平均O(n) （依赖于插入位置i、表长n）删除/* 初始条件：线性表L 已经存在，i1, ListLength ( L ) */* 操作结果：将L 中第i 个位置元素删除，并用e 返回该元素的值，L长度减1 */int ListDelete SqList L, int i , ElemType *eint k;if ( L.length = 0 ) /*顺序表为空*/return ERROR;if ( i L.length ) /* i 不合法 */return ERROR；*e = L.data i-1; /* 用e 返回删除元素的值 /if ( i L.length ) /* 删除位置不是表尾 */for ( k =i; k length; k+ )L.data k-1 = L.data k; /*删除位置后继元素逐一前移*/L.length-;return OK;时间复杂度：最好O(1) 最坏O(n) 平均O(n) （依赖于插入位置i、表长n）查找（按位获取操作）# define OK 1# define ERROR 0/* 初始条件：线性表L 已经存在，i1, ListLength ( L ) */* 操作结果：将L 中第i 个位置的元素返回给e */int GetElem SqList L, int i , ElemType *eif ( L.length = 0 | i L.length)return ERROR;*e = L.data i-1;return OK;时间复杂度：O(1)单链表建表Node* ListCreatTail() /*尾插法建立带头结点的单链表，链表长度为n，链表元素从屏幕读取,返回头结点位置*/ LinkList p,r,L;int n,i;ElemType d;L = (LinkList)new Node; printf(n请输入链表L 的数据个数：n) ;scanf(%d, &n) ;L-data = n;L-next = Null;r = L;for(i=1 ; i data = d;p-next = Null;r-next = p;r = p;printf(nNode%d=%dn,i,p-data);printf(n) ;return L;时间复杂度：O(n)插入链表的插入：一定，二建，三后，四前Status ListInsert LinkList L, int i , ElemType eNode * p, *q;p = GetElem ( L, i-1 );if ( p = Null) /*链表为空*/return ERROR;q = (Node*) malloc (sizeof (Node);q-data = e;qnext = pnext;pnext = q;return OK;时间复杂度： O (1)删除链表的删除：一定，二连，三放Status ListDelete LinkList L, int i , ElemType *eNode * p, *q;p = GetElem ( L, i-1 );if ( p = Null | p - next =Null ) /*链表为空*/return ERROR;q = p - next;*e = q-data;pnext = q-next;free (q);return OK;时间复杂度： O (1)查找a.按位获取/链表不是随机存取结构Node * GetElem LinkList L, int i int k; /* k 为计数器 */LinkList p; /* 指针p 指向当前结点 */p = L; /* 指针p 指向头结点 */k = 1;while ( p & k next; /* p 指向下一个结点 */+k; /* 计数器加1 */if ( k=i ) /* 结点i 存在 */return p;elsereturn Null;时间复杂度：最好O (1) 最坏O(n)b.按值获取/* 初始条件：线性表L 已经存在*/* 操作结果：定位L 中与给定值相等的元素，返回其位置*/Node * LocateElem LinkList L, ElemType e LinkList p; /* 指针p 指向当前结点 */p = L; /* 指针p 指向头结点 */while ( p & p - data != e )p = p - next; /* p 指向下一个结点 */if ( !p) /* 结点i 不存在 */return Null;elsereturn p;时间复杂度：最好O (1) 最坏O(n)3.了解双向链表和循环链表的定义和特点及插入、删除操作的实现（见书和PPT）二、栈和队列=考点：1.栈和队列的逻辑结构和两种存储表示方法2.定义在逻辑结构上的各种基本运算InitStack（&S）操作结果：初始化一个空的栈S。 DestroyStack（&S） 初始条件：栈S已经存在。 操作结果：销毁栈S。 ClearStack（&S） 初始条件：栈S已经存在。 操作结果：将栈S清空。 StackEmpty（S） 初始条件：栈S已经存在。 操作结果：若栈S为空返回true，否则返回false。 StackLength（S） 初始条件：栈S已经存在。 操作结果：返回栈S的元素个数。 GetTop（S，&e） 初始条件：栈S已经存在且非空。 操作结果：将S的栈顶元素返回给e。 Push（&S，e） 初始条件：栈S已经存在且非空。 操作结果：新元素e入栈。 Pop（&S，&e） 初始条件：栈S已经存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。3.在各种存储结构上如何实现这些基本运算4.各种基本运算的时间复杂性5.栈的常用应用=要求：1.理解栈和队列的异同点、栈和队列与一般线性表的不同2.了解顺序栈的溢出和顺序队列的假溢问题顺序栈的溢出上溢（overflow）：栈满时再压入数据下溢（underflow）：栈空时再弹出数据栈满：S.top = MAXSIZE 1空栈：S.top = 13.熟练掌握顺序栈（两栈共享空间）、链栈、循环队列、链队列上的队列初始化、元素插入、删除的算法实现及相关的复杂度分析顺序栈（两栈共享空间）初始化Status InitDuStack(Sqstack &S)S.top1=-1;S.top2=MAXSIZE;return OK;时间复杂度O(1)顺序栈（两栈共享空间）元素插入/* 新元素e 入栈 */Status Push SqDuStack S , SElemType e, int StackNumif ( S.top1 + 1 = S.top2 ) /* 栈满 */return ERROR;if ( StackNum = 1) /* 新元素压入栈1 */S.top1 +;S.dataS.top1 = e; /* 新元素入栈 */return OK;else if (StackNum = 2)S.top2 -;S.dataS.top2 = e; /* 新元素入栈 */return OK;else return ERROR;时间复杂度O(1)顺序栈（两栈共享空间）元素删除来自网络/若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERRORStatus Pop(SqDuStack *S , ElemType *e , int stackNumber) if(stackNumber = 1) if(S-top1 = 1) return ERROR; /说明栈1已经是空栈，溢出 *e = S-datas-top1-; /将栈1的栈顶元素出栈 else if(stackNumber = 2) if(S-top2 = MAXSIZE) return ERROR; /说明栈2已经是空栈，溢出 *e = S-dataS-top2+; /将栈2的栈顶元素出栈 return OK;时间复杂度O(1)链栈初始化来自网络void InitLinkStack (linkStack &S)S=new SNode;S-next=NULL;时间复杂度O(1)链栈元素插入/* 新元素e 入栈 */Status Push ( LinkStack *S , SElemType e )SNode *p = ( SNode * ) malloc ( sizeof (SNode) ); /* 动态申请结点*/p-data = e; /* 结点赋值 */p-next = S-top; /* 新结点插到表头 */S-top = p; /* 栈顶指针改为新结点*/S-length +;return OK;时间复杂度O(1)链栈元素删除/* 栈顶元素出栈 */Status Pop ( LinkStack *S , SElemType *e )StackNode *p;if (StackEmpty(*S)return ERROR;p = S-top; /* p 指向出栈结点*/*e = p-data; /* 返回栈顶元素 */S-top = p-next; /* 栈顶指针下移*/free(p); /* 释放结点空间*/S-length -;return OK;（7）循环队列的初始化/* 队列初始化 */Status IntiQueue ( SqQueue *Q )Q-front = 0;Q-rear = 0;return OK;/* 求队列长度 */int QueueLength (SqQueue Q )return (Q.rear Q.front + MAXSIZE) % MAXSIZE;时间复杂度O（1）（8）循环队列元素插入/* 新元素e 入队列 */Status EnQueue (SqQueue *Q , QElemType e)if (Q-rear+1)% MAXSIZE = Q-front)return ERROR; /* 队满 */Q-dataQ-rear = e; /* 新元素入队 */Q-rear = (Q-rear +1) % MAXSIZE; /* rear 指针后移，若到最后则转到数组头部 */return OK;时间复杂度O（1）（9）循环队列元素删除由书P65修改/队头元素出队StatusDeQueue (SqQueue *Q, QElemType e)if(front=rear) return ERROR; /* 队空 */e=Q-dataQ-front;Q-front = (Q-front +1) % MAXSIZE; /* front 指针后移，若到最后则转到数组头部 */return OK;（10）链队列的初始化Status InitQueue(LinkQueue &Q)Q.front = Q.rear = ( QNode * ) malloc ( sizeof (QNode) );if (!Q.front) exit(OVERFLOW);Q.front-next = NULL;return OK;时间复杂度O（1）（11）链队列的元素插入/* 新元素e 入队列 */Status EnQueue( LinkQueue *Q , QElemType e )QNode *p = ( QNode * ) malloc ( sizeof (QNode) ); /* 动态申请结点,C 语言*/ QNode *p = New QNode; /* 动态申请结点, C+*/if (!p) /*存储分配失败*/exit(OVERFLOW);p-data = e; /* 结点赋值 */p-next = Null;Q-rear-next = p; /* 新结点插到队尾 */Q-rear = p; /* 新结点设置为队尾 */return OK;时间复杂度O（1）（12）链队列的元素删除/* 队头元素出队列 */Status DeQueue( LinkQueue *Q , QElemType *e )QNode *p;if (Q-front = Q-rear) /* 队空 */return ERROR;p = Q-front-next; /* p 指向要出队元素所在结点 */*e = p-data; /*用e 返回出队元素 */Q-front-next = p-next; /* 头结点指向出队元素的下一个结点 */if (Q-rear =p) /* 出队前只有一个元素 */Q-rear = Q-front;free (p);return OK;时间复杂度O(1)4.了解栈的常用应用，理解利用栈实现递归的原理，掌握逆波兰式的生成和计算（1）栈的常用应用：数值转换、括号匹配、算术表达式求解、迷宫求解、实现递归（2）利用栈实现递归的原理：见 栈和队列3 课件（3）逆波兰式生成和计算逆波兰表示：所有的符号都在运算数字后面出现例：9 +（3 1）*3+10 / 2 中缀表示法9 3 1 3 * + 10 2 / + 后缀表示法，不再需要括号计算：遇到数字就进栈见到符号就运算运算结果也进栈最终结果栈底见生成：遇到数字就输出符号进栈要比较低级平级都得等高于栈顶才能进左边括号等匹配右括号来了一起闪三、串=考点：1.串的逻辑结构和两种存储表示方法2.堆存储串的基本运算及复杂度分析3.串的模式匹配=要求：1.理解串与线性表的不同（数据对象、操作对象）串： 数据对象：字符集 操作对象：子串线性表：数据对象：集合 操作对象：线形表2.掌握串的复制操作的算法及复杂度分析3.理解串的模式匹配思想及两种基本的模式匹配算法，掌握next数组的计算方法（1）Brute Force算法朴素匹配算法思路:从主串S第i位开始的m位字符串，依次与T第1位-第m位比较，若相等，返回比较之前的i值；否则i退回，从下一位开始比较；如果从S的所有位开始都不能成功匹配T，返回0.int Index ( SString S, SString T)int i = 1, j =1;while (i=S0 & jT0 ) return i-T0;else return 0;时间复杂度 O(m*n) 最坏：m(n-m+1)（2）KMP算法(克努特莫里斯普拉特算法)思路：失配时，i不回溯，T尽量多滑动一段距离int Index_KMP ( SString S, SString T)int i = 1, j =1;while (i=S0 & jT0 ) return i-T0;else return 0;(3)next数组的计算void get_next ( SString T, int next) int i = 1; next1 = 0; j=0; while (i=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root) 的结点； （2）其余的结点可分为m(m=0) 个互不相交的子集T1,T2,T3Tm, 其中每个子集又是一棵树，并称其为子树(Subtree) 。森林：互不相交的树的集合二叉树：由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。是有序数。树结点：包含一个数据元素及若干指向子树的分支孩子结点：结点的子树的根称为该结点的孩子双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲兄弟结点：同一双亲的孩子结点堂兄结点：同一层上结点结点层次：根结点所在层为第一层；下一层为第二层，依此类推树的高（深）度： 树中最大的结点层结点的度：结点子树的个数树的度：树中最大的结点度叶子结点：也叫终端结点，是度为0的结点分枝结点：度不为0的结点（非终端结点）有序树：子树有序的树，如：家族树无序树：不考虑子树的顺序2.理解二叉树的基本性质性质1： 在二叉树的第 i 层上至多有2i-1 个结点。性质2： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。性质3： 对任何一棵二叉树，若它含有n0 个叶子结点、 n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。性质4：具有 n 个结点的完全二叉树的深度为 log2n+1.性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1=i1， 则其双亲的编号是 i/2(整除）。（2）如果2in， 无左孩子；否则，其左孩子是结点2i。（3） 如果2i1n， 则结点i无右孩子；否则，其右孩子是结点2i1。3.掌握二叉树的两种存储结构（1）顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素按照完全二叉树的编号顺序存储在一维数组中一般二叉树可能浪费大量存储空间（可采用扩展二叉树）（2）链式存储结构：二叉链表 三叉链表 4.熟练掌握二叉树的四种遍历方法，以及二叉链表存储结构下的各种遍历算法的实现(1)层序来自网络void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。*/ /* 层序遍历二叉树T算法(利用队列)，对每个数据元素调用函数Visit */ SqQueue q; QElemType p; if(T) InitQueue(&q); EnQueue(&q,T); while(!QueueEmpty(q) DeQueue(&q,&p); Visit(p-data); if(p-lchild!=NULL) EnQueue(&q,p-lchild); if(p-rchild!=NULL) EnQueue(&q,p-rchild); printf(/n); （2）先序：先遍历根结点，再遍历左子树，最后遍历右子树。PreOrderTraversal( BiTree T) if(T!=NULL) printf(“%c/n”,T-data);PreOrderTraversal(T-lchild);PreOrderTraversal(T-rchild); else return;(3)中序：先遍历左子树，再遍历根结点，最后遍历右子树。InOrderTraversal( BiTree T) if(T!=NULL)InOrderTraversal(T-lchild); printf(“%c/n”,T-data);InOrderTraversal(T-rchild); else return;(4)后序：先遍历左子树， 再遍历右子树， 最后遍历根结点。PostOrderTraversal( BiTree T) if(T!=NULL) printf(“%c/n”,T-data);PostOrderTraversal(T-lchild);PostOrderTraversal(T-rchild); else return;5.理解通过遍历序列确定二叉树的方法，掌握先序序列输入下的二叉树的生成算法的实现(1)通过两个遍历序列确定二叉树的方法（重要）: 先序+中序；后序+中序 （大家自己找例子做一下这种题吧，这个挺重要的）(2)先序序列输入下的二叉树的生成算法void CreatBiTree (BiTree T) TElemType ch; scanf (“%c”,&ch); if ( ch = #) *T = Null; else *T = (BiTree) malloc(sizeof(BiTNode); if (!*T) exit(OVERFLOW); / 结点空间申请失败 (*T)-data = ch; /生成根结点 CreatBiTree (&(*T)-lchild); /构造左子树 CreatBiTree(&(*T)-rchild); /构造右子树 6.理解二叉树中序线索化的步骤及线索二叉树的遍历步骤，掌握中序线索链表的画法，(1)二叉树中序线索化：建立二叉树遍历二叉树，在遍历过程中修改空指针为前驱或后继结点（借助一个指针指向当前访问结点的前驱）(2)线索二叉树的遍历： p=T-lchild; p指向线索链表的根结点；若线索链表非空，循环： （a）顺着p左孩子指针找到最左下结点；访问之； （b）若p所指结点的右孩子域为线索， p的右孩子结点即为后继结点循环： p=p-rchild； 并访问p所指结点； （c） 一旦线索“中断”，p所指结点的右孩子域为右孩子指针， p=p-rchild， 使 p指向右孩子结点；(3)中序线索链表的画法：7.掌握哈夫曼树的构造过程及带全路径长度的计算(1)哈夫曼树的构造过程：1)根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2)在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3)从F中删除这两颗树，并将新树加入F；4)重复 2) 和3)，直到F中只含一颗树为止；(2)树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 li结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积五、图=考点：1.图的逻辑结构、相关概念及术语2.图的邻接矩阵和邻接表、逆邻接表存储方法3.图的深度优先搜索DFS与广度优先搜索BFS4.最小生成树、最短路径、AOV网与拓扑排序、AOE网与关键路径=要求：5.理解图的逻辑结构、分类及相关术语图G 由两个集合V 和E 组成，记作 G=(V, E) n V 是顶点的有穷非空集合nE 是V 中顶点偶对的有穷集,这些顶点偶对称边 。n E 可以为空集，若E为空，则图G 只有顶点没有边(1) 顶点和边(弧)n 线性表中把数据元素叫做元素，树中叫结点，在图中叫做 顶点（Vertex ） 。n 线性表可以没有元素（空表），树可以没有结点（空树），而图是非空的。n 图中顶点之间是多对多的关系，用边表示n 无向边(Edge) ：顶点vi 和vj 之间的边没有方向n 用无序偶表示(vi, vj)n 有向边( 弧Arc) ：顶点vi 和vj 之间的边有方向n 用有序偶表示n vi 称为为弧的 起点( 弧尾) ，vj 称为弧的终点( 弧头)(2) 有向图和无向图 在图G 中，如果代表边的顶点偶对是无序的，则称G为无向图 ，否则为有向图。(3) 简单图在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称为简单图。(4) 邻接点n 在无向图中 ， 若存在一条边 （Vi, Vj ） ， 则称Vi 和Vj 互为邻接点（Adjacent ）n 边 （vi ，vj ） 与顶点vi 和vj 相关联n 在有向图中 ， 若存在一条弧 ， 称V i邻接到V j ，V j 邻接自V i ，V i 和V j 互为邻接点 。(5) 顶点的度、入度和出度n 在无向图中，与顶点v 相邻接的边数称为 该顶点的度 ，记为D(v) 。n 在有向图中，顶点v 的度又分为 入度 和 出度 两种：n 以顶点v 为终点( 弧头) 的弧的数目称为顶点v 的 入度 ，记为ID(v) ；n 以顶点