数据结构导论_自学考试_概念整理

第 一 章 概论 第 二 章 线 性 表 第 三 章 栈 和 队 列 第 四 章 串

第 五 章 多 维 数 组 第 六 章 树 第 七 章 图 第 八 章 排序 第 九 章 查找 第 一 章 概 论

1.数据：信息的载体,能被计算机识别、存储和加工处理。

2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：

1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。 常用的运算：检索/插入/删除/更新/排序。

4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据的存储结构是逻辑结构用计算机语言的实现。

5.数据类型：一个值的集合及在值上定义的一组操作的总称。

分为：原子类型和结构类型。

6.抽象数据类型：抽象数据的组织和与之相关的操作。

优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题； 类：是在实现层上描述问题；

在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有：

（1）线性结构，若结构是非空集则仅有一个开始和终端结点，

并且所有结点最多只有一个直接前趋和后继。

（2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有：

1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。

3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的质量：

1正确性；算法应能正确地事先预定的功能。

2易读性；算法应易于阅读和理解，以便于调试和扩充。

3健壮性；当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。 4高效率；即达到所需的时间和空间性能。

11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。 时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2 )、线性阶O(n)、线性对数阶O(nlog2 )、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。 13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。 12.算法的特征：有穷性；确定性；可行性；输入；输出。

13. 决定算法运行时间的因素：（1）问题的规模；（2）编译时间；（3）指令执行速度；（4）重

复执行指令的速度。 第 二 章 线 性 表

1.线性表：是由n(n≥0)个数据元素组成的有穷序列。 2.线性表的基本运算有：

1）Initiate(L),加工型运算，作用是构造空表，即表的初始化； 2）Length(L),引用型运算，其结果是表的结点个数，即表长；

3）Get (L,i), 引用型运算，若1≤i≤Length(L)，其结果是表中的第i个结点；否则，为一特殊值。 4）Locate (L,x) ，引用型运算，查找L中值为x的结点并返回结点在L中的位置，若有多个x则返回首个；否则返回特殊值表示查找失败。

5）Insert (L,x,i)，加工型运算，在表的第i个位置插入值为x的新结点，要求1≤i≤Length(L)+1； 6）Delete (L,i)，加工型运算，删除表的第i个位置的结点，要求1≤i≤Length(L)； 3.顺序表：是线性表的顺序存储结构，即按顺序存储方式构造的线性表的存储结构。

4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n （其中Loc(a1)是顺序表的第一个结点，C每个变量占用的内存单元）。 5.顺序表上的基本运算 （1）插入

Void insert_sqlist(sqlist L,datatype x,int i) /*将X插入到顺序表L的第i-1个位置*/ {

if(st==maxsize) error(“overflow”); /*溢出*/

if((i<1)||(i>st+1)) error (“position error”); /*非法位置*/ for(j=st;j=i;j--)

L.data[j]=L.data[j-1]; /*结点依次后移*/ L.data[i-1]=x; /*置入X*/ st=st+1 /*修改表长*/ }

在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。 （2）删除

Void delete_sqlist(sqlist L,int i); /*删除顺序表L中的第i个位置上的结点*/ {

if ((i<1)||(i>st)) error (“position error”)； /*非法位置*/ for(j=i+1;j=st;j++)

L.data[j-2]=L.data[j-1]; /*依次前移，注意第一个L.data[j-2]存放ai*/ st=st-1 /*修改表长*/ }

在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。 （3）定位

Void locate_sqlist(sqlist L,datatype X)

/*在顺序表中从前往后查找第一个值等于X的结点。若找到则传回该节点的序号；否则传回0*/ {

i=1; /*i指示顺序表L中结点序号*/

while ((i≤st)&&(L.data[i-1]!=x)) /*注意：a1在L.data[i-1]中*/

i++； /*从前往后找*/ if (i≤st) return (i) else

return (0)

}

6. .单链表：只有一个链域的链表称单链表。

（单链表表示法的基本思想是用指针表示结点间的逻辑关系） 单链表的一个结点包含两个部分，结点形式如下： 数据域 指针域（链域）

（1） 建立单链表。时间复杂度为O(n)。

在单链表中加头结点的作用：操作统一；无论链表是否为空，链表的指针不变。

（2） 定位（按值查找）

Int locate_lklist(lklist head,datatype x)

/*求表head 中第一个值等于X的结点的序号。不存在这种结点时结果为0*/ {

P=head;j=0; /*置初值*/

While((p->next!=NULL)&&(p->data!=x)) {

p=p->next;j++; }

If p->data==x return(j); Else return(0); }

