PAGE\*MERGEFORMAT11中南民族大学数据结构课程设计报告姓名：康宇年级：2010学号：10061014专业：计算机科学与技术指导老师：宋中山2013年4月15日实习报告：十字链表实习报告题目：设计一个用十字链表实现稀疏矩阵相加的程序班级：计科一班姓名：康宇学号：10061014完成日期：2013.4.15需求分析十字链表分析：当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。例如，在作“将矩阵B加到矩阵A上”的操作时，由于非零元的插入或删除将会引起A.data中元素的移动。为此，对这种类型的矩阵，采用脸是存储结构表示三元组的线性表更为恰当。测试数据：两个矩阵的规模以及非零元个数都是由用户自己确定，然后有读者输入具体的非零元位置与数据域，然后输出用户输入的两个矩阵后，再把相加的矩阵输出。实现提示：在链表中，每个非零元可用一个含5个域的结点表示，其中i,j和e这三个域分别表示该非零元所在的行和列和非零元的值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。概要设计1.元素类型(栈)：typedefstructOLNode//结点类型{inti,j;//行列inte;//数据域structOLNode*right,*down;//行和列的后继域}OLNode,*OLink;typedefstruct//创建一个总的头结点{OLink*rhead,*chead;//行列链表头指针intmu,nu,tu;//稀疏矩阵的行数，列数和非零元个数}CrossList;2.本程序包括四个模块：1）主程序：Voidmain(){CrossListA,B;CreateSmatix(A);//构建矩阵ACreateSmatix(B);//构建矩阵B调用输出函数print(A)输出A;调用输出函数print(B)输出B;Add(A,B);//实现矩阵相加A+B，结果放到A中调用输出函数print(A)输出相加后的矩阵;}2）矩阵构建函数：voidCreateSmatix(CrossList&M){scanf("%d%d%d",行数m,列数n,非零元个数t);动态创建m+1个结点长的行链表指针；动态创建n+1个结点长的列链表指针；初始化创建的行列链表指针；for(k=0;k<t;k++){If(输入非零结点){生成结点；If(对应的行头结点为空||头结点列元素大于结点)插入结点；Else寻找在行表中的位置；完成行插入；If(对应的列头结点为空||头结点行元素大于结点)插入结点；Else寻找在列表中的位置；完成列插入；}}}3）矩阵输出函数：voidprint(CrossList&M){printf("\t行\t列\t值\n");OLinkp;for(inti=1;i<M.mu+1;i++){P=行的头结点；while(结点不空){printf("\t%d\t%d\t%d\n",p->i,p->j,p->e);p指针下移；}}释放p;}4）矩阵相加函数：voidAdd(CrossList&M,CrossList&N){intk;OLinkp=NULL,s=NULL;OLinkpa,pb,pre;//pre指示pa所指结点的前驱结点动态创建标记列结点的指针hl;for(k=1;k<=M.nu;k++)指针hl只想对应的列头结点；for(k=1;k<=N.mu;k++)//每行依次处理{pre=NULL;pa=M.rhead[k];//标记矩阵A的结点pb=N.rhead[k];//标记矩阵B的结点while(B的结点不空){if(A对应的结点为空||A的列结点>B的列结点){创建pb所指结点的复制新结点p初始化pb;if(pre为空)M.rhead[p->i]=p;elsepre->right=p;p->right=pa;pre=p;//pre始终指向pa