第一章：概述
1、程序=算法+数据结构
2、算法的几个基本特征：能行性 确定性 有穷性 拥有足够的情报
3、算法的复杂度主要包括： 时间复杂度和空间复杂度
第二章：数据结构
1、逻辑结构：数据集合中各数据元素之间所固有的逻辑关系(集合结构、线性结构、树形结构、图状结构)，可以看作是从具体问题抽象出来的数据模型。
2、物理(存储)结构：在对数据进行处理时，各数据元素在计算机中的存储关系，可分为以下四种：顺序存储结构(存储空间连续)、链式存储结构、索引结构、散列结构
3、数据结构的运算是指对数据结构中的结点进行操作的集合，包括插入、删除、更新、检索、排序等。
4、数据元素是数据的基本单位
5、有时数据元素可由若干个数据项(数据的属性)组成，在这种情况下，数据项组成的数据元素称为记录，数据项是具有独立含义的最小标识单位，不可分割
6、顺序存储结构：通常定义一维数组来表示线性表的顺序存储空间
7、顺序表的插入
异常处理：(m为线性表的空间大小，n为线性表的长度
当存储空间已满(即)时为上溢错误，不能进行插入，算法结束；
当i>n时，认为在最后一个元素之后(即第1个元素之前)插入；
当i<1时，认为在第1个元素之前插入
函数的代码实现：
( * i, b)
{
k;
() <
(i>n) 1;
(i<1) 1;
(>)
{
v[k][1];
v[1];
1;
}
}
8、顺序表的删除
异常处理：
当线性表为空(即0)时为下溢错误，不能进行删除，算法结束；
当i<1或i>n时，认为不存在该元素，不进行删除。
函数的代码实现：
( *v, n, i)
{
k;
(0) <
((i<1)(i>n)) <
(
v[1][k];
1;
}
9、栈(相当于一个井)的相关概念
先进后出(后进先出)
栈顶允许插入与删除
栈底不允许插入与删除
10、队列(相对于排队买饭)的相关概念
先进先出
队尾允许插入
对头允许删除
11、链式存储每个结点由两部分组成：数据域和指针域
12、单链表的插入函数实现
在包含元素x的结点前插入新元素b
( b)
{
*p,*q;
;
>;
()
{
;
>;
}
(>)
{
>;
;
}
;
((>)(((>)->)))
>;
>>;
>;
}
13、单链表的删除函数实现
删除包换元素x的结点
( x)
{
*p,*q;
() <
((>))
{
>;
;
;
}
;
(((>))(((>)->)))
>;
(>) <
>;
>>;
p;
}
14、循环链表的插入函数实现
在包含元素x的结点前插入新元素b
( b)
{
*p,*q;
;
>;
;
((>)(((>)->)))
>;
>>;
>;
}
15、循环链表的删除函数实现
删除包含元素x的结点
( x)
{
*p,*q;
;
((>)(((>)->)))
>;
(>) <
>;
>>;
p;
}
16、单链表与循环链表的区别
= 1 \* 2 ⑴单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。
= 2 \* 2 ⑵单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点.
17、下三角矩阵的压缩存储
(以行为主压缩)
(以行为主压缩)
(以列为主压缩)
(以列为主压缩)
18、对称矩阵的压缩
19、索引存储的方式
顺序—索引—顺序、顺序—索引—链接、链接—索引—顺序、链接—索引—链接
20、二叉树的性质
⑴在二叉树的第k层上，最多有2k－1(k≥1)个结点
⑵深度为m的二叉树最多有2m－1个结点(深度即为层数)
⑶在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个
⑷具有n个结点的二叉树，其深度至少为[2n]＋1，其中[2n]表示取2n的整数部分
21、满二叉树是指每层的结点都有两个子结点，满的不行不行的了，完全二叉数是指最后一层必须是从左至右的顺序断了线的，其余层都是满的。
22、前序遍历、中序遍历、后续遍历(前中后对应的是根结点的访问顺序)
前序遍历：先根结点，再左再右
中序遍历：先左，再根结点，再右
后续遍历：先左，再右，再根结点
23、若给出三种遍历中的任意两种遍历，要求写出第三种遍历，思路如下：
先正确画出对应的二叉树，根据已给条件进行验证，最后写出第三种遍历
24、三种遍历的程序实现
⑴前序遍历
()
{
