技术标签: c语言
这次小学期大作业给了几道编程题让我们自己选,其中就有一道求解八数字问题。刚拿到这个题的时候头疼得不行,还得用c语言写,大一才学了这么点东西哪能做得出来,哈希表,搜索代码一个没学。后来一想可能是想考察我们自主学习的能力?那就开整吧。
本文仅用于记录自己学习过程,仅模拟给和我同进度的同学讲解的语气,并非攻略教程,难免会有错误且代码写得烂,求轻喷。
思路参考:(8条消息) 如何通过编程解决华容道问题?_程序人生的博客-程序员宅基地
感谢大佬理清做题思路。
先看看题目要求:
规则:8数码拼图,9宫格中随机放置数字0-8,0作为空位可与上下左右的数字交换,最终排列为:
012
345
678
后面还给了几个函数的函数头,略。
emmm这题干讲了,但又什么都没讲,自由发挥了属于是。
首先得有个棋盘,这个棋盘是自己生成还是输入呢?为了提高难度我选择了自己生成随机棋盘。
其次是需要的算法。华容道其实就像走迷宫问题,0就是我们当前所在位置,0在一个3x3的棋盘里进行上下左右移动,最终目的就是恢复成012345678这样的状态。这道题我们是想要求解所有可能的解还是只要一个解就行呢?我认为是求解出一个就行了,这个解最好是最优解(也就是步骤最少的解),那么胜利的法则就决定了:宽度优先搜索。
百度宽搜可得
广度优先搜索使用队列(queue)来实现,整个过程也可以看做一个倒立的树形:
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到,结束程序。
而我们不能只搜索,还要找出解并且把它打印出来。那么就可以参考链表的方法,每次搜索的时候创建一个结点,这个结点存储它的棋盘,以及它的上一步的结点和当前走的方向,就像链表一样把它们连接起来。这样一旦发现了解,只需要顺藤摸瓜,抓住成功的那个结点一个个往回拽出来即可。
那么接下来就是定义需要的数据结构。首先定义一个结构体保存棋盘,再定义一个结构体保存结点,接着是定义一个链表队列。
好像大功告成了?但还有一个问题,如果第一步往右走,第二步又往左走了,这不就回到原来的状态了吗,势必会造成出现许多不必要的步骤的情况。那么如何解决呢?把所有出现过的状态都存起来!用什么来存呢?反观我们这学期学的的基础的数据结构,如果用顺序表链表来存,显然是不行的。因为9宫格有多少种状态……9的9次方387420489种,虽然实际计算时不可能每种状态都经历一遍,但也是个不小的数字!以顺序表链表的搜索的时间复杂度来看,会非常慢。怎么办呢?我们知道顺序表的查询指定下标的时间复杂度是O(1),也就是知道下标就能立刻查询到它。如果我们用一种特殊的方法把要查询的数据转成一个下标值,然后把它存储到下标位置,是不是可以以O(1)的时间复杂度查询到出现过的棋盘状态呢?答案是可以,这种数据结构就叫哈希表。
好,链表队列,哈希表,我们的数据结构就这么决定了。
首先定义结构体。链式队列的代码大家应该很容易写出来,这次新加了一个之前没接触过的哈希表的代码,其实很好理解,它就是一个有特殊功能,存储时较为特别的顺序表。
typedef struct{ //a来存储棋盘,i,j存储0的当前位置(别问我为什么用char数组,因为题目要求)
char a[N*N];
char i,j;
}G;
typedef struct node{
struct node *last; //存步骤中它的上一个结点
struct node *next; //存链表中它的下一个结点
int status; //存棋盘状态
int dir; //这一步走的方向
}Node;
typedef struct{
Node *head,*tail; //队列的队头和队尾指针
int size; //队列长度
}List;
typedef struct{
unsigned max_size; //哈希表最大容量capacity
unsigned cur_size; //哈希表当前容量
int* table; //存储用的数组
}hash;
接下来是他们的函数。
//队列部分
void init_list(List *lp){ //初始化队列
lp->head=(void*)0;
lp->tail=(void*)0;
lp->size=0;
}
int get_list_size(List *lp){ //获取队列长度
return lp->size;
}
void insert_list(List* lp,Node* node){ //队尾入队
if(lp->tail)
lp->tail->next=node;
else
lp->head=node;
lp->tail=node;
lp->size++;
}
int* pop_list(List* lp){ //队头出队
if(lp->size==0)
return (void*)0;
int status=lp->head->status;
lp->head=lp->head->next;
lp->size--;
if(lp->size==0)
lp->tail=(void*)0;
return status; //顺便返回队头元素的棋盘状态,写在下面那个函数里也行,用的时候改一下就好了
}
Node* get_head_list(List* lp){ //获取队头元素
return lp->head;
}
Node* make_node(Node* last,int status,int dir){ //创建结点
Node *np=malloc(sizeof(Node));
if(!np)
return (void*)0;
np->last=last;
np->status=status;
np->dir=dir;
np->next=(void*)0;
return np;
}
//哈希表部分
hash* init_hash(hash* hash_table,unsigned size){ //初始化哈希表
int i;
hash_table->max_size=(size!=0)?size:30; //给哈希表一个初始大小,默认30
hash_table->table=(int*)malloc(sizeof(int)*hash_table->max_size); //为哈希表分配空间
hash_table->cur_size=0;
for(i=0;i<hash_table->max_size;i++) //初始化哈希表,每个元素都设为0
hash_table->table[i]=0;
printf("哈希表创建成功!大小为:%d\n",hash_table->max_size);
return hash_table;
}
int toHash(hash* hash_table,int key){ //哈希函数 将元素的值转成下标的关键函数
return key%(hash_table->max_size); //这里我设定的是key和哈希表的最大容量取模,有其他转换方式都可以
}
int getIndex(hash* hash_table,int key){ //查询指定值的存储位置
int index;
index=toHash(hash_table,key);
while(hash_table->table[index]!=0){ //我使用了线性探测法处理冲突
if(index>=hash_table->max_size)
index%=hash_table->max_size;
index++;
}
return index;
}
hash* extend(hash* hash_table){ //空间扩展操作 扩展后容量变为二倍
int i,index;
int* new_table=(int*)malloc(sizeof(int)*hash_table->max_size*2);
hash_table->max_size*=2;
for(i=0;i<hash_table->max_size;i++)
new_table[i]=0;
for(i=0;i<hash_table->cur_size;i++){ //遍历旧表中的所有元素一个一个重新存入新表
if(hash_table->table[i]==0)
continue;
index=toHash(hash_table,hash_table->table[i]);
while(new_table[index]!=0){
if(index>=hash_table->max_size)
index%=hash_table->max_size;
index++;
}
new_table[index]=hash_table->table[i];
}
free(hash_table->table);
hash_table->table=new_table;
return hash_table;
}
hash* insert(hash* hash_table,int key){ //插入
if(key<=0){
return (void*)0;
}
if(hash_table->cur_size*1.2>=hash_table->max_size){
// printf("hash table has become bigger\n");
extend(hash_table);
}
int index;
index=getIndex(hash_table,key);
hash_table->table[index]=key;
hash_table->cur_size++;
return hash_table;
}
int find(hash* hash_table,int key){ //查询
int index;
if(key<=0){
return (void*)0;
}
index=toHash(hash_table,key);
while(hash_table->table[index]!=key){ //因为使用了线性探测法处理冲突
if(index>=hash_table->max_size) //所以查询也是同样,每次比对是否和要查的key相等
index%=hash_table->max_size; //如果不等,继续向后查询
if(hash_table->table[index]==0){ //如果遇到了没有存储元素的空位,说明表中没有这个元素,也就是没有找到
return -1;
}
index++;
}
return index;
}
void print_table(hash* hash_table){ //打印哈希表(这题目没用上此函数,姑且先作为示例放上来)
int i;
printf("|");
for(i=0;i<hash_table->max_size;i++){
printf("%4d |",hash_table->table[i]);
}
printf("\n");
}
首先看图解:
① 从待查队列中出队一个结点,进入②。当待查队列中没有元素的时候,退出循环。
② 在这个结点的棋盘的基础上前进一步。如果四个方向都走过了,回到①。
③ 在用来保存查询过的状态的哈希表中查询这个前进后的状态有没有出现过。
如果出现过,复原棋盘(向反方向走一步退回),继续下一个方向的探索,回到②。
如果没出现过,进入④。
④ 创建新的结点,保存当前的棋盘状态,当前的前进方向,以及指向上一步的结点的指针。接着 进入⑤。
⑤ 判断这个状态是不是我们要的最终状态,如果是,直接循环输出所有步骤后结束。如果不是, 进入⑥。
⑥ 将新的状态存入哈希表中。进入⑦。
⑦ 将创建好的新结点入队。返回②。
按照这个过程,我们就能进行宽度优先搜索,找出最优解。
如何保存棋盘状态?我使用一个整数来存储。
0 1 2
3 4 5
6 7 8
像这样的一个棋盘,我们可以简单使用12345678一个整数来存储
那么,我们都需要哪些函数来实现功能呢?
先把需要用到的头文件引入一下~我们虽然用0123表示左上右下的移动方向,但代码可读性不好。我们要定义常量,用LEFT UP RIGHT DOWN来代替0123。N代表棋盘大小为3X3。
#include<stdio.h>
#include<time.h>
#include<malloc.h>
#include<string.h>
#define N 3
#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3
首先是随机生成一个棋盘的代码。
void init(G* g){
int p=0;
int i=0;
int num;
char unused[10]={'1','2','3','4','5','6','7','8'};
srand(time(0)); //我们先随机生成一个0点的初始位置
int zero_pos=rand()%8; //还记得吗 i,j是我们用来存储0点坐标的变量
g->a[zero_pos]='0'; //因为我们使用了一维数组存储棋盘
g->i=zero_pos/3; //所以i,j的计算是i=零点位置/3 j=零点位置-(零点位置/3)*3
g->j=zero_pos-(zero_pos/3)*3;
printf("zero position:(%d,%d)\n",g->i,g->j);
p=zero_pos==0?1:0; //如果0随机出现在了(0,0)点,那么就从第二个位置开始循环,如果不是就从第一个位置开始循环
while(p<9){ //循环填入1~8
if(p==zero_pos){
p++;
continue;
}
num=1+rand()%8;
for(i=0;i<8;i++){ //为了避免出现重复数字,我们每使用一个数字就将unused数组里的对应数字变成0(也就是删除)
if(unused[i]=='0'+num){ //如果随机数在unused里有,那就是没用过,直接使用
unused[i]=0;
g->a[p]='0'+num;
p++;
break;
}
}
}
}
然后是移动,0点不会动可不行。
int move(G* g,int n){ //如果能移动,直接移动然后返回1,不能移动返回0.
char t;
int x=g->i;
int y=g->j;
switch(n){
case LEFT: //LEFT=0 UP=1 RIGHT=2 DOWN=3
if(y>0){ //如果移动后是边缘,那肯定是不能移动的
t=g->a[x*N+y-1]; //移动也就是两个元素相互交换,这里不多讲了。
g->a[x*N+y-1]='0';
g->a[x*N+y]=t;
g->j-=1;
return 1;
}
break;
case UP:
if(x>0){
t=g->a[(x-1)*N+y];
g->a[(x-1)*N+y]='0';
g->a[x*N+y]=t;
g->i-=1;
return 1;
}
break;
case RIGHT:
if(y<N-1){
t=g->a[x*N+y+1];
g->a[x*N+y+1]='0';
g->a[x*N+y]=t;
g->j+=1;
return 1;
}
break;
case DOWN:
if(x<N-1){
t=g->a[(x+1)*N+y];
g->a[(x+1)*N+y]='0';
g->a[x*N+y]=t;
g->i+=1;
return 1;
}
break;
default:return 0;
}
return 0;
}
接着是定义胜利状态的函数,如果满足它我们就成功啦。
int isok(int status){
if(status==12345678)
return 1;
else return 0;
}
既然用一个整数保存棋盘状态,那么就得有一个函数来实现这个功能,将棋盘转换成整数。
int getStatus(char* a){
int status=0;
int i;
for(i=0;i<N*N;i++){
status*=10;
status+=a[i]-'0';
}
return status;
}
对了,还有返回,我们如果走到了之前走过的状态是需要回退的。所以我们需要一个能根据当前方向回退的函数。
int back(int n){
switch(n){
case UP:return DOWN;
case DOWN:return UP;
case LEFT:return RIGHT;
case RIGHT:return LEFT;
}
}
还有什么呢?虽然题目要求要用0123表示左上右下,可这对于我们人类来说可太难阅读了!我们需要一个说人话的函数,把0123翻译成汉字,这样最终输出的步骤才能读得明白。既然追求可读性,还得要一个输出棋盘的函数,把当前棋盘写出来给我们看看是什么样。
//翻译
void translation(int n){
switch(n){
case UP:printf("上 ");break;
case DOWN:printf("下 ");break;
case LEFT:printf("左 ");break;
case RIGHT:printf("右 ");break;
}
}
//打印棋盘
void print(G* g){
int i;
int count=0;
for(i=0;i<N*N;i++){
printf("%c ",g->a[i]);
count++;
if(count%3==0)
printf("\n");
}
}
前期准备结束啦,开始我们的重头戏,宽搜算法!
Node* search(){
int dir=0;
int i,j;
int num=0;
Node *now_node;
char result[100];
G g; //创建结构体对象,这就是我们的棋盘了
init(&g); //别忘了初始化生成棋盘
// g.a[0]='8'; //这里是测试用的 可以输入指定的棋盘求解。
// g.a[1]='4';
// g.a[2]='2';
// g.a[3]='3';
// g.a[4]='5';
// g.a[5]='1';
// g.a[6]='0';
// g.a[7]='7';
// g.a[8]='6';
print(&g); //先把随机生成的棋盘发出来看看
system("pause");
hash searchedList; //同样的,待搜队列和已搜列表也要创建一个对象
List searchList;
init_hash(&searchedList,100);
init_list(&searchList);
Node *last_node=make_node((void*)0,getStatus(g.a),-1); //我们把棋盘最开始的样子作为第一个待搜结点储存
insert_list(&searchList,last_node);
while(get_list_size(&searchList)>0){ //当待搜队列里还有元素的时候,一直循环
num++; //用来计我们总共搜索了多少次
last_node=get_head_list(&searchList); //查看队首 ,获取队首元素的地址
int now_status=pop_list(&searchList); //获取队首状态并使队首出列
for(i=N-1;i>=0;i--){ //把status还原成图
for(j=N-1;j>=0;j--){
g.a[i*N+j]=now_status%10+'0';
if(g.a[i*N+j]=='0'){
g.i=i;
g.j=j;
}
now_status/=10;
}
}
for(i=0;i<4;i++){
if(move(&g,i)){ //移动一步
now_status=getStatus(g.a);
if(find(&searchedList,now_status)!=-1){ //如果出现过了,回退,继续查下一个方向。
move(&g,back(i));
continue;
}
now_node=make_node(last_node,now_status,i); //新建结点把当前情况储存
// printf("now_node lastSta=%d,nowSta=%d,dir=%d\n",now_node->last->status,now_node->status,now_node->dir);
if(isok(now_status)){ //如果解题成功 输出解题步骤后结束函数
printf("解题步骤为\n");
print(&g);
i=0;
while(now_node->dir!=-1){
result[i++]=now_node->dir;
now_node=now_node->last;
}
for(j=i-1;j>=0;j--)
translation(result[j]);
printf("共计算了%d次\n",num);
return now_node;
}
insert(&searchedList,now_status); //很遗憾现在的状态不是解题成功的
move(&g,back(i)); //那就把现在的状态放入已查列表中,把当前结点放入待查列表中,准备下一次循环。别忘了回退哦。
insert_list(&searchList,now_node);
}
}
// printf("当前队列剩余:%d\n",searchList.size);
}
printf("此题无解\n"); //如果待查列表空了,退出循环,也就代表着没有找到解
printf("共计算了%d次\n",num);
return (void*)0;
}
至此,本题结束,求解完成。最后只需要在main方法里调用search()函数就行了。
看看运行结果!这是有解的情况!
啊哦,这题没有解~
通过这次大作业我熟悉了数据结构,加深了对如何选择数据结构解题的方法的印象,还提高了自主学习能力,挺秃头,但也很值得。虽然这是一个对大佬来说很基础的题目,但对我来说可以说是我步入数据结构和算法的敲门砖了,以后的日子里也要加油!大作业还有其他的题目,比如我自己独立写了一个哈夫曼编码的代码,又臭又长就不放出来了。。。马上开学了,考试再加上网页的项目,一堆事要做,像这样纯粹学习算法的时间也不知道能不能找到了,大二加油!
谨以此文记录我的学习过程,此文并非教程,不保证正确性,请酌情参考呀。
封面是我同学的表情包(滑稽.jpg)。
附上注释写得不详细的源代码文件:
链接:https://pan.baidu.com/s/1Lt09LtTmear07qJKP0zimQ
提取码:2cj7
文章浏览阅读1.2k次。案例:绘制交货延迟天数甘特图step1:把‘计划交货日期’拖到‘列’把‘供应商名称’和‘物资类别’拖到‘行’step2:把‘计划交货日期’改成‘天’,注意:选择的是第二个‘天’!!!改了之后就变成这个样子:step3:在‘度量’那里的空白处点击右键,选择‘创建计算字段’,然后创建一个‘延迟天数’的新字段,创建好之后点‘应用’、‘确定’。step4:把‘延迟天数’拖到‘大小’那里,之后就是这个样子图中蓝色长条的长度就反映了延迟天数的长短,但是有一个问题,有些商品是提前交货的,提_甘特图 延期怎么样表示
文章浏览阅读936次。背景如果将shellcode注入到具有特定权限的进程中,使用 ShellCode 创建的进程就可以获得与该进程相同的权限。本次使用的工具,依旧是上次编写的PETools:https://www.cnblogs.com/LyShark/p/12960816.html提权降权工具下载地址:https://www.blib.cn/soft/pexec.zip枚举系统进程,与进程权限令牌等。#include <stdio.h>#include <Windows.h>#inc_shellcode 注入进程 执行
文章浏览阅读1.2k次。1. 命令行不知道大家在日常操作redis时用什么可视化工具呢?以前总觉得没有什么太好的可视化工具,于是问了一个业内朋友。对方回:你还用可视化工具?直接命令行呀,redis提供了这么多命令,操作起来行云流水。用可视化工具觉得很low。命令行的鄙视用工具的,用高端工具的鄙视低端工具的,鄙视链一直存在。虽然用命令行自己也可以,但是总感觉效率上不如用工具,在视觉上不那么直观。尤其是看json的时候,在命令行就很不友好。大佬朋友说:谁说命令行就不能格式化json了?可以利用iredis,用|将redis..._服务器可视化管理工具x
文章浏览阅读331次。1.链接:http://lbsyun.baidu.com/index.php?title=androidsdk2.申请密钥:1.获取应用sha1:keytool -v -list -keystore keystore.jks,进入存在keystore的对应路径下并将文件名替换3.如果地图空白并且提示:AndroidManifest.xml的application中没有meta-_地图sensorm接口
文章浏览阅读882次。CentOS6.8合并DVD1和DVD2 下载链接:https://pan.baidu.com/s/1kti8zLbsiB45O6iBkrZ8CA 密码:7z1gCentOS一般都会提供DVD1和DVD2两个镜像文件,形如CentOS-6.8-x86_64-bin-DVD1.iso和CentOS-6.8-x86_64-bin-DVD2.iso,使用DVD1即可安装使用CentOS系统了,DVD..._centos6.8 yum 配置本地光盘源视频
文章浏览阅读3.8k次,点赞6次,收藏57次。文章目录MySQL——数据库调优整体策略1、数据库调优1.1、调优的目标1.2、确定调优的目标1.3、调优的维度和步骤2、MySQL服务器的优化2.1、优化服务器硬件2.2、优化MySQL服务的参数3、优化数据库结构3.1、拆分表:数据冷热分离3.2、增加中间表3.3、增加冗余字段3.4、优化数据类型3.5、优化插入记录的速度3.6、使用非空约束3.7、分析表3.8、检查表3.9、优化表4、大表优化4.1、限定查询范围4.2、读写分离4.3、垂直拆分4.4、水平拆分5、其它调优策略5.1、服务器语句超时处理_mysql数据库调优
文章浏览阅读7k次。 在安装操作系统时,缺省情况下会创建一个名为 rootvg 的卷组。使用一个或多个还未分配到其他卷组并且处于可用状态的物理卷,可以在系统上创建额外的卷组。所有物理卷都将划分为具有相同大小的物理分区。在创建卷组以后,物理分区的大小就不可更改。 IBM AIX 5.3 系统管理 -- 磁盘存储管理一 http://blog.csdn.net/tianlesoftware/archive/2011/0_gvg-012
文章浏览阅读1.5k次。do{}while(next_permutation(a+1,a+n+1));//a[]数组一定要是已经从小到大排序好的,才能遍历全排列排列组合常用公式:(1)证明 0!=1;(2)证明 C(n,m)=C(n,n-m);(3)证明 C(n+1,m)=C(n,m)+C(n,m-1);(4)证明 C(n,r)+C(n,r+1)=C(n+1,r+1);(5)证明 C(n,0..._1+c(n,2)+c(n,4)等于2的幂
文章浏览阅读695次。1、下载安装Charles, 2、安装好之后,、 3、打开菜单栏,选择“Proxy”,勾选“Starting Recording”和“Mac OS X Proxy”。 其中“Starting Recording”表示开始进行记录网络请求。 “Mac OS X Proxy”表示将系统代理设置通过此“Proxy”。 4、此时打开系统偏好设置,查看网络偏好设置。 点击高级,切换到“代理”,可..._mac charles记录设置怎么填
文章浏览阅读751次。不同行业不同公司不同岗位所用到的技术千差万别,所以该图谱不具有普适性。 该图谱基于笔者从业(电子商务/互联网金融后端)以来工作经验画出,具有一定的局限性,不过对于互联网行业Java研发知识体系具有一定的代表性。 该图谱目前只画出大概框架,各分支还有待完善及补充,后期也会不断更新。 ..._java用ltp提取文本关系并创建知识图谱
文章浏览阅读479次。在java中要想实现多线程,有两种手段,一种是继续Thread类,另外一种是实现Runable接口。对于直接继承Thread的类来说,代码大致框架是:class 类名 extends Thread{方法1;方法2;…public void run(){// other code…}属性1;属性2;… }先看一个简单的例子:/** * @aut_class producer implements runnable{ int count=0; public void run(){ while(co
文章浏览阅读510次。文章目录1、内存限制2、CPU限制1、内存限制2、CPU限制_kubernetes resource cpu limit