如果说编程语言是程序员的招式，那么数据结构和算法就相当于程序员的内功。所以要学好数据结构和算法，写这篇笔记的目的是为了自我不断积累。不积跬步，无以至千里！
在计算机科学中，除非有特别的声明，所有的对数都是以 2 为底的
记住：log 1 = 0，log 2 = 1，log 1024 = 10， log 1048576 = 20
如果 N 整除 A - B，那么就说 A 与 B 模 N 同余，记为 A ≡ B（mod N）
证明数据结构分析中的结论的两个最常用的方法是归纳法和反证法，证明一个定理不成立的最好的方法是举出一个反例。
- 归纳法证明
- 反证法证明
#include <stdio.h>
void printOut(int n){
if(n >= 10){
printOut(n / 10);
}
printf("%d", n % 10);
}
int main(){
int n, result;
scanf("%d", &n);
printOut(n);
return 0;
}程序 = 数据结构 + 算法 是由 N.Wirth（沃斯）提出来的。
- 数据结构指的是数据与数据之间的逻辑关系
- 算法指的是解决特定问题的步骤和方法
理解下面三点：
算法（algorithm）是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。对于一个问题，一旦给定某种算法并且（以某种方式）确定其是正确的，那么重要的一步就是确定该算法将需要多少诸如时间或者空间等资源量的问题。
!> 如何评估算法时间开销？
所以要进行事前预估，事前预估算法时间开销 T(n) 与问题规模n的关系 (T表示“time”)
时间复杂度量级比较
$$
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
$$
算法可以原地工作——S(n)=O(1)
计算规则与时间复杂度类似
递归型算法
空间复杂度=递归调用的深度
【题目】
给定（可能有负数）整数a(1)、a(2)、……a(n)，求 a(1)+a(2)+……+a(j)的最大值。
为方便起见，若所有的整数为负数，则最大子序列和为0.
也就是：在一系列整数中，找出连续的若干个整数，这若干个整数之和 最大。
【代码实现】
- 方法一：穷举法
- 穷举所有可能，由于嵌套三层 for 循环，运行时间 O(N^3)
- 算法思想：算出每个子序列的和，即算出序列中第 i 个到第 j 个数的和 (j >= i) ，并进行比较
- C 语言版：函数原型为 int maxSubSum(int a[]);
#include <stdio.h>
int maxSubSum(int a[]){
int maxSum = 0;
int sum, i, j, k;
int len = sizeof(a) / sizeof(int);
for(i = 0; i < len; i++){
for(j = i; j < len; j++){
sum = 0;
for(k = i; k <= j; k++){
sum += a[k];//计算 a[i] 到 a[j] 的和
}
if(sum > maxSum){
maxSum = sum;
}
}
}
return maxSum;
}
int main(){
int a[] = {-2, 11, -4, 13, -5, -2};
int max = maxSubSum(a);
printf("%d\n",max);
return 0;
}- C 语言版：函数原型为 int maxSubSum(int a[], int n);
#include <stdio.h>
int maxSubSum(int a[], int n){
int maxSum = 0;
int sum, i, j, k;
for(i = 0; i < n; i++){
for(j = i; j < n; j++){
sum = 0;
for(k = i; k <= j; k++){
sum += a[k];//计算 a[i] 到 a[j] 的和
}
if(sum > maxSum){
maxSum = sum;
}
}
}
return maxSum;
}
int main(){
//int a[] = {-2, 11, -4, 13, -5, -2};
int a[] = { -2, 4, -3, 5, 7, -1, 8, 1 };
int len = sizeof(a) / sizeof(int);//有负数所以 strlen(a) 不能用
int max = maxSubSum(a, len);
printf("%d\n",max);
return 0;
}-
方法二：
- 在第一种的基础上简化，撤除一层 for 循环，运行时间 O(N^2)
- 算法思想：第一个算法的第三个 for 循环中有大量不必要的重复计算，如：计算 i 到 j 的和，然而 i 到 j-1 的和在前一次的循环中已经计算过，无需重复计算，故该 for 循环可以去掉
-
C 语言版
#include <stdio.h>
int maxSubSum(int a[], int n){
int maxSum = 0;
int sum, i, j;
for(i = 0; i < n; i++){
sum = 0;
for(j = i; j < n; j++){
sum += a[j];
if(sum > maxSum){
maxSum = sum;
}
}
}
return maxSum;
}
int main(){
//int a[] = {-2, 11, -4, 13, -5, -2};
int a[] = { -2, 4, -3, 5, 7, -1, 8, 1 };
int len = sizeof(a) / sizeof(int);//有负数所以 strlen(a) 不能用
int max = maxSubSum(a, len);
printf("%d\n",max);
return 0;
}- 方法三：分而治之
- 算法思想：把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。
- 在该问题中，如果把序列从中间分为两部分，那么最大子序列和可能在三处出现，要么整个出现在输入数据的左半部，要么整个出现在右半部，要么跨越分界线。前两种情况可以递归求解，第三种情况的最大和可以通过求出前半部分（包括前半部分的最后一个元素）的最大和以及后半部分（包含后半部分的第一个元素）的最大和而得到，此时将两个和相加。
- 运行时间 O( N log N )
- C 语言版
#include <stdio.h>
int maxSubSum(int a[], int left, int right){
// 判断是否只有一个元素
if (left == right) {
if (a[left] > 0) {
return a[left];
} else {
return 0;
}
}
int center = (left + right) / 2;
int maxLeftSum = maxSubSum(a, left, center);
int maxRightSum = maxSubSum(a, center + 1, right);
// 左端处理
int maxLeftBorderSum = 0;
int leftBorderSum = 0;
int i;
for (i = center; i >= left; i--) {
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum) {
maxLeftBorderSum = leftBorderSum;
}
}
// 右端处理
int maxRightBorderSum = 0;
int rightBorderSum = 0;
for (i = center + 1; i <= right; i++) {
rightBorderSum += a[i];
if (rightBorderSum > maxRightBorderSum) {
maxRightBorderSum = rightBorderSum;
}
}
// 返回最大值
int maxBorderSum = maxLeftBorderSum + maxRightBorderSum;
return maxBorderSum > maxLeftSum ? maxBorderSum > maxRightSum ? maxBorderSum : maxRightSum
: maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
}
int main(){
//int a[] = {-2, 11, -4, 13, -5, -2};
int a[] = { -2, 4, -3, 5, 7, -1, 8, 1 };
int max = maxSubSum(a, 0, sizeof(a) / sizeof(int) - 1);
printf("%d\n",max);
return 0;
}-
方法四：最优起点，扫描法
- 算法思想：设 a[i] 为和最大序列的起点，则如果 a[i] 是负的，那么它不可能代表最优序列的起点，因为任何包含 a[i] 作为起点的子序列都可以通过 a[i+1] 作起点而得到改进。
- 类似的，任何负的子序列也不可能是最优子序列的前缀。
- 运行时间：O(N)
-
C 语言版
#include <stdio.h>
int maxSubSum(int a[], int n){
int maxSum = 0;
int sum = a[0], i;
/*考虑如果全是负数，那么返回最大的负数，
如果最后的和为正，那么就使用扫描法*/
for(i = 1; i < n; i++){
if(sum < 0){//当前数小于0，换为下一个数
sum = a[i];
}else{
sum += a[i];
}
if(sum > maxSum){
maxSum = sum;
}
}
return maxSum;
}
int main(){
//int a[] = {-2, 11, -4, 13, -5, -2};
int a[] = { -2, 4, -3, 5, 7, -1, 8, 1 };
int len = sizeof(a) / sizeof(int);//有负数所以 strlen(a) 不能用
int max = maxSubSum(a, len);
printf("%d\n",max);
return 0;
}binary search 又叫对分查找、对半查找，时间复杂度 O(log N)
【代码实现】
- C 语言版
#include <stdio.h>
int binarySearch(int a[], int n, int x){
int low, mid, high;
low = 0;
high = n - 1;
while(low <= high){
mid = (low + high) / 2;
if(a[mid] < x){
low = mid + 1;
}else if(a[mid] > x){
high = mid - 1;
}else{
return mid;
}
}
return -1;
}
int main(){
int a[] = { 1, 2, 3, 4, 5, 6 };
int len = sizeof(a) / sizeof(int);
int x;
scanf("%d",&x);
if(binarySearch(a, len, x) != -1){
printf("Found %d.\n",x);
}else{
printf("NotFound %d.\n",x);
}
return 0;
}又叫欧几里德算法 gcd(M, N)
【代码实现】
- C 语言版：使用 while 循环
#include <stdio.h>
int gcd(int a, int b){
int tmp;
while(b > 0){
tmp = a % b;
a = b;
b = tmp;
}
return a;
}
int main(){
int x, y;
scanf("%d%d",&x, &y);
printf("%d\n", gcd(x, y));
return 0;
}- C 语言版：使用递归
#include <stdio.h>
int gcd(int a, int b){
if(b == 0){
return a;
}else{
return gcd(b, a % b);
}
}
int main(){
int x, y;
scanf("%d%d",&x, &y);
printf("%d\n", gcd(x, y));
return 0;
}【题目】
求 x^n
【代码实现】
- C 语言版：递归
#include <stdio.h>
int pow(int x, int n){
if(n == 0){
return 1;
}
if(n == 1){
return x;
}
if(n % 2 == 0){
return pow(x * x, n / 2);
}else{
return pow(x * x, n / 2) * x;
}
}
int main(){
printf("%d\n", pow(2, 5));//2^5
return 0;
}线性表是具有相同类型的 n（n>=0）个元素的有限序列，其中 n 为表长，当 n=0 时，该表为空表。
线性表的特点：
一般线性表包含下列基本操作：
- 初始化
- 销毁
- 重置为空表
- 判断是否为空
- 获取长度
- 根据位置获取对应元素
- 查找元素
- 获取指定元素的前驱和后继元素
- 插入元素
- 删除元素
- 遍历元素
ADT 线性表(SeqList)
Data
线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。
其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素an外，
每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(*L):初始化操作，建立一个空的线性表。
ListEmpty(L):若线性表为空，返回true，否则返回false。
ClearList(*L):线性表清空。
GetElem(L,i,*e):将线性表L中第i个位置元素返回给e。
LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功,返回该元素在表中的序列号；
否则，返回0表示失败。
InsertList(*L,i,e):在线性表的第i个位置插入元素e。
DeleteList(*L,i,*e):删除线性表L中的第i个元素，并用e返回其值
ListLength(L):返回线性表L的元素个数。
PrintList(L):打印线性表
根据存储方式不同，线性表可以分为顺序表和链表：
- 数据元素在内存中集中存储，采用顺序表示结构，简称 “顺序存储”；
- 数据元素在内存中分散存储，采用链式表示结构，简称 “链式存储”
是指将线性表中的各个元素依次存放在一组地址连续的存储单元中，通常将这种方法存储的线性表称为顺序表。
- 线性表中第 i 个元素的存储位置与第一个元素的 a1 的存储位置满足以下关系，location(ai) = location(a1) + (i-1) * m。其中，第一个元素的位置 location(a1) 称为起始地址或基地址。
- 顺序表逻辑上相邻的元素在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。只要确定了第一个元素的起始位置，线性表中的任一个元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。由于 C 语言的数组具有随机存储特别，因此采用数组来描述顺序表。
- 定义顺序表结构体：
typedef struct{
DataType list[MaxSize];
int length;
}SeqList;其中，DataType 表示数据元素类型，list 用于存储线性表中的数据元素，length 用来表示线性表中数据元素的个数，SeqList 是结构体类型名。定义一个顺序表代码：SeqList L; 指向顺序表的指针：SeqList *L;
顺序表的基本运算如下：
（1）初始化线性表
void InitList(SeqList *L){
L->length =0; //把线性表的长度设为0
}（2）线性表非空判断
int ListEmpty(SeqList *L){
if(L->length == 0)
return 1;
else
return 0;
}（3）线性表清空
void ClearList(SeqList *L){//线性表清空。
L->length =0; //把线性表的长度设为0
}
（4）按序号查找
int GetElem(SeqList *L, int i, DataType *e){
//查找线性表中第i个元素，查找成功将该值返回给e，并返回1表示成功，反正返回-1表失败。
if(i < 1 || i > L->length){
return -1;
}
*e = L->list[i - 1];
return 1;
}（5）按内容查找
int LocateElem(SeqList *L, DataType e){
//查找线性表中元素值为e的元素
int i;
for (i = 0; i < L->length ; i++)
if(L->list[i] == e){
return i + 1;
}
return 0;//找不到返回0
}（6）插入操作
//在顺序表的第i个位置插入元素e，成功返回1，
//失败返回-1，顺序表满了返回0
int InsertList(SeqList *L, int i, DataType e){
int j;
if(i < 1 || i > L->length + 1){
return -1;
}
else if(L->length >= MaxSize){
return 0;
}else{
for(j = L->length; j >= i; j--){
L->list[j] = L->list[j-1];
}
L->list[i-1] =e ;//插入元素到i个位置
L->length = L->length + 1;
return 1;
}
}（7）删除操作
觉得文章有帮助，不妨请我喝杯 Coffee，祝福好心人年年高升！
（8）返回线性表个数
int ListLength(SeqList *L){//返回线性表L的元素个数。
return L->length;
}（9）打印线性表
void PrintList(SeqList *L){//打印线性表,即顺序表遍历
int i;
for(i = 0; i < L->length; i++){
printf("%d\n", L->list[i]);
}
} （10）主函数调用测试 main()
int main(){
SeqList *L;
L = (SeqList *)malloc(sizeof(SeqList));//申请内存空间
//L->length = 10;
printf("初始化数组------\n");
//测试初始化数组长度为0
InitList(L);
printf("插入节点------\n");
//测试插入数据元素
InsertList(L, 1, 55);
InsertList(L, 2, 57);
InsertList(L, 3, 78);
InsertList(L, 2, 89);
//查看线性表是否为空
if(ListEmpty(L) == 1){
printf("线性表为空\n");
}else{
printf("线性表不为空\n");
}
//测试 打印线性表
PrintList(L) ;
int a = 123;
int *p = &a;
printf("删除节点------\n");
//删除测试
DeleteList(L, 2, p);
printf("%d\n",*p);
printf("删除节点后------\n");
//测试 打印线性表
PrintList(L) ;
int l = ListLength(L);
printf("线性表长度为%d\n",l);
//查找元素
//按内容查找
if(LocateElem(L, 55)){
printf("找到\n");
}
//按序号查找
GetElem(L, 2, p);
printf("%d\n",*p);
return 0;
}提供另一种方式写顺序表，不申请内存空间 malloc
#include <stdio.h>
#define MaxSize 100
//定义数据类型
typedef int DataType;
typedef struct{
//线性数组
DataType list[MaxSize];
//数组长度
int length;
}SeqList;
//初始化线性表
void InitList(SeqList *L){
L->length =0; //把线性表的长度设为0
}
int ListEmpty(SeqList L){
if(L.length == 0)
return 1;
else
return 0;
}
void ClearList(SeqList *L){//线性表清空。
L->length =0; //把线性表的长度设为0
}
int GetElem(SeqList L, int i, DataType *e){
//查找线性表中第i个元素，查找成功将该值返回给e，并返回1表示成功，反正返回-1表失败。
if(i < 1 || i > L.length){
return -1;
}
*e = L.list[i - 1];
return 1;
}
int LocateElem(SeqList L, DataType e){
//查找线性表中元素值为e的元素
int i;
for (i = 0; i < L.length ; i++)
if(L.list[i] == e){
return i + 1;
}
return 0;//找不到返回0
}
//在顺序表的第i个位置插入元素e，成功返回1，失败返回-1，顺序表满了返回0
int InsertList(SeqList *L, int i, DataType e){
int j;
if(i < 1 || i > L->length + 1){
return -1;
}
else if(L->length >= MaxSize){
return 0;
}else{
for(j = L->length; j >= i; j--){
L->list[j] = L->list[j-1];
}
L->list[i-1] =e ;//插入元素到i个位置
L->length = L->length + 1;
return 1;
}
}
int DeleteList(SeqList *L, int i, DataType *e){
int j;
if(L->length <= 0){
return 0;
}
else if(i < 1 || i > L->length){
return -1;
}else{
*e = L->list[i-1];
for(j = i;j <= L->length-1; j++){
L->list[j-1] = L->list[j];
}
L->length = L->length - 1;
return 1;
}
}
int ListLength(SeqList L){//返回线性表L的元素个数。
return L.length;
}
void PrintList(SeqList L){//打印线性表,即顺序表遍历
int i;
for(i = 0; i < L.length; i++){
printf("%d\n", L.list[i]);
}
}
int main(){
SeqList L;
//L.length = 0;
//L = (SeqList *)malloc(sizeof(SeqList));//申请内存空间
//L->length = 10;
printf("初始化数组------\n");
//测试初始化数组长度为0
InitList(&L);
printf("插入节点------\n");
//测试插入数据元素
InsertList(&L, 1, 55);
InsertList(&L, 2, 57);
InsertList(&L, 3, 78);
InsertList(&L, 2, 89);
//查看线性表是否为空
if(ListEmpty(L) == 1){
printf("线性表为空\n");
}else{
printf("线性表不为空\n");
}
//测试 打印线性表
PrintList(L) ;
int a = 123;
int *p = &a;
printf("删除节点------\n");
//删除测试
DeleteList(&L, 2, p);
printf("%d\n",*p);
printf("删除节点后------\n");
//测试 打印线性表
PrintList(L) ;
int l = ListLength(L);
printf("线性表长度为%d\n",l);
//查找元素
//按内容查找
if(LocateElem(L, 55)){
printf("找到\n");
}
//按序号查找
GetElem(L, 2, p);
printf("%d\n",*p);
return 0;
}!> 小结：顺序表的优缺点。
（1）优点：无须关心表中元素之间的关系，所以不用增加额外的存储空间；可以快速地取表中任意位置的元素。
（2）缺点：插入和删除操作需要移动大量元素。使用前需事先分配好内存空间，当线性表长度变化较大时，难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费，分配的空间过小，难以适应问题的需求
链式表包括单链表、双链表、循环链表、循环单链表等等等
单链表的存储结构用C语言描述：
typedef int DataType;
typedef struct Node{
DataType data;//创建数据域
struct Node *next;//创建指针域
}LinkList;其中，LinkList 是链表的结点类型。
单链表的基本运算如下：
（1）初始化单链表
LinkList * InitList(LinkList *p){
p = (LinkList *)malloc(sizeof(LinkList));
if(!p){
exit(-1);//exit函数，退出程序。
}
p->next = NULL;
return p;
}!> 真正使用的时候，直接在 CreateList 中定义即可，如下写法，根据实际需求使用：
LinkList *q = (LinkList *)malloc(sizeof(LinkList));
if (!q){
exit(-1); //exit函数，退出程序。
}
LinkList * r = q; //创建尾指针指向尾节点
r->next = NULL;或者：
LinkList *q = (LinkList *)malloc(sizeof(LinkList));
if (!q){
exit(-1); //exit函数，退出程序。
}
q = NULL;或者：
LinkList *q = (LinkList *)malloc(sizeof(LinkList));
if (!q){
exit(-1); //exit函数，退出程序。
}
q->next = NULL;（2）单链表非空判断
int ListEmpty(LinkList *p){
int flag = 0;
if(!p){
flag = 1;
}
return flag;
}（3）按序号查询操作
//按序号查找单链表中第i个结点
LinkList *GetElem(LinkList *head,int i){
LinkList *p;
int j = 0;
if(ListEmpty(head)||i<1){ //如果链表为空
return NULL;
}
p = head;
while(p->next !=NULL && j<i-1){//保证p的下个结点不为空
p = p->next;
j++;
}
if(j==i-1)//找到第i个结点
return p;
else
return NULL;
}（4）按内容查找操作
//按内容查找单链表中元素值为e的元素
int LocateElem(LinkList *head,DataType e){
int flag = 0;
LinkList *p;
p = head->next; //指针p指向第一个结点
while(p){
if(p->data != e){
p=p->next;//继续下一个
}else{
flag = 1;
break;
}
}
return flag;
}（5）定位操作
int LocatePos(LinkList *head,DataType e){
LinkList *p;//定义一个指向单链表的结点的指针p
int i;
if(ListEmpty(head))//非空判断
return 0;
p = head->next;//指针p指向一个结点
i =1;
while(p){
if(p->data==e)
return i;
else
{
p=p->next;//指向下一个结点
i++;
}
}
if(!p)//如果没有找到与e相等的元素
return 0;
} （6）插入新数据元素 e 到 i 位置
int InsertList(LinkList *head,int i,DataType e){
LinkList *pre,*p;//定义第i个元素的前驱结点指针pre，新生结点指针p
int j = 0;
pre = head; //指针pre指向头结点
while(pre->next != NULL && j < i-1){ //循环直到直到i元素前驱结点
pre = pre->next;
j++;
}
if(j != i-1)//如果没找到，插入位置出错
return 0;
//新生一个结点
p = (LinkList *)malloc(sizeof(LinkList));
if(!p){
exit(-1);
}
p->data =e; //将e赋值给结点的数据域
p->next = pre->next;
pre->next =p;
return 1;
}（7）删除第 i 个结点
int DeleteList(LinkList *head,int i,DataType *e){
LinkList *pre,*p;
int j = 0;
pre = head;
while(pre->next!=NULL && pre->next->next != NULL && j<i-1){
pre = pre->next;
j++;
}
if(j!=i-1){
return 0;
}
//指针p指向单链表中的第i个结点,并将该结点数据域值赋值给e
p = pre->next;
*e =p->data;
//将前驱结点的指针域指向要删除结点的下一个结点
pre->next =p->next;
free(p);//释放p指向的结点
return 1;
}（8）打印单链表
void PrintList(LinkList * p){//遍历输出
LinkList *q;
if (ListEmpty(p)){
printf("链表为空！\n");
}else{
q = p->next; //使指针指向下一个节点
printf("链表中的数据为：\n");
while (q){//q!=NULL
//printf("%d ", q->data);
if(q->next){
printf("%d->", q->data);
}else{
printf("%d", q->data);
}
q = q->next;
}
printf("\n");
}
}（9）主函数调用测试 main()
int main(){
LinkList *p; //创建头指针，用来存放头结点的地址。
p = CreateList(); //CreateList()函数动态创建链表并返回头结点的地址。
PrintList(p); //打印单链表数据
InsertList(p, 1, 23);
PrintList(p); //打印单链表数据
int x;
DeleteList(p,2,&x);
PrintList(p); //打印单链表数据
printf("删除 %d\n",x);
LinkList *q;
q = GetElem(p,2);
printf("查找到%d\n",q->data);
if(LocateElem(p,23)==1){
printf("找到\n");
}
int i = LocatePos(p,23);
printf("%d\n",i);
return 0;
}简单的单链表创建输出数据：
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int DataType;
typedef struct Node{
DataType data;//创建数据域
struct Node *next;//创建指针域
}LinkList;
LinkList * CreateList(){
//函数返回值为LinkList * 类型。
int len, i, x;
LinkList *q = (LinkList *)malloc(sizeof(LinkList));
if (!q){
printf("分配头结点空间失败，程序终止！\n");
exit(-1); //exit函数，退出程序。
}
LinkList * r = q; //创建尾指针指向尾节点
r->next = NULL;
printf("请输入链表的节点个数：len = ");
scanf("%d", &len);
for (i=0; i<len; ++i){
printf("请输入第%d个节点的值：", i+1);
scanf("%d", &x);
LinkList *p = (LinkList *)malloc(sizeof(LinkList));
//链表的不连续性在于它的内存空间在不断地一个个分配
if (!p){
printf("分配空间失败，程序终止！\n");
exit(-1);
}
p->data = x;
r->next = p;
p->next = NULL;
r = p; //递归
}
return q;
}
void PrintList(LinkList * p){//遍历输出
LinkList *q;
if (isEmpty(p)){
printf("链表为空！\n");
}else{
q = p->next; //使指针指向下一个节点
printf("链表中的数据为：\n");
while (q){//q!=NULL
printf("%d ", q->data);
q = q->next;
}
printf("\n");
}
}
int isEmpty(LinkList *p){
int flag = 0;
if(!p){
flag = 1;
}
return flag;
}
int main(){
LinkList * p; //创建头指针，用来存放头结点的地址。
p = CreateList(); //CreateList()函数动态创建链表并返回头结点的地址。
PrintList(p); //打印单链表数据
return 0;
}
循环单链表（circular linkedlist）是首尾相连的一种单链表，即将最后一个结点的空指针改为指向头结点或第一个结点的形成一个环型，最后一个结点称为尾指针: rear。判断单链表为空的条件是 head->next == NULL，而判断循环单链表为空的条件是 head->next == head。访问第一个结点即 rear->next->next。
如果将两个循环单链表（LA，LB）合成一个链表，只需将一个表的表尾和另一个表的表头连接即可。具体步骤为：
- 将 LA->next = LB->next->next; 第一个结点。
- 释放 LB 的头结点，free(LB->next);
- 将 LB 的表尾与 LA 的表头相连，LB->next = LA->next。
LinkList *Link(LinkList *head1, LinkList *head2){
LinkList *p, *q;
p = head1;//p指向1头结点
while(p->next != head1){//循环使指针p指向链表的最后一个结点
p = p->next;
}
q = head2;
while(q->next != head2){//同上
q = q->next;
}
p->next = head2->next;//将第一个链表的尾端连接第二个链表的第一个结点
q->next = head1; // 将第二个链表的尾端连接到第一个连接的第一个结点
return head1;
}说明：也可以把循环单链表中的头结点成为哨兵结点。
栈是只能在表尾进行插入或删除操作的线性表，通常我们称表尾端为栈顶，表头端为栈底，它是一种先进后出的线性表，既只能在表尾端插入元素，称为入栈，也只能在表尾端删除元素，称为退栈。栈有时又叫做 LIFO (后进先出) 表
栈既然也是线性表，那么它也有顺序存储结构和链式存储结构两种表示方法，这两种表示方法实现类似。
通过栈可以解决很多问题，例如数值转换、括号匹配、迷宫求解、表达式求值和汉诺塔等等问题。
栈的存储结构用C语言描述：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INIT_SIZE 20
#define INCREMENT_SIZE 5
typedef int SElemType;
typedef int Status;
/*
* 存储结构
*/
typedef struct
{
SElemType *base; //栈尾指针
SElemType *top; //栈顶指针
int size; //栈的大小
}SqStack;栈的基本运算如下：
（1）初始化栈
/*
* 初始化栈
*/
Status InitStack(SqStack *S)
{
S->base = (SElemType*) malloc(INIT_SIZE * sizeof(SElemType));
if (!S->base)
{
exit(OVERFLOW);
}
S->top = S->base;
S->size = INIT_SIZE;
return OK;
}（2）压栈
压栈的算法如下：
- (1) 判断是否栈满，若满则出错，需要重新分配空间
- (2) 元素 e 压入栈顶
- (3) 栈顶指针加 1
/*
* 压栈
*/
Status Push(SqStack *S, SElemType e)
{
if ((S->top - S->base) / sizeof(SElemType) >= S->size)
{
S->base = (SElemType*) realloc(S->base, (S->size + INCREMENT_SIZE) * sizeof(SElemType));
if (!S->base)
{
exit(OVERFLOW);
}
S->top = S->base + S->size;
S->size += INCREMENT_SIZE;
}
*S->top = e;
S->top++;
return OK;
}（3）退栈
退栈的算法流程如下：
- (1) 判断是否栈空，若空则出错
- (2) 获取栈顶元素 e
- (3) 栈顶指针减 1
/*
* 退栈
*/
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == S->base)
{
return ERROR;
}
S->top--;
*e = *S->top;
return OK;
}（4）销毁栈
/*
* 销毁栈
*/
Status DestroyStack(SqStack *S)
{
free(S->base);
S->base = NULL;
S->top = NULL;
S->size = 0;
return OK;
}（5）清空栈
/*
* 清空栈
*/
Status ClearStack(SqStack *S)
{
S->top = S->base;
return OK;
}（6）判空
/*
* 判断栈是否为空
*/
Status IsEmpty(SqStack S)
{
if (S.top == S.base)
{
return TRUE;
}
else
return FALSE;
}（7）获取栈的长度
/*
* 获取栈的长度
*/
int GetLength(SqStack S)
{
return S.top - S.base;
}（8）获取栈顶元素
/*
* 获取栈顶元素
*/
Status GetTop(SqStack S, SElemType *e)
{
if (S.top > S.base)
{
*e = *(--S.top);
return OK;
}
else
{
return ERROR;
}
}（9）访问元素
/*
* 访问元素
*/
void visit(SElemType e)
{
printf("%d ", e);
}（10）遍历栈
/*
* 遍历栈
*/
Status TraverseStack(SqStack S, void (*visit)(SElemType))
{
while (S.top > S.base)
{
visit(*S.base);
S.base++;
}
return OK;
}（11）主函数测试
int main()
{
SqStack S;
if (InitStack(&S))
{
SElemType e;
int i;
printf("init_success\n");
if (IsEmpty(S))
{
printf("Stack is empty\n");
}
for (i = 0; i < 10; i++)
{
Push(&S, i);
}
GetTop(S, &e);
printf("The first element is %d\n", e);
printf("length is %d\n", GetLength(S));
Pop(&S, &e);
printf("Pop element is %d\n", e);
TraverseStack(S, *visit);
if (DestroyStack(&S))
{
printf("\ndestroy_success\n");
}
}
}#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INIT_SIZE 20
#define INCREMENT_SIZE 5
typedef int SElemType;
typedef int Status;
/*
* 存储结构
*/
typedef struct
{
SElemType *base; //栈尾指针
SElemType *top; //栈顶指针
int size; //栈的大小
}SqStack;
/*
* 初始化栈
*/
Status InitStack(SqStack *S)
{
S->base = (SElemType*) malloc(INIT_SIZE * sizeof(SElemType));
if (!S->base)
{
exit(OVERFLOW);
}
S->top = S->base;
S->size = INIT_SIZE;
return OK;
}
/*
* 销毁栈
*/
Status DestroyStack(SqStack *S)
{
free(S->base);
S->base = NULL;
S->top = NULL;
S->size = 0;
return OK;
}
/*
* 清空栈
*/
Status ClearStack(SqStack *S)
{
S->top = S->base;
return OK;
}
/*
* 判断栈是否为空
*/
Status IsEmpty(SqStack S)
{
if (S.top == S.base)
{
return TRUE;
}
else
return FALSE;
}
/*
* 获取栈的长度
*/
int GetLength(SqStack S)
{
return S.top - S.base;
}
/*
* 获取栈顶元素
*/
Status GetTop(SqStack S, SElemType *e)
{
if (S.top > S.base)
{
*e = *(--S.top);
return OK;
}
else
{
return ERROR;
}
}
/*
* 压栈
*/
Status Push(SqStack *S, SElemType e)
{
if ((S->top - S->base) / sizeof(SElemType) >= S->size)
{
S->base = (SElemType*) realloc(S->base, (S->size + INCREMENT_SIZE) * sizeof(SElemType));
if (!S->base)
{
exit(OVERFLOW);
}
S->top = S->base + S->size;
S->size += INCREMENT_SIZE;
}
*S->top = e;
S->top++;
return OK;
}
/*
* 退栈
*/
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == S->base)
{
return ERROR;
}
S->top--;
*e = *S->top;
return OK;
}
/*
* 访问元素
*/
void visit(SElemType e)
{
printf("%d ", e);
}
/*
* 遍历栈
*/
Status TraverseStack(SqStack S, void (*visit)(SElemType))
{
while (S.top > S.base)
{
visit(*S.base);
S.base++;
}
return OK;
}
int main()
{
SqStack S;
if (InitStack(&S))
{
SElemType e;
int i;
printf("init_success\n");
if (IsEmpty(S))
{
printf("Stack is empty\n");
}
for (i = 0; i < 10; i++)
{
Push(&S, i);
}
GetTop(S, &e);
printf("The first element is %d\n", e);
printf("length is %d\n", GetLength(S));
Pop(&S, &e);
printf("Pop element is %d\n", e);
TraverseStack(S, *visit);
if (DestroyStack(&S))
{
printf("\ndestroy_success\n");
}
}
}队列是一种先进先出的线性表，只能在一端插入元素，在另一端删除元素，如下图所示，允许插入元素的一端称为队尾，允许删除元素的一端称为队头。
队列也一样有顺序和链式存储结构两种表示方法。
队列的存储结构用C语言描述：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
/*
* 存储结构
*/
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;队列的基本运算如下：
（1）初始化队列
/*
* 初始化队列
*/
Status InitQueue(LinkQueue *Q)
{
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front)
{
exit(OVERFLOW);
}
Q->front->next = NULL;
return OK;
}（2）销毁队列
/*
* 销毁队列
*/
Status DestroyQueue(LinkQueue *Q)
{
while (Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}（3）清空队列
/*
* 清空队列
*/
Status ClearQueue(LinkQueue *Q)
{
DestroyQueue(Q);
InitQueue(Q);
return OK;
}（4）判空
/*
* 判断队列是否为空
*/
Status IsEmpty(LinkQueue Q)
{
if (Q.front->next == NULL)
{
return TRUE;
}
else
{
return FALSE;
}
}（5）获取队列的长度
/*
* 获取队列的长度
*/
int GetLength(LinkQueue Q)
{
int i = 0;
QueuePtr p = Q.front;
while (Q.rear != p)
{
i++;
p = p->next;
}
return i;
}（6）获取队头元素
/*
* 获取队头元素
*/
Status GetHead(LinkQueue Q, QElemType *e)
{
QueuePtr p;
if (Q.front == Q.rear)
{
return ERROR;
}
p = Q.front->next;
*e = p->data;
return OK;
}（7）入队
/*
* 入队
*/
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
return OK;
}（8）出队
/*
* 出队
*/
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear)
{
return ERROR;
}
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p)
{
Q->rear = Q->front;
}
free(p);
return OK;
}（9）访问元素
/*
* 访问元素
*/
void visit(QElemType e)
{
printf("%d ", e);
}（10）遍历队列
/*
* 遍历队列
*/
Status TraverseQueue(LinkQueue Q, void (*visit)(QElemType))
{
QueuePtr p = Q.front->next;
while (p)
{
visit(p->data);
p = p->next;
}
return OK;
}（11）主函数测试
int main()
{
LinkQueue Q;
if (InitQueue(&Q))
{
QElemType e;
int i;
printf("init_success\n");
if (IsEmpty(Q))
{
printf("queue is empty\n");
}
for (i = 0; i < 10; i++)
{
EnQueue(&Q, i);
}
GetHead(Q, &e);
printf("The first element is %d\n", e);
printf("length is %d\n", GetLength(Q));
DeQueue(&Q, &e);
printf("delete element is %d\n", e);
TraverseQueue(Q, *visit);
if (DestroyQueue(&Q))
{
printf("\ndestroy_success\n");
}
}
}#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
/*
* 存储结构
*/
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
/*
* 初始化队列
*/
Status InitQueue(LinkQueue *Q)
{
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front)
{
exit(OVERFLOW);
}
Q->front->next = NULL;
return OK;
}
/*
* 销毁队列
*/
Status DestroyQueue(LinkQueue *Q)
{
while (Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
/*
* 清空队列
*/
Status ClearQueue(LinkQueue *Q)
{
DestroyQueue(Q);
InitQueue(Q);
return OK;
}
/*
* 判断队列是否为空
*/
Status IsEmpty(LinkQueue Q)
{
if (Q.front->next == NULL)
{
return TRUE;
}
else
{
return FALSE;
}
}
/*
* 获取队列的长度
*/
int GetLength(LinkQueue Q)
{
int i = 0;
QueuePtr p = Q.front;
while (Q.rear != p)
{
i++;
p = p->next;
}
return i;
}
/*
* 获取队头元素
*/
Status GetHead(LinkQueue Q, QElemType *e)
{
QueuePtr p;
if (Q.front == Q.rear)
{
return ERROR;
}
p = Q.front->next;
*e = p->data;
return OK;
}
/*
* 入队
*/
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
return OK;
}
/*
* 出队
*/
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear)
{
return ERROR;
}
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p)
{
Q->rear = Q->front;
}
free(p);
return OK;
}
/*
* 访问元素
*/
void visit(QElemType e)
{
printf("%d ", e);
}
/*
* 遍历队列
*/
Status TraverseQueue(LinkQueue Q, void (*visit)(QElemType))
{
QueuePtr p = Q.front->next;
while (p)
{
visit(p->data);
p = p->next;
}
return OK;
}
int main()
{
LinkQueue Q;
if (InitQueue(&Q))
{
QElemType e;
int i;
printf("init_success\n");
if (IsEmpty(Q))
{
printf("queue is empty\n");
}
for (i = 0; i < 10; i++)
{
EnQueue(&Q, i);
}
GetHead(Q, &e);
printf("The first element is %d\n", e);
printf("length is %d\n", GetLength(Q));
DeQueue(&Q, &e);
printf("delete element is %d\n", e);
TraverseQueue(Q, *visit);
if (DestroyQueue(&Q))
{
printf("\ndestroy_success\n");
}
}
}n个结点，有n-1个边
树中一个结点的子结点的个数称为该结点的度
树种最大度数称为树的度
度大于0的结点为分支结点
度为0的结点为叶子结点
有序树与无序树
路径：树中两个结点之间的路径，且一定是自上而下的。
路径长度：路径上所经历边的个数
森林：m课互不相交的树的集合
- 树中的结点数等于所有结点的度数加1
- 度为m的树中第i层上至多有$m^{i-1}$个结点(
$i \ge 1$ ) - 高度为h的m叉树至多有$(m^b-1)/(m-1)$个结点
- 具有n个结点的m叉树的最小高度为$log_m[n(m-1)+1]$
二叉树：每个结点最多有2个子结点
度为2的有序树：每个结点最多有2个子结点 且 必须有一个结点具有2个子结点
二叉树可以为空，而度为2的有序树至少有三个结点。
二叉树的孩子结点始终有左右之分，而度为2的有序树的孩子结点次序是相对的。
满二叉树：一棵高度为h，且含有$2^h-1$个结点的二叉树为满二叉树。对于编号为i的结点，若存在，其双亲编号为[i/2]，左孩子为2i，右孩子为2i+1。
完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。
性质：
- 若$i \le [n/2]$，则结点i为分支结点，否则为叶子结点。
- 叶子结点只可能在层次最大的两层出现。对于最大层次的叶子接待你，都依次排列在最左边的位置上。
- 度为1的结点若存在，则可能有一个，且是编号最大的分支结点，并且孩子结点一定是左节点。
二叉排序树：一棵二叉树，若树非空则具有如下性质：对于任意结点若存在左子树或右子树，则其左子树上所有结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点。
平衡二叉树：树上任意结点的左子树和右子树的深度之差不超过1。
-
非空二叉树上的叶子结点数等于度为2的结点数加1，即$n_0=n_2+1$
如何推导：
$①. n=n_0+n_1+n_2$ 结点总数=$\sum\limits_{i=0}^{2}$度为i的结点数$②. n=n_1+2n_2+1$ 结点总数= 边数+1 =$\sum\limits_{i=0}^{2}$ 度为i的结点数*该结点的出度i -
非空二叉树上第k层上至多有$2^{k-1}$个结点(
$k \ge 1$ ) -
高度为h的二叉树至多有$2^h-1$个结点(
$h \ge 1$ ) -
结点i所在层次为$[log_2i]+1$
-
具有n个(
$n \ge 1$ )结点的完全二叉树的高度为$[log_2n]+1$ (由4得)或$[log_2(n+1)]$ (由3得)
顺序存储：用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
-
适合完全二叉树。
-
最坏情况下会非常浪费存储空间。
ElementType tree[MAXSIZE] = {};链式存储：用链表来存放二叉树，二叉树中每个结点用链表的一个链结点来存储。
- 含有n个结点的二叉链表，有n+1个空链域。
- 2n-(n-1) = n+1
- 2n表示总链域数，n个结点，每个结点有两个指针域
- n-1表示非空链域，每个链域指向一个孩子结点，所以n-1个孩子结点就有n-1个非空链域。除了根节点，每个结点都能作为孩子结点，所以是n-1个孩子结点。
typedef struct Node {
ElementType data;
struct Node *lchild, *rchild;
} Node, *BiTree;先序遍历：根，左子树，右子树
中序遍历：左子树，根，右子树
后序遍历：左子树，右子树，根
层次遍历：从左至右，从上至下
递归实现
void PreOrder(BiTree T) {
if (T != NULL) {
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}中序遍历非递归实现
- 初始时依次扫描根节点的所有左侧结点并将他们一一入栈；
- 出栈一个结点，访问它；
- 扫描该结点的右孩子结点并将其入栈；
- 依次扫描右孩子结点的所有左侧结点并一一入栈；
- 反复该过程直到栈空为止。
void InOrderTraverse(BiTree T) {
Node *S;
InitStack(S);
BiTree p = T;
while (p || !IsEmpty(S)) {
if (p) {
Push(S, p);
p = p->lchild;
} else {
Pop(S, p); visit(p);
p = p->rchild;
}
}
}
void PreOrderTraverse(BiTree T) {
Node *S;
InitStack(S);
BiTree p = T;
Push(S, p);
while (p != NULL || !IsEmpty(S)) {
Pop(S, p);
visit(p);
if (p->rchild != NULL) {
Push(S, p->rchild);
}
if (p->lchild != NULL) {
Push(S, p->lchild);
}
}
}后序遍历非递归实现
待定。
层次遍历
- 初始时将根入队并访问根节点
- 若有左子树，则将左子树的根入队
- 若有右子树，则将右子树的根入队
- 然后出队，访问该结点
- 反复该过程直到队列为空
void levelOrder(BiTree T) {
InitQueue(Q);
BiTree p;
EnQueue(Q, T);
while (!isEmpty(Q)) {
DeQueue(Q, p);
visit(p);
if (p->lchild != NULL)
EnQueue(Q, p->lchild);
if (p->rchild != NULL)
EnQueue(Q, p->rchild);
}
}先（后）序遍历序列和中序遍历序列可以确定一棵二叉树。
而后序遍历序列和先序遍历序列不可以确定一棵二叉树。
线索化：
- 若无左子树，则将左指针指向其前驱结点；
- 若无右子树，则将右指针指向其后继结点。
typedef struct ThreadNode {
ElementType data;
struct Node *lchild, *rchild;
int ltag, rtag;
} ThreadNode, *ThreadTree;
// l(r)tag :
// 0: l(r)child域指向的是孩子结点
// 1: l(r)child域指向的是前驱(后继)结点中序线索二叉树寻找对应结点的前驱与后继更加方便。我们主要研究中序线索二叉树。
中序线索二叉树
- 前驱结点
- 若左指针为线索，则其指向的结点为前驱结点
- 若左指针为左孩子，则其左子树的最右侧结点为前驱结点
- 后继结点
- 若右指针为线索，则其指向的结点为后继结点
- 若右指针为右孩子，则其右子树的最左侧结点为后继结点
中序线索二叉树的线索化实现
void InThread(ThreadTree &p, ThreadTree &pre) {
if (p == NULL) return;
InThread(p->lchild, pre);
if (p->lchild == NULL) {
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
InThread(p->rchild, pre);
}得到的中序线索二叉树：
还可以将剩余两个指针利用起来，指向一个头节点的前驱与后继。
中序线索二叉树遍历
// 找到中序遍历的第一个结点
ThreadNode* FirstNode(ThreadNode *p) {
while (p->ltag == 0)
p = p->lchild;
return p;
}
// 找下一个结点
ThreadNode* NextNode(ThreadNode *p) {
if (p->rtag == 0) // 如果右指针是孩子结点
return FirstNode(p->rchild); // 找右孩子的左子树中第一个结点，为我们要的后继结点
else // 如果右指针是线索
return p->rchild; // rchild就是我们要的后继结点
}
// 中序线索树的遍历
void InOrder(ThreadNode *T) {
for (ThreadNode *p=FirstNode(T); p != NULL; p = NextNode(p)) {
visit(p);
}
}-
双亲表示法
采用一组连续的存储空间来存储每个结点，同时在每个节点中增设一个伪指针，指示双亲结点在数组中的位置。根结点的下标为0，其伪指针域为-1。
typedef struct { ElemType data; int parent; } PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int n; } PTree;
-
孩子表示法
将每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个结点具有n个孩子链表。
// 孩子结点 typedef struct { int child; // 孩子结点的下标 struct CNode *next; } CNode; // 根节点 typedef struct { ElemType data; struct CNode *child; } PNode; typedef struct { PNode nodes[MAX_TREE_SIZE]; int n; } CTree;
-
孩子兄弟表示法
以二叉链表作为树的存储结构，又称二叉树表示法。
左孩子，右兄弟
typedef strct CSNode { ElemType data; struct CSNode *firstchild, *nextsibling; } CSNode, CSTree;
优缺点比较
| 优点 | 缺点 | |
|---|---|---|
| 双亲表示法 | 寻找结点的双亲结点效率高 | 寻找结点的孩子结点效率低 |
| 孩子表示法 | 寻找结点的孩子结点效率高 | 寻找结点的双亲结点效率低 |
| 孩子兄弟表示法 | 寻找结点的孩子结点效率高，方便实现树转换成二叉树 | 寻找结点的双亲结点效率低 |
树与二叉树的转换
规则：每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点。
森林与二叉树的转换
规则：将每一棵树转换为二叉树，将每棵二叉树的根依次作为上一棵二叉树的右子树。
转换是唯一的
-
先根遍历
若树非空，先访问根节点，再按从左至右的顺序遍历根节点的每棵子树。
-
后根遍历
若树非空，则先按从左到右的顺序遍历根节点的每棵子树，再访问根节点。
-
层次遍历
⭐树的先根遍历序列与这棵树对应二叉树的先序遍历序列相同。
⭐树的后根遍历序列与这棵树对应二叉树的中序遍历序列相同。
-
先序遍历
若森林非空，则，
-
访问森林中第一棵树的根节点
-
先序遍历第一棵树的子树森林
-
先序遍历除去第一棵树之后的剩余的树构成的森林
-
-
中序遍历
若森林非空，则，
- 中序遍历第一棵树的根节点的子树森林
- 访问第一棵树的根节点
- 中序遍历除去第一棵树之后剩余的树构成的子树森林
⭐森林的先序遍历序列与森林对应二叉树的先序遍历序列相同。
⭐森林的中序遍历序列与森林对应二叉树的中序遍历序列相同。
并查集是一种简单的集合表示。
通常用树的双亲表示法作为并查集的存储结构。
定义以下几个方法：
-
Initial(S) 将集合S中的每个元素都初始化为只有一个单元素的子集合
-
Union(S, Root1, Root2)
把集合S中的子集合（互不相交）Root2并入子集合Root1
-
Find(S, X)
查找集合S中单元素x所在子集合，并返回该子集合的名字。
int UFSets[SIZE];
void Initial(int S[]) {
for (int i = 0; i < size; i++)
s[i] = -1;
}
int Find(int S[], int x) {
while(S[x] >= 0)
x = S[x];
return x;
}
void Union(int S[], int Root1, int Root2) {
S[Root1] += S[Root2]; //更新Root1的根节点值
S[Root2] = Root1; //更新Root2的根节点值
}BST，也称二叉查找树。
二叉排序树或者为空树，或者为非空树，当为非空树时有如下特点：
-
若左子树非空，则左子树上所有结点关键字均小于根节点的关键字。
-
若右子树非空，则右子树上所有结点关键字均大于根节点的关键字。
-
左右子树本身也分别是一棵二叉排序树。
⭐中序遍历二叉排序树，得到的是一个递增的有序序列。
查找
二叉树非空时，查找根节点，若相等则查找成功；
若不等，则当小于根节点值时，查找左子树；当大于根节点值时，查找右子树。
当查找到叶节点仍没查找到相应的值，则查找失败。
非递归算法实现查找算法
BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p) {
p = NULL;
while (T!=NULL && key!=T->data) {
p = T;
if (key < T->data)
T=T->lchild;
else
T=T->rchild;
}
return T;
}插入操作
若二叉排序树为空，则直接插入结点；
若二叉排序树非空，
当值小于根节点时，插入左子树；
当值大于根节点时，插入右子树；
当值等于根节点时，不进行插入；
int BST_Insert(BiTree &T, KeyType k) {
if (T == NULL) {
T = (BiTree)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = T->rchild = NULL;
return 1;
} else if (k == T->key)
return 0;
else if (k < T->key)
return BST_Insert(T->lchild, k);
else
return BST_Insert(T->rchild, k);
}构造二叉排序树
不断调用插入函数来构造。
void Create_BST(BiTree &T, KeyType str[], int n) {
T = NULL;
int i = 0;
while (i < n) {
BST_Insert(T, str[i]);
i++;
}
}删除操作
若被删结点是叶子结点，则可以直接删除。
若被删结点z只有一棵子树，则让z的子树成为z父结点的子树，代替z结点。
若被删除结点z有两棵子树，则让z的中序序列直接后继代替z，并删去直接后继结点。
在二叉排序树中删除并插入某个结点，得到的二叉排序树不一定相同。
查找效率
平均查找长度ASL取决于树的高度。
理解：
-
排序的目的：快速查找
-
衡量排序算法的优劣
- 时间复杂度：分析关键字的比较次数和记录的移动次数。
- 空间复杂度：分析排序算法中需要多少辅助内存。
- 稳定性：若两个记录 A 和 B 的关键字相等，但排序后 A 和 B 的先后次序保持不变，则称这种排序算法是稳定的。
-
排序的分类
- 内部排序
- 选择排序
- 直接选择排序、堆排序
- 交换排序
- 冒泡排序、快速排序
- 插入排序
- 直接插入排序、折半插入排序、Shell 排序
- 归并排序
- 桶式排序
- 基数排序
- 选择排序
- 外部排序（需要借助于磁盘）
- 多路归并排序
- 内部排序
做法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
- （1）第一趟比较前两个数，然后把第二个数按大小插入到有序表中；
- （2）第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；
- （3）依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
如下图所示。
算法步骤：
- （1）判断是否需要进行调整，如果
array[i] < array[i-1]就需要进行；如果不需要调整，直接判断下一个数是否要调整。 - （2）使用
array[0]暂存需要调整的数 - （3）在
array[1..i-1]中查找aray[i]的插入位置，array[1..j] < array[i] < R[j+1..i-1]；将array[j+1..i-1]中的所有记录均后移一个位置； - （4）将
array[0]插入到array[j+1]的位置上。
void InsertSort(int *array)
{
int i, j;
for (i = 2; i <= n; i++)
{
// 判断是否需要调整
if (array[i] < array[i - 1])
{
// 使用 array[0] 保存 array[i]
array[0] = array[i];
// 记录后移
array[i] = array[i - 1];
for (j = i - 2; array[0] < array[j]; j--)
{
array[j + 1] = array[j];
}
// 插入到有序子数组中
array[j + 1] = array[0];
}
}
}#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 直接插入排序
*/
void InsertSort(int *array)
{
int i, j;
for (i = 2; i <= n; i++)
{
if (array[i] < array[i - 1])
{
array[0] = array[i];
array[i] = array[i - 1];
for (j = i - 2; array[0] < array[j]; j--)
{
array[j + 1] = array[j];
}
array[j + 1] = array[0];
}
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * (n + 1));
printf("请输入数据（用空格分隔）：");
for (i = 1; i <= n; i++)
{
scanf("%d", &array[i]);
}
InsertSort(array);
printf("排序后为：");
for (i = 1; i <= n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}希尔排序也是插入排序的一种，但它在效率上要比上面的直接插入排序高，它是对直接插入排序的改进，它的基本思想是：
- （1）先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分组。
- （2）所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
- （3）然后，取第二个增量 d2< d1 重复上述的分组和排序，直至所取的增量 dt=1(dt<...< d2< d1)，即所有记录放在同一组中进行直接插入排序为止。
增量序列尤为关键（如何选择最佳增量序列，目前尚未解决），一般的初次取序列的一半为增量，以后每次减半，直到增量为 1。
算法步骤：
- （1）选择一个增量序列：初始
k = n / 2、之后k = k / 2，仅作举例； - （2）当 k > 0 时进行排序，会进行多趟排序；
- （3）每趟排序，根据对应的增量 k，将待排序列分割成若干子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
void ShellSort(int *array)
{
int k = n / 2; //增量序列（仅作举例）
while (k > 0)
{
int i, j;
// 划分子序列
for (i = k + 1; i <= n; i++)
{
// 插入排序
if (array[i] < array[i - k])
{
array[0] = array[i];
for (j = i - k; j > 0 && array[0] < array[j]; j -= k)
{
array[j + k] = array[j];
}
array[j + k] = array[0];
}
}
// 重新赋值 k
k = k / 2;
}
}#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 希尔排序
*/
void ShellSort(int *array)
{
int k = n / 2; //增量序列（仅作举例）
while (k > 0)
{
int i, j;
for (i = k + 1; i <=n; i++)
{
if (array[i] < array[i - k])
{
array[0] = array[i];
for (j = i - k; j > 0 && array[0] < array[j]; j -= k)
{
array[j + k] = array[j];
}
array[j + k] = array[0];
}
}
k = k / 2;
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * (n + 1));
printf("请输入数据（用空格分隔）：");
for (i = 1; i <= n; i++)
{
scanf("%d", &array[i]);
}
ShellSort(array);
printf("排序后为：");
for (i = 1; i <= n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}冒泡排序是一种交换排序，它的主要过程是：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。比较一趟之后，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法步骤：
- （1）外层循环定义进行 n-1 趟排序
- （2）内层循环进行两两比较
- （3）如果左边元素
array[j]大于右侧元素array[j + 1]，则进行交换
void BubbleSort(int *array)
{
int i, j, temp;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
// 交换
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 冒泡排序
*/
void BubbleSort(int *array)
{
int i, j, temp;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * n);
printf("请输入数据（用空格分隔）：");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
BubbleSort(array);
printf("排序后为：");
for (i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}快速排序是对冒泡排序的改进，它的基本思想是通过一趟排序将数据分成两部分，一部分中的数据都比另一部分中的数据小，再对这两部分中的数据再排序，直到整个序列有序。
其实现非常简单：
- （1）使用
Partition函数从原始数组中选取一个元素为中心。 - （1）所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表，这里递归调用本身分别将两个子表进行排序（对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个，此时 high >= low，递归结束）
- 实现的关键是分割原始数组：
int Partition(int *array, int low, int high)
{
int pivotkey = array[low];
array[0] = array[low];
while (low < high)
{
while (low < high && array[high] >= pivotkey)
{
high--;
}
array[low] = array[high];
while (low < high && array[low] <= pivotkey)
{
low++;
}
array[high] = array[low];
}
array[low] = array[0];
return low;
}- 快速排序
void QuickSort(int *array, int low, int high)
{
if (low < high)
{
int pivotloc = Partition(array, low, high);
QuickSort(array, low, pivotloc - 1);
QuickSort(array, pivotloc + 1, high);
}
}#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 分割使枢轴记录的左边元素比右边元素小
*/
int Partition(int *array, int low, int high)
{
int pivotkey = array[low];
array[0] = array[low];
while (low < high)
{
while (low < high && array[high] >= pivotkey)
{
high--;
}
array[low] = array[high];
while (low < high && array[low] <= pivotkey)
{
low++;
}
array[high] = array[low];
}
array[low] = array[0];
return low;
}
/*
* 快速排序递归实现
*/
void QuickSort(int *array, int low, int high)
{
if (low < high)
{
int pivotloc = Partition(array, low, high);
QuickSort(array, low, pivotloc - 1);
QuickSort(array, pivotloc + 1, high);
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * (n + 1));
printf("请输入数据（用空格分隔）：");
for (i = 1; i <= n; i++)
{
scanf("%d", &array[i]);
}
QuickSort(array, 1, n);
printf("排序后为：");
for (i = 1; i <= n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}简单选择排序的基本思想是：
通过 n-1 次数据元素的比较，从 n-i+1 个记录中选择最小的数据，并与第 i 个数据进行交换，如下图所示。
算法步骤：
- （1）循环 n 次，进行 n 趟排序
- （2）在第 i 趟排序中，从第 i 个元素开始向后查找最小的元素
- （3）将这个最小的元素不是第 i 个，而是在 i 之后的元素，则将这两个元素的位置对换。
void SelectSort(int *array)
{
int i, j, k, temp;
// n 趟排序
for (i = 0; i < n; i++)
{
k = i;
// 寻找最小的元素下标
for (j = i + 1; j < n; j++)
{
if (array[j] < array[k])
{
k = j;
}
}
// 如果这个不是第 i 个，则交换第 i 个和第 k 个
if (k != i)
{
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 选择排序
*/
void SelectSort(int *array)
{
int i, j, k, temp;
for (i = 0; i < n; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (array[j] < array[k])
{
k = j;
}
}
if (k != i)
{
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * n);
printf("请输入数据（用空格分隔）：");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
SelectSort(array);
printf("排序后为：");
for (i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}通过前面二叉树的学习，我们知道堆是完全二叉树，有最大堆和最小堆，其中最大堆是父结点的值比子结点大，相应的最小堆就是父结点的值比子节点小。
堆排序就是利用了最大堆（或最小堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字变得简单。以最大堆为例，它的基本思想就是：
- 先将初始文件
R[1..n]建成一个最大堆，此堆为初始的无序区； - 再将关键字最大的记录
R[1]（即堆顶）和无序区的最后一个记录R[n] 交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key； - 由于交换后新的根
R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n1..n].keys，同样要将R[1..n-2]调整为堆； - 重复此操作直到全部有序。
下面是示例图：
#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 生成堆
*/
void HeapAdjust(int *array, int s, int m)
{
int i;
array[0] = array[s];
for (i = s * 2; i <= m; i *= 2)
{
if (i < m && array[i] < array[i + 1])
{
i++;
}
if (!(array[0] < array[i]))
{
break;
}
array[s] = array[i];
s = i;
}
array[s] = array[0];
}
/*
* 堆排序
*/
void HeapSort(int *array)
{
int i;
for (i = n / 2; i > 0; i--)
{
HeapAdjust(array, i, n);
}
for (i = n; i > 1; i--)
{
array[0] = array[1];
array[1] = array[i];
array[i] = array[0];
HeapAdjust(array, 1, i - 1);
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * (n + 1));
printf("请输入数据（用空格分隔）：");
for (i = 1; i <= n; i++)
{
scanf("%d", &array[i]);
}
HeapSort(array);
printf("排序后为：");
for (i = 1; i <= n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}归并排序是建立在归并操作上的一种有效的排序算法，它过程为：
比较 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，则将第一个有序表中的元素 a[i] 复制到 r[k] 中，并令 i 和 k 分别加上 1；
否则将第二个有序表中的元素 a[j] 复制到 r[k] 中，并令 j 和 k 分别加上 1；
如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。
如下图所示。
#include <stdio.h>
#include <stdlib.h>
int n;
/*
* 合并
*/
void Merge(int *source, int *target, int i, int m, int n)
{
int j, k;
for (j = m + 1, k = i; i <= m && j <= n; k++)
{
if (source[i] <= source[j])
{
target[k] = source[i++];
}
else
{
target[k] = source[j++];
}
}
while (i <= m)
{
target[k++] = source[i++];
}
while (j <= n)
{
target[k++] = source[j++];
}
}
/*
* 归并排序
*/
void MergeSort(int *source, int *target, int s, int t)
{
int m, *temp;
if (s == t)
{
target[s] = source[s];
}
else
{
temp = (int*) malloc(sizeof(int) * (t - s + 1));
m = (s + t) / 2;
MergeSort(source, temp, s, m);
MergeSort(source, temp, m + 1, t);
Merge(temp, target, s, m, t);
}
}
int main()
{
int i;
int *array;
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * n);
printf("请输入数据（用空格分隔）：");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
MergeSort(array, array, 0, n - 1);
printf("排序后为：");
for (i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}基数排序是跟前面的几种排序算法完全不一样的排序算法，前面的排序算法主要通过关键字之间的比较和移动来实现，而基数排序不需要进行关键字之间的比较，它是借助多关键字的思想来实现的对于数字，每一位上的数字就是一个关键字，每一位的数字范围就是关键字范围，它的主要过程为：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零；
然后，从最低位开始，依次进行一次排序；
这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
如下图所示。类似从低位到高位比较，就是从次关键字到主关键字比较，这种称为最低位优先（LSD），反之称为最高位优先（MSD）。
#include <stdio.h>
#include <stdlib.h>
int n; //元素个数
int bit_num; //最大数字位数
/*
* 获取相应位置上的数（从右到左）
*/
int GetNumInPos(int num, int pos)
{
int i, temp = 1;
for (i = 0; i < pos - 1; i++)
{
temp *= 10;
}
return (num / temp) % 10;
}
/*
* 基数排序（LSD）
*/
void RadixSort(int *array)
{
int radix = 10;
int *count, *bucket, i, j, k;
count = (int*) malloc(sizeof(int) * radix);
bucket = (int*) malloc(sizeof(int) * n);
for (k = 1; k <= bit_num; k++)
{
for (i = 0; i < radix; i++)
{
count[i] = 0;
}
//统计各个桶中所盛数据个数
for (i = 0; i < n; i++)
{
count[GetNumInPos(array[i], k)]++;
}
//count[i]表示第i个桶的右边界索引
for (i = 1; i < radix; i++)
{
count[i] = count[i] + count[i - 1];
}
//分配
for (i = n - 1; i >= 0; i--)
{
j = GetNumInPos(array[i], k);
bucket[count[j] - 1] = array[i];
count[j]--;
}
//收集
for (i = 0, j = 0; i < n; i++, j++)
{
array[i] = bucket[j];
}
}
}
int main()
{
int i;
int *array;
printf("请输入最大数字的位数：");
scanf("%d", &bit_num);
printf("请输入数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * n);
printf("请输入数据（用空格分隔）：");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
RadixSort(array);
printf("排序后为：");
for (i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}查找包括：
- 顺序查找
- 散列查找
- 二分查找
顺序查找想必大家都知道，就是从头到尾比较数据集中的每一个数据，以此来获得想要的数据，但当数据集中拥有的数据较多时，这种方法的效率就会很低。
二分查找是比顺序查找效率高的一种查找算法，但它只适用于有序的数据集。
二分查找也叫折半查找，它的查找步骤为：
- （1）首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
- （2）否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
- （3）重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功，如下图所示。
二分查找函数需要的参数：
int *array：目标数组，在这个数组中进行查找int key：待查找的关键字int low、int high：查找的区间；若在整个数组中查找，调用时指定low为 0，high为数组的长度。
执行的流程：
- 若
key == array[mid]，查找成功 - 若
key < array[mid]，则high = mid-1，进行前一子表查找 - 若
key > array[mid]，则low = mid+1，进行后一字表查找
二分查找函数的实现：
// 若找到，则函数值为该元素在表中的位置，否则为 0
int BinarySearch(int *array, int key, int low, int high)
{
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (key == array[mid])
{
return mid;
}
else if (key < array[mid])
{
// 前一子表查找
high = mid - 1;
}
else
{
// 后一字表查找
low = mid + 1;
}
}
// 表中不存在待查元素
return 0;
}#include <stdio.h>
#include <stdlib.h>
int BinarySearch(int *array, int key, int low, int high)
{
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (key == array[mid])
{
return mid;
}
else if (key < array[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return 0;
}
int main()
{
int n, i, key, position;
int *array;
printf("请输入有序数组的大小：");
scanf("%d", &n);
array = (int*) malloc(sizeof(int) * n);
printf("请按升序输入数据：\n");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
printf("请输入想要查找的数：");
scanf("%d", &key);
if (position = BinarySearch(array, key, 0, n - 1))
{
printf("%d的位置为：%d\n", key, position);
}
else
{
printf("%d不存在\n", key);
}
}要构造哈希表首先需要有散列函数，并且这个散列函数需要尽可能地减少冲突，通常有下面几种构造方法：
我们通过一个例子来讲解，如果我们现在要对 0-20 岁的进行人口统计，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时 f(key) = key。
这个时候，我们可以得出这么个哈希函数：f(0) = 0，f(1) = 1，……，f(20) = 20。这个是根据我们自己设定的直接定址来的。人数我们可以不管，我们关心的是如何通过关键字找到地址。
如果我们现在要统计的是 80 后出生年份的人口数，那么我们对出生年份这个关键字可以用年份减去 1980 来作为地址。此时 f (key) = key-1980。
假如今年是 2000 年，那么 1980 年出生的人就是 20 岁了，此时 f(2000) = 2000 - 1980，可以找得到地址 20，地址 20 里保存了数据“人数 500 万”。
也就是说，我们可以取关键字的某个线性函数值为散列地址，即：
f(key) = a × key + b
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合査找表较小且连续的情况。由于这样的限制，在现实应用中，直接定址法虽然简单，但却并不常用。
数字分析法是在知道关键字的情况下，取关键字的尽量不重复的几位值组成散列地址。
平方取中法就是取关键字平方后的中间几位为散列地址。
折叠法是将关键字分为位数相等的几部分，最后一部分的位数可以不等，然后把这几部分的值（舍去进位）相加作为散列地址。
除留余数法此方法为最常用的构造散列函数方法。对于散列表长为 m 的散列函数公式为：
f( key ) = key mod p ( p ≤ m )
mod 是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
很显然，本方法的关键就在于选择合适的 p，p 如果选得不好，就可能会容易产生同义词。下面我们来举个例子看看：
有一个关键字，它有 12 个记录，现在我们要针对它设计一个散列表。如果采用除留余数法，那么可以先尝试将散列函数设计为 f(key) = key mod 12 的方法。比如 29 mod 12 = 5，所以它存储在下标为 5 的位置。
不过这也是存在冲突的可能的，因为 12=2×6=3×4。如果关键字中有像 18(3×6)、30(5×6)、42(7×6)等数字，它们的余数都为 6，这就和 78 所对应的下标位置冲突了。
使用除留余数法的一个经验是，若散列表表长为 m，通常 p 为小于或等于表长（最好接近 m)的最小质数或不包含小于 20 质因子的合数。实践证明，当 P 取小于散列表长的最大质数时，产生的散列函数较好。
随机数法是选择一个随机函数，取关键字的随机函数值作为散列地址。
前面在散列函数的构造中我们发现散列地址可能会产生冲突，所以处理冲突也是构造散列表中重要的一部分，通常处理冲突的方法有下面几种：
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入，公式为：
fi(key) = (f(key)+di) MOD m (di=1,2,3,...,m-1)
用开放定址法解决冲突的做法是：
当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存入该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}，表长为 12。 我们用散列函数 f(key) = key mod l2。
当计算前 S 个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入：
计算 key = 37 时，发现 f(37) = 1，此时就与 25 所在的位置冲突。
于是我们应用上面的公式 f(37) = (f(37)+1) mod 12 = 2。于是将 37 存入下标为 2 的位置。这其实就是房子被人买了于是买下一间的作法：
接下来 22,29,15,47 都没有冲突，正常的存入：
到了 key=48，我们计算得到 f(48) = 0，与 12 所在的 0 位置冲突了，不要紧，我们 f(48) = (f(48)+1) mod 12 = 1，此时又与 25 所在的位置冲突。于是 f(48) = (f(48)+2) mod 12=2，还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6 时，才有空位，机不可失，赶快存入：
我们把这种解决冲突的开放定址法称为线性探测法。
考虑深一步，如果发生这样的情况，当最后一个 key=34，f(key)=10，与 22 所在的位置冲突，可是 22 后面没有空位置了，反而它的前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差。
因此我们可以改进 di = 12, -12, 22, -22,……, q2, -q2 (q <= m/2)，这样就等于是可以双向寻找到可能的空位置。
对于 34 来说，我们取 di 即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。
fi(key) = (f(key)+di) MOD m (di = 12, -12, 22, -22,……, q2, -q2, q <= m/2)
还有一种方法，是在冲突时，对于位移量 di 采用随机函数计算得到，我们称之为随机探测法。此时一定会有人问，既然是随机，那么查找的时候不也随机生成吗？如何可以获得相同的地址呢？这是个问题。这里的随机其实是伪随机数。
伪随机数是说，如果我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在査找时，用同样的随机种子，它每次得到的数列是相同的，相同的 di 当然可以得到相同的散列地址。
fi(key) = (f(key)+di) MOD m (di 是一个随机数列)
总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。
再哈希法是：当散列地址冲突时，用另外一个散列函数再计算一次，这种方法减少了冲突，但增加了计算的时间。
前面我们谈到了散列冲突处理的开放定址法，它的思路就是一旦发生了冲突，就去寻找下一个空的散列地址。那么，有冲突就非要换地方吗？我们直接就在原地处理行不行呢？可以的，于是我们就有了链地址法：
将所有关键字散列地址相同的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。
对于关键字集合{12,67,56,16,25,37, 22,29,15,47,48,34}，我们用 12 为除数，进行除留余数法：
此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。链地址法解决冲突的做法是：将所有关键字散列地址相同的结点链接在同一个单链表中。若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1]。凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。T 中各分量的初值均应为空指针。在拉链法中，装填因子 α 可以大于 1，但一般均取α≤1。
链地址法的优势是对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了査找时需要遍历单链表的性能损耗，不过性能损耗在很多场合下也不是什么大问题。
这种方法的基本思想是：将散列表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
计算$$\large a_{i,j}$$在压缩矩阵中的下标
+1个空间是为了存储这个常数c
数组下标$$k=3*(i-1)-1+j-i+1=2*i+j-3$$
稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
理解三个概念：前缀、后缀、部分匹配值
计算模式串中所有前缀的部分匹配值
匹配成功则向后推进，匹配失败则根据next[]数组回退（j-1 - next[j-1]）步。
public class KMP2 {
private int next[];
private String pat;
public static void main(String[] args) {
KMP2 kmp = new KMP2("issip");
int res = kmp.search("mississippi");
System.out.println("res: " + res);
}
public KMP2(String pat) {
this.pat = pat;
getNext(pat);
}
public void getNext(String pat) {
char[] p = pat.toCharArray();
next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
}
public int search(String text) {
char[] t = text.toCharArray();
char[] p = pat.toCharArray();
int i = 0; // 主串位置
int j = 0; // 模式串位置
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) {
i++; j++;
} else {
j = next[j]; // j回退
}
}
if (j == p.length) {
return i-j;
} else {
return -1;
}
}
}利用动态规划 二维dp 实现KMP算法
public class KMP {
private int[][] dp;
private String pat;
public static void main(String[] args) {
KMP kmp = new KMP("issip");
int res = kmp.search("mississippi");
System.out.println("res: " + res);
}
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
// dp[状态][字符] = 下个状态
dp = new int[M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 构建状态转移图（稍改的更紧凑了）
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++) {
if (pat.charAt(j) == c) {
dp[j][c] = j + 1;
} else {
dp[j][c] = dp[X][c];
}
}
// 更新影子状态
X = dp[X][pat.charAt(j)];
}
}
public int search(String txt) {
int M = pat.length();
int N = txt.length();
// pat 的初始态为 0
int j = 0;
for (int i = 0; i < N; i++) {
// 计算 pat 的下一个状态
j = dp[j][txt.charAt(i)];
// 到达终止态，返回结果
if (j == M) return i - M + 1;
}
// 没到达终止态，匹配失败
return -1;
}
}该问题是十九世纪著名的数学家高斯1850年提出： 在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
本人在学习计算机专业知识的过程中，深知学习笔记的重要性，所以整理了相关学习笔记，为了在需要的时候方便查看，目前正在逐渐完善和补充中，如果本学习笔记有幸被您光顾和使用，在使用中出现任何疑问或者有更好的见解的话，可以右下角 OPEN CHAT 我，也可以右上角 邮我，当然还可以加入我的讨论组，如果觉得本书对你有帮助，可以打赏我，以鼓励我更好的创作，下面附微信支付二维码，再次谢谢您的大力支持！
觉得文章有帮助，不妨请我喝杯 Coffee，祝福好心人年年高升！