数据结构速成攻略

《数据结构》速成攻略考试题型：选择、填空、简答、算法。第1章绪论1、存储结构（物理结构）：顺序存储结构（特点：只存数据不存关系，其关系体现在存储位置上）和链式存储结构（特点：需存数据及其关系）2、逻辑结构：集合、线性结构、树型结构、图型结构（其中树和图属于非线性结构）3、数据类型:原子类型（非结构，可分解）、结构类型（不可分解）4、算法的时间复杂度（一个算法的时间耗费的数量级）、空间复杂度与问题规模n有关Eg：for（i=0；in;i++）for(j=0;jm;j++)A[i][j]=0;则时间复杂度为O(m*n)第2章线性表1、线性表的顺序存储结构（随机存取）：△顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。△设每个元素需占用L个存储单元，则第i个数据元素ai的存储位置为Loc（ai）=Loc（ai）+L*（i-1）。△当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，移动元素的个数取决于插入或删除元素的位置。△若表长为n，则插入、删除操作平均移动n2个元素，算法时间复杂度为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==NULL5、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）:若ST则返回值0,若S=T则返回值=0，若ST则返回值0。△StrLength（S）:返回S的元素个数，称为串的长度。△ClearString（&S）:将S清为空串。△Concat（&T，S1，S2）:用T返回由S1和S2联接而成的新串。△SubString（&Sub，S，pos，len）：用Sub返回串S的第pos个字符其长度为len的子串。△Index（S，T，pos）：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。第5章数组和广义表1、已知二维数组A[m][n]以行为主序存储，每个元素占L个字节，Loc（0,0）为首元素存储地址（基址）,则A中任一元素aij的存储位置为Loc（i，j）=Loc（0,0）+（n*i+j）*L。2、矩阵的压缩存储（以行为主序和以列为主序，存储上三角或下三角）△以行为主序将n阶对称阵的下三角（含主对角线）存储到一维数组b[1…n(n+1)/2]中：①下三角元素aij(1≤i,j≤n且i≥j)在b中的位置为——[1+2+…+(i-1)]+j=i(i-1)/2+j。上三角元素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+1。4、二叉树的顺序存储和链接存储△二叉树的顺序存储特点（仅适用于完全二叉树）：一组地址连续的存储单元存储各结点(定义一个一维数组)；自上而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储。缺点：空间利用率太低！△二叉链表：链表的头指针指向二叉树的根节点。结点结构至少包含：数据域和左右孩子指针域lchilddatarchild△在含有n个结点的二叉链表中有n+1个空链域。△三叉链表结点结构包含：数据域、左右孩子指针域和双亲指针。5、在二叉树的的先序、中序和后续三种遍历序列中，已知二叉树的先序遍历序列和中序遍历序列，可求得另一种序列。△解题思路：由先序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应先序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。△按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。△先序遍历二叉树：①访问根节点。②先序遍历左子树。③先序遍历右子树。△中序遍历二叉树：①中序遍历左子树。②访问根节点。③中序遍历右子树。△后序遍历二叉树：①后序遍历左子树。②后序遍历右子树。③访问根节点。△先序序列的第一个结点是根节点，中序序列根节点处于左右子树的中序序列之间。6、中序线索化二叉树（书132）△指向结点前驱和后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。7、完全二叉树的概念和性质△一颗深度为k且2k-1个结点的二叉树称为满二叉树（没有度为1的结点）。△深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。△完全二叉树的特点：①叶子结点只可能在层次最大的两层上出现。②对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。△具有n个结点的完全二叉树的深度为[log2n]+1。△如果对一颗有n个结点的完全二叉树（深度为[log2n]+1）的结点按层序编号（从第一层到第[log2n]+1层，每层从左到右），则对任意几点i（1≤i≤n），有：①如果i=1，则结点i是二叉树的根，无双亲；如果i＞1，则其双亲是结点[i/2]。②如果2i＞n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。③如果2i+1＞n，则结点i无右孩子，否则其右孩子是结点2i+1。Eg：完全二叉树的第五层有6个叶子。求该树结点个数最多是多少。最大层高：6（叶子只可能存在在最高2层）前5层结点数：25-1=31第5层的结点数：25