实验三 稀疏矩阵和广义表子系统.doc

韶 关 学 院 学 生 实 验 报 告 册实验课程名称：数据结构与算法实验项目名称：实验三 稀疏矩阵和广义表子系统实验类型（打 ）：（基础 、综合 、设计 ）院 系：计算机科学学院 专 业：计算机科学技术姓 名：* 学 号：*指导老师：陈正铭 韶关学院教务处编制一、实验预习报告内容 预习日期：2011年 9 月 18 日【实验目的】（1） 掌握稀疏矩阵三元组表的存储方法。 （2）掌握稀疏矩阵三元组表创建、显示、转置和查找等算法。 （3）掌握广义表的存储方法。 （4）掌握广义表的新建、显示和查找等算法。 （5）掌握稀疏矩阵三元组表和广义表的算法分析方法。【实验内容】（1）编写稀疏矩阵三元组表的存储程序； （2）编写疏矩阵三元组表创建、显示、转置和查找程序； （3）编写建立广义表的程序； （4）编写广义表的显示和查找程序； （5）设计选择式菜单，其一级菜单形式如下：稀疏矩阵和广义表子系统* 1-稀 疏 矩 阵 * 2-广 义 表 * 0-退 出 * 请输入菜单号（0-2）: 稀疏矩阵二级菜单形式如下： 稀疏矩阵的三元组存储* 1-新 建 * 2-转 置 * 3-查 找 * 4-显 示 * 0-返 回 * 请输入菜单号（0-4）: 广义表二级菜单形式如下： 广 义 表* 1-新 建 * 2-查 找 * 3-显 示 * 0-返 回 * 请输入菜单号（0-3）: 三、实验报告内容 2011年 9 月 21 日【实验程序主要代码】：#include#include#include#include#define SMAX 100 / 三元组非零元素的最大个数typedef struct SPNode / 定义三元组int i,j,v; / 三元组非零元素的行、列和值;typedef struct sparmatrix / 定义稀疏矩阵int rows,cols,terms; / 稀疏矩阵行、列和非零元素的个数SPNode dataSMAX; / 三元组表;typedef struct linknode / 定义广义表int tag; / 区分原子项或子表的标志位linknode *link; / 存放下一个元素的地址union data_sublistchar data; / 存放原子的值linknode *sublist; / 存放子表的指针node;sparmatrix CreateSparmatrix() / 创建稀疏矩阵 sparmatrix A; printf(ntt请输入稀疏矩阵的行数,列数和非零元个数(用逗号隔开): ); scanf(%d,%d,%d,&A.rows,&A.cols,&A.terms); for(int n=0;n=A.terms-1;n+)printf(ntt输入非零元值(格式: 行号,列号,值): );scanf(%d,%d,%d,&A.datan.i,&A.datan.j,&A.datan.v);return A;sparmatrix Trans(sparmatrix A) / 转置稀疏矩阵sparmatrix B;B.rows=A.cols; B.cols=A.rows; B.terms=A.terms;for(int n=0;n=A.terms-1;n+)B.datan.i=A.datan.j;B.datan.j=A.datan.i;B.datan.v=A.datan.v;return B;void ShowSparmatrix(sparmatrix A) / 显示稀疏矩阵 int k; printf(ntt); for(int x=0;x=A.rows-1;x+) for(int y=0;y=A.cols-1;y+)k=0;for(int n=0;n=A.terms-1;n+) if(A.datan.i=x)&(A.datan.j=y)printf(%8d,A.datan.v);k=1;if(k=0)printf(%8d,k); printf(ntt); void SearchSparmatrix(sparmatrix A,int s) / 查找稀疏矩阵中非零元素 int n,t; t=A.terms; for(n=0;ntag=0;gh-node.data=*s;gh-link=NULL;elsegh=new linknode;gh-tag=1;p=gh;s+;strncpy(subs,s,len-2);subslen-2=0;doDisastr(subs,hstr);r=CreateGL(hstr);p-node.sublist=r;q=p;len=strlen(subs);if (len0)p=new linknode;p-tag=1;q-link=p;while (len0);q-link=NULL;return gh;void Showvl(linknode *gnode) / 显示广义表linknode *p,*q; if(gnode)dop=gnode-node.sublist;q=gnode-link;while(q&p&!p-tag)printf(%c,p-node.data);p=q-node.sublist;q=q-link;if(p&!p-tag)printf(%c,p-node.data); break; elseif(!p)printf();else Showvl(p);if(q)printf(,);gnode=q;while(gnode);printf(b); / 输出格式中的b表示退格int Search(linknode *gnode,char x) / 查找广义表中的元素int find=0;if(gnode!=NULL)if(!gnode-tag & gnode-node.data=x)return 1;else if(gnode-tag)find=Search(gnode-node.sublist,x);if(find)return 1;else return Search(gnode-link,x);else return 0;void vastlist() / 广义表 int ch=1,choice; char x; char strSMAX ; linknode *vastlist=NULL; while(ch) printf(n);printf(ntt 广 义 表n );printf(ntt*);printf(ntt* 1-新 建 *);printf(ntt* 2-查 找 *);printf(ntt* 3-显 示 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(nntt 请输入菜单号(0-3): );scanf(%u,&choice);switch(choice) case 1:printf(ntt新建广义表: );scanf(%s,&str);vastlist=CreateGL(str);break; case 2:if(vastlist=NULL)printf(ntt广义表为空! n);elseprintf(ntt输入要查找的广义表中的元素: );scanf(%s,&x);if(Search(vastlist,x)=1)printf(ntt该元素在广义表中存在! n);elseprintf(ntt该元素在广义表中不存在! n);break; case 3:if(vastlist=NULL)printf(ntt广义表为空! n);elseprintf(ntt);printf();Showvl(vastlist);break; case 0:ch=0;break;if(choice=1|choice=2|choice=3)printf(ntt);system(pause);system(cls);else system(cls); void main() int ch=1,choice; while(ch) printf(n);printf(ntt 稀疏矩阵和广义表子系统n );printf(ntt*);printf(ntt* 1-稀 疏 矩 阵 *);printf(ntt* 2-广 义 表 *);printf(ntt* 0-退 出 *);printf(ntt*);printf(nntt 请输入菜单号(0-2): );scanf(%u,&choice);switch(choice) case 1:system(cls);sparmatrix(); break; case 2:syste