数据结构八皇后问题实习报告（写写帮整理）

第一篇：数据结构八皇后问题实习报告（写写帮整理）

数据结构 实习报告

专业：数字媒体技术 姓名：李义 年级：2013级

学号：201301052015 完成日期：2015.12.31

题目：八皇后问题

一、项目简介

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在88格的国际象棋棋盘上，安放八个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，求解有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法得出结论，有92种摆法。

二、概要设计

2.1 主要模块：

这个程序主要由4个模块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模块，和解决如何摆置皇后模块。这4个模块隶属于主函数模块。既主函数通过对这4个模块的合理调用解决“8皇后问题”，同时这4个模块之间也互有调用。

2.2 程序设计的数据结构及其关系：

数据结构的实现：数组a[i]：a [i]表示第i个皇后放置的列；i的范围：1-8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；然后进行数据的初始化。从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:如果是，摆放第n个皇后，并宣布占领(切记要横列竖列斜列一起来)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当时，却发现此时已经无法摆放时，便要进行回溯。

三、详细设计

3.1 定义相关的数据类型： 3.1.1 定义的相关数据类型： int A[21],B[21],C[21],Y[8];void *buff1,*buff2 3.1.2 设计思想：

本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。特别是在对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生„„，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是：

判断该子树根的布局是否合法：如果合法的话，则先根遍历该子树；如果不合法的话，则剪去该子树的分支。

3.2 相关代码及算法

3.2.1 主模块C码算法： void main(void){

Queen Q;

int gdriver=DETECT,gmode;

initgraph(&gdriver,&gmode,“D://Win-TC”);

SetQueen(&Q);

setcolor(YELLOW);

QueenPic();

cleardevice();

setcolor(LIGHTGREEN);

settextstyle(0,0,3);

outtextxy(180,10,“Eight Queens”);

setcolor(WHITE);

settextstyle(0,0,1);

outtextxy(250,400,“2009.11.8 3:30pm”);

QueenRe(&Q,0);

getch();

closegraph();}

3.2.2 棋盘模块C码算法

void Checker(void)

/* 画棋盘函数 */ {

int i,k;

for(k=0;k<8;k++)

for(i=0;i<8;i++)

if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){

setfillstyle(SOLID_FILL,LIGHTBLUE);

setcolor(LIGHTBLUE);

rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);

floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else {

setfillstyle(SOLID_FILL,WHITE);

setcolor(WHITE);

rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);

floodfill(i*20+10,20+k*20+10,WHITE);} } 3.2.3 皇后模块C码算法：

void QueenPic(void)

/* 画皇后图象，然后存储到缓冲区 */ {

int size，polypoints1[10]={9,1,11,1,20,20,1,20,9,1}，polypoints2[10]={29,1,31,1,40,20,21,20,29,1};

setfillstyle(SOLID_FILL,LIGHTBLUE);

/* 画淡蓝色棋格 */ setcolor(LIGHTBLUE);

rectangle(1,1,20,20);

floodfill(10,10,LIGHTBLUE);

setfillstyle(SOLID_FILL,WHITE);

/* 画白色棋格 */

setcolor(WHITE);

rectangle(21,1,40,20);

floodfill(30,10,WHITE);

setfillstyle(SOLID_FILL,DARKGRAY);

setcolor(YELLOW);

drawpoly(5,polypoints1);

drawpoly(5,polypoints2);

floodfill(10,10,YELLOW);

floodfill(30,10,YELLOW);

size=imagesize(1,1,20,20);

/* 计算缓冲区大小，然后存储 */

buff1=(void *)malloc(size);

buff2=(void *)malloc(size);

getimage(1,1,20,20,buff1);

getimage(21,1,40,20,buff2);

cleardevice();} 3.2.4 八皇后摆放方法模块C码:

void QueenRe(Queen *Q, int y)

八皇后的递归算法

{int x;

if(y>7)

return;

for(x=0;x<8;x++)

if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])下一棵要遍历的子树由状态数确定

