数据结构课程设计
(Java)
题目:九宫排序问题
学号:200808204139
姓名:朱刚
时间:2022/6/20
一. 实验要求:
实现九宫算法排序问题,分别实现人机交互版和演示版。为人机交互版设计图形
用户界面,显示九宫图的状态,并通过鼠标或键盘上下左右键控制数据移动。
二.实验过程:
1. 题目分析:
一个 的棋盘,初始状态有一个位置空着,其他位置元素为 之中的随机一个。
移动各位置元素,使他们成为按 图排序的状态,元素移动的限制是,只能将与空
位置相邻的元素移入空位置。演示版给出移动步伐,或不能移动信息。
→
我采用了一个 元数组 来描述九宫图的每一个
状态。将九宫图的九个格子依次编号为 、、、、、、、、。数组中的
代表空格位于九宫图的那个格子, 九个元素代表了九个格子上分别是什
么将牌。例如,数组就代表了如下的状态:
.
用 编写九宫重排问题游戏。游戏规则是可随机产生或由用户设置初始状态
由初始状态出发不断地在空格上下左右的数码移至空格若能排出目标状态则成
功。为了避免对无解节点进行无用搜索首先对初始节点进行逆序数分析对有解
的节点进行搜索从而节省了资源也提高了效率。
2. 应用算法设计:
①首先要搭建图形界面框架,要用到 的知识。
自定义的类 类继承( !") 类,完成主界面的设计和监听所
有事件(包括 #$%& 事件和 &$" 事件);'(&! 类定义了节点的构造方法及
操作;)*!+" 类定义了搜索过程中用到的链表结构及相关操作; &&)$, 类定
义了系统中要用到的一些公用函数;!"-).' /) 类定义了问题状态的显示。
0/1 中的类2#$%& 类完成与用户的交互实现随机生成初始状态、设置初始
状态 、单 步演 示和 手动 游戏 3+" 类显 示单 步演 示时 每一 步的 具体 的操 作 3
)! 类显示系统工作状态及其它信息;+) 类显示标题。
-$),,)"" !"4
56, 6$7&7898944:4:4::3
56, 6$7&7898944:4:4::3
56, &6894;<" ;;",&!;; =!;:3
/),& /3
/)6/)>/)3
/)6/)>/)3
?)6?)>?)3
?)6?)>?)3
#$%&6#$%&>#$%&3
#$%&6#$%&>#$%&3
#$%&6#$%&>#$%&3
+)6+)>+)3
+)6+)>+)3
',&))/6',&))/>',&))/3
? 6? >? 3
@A$) ?)&!)",>@A$) ?)&!)6$7&7&63
@A$) ?)&!)!" >@A$) ?)&!)6$7&7&63
-$),4
.4
" @A$) B)&"5-C&DE1?F5(FB+5'D3
61 3
:, ,=D,-C&,-C&4
,-C&G- ' ,*?,3
:
:
-0 0&!61 =&>"D,-C&4
,& //)7 B& /3
,& /G" +.&$ $))3
="G7 B& /G" #,*7&$!B&)&G-*3
" 'H>@"&3
,& /G" #,*7&$!B&)&G-*3
6+)G" ? ;初始状态:;3
6+)G" & >60G> G& ;宋体;& G/+1(3
6+)G" #&$!"3
6+)G" & >60G> G& ;宋体;& G/+1(3
6+)G" ? ;目标状态:;3
6+)G" #&$!"3
6#$%&G" ? ;广度优先搜索;3
6#$%&G" #&$!"3
6#$%&G" & >60G> G& ;宋体;& G/+1(3
6#$%&G!!,C&+" >,C&+" 4
-$),0&!,C&/A&!,C&D0 4
",@A$) ?)&!)6?)G7 &!)3
!" @A$) ?)&!)6?)G7 &!)3
#! =" ',=G#! =F" F',=G ="",!" 3
:
:3
6#$%&G" ? ;随机;3
6#$%&G" #&$!"3
6#$%&G" & >60G> G& ;宋体;& G/+1(3
6#$%&G!!,C&+" >,C&+" 4
-$),0&!,C&/A&!,C&D0 4
I!&!&>I!&3
.894:3
3
A& 3J3KK4
A& 636J36KK4
>=) =&!G1"--.!&G 1 K63
.8K693
",G" )$ 63
:
:
:
:3
6#$%&G" ? ;随机;3
6#$%&G" #&$!"3
6#$%&G" & >60G> G& ;宋体;& G/+1(3
6#$%&G!!,C&+" >,C&+" 4
-$),0&!,C&/A&!,C&D0 4
I!&!&>I!&3
.894:3
3
A& 3J3KK4
A& 636J36KK4
>=) =&!G1"--.!&G 1 K63
.8K693
!" G" )$ 63
:
:
:
:3
6/)G" #,*7&$!B&)&G-*3
6/)G" #&$!"3
6/)G" #,*7&$!B&)&G-*3
6/)G" #&$!"3
6? G" & >60G> G& ;宋体;& G/+1(3
6',&))/G" #&$!"3
6?)>?)",3
6?)G" & >60G> G& ;宋体;& G/+1(3
6?)G" $ &I"H&!?)GL?5FID'1MDF53
6?)>?)!" 3
6?)G" & >60G> G& ;宋体;& G/+1(3
6?)G" $ &I"H&!?)GL?5FID'1MDF53
A& 3J3KK4
6?)G7 B&)$&!)G7 B&)$G" /A!N! =3
6?)G7 B&)$&!)G7 B&)$G" /A!N! =3
:
6?)G" I&>O7= 3
6/)G!!6?)3
6?)G" I&>O7= 3
6/)G!!6?)3
6',&))/G7 >-& G!!6? 3
,& /G!!6/)3
,& /G!!6/)3
,& /G!!6#$%&3
,& /G!!6#$%&3
,& /G!!6#$%&3
,& /G!!6+)3
,& /G!!6+)3
,& /G!!6',&))/3
:
:
②其次是定义发射器函数,定义的发生器函数由以下的四种操作组成:
将当前状态的空格上移
将当前状态的空格下移
将当前状态的空格左移
将当前状态的空格右移
以上的发生器函数,我在程序中(60)分别采用了几个类方法来实现。一个
结点最多能够扩展出 个结点,而扩展出的结点也不一定就会被采用,这与具体
情况有关。
public class Method {
-$)," C,&&)/ . 894
&&)- . $3
A& 3JG)7 =3KK4
*3
A& 6K36JG)7 =36KK4
A8*9P8694
*63
:
:
A*Q4
-3
-893
898*93