十字链表实验报告

十字链表实验报告院系：计算机科学学院专业：计算机科学与技术年级：2021级课程名称：数据结构学号：10061065姓名：徐丽指导教师：宋中山2021年5月1日稀疏矩阵的应用（十字链表）一、设计要求1．问题描述设计程序用十字链表实现稀疏矩阵的加、乘。2．需求分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（5）退出系统。二、概要设计为了实现以上功能，可以从3个方面着手设计。1．主界面设计为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。2．存储结构设计本系统采用单链表结构(singlelist)存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储；每个结点里面包含行下标(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）intinit_matrix(crosslist&one)//初始化矩阵one(2)_intcreat_matrix(crosslist&one)//建立矩阵one（3）intprint_matrix(crosslist&one)//输出矩阵one的信息（4）intadd_matrix(crosslistone,crosslisttwo,crosslist&three)//把one和two两个矩阵相加，结果是three（5）intmulti_matrix(crosslistone,crosslisttwo,crosslist&three)//把one和two两个矩阵相乘，结果是three（6）intmain()//主函数。设定界面的颜色,大小和窗口的标题，调用工作区模块函数四、详细设计1．数据类型定义（1）稀疏矩阵的定义：typedefstructlist{nodestructure//结点结构introw;//行标intcolum;//列标intvalue;//值structlist*right;//同一行的下一个结点structlist*down;//同一列的下一个结点}node,*element;typedefstructlink{crossliststructureintrow_size;//行数intcolum_size;//列数intnon_zero_amount;//非零元素个数element*rhead;//行指针基指element*chead;//列指针基指}crosslist;2．系统主要子程序详细设计（1）主程序模块设计及用户工作区模块设计主函数。设定操作区用户界面的颜色,大小和窗口的标题，调用工作区模块函数。intmain(void){crosslistone,two,three;//声明三个十字链表链表intchoice;//选择的标志charflag;//选择的标志while(OK)//死循环{system(cls);//清屏system(colora4);//界面颜色设定system(modeconcols=80lines=400);//界面大小设定system(title#CrosslistToDealWithSparseMatrix#);//窗口标题设定//下面是主界面printf(\t@**********************************************************@\n);putchar('\n');printf(\t\t%c---Sparse-Matrix's--Application-System---%c\n,2,2);putchar('\n');printf(\t@*************************************************************@\n);printf(\t$*************************************************************$\n);printf(\t\t%c----------------Functions----------------%c\n,2,2);putchar('\n');printf(\t\t%c-----------------------------------------%c\n,2,2);printf(\t\t%cprintf(\t\t%c-----------------------------------------%c\n,2,2);printf(\t\t%cprintf(\t\t%c-----------------------------------------%c\n,2,2);printf(\t\t%cprintf(\t\t%c-----------------------------------------%c\n,2,2);putchar('\n');printf(\t\t%c-----------CrosslistRowFirst-----------%c\n,2,2);printf(\t$*************************************************************$\n);printf(\t\t!!Tips:ifyouwanttobreakjustpressCtrl+C\n);printf(\t$*************************************************************$\n);printf(Pleasechooseachoice:(1--3)\n);printf(Yourchoiceis:);scanf(%d,&choice);//输入选择switch(choice){//下面是每项的功能putchar('\n');printf(\tinit_matrix(one);//初始化矩阵putchar('\n');printf(\tcreat_matrix(one);//建立矩阵putchar('\n');printf(Printthefirstmatrix\n);printf(\t\tRow\t\t\tColum\t\t\tValue\n);printf(\t\t-------------------------------------------------\n);print_matrix(one);//输出矩阵printf(\tinit_matrix(two);putchar('\n');printf(\tcreat_matrix(two);putchar('\n');printf(Printthesecondmatrix\n);printf(\t\tRow\t\t\tColum\t\t\tValue\n);printf(\t\t-------------------------------------------------\n);print_matrix(two);case1:printf(\t\n);//加法printf(Addthetwomatrix\n);init_matrix(three);putchar('\n');add_matrix(one,two,three);//矩阵相加printf(Theresultisbelow:\n);print_matrix(three);break;case2:printf(\t/*multiplythetwomatrix*/printf(Multiplythetwomatrix\n);init_matrix(three);multi_matrix(one,two,three);//矩阵相乘printf(Theresultisbelow:\n)；print_matrix(three);break;case3:printf(Areyousuretoquitthesystemscanf(%c,&flag);if(flag=='y'||flag=='Y'||flag=='\n'){printf(\t\t%c-------%c-------%c-------%c-------%c\n,2,2,2,2,2);putchar('\n');printf(\t\t(^_^)ThanksForUsingThis!(^_^)\n);putchar('\n');printf(\t\t%c-------%c-------%c-------%c-------%c\n,2,2,2,2,2);putchar('\n')；exit(OK);}else{printf(………………continue………………\n);}break;default:printf(Pleaseinputavalidchoicefrom1to3!\n);//选择无效的选择break;}//switch}//whilereturnOK;}2.稀疏矩阵操作各子函数的定义：（1）初始化稀疏矩阵：Intinit_matrix(crosslist&one){//初始化one.row_size=0;one.colum_size=0;one.non_zero_amount=0;one.rhead=NULL;one.chead=NULL;returnOK;}//init_matrix（2）建立稀疏矩阵：intcreat_matrix(crosslist&one){//赋值inti;//循环中的计数elementnews,temp;/*输入行数和列数以及非零元素的个数*/printf(Inputtherowsizeofthematrix:);scanf(%d,&one.row_size);printf(Inputthecolumsizeofthematrix:);scanf(%d,&one.colum_size);printf(Inputthenonzeroamountofthematrix:);scanf(%d,&one.non_zero_amount);/*分配内存，第一个元素不用*/one.rhead=(element*)malloc(sizeof(element)*(one.row_size+1));assert(one.rhead!=NULL);//asserthavespaceone.chead=(element*)malloc(sizeof(element