大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告材料

實(shí)用文檔實(shí)用文檔本科生實(shí)驗(yàn)報(bào)告（二）實(shí)驗(yàn)課程名稱:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期: 2013年5月25指導(dǎo)教師及職稱:實(shí)驗(yàn)成績:開課時間：2012～2013學(xué)年第二學(xué)期實(shí)驗(yàn)題目實(shí)驗(yàn)題目數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)小組合作姓名 班級 學(xué) 號 3一、實(shí)驗(yàn)?zāi)康臄?shù)組和廣義表：6.1：5*56.2：實(shí)驗(yàn)6.3：求兩個對稱矩陣之和與乘積；6.4：實(shí)現(xiàn)稀疏矩陣（采用三元組表示）6.5：實(shí)現(xiàn)廣義表的基本運(yùn)算。二．實(shí)驗(yàn)環(huán)境計(jì)算機(jī)Visualc++ 6.0三、實(shí)驗(yàn)內(nèi)容與步驟5*5的螺旋矩陣。設(shè)計(jì)一個程序exp6-1.cppn*n（n<10）方陣（順時針方向旋進(jìn)。12345161718196152425207142322218131211109主程序如下：#include"stdafx.h"#include<stdio.h>#defineMaxLen10voidfun(inta[MaxLen][MaxLen],intn){inti,j,k=0,m;if(n%2==0) m=n/2;elsem=n/2+1;for(i=0;i<m;i++){for(j=i;j<n-i;j++){k++;a[i][j]=k;}for(j=i+1;j<n-i;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++;[j][i]=k;}}}voidmain(){intn,i,j;inta[MaxLen][MaxLen];printf("輸入n(n<10):");scanf("%d",&n);fun(a,n);printf("%d階數(shù)字方陣如下:\n",n);for(i=0;i<n;i++){for(j=0;j<n;j++)printf("%4d",a[i][j]);printf("\n");}}運(yùn)行結(jié)果：：如果矩陣A中存在這樣的一個元素A[i][jijexp6-2.cpp計(jì)算出m*nA主程序如下：#include<stdio.h>#defineM4#defineN4voidMinMax(intA[M][N]){ inti,j;boolhave=false;intmin[M],max[N];for(i=0;i<M;i++) //計(jì)算出每行的最小值元素,放入min[0..M-1]之中{min[i]=A[i][0];forif(A[i][j]<min[i])min[i]=A[i][j];}for(j=0;j<N;j++) //計(jì)算出每列的最大值元素,放入max[0..N-1]之中{ max[j]=A[0][j];forif(A[i][j]>max[j])max[j]=A[i][j];}for(i=0;i<M;i++) //for(j=0;j<N;j++)if(min[i]==max[j]){ printf("A[%d][%d]=%d\n",i,j,A[i][j]);have=true;}if(!have)printf("沒有鞍點(diǎn)\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<M;i++){ for(j=0;j<N;j++)printf("%4d",A[i][j]);printf("\n");}printf("A矩陣中的馬鞍點(diǎn):\n");MinMax(A); //調(diào)用MinMax()找馬鞍點(diǎn)}運(yùn)行結(jié)果：：已知AB為兩個n*n一維數(shù)組，如圖6.5所示（對稱矩陣M存儲在一維數(shù)組A中，設(shè)計(jì)一個程序exp6-3.cpp實(shí)習(xí)如下功能：求對稱矩陣AB求對稱矩陣ABA:圖6.5對稱矩陣的存儲轉(zhuǎn)換形式主程序如下：#include<stdio.h>#defineN4#defineM10intvalue(inta[],inti,intj){if(i>=j)returna[(i*(i-1))/2+j];elsereturna[(j*(j-1))/2+i];}voidmadd(inta[],intb[],intc[][N]){inti,j;for(i=0;i<N;i++)for(j=0;j<N;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<N;i++)for{s=0;for(k=0;k<N;k++)s=s+value(a,i,k)*value(b,k,j);c[i][j]=s;}}voiddisp1(inta[]){inti,j;for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%4d",value(a,i,j));printf("\n");}}voiddisp2(intc[][N]){inti,j;for(i=0;i<N;i++){for(j=0;j<N;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");}運(yùn)行結(jié)果：n*n的稀疏矩陣A采用三元組表示，設(shè)計(jì)一個程序exp6-4.cpp實(shí)現(xiàn)如下功能：生成如下兩個稀疏矩陣矩陣的三元組ab:aa+ba*b主程序如下：#include<stdio.h>#defineN4typedefintElemType;#defineMaxSize100 //矩陣中非零元素最多個數(shù)typedefstruct{ intr;//行號intc;//列號ElemTyped;//元素值}TupNode;//三元組定義typedefstruct{ introws;//行數(shù)值intcols;//列數(shù)值intnums;//非零元素個數(shù)TupNodedata[MaxSize];}TSMatrix; voidCreatMat(TSMatrix&t,ElemTypeA[N][N]){inti,j;t.rows=N;t.cols=N;t.nums=0;for(i=0;i<N;i++){for(j=0;j<N;j++)if{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<t.nums;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.datatb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if(t.nums!=0){for(v=0;v<t.cols;v++) //tb.data[q]中的記錄以cfor(p=0;p<t.nums;p++)//pt.dataif(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;//cawhile(i<a.nums&&j<b.nums)//處理a和b中的每個元素{if(a.data[i].r==b.data[j].r) //行號相等時{if(a.data[i].c<b.data[j].c)//a元素的列號小于b元素的列號{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元素添加到cc.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}else //ab{v=a.data[i].d+b.data[j].d;if(v!=0) //0c{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<b.data[j].r)//a元素的行號小于b元素的行號{c.data[k].r=a.data[i].r; //acc.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else //ab{c.data[k].r=b.data[j].r; //bcc.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<c.nums&&(c.data[k].r!=i||c.data[k].c!=j))k++;if(k<c.nums)return(c.data[k].d);elsereturn(0);}boolMatMul(TSMatrixa,TSMatrixb,TSMatrix&c){inti,j,k,p=0;ElemTypes;if(a.cols!=b.rows) //a的列數(shù)不等于breturnfalse;for(i=0;i<a.rows;i++)for(j=0;j<b.cols;j++){s=0;for(k=0;k<a.cols;k++)s=s+getvalue(a,i,k)*getvalue(b,k,j);if(s!=0) 產(chǎn)生一個三元組元素{c.data[p].r=i;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轉(zhuǎn)置為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);}運(yùn)行結(jié)果：：編寫一個程序exp6-5.cpp成如下功能：1）建立廣義表g（b,(b,a,(#),d),((a,b),c,((#))”的鏈?zhǔn)酱鎯Y(jié)構(gòu)；輸出廣義表g輸出廣義表g輸出廣義表g主程序如下：#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlnode{ inttag; //union{ElemTypedata;structlnode*sublist;}val;structlnode*link; //指向下一個元素}GLNode;GLNode*CreateGL(char*&s) //返回由括號表示法表示s的廣義表鏈?zhǔn)酱鎯Y(jié)構(gòu){ GLNode*g;charch=*s++; //取一個字符if(ch!='\0') //串未結(jié)束判斷{ g=(GLNode*)malloc(sizeof(GLNode));//創(chuàng)建一個新節(jié)點(diǎn)if(ch=='(') //當(dāng)前字符為左括號時{ g->tag=1; //新節(jié)點(diǎn)作為表頭節(jié)點(diǎn)g->val.sublist=CreateGL(s); //遞歸構(gòu)造子表并鏈到表頭節(jié)點(diǎn)}elseif(ch==')')g=NULL; //遇')'字符,g置為空elseif(ch=='#') //遇'#'字符，表示空g->val.sublist=NULL;else //為原子字符{ g->tag=0; //g->val.data=ch;}}else //,gg=NULL;ch=*s++; //取下一個字符if(g!=NULL) //串未結(jié)束，繼續(xù)構(gòu)造兄遞節(jié)if(ch==',') //當(dāng)前字符','g->link=CreateGL(s); //遞歸構(gòu)造兄遞節(jié)點(diǎn)else //沒有兄弟了,將兄弟指針置為g->link=NULL;returng; //返回廣義表g}intGLLength(GLNode*g) //求廣義表g{intn=0;g=g->val.sublist; //gwhile(g!=NULL){n++;g=g->link;}returnn;}intGLDepth(GLNode*g) //求廣義表g{intmax=0,dep;if(g->tag==0)return0;g=g->val.sublist; //gif(g==NULL) //return1;while(g!=NULL) //遍歷表中的每一個元素{if(g->tag==1) //元素為子表的情況{dep=GLDepth(g); //遞歸調(diào)用求出子表的深度if(dep>max)max=dep; //max為同一層所求過的子表中深度的最大值}g=g->link; //g}return(max+1); //返回表的深度}voidDispGL(GLNode*g) //輸出廣義表g{ if(g!=NULL) //表不為空判斷{ //先輸出gif(g->tag==0) //gprintf("%c",g->val.data);//輸出原子值else //g{ printf("("); //輸'('if(g->val.sublist==NULL) //為空表printf("#");else //為非空子表時DispGL(g->val.sublist);遞歸輸出子printf(")"); //輸')'}if(g->link!=NULL){ printf(",");DispGL(g->link); //遞歸輸出g}}}ElemTypemaxatom(GLNode*g) //求廣義表g{ElemTypemax1,max2;if(g!=NULL){if(g->tag==0){max1=maxatom(g->link);return(g->val.data>max1?g->val.data:max1);}else{max1=maxatom(g->val.sublist);max2=maxatom(g->link);return(max1>max2?max1:max2);}}elsereturn0;}voidmain(){GLNode*g;char*str="(b,(b,a,(#),d),((a,b),c,((#)