{

Q->Y[y]=x;放置皇后

Q->A[x+7]=1;标记下次这里不能放置皇后

Q->B[x+y+7]=1;标记下次这里不能放置皇后 Q->C[x-y+7]=1;标记下次这里不能放置皇后

if(y==7)

PrintQueen(Q);调用输出图形函数

QueenRe(Q,y+1);进入下一层递归

Q->A[x+7]=0;如果上次摆法导致后面不能继续摆放则重置标记为0

Q->B[x+y+7]=0;

Q->C[x-y+7]=0;

} } 3.2.5 初始化模块C码:

void SetQueen(Queen *Q)

/* 初始化 */ {int i;

for(i=0;i<21;i++)

{Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;初始化为0，表示可以放置皇后。} for(i=0;i<8;i++)

Q->Y[i]=-1;}

3.2.6 图形输出：

void PrintQueen(Queen *t)

/* 图形输出函数 */

{int k;

char str[20];

static total=0;

total++;

setviewport(240,80,400,260,1);

/* 设置窗口 */

sprintf(str,“NO.%d”,total);

setcolor(GREEN);

settextstyle(0,0,1);

outtextxy(0,0,str);

Checker();

for(k=0;k<8;k++)

if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)

putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);else

putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT);

getch();

if(getch()==27)exit(0);

clearviewport();}

void QueenRe(Queen *Q, int y)

/* 八皇后的递归算法 */ {int x;

if(y>7)

return;

for(x=0;x<8;x++)

if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍历的子树由状态数确定 */

{Q->Y[y]=x;

Q->A[x+7]=1;

Q->B[x+y+7]=1;

Q->C[x-y+7]=1;

if(y==7)

PrintQueen(Q);

QueenRe(Q,y+1);

/* 进入下一层递归 */

Q->A[x+7]=0;

Q->B[x+y+7]=0;

Q->C[x-y+7]=0;} } } 3.3函数调用图

3.4项目流程图

通过编译连接后，程序基本上把八皇后的92种摆法的都进行了演示；

但程

四、调试分析

序运行中也出现了以下缺点：

因为八皇后的表现方法甚多，输出后虽能全部显示，但未能使屏幕停留，把一个一个的将其显示出来,但是这样便使得操作步骤太多,也会造成不必要的麻烦!所以只画出了第一种和最后一种的输出结果，演示如图所示：

五、设计体会

该程序在调试的过程中出现了不少的问题！如数据溢出等（是自己过于粗心而造成的）。在调试的过程中出现的一个最大的问题就是：在运行的时候出现解的个数大于自己所预计的。经过不断的查看内存变量，操作次数但还是没有找出问题的所在。终于在晚上十二点的时候，决定睡觉！但一关上电脑，躺在床上的时候，突然想到了一个问题：经过读了一些资料，知道八皇后问题有12组实质解，92组全解——这说明在这12组实质解中有其中的一组解是比其它的解要特殊一点的：其它的解经过等价的变换之后都会产生8组等价的解，只有这个特殊的解只有4组等价的解。说不定我的问题就出在这里！我之前也写了一些有关的代码处理这个问题，但我之前以为这个特殊的解是一个完全中心对称的图形（每转90度得到的图形就是它自己本身），所以我的在这里的判断就出现错误了！后来经过相关代码的修改，问题终于解决了，程序正确运行。

本课程设计本人的目的也是通过用WIN-TC程序设计平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．最终将其问题变得一目了然，更加易懂。

六、用户使用说明

6.1 程序的使用平台：

系统要求：windows2000以上操作系统； 语言开发平台：WIN-TC； 6.2 源代码分析：

