(数据结构课程设计十字链表.docVIP

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