数组与广义表的算法的实验报告.pdf

数组与广义表的算法数组与广义表的算法实验工具：visual C+实验内容：1、三元组表示稀疏矩阵的转置算法（一般&快速）2、稀疏矩阵乘法、加法的算法（一般&十字链表）3、广义表的各种算法体验：通过利用 visual C+实验工具，实现数组与广义表各类算法的过程中，本人对数组与广义表的知识有了更深的了解，而且认识到数组与广义表各类操作可由形式多样的算法结构实现。算法并非统一标准的，同样的结果可有多种算法得出，算法的编写鼓励创造性思维。1、三元组表示稀疏矩阵的转置算法（一般三元组表示稀疏矩阵的转置算法（一般&快速）快速）代码：代码：#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;/各行第一个非零元的位置表int mu,nu,tu;/矩阵的行数、列数和非零元个数RLSMatrix;CreateSMatrix(RLSMatrix&M)/创建稀疏矩阵 Mint i,m,n;ElemType e;int k,j;printf(输入矩阵的行数、列数、非零元的个数：);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);M.data0.i=0;for(i=1;i3)/控制跳出死循环printf(本次输入失败！);return ERROR;printf(按行序输入第%d 个非零元素所在的行(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)/销毁稀疏矩阵 MM.mu=0;M.nu=0;M.tu=0;void PrinRLSMatrix(RLSMatrix M)/遍历稀疏矩阵 Mint i;printf(稀疏矩阵对应的三元组表为：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)/打印矩阵函数，以通常形式输出矩阵 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(*请选择要执行的操作*nn);printf(&1 采用一般算法实现&n);printf(&2 采用快速转置的算法实现&n);printf(&3 同时采用两种算法，先显示一般算法，再显示快速算法&n);printf(*nn);/头文件结束TransposeSMatrix(RLSMatrix M,RLSMatrix&T)/求稀疏矩阵 M 的转置矩阵 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)/按列序求转置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)/快速转置算法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 辅助数组的值为：n);printf(列号：);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(稀疏矩阵的转置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 函数，用来设置控制台标题doshowtip();/调用菜单函数int i;scanf(%d,&i);switch(i)case 1:printf(创建矩阵 A：);if(result=CreateSMatrix(A)=0)exit(ERROR);PrinRLSMatrix(A);printf(求 A 的转置矩阵 B(一般算法)：n);TransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(B);printf(nn);break;case 2:printf(创建矩阵 A：);if(result=CreateSMatrix(A)=0)exit(ERROR);PrinRLSMatrix(A);printf(求 A 的转置矩阵 B(快速转置):n);FastTransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(A);DestroySMatrix(B);printf(nn);break;case 3:printf(创建矩阵 A：);if(result=CreateSMatrix(A)=0)exit(ERROR);PrinRLSMatrix(A);printf(求 A 的转置矩阵 B-(一般算法)：n);TransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(B);printf(nn);printf(求 A 的转置矩阵 B-(快速转置):n);FastTransposeSMatrix(A,B);PrinRLSMatrix(B);print(B);DestroySMatrix(A);DestroySMatrix(B);printf(nn);break;printf(*请选择是否继续输入其他稀疏矩阵？*n);printf(1 是，输入其他矩阵n);printf(0 否，不输入n);printf(*);fflush(stdin);/清除输入缓存区scanf(%d,&j);while(j=1);运行结果：运行结果：（1）创建矩阵（2）一般转置 （3）快速转置 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中的序号int mu;/行数int nu;/列数int tu;/非零元数 juzhen;/定义矩阵typedef struct node/定义十字链表元素int i,j,e;struct node*right,*down;/该非零元所在行表和列表的后继元素 node,*link;typedef struct/定义十字链表对象结构体 link*rhead,*chead;/行和列的头指针int m,n,t;/系数矩阵的行数，列数，和非零元素个数 crosslist;void createcross(crosslist&M)/建立十字链表int i,j,e,k;node*p,*q;printf(输入行，列和非零元数，空格隔开：n);scanf(%d%d%d,&M.m,&M.n,&M.t);M.rhead=(link*)malloc(M.m+1)*sizeof(link);/给行和列的头指针分配内存 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(输入非零元的行，列和值，空格隔开：n);for(k=1;ki=i;p-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)/插入元素所在行无非零元或首非零元的列标大于插入元素的列标p-right=M.rheadi;M.rheadi=p;else for(q=M.rheadi;(q-right)&q-right-jright);/空循环找到第一个列标大于或等于插入元素列标的元素p-right=q-right;q-right=p;if(M.cheadj=NULL|(M.cheadj-ii)/插入元素所在列无非零元或首非零元的行标大于插入元素的行标p-down=M.cheadj;M.cheadj=p;elsefor(q=M.cheadj;(q-down)&q-down-idown);/空循环找到第一个行标大于或等于插入元素行标的元素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;/创建两个十字链表对象，并初始化createcross(a);createcross(b);node*pre,*h51,*pa,*pb,*q;/定义辅助指针，pa，pb 分别为 a,b 当前比较的元素，pre 为 pa 的前驱元素 int i,j,k=0,m,n;/hj指向 j 列的当前插入位置 if(a.m!=b.m|a.n!=b.n)printf(格式不对，不能相加!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)/当 a 此行已经检查完或者 pb 因该放在 pa前面if(pre=NULL)a.rheadp-i=p;else pre-right=p;p-right=pa;pre=p;if(hp-j=NULL)/当前插入位置下面无非零元/因为是逐行处理，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 指向该行下个元素else if(pa&pa-jj)/只要移动 pa 的指针*先不加|(pb=NULL&pa)pre=pa;hpa-j=pa;/移动 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 为零，删除节点if(pre=NULL)a.rhead pa-i=pa-right;else pre-right=pa-right;p=pa;/p 指向 pa，用来在下面修改列指针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(格式错误，不能相乘！n);else c.m=a.m;c.n=b.n;c.t=0;c.rhead=(link*)malloc(a.m+1)*sizeof(link);/给行和列的头指针分配内存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)/插入元素所在行无非零元或首非零元的列标大于插入元素的列标v-right=c.rheadi;c.rheadi=v;else for(p2=c.rheadi;(p2-right)&(p2-right-jright);/空循环找到第一个列标大于或等于插入元素列标的元素v-right=p2-right;p2-right=v;if(c.cheadj=NULL|c.cheadj-ii)/插入元素所在列无非零元或首非零元的行标大于插入元素的行标v-down=c.cheadj;c.cheadj=v;elsefor(p2=c.cheadj;(p2-down)&(p2-down-idown);/空循环找到第一个行标大于或等于插入元素行标的元素v-down=p2-down;p2-down=v;void create(juzhen&M)/创建稀疏矩阵int i,t=0;printf(输入矩阵行数和列数 and 非零元的个数，以空格隔开:n);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);printf(输入矩阵非零元的行，列，和数值(中间空格隔开):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+)/得到各行第一个元素的序号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 中非零元的序号变化printf(稀疏矩阵加法:n);create(A);create(B);if(A.mu!=B.mu|A.nu!=B.nu)printf(格式不对，不能相加!n);elsewhile(k1=A.tu&k2=B.tu)/当 A，B 中的非零元都没用完if(A.datak1.iB.datak2.i)/同上C.datak+=B.datak2+;else/datak1,datak2行标相同if(A.datak1.jB.datak2.j)/datak1列标大于 datak2列标，则把datak2的值赋给 datakC.datak+=B.datak2+;else if(A.datak1.jB.datak2.j)/同上C.datak+=A.datak1+;else/行，列标都相同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 的行列数和非零元个数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)/行和列分别对应相等则输出相应非零元，否则输出零printf(%5d,A.datak+.e);else printf(%5d,0);printf(n);/该行输出结束，空行输出下一行printf(n);void multy(juzhen A,juzhen B,juzhen&C)/稀疏矩阵乘法int arow,brow,ccol,temp51,p,q,t,tp,i;/各变量代表含义见下面printf(稀疏矩阵乘法:n);create(A);create(B);if(A.nu!=B.mu)printf(格式错误，不能相乘！n);elseC.mu=A.mu;/初始化 c 的行列及非零元个数C.nu=B.nu;C.tu=0;if(A.nu!=B.mu)printf(A,B 格式不对不能相乘!n);else/for(arow=1;arow=A.mu;arow+)/arow 为当前 A 矩阵的行标for(i=0;i51;i+)/初始化 temptempi=0;if(arowA.mu)tp=A.ropsarow+1;/tp 为 arow+1 行的首非零元在 data【】中的序号else/arow 为最后一行tp=A.tu+1;for(p=A.ropsarow;ptp;p+)/p 为 A 中当前元素在 data中的序号brow=A.datap.j;/brow 为 与 B 矩阵中的相应行对应的 A 中当前元素的列标if(browB.mu)t=B.ropsbrow+1;/t 为 brow+1 行的首非零元在 B 中data【】中的序号else/brow 大小等于 B.mut=B.tu+1;for(q=B.ropsbrow;qt;q+)/q 为 B 中当前元素在 B.data中的序号ccol=B.dataq.j;/ccol：datap*dataq所得结果所在的列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(请选择：1、稀疏矩阵的加法，并输出结果，2、稀疏矩阵乘法，并输出结果n);printf(n3、十字链表加法,并输出，4、十字链表乘法并输出，5、结束：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);运行结果：运行结果：（1）稀疏矩阵加法 （2）稀疏矩阵乘法 （3）十字链表加法（4）十字链表乘法3、广义表的各种算法广义表的各种算法代码：代码：#include#include#include#define maxlen 100typedef char ElemType;typedef struct GLode/广义表结构体的定义int tag;unionElemType atom;struct GLode*hp;val;struct GLode*tp;GList;typedef struct/栈结构的定义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;/查找函数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+;s-datas-top=);if(g-val.hp=NULL)printf();elseNIGList(g-val.hp,s);elses-top+;s-datas-top=g-val.atom;if(g-tag=1)s-top+;s-datas-top=(;if(g-tp!=NULL)s-top+;s-datas-top=,;NIGList(g-tp,s);/广义表的输出void Pop(SeqStack*s)while(s-top=0)printf(%c,s-datas-top);s-top-;/以下主函数用于调试void main()GList*g,*gt;printf(请输入一个广义表:如(a,b),c)n);char str30;char x;int y=0,mark,xz=1;system(color 0c);/调用系统命令，改变运行时的字体颜色SeqStack*k;k=(SeqStack*)malloc(sizeof(SeqStack);k-top=-1;char*s=gets(str);g=CreateGL(s);printf(你输入的广义表为：n);while(xz)DispGL(g);printf(n);printf(*广义表的运算*n);printf(=n);printf(*1.广义表的查找*n);printf(*2.求广义表表尾*n);printf(*3.求广义表深度*n);printf(*4.求广义表逆表*n);printf(*0.退出表的运算*n);printf(=n);printf(请 选 择:(05)n);scanf(%d,&y);switch(y)case 1:printf(请输入要查找的元素:);mark=0;getchar();scanf(%c,&x);FindGListX(g,x,mark);if(mark)printf(_该元素存在于您输入的表中!n);elseprintf(T_T 对不起，没有找到该元素!n);break;case 2:gt=tail(g);printf(表尾:);DispGL(gt);printf(n);break;case 3:printf(广义表的深度:%dn,GLDepth(g);break;case 4:printf(所求广义表的逆表为:n);NIGList(g,k);Pop(k);printf(n);break;default:system(cls);/*调用系统命令 CLS，实现清屏*/printf(再见,欢迎再次使用!n);return;printf(是否继续:1.继续;0.停止n);printf(请选择:);scanf(%d,&xz);if(xz=1)system(cls);elsesystem(cls);printf(再见,欢迎再次使用!n);运行结果：运行结果：（1）创建广义表 （2）广义表的查找 （3）广义表表尾 （4）广义表的深度（5）广义表的逆表