数组与广义表的算法
实验工具：visual C++
实验内容：1、三元组表示稀疏矩阵的转置算法（一般&快速）<1-7页> 2、 稀疏矩阵乘
法、加法的算法（一般&十字链表）<8-21页> 3、广义表的各种算法<22-28页>
体验：通过利用visual C++实验工具，实现数组与广义表各类算法的过程中，本人对数组与
广义表的知识有了更深的了解，而且认识到数组与广义表各类操作可由形式多样的算法结构实现。算法并非统一标准的，同样的结果可有多种算法得出，算法的编写鼓励创造性思维。
1、 三元组表示稀疏矩阵的转置算法（一般&快速）
代码：
#include #define OVERFLOW 0 #define MAXSIZE 100 #define MAXRC 100 typedef int ElemType; typedef struct { int i,j; ElemType e; }Triple; typedef struct { Triple data[MAXSIZE+1]; //非零元三元组 int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu,nu,tu; //矩阵的行数、列数和非零元个数 }RLSMatrix; CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵M { int i,m,n; ElemType e; int k,j; printf(\"输入矩阵的行数、列数、非零元的个数：\"); scanf(\"%d%d%d\ M.data[0].i=0; for(i=1;i<=M.tu;i++) { j=0; do { j++; if(j>3) //控制跳出死循环 { printf(\"本次输入失败！\"); return ERROR; } printf(\"按行序输入第%d个非零元素所在的行(1~%d)列(1~%d)值：\ scanf(\"%d%d%d\ k=0; if(m<1||m>M.mu||n<1||n>M.nu) //行或列超出范围 k=1; if(m void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵 M { int i; printf(\"稀疏矩阵对应的三元组表为：\\n\\n\"); printf(\"行 列 元素值、\\n\\n\"); for(i=1;i<=M.tu;i++) printf(\"%2d%4d%8d\\n\ printf(\"\\n\\n\"); } void print(RLSMatrix A) //打印矩阵函数，以通常形式输出矩阵 { int k=1,a,b; printf(\"稀疏矩阵的通常形式为：\\n\"); int M[MAXSIZE][MAXSIZE]; for(a=0;a **********************************************************\\n\\n\"); } ////头文件结束 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.data[p].j==col) { T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].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) num[col]=0; for(t=1;t<=M.tu;++t) ++num[M.data[t].j]; cpot[1]=1; for(col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; printf(\"\\n辅助数组的值为：\\n\"); printf(\"列号：\"); for(t=1;t<=M.nu;++t) printf(\"%4d\ printf(\"\\n\"); printf(\"num[]\"); for(t=1;t<=M.nu;++t) printf(\"%4d\ printf(\"\\n\"); printf(\"cpot[]\"); for(t=1;t<=M.nu;++t) printf(\"%4d\ printf(\"\\n\\n\"); for(p=1;p<=M.tu;++p) { col=M.data[p].j; //快速转置算法 q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++cpot[col]; } } 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函数，用来设置控制台标题 do { showtip(); //调用菜单函数 int i; scanf(\"%d\ 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(\"\\n\\n\");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(\"\\n\\n\");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(\"\\n\\n\"); printf(\"求A的转置矩阵B------(快速转置):\\n\"); FastTransposeSMatrix(A,B); PrinRLSMatrix(B); print(B); DestroySMatrix(A); DestroySMatrix(B); printf(\"\\n\\n\");break; } printf(\" **********请选择是否继续输入其他稀疏矩阵？**********\\n\"); printf(\" 1 是，输入其他矩阵\\n\"); printf(\" 0 否，不输入\\n\"); printf(\" ****************************************************\"); fflush(stdin);//清除输入缓存区 scanf(\"%d\ }while(j==1); } 运行结果： （1）创建矩阵 （2）一般转置 （3）快速转置 2、 稀疏矩阵乘法、加法的算法（一般&十字链表） 代码： #include #include int e;//非零元的值 }triple; //定义三元组 typedef struct { triple data[Size+1];//矩阵中的元素 int rops[Size1+1];// rops[i]为第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.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.rhead[k]=NULL; for(k=1;k<=M.n;k++) M.chead[k]=NULL; printf(\"输入非零元的行，列和值，空格隔开：\\n\"); for(k=1;k<=M.t;k++)//输入非零元 { scanf(\"%d %d %d\ p=(node *)malloc(sizeof(node)); p->i=i; p->j=j; p->e=e; if(M.rhead[i]==NULL||M.rhead[i]->j>j)//插入元素所在行无非零元或首非零元的列标大于插入元素的列标 { p->right=M.rhead[i]; M.rhead[i]=p; } else { for(q=M.rhead[i];(q->right)&&q->right->j p->right=q->right; q->right=p; } if(M.chead[j]==NULL||(M.chead[j]->i>i))//插入元素所在列无非零元或首非零元的行标大于插入元素的行标 { p->down=M.chead[j]; M.chead[j]=p; } else { for(q=M.chead[j];(q->down)&&q->down->i p->down=q->down; q->down=p; } } } void printcross(crosslist A)//输出十字链表 { if(A.m==0) printf(\"十字链表为空!\\n\"); else { printf(\"十字链表为:\\n\"); int i,j; for(i=1;i<=A.m;i++) { link p=A.rhead[i]; for(j=1;j<=A.n;j++) { if((p)&&(j==p->j)) { printf(\"%5d\->e); p=p->right; } else printf(\"%5d\ } printf(\"\\n\"); } } printf(\"\\n\"); } crosslist addcross() { printf(\"十字链表加法:\\n\"); crosslist a,b;// 创建两个十字链表对象，并初始化 createcross(a); createcross(b); node *pre,*h[51],*pa,*pb,*q;//定义辅助指针，pa，pb分别为a,b当前比较的元素，pre为pa的前驱元素 int i,j,k=0,m,n; //h[j]指向j列的当前插入位置 if(a.m!=b.m||a.n!=b.n) printf(\"格式不对，不能相加!\\n\"); else { for(i=1;i<=a.m;i++) { pa=a.rhead[i]; pb=b.rhead[i]; pre=NULL; for(j=1;j<=a.n;j++) h[j]=NULL; while(pb) { link p; p=(node *)malloc(sizeof(node)); // 开辟新节点，存储b中取出的元素 p->i=pb->i; p->j=pb->j; p->e=pb->e; if(pa==NULL||pa->j>pb->j)//当a此行已经检查完或者pb因该放在pa前面 { if (pre==NULL) a. rhead[p->i]=p; else pre->right=p; p->right=pa; pre=p; if (h[p->j]==NULL)//当前插入位置下面无非零元 //因为是逐行处理，so,h[p->j]，依次下移 //因此每次都是指向插入的位置 { a. chead [p->j]= p; p->down = NULL; } else { p->down = h[p->j]->down; h[p->j]->down = p; } h[p->j]=p;//*******h[p->j]下移指向下次插入的位置 pb=pb->right;//pb指向该行下个元素 } else if((pa&&pa->j { pre = pa; h[pa->j]=pa;//移动h[]，使其指向下次插入的位置 pa = pa->right; } else if(pa->j==pb->j) { pa->e+=pb->e; if(pa->e)//不为零 { pre=pa; h[pa->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 { h[p->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.rhead[k]=NULL; for(k=1;k<=b.n;k++) c.chead[k]=NULL; r=(link *)malloc((b.n+1)*sizeof(link)); for(i=1;i<=a.m;i++) { u=(node *)malloc(sizeof(node)); u->e=0; u->i=0; u->j=0; for(k=1;k<=b.n;k++)//初始化r[] r[k]=u; p1=p=a.rhead[i]; for(j=1;j<=b.n;j++) { p=p1; q=b.chead[j]; v=(node *)malloc(sizeof(node));//初始化v，v为将插入c矩阵的元素 v->e=0; v->i=i; v->j=j; while(p&&q) { if(p->j>q->i) q=q->down; else if(p->j { //同建立十字链表 if(c.rhead[i]==NULL||c.rhead[i]->j>j)//插入元素所在行无非零元或首非零元的列标大于插入元素的列标 { v->right=c.rhead[i]; c.rhead[i]=v; } else { for(p2=c.rhead[i];(p2->right)&&(p2->right->j v->right=p2->right; p2->right=v; } if(c.chead[j]==NULL||c.chead[j]->i>i)//插入元素所在列无非零元或首非零元的行标大于插入元素的行标 { v->down=c.chead[j]; c.chead[j]=v; } else { for(p2=c.chead[j];(p2->down)&&(p2->down->i v->down=p2->down; p2->down=v; } } } } } } void create(juzhen & M) //创建稀疏矩阵 { int i,t=0; printf(\"输入矩阵行数和列数and非零元的个数，以空格隔开:\\n\"); scanf(\"%d %d %d\ printf(\"输入矩阵非零元的行，列，和数值(中间空格隔开):\\n\"); for(i=1;i<=M.tu;i++) scanf(\"%d %d %d\输入三元组的元素 for(i=1;i<=Size1;i++)//初始化rops【】 M.rops[i]=0; for(i=1,t=1;i<=M.mu;i++)//得到各行第一个元素的序号 { M.rops[i]=t; while(M.data[t].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\"); else { while(k1<=A.tu&&k2<=B.tu)//当A，B中的非零元都没用完 { if(A.data[k1].i C.data[k++]=B.data[k2++]; else if(A.data[k1].j 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.data[k].i==i&&A.data[k].j==j)//行和列分别对应相等则输出相应非零元，否则输出零 printf(\"%5d\ else printf(\"%5d\ } printf(\"\\n\");//该行输出结束，空行输出下一行 } printf(\"\\n\"); } void multy(juzhen A,juzhen B,juzhen &C)//稀疏矩阵乘法 { int arow,brow,ccol,temp[51],p,q,t,tp,i;//各变量代表含义见下面 printf(\"稀疏矩阵乘法:\\n\"); create(A); create(B); if(A.nu!=B.mu) printf(\"格式错误，不能相乘！\\n\"); else { C.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;i<51;i++)//初始化temp temp[i]=0; if(arow } } for(ccol=1;ccol<=B.nu;ccol++)// if(temp[ccol])//temp【ccol】不为零，则把值赋到c中，c.tu加1。 { C.data[++C.tu].e=temp[ccol]; C.data[C.tu].i=arow; C.data[C.tu].j=ccol; } } } } } void clear(juzhen & A)//清空稀疏矩阵 { int i; A.mu=0; A.nu=0; A.tu=0; for(i=0;i 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\ 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 typedef struct GLode//广义表结构体的定义 { int tag; union { ElemType atom; struct GLode *hp; } val; struct GLode *tp; } GList; typedef struct //栈结构的定义 { ElemType data[maxlen] ; 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; else { h->tag=0; h->val.atom=ch; } } else h=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(\"\"); else DispGL(g->val.hp); } else printf(\"%c\->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 (dep>max) 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; } else if(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->data[s->top]=')'; if (g->val.hp==NULL) printf(\"\"); else NIGList(g->val.hp,s); } else { s->top++; s->data[s->top]=g->val.atom; } if (g->tag==1) { s->top++; s->data[s->top]='('; } if (g->tp!=NULL) { s->top++; s->data[s->top]=','; NIGList(g->tp,s); } } } //广义表的输出 void Pop(SeqStack *s) { while(s->top>=0) { printf(\"%c\->data[s->top]); s->top--; } } //以下主函数用于调试 void main() { GList *g,*gt; printf(\"请输入一个广义表:如((a,b),c)\\n\"); char str[30]; 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(\"请 选 择:(0～5)\\n\"); scanf(\"%d\ switch (y) { case 1: printf(\"请输入要查找的元素:\"); mark=0; getchar(); scanf(\"%c\ FindGListX(g,x,mark); if (mark) printf(\"^_^该元素存在于您输入的表中!\\n\"); else printf(\"T_T对不起，没有找到该元素!\\n\"); break; case 2: gt=tail(g); printf(\"表尾:\");DispGL(gt);printf(\"\\n\"); break; case 3: printf(\"广义表的深度:%d\\n\ 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\ if(xz==1) system(\"cls\"); else { system(\"cls\"); printf(\"再见,欢迎再次使用!\\n\"); } } } 运行结果： （1） 创建广义表 （2）广义表的查找 （3）广义表表尾 （5）广义表的逆表 （4）广义表的深度
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- 517ttc.cn 版权所有 赣ICP备2024042791号-8
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务