数据结构与算法笔记
包含课程与自学笔记
2025-05-28
《数据结构：Java语言描述》笔记
第1章 绪论
逻辑结构用接口来展现。
数据元素：基本组织单位。
数据项：最小单位，组成了数据元素。
数据对象：性质相同的数据元素的集合。
数据结构：相互之间存在一种或多种关系的数据元素的集合。按逻辑关系分为：
- 线性结构：1对1，前趋与后继
- 树形结构：1对多
- 图状结构：多对多
- 集合结构：松散
逻辑结构可定义为(D, R)。
数据关系映射到存储结构中，有以下几种：
- 顺序映象：元素存放在连续的物理存储单元，与其逻辑上的相邻关系一致。
- 链式映象：用指针表示后继关系，存放是不连续的。
存储结构一般分为顺序存储和链式存储。
抽象数据类型（ADT）=数据的集合+对应操作的集合。用Java接口描述ADT。
描述算法的方式：伪代码、自然语言、流程图、程序代码。
问题规模用整数n表示，时间复杂度T(n)是问题规模的函数，其上界表示为O(f(n))。
第2章 线性表
线性表IList
线性表由n个同类型元素构成，有且只有一个首元素与尾元素，除首尾元素外每个元素都有一个前驱一个后继。Java接口为IList。
线性表基本操作：置空clear()、判空isEmpty()、求线性表长度length()、取元素get(i)、插入insert(i, x)、删除remove(i)、查找indexOf(x)、输出display()。
一般用有序对<a_i, a_{i+1}>来表示逻辑上的相邻关系。
顺序表SqList
// 顺序线性表及其基本操作，顺序表就地逆置，顺序表右移k位
public class SqList implements IList {
private Object[] listElem; // 线性表存储空间
private int curLen; // 当前长度
// 顺序表的构造函数，构造一个存储空间容量为maxSize的线性表
public SqList(int maxSize) {
curLen = 0; // 置顺序表的当前长度为0
listElem = new Object[maxSize];// 为顺序表分配maxSize个存储单元
}
// 将一个已经存在的线性表置成空表
public void clear() {
curLen = 0; // 置顺序表的当前长度为0
}
// 判断当前线性表中数据元素个数是否为0,若为0则函数返回true，否则返回false
public boolean isEmpty() {
return curLen == 0;
}
// 求线性表中的数据元素个数并由函数返回其值
public int length() {
return curLen; // 返回顺序表的当前长度
}
// 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常
public Object get(int i) throws Exception {
if (i < 0 || i > curLen - 1) // i小于0或者大于表长减1
throw new Exception("第" + i + "个元素不存在"); // 输出异常
return listElem[i]; // 返回顺序表中第i个数据元素
}
// 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x
public void insert(int i, Object x) throws Exception {
if (curLen == listElem.length) // 判断顺序表是否已满
throw new Exception("顺序表已满");// 输出异常
if (i < 0 || i > curLen) // i小于0或者大于表长
throw new Exception("插入位置不合理");// 输出异常
for (int j = curLen; j > i; j--)
listElem[j] = listElem[j - 1];// 插入位置及之后的元素后移
listElem[i] = x; // 插入x
curLen++;// 表长度增1
}
// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
if (i < 0 || i > curLen - 1) // i小于1或者大于表长减1
throw new Exception("删除位置不合理");// 输出异常
for (int j = i; j < curLen - 1; j++)
listElem[j] = listElem[j + 1];// 被删除元素之后的元素左移
curLen--; // 表长度减1
}
// 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1 public int indexOf(Object x) {
int j = 0;// j为计数器
while (j < curLen && !listElem[j].equals(x))
// 从顺序表中的首结点开始查找，直到listElem[j]指向元素x或到达顺序表的表尾
j++;
if (j < curLen)// 判断j的位置是否位于表中
return j; // 返回x元素在顺序表中的位置
else
return -1;// x元素不在顺序表中
}
// 输出线性表中的数据元素
public void display() {
for (int j = 0; j < curLen; j++)
System.out.print(listElem[j] + " ");
System.out.println();// 换行
}
// 实现对顺序表就地逆置
public void reverse() {
for (int i = 0,j=curLen-1; i < j; i++,j--) {
Object temp = listElem[i];
listElem[i] = listElem[j];
listElem[j] = temp;
}
}
}
用顺序存储的线性表称为顺序表。
线性表的顺序存储：存储单元地址连续、依次存放。Java接口的实现类为SqList。
-
线性表的起始地址称为线性表的基地址。对应位序号为0。
-
计算地址：\mathrm{L} \mathrm{O} \mathrm{C} \left( \mathrm{a}_{i} \right)=\mathrm{L} \mathrm{O} \mathrm{C} \left( \mathrm{a}_{i-1} \right) +\mathrm{C}，其中\mathrm{C}为一个数据元素所占存储量。
顺序表的特点：
-
以物理位置的相邻映射逻辑上的相邻。
-
存储密度高。便于随机存取（通过首地址和元素的位序号可在
O(1)时间内找到指定元素）。
[!TIP] 存储密度 d=\frac{\text{数据元素的值所需空间}}{\text{该元素实际所需空间}}
- 不便于插入删除操作（会引起大量结点移动）。
顺序表的插入操作和删除操作都使用平均O(n)时间；查找操作使用平均O(n)时间。
[!Question] 循环右移k位 编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为(a_1,a_2,\dots ,a_{n-k},a_{n-k+1},\dots ,a_n)，循环向右移动k位后变成(a_{n-k+1},\dots ,a_n,a_1,a_2,\dots ,a_{n-k})。要求时间复杂度为O(n)。
// 实现对顺序表右移k位
public void shit(int k) {
int n=curLen,p=0,i,j,l;
Object temp;
for(i=1;i<=k;i++)
if(n%i==0&&k%i==0) //求n和k的最大公约数p
p=i;
for(i=0;i<p;i++){
j=i;
l=(i+n-k)%n;
temp=listElem[i];
while(l!=i){
listElem[j]=listElem[l];
j=l;
l=(j+n-k)%n;
}// 循环右移一步
listElem[j]=temp;
}
}
[!Question] 循环左移p位（例2.9） 先将由n个整数构成的数组R逆置，再把R中的前n-p位和后p位分别进行逆置，即得结果。
时间复杂度
O(n)，空间复杂度O(1)。
链表LinkList
用链式存储的线性表是链表。
单链表LinkList
// 单链表的结点
public class Node {
public Object data; // 存放结点值
public Node next; // 后继结点的引用
public Node() { // 无参数时的构造函数
this(null, null);
}
public Node(Object data) { // 构造值为data的结点
this(data, null);
}
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
// 带头结点的单链表及其基本操作，头插法就地逆置
public class LinkList implements IList {
public Node head;// 单链表的头指针
// 单链表的构造函数
public LinkList() {
head = new Node(); // 初始化头结点
}
public LinkList(int n, boolean Order) throws Exception {
this();// 初始化头结点
if (Order) // 用尾插法顺序建立单链表
create1(n);
else
// 用头插法逆位序建立单链表
create2(n);
}
// 用尾插法顺序建立单链表。其中n为该单链表的元素个数
public void create1(int n) throws Exception {
Scanner sc = new Scanner(System.in);// 构造用于输入的对象
for (int j = 0; j < n; j++)
// 输入n个元素的值
insert(length(), sc.next());// 生成新结点,插入到表尾
}
// 用头插法逆位序建立单链表。其中n为该单链表的元素个数
public void create2(int n) throws Exception {
Scanner sc = new Scanner(System.in);// 构造用于输入的对象
for (int j = 0; j < n; j++)
// 输入n个元素的值
insert(0, sc.next());// 生成新结点,插入到表头
}
// 将一个已经存在的带头结点单链表置成空表
public void clear() {
head.data=null;
head.next=null;
}
// 判断当前带头结点的单链表是否为空
public boolean isEmpty() {
return head.next == null;// 判断首结点是否为空
}
// 求带头结点单链表中的数据元素个数并由函数返回其值
public int length() {
Node p = head.next;// 初始化,p指向首结点,length为计数器
int length = 0;
while (p != null) {// 从首结点向后查找，直到p为空
p = p.next;// 指向后继结点
++length;// 长度增1
}
return length;
}
// 读取带头结点单链表中的第i个数据元素
public Object get(int i) throws Exception {
Node p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (p != null && j < i) {// 从首结点向后查找，直到p指向第i个元素或p为空
p = p.next;// 指向后继结点
++j;// 计数器的值增1
}
if (j > i || p == null) { // i小于0或者大于表长减1
throw new Exception("第" + i + "个元素不存在");// 输出异常
}
return p.data;// 返回元素p
}
// 在带头结点单链表中第i个数据元素之前插入一个值为x的数据元素
public void insert(int i, Object x) throws Exception {
Node p = head;// 初始化p为头结点,j为计数器
int j = -1; // 第i个结点前驱的位置
while (p != null && j < i - 1) {// 寻找i个结点的前驱
p = p.next;
++j;// 计数器的值增1
}
if (j > i - 1 || p == null) // i不合法
throw new Exception("插入位置不合理");// 输出异常
Node s = new Node(x); // 生成新结点
s.next=p.next;// 插入单链表中
p.next=s;
}
// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
Node p = head;// p指向要删除结点的前驱结点
int j = -1;
while (p.next != null && j < i - 1) {// 寻找i个结点的前驱
p = p.next;
++j;// 计数器的值增1
}
if (j > i - 1 || p.next == null) { // i小于0或者大于表长减1
throw new Exception("删除位置不合理");// 输出异常
}
p.next=p.next.next;// 删除结点
}
// 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1
public int indexOf(Object x) {
Node p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (p != null && !p.data.equals(x)) {// 从单链表中的首结点元素开始查找，直到p.data指向元素x或到达单链表的表尾
p = p.next;// 指向下一个元素
++j;// 计数器的值增1
}
if (p != null)// 如果p指向表中的某一元素
return j;// 返回x元素在顺序表中的位置
else
return -1;// x元素不在顺序表中
}
// 输出线性表中的数据元素
public void display() {
Node node = head.next;// 取出带头结点的单链表中的首结点元素
while (node != null) {
System.out.print(node.data + " ");// 输出数据元素的值
node = node.next;// 取下一个结点
}
System.out.println();
}
// 在非递减的有序单链表中插入一个值为x的数据元素，并使单链表仍保持有序的操作
//方法一
public void insert(int x) {
Node p = head.next;
Node q = head;// q用来记录p的前驱结点
int temp;
while (p != null) {
temp = ((Integer) p.data).intValue();
if (temp < x) {
q = p;
p = p.next;
} else
break;
}
Node s = new Node(x); // 生成新结点
s.next=p;// 将s结点插入到单链表的q结点与p结点之间
q.next=s;
}
// 在非递减的有序单链表中插入一个值为x的数据元素，并使单链表仍保持有序的操作
//方法二
public void insert1(int x) {
Node p = head.next;
while (p.next != null&&((Integer) p.next.data).intValue()<x) {
p = p.next;
}
Node s = new Node(x); // 生成新结点
s.next=p.next;// 将s结点插入到单链表的q结点与p结点之间
p.next=s;
}
// 实现对单链表就地逆置(采用的是头插法)
public void reverse() {
Node p = head.next;
head.next=null;
Node q;
while (p != null) {
q = p.next;
p.next=head.next;
head.next=p;
p = q;
}
}
// 实现删除单链表中数据域值等于x的所有结点的操作，并返回被删除结点的个数
public int removeAll(Object x) {
Node p = head.next;// 初始化,p指向首结点,j为计数器
Node q = head; // 用来记录p的前驱结点
int j = 0;// 用来记录被删除结点的个数
while (p != null) { // 从单链表中的首结点开始对整个链表遍历一次
if ((p.data).equals(x)) {
q.next=p.next;
++j;// 计数器的值增1
} else
q = p;
p = p.next;// 指向下一个元素
}
return j;// 返回被删除结点的个数
}
}
// 不带头结点的单链表及其基本操作
public class LinkList2 implements IList {
public Node head;// 单链表的首结点指针
// 构造函数
public LinkList2() {
head = null;
}
// 将一个已经存在的单链表置成空表
public void clear() {
head = null;
}
// 判断当前单链表是否为空
public boolean isEmpty() {
return head == null;
}
// 求单链表中的数据元素个数并由函数返回其值
public int length() {
Node p = head;// 初始化,p指向首结点,length为计数器
int length = 0;
while (p != null) {// 从首结点向后查找，直到p为空
p = p.next;// 指向后继结点
++length;// 长度增1
}
return length;
}
// 读取单链表中的第i个数据元素
public Object get(int i) throws Exception {
Node p = head;// 初始化,p指向首结点,j为计数器
int j = 0;
while (p != null && j < i) {// 从首结点向后查找，直到p指向第i个元素或p为空
p = p.next;// 指向后继结点
++j;// 计数器的值增1
}
if (j > i || p == null) // i小于0或者大于表长减1
throw new Exception("第" + i + "个元素不存在");// 输出异常
return p.data;// 返回元素p
}
// 在单链表中第i个数据元素之前插入一个值为x的数据元素
public void insert(int i, Object x) throws Exception {
Node s = new Node(x);
if (i == 0) { // 插入位置为表头
s.next=head;
head = s;
return;
}
Node p = head;
int j = 0;// 第i个结点前驱的位置
while (p != null && j < i - 1) {// 寻找i个结点的前驱
p = p.next;
++j;
}
if (j > i - 1 || p == null)
throw new Exception("插入位置不合理");
// 插入位置为表的中间或表尾
s.next=p.next;
p.next=s;
}
// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
Node p = head;// 初始化p为首结点,j为计数器
Node q = null; // 用来记录p的前驱结点
int j = 0;
while (p != null && j < i) {// 寻找i个结点
q = p;
p = p.next;
++j;// 计数器的值增1
}
if (j > i || p == null) // i小于0或者大于表长减1
throw new Exception("删除位置不合理");// 输出异常
if (q == null)
head = null;// 删除首结点
else
q.next=p.next;// 删除其他结点
}
// 实现删除单链表中数据域值等于x的第一个结点的操作。若删除成功，则返回被删除结点的位置；否则，返回-1。
public int remove(Object x) {
Node p = head;// 初始化,p指向首结点
Node q=null; //q用来记录p的前驱结点
int j = 0; //j为计数器
while (p != null && !p.data.equals(x)) {// 从单链表中的首结点元素开始查找，直到p.data指向元素x或到达单链表的表尾
q=p;
p = p.next;// 指向下一个元素
++j;// 计数器的值增1
}
if (p!=null&&q==null) //删除的是单链表中的首结点
head=p.next;
else if (p != null) {// 删除的是单链表中的非首结点
q.next=p.next;
}
else
return -1;//值为x的结点在单链表中不存在
return j;
}
// 在不带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1
public int indexOf(Object x) {
Node p = head;// 初始化,p指向首结点,j为计数器
int j = 0;
while (p != null && !p.data.equals(x)) {// 从单链表中的首结点元素开始查找，直到p.data指向元素x或到达单链表的表尾
p = p.next;// 指向下一个元素
++j;// 计数器的值增1
}
if (p != null)// 如果p指向表中的某一元素
return j;// 返回x元素在顺序表中的位置
else
return -1;// x元素不在顺序表中
}
// 输出线性表中的数据元素
public void display() {
Node node = head;// 取出带头结点的单链表中的首结点元素
while (node != null) {
System.out.print(node.data + " ");// 输出数据元素的值
node = node.next;// 取下一个结点
}
System.out.println();// 换行
}
}
单链表是一种顺序存取结构。
每个数据元素由元素本身及指向后继元素位置的指针组成。
线性表中第一个数据元素的存储地址作为线性表的地址，称为线性表的头指针。有时在首结点前虚加一个头结点，把指向头结点的指针称为头指针。
- 线性表为空时，头结点的指针域为空。
[!NOTE] 带头结点时，头指针是头结点的指针，它指向首结点。
单链表的查找操作分为按位序号查找get(i)和按值查找indexOf(x)。都使用平均O(n)时间。
单链表的插入操作insert(i, x)是将元素x插入到第i个结点（不包括头结点）前面的操作。使用平均O(n)时间。
- 如果单链表不含头结点，在实现插入操作时要对首结点单独处理。
单链表的删除操作remove(i)需要处理待删结点的前驱。使用平均O(n)时间。
-
同样地，如果单链表不含头结点，那么要对首结点单独处理。
-
可以将功能改为删除值为
x的结点，此时需要重载方法。
单链表的创建有两种方法：create1(n)和create2(n)，实质都是“逐个插入”，即不断调用insert(i, x)方法。
[!TIP] 尾插法（顺位序法）、头插法（逆位序法）创建单链表
- 头插法每次将新结点插入到当前单链表表头。Java实现为
create2(n)方法。使用平均O(n)时间。- 尾插法每次将新结点插入到当前单链表表尾。Java实现为
create1(n)方法。使用平均O(n)时间。
[!Question] 单链表元素去重
removeRepeatElem(L)建立一个单链表，然后删除单链表中“多余”的数据元素，即使操作之后的单链表中所有元素的值都不相同。
// 删除单链表中"多余"的数据元素
private static void removeRepeatElem(LinkList L) throws Exception {
Node p = L.head.next, q;// 初始化,p指向首结点
while (p != null) {// 从首结点向后查找，直到p为空
int order = L.indexOf(p.data);// 记录p在单链表中的位置
q = p.next;
while (q != null) {
if ((p.data).equals(q.data))// 删除重复数据结点
L.remove(order + 1);
else
++order;
q = q.next;
}
p = p.next;
}
}
[!Question] 对带头结点的单链表就地逆置
reverse()所谓逆置，就是把（a1,a2,…,an）变成（an,an-1,…,a1）；所谓就地，就是指逆置后的结点仍存储在原来单链表的存储空间中，只不过通过修改链来改变单链表中每一个结点之间的逻辑位置关系。
// LinkList#reverse()方法实现对单链表就地逆置
public class Exercise2_3_4 {
public static void main(String[] args) throws Exception {
LinkList L = new LinkList();
for (int i = 0; i <= 8; i++)
L.insert(i, i);
System.out.println("逆置前单链表中的各个数据元素为：");
L.display();
L.reverse();
System.out.println("逆置后单链表中的各个数据元素为：");
L.display();
}
}
[!Question] 寻找两个单链表的首个公共结点 已知两个链表长度后，假设其中一个比另一个长k个结点。先在较长链表上遍历k个结点后，再开始两个链表同步遍历。这样两个链表遍历时会同时到达它们的尾结点（若存在公共结点，就是首个公共结点了）。
时间复杂度
O(m+n)。
[!Question] 两个有序链表的合并
mergeList_L(LA, LB)将两个有序的单链表LＡ（有m个元素）和LＢ（有n个元素）其元素均以从小到大的升序排列，合并成一个有序单链表LA。
// 归并两个按值非递减排列的带头结点的单链线性表LA和LB，得到新的带头结点单链表LA，LA元素也按值非递减排列，并返回LA
public static LinkList mergeList_L(LinkList LA, LinkList LB) {
Node pa = LA.head.next;// 初始化，pa为LA的首结点
Node pb = LB.head.next;// 初始化，pb为LB的首结点
Node pc = LA.head;// 用LA的头结点，初始化pc
int da, db;// 元素值所对应的浮点数
while (pa != null && pb != null) {// pa和pb同时非空
da = Integer.valueOf(pa.data.toString());// 把字符串转化成浮点数
db = Integer.valueOf(pb.data.toString());// 把字符串转化成浮点数
if (da <= db) {
pc.next=pa;// 将LA中的结点加入到新的LA中
pc = pa;
pa = pa.next;
} else {
pc.next=pb;// 将LB中的结点加入到新的LA中
pc = pb;
pb = pb.next;
}
}
pc.next=(pa != null ? pa : pb); // 插入剩余结点
return LA;
}
[!Question] 单链表求倒数第k位元素 先创建两个指向头结点的指针
p和q，再令q沿着链表向后移动k位，接着让两个指针开始同时向后移动。当q到达尾结点时，p指向的就是目标结点。
[!Question] 一元多项式的加法
// 多项式类继承于单链表
public class PolynList extends LinkList {
// 创建多项式有序链表
public PolynList(int n) throws Exception {
head.data=new PolynNode(0, -1); // 初始化头结点中的数据元素
Scanner sc = new Scanner(System.in);// 构造用于输入的对象
for (int i = 1; i <= n; i++) {// 输入n个元素的值
double coef = sc.nextDouble(); // 系数值
int expn = sc.nextInt(); // 指数值
insert(new PolynNode(coef, expn));// 插入到有序链表
}
}
// 按指数从小到大的顺序插入到多项式有序链表
public void insert(PolynNode e) throws Exception {
int j = 0;
while (j < length()) {// 与有序链表中的已有项进行指数比较
PolynNode t = (PolynNode) get(j);
if (t.expn > e.expn)
break;
j++;
}
insert(j, e);// 调用父类的插入函数
}
// 判定函数，比较多项式中，两项的指数。依a的指数值小于、等于和大于b的指数值，分别返回-1,0和+1
public int cmp(PolynNode a, PolynNode b) {
if (a.expn < b.expn)// a、b的指数相比较
return -1;
else if (a.expn == b.expn)
return 0;
else
return 1;
}
// 多项式加法：Pa = Pa + Pb,利用两个多项式的结点构成的"和多项式"，并返回LA
public PolynList addPolyn(PolynList LA, PolynList LB) {
Node ha = LA.head; // ha指向新形成链的尾结点
Node qa = LA.head.next; // qa指向LA中需要计算的当前项
Node qb = LB.head.next;// qb指向LB中需要计算的当前项
while (qa != null && qb != null) { // qa、qb同时非空
PolynNode a = (PolynNode) qa.data;
PolynNode b = (PolynNode) qb.data;
switch (cmp(a, b)) {
case -1: // 多项式LA中当前结点的指数值小
ha.next=qa;
ha = qa;
qa = qa.next;
break;
case 0: // 两者的指数值相等
double sum = a.coef + b.coef; // 求系数的和
if (sum != 0.0) { // 修改多项式LA中当前结点的系数值
a.coef=sum;
ha.next=qa;
ha = qa;
qa = qa.next; // 指向下一结点
qb = qb.next;
} else { // 删除多项式LA中的当前项
qa = qa.next;// 指向下一结点
qb = qb.next;
}
break;
case 1: // 多项式LB当前结点的指数值小
ha.next=qb;
ha = qb;
qb = qb.next;
break;
}
}
ha.next=(qa != null ? qa : qb); // 插入剩余结点
return LA;
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
System.out.println("请输入A多项式的项数：");
int m = sc.nextInt(); // 记录A多项式的项数
System.out.println("请分别输入多项式A各项的系数和指数：");
PolynList LA = new PolynList(m);
System.out.println("请输入B多项式的项数：");
int n = sc.nextInt();
System.out.println("请分别输入多项式B各项的系数和指数：");
PolynList LB = new PolynList(n);// 创建多项式LB
LA = LA.addPolyn(LA, LB); // 对多项式LA、LB求和，并赋给LA
System.out.println("求和后的多项式各项为： ");
LA.display(); // 打印LA中的项
}
// 重载父类display()方法
public void display() {
for (int i = 0; i < length(); i++) {
try {
PolynNode e = (PolynNode) get(i);
System.out.println("系数为： " + e.coef + " 指数为： " + e.expn);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
// 多项式的结点,作为链表(LNode)的数据元素(data)
public class PolynNode {
public double coef; // 系数
public int expn; // 指数
public PolynNode(double coef, int expn) { // 构造函数
this.coef = coef;
this.expn = expn;
}
}
// 以带头结点的循环链表为存储结构的多项式
public class Polyn {
private CircleLinkList cList;// 表示多项式的循环链表
public Polyn() {
}
public Polyn(CircleLinkList cList) throws Exception {
this.cList = cList;
}
// 构造循环链表表示的多项式，参数分别为系数以及指数数组
public CircleLinkList creatPolyn(double[] coefs, int[] expns) throws Exception {
cList = new CircleLinkList();
// 初始化多项式
for (int i = 0; i < coefs.length; i++) {
PolynNode node = new PolynNode(coefs[i], expns[i]);
cList.insert(i, node);
}
return cList;
}
// 把一个多项式分解成两个多项式，并且各自仅含奇次项或偶次项，并返回一个一维数组，其中数组中第一个数据元素为奇次项多项式，第二个为偶次项多项式
public CircleLinkList [] separatePolyn(CircleLinkList cList) {
CircleLinkList cList1 = new CircleLinkList();// 含奇次项的多项式
Node p1 = cList1.head; // p2指向奇次项多项式的头结点
CircleLinkList cList2 = new CircleLinkList();// 含偶次项的多项式
Node p2 = cList2.head; // p2指向偶次项多项式的头结点
Node p = cList.head.next; // 原多项式的首结点
while (p!=cList.head) {
PolynNode data = (PolynNode) p.data;
int expn = data.expn;
if (expn % 2 != 0) { // 加入奇次项多项式
p1.next=p;
p1 = p;
} else {// 加入偶此项多项式
p2.next=p;
p2 = p;
}
p = p.next;
}
p1.next=cList1.head;
p2.next=cList2.head;
CircleLinkList[] polyns = { cList1, cList2 };
return polyns;
}
// 输出多项式
public void display(CircleLinkList cList) {
Node p = cList.head.next;// 多项式的首结点
while (p!=cList.head){
PolynNode e = (PolynNode) p.data;
System.out.println("系数为： " + e.coef + " 指数为： " + e.expn);
p=p.next;
}
}
}
单循环链表CircleLinkList
// 带头结点的循环链表及其基本操作
public class CircleLinkList implements IList {
public Node head;// 循环单链表的头指针
// 循环单链表的构造函数
public CircleLinkList() {
head = new Node(); // 初始化头结点
head.next=head;
}
// 将一个已经存在的带头结点的循环单链表置成空表
public void clear() {
head.next=head;
}
// 判断当前带头结点的循环单链表是否为空
public boolean isEmpty() {
return head.next.equals(head);
}
// 求带头结点的循环单链表中的数据元素个数并由函数返回其值
public int length() {
Node p = head.next;// 初始化,p指向首结点,length为计数器
int length = 0;
while (!p.equals(head)) {// 从首结点向后查找，直到p指向头结点
p = p.next;// 指向后继结点
++length;// 长度增1
}
return length;
}
// 读取带头结点的循环单链表中的第i个数据元素
public Object get(int i) throws Exception {
Node p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (!p.equals(head) && j < i) {// 从首结点向后查找，直到p指向第i个元素或p指向头结点
p = p.next;// 指向后继结点
++j;// 计数器的值增1
}
if (j > i || p.equals(head)) { // i小于0或者大于表长减1
throw new Exception("第" + i + "个元素不存在");// 输出异常
}
return p.data;// 返回元素p
}
// 在带头结点的循环单链表中第i个数据元素之前插入一个值为x的数据元素
public void insert(int i, Object x) throws Exception {
Node p = head;// 初始化p为头结点,j为计数器
int j = -1; // 第i个结点前驱的位置
while ((!p.equals(head) || j == -1) && j < i - 1) {// 寻找i个结点的前驱
p = p.next;
++j;// 计数器的值增1
}
if (j > i - 1 || (p.equals(head) && j != -1)) // i不合法
throw new Exception("插入位置不合理");// 输出异常
Node s = new Node(x); // 生成新结点
s.next=p.next;// 插入单链表中
p.next=s;
}
// 将循环单链表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
Node p = head;// p指向要删除结点的前驱结点
int j = -1;
while ((!p.next.equals(head) || j == -1) && j < i - 1) {// 寻找i个结点的前驱
p = p.next;
++j;// 计数器的值增1
}
if (j > i - 1 || (p.next).equals(head)) { // i小于0或者大于表长减1
throw new Exception("删除位置不合理");// 输出异常
}
p.next=p.next.next;// 删除结点
}
// 在带头结点的循环单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1
public int indexOf(Object x) {
Node p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (!p.equals(head) && !p.data.equals(x)) {// 从单链表中的首结点元素开始查找，直到p.data指向元素x或到达单链表的表尾
p = p.next;// 指向下一个元素
++j;// 计数器的值增1
}
if (!p.equals(head))// 如果p指向表中的某一元素
return j;// 返回x元素在顺序表中的位置
else
return -1;// x元素不在顺序表中
}
// 输出循环链表中的数据元素
public void display() {
Node node = head.next;// 取出带头结点的单链表中的首结点元素
while (!node.equals(head)) {
System.out.print(node.data + " ");// 输出数据元素的值
node = node.next;// 取下一个结点
}
System.out.println();// 换行
}
}
尾结点的指针域指向的是头结点（注意不是首结点），形成循环链表。
- 对于空循环链表，头结点的指针域指向头结点自身。这可作为循环链表的判空条件。
与单链表主要区别：判别是否为尾结点的条件由“后继是否为空”转变为“后继是否为头结点”。
用头指针表示的单循环链表寻找首结点需要O(1)时间，寻找尾结点需要O(n)时间。而用尾指针表示的单循环链表寻找首结点或尾结点都只需要O(1)时间。
两个单循环链表的合并
[!Question] 判断单链表是否存在环路 创建两个指向头结点的指针
p和q。p为慢指针，每次前进1步，q为快指针，每次前进两步。通过迭代让两个指针沿链表前进，若某一刻快指针追上了慢指针，说明存在环路。
双向循环链表DuLinkList
// 双向链表的结点
public class DuLNode {
public Object data;// 存放结点值
public DuLNode prior; // 前驱结点的引用
public DuLNode next; // 后继结点的引用
public DuLNode() {// 无参数时的构造函数
this(null);
}
public DuLNode(Object data) {// 构造值为data的结点
this.data = data;
this.prior = null;
this.next = null;
}
}
// 双向循环链表及其基本操作
public class DuLinkList implements IList {
public DuLNode head;// 双向循环链表的头结点
// 双向链表的构造函数
public DuLinkList() {
head = new DuLNode(); // 初始化头结点
head.prior=head;// 初始化头结点的前驱和后继
head.next=head;
}
// 从表尾到表头逆向建立双向链表的算法。其中n为该双向链表的元素个数
public DuLinkList(int n) throws Exception {
this();
Scanner sc = new Scanner(System.in);// 构造用于输入的对象
for (int j = 0; j < n; j++)
insert(0, sc.next());// 生成新结点,插入到表头
}
// 在双向循环链表的第i个数据元素之前插入一个值为x的数据元素，i等于表长时，p指向头结点；i大于表长时，p=NULL。
// 其中i取值范围为：0≤i≤length()。当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x
public void insert(int i, Object x) throws Exception {
DuLNode p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (!p.equals(head) && j < i) {// 寻找插入位置i
p = p.next;// 指向后继结点
++j;// 计数器的值增1
}
if (j != i && !p.equals(head)) // i小于0或者大于表长
throw new Exception("插入位置不合理");// 输出异常
DuLNode s = new DuLNode(x);// 生成新结点
p.prior.next=s;
s.prior=p.prior;
s.next=p;
p.prior=s;
}
// 将双向循环链表中第i个数据元素删除。其中i 取值范围为：0≤i≤ength()-1
public void remove(int i) throws Exception {
DuLNode p = head.next;// 初始化,p指向首节点结点,j为计数器
int j = 0;
while (!p.equals(head) && j < i) {// 寻找删除位置i
p = p.next;// 指向后继结点
++j;// 计数器的值增1
}
if (j != i) // i小于0或者大于表长减1
throw new Exception("删除位置不合理");// 输出异常
p.prior.next=p.next;
p.next.prior=p.prior;
}
// 将一个已经存在的双向循环链表置成空表
public void clear() {
head.prior=head;
head.next=head;
}
// 判断当前双向循环链表是否为空
public boolean isEmpty() {
return head.equals(head.next);
}
// 读取双向循环链表中的第i个数据元素
public Object get(int i) throws Exception {
DuLNode p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (!p.equals(head) && j < i) {// 从首结点向后查找，直到p指向第i个元素或p指向头结点
p = p.next;// 指向后继结点
++j;// 计数器的值增1
}
if (j > i || p.equals(head)) { // i小于0或者大于表长减1
throw new Exception("第" + i + "个元素不存在");// 输出异常
}
return p.data;// 返回元素p
}
// 求双向循环链表中的数据元素个数并由函数返回其值
public int length() {
DuLNode p = head.next;// 初始化,p指向首结点,length为计数器
int length = 0;
while (!p.equals(head)) {// 从首结点向后查找，直到p指向头结点
p = p.next;// 指向后继结点
++length;// 长度增1
}
return length;
}
// 在双向循环链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1
public int indexOf(Object x) {
DuLNode p = head.next;// 初始化,p指向首结点,j为计数器
int j = 0;
while (!p.equals(head) && !p.data.equals(x)) {// 从链表中的首结点元素开始查找，直到p.data指向元素x或到达链表的表尾
p = p.next;// 指向下一个元素
++j;// 计数器的值增1
}
if (!p.equals(head))// 如果p指向表中的某一元素
return j;// 返回x元素在顺序表中的位置
else
return -1;// x元素不在顺序表中
}
public void display() {
DuLNode node = head.next;// 取出带头结点的双向链表中的首结点
while (!node.equals(head)) {
System.out.print(node.data + " ");// 输出数据元素的值
node = node.next;
}
System.out.println();
}
public DuLNode getHead() {
return head;
}
public void setHead(DuLNode head) {
this.head = head;
}
}
每个结点除了存放指向前驱结点的指针域，还存放指向后继结点的指针域prior，这是双向链表。若循环也是双向的：头结点的prior指向尾结点，尾结点的next指向首结点，那么这就是双向循环链表。
- 对于空的双向循环链表，头结点的两个指针域都指向头结点自身。这可作为循环链表的判空条件。
双向链表的查找操作与单链表相同。
双向链表的插入和删除需要修改两边各两个方向的指针。
顺序表与链表的比较
链表比较灵活，插入和删除操作的效率较高，但链表的空间利用率较低，适合于实现动态的线性表；
顺序表实现比较简单，因为任何高级程序语言中都有数组类型，并且空间利用率也较高，可高效地进行随机存取，但顺序表不易扩充，插人和删除操作的效率较低，适合于实现相对“稳定”的静态线性表。
本章小结
顺序表和链表各8种操作
单链表的创建：包括头插法、尾插法
集合运算：合并、交、差
循环右移、逆置
如何判断链表是否成环、如何去重、如何将链表拆分
第3章 栈与队列
栈
栈的基本操作：置空clear()、判空isEmpty()、求栈长度length()、取栈顶元素peek()、入栈push(x)、出栈pop()。
- 其中
push()会抛出异常，避免栈溢出。
顺序栈
[!Question] 分隔符匹配问题 程序语言里的左括号总要与右括号成对且同级出现，根据栈来判断是否出现相关语法错误：
凡是左括号都在等待着对应的右括号，越晚出现的左括号等待得越急迫。因此所有左括号都入栈，凡是出现右括号就与当前栈顶进行比较。
若栈顶元素（最晚出现的左括号）与当前出现的右括号不匹配，说明语法错误。
若结束后栈内仍有元素，说明有左括号缺少对应的右括号；若结束后仍有右括号但栈已空，说明该右括号多余。
// 分隔符匹配问题：编写判断Java程序中分隔符是否匹配的程序。Java程序中有以下分隔符：圆括号“（”和“）”，方括号“[”和“]”，大括号“{”和“}”以及注释分隔符“/*”和“*/”
public class Example3_1 {
private static final int LEFT = 0;// 记录分隔符为"左"分隔符
private static final int RIGHT = 1;// 记录分隔符为"右"分隔符
private static final int OTHER = 2;// 记录其他字符
// 判断分隔符的类型，有三种"左"、"右"、"非法"
public int verifyFlag(String str) {
if ("(".equals(str) || "[".equals(str) || "{".equals(str)
|| "/*".equals(str))// 左分隔符
return LEFT;
else if (")".equals(str) || "]".equals(str) || "}".equals(str)
|| "*/".equals(str))// 右分隔符
return RIGHT;
else
// 其他字符
return OTHER;
}
// 匹配左分隔符str1和右分隔符str2，是否匹配
public boolean matches(String str1, String str2) {
if (("(".equals(str1) && ")".equals(str2))
|| ("[".equals(str1) && "]".equals(str2))
|| ("{".equals(str1) && "}".equals(str2))
|| ("/*".equals(str1) && "*/".equals(str2)))// 匹配规则
return true;
else
return false;
}
private boolean isLegal(String str) throws Exception {
if (!"".equals(str) && str != null) {
SqStack S = new SqStack(100);// 新建最大存储空间为100的顺序栈
int length = str.length();
for (int i = 0; i < length; i++) {
char c = str.charAt(i);// 指定索引处的 char 值
String t = String.valueOf(c);// 转化成字符串型
if (i != length) {// c不是最后一个字符
if (('/' == c && '*' == str.charAt(i + 1))
|| ('*' == c && '/' == str.charAt(i + 1))) {// 是分隔符"/*"或"*/"
t = t.concat(String.valueOf(str.charAt(i + 1)));// 与后一个字符相连
++i;// 跳过一个字符
}
}
if (LEFT == verifyFlag(t)) {// 为左分隔符
S.push(t);// 压入栈
} else if (RIGHT == verifyFlag(t)) {// 为右分隔符
if (S.isEmpty() || !matches(S.pop().toString(), t)) {// 右分隔符与栈顶元素不匹配
throw new Exception("错误：Java语句不合法！");// 输出异常
}
}
}
if (!S.isEmpty())// 栈中存在没有匹配的字符
throw new Exception("错误：Java语句不合法！");// 输出异常
return true;
} else
throw new Exception("错误：Java语句为空！");// 输出异常
}
public static void main(String[] args) throws Exception {
Example3_1 e = new Example3_1();
System.out.println("请输入分Java语句：");// 输出
Scanner sc = new Scanner(System.in);
if (e.isLegal(sc.nextLine()))
System.out.println("Java语句合法!");// 输出
else
System.out.println("错误：Java语句不合法！");// 输出
}
}
链栈
栈的链式存储结构称为链栈。实质是运算受限（只允许在头结点插入删除）的单链表。
- 没有必要像单链表一样附加头结点，而是需要一个栈顶指针。
[!Question] 已知几种元素的入栈次序，求不可能出现的出栈次序？ 已知
1、2、3、4四种元素依次入栈，那么任何含有入栈次序的相邻序列都不可能是出栈次序。例如序列
4、2、3、1含有入栈序列2、3，它不可能是出栈次序；序列1、3、2、4虽然含有序列2、4，但不是相邻的，因此它是有可能的。
栈与函数调用以及被调用函数之间的链接和信息交换有关。
函数被调用时：
-
将所有实参、返回地址等信息传递给被调用函数；
-
为被调用函数的局部变量分配内存空间；
-
将处理器控制权转移到被调用函数入口。
被调用函数返回给主调用函数时：
-
保存被调用函数的结果；
-
释放被调用函数的内存空间；
-
依据被调用函数保存的返回地址，将处理器控制权转移到主调用函数。
多个函数嵌套调用时采用栈式管理（函数的信息保存在栈帧空间），后被调用的先返回。
[!Question] 大数加法问题 对于两个位数已经超出整型范围的大数的加法，先将它们转为字符串。然后从高位到低位依次入栈。栈能够帮助将相同数位对齐。
每次相加时分别令两边出栈，让取得的栈顶元素相加，保留该数位的结果，若需进位则在下一数位的加法中加一。
// 大数加法问题：编程实现两个大数的加法运算。所谓大数是指超过整数最大上限的数，如18 452 543 389 943 209 752 345 473和8 123 542 678 432 986 899 334相加。（提示：可以把两个加数看成是数字字符串，将这些数的相应数字存储在两个堆栈中，并从栈中弹出数字执行加法）
public class Example3_2 {
// 求两个大数的和，加数和被加数以字符串的形式输入（允许大数中出现空格），计算的结果也以字符串的形式返回。
public String add(String a, String b) throws Exception {
LinkStack sum = new LinkStack();// 大数的和
LinkStack sA = numSplit(a);// 加数字符串以单个字符的形式放入栈中
LinkStack sB = numSplit(b);// 被加数字符串以字符的形式放入栈中
int partialSum;// 对于两个位的求和
boolean isCarry = false;// 进位标示
while (!sA.isEmpty() && !sB.isEmpty()) {// 加数和被加数同时非空
partialSum = (Integer) sA.pop() + (Integer) sB.pop();// 对于两个位求和，并在栈中去除加数和被加数中的该位
if (isCarry) {// 低位进位
partialSum++;// 进位加到此位上
isCarry = false;// 重置进位标示
}
if (partialSum >= 10) {// 需要进位
partialSum -= 10;
sum.push(partialSum);
isCarry = true;// 标示进位
} else {// 位和不需要进位
sum.push(partialSum);// 和放入栈中
}
}
LinkStack temp = !sA.isEmpty() ? sA : sB;// 引用指向加数和被加数中非空栈
while (!temp.isEmpty()) {
if (isCarry) {// 如果在最后一次执行加法运算中，需要进位
int t = (Integer) temp.pop();// 取出加数或被加数没有参加的位
++t;// 进位加到此位上
if (t >= 10) {// 需要进位
t -= 10;
sum.push(t);
} else {
sum.push(t);
isCarry = false;// 重置进位标示
}
} else
// 如果在最后一次执行加法运算中，不需要进位
sum.push(temp.pop());// 把加数或被加数中非空的值放入和中
}
if (isCarry) {// 最高位需要进位
sum.push(1);// 进位放入栈中
}
String str = new String();
while (!sum.isEmpty())
// 把栈中元素，转化成字符串
str = str.concat(sum.pop().toString());
return str;
}
// 字符串以单个字符的形式放入栈中，并去除字符串中空格，返回以单个字符为元素的栈
public LinkStack numSplit(String str) throws Exception {
LinkStack s = new LinkStack();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);// 指定索引处的 char 值
if (' ' == c)// 去除空格
continue;
else if ('0' <= c && '9' >= c) // 数字放入栈中
s.push(Integer.valueOf(String.valueOf(c)));
else
// 非法数字字符
throw new Exception("错误：输入了非数字型字符!");
}
return s;
}
public static void main(String[] args) throws Exception {
Example3_2 e = new Example3_2();
System.out.println("两个大数的和为："
+ e.add("18 452 543 389 943 209 752 345 473",
"8 123 542 678 432 986 899 334"));// 输出运算结果
}
}
[!Question] 表达式求值问题 对于二元运算符而言，表达式分为前缀、中缀和后缀三种。运算符处在两个操作数的前面称为前缀，处在中间是中缀，处在后面则是后缀。
中缀表达式运算顺序不确定，而且括号会让次序更加复杂，相比而言后缀表达式中运算符的先后顺序就是实际的运算顺序，更适合计算机运行。
- 例如中缀表达式
A + ( B - C / D ) * E对应前缀表达式+ A * - B / C D E，对应后缀表达式A B D / - E * +。可以看出，操作数之间的相对次序不变，而后缀表达式中运算符的先后顺序就是实际的运算顺序。表达式求值一般分两步：
- 将原表达式转为后缀式。
先建立一个运算符栈。从左到右依次对原表达式进行操作：
若当前字符是操作数：就直接发送给后缀式。
若当前字符是运算符：且运算符栈为空，或当前运算符的优先级高于栈顶元素，那么该运算符进栈；否则就弹出栈顶运算符发送给后缀式，并让当前运算符进栈。
若当前字符是左括号
(：就直接进栈。若当前字符是右括号
)：就持续将栈顶元素弹出发送给后缀式，直到栈顶是左括号(，再把左括号(弹出并丢弃。重复上述操作，至原表达式读取完毕，再将运算符栈中依次全部弹出发送给后缀式。
- 从后缀式求值。
建立一个操作数栈。从左到右扫描后缀式：
若当前字符是操作数：就直接入栈。
若当前字符是运算符：从栈顶取出两个操作数与之运算，将运算结果再次入栈。
[!TIP] 运算符优先级为左括号
(优先级0，加+减-优先级1，乘*除/取模%优先级2，幂^优先级3。
// 表达式求值问题：编程实现算术表达式求值（包括将原表达式转换成后缀表达式及根据后缀表达式求值两个过程）
public class Example3_3 {
// 此函数将表达式变换为后缀表达式，把结果以字符串的形式返回，此函数的算法如下：
// 1)检查表达式的下一元素。
// 2)假如是个操作数，输出。
// 3)假如是个开括号，将其压栈。
// 4)假如是个运算符，则
// i) 假如栈为空，将此运算符压栈。
// ii) 假如栈顶是开括号，将此运算符压栈。
// iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。
// iv) 否则栈顶运算符出栈并输出，重复步骤4。
// 5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。
// 6)假如表达式还未完毕，跳转到步骤1。
// 7)假如遍历表达式完毕，栈中剩余的所有操作符出栈并加到后缀表达式的尾部。
public String convertToPostfix(String expression) throws Exception {
LinkStack st = new LinkStack();// 用于存放函数运行过程中的括号和运算符（函数结束时此栈为空）
String postfix = new String();// 用于输出的后缀表达式
for (int i = 0; expression != null && i < expression.length(); i++) {
char c = expression.charAt(i);// 指定索引处的 char 值
if (' ' != c) {// 字符c不为空格
if (isOpenParenthesis(c)) {
st.push(c);// 为开括号，压栈
} else if (isCloseParenthesis(c)) {// 为闭括号,栈中运算符逐个出栈并放入用于输出的栈，直到遇到开括号。开括号出栈并丢弃
Character ac = (Character) st.pop();// 移除栈顶元素
while (!isOpenParenthesis(ac.charValue())) {// 一直到为开括号为止
postfix = postfix.concat(ac.toString());// 串联到后缀表达式的结尾
ac = (Character) st.pop();
}
} else if (isOperator(c)) {// 为运算符
if (!st.isEmpty()) {// 栈非空，取出栈中优先级高的操作符串联到后缀表达式的结尾
Character ac = (Character) st.pop();
while (ac != null
&& priority(ac.charValue()) >= priority(c)) {// 优先级比较
postfix = postfix.concat(ac.toString());// 串联到后缀表达式的结尾
ac = (Character) st.pop();
}
if (ac != null) {// 如果最后一次取出的优先级低的操作符，重新压栈
st.push(ac);
}
}
st.push(c);
} else {// 为操作数，串联到后缀表达式的结尾
postfix = postfix.concat(String.valueOf(c));
}
}
}
while (!st.isEmpty()) {// 栈中剩余的所有操作符串联到后缀表达式的结尾
postfix = postfix.concat(String.valueOf(st.pop()));// 串联到后缀表达式的结尾
}
return postfix;
}
// 对后缀表达式进行求值计算，此函数的算法如下：
// 1)初始化一个空堆栈
// 2)从左到右读入后缀表达式
// i)如果字符是一个操作数，把它压入堆栈。
// ii)如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果不能够弹出两个操作数，后缀表达式的语法就不正确。
// 3)到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。
public double numberCalculate(String postfix) throws Exception {
LinkStack st = new LinkStack();
for (int i = 0; postfix != null && i < postfix.length(); i++) {
char c = postfix.charAt(i);// 指定索引处的 char 值
if (isOperator(c)) {// 当为操作符时
// 取出两个操作数
double d2 = Double.valueOf(st.pop().toString());
double d1 = Double.valueOf(st.pop().toString());
double d3 = 0;
if ('+' == c) {// 加法运算
d3 = d1 + d2;
} else if ('-' == c) {// 加法运算
d3 = d1 - d2;
} else if ('*' == c) {// 乘法运算
d3 = d1 * d2;
} else if ('/' == c) {// 除法运算
d3 = d1 / d2;
} else if ('^' == c) {// 幂运算
d3 = Math.pow(d1, d2);
} else if ('%' == c) {
d3 = d1 % d2;
}
st.push(d3);
} else {// 当为操作数时
st.push(c);
}
}
return (Double) st.pop();// 返回运算结果
}
// 判断字符串是否为运算符
public boolean isOperator(char c) {
if ('+' == c || '-' == c || '*' == c || '/' == c || '^' == c
|| '%' == c) {
return true;
} else {
return false;
}
}
// 判断字符串是否为开括号
public boolean isOpenParenthesis(char c) {
return '(' == c;
}
// 判断字符串是否为闭括号
public boolean isCloseParenthesis(char c) {
return ')' == c;
}
// 判断运算法的优先级
public int priority(char c) {
if (c == '^') {// 为幂运算
return 3;
}
if (c == '*' || c == '/' || c == '%') {// 为乘、除、取模运算
return 2;
} else if (c == '+' || c == '-') {// 为加、减运算
return 1;
} else { // 其他
return 0;
}
}
public static void main(String[] args) throws Exception {
Example3_3 p = new Example3_3();
String postfix = p.convertToPostfix("(1 + 2)*(5 - 2)/2^2 + 5%3");// 转化为后缀表达式
System.out.println("表达式的结果为： " + p.numberCalculate(postfix));// 对后缀表达式求值后，并输出
}
}
[!Question] 递归问题
[!Question] 汉诺塔问题
要求将所有圆盘从A移到C上，每次只能移动一个圆盘，并且大圆盘不能放在小圆盘上面。现假设有
n块盘。使用递归求解：先把A塔顶部的
n - 1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的n - 1块盘移到C。现在把A塔顶部的n - 2块盘看作原先的n - 1块盘，重复上述操作，通过递归不断缩小规模。[!Question] 地图四染色问题 使用不多于四种颜色对地图着色，使相邻的区域不重色。
可以先将地图上的邻近关系抽象成矩阵，矩阵元素的0或1代表对应两个区域是否相邻。
然后建立一个长度为区域数的栈，先入栈的可以先选色，后面入栈的如果通过矩阵发现冲突，需要弹出并重新选色。
[!Question] 迷宫问题
[!Question] 八皇后问题
队列
队列常用操作：队列置空clear()、队列判空isEmpty()、求队列长度length()、访问队首元素peek()、队首元素出队poll()、元素入队offer()、打印队列display()。
循环顺序队列CircleSqQueue
// 循环顺序队列类
public class CircleSqQueue implements IQueue {
private Object[] queueElem; // 队列存储空间
private int front;// 队首的引用，若队列不空，指向队首元素
private int rear;// 队尾的引用，若队列不空，指向队尾元素的下一个位置
// 循环队列类的构造函数
public CircleSqQueue(int maxSize) {
front = rear = 0;// 队头、队尾初始化为0
queueElem = new Object[maxSize];// 为队列分配maxSize个存储单元
}
// 将一个已经存在的队列置成空
public void clear() {
front = rear = 0;
}
// 测试队列是否为空
public boolean isEmpty() {
return front == rear;
}
// 求队列中的数据元素个数并由函数返回其值
public int length() {
return (rear - front + queueElem.length) % queueElem.length;
}
// 把指定的元素插入队列
public void offer(Object x) throws Exception {
if ((rear + 1) % queueElem.length == front)// 队列满l
//if (length()==queueElem.length)
throw new Exception("队列已满");// 输出异常
else {// 队列未满
queueElem[rear] = x;// x赋给队尾元素
rear = (rear + 1) % queueElem.length;// 修改队尾指针
}
}
// 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 null
public Object peek() {
if (front == rear)// 队列为空
return null;
else
return queueElem[front]; // 返回队首元素
}
// 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null
public Object poll() {
if (front == rear)// 队列为空
return null;
else {
Object t = queueElem[front];// 取出队首元素
front = (front + 1) % queueElem.length;// 更改队首的位置
return t;// 返回队首元素
}
}
// 打印函数，打印所有队列中的元素(队首到队尾)
public void display() {
if (!isEmpty()) {
for (int i = front; i != rear; i = (i + 1) % queueElem.length)
// 从队首到队尾
System.out.print(queueElem[i].toString() + " ");
} else {
System.out.println("此队列为空");
}
}
public Object[] getQueueElem() {
return queueElem;
}
public void setQueueElem(Object[] queueElem) {
this.queueElem = queueElem;
}
public int getFront() {
return front;
}
public void setFront(int front) {
this.front = front;
}
public int getRear() {
return rear;
}
public void setRear(int rear) {
this.rear = rear;
}
}
使用两个指针front和rear，分别指向队首元素和队尾元素的下一个元素。
- 空队列是
front == rear。
为解决假溢出问题（rear超出数组索引），将队列首尾相接成为循环队列。
循环队列时原先的判空条件front == rear已经失效（无法判断是全空还是全满），解决方案有：
-
（常用方法）减少使用数组的一个元素空间。也就是当队列只剩最后一个空位时，此时
rear指向front的前一个位置。使rear+1对队列容量（数组长度）求余，若等于front则队满。- 此时队空条件为
front == rear，队满条件是(rear+1) % queueElem.length == front。
- 此时队空条件为
-
（本方法不常用）添加一个计数器
num并置为0，以后每次有元素入队成功就自增1，每次有元素出队成功就自减1。
// 循环顺序队列类(采用设置一个计数器的方法来区分循环队列的判空和判满)
public class CircleSqQueue2 implements IQueue {
private Object[] queueElem; // 队列存储空间
private int front;// 队头的引用，若队列不空，指向队首元素
private int rear;// 队尾的引用，若队列不空，指向队尾元素的下一个位置
private int count; // 计数器用来记录队列中的数据元素个数
// 循环队列类的构造函数
public CircleSqQueue2(int maxSize) {
count = 0;
front =rear= 0;// 队头、队尾初始化为0
queueElem = new Object[maxSize];// 为队列分配maxSize个存储单元
}
// 将一个已经存在的队列置成空
public void clear() {
front = rear=0;
count = 0;
}
// 判断队列是否为空
public boolean isEmpty() {
return count == 0;
}
// 判断队列是否已满
public boolean isFull() {
return count == queueElem.length;
}
// 求队列中的数据元素个数并由函数返回其值
public int length() {
return count;
}
// 把指定的元素插入队列
public void offer(Object x) throws Exception {
if (isFull())// 队列满
throw new Exception("队列已满");// 输出异常
else {// 队列未满
queueElem[(front + count) % queueElem.length] = x;// x加入队尾
++count;
}
}
// 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 null
public Object peek() {
if (isEmpty())// 队列为空
return null;
else
return queueElem[front]; // 返回队首元素
}
// 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null
public Object poll() {
if (isEmpty())// 队列为空
return null;
else {
Object t = queueElem[front];// 取出队首元素
front = (front + 1) % queueElem.length;// 更改队首的位置
--count;
return t;// 返回队首元素
}
}
// 打印函数，打印所有队列中的元素(队首到队尾)
public void display() {
if (!isEmpty()) {
// 从队首到队尾
for (int i = front; i != (front + count) % queueElem.length; i = (i + 1)
% queueElem.length)
System.out.print(queueElem[i].toString() + " ");
} else {
System.out.println("此队列为空");
}
}
}
-
（本方法不常用）添加一个标志量
flag并置为0，以后每次有元素入队成功就置为1，每次有元素出队成功就置为0。- 此时队空条件为
front==rear && flag==0，队满条件为front==rear && flag==1。
- 此时队空条件为
// 循环顺序队列类(采用设置一个标志位的方法来区分循环队列的判空和判满)
public class CircleSqQueue3 implements IQueue {
private Object[] queueElem; // 队列存储空间
private int front;// 队头的引用，若队列不空，指向队首元素
private int rear;// 队尾的引用，若队列不空，指向队尾元素的下一个位置
private int flag; // 队列判空与判满的标志量,当入列操作后其值置为1,出队操作后其值置为0
// 循环队列类的构造函数
public CircleSqQueue3(int maxSize) {
queueElem = new Object[maxSize];// 为队列分配maxSize个存储单元
front =rear= 0;// 队头、队尾初始化为0
flag = 0;
}
// 将一个已经存在的队列置成空
public void clear() {
front = rear=0;
flag = 0;
}
// 判断队列是否为空
public boolean isEmpty() {
return front==rear&&flag==0;
}
// 判断队列是否已满
public boolean isFull() {
return front==rear&&flag==1;
}
// 求队列中的数据元素个数并由函数返回其值
public int length() {
return (rear-front+queueElem.length)%queueElem.length;
}
// 把指定的元素x插入队列
public void offer(Object x) throws Exception {
if (isFull())// 队列满
throw new Exception("队列已满");// 输出异常
else {// 队列未满
queueElem[rear] = x;// x赋给队尾元素
rear = (rear + 1) % queueElem.length;// 修改队尾指针
flag=1; //修改标志位值
}
}
// 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 null
public Object peek() {
if (isEmpty())// 队列为空
return null;
else
return queueElem[front]; // 返回队首元素
}
// 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null
public Object poll() {
if (isEmpty())// 队列为空
return null;
else {
Object t = queueElem[front];// 取出队首元素
front = (front + 1) % queueElem.length;// 更改队首的位置
flag=0; //修改标志位值
return t;// 返回队首元素
}
}
// 打印函数，打印所有队列中的元素(队首到队尾)
public void display() {
if (!isEmpty()) {
// 从队首到队尾
int i = front;
do {
System.out.print(queueElem[i].toString() + " ");
i = (i + 1)% queueElem.length;}
while(i!=rear);
}
else {
System.out.println("此队列为空");
}
}
public static void main(String[] args) throws Exception {
CircleSqQueue3 Q = new CircleSqQueue3(100);
for (int i = 1; i <= 10; i++)
// 初始化队列中的元素，其中元素个数为10
Q.offer(i);
System.out.println("队列中各元素为(队首到队尾)： ");
Q.display();// 打印队列中元素（队首到队尾）
System.out.println();
if (!Q.isEmpty())// 队列非空，输出
System.out.println("队列非空！");
System.out.println("队列的长度为： " + Q.length());// 输出队列的长度
System.out.println("队首元素为： " + Q.peek().toString());// 输出队首元素
System.out.println("去除队首元素后，队列中各元素为(队首到队尾)： ");
Q.poll();// 删除元素
Q.display();// 打印队列中元素
System.out.println();
System.out.println("去除队列中剩余的所有元素！ 进行中。。。"); // 输出
Q.clear(); // 清除队列中的元素
if (Q.isEmpty())// 队列空，输出
System.out.println("队列已清空!");
}
}
求队列当前长度length()需要用到求余运算：(rear - front + queueElem.length) % queueElem.length。
入队操作offer()需要先判断是否队满，要用到前面方法1.的判满条件（这与链队列的判定相反）。时间复杂度O(1)。
访问队首元素peek()和出队操作poll()都需要先判断是否队空，要用到前面方法1.的判空条件。时间复杂度O(1)。
链队列LinkQueue
// 链队列类
public class LinkQueue implements IQueue {
private Node front;// 队头的引用
private Node rear;// 队尾的引用，指向队尾元素
// 链队列类的构造函数
public LinkQueue() {
front = rear = null;
}
// 将一个已经存在的队列置成空
public void clear() {
front = rear = null;
}
// 测试队列是否为空
public boolean isEmpty() {
return front == null;
}
// 求队列中的数据元素个数并由函数返回其值
public int length() {
Node p = front;
int length = 0;// 队列的长度
while (p != null) {// 一直查找到队尾
p = p.next;
++length;// 长度增1
}
return length;
}
// 把指定的元素插入队列
public void offer(Object o) {
Node p = new Node(o);// 初始化新的结点
if (front != null) {// 队列非空
rear.next=p;
rear = p;// 改变队列尾的位置
} else
// 队列为空
front = rear = p;
}
// 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 null
public Object peek() {
if (front != null) // 队列非空
return front.data;// 返回队列元素
else
return null;
}
// 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null
public Object poll() {
if (front != null) { // 队列非空
Node p = front;// p指向队列头结点
front = front.next;
if (p==rear) //被删的结点是队尾结点
rear=null;
return p.data;// 返回队列头结点数据
} else
return null;
}
// 打印函数，打印所有队列中的元素(队列头到队列尾)
public void display() {
if (!isEmpty()) {
Node p = front;
while (p != rear.next) {// 从对头到队尾
System.out.print(p.data.toString() + " ");
p = p.next;
}
} else {
System.out.println("此队列为空");
}
}
}
// 链队列类(采用带头结点的循环链表来表示队列)
public class LinkQueue2 implements IQueue {
private Node rear;// 队尾的引用，指向队尾元素
private CircleLinkList cList;
// 链队列类的构造函数
public LinkQueue2() {
cList = new CircleLinkList();
rear = cList.head;
}
// 将一个已经存在的队列置成空
public void clear() {
rear = cList.head;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear.equals(cList.head);
}
// 返回队列中的数据元素个数
public int length() {
return cList.length();
}
// 把指定的元素插入队列
public void offer(Object o) throws Exception {
cList.insert(length(), o);
rear = new Node(cList.get(length() - 1));
}
// 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 null
public Object peek() {
if (!isEmpty())
try {
return cList.get(0);
} catch (Exception e) {
return null;
}
else
return null;
}
// 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null
public Object poll() {
if (!isEmpty())
try {
Object t = cList.get(0);// 记录移除前的队首元素
cList.remove(0);
return t;
} catch (Exception e) {
return null;
}
else
return null;
}
// 打印函数，打印所有队列中的元素(队列头到队列尾)
public void display() {
if (!isEmpty()) {
cList.display();
} else {
System.out.println("此队列为空");
}
}
}
一般用不带头结点的单链表实现。队首指针与队尾指针直接指向队首队尾元素。
-
front == null时队列为空。链队列没有队满情况，因此入队时判断的是队空而非队满 -
求队列长度需要沿着
next指针遍历每个结点确定。
入队操作offer()需要先判断是否队空，要用到前面方法1.的判空条件（这与顺序队列的判定相反）。时间复杂度O(1)。
出队操作poll()需要先判断是否队空，再判断是否删除的是最后一个元素（即队尾元素）。时间复杂度O(1)。
[!Question] 素数环问题 输入正整数n，把整数1,2,\dots,n组成一个环，使得相邻两个整数之和均为素数。
// 解素数环问题。即将1-n的n个自然数排列成环形，使得每相邻两数之和为素数，构成一个素数环
public class Example3_5 {
// 判断正整数是否为素数
public boolean isPrime(int num) {
if (num == 1)// 整数1返回false
return false;
Double n = Math.sqrt(num);// 求平方根
for (int i = 2; i <= n.intValue(); i++)
if (num % i == 0)// 模为0返回false
return false;
return true;
}
// 求n个正整数的素数环，并以顺序表返回
public SqList makePrimeRing(int n) throws Exception {
if (n % 2 != 0)// n为奇数则素数环不存在
throw new Exception("素数环不存在！");
SqList L = new SqList(n);// 构造一个顺序表
L.insert(0, 1);// 初始化顺序表的首节点为1
LinkQueue Q = new LinkQueue();// 构造一个链队列
for (int i = 2; i <= n; i++)
// 初始化链队列
Q.offer(i);
return insertRing(L, Q, 2, n);// 返回素数环
}
// 在一个顺序表中插入第m个数，使其与顺序表中第m - 1个数的和为素数，如果m等于n则还要满足第m个数与1的和也为素数。程序返回顺序表
public SqList insertRing(SqList L, LinkQueue Q, int m, int n)
throws NumberFormatException, Exception {
int count = 0;// 记录遍历队列中的元素个数，防止在一次循环中重复遍历
while (!Q.isEmpty() && count <= n - m) {// 队列非空，且未重复遍历队列
int p = (Integer) Q.poll();
int q = (Integer) L.get(L.length() - 1);// 取出顺序表中的最后一个元素
if (m == n) {// 为队列中的最后一个元素
if (isPrime(p + q) && isPrime(p + 1)) {// 满足素数环的条件
L.insert(L.length(), p);// 插入到顺序表尾
return L;
} else
// 不满足素数环条件
Q.offer(p);
} else if (isPrime(p + q)) {// 未遍历到队列的最后一个元素,且满足素数环条件
L.insert(L.length(), p);// 插入到顺序表尾
if (insertRing(L, Q, m + 1, n) != null)// 递归调用函数，如果返回值不为空，即已成功找到素数环，则返回
return L;
L.remove(L.length() - 1);// 移除顺序表表尾元素
Q.offer(p);
} else
Q.offer(p);// 加入的队列尾部
++count;// 遍历次数增1
}
return null;
}
public static void main(String[] args) throws Exception {
Example3_5 r = new Example3_5();// 构造素数环对象
SqList L = r.makePrimeRing(6);// 求素数环
for (int i = 0; i < L.length(); i++)
System.out.print(L.get(i) + " ");
}
}
优先队列PriorityQueue
// 充当优先队列结点类Node的数据域data
public class PriorityQData {
public Object elem;// 结点的值
public int priority;// 结点的优先级
// 构造函数
public PriorityQData(Object elem, int priority) {
this.elem = elem;
this.priority = priority;
}
}
// 优先队列类
public class PriorityQueue implements IQueue {
private Node front;// 队头的引用
private Node rear;// 队尾的引用，指向队尾元素
// 优先队列类的构造函数
public PriorityQueue() {
front = rear = null;
}
// 将一个已经存在的队列置成空
public void clear() {
front = rear = null;
}
// 测试队列是否为空
public boolean isEmpty() {
return front == null;
}
// 求队列中的数据元素个数并由函数返回其值
public int length() {
Node p = front;
int length = 0;// 队列的长度
while (p != null) {// 一直查找到队尾
p = p.next;
++length;// 长度增1
}
return length;
}
// 把指定的元素插入队列
public void offer(Object o) {
PriorityQData pn = (PriorityQData) o;
Node s = new Node(pn); // 构造一个新的结点
if (front == null) // 队列为空
front = rear = s;// 修改队列头尾结点
else {
Node p = front, q = front;
while (p != null
&& pn.priority>= ((PriorityQData) p.data)
.priority) {// 新结点的值与队列结点中的元素的值相比较
q = p;
p = p.next;
}
if (p == null) {// p为空，表示遍历到了队列尾部
rear.next=s;// 在队列中加入新结点
rear = s;// 修改队尾指针
} else if (p == front) {// p的优先级大于头结点的优先级
s.next=front;
front = s;// 修改头结点的值
} else {// 新结点加入队列中部
q.next=s;
s.next=p;
}
}
}
// 查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 null
public Object peek() {
if (front == null)// 队列为空
return null;
else
// 返回队列头结点的值
return front.data;
}
// 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null
public Object poll() {
if (front == null)// 队列为空
return null;
else {// 返回队列头结点的值，并修改队列头指针
Node p = front;
front = p.next;
return p.data;
}
}
// 打印函数，打印所有队列中的元素(队列头到队列尾)
public void display() {
if (!isEmpty()) {
Node p = front;
while (p != rear.next) {// 从对头到队尾
PriorityQData q = (PriorityQData) p.data;
System.out.println(q.elem + " " + q.priority);// 打印
p = p.next;
}
} else {
System.out.println("此队列为空");// 打印
}
}
}
优先链队列的结点在数据域新增了一个值priority表示其优先级。优先数越小优先级越高。
- 优先队列也有顺序和链式两种存储结构。此处采用链式实现。
入队操作会根据优先级高低进行插队。
栈与队列的比较
不同点：
-
删除数据元素操作的位置不同。栈的删除操作控制在表尾进行，而队列的删除操作控制在表头进行。
-
两者的应用场合不相同。
-
顺序栈可实现多栈空间共享，而顺序队列则不同。
相同点：
-
都是线性结构，即数据元素之间具有“一对一”的逻辑关系。
-
插入操作都是限制在表尾进行。
-
都可在顺序存储结构和链式存储结构上实现。
-
在时间代价上，插入与删除操作都需常数时间；在空间代价上，情况也相同。
-
多链栈和多链队列的管理模式可以相同。
多链栈与多链队列
将多个链栈的栈顶指针或链队列的队首、队尾指针分别存放在一个一维数组（顺序栈）中。
第4章 串与数组
串
串的基本操作：
-
已存在的串置空
clear()、串判空isEmpty()、字符串求长length()、 -
返回指定索引的字符
charAt(int index)、 -
返回从
begin至end-1的子串substring(int begin, int end)、 -
插入串
insert(int offset, IString str)、 -
删除从
begin至end-1的子串delete(int begin, int end)、 -
添加串到当前串尾
concat(IString str)、 -
比较串并返回一整数
compareTo(IString str)、 -
返回从
start处开始的子串中匹配str的第一个索引indexOf(IString str,int start)。
Java中，可以使用字符数组实现串的存储。顺序存储结构的串称为顺序串。也可以采用单链表来存储串值，这种链式存储结构称为链串。
串的模式匹配操作
Brute-Force模式匹配算法
设s为主串；t为模式串；i为主串当前比较字符的下标；j为模式串当前比较字符的下标。令i的初值为start，j的初值为0。从主串的第start个字符(i=start)起和模式串的第一个字符(j=0)比较，若相等则继续逐个比较后续字符(i++,j++)，否则从主串的第二个字符起重新和模式串比较（i返回到原位置加1，j返回到0）。依此类推，直至模式串t中的每一个字符依次和主串s的一个连续的字符序列相等，则称匹配成功，函数返回模式串t的第一个字符在主串s中的位置；否则称匹配失败，函数返回-1。
BF算法最差达到O(m\times n)时间。
KMP模式匹配算法
每当某趟匹配失败时，i指针不回退，而是利用已经得到的“部分匹配”的结果，将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
KMP算法能达到O(m+n)时间。
[!Question]
next[j]与nextval[j]函数求值 给定一长度为n的字符串s，其next函数定义为一个长度为n的数组。
next[j]就是子串s[0...j-1]最长的相等的真前缀与真后缀的长度。特别地，定义
next[0] = -1。
由于
next[j]存在缺陷，对其修正后成为nextval[j]。
特别地，依然有
nextval[0] = next[0] = -1。令
k = next[j]：
若
s[j] != s[k]：nextval[j] = next[j]。若
s[j] == s[k]：nextval[j] = next[k]。其他情况
nextval[j] = 0。
数组
数组是一组具有相同类型的数据元素的集合，数组元素按某种次序存储在一个地址连续的内存单元空间中，其中每个内存单元空间中的数据元素类型完全相同。数组可以看作是线性表的推广。
数组元素在数组中的位置称为数组元素的下标，通过数组元素的下标找到该数组元素的存储地址，继而访问该数组元素的值。
数组下标的个数就是数组的维数。
数组的基本操作：求长length()、取值getValue(index1, index2, ..., indexn)、赋值assign(value, index1, ..., indexn)。
数组是多维的结构，但存储空间是一维的。为了用一维存储地址来表示多维，有两种顺序映象方式：
-
行优先顺序（以行序为主序）
-
列优先顺序（以列序为主序）
[!TIP] 不同存储映象方式下计算数组元素的存储地址（
n维数组的映象函数） 对于二维数组A[m][n]中的元素a[i][j]：\begin{gathered}\begin{gathered}\text{以行序为主序存储映象} \colon \mathrm{L} \mathrm{O} \mathrm{C} \left( i,j \right) =\textcolor{red}{\mathrm{L} \mathrm{O} \mathrm{C} \left( 0,0 \right)} +\left( \textcolor{blue}{n\times i+j} \right) \times \textcolor{green}{L}\\ \text{以列序为主序存储映象} \colon \mathrm{L} \mathrm{O} \mathrm{C} \left( i,j \right) =\textcolor{red}{\mathrm{L} \mathrm{O} \mathrm{C} \left( 0,0 \right)} +\left( \textcolor{blue}{m\times j+i} \right) \times \textcolor{green}{L}\end{gathered}\\ \\ \text{其中} \textcolor{green}{L\text{为单个数组元素所占字节数}} ,\textcolor{red}{\mathrm{L} \mathrm{O} \mathrm{C} \left( 0,0 \right) \text{称为基地址或基址}}\end{gathered}
推广至
n维数组A[m1][m2]...[mn]中的元素a[i1][i2]...[in]：\mathrm{L} \mathrm{O} \mathrm{C} \left( i_{1},i_{2},\cdots ,i_{n} \right) =\textcolor{red}{\mathrm{L} \mathrm{O} \mathrm{C} \left( 0,\cdots ,0 \right)} +\left( \textcolor{blue}{i_{\textcolor{magenta}{1}}} \times \textcolor{blue}{m_{\textcolor{magenta}{2}}} \times \cdots \times \textcolor{blue}{m_{\textcolor{magenta}{n}}} +\textcolor{blue}{i_{\textcolor{magenta}{2}}} \times \textcolor{blue}{m_{\textcolor{magenta}{3}}} \times \cdots \times \textcolor{blue}{m_{\textcolor{magenta}{n}}} +\cdots +\textcolor{blue}{i_{\textcolor{magenta}{n-1}}} \times \textcolor{blue}{m_{\textcolor{magenta}{n}}} +\textcolor{blue}{i_{\textcolor{magenta}{n}}} \right) \times \textcolor{green}{L}
[!NOTE] 数组
A[1..8, 1..10]的记法表示二位数组A的行列记作1～8行、1～10列。
具有许多相同数据元素或者零元素，且数据元素分布具有一定规律的矩阵为特殊矩阵。为了节省存储空间，需要对这类矩阵进行压缩存储。
压缩存储的原则是：多个值相同的矩阵元素分配同一个存储空间，零元素不分配存储空间。
[!TIP] 特殊矩阵的压缩存储
- 对称矩阵
对称矩阵（a_{ij}=a_{ji}）的每一对对称元素仅分配一个存储。即将n^2个元素压缩为\frac{n\left( n+1 \right)}{2}个元素空间。
以行优先顺序存储的对称矩阵为例。假设以一维数组
S作为n阶对称矩阵A的存储结构，S[k]对应A[i][j]，则：k=\begin{cases}\frac{i\left( i+1 \right)}{2} +j&\left( i\geqslant j \right)\\ \frac{j\left( j+1 \right)}{2} +i&\left( i<j \right)\end{cases}
- 三角矩阵
三角矩阵分为上三角矩阵和下三角矩阵。下三角矩阵是指矩阵的主对角线（不包括主对角线）上方的元素的值均为0；上三角矩阵是指矩阵的主对角线（不包括主对角线）下方的元素的值均为0。
仍是将n^2个元素压缩为\frac{n\left( n+1 \right)}{2}个元素空间。
用一维数组
B存放三角矩阵中的元素，B[k]对应A中i行j列的元素，则：\begin{gathered}\text{下三角矩阵：} k=\begin{cases}\frac{i\left( i+1 \right)}{2} +j&\left( i\geqslant j;i,j=0,1,\cdots ,n-1 \right)\\ \text{空}&\left( i<j;i,j=0,1,\cdots ,n-1 \right)\end{cases}\\ \\ \text{上三角矩阵：} k=\begin{cases}\frac{j\left( j+1 \right)}{2} +i&\left( i<j;i,j=0,1,\cdots ,n-1 \right)\\ \text{空}&\left( i\geqslant j;i,j=0,1,\cdots ,n-1 \right)\end{cases}\end{gathered}
- 对角矩阵
对角矩阵是指矩阵的所有非零元素都集中在以主对角线为中心的带状区域中（除主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零）。
这样的称为半带宽为
d的带状矩阵（带宽为2d+1），d为直接在对角线上、下方不为0的对角线数。只需要存储带状区域元素，即满足\left| i-j \right| \leqslant d的元素。假设以一维数组
S作为n阶2d+1对角矩阵A的存储结构，则：\begin{gathered}\mathrm{L} \mathrm{O} \mathrm{C} \left( i,j \right) =\textcolor{red}{\mathrm{L} \mathrm{O} \mathrm{C} \left( 0,0 \right)} +\left[ \textcolor{blue}{i\left( 2d+1 \right)} +\textcolor{blue}{d} +\textcolor{blue}{\left( j-i \right)} \right] \times \textcolor{green}{L}\\ \text{其中} 0\leqslant i\leqslant n-1,0\leqslant j\leqslant n-1,\left| i-j \right| \leqslant d\end{gathered}
人们称具有较多零元素且非零元素的分布无规律的矩阵为稀疏矩阵。对其有两种压缩存储方式：
-
三元组顺序表
-
十字链表
[!NOTE] 三元组顺序表 稀疏矩阵可由表示非零元的三元组
(row, column, value)及其行列数唯一确定。稀疏矩阵中的所有非零元素组成一个三元组表，按照行优先顺序，将稀疏矩阵中的非零元素存放在一个由三元组组成的数组。
[!NOTE] 十字链表 在十字链表中稀疏矩阵的非零元素用一个结点来表示，每个结点由5个域组成：
row域存放该非零元素所在行的位置；
column域存放该非零元素所在列的位置；
value域存放该非零元素的值
right域存放与该非零元素同行的下一个非零元素结点指针；
down域存放与该非零元素同列的下一个非零元素结点指针。整个十字链表用一个包含5个域的头结点表示，
mu域存放稀疏矩阵的行数；nu域存放稀疏矩阵的列数；tu域存放稀疏矩阵的非零元素个数；rhead域存放行链表头指针数组的基地址；chead域存放列链表头指针数组的基地址。
第5章 树与二叉树
树
树是由n (n>=0)个结点所构成的有限集合。
-
n==0时，称为空树。 -
n>0时，满足：有且只有一个称为根的结点；其余结点可分为m个互不相交的有限集合，且每一集合又构成一棵树，即根结点的子树。
树可以用这些方法表示：树形表示法、文氏图、凹入图、广义表（括号）。
树型结构（一对多）与线性结构（一对一）之间的异同：
-
都存在无前驱或无后继的特殊元素/结点。
-
其它元素/结点都有一个前驱。线性结构的元素有一个后继，而树型结构的结点有多个后继。
树的术语：
-
分支（相当于边）、结点、结点的路径、结点的度（结点拥有的子树数目）、树的度（结点的度的最大值）、叶子结点（度为零）、分支结点（度大于零）；
-
孩子结点、双亲结点、兄弟结点、堂兄弟结点、祖先结点、子孙结点；
-
结点的层次（约定根结点层次为0）、树的深度（最大层次数加1）；
-
有序树（各子树之间从左到右有次序）、无序树、森林。
二叉树
// 二叉链式存储结构下的二叉树结点
public class BiTreeNode {
public Object data;// 结点的数据元素
public BiTreeNode lchild, rchild; // 左右孩子
public BiTreeNode() {// 构造一个空结点
this(null);
}
public BiTreeNode(Object data) {// 构造一棵左右孩子为空的结点
this(data, null, null);
}
public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) {// 构造一棵数据元素和左右孩子都不为空的结点
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
}
// 二叉链式存储结构下的二叉树
public class BiTree {
private BiTreeNode root;// 树的根结点
public BiTree() {// 构造一棵空树
this.root = null;
}
public BiTree(BiTreeNode root) {// 构造一棵树
this.root = root;
}
// 由先根遍历的数组和中根遍历的数组建立一棵二叉树
// 其中参数preOrder是整棵树的 先根遍历，inOrder是整棵树的中根遍历，preIndex是
// 先根遍历从preOrder字符串中的开始位置，inIndex是中根遍历从字符串inOrder中的开始位置，count表示树结点的个数
public BiTree(String preOrder, String inOrder, int preIndex, int inIndex,
int count) {
if (count > 0) {// 先根和中根非空
char r = preOrder.charAt(preIndex);// 取先根字符串中的第一个元素作为根结点
int i = 0;
for (; i < count; i++)
// 寻找根结点在中根遍历字符串中的索引
if (r == inOrder.charAt(i + inIndex))
break;
root = new BiTreeNode(r);// 建立树的根结点
root.lchild=new BiTree(preOrder, inOrder, preIndex + 1, inIndex,
i).root;// 建立树的左子树
root.rchild=new BiTree(preOrder, inOrder, preIndex + i + 1,
inIndex + i + 1, count - i - 1).root;// 建立树的右子树
}
}
// 由标明空子树的先根遍历序列建立一棵二叉树
private static int index = 0;// 用于记录preStr的索引值
public BiTree(String preStr) {
char c = preStr.charAt(index++);// 取出字符串索引为index的字符，且index增1
if (c != '#') {// 字符不为#
root = new BiTreeNode(c);// 建立树的根结点
root.lchild=new BiTree(preStr).root;// 建立树的左子树
root.rchild=new BiTree(preStr).root;// 建立树的右子树
} else
root = null;
}
// 先根遍历二叉树基本操作的递归算法
public void preRootTraverse(BiTreeNode T) {
if (T != null) {
System.out.print(T.data); // 访问根结点
preRootTraverse(T.lchild);// 访问左子树
preRootTraverse(T.rchild);// 访问右子树
}
}
// 先根遍历二叉树基本操作的非递归算法
public void preRootTraverse() {
BiTreeNode T = root;
if (T != null) {
LinkStack S = new LinkStack();// 构造栈
S.push(T);// 根结点入栈
while (!S.isEmpty()) {
T = (BiTreeNode) S.pop();// 移除栈顶结点，并返回其值
System.out.print(T.data); // 访问结点
while (T != null) {
if (T.lchild != null) // 访问左孩子
System.out.print(T.lchild.data); // 访问结点
if (T.rchild != null)// 右孩子非空入栈
S.push(T.rchild);
T = T.lchild;
}
}
}
}
// 中根遍历二叉树基本操作的递归算法
public void inRootTraverse(BiTreeNode T) {
if (T != null) {
inRootTraverse(T.lchild);// 访问左子树
System.out.print(T.data); // 访问根结点
inRootTraverse(T.rchild);// 访问右子树
}
}
// 中根遍历二叉树基本操作的非递归算法
public void inRootTraverse() {
BiTreeNode T = root;
if (T != null) {
LinkStack S = new LinkStack();// 构造链栈
S.push(T); // 根结点入栈
while (!S.isEmpty()) {
while (S.peek() != null)
// 将栈顶结点的所有左孩子结点入栈
S.push(((BiTreeNode) S.peek()).lchild);
S.pop(); // 空结点退栈
if (!S.isEmpty()) {
T = (BiTreeNode) S.pop();// 移除栈顶结点，并返回其值
System.out.print(T.data); // 访问结点
S.push(T.rchild);// 结点的右孩子入栈
}
}
}
}
// 后根遍历二叉树基本操作的递归算法
public void postRootTraverse(BiTreeNode T) {
if (T != null) {
postRootTraverse(T.lchild);// 访问左子树
postRootTraverse(T.rchild);// 访问右子树
System.out.print(T.data); // 访问根结点
}
}
// 后根遍历二叉树基本操作的非递归算法
public void postRootTraverse() {
BiTreeNode T = root;
if (T != null) {
LinkStack S = new LinkStack();// 构造链栈
S.push(T); // 根结点进栈
Boolean flag;// 访问标记
BiTreeNode p = null;// p指向刚被访问的结点
while (!S.isEmpty()) {
while (S.peek() != null)
// 将栈顶结点的所有左孩子结点入栈
S.push(((BiTreeNode) S.peek()).lchild);
S.pop(); // 空结点退栈
while (!S.isEmpty()) {
T = (BiTreeNode) S.peek();// 查看栈顶元素
if (T.rchild == null || T.rchild == p) {
System.out.print(T.data); // 访问结点
S.pop();// 移除栈顶元素
p = T;// p指向刚被访问的结点
flag = true;// 设置访问标记
} else {
S.push(T.rchild);// 右孩子结点入栈
flag = false;// 设置未被访问标记
}
if (!flag)
break;
}
}
}
}
// 层次遍历二叉树基本操作的算法(自左向右)
public void levelTraverse() {
BiTreeNode T = root;
if (T != null) {
LinkQueue L = new LinkQueue();// 构造队列
L.offer(T);// 根结点入队列
while (!L.isEmpty()) {
T = (BiTreeNode) L.poll();
System.out.print(T.data); // 访问结点
if (T.lchild != null)// 左孩子非空，入队列
L.offer(T.lchild);
if (T.rchild != null)// 右孩子非空，入队列
L.offer(T.rchild);
}
}
}
public BiTreeNode getRoot() {
return root;
}
public void setRoot(BiTreeNode root) {
this.root = root;
}
// 统计叶结点数目
public int countLeafNode(BiTreeNode T) {
int count = 0;
if (T != null) {
if (T.lchild == null && T.rchild == null) {
++count;// 叶结点个数加1
} else {
count += countLeafNode(T.lchild); // 加上左子树上叶结点的个数
count += countLeafNode(T.rchild);// 加上右子树上叶结点的个数
}
}
return count;
}
// 统计结点的数目
public int countNode(BiTreeNode T) {
int count = 0;
if (T != null) {
++count;// 结点的个数加1
count += countNode(T.lchild); // 加上左子树上结点的个数
count += countNode(T.rchild);// 加上右子树上结点的个数
}
return count;
}
}
有五种基本形态：空树、只含根结点、左子树为空、右子树为空、左右子树均非空。
[!TIP] 二叉树是度小于等于2的有序树。但不能说二叉树是度小于等于2的树。 一般默认“树”是无序树。因此具有3个结点的树只有2种。
左支树是所有结点都没有右孩子的二叉树；右支树是所有结点都没有左孩子的二叉树。
一棵二叉树，它的所有结点或是叶子结点，或是左右子树均非空，并且所有叶子结点在同一层，则为满二叉树。
- 满二叉树第i层有2^i个结点。
一棵二叉树拥有n个结点，其逻辑结构与满二叉树前n个结点的逻辑结构相同，则为完全二叉树。
[!NOTE] 二叉树的性质 深度为
h (h>=1)的二叉树至多有2^h-1个结点。第i层至多有2^i个结点。对任意二叉树，若叶子结点（即度为0）个数为n_0，度为2的结点个数为n_2，则有n_0 = n_2 +1。
具有
n个结点的完全二叉树的深度为\left\lfloor \log_{2} n \right\rfloor +1。对具有
n个结点的完全二叉树进行起始为0的从上到下、从左至右的编号：
i==0代表为根结点。除根结点外，结点
i的双亲编号为(i-1)/2。求结点
i的左右孩子：若2i+1>=n表明结点i无左孩子，否则编号为2i+1的结点为其左孩子；若2i+2>=n表明结点i无右孩子，否则编号为2i+2的结点为其右孩子。叶子结点的个数为\left\lceil n/2 \right\rceil。
（以上性质只适用完全二叉树）
[!NOTE] 二叉树的存储结构
- 顺序存储
对完全二叉树，可以用数组存储结点元素。编号
i与数组索引一一对应。结点之间的关系根据完全二叉树性质可以得出。对非完全二叉树，将其补成完全二叉树再用数组存储。此时会造成空间浪费，因此顺序存储仅适用于满/完全二叉树。
- 链式存储
分为二叉链表（存储左右孩子）和三叉链表（存储左右孩子和双亲）。
二叉树的遍历是沿某一路径对所有结点访问，每个结点均被访问且只有一次：包含三种递归遍历（先根、中根、后根遍历）、三种非递归遍历和层次遍历。
[!Example] 层次遍历
levelTraverse的非递归实现 层次遍历对二叉树进行从上到下、先左后右地遍历。若二叉树为空则为空操作。否则从第0层开始，依次从左到右访问每层所有结点。层次遍历借助队列实现：
- 先将根结点入队，只要队列未空就进行如下迭代：取出队首元素并进行处理，处理是先访问该结点，再将其左右孩子依次入队（只要其左右孩子非空）。
[!Example] 先根
preRootTraverse、中根inRootTraverse、后根遍历postRootTraverse的非递归实现 非递归遍历借助栈实现。此三种非递归遍历都遵循“沿左子树深入到底”的初始步骤，差异体现在访问结点的时机。
先根遍历：每深入一个左子结点，就在入栈前立刻访问之（先处理根）。左子树到底后弹出栈顶，转向其右子树重复上述过程。
中根遍历：先沿左子树深入到底，结点入栈时先不访问。待到无法深入时弹出栈顶并访问该结点（此时左子树已处理完），再转向右子树重复左深入过程。
后根遍历：在第一次弹出结点时不访问之，而是将之重新压入栈并转向右子树。当结点第二次被弹出时（右子树已处理完）才访问该结点。
栈中保存的是等待处理的祖先节点。
[!TIP] 若中缀表达式通过中序遍历生成了一棵正确的二叉树，再对该二叉树进行先序遍历和后序遍历，可以得到对应的前缀表达式（波兰式）和后缀表达式（逆波兰式）。
[!Question] 在二叉树上查找结点 通过递归遍历，将当前结点值与查找值进行比较。
// 编写一个基于二叉树类的查找二叉树结点的成员函数
public BiTreeNode searchNode(BiTreeNode T,Object x) {
// 在以T为根结点的二叉树中查找值为x的结点,若找到,则返回该结点,否则返回空值
if (T != null) {
if (T.data.equals(x))
return T;
else {
BiTreeNode lresult = searchNode(T.lchild,x); // 在左子树上查找
return (lresult != null ? lresult : searchNode(T.rchild,x)) ;// 若左子树上没找到,则到右子树上找
}
}
return null;
}
[!Question] 求二叉树的深度和宽度 二叉树深度应为其左右子树深度的最大值加1，因此必须用后根遍历。
二叉树宽度应用层序遍历实现。
// 编写成员函数完成求二叉树的深度
public int getDepth(BiTreeNode T) {
if (T != null) {
int lDepth = getDepth(T.lchild);// 左子树的深度
int rDepth = getDepth(T.rchild);// 右子树的深度
return 1 + (lDepth > rDepth ? lDepth : rDepth);// 返回左子树的深度和右子树的深度中的最大值加1
}
return 0;
}
// 采用递归模型方法，计算二叉树的深度
public int getDepth1(BiTreeNode T) {
if (T==null)
return 0;
else if (T.lchild==null&&T.rchild==null)
return 1;
else
return 1 + (getDepth1(T.lchild)> getDepth1(T.rchild)? getDepth1(T.lchild) : getDepth1(T.rchild));
}
[!Question] 计算二叉树结点/叶子结点个数
// 统计结点的数目
public int countNode(BiTreeNode T) {
int count = 0;
if (T != null) {
++count;// 结点的个数加1
count += countNode(T.lchild); // 加上左子树上结点的个数
count += countNode(T.rchild);// 加上右子树上结点的个数
}
return count;
}
// 统计叶结点数目
public int countLeafNode(BiTreeNode T) {
int count = 0;
if (T != null) {
if (T.lchild == null && T.rchild == null) {
++count;// 叶结点个数加1
} else {
count += countLeafNode(T.lchild); // 加上左子树上叶结点的个数
count += countLeafNode(T.rchild);// 加上右子树上叶结点的个数
}
}
return count;
}
[!Question] 判断二叉树是否相等
// 编写成员函数完成判断两棵二叉树是否相等
public boolean isEqual(BiTreeNode T1, BiTreeNode T2) {
if (T1 == null && T2 == null)// 同时为空
return true;
if (T1 != null && T2 != null) // 同时非空进行比较
if (T1.data.equals(T2.data))// 根结点数据元素是否相等
if (isEqual(T1.lchild, T2.lchild)) // 左子树是否相等
if (isEqual(T1.rchild, T2.rchild))// 右子树是否相等
return true;
return false;
}
// 采用递归模型方法，判断两棵树相等
public boolean isEqual1(BiTreeNode T1, BiTreeNode T2) {
if (T1 == null && T2 == null)
return true;
else if (T1 != null && T2 != null)
return (T1.data.equals(T2.data))&&(isEqual1(T1.lchild, T2.lchild))&&(isEqual(T1.rchild, T2.rchild));
else
return false;
}
[!Question] 递归算法（P166） 构造一个递归模型来反映一个递归问题的递归结构，然后根据递归模型将更易于写出对应的递归算法。递归模型包括两个要素，一是递归终止条件（又称递归出口），是所描述问题的最简单情况，本身不再使用递归的定义；二是递归体，是问题向终止条件转化的规则，能够使大问题分解成小问题直到找到递归终止条件。
[!Question] 由先序序列和中序序列建立二叉树 根据先序序列得到根结点，再在中序序列中找到根结点，从而划分出左子树与右子树，区分出左右子树的序列。再分别于左右子树中递归执行。
该方法要求序列中不存在相同的元素。
// 由先根遍历的数组和中根遍历的数组建立一棵二叉树
// 其中参数preOrder是整棵树的 先根遍历，inOrder是整棵树的中根遍历，preIndex是先根遍历从preOrder字符串中的开始位置，inIndex是中根遍历从字符串inOrder中的开始位置，count表示树结点的个数
public BiTree(String preOrder, String inOrder, int preIndex, int inIndex, int count) {
if (count > 0) {// 先根和中根非空
char r = preOrder.charAt(preIndex);// 取先根字符串中的第一个元素作为根结点
int i = 0;
for (; i < count; i++)
// 寻找根结点在中根遍历字符串中的索引
if (r == inOrder.charAt(i + inIndex))
break;
root = new BiTreeNode(r);// 建立树的根结点
root.lchild=new BiTree(preOrder, inOrder, preIndex + 1, inIndex, i).root;// 建立树的左子树
root.rchild=new BiTree(preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1).root;// 建立树的右子树
}
}
[!Question] 由标明空子树的先序序列建立二叉树
// 由标明空子树的先根遍历序列建立一棵二叉树
private static int index = 0;// 用于记录preStr的索引值
public BiTree(String preStr) {
char c = preStr.charAt(index++);// 取出字符串索引为index的字符，且index增1
if (c != '#') {// 字符不为#
root = new BiTreeNode(c);// 建立树的根结点
root.lchild=new BiTree(preStr).root;// 建立树的左子树
root.rchild=new BiTree(preStr).root;// 建立树的右子树
} else
root = null;
}
[!Question] 由顺序存储的完全二叉树建立二叉树
// 由顺序存储的完全二叉树建立一棵二叉树，并返回其根结点,其中index标识结点在完全二叉树中的序号
public BiTreeNode createBiTree(String sqBiTree, int index) {
BiTreeNode root = null;// 根结点
if (index < sqBiTree.length()) {// 位置不越界
root = new BiTreeNode(sqBiTree.charAt(index));// 建立树的根结点，存储二叉树使用了0号单元
root.lchild=createBiTree(sqBiTree, 2 * index + 1);// 建立树的左子树
root.rchild=createBiTree(sqBiTree, 2 * index + 2);// 建立树的右子树
}
return root;
}
[!Question] 求含有
n个结点的二叉树有多少种形态
哈夫曼树
// 赫夫曼树的结点类
public class HuffmanNode {
public int weight;// 结点的权值
public int flag;// 加入赫夫曼树的标志，flag=0时表示该结点未加入哈夫曼树，flag=1时则表示该结点已加入哈夫曼树
public HuffmanNode parent, lchild, rchild; // 父结点及左右孩子结点
public HuffmanNode() {// 构造一个空结点
this(0);
}
public HuffmanNode(int weight) {// 构造一个具有权值的结点
this.weight = weight;
flag = 0;
parent = lchild = rchild = null;
}
}
// 赫夫曼树及其操作
public class HuffmanTree {
// 求赫夫曼编码的算法，W存放n个字符的权值(均>0)
public int[][] huffmanCoding(int[] W) {
int n = W.length;// 字符个数
int m = 2 * n - 1;// 赫夫曼树的结点数
HuffmanNode[] HN = new HuffmanNode[m];
int i;
for (i = 0; i < n; i++)
HN[i] = new HuffmanNode(W[i]);// 构造n个具有权值的结点
for (i = n; i < m; i++) {// 建赫夫曼树
// 在HN[0..i - 1]选择不在赫夫曼树中且weight最小的两个结点min1和min2
HuffmanNode min1 = selectMin(HN, i - 1);
min1.flag=1;
HuffmanNode min2 = selectMin(HN, i - 1);
min2.flag=1;
// 构造min1和min2的父结点，并修改且父结点的权值
HN[i] = new HuffmanNode();
min1.parent=HN[i];
min2.parent=HN[i];
HN[i].lchild=min1;
HN[i].rchild=min2;
HN[i].weight=min1.weight + min2.weight;
}
// 从叶子到根逆向求每个字符的赫夫曼编码
int[][] HuffCode = new int[n][n];// 分配n个字符编码存储空间
for (int j = 0; j < n; j++) {
int start = n - 1;// 编码的开始位置，初始化为数组的结尾
for (HuffmanNode c = HN[j], p = c.parent; p != null; c = p, p = p.parent)
// 从叶子到根逆向求编码
if (p.lchild.equals(c))// 左孩子编码为0
HuffCode[j][start--] = 0;
else
// 右孩子编码为1
HuffCode[j][start--] = 1;
HuffCode[j][start] = -1;// 编码的开始标志为 -1，编码是-1之后的0、1序列
}
return HuffCode;
}
// 在HN[0..i - 1]选择不在赫夫曼树中且weight最小的结点
private HuffmanNode selectMin(HuffmanNode[] HN, int end) {
HuffmanNode min = HN[end];
for (int i = 0; i <= end; i++) {
HuffmanNode h = HN[i];
if (h.flag == 0 && h.weight < min.weight)// 不在赫夫曼树中且weight最小的结点
min = h;
}
return min;
}
public static void main(String[] args) {
int[] W = { 23, 11, 5, 3, 29, 14, 7, 8 };// 初始化权值
HuffmanTree T = new HuffmanTree();// 构造赫夫曼树
int[][] HN = T.huffmanCoding(W);// 求赫夫曼编码
System.out.println("赫夫曼编码为：");
for (int i = 0; i < HN.length; i++) {// 输出赫夫曼编码
System.out.print(W[i] + " ");
for (int j = 0; j < HN[i].length; j++) {
if (HN[i][j] == -1) {// 开始标志符读到数组结尾
for (int k = j + 1; k < HN[i].length; k++)
System.out.print(HN[i][k]);// 输出
break;
}
}
System.out.println();// 输出换行
}
}
}
术语：结点间的路径、结点的路径长度（从根结点到该结点间的路径上的分支数目）、结点的权、结点的带权路径长度（该结点的路径长度与该结点的权值的乘积）、树的带权路径长度WPL（树中所有叶子结点的带权路径长度之和）。
- 在结点个数相同的多棵二叉树中，若不考虑每个结点的权值，则路径长度最短的应是一棵完全二叉树。
给定n个有权值的叶子结点，按一定规则构造一棵使WPL达到最小的二叉树，称为最优二叉树或哈夫曼树。
- 哈夫曼树不一定是完全二叉树。
[!TIP] 构造哈夫曼树的算法 给定多个权值，在各个权值对应单结点构成的森林中，找出权最小和次小的两树合并为一棵二叉树（均作为此树的孩子），该二叉树的根结点权值规定为左右孩子的权值和。再将该树的根结点权值和原先的单结点继续比较，迭代上述步骤。最终会生成哈夫曼树。
由于未规定合并时的左右位置，因此同样的多个权值可以生成多棵哈夫曼树，但它们的WPL都相等。
[!NOTE] 哈夫曼树的性质 含
n个叶子结点（即n个权值）的哈夫曼树有2n-1个结点。不存在度为1的结点。
哈夫曼编码是由哈夫曼树求得的最优前缀编码，它是一种可变字长编码。
-
等长编码是将所有字符按相同数量的二进制位进行编码，但这样往往会降低存储与传输效率。因此使用可变字长的编码实现数据的压缩。
-
在可变字长编码中，前缀编码是指在所有字符的编码中，任何字符都不是另外某个字符的前缀。若用前缀相同的代码来表示不同的字符，则不同字符的编码之间会产生二义性（如果不用分隔符隔开）。
-
哈夫曼编码是最优的前缀编码。译码时不会出现二义性。
[!TIP] 构造哈夫曼编码
用电文中各个字符使用的频度作为叶结点的权，构造一棵具有最小WPL的哈夫曼树；
再对树中的每个左分支赋予标记
0，右分支赋予标记1；则从根结点到每个叶结点的路径上的标记连接起来就构成一个二进制串，该二进制串被称为哈夫曼编码。
译码过程就是编码的逆。
例：已知在一个信息通信联络中使用了8个字符：a、b、c、d、e、f、g、h，，每个字符的使用频度分别为：6、30、8、9、15、24、4、12。则其哈夫曼编码为：
使用哈夫曼编码时，相对于等长编码的压缩效率会受到所编码内容的影响。
树与森林CSTree
// 二叉链式(孩子 - 兄弟)存储结构下的树结点
public class CSTreeNode {
public Object data;// 结点的数据元素
public CSTreeNode firstchild, nextsibling; // 孩子兄弟结点
public CSTreeNode() {// 构造一个空结点
this(null);
}
public CSTreeNode(Object data) {// 构造一棵孩子及兄弟为空的结点
this(data, null, null);
}
public CSTreeNode(Object data, CSTreeNode firstchild, CSTreeNode nextsibling) {// 构造一棵数据元素和孩子及兄弟都不为空的结点
this.data = data;
this.firstchild = firstchild;
this.nextsibling = nextsibling;
}
}
// 二叉链式(孩子 - 兄弟)存储结构下的树
public class CSTree {
private CSTreeNode root;// 树的根结点
public CSTree() {// 构造一棵空树
this(null);
}
public CSTree(CSTreeNode root) {// 构造一棵树
this.root = root;
}
// 先根遍历树的递归算法
public void preRootTraverse(CSTreeNode T) {
if (T != null) {
System.out.print(T.data); // 访问根结点
preRootTraverse(T.firstchild);// 访问孩子结点
preRootTraverse(T.nextsibling);// 访问兄弟结点
}
}
// 后根遍历树的递归算法
public void postRootTraverse(CSTreeNode T) {
if (T != null) {
postRootTraverse(T.firstchild);// 访问孩子结点
System.out.print(T.data); // 访问根结点
postRootTraverse(T.nextsibling);// 访问兄弟结点
}
}
// 层次遍历
public void levelTraverse() {
CSTreeNode T = root;
if (T != null) {
LinkQueue L = new LinkQueue();// 构造队列
L.offer(T);// 根结点入队列
while (!L.isEmpty())
for (T = (CSTreeNode) L.poll(); T != null; T = T
.nextsibling) {// 访问结点及其所有兄弟结点
System.out.print(T.data); // 访问结点
if (T.firstchild != null)// 第一个孩子结点非空入队列
L.offer(T.firstchild);
}
}
}
public CSTreeNode getRoot() {
return root;
}
public void setRoot(CSTreeNode root) {
this.root = root;
}
}
树的四种存储结构：双亲链表存储结构（不易查找某结点的孩子）、孩子链表存储结构（不易查找某结点的双亲）、双亲孩子链表存储结构、孩子兄弟链表存储结构。
[!NOTE] 孩子兄弟链表存储结构 结点采用左孩子右兄弟的结构。树采用二叉链表结构。
由这种存储结构可知，树与由它转换成的二叉树是一一对应的。
[!TIP] 树与二叉树的转换 将树转换为二叉树分为三步：加线、删线、旋转。
加线：将树中所有相邻兄弟之间加一条连线；
删线：对树中每个结点，只保留它与第一个孩子（长子）结点之间的连线，删去它与其他孩子结点之间的连线；
旋转：将树进行旋转调整使其比较规整。
二叉树转换成树是由树转换二叉树的逆过程。
加线：左孩子的右分支向下的所有结点都与该左孩子的双亲结点相连；
删线：删去树中所有双亲结点与右孩子的连线；
旋转：进行旋转调整。
[!Question]
n个结点的树有多少种形态？ 先将n个结点的树转换为n-1个结点的二叉树，然后计算该二叉树的形态数目。利用树递推的特性，可以得出结果是卡特兰数C_{n-1}。即： C_{n-1}=\sum_{k=0}^{n-1} C_{k}C_{n-1-k}=\frac{1}{n} \binom{2n-2}{n-1} =\frac{\left( 2n-2 \right) !}{n!\cdot \left( n-1 \right) !}
树的遍历
由于树的根结点的各子结点之间没有先后之分，因此不存在中根遍历。
-
树的先根遍历：树非空时访问根结点，再从左到右依次先根遍历根结点的每棵子树。
-
树的后根遍历：树非空时从左到右依次后根遍历根结点的每棵子树，再访问根结点。
-
树的层次遍历：树非空时从上到下依次访问每层各个结点。同层的各结点从左到右访问。借助队列实现。
[!TIP] 树的遍历与二叉树遍历的对应关系 森林/树的先根遍历对应二叉树的先根遍历；
森林/树的后根遍历对应二叉树的中根遍历。
- 这里的森林/树都是以二叉链表形式（
CSTree）存储，后根遍历一棵树实际上是按照中根遍历的方式遍历二叉链表，程序也是按照中根遍历方式编写的。
森林的遍历
森林的遍历也不存在中根遍历。
-
先根遍历：森林非空时从左到右依次对森林的每棵树进行先根遍历。
-
后根遍历：森林非空时从左到右依次对森林的每棵树进行后根遍历。
-
层次遍历：森林非空时从左到右依次对森林的每棵树进行层次遍历。
第6章 图
// 图的种类 有向图、有向网、无向图、无向网
public enum GraphKind {
UDG, // 无向图（UnDirected Graph)
DG, // 有向图（Directed Graph)
UDN, // 无向网（UnDirected Network)
DN; // 有向网（Directed Network)
}
//图的数组表示法
public class MGraph implements IGraph {
public final static int INFINITY = Integer.MAX_VALUE;
private GraphKind kind;// 图的种类标志
private int vexNum, arcNum;// 图的当前顶点数和边数
private Object[] vexs;// 顶点
private int[][] arcs;// 邻接矩阵
public MGraph() {
this(null, 0, 0, null, null);
}
public MGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs,
int[][] arcs) {
this.kind = kind;
this.vexNum = vexNum;
this.arcNum = arcNum;
this.vexs = vexs;
this.arcs = arcs;
}
// 创建一个图
public void createGraph() {
Scanner sc = new Scanner(System.in);
System.out.println("请输入图的类型：");
GraphKind kind = GraphKind.valueOf(sc.next());
switch (kind) {
case UDG:
createUDG();// 构造无向图
return;
case DG:
createDG();// 构造有向图
return;
case UDN:
createUDN();// 构造无向网
return;
case DN:
createDN();// 构造有向网
return;
}
}
// 创建无向图
private void createUDG() {
// 略
};
// 创建有向图
private void createDG() {
// 略
};
// 创建无向网
private void createUDN() {
Scanner sc = new Scanner(System.in);
System.out.println("请分别输入图的顶点数、图的边数:");
vexNum = sc.nextInt();
arcNum = sc.nextInt();
vexs = new Object[vexNum];
System.out.println("请分别输入图的各个顶点:");
for (int v = 0; v < vexNum; v++)
// 构造顶点向量
vexs[v] = sc.next();
arcs = new int[vexNum][vexNum];
for (int v = 0; v < vexNum; v++)
// 初始化邻接矩阵
for (int u = 0; u < vexNum; u++)
arcs[v][u] = INFINITY;
System.out.println("请输入各个边的顶点及其权值:");
for (int k = 0; k < arcNum; k++) {
int v = locateVex(sc.next());
int u = locateVex(sc.next());
arcs[v][u] = arcs[u][v] = sc.nextInt();
}
}
// 创建有向网
private void createDN() {
Scanner sc = new Scanner(System.in);
System.out.println("请分别输入图的顶点数、图的边数:");
vexNum = sc.nextInt();
arcNum = sc.nextInt();
vexs = new Object[vexNum];
System.out.println("请分别输入图的各个顶点:");
for (int v = 0; v < vexNum; v++)
// 构造顶点向量
vexs[v] = sc.next();
arcs = new int[vexNum][vexNum];
for (int v = 0; v < vexNum; v++)
// 初始化邻接矩阵
for (int u = 0; u < vexNum; u++)
arcs[v][u] = INFINITY;
System.out.println("请输入各边的顶点及其权值:");
for (int k = 0; k < arcNum; k++) {
int v = locateVex(sc.next());
int u = locateVex(sc.next());
arcs[v][u] = sc.nextInt();
}
}
// 返回顶点数
public int getVexNum() {
return vexNum;
}
// 返回边数
public int getArcNum() {
return arcNum;
}
// 给定顶点的值vex，返回其在图中的位置，如果图中不包含此顶点，则返回-1
public int locateVex(Object vex) {
for (int v = 0; v < vexNum; v++)
if (vexs[v].equals(vex))
return v;
return -1;
}
// 返回v表示结点的值， 0 <= v < vexNum public Object getVex(int v) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在!");
return vexs[v];
}
// 返回v的第一个邻接点，若v没有邻接点则返回-1， 0 <= v < vexnum public int firstAdjVex(int v) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在!");
for (int j = 0; j < vexNum; j++)
if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
return j;
return -1;
}
// 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1，其中0≤v, w<vexNum
public int nextAdjVex(int v, int w) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在!");
for (int j = w + 1; j < vexNum; j++)
if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
return j;
return -1;
}
public GraphKind getKind() {
return kind;
}
public void setArcNum(int arcNum) {
this.arcNum = arcNum;
}
public void setArcs(int[][] arcs) {
this.arcs = arcs;
}
public void setKind(GraphKind kind) {
this.kind = kind;
}
public void setVexNum(int vexNum) {
this.vexNum = vexNum;
}
public void setVexs(Object[] vexs) {
this.vexs = vexs;
}
public int[][] getArcs() {
return arcs;
}
public Object[] getVexs() {
return vexs;
}
}
//图的邻接表存储表示
public class ALGraph implements IGraph {
private GraphKind kind;// 图的种类标志
private int vexNum, arcNum;// 图的当前顶点数和边数
private VNode[] vexs;// 顶点
public ALGraph() {
this(null, 0, 0, null);
}
public ALGraph(GraphKind kind, int vexNum, int arcNum, VNode[] vexs) {
this.kind = kind;
this.vexNum = vexNum;
this.arcNum = arcNum;
this.vexs = vexs;
}
// 创建图
public void createGraph() {
Scanner sc = new Scanner(System.in);
System.out.println("请输入图的类型：");
GraphKind kind = GraphKind.valueOf(sc.next());
switch (kind) {
case UDG:
createUDG();// 构造无向图
return;
case DG:
createDG();// 构造有向图
return;
case DN:
createDN();// 构造有向网
return;
case UDN:
createUDN();// 构造无向网
return;
}
}
// 创建无向图
private void createUDG() {
// 略
};
// 创建有向图
private void createDG() {
// 略
};
// 创建无向网
private void createUDN() {
Scanner sc = new Scanner(System.in);
System.out.println("请分别输入图的顶点数、图的边数:");
vexNum = sc.nextInt();
arcNum = sc.nextInt();
vexs = new VNode[vexNum];
System.out.println("请分别输入图的各各顶点:");
for (int v = 0; v < vexNum; v++)
// 构造顶点向量
vexs[v] = new VNode(sc.next());
System.out.println("请输入各各边的顶点及其权值:");
for (int k = 0; k < arcNum; k++) {
int v = locateVex(sc.next());// 弧尾
int u = locateVex(sc.next());// 弧头
int value = sc.nextInt();
addArc(v, u, value);
addArc(u, v, value);
}
}
// 创建有向网
private void createDN() {
Scanner sc = new Scanner(System.in);
System.out.println("请分别输入图的顶点数、图的边数:");
vexNum = sc.nextInt();
arcNum = sc.nextInt();
vexs = new VNode[vexNum];
System.out.println("请分别输入图的各各顶点:");
for (int v = 0; v < vexNum; v++)
// 构造顶点向量
vexs[v] = new VNode(sc.next());
System.out.println("请输入各各边的顶点及其权值:");
for (int k = 0; k < arcNum; k++) {
int v = locateVex(sc.next());// 弧尾
int u = locateVex(sc.next());// 弧头
int value = sc.nextInt();
addArc(v, u, value);
}
}
// 在位置为v、u的顶点之间，添加一条弧，其权值为value
public void addArc(int v, int u, int value) {
ArcNode arc = new ArcNode(u, value);
arc.setNextArc(vexs[v].getFirstArc());
vexs[v].setFirstArc(arc);
}
// 返回顶点数
public int getVexNum() {
return vexNum;
}
// 返边数
public int getArcNum() {
return arcNum;
}
// 给定顶点的值vex，返回其在图中的位置，如果图中不包含此顶点，则返回-1
public int locateVex(Object vex) {
for (int v = 0; v < vexNum; v++)
if (vexs[v].getData().equals(vex))
return v;
return -1;
}
public VNode[] getVexs() {
return vexs;
}
public GraphKind getKind() {
return kind;
}
// 返回v表示结点的值， 0 <= v < vexNum public Object getVex(int v) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在!");
return vexs[v].getData();
}
// 返回v的第一个邻接点，若v没有邻接点则返回-1， 0 <= v < vexnum public int firstAdjVex(int v) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在!");
VNode vex = vexs[v];
if (vex.getFirstArc() != null)
return vex.getFirstArc().getAdjVex();
else
return -1;
}
// 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1，其中0≤v, w<vexNum
public int nextAdjVex(int v, int w) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在!");
VNode vex = vexs[v];
ArcNode arcvw = null;
for (ArcNode arc = vex.getFirstArc(); arc != null; arc = arc
.getNextArc())
if (arc.getAdjVex() == w) {
arcvw = arc;
break;
}
if (arcvw != null && arcvw.getNextArc() != null)
return arcvw.getNextArc().getAdjVex();
else
return -1;
}
}
由顶点（Vertex）集和边（Edge）集组成，记为G＝(V, E)。其中V 是有穷非空集合，称为顶点集，v ∈ V 称为顶点。E是有穷集合，称为边集， e∈ E 称为边。
- 零图只有顶点没有边。
术语：
-
无向边、无向图、有向边、有向图；
-
权、网；
-
完全无向图（每两个顶点之间都存在着一条边）、完全有向图（每两个顶点之间都存在着方向相反的两条边）；
-
稀疏图（
e<vlogv）、稠密图； -
子图、生成子图（包含原图中所有顶点的子图）；
-
邻接点（无向图中互为邻接点，还有关联的边以及边关联的顶点）；
-
顶点的度（无向图，记做
D(v)）、入度和出度（有向图，记做ID(v)和OD(v)）； -
路径（顶点序列）、回路/环、路径长度、初等路径（无重复顶点）、初等回路；
-
网中的路径长度（从始点到终点的路径上各边的权值之和）；
-
连通图、连通分量；
-
强连通图（有向图中任意两个顶点之间都存在一条有向路径）、强连通分量；
-
生成树（极小连通子图）、生成森林（对于非连通图，各个连通分量的生成树的集合）。
[!TIP] 图中有v个顶点，则完全无向图有\frac{v\left( v-1 \right)}{2}条边，完全无向图有v\left( v-1 \right)条弧。
[!TIP] 图所有顶点的度之和是该图边数的二倍。
[!TIP] 有向图中，顶点
v的度等于它的入度和出度之和，即D(v) = ID(v) + OD(v)。
[!TIP]
v个顶点的连通图的边数最少为v-1，强连通图的边数最少为v。
常用操作：
-
创建图
createGraph()、返回顶点数getVexNum()、返回边数getArcNum()； -
返回
v表示的结点值getVex(int v)； -
给定顶点值并返回其在图中的位置
locateVex(Object vex)； -
返回
v的首个邻接点firstAdjVex(int v)；- 在邻接矩阵表示的图中，该方法通过查找矩阵第
v行内非0非无穷的值来实现。
- 在邻接矩阵表示的图中，该方法通过查找矩阵第
-
返回
v相对于w的下一邻接点nextAdjVex(int v, int w)。- 在邻接矩阵表示的图中，该方法从矩阵第
v行第w+1列开始查找该行内下一个非0非无穷的值。
- 在邻接矩阵表示的图中，该方法从矩阵第
图的存储结构
图的邻接阵是用来表示顶点之间相邻关系的方阵。邻接处为1，不邻接为0。
-
无向图的邻接矩阵是对称的（可采用压缩存储）。顶点v_i的度是第
i行或第i列中元素1的个数。 -
有向图的邻接矩阵不一定为对称矩阵。行中
1的个数对应该顶点的出度，列对应入度。
网的邻接阵表示顶点之间相邻关系和权值。邻接处为该边的权值w_{ij}，不邻接为无穷。
[!NOTE] 稠密图适合用邻接矩阵方式存储（边数较多）。
图的邻接表是链式存储，包括一个顺序存储的顶点表和多个链式存储的边表。
-
无向图对应的邻接表某行上的结点个数为该行所表示结点的度。
-
有向图邻接表的边表表示所有以v_i为始点的弧，某行上边结点个数为该结点的出度。有向图的邻接表中不易找到指向该顶点的弧。
-
有向图逆邻接表的边表表示所有以v_i为终点的弧，某行上边结点个数为该结点的入度。
[!TIP] 无向图/网中有
e条边，则对应邻接表有2e个边结点。有向图/网中有e条边，则对应邻接表有e个边结点。
[!NOTE] 对于稀疏图，邻接表比邻接矩阵节省存储空间。邻接表上更容易找到任意一个顶点的邻接点。但不易判定任意两个邻接点是否有边相连。
图的遍历
public class BTraverser {
private static boolean[] visited;// 访问标志数组
// 对图G做广度优先遍历
public static void BFSTraverse(IGraph G) throws Exception {
visited = new boolean[G.getVexNum()];// 访问标志数组
for (int v = 0; v < G.getVexNum(); v++)
// 访问标志数组初始化
visited[v] = false;
for (int v = 0; v < G.getVexNum(); v++)
if (!visited[v]) // v尚未访问
BFS(G, v);
}
private static void BFS(IGraph G, int v) throws Exception {
visited[v] = true;
System.out.print(G.getVex(v).toString() + " ");
LinkQueue Q = new LinkQueue();// 辅助队列Q
Q.offer(v);// v入队列
while (!Q.isEmpty()) {
int u = (Integer) Q.poll();// 队头元素出队列并赋值给u
for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w))
if (!visited[w]) {// w为u的尚未访问的邻接顶点
visited[w] = true;
System.out.print(G.getVex(w).toString() + " ");
Q.offer(w);
}
}
}
public static void main(String[] args) throws Exception {
ALGraph G = GenerateGraph.generateALGraph();
BTraverser.BFSTraverse(G);
}
}
public class DTraverser {
private static boolean[] visited;// 访问标志数组
// 对图G做深度优先遍历
public static void DFSTraverse(IGraph G) throws Exception {
visited = new boolean[G.getVexNum()];
for (int v = 0; v < G.getVexNum(); v++)
// 访问标志数组初始化
visited[v] = false;
for (int v = 0; v < G.getVexNum(); v++)
if (!visited[v])// 对尚未访问的顶点调用DFS
DFS(G, v);
}
// 从第v个顶点出发递归地深度优先遍历图G
public static void DFS(IGraph G, int v) throws Exception {
visited[v] = true;
System.out.print(G.getVex(v).toString() + " ");// 访问第v个顶点
for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w))
if (!visited[w])// 对v的尚未访问的邻接顶点w递归调用DFS
DFS(G, w);
}
public static void main(String[] args) throws Exception {
ALGraph G = GenerateGraph.generateALGraph();
DTraverser.DFSTraverse(G);
}
}
对于一个图，从某个顶点出发可得到多种搜索遍历结果，但如果是在特定存储结构上，按照某种特定搜索算法只能有一种唯一的遍历结果。
图的广度优先搜索算法BFSTraverse(G)：
-
遍历过程实际上是寻找邻接点的过程；
-
类似于树的层次遍历过程；
-
使用队列操作体现结点访问的先后次序：每个结点一旦被访问就插入队列中，每次从队头取出结点，访问它所有未被访问过的邻接点；
-
使用
visited数组，标记结点是否被访问过。
[!NOTE] 广度优先搜索BFS算法
初始化
visited数组；从某个未被访问过顶点出发广度搜索所有未被访问的结点
BFS(G, v)；如果图为非连通图，则从某个顶点出发并不能访问图中所有结点而只能访问图中一连通分量，此时需从图选择另一未被访问过的结点，继续广度搜索。
注意：如果不是连通图，需要确保每个连通分量都可以被访问到。
存储结构采用邻接矩阵时，需要扫描邻接矩阵中的每一个顶点，其时间复杂度为O(n^2)；
存储结构采用邻接表时，需要扫描邻接表中的每一个单链表，其时间复杂度为O(e)。
由于需要使用队列依次记住被访问过的顶点，每一个顶点最多入队、出队一次，并且增设一个辅助数组
visited，因此空间复杂度为O(n)。
图的深度优先搜索算法DFSTraverse(G)：
-
遍历过程实际上也是寻找邻接点的过程；
-
因为是搜索邻接点的邻接点，所以可以看成是一个递归的过程；
-
深度优先搜索遍历连通图的过程类似于树的先根遍历。
[!NOTE] 深度优先搜索DFS算法 从图中某个顶点
V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。
初始化
visited数组从某个未被访问过顶点出发深度搜索所有未被访问的结点
DFS(G, v)；如果图为非连通图，则从某个顶点出发并不能访问图中所有结点而只能访问图中一连通分量，此时需从图选择另一未被访问过的结点，继续深度优先搜索。
注意：若图不通，在访问完一个连通分量后，则另选图中一个未曾被访问的顶点作起始点继续进行深度优先搜索遍历。
深度优先搜索遍历图的时间复杂度和广度优先搜索遍历相同。
空间复杂度上，除了增设的
visited数组为O(n)，递归调用会使用栈，栈最深为n。
图的最小生成树
连通图的生成树^[Spanning Tree]是图的极小连通子图，它包含图中的全部顶点；也是图的极大无回路子图，它的边集是关联图中的所有顶点而又没有形成回路的边。
-
一个有n个顶点的连通图的生成树只能有n-1条边。
-
图的生成树不是唯一的。
广度优先生成树（BFS Spanning Tree）和深度优先生成树（DFS Spanning Tree）
[!TIP] 已知图/图的邻接矩阵/图的邻接表，画出其广度优先/深度优先生成树
构造网的最小代价生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。
求图的最小生成树的典型的算法：Kruskal算法、Prim算法。
-
最小生成树不唯一。但它们最终的权值和是一样的。
-
Kruskal适合稀疏图，时间复杂度O(e\log e)。Prim适合稠密图，时间复杂度O(v^2)。
[!NOTE] Kruskal算法 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在 SG 上加上这条边，如此重复直至加上 n-1 条边为止。
设图G＝(V, E)是一个具有n个顶点的连通无向网， T＝(V, TE)是图G的最小生成树。
T的初始状态为T＝(V, ∅)；
将图G中的边按照权值从小到大的顺序排序；
依次选取每条边，若选取的边未使生成树T形成回路，则加入TE中；否则舍弃，直至TE中包含了n-1条边为止。
如何判断是否构成回路？
使用辅助数组，数组长度为顶点数。初始化数组元素的值为其对应的顶点编号。要增加边时，就将对应顶点的数组元素值进行比较，若不同说明未构成回路，可以添加，再将对应顶点的数组元素值连通其他与该值相同的元素置成同一值。
在网中，定义下列距离：两个顶点之间的距离、顶点到顶点集合之间的距离、两个顶点集合之间的距离。
[!NOTE] Prim算法 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。
设图G＝(V, E)是一个具有n个顶点的连通无向网， T＝(U, TE)是图G的最小生成树。
从V中任取一顶点，将它并入U 中，每次选择连接U内顶点和V-U（U之外的顶点）内顶点的所有边中最小的，并将另一不在U内的顶点并入U，相应的边并入TE中，直到所有顶点都并入U。
[!TIP] 使用辅助数组求Prim算法各步操作及状态
P237 4.
图的最短路径
只要存在多条路径，就有最短路径。路径中的第一个顶点为源点（Source）最后一个顶点为终点（Destination）。
Dijkstra计算某一源点到其余点的最短路径，Floyd计算每一对顶点之间的最短路径。
[!NOTE] Dijkstra算法 初始若从源点v到各个终点有弧，则存在一条路径，路径长度即为该弧上的权值，保存于D中。
求得一条到达某个终点的最短路径，即当前路径中的最小值，该顶点记为w。检查是否存在经过顶点w的其它路径，若存在，判断其长度是否比当前求得的路径长度短，若是，则修改D中当前最短路径。
重复上一步。
算法的时间复杂度为O(n^2)。
找一条从源点到某一特定终点之间的最短路径问题和求源点到各个终点的最短路径一样复杂，其时间复杂度仍为O(n^2)。 若希望得到图中任意两个顶点之间的最短路径，只要依次将每一个顶点设为源点，调用迪杰斯特拉算法n次便可求出，其时间复杂度为O(n^3)。
[!NOTE] Floyd算法 求得一个n阶方阵序列：D^{(-1)},D^{(0)},D^{(1)},…,D^{(k)},…,D^{(n-1)}。
D^{(-1)}[i][j]表示从顶点vi出发，不经过其它顶点直接到达顶点vj的路径长度。
D^{(k)} [i][j]表示从vi到vj的中间只可能经过v0 , v1,…, vk而不可能经过vk+1， vk+2，…， vn-1等顶点的最短路径长度。
D^{(n-1)} [i][j]就是从顶点vi到顶点vj的最短路径的长度。
核心操作是不断对矩阵中的元素进行判断：
if (D[i][k]+D[k][j]<D[i][j]){ D[i][j]=D[i][k]+D[k][j]; //更新最短路径长度 P[i][j]=P[i][k]+P[k][j]; //更新最短路径 }其中：k表示在路径中新增的顶点号，i为路径的源点，j为路径的终点。
该算法计算每一对顶点之间的最短路径，时间复杂度为O(n^3)。
拓扑排序步骤： (1)在AOV网中选择一个没有前驱的顶点并输出 (2)从AOV网中删除该顶点以及从它出发的弧； (3)重复(1)和(2)直至AOV网为空（即已输出所有的顶点），或者剩余子图中不存在没有前驱的顶点。后一种情况则说明该AOV网中存在有向环。
检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。
存在拓扑序列，说明不存在环
由于拓扑排序中对图的主要操作是“找从顶点出发的弧”，并且AOV网在多数情况下是稀疏图，因此存储结构取邻接表为宜
拓扑序列不唯一，但在特点的存储结构和特定的算法下拓扑排序是唯一的：
(1)写出有向图的邻接表存储结构 (2)统计各顶点的入度值 (3)从上到下扫描各顶点入度，若为0则入栈 (4)从栈顶取一顶点加入拓扑序列中 (5) 相应的在邻接表中以该顶点为起点的终点入度值减1，若为0则入栈 (6)重复上述第4、5步
若以弧表示活动，弧上的权值表示进行该项活动所需的时间，以顶点表示“事件（Event）”，称这种有向网为边活动网络，简称为AOE(Activity On Edge)网
一个工程的AOE网应该是只有一个源点和一个汇点的有向无环图
要缩短整个工期，必须先找到关键路径，提高关键活动的工效 由于关键路径上的活动都是关键活动，所以，提前完成非关键活动并不能加快工程的进度
第7章 排序
// 顺序表记录结点类
public class RecordNode {
public Comparable key; // 关键字
public Object element; // 数据元素
/* public Object getElement() { return element; }
public void setElement(Object element) { this.element = element; }
public Comparable getKey() { return key; }
public void setKey(Comparable key) { this.key = key; }*/
public RecordNode() {
}
public RecordNode(Comparable key) { // 构造方法1
this.key = key;
}
public RecordNode(Comparable key, Object element) { // 构造方法2
this.key = key;
this.element = element;
}
public String toString() { // 覆盖toString()方法
return "[" + key + "," + element + "]";
}
}
// 顺序表类
public class SeqList {
public RecordNode[] r; //顺序表记录结点数组
public int curlen; //顺序表长度,即记录个数
/*
public RecordNode[] getRecord() { return r; }
public void setRecord(RecordNode[] r) { this.r = r; }*/
public SeqList(){}
// 顺序表的构造方法，构造一个存储空间容量为maxSize的顺序表
public SeqList(int maxSize) {
this.r = new RecordNode[maxSize]; // 为顺序表分配maxSize个存储单元
this.curlen = 0; // 置顺序表的当前长度为0
}
// 求顺序表中的数据元素个数并由函数返回其值
public int length() {
return curlen; // 返回顺序表的当前长度
}
// 在当前顺序表的第i个结点之前插入一个RecordNode类型的结点x
//其中i取值范围为：0≤i≤length()。
//如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,
//当i=length()时表示在表尾插入一个数据元素x
public void insert(int i, RecordNode x) throws Exception {
if (curlen == r.length) { // 判断顺序表是否已满
throw new Exception("顺序表已满");
}
if (i < 0 || i > curlen) { // i小于0或者大于表长
throw new Exception("插入位置不合理");
}
for (int j = curlen; j > i; j--) {
r[j] = r[j - 1]; // 插入位置及之后的元素后移
}
r[i] = x; // 插入x
this.curlen++; // 表长度增1
}
public void display() { //输出数组元素
for (int i = 0; i < this.curlen; i++) {
System.out.print(" " + r[i].key.toString());
}
System.out.println();
}
public void display(int sortMode) { //输出数组元素
int i;
if(sortMode==9) //带监视哨的直接插入排序方法，0号单元用于存放监视哨
i=1;
else
i=0;
for (; i < this.curlen; i++) {
System.out.print(" " + r[i].key.toString());
}
System.out.println();
}
}
排序是计算机内经常进行的一种操作，是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。
关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
插入排序
直接插入排序
待排序记录依次存放在数据r[0..n-1]中。
步骤：
- 查找
r[i]的插入位置：将r[i]暂存在临时变量temp中，将temp与r[j](j=i-1, …, 0)依次进行比较； - 将处在
r[i]前面并且比r[i]大的后移，r[i]插入到第j+1个位置； - 从
1~n-1重复1.和2.操作，实现整个序列的排序。
//【要求掌握代码默写】 不带监视哨的直接插入排序算法
public void insertSort() {
RecordNode temp;
int i, j;
// System.out.println("直接插入排序");
for (i = 1; i < this.curlen; i++) {//n-1趟扫描
temp = r[i]; //将待插入的第i条记录暂存在temp中
for (j = i - 1; j >= 0 && temp.key.compareTo(r[j].key) < 0; j--) { //将前面比r[i]大的记录向后移动
r[j + 1] = r[j];
}
r[j + 1] = temp; //r[i]插入到第j+1个位置
// System.out.println("第" + i + "趟: ");
// display();
}
}
循环条件中的“j >= 0”是控制下标越界的。可以进行改进：
-
将待排序的
n条记录从下标为1的存储单元开始依次存放在数组中； -
将顺序表的第
0个存储单元设置为一个“监视哨”，替代原来的temp。这样也不需要比较下标是否越界。
//【要求掌握代码默写】带监视哨的直接插入排序算法
public void insertSortWithGuard() {
int i, j;
System.out.println("带监视哨的直接插入排序");
for (i = 2; i <this.curlen; i++) { //n-1趟扫描
r[0] = r[i]; //将待插入的第i条记录暂存在r[0]中，同时r[0]为监视哨
for (j = i - 1; r[0].key.compareTo(r[j].key) < 0; j--) { //将前面较大元素向后移动
r[j + 1] = r[j];
}
r[j + 1] = r[0]; // r[i]插入到第j+1个位置
// System.out.println("第" + i + "趟: ");
// display();
}
}
[!NOTE] 不带监视哨的直接插入排序性能分析 平均时间为O(n^2)。只需要一个辅助空间
temp。是稳定排序。最优情况是完全有序，此时比较
n-1次，移动2(n-1)次。最劣情况是完全逆序，此时比较
(n-1)(n-2)/2次，移动(n+4)(n-1)/2次。
希尔排序
将 n 个记录分成 d 个子序列。例如：子序列{r[0],r[0+d],[0+2d],…,r[0+kd]}、子序列{r[1],r[1+d],r[1+2d],…,r[1+kd]}、…、子序列{ r[d-1],r[2d-1],r[3d-1],…,r[d+kd-1]}。
d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。
//【算法7.3不要求】希尔排序算法
public void shellSort(int[] d) { //d[]为增量数组
RecordNode temp;
int i, j;
System.out.println("希尔排序");
//控制增量，增量减半，若干趟扫描
for (int k = 0; k < d.length; k++) {
//一趟中若干子表，每个记录在自己所属子表内进行直接插入排序
int dk = d[k];
for (i = dk; i < this.curlen; i++) {
temp = r[i];
for (j = i - dk; j >= 0 && temp.key.compareTo(r[j].key) < 0; j -= dk) {
r[j + dk] = r[j];
}
r[j + dk] = temp;
}
System.out.print("增量dk=" + dk + " ");
display();
}
}
[!NOTE] 希尔排序性能分析 时间复杂度不确定，取决于增量序列，最优为O(n\log_2n)。
只需要一个辅助空间
temp。是不稳定排序。
交换排序
冒泡排序
小关键字的记录好像水中的气泡一样向上浮；大关键字的记录如水中的石块向下沉。
从第一个记录开始，依次对无序区中相邻记录进行关键字比较，如果大在上小在下，则交换。
每经过一趟“冒泡”，若出现交换操作，那么无序区的长度减一。若该趟没有发生交换操作，说明排序完成。
第i趟扫描时 ,r[0]到r[n-i]和r[n-i+1]到r[n－1]分别为当前的无序区和有序区。
结束条件为最后一趟没有进行“交换记录”。
//【要求掌握代码默写】 冒泡排序算法
public void bubbleSort() {
// System.out.println("冒泡排序");
RecordNode temp; //辅助结点
boolean flag = true; //是否交换的标记
for (int i = 1; i < this.curlen && flag; i++) { //有交换时再进行下一趟，最多n-1趟
flag = false; //假定元素未交换
for (int j = 0; j < this.curlen - i; j++) { //一次比较、交换
if (r[j].key.compareTo(r[j + 1].key) > 0) { //逆序时，交换
temp = r[j];
r[j] = r[j + 1];
r[j + 1] = temp;
flag = true;
}
}
// System.out.print("第" + i + "趟: ");
// display();
}
}
[!NOTE] 冒泡排序性能分析 平均时间为O(n^2)。需要一个辅助空间
temp和一个记录空间flag。是稳定排序。最优情况是完全有序，此时只需一趟冒泡，比较
n-1次，不需要移动。最劣情况是完全逆序，此时需
n-1趟冒泡，比较n(n-1)/2次，移动3n(n-1)/2次。
快速排序
找一个记录作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。
一趟排序之后无序序列r[s..t]将分割成两部分，枢轴处在分界处。
以首结点为枢轴，考虑的结点序列为r[i],r[i+1],…,r[j]且i<j。令枢轴pivot= r[i]。
如果i!=j，则进行判断：
如果j处的值比枢轴大，说明符合条件，将j前移一位继续比较j处值与枢轴值；如果j处的值小于等于枢轴，那么交换i值与j值并让i后移一位，然后进行下一步操作：
如果i处值小于等于枢轴值，说明符合条件，i后移一位，并继续比较i处值与枢轴值；如果i处值大于枢轴值，说明需要交换i值与j值，并让j前移一位，重新回到i!=j的比较。
i==j时把枢轴值赋给i处，算法结束。
再递归对产生的左右两部分序列重新应用算法即可。
//【算法7.5】一趟快速排序
//交换排序表r[i..j]的记录，使支点记录到位，并返回其所在位置
//此时，在支点之前(后)的记录关键字均不大于(小于)它
public int Partition(int i, int j) {
RecordNode pivot = r[i]; //第一个记录作为支点记录
// System.out.print(i + ".." + j + ", pivot=" + pivot.key + " ");
while (i < j) { //从表的两端交替地向中间扫描
while (i < j && pivot.key.compareTo(r[j].key) <= 0) {
j--;
}
if (i < j) {
r[i] = r[j]; //将比支点记录关键字小的记录向前移动
i++;
}
while (i < j && pivot.key.compareTo(r[i].key) > 0) {
i++;
}
if (i < j) {
r[j] = r[i]; //将比支点记录关键字大的记录向后移动
j--;
}
}
r[i] = pivot; //支点记录到位
// display();
return i; //返回支点位置
}
//【算法7.6】 递归形式的快速排序算法
//对子表r[low..high]快速排序
public void qSort(int low, int high) {
if (low < high) {
int pivotloc = Partition(low, high); //一趟排序，将排序表分为两部分
qSort(low, pivotloc - 1); //低子表递归排序
qSort(pivotloc + 1, high); //高子表递归排序
}
}
//【算法7.7】顺序表快速排序算法
public void quickSort() {
qSort(0, this.curlen - 1);
}
[!NOTE] 快速排序性能分析 平均时间为O(n\log_2n)。需要辅助空间O(\log_2n)（递归调用栈的深度）。是不稳定排序。
最优情况是每次划分恰好分成两个等长的子序列，此时问题规模缩减最快。
最劣情况是完全有序，每次划分只分出一个子序列，而枢轴处在一端。此时时间劣化为O(n^2)。
为防止最劣情况发生，划分前一般选取序列首尾和中央的三个值取中位数作为枢轴。
选择排序
直接选择排序
在所有记录中选出关键字值最小的记录，把它与第一个记录进行位置交换，然后在其余的记录中再选出关键字值次小的记录与第二个记录进行位置交换。直至所有均有序。
//【要求掌握代码默写】直接选择排序
public void selectSort() {
// System.out.println("直接选择排序");
RecordNode temp; //辅助结点
for (int i = 0; i < this.curlen - 1; i++) {//n-1趟排序
//每趟在从r[i]开始的子序列中寻找最小元素
int min = i; //设第i条记录的关键字最小
for (int j = i + 1; j < this.curlen; j++) {//在子序列中选择关键字最小的记录
if (r[j].key.compareTo(r[min].key) < 0) {
min = j; //记住关键字最小记录的下标
}
}
if (min != i) { //将本趟关键字最小的记录与第i条记录交换
temp = r[i];
r[i] = r[min];
r[min] = temp;
}
// System.out.print("第" + (i + 1) + "趟: ");
// display();
}
}
[!NOTE] 直接选择排序性能分析 平均时间为O(n^2)。只需要一个辅助空间
temp。是不稳定排序。比较
(n-1)(n-2)/2次，移动0 ~ 3(n-1)次。
树形选择排序
首先针对n个记录进行两两比较，比较的结果是把关键字值较小者作为优胜者上升到父结点，这些优胜者作为第一步比较的结果保留下来；然后对这些优胜者再进行关键字的两两比较，如此重复，直到选出一个关键字值最小的记录为止。
要求出次小关键字记录，只需将叶子结点中最小的关键字值改为“∞”。从下到上修改从该叶子结点到根结点路径上的所有结点的关键字值，则可得到次小关键字记录。
如果n不是2的k次幂，需要将叶子结点补足到k次幂个，保证是一棵满二叉树。
//【算法7.9】 树形选择排序(锦标赛排序)
//建立树的顺序存储数组tree,并对其排序，并将结果返回到r中
void tournamentSort() {
TreeNode[] tree; //胜者树结点数组
int leafSize = 1; //胜者树的叶子结点数
//得到胜者树叶子结点(外结点)的个数，该个数必须是2的幂
while (leafSize < this.curlen) {
leafSize *= 2;
}
int TreeSize = 2 * leafSize - 1; //胜者树的所有节点数
int loadindex = leafSize - 1; //叶子结点(外结点)存放的起始位置
tree = new TreeNode[TreeSize];
int j = 0;
//把待排序结点复制到胜者树的叶子结点中
for (int i = loadindex; i < TreeSize; i++) {
tree[i] = new TreeNode();
tree[i].index=i;
if (j < this.curlen) { //复制结点
tree[i].active=1;
tree[i].data=r[j++];
} else {
tree[i].active=0 ; //空的外结点
}
}
int i = loadindex; //进行初始比较查找关键码最小结点
while (i > 0) { //产生胜者树
j = i;
while (j < 2 * i) { //处理各对比赛者
if (tree[j + 1].active == 0 || ((tree[j].data).key.compareTo((tree[j + 1].data).key)) <= 0) {
tree[(j - 1) / 2] = tree[j]; //左孩子(胜者)赋值给父结点
} else {
tree[(j - 1) / 2] = tree[j + 1]; //右孩子(胜者)赋值给父结点
}
j += 2; //下一对比赛者
}
i = (i - 1) / 2; //处理上层结点
}
for (i = 0; i < this.curlen - 1; i++) { //处理剩余的n-1个记录
r[i] = tree[0].data; //将胜者树的根(最小者)存入数组r
tree[tree[0].index].active=0; //该元素相应外结点不再比赛
updateTree(tree, tree[0].index); //调整胜者树
}
r[this.curlen - 1] = tree[0].data;
}
//【算法7.10】树形选择排序的调整算法，i是当前最小关键字记录的下标
void updateTree(TreeNode[] tree, int i) {
int j;
if (i % 2 == 0) { //i为偶数，对手为左结点
tree[(i - 1) / 2] = tree[i - 1];
} else { //i为奇数，对手为右结点
tree[(i - 1) / 2] = tree[i + 1];
}
i = (i - 1) / 2; //最小元素输出后，其对手上升到父结点
while (i > 0) { //直到i==0
if (i % 2 == 0) { //i为偶数，对手为左结点
j = i - 1;
} else { //i为奇数，对手为右结点
j = i + 1;
}
//比赛对手中有一个为空
if (tree[i].active == 0 || tree[j].active == 0) {
if (tree[i].active == 1) {
tree[(i - 1) / 2] = tree[i]; //i可参选，i上升到父结点
} else {
tree[(i - 1) / 2] = tree[j]; //否则，j上升到父结点
}
} else //双方都可参选
//关键码小者上升到父结点
if ((tree[i].data).key.compareTo((tree[j].data).key) <= 0) {
tree[(i - 1) / 2] = tree[i];
} else {
tree[(i - 1) / 2] = tree[j];
}
i = (i - 1) / 2; //i上升到父结点
}
}
[!NOTE] 树形选择排序性能分析 平均时间为O(n\log_2n)。需要辅助空间以存放胜者树。是稳定排序。
n<=2^k时胜者树需要使用2\times 2^k-1个结点的顺序表。
堆排序
大顶堆是根结点值大于等于左右子树的根结点值的完全二叉树。小顶堆是根结点值小于等于左右子树的根结点值的完全二叉树。该关系可以映射在数组表示的完全二叉树。
筛选：对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。
建堆是一个从下往上进行“筛选”的过程。
首先建堆：把待排序的记录序列对应成一棵完全二叉树，并把它转换成一个初始堆。此时根结点具有最大或最小值。
然后交换根结点和最后一个结点（即第n个结点）的位置，把此时的最后结点排除在筛选范围之外。对剩下的完全二叉树继续进行建堆。
重复上述过程，直到剩下一个根结点为止。
//【算法7.11】将以筛选法调整堆算法
//将以low为根的子树调整成小顶堆，low、high是序列下界和上界
public void sift(int low, int high) {
int i = low; //子树的根
int j = 2 * i + 1; //j为i结点的左孩子
RecordNode temp = r[i];
while (j < high) { //沿较小值孩子结点向下筛选
if (j < high - 1 && r[j].key.compareTo(r[j + 1].key) > 0) {
j++; //数组元素比较,j为左右孩子的较小者
}
if (temp.key.compareTo(r[j].key) > 0) { //若父母结点值较大
r[i] = r[j]; //孩子结点中的较小值上移
i = j;
j = 2 * i + 1;
} else {
j = high + 1; //退出循环
}
}
r[i] = temp; //当前子树的原根值调整后的位置
// System.out.print("sift " + low + ".." + high + " ");
// display();
}
//【算法7.12】 堆排序算法
public void heapSort() {
// System.out.println("堆排序");
int n = this.curlen;
RecordNode temp;
for (int i = n / 2 - 1; i >= 0; i--) {//创建堆
sift(i, n);
}
for (int i = n - 1; i > 0; i--) {//每趟将最小值交换到后面，再调整成堆
temp = r[0];
r[0] = r[i];
r[i] = temp;
sift(0, i);
}
}
[!NOTE] 堆排序性能分析 平均时间为O(n\log_2n)。只需要一个辅助空间
temp。是不稳定排序。堆的深度为k时，每次筛选需要进行最多
2(k-1)次比较。n个关键字排序会比较至多4n次。一共调整堆顶n-1次。
归并排序
通常采用的是2-路归并排序，即将两个位置相邻的记录有序子序列归并为一个记录的有序序列。这个操作适合于顺序表。
//【算法7.13】两个有序序列的归并算法
//把r数组中两个相邻的有序表r[h]-r[m]和r[m+1]-r[t]归并为一个有序表order[h]-order[t]
public void merge(RecordNode[] r, RecordNode[] order, int h, int m, int t) {
int i = h, j = m + 1, k = h;
while (i <= m && j <= t) {//将r中两个相邻子序列归并到order中
if (r[i].key.compareTo(r[j].key) <= 0) {//较小值复制到order中
order[k++] = r[i++];
} else {
order[k++] = r[j++];
}
}
while (i <= m) {//将前一个子序列剩余元素复制到order中
order[k++] = r[i++];
}
while (j <= t) {//将后一个子序列剩余元素复制到order中
order[k++] = r[j++];
}
}
//【算法7.14】一趟归并算法
//把数组r[n]中每个长度为s的有序表两两归并到数组order[n]中
//s 为子序列的长度，n为排序序列的长度
public void mergepass(RecordNode[] r, RecordNode[] order, int s, int n) {
System.out.print("子序列长度s=" + s + " ");
int p = 0; //p为每一对待合并表的第一个元素的下标，初值为0
while (p + 2 * s - 1 <= n - 1) { //两两归并长度均为s的有序表
merge(r, order, p, p + s - 1, p + 2 * s - 1);
p += 2 * s;
}
if (p + s - 1 < n - 1) { //归并最后两个长度不等的有序表
merge(r, order, p, p + s - 1, n - 1);
} else {
for (int i = p; i <= n - 1; i++) //将剩余的有序表复制到order中
{
order[i] = r[i];
}
}
}
//【算法7.15】2-路归并排序算法
public void mergeSort() {
System.out.println("归并排序");
int s = 1; //s为已排序的子序列长度，初值为1
int n = this.curlen;
RecordNode[] temp = new RecordNode[n]; //定义长度为n的辅助数组temp
while (s < n) {
mergepass(r, temp, s, n); //一趟归并，将r数组中各子序列归并到temp中
display();
s *= 2; //子序列长度加倍
mergepass(temp, r, s, n); //将temp数组中各子序列再归并到r中
display();
s *= 2;
}
}
[!NOTE] 归并排序性能分析 平均时间为O(n\log_2n)。需要同等大小的顺序表作为辅助空间
O(n)。是稳定排序。每趟归并耗费O(n)时间，共进行\left\lceil \log_{2} n \right\rceil趟。
基数排序
基数排序借助“多关键字排序”的思想来实现“单关键字排序”。
多关键字的排序
链式基数排序
第8章 查找
查找，就是在由一组记录组成的集合中寻找主关键字值等于给定值的某个记录，或是寻找属性值符合特定条件的某些记录。
查找表是一种以同一类型的记录构成的集合为逻辑结构，以查找为核心运算的数据结构。集合中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
-
对查找表经常进行的操作：建表、查找、读表元（相当于遍历）、修改（增删等）。
-
静态查找表：仅作查找和读表元操作的查找表。
-
动态查找表：需做修改操作的查找表。例如查找的记录不存在时插入，或是查找记录存在时删除。
平均查找长度ASL是为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。它衡量一个查找算法效率的时间优劣。
静态表查找
// 顺序表记录结点类
public class RecordNode {
private Comparable key; //关键字
private Object element; //数据元素
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public Comparable getKey() {
return key;
}
public void setKey(Comparable key) {
this.key = key;
}
public RecordNode(Comparable key) { //构造方法1
this.key = key;
}
public RecordNode(Comparable key, Object element) { //构造方法2
this.key = key;
this.element = element;
}
public String toString() { //覆盖toString()方法
return "[" + key + "," + element + "]";
}
}
静态查找表由于不涉及增删，一般采用顺序存储。
顺序查找
// 【算法8.1】顺序查找算法
// 从顺序表r[0]到r[n-1]的n个元素中顺序查找出关键字为key的记录
// 若查找成功返回其下标，否则返回-1
public int seqSearch(Comparable key) {
int i = 0, n = length();
while (i < n && r[i].getKey().compareTo(key) != 0) {
i++;
}
if (i < n) { //查找成功则返回该元素的下标i，否则返回-1
return i;
} else {
return -1;
}
}
//【要求掌握默写】带监视哨的顺序查找算法
// 从顺序表r[1]到r[n]的n个元素中顺序查找出关键字为key的元素
// 若查找成功返回其下标，否则返回-1
public int seqSearchWithGuard(Comparable key) {
int i = length() - 1;
r[0].setKey(key); //哨兵
while ((r[i].getKey()).compareTo(key) != 0) {
i--;
}
if (i > 0) {
return i;
} else {
return -1;
}
}
从顺序表的一端开始，依次将每一个数据元素的关键字值与给定值key进行比较，若某个数据元素的关键字值等于给定值key，则表明查找成功；若直到所有数据元素都比较完毕，仍找不到关键字值为key的数据元素，则表明查找失败。
二分查找
//【要求掌握默写】二分查找算法
// 数组元素已按升序排列，若查找成功返回元素下标，否则返回-1
public int binarySearch(Comparable key) {
if (length() > 0) {
int low = 0, high = length() - 1; //查找范围的下界和上界
while (low <= high) {
int mid = (low + high) / 2; //中间位置，当前比较元素位置
// System.out.print(r[mid].getKey() + "? ");
if (r[mid].getKey().compareTo(key) == 0) {
return mid; //查找成功
} else if (r[mid].getKey().compareTo(key) > 0) { //给定值更小
high = mid - 1; //查找范围缩小到前半段
} else {
low = mid + 1; //查找范围缩小到后半段
}
}
}
return -1; //查找不成功
}
[!Question] 求对一有序表进行折半查找的判定树，并求出其在等概率时查找成功和查找不成功的平均查找长度。
以最小代价，保持中序遍历有序性。查找距离插入位置最近的、平衡因子为2或-2的结点，对以该结点为根的树进行调整，调整后再检查是否平衡。
[!Question] 给定一关键字序列，构造其平衡二叉树。
[!Question] 给定一层数为n的平衡二叉树，问其最小的叶子结点可能的所在层数。
[!TIP] 使用公式求给定条件下的平衡二叉树信息 以N_h表示深度为h的平衡二叉树的最少结点数，则有递推式： \begin{gathered}N_{h}=N_{h-1}+N_{h-2}+1\\ N_{0}=0,\ N_{1}=1,\ N_{2}=2\end{gathered} 可以推导出： N_{h}=\frac{\left( \frac{1+\sqrt{5}}{2} \right)^{h+2}}{\sqrt{5}} -1=\frac{\phi^{h+2}}{\sqrt{5}} -1 所以含n个结点的平衡二叉树的最大高度： h=\log_{\phi} \left( \sqrt{5} \left( n+1 \right) \right) -2
[!Question] 给定关键字序列，给定哈希函数，给定处理冲突方案，构造相应哈希表，并确定等概率查找时的效率
《Hello 算法》笔记
第2章 复杂度分析
递归通常比迭代更加耗费内存空间，通常比循环的时间效率更低。如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归。
- 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
- 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。
递归处理分治问题时，会生成递归树。
时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。本质上是计算“操作数量T(n)”的渐近上界。
具体计算时，忽略T(n)中的常数项和所有系数，循环嵌套时使用乘法。时间复杂度由T(n)中最高阶的项来决定。 O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) “最差时间复杂度”对应函数渐近上界，使用大O记号表示。相应地，“最佳时间复杂度”对应函数渐近下界，用\Omega记号表示。最差时间复杂度和最佳时间复杂度只出现于“特殊的数据分布”，而平均时间复杂度可以体现算法在随机输入数据下的运行效率，用\Theta记号来表示。
对于较为复杂的算法，计算平均时间复杂度往往比较困难，因为很难分析出在数据分布下的整体数学期望。在这种情况下，我们通常使用最差时间复杂度作为算法效率的评判标准。
空间复杂度用于衡量算法占用内存空间随着数据量变大时的增长趋势。
算法在运行过程中使用的内存空间主要包括输入空间、暂存空间、输出空间。暂存空间可以进一步划分为暂存数据、栈帧空间、指令空间。空间复杂度的统计范围一般是暂存数据、栈帧空间和输出数据三部分。
通常只关注最差空间复杂度。在递归函数中，需要注意统计栈帧空间。因为递归与循环不同：单次循环结束时初始化变量或调用函数占用的内存会释放，而递归会累积占用空间。
降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。
第3章 数据结构
逻辑结构揭示了数据元素之间的逻辑关系，即线性还是非线性。
物理结构反映了数据在计算机内存中的存储方式，是连续分布还是分散。
所有数据结构都是基于数组、链表或二者的组合实现的。数组初始化后长度不可变，因此称为静态数据结构；链表则称为动态数据结构。
基本数据类型是 CPU 可以直接进行运算的类型，以二进制的形式存储在计算机中。基本数据类型提供了数据的“内容类型”，而数据结构提供了数据的“组织方式”。
第4章 数组与链表
4.1 数组
元素在数组中的位置称为该元素的索引，本质上是内存地址的偏移量。
访问数组元素非常高效，时间复杂度O(1)。但进行数组的插入与删除就比较麻烦（时间复杂度O(n)），还可能造成丢失元素、内存浪费。数组扩容也相当麻烦。
数组是线性存储的，查找数组元素的一般方法称为“线性查找”。
缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
4.2 链表
链表的组成单位是节点对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。在 C、C++、Go 和 Rust 等支持指针的语言中，“引用”应被替换为“指针”。
通常将头节点当作链表的代称，尾节点指向的是“空”。
链表中插入节点非常容易，只需改变两个节点引用（指针）即可。链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。
链表中访问节点的效率较低，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。遍历链表查找节点也属于线性查找。
常见的链表类型包括单向链表、双向链表和环形链表。
4.3 列表
列表是一个抽象的数据结构概念，表示元素的有序集合，可以基于链表或数组实现。
动态数组继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。许多编程语言中的标准库提供的列表是基于动态数组实现的。
第5章 栈与队列
5.1 栈
栈是一种遵循先入后出逻辑的线性数据结构。堆叠元素的顶部称为“栈顶”，底部称为“栈底”。只能在栈顶添加或删除元素，因此栈可以视为一种受限制的数组或链表。
元素入栈（push）、栈顶元素出栈（pop）、访问栈顶元素（peek）。
5.2 队列
队列是一种遵循先入先出规则的线性数据结构。队列头部称为“队首”，尾部称为“队尾”。
元素入队，即将元素添加至队尾（push）、队首元素出队（pop）、访问队首元素（peek）。
用数组实现队列时，由于pop时需要不断对所有元素进行移动，很麻烦，所以可以通过移动指向队首和队尾的指针来确定哪里入队哪里出队。此时，为了防止指针的索引溢出，使用求余运算将原数组改造成环形数组。
5.3 双向队列
双向队列允许在头部和尾部执行元素的添加或删除操作。可以同时实现访问队首队尾元素、将元素添加至队首队尾、删除队首队尾元素。
第6章 哈希表
6.1 哈希表
哈希表建立了键key与值value之间的映射，通过键能够对值进行各项操作。在哈希表中进行增删查改非常高效（O(1)）。
进行遍历时，可以遍历键值对，也可以单独遍历键和遍历值。
使用数组实现哈希表时，数组中的每个空位存储一个键值对，称为一个桶。把key输入某一函数（即哈希函数hash()）得到的值再对桶数量（数组长度）capacity 取模，这样能得到该key对应桶的索引，也就找到了value。
6.2 哈希冲突
由于哈希函数输入的key的空间远大于输出的索引空间，理论上一定存在“多个输入对应同一输出”的情况。即哈希冲突。
通过扩容哈希表来减少哈希冲突简单有效但异常繁琐，非必要不扩容。\underset{\text{load factor}}{\text{负载因子}} =\frac{\text{已存储键值对数目，即哈希表元素数}}{\text{桶数，即数组长度}}是重要的哈希表扩容的触发条件。超过某一阈值，编程语言会自动扩容一倍。
改良哈希表数据结构使得哈希表可以在出现哈希冲突时正常工作，改良方法主要包括“链式地址”和“开放寻址”。
[!NOTE] 链式地址
此时基于链式地址实现的哈希表的操作方法也会发生变化。这种改良导致哈希表占用空间增大，并且查询效率下降。当链表很长时，查询效率会很差（
O(n)）。
[!NOTE] 开放寻址 这种改良不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突。探测方式主要包括线性探测、平方探测和多次哈希等。
[!Example] 线性探测
- 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为1），直至找到空桶，将元素插入其中。
- 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素返回
value；如果遇到空桶说明目标元素不在哈希表中，返回None。线性探测容易产生“聚集现象”，导致操作效率劣化。
[!Example] 平方探测 当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即1、4、9……
线性探测的聚集效应虽然得到缓解却依旧存在。并且平方探测可能不会探测整个哈希表，因此会略过存在的空桶。
[!Example] 多次哈希 使用多个哈希函数进行探测。
- 插入元素：若哈希函数f_1(x)出现冲突，则尝试f_2(x)，以此类推直到找到空位后插入元素。
- 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，返回
None。不能在开放寻址哈希表中直接删除元素，因为这会在数组内产生一个空桶，查询元素时，在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在。为了解决该问题，采用懒删除机制。
[!NOTE] 懒删除机制 不直接从哈希表中移除元素，而是利用一个常量
TOMBSTONE来标记这个桶。在该机制下
None和TOMBSTONE都代表空桶，都可以放置键值对。但不同的是，探测到TOMBSTONE时应该继续遍历，因为其之下可能还存在键值对。随着
TOMBSTONE的增加，搜索时间也会增加，因此懒删除可能会加速哈希表的性能退化。为此，考虑在探测中记录遇到的首个TOMBSTONE的索引，并将搜索到的目标元素与该TOMBSTONE交换位置以优化效率。
各种编程语言采取了不同的哈希表实现策略。Java采用链式地址。
6.3 哈希算法
键值对的分布情况由哈希函数决定，设计好哈希算法有助于降低哈希冲突。哈希算法应该具备：
- 确定性、效率高、均匀分布
密码学上，对哈希算法提出更高的要求：
- 单向性、抗碰撞性、雪崩效应
哈希算法的最后一步都是对大质数取模，这样能保证哈希值落在一定范围内，并且最大程度保证均匀分布。
在许多编程语言中，只有不可变对象才可作为哈希表的key。自定义对象虽然其成员可变，但它是可哈希的，因为对象的哈希值通常是基于内存地址生成的。
第7章 树
7.1 二叉树
二叉树的基本单元是节点（包含值、左子节点引用和右子节点引用）。除叶节点外，其他所有节点都包含子节点和非空子树。
根节点、叶节点、边、节点所在的层、节点的度、二叉树的高度、节点的深度、高度。
插入节点可能会改变二叉树的原有逻辑结构，而删除节点通常意味着删除该节点及其所有子树。两种操作一般综合使用。
二叉树可进行分类：
-
满二叉树（完美二叉树）：所有层的节点都被完全填满。叶节点的度为0，其余所有节点的度都为2。节点总数为2^{h+1}-1，其中h为二叉树高度。
-
完全二叉树：只有最底层的节点未被填满，且最底层节点尽量靠左填充。
-
完满二叉树：除了叶节点之外，其余所有节点都有两个子节点。
-
平衡二叉树：任意节点的左子树和右子树的高度之差的绝对值不超过1。
满二叉树是理想情况，而最差情况是退化为链表。
7.2 二叉树遍历
通过指针逐个访问节点，并且需要借助搜索算法来实现。二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。
[!Example] 层序遍历 从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。时间复杂度为O(n)，空间复杂度为O(n)。
本质上属于广度优先遍历，也称广度优先搜索，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。通常借助“队列”来实现。
[!Example] 前序、中序、后序遍历 都属于深度优先遍历，也称深度优先搜索，它体现了一种“先走到尽头，再回溯继续”的遍历方式。时间复杂度为O(n)，空间复杂度为O(n)。
就像是绕着整棵二叉树的外围“走”一圈。在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。通常基于递归或迭代实现。
7.3 二叉树数组表示
对于完美二叉树，用层序遍历的顺序把每个节点存储在数组中。可利用“映射公式”（若某节点的索引为i，则该节点的左子节点索引为2i+1，右子节点索引为2i+2）确定父节点与子节点的索引。
而对于一般二叉树，先将其补为完美二叉树，再将原本缺失节点的数组索引处替换为null即可。
完全二叉树非常适合使用数组来表示，由于其独特的结构，可以在数组中省略掉所有null。
用数组表示二叉树，一方面访问和遍历比较高效，无需存储指针，还可随机访问节点；另一方面连续存储不适合数据量过大的情况，而且增删效率低下，过多的null还会浪费空间。
7.4 二叉搜索树
-
对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值。
-
任意节点的左、右子树也是二叉搜索树，即同样满足条件
1.。
满足以上两点的二叉树是二叉搜索树。
-
查找节点：通过循环比较当前节点值和所寻求的节点值之间的大小关系，判断所寻求的节点位于当前节点的左子树还是右子树。循环次数最多为二叉树的高度，即时间复杂度O(\log n)。
-
插入节点：先按上面的思路查找插入位置，找到后将节点放在
null的位置。若待插入节点在树中已存在，则不执行插入直接返回。插入节点使用O(\log n)时间。 -
删除节点：同样先对节点进行查找，但是这里需要对该节点的度进行分开处理：度为0直接使其指向
null即可；度为1就替换为它的子节点；度为2时不能直接删除，只能替换为右子树的最小节点或左子树的最大节点，并保持二叉搜索树的性质。删除节点使用O(\log n)时间。 -
中序遍历有序：二叉搜索树的中序遍历序列是升序的。因此在二叉搜索树中获取有序数据仅需O(n)时间，无须进行额外的排序操作。
多数操作下二叉搜索树比无序数组具有更稳定且高效的性能。只有在高频添加、低频查找删除数据的场景下，数组比二叉搜索树的效率更高。
在理想情况下，二叉搜索树是“平衡”的，这样就可以在\log n轮循环内查找任意节点。然而如果频繁地插入和删除节点，可能导致二叉树退化为链表。
第8章 堆
8.1 堆
堆是一种满足特定条件的完全二叉树，主要可分为小顶堆（任意节点的值\leqslant其子节点的值）和大顶堆（任意节点的值\geqslant其子节点的值）。其根节点称为“堆顶”，底层最靠右的节点称为“堆底”。
-
最底层节点靠左填充，其他层的节点都被填满。
-
对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。
堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，可以将“优先队列”和“堆”看作等价的数据结构。Java中提供PriorityQueue。
堆是完全二叉树，故使用数组来存储堆。对于数组中索引为i，其左子节点的索引为2i+1，右子节点的索引为2i+2，父节点的索引为\frac{i-1}{2}（向下整除）。
-
访问堆顶元素就是访问根节点，也就是索引为0。
-
元素入堆时，先将其添加到堆底，此时堆的成立条件可能已被破坏，因此要进行堆化（修复从插入节点到根节点的路径上的各个节点）。从入堆节点开始，从底至顶执行堆化。不断比较插入节点与其父节点的值，满足条件则交换位置。时间复杂度O(\log n)。
-
堆顶元素出堆时，先交换堆顶元素与堆底元素，再将堆底（原先的堆顶）删除，然后从根节点开始，从顶至底执行堆化。时间复杂度O(\log n)。
8.2 建堆操作
使用一个列表的所有元素来构建一个堆。
-
借助入堆操作实现：创建一个空堆，然后遍历列表依次对每个元素执行“入堆操作”。时间复杂度O(n \log n)。
-
通过遍历堆化实现：将列表所有元素原封不动地添加到堆中，再倒序遍历堆（层序遍历的倒序），依次对每个非叶节点执行“从顶至底堆化”。每当堆化一个节点后，以该节点为根节点的子树就形成一个合法的子堆。由于叶节点没有子节点，因此它们天然就是合法的子堆，无须堆化。推导后知时间复杂度O(n)。
8.3 Top-k问题
[!Question] 给定一个长度为n的无序数组
nums，请返回数组中最大的k个元素。
[!Example] 遍历选择 遍历k轮，每轮遍历找到第1,2,\dots,k大的元素。
遍历的方法只适合k\ll n的情况，当两者接近时，时间复杂度趋向于O(n^2)。
当k = n时得到完整的有序序列，此时等价于“选择排序”算法。
[!Example] 先排序再选取 先对数组
nums进行排序，再返回最右边的k个元素，时间复杂度O(n \log n)。
[!Example] 使用堆更为高效
- 初始化一个小顶堆（堆顶元素最小）。将数组的前k个元素依次入堆。
- 从第k+1个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
- 完成后，堆中保存的就是最大的k个元素，返回即可。
时间复杂度为O(n \log k)，介于O(n)与O(n \log n)之间。
第9章 图
9.1 图
图由顶点和边组成。相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高。
根据边是否具有方向，可分为无向图和有向图。根据所有顶点是否连通，可分为连通图和非连通图。给边添加“权重”变量后成为有权图。
邻接、路径、度（入度、出度）。
[!Example] 邻接矩阵
在简单图中，顶点不能与自身相连，此时邻接矩阵主对角线元素没有意义。
无向图的邻接矩阵关于主对角线对称。
将邻接矩阵的元素替换为权重，可表示有权图。
邻接矩阵的增删查改操作极为高效，但空间复杂度为O(n^2)。
[!Example] 邻接表 使用n个链表来表示图，链表节点表示顶点。
邻接表更加节省空间，但操作效率不如邻接矩阵。
当链表较长时，可以将链表转化为AVL树或红黑树，或是哈希表。
9.2 图的基础操作
[!Example] 基于邻接矩阵实现
添加或删除边：直接在邻接矩阵中修改。若为无向图还需要在对称位同时修改。
添加顶点：在邻接矩阵的尾部添加一行一列并填充0。使用O(n)时间。
删除顶点：在邻接矩阵中删除一行一列，并移动其余元素。因此删除首行首列时达到最差情况O(n^2)。
初始化：传入n个顶点，初始化长度为n的顶点列表使用O(n)时间；初始化邻接矩阵使用O(n^2)时间。
[!Example] 基于邻接表实现
添加边：在顶点对应链表的末尾添加边即可。若为无向图还需要在另一顶点处同时修改。使用O(1)时间。
删除边：在顶点对应链表中查找并删除指定边，若为无向图还需要在另一顶点处同时修改。使用O(m)时间。
添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，不需要添加与之相连的顶点。使用O(1)时间。
删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用O(n+m)时间。
初始化：在邻接表中创建n个顶点和m条边，使用O(n+m)时间。
（顶点总数为n、边总数为m）
9.3 图的遍历
树（一对多）的遍历操作也是图（多对多）的遍历操作的一种特例。
[!Example] 广度优先遍历 一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。
每访问一个节点就遍历该顶点的所有邻接顶点。
通常借助队列来实现：
- 将遍历起始顶点加入队列，并开启循环。
- 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
- 循环步骤
2.，直到所有顶点被访问完毕后结束。为防止重复遍历顶点，需要借助一个哈希集合（可以看作一个只存储
key而不存储value的哈希表）来记录哪些节点已被访问。
总体使用O(\left| V \right| + \left| E \right|)时间，使用O(\left| V \right|)空间。
[!NOTE] 广度优先遍历的序列不唯一，因为多个相同距离的顶点的遍历顺序允许被任意打乱。
[!Example] 深度优先遍历 一种优先走到底、无路可走再回头的遍历方式。这种“走到尽头再返回”的算法范式通常基于递归来实现。
与广度优先遍历类似，深度优先遍历中也需要借助一个哈希集合来记录已访问顶点，以避免重复访问。
总体使用O(\left| V \right| + \left| E \right|)时间，使用O(\left| V \right|)空间。
[!NOTE] 深度优先遍历序列的顺序也不是唯一的。
第10章 搜索
10.1 二分查找
基于分治策略。利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
[!Question] 给定一个长度为n的数组
nums，元素按从小到大的顺序排列且不重复。请查找并返回元素target在该数组中的索引。若数组不包含该元素，则返回-1。
设i = 0, j = n-1。两者分别指向数组首元素和末尾元素。搜索区间是\left[ 0, n-1 \right]闭区间。计算中点元素索引时一般用公式\left\lfloor i+\frac{j-i}{2} \right\rfloor而不是\left\lfloor \frac{j+i}{2} \right\rfloor，因为i+j可能超过int可用范围。
若设i = 0, j = n。则搜索区间是\left[ 0, n \right)左闭右开区间。此时若i=j则说明元素不存在。虽然两种方法相差无几，但一般建议采用“双闭区间”的写法。
时间复杂度O(\log n)，空间复杂度O(1)，且无须额外空间。
但是二分查找仅适用于有序数据且为数组。并且当数据量小时，线性查找往往优于二分查找。
10.2 二分查找插入点
二分查找还可用于解决许多变种问题，比如搜索目标元素的插入位置。（本节只讨论i,j双闭区间的写法）
[!Question] 给定一个长度为n的有序数组
nums和一个元素target。现将target插入数组nums中，并保持其有序性。若数组中已存在元素target，则插入到其左方。请返回插入后target在数组中的索引。
该问题分为两种情况：插入元素前，数组nums存在重复元素吗？
[!Example] 插入元素前
nums不存在重复元素 再次分为两种情况分析：
- 插入元素前，如果
nums中已经含有target：插入后所求的索引就是原先已存在target的索引，因为问题规定插入其左方。- 插入元素前，如果
nums中不含target：插入后所求的索引就是指针i。可以由i,j的移动规律推出。
[!Example] 插入元素前
nums存在重复元素 如果有多个target，此时如果只使用普通二分查找，会返回其中一个target的索引，而这个索引不一定是最左边的。因此考虑二分查找+线性查找的方法，先二分查找到一个target，再往左线性遍历，直到找到最左边的target。但这种方法效率较低。改良后，依然使用二分查找：每轮先计算中点索引，再判断
target和nums[m]的大小关系。采用普通二分查找缩小区间，逐渐逼近目标，直到nums[m] == target时，采用j = m - 1来缩小区间，最终返回i。
10.3 二分查找边界
查找插入点本质上是在查找最左一个target的索引。区别在于：查找边界的数组中不一定含有target。遇到异常情况直接返回-1。
- 查找右边界，可以转化为查找左边界的方法。将查找最右一个
target转化为查找最左一个target+1。此时返回的是j，即i+1。 - 可以构造一个数组中不存在的元素用于查找左右边界。查找最左一个
target可以转化为查找target-0.5，并返回指针i。查找最右一个target可以转化为查找target+0.5，并返回指针j。无须关心如何处理相等的情况。
10.4 哈希优化策略
常通过将线性查找替换为哈希查找来降低算法的时间复杂度。
[!Question] 给定一个整数数组
nums和一个目标元素target，请在数组中搜索“和”为target的两个元素，并返回它们的数组索引。返回任意一个解即可。
直接暴力枚举所有可能的组合并一一检验，这是用时间换空间，时间复杂度O(n^2)，空间复杂度O(1)。
使用哈希查找可以用空间换时间。考虑借助一个哈希表，键值对分别为数组元素和元素索引。遍历数组元素，每轮执行：
-
判断数字
target - nums[i]是否在哈希表中，若是，则直接返回这两个元素的索引。若否则不操作。（Java的HashMap提供containsKey方法） -
然后再将键值对
nums[i]与i放入哈希表。
时间复杂度O(n)，空间复杂度O(n)。相比暴力枚举更为均衡。
10.5 重识搜索算法
搜索算法用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素。
实现思路一般分为：
-
通过遍历数据结构来定位目标元素。
-
利用数据组织结构或数据包含的先验信息，实现高效元素查找。
暴力搜索遍历数据结构的每个元素来定位目标元素。优点是简单且通用性好，无须对数据做预处理和借助额外的数据结构。数据量较大的情况下性能较差。
-
线性搜索从线性数据结构一端向另一端遍历。
-
广度优先搜索和深度优先搜索遍历树或图时，前者由近及远逐层搜索，后者先一条路走到头再回溯。
自适应搜索利用数据的特有属性（例如有序性）来优化搜索过程。依赖于特定数据结构，往往需要对数据进行预处理或额外的数据结构。效率更高，甚至能优化至O(1)。
-
二分查找借助数组元素的有序性。
-
哈希查找利用键值对映射实现高效查询。
-
树查找在特定树结构中可用，通过比较节点来排除元素。
搜索算法的选择取决于数据体量、搜索性能要求、数据查询与更新频率等因素。
第11章 排序
11.1 排序算法
对一组数据按照特定顺序进行排列。数据类型可以是整数、浮点数、字符或字符串等，排序规则可根据需求设定。
评价维度：运行效率、就地性（减少数据的搬运操作）、稳定性（原先相等的元素在排序后相对位置不变）、自适应性（算法根据输入数据的已有信息来减少计算量）、是否基于比较（非比较排序的时间复杂度略优，但通用性较差）。
因此理想的排序算法应该是：运行快、原地、稳定、自适应、通用性好。
在对数据的多级排序时，可能对稳定性有较高要求。
11.2 选择排序
进行循环：每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n^2) | 非自适应排序 |
| 空间复杂度O(1) | 原地排序 |
| 非稳定排序 |
11.3 冒泡排序
连续地比较与交换相邻元素实现排序。先从最左端开始向右遍历，遇到左>右就交换，一直遍历至右端。如此每轮从剩余未冒泡元素开始进行迭代。
若发现某轮循环没有进行任何交换，说明已经完成排序了。可以通过增加一个flag来进行优化。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n^2)，优化后最佳达到O(n) | 自适应排序 |
| 空间复杂度O(1) | 原地排序 |
| 稳定排序 |
11.4 插入排序
在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，再将该元素插入到正确的位置。
初始状态下，数组的第 1 个元素已完成排序。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n^2)，但在数据量小的时候总是快于快速排序 | 自适应排序 |
| 空间复杂度O(1) | 原地排序 |
| 稳定排序 |
在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序。因为：
-
冒泡排序的计算开销过高；
-
选择排序总是以O(n^2)时间运行，无自适应能力；选择排序不稳定，不适于多级排序。
11.5 快速排序
基于分治策略，核心操作是“哨兵划分”，实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。
[!NOTE] 哨兵划分
先选择数组中的最左元素作为“基准数”，从右到左找首个小于基准数的元素，从左到右找首个大于基准数的元素；
再交换这两个元素；
然后将基准数交换至两个子数组的分界线；
最后返回基准数索引。
此时原数组被划分成三部分：左子数组、基准数、右子数组，并且左子数组任意元素\leqslant基准数\leqslant右子数组任意元素。
[!Caution] 哨兵划分中“从右往左查找”与“从左往右查找”的顺序不可交换。
通过对未排序的左子数组和右子数组分别递归执行“哨兵划分”直到子数组长度为1时终止。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n\log n)，所有元素相等或是完全倒序时最差，劣化为O(n^2)时间 | 非自适应排序 |
| 空间复杂度O(n)，使用尾递归优化后可至O(\log n) | 原地排序 |
| 非稳定排序 |
快速排序通常比归并排序、堆排序效率高，即便它们都是平均O(n\log n)时间。这是因为其出现最差情况（完全倒序）的概率很低，缓存使用效率高且复杂度的常数系数小。
最差情况下，可以对基准数的选取进行优化：即不从左端选取，而是随机选取一个元素或者随机选取多个元素并取中位数。这样可以降低时间劣化的概率。
在特定的输入下，当每轮“哨兵划分”过后，可能两个子数组的长度相差悬殊，这会导致问题规模减少得太慢，从而导致更多空间开销。可以在每轮哨兵排序完成后，比较两个子数组的长度，先对较短的子数组进行递归。这样可以减少递归调用栈的深度，即从n优化至\log n。
11.6 归并排序
基于分治策略，包含“划分”和“合并”两个阶段。
-
计算数组中点
mid，递归划分左子数组（区间[left, mid]）和右子数组（区间[mid + 1, right]）。 -
递归执行步骤
1.，直至子数组区间长度为 1 时终止。 -
从长度为1的子数组开始，从底至顶地将左子数组和右子数组合并为一个有序数组。合并阶段中的每个子数组都是有序的。
归并排序与二叉树后序遍历的递归顺序是一致的。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n\log n) | 非自适应排序 |
| 空间复杂度O(n)，在链表上可优化至O(1) | 非原地排序 |
| 稳定排序 |
在链表上使用归并排序有显著优势，划分阶段可使用迭代替换掉递归以节省栈帧空间；在合并阶段只需要指针操作即可完成短链表的合并。
11.7 堆排序
设数组的长度为n,
-
输入数组并建立大顶堆。完成后最大元素位于堆顶。
-
将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减
1，已排序元素数量加1。 -
从堆顶元素开始，从顶到底执行堆化操作。完成堆化后，堆的性质得到修复。
-
循环执行第
2.步和第3.步。循环n-1轮后即完成数组排序。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n\log n) | 非自适应排序 |
| 空间复杂度O(1) | 原地排序 |
| 非稳定排序 |
11.8 桶排序
桶排序基于分治，属于非比较排序算法。
先初始化k个桶，然后通过建立映射将n个桶分配到k个桶中。这一过程尽量保证所有桶内元素个数大致相等。
然后在各个桶内分别应用排序算法。
最后按照桶从小到大的顺序合并结果。
桶排序适用于处理体量很大的数据。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n+k)，当所有元素进入同一桶时最差，劣化为O(n^2) | 非自适应排序 |
| 空间复杂度O(n+k) | 非原地排序 |
| 取决于桶内部的排序算法是否稳定 |
最大化发挥桶排序优势的关键是元素在各个桶内的分布是平均的。为了实现平均分配，可以通过递归划分桶：进行一次划分后，将元素最多的桶再次划分为几个桶……直至所有桶内元素数量大致相当。
若已知元素的分布情况，可根据概率分布进行分桶。
11.9 计数排序
计数排序通过统计元素数量来实现排序，只适用于非负整数：
-
先遍历一次数组，找出最大数
m，然后创建一个长度为m+1的辅助数组counter。 -
每次遍历数组统计各个数字的出现次数，并将次数对应填入到
counter中。counter[num]就对应数字num的出现次数。 -
最后遍历
counter，将各个数字按照counter[num]中的次数依次填入nums即可。
但上述算法有局限，下面的算法完整地实现了计数排序：
-
按上述算法得到完整的
counter后，对counter内的数据求前缀和，也就是说修改后的counter[i]等于原先的counter[i-1] + counter[i-2] + ... + counter[0]。 -
counter所有元素都改为前缀和后，再令所有元素自减1。此时counter[i]的值恰好是排序过后的数组res中最后一个元素i的索引。 -
倒序遍历原数组
nums，对于每个被遍历到的元素num：-
先把该元素填入最终有序数组
res的索引counter[num]处。 -
再使
counter[num]自减1，从而使得下一个num还能使用该索引。
-
-
倒序遍历完成后，
res就是有序的了。
本质上，计数排序是桶排序在整型数据下的一个特例。计数排序虽然巧妙，但其条件苛刻：只适用于非负整数，且要求数据量n大但数据范围m小。
| 复杂度 | 排序特性 |
|---|---|
| 时间复杂度O(n+m)，但m过大时可能慢于O(n\log n) | 非自适应排序 |
| 空间复杂度O(n+m)，但m过大时占用空间也会过多 | 非原地排序 |
| 最后一步倒序遍历时是稳定排序，若是正序遍历就是非稳定排序 |
11.10 基数排序
基数排序的核心思想与计数排序一致，也通过统计个数来实现排序。但它克服了计数排序要求“数据量n大但数据范围m小”的限制。以8位数的排序为例：
-
先初始化位数
k = 1。 -
取出所有要排序的数据的第
k位并进行计数排序，此时所有数会以“第k位从小到大”的顺序排列。 -
k自增1，然后如此从低位到高位迭代完所有位数。
[!Caution] 必须从低位向高位排序，而不能倒过来，因为数字的高位优先级高于低位。
[!TIP] d进制数字x的\text{第}k\text{位数字}\ x_{k}=\left\lfloor\frac{x}{d^{k-1}}\right\rfloor\mod d
基数排序克服了数值范围不能过大的限制，但是它要求数据位数一致且位数不能过大。另外位数过大的浮点数也不适用该方法。
| 复杂度 | 排序特性 |
|---|---|
| O((n+d)k)，当d,k不大时趋向时间复杂度O(n) | 非自适应排序 |
| 空间复杂度O(n+d) | 非原地排序 |
| 稳定排序 |
第12章 分治
12.1 分治算法
分治（分而治之）通常基于递归实现，包括“分”和“治”两个步骤。
-
分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
-
治（合并阶段）：从已知解的最小子问题开始，从底至顶将子问题的解进行合并，从而构建出原问题的解。
归并排序就体现了分治思想。
[!TIP] 如何判断问题是否适合用分治解决？
问题可否拆解为更小且类似的子问题，并且还能以相同方式递归地进行划分。
子问题之间是否独立不依赖无重叠。
子问题的解可否最终合并为原问题的解。
分治不仅可以有效地解决算法问题，往往还可以提升算法效率。这是因为其同时优化了操作数量和并行计算（子问题间的独立允许并行解决，因此分治有利于操作系统的并行优化）。
[!Example] 分治在经典算法问题中的应用
寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后找出跨越两部分的最近点对。
大整数乘法：例如 Karatsuba 算法，它将大整数乘法分解为几个较小的整数的乘法和加法。
矩阵乘法：例如 Strassen 算法，它将大矩阵乘法分解为多个小矩阵的乘法和加法。
汉诺塔问题：汉诺塔问题可以通过递归解决，这是典型的分治策略应用。
求解逆序对：在一个序列中，如果前面的数字大于后面的数字，那么这两个数字构成一个逆序对。求解逆序对问题可以利用分治的思想，借助归并排序进行求解。
[!Example] 分治在算法和数据结构设计中的应用
二分查找；
归并排序、快速排序、桶排序；
树、堆、哈希表。
12.2 分治搜索策略
搜索算法分为暴力遍历和自适应搜索，后者利用特有的组织结构或先验信息优化效率。二分查找就是后者的典型，其基于分治思想。
现在使用递归（分治）来实现二分查找：
-
每次计算搜索区间的中点，然后排除一半。
-
再用递归求解一半大小的子问题，也就是被上一步一分为二的两个搜索区间。
-
循环前两步，直至找到目标或区间为空。
12.3 构建树问题
12.4 汉诺塔问题
第13章 回溯
13.1 回溯算法
回溯算法通过暴力穷举所有可能，当遇到解时将其记录，如此直至找到全部解或搜索完毕所有可能。
回溯算法通常采用“深度优先搜索”来遍历解空间。
之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。
[!Question] 给定一棵二叉树，搜索并记录所有值为k的节点，请返回节点列表。 这里访问每个节点都代表一次“尝试”，而越过叶节点或返回父节点的
return则表示“回退”。
[!Question] 在二叉树中搜索所有值为k的节点，请返回根节点到这些节点的路径。 借助一个列表
path记录访问过的节点路径，每次尝试都会把当前节点添加进入path来记录路径，而在回退时将该节点弹出（回溯）。访问到目标节点就将path复制进结果列表res，遍历完成后res就是所有解。
复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。
[!Question] 在二叉树中搜索所有值为k的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为s的节点。 约束条件是不包含值为s的节点，因此需要添加剪枝操作：搜索过程中只要遇到值为s的节点就提前返回。
可以得出回溯算法的主体框架：
-
尝试
-
回退
-
剪枝
/* 回溯算法框架 */
func backtrack(state *State, choices []Choice, res *[]State) {
// 判断是否为解
if isSolution(state) {
// 记录解
recordSolution(state, res)
// 不再继续搜索
return
}
// 遍历所有选择
for _, choice := range choices {
// 剪枝：判断选择是否合法
if isValid(state, choice) {
// 尝试：做出选择，更新状态
makeChoice(state, choice)
backtrack(state, choices, res)
// 回退：撤销选择，恢复到之前的状态
undoChoice(state, choice)
}
}
}
常用回溯算法术语
解（solution）：满足问题特定条件的答案，可能有一个或多个。
约束条件（constraint）：问题中限制解的可行性的条件，通常用于剪枝。
状态（state）：问题在某一时刻的情况，包括已经做出的选择。
尝试（attempt）：根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解。
回退（backtracking）：遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态。
剪枝（pruning）：根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率。