首先对程序中的函数头文件进行引入，定位；在这个程序中，与其他C++的程序一样，都是引入：#include；然后开始定义里面的函数所需要的数组，其中，setviewport(240,80,400,260,1);;是对总的棋盘状态数进行定位，记录。接着，进入了主函数，在主函数中，先对棋盘进行初始化，并规定了在程序输出时的情况；然后，对行列，对角线也进行了初始化；并在对这些元素初始后，对子函数进行调用； 进入子函数后，便马上对皇后放入的位置进行判断，通过语句的判断，如果没有冲突的话，则放下皇后，并标记，在下一次的时候，不再放入皇后；并在主从对角线进行判断，标记；然后再通过if语句判断，如果行还没有遍历完，进入下一行；接着通过放入一个for语句进行分析，如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置；当所有工作完成后，无冲突后，就返回主函数，并通过编译后对结果进行展示。

七、附录

#include #include #include #include #include

void *buff1,*buff2;typedef struct { int A[21],B[21],C[21],Y[8];} Queen;void SetQueen(Queen *Q)

/* 初始化 */ { int i;for(i=0;i<21;i++){ Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;} for(i=0;i<8;i++)Q->Y[i]=-1;} void QueenPic(void)

/* 画皇后图象，然后存储到缓冲区 */ { int size, polypoints1[10]={9,1,11,1,20,20,1,20,9,1}, polypoints2[10]={29,1,31,1,40,20,21,20,29,1};setfillstyle(SOLID_FILL,LIGHTBLUE);

/* 画淡蓝色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE);

/* 画白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20);

/* 计算缓冲区大小，然后存储 */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();} void Checker(void)

/* 画棋盘函数 */ { int i,k;

for(k=0;k<8;k++)for(i=0;i<8;i++)if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);} } void PrintQueen(Queen *t)

/* 图形输出函数 */ {int k;char str[20];static total=0;total++;setviewport(240,80,400,260,1);

/* 设置窗口 */ sprintf(str,“NO.%d”,total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k<8;k++)if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍历的子树由状态数确定 */ {Q->Y[y]=x;Q->A[x+7]=1;Q->B[x+y+7]=1;Q->C[x-y+7]=1;if(y==7)PrintQueen(Q);QueenRe(Q,y+1);

/* 进入下一层递归 */ Q->A[x+7]=0;Q->B[x+y+7]=0;Q->C[x-y+7]=0;} }

void main(void){ Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,“D://Win-TC”);SetQueen(&Q);setcolor(YELLOW);QueenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,“Eight Queens”);setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,“2009.11.8 3:30pm”);QueenRe(&Q,0);getch();closegraph();}

第二篇：数据结构实验报告--八皇后（写写帮整理）

数据结构实验报告

1．实验要求

实验目的：利用栈结构实现八皇后问题

八皇后问题如下：八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是，在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列，同一斜线上。

实验内容：利用所学的栈结构用递归或非递归解决八皇后问题。

2.程序分析

程序使用程序最主要只是在主函数用了一个递归函数Queen。

Queen函数使用了三个参数m,flag[][],chess[][]。其中m是行数，flag[][]是判断二维数组何处可以放置皇后，chess[][]是存储字符串的二维数组。

主函数中对Queen函数中的形参数组flag[][],chess[][]进行初始化，在Queen函数中再进行各种操作。

Queen函数执行代码，首先行数m为0，当m小于7时，通过if…else…语句，利用Queen(m+1,f,c)重新执行递归函数到下一行。

2.1 存储结构

存储结构：数组存储。

flag[][]数组存储数字判断输出和储能放置皇后,chess[][]数组存储字符串即皇后和非皇后的形状。

2.2 关键算法分析

1、关键算法： a．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

f[i][j]=0;

c[i][j]='*';

说明：对棋盘进行初始化 未放置皇后的为“*” b．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

c[i][j]=chess[i][j];

f[i][j]=flag[i][j];

} 说明：对c[][]，f[][]进行初始化。c．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

if(f[i][j]==0 &&(i+j==m+k || m==i || k==j || m-k==i-j))

f[i][j]=-1;

}

c[m][k]='#';

说明：已放置皇后的行、列以及对角线都不能再放置皇后。

已放置皇后的显示为“#”。d.if(m==7)

{

cout<<“算法的第”<<++count<<“个解为：”<

for(int i=0;i<8;i++)

{

for(int j=0;j<8;j++)

{

cout<

}

cout<

}

cout<

cout<

return;

}

