《数据结构速成攻略》由会员分享，可在线阅读，更多相关《数据结构速成攻略（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构速成攻略考试题型：选择、填空、简答、算法。第1章绪论1、存储结构物理结构：顺序存储结构特点：只存数据不存关系，其关系体现在存储 位置上和链式存储结构特点：需存数据与其关系2、 逻辑结构：集合、线性结构、树型结构、图型结构其中树和图属于非线性结构3、数据类型:原子类型非结构，可分解、结构类型不可分解4、算法的时间复杂度一个算法的时间耗费的数量级、空间复杂度与问题规模n有关Eg： for i=0； in;i+for(j=0;jm;j+)Aij=O;则时间复杂度为0(m*n)第2章线性表1、线性表的顺序存储结构随机存取：顺序存储时，相邻数据元素的存放地址也相邻逻辑与物理统一；要求内存中可用
2、存储单元的地址必须是连续的。设每个元素需占用L个存储单元，则第i个数据元素a的存储位置为Loca=Lociia+L* i-1。i当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时,其时间主要耗 费在移动元素上，移动元素的个数取决于插入或删除元素的位置。若表长为n,则插入、删除操作平均移动n个元素，算法时间复杂度为0n。优点：存储密度大=1，存储空间利用率高，便于访问。缺点：插入或删除元素 时不方便。宜做查找这样的静态操作。若线性表长度变化不大插入、删除等操作在表尾进行， 且主要操作是查找，则采用顺序表。2、线性表的链式存储结构顺序存取：链式存储时，相邻数据元素可随意存放逻辑相邻物理不
3、一定相邻，但所占存储空间 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。每个元素由结点Node构成，它至少包括两个域，数据域data：存储数据元素信 息；指针域link：存储直接后继存储位置指示数据元素之间的逻辑关系。整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置。最后一个数据元素没有直接后继，现行链表中最后一个结点的指针为“空NULL。优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小1，存储空间利用 率低。宜做插入、删除等动态操作。若线性表长度变化较大，且主要操作是插入、删除则采 用链表。3、单链表插入操作（核心语句）：s-next=p-ne
4、xt; p-next=s;删除操作（核心语句）：q=p-next; p-next=q-next; free（q）;在单链表中，除了首元结点外，任意结点内的存储位置由前驱结点的后继指针指示。在单链表中设置头结点的作用是简化链表操作。4、L为指向表头结点的指针，p为指向表尾结点的指针，p满足的条件判断是哪类链表: 单链表 p-nex t=NULL循环链表表中最后一个结点的指针域指向头结点，整个链表形成一个环p-nex t=L双向链表结点中有两个指针域，其一指向直接后继，另一指向直接前驱p-next=NULL双向循环链表p-nex t=NULL5、L为指向表头结点的指针，链表为空，应满足条件：单链表
5、 L-nex t=NULL循环链表L-nex t=L双向链表 L-nex t=NULL双向循环链表L-nex t=NULL & L-prior=NULL第3章栈和队列1、栈栈是限定仅在表尾进行插入进栈Push或删除出栈Pop操作的线性表。表尾端称 为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的。2、队列队列是一种先进先出的线性表。队列只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做队尾, 允许删除的一端则称为对头。3、栈和队列的顺序存储和链式存储顺序栈栈的顺序存储结构是利用一组地址连续的存储单元一次存放自栈底到栈顶的 数据元素，同时附设指针to
6、p指示栈顶元素在顺序栈中的位置。以栈顶指针top=0表示空 栈顺序栈中入栈操作需判断栈满，出栈操作需判断栈空。链栈栈的链式存储结构是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。链栈中指针方向指向前驱结点。链栈入栈操作不需判断栈满：p-data=x;/设置新结点的值p-next=top;/ 将新元素插入栈中top=p； /将新元素设置为栈顶链栈出栈操作需判断栈空：p-top;/指向被删除的栈top二top-next;/修改 栈顶指针 freep；4、循环队列，队空、队满的条件设数组维数M,两个指针front队头指针、rear队尾指针队空：front二二rear队满：rear+1%
7、M=front入队列：rear二rear+1%M出队列：front=front+1%M循环队列中是否能插入下一个元素与队头指针与队尾指针有关。循环队列用数组Am存放其元素值，已知队头指针front、队尾指针rear，则当前 队列中元素个数是rear-front+mm。第4章字符串1、字符串的操作StrAssign(&T,chars):生成一个其值等于 chars 的串 T。StrCopy(&T,S):由串S复制得串T。StrEmptyS：若S为空串，则返回TRUE，否则返回FALSE。StrCompareS,T：若ST则返回值0，若S=T则返回值=0，若S=0)个结点的有限集合，它或为空树(n
8、=0),或由一个根结点和至多两棵称为根的 左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2 的结点，并且二叉 树的子树有左子树和右子树之分。二叉树的五中形态由三个结点构成：空树、只含根节点、右子树为空树、左子树 为空树、左右子树均不为空树。3、二叉树的性质在二叉树的第i层上至多有2i-1个结点il。深度为k的二叉树至多有2k-1个结点kl。对任何一颗二叉树T,如果其终端结点数为气，度为2的结点数为气,则气=气+1。4、二叉树的顺序存储和存储2 2二叉树的顺序存储特点仅适用于完全二叉树：一组地址连续的存储单元存储各结 点(定义一个一维数组)；自上而下、自左而右存储结点；按完全二叉
9、树上的结点位置进行编 号和存储。缺点：空间利用率太低！二叉链表：链表的头指针指向二叉树的根节点。结点结构至少包含：数据域和左右孩 子指针域 lchild data rchild在含有n个结点的二叉链表中有n+1个空链域。三叉链表结点结构包含：数据域、左右孩子指针域和双亲指针。5、在二叉树的的先序、中序和后续三种遍历序列中，已知二叉树的先序遍历序列和中序遍 历序列，可求得另一种序列。解题思路：由先序先确定root,由中序可确定root的左、右子树。然后由其左子树 的元素集合和右子树的集合对应先序遍历序列中的元素集合，可继续确定root的左右孩子。 将他们分别作为新的root,不断递归，则所有元素都将被唯一确定，问题得解。按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次,而且仅被访问一次。先序遍历二叉树：访问根节点。先序遍历左子树。先序遍历右子树。中序遍历二叉树：中序遍历左子树。访问根节点。中序遍历右子树。后序遍历二叉树：后序遍历左子树。后序遍历右子树。访问根节点。先序序列的第一个结点是根节点，中序序列根节点处于左右子树的中序序列之间。6、中序线索化二叉树书132指向结点前驱和后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。7、完全二叉树的概念和性质 一颗深度为k且2k-1个结点的二叉树称为满二叉树没有度为1的结点。深度为k的，有n个结点
