Intro
啊哈，算法封面.png
t1.这篇文章记录我的一个学习和心得
t2.需要c语言基础
t3.需要数据结构和算法的基础
t4.Just Do it!
一大波树数正在靠近——排序
本节讲的是简化版桶排序法，事件复杂度为O(M+N)，这是一种非常快的排序算法，从1956年开始被使用。但它的缺点是非常的浪费空间。
对数字5 3 5 2 8进行排序.png
#include <stdio.h>
int main() {
//定义变量和数组
int a[11],i,j,t;
//初始化为0
for(i=0;i<11;i++) {
a[i] = 0;
}
//循环读入5个数
for(i=1;i<=5;i++) {
scanf("%d",&t);
a[t]++;
}
//遍历每一个桶，并输出每一个桶内的东西
//输出的内容就是i
//输出的次数就是a[i]此
for(i=0;i<=10;i++) {
for(j=1;j<=a[i];j++) {
printf("%d ",i);
}
}
//使用getchar();暂停程序，以便查看程序的输出
//你也可以使用 system("pause")进行暂停;
getchar();getchar();
return 0;
}
//最初我们使用的是从小到大排序
//如果想要使用从大到小的排序，则将21行的改为 for(i=10;i>=0;i--) 即可
#include <stdio.h>
int main() {
//初始化
int book[1000],i,j,t,n;
for(i=0;i<=1000;i++) { //m次循环
book[i] = 0;
}
printf("请输入读入元素的个数：\n");
scanf("%d",&n);
//输入
for(i=1;i<=n;i++) { //n次循环
scanf("%d",&t);
book[t]++;
}
//输出
for(i=0;i<=1000;i++) { //for循环嵌套 m+n次循环
for(j=1;j<=book[i];j++) {
printf("%d ",i);
}
}
getchar();getchar();
return 0;
}
//关键要把for循环嵌套那里的桶概念记清楚
//外圈i是桶的个数，也是我们的数据
//内圈j是元素出现次数
//事件复杂度 O(m+n+m+n) => O(2*(m+n)) => O(M+N)
//大O表示法一般都是大写
//大O表示法一般可以忽略较小的常数
邻居好说话——冒泡排序
冒泡排序的基本思想是：每次比较俩个相邻的数字，如果他们顺序错误，则进行交换位置冒泡排序的时间度是O(N方)，这是一个非常高的时间复杂度。
冒泡排序.png
#include <stdio.h>
int main() {
int a[100],i,j,t,n;
printf("请输入你要排序的个数:\n");
scanf("%d",&n);
//存储玩家输入的数字
for(i=0;i<n;i++) {
scanf("%d",&a[i]);
}
//冒泡排序
for(i=0;i<n-1;i++) { //比较n-1躺
for(j=0;j<=n-i;j++) { //每一躺比较的元素个数n-i
if(a[j]>a[j+1]) {
t = a[j]; //临时存储a[j]
a[j] = a[j+1];
a[j+1] = t;
}
}
}
//输出结果
for(i=0;i<n;i++) {
printf("%d ",a[i]);
}
//暂停程序
getchar();getchar();
return 0;
}
//这里的i和j都是以0开始的，没有出现数据错误乱码的情况
#include <stdio.h>
//结构体
struct student {
char name[100];
int score;
};
int main() {
//初始化变量
struct student a[100],t;
int i,j,n;
//输入
printf("请输入你要比较的元素的个数:");
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%s %d",a[i].name,&a[i].score);
}
//冒泡排序
for(i=1;i<=n-1;i++) {
for(j=1;j<=n-i;j++) {
if(a[j].score>a[j+1].score) {
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
//输出
for(i=1;i<=n;i++)
printf("%s ",a[i].name);
//暂停程序
getchar();getchar();
return 0;
}
最常用的排序——快速排序
冒泡排序虽然解决了桶排序的极大浪费空间的问题，但是它的算法执行效率上却牺牲了很多，它的时间复杂度为O(N方)，假如我们的计算机是运算次数是10亿/s，那么对1亿个数进行排序，桶排序只需0.1s，而冒泡排序则需要一千万秒，达到115天之久，可以使用更加高效的排序算法，快速排序
从右边开始查找.png
找到并交换值.png
再次找到再次交换.png
i等于j，更新基准数.png
#include <stdio.h>
//定义全局变量
int a[101],n;
//快速排序
void QuickSort(int left,int right) {
int i,j,t,temp;
if(left>right)
return;
i = left;
j = right;
temp = a[i];
while(i != j) {
//从j开始向左查找
while(a[j]<=temp && i<j)
j--;
//从i开始向右查找
while(a[i]>=temp && i<j) {
i++;
}
if(i<j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//将基数归位
a[left] = a[i];
a[i] = temp;
QuickSort(left,i-1);
QuickSort(i+1,right);
}
int main() {
int i;
printf("请输入数据元素的个数:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
QuickSort(1,n);
for(i=1;i<=n;i++) {
printf("%d ",a[i]);
}
getchar();getchar();
return 0;
}
//快速排序是由英国计算机科学家 Tony Hoare 发明，是一位伟大的英国计算机科学家
//快速排序是分治法的一种思想
//哨兵i,j
//首先，找一个基准数，一般我们把第一个数作为基准数
//然后，从右边找一个小于基准数的值并记录索引的位置，这个过程是j--
//然后同理从左边找一个大于基准数的值并记录索引，这个过程是i++
//都找到后交换位置
//当i=j，交换位置，更新基准数
//快速排序最差的情况的它的执行效率和冒泡排序一样都是O(N方),平均时间复杂度是O(NlogN)
小哼买书——练习测试
q1:输入一串1~1000的整数，去重且排序，完成后输出数据元素的个数。
最终效果.png
思路一：使用改变的桶排序法可以实现
思路二：使用冒泡先排序，后去重，就是从第二个开始，比较与前一个数是否相等，不相等则输出
思路三：快速排序，最优解法！
总结：综上所述，我们的ISBN是在1-1000，范围太小，如果是-2亿~2亿呢？或者n接近10万呢？冒泡排序则需要数十秒，快速排序则只需要 0.0017s,差距是多么的大，这就是算法的魅力!
//这里只给出桶排序的实现方法
#include <stdio.h>
int main() {
//j是去重后的元素的个数
int a[1000],i,j,t,n;
//初始化数组
for(i=1;i<1001;i++) {
a[i] = 0;
}
//输入
printf("请输入ISBN的总个数:");
scanf("%d",&n);
//记录
for(i=1;i<=n;i++) {
scanf("%d",&t);
if(a[t] == 0) {
a[t]++;
j++;
}
}
//输出
printf("共有%d种不同类型的ISBN号\n",j);
for(i=1;i<=1000;i++) {
if(a[i]>0) {
printf("%d ",i);
}
}
return 0;
}
//桶排序遍历输入时，注意遍历的是所有的桶，即遍历所有数组的索引
栈，队列，链表
解密QQ号——队列
规则是这样的：首先将第 1 个数删除，紧接着将第 2 个数放到这串数的末尾，再将第 3 个数删除并将第 4 个数放到这串数的末尾，再将第 5 个数删除……直到剩下后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的 QQ 啦。
过程图.png
#include <stdio.h>
int main() {
int a[102] ={6,3,1,7,5,8,9,2,4},head,tail;
//初始化头游标和尾游标
head = 0;
tail = 9;
while(head<tail) {
printf("%d ",a[head]); //输出第一个数
head++; //头游标自增
a[tail]=a[head]; //将第二个数移到后边
tail++; //尾游表自增
head++; //重新一轮
}
getchar();getchar();
return 0;
}
//这个小算法相当于帮助我们了解队列的概念
//使用结构体实现解密QQ号的算法
#include <stdio.h>
//队列
struct queue {
int data[100];
int head;
int tail;
};
int main() {
//初始化
struct queue q;
int i;
q.head = 1;
q.tail = 1;
for(i=1;i<=9;i++) {
scanf("%d",&q.data[q.tail]);
q.tail++;
}
while(q.head<q.tail) { //队列不为空时
//删除数据元素
printf("%d ",q.data[q.head]);
q.head++;
//移动数据元素
q.data[q.tail] = q.data[q.head];
q.tail++;
q.head++;
}
getchar();getchar();
return 0;
}
使用栈解密回文串
#include <stdio.h>
#include <string.h>
int main() {
//初始化
char a[101],s[101];
int i,len,mid,n,next,top;
//读入字符串的个数
scanf("%d",&n);
//读入n个字符并存储
for(i=1;i<=n;i++) {
scanf("%c",&a[i]);
}
//初始化变量
top = 0;
len = strlen(a);
mid = len/2-1;
//将mid前的数加入到栈中
for(i=1;i<=mid;i++) {
s[++top]=a[i];
}
//确定mid后next的位置
if(len%2==0)
next = mid + 1;
else
next = mid + 2;
//遍历从next到结尾的数据比较是否相同
for(i=next;i<=len-1;i++) {
if(a[i] != s[top])
break;
top--;
}
//输出结果
if(top == 0)
printf("是回文串");
else
printf("不是回文串");
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
纸牌游戏——小猫钓鱼（爬山）
游戏的规则是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手的
第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出牌
的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌尾。任意一人手中的牌全部出完时，游戏结束，对手获胜。
结果的验证.png
#include <stdio.h>
//模拟我们手牌的队列
struct queue {
int data[1000];
int head;
int tail;
};
//模拟桌牌的栈
struct stack {
int data[10];
int top;
};
int main() {
//定义变量
struct queue q1,q2;
struct stack s;
int book[10];
int i,t;
//初始化
q1.head=1;q1.tail=1;
q2.head=1;q2.tail=1;
s.top = 0;
for(i=0;i<=9;i++) {
book[i]=0;
}
//给玩家一发牌
for(i=1;i<=6;i++) {
scanf("%d",&q1.data[q1.tail]);
q1.tail++;
}
//给玩家二发牌
for(i=1;i<=6;i++) {
scanf("%d",&q2.data[q2.tail]);
q2.tail++;
}
while(q1.head<q1.tail && q2.head<q2.tail) {
//玩家一出牌
t = q1.data[q1.head];
//判断玩家一是否可以赢牌
if(book[t]==0) {
//不赢
q1.head++;
s.top++;
s.data[s.top] = t;
book[t] = 1;
}else{
//赢牌
//取得所有赢的牌
/* 我们出的牌 */
q1.head++;
q1.data[q1.tail] = t;
q1.tail++;
/* 中间的牌 */
while(s.data[s.top] != t) {
book[s.data[s.top]] = 0;
q1.data[q1.tail] = s.data[s.top];
q1.tail++;
s.top--;
}
/* 和第一张相同的牌 */
q1.data[q1.tail] = s.data[s.top];
}
//玩家二出牌
t = q2.data[q2.head];
//判断玩家是否出牌
if(book[t] == 0) {
//没有赢牌
q2.head++;
s.top++;
s.data[s.top] = t;
book[t] = 1;
}else {
//赢牌
q2.head++;
q2.data[q2.tail] = t;
q2.tail++;
while(s.data[s.top] != t) {
book[s.data[s.top]] = 0;
q2.data[q2.tail] = s.data[s.top];
q2.tail++;
s.top--;
}
q2.data[q2.tail] = s.data[s.top];
}
}
if(q1.head == q1.tail) {
//玩家一输了
printf("玩家二赢了!\n");
printf("玩家二当前的手牌是: ");
for(i=q2.head;i<=q2.tail-1;i++) {
printf("%d ",q2.data[i]);
}
}else {
//玩家二输了
printf("玩家一赢了!\n");
printf("玩家一的手牌为：");
for(i=q1.head;i<=q1.tail-1;i++) {
printf("%d ",q1.data[i]);
}
}
//如果桌上还有牌
printf("\n");
if(s.top > 0) {
printf("桌上剩余的牌为：");
for(i=1;i<=s.top;i++) {
printf("%d ",s.data[i]);
}
}else {
printf("桌上已经没有牌了!");
}
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
//输入输出log为：
//2 4 1 2 5 6
//3 1 3 5 6 4
//玩家一赢了!
//玩家一的手牌为：5 6 2 3 1 4 6 5
//桌上剩余的牌为：2 1 3 4
链表
单链表的结构.png
单链表插入结点.png
关于使用c实现链表需要注意的几点:
t1:怎么分配结点的内存空间，我们使用 (type 星号)malloc(sizeof(dataType)) 来动态声明内存空间。
t2:因为我们的节点是指针，访问每一个节点的内部成员要使用指针运算符'->'符号，如p->data=1。
t3:具体实现代码会在下面的代码块给出。
/*----使用c的结构体+动态内存分配malloc函数实现单链表----*/
#include <stdio.h>
#include <stdlib.h>
//表示一个节点
struct node {
int data;
struct node *next;
};
int main() {
//初始化（头结点head,临时结点q,迭代结点q,遍历临时头结点t）
struct node *head,*p,*q,*t;
int i,n,a;
//要读取几个数
scanf("%d",&n);
//循环读入n个数
for(i=1;i<=n;i++) {
scanf("%d",&a);
//动态申请一个内存空间，初始化结点
p = (struct node *)malloc(sizeof(struct node));
p->data=a;
p->next=NULL;
//判断头结点是否为空
if(head==NULL) {
head=p;
}else{
q->next=p;
}
//更新迭代结点
q=p;
}
//遍历单链表
t=head;
while(t != NULL) {
printf("%d ",t->data);
t=t->next;
}
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
//打印的日志为
//5
//1 6 6 9 6
//1 6 6 9 6
/*----------接上一节，实现单链表的插入结点的操作----------*/
#include <stdio.h>
#include <stdlib.h>
//结点结构体
struct node {
int data;
struct node *next;
};
int main() {
struct node *head,*p,*q,*t;
int i,n,a;
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%d",&a);
p = (struct node *)malloc(sizeof(struct node));
p->data=a;
p->next=NULL;
if(head==NULL) {
head = p;
}else{
q->next=p;
}
q = p;
}
//单链表插入结点
scanf("%d",&a);
t=head;
while(t != NULL) {
if(t->next->data > a) {
//申请内存空间
p = (struct node*)malloc(sizeof(struct node));
p->data=a;
//插入结点
p->next=t->next;
t->next=p;
break;
}
t=t->next;
}
//遍历结点
t=head;
while(t != NULL) {
printf("%d ",t->data);
t=t->next;
}
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
//需要注意的是遍历所有节点的下一个节点的操作那里，要使用while循环包上if条件判断
//置换节点那里理清思路即可
//测试打印的日志为
//5
//1 3 5 7 9
//6
//1 3 5 6 7 9
模拟链表
模拟链表的实现原理图.png
t1:新插入的数据我们直接放在data数组的后边即可。
t2:它们之间的关系我们存储right数组中
t3:例如 data[3]右边的值为data[right[3]]，即data[3]右边为data[10]
t4:仔细看一下上面那张图我们就可以理解。
t5:实现的代码在下边
#include <stdio.h>
int main() {
int data[101],right[101];
int i,n,t,len;
//读入n个数
scanf("%d",&n);
len=n;
//循环读入n个数
for(i=1;i<=n;i++) {
scanf("%d",&data[i]);
}
//初始化right数组
for(i=1;i<=n;i++) {
if(i!=n)
right[i]=i+1;
else
right[i]=0;
}
//直接在数组末尾增加一个数
len++;
scanf("%d",&data[len]);
//插入数据，更新right数组
t=1;
while(t!=0) {
if(data[right[t]] > data[len]) {
right[len]=right[t];
right[t]=len;
break;
}
t=right[t];
}
//遍历数组
t=1;
while(t!=0) {
printf("%d ",data[t]);
t=right[t];
}
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
//主要是right数组赋值的逻辑
//right数组索引保存的是它自身的data数组的索引，值保存的是它的右边数据的索引
//使用模拟链表可以实现双向链表和循环链表
//打印的日志为
//5
//1 3 5 7 9
//6
//1 3 5 6 7 9
枚举，很暴力！
坑爹的奥数
问题图.png
t1:求像 123 + 456 = 579 这样的组合有多少种？
t2:我们可以使用暴力枚举法，遍历出每种组合？
t3:因为 456 + 123 = 579 和t1重复了，所以我们需要将计算的结果除2
/*使用暴力枚举法求解，又叫做穷举法*/
#include <stdio.h>
int main() {
int a[10],i,total=0,book[10],sum;
for(a[1]=1;a[1]<=9;a[1]++)
for(a[2]=1;a[2]<=9;a[2]++)
for(a[3]=1;a[3]<=9;a[3]++)
for(a[4]=1;a[4]<=9;a[4]++)
for(a[5]=1;a[5]<=9;a[5]++)
for(a[6]=1;a[6]<=9;a[6]++)
for(a[7]=1;a[7]<=9;a[7]++)
for(a[8]=1;a[8]<=9;a[8]++)
for(a[9]=1;a[9]<=9;a[9]++) {
//初始化book数组
for(i=1;i<=9;i++) {
book[i]=0;
}
//如果某个数出现就标记一下
for(i=1;i<=9;i++) {
book[a[i]]=1;
}
sum=0;
for(i=1;i<=9;i++) {
sum+=book[i];
}
if(sum==9 && a[1]*100 + a[2]*10 + a[3] + a[4]*100 + a[5]*10 + a[6] == a[7]*100 + a[8]*10 + a[9]) {
total++;
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
}
printf("total=%d",total/2);
getchar();getchar();
return 0;
}
炸弹人
炸弹人游戏.png
上下左右遍历.png
t1:给出一个二维的数组模拟我们的整个地图
t2:使用 "#" 表示墙， "." 表示空地， "G" 表示敌人
t3:如是是向上遍历地图，则是y不变x--,可以结合上图看
t4:请写出相关的算法，算出将炸弹放在哪个位置炸死的敌人最多
#include <stdio.h>
int main() {
//地图大小不超过20*20
char a[20][20];
//初始化变量
int i,j,sum,map=0,p,q,x,y,n,m;
scanf("%d %d",&n,&m);
//读入n行字符,每行读取20个以内的字符
for(i=0;i<=n-1;i++) {
scanf("%s",a[i]);
}
//双层for循环枚举所有地形
for(i=0;i<=n-1;i++) {
for(j=0;j<=n-1;j++) {
//如果是空地，才可以放置炸弹
if(a[i][j] == '.') {
//可以杀死的敌人的数量
sum=0;
//将当前遍历的格子存储在临时变量x和y中
x=i;y=j;
//向上统计可以消灭敌人的数量
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x--;
}
//向下统计可以消灭敌人的数量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x++;
}
//向左统计可以消灭敌人的数量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
//向右统计可以消灭敌人的数量
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
if(sum>map) {
//更新和记录能消灭敌人的最大数量
map=sum;
//同时更新坐标(哪行哪列)
p=i;
q=j;
}
}
}
}
printf("将炸弹放置在%d行%d列，最多可以消灭%d个敌人",p,q,map);
getchar();getchar();
return 0;
}
//输入和输出为
//13 13
//#############
//#GG.GGG#GGG.#
//###.#G#G#G#G#
//#.......#..G#
//#G#.###.#G#G#
//#GG.GGG.#.GG#
//#G#.#G#.#.###
//##G...G.....#
//#G#.#G###.#G#
//#...G#GGG.GG#
//#G#.#G#G#.#G#
//#GG.GGG#G.GG#
//#############
//将炸弹放置在9行9列，最多可以消灭8个敌人
火柴棍等式
每个数字需要用到的火柴棍的个数.png
t1:加号和等于号各需要2根火柴棍
t2:如果a不等于b，a+b=c 和 b+a=c 视为不同的等式(a,b,c都大于0)
t3:所有火柴棍必须都用上，假设有火柴棍24个，即24-4=20个
t4:假如某人有m根火柴，那么究竟可以拼出多少个a+b=c的等式
t5:设计求解算法，要求时间复杂度为O(N方)
#include <stdio.h>
//得到一个数字的火柴的个数
int fun(int x) {
//记录已经使用的火柴的数量
int num=0;
//记录0~9数字的火柴棍的个数
int f[10] = {6,2,5,5,4,5,6,3,7,6};
//如果x不是一位数
while(x/10!=0) {
//获得末尾的数字的火柴的个数
num+=f[x%10];
//取出末尾的数字
x/=10;
}
//出了上面的while循环,x必定是一位数
num+=f[x];
//返回火柴的总个数
return num;
}
int main() {
//初始化变量
int a,b,c,m,i,sum=0; //sum是用来计数的，因此一定要初始化为0
//读入火柴棍的个数，存储在m变量中
scanf("%d",&m);
//开始枚举a和b
for(a=0;a<=1111;a++) {
for(b=0;b<=1111;b++) {
//算a+b的和
c=a+b;
//如果满足条件
if(fun(a)+fun(b)+fun(c)==m-4) {
printf("%d+%d=%d\n",a,b,c);
sum++;
}
}
}
printf("一共可以拼出%d个不同的等式",sum);
//暂停程序
getchar();getchar;
//结束程序
return 0;
}
//要枚举a b c,就要想到三个数值的范围是0~1111之间
//那么接下来只需要暴力枚举这之间的数判断筛选即可
//输入和输出的结果为
//18
//0+4=4
//0+11=11
//1+10=11
//2+2=4
//2+7=9
//4+0=4
//7+2=9
//10+1=11
//11+0=11
//一共可以拼出9个不同的等式
数的全排列
数字123的全排列.png
t1:请设计一个算法，实现1234的数字的全排列
t2:我们可以使用四层for循环嵌套筛选和过滤出满足 a!=b a!=c a!=d b!=c b!=d c!=d的排列
t3:具体实现代码如下图
//求1234的数的全排列组合
//并输出一共有多少种这样的组合
#include <stdio.h>
int main() {
//求1234的数的全排列
int a,b,c,d,sum=0;
for(a=1;a<=4;a++)
for(b=1;b<=4;b++)
for(c=1;c<=4;c++)
for(d=1;d<=4;d++) {
if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d) {
printf("%d%d%d%d\n",a,b,c,d);
sum++;
}
}
printf("一共有%d种排列",sum);
getchar();getchar();
return 0;
}
//输出为
//1234
//1243
//1324
//1342
//1423
//1432
//2134
//2143
//2314
//2341
//2413
//2431
//3124
//3142
//3214
//3241
//3412
//3421
//4123
//4132
//4213
//4231
//4312
//4321
//一共有24种排列
深度优先搜索
用深度优先的思想解决数的全排列
t1:接上边的那个算法
t2:输入3,就是求123的全排列，4就是1234的全排列，(0<n<9)
#include <stdio.h>
int a[10],book[10],n;
void dfs(int step) { //step表示我们当前在第几个盒子面前
int i;
if(step==n+1) {
for(i=1;i<=n;i++) {
printf("%d",a[i]);
}
printf("\n");
return;
}
//此时站在第step个盒子面前，要考虑放哪张牌的问题
for(i=1;i<=n;i++) {
if(book[i]==0) {
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}
int main() {
scanf("%d",&n);
dfs(1);
getchar();getchar();
return 0;
}
//输出和输出的结果为
//3
//123
//132
//213
//231
//312
//321
用深度优先解决之前的数字填空的问题
即 口口口+口口口=口口口 这种问题
#include <stdio.h>
int a[10],book[10],n;
//封装到每一个箱子面前要进行的步骤
void dfs(int step) {
int i;
if(step==n+1) {
if((a[1]*100+a[2]*10+a[3]) + (a[4]*100+a[5]*10+a[6]) == (a[7]*100+a[8]*10+a[9])) {
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
return;
}
for(i=1;i<=9;i++) {
if(book[i]==0) {
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}
int main() {
//表示有几个箱子，其实就是数字一共有9为，如123+456=579
n=9;
//从第一个箱子开始
dfs(1);
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
解救小哈
要走的四个方向的关系变化图.png
t1:使用深度优先搜索找到最段路径
t2:遍历查找的方向依次为右下左上(顺时针)查找，这里我们使用了一个int[4][2]的二维数组
t3:具体的实现的代码如下
/*使用深度优先的算法求俩点的最短路径*/
#include <stdio.h>
//初始化全局变量
int n,m,p,q,min=99999999;
int a[51][51],book[51][51];
void dfs(int x,int y,int step) {
//定义一个二维的数组存储存储我们要搜索的方向
int next[4][2] = {{0,1}, //向右搜索
{1,0}, //向下搜索
{0,-1}, //向左搜索
{-1,0}}; //向上搜索
int tx,ty,k;
//判断是否到达小哈的位置
if(x==p && y==q) {
if(step<min) {
min=step;
return;
}
}
//枚举四种走法
for(k=0;k<=3;k++) {
//计算下一个方向
tx=x+next[k][0];
ty=y+next[k][1];
//如果越界，就直接进行计算下一个方向
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
//判断该店是否为障碍物且已经在路径中
if(a[tx][ty]==0 && book[tx][ty]==0) {
//标记这个点为已经走过
book[tx][ty]=1;
//尝试下一个点
dfs(tx,ty,step+1);
//尝试结束，取消这个点的标记
book[tx][ty]=0;
}
}
return;
}
int main() {
//初始化变量
int i,j,startx,starty;
//读入n和m,n为行，m为列
scanf("%d %d",&n,&m);
//读入迷宫
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
//读入起点和终点
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//从起点开始走
book[startx][starty]=1;
dfs(startx,starty,0);
//输出最短步数
printf("解救小哈的最短步数为%d",min);
getchar();getchar();
return 0;
}
广度优先搜索
解救小哈
t1:我们之前使用了深度优先搜索，查找了小哈到小哼的步数
t2:这一接我们使用宽度优先搜索的方法
t3:实现的代码如下
#include <stdio.h>
//结点结构体
struct note {
int x; //横坐标
int y; //纵坐标
int f; //父亲在队列中的编号
int s; //步数
};
int main() {
struct note queue[2501]; //队列
//存储地图的二位数组和book标记数组
int a[51][51] = {0};
int book[51][51] = {0};
//定义一个方向的数组，依次是右下左上
int next[4][2] = {{0,1},
{1,0},
{0,-1},
{-1,0}};
//队列的头尾标记
int head,tail;
//初始化各种变量
int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
//输入行列的信息
scanf("%d %d",&n,&m);
//初始化二维数组
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
//输入起点和终点
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//队列的初始化
head=1;
tail=1;
//往队列插入起点
queue[tail].x = startx;
queue[tail].y = starty;
queue[tail].f = 0;
queue[tail].s = 0;
tail++;
//标记起点为已走过
book[startx][starty] = 1;
//flag为0未找到终点，1则是找到
flag = 0;
//当队列不为空
while(head<tail) {
for(k=0;k<=3;k++) {
//计算下一个点的位置
tx=queue[head].x+next[k][0];
ty=queue[head].y+next[k][1];
//校验
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
//如果这个点为0即空地且未被标记
if(a[tx][ty]==0 && book[tx][ty]==0) {
//满足条件，加入到队列中
book[tx][ty] = 1;
queue[tail].x = tx;
queue[tail].y = ty;
queue[tail].f = head;
queue[tail].s = queue[head].s+1;
tail++;
}
//判断是否到达终点
if(tx==p && ty==q) {
flag=1;
break;
}
}
if(flag==1)
break;
head++;
}
//输出到目标点一共走了多少步
printf("从小哈到小哼一共走了%d步",queue[tail-1].s);
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
//输入和输出为
//5 4
//0 0 1 0
//0 0 0 0
//0 0 1 0
//0 1 0 0
//0 0 0 1
//1 1 4 3
//从小哈到小哼一共走了7步
使用广搜再解炸弹人
t1:这次我们解决了炸弹人不可以走在炸弹上的问题
t2:使用的是广度优先搜索
t3:关于二维字符数字的赋值我们这里可以使用下面的方式，给一个for循环，里面加上scanf("%s",a[i]);这样
t4:上面表示接受了多少行字符，不用加取地址符&
t5:具体代码如下
#include <stdio.h>
//表示一个位置结点
struct node {
int x;
int y;
};
char a[20][21];
//求炸弹可以消灭敌人的数量
int getnum(int i,int j) {
int sum,x,y;
sum=0;
//向上搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y]=='G') {
sum++;
}
x--;
}
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y]=='G') {
sum++;
}
x++;
}
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
return sum;
}
int main() {
struct node queue[401];
int book[20][20]={0};
int head;
int tail;
int startx,starty,mx,my,tx,ty,sum,max=0,n,m,i,j,k;
//四个方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=0;i<=n-1;i++)
scanf("%s",a[i]);
head=1;
tail=1;
queue[tail].x=startx;
queue[tail].y=starty;
tail++;
book[startx][starty] = 1;
max=getnum(startx,starty);
mx=startx;
my=starty;
while(head<tail) {
for(k=0;k<=3;k++) {
//求出下一个要搜索的位置结点
tx=queue[head].x+next[k][0];
ty=queue[head].y+next[k][1];
//判断这个位置是否符合要求
if(tx<0 || tx>n-1 || ty<0 || ty>m-1)
continue;
if(a[tx][ty]=='.' && book[tx][ty]==0) {
book[tx][ty]=1;
queue[tail].x=tx;
queue[tail].y=ty;
tail++;
sum=getnum(tx,ty);
if(sum>max) {
//更新最小值min和记录结点的位置
max=sum;
mx=tx;
my=ty;
}
}
}
head++;
}
printf("将炸弹人放在(%d,%d)个位置上，最多可以消灭%d个敌人",mx,my,max);
getchar();getchar();
return 0;
}
//输入和输出为
//13 13 3 3
//#############
//#GG.GGG#GGG.#
//###.#G#G#G#G#
//#.......#..G#
//#G#.###.#G#G#
//#GG.GGG.#.GG#
//#G#.#G#.#.#.#
//##G...G.....#
//#G#.#G###.#G#
//#...G#GGG.GG#
//#G#.#G#G#.#G#
//#GG.GGG#G.GG#
//#############
//将炸弹人放在(7,11)个位置上，最多可以消灭10个敌人
使用深搜再解炸弹人
t1:思路就是使用深度优先遍历的方法，遍历每一个点，最后会记录的一个点的位置，这个位置炸死的敌人的数量是最多的
t2:只需要把dfs的每一步做好就行，在每一个点进行遍历，计算炸死的敌人的数量即可
t3:实现代码如下
#include <stdio.h>
//定义标志和地图的二维数组
char a[20][21];
int book[20][20],max=0,mx,my,n,m;
//得到可以消灭的敌人的数量
int getnum(int i,int j) {
//炸死的敌人的数量
int sum,x,y;
sum = 0;
//向上搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x--;
}
//向下搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
x++;
}
//向左搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y--;
}
//向右搜索
x=i;y=j;
while(a[x][y] != '#') {
if(a[x][y] == 'G') {
sum++;
}
y++;
}
//返回得到的炸弹数
return sum;
}
//每一步递归要进行的操作
void dfs(int x,int y) {
//定义一个用户表示方向的数组
int next[4][2] = {{0,1},
{1,0},
{0,-1},
{-1,0}};
int k,sum,tx,ty;
sum=getnum(x,y);
if(sum>max) {
max=sum;
mx=x;
my=y;
}
for(k=0;k<=3;k++) {
//计算下一个要遍历的点
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<0 || tx>n-1 || ty<0 || ty>m-1)
continue;
if(a[tx][ty]=='.' && book[tx][ty]==0) {
book[tx][ty]=1;
dfs(tx,ty);
}
}
return;
}
int main() {
//初始化变量
int i,j,startx,starty;
//读入有多少行和多少列
scanf("%d %d %d %d",&n,&m,&startx,&starty);
//读入n行字符
for(i=0;i<=n-1;i++)
scanf("%s",a[i]);
book[startx][starty]=1;
max=getnum(startx,starty);
mx=startx;
my=starty;
dfs(startx,starty);
//输出结果
printf("将炸弹放在(%d,%d)个位置，最多可以消灭%d个敌人",mx,my,max);
//暂停程序
getchar();getchar();
//退出程序
return 0;
}
//输入和输出的结果为
//13 13 3 3
//#############
//#GG.GGG#GGG.#
//###.#G#G#G#G#
//#.......#..G#
//#G#.###.#G#G#
//#GG.GGG.#.GG#
//#G#.#G#.#.#.#
//##G...G.....#
//#G#.#G###.#G#
//#...G#GGG.GG#
//#G#.#G#G#.#G#
//#GG.GGG#G.GG#
//#############
//将炸弹放在(7,11)个位置，最多可以消灭10个敌人
宝岛探险
使用广搜解决岛屿的面积的问题
宝岛探险.png
t1:有一个10*10大小的二维矩阵是一个宝岛的航拍地图，使用数字0代表海洋，使用数字1~9代表陆地
t2:现在假设小哼要降落在某个岛上并算出这个岛的面积
t3:我们可以使用广度优先搜索方法解决这个问题
t4:顶一个一个变量，遍历每一个格子，如果是大于1， 变量就进行自增
t5:最后输出这个变量就是这个岛屿的面积
#include <stdio.h>
//0海洋 1~9表示陆地
//格子不超过50*50
//表示一个结点
struct node {
int x;
int y;
};
int main() {
//初始化
struct node queue[2501];
int a[51][51];
int book[51][51];
int n,m,i,j,k,tx,ty,startx,starty,head,tail,sum;
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
head=1;
tail=1;
//把小哼降落的位置加入到队列
queue[head].x=startx;
queue[head].y=starty;
tail++;
book[startx][starty]=1;
sum=1;
//要遍历的四个方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
//队列不为空
while(head<tail) {
for(k=0;k<=3;k++) {
tx=queue[head].x+next[k][0];
ty=queue[head].y+next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
sum++;
book[tx][ty]=1;
queue[tail].x=tx;
queue[tail].y=ty;
tail++;
}
}
head++;
}
//输出
printf("该岛屿的面积为%d",sum);
getchar();getchar();
return 0;
}
//输入和输出为
//10 10 6 8
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 1 2 1 0 1 2
//4 0 1 0 1 2 3 2 0 1
//3 2 0 0 0 1 2 4 0 0
//0 0 0 0 0 0 1 5 3 0
//0 1 2 1 0 1 5 4 3 0
//0 1 2 3 1 3 6 2 1 0
//0 0 3 4 8 9 7 5 0 0
//0 0 0 3 7 8 6 0 1 2
//0 0 0 0 0 0 0 0 1 0
//该岛屿的面积为38
使用广搜解决岛屿的面积的问题(接上一节)
#include <stdio.h>
int a[51][51];
int book[51][51];
int n,m,sum=0;
void dfs(int x,int y) {
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
int tx,ty,k;
for(k=0;k<=3;k++) {
//计算下一个点
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<1 || tx>n || ty<1 || tx>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
sum++;
book[tx][ty]=1;
dfs(tx,ty);
}
}
return;
}
int main() {
int i,j,startx,starty;
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
sum=1;
book[startx][starty]=1;
dfs(startx,starty);
printf("小岛的面积为%d",sum);
getchar();getchar();
return 0;
}
//输出和输入同上一节
宝岛探险添加参数color
t1:只是给递归函数dfs添加了一个新的int类型参数color
t2:就是将小哼降落的小岛染色
#include <stdio.h>
int a[51][51];
int book[51][51],n,m,sum;
void dfs(int x,int y,int color) {
int k,tx,ty;
//四个方向
int next[4][2]={{0,1},
{1,0},
{0,-1},
{-1,0}};
a[x][y]=color;
for(k=0;k<=3;k++) {
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
book[tx][ty]=1;
dfs(tx,ty,color);
}
}
//这个return可以忽略不加
return;
}
int main() {
int i,j,startx,starty;
scanf("%d %d %d %d",&n,&m,&startx,&starty);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
dfs(startx,starty,-1);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
printf("%3d",a[i][j]);
}
printf("\n");
}
getchar();getchar();
return 0;
}
//输入和输出为
//10 10 6 8
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 1 2 1 0 1 2
//4 0 1 0 1 2 3 2 0 1
//3 2 0 0 0 1 2 4 0 0
//0 0 0 0 0 0 1 5 3 0
//0 1 2 1 0 1 5 4 3 0
//0 1 2 3 1 3 6 2 1 0
//0 0 3 4 8 9 7 5 0 0
//0 0 0 3 7 8 6 0 1 2
//0 0 0 0 0 0 0 0 1 0
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 -1 -1 -1 0 1 2
//4 0 1 0 -1 -1 -1 -1 0 1
//3 2 0 0 0 -1 -1 -1 0 0
//0 0 0 0 0 0 -1 -1 -1 0
//0 -1 -1 -1 0 -1 -1 -1 -1 0
//0 -1 -1 -1 -1 -1 -1 -1 -1 0
//0 0 -1 -1 -1 -1 -1 -1 0 0
//0 0 0 -1 -1 -1 -1 0 1 2
//0 0 0 0 0 0 0 0 1 0
宝岛探险求得海洋上小岛的个数
t1:思路还是使用深度优先搜索
t2:改变的只是添加了一个num参数，每次找到一个小岛的一部分，num--即可
t3:使用深度优先搜索递归完成之后，输出num的值即可
t4:这里思维较容易混乱，要注意区分最后使用递归找小岛的dfs和num之间关系的区分
#include <stdio.h>
int a[51][51];
int book[51][51],n,m,sum;
//深度优先遍历的递归调用
void dfs(int x,int y,int color) {
int next[4][2] = {{0,1}, //右边
{1,0}, //下边
{0,-1}, //左边
{-1,0}}; //上边
int k,tx,ty;
//将这个格子进行染色
a[x][y]=color;
//枚举四个方向
for(k=0;k<=3;k++) {
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0) {
sum++;
book[tx][ty]=1;
dfs(tx,ty,color);
}
}
}
int main() {
//初始化变量
int i,j,num=0;
//输入小岛的行列和连接信息
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
//递归计算一共有几个小岛
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
if(a[i][j]>0) {
num--;
book[i][j]=1;
dfs(i,j,num);
}
}
}
//输出小岛信息
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
printf("%3d",a[i][j]);
}
printf("\n");
}
printf("一共有%d个小岛",-num);
getchar();getchar();
return 0;
}
//输入和输出分别是
//10 10
//1 2 1 0 0 0 0 0 2 3
//3 0 2 0 1 2 1 0 1 2
//4 0 1 0 1 2 3 2 0 1
//3 2 0 0 0 1 2 4 0 0
//0 0 0 0 0 0 1 5 3 0
//0 1 2 1 0 1 5 4 3 0
//0 1 2 3 1 3 6 2 1 0
//0 0 3 4 8 9 7 5 0 0
//0 0 0 3 7 8 6 0 1 2
//0 0 0 0 0 0 0 0 1 0
// -1 -1 -1 0 0 0 0 0 -2 -2
// -1 0 -1 0 -3 -3 -3 0 -2 -2
// -1 0 -1 0 -3 -3 -3 -3 0 -2
// -1 -1 0 0 0 -3 -3 -3 0 0
// 0 0 0 0 0 0 -3 -3 -3 0
// 0 -3 -3 -3 0 -3 -3 -3 -3 0
// 0 -3 -3 -3 -3 -3 -3 -3 -3 0
// 0 0 -3 -3 -3 -3 -3 -3 0 0
// 0 0 0 -3 -3 -3 -3 0 -4 -4
// 0 0 0 0 0 0 0 0 -4 0
//一共有4个小岛
水管工游戏
水管工游戏.png水管连通之后.png每个数字代表不同的水管.png
t1:0代表树木，1-6代表管子（1-4是弯管，5和6是直的管子）
t2:输入矩阵的行列信息
t3:输入每条管道的信息
t4:输出是否可以构成一条连通的管道
#include <stdio.h>
int a[51][51];
int book[51][51],n,m,flag=0;
void dfs(int x,int y,int front) {
if(x==n && y==m+1) {
flag=1;
return;
}
//判断是否越界
if(x<1 || x>n || y<1 || y>m)
return;
//判断管道是否在游戏中使用过
if(book[x][y]==1)
return;
//标记这个管道已经遍历过
book[x][y]=1;
//当前水管是直管的时候
if(a[x][y]>=5 && a[x][y]<=6) {
//进水口在左边
if(front==1) {
dfs(x,y+1,1);
}
//进水口在上边
if(front==2) {
dfs(x+1,y,2);
}
//进水口在右边
if(front==3) {
dfs(x,y-1,3);
}
//进水口在下边
if(front==4) {
dfs(x-1,y,4);
}
}
if(a[x][y]>=1 && a[x][y]<=4) {
if(front==1) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==2) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
if(front==3) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==4) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
}
//如果有管子可以连接下去，就会一直递归调用，否则就会执行下面这个操作返回到上一次的地方
//这里是个难点，也是区分于广度优先搜索的代码
book[x][y]=0;
return;
}
int main() {
int i,j,num=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
dfs(1,1,1);
if(flag==0) {
printf("impossible\n");
}else{
printf("找到铺设方案\n");
}
getchar();getchar();
return 0;
}
//输入和输出是
//5 4
//5 3 5 3
//1 5 3 0
//2 3 5 1
//6 1 1 5
//1 5 5 4
//找到铺设方案
水管工游戏保存和输出路径点
t1:就是添加了一个结构体和结构体的数组
t2:添加了一个新的标志位top，默认为0
#include <stdio.h>
struct node {
int x;
int y;
}s[100];
int a[51][51];
int book[51][51],n,m,flag=0;
int top=0;
void dfs(int x,int y,int front) {
int k;
if(x==n && y==m+1) {
flag=1;
for(k=1;k<=top;k++) {
printf("(%d,%d)",s[k].x,s[k].y);
}
return;
}
//判断是否越界
if(x<1 || x>n || y<1 || y>m)
return;
//判断管道是否在游戏中使用过
if(book[x][y]==1)
return;
//标记这个管道已经遍历过
book[x][y]=1;
top++;
s[top].x=x;
s[top].y=y;
//当前水管是直管的时候
if(a[x][y]>=5 && a[x][y]<=6) {
//进水口在左边
if(front==1) {
dfs(x,y+1,1);
}
//进水口在上边
if(front==2) {
dfs(x+1,y,2);
}
//进水口在右边
if(front==3) {
dfs(x,y-1,3);
}
//进水口在下边
if(front==4) {
dfs(x-1,y,4);
}
}
if(a[x][y]>=1 && a[x][y]<=4) {
if(front==1) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==2) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
if(front==3) {
dfs(x+1,y,2);
dfs(x-1,y,4);
}
if(front==4) {
dfs(x,y+1,1);
dfs(x,y-1,3);
}
}
book[x][y]=0;
top--;
return;
}
int main() {
int i,j,num=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
dfs(1,1,1);
if(flag==0) {
printf("impossible\n");
}
getchar();getchar();
return 0;
}
//输入和输出为:
//5 4
//5 3 5 3
//1 5 3 0
//2 3 5 1
//6 1 1 5
//1 5 5 4
//(1,1)(1,2)(2,2)(3,2)(3,3)(3,4)(4,4)(5,4)
再探深度优先搜索
我们要遍历的图.png
使用邻接矩阵存储边.png
图的顶点的访问顺序.png
t1:本题要求使用深度优先搜索遍历所有顶点并输出顶点
t2:图三是使用深度优先搜索遍历输出顶点的顺序，顶点旁边的数字我们叫做事件戳
t3:实现代码如下
#include <stdio.h>
//初始化变量
int book[101],e[101][101],sum=0,n,inf=99999999;
//深度优先搜索
void dfs(int cur) {
//初始化变量并输出当前遍历的点
int i;
printf("%d ",cur);
sum++;
if(sum==n)
return;
//检查是否有边的连接
for(i=1;i<=n;i++) {
if(e[cur][i]==1 && book[i]==0) {
book[i]=1;
dfs(i);
}
}
return;
}
int main() {
int m,i,j,a,b;
//n是顶点的个数，m的边的个数
scanf("%d %d",&n,&m);
//初始化二维数组
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if(i==j){
e[i][j]=0;
}else{
e[i][j]=inf;
}
}
}
//输入边的信息并存储，注意这里是无向图
for(i=1;i<=m;i++) {
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
//从一号顶点开始深度优先搜索
book[1]=1;
dfs(1);
getchar();getchar();
return 0;
}
//输入和输出为
//5 5
//1 2
//1 3
//1 5
//3 5
//2 4
//1 2 4 3 5
使用广度优先搜索遍历上一节的图
t1:遍历方式改为广搜，实现的代码如下
#include <stdio.h>
//初始化相关变量
int queue[101],book[101],e[101][101],inf=99999999;
int main() {
int n,m,i,j,a,b,cur;
int head,tail;
//n是顶点个数，m是边的个数
scanf("%d %d",&n,&m);
//初始化二维数组
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if(i==j) {
e[i][j]=0;
}else{
e[i][j]=inf;
}
}
}
//使用邻接矩阵存储边
for(i=1;i<=m;i++) {
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
//初始化队列的头尾节点
head=1;
tail=1;
//将第一个顶点添加到队列中
queue[tail]=1;
tail++;
book[1]=1;
//当队列不为空
while(head<tail) {
//当前药遍历的根节点
cur=queue[head];
//遍历所有节点
for(i=1;i<=n;i++) {
if(e[cur][i]==1 && book[i]==0) {
queue[tail]=i;
tail++;
book[i]=1;
}
//如果tail大于顶点个数，就跳出循环
if(tail>n) {
break;
}
}
head++;
}
//遍历输出队列中的顶点
for(i=1;i<tail;i++) {
printf("%d ",queue[i]);
}
getchar();getchar();
return 0;
}
//输出和输出为
//5 5
//1 2
//1 3
//1 5
//2 4
//3 5
//1 2 3 5 4
城市地图——图的深度优先遍历
城市路径求点到点的最短路径.png
图的邻接矩阵.png
t1:图的邻接矩阵存储的是路径和路径上的权值
t2:本题是求顶点1到顶点5的最短路径
t3:示例代码如下
#include <stdio.h>
//初始化
int min=99999999,book[101],n,e[101][101];
//递归函数(顶点试完之后要重置标志位)
void dfs(int cur,int dis) {
if(dis>min) return;
if(cur==n) {
if(dis<min) min=dis;
return;
}
int j;
for(j=1;j<=n;j++) {
if(e[cur][j]!=99999999 && book[j]==0) {
book[j]=1;
dfs(j,dis+e[cur][j]);
book[j]=0;
}
}
return;
}
int main() {
int i,j,m,a,b,c;
scanf("%d %d",&n,&m);
//初始化邻接矩阵
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
if(i==j) e[i][j]=0;
else e[i][j]=99999999;
}
}
//读入边
for(i=1;i<=m;i++) {
scanf("%d %d %d",&a,&b,&c);
e[a][b]=c;
}
book[1]=1;
dfs(1,0);
printf("一号城市到五号城市的最短路径为%d",min);
getchar();getchar();
return 0;
}
//输入和输出为：
//5 8
//1 2 2
//1 5 10
//2 3 3
//2 5 7
//3 1 4
//3 4 4
//4 5 5
//5 3 3
//一号城市到五号城市的最短路径为9
最少转机——图的广度优先遍历
小哼和小哈.png
城市地图.png
队列过程.png
t1:本题是求顶点1到顶点5的最短路径
t2:所有路径的权值均为1
t3:示例代码如下:
t4:5 7 1 5意思是五个顶点7条边，起点为1，终点为5
#include <stdio.h>
//一个顶点
struct node {
int x; //城市编号
int s; //转机次数
};
int main() {
//初始化
struct node que[2501];
int e[51][51]={0},book[51]={0};
int head,tail;
int i,j,n,m,a,b,cur,start,end,flag=0;
scanf("%d %d %d %d",&n,&m,&start,&end);
//初始化二维矩阵
for(i=1;i<=m;i++) {
for(j=1;j<=m;j++) {
if(i==j) e[i][j]=0;
else e[i][j]=99999999;
}
}
//读入城市之间的航班
for(i=1;i<=m;i++) {
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
//队列初始化
head=1;
tail=1;
que[tail].x=start;
que[tail].s=0;
tail++;
book[1]=start;
//只要队列不为空
while(head<tail) {
//保存当前头结点
cur=que[head].x;
//尝试头结点连接的所有顶点
for(i=1;i<=n;i++) {
if(e[cur][i]!=99999999 && book[i]==0) {
que[tail].x=i;
que[tail].s=que[head].s+1;
book[i]=1;
tail++;
}
//到达目标点
if(que[tail].x==end) {
flag=1;
break;
}
}
//如果找到则跳出while循环
if(flag==1)
break;
//没到目标点则继续查找，head++;
head++;
}
printf("起点%d到终点%d的最短距离为%d",start,end,que[tail-1].s);
getchar();getchar();
return 0;
}
//输入和输出为：
//5 7 1 5
//1 2
//1 3
//2 3
//2 4
//3 4
//3 5
//4 5
//起点1到终点5的最短距离为2
