一、线性表的连接存储
1 、单链表
单链表定义：每个结点只含有一个链接域的链表
头指针(head) 尾指针(tail) 哨位结点对应指针(dummyhead)
哨位结点的作用：简化边界条件的处理
判断空表的条件（含哨位结点）：head->next==NULL
判断表尾的条件：tail->next=NULL
1、返回链表第k个节点的地址(包括哨位结点)
Node*Find(Node*head,int k)
{
if(k<0)
{
return NULL; //输入k的位置不合法
}
Node* p=head; //p指向哨兵结点
for(int i=0;i<k && p!=NULL;i++) //找到第k个节点
{
p=p->next;
}
return p;
}
//若i==k则p为所求，返回p的值
//若p==NULL，链表长度不够，返回NULL
2、找到链表中data域值为item的结点并返回其指针(不包括哨位结点)
Node*search(Node*head,int item)
{
Node*p=head; //p指向头结点
while(p!=NULL && p->data!=item)
{
p=p->next;
}
return p;
}
//若p->data=item，则返回p，p即为所求
//若p=NULL，表示没有item结点，返回NULL
3、删除第k个结点（有哨位结点）
void deleteNode(Node*head,int k)
{
if(k<1)
{
return -1;
}
Node*p=head //p指向哨位结点
for(int i=0;i<k-1;i++)
{
p=p->next; //让指针p指向第k-1个结点
}
if(p==NULL || p->next) //第k-1个结点不存在或者第k个结点不存在
{
return -1;
}
Node*q=p->next; //让指针q指向第k个结点
p->next=q->next;
free(q); //删除掉第k个结点
}
4、在链表第k个结点后插入一个结点
void insertNode(Node*head,int k,int item)
{
Node*p=head; //p指向哨位结点
for(int i=0;i<k;i++)
{
p=p->next;
}
if(p==NULL)
{
return -1;
}
Node*q=(Node*)malloc(sizeof(Node));
q->next=p->next;
q->data=item;
p->next=q;
}
2、循环链表
循环链表的定义：表尾的next域存放在哨位结点的指针，而不是存放在NULL）中
判断空表的条件（包含哨位结点）：head->next==head
判断表尾的条件：tail->next==head
3、双向链表
双向链表的定义：每个结点都有一个前驱和一个后继
优点：方便找结点的前驱
1、删除结点s
(1) 常规情况：s是中间结点
(2) s是第一个结点
引入表头哨位结点
(3) s是最后一个结点
表尾引入哨位结点
带双哨位结点的删除
void deleteNode(Node*head,Node*tail,Node*s)
//删除双链表（带双哨位结点）中非哨位结点s
//head,tail,s都非空
{
Node*prev=s->prev;
Node*current=s->next;
prev->next=current;
current->prev=prev;
s->prev=NULL; //通过将s->prev和s->next设置为NULL，可以确保s不再引用链表中的其他节点
s->next=NULL;
}
2、插入结点s
带单哨位结点的插入
void insertNode(Node*head,Node*s,Ndoe*p)
//双链表（带单哨位链表）中结点s的后面插入结点p
{
p->next=s->next;
s->next->prev=p;
p->prev=s;
s->next=p;
}
4、顺序表和链式表的比较
1、顺序存储->数组：如果一个数组是在main函数中定义的，那么将他以参数的形式传到一个函数中操作之后并不需要返回这个数组
因为原数组是通过指针传递的，函数内部对其进行的修改会影响到原数组
（在C语言中，如果你将一个数组通过指针传递给一个函数，并在函数内部修改了数组的元素，那么这些修改将直接影响到原始数组。）
2、链式存储->head哨兵结点传入一个函数后，将在函数内部修改它后面的结点，而这些修改将直接影响到整个链表，并不需要返回哨兵结点
如果只是一个指针head传入一个函数，如果在函数内部head指针指向的结点变更过，那么应该返回这个指针以更新指针指向的地址
eg:(栈的stacktop指针)
5、静态链表
静态单链表
静态双链表
6、侵入式链表
7、链表的双指针技巧
1、找单链表倒数第k个结点
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* insertNode(Node* head,int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
if (head == NULL)
{
head = node;
}
else
{
Node* current = head;
while (current->next)
{
current = current->next;
}
current->next = node;
return head;
}
}
int searchNode(Node* head, int k)
{
Node* fast = head;
Node* slow = head;
for (int i = 1; fast!=NULL && i < k; i++)
{
fast = fast->next;
}
if (fast == NULL)
{
return 0;
}
while (fast->next != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow->data;
}
void printList(Node* head)
{
Node* temp = head;
while (temp)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void freeNode(Node* head)
{
Node* temp = head;
while (head)
{
head = head->next;
free(temp);
temp = head;
}
}
int main()
{
Node* head = NULL;
head = insertNode(head, 1);
head = insertNode(head, 2);
head = insertNode(head, 3);
head = insertNode(head, 4);
head = insertNode(head, 5);
printf("The list is: ");
printList(head);
int k = 3;
int result=searchNode(head, k);
printf("%d", result);
freeNode(head);
return 0;
}
2、找出单链表中间结点
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* insertNode(Node* head,int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
if (head == NULL)
{
head = node;
}
else
{
Node* current = head;
while (current->next)
{
current = current->next;
}
current->next = node;
}
return head;
}
void printList(Node* head)
{
Node* temp = head;
while (temp)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
Node* searchNode(Node* head)
{
Node* fast = head, *slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
void freeNode(Node* head)
{
Node* temp = head;
while (head)
{
head = head->next;
free(temp);
temp = head;
}
}
int main()
{
Node* head = NULL;
head = insertNode(head, 1);
head = insertNode(head, 2);
head = insertNode(head, 3);
head = insertNode(head, 4);
head = insertNode(head, 5);
printf("The list is: ");
printList(head);
Node*middle=searchNode(head);
printf("%d\n", middle->data);
freeNode(head);
return 0;
}
//方法一
Node*slow=head; Node*fast=head;
while(fast->next && fast->next->next)
//方法二
Node*slow=head; Node*fast=head->next;
while(fast && fast->next)
3、链表相交（并找出第一个相交的结点）
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* insertNode1(Node* head1,int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
if (head1 == NULL)
{
head1 = node;
}
else
{
Node* current = head1;
while (current->next)
{
current = current->next;
}
current->next = node;
}
return head1;
}
Node* insertNode2(Node* head2, int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
if (head2 == NULL)
{
head2 = node;
}
else
{
Node* current = head2;
while (current->next)
{
current = current->next;
}
current->next = node;
}
return head2;
}
void printList1(Node* head1)
{
Node* temp = head1;
while (temp)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void printList2(Node* head2)
{
Node* temp = head2;
while (temp)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
static Node* p1 = NULL;
Node* crossNode(Node* head1, Node* head2)
{
Node* p1 = head1; //判断是否相交
Node* p2 = head2;
int L1=1, L2 = 1;
while (p1->next)
{
p1 = p1->next;
L1++;
}
while (p2->next)
{
p2 = p2->next;
L2++;
}
if (p1 != p2)
return NULL;
if (L1 >= L2) //找出第一个相交的结点
{
p1 = head1;
p2 = head2;
}
else
{
p1 = head2;
p2 = head1;
}
for (int i = 0; i < abs(L1 - L2); i++)
{
p1 = p1->next;
}
while (p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
void freeNode1(Node* head1)
{
Node* temp = head1;
while (head1)
{
head1 = head1->next;
free(temp);
temp = head1;
}
}
void freeNode2(Node* head2)
{
Node* temp = head2;
while (head2)
{
head2 = head2->next;
free(temp);
temp = head2;
}
}
int main()
{
Node* head1 = NULL;
Node* head2 = NULL;
head1 = insertNode1(head1, 1);
head1 = insertNode1(head1, 2);
head1 = insertNode1(head1, 3);
head1 = insertNode1(head1, 4);
head1 = insertNode1(head1, 5);
printf("The list1 is:");
printList1(head1);
head2 = insertNode2(head2, 6);
head2 = insertNode2(head2, 7);
head2 = insertNode2(head2, 5);
printf("The list2 is:");
printList2(head2);
Node* p1 = crossNode(head1, head2);
printf("%d\n", p1->data);
freeNode1(head1);
freeNode2(head2);
}
4、单链表判环问题（并找到环的起点）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head)
{
struct ListNode*fast=head,*slow=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
return true;
}
}
return false;
}
```c
Node*searchNode(Node*head)
{
Node*fast=head,*slow=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow) //返回环的起点
{
Node*p1=head;
Node*p2=fast;
while(p1!=p2)
{
p1=p1->next;
p2=p2->next;
}
return p1;
}
}
return NULL;
}
5、判断一个单链表是否是回文
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head)
{
struct ListNode* fast=head,*slow=head; //快慢指针找中点
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
struct ListNode*prev=NULL; //反转后半部分链表
struct ListNode*current=slow;
struct ListNode*next=NULL;
while(current)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
struct ListNode*a=head; //判断回文
struct ListNode*b=prev;
while(b!=NULL)
{
if(a->val!=b->val)
{
return false;
}
a=a->next;
b=b->next;
}
return true;
}
6、重排链表结点
方法：（1）找中间结点（2）反转后半部分链表（3）前半段和反转后的后半段合并
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode*reverseList(struct ListNode*right)
{
struct ListNode*prev=NULL;
struct ListNode*curr=right;
while(curr)
{
struct ListNode*next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev;
}
struct ListNode* arrangeList(struct ListNode*A,struct ListNode*B)
{
struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*cur=dummyhead;
int i=0;
while(A && B)
{
if(i & 1)
{
cur->next=B;
B=B->next;
}
else
{
cur->next=A;
A=A->next;
}
cur=cur->next;
i++;
}
cur->next=A ? A : B;
struct ListNode*newhead=dummyhead->next;
dummyhead->next=NULL;
free(dummyhead);
return newhead;
}
void reorderList(struct ListNode*head) //c语言中此函数调用的函数必须在此函数上边实现或者声明
{
struct ListNode* fast=head, *slow=head;
while(fast->next && fast->next->next)
{
fast=fast->next->next;
slow=slow->next;
}
struct ListNode*right=slow->next;
slow->next=NULL;
struct ListNode*head2=reverseList(right); //找到链表的中间结点
struct ListNode*newhead=arrangeList(head,head2); //重新排列
}
7、一元多项式及其操作
二、栈与队列及其应用
栈：相当于链表的头插法
1、进制转换
十进制转换成八进制：(66)10=(102)8
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
int isEmpty(Node* stacttop)
{
if (stacttop == NULL)
{
return -1;
}
return 0;
}
Node* Push(Node* stacttop, int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = stacttop;
stacttop = node;
return stacttop;
}
Node* Pop(Node* stacttop) /*Pop函数要定义为Node*类型，这样可以保证能够返回修改后的链表如果用int型函数内
{ 部对 stacktop 的修改不会影响到函数外部的指针。*/
Node* cur = stacttop; //还可以int Pop(Node** stacttop)
int data = cur->data;
if (stacttop != NULL)
{
stacttop = stacttop->next;
free(cur);
printf("%d", data);
}
return stacttop;
}
int main()
{
Node* stacttop = NULL; //这里是将stacttop定义为一个Node型的指针，并不是一个结点
int n = 0;
printf("print a data:");
scanf_s("%d", &n);
while (n > 0)
{
stacttop = Push(stacttop, n%8);
n = n / 8;
}
while (!isEmpty(stacttop))
{
stacttop=Pop(stacttop);
}
return 0;
}
2、括号匹配
c的算法思路
不匹配共有三种情况：1、左括号多了 2、右括号多了 3、括号不多但是不匹配
bool isValid(char * s)
{
int len=strlen(s);
char* stack=(char*)malloc(sizeof(char)*len);
int count=0;
for(int i=0;i<len;i++)
{
if(s[i]=='('){
stack[count++]=')';
}else if(s[i]=='[')
{
stack[count++]=']';
}else if(s[i]=='{')
{
stack[count++]='}';
}else if(count==0 || stack[count-1]!=s[i]) //情况2、3
{
free(stack);
return false;
}else count--;
}
return count==0; //情况1 在bool函数中return count==0;即为判断count是否为0；是返回true；不是返回false
}
7、队列的讨论以及应用
队：相当于链表尾插法
循环队列：用顺序表实现的
打印循环队列：只要涉及到减法egf：判断队列长度（防止出现负数的情况）
三、数组与矩阵
1、数组存储与寻址
2、特殊矩阵的压缩存储
1、对角矩阵的压缩存储
2、三角矩阵的压缩储存
1+2+3+……+n=n*(n+1)/2
下标是k属于第26个元素
（上例是按行优先存储的，如果按列优先存储，则不符合公式，具体参考下题）
上题为按行优先存入，所以不符合公式
3、对称矩阵的压缩存储
上三角元素按列优先存入
下三角M(i,j)=M(7,2)=上三角M(j,i)=M(7,2)
4、三对角矩阵的压缩存储
按行存储(从第一行到第i行)eg:下面例题
3、稀疏矩阵的压缩存储
1、顺序存储方式：三元组表
行列转换
时间复杂度为O(nt)的算法
#include<stdio.h>
#include<stdlib.h>
typedef struct Triple
{
int row;
int col;
int data;
}Triple;
int Maxcol(Triple* a, int len) //先求出最大行数
{
int maxcol = 0;
for (int i = 0; i < len; i++)
{
if (a[i].col > maxcol)
{
maxcol = a[i].col;
}
}
return maxcol;
}
void TransposeTriple(Triple* a, Triple* b, int len,int maxncol)
{
int j = 0;
for (int k = 1; k <= maxncol; k++) //这里要注意k要能等于maxncol即等于最大行数
{
for (int i = 0; i < len; i++)
{
if (a[i].col == k)
{
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].data = a[i].data;
j++;
}
}
}
}
void printTriple(Triple* a, Triple* b, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d %d %d\n", a[i].row, a[i].col, a[i].data);
}
printf("\n");
for (int i = 0; i < len; i++)
{
printf("%d %d %d\n", b[i].row, b[i].col, b[i].data);
}
printf("\n");
}
int main()
{
Triple a[] =
{
{ 1,1,50 },
{ 2,1,10 },
{ 2,3,20 },
{ 4,1,-30 },
{ 4,3,-60 },
{ 4,4,5 },
};
int len = sizeof(a) / sizeof(a[0]);
int maxcol = Maxcol(a, len);
Triple* b = (Triple*)malloc(sizeof(Triple) * len);
TransposeTriple(a, b, len,maxcol);
printTriple(a, b, len);
free(b); //跟free链表不同的是只用free掉b一个即可因为 sizeof(Triple) * len；
return 0;
}
时间复杂度为O(n+t)的算法
#include<stdio.h>
#include<stdlib.h>
#define maxn 100
typedef struct Triple
{
int row;
int col;
int data;
}Triple;
void Rowsize(Triple* a, int len,int* rowsize)
{
int k = 0;
for (int i = 0; i < len; i++) //注意此处遍历数组的长度为len
{
k = a[i].col;
rowsize[k]++;
}
}
void TransposeTriple(Triple* a, Triple* b, int len,int* rowsize)
{
int k = 0;
int j = 0;
int start[maxn + 1] = { 0 }; //注意这里因为不需要start[0]而且要能够遍历到start[maxn] 所以可以将数组设为maxn+1个元素
for (int i = 2; i <= maxn; i++) //注意这里要遍历maxn所以是<=maxn
{
start[i] = start[i - 1] + rowsize[i - 1];
}
for (int i = 0; i < len; i++)
{
k = a[i].col;
j = start[k];
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].data = a[i].data;
start[k]++;
}
}
void printTriple(Triple* a, Triple* b, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d %d %d\n", a[i].row, a[i].col, a[i].data);
}
printf("\n");
for (int i = 0; i < len; i++)
{
printf("%d %d %d\n", b[i].row, b[i].col, b[i].data);
}
printf("\n");
}
int main()
{
Triple a[]=
{
{ 1,1,50 },
{ 2,1,10 },
{ 2,3,20 },
{ 4,1,-30 },
{ 4,3,-60 },
{ 4,4,5 },
};
int len = sizeof(a) / sizeof(a[0]);
int rowsize[maxn] = { 0 }; /*后续TransposeTriple函数中还要继续用到rowsize数 所以要将rowsize数组定义为全局变量*/
Rowsize(a, len, rowsize);
Triple* b = (Triple*)malloc(sizeof(Triple) * len);
TransposeTriple(a, b, len,rowsize);
printTriple(a, b, len);
free(b);
return 0;
}
2、十字链表
4、递归与动态规划
1、递归介绍
递归算法的时间复杂度高，效率低
原因：包含过多重复计算
#include<stdio.h>
#include<stdlib.h>
int F(int n)
{
if (n <= 1)
{
return n;
}
return F(n - 1) + F(n - 2);
}
int main()
{
int n = 0;
scanf_s("%d", &n);
printf("%d", F(n)); //在C语言中，函数调用表达式的返回值可以直接用作其他表达式的一部分
return 0;
}
2、动态规划介绍
3、一维情况
1、一维动态规划01
动态规划优化时间复杂度(时间复杂度为O(n)）
动态规划优化时间复杂度的方法为：用一个局部数组来存储已经计算过的数值，避免重复计算
空间复杂度为O(n)
#include<stdio.h>
#include<stdlib.h>
#define maxn 100
int Fib(int n)
{
int F[maxn] = { 0 }; //注意不能int F[]={0};数组的大小会根据初始值的数量进行推断。在这个例子中数组大小为1
F[0] = 0;
F[1] = 1;
for (int i = 2; i <= n; i++)
{
F[i] = F[i - 1] + F[i - 2];
}
return F[n];
}
int main()
{
int n = 0;
scanf_s("%d", &n);
printf("%d", Fib(n));
return 0;
}
2、一维动态规划02
空间复杂度为O(1)
用一个整型的局部变量来存储F(i)的值,并不断更新，知道其为F(n)的值，然后返回
#include<stdio.h>
#include<stdlib.h>
int Fib(int n)
{
int cur = 0;
int prev1 = 0, prev2 = 1;
if (n <= 1) //注意用这种方法时要保证有n<=1时的情况
{
return n;
}
for (int i = 2; i <= n; i++)
{
cur = prev1 + prev2;
prev1 = prev2;
prev2 = cur;
}
return cur;
}
int main()
{
int n;
scanf_s("%d", &n);
printf("%d", Fib(n));
return 0;
}
题目条件更换
4、二维情况
1、二维递归
递归实现
#include<stdio.h>
#include<stdlib.h>
int Fib(int m, int n)
{
if (m || n == 0)
{
return 1;
}
return Fib(m, n - 1) + Fib(m - 1, n);
}
int main()
{
int m = 0, n = 0;
scanf_s("%d %d", &m, &n); //注意取址符号
printf("%d", Fib(m, n));
}
2、二维动态规划01
时间、空间复杂度均为O(m*n)的动态规划算法
步骤：先初始化一个二维数组，然后填第0列和第0行，最后填其他位置
注意初始二维数组: int F[N][N] = {{0}}; 将所有元素都显式初始化为0，确保了整个二维数组中的每个元素都是0。
int F[N][N] = {0}; 只将第一个元素初始化为0，其他元素将被默认初始化为0。
int F[][N] = {{0}};创建了一个二维数组F，第一维的大小根据初始值列表中的元素数量进行推断，第二维的大小为N`。所有元素都被初始化为0。
#include<stdio.h>
#include<stdlib.h>
#define maxn 10
int Fib(int m, int n)
{
int F[maxn][maxn] = { {0} };
for (int i = 0; i < m; i++)
{
F[i][0] = 1; //将第0列的数组元素值附为1
}
for (int i = 0; i < n; i++)
{
F[0][i] = 1; //将第0行的数组元素值附为1
}
if (m==0 || n == 0)
{
return F[m][n];
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
F[i][j] = F[i][j - 1] + F[i - 1][j];
}
}
return F[m-1][n-1];
}
int main()
{
int m = 0,n = 0;
scanf_s("%d %d", &m, &n); //注意取址符
printf("%d", Fib(m, n));
return 0;
}
3、二维动态规划02
空间复杂度为O(n)的动态规划算法
滚动数组
步骤：创建一个一维数组来表示每一行各个列元素，然后遍历数组将所有元素附为1，最后再遍历
#include<stdio.h>
#include<stdlib.h>
#define maxn 100
int Fib(int m, int n) //这种方法不能返回行数为0的二维数组元素
{
int F[maxn] = { 0 };
for (int i = 0; i <= n; i++)
{
F[i] = 1;
}
if (m == 0)
{
return F[n];
}
for (int i = 1; i < m; i++)
{
for (int j = 0; j < n; j++)
{
F[j] = F[j - 1] + F[j];
}
}
return F[n-1];
}
int main()
{
int m = 0, n = 0;
scanf_s("%d %d", &m, &n); //记得取址符
printf("%d", Fib(m, n));
return 0;
}
62. 不同路径 - 力扣（LeetCodehttps://leetcode.cn/problems/unique-paths/description/）
4、排列组合公式 $c_m^n$ 实现(无障碍物)
在此之前上述所有方法均是在无障碍物的情况下实现的
1、法一：只返回一个值即$c_m^n$
上 边是n~m-1一共m个数，下边是m—1一共m个数
在C语言中，long long 是一种整数数据类型修饰符，用于声明一个更大范围的整数变量。
它通常用于表示非常大的整数值，超过了int和long类型的表示范围
int F(int n,int m)
{
long long a=1,b=1;
for(int i=n;i>=n-m+1;i--)
{
a*=i;
}
for(int i=m;i>=1;i--)
{
b*=i;
}
return a/b;
}
2、法2：可以返回中间过程值,也可以只返回$c_m^n$
int F(int n,int m)
{
if(m==0 || m==n) return 1;
if(m>n/2) m=n-m; //利用排列组合的性质
long long ans=1;
for(int i=n-m+1,j=1;i<=n,j<=m;i++,j++)
{
ans=ans*i/j;
}
return ans;
}
int uniquePaths(int m, int n){
long long ans=1;
if(m==1 || n==1) return 1;
for(int i=n,j=1;i<=n+m-2;i++,j++)
{
ans=ans*i/j;
}
return ans;
}
5、排列组合公式$c_m^n$实现(有障碍物)
上述情况分为5种：1、map位于
2、map位于
3、map位于
4、map位于
5、map位于
5、最大子数组和
memset函数是C和C++编程语言中常用的函数，它在<cstring>（C++）或<string.h>（C）头文件中声明。它接受三个参数：
- 要设置的内存块的指针（在这个例子中是
nums）。 - 要设置的值（在这个例子中是0）。
- 要设置的内存块的大小（在这个例子中是
sizeof(int) * n）
int maxSubArray(int* nums, int numsSize){
int f=nums[0];
int maxsum=f;
for(int i=1;i<numsSize;i++)
{
if(f>0) f=f+nums[i];
else f=nums[i];
if(f>maxsum) maxsum=f;
}
return maxsum;
}
1、遍历所有数组
算法思路： i=0；j=0;k=0;k<=0
sum=a[0]
i=0;j=1;k=0;k<=1 i的作用：子数组和的起点元素
sum=a[0]+a[1]; j的作用：此次有多少个元素求和
i=0;j=2;k=0;k<=2; k的作用：将此次的元素求和
#include<limits.h>
int maxSubArray(int* a,int n)
{
int maxsum=INT_MIN;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=a[k];
}
if(sum>maxsum) maxsum=sum;
}
}
return maxsum;
}
2、利用sum优化
算法思路：将if()条件语句放进第二次循环，sum每更新一次，就判断一次
#include<limits.h>
int maxSubArray(int* a,int n)
{
int maxsum=INT_MIN;
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=i;j<n;j++)
{
sum+=a[j];
if(sum>maxsum) maxsum=sum;
}
}
return maxsum;
}
3、线性时间算法01
f(i)表示以i结尾的子数组的最大和
#define maxn 1e5+10;
int maxSubArray(int* a,int n)
{
int f[maxn]; f[0]=a[0]
int maxsum=f[0];
for(int i=1;i<n;i++)
{
if(f[i-1]>0) f[i]=f[i-1]+a[i];
else f[i]=a[i];
if(f[i]>maxsum) maxsum=f[i];
}
return maxsum;
}
4、线性时间算法02
int maxSubArray(int* a,int n)
{
int f=a[0];
int maxsum=f;
for(int i=1;i<n;i++)
{
if(f>0) f=f+a[i];
else f=a[i];
if(f>maxsum) maxsum=f;
}
return maxsum;
}
连续子数组的最大和(二)_牛客题霸_牛客网 (nowcoder.com)
6、最大数组乘积
int max(int a,int b,int c)
{
int maxval=a;
if(b>maxval) maxval=b;
if(c>maxval) maxval=c;
return maxval;
}
int min(int a,int b,int c)
{
int minval=a;
if(b<minval) minval=b;
if(c<minval) minval=c;
return minval;
}
int maxProduct(int a[],int n)
{
int f=a[0];
int g=a[0];
int maxproduct=a[0];
for(int i=1;i<n;i++)
{
int pref=f*a[i];
int preg=g*a[i];
f=max(pref,preg,a[i]);
g=min(pref,preg,a[i]);
if(f>maxproduct) maxproduct=f;
}
return maxproduct;
}
5、区间处理技巧
1、前缀和
前缀和技巧适用情况：数组在不被修改的前提下频繁查询某个区间的累加和
#include<stdio.h>
#include<stdlib.h>
void creatArray(int* a, int len)
{
for (int i = 0; i <len; i++)
{
scanf_s("%d ", &a[i]);
}
}
void Inquire(int* a, int len,int m)
{
int average = 0;
int i = 0, j = 0;
for (int k = 1; k <= m; k++)
{
int sum = 0;
scanf_s("%d %d", &i, &j);
for (int b=i; b <= j; b++)
{
sum += a[b];
}
average = sum / (j - i + 1);
printf("%d", average);
}
}
int main()
{
int n = 0,m=0;
scanf_s("%d %d", &n, &m);
int len = n + 1;
int* a = (int*)malloc(sizeof(int) * len);
creatArray(a, len);
Inquire(a, len,m);
free(a);
return 0;
}
while(m--)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=a[k];
}
}
空间复杂度为：O(n)
# define maxn 1e5+10;
int main()
{
int sum[maxn]=0;
int n=0,m=0,i=0,j=0;
scanf("%d",&n);
int len=n+1;
int* a=(int*)malloc(sizeof(int)*len);
for(int i=1;i<len;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
scanf("%d",&m);
while(m--)
{
scanf("%d %d",&i,&j);
printf("%d",sum[j]-sum[i-1]);
}
free(a);
return 0;
}
2、差分数组
差分数组适用场合：频繁对数组某个区间的元素进行增减
下列示例为差分数组前提之一
/**
* Note: The returned array must be malloced, assume caller calls free().
bookings: 一个二维数组，表示航班预订表。bookings[i]表示第i条预订记录，包含三个元素: firsti、lasti、seatsi。其中，firsti表示预订起始航班编号，lasti表示预订结束航班编号，seatsi表示在这些航班上 预订的座位数量。
bookingsSize: 表示bookings数组的行数，即预订记录的数量。
bookingsColSize: 一个整数指针数组，表示bookings数组的列数。由于bookings是一个二维数组，每条预订记录的元素数量可能不一样，因此使用bookingsColSize来表示每条记录的列数。
n: 表示航班的总数，航班从1到n进行编号。
returnSize: 一个整数指针，用于指示返回的数组的长度。
*/
int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize) {
int* nums = malloc(sizeof(int) * n);
memset(nums, 0, sizeof(int) * n);
*returnSize = n;
for (int i = 0; i < bookingsSize; i++) {
nums[bookings[i][0] - 1] += bookings[i][2];
if (bookings[i][1] < n) {
nums[bookings[i][1]] -= bookings[i][2]; //难点
}
}
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n = 0, m = 0,i=0,j=0,d=0;
scanf_s("%d", &n);
int len = n + 1;
int* a = (int*)malloc(sizeof(int)*len);
for (int i = 0; i < len; i++)
{
scanf_s("%d", &a[i]);
}
scanf_s("%d", &m);
while (m--)
{
scanf_s("%d %d %d", &i, &j, &d);
for (int k = i; k <= j; k++)
{
a[k]+=d;
}
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
}
free(a);
return 0;
}
差分数组的核心思想：
diff[i]+=d；
f(j<n) diff(j+1) - =d;(与leetcode题目1109的区别：此题的下标从1开始，所以应为 if(j<n) diff(j+1) - =d;而不是 if(j<n) diff(j) =d;)
3、ST表
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int main()
{
int n = 0, m = 0, i = 0, j = 0;
scanf_s("%d", &n);
int* a = (int*)malloc(sizeof(int) * (n + 1));
for (int i = 0; i <= n; i++)
{
scanf_s("%d ", &a[i]);
}
scanf_s("%d", &m);
while (m--)
{
int max = INT_MIN;
scanf_s("%d %d", &i, &j);
for (int k = i; k <= j; k++)
{
if (a[k] > max) max = a[k];
}
printf("%d\n", max);
}
return 0;
}
如何计算$2^j$
P3865 【模板】ST 表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
4、尺取法
双指针法
暴力解决
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n = 0, S = 6;
scanf_s("%d", &n);
int* a = (int*)malloc(sizeof(int));
for (int i = 0; i < n; i++)
{
scanf_s("%d ", &a[i]);
}
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
sum += a[j];
if (sum == S)
{
printf("%d %d\n",i,j);
}
}
}
return 0;
}
下列算法：外层的while循环是一个无限循环，只有在内层的if语句中满足条件时才会跳出循环。
内层的while循环用于向右扩展子数组的右边界，直到子数组的元素之和大于等于给定值S或者右边界到达数组的最后一个元素。每次循环，right指针向右移动一位，同时累加当前位置的元素到sum中
当满足if(sum<S) break;时rifht=n-1 && sum<S
当不满足if(sum
前提补充：++a和a++的区别
/*原始代码中的sum+=a[++right]使用了前缀递增操作符++right，它会先将right的值增加1，然后将增加后的值用于索引数组元素。
如果将其替换为sum+=a[right++]，使用后缀递增操作符right++，则会先使用right的当前值进行索引，然后再将right的值增加1。*/
#include <stdio.h>
void examplePrefixIncrement() {
int a[] = { 1, 2, 3, 4, 5 };
int n = sizeof(a) / sizeof(a[0]);
int left = 0, right = 0, sum = a[0];
while (right < n - 1 && sum < 10) {
sum += a[++right];
}
printf("Prefix Increment:\n");
printf("Sum: %d\n", sum);
printf("Right: %d\n", right);
}
void examplePostfixIncrement() {
int a[] = { 1, 2, 3, 4, 5 };
int n = sizeof(a) / sizeof(a[0]);
int left = 0, right = 0, sum = a[0];
while (right < n - 1 && sum < 10) {
sum += a[right++];
}
printf("Postfix Increment:\n");
printf("Sum: %d\n", sum);
printf("Right: %d\n", right);
}
int main() {
examplePrefixIncrement();
examplePostfixIncrement();
return 0;
}
//结果如下
Prefix Increment:
Sum: 10
Right: 3
Postfix Increment:
Sum: 11
Right: 4
```c
int minSubArrayLen(int target, int* nums, int numsSize)
{
int left=0,right=0;
int min=numsSize+1; //特别注意
int sum=nums[0];
while(1)
{
while(right<numsSize-1 && sum<target)
{
sum+=nums[++right];
}
if(sum<target) break;
int len=right-left+1;
if(len<min) min=len;
sum-=nums[left++];
}
if(min==numsSize+1) min=0;
return min;
}
6、子集生成
四、字符串模式匹配
1、暴力算法
int ForceMatch(char*s,char*p)
{
int len1=strlen(s);
int len2=strlen(p);
int i=0;
while(i<=len1-len2) //当i>len1-len2时注定了字串与母串不匹配
{
int j=0;
while(j<len2 && s[i]==p[j])
{
i++;
j++;
}
if(j==m) return i-m;
else i=i-j+1;
}
return -1;
}
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
int strStr(char * haystack, char * needle)
{
int i=0,j=0;
int len1=strlen(haystack);
int len2=strlen(needle);
while(i<len1 && j<len2)
{
if(haystack[i]==needle[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j==len2)
{
return i-len2;
}
else return -1;
}
```c
#include<stdio.h>
#include<string.h>
void forceMatch(char* master, char* sub, int len1, int len2)
{
int i = 0, j = 0;
while (i < len1 && j < len2)
{
if (master[i] == sub[j])
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
if (j == len2) printf("match successful\n");
else printf("match false\n");
}
void printString(char* master, char* sub, int len1, int len2)
{
for (int i = 0; i < len1; i++)
{
printf("%c ", master[i]);
}
printf("\n");
for (int i = 0; i < len2; i++)
{
printf("%c ", sub[i]);
}
printf("\n");
}
int main()
{
char* master = "hello";
char* sub = "llo";
int len1 = strlen(master);
int len2 = strlen(sub);
forceMatch(master, sub, len1, len2);
printString(master, sub, len1, len2);
return 0;
}
暴力匹配时间复杂度
2、KMP算法匹配
前缀：包含首字母不包含尾字母的所有字串
后缀：包含为字母不包含首字母的所有字串
最长公共前后缀：前缀和后缀相同的最大长度
字符串 前缀 后缀 最长公共相等前后缀 next数组01 next数组02(右移) next数组03(全减1) 前缀表
a 无 无 无 0 -1 无
aa a a a 1 0
aab a/a/aa a/b/ab 无 1 -1
aaba a/a/b/aa/ab/aab a/b/a/ab/ba/aba a 1 0
a a b a a f
定义next数组的思路：
next数组实际上的意义就是代表了回退的位置
next01: 0 1 0 1 2 0
主串与子串发生不匹配时看前一个next数组的值为多少，子串第一个字符就跳到相应的下标位置
next02:-1 0 1 0 1 2 整体右移一个单位，next[0]变为-1
主串与子串发生不匹配时看当前next数组的值为多少，子串的第一个字符就跳到相应的下标位置
next03:-1 0 -1 0 1 -1 整体减1
主串与子串发生不匹配时看前一个next数组的值为多少，子串第一个字符就跳到n(ext数组值＋1)对应的下标位置
定义next数组中双指针i:后缀末尾 j:前缀末尾，还代表了i(包括i)之前的最大公共前后缀的长度
1、初始化
2、处理前后缀不相同情况：进行匹配时当下标j对应的字符跟i对应的字符不相同时，j就回退到前一位next数组对应的值>他的初始条件
(特别注意：1、j要eg:next01 j>0 2、这是一个连续回退的过程所以应该用一个循环)
3、处理前后缀相同的情况：j应改加1(因为j还代表着i之前(包括i)的最大公共前后缀的位置)
4、更新next数组的值：此时i位置next数组的值就等于j，然后i自然的向后走一位(i在for循环中)
进行KMP匹配的思路：
1、初始化：初始化双指针 循环大前提是i<len1
2、当主串与子串从头开始就一一对应时：主串，子串相匹配，return
3、如果主串与子串从开头就不匹配：指针i往后移一位，然后继续匹配
4、主串与子串在其他位置不匹配，那么指针j就跳转到他的前一个next数组元素数值所对应的下标位置
```c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void creatNext(char* sub, int len2,int* next)
{
int j = 0;
next[0] = 0;
for (int i = 1; i < len2; i++)
{
while (j > 0 && sub[j] != sub[i])
{
j = next[j - 1];
}
if (sub[i] == sub[j])
{
j++;
next[i] = j;
}
}
}
void KMPmatch(char* master, char* sub, int* next, int len1, int len2)
{
int i = 0, j = 0;
while (i < len1)
{
if (master[i] == sub[j])
{
i++;
j++;
if (j == len2)
{
printf("match successful\n");
return; //return语句的作用是提前终止函数的执行，并将控制权返回给调用者，而不会返回任何值。
}
}
else
{
if (j == 0) i++;
else j = next[j - 1];
}
}
printf("match false\n");
}
int main()
{
char* master = "aabaabaaf";
char* sub = "aabaaf";
int len1 = strlen(master);
int len2 = strlen(sub);
int* next = (int*)malloc(sizeof(int) * len2);
creatNext(sub, len2, next);
KMPmatch(master,sub,next,len1,len2);
free(next);
return 0;
}
公共前后缀：abca
下面的KMP算法中：next数组是next 02
3、KMP算法的隐藏应用举例
1、回文串
2、循环节
4、KMP算法的改进
next数组的改进：最长相等前后缀后面两个字符不能相等
5、小结
五、树和二叉树的定义和性质
1、树的定义
1、树、子树、根
2、有序树
3、树与线性结构的比较
4、树的相关用语
2、二叉树的定义
1、满二叉树
2、完全二叉树
除了最下面一层，其他层都是满的
叶结点个数 =384 表示对n/2 进行向上取整（向上取整是指不小于n/2的最大整数）
表示对 log2n 进行向下取整（向下取整是指不大于 log2n 的最大整数）
3、二叉树的性质
1、二叉树的第i层中最多有$2^i$个结点(i$>=$0)
2、高度为k的二叉树最少有k+1个结点(k>=1)
含有k个结点的二叉树高度最多为k-1(k>=1)
3、高度为k的二叉树最多有$2^(k+1)$-1个结点
$20$+$21$+$22$+…..+$2k$=$2^(k+1)-1$
4、在由n个结点的二叉树中，若叶节点的个数为n0个，则度为2的结点个数为：n2=n0-1
六、二叉树的存储与操作
1、二叉树的存储结构
二叉树的顺序存储非常适合完全二叉树 二叉树的连接存储适合非完全二叉树
1、二叉树的顺序存储
二叉树的顺序存储是指将二叉树的结点存放在一块地址连续的内存空间中，同时反映出二叉树中结点之间的逻辑关系
2、二叉数的链接存储
非完全二叉树的顺序存储无法表达父子结点之间的逻辑关系
二叉链表的创建(一级指针)
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
TreeNode* creatTree(TreeNode* T)
{
int val = 0;
scanf_s("%d ", &val);
if (val == -1) T = NULL;
else
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
T = node;
T->left=creatTree(T->left);
T->right=creatTree(T->right);
}
return T;
}
void preorder(TreeNode* T)
{
if (!T) return;
printf("%d ", T->val);
preorder(T->left);
preorder(T->right);
}
int main()
{
TreeNode* T = NULL;
T=creatTree(T);
preorder(T);
return 0;
}
二叉树的创建(二级指针)
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
void creatTree(TreeNode** T)
{
int val = 0;
scanf_s("%d ", &val);
if (val == -1) *T = NULL; //*T就代表了结点的地址
else
{
*T = (TreeNode*)malloc(sizeof(TreeNode));
(*T)->val = val;
creatTree(& ((*T)->left));
creatTree(& ((*T)->right));
}
}
void preorder(TreeNode* T)
{
if (!T) return;
printf("%d ", T->val);
preorder(T->left);
preorder(T->right);
}
int main()
{
TreeNode* T = NULL;
creatTree(&T);
preorder(T);
return 0;
}
2、二叉树遍历及递归算法
二叉树的遍历：按照一定的次序访问二叉树的所有结点，并且每个结点仅被访问一次的过程
二叉树为空时，什么都不做，否则分为三步
下列三种遍历二叉树的方法：
1、先根(先序/前序)遍历：(1) 先访问根节点 (2) 先根遍历左子树 (3) 先根遍历右子树
2、中根遍历 (1) 中跟遍历左子树 (2) 访问根节点 (3) 中跟遍历右子树
3、后根遍历 (1) 后根遍历左子树 (2) 后根遍历右子树 (3) 访问根节点
分别得到先根、、中根、后根序列
1、先根遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void preorder(struct TreeNode* root,int* arr,int* returnSize)
{
if(root==NULL) return;
arr[(*returnSize)++]=root->val;
preorder(root->left,arr,returnSize);
preorder(root->right,arr,returnSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
int* arr=(int*)malloc(sizeof(int)*1000);
*returnSize =0;
preorder(root,arr,returnSize);
return arr;
}
2、中根遍历
94. Binary Tree Inorder Traversal - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void inorder(struct TreeNode* root,int* arr,int* returnSize)
{
if(root==NULL) return;
inorder(root->left,arr,returnSize);
arr[(*returnSize)++]=root->val;
inorder(root->right,arr,returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int* arr=(int*)malloc(sizeof(int)*1000);
*returnSize=0;
inorder(root,arr,returnSize);
return arr;
}
3、后根遍历
145. Binary Tree Postorder Traversal - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void postorder(struct TreeNode* root,int* arr,int* returnSize)
{
if(root==NULL) return;
postorder(root->left,arr,returnSize);
postorder(root->right,arr,returnSize);
arr[(*returnSize)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
int* arr=(int*)malloc(sizeof(int)*1000);
*returnSize=0;
postorder(root,arr,returnSize);
return arr;
}
先根序列：A B C D E F G H
中根序列：C B E D F A G H
后根序列：C E F D B H G A
3、遍历的非递归算法
研究二叉树遍历非递归算法的原因：
1、当二叉树很高时，递归算法可能因为递归深度过深而导致系统栈溢出。如果递归深度过深(即递归调用次数过多)，系统栈的内存空间可能会被耗尽，因为每一次递归调用，都会占用一定的栈空间，而系统栈空间是有限的。
2、有利于更深刻理解二叉数的遍历过程
1、非递归先根遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int* arr=(int*)malloc(sizeof(int)*2000);
*returnSize=0;
if(root==NULL) return arr;
struct TreeNode* stack[2000]; //指针数组用来模拟栈结构
struct TreeNode* p=root; //用一个指针来指向根节点，并向下进行
int stacktop=0; //初始化栈顶
while(stacktop > 0 || p!=NULL )
{
while(p!=NULL)
{
arr[(*returnSize)++]=p->val; //此处数组赋值
stack[stacktop++]=p; /*stacktop++如果stack==1,那么stack[stacktop++]=stacktop[1]
过了这步之后stacktop=2*/
p=p->left; //遍历左子数的结点
}
p=stack[--stacktop]; //回溯到上一级的父节点
p=p->right; //遍历上一级父节点的右子树
}
return arr;
}
2、非递归中根遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int* arr=(int*)malloc(sizeof(int)*200);
*returnSize=0;
if(root==NULL) return arr;
struct TreeNode* stack[200];
struct TreeNode* p=root;
int stacktop=0;
while(stacktop>0 || p!=NULL)
{
while(p!=NULL)
{
stack[stacktop++]=p;
p=p->left;
}
p=stack[--stacktop];
arr[(*returnSize)++]=p->val; //此处数组赋值
p=p->right;
}
return arr;
}
3、非递归后根算法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
int*arr=(int*)malloc(sizeof(int)*2000);
*returnSize=0;
if(root==NULL) return arr;
struct TreeNode *stack[2000];
struct TreeNode* p=root;
struct TreeNode* prev=NULL;
int stacktop=0;
while(stacktop>0 || p!=NULL)
{
while(p!=NULL)
{
stack[stacktop++]=p; //特别注意入栈的是整个结点而不仅仅就是一个节点的数值域
p=p->left;
}
p=stack[--stacktop];
if(p->right==NULL || p->right==prev)
{
arr[(*returnSize)++]=p->val;
prev=p;
p=NULL;
}
else
{
stack[stacktop++]=p;
p=p->right;
}
}
return arr;
}
```c
if(p->right==NULL || p->right==prev)
{
arr[(*returnSize)++]=p->val;
prev=p;
p=NULL;
}
else
{
stack[stacktop++]=p;
p=p->right;
}
下面是对这段代码逐步解释以及相关原因的说明：
1、首先，代码检查当前节点 root 的右子树是否为空或者已经被访问过（即右子树是上一个访问的节点）：
如果右子树为空或者已经被访问过，说明当前节点可以被访问。
如果右子树不为空且没有被访问过，说明当前节点的右子树还未遍历，需要先处理右子树。
2、如果右子树为空或者已经被访问过，执行以下操作：
将当前节点的值 root->val 存入结果数组 res，并更新 *returnSize 表示结果数组的大小增加了一个元素。
将 prev 更新为当前节点 root，记录当前节点已经被访问。
将 root 置为 NULL，为下一轮循环准备。
3、如果右子树不为空且没有被访问过，执行以下操作：
将当前节点入栈，以便在处理完右子树后回到当前节点。
将 root 更新为当前节点的右子树，进入下一轮循环处理右子树。
4、层次遍历
int*LevelOrder(TreeNode*root,int* returnSize){
int* arr=(int*)malloc(sizeof(int)*200);
*returnSize=0;
if(root==NULL) return arr;
TreeNode*Q[200];
int front=0,rear=0;
Q[front++]=root;;
while(front!=rear){
TreeNode*p=Q[rear++];
arr[*returnSize++]=p;
if(root->left!=NULL) Q[front++]=root->left;
if(root->right!=NULL) Q[front++]=roo t->right;
}
}
最大个数为叶节点的和
n/2向上取整
错了，这只是一个二叉树
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
typedef struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
TreeNode* creatTreeNode(TreeNode* t) {
int data;
scanf_s("%d ", &data);
if (data == 0) t = NULL;
else {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = data;
t = node;
t->left = creatTreeNode(t);
t->right = creatTreeNode(t);
}
return t;
}
int leafineachLevel(TreeNode* t, int* leafnum, int* level) {
TreeNode* Q[MAXN];
int front = 0;
int rear = 0;
if (t == NULL) return;
Q[front++] = t;
Q[front++] = NULL;
while (front != rear) {
TreeNode* p=Q[rear++];
if (p == NULL) {
(*level)++;
if(front != rear) Q[front++] = NULL;
}
else {
if (p->left == NULL && p->right == NULL) leafnum[*level]++;
if (p->left != NULL) Q[front++] = p->left;
if (p->right != NULL) Q[front++] = p->right;
}
}
return *level - 1;
}
int main() {
TreeNode* t = NULL;
t = creatTreeNode(t);
int level = 0;
int leafnum[MAXN] = {0};
int head = leafineachLevel(t, leafnum, &level);
printf("\n");
for (int i = 0; i < level; i++) {
printf("%d ", leafnum[i]);
}
printf("\n");
printf("树的高度:%d", head);
return 0;
}
4、二叉树的重建和计数
1、二叉树的重建
E
1、由后根序列和中根序列可以确定一棵二叉树
由中根序列和先根序列可以确定一棵二叉树
由先根序列和后根序列不能确定一棵二叉树
2、由层次遍历不能确定一棵二叉树
3、由先根序列和层次遍历不能确定一棵二叉树
由后根序列和层次遍历不能确定一棵二叉树
由中根序列和层次遍历可以确定一棵二叉树
4、由先根序列和后根序列不能确定层次遍历
5、由任一种都能确定完全二叉树
每多一个度为1的结点，二叉树结构翻倍
2、二叉树的计数
考点：二叉树的重建(先序，中序)
3、二叉树的其他操作
1、在二叉树中搜索给定结点的父结点
2、搜索二叉树中符合数据域条件的结点
3、释放二叉树
4、在以t为根的二叉树中删除p指向的子树
5、复制二叉树
6、计算二叉树结点个数
7、创建二叉树
8、计算二叉树高度
9、二叉树中、先、后序列的首末结点(不用递归、不用栈)
10、二叉树的路径
七、线索二叉树
1、动机和基本概念
中根序列中，结点的前驱称为中根前驱，节点的后继称为中根的后继
2、中序线索二叉树的基本操作
1、寻找中序线索二叉树结点
1、找中根序列的首结点：firstInOrder
2、找中根序列的尾结点：lastInOrder
3、找中根序列的前驱结点：preInOrder
4、找中根序列的后继结点：nextInOrder
2、中根线索二叉树的遍历
3、二叉树的中序线索化
3、实现方案
4、关于先序、后序线索二叉树
八、树的存储和操作
1、树与二叉树的转换
1、树转换成二叉树
2、森林转换成二叉树
3、二叉树转换成树
4、二叉树转换成森林
2、树的存储结构
1、层次顺序+父节点下标
2、层次顺序+子节点下标
3、树的遍序列＋结点度序列
1、树没有中根遍历
2、如果已知一个树的先根序列和每个结点的度，则能唯一确定该树的结构
3、如果已知一个树的层次序列和每个结点的度，则能唯一确定该树的结构
4、father链表链接结构
5、child链表链接结构
6、father、child链表链接结构
7、左孩子-右兄弟链表链接结构
3、树和森林的遍历
树的左孩子——右兄弟链接存储上的主要操作
1、遍历
2、搜索父节点
3、搜索指定数据域的结点
4、删除以给定结点为根的子树
1、树和森林的先、后序遍历
void preOrder(TreeNode*t){
if(t==NULL) return;
visit(t->data);
TreeNode*p=t->firstChild;
while(p!=NULL){
preOrder(p);
p=p->nextBrother;
}
}
2、搜索父结点
TreeNode*findFather(TreeNode*t,TreeNode*p){
if(t==NULL || p==NULL || p==t) return NULL;
for(TreeNode*child=t->firstChild,child,child=chile-nextBrother){
if(child==p) return t;
TreeNode* ans=findFather(child,p);
if(ans!=NULL) return ans;
}
return NULL;
}
3、搜索指定数据域的结点
TreeNode*findTarget(TreeNode* t,int target){
if(t==NULL) return NULL;
if(t->data=targrt) return t;
for(TreeNode* p=t->firstChild; p; p=p->nextBrother){
TreeNode* ans=findTarget(p,target);
if(ans!=NULL) return ans;
}
return NULL;
}
4、释放以p为根的子树
void Del(TreeNode* p){
if(p==NULL) return;
TreeNode* child=p->firstChild;
while(child){
TreeNode*next=child;
Del(child);
child=next;
}
free(p);
}
5、在以t为根的树中删除以p为根的子树
6、树和森林的层次遍历
九、树和二叉树的应用
1、压缩与哈夫曼树
1、信息编码与扩充二叉树
2、Huffman算法基本思想
3、Huffman算法实现
Huffman结点的创建
Huffman算法的具体实现过程(注意for循环的条件是小于n-1)
HuffmanNode* creatHuffmantree(Huffman* H[],int n){
for(int i=0;i<n-1;i++){
//未完待续
}
}
权值最小的两个数组元素的权值相加
HuffmanNode*creatHuffmantree(HuffmanNode* H[],int n){
for(int i=0;i<n-1;i++){
HuffmanNode* t=(HuffmanNode*)malloc(sizeof(HuffmanNode));
t->weight=H[i]->weight+H[i+1]->weight;
t->data=' ';
t->left=H[i];
t->right=H[i+1];
//未完待续
}
}
权值较小的数组元素左移
HuffmanNode* creatHuffmantree(HuffmanNode* H[],int n){
for(int i=0;i<n-1;i++){
HuffmanNode* t=(HuffmanNode*)malloc(sizeof(HuffmanNode));
t->weight=H[i]->weight+H[i+1]->weight;
t->data=' ';
t->left=H[i];
t->right=H[i+1];
int j=i+2;
while(j<n && j->weight<t->weight){
H[j-1]=H[j];
j++;
}
//未完待续
}
}
数组按照权值升序排列
HuffmanNode* creatHuffmantree(HuffmanNode* H[],int n){
for(int i=0;i<n-1;i++){
HuffmanNode* t=(HuffmanNode*)malloc(sizeof(HuffmanNode));
t->weight=H[i]->weight+H[i+1]->weight;
t->data=' ';
t->left=H[i];
t->right=H[i+1];
//把新结点插入到数组H中，使得数组H按照权值升序排列
int j=i+2;
while(j<n && H[j]->weight<t->weight){
H[j-1]=H[j];
j++;
}
H[j-1]=t; //j-1是因为j++在最后一次多加了个1
}
return H[n-1]; //最终返回
}
4、Huffman算法的正确性
5、求WPL
1、计算WPL(编码总长度/加权路径长度)的方法二(对应的是Huffman树)： 每次把最小的两个权值累加起来
Huffman树构造的过程中求WPL
int WPL=0; //全局变量
HuffmanNode* creatHuffmantree(HuffmanNode* H[],int n){
for(int i=0;i<n-1;i++){
HuffmanNode* t=(HuffmanNode*)malloc(sizeof(HuffmanNode));
t->weight=H[i]->weight+H[i+1]->weight;
WPL+=t->weight; //把每次找到的两个最小权值累加起来
t->data=' ';
t->left=H[i];
t->right=H[i+1];
int j=i+2;
while(j<n && j->weight<t->weight){
H[j-1]=H[j];
j++;
}
H[j-1]=t;
}
return H[n-1];
}
无需建树即可求WPL
int sumWPL(int* weight,int n){
sort(weight,n); //对weight数组按权递增排序，需要预先实现
int WPL=0;
for(int i=0;i<n-1;i++){
int t=weight[i]+weight[i+1];
WPL+=t;
int j=i+2;
while(j<n && weight[j]<t){
weight[j-1]=weight[j];
j++;
}
weight[j-1]=t;
}
return WPL;
}
2、计算WPL(加权路径长度/编码总长度)的方法一(对应的是二叉树)：（每个结点对应的权值 * 对应的深度）之和
int WPL=0; //全局变量
void WPLpreOrder(TreeNode* t,int k){
if(t==NULL) return;
if(t->left==NULL && t->right==NULL){
WPL+=t->weight*k; //k为当前递归深度
WPLpreOrder(t->left,k+1);
WPLpreOrder(t->right,k+1);
}
}
6、Huffman算法-贪心算法
7、解码
2、表达式树
1、构造表达式树
peek函数求的是栈顶元素
#define MAXN 100
TreeNode* buildExptree(char* s,int n){
TreeNode* stack[MAXN];
int top=0;
for(int i=0;i<n;i++){
TreeNode* p=(TreeNode*)malloc(sizeof(TreeNode));
p->data=s[i];
if(s[i]>='a' && s[i]<='z'){
p->left=NULL;
p->right=NULL;
}
else{
p->right=stack[--top];
p->left=stack[--top];
}
stack[top++]=p;
}
return stack[--top]; //返回栈顶(--top是因为top++最终多加了一个1)
}
2、计算表达式二叉树对应的值
其中 return t->data-‘0’目的是：将字符形式的操作数转换为对应的整数值
在ASCII编码中，数字字符的值与其对应的整数值之间存在一个偏移量。例如，字符 '0' 的ASCII值为 48，而字符 '1' 的ASCII值为 49，以此类推。因此，通过将字符 '0' 的ASCII值减去 '0' 的ASCII值，可以得到对应的整数值。
例如，如果 t->data 的值为字符 '5'，那么 t->data - '0' 的结果将为整数 5。
int Calc(TreeNode* t){
if(t->left==NULL && t->right==NULL) return t->data-'0';
int ch1=Calc(t->left);
int ch2=Calc(t->right);
char op=t->data;
switch(op){
case'+':
return ch1+ch2;
case'-':
return ch1-ch2;
case'*':
return ch1*ch2;
case'/':
return ch1/ch2;
default:
break;
}
// 处理未知的运算符或其他错误情况
// 可以抛出异常、返回特定值或进行其他错误处理
return 0; // 默认返回0，可以根据实际需求进行修改
}
3、并查集
求交集、求并集、判断一个元素属于哪个集合
1、并查集实现算法基本思想(树的父指针)
2、并查集三大步的实现
//make_Set:为x所代表的结点元素生成一棵单节点的树
//x代表的是结点的编号
void make_Set(int x){
father[x]==0;
}
//find:查找元素x所在树的根结点
int find(int x){
if(father[x]==0) return x;
return find(father[x]);
}
//合并x和y的树
void union(int x,int y){
//y所在树的根结点指向x所在树的根结点
father[find(y)]=find(x);
}
原始的并查集算法存在的问题：算法时间复杂度取决于树的高度
3、并查集的优化1-路径压缩
int find(int x){
if(father[x]==0) return x; //x是根
//递归查找根节点同时路径压缩
father[x]=find(father[x]);//路径压缩
return father[x];//更新每个结点的父指针使其指向根节点
}
优化不能按高度合并原因：树增高时可以更新树高，但是树高减小时难以更新树高
4、并查集的优化2-按秩合并
/*秩"（Rank）是并查集中用于优化的一个概念，它通常与"路径压缩"一起使用。秩是指树的高度的一个上界，但不一定等于树的实际高度。秩的作用是在执行"合并"操作时，将较小的树合并到较大的树中，从而保持树的平衡，避免树变得过深。
初始时，每个节点的秩通常设为0或1。当进行合并操作时，如果两个树的秩相同，可以将其中一个树的根节点作为另一个树的子节点，并将后者的秩增加1。如果两个树的秩不同，则将秩较小的树合并到秩较大的树中，并不需要增加秩。
通过优化秩的分配和合并过程，可以减少树的高度，从而提高并查集操作的效率。
需要注意的是，并查集中的秩并不是绝对准确的高度值，而是一种用于指导合并操作的启发式信息。在实际实现中，对秩的更新策略可以有所差异，例如可以采用按秩合并（Union by Rank）或按秩合并加路径压缩（Union by Rank with Path Compression）等优化策略。
5、并查集算法的最终优化版本
第一种初始化方式：初始化时是将所有的结点的父节点先初始化为0
void make_Set(int x){
father[x]=0; //根结点的秩为0（实际上x为根时,father[x]为秩的相反数）
}
int find(int x){
if(father[x]<=0) return x;//x是根
father[x]=find(father[x]); //路径压缩
return father[x]; //更新各结点父指针使其指向根结点
}
void union(int x,int y){
int fx=find(x);//找到元素x所在的根节点
int fy=find(y);//找到元素y所在的根节点
if(fx==fy) return;//x和y在同一棵树
if(father[fx]<father[fy]{ //x的秩大于y的秩(存的是秩的相反数实际上是rank[fx]>rank[fy] )
father[fy]=fx; //fx作为fy的父结点
}
else{
father[fx]=fy; //fy作为fx的父节点
if(father[fx]==father[fy]){
father[fy]--; //fy的秩加1
}
}
}
第二种初始化方式：初始化时将所有结点的父节点设为自身
void make_Set(int x){
father[x]=x;
}
int find(int x){
if(father[x]==x) return x;
father[x]=find(father[x]);
return father[x];
}
void union(int x,int y){
int fx=find(x);
int fy=find(y);
if(father[fx]==father[fy]) return;
if(father[fy]<father[fy]){
father[fy]=fx;
}
else{
father[fx]=fy;
if(father[fy]==father[fx]){
father[fy]--;
}
}
}
6、并查集的应用-等价性问题
优化前方法的思路
//优化前每增加一个结点，秩就加一
初始状态：
1: father[1] = 1, rank[1] = 0
2: father[2] = 2, rank[2] = 0
3: father[3] = 3, rank[3] = 0
4: father[4] = 4, rank[4] = 0
5: father[5] = 5, rank[5] = 0
6: father[6] = 6, rank[6] = 0
7: father[7] = 7, rank[7] = 0
8: father[8] = 8, rank[8] = 0
//逐个合并给定的关系，更新集合的秩
合并 1 和 2：
father[1] = 2, rank[2] = 1 （因为根节点2的秩大于根节点1的秩）
合并 1 和 5：
father[5] = 2, rank[2] = 2 （因为根节点2的秩大于根节点5的秩）
合并 5 和 6：
father[6] = 2, rank[2] = 3 （因为根节点2的秩大于根节点6的秩）
合并 3 和 7：
father[7] = 3, rank[3] = 1 （因为根节点3的秩大于根节点7的秩）
合并 6 和 8：
father[8] = 2, rank[2] = 4 （因为根节点2的秩大于根节点8的秩）
//最终状态
最终状态：
1: father[1] = 2, rank[2] = 4
2: father[2] = 2, rank[2] = 4
3: father[3] = 3, rank[3] = 1
4: father[4] = 4, rank[4] = 0
5: father[5] = 2, rank[2] = 4
6: father[6] = 2, rank[2] = 4
7: father[7] = 3, rank[3] = 1
8: father[8] = 2, rank[2] = 4
优化后的方法的思路
//优化后的状态（每个结点的父指针指向根，秩最大为1）
初始状态：
1: father[1] = 1, rank[1] = 0
2: father[2] = 2, rank[2] = 0
3: father[3] = 3, rank[3] = 0
4: father[4] = 4, rank[4] = 0
5: father[5] = 5, rank[5] = 0
6: father[6] = 6, rank[6] = 0
7: father[7] = 7, rank[7] = 0
8: father[8] = 8, rank[8] = 0
//逐个合并给定的关系，更新集合的秩
合并 1 和 2：
father[1] = 2, rank[2] = 1 （因为根节点2的秩大于根节点1的秩）
合并 1 和 5：
father[5] = 2, rank[2] = 1 （因为根节点2的秩大于根节点5的秩）
合并 5 和 6：
father[6] = 2, rank[2] = 1 （因为根节点2的秩大于根节点6的秩）
合并 3 和 7：
father[7] = 3, rank[3] = 1 （因为根节点3的秩大于根节点7的秩）
合并 6 和 8：
father[8] = 2, rank[2] = 1 （因为根节点2的秩大于根节点8的秩）
//最终状态
最终状态：
1: father[1] = 2, rank[2] = 1
2: father[2] = 2, rank[2] = 1
3: father[3] = 3, rank[3] = 1
4: father[4] = 4, rank[4] = 0
5: father[5] = 2, rank[2] = 1
6: father[6] = 2, rank[2] = 1
7: father[7] = 3, rank[3] = 1
8: father[8] = 2, rank[2] = 1
```c
void equivalenceClass(int n,int m,int q){
int x;
int y;
for(int i=1;i<=n;i++){
make_Set(i);
}
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
union(x,y);
}
for(int i=0;i<q;i++){
scanf("%d %d",&x,&y);
if(find(x)==find(y)) printf("yes\n");
else printf("no\n");
}
}
#define MAXN 100
int findprovinceCout(int C[MAXN][MAXN],int n){
for(int i=1;i<=n;i++){
make_Set(i);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(C[i][j]==1) union(i,j);
}
}
int cout=0;
for(int i=1;i<=n;i++){
if(father[i]<=0) cout++;
}
return cout;
}
#include<st
#define MAXN 100
int father[MAXN];
void init(int i){
father[i]=0;
}
int find(int x){
if(father[x]==0) return x;
father[x]=find(father[x]);
return father[x];
}
void union(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx==fy) return;
father[fx]=fy;
}
void queueUp(int n){
int x,y;
for(int i=1;i<=n;i++){ //第一步：初始化
init(i);
}
while(scanf("%d %d",&x,&y)!=EOF){ //第二步：合并（题目已规定了合并次序，不能按秩合并）
union(x,y);
}
printf("Final queue heads:\n"); //第三步 输出每位同学所在队列的排头
for(int i=1;i<=n;i++){
printf("Student %d is in queue %d\n",i,find(i));
}
}
int main(){
int n;
printf("the student nums is:");
scanf("%d",&n);
queueUp(n);
return 0;
}
```c
father[fx] = fy;
这行代码将节点x所在的集合的根节点fx的父节点设置为节点y所在集合的根节点fy。这会导致根节点的父节点值变为具体的节点索引，而不再是负数表示的集合大小。
当使用并查集数据结构时，通常我们使用一个数组来表示每个节点的父节点。初始时，每个节点都是独立的集合，因此父节点可以初始化为负数，表示集合的大小（节点数目）为1。
当两个集合进行合并时，我们需要考虑两个集合的大小，以便将较小的集合并入较大的集合，以保持根节点的父节点仍然表示集合的大小（负数）。
在你提供的代码中，`Union`函数中的行 `father[fx] = fy;` 错误地将根节点x所在的集合的父节点设置为节点y所在集合的根节点。这会导致根节点的父节点值变为具体的节点索引，而不再是负数表示的集合大小。
为了修复这个问题，我们需要根据集合的大小来决定合并的方向。具体而言，我们比较根节点所在集合的大小（负数值），将节点数较少的集合合并到节点数较多的集合。这样可以保持根节点的父节点仍然表示集合的大小。
修改后的`Union`函数如下：
void Union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) return;
if (father[fx] < father[fy]) {
father[fx] += father[fy];
father[fy] = fx;
} else {
father[fy] += father[fx];
father[fx] = fy;
}
}
这样修改后，根节点的父节点仍然表示集合的大小，而不是具体的节点索引。这样可以保持并查集数据结构的正确性，并且输出结果符合预期。
十、图的概念与存储结构
1、图的基本概念
1、邻接顶点
2、多重图和简单图和完全图
3、顶点的度与边的关系
4、图的路径
5、子图
6、连通性
连通子图的父图不一定是连通图
连通分量即为及大连通子图
强连通子图：任意两个顶点之间都可及的子图
强连通分量即为极大强连通子图
7、带权图
8、小结
2、图的存储结构
1、邻接矩阵(顺序存储)
2、邻接表
邻接表：反映的是顶点出度的情况
//邻接表创建有向图
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
typedef struct Vertex {
int vername;
struct Edge* adjacent;
} Vertex;
typedef struct Edge {
int veradj;
int weight;
struct Edge* link;
} Edge;
void initVertex(Vertex* G, int n) {
int i;
for (i = 0; i < n; i++) {
G[i].vername = i;
G[i].adjacent = NULL;
}
}
void creatEdge(Vertex* G, int a, int b, int weight) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->veradj = b;
edge->weight = weight;
edge->link = NULL;
if (G[a].adjacent == NULL) {
G[a].adjacent = edge;
}
else {
Edge* p = G[a].adjacent;
while (p->link) {
p = p->link;
}
p->link = edge;
}
}
void printGraph(Vertex* G, int n) {
int i;
for (i = 0; i < n; i++) {
Edge* p = G[i].adjacent;
if (p != NULL) {
printf("%d:", i);
while (p) {
printf("(%d,%d,%d)", i, p->veradj, p->weight);
p = p->link;
}
printf("\n");
}
}
}
int main() {
Vertex G[MAXN];
int n, e;
scanf_s("%d %d", &n, &e);
initVertex(G, n);
int i;
for (i = 0; i < e; i++) {
int a, b, c;
scanf_s("%d %d %d", &a, &b, &c);
creatEdge(G, a, b, c);
}
printGraph(G, n);
return 0;
}
#include<stdio.h>
typedef struct Vertex{
int name;
Edge* adjacent;
}Vertex;
typedef struct Edge{
int veradj;
Edge* link;
}Edge;
void getIndegree(Vertex* Head,int n,int* inDegree){
for(int i=0;i<n;i++){
inrDegree[i]=0;
}
for(int i=0;i<n;i++){
Edge* p=Head[i].adjacent;
while(p!=NULL){
int k=p->veradj;
inDegree[k]++;
p=p->link;
}
}
}
逆邻接表：反映的是顶点的入度情况
十一、图的遍历及应用
1、深度优先搜索(DFS)
void visit(int v){
printf("%d ",v);
}
void DFS(Vertex* Head,int v,int* visited){
visit(v);//访问顶点v
visited[v]=1;//表示已经访问过了
Edge* p=Head[v].adjacent;
if(p!=NULL){
int k=p->veradj;
if(visited[k]==0){
DFS(Head,k,visited);
}
else{
p=p->link;
}
}
}
1、递归算法基本思想
/*递归DFS基本步骤
1、访问源点v，并将visited置为1
2、用一个for循环来扫描每个顶点的边结点，如果没有访问过，就进行递归
2、栈算法的基本思想
在给定的算法中，步骤④中的判断是否被访问过是为了确保在从栈中弹出一个顶点后，不会重复访问该顶点。尽管在步骤③中将顶点v标记为已访问(visited[v] = 1)，但是在多次循环迭代中，可能会多次将顶点v的邻接顶点压入栈中。如果在栈顶元素弹出之后不进行判断，那么在下一次循环迭代中，又会将顶点v压入栈中，导致重复访问。
通过判断是否被访问过，可以避免重复访问已经出栈的顶点。只有当一个顶点被弹出栈后，才能确保它的邻接顶点都被访问过了，因此在下一次循环迭代中，可以跳过已经访问过的顶点，避免重复入栈。
简而言之，这个判断是为了保证在深度优先搜索算法中，每个顶点只被访问一次，避免重复访问和陷入死循环。
/*非递归算法的思路：
1、创建栈，和顶指针
2、将源点v压入栈中
3、一个while循环，条件为栈不为空
4、出栈一个元素赋给V
5、如果没有访问过这个元素，访问，并将visited置为1
6、用一个for循环来扫描每个顶点的边结点，如果没访问过，就压入栈中
2、广度优先搜索(BFS)
1、队列算法基本思想
/*BFS的基本实现过程
1、创建一个队列，和front,rear指针
2、访问v，并将visited置为1
3、源点入队
4、用一个while循环，当对列不为空时
5、出队一个元素赋给v
6、用一个for循环来扫描每个顶点的边结点
7、如果没有访问过，那么访问，将visited置为1，然后入队
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
typedef struct Vertex {
int vername;
struct Edge* adjacent;
}Vertex;
typedef struct Edge {
int veradj;
struct Edge* link;
}Edge;
void initVertex(Vertex* Head, int n) {
for (int i = 0; i < n; i++) {
Head[i].vername = i;
Head[i].adjacent = NULL;
}
}
void creatEdge(Vertex* Head, int a, int b) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->veradj = b;
edge->link = NULL;
if (Head[a].adjacent == NULL) {
Head[a].adjacent = edge;
return;
}
else {
Edge* cur = Head[a].adjacent;
if (edge->veradj < cur->veradj) {
Head[a].adjacent = edge;
edge->link = cur;
return;
}
Edge* pre = NULL;
while (cur->link) {
pre = cur;
cur = cur->link;
if (edge->veradj < cur->veradj) {
pre->link = edge;
edge->link = cur;
return;
}
}
cur->link = edge;
}
}
void visit(int v) {
printf("%d ", v);
}
void BFS(Vertex* Head, int v, int* visited) {
int Q[MAXN];
int front = 0;
int rear = 0;
visit(v);
visited[v] = 1;
Q[front++] = v;
while (front != rear) {
v = Q[rear++];
for (Edge* p = Head[v].adjacent; p; p = p->link) {
if (visited[p->veradj] == 0) {
visit(p->veradj);
visited[p->veradj] = 1;
Q[front++] = p->veradj;
}
}
}
}
int main() {
int n, e;
scanf_s("%d %d", &n, &e);
Vertex Head[MAXN];
initVertex(Head, n);
int a, b;
while (e--) {
scanf_s("%d %d", &a, &b);
creatEdge(Head, a, b);
}
int visited[MAXN];
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
for (int i = 0; i < n; i++) {
BFS(Head, i, visited);
}
return 0;
}
3、图遍历的应用
1、判断无向图是否连通以及连通分量数目思想
/*判断无向图是否连通及连通分量的数目
1、初始化一个计数变量为0
2、每遍历一个连通分量，计数器就加一
2、判断u->v是否存在路径思想
/*判断顶点u到v是否存在路径
if(visited[p->veradj]==0)
解读：在代码中，if (DFS(Head, p->VerAdj, v, visited))是一个条件语句，用于判断是否调用DFS函数进行递归搜索。
如果递归调用的DFS函数返回true，表示从顶点p->VerAdj找到了一条路径到目标顶点v，那么条件为真。此时，代码块中的逻辑将执行，可能包含一些处理路径的操作。
如果递归调用的DFS函数返回false，表示从顶点p->VerAdj无法找到目标顶点v的路径，那么条件为假。此时，代码块中的逻辑将被跳过，继续执行后续的循环或返回false。
这样，通过递归调用DFS函数，可以在遍历图的过程中动态地搜索路径，并根据返回值进行相应的处理。
if(visited[p->veradj==0]){
if(DFS(Head,p->veradj,v,visited)) return true
}
解读：在这个递归调用中，DFS函数会以顶点p->VerAdj作为新的起始顶点进行深度优先搜索，继续寻找从该顶点到目标顶点v的路径。
如果递归调用的DFS函数返回true，表示从顶点p->VerAdj找到了一条路径到目标顶点v，那么当前的DFS函数也会返回true，并立即结束执行，将结果传递给上一层的递归调用或主调函数。这样可以有效地向上回溯，并在找到路径后立即返回结果，避免不必要的遍历。
这种通过递归调用自身来深入搜索路径的方式称为深度优先搜索（DFS），它会不断地沿着一条路径进行搜索，直到搜索完所有可能的路径或找到目标路径为止。
3、判断无向图是否有环思想一
/*判断无向图是否有环思想一：prev
1、先访问顶点，将visited置为1
2、for循环遍历v的邻接顶点
3、如果visited为0，if (DFS(Head, p->VerAdj, visited, v)) return true：递归调用 DFS 函数，以顶点 p->VerAdj 作为新的起始顶点，继续寻找路径。如果返回 true，表示找到了一条路径，直接返回 true。
4、else if (p->VerAdj != pre) return true：如果顶点 p->VerAdj 已经被访问过，并且不是之前访问的结点 pre，表示找到了一个环路，直接返回 true
5、如果以上条件都不满足，则返回 false，表示从顶点 v 无法找到目标顶点的路径或环路
4、判断有向图是否有环的思想二
/*判断无向图是否有环的思想二：visited=2代表一个顶点的邻接顶点都完成遍历
1、访问源点v，并将visited置为1
2、for循环遍历v的邻接顶点，如果没有访问过，那就进入递归，进行遍历
3、如果这个顶点的所有邻接顶点都遍历过了，那就将它的visited置为2
/*代码解读
visited[v] = 1：将当前顶点 v 标记为正在访问中。
for (Edge* p = Head[v].adjacent; p != NULL; p = p->link)：遍历顶点 v 的邻接边链表，其中 p 指向当前边。
int k = p->VerAdj：获取当前边的邻接顶点 k。
if (visited[k] == 0)：如果顶点 k 尚未被访问（visited[k] == 0），则进行以下判断：
if (HasCircle(Head, k, visited) == true)：递归调用 HasCircle 函数，以顶点 k 作为新的起始顶点，继续搜索。如果返回 true，表示找到了环路，直接返回 true。
if (visited[k] == 1)：如果顶点 k 已经被标记为正在访问中（visited[k] == 1），表示在当前路径中遇到了顶点 k，即找到了环路，直接返回 true。
visited[v] = 2：将顶点 v 标记为已经访问完成。
返回 false，表示从顶点 v 出发，没有找到环路
十二、拓扑排序和关键路径
1、拓扑排序(栈实现)
解读拓扑排序
拓扑排序是一种对/*有向无环图（DAG）进行排序的算法*/。它将图中的顶点按照一种特定的顺序进行排列，使得所有的有向边都从排在前面的顶点指向排在后面的顶点。换句话说，对于任意一条有向边 (u, v)，在拓扑排序中顶点 u 总是在顶点 v 的前面。
拓扑排序的步骤如下：
1. 初始化一个空的排序结果列表。
2. /*找到图中入度为 0 的顶点，将其加入排序结果列表。*/
3. /*从图中移除该顶点以及以它为起点的所有有向边。*/
4. 重复步骤 2 和步骤 3，直到所有顶点都被加入排序结果列表。
/*如果在拓扑排序过程中不存在入度为 0 的顶点，那么图中一定存在环路，无法进行拓扑排序。*/
拓扑排序的应用广泛，特别适用于以下情况：
1. 任务调度：将任务按照依赖关系进行排序，保证每个任务在依赖的任务完成后才能执行。
2. 编译顺序：编译程序时，需要按照依赖关系将源代码文件进行排序，确保依赖的文件先编译。
3. 课程安排：对学习课程进行排序，使得先修课程在后修课程之前进行学习。
4. 项目管理：对项目中的任务进行排序，确定任务的执行顺序。
总之，拓扑排序是一种/*有向无环图的排序算法*/，它在许多实际应用中都发挥着重要的作用，特别是对于涉及依赖关系的任务和顺序安排等问题。
1、拓扑排序
/*代码解读：
1、定义一个存储每个顶点入度数量的数组，并定义一个栈，和栈顶指针
2、构造一个求每个顶点入度数目的函数
3、用一个for循环，将入度为0的顶点入栈
4、再用一个for循环进行真正的拓扑排序
5、如果栈为空，return false，代表图有环，无法进行拓扑排序
6、否则，出栈栈顶元素，赋值给变量j(可以选择打印这个元素：如果能过遍历所有元素，最终结果就是拓扑排序的结果；如果不能，代表有环)
7、遍历j元素的所有邻接顶点，将所有邻接顶点的入度减一，如果入度为0，那就入栈
8、最终循环结束后，return true，代表拓扑排序完成
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXN 100
typedef struct Vertex {
int vername;
struct Edge* adjacent;
}Vertex;
typedef struct Edge {
int veradj;
struct Edge* link;
}Edge;
void initVertex(Vertex* Head, int n) {
for (int i = 0; i < n; i++) {
Head[i].vername = i;
Head[i].adjacent = NULL;
}
}
void creatEdge(Vertex* Head, int a, int b) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->veradj = b;
edge->link = NULL;
if (Head[a].adjacent == NULL) {
Head[a].adjacent = edge;
return;
}
else{
Edge* cur = Head[a].adjacent;
if (edge->veradj < cur->veradj) {
Head[a].adjacent = edge;
edge->link = cur;
return;
}
Edge* pre = NULL;
while (cur->link) {
pre = cur;
cur = cur->link;
if (edge->veradj < cur->veradj) {
pre->link = edge;
edge->link = cur;
return;
}
}
cur->link = edge;
}
}
//统初始化并计每个顶点的入度
void getIndegree(int* indegree, int n, Vertex* Head) {
for (int i = 0; i < n; i++) {
indegree[i] = 0;
}
for (int i = 0; i < n; i++) {
for (Edge* p = Head[i].adjacent; p; p = p->link) {
indegree[p->veradj]++;
}
}
}
//判断是否能拓扑排序，如果可以就打印
bool topoOrder(Vertex* Head, int n) {
int indegree[MAXN];
getIndegree(indegree, n, Head);
int stack[MAXN];
int top = 0;
for (int i = 0; i < n; i++) {//将入度为0的顶点入栈
if (indegree[i] == 0) {
stack[top++] = i;
}
}
if (top == 0) return false;//如果栈为空，那就return false
int v = stack[--top];//出栈一个入度为0的顶点
printf("%d ", v);
for (Edge* p = Head[v].adjacent; p; p = p->link) {//将它临接顶点的入度减一，如果其入度为0，那么就进栈
indegree[p->veradj]--;
if (indegree[p->veradj == 0]) stack[top++] = p->veradj;
}
return true;
}
int main() {
int n, e;
scanf_s("%d %d", &n, &e);
Vertex Head[MAXN];
initVertex(Head, n);
int a, b;
while (e--) {
scanf_s("%d %d", &a, &b);
creatEdge(Head, a, b);
}
bool result = topoOrder(Head, n);
return 0;
}
2、逆拓扑序
/*代码主体解读
visited[v] = 1：将当前顶点 v 标记为正在访问中。
for (Edge* p = Head[v].adjacent; p != NULL; p = p->link)：遍历顶点 v 的邻接边链表，其中 p 指向当前边。
if (visited[p->VerAdj] == 0)：如果顶点 p->VerAdj 尚未被访问，则进行以下操作：
递归调用 DFS_TopoSort 函数，以顶点 p->VerAdj 作为新的起始顶点，继续深度优先搜索。
visited[v] = 2：将顶点 v 标记为已经访问完成。
printf("%d ", v)：输出已经访问完成的顶点 v，即将其加入排序结果中。
整体上，该代码通过递归的深度优先搜索方式进行拓扑排序。首先将起始顶点作为参数传入函数，然后递归地访问其邻接顶点，直到到达没有未访问邻接顶点的顶点。然后将该顶点标记为已访问完成，并将其输出，即加入拓扑排序的结果中。
需要注意的是，该代码并未返回排序结果，而是通过 printf 函数直接输出排序结果。如果需要保存排序结果，可以将结果存储到一个数组或其他数据结构中。
初始调用解读：如果有多个连通分量
这段代码的作用是遍历图中的所有顶点，对每个未访问的顶点调用 DFS_TopoSort 函数进行拓扑排序。通过这个循环，可以确保对于图中的每个连通分量都进行了拓扑排序
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
typedef struct Vertex {
int vername;
struct Edge* adjacent;
}Vertex;
typedef struct Edge {
int veradj;
struct Edge* link;
}Edge;
void initVertex(Vertex* Head, int n) {
for (int i = 0; i < n; i++) {
Head[i].vername = i;
Head[i].adjacent = NULL;
}
}
void creatEdge(Vertex* Head, int a, int b) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->veradj = b;
edge->link = NULL;
if (Head[a].adjacent == NULL) {
Head[a].adjacent = edge;
return;
}
else {
Edge* cur = Head[a].adjacent;
if (edge->veradj < cur->veradj) {
Head[a].adjacent = edge;
edge->link = cur;
return;
}
Edge* pre = NULL;
while (cur->link) {
pre = cur;
cur = cur->link;
if (edge->veradj < cur->veradj) {
pre->link = edge;
edge->link = cur;
return;
}
}
cur->link = edge;
}
}
void DFS_TopoOrder(Vertex* Head, int v, int* visited) {
visited[v] = 1;
for (Edge* p = Head[v].adjacent; p; p = p->link) {
if (visited[v] == 0) {
DFS_TopoOrder(Head, p->veradj, visited);
}
}
visited[v] = 2;//代表有环，并不一定是有向环
printf("%d ", v);
}
int main() {
int n, e;
scanf_s("%d %d", &n, &e);
Vertex Head[MAXN];
initVertex(Head, n);
int a, b;
while (e--) {
scanf_s("%d %d", &a, &b);
creatEdge(Head, a, b);
}
int visited[MAXN];
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
DFS_TopoOrder(Head, i, visited);
}
}
return 0;
}
2、关键路径
关键路径是项目管理中用于确定项目完成所需时间的概念。它是指在项目网络图中，/*连接起始节点和结束节点的最长路径*/，即项目的最长持续时间。关键路径上的活动是项目完成的关键，它们的延误会导致整个项目延误
关键路径分析的题型通常是/*给定项目网络图和每个活动的持续时间*/，/*要求计算最早开始时间、最晚开始时间、最早完成时间、最晚完成时间以及关键路径*/。题型可能涉及计算单个活动的浮动时间、整个项目的最长持续时间，或者进行资源优化和时间压缩的相关问题。
/*关键活动：e==l即为关键活动
/*求解ve时，拓扑排序；求解vl时，逆拓扑排序；
同理，求解e时，拓扑排序；求解l时，逆拓扑排序(完成顶点的时间减去到工程结束顶点的最小权值)*/
/*ve:从源点开始，一个顶点到下一个顶点的最长距离
vl:(ve(n)减去 vj 到 vn 的最长路径长度)
ei:即ai的前一个顶点的ve
li:即逆着来看，要求的li对应的后边的哪个顶点的vl-weight(li对应的a) eg:li 11=vl 9 - a11=14
```c
/*关键活动算法：
1、对AOE网进行拓扑排序，若网中有环则终止算法，按照拓扑序求出各顶点的最早发生时间ve
2、按逆拓扑序求出各顶点的最迟发生时间vl
3、根据ve和vl的值，求各活动的最早开始时间e和最迟开始时间l，若e=l，则对应活动是关键活动*/
第一步：计算各项点的最早发生时间
图中顶点已按拓扑序编号
/*最为关键的一步：
对于i的所有邻接顶点
if(ve[i]+p->cost>ve[k]){
ve[k]=ve[i]+p->cost
}
图中顶点未按拓扑序编号
/*ve初始化为0(正序)
/*没有按照拓扑排序的路径，先按照拓扑排序，创建一个数组来存放经过拓扑排序的顶点
然后关键的一步：topo[i]就对应了经过Topo排序后的i
if(ve[topo[i]]+p->cost>ve[k]){
ve[k]=ve[topo[i]]+p->cost;
}
第二步：计算各项点的最迟发生时间
图中顶点已按拓扑序编号
/*注意vl的初始化：(逆序)
如果已经进行了Topo排序，那么用一个for循环，vl初始化为vl[i]=vl[n]
/*找最迟发生时间vl：找的是比较小的那个(减去最大的p->cost)
if(vl[k]-p->cost<vl[i]){
vl[i]=vl[k]-p->cost;
}
图中顶点未按拓扑序编号
/*如果没有进行拓扑排序
初始化时，vl[i]=ve[topo[n]];
第二个for循环是从n开始到源点的
前一个顶点的vl：vl[topo[i]];
后一个顶点的vl：vl[k];
if(vl[k]-p->cost<vl[topo[i]]){
vl[topo[i]]=vl[k]-p->cost;
}
第三步：计算活动的最早和最迟开始时间
/*计算活动最早开始时间，和最迟开始时间，并求关键活动：
1、用一个for循环遍历所有的顶点，并在内部遍历所有顶点的邻接顶点
2、如果一个顶点的e(ve[i])和他的邻接顶点l(vl[k]-p->cost)相等，那么这个从i到k的活动就是关键活动
3、ve[n]即为完成工程所需要的最短时间(关键路径的长度)
总的：求关键路径和关键活动
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int m = 0;
typedef struct Vertex
{
int vername;
struct Edge* adjacent;
}Vertex;
typedef struct Edge
{
int veradj;
int cost;
struct Edge* link;
}Edge;
void initVertex(Vertex* Head, int n) {
for (int i = 0; i <= n; i++) {
Head[i].vername = i;
Head[i].adjacent = NULL;
}
}
void creatEdge(Vertex* Head, int a, int b, int c) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->veradj = b;
edge->link = NULL;
edge->cost = c;
if (Head[a].adjacent == NULL) {
Head[a].adjacent = edge;
return;
}
else {
Edge* cur = Head[a].adjacent;
if (edge->veradj < cur->veradj) {
Head[a].adjacent = edge;
edge->link = cur;
return;
}
Edge* pre = NULL;
while (cur->link) {
pre = cur;
cur = cur->link;
pre->link = edge;
edge->link = cur;
return;
}
cur->link = edge;
}
}
void getinDegree(Vertex* Head, int n, int* indegree) {
for (int i = 1; i <= n; i++) {
indegree[i] = 0;
for (Edge* p = Head[i].adjacent; p; p = p->link) {
indegree[p->veradj]++;
}
}
}
void topoOrder(Vertex* Head,int n,int* ve,int* topo) {
int indegree[MAXN];
getinDegree(Head, n, indegree);
int stack[MAXN];
int top = 0;
int q = 1;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) stack[top++] = i;
}
for (int i = 1; i <= n; i++) {//此个for循环用于计算顶点最早发生时间
if (top == 0) {
m = 1;
return;
}
int v = stack[--top];
topo[q++] = v;
for (Edge* p = Head[v].adjacent; p; p = p->link) {
int k = p->veradj;
indegree[k]--;
if (indegree[k] == 0) stack[top++] = k;
if (ve[v] + p->cost > ve[k]) ve[k] = ve[v] + p->cost;//计算最早发生时间
}
}
}
void vertexLatestTime(Vertex* Head, int n, int* ve, int* vl,int* topo) {
for (int i = n; i >= 1; i--) {
for (Edge* p = Head[topo[i]].adjacent; p; p = p->link) {
int k = p->veradj;
if (vl[k] - p->cost < vl[topo[i]]) vl[topo[i]] = vl[k] - p->cost;
}
}
}
void activityStartTime(Vertex* Head, int n, int* ve, int* vl) {
for (int i = 1; i <= n; i++) {
for (Edge* p = Head[i].adjacent; p; p = p->link) {
int k = p->veradj;
int e = ve[i];
int l = vl[k] - p->cost;
if (e == l) printf("%d->%d\n", i, k);
}
}
}
int main() {
int n, e;
scanf_s("%d %d", &n, &e);
Vertex Head[MAXN];
initVertex(Head, n);
int a, b, c;
while (e--) {
scanf_s("%d %d %d", &a, &b, &c);
creatEdge(Head, a, b, c);
}
int ve[MAXN];
for (int i = 1; i <= n; i++) {
ve[i] = 0;
}
int topo[MAXN];
topoOrder(Head,n,ve,topo);//拓扑排序＋最早发生时间
if (m == 0) {
for (int i = 1; i <= n; i++) {
printf("%d ", ve[i]);
}
}
int vl[MAXN];
for (int i = 1; i <= n; i++) {
vl[i] = ve[topo[n]];
}
vertexLatestTime(Head, n, ve, vl,topo);
activityStartTime(Head, n, ve, vl);
return 0;
}
十三、图的最短路径
1、无权图最短路径(无权图的单源最短路径问题)
1、基于BFS的无权图最短路径算法基本思路
/*基于BFS（广度优先搜索）的无权图最短路径算法用于解决无权图中从给定源点到目标顶点的最短路径问题。该算法适用于图中所有边的权重相等的情况*/
以下是基于BFS的无权图最短路径算法的基本思路：
1. 初始化距离数组dist，将源点到所有其他顶点的初始距离设置为无穷大（表示尚未确定最短路径）。
2. 初始化队列，并将源点入队。
3. 进入BFS循环，直到队列为空：
- 出队一个顶点v。
- 遍历v的所有邻居顶点u：
- 如果dist[u]仍然是无穷大，则将dist[u]更新为dist[v] + 1（因为图中边的权重相等，所以距离为边数）。
- 将顶点u入队。
4. 循环结束后，dist数组中存储的就是源点到每个顶点的最短路径长度。
注意事项：
- 在算法执行过程中，可以通过一个数组prev来记录每个顶点的前驱顶点，以便后续重构最短路径。
- 如果需要重构最短路径，可以从目标顶点开始，按照prev数组逆向回溯，直到回溯到源点，即可得到最短路径的顶点序列。
基于BFS的无权图最短路径算法的时间复杂度为O(V + E)，其中V是顶点数，E是边数。这是因为BFS遍历图的时间复杂度为O(V + E)，而在每个顶点上的操作时间复杂度为O(1)。
/*无权图最短路径(BFS的队列实现)
1、创建队列,和front，rear指针
2、初始化dist[]=INF,pre=[]=-1
3、入队源点，并将dist置为0
4、当队列不为空时，出队一个点，并对其邻接结点进行访问遍历
5、如果邻接结点没有被访问过，那么dist=dist[v]+weight，pre=v，并将这个邻接结点入队
2、Dijkstra算法(正权图的单源最短路径问题)
Dijkstra算法是一种用于解决/*单源最短路径问题的贪心算法，适用于带有非负权重的有向图或无向图*/。
Dijkstra算法适用于以下情况：
1. 单源最短路径：Dijkstra算法解决的是从/*一个固定源点到其他所有顶点的最短路径问题*/，即单源最短路径问题。
2. 带权图：Dijkstra算法适用于带有权重的图，每条边都有一个关联的非负权重值。
3. 非负权重：Dijkstra算法要求图中的边权重都是非负的。这是因为Dijkstra算法使用贪心策略，每次选择距离最短的顶点进行处理，如果存在负权边，则可能导致算法无法正常运行。
4. 有向图或无向图：Dijkstra算法既适用于有向图，也适用于无向图。对于无向图，可以将其视为双向的有向图来处理。
Dijkstra算法的基本思路是从源点开始，逐步确定源点到其他顶点的最短路径。它维护一个距离数组，记录从源点到各顶点的当前最短距离。通过不断选择距离最短的顶点，并更新与该顶点相邻的顶点的距离，直到所有顶点都被处理过。
Dijkstra算法的时间复杂度取决于具体实现方式，通常为O((V + E) log V)，其中V是顶点数，E是边数。使用优先队列（最小堆）来实现距离的更新操作可以提高算法的效率。
解决的是正权图的单元最短路径问题
1、Dijkstr算法的实现思路
findMin函数的作用找到源点u到v的最短路径距离，并返回v
/*Dijkstra算法的基本代码思路
1、需要一个dist[]初始化为INF,pre[]初始化为-1,S[]初始化为1
2、将源点的dist置为0
3、从不在S的顶点中选出dist值最小的v，如果v=-1，代表没有，不在进行下面的操作
4、v存在，将v置于S中，并遍历v的邻接顶点，如果邻接顶点不在S中，并且dist[v]+p->cost<dist[v的邻接顶点],
更新其dist为dist[v]+p->cost,和pre
2、打印最短路径
/*打印顶点s到顶点t的最短路径时利用递归
if(s==t) {printf("%d ",s); return;}
printPath(pre,s,pre[t]);
printf("%d ",t);
/*输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。
for(int i=1;i<n;i++){
if(dist[i]!=INF){
printf("%d ",dist[i]);
}
}
dist[i]=INF代表不可达
3、floyd算法(任意两点间最短路径问题)
Floyd-Warshall算法适用于/*全源最短路径问题，即在一个带权(正、负、零)有向图或者无向图中找到任意两个顶点之间的最短路径长度*/
Floyd-Warshall算法适用于以下情况：
1. 有向图：Floyd-Warshall算法适用于有向图，它可以处理带有正、负或零权重的有向图。
2. 带权图：Floyd-Warshall算法适用于带有权重的图，每条边都有一个关联的权重值。
3. 同向连通图：Floyd-Warshall算法要求图是同向连通的，即从任意一个顶点出发，可以通过一系列边到达图中的任意其他顶点。如果图不是连通的，则Floyd-Warshall算法可以分别应用于各个连通分量。
4. 边权重可正可负：Floyd-Warshall算法可以处理边权重为正数、负数或零的情况。它可以找到任意两个顶点之间的最短路径长度，包括负权环的检测。
Floyd-Warshall算法通过使用一个二维矩阵来存储任意两个顶点之间的最短路径长度。它通过动态规划的思想，逐步更新矩阵中的路径长度，直到得到所有顶点对之间的最短路径长度。
Floyd-Warshall算法的时间复杂度为O(V^3)，其中V是顶点数。由于需要计算任意两个顶点之间的最短路径，因此在顶点数较大时，算法的时间复杂度可能变得较高。
1、floyd算法的实现
/*Floyd算法分为两部分：
1、初始化
用一个二维数组D[i][j]来存放vi->vj的最短距离
path[i][j]来代表i到j的最短路径上i的下一个顶点的编号j
用两个for循环来初始化D[][]和path[][],
其中D[i][j]=G[i][j]
如果说G[i][j]!=INF && i!=j,那么path[i][j]=j; else path[i][j]=-1
2、递推构造D1~Dk
一共三个for循环嵌套，第一个for循环就是k的
如果说D[i][k]+D[k][j]<D[i][j]
则：D[i][j]=D[i][k]+D[k][j]
path[i][j]=path[i][k];
2、有向图的传递闭包
/*关注vi~vj是否可及
传递性：n阶矩阵R称为可及矩阵，若顶点vi~vj可及，则Rij=1，否则=0；
传递闭包：在图论中，传递闭包（Transitive Closure）是一个有向图的性质，指的是对于图中的每一对顶点，如果存在一条路径从顶点A到顶点B，那么在传递闭包中，顶点A到顶点B之间会存在一条直接的边
/*1、如果图为无权图
R[i][k]=G[i][k];
2、如果图为有权图
if(i!=j && G[i][j]<INF){
R[i][j]=1
}
else R[i][j]=0;
第二大步核心
R[i][j]=R[i][j] || (R[i][k] && R[k][j]);
4、满足约束的最短路径(第k短路径问题)
5、A*算法(正权图单源单目标点最短路径问题)
十四、最小支撑树及图应用
1、最小支撑树的概念
最小支撑子树中无环
2、Prim算法
/*Prime算法适用于解决最小生成树（Minimum Spanning Tree，简称MST）问题，即在一个有权无向图中找到一棵包含所有顶点且权重之和最小的树。
Prime算法适用于以下情况：
1. 无向图：Prime算法仅适用于无向图，因为最小生成树是一个无向树，只考虑边的权重，与边的方向无关。
2. 带权图：Prime算法适用于带有权重的图，每条边都有一个关联的权重值。
3. 连通图：Prime算法要求图是连通的，即从任意一个顶点出发，可以通过一系列边到达图中的任意其他顶点。
4. 正权图或非负权图：Prime算法通常用于正权图或非负权图，即图中的边权重都为正数或非负数。如果图中存在负权边，最小生成树问题则需要使用其他算法，如Kruskal算法。
Prime算法的基本思路是从一个起始顶点开始，逐步扩展生成树，每次选择与当前生成树相连的顶点中权重最小的边并添加到生成树中。通过不断扩展生成树，直到包含所有顶点为止，得到最小生成树。
Prime算法的时间复杂度为O(E log V)或O(V^2)，其中E是边数，V是顶点数。当使用优先队列（最小堆）实现时，时间复杂度为O(E log V)；当使用邻接矩阵实现时，时间复杂度为O(V^2)。*/
1、Prime算法举例
2、Prime算法实现
/*Lowcost[v]=min{weight(u,v)|uS, vV-S,}
pre[v] = u , uS.
3、Prime算法实现具体过程
4、Kruskal算法(逐边加入)
/*Kruskal算法适用于解决最小生成树（Minimum Spanning Tree，简称MST）问题，即在一个带权无向图中找到一棵包含所有顶点且权重之和最小的树。
Kruskal算法适用于以下情况：
1. 无向图：Kruskal算法适用于无向图，因为最小生成树是一个无向树，只考虑边的权重，与边的方向无关。
2. 带权图：Kruskal算法适用于带有权重的图，每条边都有一个关联的权重值。
3. 连通图：Kruskal算法要求图是连通的，即从任意一个顶点出发，可以通过一系列边到达图中的任意其他顶点。如果图不是连通的，则需要对各个连通分量分别应用Kruskal算法。
4. 正权图、负权图或零权图：Kruskal算法可以处理正权图、负权图或零权图。它根据边的权重逐步构建最小生成树，不论边的权重为正数、负数或零。
Kruskal算法的基本思路是首先将图中的所有边按照权重从小到大进行排序，然后从权重最小的边开始逐步构建最小生成树。在构建过程中，会逐步加入边，但要确保加入的边不会形成环路（保证生成树的连通性）。通过不断选择权重最小且不形成环路的边，直到加入了足够数量的边，得到最小生成树。
Kruskal算法的时间复杂度取决于边的排序和并查集的实现方式，通常为O(E log E)，其中E是边数。边的排序需要O(E log E)的时间，而并查集的操作时间复杂度为O(log V)，其中V是顶点数。因此，总体时间复杂度为O(E log E + E log V)。
/*初始时每个顶点为一个集合，当这两个顶点对应的边加入到最小支撑树中时，这两个集合(即这两个顶点)合并为一个集合
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
const int INF = 0x3f3f3f3f;
int father[MAXN];
typedef struct Edge {
int head;
int tail;
int weight;
}Edge;
void creatEdge(Edge E[], int e) {
for (int i = 0; i < e; i++) {
scanf_s("%d%d%d", &E[i].head, &E[i].tail, &E[i].weight);
}
}
void Make_set(int x) {
father[x] = 0;
}
int Find(int x) {
if (father[x] <= 0) return x;//如果x的父节点为根(father=0时)，或者x本来就是根(father<0时)
father[x] = Find(father[x]);//压缩路径
return father[x];//更新各结点父指针使其指向根结点
}
void Union(int u, int v) {
int fu = Find(u);
int fv = Find(v);
if (fu == fv) return;
if (father[fu] < father[fv]) {
father[fv] = fu;
}
else {
father[fu] = fv;
if (father[fu] == father[fv]) father[fv]--;//如果father[fu]==father[fv]，那么合并后，fv的秩增加1
}
}
void sort(Edge E[], int e) {
for (int i = 0; i < e - 1; i++) {
for (int j = 0; j < e - 1 - i; j++) {
int temp = E[j].weight;
E[j].weight = E[j + 1].weight;
E[j + 1].weight = temp;
}
}
}
int Kruskal(Edge E[], int n, int e) {
for (int i = 0; i < n; i++) {
Make_set(i);//初始化每个点为一个集合
}
sort(E, e);
int ans = 0;
int k = 0;
for (int i = 0; i < e; i++) {
int u = E[i].head;
int v = E[i].tail;
int w = E[i].weight;
if (Find(u) != Find(v)) {//边uv是最小支撑子树的一条边
k++;
ans += w;
Union(u, v);//合并集合
}
if (k == n - 1) return ans;//如果生成最小支撑子树成功，那么k==n-1;返回最小支撑子树的长度
}
return INF;
}
int main() {
Edge E[MAXN]; //这个数组是关于边的数组
int n, e;
scanf_s("%d%d", &n, &e);
creatEdge(E, e);
printf("%d", Kruskal(E, n, e));
return 0;
}
5、强连通图
/*R为可及矩阵
这段代码实现了求解图的强连通分量的算法，并返回强连通分量的个数。
函数`SCC`的参数包括：
- `G[N][N]`：表示输入的图的邻接矩阵，其中`N`表示图的最大顶点数。矩阵`G`中的元素`G[i][j]`为1表示顶点`i`到顶点`j`之间存在一条有向边，为0表示不存在边。
- `n`：表示图中顶点的个数。
- `scc[]`：用于存储每个顶点所属的强连通分量编号。
函数内部的操作步骤如下：
1. 创建一个辅助的邻接矩阵`R[N][N]`，并初始化为全0。它将被用来存储图的可及矩阵。
2. 创建一个辅助数组`visited[N]`，并初始化为全0。它用于标记顶点是否已经被放入某个强连通分量中。
3. 创建一个变量`t`，用于记录当前的强连通分量编号，初始化为0。
4. 对图进行Warshall算法处理，将可及矩阵存储在`R`中。Warshall算法用于计算图的传递闭包，即求解任意两个顶点之间是否存在路径。
5. 循环遍历图中的每个顶点`i`，如果顶点`i`尚未被放入任何强连通分量中，则执行以下操作：
a. 将当前的强连通分量编号`t`递增，并将其赋值给`scc[i]`，表示将顶点`i`放入强连通分量`t`中。
b. 将顶点`i`标记为已访问（`visited[i]`设为1）。
c. 对于顶点`i`之后的每个顶点`j`，如果顶点`j`尚未被放入任何强连通分量中且顶点`i`与`j`相互可及（即`R[i][j]`和`R[j][i]`均为1），则执行以下操作：
- 将当前的强连通分量编号`t`赋值给`scc[j]`，表示将顶点`j`放入强连通分量`t`中。
- 将顶点`j`标记为已访问（`visited[j]`设为1）。
6. 返回强连通分量的个数`t`。
总的来说，该算法通过Warshall算法求解图的可及矩阵，并利用深度优先搜索的思想，将图中相互可及的顶点划分到同一个强连通分量中，最终得到强连通分量的个数以及每个顶点所属的强连通分量编号。
```c
#include <stdio.h>
#define N 105
void Warshall(int G[N][N], int n, int R[N][N]) {
int i, j, k;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
R[i][j] = G[i][j];
}
}
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
}
}
}
}
int SCC(int G[N][N], int n, int scc[]) {
int R[N][N] = { 0 }, visited[N] = { 0 };
int i, j, t = 0;
for (i = 1; i <= n; i++) {
scc[i] = 0;
}
Warshall(G, n, R);
for (i = 1; i <= n; i++) {
if (visited[i] == 0) {
t++;
scc[i] = t;
visited[i] = 1;
for (j = i + 1; j <= n; j++) {
if (visited[j] == 0 && R[i][j] == 1 && R[j][i] == 1) { //如果j没有被访问过，并且i,j互相可及
scc[j] = t;//证明j和i在同一个连通分量中
visited[j] = 1;
}
}
}
}
return t;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, i, j;
scanf("%d", &n);
int G[N][N] = { 0 }, scc[N] = { 0 };
for (i = 1; i <= n; i++) {
int x;
do {
scanf("%d", &x);
if (x != 0) {
G[i][x] = 1;
}
} while (x != 0);
}
int result = SCC(G, n, scc);
printf("%d\n", result);
}
return 0;
}
十五、平方阶排序算法
1、排序概念
2、直接插入排序
1、直接插入算法思想核心
void insertSort(int R[],int n,int m){//从下标为m的地方开始
for(int i=m+1;i<n;i++){
int k=R[i];
int j=i-1;
while(j>=m && R[j]>k){
R[j+1]=R[j];
j--;
}
R[j+1]=k; //j+1的原因：多进行了一次j--
}
}
```c
#include<stdio.h>
#define MAXN 100
void insertionSort(int R[], int n) {
for (int i = 1; i < n; i++) {
int k = R[i];
int j = i - 1;
while (j >= 0 && R[j] > k) {
R[j + 1] = R[j];
j--;
}
R[j + 1] = k;
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
insertionSort(R, n);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
3、冒泡排序
4、直接选择排序
多个最大元素时，选择第一个最大元素(选最后一个最大元素不稳定)
void swap(int R[max],int R[i]){
int temp=R[max];
R[max]=R[i];
R[i]=temp;
}
void selectSort(int R[],int n){
for(int i=n-1;i>=0;i--){
int max=0;
for(int j=1;j<n;j++){
if(R[j]>R[max]) max=j;
}
swap(R[max],R[i]);
}
}
5、希尔排序
void shellSort(int R[],int n){
for(int d=n/2;d>0;d/=2){
for(int i=d;i<n;i++){
int k=R[i];
int j=i-d;
while(j>=0 && R[j]>k){
R[j+d]=R[j];
j-=d;
}
R[j+d]=k;
}
}
}
十六、堆排序
1、堆排序的动机
2、锦标赛排序
3、堆的概念和基本操作
1、堆的概念
堆的结构性：完全二叉树
2、堆的两个基本操作
//根的下标为0
void shiftUp(int R[],int n,int i){
while(i>0 && R[i]>R[i/2]){
swap(&R[i],&R[i/2]);
i/=2;
}
}
下沉到更大子节点的位置
//根的下标为1
void shiftDown(int R[],int n,int i){
while(i<=n/2){
int maxchd=2*i;//先定义maxchd为一个结点的左孩子
if(maxchd<n && R[maxchd]<R[maxchd+1]){//如果说i有右孩子，并且右孩子的值大于左孩子，那么maxchd=右孩子的下标
maxchd++;
}
if(R[i]>R[maxchd]) return;
swap(R[i],R[maxchd]);
i=maxchd;
}
}
3、初始建堆
4、堆排序算法(下沉)
1、堆排序算法思想核心
void shiftDown(int R[],int n,int i){
while(i<=n/2){ //如果i<=n/2进行下沉
int maxchd=2*i; //先初始化左孩子是最大的数
if(maxchd<n && R[maxchd]<R[maxchd+1]){ //如果左孩子的下标小于n，且小于右孩子
maxchd++; //那么maxchd就是右孩子
}
swap(&R[maxchd],&R[i]); //R[i]下沉
i=maxchd; //更新i的值，满足条件则继续下沉
}
}
void buildHeap(int R[],int n){
for(int i=n/2;i>=1;i--){ //初始建堆，从最后一个非叶结点开始
shiftDown(R ,n,i); //建立以i为根的堆，即下沉i
}
}
void headpSort(int R[],int n){
buildHeap(R,n);
for(int i=n;i>1;i--){ //i>1当到树只有最后一个根结点时，不再进行操作
swap(&R[i],&R[1]); //交换最后一个结点和根节点的值
shiftDown(R,i-1,1); //摘除新的最后一个结点，并下沉新的根节点的值
}
}
```c
/*堆排序算法(以大根堆为例，排序生成的数组按照从小到大排列)
1、创建大根堆
2、从最后一个叶结点开始，与第一个根结点(即值最大的根结点)进行交换，然后将去掉最后一个结点的堆进行下沉操作直至只剩一个结点(那个剩余的结点就是最小的结点，不用操作就行)*/
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void shiftDown(int R[], int n, int i) {
while (i <= n / 2) {
int maxchd = 2 * i;
if (maxchd < n && R[maxchd] < R[maxchd + 1]) maxchd++;//如果说有右孩子，并且右孩子的值大于左孩子的值，那么maxchd就是右孩子的下标
if (R[i] > R[maxchd]) return;
swap(&R[i], &R[maxchd]);
i = maxchd;
}
}
void buildHeap(int R[], int n) {
for (int i = n / 2; i >= 1; i--) {
shiftDown(R, n, i);
}
}
void heapSort(int R[], int n) {
buildHeap(R, n);//先创建大根堆
for (int i = n; i > 1; i--) {//只剩最后一个结点时，不用在进行交换
swap(&R[i], &R[1]);//再将堆中根结点与最后一个叶结点的值进行交换
shiftDown(R, i - 1, 1);//每进行交换一次根结点就要进行下沉一次，且不跟最后一个结点比较
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &R[i]);
}
heapSort(R, n);
for (int i = 1; i <= n; i++) {
printf("%d ", R[i]);
}
return 0;
}
5、堆与优先级队列
1、堆的插入(上浮)
void shiftUp(int R[],int n,int i){
while(i>1 && R[i]<R[i/2]){
swap(&R[i],&R[i/2]);
i/=2;
}
}
void insert(int R[],int* n,int x){//堆尾插入x
R[++(*n)]=x; //x放在R[n+1]处，堆元素的个数加一
shiftUp(R,n,n) //树共有n个结点，需要上浮的结点，下标为n
}
2、堆的删除(下沉)
void shiftDown(int R[],int n,int i){
while(i<=n/2){
int maxchd=2*i;
if(maxchd<n && R[maxchd]<R[maxchd]){
maxchd++;
}
if(R[i]>R[maxchd]) return;
swap(&R[i],&R[maxchd]);
i=maxchd;
}
}
int delMax(int R[],int* n){
int maxKey=R[1]; //暂存堆顶元素
R[1]=R[n--]; //堆尾移至堆顶，对元素个数减一
shiftDown(R,n,1); //新堆堆顶R[1]下沉
return maxKey;
}
/*针对插入在堆的最后一个位置
* 删除在根结点
过程：
1、创建一个原始堆
2、增加一个结点时，在原来堆的最后一个结点后面加一个结点，然后进行上浮操作
3、删除一个结点时，删除的是最后一个结点，将最后一个结点的值赋给根结点，然后进行下浮操作*/
#include<stdio.h>
#define MAXN 100
int x = 30;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void shiftUp(int R[], int n, int i) {
while (i >= 1) {
if (R[i] > R[i / 2]) swap(&R[i], &R[i / 2]);
i = i / 2;
}
}
void insertNode(int R[], int* n) {
R[++(*n)] = x;//最后一个结点后边加一个结点x，n值加一
shiftUp(R, n, n);//进行上浮操作
}
void shiftDown(int R[], int n, int i) {
while (i <= n / 2) {
int maxchd = 2 * i;
if (maxchd < n && R[maxchd] < R[maxchd+1]) maxchd++;
if (R[i] > R[maxchd]) return;
swap(&R[i], &R[maxchd]);
i = maxchd;
}
}
void deleteNode(int R[], int* n) {
R[1] = R[(*n)--];
shiftDown(R, (*n)-1, 1);//下沉新的根结点
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &R[i]);
}
insertNode(R, &n);
for (int i = 1; i <= n; i++) {
printf("%d ", R[i]);
}
printf("\n");
deleteNode(R, &n);
for (int i = 1; i <= n; i++) {
printf("%d ", R[i]);
}
return 0;
}
3、优先级队列
4、优先级队列优化Huffman算法
5、优先级队列优化Dijkstr算法
6、优先级队列优化Prim算法
7、d堆
十七、快速排序
1、快速排序算法
经过Partition操作之后数组序列为：
18 35 56 11 23 60 93 69 70 68
k L
G
1、快排核心思想
/*在给定的代码中，`R[G]` 的值与 `m` 的比较条件是在 `while` 循环的条件内进行的。当 `R[G]` 的值大于 `K` 时，循环条件不再满足，循环终止，不会进入下一轮循环。
因此，在循环终止时，`R[G]` 的值可能大于或等于 `K`，并且不再满足 `R[G] > K` 的条件。这并不影响后续的划分操作，因为在最后的交换步骤中，我们将划分点 `K` 移动到了位置 `G` 上，并且 `G` 之前的元素都小于或等于 `K`。所以，即使 `R[G]` 的值等于 `K`，也不会影响排序的正确性。
因此，在给定的代码中，我们不需要在 `while (R[G] > K)` 的条件中考虑 `R[G] >= m` 的情况，直接进行划分点的交换操作即可。
初始：L=m+1 G=n
在while(L<=G)的大前提条件下：
while(L<=n && R[L]<=K) L++; 否则L的位置不变
while(G>K) G- -; 否则G的位置不变
if(L<G) {swap(&R[L],&R[G]); L++; G- -;}
L指向56，G指向11 继续操作
最终结果：
然后再将K和R[G]进行交换
2、快排代码实现
/*快速排序算法采用分治法：
将一个数组分为两个子数组，然后再分别进行递归操作，知道不能再分了为止*/
#include<stdio.h>
#define MAXN 100
const int threshold = 16;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
int k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] <= k) L++;//要用一个while循环，因为这是一个循环查找的过程
G--;
while (R[G] > k) G--;//要用一个while循环因为这是一个循环查找的过程
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
//void insertSort(int R[], int m, int n) {
// for (int i = m + 1; i < n; i++) {
// int k = R[m];
// int j = i - 1;
// while (j >= m && R[j] > k) {
// R[j + 1] = R[j];
// j--;
// }
// R[j + 1] = k;
// }
//}
void quickSort(int R[], int m, int n) {
if (m < n) {
int j = partition(R, m, n);
quickSort(R, m, j-1);
quickSort(R, j + 1, n);
}
}
//优化快速排序算法，当数组长度小于16时，使用直接插入排序
//void quickSort(int R[], int m, int n) {
// if (n - m > threshold) {
// int j = partition(R, m, n);
// quickSort(R, m, j);
// quickSort(R, j + 1, n);
// }
// else {
// insertSort(R, m, n);
// }
//}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n-1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
```c
int partition(int R[],int m,int n){
int k=R[m];
int L=m+1;
int G=n;
while(L<=G){
while(L<=n && R[L]<=k){
L++;
}
while(R[G]>k){
G--;
}
if(L<G){
swap(&R[L],&R[G]);
L++;
G--;
}
}
swap(&R[m],&R[G]);
return G;
}
void quickSort(int R[],int m,int n){//从R[m]到R[n]
if(m<n){ //条件
int j=partition(R,m,n);
quickSort(R,m,j-1);
quickSort(R,j+1,n);
}
}
2、时间复杂度分析
1、最好情况
2、最坏情况
3、平均情况
4、时间复杂度总结
3、题型补充
1、正负数划分
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void partition(int R[], int m, int n) {
int L = m;
int G = n;
while (L < G) {
while (L <= n && R[L] < 0) L++;
while (G >= 0 && R[G] > 0) G--;
if (L < G) swap(&R[L], &R[G]);
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
partition(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
2、奇偶数划分
3、奇偶数划分变型
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void partition(int R[], int n) {
int L = 1;
int G = 0;
while (L <= n && G <= n) {
while (L <= n && R[L] % 2 == 1) L += 2;
while (G <= n && R[G] % 2 == 0) G += 2;
if (L <= n && G <= n) {
swap(&R[L], &R[G]);
L += 2;
G += 2;
}
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
partition(R, n-1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
4、优化策略
1、处理小数据时结合插入排序
const int threshold=16 //阈值，当数组长>16时，采用快排；否则采用直接排序插入
//此序列为R[1]~R[n]
void insertSort(int R[],int n,int m){
for(int i=m+1;i<=n;i++){
int k=R[i];
int j=i-1;
while(j>=m && R[j]>k){
R[j+1]=R[j];
j--;
}
R[j+1]=k; //j+1的原因：多进行了一次j--
}
}
int partition(int R[],int n,int m){
int k=R[m];
int L=m+1;
int G=n;
while(L<=G){
while(L<=n && R[L]<=k) L++;
while(R[G]>k) G--;
if(L<G){
swap(&R[L],&R[G]);
L++;
G--;
}
}
swap(&R[m],&R[G]);
return G;
}
void quickSort(int R[],int n,int m){
if(n+m-1>16){
int j=partition(R,n,m);
quickSort(R,j-1,m);
quickSort(R,n,j+1);
}
else{
insertSort(R,n,m);
}
}
2、随机选取基准元素
int partition(int R[],int n,int m){
int k=R[m]; /*替换成 int k=rand()%(n-m+1)+m
swap(&R[m],&R[k]);*/
int L=m+1;
int G=n;
while(L<=G){
while(L<=n && R[L]<=k) L++;
while(R[G]>k) G--;
if(L<G){
swap(&R[L],&R[G]);
L++;
G--;
}
}
swap(&R[m],&R[G]);
return G;
}
```c
/*rand()取随机数函数，在头文件stdlib.h中*/
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
int k = rand() % (n - m + 1) + m;//返回m~n之间一个随机数
swap(&R[m], &R[k]);//将R[k]与R[m]进行交换，之后R[k]为基准元素
k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while (R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
void quickSort(int R[], int m, int n) {
if (m < n) {
int j = partition(R, m, n);
quickSort(R, m, j - 1);
quickSort(R, j + 1, n);
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
3、三数取中选基准元素
/*选取R[m],R[(m+n)/2],R[n]中的中位元素作为基元素，保证分化不会被分到最边上
注：1、这里的n不是数组长度，而是最后一个元素的下标
2、在比较之前先将R[m+1]和R[(m+n)/2]元素交换
3、最终结果是R[m]为中位元素，R[m+1]为小,R[n]为大*/
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
swap(&R[m + 1], &R[(m + n) / 2]);
if (R[m + 1] > R[n]) swap(&R[m + 1], &R[n]);//R[n]为较大的
if (R[m] > R[n]) swap(&R[m], &R[n]);//R[m]为中位数
if (R[m + 1] > R[m]) swap(&R[m + 1], &R[m]);//R[m]为中位数
int k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while (R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
void quickSort(int R[], int m, int n) {
while (m < n) {
int j = partition(R, m, n);
quickSort(R, m, j - 1);
m = j + 1;
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
4、尾递归转化为循环
void quickSort(int R[],int m,int n){
while(m<n){
int j=partition(R,m,n);
quickSort(R,m,j-1); //先递归处理左区间
m=j+1; //再循环处理右区间
}
}
```c
/*先对左子数组进行递归操作，再利用回溯对右子数组进行循环*/
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
int k = rand() % (n - m + 1) + m;
swap(&R[m], &R[k]);
k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while(R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
void quickSort(int R[], int m, int n) {
while (m < n) {//注意这里是while循环
int j = partition(R, m, n);
quickSort(R, m, j - 1);
m = j + 1;//回溯过程中遍历右子数组
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
5、尾递归转循环
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
int k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while (R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
void quickSort(int R[], int m, int n) {
while (m < n) {
int j = partition(R, m, n);
if (j - m < n - j)//左区间短
{
quickSort(R, m, j - 1);//递归处理左区间，再循环处理右区间
m = j + 1;
}
else {
quickSort(R, j + 1, n);//递归处理右区间，在循环处理左区间
n = j - 1;
}
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
6、利用栈消除所有递归
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
/*swap(&R[m + 1], &R[(m + n) / 2]);
if (R[m + 1] > R[n]) swap(&R[m + 1], &R[n]);
if (R[m] > R[n]) swap(&R[m], &R[n]);
if (R[m + 1] > R[m]) swap(&R[m + 1], &R[m]);*/
int k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while (R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
void quickSort(int R[], int m, int n) {
int stack[MAXN][2] = {0};
int top = 0;
stack[top][0] = m;
stack[top][1] = n;
top++;
while (top) {
top--;
m = stack[top][0];//更新m，n的值为二维栈中的元素
n = stack[top][1];
int j = partition(R, m, n);
if (m < j - 1) {//在这个条件下进行左子数组的入栈
stack[top][0] = m;
stack[top][1] = j - 1;
top++;
}
if (j + 1 < n) {//在这个条件下进行右子数组的入栈
stack[top][0] = j + 1;
stack[top][1] = n;
top++;
}
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
7、侦测递归深度，适时转化为堆排序
8、三路划分(针对重复元素很多)
在给定的代码中，当 R[j] 的值为 '蓝' 时，执行了 swap(R[j], R[k]) 并且 k--。这样做的目的是将 '蓝' 移动到右边的区域，并且保持 '蓝' 区域的左侧都是 '白' 区域。
而在这个过程中，我们不需要递增 j 的值。这是因为 R[j] 的新值是从右侧交换过来的，我们需要再次检查交换过来的元素，因为它可能是 '红'、'蓝' 或 '白'。通过不递增 j 的值，我们可以在下一次循环中继续处理当前位置的元素。
/*总结一下，当 R[j] 的值为 '蓝' 时，我们将其与右侧的元素交换，并将右侧区域的指针 k 向左移动。而左侧区域的指针 i 不需要移动，因为我们需要再次检查交换过来的元素。*/
因此，在这个特定的算法中，当 R[j] 的值为 '蓝' 时，我们只需要递减 k 的值，而不需要递增 j 的值。
/*针对重复的元素很多的情况：将数组划分为三个区域，一个是小于基数R[k]，一个是等于基数R[k],一个是大于基数R[k]
在进一步递归时，对小于R[K]的左半部分数组和大于k的右半部分数组进行递归排序即可*/
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void partition3way(int R[], int m, int n, int* i, int* k) {
int j = m;
*i = m;
*k = n;
int pivot = R[m];//基准元素
while (j <= *k) {
if (R[j] < pivot) {
swap(&R[j], &R[*i]);
(*i)++;
j++;
}
else if (R[j] > pivot) {
swap(&R[j], &R[*k]);
(*k)--;
}
else {
j++;
}
}
}
void quickSort(int R[], int m, int n) {
if (m >= n) return;
int i, k;
partition3way(R, m, n, &i, &k);//i，k需传进去地址
quickSort(R, m, i - 1);//注意递归的条件
quickSort(R, k + 1, n);
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
quickSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
9、c/c++快排源码剖析，总结
10、高速缓冲器cache
5、快速选择算法(选择第k小的数)(基于快速排列)
1、递归形式
int quickselect(int R[],int m,int n,int k){
int j=partition(R,m,n);
int nL=j-m //求左半部分元素的个数
if(nL==k-1) return R[k] //如果左半部分元素的个数等于k-1，那么基准元素就是要找的第k小的数
if(nL>k-1){ //利用递归，在左半部分找第k小的元素
return quickselect(R,m,j-1,k);
}
else{
return quickselect(R,j+1,n,k-nL-1);//利用递归在右半部分找第k-nL-1的数
}
}
```c
/*基于快速排列的partition算法，将数组分为两部分
1、若左区间元素个数等于k-1，则左区间基准元素即为第k小的元素
2、若左区间元素个数大于k-1，则在左区间寻找第k小的元素
3、若左区间元素个数大于k-1，则在右区间寻找第k小的元素*/
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
int k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while (R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
int quickSelect(int R[], int m, int n, int k) {
int j = partition(R, m, n);
int nL = j - m;
if (nL == k - 1) return R[j];//由此计算长度时，计算的是第k-1个元素及之前元素的个数=k-2+1=k-1;以下递归时输入参数k时同理
else if (nL > k - 1) {
quickSelect(R, m, j - 1, k);
}
else {
quickSelect(R, j + 1, n, k - 1 - nL);
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
int k;
scanf_s("%d", &k);
printf("%d\n", quickSelect(R, 0, n - 1, k));
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
2、迭代形式
int quicSelect(int R[],int m.int n,int k){
int j,nL;
while(1){
j=partition(R,m,n);
nL=j-m; //求出左半部分元素的个数
if(nL==k-1) return R[j];
else if(nL>k-1) n=j-1;
else m=j+1,k=k-nL-1;
}
}
/*初始调用
quickSelect(R,1,n,k);
```c
#include<stdio.h>
#define MAXN 100
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int R[], int m, int n) {
int k = R[m];
int L = m;
int G = n + 1;
while (L < G) {
L++;
while (L <= n && R[L] < k) L++;
G--;
while (R[G] > k) G--;
if (L < G) swap(&R[L], &R[G]);
}
swap(&R[m], &R[G]);
return G;
}
int quickSelect(int R[], int m, int n, int k) {
while (1) {
int j = partition(R, m, n);
int nL = j - m;
if (nL == k - 1) return R[j];
else if (nL > k - 1) n = j - 1;
else {
m = j + 1;
k = k - 1 - nL;
}
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
int k;
scanf_s("%d", &k);
printf("%d\n", quickSelect(R, 0, n - 1, k));
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
3、时间复杂度分析
4、中位数的中位数算法
十八、归并排序
1、归并排序
归并算法提出者：冯 诺伊曼(现代计算机之父)
归并排序：两个相邻的有序子数组合并成一个大的有序子数组
归并排序的具体过程：
1、归并排序两个有序子数组的合并
void merge(int R[],int low,int mid,int high){
int i=low;
int j=mid+1;
int k=0;
int* X=(int*)malloc(sizeof(int)*(high-low+1));
while(i<=mid && j<=high){
if(R[i]<R[j]) X[k++]=R[i++];
else X[k++]=R[j++];
}
while(i<=mid) X[k++]=R[i++];
while(i<=high) X[k++]=R[j++];
for(int i=0;i<high-low+1;i++){
R[low+i]=X[i]; //将X拷贝回R
}
free(X);
}
2、归并排序递归形式
这是对一个没有排序的数组来说，要先递归将每个都分割为两组，再进行归并排序
void merge(int R[],int low,int mid,int high){
int i=low;
int j=mid+1;
int k=0;
int* X=(int*)malloc(sizeof(int)*(high-low+1));
while(i<=mid && j<=high){
if(R[i]<R[j]) X[k++]=R[i++];
else X[k++]=R[j++];
}
while(i<=mid) X[k++]=R[i++];
while(j<=high) X[k++]=R[j++];
for(int i=0;i<high-low+1){
R[low+i]=X[i];
}
free(X);
}
void mergeSort(int R[],int m,int n){
if(m>=n) return;
int k=(m+n)/2;
mergeSort(R,k+1,n);//右半部分进行排序
mergeSort(R,m,k); //左半部分排序;
merge(R,m,k,n);
}
```c
/*将两个有序子数组合并成一个大的数组*/
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
void merge(int R[], int low, int mid, int high) {
int i = low;
int j = mid + 1;
int* X = (int*)malloc(sizeof(int) * (high - low + 1));
int k = 0;
while (i <= mid && j <= high) {
if (R[i] <= R[j]) X[k++] = R[i++];
else X[k++] = R[j++];
}
while (i <= mid) X[k++] = R[i++];//复制拷贝余留的
while (j <= high) X[k++] = R[j++];//复制拷贝余留的
for (int i = 0; i < high - low + 1; i++) {//将X中的元素拷贝回R
R[low + i] = X[i];
}
free(X);
}
void mergeSort(int R[], int m, int n) {
if (m >= n) return;
int k = (m + n) / 2;//求中间下标位置
mergeSort(R, m, k);//从左部分递归继续将数组分为两个
mergeSort(R, k + 1, n);//从右半部分递归继续将数组分为两个部分
merge(R, m, k, n);//进行合并
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
mergeSort(R, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
3、时间复杂度
4、归并排序非递归形式
void merge(int R[],int low,int mid,int high){
int i=low;
int j=mid+1；
int k=0;
int* X=(int*)malloc(sizeof(int)*(high-low+1));
while(i<=mid && j<=high){
if(R[i]<R[j]) X[k++]=R[i++];
else X[k++]=R[j++];
}
while(i<=mid) X[k++]=R[i++];
while(j<=mid) X[k++]=R[j++];
for(int i=0;i<high-low+1){
R[low+i]=X[i];
}
free(X);
}
void mergePass(int R[],int n,int L){
int i; //i要声明在for循环外。因为下面如果数组不能平均分配，那么要处理，剩余的部分
for(i=1;i+2L-1<=n;i+=2*L){
merge(R,i,i+L-1,i+2L-1);
}
if(i+L-1<n){
merge(R,i,i+L-1,n); //L<剩余部分长度<2L,所以第二个子数组的长度到n位置
}
}
void mergeSort(int R[], int n){
for(int L=1;L<n;L*=2){//从长度为一的子数组开始合并，直到长度为n/2
mergePass(R,n,L);
}
}
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
void merge(int R[], int low, int mid, int high) {
int i = low;
int j = mid + 1;
int k = 0;
int* X = (int*)malloc(sizeof(int) * (high - low + 1));
while (i <= mid && j <= high) {
if (R[i] <= R[j]) X[k++] = R[i++];
else X[k++] = R[j++];
}
while (i <= mid) X[k++] = R[i++];
while (j <= high) X[k++] = R[j++];
for (int i = 0; i < high - low + 1; i++) {
R[low + i] = X[i];
}
free(X);
}
void mergePass(int R[], int n, int L) {
int i;
for (i = 0; i + 2 * L - 1 <= n; i += 2 * L) {
merge(R, i, i + L - 1, i + 2 * L - 1);
}
if (i + L - 1 < n) merge(R, i, i + L - 1, n);
}
void mergeSort(int R[], int n) {
for (int L = 1; L < n; L *= 2) {//注意循环条件为L=1，若L=0，则L*=2永远为0
mergePass(R, n, L);
}
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
mergeSort(R, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
5、归并算法的稳定性
6、总结
归并算法是最快的稳定性排序算法
2、归并算法的优化
数据量较大时，使用分治策略；
数据量较小时，使用直接插入；
/*对于单链表的排序，最适合的排序算法是归并排序（Merge Sort）。
归并排序的主要思想是将链表切分为两个子链表，分别对其进行排序，然后再将排序好的子链表合并成一个有序链表。相比于其他排序算法，归并排序在链表上的操作相对简单，而且时间复杂度为O(nlogn)，其中n是链表的长度。
归并排序在链表上的操作主要包括以下步骤：
1. 找到链表的中点，将链表分为两个子链表。
2. 递归地对两个子链表进行排序。
3. 合并两个已排序的子链表，得到一个有序链表。
由于归并排序是基于分治法的思想，它可以很容易地应用于链表结构，而不需要对链表进行随机访问。这使得归并排序成为对单链表进行排序的较优选择。
综上所述，归并排序是对单链表进行排序最适合的算法之一。
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
typedef struct Node {
int val;
struct Node* next;
}Node;
Node* creatList(Node* head,int n) {
int data;
while (n--) {
scanf_s("%d", &data);
Node* node = (Node*)malloc(sizeof(Node));
node->next = NULL;
node->val = data;
if (head->next == NULL) head->next = node;
else {
node->next = head->next;
head->next = node;
}
}
return head;
}
Node* merge(Node* head1, Node* head2) {
Node* dummy = (Node*)malloc(sizeof(Node));//创建一个哨兵结点
dummy->next = NULL;
Node* cur = dummy;
while (head1 && head2) {
if (head1->val <= head2->val) {
cur->next = head1;
head1 = head1->next;//更新head1的位置
}
else {
cur->next = head2;
head2 = head2->next;//跟head2的位置
}
cur = cur->next;//更新cur指针的位置
}
if (head1) {//这里用if而不用while的原因是快慢指针刚好将链表分为了两部分，很对称
cur->next = head1;
}
else if(head2) {
cur->next = head2;
}
Node* result = dummy->next;
free(dummy);
return result;
}
Node* mergeSort(Node* head) {
if (!head || !head->next) return head;
Node* slow = head;
Node* fast = head;
while (fast->next && fast->next->next) {//如果链表个数为偶数，最终slow指向中间结点靠左边的那个
slow = slow->next;
fast = fast->next->next;
}
Node* mid = slow->next;
slow->next = NULL;//将链表断开
Node* left = mergeSort(head);//左半部分链表
Node* right = mergeSort(mid);//右半部分链表
return merge(left, right);
}
void printList(Node* head) {
Node* cur = head->next;
while (cur) {
printf("%d ", cur->val);
cur = cur->next;
}
}
void freeList(Node* head) {
Node* cur = head;
while (cur) {
Node* temp = cur;
cur = cur->next;
free(temp);
}
}
int main() {
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
head->val = 0;
int n;
scanf_s("%d", &n);
head = creatList(head,n);
head->next = mergeSort(head->next);
printList(head);
freeList(head);
return 0;
}
3、归并算法的经典应用—求逆序对数目
int cnt=0;
void merge(int R[],int low,int mid,int high){
int i=low;
int j=high;
int k=0;
int* X=(int*)malloc(sizeof(int)*(high-low+1));
while(i<=mid && j<=high){
if(R[i]<=R[j]) X[k++]=R[i++];
else { X[k++]=R[j++]; cnt +=mid-i+1; }
}
while(i<=mid) X[k++]=R[i++];
while(j<=high) X[k++]=R[j++];
for(int i=0;i<high-low+1;i++){
R[low+i]=X[i];
}
free(X);
}
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int merge(int R[], int low, int mid, int high) {
int count = 0;
int i = low;
int j = mid + 1;
int k = 0;
int* X = (int*)malloc(sizeof(int) * (high - low + 1));
while (i <= mid && j <= high) {
if (R[i] <= R[j]) X[k++] = R[i++];
else {
X[k++] = R[j++];
count += mid - i + 1;//关键
}
}
while (i <= mid) X[k++] = R[i++];
while (j <= high) X[k++] = R[j++];
for (int i = 0; i < high - low + 1; i++) {
R[i + low] = X[i];
}
return count;
free(X);
}
int mergeSort(int R[], int m, int n) {
if (m >= n) return;
int k = (m + n) / 2;
mergeSort(R, m, k);
mergeSort(R, k + 1, n);
return merge(R, m, k, n);
}
int main() {
int R[MAXN];
int n;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
printf("%d ",mergeSort(R, 0, n - 1));
return 0;
}
十九、基于分治法的算法总结
二十、排序算法时间下界
实际叶结点的个数：n个元素的排列数为n!，故n个元素的排列判定树右n!个叶结点
应该的叶结点的个数：设树的高度为h,高为h的二叉树最多右2^h个叶结点
所以：n!<=2^h
二十一、外排序方法简介
二十二、分布排序
1、桶排序
1、分配：扫描n个元素，按关键词放入对应的桶中
2、收集：依次将桶中的元素取出
先进先出，桶排序时稳定的
#include<stdio.h>
#include<stdlib.h>
#define MAXN 20
const int INF = 0x3f3f3f3f;
void barrelSort(int R[], int n, int m, int Q[][MAXN]) {
for (int i = 0; i < n; i++) {
int j = R[i];
int k = 0;
while (Q[j][k] != INF) {
k++;
}
Q[j][k] = j;
}
int j = 0;
for (int i = 0; i < m; i++) {
int k = 0;
while (Q[i][k] != INF) R[j++] = Q[i][k++];
}
}
int main() {
int n;
scanf_s("%d", &n);//输入n个数
int R[MAXN];
for (int i = 0; i < n; i++) {
scanf_s("%d", &R[i]);
}
int m;
scanf_s("%d", &m);//输入的整都小于m，m为桶的个数
int Q[MAXN][MAXN];
for (int i = 0; i < m; i++) {
for (int j = 0; j < MAXN; j++) {
Q[i][j] = INF;
}
}
barrelSort(R, n, m, Q);
for (int i = 0; i < n; i++) {
printf("%d ", R[i]);
}
return 0;
}
2、计数排序
3、基数排序
1、基于桶排序的基数排序
1、按个位排列
2、按十位排列
3、按百位排列
2、基于计数排序的基数排序
评论区