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