数据结构知识点总结整理

数据结构知识点总结整理0、常考基础必知必会A.排序：排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法；B.查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别？C.链表和数组的区别，在什么情况下用链表什么情况下用数组？D.栈和队列的区别？E.多态，举例说明；overload和override的区别？F.字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。strcpy和memcpy？G.继承、多继承？H.面向对象有什么好处？I.说说static的与众不同之处，如果一个变量被声明为static，它会被分配在哪里？在什么时候分配空间等？J.什么是虚函数、纯虚函数、虚的析构函数，用途？K.内存泄漏及解决方法？网络部分：OSI模型7层结构，TCP/IP模型结构？B.TCP/UDP区别？C.TCP建立连接的步骤？D.香农定理？1、二叉树三种遍历的非递归算法（背诵版）本贴给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。1.先序遍历非递归算法#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{visite(p-data);push(s,p);p=p-lchild;}//endwhileif(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p-rchild;}//endif}//endwhile}//PreOrderUnrec2.中序遍历非递归算法#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidInOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{push(s,p);p=p-lchild;}//endwhileif(!StackEmpty(s)){p=pop(s);visite(p-data);//访问根结点p=p-rchild;//通过下一次循环实现右子树遍历}//endif}//endwhile}//InOrderUnrec3.后序遍历非递归算法#definemaxsize100typedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack;//后序遍历voidPostOrderUnrec(Bitreet){SqStacks;stacknodex;StackInit(s);p=t;do{while(p!=null)//遍历左子树{x.ptr=p;x.tag=L;//标记为左子树push(s,x);p=p-lchild;}while(!StackEmpty(s)&&s.Elem[s.top].tag==R){x=pop(s);p=x.ptr;visite(p-data);//tag为R，表示右子树访问完毕，故访问根结点}if(!StackEmpty(s)){s.Elem[s.top].tag=R;//遍历右子树p=s.Elem[s.top].ptr-rchild;}}while(!StackEmpty(s));}//PostOrderUnrec4.层次遍历算法//二叉树的数据结构structBinaryTree{intvalue;//不写模板了，暂时用整形代替节点的数据类型BinaryTree*left;BinaryTree*right;};BinaryTree*root;//已知二叉树的根节点//层次遍历voidLevel(constBinaryTree*root){Queue*buf=newQueue();//定义一个空队列，假设此队列的节点数据类型也是整形的BinaryTreet;//一个临时变量buf.push_back(root);//令根节点入队while(buf.empty==false)//当队列不为空{p=buf.front();//取出队列的第一个元素coutp-value'';if(p-left!=NULL)//若左子树不空，则令其入队{q.push(p-left);}if(p-right!=NULL)//若右子树不空，则令其入队{q.push(p-right);}buf.pop();//遍历过的节点出队}coutendl;}2、线性表（1）性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。（2）单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。（3）单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。3、栈与队列你可以问一下自己是不是已经知道了以下几点：(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。(4)循环队列中判队空、队满条件，循环队列中入队与出队（循环队列在插入时也要判断其是否已满，删除时要判断其是否已空）算法。【循环队列的队空队满条件为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：front=rear，当队满时：front=rear亦成立，因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：（1）另设一个标志位以区别队列是空还是满。（2）少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。队空时：front=rear，队满时：(rear+1)%maxsize=front】如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。////////////////////////////////////////////////////////////////////////////////////////////////循环队列的主要操作：(1)创建循环队列(2)初始化循环队列(3)判断循环队列是否为空(4)判断循环队列是否为满(5)入队、出队//空出头尾之间的一个元素不用#include#include#defineMAXSIZE100typedefstruct{intelem[MAXSIZE];intfront,rear;}Quque;//定义队头intinitQue(Quque**q)//初始化{(*q)-front=0;(*q)-rear=0;}intisFull(Quque*q){if(q-front==(q-rear+1)%MAXSIZE)//判满(空出一个元素不用)刘勉刚return1;elsereturn0;}intinsertQue(Quque**q,intelem){if(isFull(*q))return-1;(*q)-elem[(*q)-rear]=elem;(*q)-rear=((*q)-rear+1)%MAXSIZE;//插入return0;}intisEmpty(Quque*q){if(q-front==q-rear)//判空return1;elsereturn0;}intdeleteQue(Quque**q,int*pelem){if(isEmpty(*q))return0;*pelem=(*q)-elem[(*q)-front];(*q)-front=((*q)-front+1)%MAXSIZE;return0;}4、串串一章需要攻破的主要堡垒有：1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件；2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。3.顺序串与链串及块链串的区别和联系，实现方式。4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。5、多维数组和广义表矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。6、树与二叉树树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。(1)二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树(左右子树无序)的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：A.第i层的最多结点数，B.深度为k的二叉树的最多结点数，C.n0=n2+1的性质，D.n个结点的完全二叉树的深度，E.顺序存储二叉树时孩子结点与父结点之间的换算关系（root从1开始，则左为：2*i，右为：2*i+1）。二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。(2)二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。(3)可在三种遍历算法的基础上改造完成的其它二叉树算法：求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。(4)线索二叉树：线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定