数据结构实验报告二.docx
- 文档编号:13819687
- 上传时间:2023-06-17
- 格式:DOCX
- 页数:26
- 大小:90.48KB
数据结构实验报告二.docx
《数据结构实验报告二.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告二.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构实验报告二
甘肃政法学院
本科生实验报告
()
姓名
学院:
专业:
班级:
实验课程名称:
实验日期:
指导教师及职称:
实验成绩:
开课时间:
2013-2014学年第二学期
甘肃政法学院实验管理中心印制
实验题目
第五章、递归
第六章数组和广义表
小组合作
否
姓名
班级
学号
一、实验目的
5.1求解n皇后问题
5.2求解背包问题
6.1求5x5阶螺旋方阵
6.2求一个矩阵的马鞍点
6.3求两个对称矩阵之和与乘积
6.4实现稀疏矩阵(采用三元组表示)的基本运算
6.5实现广义表的基本运算
二.实验环境
安装了Windows7操作系统,并且安装了MicrosoftVisualC++6.0。
三、实验内容与步骤
1、安装MicrosoftVisualC++6.0。
2打开MicrosoftVisualC++6.0
5.1求解n皇后问题
【编写一个程序exp5-1.cpp,求解皇后问题:
在nxn的方格棋盘上,放置n个皇后,要求每个皇后不同行、不同列、不同左右对角线。
(
皇后的个数n由用户输入,其值不能超过20。
采用递归方法求解。
)】
输入程序如下:
//文件名:
exp5-1.cpp
#include
#include
constintN=20;//最多皇后个数
intq[N];//存放各皇后所在的列号
intcount=0;//存放解个数
voidprint(intn)//输出一个解
{
count++;
inti;
printf("第%d个解:
",count);
for(i=1;i<=n;i++)
printf("(%d,%d)",i,q[i]);
printf("\n");
}
intplace(intk,intj)//测试(k,j)位置能否摆放皇后
{
inti=1;
while(i { if((q[i]==j)||(abs(q[i]-j)==abs(i-k))) return0; i++; } return1; } voidqueen(intk,intn)//放置1-k的皇后 { intj; if(k>n) print(n);//所有皇后放置结束 else for(j=1;j<=n;j++)//在第k行上穷举每一个位置 if(place(k,j))//在第k行上找到一个合适位置(k,j) { q[k]=j; queen(k+1,n); } } voidmain() { intn;//n存放实际皇后个数 printf("皇后问题(n<20)n="); scanf("%d",&n); if(n>20) printf("n值太大,不能求解\n"); else { printf("%d皇后问题求解如下: \n",n); queen(1,n); printf("\n"); } } 输入程序并运行,如图 5.2求解背包问题 【编写一个程序exp5-2.cpp,求解背包问题: 设有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的总重量不超过指定的限制重量,但选中物品的价值之和为最大。 编写一个程序求背包问题。 】 输入程序如下: //文件名: exp5-1.cpp #include #include constintN=20;//最多皇后个数 intq[N];//存放各皇后所在的列号 intcount=0;//存放解个数 voidprint(intn)//输出一个解 { count++; inti; printf("第%d个解: ",count); for(i=1;i<=n;i++) printf("(%d,%d)",i,q[i]); printf("\n"); } intplace(intk,intj)//测试(k,j)位置能否摆放皇后 { inti=1; while(i { if((q[i]==j)||(abs(q[i]-j)==abs(i-k))) return0; i++; } return1; } voidqueen(intk,intn)//放置1-k的皇后 { intj; if(k>n) print(n);//所有皇后放置结束 else for(j=1;j<=n;j++)//在第k行上穷举每一个位置 if(place(k,j))//在第k行上找到一个合适位置(k,j) { q[k]=j; queen(k+1,n); } } voidmain() { intn;//n存放实际皇后个数 printf("皇后问题(n<20)n="); scanf("%d",&n); if(n>20) printf("n值太大,不能求解\n"); else { printf("%d皇后问题求解如下: \n",n); queen(1,n); printf("\n"); } } 输入程序并运行,如图 图8 6.1求5x5阶螺旋方阵 【以下是一个5x5阶的螺旋方阵。 设计一个程序exp6-1.cpp输入该形式的nxn(n<10)阶方阵(顺时针方向旋进)。 】 输入程序如下: //文件名: exp6-1.cpp #include #defineMaxLen10 voidfun(inta[MaxLen][MaxLen],intn) { inti,j,k=0,m; if(n%2==0)//m=én/2ù m=n/2; else m=n/2+1; for(i=0;i { for(j=i;j { k++; a[i][j]=k; } for(j=i+1;j { k++; a[j][n-i-1]=k; } for(j=n-i-2;j>=i;j--) { k++; a[n-i-1][j]=k; } for(j=n-i-2;j>=i+1;j--) { k++; a[j][i]=k; } } } voidmain() { intn,i,j; inta[MaxLen][MaxLen]; printf("输入n(n<10): "); scanf("%d",&n); fun(a,n); printf("%d阶数字方阵如下: \n",n); for(i=0;i { for(j=0;j printf("%4d",a[i][j]); printf("\n"); } } 输入程序并运行,如图 图12 6.2求一个矩阵的马鞍点 【如果矩阵A中存在这样的一个元素A[i][j]满足条件: A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称为该矩阵的一个马鞍点。 设计一个程序exp6-2.cpp计算出mxn的矩阵A的所有马鞍点。 】 输入程序如下: //文件名: exp6-2.cpp #include #defineM4 #defineN4 voidMinMax(intA[M][N]) {inti,j; boolhave=false; intmin[M],max[N]; for(i=0;i { min[i]=A[i][0]; for(j=1;j if(A[i][j] min[i]=A[i][j]; } for(j=0;j {max[j]=A[0][j]; for(i=1;i if(A[i][j]>max[j]) max[j]=A[i][j]; } for(i=0;i for(j=0;j if(min[i]==max[j]) {printf("A[%d][%d]=%d\n",i,j,A[i][j]);//显示马鞍点 have=true; } if(! have) printf("没有鞍点\n"); } voidmain() {inti,j; intA[M][N]={{9,7,6,8},{20,26,22,25},{28,36,25,30},{12,4,2,6}}; printf("A矩阵: \n"); for(i=0;i {for(j=0;j printf("%4d",A[i][j]); printf("\n"); } printf("A矩阵中的马鞍点: \n"); MinMax(A);//调用MinMax()找马鞍点 } 运行程序,如图 6.3求两个对称矩阵之和与乘积 已知A和B为两个nxn阶的对称矩阵,输入时,对称矩阵只输入下三角元素,存入一维数组,设计一个程序exp6-3.cpp实现如下功能: (1)求对矩阵A和B的和。 (2)求对矩阵A和B的乘积。 输入程序如下: //文件名: exp6-3.cpp #include #defineN4 #defineM10 intvalue(inta[],inti,intj) { if(i>=j) returna[(i*(i-1))/2+j]; else returna[(j*(j-1))/2+i]; } voidmadd(inta[],intb[],intc[][N]) { inti,j; for(i=0;i for(j=0;j c[i][j]=value(a,i,j)+value(b,i,j); } voidmult(inta[],intb[],intc[][N]) { inti,j,k,s; for(i=0;i for(j=0;j { s=0; for(k=0;k s=s+value(a,i,k)*value(b,k,j); c[i][j]=s; } } voiddisp1(inta[]) { inti,j; for(i=0;i { for(j=0;j printf("%4d",value(a,i,j)); printf("\n"); } } voiddisp2(intc[][N]) { inti,j; for(i=0;i { for(j=0;j printf("%4d",c[i][j]); printf("\n"); } } voidmain() { inta[M]={1,2,3,4,5,6,7,8,9,10}; intb[M]={1,1,1,1,1,1,1,1,1,1}; intc1[N][N],c2[N][N]; madd(a,b,c1); mult(a,b,c2); printf("a矩阵: \n");disp1(a); printf("b矩阵: \n");disp1(b); printf("a+b: \n");disp2(c1); printf("a×b: \n");disp2(c2); printf("\n"); } 运行程序,如图 6.4实现稀疏矩阵(采用三元组表示)的基本运算 【假设nxn的稀疏矩阵A采用三元组表示: A[i][j]是第i行中值最小的元素,且又设计一个程序exp6-4.cpp实现如下功能: (1)生成如下两个稀疏矩阵的三元组: 10303000 01000400 00100010 00110002 (2)输出a转置矩阵的三元组; (3)输入a+b的三元组; (4)输入axb的三元组。 输入程序如下 //文件名: exp5-4.cpp #include #defineN4 typedefintElemType; #defineMaxSize100//矩阵中非零元素最多个数 typedefstruct {intr;//行号 intc;//列号 ElemTyped;//元素值 }TupNode;//三元组定义 typedefstruct {introws;//行数值 intcols;//列数值 intnums;//非零元素个数 TupNodedata[MaxSize]; }TSMatrix;//三元组顺序表定义 voidCreatMat(TSMatrix&t,ElemTypeA[N][N]) { inti,j; t.rows=N;t.cols=N;t.nums=0; for(i=0;i { for(j=0;j if(A[i][j]! =0) { t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } } } voidDispMat(TSMatrixt) { inti; if(t.nums<=0) return; printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums); printf("\t------------------\n"); for(i=0;i printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); } voidTranMat(TSMatrixt,TSMatrix&tb) { intp,q=0,v;//q为tb.data的下标 tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums; if(t.nums! =0) { for(v=0;v for(p=0;p if(t.data[p].c==v) { tb.data[q].r=t.data[p].c; tb.data[q].c=t.data[p].r; tb.data[q].d=t.data[p].d; q++; } } } boolMatAdd(TSMatrixa,TSMatrixb,TSMatrix&c) { inti=0,j=0,k=0; ElemTypev; if(a.rows! =b.rows||a.cols! =b.cols) returnfalse;//行数或列数不等时不能进行相加运算 c.rows=a.rows;c.cols=a.cols;//c的行列数与a的相同 while(i { if(a.data[i].r==b.data[j].r)//行号相等时 { if(a.data[i].c { c.data[k].r=a.data[i].r;//将a元素添加到c中 c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; } elseif(a.data[i].c>b.data[j].c)//a元素的列号大于b元素的列号 { c.data[k].r=b.data[j].r;//将b元素添加到c中 c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++;j++; } else//a元素的列号等于b元素的列号 { v=a.data[i].d+b.data[j].d; if(v! =0)//只将不为0的结果添加到c中 { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=v; k++; } i++;j++; } } elseif(a.data[i].r { c.data[k].r=a.data[i].r;//将a元素添加到c中 c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; } else//a元素的行号大于b元素的行号 { c.data[k].r=b.data[j].r;//将b元素添加到c中 c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++;j++; } c.nums=k; } returntrue; } intgetvalue(TSMatrixc,inti,intj) { intk=0; while(k =i||c.data[k].c! =j)) k++; if(k return(c.data[k].d); else return(0); } boolMatMul(TSMatrixa,TSMatrixb,TSMatrix&c) { inti,j,k,p=0; ElemTypes; if(a.cols! =b.rows)//a的列数不等于b的行数时不能进行相乘运算 returnfalse; for(i=0;i for(j=0;j { s=0; for(k=0;k s=s+getvalue(a,i,k)*getvalue(b,k,j); if(s! =0)//产生一个三元组元素 { c.data[p].r=i; c.data[p].c=j; c.data[p].d=s; p++; } } c.rows=a.rows; c.cols=b.cols; c.nums=p; returntrue; } voidmain() { ElemTypea1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}}; ElemTypeb1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}}; TSMatrixa,b,c; CreatMat(a,a1); CreatMat(b,b1); printf("a的三元组: \n");DispMat(a); printf("b的三元组: \n");DispMat(b); printf("a转置为c\n"); TranMat(a,c); printf("c的三元组: \n");DispMat(c); printf("c=a+b\n"); MatAdd(a,b,c); printf("c的三元组: \n");DispMat(c); printf("c=a×b\n"); MatMul(a,b,c); printf("c的三元组: \n");DispMat(c); } 运行程序,如图 6.5实现广义表的基本运算 设计一个程序exp6-5cpp实现广义表的各种运算,并在此基础上设计一个主程序完下功能: (1)建立广义表g=“b,(b,a,(#),d),((a,b),c,((#))))”的链式存储结构; (2)输入广义表的长度; (3)输入广义表的深度; (4)输入广义表的最大原子; 输入程序如下: //文件名: exp6-5.cpp #include #include typedefcharElemType; typedefstructlnode {inttag;//节点类型标识 union { ElemTypedata; structlnode*sublist; }val; structlnode*link;//指向下一个元素 }GLNode; GLNode*CreateGL(char*&s)//返回由括号表示法表示s的广义表链式存储结构 {GLNode*g; charch=*s++;//取一个字符 if(ch! ='\0')//串未结束判断 {g=(GLNode*)malloc(sizeof(GLNode));//创建一个新节点 if(ch=='(')//当前字符为左括号时 {g->tag=1;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告