第一章简介
内容摘要：
数据结构研究内容。
对于非数值计算编程问题，了解计算机操作的对象以及它们之间的关系和操作。
数据结构涵盖的内容：
基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
data —— 计算机可以识别、存储和处理的所有符号的集合。
数据元素——是数据的基本单位，具有完整、明确的实际意义。
数据对象——是具有相同属性的数据元素的集合并且是数据的子集。
数据结构——是彼此之间具有一种或多种特定关系的数据元素的集合，表示如下：
数据结构=(D,R)
数据类型——是值的集合以及对这些值定义的一组操作。
抽象数据类型—— 是用户定义的数学模型以及在该模型上定义的一组操作。
由基本数据类型组成。
算法定义及五个特点。
算法—— 描述了解决特定问题的步骤。它是一组有限的指令和一组将输入转换为输出的计算步骤。
算法的基本属性：输入、输出、有限性、确定性、可行性。
算法设计要求。
准确性， 可读性， 稳健性， 效率和低存储要求。
算法分析。
时间复杂度、空间复杂度、稳定性
学*要点：
数据结构的“三要素”：逻辑结构、物理（存储）结构以及在该结构上定义的操作。
使用语句频率计算来估计算法的时间复杂度。
第2 章线性表
内容摘要：
定义线性表的逻辑结构并使用线性表定义。
线性表的定义：由数据元素的有限序列表示。
线性表的存储结构：顺序存储结构和链式存储结构。
顺序存储定义：将逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
链存储结构：内的节点在存储器中的位置是任意的。也就是说，逻辑上相邻的数据元素不一定需要物理上相邻。通过指针来完成。
在两种存储结构上实现线性表操作。
基本数据结构操作：修改、插入、删除、查找、排序
1）更改——。您可以通过数组下标访问和修改特定元素。
核心语句： V[i]=x;
序列表修改操作的时间效率为O(1)
2) Insert —— 在线性列表中的第i 个位置之前插入一个元素。
实施步骤：
将第n到第i个元素向后移动一位。
将要插入的元素写入第i个位置。
表的长度加1。
注意：必须提前判断：中的插入位置i是否合法。桌子满了吗？
必须满足条件：1in+1 或i=[1, n+1]
核心说法：
对于(j=n; j=i; j--)
a[j+1]=a[j]；
a[i]=x;
n++；
插入时平均移动次数为：n(n+1)/2(n+1)=n/2O(n)
3）移除——，移除线性表第i个位置的元素。
实施步骤：
将第i+1 到第n 个位置的元素向前移动一位。
表的长度减1。
注意：您必须提前确定删除位置i 是否合法。
必须满足条件：1in 或i=[1, n]
核心说法：
对于( j=i+1; j=n; j++ )
a[j-1]=a[j];
是的- ;
从序列表中删除元素的时间效率为：T(n)=(n-1)/2 O(n)。
顺序表插入和删除算法的平均空间复杂度为O(1)。
单链表：
(1)
使用单链表结构存储26 个字母字符（a、b、c、z）的线性列表。创建一个C语言程序。
#includesdio.h
#includestdlib.h
typedef 结构节点{
字符数据。
结构节点*下一个；
}节点；
node *p,*q,*head; //通常需要三个指针变量。
int n; //数据元素的数量
int m=sizeof(node); /*当定义了结构体类型后，每个节点类型都有固定的长度。
m只能找到一次*/
void build() //创建一个按字母顺序排列的链表。我会慢慢地把它们一一联系起来。
{
整数我；
head=(node*)malloc(m); //m=sizeof(node) 是之前计算出来的。
p=头；
for( i=1; i26; i++) //尾随节点需要特殊处理，所以i26
{
p-data=i+‘a’-1; //第一个节点值为字母a。
p-next=(node*)malloc(m); //为后续节点“挖洞”！
p=p-next;} //将指针变量P指向下一个节点
p-data=i+‘a’-1; //最后一个元素必须单独处理
p-next=NULL; //单链表结束节点的指针字段必须留空。
}
}
void display() //输出字母列表
{
p=头；
while (p) //如果指针不为空则循环（仅适用于无头节点）
{
printf('%c',p-data);
p=p-next; //继续用指针“跟随线索”。
}
}
(2) 修改（或读取）单链表
思路：要修改第i个数据元素，我们需要找到从第一个指针开始的节点的指针p。
然后您可以运行pdata=new_value。
读取第i个数据元素的核心语句是：
链接列表*find(链接列表*head,int i)
{
整数j=1；
链接列表*p；
P=下一个；
而((p!=NULL)(ji))
{
p=p-下一个；
j++;
}
返回页数。
}
3.
插入到单个链表中
链表插入的核心语句是：
步骤一：s-next=p-next；
步骤2：p-next=s；
6. 删除单个链表
删除动作的核心语句（使用辅助指针变量q）：
q=p-next; //首先，保存一个指向b的指针，可以用来查找c。
p-next=q-next; //连接两个节点a和c并删除b节点。
free(q); //b 节点上完全释放空间。
7、双向链表插入操作：
假设p 已经指向第i 个元素。在第i 个元素之前插入元素x。
ai-1的后继由ai（指针为p）改为x（指针为s） :
s-下一个=p；p-前一个-下一个=s；
ai 的前驱从ai-1（指针为p-prior）变为x（指针为s）。
s 先验=p 先验=s；
8、双向链表删除操作：
让p指向第i个元素并删除第i个元素
后继方向：ai-1的后继从ai（指针p）变为ai+1（指针p-next）。
p-上一个-下一个=p-下一个；
前驱方向：ai+1的前驱从ai（指针p）变为ai-1（指针p - before）。
p-下一个-上一个=p-上一个；
定义并保存数组的逻辑结构
数组：由一组名称相同但下标不同的变量组成。
N维数组的特点：n个下标，每个元素受n个关系约束
n 维数组可以看作是由多个n-1 维数组组成的线性表。
存储：事先约定将数组元素按照特定的顺序排列成一个序列，并将这个线性序列存储在内存中。
二维数组可以按行或列指定存储。
假设一般的二维数组是A[c1.d1, c2.d2]。
在这种情况下，行优先存储的寻址公式为：
二维数组列主存储的一般公式为：
稀疏矩阵（包括特殊矩阵）的存储和操作。
稀疏矩阵：矩阵中非零元素的数量很少（通常小于5%）
学*要点：
线性表的逻辑结构是指线性表中的数据元素之间存在线性关系。在顺序存储结构中，元素存储的顺序位置反映了这种线性关系，而在链式存储结构中，则使用指针来反映这种关系。
顺序存储结构由一维数组表示，可以通过指定下标来访问相应的元素。这是一种随机存取存储结构。
使用链表时，请小心不要意外“破坏”链。因此，如果要在节点之前插入或删除元素，则需要知道指向该元素的前驱节点的指针。
绘制节点图，学*创建、插入、删除、扫描链表（单链表、循环链表等）等操作。
行序/列序存储的数组（主要是二维）的地址计算方法。
稀疏矩阵的三表存储结构。
如何保存稀疏矩阵的交联表。
其他亮点：
1、每个存储节点包含两部分：数据域和指针域（链域）。
2. 在单向链表中，除第一个节点外的任何节点的存储位置都由其前一个节点的link 字段的值表示。
3、链表设置头节点有什么好处？
头节点是链表中连接在第一个节点之前的节点，它的数据字段可以为空，也可以存储附加信息，例如表的长度。使用链表时，对保留表、非空表和首节点的集成处理使编程更加方便。
4. 如何表示一个空表？
(1) 如果头节点不存在，头指针值为空则表示链表为空。
(2) 如果存在头节点，如果头节点的指针字段为空，则表示链表为空。
5.链表数据元素有两个字段，不是简单的数据类型。在编程中应该如何表达呢？
使用结构数据类型是因为每个节点至少有两个组件，并且数据类型通常不一致。
6.sizeof(x)—— 计算变量x的长度（以字节为单位）。
malloc(m) — 打开一个长度为m 字节的地址空间并返回该空间的首地址。
free(p) —— 释放指针p 指向的变量的存储空间。换句话说，完全删除变量。
7、链表运行效率分析：
(1) 搜索
线性链表只能顺序访问，也就是说查找时必须从第一个指针开始，查找的时间复杂度为O(n)。
(2)插入和删除
线性链表不需要移动元素，只需要改变指针，因此时间复杂度通常为O(1)。
然而，当对单链表进行正向插入或删除操作时，时间复杂度为O(n)，因为必须从头找到前驱节点。
示例：要删除n 个节点的单向链表中的已知节点*P，我们需要找到其前任节点的地址，其时间复杂度为O(n)。
8、顺序存储和链式存储有什么区别、优缺点？
当顺序存储时，逻辑上相邻的数据元素具有相邻的物理存储地址。顺序存储的优点是存储密度高、存储空间利用率高。缺点是插入或删除元素不方便。
在链式存储中，数据元素可以任意相邻存储，但是所占用的存储空间分为两部分，一部分存储节点值，另一部分存储代表节点之间关系的指针。链式存储的优点是插入或删除元素方便灵活。缺点是存储密度低，存储空间利用率低。
顺序表适用于搜索等静态操作。
链表适合插入、删除等动态操作。
当线性表的长度变化不大且主要操作是搜索时，使用序数表。
当线性表的长度变化很大且操作主要是插入和删除时，使用链表。
9. 结论：“数组比其他复杂结构更容易处理，”对吗？
答：是的。因为——
数组中每个元素的类型是统一的。
数组元素的下标一般有固定的上下界。也就是说，一旦定义了数组，它的维度和维度边界就不会改变。
数组的基本操作比较简单，只涉及初始化和销毁结构、访问元素和更改元素值。
10、三元素群表中的每个节点对应稀疏矩阵的一个非零元素，并包含三个数据项，每个数据项代表元素的行索引、列索引和元素值。
11. 描述右图稀疏矩阵的压缩存储格式。
解决方案：引入三种存储格式。
方法一：用线性表表示：
((1,2,12),(1,3,9),(3,1,-3),(3,5,14),
(4,3,24), (5,2,18), (6,1,15), (6,4,-7))
方法二：表示为相互链表
目的：对于稀疏矩阵的加法和减法很有用
How：每个非零元素占据5个字段
方法3：表示为三重矩阵：
稀疏矩阵压缩存储的缺点：失去随机访问能力
代码：
1. 编写一个C 语言程序，使用数组V 存储26 个字母字符（a、b、c、z）的线性表，并以顺序结构生成并显示该表。
字符V[30]；
void build() //生成线性字符表，即建表操作
{
整数我；
V[0]='a';
for( i=1; i=n-1; i++ )
V[i]=V[i-1]+1；
}
void display() //显示按字母顺序排列的线性表，即读表操作
{
整数我；
for( i=0; i=n-1; i++ )
printf( '%c', v[i] );
printf('\n');
}
void main(void) //主函数，生成并输出字母表线性表
{
n=26; //n是表的长度，而不是V的实际索引。
建造（）;
屏幕（ ）;
}
第3 章堆栈和队列
内容摘要：
从数据结构的角度来看，栈和队列也是线性表，它们的操作是线性表操作的子集，是操作有限的线性表。然而，从数据类型的角度来看，这些都是重要的抽象数据类型，与线性表有很大不同。
堆栈的定义和操作。堆栈是一种线性列表，其中仅允许在一端（称为堆栈顶部）进行插入和删除操作。
将元素插入栈顶的操作称为入栈。
从栈顶移除最后一个元素的操作称为出栈。
对于向上生成的堆栈：
压入栈的技巧：栈顶指针“先压入，再添加” : S[top++]=an+1
出栈提示：栈顶指针“先减后出栈” : e=S[--top]
栈顺序和链式存储结构的实现以及这两种结构下的栈操作。
顺序压栈函数PUSH()
statusPush(ElemType e)
{ if(topM){溢出}
否则s[top++]=e；
}
顺序出栈函数POP()
状态弹出()
{ if(top=L) { 下溢}
否则{ e=s[--top];}
}
队列的定义和操作是这样的：删除发生在队列的一端（队列的末尾），插入发生在队列的另一端（队列的开头）。因此，这两种存储结构都需要两个指针：开始指针和尾随指针。
队列：一种线性表，表的一端只能进行插入操作，表的另一端只能进行删除操作。
连锁提示
定义节点类型：
typedef 结构QNode{
QElemType 数据；//元素
struct QNode *next; //指向下一个节点的指针
}Qnode, * QueuePtr;
链式队列类型定义：
类型定义结构{
QueuePtr front; //队列头指针
QueuePtr back //队列结束指针；
链接队列；
连锁团队图：
空链队伍特点：前=后
连锁团队是否满员？这通常是不必要的，因为删除时有自由操作。除非你内存不足！
入队（尾部插入）：rear=S；rear=S；
Dequeue（头删除）：front-next=p-next；
2.连续组队
定义连续团队类型：
#define QUEUE-MAXSIZE 100 //最大队列长度
类型定义结构{
QElemType *base //队列基地址
intfront; //队列头指针
int反向； //队列结束指针
}SqQueue
团队建设核心宣言：
q .base=(QElemType *)malloc(sizeof (QElemType )
* QUEUE_MAXSIZE; //分配空间。
顺序团队图：
循环队列：
队伍空状态： 前=后（初始化：前=后）
全队：前=（后+1）N（N=最大尺寸）
队列长度（数据元素个数）：L=(N+前后)%N
1）初始化一个空队列
Status InitQueue(SqQueue q) //初始化一个空循环队列q
{
q .base=(QElemType *)malloc(sizeof(QElemType)
* QUEUE_MAXSIZE); //分配空间
if (!q.base) exit(OVERFLOW);//内存分配失败，退出程序
q.front=q.rear=0; //清空队列
返回正常。
} //初始化队列；
2）参与团队管理
状态EnQueue(SqQueue q, QElemType e)
{//将元素e添加到循环队列q的末尾。
if ( (q.rear+1) % QUEUE_MAXSIZE==q.front )
return ERROR; //如果队列已满，则会溢出，无法再添加到队列中。
q.rear=(q.rear + 1) % QUEUE_MAXSIZE;
q.base [ q.rear ]=e; //新元素e 被添加到队列中。
返回正常。
}//入队；
3）出队操作
状态出队（SqQueue q，QElemType e）
{//如果队列不为空，则移除循环队列q 的第一个元素。
//从e 返回值并返回OK
if ( q.front==q.rear ) return ERROR;//队列为空
q.front=(q.front+1) % QUEUE_MAXSIZE;
e=q.base [q.front] ;
返回正常。
}//出队
链式队列为空的条件是起始指针和结束指针相等。循环队列变满的条件是通过设置队列末尾加1等于队列开头来确定的。标记。
其他亮点：
1. 为什么要设计堆栈？它有什么独特的用途？
它是唯一调用函数或子程序的东西。
强大的递归运算工具。
用于保护和恢复场地。
编程问题的简化。
2. 为什么要设计队列？它们有什么独特的用途？
离散事件的模拟（模拟事件发生的顺序，如CPU芯片中的指令译码队列）。
操作系统中的作业调度（一个CPU执行多个作业）。
简化程序设计。
3.什么是“假溢出”？
答：在顺序队列中，当尾指针到达数组上限时，无法再进行队列操作，但实际上数组中还有空位置。这称为“假溢出”。假溢出——的解决方案是使用循环队列。
4、循环队列中，约定头指针指向头元素的前一个位置。当从循环队列中删除元素时，操作是移动队列的顶部位置，然后删除该元素。
5、线性表、栈、组的异同：
相似之处：逻辑结构相同，都是线性的。两者都可以使用顺序存储或链表存储。栈和队列是两种特殊的线性表，受限线性表（仅限制插入和删除操作）。
区别：操作规则的区别：
线性表是随机访问的。
堆栈只允许在一端进行插入和删除操作，使其成为后进先出表LIFO。
队列只允许一端插入，另一端删除，使其成为先进先出表FIFO。
线性表更常见，用于各种用途。堆栈用于函数调用、递归和简化设计。用于离散事件模拟、操作系统作业调度和简化设计等。
第4章字符串
内容摘要：
字符串是一个线性列表，其数据元素是字符串。
字符串是零个或多个字符的有限序列，是一种特殊的线性列表，其数据元素是一个字符。
字符串比较：int strcmp(char *s1,char *s2);
求字符串的长度：int strlen(char *s);
字符串连接：char strcat(char *to,char *from)
定位子串T： char strchr(char *s,char *c);
对于字符串的存储结构，“节点大小”是一个问题，因为字符串是线性表，其数据元素是字符。
模式匹配算法。
字符串有三种板载表示形式。
模式匹配算法：
算法的目的：确定子字符串在主字符串中的第一次出现（位置）
定位问题称为字符串模式匹配，典型的函数是Index(S,T,pos)。
实现BF算法，即创建Index(S, T, pos)函数
BF算法设计思路：
将主字符串S 的最后一个字符与模式T 的第一个字符进行比较。
如果相等，则继续一一比较后面的字符。
如果不是，则从主字符串S 的下一个字符（pos+1）开始，再次与T 的第一个字符进行比较。
直到主串S的连续子串串等于模式T。返回值是S的子序列中与T匹配的第一个字符的序号。换句话说，一场比赛就是成功的。
否则，匹配失败并返回0值。
Int Index_BP(SString S, SString T, int pos)
{ //返回主字符串S的后置字符之后子字符串T的位置。如果不存在，则该函数的值为0。
//其中，T不为空，1posStrLength(S)
我=位置；
while ( i=S[0] j=T[0] ) //如果i 和j 指针在其正常长度内，
{
if (S[i]==T[j] ) {++i, ++j } //继续比较后续字符。
else {i=i-j+2; j=1;} //如果不相等，则指针返回并重新开始匹配。
}
if(jT[0]) return i-T[0]; //T表示子串指针j成功完成，匹配成功。否则返回0。对我来说最先到达终点的情况很不寻常。
} //index_BP
其他亮点：
1、空字符串和空字符串有区别吗？
答：有区别。
空字符串是长度为零的字符串。
空白字符串是包含一个或多个空白字符“ ”（空格键）的字符串。
2.“空串是任意串的子串，任意串S是S本身的子串。除了S本身之外，S的任何其他子串都是S的合适子串。称为子串。
第6 章树和二叉树
内容摘要：
树是一种复杂的非线性数据结构，递归定义树、二叉树的基本概念和术语。
树：由一个或多个节点（n0）组成的有限集合T，只有一个节点称为根，当n1时，其余节点是不相交的有限集T1，T2，T2，它将被分裂。Tm。每个集合本身就是一棵树，称为根的子树。
二叉树：是n（n0）个节点的有限集合，由一个根节点和两个不相交的二叉树组成，分别称为左子树和右子树。
词汇表：P88
二叉树的性质和存储结构。
属性1: 二叉树的第i 层最多有2i-1 个节点(i0)。
属性2: 深度为k 的二叉树最多有2k-1 个节点(k0)。
属性3: 对于任何二叉树，如果2 度节点的数量为n2，则叶子数量(n0) 必须为n2+1。
属性4: 具有n 个节点的完全二叉树必须具有深度
性质5: 对于完全二叉树，节点从上到下、从左到右编号，编号为i 的节点编号为2i，其左子节点编号为2i，右子节点编号必须为2i。 2i+1; 父项的数量必须为i/2（除非i=1，即根）。
二叉树存储结构：
1、顺序存储结构
二叉树的节点按照“从上到下、从左到右”的方式编号，并存储在一系列连续的存储单元中。
完整/完整二叉树允许唯一的恢复。
这不是一个完整的二叉树。转换为完全二叉树。
方法很简单，如果用“虚拟节点”填充每一层中的所有空白区域，那么它们的内容就会变成空的。
缺点：浪费空间，插入删除不方便。
2、链式存储结构
这可以很容易地用二元链表来表示。存储通常从根节点开始。
优点：（1）不浪费空间，（2）易于插入和删除。
遍历二叉树。
这是指按照特定的顺序访问二叉树的所有节点，并且每个节点仅被访问一次，从而产生线性序列。
遍历规则———
二叉树由根、左子树和右子树组成，定义为D、L 和R。
如果您先被限制在左侧，然后又被限制在右侧，则您有三种实施选项。
DLR LDR LRD
前序遍历、中序遍历、后序遍历
树的内存结构，树和森林之间的遍历，以及与二叉树的相互转换。
回顾2：如何将二叉树恢复为树？
要点：逆向操作，将所有正确的孩子变成兄弟姐妹！
讨论1：如何将森林转换为二叉树？
方法一：首先将每个森林转换为二叉树，依次连接到前一个二叉树的右子树。
方法二：森林直接变成兄弟树，然后变成二叉树。
讨论2：如何将二叉树恢复到森林中？
关键点：将最右边的子树变成森林，将其余的右子树变成兄弟树。
如何储存树木和森林：
保护树木的常用方法有3种。
家长仪式 孩子仪式 孩子
子—兄弟表示法 问：树→二叉树的“连线—抹线—旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是树转换为二叉树的过程！ 树、森林的遍历： ① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。 ② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。 讨论：树若采用“先转换，后遍历”方式，结果是否一样？ 1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。 ① 先序遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先根遍历第一棵树的根结点的子树森林； 先根遍历除去第一棵树之后剩余的树构成的森林。 ② 中序遍历 若森林为空，返回； 中根遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中根遍历除去第一棵树之后剩余的树构成的森林。 ◆ 二叉树的应用：哈夫曼树和哈夫曼编码。 Huffman树：最优二叉树（带权路径长度最短的树） Huffman编码：不等长编码。 树的带权路径长度：（树中所有叶子结点的带权路径长度之和） 构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。 构造Huffman树的步骤（即Huffman算法）： (1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。 (2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。 (3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。 (4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。 具体操作步骤： 学*重点：（本章内容是本课程的重点） ◆ 二叉树性质及证明方法，并能把这种方法推广到K叉树。 ◆ 二叉树遍历，遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结点数。 ◆ 由二叉树遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树。由前序和后序序列不能唯一确定一棵二叉树。 ◆ 完全二叉树的性质。 ◆ 树、森林和二叉树间的相互转换。 ◆ 哈夫曼树的定义、构造及求哈夫曼编码。 补充： 1.满二叉树和完全二叉树有什么区别？ 答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 2.Huffman树有什么用？ 最小冗余编码、信息高效传输 第七章 图 内容提要： ◆ 图的定义，概念、术语及基本操作。 图：记为 G＝( V, E ) 其中：V 是G 的顶点集合，是有穷非空集； E 是G 的边集合，是有穷集。 术语：见课件 ◆ 图的存储结构。 1.邻接矩阵(数组)表示法 ① 建立一个顶点表和一个邻接矩阵 ② 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]。 注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。 邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 邻接矩阵法缺点：n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 2.邻接表(链式)表示法 ① 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域: ② 每个单链表还应当附设一个头结点（设为2个域），存vi信息； ③ 每个单链表的头结点另外用顺序存储结构存储。 邻接表的优点：空间效率高；容易寻找顶点的邻接点； 邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。 ◆ 图的遍历。 遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。 图常用的遍历：一、深度优先搜索；二、广度优先搜索 深度优先搜索（遍历）步骤： ① 访问起始点 v; ② 若v的第1个邻接点没访问过，深度遍历此邻接点； ③ 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。 基本思想：——仿树的先序遍历过程。 广度优先搜索（遍历）步骤： ① 在访问了起始点v之后，依次访问 v的邻接点； ② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点； ③ 直到所有顶点都被访问过为止。 ◆ 图的应用（最小生成树，最短路经） 最小生成树（MST）的性质如下：若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0ÎU，v0ÎV-U；则：(u0, v0)必在最小生成树上。 求MST最常用的是以下两种：Kruskal（克鲁斯卡尔）算法、Prim（普里姆）算法 Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。 在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。 两种常见的最短路径问题： 一、 单源最短路径—用Dijkstra（迪杰斯特拉）算法 二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法 一、单源最短路径 (Dijkstra算法)一顶点到其余各顶点（v0→j） 目的： 设一有向图G=（V, E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。 二、所有顶点之间的最短路径 可以通过调用n次Dijkstra算法来完成，还有更简单的一个算法：Floyd算法（自学）。 学*重点： 图是应用最广泛的一种数据结构，本章也是这门课程的重点。 ◆ 基本概念中，连通分量，生成树，邻接点是重点。 ① 连通图：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。 如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 ② 生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。 ③ 邻接点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。 ◆ 图是复杂的数据结构，也有顺序和链式两种存储结构：数组表示法（重点是邻接距阵）和邻接表。这两种存储结构对有向图和无向图均适用 ◆ 图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历。 ◆ 连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。 应熟练掌握prim和kruscal算法，特别是手工分步模拟生成树的生成过程。 ◆ 从单源点到其他顶点，以及各个顶点间的最短路径问题，掌握熟练手工模拟。 补充： 1.问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？ 答：是树！而且是一棵有向树！ 2.讨论：邻接表与邻接矩阵有什么异同之处？ 1. 联系：邻接表中每个链表对应于邻接矩阵中的一行， 链表中结点个数等于一行中非零元素的个数。 2. 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致）， 但邻接表不唯一（链接次序与顶点编号无关）。 3. 用途： 邻接矩阵多用于稠密图的存储 而邻接表多用于稀疏图的存储 3.若对连通图进行遍历，得到的是生成树 若对非连通图进行遍历，得到的是生成森林。 第八章 查找 内容提要： ◆ 查找表是称为集合的数据结构。是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合中。（同一类型的数据元素构成的集合） ◆ 查找表的操作：查找，插入，删除。 ◆ 静态查找表：顺序表，有序表等。 针对静态查找表的查找算法主要有:顺序查找、折半查找、分块查找 一、顺序查找（线性查找） 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。 int Search_Seq( SSTable ST , KeyType key ){ ST.elem[0].key =key; for( i=ST.length; ST.elem[ i ].key!=key; - - i ); return i; } // Search_Seq //ASL＝（1＋n）/2，时间效率为 O(n)，这是查找成功的情况: 顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL 太大，时间效率太低。 二、折半查找（二分或对分查找） 若关键字不在表中，怎样得知并及时停止查找？ 典型标志是：当查找范围的上界≤下界时停止查找。 ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以： 三、分块查找（索引顺序查找） 思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。 特点：块间有序，块内无序。 查找：块间折半，块内线性 查找步骤分两步进行： ① 对索引表使用折半查找法（因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）； 查找效率ASL分析： ◆ 动态查找表：二叉排序树，平衡二叉树。 特点：表结构在查找过程中动态生成。 要求：对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key 的记录。 ① 二叉排序树的定义 ----或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 ② 二叉排序树的插入与删除 思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功则返回。 SearchBST (K, &t) { //K为待查关键字，t为根结点指针 p=t; //p为查找过程中进行扫描的指针 while（p!=NULL）{ case { K= p->data: {查找成功，return } K< p->data : {q=p；p=p->L_child } //继续向左搜索 K> p->data : {q=p；p=p->R_child } //继续向右搜索 } } //查找不成功则插入到二叉排序树中 s =(BiTree)malloc(sizeof(BiTNode)); s->data=K; s ->L_child=NULL; s ->R_child=NULL; //查找不成功，生成一个新结点s，插入到二叉排序树叶子处 case { t=NULL： t=s; //若t为空，则插入的结点s作为根结点 K < q->data: q->L_child=s; //若K比叶子小，挂左边 K > q->data: q->R_child=s; //若K比叶子大，挂右边 } return OK } ③ 二叉排序树的删除操作如何实现？ 如何删除一个结点？ 假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针； *f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况： *p有两棵子树时，如何进行删除操作？ 设删除前的中序遍历序列为：…. PL s p PR f //显然p的直接前驱是s ，s是*p左子树最右下方的结点 希望删除p后，其它元素的相对位置不变。有两种解决方法： 法1：令*p的左子树为 *f的左子树，*p的右子树接为*s的右子树； //即 fL=PL ; SR=PR ; 法2：直接令*s代替*p // *s为*p左子树最右下方的结点 二叉排序树的 ④ 平衡二叉树的定义：又称AVL树，即它或者是一颗空树，或者是它的左子树和右子树都是平衡二叉树，且左子树与右子树的深度之差的绝对值不超过1。 平衡因子：——该结点的左子树的深度减去它的右子树的深度。 平衡二叉树的特点：任一结点的平衡因子只能取：-1、0 或 1。 如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。 平衡旋转可以归纳为四类： 学*重点： ◆ 查找表是称为集合的数据结构。因元素间关系非常松散，其操作需借助其它数据结构来实现。本章列举了三种方法（静态查找表，动态查找表）实现查找表的运算。 ◆ 顺序表因设置了监视哨使查找效率大大提高。有序表的平均查找长度不超过树的深度。 ◆ 查找的ASL ◆ 二叉排序树的形态取决于元素的输入顺序。按中序遍历可得到结点的有序序列，应熟练掌握其建立、查找，插入和删除算法。 ◆ 平衡二叉树的概念，应熟练掌握手工绘制平衡二叉树。 补充： 1.查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 2.对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 3.哪些查找方法？ 查找方法取决于表中数据的排列方式; 4.如何评估查找方法的优劣？ 用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。 ASL=∑ Pi. Ci 5.使用折半查找算法时，要求被查文件：采用顺序存贮结构、记录按关键字递增有序 6.将线性表构造成二叉排序树的优点： ① 查找过程与顺序结构有序表中的折半查找相似，查找效率高； ② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； ③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。 第九章 内部排序 内容提要： ◆ 排序的定义，排序可以看作是线性表的一种操作 排序:将一组杂乱无章的数据按一定的规律顺次排列起来。 ◆ 排序的分类，稳定排序与不稳定排序的定义。 稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。 ◆ 插入排序（直接插入、折半插入，索引表插入、希尔插入排序）。 插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 1) 直接插入排序 在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。 时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。 其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) 空间效率：仅占用1个缓冲单元——O（1） 算法的稳定性：因为25*排序后仍然在25的后面——稳定 直接插入排序算法的实现： void InsertSort ( SqList &L ) { //对顺序表L作直接插入排序 for ( i = 2; i <=L.length; i++) //假定第一个记录有序 { L.r[0]= L.r[i]; j=i-1 ; //先将待插入的元素放入“哨兵”位置 while（L[0] .key<L[j].key) { L.r[j+1]= L.r[j]; j-- ; } //只要子表元素比哨兵大就不断后移 L.r[j+1]= L.r[0]; //直到子表元素小于哨兵，将哨兵值送入 //当前要插入的位置（包括插入到表首） } } 2） 折半插入排序 既然子表有序且为顺序存储结构，则插入时采用折半查找定可加速。 优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。 时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。 空间效率：仍为 O（1） 稳 定 性： 稳定 若记录是链表结构，用直接插入排序行否？ 答：行，而且无需移动元素，时间效率更高！ 但请注意：单链表结构无法实现“折半查找” 3） 表插入排序 基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。 优点：在排序过程中不移动元素，只修改指针。 此方法具有链表排序和地址排序的特点 表插入排序算法分析： ① 无需移动记录，只需修改指针值。但由于比较次数没有减少，故时间效率仍为O(n2) 。 ② 空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。 ③ 稳定性：25和25*排序前后次序未变，稳定。 注：此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。 5）希尔（shell）排序 基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。 ◆ 交换排序（冒泡排序、快速排序）。 交换排序的基本思想是：两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。 1) 冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构 冒泡排序的算法分析： 时间效率：O（n2) —因为要考虑最坏情况 空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定 —25和25*在排序前后的次序未改变 冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾），还可以对前面的元素作一些整理，所以比一般的排序要快。 2） 快速排序 基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！ 前提：顺序存储结构 时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加 空间效率：O（log2n）—因为递归要用栈(存每层low，high和pivot) 稳 定 性： 不 稳 定 —因为有跳跃式交换。 ◆ 选择排序（简单选择排序、树形选择排序、堆排序）。 选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。 1）简单选择排序 思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。 ——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构 Void SelectSort(SqList &L ) { for (i=1; i<L.length; ++i){ j = SelectMinKey(L,i); if( i!=j ) r[i] «r[j]; } //for } //SelectSort 2）锦标赛排序 (又称树形选择排序) 基本思想：与体育比赛时的淘汰赛类似。 首先对 n 个记录的关键字进行两两比较，得到 én/2ù 个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这 én/2ù 个较小者之间再进行两两比较，…，如此重复，直到选出最小关键字的记录为止。 优点：减少比较次数，加快排序速度 缺点：空间效率低 3）堆排序 1.堆的定义：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 解释：如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。 2. 怎样建堆？ 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。 堆排序算法分析： 时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。 学*要点： ◆ 各种排序所基于的基本思想。 ◆ 在“最好”和“最差”情况下，排序性能的分析，是否是稳定排序的结论，时间效率和空间效率。 ◆ 对每种排序方法的学*，应掌握其本质（排序所基于的思想），熟练掌握手工模拟各种排序的过程。 补充： 1.排序算法的好坏如何衡量？ 时间效率——排序速度（即排序所花费的全部比较次数） 空间效率——占内存辅助空间的大小 稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。 2.“快速排序”是否真的比任何排序算法都快？ ——基本上是，因为每趟可以确定的数据元素是呈指数增加的。 版权声明：本文转载于网络，版权归作者所有，如果侵权，请联系本站编辑删除