十字链表实验报告.docVIP

院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 2010级 课程名称： 数据结构 学 号： 姓 名： 徐丽 指导教师： 宋中山 2012年 5月1日 稀疏矩阵的应用（十字链表） 一、 设计要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、乘。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （5）退出系统。 二、 概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。 2．存储结构设计 本系统采用单链表结构(single list)存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储；每个结点里面包含行下标(row)，列下标(colum)和对应的数值(value)，它们是整型数据，还有两个指针(right)、(down),属于data结构体。全部的信息用结构体(crosslist)包含，包括指针数组(element * one.rhead和*one.colum）和总共的行数（row_size）,列数（colum_size）以及非零元素的个数(non_zero_amount)。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数init_matrix( )实现。建立稀疏矩阵用creat_matrix( )实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数add_matrix( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数multi_matrix( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）退出： 即退出稀疏矩阵的应用系统。由exit(1)函数实现，但用户选择此功能时，系统会提示你是否确实想退出，如果是，则退出，否则继续。 三、 模块设计 1.模块设计 本程序包含2个模块：主程序模块和各功能实现模块。调用关系如图7-8所示。 主程序模块 2．系统子程序及功能设计 本系统共设置7个子程序，各子程序的函数名及功能说明如下。 （1）int init_matrix(crosslist one) // 初始化矩阵one (2)_int creat_matrix(crosslist one) //建立矩阵one （3）int print_matrix(crosslist one) // 输出矩阵one的信息 （4）int add_matrix(crosslist one,crosslist two, crosslist three) //把one 和two两个矩阵相加，结果是three （5）int multi_matrix(crosslist one, crosslist two,crosslist three) //把one和two两个矩阵相乘，结果是three （6）int main( ) // 主函数。设定界面的颜色,大小和窗口的标题，调用工作区模块函数 四、 详细设计 1．数据类型定义 （1）稀疏矩阵的定义： typedef struct list {node structure //结点结构 int row; //行标 int colum; //列标 int value; //值 struct list *right; //同一行的下一个结点 struct list *down; //同一列的下一个结点 }node,*element; typedef struct link {cross list structure int row_size; //行数 int colum_size; //列数 int non_zero_amount; //非零元素个数 element *rhead; //行指针基指 element *chead; //