UC知道C语言 环形排序
来源：百度知道 编辑：UC知道 时间：2024/09/22 03:42:07
在图中的9个点上，空出中间的点。其余的点上任意填入数字1至8；1的位置固定不动。然后移动其余的数字，使1到8顺时针从小到大排序。移动的规则是：只能将数字沿线移向空白的点。编程显示数字的移动过程。
【提示】该问题的实质就是将以上3*3矩阵外面的8个格看成一个环，8个数字在环内进行排序。由于受题目要求的限制，要利用中间的空格进行排序，这样要求的排序算法与众不同。观察中间的点，它是唯一一个与其它8个点有连线的点，即为中心点。中心点的活动的空间最大，它可以向8个方向移动。充分利用中心点这一特性是算法设计成功的关键。
在找到1所在的位置后。其余各个数字的正确位置就是固定的。我们可以按照以下算法从数字2开始，一个一个地调整各个数字的位置。
1） 确定数字i应处的位置；
2） 从数字i应处的位置的位置开始，向后查找数字i现在的位置；
3） 若数字i现在的位置不正确，则将数字i从现在的位置（沿连线）移向中间的空格，而将原有的位置空出，依次将现有空格前的所有元素向后移动，直到将i应处的位置空出，把它移入再次空出中间的空格。
从数字2开始便使用以上过程，就可以完成全部数字的移动排序。
需要仔细考虑如何表示以上3*3矩阵，以及如何记录矩阵外边八个格构成环时的连接关系。力求简单，这样可以大大简化程序设计的难度。
【提示】该问题的实质就是将以上3*3矩阵外面的8个格看成一个环，8个数字在环内进行排序。由于受题目要求的限制，要利用中间的空格进行排序，这样要求的排序算法与众不同。观察中间的点，它是唯一一个与其它8个点有连线的点，即为中心点。中心点的活动的空间最大，它可以向8个方向移动。充分利用中心点这一特性是算法设计成功的关键。
在找到1所在的位置后。其余各个数字的正确位置就是固定的。我们可以按照以下算法从数字2开始，一个一个地调整各个数字的位置。
1） 确定数字i应处的位置；
2） 从数字i应处的位置的位置开始，向后查找数字i现在的位置；
3） 若数字i现在的位置不正确，则将数字i从现在的位置（沿连线）移向中间的空格，而将原有的位置空出，依次将现有空格前的所有元素向后移动，直到将i应处的位置空出，把它移入再次空出中间的空格。
从数字2开始便使用以上过程，就可以完成全部数字的移动排序。
需要仔细考虑如何表示以上3*3矩阵，以及如何记录矩阵外边八个格构成环时的连接关系。力求简单，这样可以大大简化程序设计的难度。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void Graph(char rect[9]);
int main()
{
int i,j,k;
char Cyc[9]={0};//Cyc[0]到Cyc[7]用于保存8个数，Cyc[8]为空白区
int CurNode=9,Temp;
srand((unsigned int)time(NULL));
for(i=0;i<8;i++)//随机产生序列
{
Cyc[i]=(rand()%8)+1;
if(CurNode==9 && Cyc[i]==1) CurNode=i;//记录数字1的位置
for(j=0;j<i;j++)
{
if(Cyc[i]==Cyc[j])
{
i--;
break;
}
}
}
printf("原始状态:\n");
Graph(Cyc);
printf("开始移动:\n");
for(i=2;i<=8;i++)//下一个要找的数
{
for(j=0;j<8;j++)//扫描找数
{
if(Cyc[j]==i)
{
Temp=(CurNode+1)%8;
if(i!=Cyc[Temp])//如果位置正确就不用再移
{
Cyc[8]=i;//移入中心区
Cyc[j]=0;
Graph(Cyc);
if(Temp!=j)
{
if(Temp>j) j+=8;
for(k=j;k>Te