else Queen(m+1,f,c);

说明：首先判断是否已执行到最后一行

每输出一个算法，count计数器加1 若没有执行到最后一行，m+1继续执行Queen函数

2.3 其他

要求程序在一开始创建一个统计算法解个数的加法器。

3.程序运行结果

1、测试主函数流程：流程图如图所示

2、测试结论：输出解决算法的个数及八皇后问题的图解。

4.总结

一．问题及解决办法

1.一开始编的时候对同一行，同一列以及同一斜行不能排皇后的算法不能准确编写，后来通过画图发现了这三个情况数组行标和列标的特点，从而解决了这个问题。

2.程序只能输出从65至99的解，其他解不显示，后来发现是因为界面太小的原因。二．心得体会

对于刚学的栈表以及递归函数一定要多用才能熟悉，才能知道实现的具体细节问题。对一些出现的错误一点要仔细分析，明白以后就会掌握的很牢固。对于递归函数一定要充分理解它的意义才能用好它。

在编写代码中如果对于一些抽象的算法构思感到困难，可以通过画图，在纸上先进行演算推导出各变量之间的关系，再进行编写可能会使问题变得简单明了一些。三．改进

递归算法解决八皇后问题比较简单明了，下次可以尝试不使用递归而用非递归编写算法，这样可能会更牢固更好的掌握栈的思想，巩固已学的知识。

第三篇：哈尔滨理工大学信管专业数据结构课程实践报告之八皇后问题 优秀案例

数据结构课程设计

学院：管理学院班级：信息 11-2班

数据结构课程设计八皇后问题

一、内容

设计程序完成如下要求：在8×8的国际象棋棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。

要求：(1)依次输出各种成功的放置方法。(2)最好能画出棋盘的图形形式，并在其上动态地标注行走的过程。(3)程序能方便地移植到其他规格的棋盘上。

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，根据国际象棋的规定，皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。在8!=40320种排列中共有92种解决方案。

二、本程序需要解决的问题

1、建立合适的数据类型表示皇后在棋盘上所处的位置。

2、成功的输出全部正确的放置方法。

3、画出棋盘形式，在上面动态的标注其行走的过程。

4、预期目标：运用C++程序设计的编程思想编写代码，实现八皇后问题的所有（92种）摆放情况。

三、数据结构的选择和概要设计

1、为了简单易行的表示皇后在棋盘所处的位置，在此建立一个整型数组queen[i]来表示，若queen[3]=2则表示皇后处在8×8棋盘的第三行和第二列。

2、列：规定每一列放一个皇后，就不会造成列上的冲突；行：当第i行被某个皇后占据时，该行所有空格就都不能放置其他皇后；对角线：对角线有两个方向，在同一对角线上的所有点都不能有冲突。

四、代码编写

第一种：

#include

#define true 1

#define false 0

int a[9],b[17],c[17];

int s[9];

void main()

{

void print(),movequeen(),eightqueen();

eightqueen();

}

void print()

{

int k;

printf(“n行号:123456

printf(”列号:“);

for(k=1;k<=8;k++)

printf(”%4d“,s[k]);printf(”n“);

}

void movequeen(int i,int j)

{

a[j]=1;b[i+j]=1;c[i-j+9]=1;

}

void eightqueen()

{

int i,j;

for(i=2;i<=16;i++)

{

if(i>=2 && i<=9)

a[i-1]=true;

b[i]=true;

c[i]=true;

}

i=1;j=1;

while(i>=1)

{

while(j<=8)

{

if(a[j] && b[i+j] && c[i-j+9])break;

j++;

}

if(j<=8)78n”);

a[j]=false;

b[i+j]=false;

c[i-j+9]=false;

s[i]=j;

if(i==8)

{

print();

movequeen(i,j);

i--;

j=s[i];

movequeen(i,j);

j++;

}

else

{

i++;

j=1;

}

}

else

{

i--;

if(i>=1)

{

j=s[i];

movequeen(i,j);

j++;

}

}

}

}

