int i,Mj; int arow, Mlim, Nlim, Mcol, Nrow; int ctemp[MAXC]; Q->tu=0;//初始化Q Q->mu=M.mu; Q->nu=M.nu; if(M.tu*N.tu!=0) { //非零矩阵 for(arow=1; arow<=M.mu; arow++) { for(i=1; i<=M.nu; i++)//清空累加器 ctemp[i]=0; Q->rpos[arow]=Q->tu+1; //给Q->rpos[]数组赋值
Mlim = arow for( Mcol=M.rpos[arow]; Mcol Nlim = Mj for(i=1; i<=Q->nu; i++) {//列号对应元素不为零，赋值 if( ctemp[i] ) { if( ++Q->tu > MAXSIZE ) return 0; Q->matrix[Q->tu].i = arow; Q->matrix[Q->tu].j = i; Q->matrix[Q->tu].data = ctemp[i]; } } } } return 1; } 四、 注意事项： 1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序； 2. 用数组存放矩阵的三元组，矩阵的行数和列数及非0数据从键盘输入； 3. 若两个矩阵不能相乘则输出“Error” 实验七 二叉树1 16 一、实验目的： 1． 进一步掌握指针变量的含义。 2． 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3． 掌握用指针类型描述、访问和处理二叉树的运算。 二、 实验要求： 1． 认真阅读和掌握本实验的程序。 2． 上机运行本程序。 3． 保存和打印出程序的运行结果，并结合程序进行分析。 4． 按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。 三、实验内容： 编写一个程序实现下列目标。 1，根据输入的数据建立一个二叉树 2，输出二叉树（输出的结果应为树型结构） 3，输出其前序、中序和后序遍历的结果 //Filename:exp7.cpp //date:05-31 #include void CreateBTNode(BTNode *&b,char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break; case')':top--;break; case',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch; p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } } 17 void DispBTNode(BTNode *b) { if(b!=NULL) { printf(\ if(b->lchild!=NULL||b->rchild!=NULL) { printf(\ DispBTNode(b->lchild); if(b->rchild!=NULL) printf(\ DispBTNode(b->rchild); printf(\ } } } void PreOrder(BTNode *b) { if(b!=NULL) { printf(\ PreOrder(b->lchild); PreOrder(b->rchild); } } void InOrder(BTNode *b) { if(b!=NULL) { InOrder(b->lchild); printf(\ InOrder(b->rchild); } } void PostOrder(BTNode *b) { if(b!=NULL) { PostOrder(b->lchild); PostOrder(b->rchild); printf(\ } } void main() { BTNode *b; CreateBTNode(b,\ printf(\二叉树b:\ printf(\先序遍历序列:\\n\ PreOrder(b);printf(\ printf(\中序遍历序列:\\n\ InOrder(b);printf(\ printf(\后序遍历序列:\\n\ PostOrder(b);printf(\} 18 四、 注意事项： 1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 实验八 二叉树2 一、实验目的： 1． 进一步掌握指针变量的含义。 2． 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3． 掌握用指针类型描述、访问和处理二叉树的运算。 二、 实验要求： 1． 认真阅读和掌握本实验的程序。 2． 上机运行本程序。 3． 保存和打印出程序的运行结果，并结合程序进行分析。 4． 按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。 三、实验内容： 按先序次序输入二叉树中结点的值（一个字符），`0`表示空树，生成二叉树的二叉链表存储结构， a为指向根结点的指针。然后按中序顺序遍历二叉树。 算法思想：先访问左子树,再访问根结点,最后访问右子树。 四、 注意事项： 1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 **参考程序如下： //Filename:exp8.cpp //date:06-07 #include struct stu *left,*right; }sn; sn *Create(sn *a) { char ch; scanf(\ if(ch==' ')a=NULL; else{a=(sn *)malloc(sizeof(sn)); if (!a) printf(\ a->data=ch; a->left=Create(a->left); a->right=Create(a->right); } return(a); } void inc(sn *b) { if(b){ inc(b->left); printf(\ inc(b->right);} } 19 void main( ) { sn *t,*q; q=NULL; t=Create(q); inc(t); printf(\//getch(); } 实验数据：abc00de0g00f000(0表示空格) 实验九 图的操作 一、实验目的： 1． 掌握图的基本存储方法。 2． 掌握有关图的操作算法并用高级语言编程实现； 3． 熟练掌握图的两种搜索路径的遍历方法。 二．实验要求： 1． 认真阅读和掌握本实验的算法； 2． 上机将本算法实现； 3． 保存和打印出程序的运行结果，并结合程序进行分析； 4． 按照对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。 二、实验内容： 以邻接矩阵和邻接表的方式存储连通图。然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。 算法 如下： 深度优先遍历的递归算法 （1）深度优先遍历算法 int visited[MaxVertexNum]； //访问标志向量是全局量 void DFSTraverse(ALGraph *G) { //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同 int i； for(i=0;i visited[i]=FALSE； //标志向量初始化 for(i=0;i if(!visited[i]) //vi未访问过 DFS(G，i)； //以vi为源点开始DFS搜索 }//DFSTraverse （2）邻接表表示的深度优先搜索算法 void DFS(ALGraph *G，int i){ //以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p； printf(\：％c\，G->adjlist[i].vertex)；//访问顶点vi visited[i]=TRUE； //标记vi已访问 p=G->adjlist[i].firstedge； //取vi边表的头指针 while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex if (!visited[p->adjvex])//若vi尚未被访问 DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索 p=p->next； //找vi的下一邻接点 } }//DFS //文件名:exp9.cpp //date:06-21 #include 20