第一章绪论。
1、数据结构研究的内容：数据的逻辑结构、数据的物理结构、数据运算。
2、数据的逻辑结构：集合、线性结构、树形结构、图形结构。
1)各种逻辑结构的特点：线性结构(一对一)、树形结构(一对多)、图形结构(多对多)
(2)逻辑结构的二元组描述（见下例）
例：数据的逻辑结构如下，试画出对应的逻辑结构图。
family_tree=(d,r)d=r=
r=解：逻辑结构图如下。
3、数据的物理结构：顺序结构、链式结构、索引、哈希。
4、算法的特征：有限性、确定性、可行性、输入性、输出性。
5、衡量算法有效性的两个主要指标：空间复杂度、时间复杂度。
6、算法的时间复杂度的分析：o(f(n))
通常用算法中基本语句的运行次数来分析算法的时间复杂度，算法中基本语句一般是最深层循环内的语句。
第二章线性表。
1、顺序表的特点。
1)逻辑相邻的数据元素物理相邻(内存空间相邻)；
2)元素之间的逻辑关系由存储位置体现，能实现随机存储；
3)顺序表通常采用数组存放数据元素；
(4)插入、删除元素时需要移动大量数据，所移动的数据数与插入、删除的位置有关。
2、单链表。
1)结点间的逻辑关系用指针表示；
2)存储结点：
数据域data：存储线性表的一个数据元素。
指针域next：存储线性表后继数据元素地址(即：指针表示后继关系)。
(3)单链表的插入、删除操作。
删除a1结点：pre->next=p->next;
在a1结点与a2结点之间插入结点x：q->next=p->next; p->next=q;
3、双向链表。
1)结点间的逻辑关系(前驱关系、后继关系)用指针表示；
2)存储结点：
数据域data：用于存储线性表的一个数据元素，指针域prior：用于存储线性表前驱数据元素地址。
指针域next：用于存储线性表后继数据元素地址。
(3)双向链表的插入、删除操作。
删除：删除指针p所指结点。
pre->next=p->next; p->next->prior=pre;
插入(先连后断)：在指针p所指结点后插入指针s所指结点：
s->next=p->next; p->next->prior=s; s->prior=p; p->next=s;
第三章栈和队列。
1、栈。1)栈的特点：后进先出、先进后出；
2)栈顶：允许删除、插入的一端。
3)栈底：不允许删除、插入的一端。
(4)n个元素按序进栈，出栈序列数为“卡特兰数”：
5)已知顺序栈的栈顶标记为top，栈空间大小为maxsize
栈空条件：栈满条件：
元素x进栈：将元素x存入中。
栈顶元素出栈：
6)已知链栈ls
1)栈空条件：ls==null
2)栈满条件：不考虑。
3)元素x进栈：动态申请存放栈元素结点*p；将结点*p插入到栈顶位置(头插法)
4)栈顶元素x出栈：置x为栈顶结点的data域；删除栈顶结点。
2、队列。1)队列的特点：先进先出、后进后出；
2)队头：允许删除的一端。
3)队尾：允许插入的一端。
4)循环队列sq
设：队尾指针rear为队尾元素下标，队头指针front为队头元素前一位置的下标，队列的容量maxsize
队空条件：队满条件：(
元素x进队：
栈顶元素出队： x= ；
5)链队列lq
设：队列操作过程中，队头指针front始终指向队头元素，队尾指针rear始终指向队尾元素。
队空条件：lq->front=null
队满条件：不考虑(因为每个结点是动态分配)
元素x进队：动态申请存放队列元素的结点*p；将结点*p插入到队尾位置，由lq->rear指向。
栈顶元素出队：读取头结点信息后删除队头结点。
第四章排序。
1、直接插入排序。
将待排序表看做是左、右两个部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，构成新的有序区。
2、折半插入排序。
方法和“直接插入排序相同”，将待排序表看做是左、右两个部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，构成新的有序区。
只是新元素在插入到有序表中采用折半查找插入位置，找到插入位置后把原位置上元素向后顺移。
3、冒泡排序。
两两比较待排序记录的关键码，如果发生逆序(即与设定的排序次序正好相反)，则交换之，直到所有记录都排好序为止。
4、快速排序。
从待排序序列中任取一个元素(一般取第一个)，将该元素放入正确位置后，整个数据序列被该数分割成两个子序列：所有比它小的元素放在前子序列，所有比它大的元素放在后子序列，该数放在这两个子序列中间，该过程称为一趟快速排序。
之后对所有的两个子序列分别重复以上过程，直到每个子序列只有一个数止。此时便为有序序列了。
5、选择排序
首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n-1趟排序后，排序结束。
例：(1)已知序列，需要将该序列按由小到大的顺序排列，请写出冒泡排序的过程和结果。
解：冒泡排序过程。
2)已知序列，需要将该序列按由小到大的顺序排列，请写出直接插入排序的过程和结果。
第五章树。1、树的性质。
1)树中结点数等于所有结点的度数加1 ：n结点数=n度数和+1
2) n度为m的树，第i层最多有mi-1个结点(i≥1)
3) 高度为h的m次树至多有个结点。
2．二叉树与度为2的树的区别。
a) 度为2的树至少有3个结点；而二叉树的结点数可以为0；
b) 度为2的树不区分子树次序，而二叉树中的每个结点最多有两个孩子结点，且严格区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
二叉树的5种形态。
3、二叉树的性质]
1)非空二叉树的叶结点数=双分支结点数+1 ：n0=n2+1
例1：一棵二叉树中总结点个数为200，其中单分支结点个数为19，求其叶子结点个数。
解：已知n=200，n1=19。又n=n0+n1+n2，由性质1得，n2=n0-1，所以有：n=2n0-1+n1，即n0=(n-n1+1)/2=91。
所以这样的二叉树中叶子结点个数为91。
2) 非空二叉树第i层至多有2i-1个结点 (i≥1)
3) 高度为h的二叉树至多有2h-1个结点(h≥1)
4) 完全二叉树中编号为i的结点 (1≤i≤n, n≥1,n为结点数)，孩子结点与双亲结点之间的关系如下。
例1：一棵完全二叉树中总结点个数为200，求其叶子结点个数。
解：依题意。
1)总结点个数： 200
2)因为n为偶数，所以： n1 =1
3)因为： n=n0+n1+n2
5)由性质1得： n2=n0-1
6)所以有： n=2n0-1+n1，n0=(n-n1+1)/2=100
所以完全二叉树中叶子结点个数为100。
4、满二叉树：二叉树中的每层都是满的。
1)第i层结点数：2i-1；
2)除叶子结点外的其他结点的度为2；
3)叶子结点在同一层上；
4)高度为h的满二叉树中的结点数为2h-1。
5、完全二叉树：二叉树除最后一层外，其余各层都是满的，并且最后一层的叶结点都集中在左侧。
6、二叉树遍历。
1)先根(前序)遍历：若树不空，则先访问根结点，然后先根遍历左子树，再先根遍历右子树。
2)中根(中序)遍历：若树不空，中根遍历左子树，访问根结点，再中根遍历右子树。
3)后根(后序)遍历：若树不空，后根遍历左子树，再后根遍历右子树，最后访问根结点。
例1：已知一棵二叉树的先根遍历序列为abcdef，中根遍历序列为cbdafe，求这棵二叉树。
7、哈夫曼树。
1)二叉树的带权路径长度：
设二叉树具有n个带权值的叶子结点，从根结点到每个叶子结点都有一个路径长度。从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和称为该二叉树的带权路径长度。
2) 哈夫曼树：由一组具有确定权值的叶子结点所构造的二叉树中，最小带权路径长度的树。
(3) 构造哈夫曼树的步骤。
由n个权值构造n棵只有一个根结点的二叉树，得到一个二叉树的集合f=；
选取f中根结点权值最小、次小的两棵二叉树作为左、右子树构造一棵新二叉树，这棵新的二叉树根结点权值为其左、右子树根结点权值之和；
删除集合f中所选出两棵二叉树，将新建立的二叉树加入到集合f中；
重复②、③两步，到f中只剩下一棵哈夫曼树。
8、哈夫曼编码：利用哈夫曼树构造的、用于通信的二进制编码。
例：求电文“casttatasa”(其中，“”表示空格)中各字符的哈夫曼编码。
解：(1)统计电文中字母的频度：f(‘c’)=1，f(‘s’)=2，f(‘t’)=3，f(‘’3，f(‘a’)=4 。
2)用频度为权值构造哈夫曼树，叶结点为对应字符。
3)约定：树中的左分支表示”0”码，右分支表示”1”码。
4)从根到叶子路径上的“0”或“1”的序列即为字符的哈夫曼编码。
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...