运行结果：以行号和列号的形式出现92种结果。

第二种：

#include

static char Queen[8][8];

static int a[8];

static int b[15];

static int c[15];

static int iQueenNum=0;//记录总的棋盘状态数

void qu(int i);//参数i代表行

{

int iLine,iColumn;

//棋盘初始化，空格为*，放置皇后的地方为@

for(iLine=0;iLine<8;iLine++)

{

a[iLine]=0;//列标记初始化，表示无列冲突

for(iColumn=0;iColumn<8;iColumn++)

Queen[iLine][iColumn]='*';

}

//主、从对角线标记初始化，表示没有冲突

for(iLine=0;iLine<15;iLine++)

b[iLine]=c[iLine]=0;

qu(0);

return 0;

}

void qu(int i)

{

int iColumn;

for(iColumn=0;iColumn<8;iColumn++)

{

if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)

//如果无冲突

{

Queen[i][iColumn]='@';//放皇后

a[iColumn]=1;//标记，下一次该列上不能放皇后

b[i-iColumn+7]=1;//标记，下一次该主对角线上不能放皇后

c[i+iColumn]=1;//标记，下一次该从对角线上不能放皇后if(i<7)qu(i+1);//如果行还没有遍历完，进入下一行

else //否则输出

{

//输出棋盘状态

int iLine,iColumn;

printf(“第%d种状态为：n”,++iQueenNum);

for(iLine=0;iLine<8;iLine++)

{

for(iColumn=0;iColumn<8;iColumn++)

printf(“%c ”,Queen[iLine][iColumn]);

printf(“n”);

}

printf(“nn”);

}

//如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置Queen[i][iColumn]='*';

a[iColumn]=0;b[i-iColumn+7]=0;c[i+iColumn]=0;}

}

}

运行结果：出现92种状态。

第四篇：数据结构实习报告

数据结构课程设计的实习报告怎么写呀，请求做过课设的同学发一篇范文过来谢谢-_-规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：

1、需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确地输入及其输出结果和含有错误的输入及其输出结果，数据结构实习报告。

2、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3、详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。

4、调试分析内容包括：(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进思想；(3)经验和体会等，实习报告《数据结构实习报告》。

5、用户使用说明说明如何使用你编写的程序，详细列出每一步操作步骤。

6、测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。

7、附录题目：约瑟夫-实习报告尺寸：约瑟夫-实习报告.doc目录：

一、需求分析

二、概要设计

三、程序具体设计及函数调用关系

四、调试分析

五、测试结果原文：实习报告题目：约瑟夫(Joseph)问题的一种描述是：编号为1，2，.，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。试设计一个程序求出出列顺序。班级：姓名：学号：完成日期：

一、需求分析1.本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据(即n个人的编号和密码)。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。3.程序执行的命令包括：1)构造单向循环链表；2)4.测试数据m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6(正确的出列顺序为6，1，4，7，2，1，3，5)。

