数据结构课程设计报告格式

数据结构课程设计报告题目：求矩阵的所有马鞍点—依次搜索法班级：软件092班姓名：….指导教师：….成绩：_________信息工程学院2011年6月13日摘要(题目):求矩阵的所有马鞍点。

矩阵A中的元素若满足：A[i,j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称元素A[i,j]为该矩阵的一个马鞍点。

求出m×n矩阵的所有马鞍点。

目录第一章引言 (2)第二章需求分析 (3)第三章概要设计 (3)第四章详细设计 (4)第五章测试结果 (6)第六章调试分析 (10)第七章设计体会 (11)第八章结束语 (11)第九章附录（源代码） (11)1.引言马鞍点的定义1.若矩阵Am×n的某个元素ai,j是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵中的一个马鞍点。

根据马鞍点的定义,马鞍点一定等于其所在行的最小值,因此,只需判断和每行最小值相等的元素是否为马鞍点即可;根据上述性质,若已找到一个马鞍点saddle,则其他马鞍点的值一定等于saddle,此时先比较一行中的最小值是否等于saddle,若不等,则该行不存在马鞍点;若相等,需进一步判断和该行最小值相等的元素是否是其所在行的最大值。

2.依次搜索法首先扫描矩阵,求出每行的最小值,存入min数组中相应的单元;第二次扫描矩阵,求出每列的最大值,存入max数组中的相应单元;第三次扫描矩阵,找出所有的马鞍点。

对于第i行,若f=1,即已找到一个马鞍点,只需将min[i]和马鞍点的值saddle进行比较,若不相等,则该行不存在马鞍点,继续扫描下一行;若相等,需进一步判断和min[i]相等的元素是否等于其所在列的最大值,若是,则为马鞍点,否则不是。

若f=0,即还未找到马鞍点,须判断和min[i]相等的所有元素是否等于其所在列的最大值,若是,则为马鞍点,令f=1,saddle为马鞍点的值,否则不是。

3.算法思想对于矩阵的每一行,扫描第一遍求出该行的最小元素值;扫描第二遍,对于和最小元素值相等的每个元素(可能是马鞍点),扫描其所在列,若是该列的最大元素值,则为马鞍点,输出该元素的信息。

2.需求分析本程序主要的任务是遍历二维数组，找出数组中行最小列最大的元素，称为马鞍点。

（1输入形式为自定义数组大小以及输入数组内容（整形数字），输出范围为数组中的数。

（2输出形式为第i行第j列为马鞍点（3程序能达到输出数组中的马鞍点3.概要设计程序中定义的抽象数据类型：int（整形）。

1. 流程模块（1）随机生成数组：计算机随机初始化二维数组。

（2）手动生成数组：自己有目的的初始化一个二维数组，求出需要的马鞍点。

（3）循环查找马鞍点：通过循环查找找出马鞍点。

（4）没有马鞍点再重复：查找后没有找到马鞍点，将继续从新初始化。

4.详细设计算法：1.计算机自动初始化一个二维数组void Automatic(int line,int row)//数组的随机生成函数{int i,j;srand((unsigned)time(NULL));//以当前时间做种子for(i=0;i<line;i++)//行for(j=0;j<row;j++)//列A[i][j]=rand()%10;//随机获取0-9之间的数cout<<"随机生成矩阵里的数据"<<endl;for(i=0;i<line;i++)for(j=0;j<row;j++){if(j==row-1) cout<<A[i][j]<<endl;else cout<<A[i][j]<<" ";} cout<<endl;cout<<setiosflags(ios::right)<<setw(40)<<"矩阵已经自动建立完毕！"<<endl<<endl;算法2；手动初始化一个二维数组；void Manual(int line,int row){ int i,j;int a[256][256];for( i =0 ;i < line ;i++)for( j =0 ;j < row; j++)scanf("%d",&a[i][j]);for( i =0 ;i < line ;i++){ for( j =0 ;j <row; j++)printf("%4d",a[i][j]);printf("\n");}算法3使用for语句进行查找马鞍点void maan(int line,int row){int a[256][256];int l, maxx;int k,minn,flag,h=0;for( int i = 0; i < line ;i++)for( int j = 0; j < row; j++){minn = a[i][j];for( k = 0 ;k < row; k++)if( minn > a[i][k])break;if( k == row){maxx = a[i][j];for( l = 0; l < line; l++)if( maxx < a[l][j])break;if( l == line){printf("%d %d %d\n",i , j ,a[i][j]);flag = 1;}}}if( flag == 0)printf("此矩阵没有马鞍点\n");}算法4；退出时的界面算法void exit(){cout<<endl<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆欢迎检查魏任恩的数据结构课程设计实验★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆感谢您的检查★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆若有什么错误的地方请老师校正★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆谢谢！★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━+━━━━━━━━━━━━━━━━━━━━"<<endl;system("pause");}}5.测试结果6.调试分析若在一个矩阵中存在多个马鞍点,则这些马鞍点的值必相同;反之,和马鞍点值相等的元素,不一定是马鞍点例如矩阵A[m][n]中存在马鞍点,马鞍点为A[x][y]。

根据马鞍点的定义,该元素是其所在行的最小值,是其所在列的最大值,可知对于任一元素A[x][j](j!=y),必有A[x][j]>=A[x][y];对于任一元素A[i][y](i!=x),必有A[i][y]<=A[x][y]。

若矩阵中存在另一马鞍点A[k][s](k!=x且s!=y),则:A[k][s]>= A[x][s](A[k][s]为第s列中的最大值)又因为A[x][s]>=A[x][y],可得A[k][s]>= A[x][y] (式1);A[k][s]<= A[k][y](A[k][s]为第k行中的最小值)又因为A[k][y]<=A[x][y],可得A[k][s]<= A[x][y] (式2);式1和式2联立可得:A[k][s] = A[x][y]。

该算法的基本操为元素的比较,求每行的最小元素值比较次数为n,判断每行中的最小值是否为马鞍点,最好情况下每行的最小值只有一个,比较次数为n-1+m,总共m行,所以最好情况下的比较次数为m*(n+n-1+m);最坏情况下,每行的元素值都相等,比较次数为m*n*m。

因此,最好情况下,该算法的时间复杂度,为O(m*(n+m)),最坏情况下的时间复杂度为O(m2*n)。

该算法的空间复杂度为O(0)。

7.设计体会本次的数据结果课程设计使我学到了很多，让我知道了写程序的一些基本思路和基本的方法，让我在以后的课程设计中可以更加熟练，在这次的课程设计中我走了很多的弯路，例如：在初始化二维数组时刚刚开始初始化的过于单调，简单，是程序的健壮性和可行性大打折扣。

经过和同学的商量和老师的指导将程序的健壮性改进了许多。

在这次的课程设计中我也体会到了合作的力量，编程是一个团队的事，一个人的力量是有限的，团队的力量是无穷的啊。

8.结束语求解矩阵中的马鞍点的方法有多种,这里只列出两种。

可以看出第一种方法的算法思想比较简单,所用的辅助空间较小,但时间效率较差;第二种方法的算法思想相对较复杂,利用了“矩阵中的马鞍点值均相等”的性质,时间效率好于第一种方法,特别是在矩阵较大的情况下,但所占用的空间要大一些9.源代码#include <iostream>#include <ctime>#include <cstdlib>#include <iomanip>#include<stdio.h>#include<malloc.h>#include<stdlib.h>using namespace std;void maan(int ,int);int A[10][10] void Automatic(int line,int row)//数组的随机生成函数{ int i,j;srand((unsigned)time(NULL));//以当前时间做种子for(i=0;i<line;i++)//行for(j=0;j<row;j++)//列A[i][j]=rand()%10;//随机获取0-9之间的数cout<<"随机生成矩阵里的数据"<<endl;for(i=0;i<line;i++)for(j=0;j<row;j++){if(j==row-1)cout<<A[i][j]<<endl;else cout<<A[i][j]<<" "; }cout<<endl;cout<<setiosflags(ios::right)<<setw(40)<<"矩阵已经自动建立完毕！"<<endl<<endl;}void Manual(int line,int row){ int i,j;int A[256][256];printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");printf(" *请输入与行列数相符的矩阵(数与数之间用空格隔开)：*\n");printf(" *输入完一行按回车键*\n");printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");for( i =0 ;i < line ;i++)for( j =0 ;j < row; j++)scanf("%d",&A[i][j]);printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");printf(" 输入的矩阵为：\n");for( i =0 ;i < line ;i++){ for( j =0 ;j <row; j++)printf("%4d",A[i][j]);printf("\n");} }void maan(int line,int row){int i,j,k,min,flag,h=0;cout<<"马鞍点输出(输出该点所在的行数与列数):"<<endl<<endl;for(i=0;i<line;i++)//一行一行循环{ min=A[i][0];for(j=0;j<row;j++) //一列一列循环{if(min>A[i][j])min=A[i][j];//求行最小值}for(j=0;j<row;j++)//在该行里查找最小值的数据（允许多个最小值）if(min==A[i][j]){for(flag=1,k=0;k<line;k++){if(min<A[k][j])flag=0;}if(flag){cout<<"马鞍点所在"<<i+1<<"行"<<" "<<"所在"<<j+1<<"列"<<" 数值为："<<A[i][j]<<endl; h=h+1;} } }cout<<"一共有"<<h<<"个马鞍点"<<endl;if(flag==0) cout<<"此矩阵没有马鞍点"<<endl<<endl;}void exit(){cout<<endl<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆欢迎检查魏任恩的数据结构课程设计实验★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆感谢您的检查★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆若有什么错误的地方请老师校正★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆谢谢！★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━+━━━━━━━━━━━━━━━━━━━━"<<endl;system("pause");}void main(){printf(" * * * * * * 数据结构课程设计求矩阵的所有马鞍点* * * * * *\n");printf(" **\n");printf(" **\n");printf(" * 班级：软件092班06号*\n");printf(" * 制作人：魏任恩*\n");printf(" **\n")printf(" * * * * * * * * * * * ~~~^_^~~~ * * * * * * * * * * * * *\n"); printf("\n"); int flag=1,key=1,line,row;char choose;printf("\n");printf(" *请输入矩阵的行数line（10以内）:");scanf("%4d",&line);printf(" *请输入矩阵的列数row（10以内）:");scanf("%4d",&row); printf("\n");while(flag){cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆1.自动生成矩阵★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆2.手动生成矩阵★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆3.寻找马鞍点★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆4.退出系统★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"★☆请输入选择的代号★☆"<<endl;cout<<setiosflags(ios::left)<<setw(40)<<"━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;do{cin>>choose;switch(choose-'0'){case 1:Automatic(line,row);key=0;break;case 2:Manual(line,row);key=0;break;case 3:maan(line,row);key=0;break;case 4:key=0;flag=0;exit();break;default :cout<<"输入错误请重新输入！"<<endl;}}while(key)；}}。