數(shù)組與廣義表的算法的實(shí)驗(yàn)報(bào)告.doc

數(shù)組與廣義表的算法實(shí)驗(yàn)工具：visual C+實(shí)驗(yàn)內(nèi)容：1、三元組表示稀疏矩陣的轉(zhuǎn)置算法（一般&快速） 2、稀疏矩陣乘法、加法的算法（一般&十字鏈表） 3、廣義表的各種算法體驗(yàn)：通過(guò)利用visual C+實(shí)驗(yàn)工具，實(shí)現(xiàn)數(shù)組與廣義表各類算法的過(guò)程中，本人對(duì)數(shù)組與廣義表的知識(shí)有了更深的了解，而且認(rèn)識(shí)到數(shù)組與廣義表各類操作可由形式多樣的算法結(jié)構(gòu)實(shí)現(xiàn)。算法并非統(tǒng)一標(biāo)準(zhǔn)的，同樣的結(jié)果可有多種算法得出，算法的編寫(xiě)鼓勵(lì)創(chuàng)造性思維。1、 三元組表示稀疏矩陣的轉(zhuǎn)置算法（一般&快速）代碼：#include#include#include#include#define OK 1#define ERROR 0#define OVERFLOW 0#define MAXSIZE 100#define MAXRC 100typedef int ElemType;typedef structint i,j;ElemType e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元組int rposMAXRC+1; /各行第一個(gè)非零元的位置表int mu,nu,tu; /矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)RLSMatrix;CreateSMatrix(RLSMatrix &M) /創(chuàng)建稀疏矩陣Mint i,m,n;ElemType e;int k,j;printf(輸入矩陣的行數(shù)、列數(shù)、非零元的個(gè)數(shù)：);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);M.data0.i=0;for(i=1;i3) /控制跳出死循環(huán)printf(本次輸入失??！);return ERROR;printf(按行序輸入第%d個(gè)非零元素所在的行(1%d)列(1%d)值：,i,M.mu,M.nu);scanf(%d%d%d,&m,&n,&e);k=0;if(mM.mu|nM.nu) /行或列超出范圍k=1;if(mM.datai-1.i|m=M.datai-1.i&nM.datai-1.j)k=1;while(k);M.datai.i=m;M.datai.j=n;M.datai.e=e; /end forprintf(n);return(OK);void DestroySMatrix(RLSMatrix &M) /銷(xiāo)毀稀疏矩陣MM.mu=0;M.nu=0;M.tu=0;void PrinRLSMatrix(RLSMatrix M) /遍歷稀疏矩陣 Mint i;printf(稀疏矩陣對(duì)應(yīng)的三元組表為：nn);printf(行 列 元素值、nn);for(i=1;i=M.tu;i+)printf(%2d%4d%8dn,M.datai.i,M.datai.j,M.datai.e);printf(nn);void print(RLSMatrix A) /打印矩陣函數(shù)，以通常形式輸出矩陣 int k=1,a,b; printf(稀疏矩陣的通常形式為：n);int MMAXSIZEMAXSIZE;for(a=0;aA.mu;a+) /初始化矩陣Mfor(b=0;bA.nu;b+)Mab=0;while(k=A.tu)MA.datak.i-1A.datak.j-1=A.datak.e;k+;for(a=0;aA.mu;a+)printf( | );for(b=0;bA.nu;b+)printf(%d ,Mab);printf( | n);void showtip() /菜單printf( *請(qǐng)選擇要執(zhí)行的操作*nn);printf( & 1 采用一般算法實(shí)現(xiàn) &n);printf( & 2 采用快速轉(zhuǎn)置的算法實(shí)現(xiàn) &n);printf( & 3 同時(shí)采用兩種算法，先顯示一般算法，再顯示快速算法 &n);printf( *nn);/頭文件結(jié)束TransposeSMatrix(RLSMatrix M,RLSMatrix &T) /求稀疏矩陣M的轉(zhuǎn)置矩陣T(一般算法)int p,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;+col) /按列序求轉(zhuǎn)置for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T) /快速轉(zhuǎn)置算法int p,q,t,col,*num,*cpot;num=(int*)malloc(M.nu+1)*sizeof(int);cpot=(int*)malloc(M.nu+1)*sizeof(int);T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;printf(n輔助數(shù)組的值為：n);printf(列號(hào)：);for(t=1;t=M.nu;+t)printf(%4d,t);printf(n);printf(num);for(t=1;t=M.nu;+t)printf(%4d,numt);printf(n);printf(cpot);for(t=1;t=M.nu;+t)printf(%4d,cpott);printf(nn);for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;free(num);free(cpot);return OK;void main()int result;int j;RLSMatrix A,B;/*COORD Co=0,0;DWORD Write;SetConsoleTitle(稀疏矩陣的轉(zhuǎn)置n);HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleTextAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY);FillConsoleOutputAttribute(hOut,FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_INTENSITY,100000000,Co,&Write);/windows的API函數(shù)，用來(lái)設(shè)置控制臺(tái)標(biāo)題doshowtip(); /調(diào)用菜單函數(shù)int i;scanf(%d,&i);switch(i)case 1:printf(創(chuàng)建矩陣A：);if(result=CreateSMatrix(A)=0)exit(ERROR);PrinRLSMatrix(A);printf(求A的轉(zhuǎn)置矩陣B(一般算法)：n);TransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(B); printf(nn);break;case 2:printf(創(chuàng)建矩陣A：);if(result=CreateSMatrix(A)=0)exit(ERROR); PrinRLSMatrix(A);printf(求A的轉(zhuǎn)置矩陣B(快速轉(zhuǎn)置):n);FastTransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(A); DestroySMatrix(B);printf(nn);break;case 3: printf(創(chuàng)建矩陣A：);if(result=CreateSMatrix(A)=0)exit(ERROR); PrinRLSMatrix(A); printf(求A的轉(zhuǎn)置矩陣B-(一般算法)：n); TransposeSMatrix(A,B);PrinRLSMatrix(B);print(B); DestroySMatrix(B); printf(nn); printf(求A的轉(zhuǎn)置矩陣B-(快速轉(zhuǎn)置):n);FastTransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(A); DestroySMatrix(B);printf(nn);break;printf( *請(qǐng)選擇是否繼續(xù)輸入其他稀疏矩陣？*n);printf( 1 是，輸入其他矩陣n);printf( 0 否，不輸入n);printf( *);fflush(stdin);/清除輸入緩存區(qū)scanf(%d,&j);while(j=1);運(yùn)行結(jié)果：（1）創(chuàng)建矩陣（2）一般轉(zhuǎn)置 （3）快速轉(zhuǎn)置 2、 稀疏矩陣乘法、加法的算法（一般&十字鏈表）代碼：#include#include#define Size 2501# define Size1 51typedef structint i;int j;int e;/非零元的值triple; /定義三元組typedef structtriple dataSize+1;/矩陣中的元素int ropsSize1+1;/ ropsi為第i行元素中的首非零元在data中的序號(hào)int mu;/行數(shù)int nu;/列數(shù)int tu;/非零元數(shù) juzhen;/定義矩陣typedef struct node/ 定義十字鏈表元素int i,j,e; struct node *right,*down;/ 該非零元所在行表和列表的后繼元素 node,*link;typedef struct / 定義十字鏈表對(duì)象結(jié)構(gòu)體 link *rhead,*chead;/行和列的頭指針int m,n,t;/ 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個(gè)數(shù) crosslist;void createcross(crosslist &M)/建立十字鏈表int i,j,e,k;node *p,*q;printf(輸入行，列和非零元數(shù)，空格隔開(kāi)：n);scanf(%d %d %d,&M.m,&M.n,&M.t);M.rhead=(link *)malloc(M.m+1)*sizeof(link);/給行和列的頭指針?lè)峙鋬?nèi)存 M.chead=(link *)malloc(M.n+1)*sizeof(link);for(k=1;k=M.m;k+)/初始化行，列的頭指針M.rheadk=NULL;for(k=1;k=M.n;k+)M.cheadk=NULL;printf(輸入非零元的行，列和值，空格隔開(kāi)：n);for(k=1;ki=i;p-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)/插入元素所在行無(wú)非零元或首非零元的列標(biāo)大于插入元素的列標(biāo)p-right=M.rheadi;M.rheadi=p;else for(q=M.rheadi;(q-right)&q-right-jright);/空循環(huán)找到第一個(gè)列標(biāo)大于或等于插入元素列標(biāo)的元素p-right=q-right;q-right=p;if(M.cheadj=NULL|(M.cheadj-ii)/插入元素所在列無(wú)非零元或首非零元的行標(biāo)大于插入元素的行標(biāo)p-down=M.cheadj;M.cheadj=p;elsefor(q=M.cheadj;(q-down)&q-down-idown);/空循環(huán)找到第一個(gè)行標(biāo)大于或等于插入元素行標(biāo)的元素p-down=q-down;q-down=p;void printcross(crosslist A)/輸出十字鏈表if(A.m=0)printf(十字鏈表為空!n);elseprintf(十字鏈表為:n);int i,j;for(i=1;i=A.m;i+) link p=A.rheadi; for(j=1;jj) printf(%5d,p-e);p=p-right; elseprintf(%5d,0); printf(n);printf(n);crosslist addcross()printf(十字鏈表加法:n);crosslist a,b;/ 創(chuàng)建兩個(gè)十字鏈表對(duì)象，并初始化createcross(a);createcross(b);node *pre,*h51,*pa,*pb,*q;/定義輔助指針，pa，pb分別為a,b當(dāng)前比較的元素，pre為pa的前驅(qū)元素 int i,j,k=0,m,n; /hj指向j列的當(dāng)前插入位置 if(a.m!=b.m|a.n!=b.n)printf(格式不對(duì)，不能相加!n);elsefor(i=1;i=a.m;i+) pa=a.rheadi;pb=b.rheadi;pre=NULL;for(j=1;ji=pb-i;p-j=pb-j;p-e=pb-e;if(pa=NULL|pa-jpb-j)/當(dāng)a此行已經(jīng)檢查完或者pb因該放在pa前面if (pre=NULL)a. rheadp-i=p;else pre-right=p;p-right=pa;pre=p;if (hp-j=NULL)/當(dāng)前插入位置下面無(wú)非零元/因?yàn)槭侵鹦刑幚?，so,hp-j，依次下移/因此每次都是指向插入的位置 a. chead p-j= p; p-down = NULL;else p-down = hp-j-down;hp-j-down = p;hp-j=p;/*hp-j下移指向下次插入的位置pb=pb-right;/pb指向該行下個(gè)元素else if(pa&pa-jj)/只要移動(dòng)pa的指針*先不加|(pb=NULL&pa)pre = pa;hpa-j=pa;/移動(dòng)h，使其指向下次插入的位置pa = pa-right;else if(pa-j=pb-j)pa-e+=pb-e;if(pa-e)/不為零pre=pa;hpa-j=pa;pb=pb-right;/加else/pa-e為零，刪除節(jié)點(diǎn)if (pre =NULL)a.rhead pa-i=pa-right;else pre-right=pa-right;p=pa;/p指向pa，用來(lái)在下面修改列指針pa=pa-right;if (h p-j=NULL) a.chead p-j=p-down;else hp-j-down=p-down;free(p);pb=pb-right;return a;void multycross(crosslist &c)/十字鏈表乘法node *p,*q,*u,*v,*p1,*p2;crosslist a,b;link *r;int i,j,k,e;printf(十字鏈表乘法:n);createcross(a);createcross(b);if(a.n!=b.m)printf(格式錯(cuò)誤，不能相乘！n);else c.m=a.m;c.n=b.n;c.t=0;c.rhead=(link *)malloc(a.m+1)*sizeof(link);/給行和列的頭指針?lè)峙鋬?nèi)存c.chead=(link *)malloc(b.n+1)*sizeof(link);for(k=1;k=a.m;k+)/初始化行，列的頭指針c.rheadk=NULL;for(k=1;k=b.n;k+)c.cheadk=NULL;r=(link *)malloc(b.n+1)*sizeof(link);for(i=1;ie=0;u-i=0;u-j=0;for(k=1;k=b.n;k+)/初始化rrk=u;p1=p=a.rheadi;for(j=1;je=0;v-i=i;v-j=j;while(p&q)if(p-jq-i)q=q-down;else if(p-ji)p=p-right;elsev-e+=p-e*q-e;p=p-right;q=q-down;if(v-e)/如果不為零，則插入c矩陣中/同建立十字鏈表if(c.rheadi=NULL|c.rheadi-jj)/插入元素所在行無(wú)非零元或首非零元的列標(biāo)大于插入元素的列標(biāo)v-right=c.rheadi;c.rheadi=v;else for(p2=c.rheadi;(p2-right)&(p2-right-jright);/空循環(huán)找到第一個(gè)列標(biāo)大于或等于插入元素列標(biāo)的元素v-right=p2-right;p2-right=v;if(c.cheadj=NULL|c.cheadj-ii)/插入元素所在列無(wú)非零元或首非零元的行標(biāo)大于插入元素的行標(biāo)v-down=c.cheadj;c.cheadj=v;elsefor(p2=c.cheadj;(p2-down)&(p2-down-idown);/空循環(huán)找到第一個(gè)行標(biāo)大于或等于插入元素行標(biāo)的元素v-down=p2-down;p2-down=v;void create(juzhen & M) /創(chuàng)建稀疏矩陣int i,t=0;printf(輸入矩陣行數(shù)和列數(shù)and非零元的個(gè)數(shù)，以空格隔開(kāi):n);scanf(%d %d %d,&M.mu,&M.nu,&M.tu);printf(輸入矩陣非零元的行，列，和數(shù)值(中間空格隔開(kāi)):n);for(i=1;i=M.tu;i+)scanf(%d %d %d,&M.datai.i,&M.datai.j,&M.datai.e); /輸入三元組的元素for(i=1;i=Size1;i+)/初始化rops【】M.ropsi=0;for(i=1,t=1;i=M.mu;i+)/得到各行第一個(gè)元素的序號(hào)M.ropsi=t;while(M.datat.i=i&t=M.tu)/遇到i行非零元，則t累加t+;void add(juzhen A,juzhen B,juzhen & C)/稀疏矩陣加法int k=1,temp=0,k1=1, k2=1;/k1,k2,k分別控制A，B，C中非零元的序號(hào)變化printf(稀疏矩陣加法:n);create(A);create(B);if(A.mu!=B.mu|A.nu!=B.nu)printf(格式不對(duì)，不能相加!n);elsewhile(k1=A.tu&k2=B.tu)/當(dāng)A，B中的非零元都沒(méi)用完if(A.datak1.iB.datak2.i)/同上C.datak+=B.datak2+;else/datak1,datak2行標(biāo)相同if(A.datak1.jB.datak2.j)/datak1列標(biāo)大于datak2列標(biāo)，則把datak2的值賦給datakC.datak+=B.datak2+;else if(A.datak1.jB.datak2.j)/同上C.datak+=A.datak1+;else /行，列標(biāo)都相同temp=0;temp=A.datak1.e+B.datak2.e;if(temp)/相加后不為零C.datak.i=A.datak1.i;C.datak.j=A.datak1.j;C.datak.e=temp;k+;k1+;k2+; while(k1=A.tu)/B中非零元已用完，A中還有非零元C.datak+=A.datak1+;while(k2=B.tu)/A中非零元已用完，B中還有非零元C.datak+=B.datak2+;C.mu=A.mu;/確定C的行列數(shù)和非零元個(gè)數(shù)C.nu=A.nu;C.tu=k-1; void print(juzhen A)/輸出稀疏矩陣printf(n矩陣為:n);int i,j,k=1;if(A.mu=0)printf(矩陣為空！n);else if(A.tu=0)/矩陣元素為空printf(零矩陣！n);else for(i=1;i=A.mu;i+)/逐行輸出for(j=1;j=A.nu;j+) if(A.datak.i=i&A.datak.j=j)/行和列分別對(duì)應(yīng)相等則輸出相應(yīng)非零元，否則輸出零printf(%5d,A.datak+.e);else printf(%5d,0);printf(n);/該行輸出結(jié)束，空行輸出下一行printf(n);void multy(juzhen A,juzhen B,juzhen &C)/稀疏矩陣乘法int arow,brow,ccol,temp51,p,q,t,tp,i;/各變量代表含義見(jiàn)下面printf(稀疏矩陣乘法:n);create(A);create(B);if(A.nu!=B.mu)printf(格式錯(cuò)誤，不能相乘！n);elseC.mu=A.mu;/初始化c的行列及非零元個(gè)數(shù)C.nu=B.nu;C.tu=0;if(A.nu!=B.mu)printf(A,B格式不對(duì)不能相乘!n);else /for(arow=1;arow=A.mu;arow+)/arow為當(dāng)前A矩陣的行標(biāo)for(i=0;i51;i+)/初始化temptempi=0;if(arowA.mu)tp=A.ropsarow+1;/tp為arow+1行的首非零元在data【】中的序號(hào)else /arow為最后一行tp=A.tu+1;for(p=A.ropsarow;ptp;p+)/p為A中當(dāng)前元素在data中的序號(hào)brow=A.datap.j;/brow為 與B矩陣中的相應(yīng)行對(duì)應(yīng)的 A中當(dāng)前元素的列標(biāo)if(browB.mu)t=B.ropsbrow+1;/t為brow+1行的首非零元在B中data【】中的序號(hào)else /brow大小等于B.mut=B.tu+1;for(q=B.ropsbrow;qt;q+)/q為B中當(dāng)前元素在B.data中的序號(hào)ccol=B.dataq.j;/ccol：datap*dataq所得結(jié)果所在的列tempccol+=A.datap.e*B.dataq.e;/temp【ccol】：相乘所得的C矩陣中第arow行cool列元素的值for(ccol=1;ccol=B.nu;ccol+)/if(tempccol)/temp【ccol】不為零，則把值賦到c中，c.tu加1。C.data+C.tu.e=tempccol;C.dataC.tu.i=arow;C.dataC.tu.j=ccol;void clear(juzhen & A)/清空稀疏矩陣int i; A.mu=0;A.nu=0;A.tu=0; for(i=0;iSize1+1;i+)A.ropsi=0;for(i=0;iSize+1;i+)A.datai.i=0;A.datai.j=0;A.datai.e=0;void main()juzhen A,B,C,D;crosslist a,b,c,d;lable: printf(*n); printf(請(qǐng)選擇：1、稀疏矩陣的加法，并輸出結(jié)果，2、稀疏矩陣乘法，并輸出結(jié)果n); printf(n3、十字鏈表加法,并輸出，4、十字鏈表乘法并輸出，5、結(jié)束：n); printf(*n); int x; scanf(%d,&x); switch(x) case 1: add(A,B,C); print(C); printf(n); goto lable; case 2: multy(A,B,C); print(C); printf(n); goto lable; case 3: a=addcross(); printcross(a); printf(n); goto lable; case 4: multycross(b); printcross(b); printf(n); goto lable; case 5: break; printf(n); 運(yùn)行結(jié)果：（1） 稀疏矩陣加法 （2）稀疏矩陣乘法 （3）十字鏈表加法（4）十字鏈表乘法3、 廣義表的各種算法代碼：#include #include #include#define maxlen 100typedef char ElemType;typedef struct GLode/廣義表結(jié)構(gòu)體的定義int tag;unionElemType atom;struct GLode *hp; val;struct GLode *tp; GList;typedef struct /棧結(jié)構(gòu)的定義ElemType datamaxlen ;int top;SeqStack;/生成廣義表GList *CreateGL(char *&s)GList *h;char ch;ch=*s; s+; if (ch!=0) h=(GList *)malloc(sizeof(GList);if (ch=() h-tag=1;h-val.hp=CreateGL(s);else if (ch=)h=NULL;elseh-tag=0;h-val.atom=ch;elseh=NULL; ch=*s;s+;if (h!=NULL)if (ch=,) h-tp=CreateGL(s); else h-tp=NULL; return h; /遍歷廣義表void DispGL(GList *g)if (g!=NULL)if (g-tag=1) printf(); if (g-val.hp=NULL)printf();elseDispGL(g-val.hp); elseprintf(%c, g-val.atom); if (g-tag=1)printf();if (g-tp!=NULL)printf(,);DispGL(g-tp); /求廣義表的深度int GLDepth(GList *g) int max=0,dep;if (g-tag=0)return 0;g=g-val.hp;if (g=NULL)return 1;while (g!=NULL)if (g-tag=1)dep=GLDepth(g);if (depmax)max=dep; g=g-tp; return(max+1);/求廣義表的表尾GList *tail(GList *g) GList *p=g-val.hp;GList *t;if (g=NULL)printf(空表不能求表尾n);return NULL;else if (g-tag=0)printf(原子不能求表尾n);return NULL;p=p-tp;t=(GList *)malloc(sizeof(GList);t-tag=1;t-tp=NULL;t-val.hp=p;return t;/查找函數(shù)void FindGListX(GList *g,char x,int &mark)if(g!=NULL)if (g-tag = 0 & g-val.atom =x)mark = 1;elseif(g-tag = 1) FindGListX(g-val.hp,x,mark);FindGListX(g-tp,x,mark);/求廣義表的逆表void NIGList(GList *g,SeqStack *s)if(g!=NULL)if (g-tag=1)s-top+