二、概要设计1.单向循环链表的抽象数据类型定义为：ADT List{数据对象：D={ai|ai∈正整数，I=1，2，.，n,n≥0}数据关系：R1={ai-1，ai|，ai-1，ai∈D,I=1，2，.，n}基本操作：Init List(&L)操作结果：构造一个空的线性表L。List Insert(&L,i,e)初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。List Delete(&L,i,&e)初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。2.程序包含四个模块：1)主程序模块：void main(){.

第五篇：数据结构实习报告

数据结构第六次作业p134

——11411203张玉

24.template

void SeqQueue::EnQueue(const T& x){//插入函数

if(IsFull()==true){

maxSize=2*maxSize;

elements[rear]=x;

rear=(rear+1)%maxSize;

}

elements[rear]=x;

rear=(rear+1)%maxSize;

};

template

bool SeqQueue::DeQueue(const T& x){//删除函数if(IsEmpty()==true)return false;

if(rear<=maxSize/4){

maxSize=maxSize/2;

x=elements[front];

front=(front+1)%maxSize;

}

x=elements[front];

front=(front+1)%maxSize;

return true;

};

29.// 利用优先级队列实现栈和队列

#include

template class PQueue;//前视的类定义

template class Stack;

template class Queue;//优先级队列结点类的定义 template

class PQueueNode

{

friend class PQueue;//PQueue类作为友元类定义friend class Stack;

friend class Queue;

public:

PQueueNode(T &value, int newpriority, PQueueNode priority(newpriority), link(next){}//构造函数 * next):data(value),virtual T GetData(){ return data;}//取得结点数据

virtual int GetPriority(){ return priority;}//取得结点优先级

virtual PQueueNode * GetLink(){ return link;}//取得下一结点地址

virtual void SetData(T& value){ data = value;}//修改结点数据

virtual void SetPriority(int newpriority){ priority = newpriority;} //修改结点优先级

virtual void SetLink(PQueueNode * next){ link = next;}//修改指向下一结点的指针 private:

T data;//数据

int priority;//优先级

PQueueNode *link;//链指针

};

//优先级队列的类定义

template

class PQueue

{

friend class Stack;

friend class Queue;

public:

PQueue():front(NULL), rear(NULL){}//构造函数

virtual ~PQueue(){ MakeEmpty();}//析构函数

virtual void Insert(T &value, int newpriority);//插入新元素value到队尾 virtual T Remove();//删除队头元素并返回 virtual T Get();//读取队头元素的值 virtual void MakeEmpty();//置空队列

virtual int IsEmpty(){ return front == NULL;}//判队列空否private:

PQueueNode *front, *rear;//队头指针, 队尾指针

};template

void PQueue::MakeEmpty()

{

//将优先级队列置空

PQueueNode *q;

while(front!= NULL)//链不空时, 删去链中所有结点

{

//循链逐个删除

q = front;

front = front->link;

delete q;

}

rear = NULL;//队尾指针置空

}template

void PQueue::Insert(T &value, int newpriority)

{

//插入函数

PQueueNode *q = new PQueueNode(value, newpriority, NULL);if(IsEmpty())

front = rear = q;//队列空时新结点为第一个结点

else

{

PQueueNode *p = front, *pr = NULL;//寻找q的插入位置

while(p!= NULL && p->priority >= newpriority)//队列中按优先级从大到小链接{

pr = p;

p = p->link;

}

if(pr == NULL)

{

//插入在队头位置

q->link = front;

front = q;

}

else

{

q->link = p;

pr->link = q;//插入在队列中部或尾部

if(pr == rear)

rear = q;

}

}

}

//删除队头元素并返回

template

T PQueue::Remove()

{

if(IsEmpty())

return NULL;PQueueNode *q = front;

front = front->link;//将队头结点从链中摘下

T &retvalue = q->data;

delete q;

if(front == NULL)

rear = NULL;return retvalue;

}

//读取队头元素的值

template

T PQueue::Get()

if(IsEmpty())

return NULL;

else

return front->data;

}

//(1)栈的定义与实现

template

class Stack:public PQueue

{

//栈类定义

public:

Stack():PQueue(){} //构造函数

void Insert(T & value);//插入新元素value到队尾

};template

void Stack::Insert(T & value)

{

//插入函数

PQueueNode *q = new PQueueNode(value, 0, NULL);if(IsEmpty())front = rear = q;//栈空时新结点为第一个结点

else

{

//插入在前端

q->link = front;

front = q;

}

}//--------------------------Queue //(2)队列的定义与实现

template

class Queue:public PQueue

{

//队列类定义

public:

Queue():PQueue(){}//构造函数

void Insert(T & value);//插入新元素value到队尾

};template

void Queue::Insert(T & value)

{

//插入函数

PQueueNode *q = new PQueueNode(value, 0, NULL);

if(IsEmpty())

front = rear = q;//队列空时新结点为第一个结点

else

rear = rear->link = q;//插入在队尾位置

void main(){

Stack aStack;Queue aQueue;

int n = 1;

aStack.Insert(n);aQueue.Insert(n);}