(3)删除 时间复杂度为O(n)

Void delete_lklist(lklist head;int i) /*删除表head的第i个结点*/ {

p=find_lklist(head,i-1); /*先找待删结点的直接前驱*/ q=p->next; /*q指向待删结点*/

p->next=q->next; /*摘除待删结点*/ free(q); /*释放已摘除结点q*/ }

Else error(“不存在第i个结点”) /*否则给出相关信息*/ }

（3） 插入 时间复杂度为O(n)

Void insert_lklist(lklist head,datatype x,int i)

/*在表head的第i个位置上插入一个以x为值的新结点*/ {

P=find_lklist (head,i-1); /*先找第i-1个结点*/ if(p==NULL) /*若第i-1个结点不存在*/

error(“不存在第i个位置”) /*退出并给出出错信息*/ else {

S=malloc(size); s->data=x; /*否则生成新结点*/

S->next=p->next; /*结点*p的链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } }

7..循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。

主要优点：从表中任一结点出发都能通过后移做而扫描整个循环链表。 8.空循环链表仅由一个自成循环的头结点表示。 prior data next

，形成的链表中有两条不同方向的链称为双链表。 10.双链表的特点是找结点的前驱和后继都很容易。 11.顺序表和链表的比较

1） 基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。 2） 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。

第 三 章 栈 和 队 列

1. 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。 插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。 2. 栈的基本运算有：

（1） 初始化 Initstack(s),加工型运算，构造一个空栈。

（2） 进栈 Push(S,X)，加工型运算，将元素X插入栈S中，是X成为栈S的栈顶元素。

（3） 退栈 Pop(s),加工型运算， 当栈不为空时，将栈顶元素赋给X，并从栈中删除当前栈顶。 （4） 读栈顶 Top(s),引用型运算，若栈S不空，由X返回栈顶元素；当栈S为空时，结果为一个特殊标志。

（5） 判栈空 Empty(s), 引用型运算，若栈S为空栈，则结果为1，否则结果为0. 3. 顺序栈：栈的顺序存储结构称顺序栈。

4. .当栈满时，做进栈运算必定产生空间溢出，称“上溢”。 当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。 5. 在顺序栈上的基本运算： 1） 置空栈。

Void initstack(seqstack *s) {

s->top=-1; }

2)判栈空。

int stackempty(seqstack *s) {

return s->top==-1; }

3)判栈满。

int stackfull(seqstack *s) {

return s->top==stacksize-1; }

4)进栈。

Void push(seqstack *s,datatype x) {

if(stackfull(s))

error(“stack overflow”);

s->data[++s->top]=x;

}

5)退栈。

Datatype pop(seqstack *s) {

if(stackempty(s))

error(“stack underflow”); return S->data[s->top--]; }

6)取栈顶元素。

Dtatatype stacktop(seqstack *s) {

if(stackempty(s))

error(“stack underflow”); return S->data[s->top]; }

6. 链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。 7.链栈上的基本运算： 1） 建栈。

Void initstack(linkstack *s) {

s->top=NULL; }

2)判栈空。

Int stackempty (linkstack *s) {

return s->top==NULL; }

3) 进栈。

Void push(linkstack *s,datatype x) {

stacknode *p=(stacknode *)malloc(sizeof(stacknode)); p->data=x;

p->next=s->top; s->top=p; }

4) 退栈。

Datatype pop(linksatck *s) {

datatype x;

stacknode *p=s->top; if(stackempty(s))

error(“stack underflow”); x=p->data;

s->top=p->next;

free(p); return x;

}

5) 取栈顶元素。

Datatype stacktop(linkstack *s) {

if(stackempty(s))

error(“stack is empty”); return s->top->data; }

8. 队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。 队列又称为先进先出线性表，FIFO表。 9. 队列的基本运算：

1）初始化 InitQueue(Q),加工型运算，设置一个空队列Q。

2）入队列 EnQueue(Q,X),加工型运算，将X插入到队列Q的队尾。

3）出队 OutQueue(Q,X)，加工型运算，若队列Q不为空，则将队头元素赋给X，并删除队头结点，而该结点的后继成为新的队头结点。

4）判队列空 EmptyQueue(Q),引用型运算，若队列Q为空，则返回的值为1，否则为0。

5）读队头 GetHead(Q,x),引用型运算，Q不空时由参数X返回队头结点的值，否则给一特殊标志。 10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。

11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。

12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize

13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。 解决的方法有：

1） 另设一个布尔变量以区别队列的空和满；

2） 少用一个元素，在入队前测试rear在循环意义下加1是否等于front； 3） 使用一个记数器记录元素总数

14. 链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。 15. .链队列的基本运算： 1）入队。

Void enqueue(linkqueue *q,datatype x) {

queuenode *p=(queuenode *)malloc(sizeof(queuenode)); p->data=x; p->next=NULL; if(queueempty(q))

q-front=q->rear=p; else {

q->rear->next=p; q->rear=p; }

}

2）出队。

Datatype dequeue(linkqueue *q) {

datatype x;

queuenode *p; if(queueempty(q))

error(“queue is underflow”); p=q->front; x=p->data;

q->front=p->next; if(q->rear==p)

q->rear=NULL; free(p); return x; }

第 四 章 串

1. 串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；

2. 空串：长度为零的串称空串； 空白串：由一个或多个空格组成的串称空白串；

子串：串中任意个连续字符组成的子序列称该串的子串； 主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置； 3. 空串是任意串的子串； 任意串是自身的子串；

串常量在程序中只能引用但不能改变其值； 串变量取值可以改变； 4. 串的基本运算

（1） 赋值 ASSIGN(S,T),加工型运算，将串T的值传给串变量S。

（2） 判等 EQUAL(S,T),引用型运算，若S和T 的值相等则返回值为1，否则返回值为0. （3） 求长 LENGTH(S),引用型运算，求串的长度。

（4） 联接 CONCAT(S,T),引用型运算，运算结果为由S和T联接在一起形成的新串。

（5） 求子串SUBSTR(S,i,j),引用型运算，其结果是串S中从第i个字符开始的，由连续j个字符组成的子串。

（6） 插入 INSERT(S1,i,S2),加工型运算，作用是将串S2整个插入到串S1的第i个字符之后从而产生的一个新串。

（7） 删除 DELETE(S,I,j),加工新运算，作用是从串S中删去从第i个字符开始的长度为j的子串。 （8） 定位INDEX(S,T)，引用型运算，若在串S中存在一个于T相等的子串，则本运算的结果为S中第一个这样的子串中的第一个字符在S中的位置；否则，结果为0.

（9） 替换 REPLACE(S,T,R)，加工型运算，结果是在串S中处处同时以串R置换串T的所有出现所得的新串。

5. 串的存储结构： （1） 串的顺序存储 （2） 串的链接存储 第 五 章 多 维 数 组

1. 多维数组：一般用顺序存储的方式表示数组。 2. 数组的逻辑结构是线性结构的推广。 3. 数组的基本运算是：

（1） 读：给定一组下标，读取相应的数据元素；

（2） 写：给定一组下标，修改相应的数据元素。

4. 矩阵的压缩存储：值相同的多个元素只分配一个存储空间，零元素不分配空间。 （1） 特殊矩阵：值相同的元素或零元素在矩阵中分布有一定的规律的矩阵。

1） 对称矩阵：：在一个n阶的方阵A中，元素满足Aij=Aji 1<=i,j<=n;称为对称矩阵。 元素的总数为：n(n+1)/2;

2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c。 元素总数为：(n(n+1)/2)+1;

（2） 稀疏矩阵：矩阵中零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵。

第 六 章 树

1.树：是n个结点的有限集T，T为空时称空树，否则满足：

1）有且仅有一个特定的称为根的结点；

2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。 2. 树上任一个结点拥有的子树数称为该结点的度； 3.一棵树的度是指树中结点最大的度数。

4. 度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点 5.根结点称开始结点，根结点外的分支结点称内部结点；

6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；

7. 结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；一棵树中所有结点层数的最大值称为树的高度或深度；

8.树中的每个结点的子树不能更改其位置，称为有序树；反之称为无序树。 9.二叉树是结点的有穷集合，它或者是空集，或者同时满足下面两个条件： （1）有且只有一个称为根的结点；

（2）其余结点分为两个互不相交的集合T1,T2，T1和T2都是二叉树，并且T1,T2有顺序关系（T1在T2前面），它们分别称为根的左子树和右子树。 10.二叉树的特征：1 度不大于2; 2 分左，右分支。

11.度为2的有序树与二叉树的区别是：前者的子树次序是相对的，而后者是绝对的。 12.二叉树的物种形态：

13.二叉树的基本运算：

1）.初始化 2）.求根 3）求双亲 4）求左孩子和右孩子 5）建树 6）剪枝 14.二叉树的性质：

1）二叉树第i(i≥1)层上至多有2i-1个结点。 2）深度为k(k≥1)的二叉树至多有2k-1个结点。

3）对任何二叉树，若2度结点数为n2，则叶子数为n0=n2+1。 15. 满二叉树是一棵深度为k的且有2k-1个结点的二叉树；

16.完全二叉树是在一棵深度为k(k≥1)的满二叉树上删去第k层上最右边的连续j(0≤j≤2k-1)个结点。

17 .具有N个结点的完全二叉树的深度为log2N取整加1；（二叉树的第四个性质）

18.如果将一棵有n个结点的完全二叉树按层编号，则对任意编号i(1≤i≤n)的结点X有：

1）.若i=1，则结点X是根；若i>1,则X的双亲的编号为∣i/2∣.

2).若2i>n,则结点X无左孩子（且无右孩子）；否则，X的左孩子的编号为2i。 3）.若2i+1>n,则结点X无右孩子；否则，X的右孩子编号为2i+1。

19.二叉树中某一结点的左子树深度减去右子树的深度，称为该结点的平衡因子。 20.二叉树的存储结构 （1）链式存储结构：

二叉链表结点的结构为：l lchild | data | rchild ∣ ； 二叉链表由根指针唯一确定。 （2）顺序存储结构：

把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个一维数组b[0~n]中，b[1~n]存放结点，b[0]存放结点总数。 各个结点编号间的关系：

1） i=1是根结点；i>1则双亲结点是i/2取整； 2） 左孩子是2i, 右孩子是2i+1；（要小于n） 3） i>（n/2取整）的结点是叶子； 4） 奇数没有右兄弟，左兄弟是i-1； 5） 偶数没有左兄弟，右兄弟是i+1；

21.二叉树的遍历：就是按某种次序系统的“访问”二叉树上的所有结点，是每个结点恰好被“访问”一次。

22. 二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。

23.树的存储结构：

（1）孩子链表表示法是树的一种链式存储结构。

1）孩子链表表示法的思想是：树上的一个结点的内容以及指向该结点所有的孩子的指针存储在一起以便于运算的实现。

2）一个孩子链表是一个带头结点的单链表，单链表的头结点含有两个域：数据域和指针域。 （以图1为例）

数据域指针域 孩子域 指针域

（2）孩子兄弟链表表示法： （3）.双亲表示法：

24.森林通常定义为树的集合。 25. 树、森林与二叉树的转换 （1）树与二叉树的转换：

1）所有兄弟间连线；

2）保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空 （2）森林与二叉树的转换：

1）将所有树转换成二叉树； 2）将所有树根连线。

26. 树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；

后序遍历等价于中序遍历对应二叉树。

27.从树中一个结点到另一个结点之间的分支，构成这两个节点之间的路径；

路径上的分支的数目称为路径的长度。

28.结点上赋一个有实际意义的实数，称此实数为根结点的权。

29.从根结点到根结点之间的路径长度于根结点上权的积称为结点的带权路径长度。 30.树中所有叶子结点的带权路径长度之和记做树的带权路径长度。

31.n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树称为哈夫曼树（HuFFman），又叫最优二叉树。

32.对字符集进行编码时，字符集中任一个编码都不是其他字符的编码的前缀，称为前缀码。

第 七 章 图

1. 图：图G由两个集合V和E组成，记作G=(V,E)，其中V是顶点的有穷非空集合，E是边的集合，而边是V中顶点的偶对。

2. 若定点的偶对是有序的，则称此图为有向图，有序偶对用<>括起来；

若顶点偶对是无序的，则称此图为无向图，无序偶对用（）括起来。

3. 端点和邻接点：图中若存在有一条边（Vi,Vj），则称Vi,Vj为此边的两个端点，并称他们为邻接点。

4. 顶点的度，入度，出度：无向图中顶点的度定义为无向图中以该顶点为一个端点的边的数目；有向图顶点的出度是以该顶点为起始点的边的数目；入度是以该顶点为终点的边的数目。 5. 顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图；

6. 子图：设G,H是图，若V(H)包含于V(G)，E(H)包含于E(G)，则称H是G的子图，G是H的母图；如果H是G的子图且V(H)= V(G)，则称H为G的支撑子图。

7. 可及和连通分量：从顶点Vi到顶点Vj若存在路径，则称Vi和Vj可及；在无向图的顶点集中任意两个顶点都可及，则称此无向图为连通图；；极大连通子图称连通分量。

8. 在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量。 9. 权和网：为边赋一个具有某种意义的数值，成这个数值为该边的权；带权的图称为网。 10. 一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。 11. 图的存储结构：（P109）

（1） 邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。 无向图是对称矩阵；有向图行是出度，列是入度。

（2） 邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstarc,并顺序存储在一个向量中；vertex保存顶点信息，firstarc保存邻接表头指针。

12. 邻接矩阵表示法与邻接表表示法的比较： 1） 邻接矩阵是唯一的，邻接表不唯一；

2） 存储稀疏图用邻接表，存储稠密图用邻接矩阵；

3） 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便； 4） 判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；

5） 求边数e，邻接矩阵耗时为O(n^2)，与e无关，邻接表的耗时为O(e+n)； 13.图的遍历：

（1）.图的深度优先搜索：假定图中某个顶点Vi为出发点，首先访问出发点，然后任选一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索，直到图中所有结点都被访问过。 （2）.图的广度优先搜索：从图中某个顶点Vi出发，在访问了Vi之后依次访问Vi的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。 14.生成树中各边的权值和称为该树的树值。 15.权值最小的生成树称为图的最小生成树。 16.求最小生成树的方法：（书P118） （1）.普里姆（PRIM）算法：

（2）克鲁斯卡尔（kruskal）算法：

17.在有向图中，顶点表示活动，有向边表示活动之间的先后关系，称这种关系为A.O.V网。

18.拓扑序列：A.O.V网中的所有顶点排成一个顺序序列，使每个活动的所有前驱活动都排在该活动的前面。

19.构造A.O.V网拓扑序列的过程称为拓扑排序。

第 八 章 排 序

1. 文件：由一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字； 2. 排序是将文件按关键字的递增（减）顺序排列；

3. 排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序； 4. 在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序，反之称外排序； 5. 内排序的方法主要有：插入排序，交换排序，选择排序，归并排序等四类。 6. 常用的插入排序有：直接插入排序，折半插入排序，表插入排序和希尔排序。 7. 直接插入排序：依次将每个记录插入到一个有序的子序列中去。 算法中引入监视哨R[0]的作用是： 1） 保存R[i]的副本；

2） 简化边界条件，防止循环下标越界。

关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2； 算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序；

8. 交换排序：将键值较大的记录向序列尾部移动，键值较小的记录向序列的前部移动。 （1）.冒泡排序：

实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2；

算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； （2）.快速排序：

实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2；

算法的最好时间是O(nlog2n)；最坏时间是O(n^2)；平均时间是O(nlog2n)；辅助空间为O(log2n)；是一种不稳定排序；

9.选择排序：

（1）直接选择排序

实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。 关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)；

算法的最好时间是O(n^2)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的不稳定的排序；

（2） 堆排序 实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。

算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序；

9. 归并排序：要求待排序列部分有序

（1）.部分有序的含义是待排序列由若干个有序的子序列组成。

（2）.基本是想：将这些有序的子序列进行合并，从而得到有序的序列。

（3）.方法：比较各子序列的第一个记录的键值，最小的一个就是排列后序列的第一个记录的键值。取出这些记录，继续比较各子序列现在的第一个记录的键值，便可以找出排序后的第二个记录。如此继续下去，最终得到排序结果。 因此，归并的基础是合并。 10. 二路归并排序：

实现过程：如果序列中有n个记录，可以把它看成n个子序列，每个子序列中只包含一个记录。先将每相邻的两个子序列合并，得到（n/2）个较大的有序子序列，每个子序列包含2个记录。再将这些子序列两两合并，得到（（n/2）/2）个有序子序列。如此反复，直到最后合并成一个有序序列。 第 九 章 查 找

1. 查找表是一种以集合为逻辑结构，以查找为“核心”运算，同时包括其他运算的数据结构。 2. 由任意一些可辨认的对象构成的整体称为集合。

3. 集合与其他逻辑结构（线性结构，树状结构，图状结构）的根本区别：在集合这种逻辑结构中，任何结点之间都不存在逻辑关系。这也是集合这种逻辑结构的基本特点。

4. .查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。

5. 二分查找(又称折半查找)，它的算法思想：是对一有序表中的元素，从初始的查找区间开始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，则查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。

1）二分查找在等概率的情况下查找成功的平均查找长度ASL为lg(n+1)-1,在查找失败时所需比较的关键字个数不超过判定树的深度，最坏情况下查找成功的比较次数也不超过判定树的深度lg(n+1)(不小于lg(n+1)的最小整数)

2）二分查找只适用于顺序存储结构而不能用链式存储结构实现。因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

6. 二叉排序树(BST)又称二叉查找树，其定义是：二叉排序树要或者是空树或者满足如下性质的二叉树：

1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

本文来源：https://www.bwwdw.com/article/3owe.html