数据结构速成攻略(共9页).docx

精选优质文档-----倾情为你奉上《数据结构》速成攻略考试题型：选择、填空、简答、算法第1章 绪论1、存储结构（物理结构）： 顺序存储结构（特点：只存数据不存关系，其关系体现在存储位置上） 和 链式存储结构（特点：需存数据及其关系）2、逻辑结构： 集合 、 线性结构 、 树型结构 、 图型结构（其中树和图属于非线性结构）3、数据类型:原子类型（非结构，可分解）、结构类型（不可分解）4、算法的时间复杂度（一个算法的时间耗费的数量级）、空间复杂度与问题规模n有关 Eg： for（i=0；i

△若表长为n，则插入、删除操作平均移动个元素，算法时间复杂度为O（n）△优点：存储密度大（＝1），存储空间利用率高，便于访问缺点：插入或删除元素时不方便△宜做查找这样的静态操作若线性表长度变化不大（插入、删除等操作在表尾进行），且主要操作是查找，则采用顺序表2、线性表的链式存储结构（顺序存取）：△链式存储时，相邻数据元素可随意存放（逻辑相邻物理不一定相邻），但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针△每个元素由结点（Node）构成，它至少包括两个域，数据域（data）：存储数据元素信息；指针域（link）：存储直接后继存储位置（指示数据元素之间的逻辑关系）△整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置最后一个数据元素没有直接后继，现行链表中最后一个结点的指针为“空”（NULL）△优点：插入或删除元素时很方便，使用灵活缺点：存储密度小（<1），存储空间利用率低△宜做插入、删除等动态操作若线性表长度变化较大，且主要操作是插入、删除则采用链表3、单链表△插入操作(核心语句)：s->next=p->next; p->next=s;△删除操作(核心语句)：q=p->next; p->next=q->next; free(q);△在单链表中，除了首元结点外，任意结点内的存储位置由前驱结点的后继指针指示。

△在单链表中设置头结点的作用是简化链表操作4、L为指向表头结点的指针，p为指向表尾结点的指针，p满足的条件（判断是哪类链表）：单链表 p->next==NULL循环链表（表中最后一个结点的指针域指向头结点，整个链表形成一个环） p->next==L双向链表（结点中有两个指针域，其一指向直接后继，另一指向直接前驱） p->next==NULL双向循环链表  p->next==NULL 5、L为指向表头结点的指针，链表为空，应满足条件：单链表 L->next==NULL循环链表 L->next==L双向链表 L->next==NULL双向循环链表  L->next==NULL && L->prior==NULL  第3章  栈和队列1、栈  △栈是限定仅在表尾进行插入（进栈Push）或删除（出栈Pop）操作的线性表表尾端称为栈顶，表头端称为栈底不含元素的空表称为空栈△栈的修改是按后进先出的原则进行的2、队列△队列是一种先进先出的线性表△队列只允许在表的一端进行插入，而在另一端删除元素允许插入的一端叫做队尾，允许删除的一端则称为对头3、栈和队列的顺序存储和链式存储  △顺序栈（栈的顺序存储结构）是利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

以栈顶指针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）%M=front 入队列：rear=（rear+1）%M出队列：front=（front+1）%M△循环队列中是否能插入下一个元素与队头指针与队尾指针有关△循环队列用数组A[m]存放其元素值，已知队头指针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）:若S>T则返回值>0,若S=T则返回值=0，若S

上三角元素aij(1≤i,j≤n且i≤j)在b中的位置为——j(j-1)/2+i ②上三角元素aij(1≤i,j≤n且i≤j)在b中的位置为——[n+(n-1)+…+(n-i+2)]+(j-i+1)= (2n-i+2)(i-1)/2+[j-(i-1)]= (2n-i)(i-1)/2+j下三角元素aij(1≤i,j≤n且i≥j)在b中的位置为——(2n-j)(j-1)/2+i① 更简单） △以列为主序将n阶对称阵的下三角（含主对角线）存储到一维数组b[n(n+1)/2]中，①下三角元素aij(1≤i,j≤n且i≥j)在b中的位置为——[n+(n-1)+…+(n-j+2)]+(i-j+1)= (2n-j+2)(j-1)/2+[i-(j-1)]=(2n-j)(j-1)/2+i上三角元素aij(1≤i,j≤n且i≤j)在b中的位置为——(2n-i)(i-1)/2+j②以列为主序将n阶对称阵的上三角（含主对角线）存储到一维数组b[n(n+1)/2]中，上三角元素aij(1≤i,j≤n且i≤j)在b中的位置为——[1+2+…+(j-1)]+i = j(j-1)/2+i下三角元素aij(1≤i,j≤n且i≥j)在b中的位置为——i(i-1)/2+j（② 简单） 2、 广义表△广义表LS=（a1，a2，……an），n为其长度。

ai可以是单个元素也可以是广义表称第一个元素a1广义表的表头，成其余元素组成的表（a2，a3……an）是广义表的表尾△广义表的深度定义为广义表中括弧的重数空表也是广义表，且空表的深度为1. 第6章  树1、树△结点：包含一个数据元素及若干指向其子树的分支△结点的度：结点拥有的子树数△叶子（或终端）结点：度为零的结点分支（或非终端）结点：度大于零的结点 △树的度：树中所有结点的度的最大值 △结点的层次：根结点的层次为1，第l层的结点的子树的根结点的层次为l+1△树的深度：树中叶子结点所在的最大层次△任何一棵非空树是一个二元组Tree = (root，F)其中：root 被称为根结点 F 被称为子树森林Eg：n个结点的树，只有度为0和度为5的结点问有几个度为0的结点借助分支计算）设：度为0的个数n0，度为5的个数n5则有n=n0+n5；n=5*n5=+1解得：度为0的结点个数有n0=（4n+1）/5个2、二叉树△n(n>=0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成注：二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分。

△二叉树的五中形态（由三个结点构成）：空树、只含根节点、右子树为空树、左子树为空树、左右子树均不为空树3、二叉树的性质△在二叉树的第i层上至多有2i-1个结点（i≥1）△深度为k的二叉树至多有2k-1个结点（k≥1）△对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+14、二叉树的顺序存储和链接存储△二叉树的顺序存储特点（仅适用于完全二叉树）：一组地址连续的存储单元存储各结点(定义一个一维数组)；自上而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储缺点：空间利用率太低！△二叉链表：链表的头指针指向二叉树的根节点结点结构至少包含：数据域和左右孩子指针域 lchild data rchild△在含有n个结点的二叉链表中有n+1个空链域△三叉链表结点结构包含：数据域、左右孩子指针域和双亲指针5、在二叉树的的先序、中序和后续三种遍历序列中，已知二叉树的先序遍历序列和中序遍历序列，可求得另一种序列△解题思路：由先序先确定root，由中序可确定root的左、右子树然后由其左子树的元素集合和右子树的集合对应先序遍历序列中的元素集合，可继续确定root的左右孩子。

将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解△按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次△先序遍历二叉树：①访问根节点②先序遍历左子树③先序遍历右子树△中序遍历二叉树：①中序遍历左子树②访问根节点③中序遍历右子树△后序遍历二叉树：①后序遍历左子树②后序遍历右子树③访问根节点△先序序列的第一个结点是根节点，中序序列根节点处于左右子树的中序序列之间6、中序线索化二叉树（书132）△指向结点前驱和后继的指针叫做线索加上线索的二叉树称之为线索二叉树7、完全二叉树的概念和性质△一颗深度为k且2k-1个结点的二叉树称为满二叉树（没有度为1的结点）△深度为k的，有n个结点的二叉树，当且仅当其每一个结点都。