数据结构实习报告 本文关键词：数据结构，实习报告
数据结构实习报告 本文简介：数据结构实习报告姓名：学号：班级：一、一元多项式计算1、题目要求：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。2、程序代码：#include#includetypedefstructPolynomial{floatcoef;intexpn;structP
数据结构实习报告 本文内容：
数据结构实习报告
姓
名：
学
号：
班
级：
一、一元多项式计算
1、题目要求：
能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。
2、程序代码：
#include
#include
typedef
struct
Polynomial{
float
coef;
int
expn;
struct
Polynomialnext;
}*Polyn,Polynomial;
//Polyn为结点指针类型
void
Insert(Polyn
p,Polyn
h){
if(p->coef==0)
free(p);
//系数为0的话释放结点
else{
Polyn
q1,q2;
q1=h;q2=h->next;
while(q2
q2=q2->next;
}
if(q2
free(p);
if(!q2->coef){
//系数为0的话释放结点
q1->next=q2->next;
free(q2);
}
}
else{
//指数为新时将结点插入
p->next=q2;
q1->next=p;
}
}
}
//Insert
Polyn
CreatePolyn(Polyn
head,int
m){
//建立一个头指针为head、项数为m的一元多项式
int
i;
Polyn
p;
p=head=(Polyn)malloc(sizeof(struct
Polynomial));
head->next=NULL;
for(i=0;icoef,Insert(p,head);
//调用Insert函数插入结点
}
return
head;
}//CreatePolyn
void
DestroyPolyn(Polyn
p){//销毁多项式p
Polyn
q1,q2;
q1=p->next;
q2=q1->next;
while(q1->next){
free(q1);
q1=q2;
//指针后移
q2=q2->next;
}
}
void
PrintPolyn(Polyn
P){
Polyn
q=P->next;
int
flag=1;
//项数计数器
if(!q)
{
//若多项式为空，输出0
putchar(
0
);
printf(“/n“);
return;
}
while
(q){
if(q->coef>0
//系数大于0且不是第一项
if(q->coef!=1
if(q->expn==1)
putchar(
X
);
else
if(q->expn)
printf(“X^%d“,q->expn);
}
else{
if(q->coef==1){
if(!q->expn)
putchar(
1
);
else
if(q->expn==1)
putchar(
X
);
else
printf(“X^%d“,q->expn);
}
if(q->coef==-1){
if(!q->expn)
printf(“-1“);
else
if(q->expn==1)
printf(“-X“);
else
printf(“-X^%d“,q->expn);
}
}
q=q->next;
flag++;
}//while
printf(“/n“);
}
//PrintPolyn
int
compare(Polyn
a,Polyn
b){
if(a
else
if(!a||a->expnexpn)
return
-1;
else
return
0;
}
else
if(!a
//a多项式已空，但b多项式非空
else
return
1;
//b多项式已空，但a多项式非空
}
//compare
Polyn
AddPolyn(Polyn
pa,Polyn
pb){
//求解并建立多项式a+b，返回其头指针
Polyn
qa=pa->next;
Polyn
qb=pb->next;
Polyn
headc,hc,qc;
hc=(Polyn)malloc(sizeof(struct
Polynomial));//建立头结点
hc->next=NULL;
headc=hc;
while(qa||qb){
qc=(Polyn)malloc(sizeof(struct
Polynomial));
switch(compare(qa,qb)){
case
1:
{
qc->coef=qa->coef;
qc->expn=qa->expn;
qa=qa->next;
break;
}
case
0:
{
qc->coef=qa->coef+qb->coef;
qc->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case
-1:
{
qc->coef=qb->coef;
qc->expn=qb->expn;
qb=qb->next;
break;
}
}//switch
if(qc->coef!=0){
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else
free(qc);
//当相加系数为0时，释放该结点
}
//while
return
headc;
}
//AddPolyn
Polyn
SubtractPolyn(Polyn
pa,Polyn
pb){//求解并建立多项式a+b，返回其头指针
Polyn
h=pb;
Polyn
p=pb->next;
Polyn
pd;
while(p){
//将pb的系数取反
p->coef*=-1;
p=p->next;
}
pd=AddPolyn(pa,h);
for(p=h->next;p;p=p->next)
//恢复pb的系数
p->coef*=-1;
return
pd;
}
//SubtractPolyn
int
main(){
int
m,n,flag=0;
float
x;
Polyn
pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL
printf(“请输入a的项数:“);
scanf(“%d“,pa=CreatePolyn(pa,m);//建立多项式a
printf(“请输入b的项数:“);
scanf(“%d“,pb=CreatePolyn(pb,n);//建立多项式a
//输出菜单
printf(“**********************************************/n“);
printf(“操作提示：/n/t1.输出多项式a和b/n/t2.建立多项式a+b/n/t3.建立多项式a-b/n“);
printf(“/t4.退出/n**********************************************/n“);
for(;;flag=0){
printf(“执行操作：“);
scanf(“%d“,if(flag==1){
printf(“多项式a：“);PrintPolyn(pa);
printf(“多项式b：“);PrintPolyn(pb);continue;
}
if(flag==2){
pc=AddPolyn(pa,pb);
printf(“多项式a+b：“);PrintPolyn(pc);
DestroyPolyn(pc);continue;
}
if(flag==3){
pd=SubtractPolyn(pa,pb);
printf(“多项式a-b：“);PrintPolyn(pd);
DestroyPolyn(pd);continue;
}
if(flag==4)
break;
if(flag4)
printf(“Error!!!/n“);continue;
}//for
DestroyPolyn(pa);
DestroyPolyn(pb);
return
0;
}
3、运行结果：
二、设计一个模拟计算器的程序
1、题目要求：
设计一个模拟计算器的程序
要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。
2、
程序代码：
#include
#include
#include
using
namespace
std;
class
calculator
{
public:
void
cal(string
s);
void
express();
int
legal(string
w);
private:
void
push();
void
pop();
bool
can();
int
StringToNumber(string
aStr);
int
number[1000];
char
symbolt[1000];
string
s,t;
int
i,j,p;
};
void
calculator::push()
{
p++;
symbolt[p]=s[i];
}
void
calculator::pop()
{
p--;
switch
(symbolt[p+1])
{
case
+
:{number[p]+=number[p+1];break;}
case
-
:{number[p]=number[p]-number[p+1];break;}
case
:{number[p]=number[p]*number[p+1];break;}
case
/
:{number[p]=number[p]/number[p+1];break;}
}
}
bool
calculator::can()
{
if
(((s[i]==
+
)||(s[i]==
-
))
if
(((s[i]==
)||(s[i]==
/
))
return
false;
}
int
calculator::StringToNumber(string
aStr)
{
int
number
=
0;
for
(int
i=0;i=
0
)
calculator
MyCal;
if(!MyCal.legal(w))
{
MyCal.cal(w);
MyCal.express();
}
char
chose;
cout>chose;
if
(chose==
n
||chose==
N
)
break;
}
return
0;
}
3、
运行结果：
三、Josephus问题
1、
题目要求：
设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。
2、
程序代码：
#include
#include
“malloc.h“#define
False
0
#define
TRUE
1
typedef
int
DataType;
struct
SeqList{
int
MAXNUM;
int
n;
DataTypeelement;
};
typedef
struct
SeqListPSeqList;
PSeqList
createNullList_seq(int
m){
PSeqList
palist=(PSeqList)malloc(sizeof(struct
SeqList));
if(palist!=NULL){
palist->element=(DataType*)malloc(sizeof(DataType)*m);
if(palist->element){
palist->MAXNUM=m;
palist->n=0;
return
palist;
}
else
free(palist);
}
printf(“Out
of
space!!/n“);
return
NULL;
}
int
insertPre_seq(PSeqList
palist,int
p,DataType
x){
/*在palist所指顺序表中下标为P的元素之前插入元素x*/
int
q;
if
(palist->n>=palist->MAXNUM){//溢出
printf(“Overflow!
/n“);
return
0;
}
if
(ppalist->n){
printf(“Not
exist!
/n“);
return
0;
}
for(q=palist->n-1;q>=p;q--)
palist->element[q+1]=palist->element[q];
palist->element[p]=x;
palist->n=palist->n+1;
return
1;
}
int
deleteP_seq(PSeqList
palist,int
p){
//删除下标为p的元素
int
q;
if
(ppalist->n-1){
printf(“Not
exist!
/n“);
return
0;
}
for(q=p;qn-1;q++)
palist->element[q]=palist->element[q+1];
palist->n=palist->n-1;
return
1;
}
void
josephus_seq(PSeqList
palist,int
s,int
m){
int
s1,i,w;
s1=s-1;
for(i=palist->n;i>0;i--){
s1=(s1+m-1)%i;
w=palist->element[s1];
printf(“Out
element
%d
/n“,w);
deleteP_seq(palist,s1);
}
}
main(){
PSeqList
jos_alist;
int
i;
int
n,s,m;
printf(“/nplease
input
the
values(element);
free(jos_alist);
}
}
3、
运行结果：
例如输入n＝8，s＝1，m＝4；结果如下：
14
篇2：数据结构实验报告
数据结构实验报告 本文关键词：数据结构，实验，报告
数据结构实验报告 本文简介：计算机科学与技术学院实验报告课程名称：数据结构专业：计算机科学与技术班级：2011级1班学号：201113137024姓名：镇方权指导老师：邱奕敏20实验一1.实验题目设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到
数据结构实验报告 本文内容：
计算机科学与技术学院
实验报告
课程名称：数据结构
专
业：计算机科学与技术
班
级：2011
级
1
班
学
号：
201113137024
姓
名：
镇方权
指导老师：
邱奕敏
20
实验一
1.
实验题目
设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
2.
程序核心代码
struct
LNode
{
int
data;
struct
LNodenext;
};
typedef
struct
LNodeLinkList;
LinkList
Union(
LinkList
ha,LinkList
hb
)
{
LinkList
head
=
(LNode*)malloc(sizeof(LNode));
head->next
=
ha;
LNode*
pa,*pb,*pTmp;
pa
=
ha->next;
pb
=
hb->next;
pTmp
=
ha;
while
(
pa
pa
=
pa->next;
}
else
if
(
pa->data
>
pb->data
)
{
LNode*
Lr
=
(LNode*)malloc(sizeof(LNode));
Lr->data
=
pb->data;
Lr->next
=
pa;
pTmp->next
=
Lr;
pTmp
=
Lr;
pb
=
pb->next;
}
else
{
pTmp
=
pa;
pa
=
pa->next;
pb
=
pb->next;
}
}
if
(
pa
)
{
pTmp->next
=
pa;
}
else
{
while
(
pb
)
{
LNode*
Lr
=
(LNode*)malloc(sizeof(LNode));
Lr->data
=
pb->data;
pTmp->next
=
Lr;
pTmp
=
Lr;
pb
=
pb->next;
}
pTmp->next
=
NULL;
}
free(head);
return
ha;
}
int
ListInsert(LinkList
L,int
i,int
e)
{
int
j=0;
LinkList
p=L,s;
while(p
j++;
}
if(!p||j>i-1)
return
0;
s=(LinkList)malloc(sizeof(struct
LNode));
/*
生成新结点/
s->data=e;
/*
插入L中/
s->next=p->next;
p->next=s;
return
1;
}
int
main()
{
LinkList
ha,hb;
int
n,i;
int
data;
InitList(
printf(“请输入ha中数据的个数：
“);
scanf(“%d“,printf(“请依次输入ha中的数据：/n“);
for(int
i
=
1;i
next;
while(p)
{
printf(“%d
“,p->data);
p
=
p->next;
}
printf(“/n“);
InitList(
printf(“请输入hb中数据的个数：
“);
scanf(“%d“,printf(“请依次输入hb中的数据：/n“);
for(i
=
1;i
next;
while(p)
{
printf(“%d
“,p->data);
p
=
p->next;
}
printf(“/n“);
printf(“hb归并到ha后，新的ha=“);
p
=
Union(ha,hb)->next;
while(p)
{
printf(“%d
“,p->data);
p
=
p->next;
}
printf(“/n“);
system(“pause“);
return
0;
}
3.
运行结果
4.实验总结
要注意归并时若ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
实验二
1.
实验题目
结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。
2.
程序核心代码
typedef
struct
LNode{
int
data;
//存储系数
int
flag;
//存储对应幂数
struct
LNodenext;
}LNode;
//建立带头结点的单链表，n项多项式
void
CreateList(LNode*L,int
n)
{
LNodep;
int
i
=
0;L
=
(LNode)
malloc
(sizeof(LNode));
(*L)->next
=
NULL;
for
(i
=
0;
idata),p->next
=
(*L)->next;
(*L)->next
=
p;
//插入链表
}
}
//多项式L1与L2对应项相加得到新的L2
void
PolyoAdd(LNode*L1,LNode*L2)
{
int
ck;
LNodep,*q;
p
=
NULL;
q
=
NULL;
q
=
(*L1)->next;
while(q)
{
ck
=
0;
p
=
(*L2)->next;
while(p)
{
if
(q->flag
==
p->flag){
ck
=
1;
break;
}
p
=
p->next;
}
if
(ck
==
1)
//同类项合并
{
p->data
+=
q->data;
q
=
q->next;
}
else
//否则，直接将非同类项插到L2最前面
{
(*L1)->next
=
q->next;
q->next
=
(*L2)->next;
(*L2)->next
=
q;
q
=
(*L1)->next;
}
}
}
int
main()
{
int
m=0;
LNodep1,*p2;
p1
=
NULL;
p2
=
NULL;
printf(“设定多项式A的项数：/n“);
scanf(“%d“,printf(“请输入多项式A的系数及对应位幂次：/n“);
CreateList(
printf(“A“);
PolyoPrint(
printf(“设定多项式B的项数：/n“);
scanf(“%d“,printf(“请输入多项式B的系数及对应位幂次：/n“);
CreateList(
printf(“B“);
PolyoPrint(
PolyoAdd(
printf(“相加后的“);
PolyoPrint(
system(“pause“);
return
0;
}
3.
运行结果
4.
实验总结
合并多项式是指相同指数的项的系数相加，比较两个链表的节点的指数的大小，作为指针移动的条件，同事合并的过程中应消除系数项为零的节点。
实验三
1.
实验题目
二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild
下标
data
lchild
rchild
1
A
2
6
2
B
3
4
3
C
0
0
4
D
5
0
5
E
0
0
6
F
0
7
7
G
0
0
和rchild的类型为bitree。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild
为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，二叉树的静态二叉链表如上图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。
2.
程序核心代码
typedef
struct
BiTNode
{
char
data;
struct
BiTNodelchild,*rchild;
}BiTNode,*BiTree;
typedef
struct
Node
//静态链表结点结构
{
char
data;
//结点数据
int
row,lchild,rchild
;
//下标，左右孩子
}Node;
Nodest;
//st容量足够大
static
int
length=0;
static
int
num=0;
void
createBiTree(BiTree
scanf(“%c“,if
(ch==
#
)
T
=
NULL;
else
{
if
(!(T
=
(BiTNode)malloc(sizeof(BiTNode))))
printf(“error“);
T->data
=
ch;
//
生成根结点
createBiTree(T->lchild);
//
构造左子树
createBiTree(T->rchild);
//
构造右子树
}
}
void
PreOrder(BiTree
bt)
//
先序遍历二叉树，填写静态链表的“下标”和data域
{
if
(bt)
{
st[++num].data=bt->data;
st[num].row=num;
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
int
Locate(char
x)
{
//在静态链表中查二叉树结点的下标
int
i;
{
for
(i=1;idata
==
x)
return
p;
if(p->lchild)
queue[rear++]
=
p->lchild;
if(p->rchild)
queue[rear++]
=
p->rchild;
}
}
}
void
DynaToST
(BiTree
t){
int
i;
BiTree
p;
PreOrder(t);
for(i
=
1;i
lchild)
st[i].lchild
=
Locate(p->lchild->data);
else
st[i].lchild=0;//无左孩子，其lchild域填0
if(p->rchild)
st[i].rchild
=
Locate(p->rchild->data);
else
st[i].rchild=0;//无右孩子，其rchild域填0
}
}
int
main(){
BiTree
t;
printf(“请输入二叉树各结点的值:/n“);
createBiTree(t);
nodeNum(t);
st
=
(Node*)malloc(sizeof(struct
Node)*length);
DynaToST(t);
show(st);
return
0;
}
3.
运行结果
4.
实验体会
二叉树的建立是按照先序遍历的方式递归的建立的，因此在输入二叉树的节点中的值时，要注意#字符的个数。
实验四
1.
实验题目
设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接表本身所占空间之外只用O（1）辅助空间。
2.
程序核心代码
struct
edgenode//表结点
{int
endver;
edgenode*
edgenext;
};
struct
vexnode//头结点
{
char
vertex;
edgenode
edgelink;
};
struct
Graph//无向图
{
vexnode
adjlists[Max_Ver_Num];
int
vexnum,arcnum;
};
void
CreatAdjList(Graph*
G)
{
int
i,j,k;
edgenode
p1;
edgenode
p2;
cout>G->vexnum>>G->arcnum;
coutvexnum;i++)
{
cin>>G->adjlists[i].vertex;
G->adjlists[i].edgelink=NULL;
}
coutarcnum;k++)
{
cout对应的顶点序号:“;
cin>>i>>j;
coutendver=j;
p1->edgenext=G->adjlists[i].edgelink;
//将结点始终插到表结点后
G->adjlists[i].edgelink=p1;
p2=new
edgenode;
p2->endver=i;
p2->edgenext=G->adjlists[j].edgelink;
G->adjlists[j].edgelink=p2;
}
}
void
DFS(GraphG,int
i,int
visited[])
{
coutadjlists[i].vertexadjlists[i].edgelink;
if(G->adjlists[i].edgelink
}
}
void
DFStraversal(GraphG,char
c)
{
coutvexnum;
i++)
{
visited[i]=0;
}
for
(int
i=1;ivexnum;i++)
{
if
(G->adjlists[i].vertex==c)
{
DFS(G,i,visited);
break;
}
}
for(int
i=1;ivexnum;i++)
{
if(visited[i]==0)
DFS(G,i,visited);
}
cout>Vi;
DFStraversal(G,Vi);
coutdata=number;
p->lchild
=p->rchild=NULL;
if(head==NULL)
{
return
p;
}
else
{
if(p->data
data)
head->lchild=createBST(head->lchild,number);
else
head->rchild=createBST(head->rchild,number);
return
head;
}
}
//求p的双亲
BiTree
searchParent(BiTree
head,BiTree
p)
{
if(head->lchild==p||head->rchild==p||head==p||head==NULL)
return
head;
else
{
if(p->data
data)
return
searchParent(head->lchild,p);
else
return
searchParent(head->rchild,p);
}
}
//删除二叉排序树中结点p
bool
Delete(BiTree
p){
BiTree
q,s;
q=(BiTree)malloc(sizeof(BiTNode));
s=(BiTree)malloc(sizeof(BiTNode));
if(!p->rchild
if(q->lchild==p)
q->lchild=NULL;
else
q->rchild=NULL;
}
else
if(!p->rchild){
//左子树不为空，右子树为空
searchParent(head,p)->lchild
=
p->lchild;
free(p);
}
else
if(!p->lchild){
//右子树不为空，左子树为空
searchParent(head,p)->rchild
=
p->rchild;
free(p);
}
else
{
//左右子树都不为空
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild;
}
p->data=s->data;
if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
delete
s;
}
return
true;
}
bool
deleteBST(BiTree
Head,int
number){
if(!Head)
return
false;
else{
if(Head->data
==
number)
return
Delete(Head);
else
if(number
data)
return
deleteBST(Head->lchild,number);
else
return
deleteBST(Head->rchild,number);
}
}
//主程序
int
main(){
BiTree
Head;
printf(“建立一棵二叉排序树,请输入你要建树的所有数(以-1
作为结束标志!):
/n“);
Head=NULL;
int
number,n;
scanf(“%d“,while(number!=-1)
{
Head=createBST(Head,number);
scanf(“%d“,}
head=Head;
printf(“中序遍历二叉排序树为：
/n“);
printBST(Head);
printf(“/n“);
printf(“请输入要删除的结点:
“);
scanf(“%d“,if(deleteBST(Head,n))
printf(“删除成功！/n“);
else
printf(“删除失败！/n“);
printf(“删除之后的二叉排序树中序遍历为：/n“);
printBST(Head);
printf(“/n“);
return
0;
}
3.
运行结果
4.
实验体会
二叉排序树的删除要注意分类讨论，删除的节点p为叶子节点时，不能简单的直接删除p，而要找到p的双亲节点，令双亲节点指向p的指针为NULL即可。
篇3：数据结构实习报告——国际象棋中马及遍历
数据结构实习报告——国际象棋中马及遍历 本文关键词：遍历，国际象棋，数据结构，实习报告
数据结构实习报告——国际象棋中马及遍历 本文简介：数据结构与VC编程实习实习报告学生姓名：学号：专业班级：指导教师：2012年7月14日实习题目在国际象棋棋盘上实现马的遍历一、任务描述及要求国际象棋的棋盘有8×8＝64个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可
数据结构实习报告——国际象棋中马及遍历 本文内容：
数据结构与VC编程实习
实习报告
学生姓名：
学
号：
专业班级：
指导教师：
2012年7月14日
实习题目
在国际象棋棋盘上实现马的遍历
一、任务描述及要求
国际象棋的棋盘有8×8＝64个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可以跳到（x±1，y±2）或（x±2，y±1）（所有的“±”之间没有相关性）。一般来说它下一步可以有八种跳法，但是它不能跳出这64个格子。
设计算法使它不管从哪出发都可以跳遍所有的格子（每个格子只能路过一次）最后回到起点。
1.基本要求：
合理设计界面，自行设计国际象棋棋盘，用鼠标选择马的起始位置，起始位置选定后，按“开始”按钮演示马的每一步行走路线。棋盘和马的显示尽量美观逼真。功能菜单或按钮自行设计，以合理为目的。
2.扩展要求：
对算法进行优化，根据j.c.Warnsdorff规则设计算法，该规则是在所有可跳的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数为最少；如果可跳的方格数相等,则从当前位置看,方格序号小的优先。
二、概要设计
1．抽象数据类型
本次实习中，我主要采用图的深度遍历知识和贪心算法来解决在国际象棋棋盘上实现马的遍历问题。棋盘上将64个格子视为64个点，将马从一个格子跳到另一个格子视为一条边，则共有168条边，那么可以将棋盘视为一个无向图，马在棋盘上按c.Warnsdorff规则跳动可视为图的深度遍历过程中的一步。
为了实现图的存储，需要建立顶点顺序表和邻接表，这个过程是在图的构造函数里实现的。图的操作主要包括：给出顶点vertex在表中的位置，给出顶点位置为
v
的第一个邻接顶点的位置，给出顶点v的邻接顶点w的下一个邻接顶点的位置，给出顶点位置为
v
的最优邻接顶点的位置。图的遍历算法是在视图类里面实现的。
图的抽象数据类型为：
ADT
Graph{
数据：顶点顺序表
关系:
邻接表表示了顶点之间的邻接关系
操作：①
给出顶点vertex在表中的位置
②
给出顶点位置为
v
的第一个邻接顶点的位置
③
给出顶点v的邻接顶点w的下一个邻接顶点的位置
④
给出顶点位置为
v
的最优邻接顶点的位置
}
由于贪心算法有时不能得到整体最优解，所以我设计了另一种遍历算法。由于要求遍历完所有点后要回到起点，则这是一条哈密顿回路，故可以事先找出这样的一种遍历序列并将其用点数组记录下来，以后在每次遍历时不论从哪个点出发都走这条路线，则一定能回到起点。此种遍历易于理解，下面不再详细介绍。
2．整个程序包含功能模块及模块间的调用关系
⑴
整个程序包含的主要功能模块：更换棋盘颜色，遍历起点的定位（鼠标定位、坐标定位和默认起点），在窗口的状态栏右边可以显示鼠标当前所处的坐标值以协助顶点的定位，棋盘上遍历过程的动态显示（图片（可更换）或路线），遍历顶点序列的打印，两种遍历方式（规则遍历（基于c.Warnsdorff规则的图的深度遍历）和固定遍历（按固定的路线遍历）），重新遍历。
⑵
模块间的调用关系：每次开始遍历之前可以更换棋盘的颜色、选择遍历过程的动态显示方式和遍历起点，然后选择规则遍历或固定遍历。开始遍历之后可以动态显示遍历过程，并打印遍历的顶点序列。在下一次遍历之前要选择重新遍历，并重新选择起点和遍历方式。实际上整个遍历是在开始动态显示遍历过程之前完成的，在遍历时将遍历序列用一维数组记录下来，遍历完之后利用此数组记录的序列来控制遍历过程的动态显示和遍历顶点序列的打印。
三、详细设计
1．虚拟实现（即数据结构的C++语言描述）
⑴
规则遍历中图的抽象数据类型的C++类定义为：
class
Edge
{
//边结点的定义
public:
int
dest;
//边的另一顶点位置，即下标
Edgelink;
//下一条边结点的指针
public:
Edge
(int
num=-1,Edgeptr=NULL):
dest
(num),link
(ptr)
{
}
//构造函数
};
struct
Vertex
{
//顶点的定义
E
data;
//顶点的名字
int
numEdge;
//此顶点当前关联的可走边数
bool
ver;
//标记此顶点是否被访问过
Edgeadj;
//边链表的头指针
};
class
Graph
{
//图的类定义
public:
VertexNodeTable;
//顶点顺序表
(各边链表的头结点)
int
numVertices;
//顶点个数
public:
Graph
();
//构造函数
~Graph();//析构函数
int
getVertexPos
(const
E
vertx);//给出顶点vertex在表中的位置
int
getFirstNeighbor
(int
v);
//给出顶点位置为
v
的第一个邻接顶点的位置
int
getNextNeighbor
(int
v,int
w);//给出顶点v的邻接顶点w的下一个邻接//顶点的位置
int
GetPriNeighbor(int
v);
//给出顶点位置为
v
的最优邻接顶点的位置
};
⑵
固定遍历中存储点的数组的定义：
CPoint
arr[64];
//存储马的固定行走回路路径，共64步
2．抽象数据类型中定义的操作算法实现（用伪代码描述）
此处只介绍求顶点位置为
v
的最优邻接顶点的位置的函数和图的深度遍历算法的伪代码：
⑴
int
GetPriNeighbor(int
v)的伪代码：
①若v存在则执行以下操作,否则返回-1；
②令min=9,w2=-1，w2记录最优邻接点；
③令w1为v的第一个邻接顶点的位置；
④当邻接顶点w1存在时执行以下操作:
⑤若
w1未被访问，则转到⑥，否则转到⑦；
⑥若min大于w1当前关联的可走边数numEdge则令min=
numEdge，令w2=w1；若min等于w1当前关联的可走边数numEdge，如果w2>w1则令w2=w1；
⑦令w1为v的邻接顶点w1的下一个邻接顶点的位置，转到④；
⑧
返回w2；
具体实现代码如下：
int
Graph::GetPriNeighbor(int
v)
{//给出顶点位置为
v
的最优邻接顶点的位置,如果找不到,则函数返回-1
if
(v
!=
-1)//顶点v存在
{
int
min=9,w2=-1;
//w2记录最优邻接点
int
w1
=
getFirstNeighbor
(v);
//获取第一个邻接顶点的位置
while
(w1
!=
-1)
//若邻接顶点w存在
{
if
(
!NodeTable[w1].ver
)
//w1未被访问
{
if(min>NodeTable[w1].numEdge)
{
min=NodeTable[w1].numEdge;//记录v的最优邻接顶点的当前关联的边数
w2=w1;
//从该方格出发,马能跳的方格数为最少
}
else
if(min==NodeTable[w1].numEdge)
{if(w2>w1)
w2=w1;
}
//如果可跳的方格数相等,则从当前位置看,方格序号小的优先
else
{}
}
w1
=
getNextNeighbor
(v,w1);
//获取下一个邻接顶点
}
return
w2;
}
return
-1;
}
⑵
void
DFS(Graph
//标记序号,存储下标
G.NodeTable[v].numEdge--;
//起始点被访问过则将其边数减1
if(k==64)
G.NodeTable[m].ver=false;
//k=64时将起始点标记为未被遍历,以便回到起始点
int
w
=
G.getFirstNeighbor
(v);
//获取第一个邻接顶点的位置
while
(w
!=
-1)
//若邻接顶点w存在
{
//if
(
!G.NodeTable[w].ver
)
//w未被访问
G.NodeTable[w].numEdge--;
//顶点各邻接点的边数都应减1
w
=
G.getNextNeighbor
(v,w);
//获取下一个邻接顶点
}
int
pw=G.GetPriNeighbor(v);
//给出顶点位置为
v
的最优邻接顶点的位置,如果找不到,则函数返回-1
if(pw!=-1)
dfs(G,pw,m);
//若最优邻接顶点存在,递归访问顶点pw
}
}
3．函数之间的调用关系
⑴
运行程序后调用视图类的OnDraw()函数在窗口中绘制棋盘。
⑵
在菜单栏的“操作”中点击“黄绿相间”
、“黑白相间”
、“恢复默认”菜单后分别调用视图类的OnMenuitemby()、OnMenuitembw()、OnSyschMenuitem()函数，在此函数中调用了Invalidate()函数，它自动调用OnDraw函数重新绘制窗口。
⑶
点击“图片”
、“路线”菜单后分别调用视图类的OnMaMenuitem()、OnRouteMenuitem()函数。
⑷
点击“更换图片”菜单调用视图类的OnDialog3()函数以弹出对话框，在对话框上点击单选按钮选择图片后，若点击“确定”按钮调用Dialog3类的OnOk3Button()函数，若点击“缺省设置”按钮则调用Dialog3类的OnPicsysButton()函数。
⑸
点击“鼠标定位”、“坐标定位”菜单后分别调用视图类的OnMouselocation()、OnMenuitemsys()函数，点击“坐标定位”
后弹出OnDialog2()对话框，设置起点后，若点击对话框上的“确定”“按钮后调用OnDialog2()类的OnOk2Button()
函数，在此函数中调用了UpdateData(TRUE)函数以刷新控件的值到对应的变量，若点击“缺省值”按钮则调用OnDialog2()类的OnSysButton()函数
关闭对话框后调用视图类的OnDialog2()函数。
⑹
点击“规则遍历”菜单或工具栏中的“J”图标后调用视图类的OnMenuitemstart()函数，此函数中调用了Graph类的构造函数Graph
()来建立图，也调用了视图类的图的深度遍历函数DFS()和显示图片或路线和遍历序列listnumber()函数。在DFS()中调用了Graph类的getVertexPos()和视图类的dfs
()函数，在dfs
()中又调用了Graph类的getFirstNeighbor()、getNextNeighbor
()、GetPriNeighbor()函数，也调用了它本身来形成深度遍历，也用到了遍历序列存储数组h[65]。在listnumber()中调用了视图类的picture()和route()函数和延时函数Sleep()，用以动态显示遍历过程，之后打印顶点的遍历序列并提示遍历成功与否。
⑺
点击“固定遍历”菜单或工具栏中的“S”图标后调用视图类的OnSolidMenuitem()和listnumber()函数,也用到了存储固定路径的点数组arr[64]和遍历序列存储数组h[65]。
⑻
点击“重新遍历”菜单或工具栏中的“T”图标后视图类的OnStopMenuitem()函数，在此函数中对遍历序列存储数组h[65]和全局变量进行了初始化，也调用了Invalidate()函数，它自动调用OnDraw函数重新绘制窗口。
四、调试分析
1．程序在调试过程中出现的问题及解决方法
我个人认为我在写程序之前时考虑得比较仔细，所以需要调试的地方比较少。以下是我在调试过程中出现的问题及解决方法：
⑴
实习期间的前几天我一直认为利用c.Warnsdorff规则设计出的图的深度遍历算法自己设计出算法后，通过窗口右侧显示的遍历序列发现算法不正确。为了解决这个问题，我先仔细得把程序读了几遍，觉得算法设计得不缜密，尤其是对当前遍历点和其邻接点的边数减少问题的考虑和对获取最优邻接点的函数的设计。经过改进后，还是不能得到理想的结果。于是我认为还是算法设计得有问题，所以我对程序进行了调试。经过反复地调试和改进，我觉得算法没有问题了，可是对于某些起始点遍历结果还是不正确。于是我开始怀疑利用c.Warnsdorff规则设计出的算法是不是一定能遍历到所有点并回到起点。在网上查询资料并与老师交流后发现自己前期的想法是错误的，实际上利用c.Warnsdorff规则在大多数情况下能够实现遍历，但并不能确保成功。经过再次深究自己设计的算法，我认为算法是正确的。
⑵
与老师探讨自己设计的算法后，老师要求我重新设计一种算法使得从任何一个点出发都可以遍历到所有点并回到起点，即利用事先已知的固定路线来遍历。在这个算法的设计过程中，也出现了遍历序列不正确的问题，序列的前一部分正确，后一部分错误。经过调试，发现在存储遍历序列的过程中用来控制点数组元素从arr[63]转到arr[0]的变量出了问题，修改之后，问题顺利解决。
2．算法的时间复杂度分析
⑴
图的深度遍历算法的时间复杂度分析：
设第i（1<=i<=64）个点的邻接点个数为Di,图的边数为e。则遍历算法第i个点的各邻接点的边数都减1的循环的时间代价是Di，获取最优邻接顶点的函数的时间代价也是Di，故深度遍历算法的总时间代价为2(D1+D2+…+D63+D64+Dj)=2
O(e)+2Dj，其中Dj是起点的邻接点个数。
⑵
固定路线遍历算法的时间复杂度分析：
设数组元素个数为n,则遍历算法中for循环、while循环和listnumber()函数的时间复杂度都为O(n),故固定路线遍历算法的时间复杂度为O(n)。
五、测试结果
根据一组提供的测试数据得到什么样的结果？
⑴
图的深度遍历算法的测试数据为：坐标值（7，8）
遍历序列：63，48，31，16，6，12，2，17，11，1，18，3，9，26，41，58，52，62，56，46，40，55，61，51，57，42，25，10，4，14，8，23，13，7，24，39，29，19，34，49，59，44，27，33，50，35，20，5，15，21，36，30，45，60，54，64，47，32，22，37，43，28，38，53，63
遍历结果正确！
⑵
固定路线遍历算法的测试数据为：坐标值（1，4）
遍历序列：25，10，4，14，8，23，6，16，31，48，63，53，59，49，34，17，2，12，29，19，9，3，13，7，24，39，56，62，47，64，54，60，50，33，18，1，11，5，15，32，22，28，38，21，27，44，61，55，40，46，52，37，43，58，41，26，20，35，45，30，36，51，57，42，25
遍历结果正确！
六、心得体会
为期九天的数据结构实习，感觉比平常的一个月都要漫长。这不仅仅是因为在考完试后的这九天中我依然早起晚睡，每天的工作量不亚于考前复习每天的工作量，每天对着电脑思考一些复杂的问题，更重要的是因为这九天我坚持下来了，学到了很多知识，锤炼了自己多方面的能力，增强了自己的毅力和信心，为以后的学习和工作奠定了很好的基础。
实习前我并没有做充分的准备，实习开始时老师只说了相关事项，并没有说怎么去做。所以，一切工作都得靠自己，自己利用网络和书籍去解决编程中遇到的问题，请教老师和同学也是很好的一种解决问题的方式，此时我才体会到了“书到用时方恨少”的含义。实习前期主要是对题目加以分析，设计实习作品的预期效果，查找资料并学习相关知识。由于缺乏独立解决问题的经验，以前接触的很少，所以这个阶段感觉比较费力。由于时间有限，所以实习中期知识基本上都是现学现用，而且还得自己设计算法解决相关问题。然而自己设计的算法并不一定正确，需要反复改进并反复测试，经过多次修改后结果还不正确时，自己会感到很失望，并且会动摇自己的信心，甚至想放弃。更令人头疼的是编程过程中会遇到很多错误，有时需要查阅相关资料，有时需要调试程序，所以这个阶段感觉相当费力，当然这个阶段多与老师和同学沟通是非常有必要的，在沟通中常常会有意想不到的收获。但当每一个问题得到解决时，都会令自己信心大增，都会展现出最灿烂的笑容，吃饭都觉得胃口好，睡觉也睡得安稳，于是更加坚定地接着做下去。实习后期主要是对程序进行优化，添加一些功能，验收程序并撰写实习报告。
实习期间一次次的失望对自己是一个很大的考验，但一次次的看到希望对自己则是莫大的肯定。当自己独立完成整个作品时，再回首整个实习期间遇到的问题和经受的苦难，感觉那也不算什么，并且觉得自己的付出是非常值得的，因为这是大学期间乃至整个人生中的一笔宝贵的财富。
指导教师评语及成绩
姓名
学号
评价项目
评
价
内
容
得
分
（百分制）
平时表现
(30%)
学习、工作态度(30%)
纪律性(30%)
综合运用知识能力(40%)
实习成果
(70%)
开题报告书写水平(15%)
成果(70%)
总分
评语：
指导教师（签名）：*年*月*日
