《第五章 数组和广义表.doc》由会员分享，可在线阅读，更多相关《第五章 数组和广义表.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除第五章 数组和广义表一、稀疏矩阵1.题目要求：矩阵在工程计算上的应用非常广泛。本题目要求对稀疏矩阵完成加法运算。本题目要求用以下存储方法表示稀疏矩阵，即：以一维数组顺序存放非零元素的行号、列号和数值，行号-1作为结束标志。例如，如图所示的稀疏矩阵A，则存储在一维数组B中后内容为：B0=0,B1=2,B2=3,B3=4,B4=6,B5=5,B6=3,B7=4,B8=7,B9=5,B10=1,B11=9,B12=-1 0 0 3 0 0 0 0 0 0 0 0 0 0 0 5 0A= 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0
2、 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0假设有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，要求编写求矩阵加法如C=A+B的算法，C矩阵存放在数组C中。2.算法分析：根据设计要求，首先需要解决如何将一个稀疏矩阵对应存储到一个一维数组中，然后再进行矩阵加法时依次扫描矩阵A和B的列值，并以行优先。当行列相同时，将第三个元素值相加的和以及行列号三个元素存入结果数组C.中；不相同时，将A或B的值三个元素直接存入结果数组中。二、矩阵运算1.题目要求：利用C语言实现：1、矩阵的转置、相加和相乘运算；2、将稀疏矩阵转换为三元组后实现其转置、查找、相加和相乘运
3、算。Java语言实现部分见网站。2.算法分析：1.矩阵的转置、相加和相乘：矩阵采用二维数组存储，一个m*n的二维数组a m*n转置，就是将其行、列互换，形成一个n*m的二维数组b n*m。二维数组的相加运算，是将两个数组对应位置上的元素相加，这要求被加的两个数组维数相同，且每一维中所含的元素数目相同。一个m*t的二维数组a m*t与一个t*n的数组b t*n相乘后的结果是一个m*n的二维数组c m*n。2.稀疏矩阵的转换、转置、查找、相加和相乘：1）转换：按行优先顺序扫描二维数组a m*n的元素，将不为0者存入三元组b中。2）实现三元组表a.data到三元组表b.data的转置：按b.data
4、中三元组的顺序在a.data中找到相应的三元组的形式进行转换，实际就是按矩阵M的列序进行转换。为了找到M中的每一列的所有非零元素，每一次都需要对a.data从第一行开始进行扫描。3）查找：以三元组的非零元素个数为循环终止条件，查找相应的关键字。4）相加：将两个稀疏矩阵首先转换为两个相应的三元组a,b表示。判断两个三元组的维数是否相同，如果维数不同，不能相加。维数相同的情况下，比较行号。行号相等时，比较列号，若不等，将两个三元组中列号小的项存入结果三元组c中；若列号也相等，则将对应的值相加后存入结果三元组c中。如果a的行号小于b的行号，将a的项存入c中，否则将b的项存入c中。5）相乘：将a,b两
5、个三元组中的元素按矩阵相乘的格式进行乘法运算，判断其值，若不等于0，将其存入相应的三元组c中。三、统计成绩1.题目要求：使用数组和指针统计成绩。要求输入班级以下各科考试平均成绩：数学、物理、外语、政治、体育、人数 要求统计出全班学期总平均成绩以及得分最低的科目和该科目的成绩。 本题目考虑如何为字符分配内存，并将字符数组的内容也存入所分配的内存中，使用指针实现设计要求。2.算法分析：设计步骤：1、设计循环将各门课成绩和总人数读入数组；2、为各门课程名称申请内存并赋值；3、为所求各项申请内存并赋值；4、求最小值和平均值；5、作相应的赋值及输出。四、广义表运算1.题目要求：本设计要求实现广义表的建立
6、、查找、输出、取表头和取表尾以及求深度等。本设计用一个主控菜单控制，共分为6个子系统。1建立广义表首先提示用户输入广义表字符串，要求构成广义表的合法字符为：大写或小写字母、空格字符、圆括号和逗号，并且设广义表的原子为单个字母。如果输入字符为非法字符时要求能给出错误提示。2输出广义表对给定存储结构的广义表，打印输出其表示格式。3结点的查找查找数据域值为x的结点.4. 求广义表表头按照广义表表头的定义，编写求表头的算法。5 求广义表表尾按照广义表表尾的定义，编写求表尾的算法。6求广义表的深度求一个表展开后所包含括号的层数，它是广义表的一种度量。2.算法分析：1.建立广义表CreateGlist(G
7、list &GL)。通过用户输入的广义表表达式建立相应的广义表，并且边输入便建立。基本思想是：在广义表表达式中，遇到左括号“（”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到表达式字符串输入结束（假设结束符号为;）。因此，实现的过程描述如下：void CreateGlist(Glist &GL) 读入广义表的一个字符给ch; if(ch!=空格) 建立一个新结点；if(ch=() 递归调用构造子表； else 构造原子结点； 读表达式中一字符到ch; if(ch=,)递归构造后续广义表； else 表示遇)或结束符;时，无后续表； 2.输出广义表PrintGlist(Gl
8、ist GL)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号(。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完成后，再打印一个右括号)。若遇到tag=0的结点，则直接输出其数据域的值。若还有后续元素，则递归调用后续每个元素，直到遇到link域为NULL。其实现过程描述如下：void PrintGlist(Glist GL)if(GL=NULL）if（GL-tag=list）输出左括号(；if（GL-slink=NULL）输出一个空格；else 递归调用输出子表；else 输出结点数据域值；if（GL-tag=list）打
9、印右括号)；if（GL-link!=NULL）输出逗号,；递归调用输出下一个结点；3.广义表的查找FindGlistX(Glist GL,DataType x,int &mark)。在给定的广义表中查找数据域为x的结点，采用的算法思想是：若遇到tag=0的原子结点，如果是要找的结点，则查找成功；否则，若还有后续元素，则递归调用本过程查找后续元素，直到遇到link域为NULL。若遇到tag=1的结点，则递归调用本过程在该子表中查找，如还有后续元素，则递归调用本过程查找后续每个元素，直到遇到link域为NULL。设f(p,x)为查找的函数，当查找成功时返回true，否则返回false，则有以下递归
10、模型：f(p,x)=true 若p-tag=0 且p-data =xf(p,x)=f(p-link,x) 若p-tag=0 且p-data! =xf(p,x)=f(p-slink,x)or f(p-link,x)若p-tag=1 4.求广义表表头head(Glist GL)。一个广义表的表头是指该广义表的第一个元素。求表头的实现过程如下：Glist head(Glist GL)if（表不为空并且不只是原子）返回GL中指向子表的指针；5.求广义表表尾tail(Glist GL)。一个广义表的表尾指的是除去该广义表的第一个元素后的所有剩余部分，因此，实现上述算法的过程描述如下：Glist tail
11、(Glist GL)if（表不为空表并且有表尾） 保存指向表尾的指针，删除广义表的第一个元素；6.求广义表的深度depth(Glist GL ,int &maxdh)。假设广义表是一个无共享子表的非递归表，求其表深度的算法思想是：扫描广义表的第一层的每个结点，对每个结点递归调用计算出其子表的深度，取最大的子表的深度，然后加1即为广义表的最大深度，其递归模型如下：maxdn(GL) =0 GL为单个元素，即GL-tag =0maxdh(GL) =1 GL为空表，即GL-tag =1且GL-slink =NULLmaxdh(GL) =max(maxdh(GL1), maxdh(GL2). maxd
12、h(GLn)+1其中，实现该功能的算法描述如下：depth(Glist GL,int &maxdh)if（广义表不是单个元素并且不为空表）循环扫描广义表的第一层的每个结点；递归对每个结点求其子表的深度；找出最大的子表的深度；直到GL=NULL为至；子表最大深度加1；五、十字链表运算1.题目要求：当稀疏矩阵中非0元素的个数和位置经常发生变化的时候，采用三元组顺序表的结构不太合理，但如果采用链表的结构就可以避免这种情况的出现。本题目要求对稀疏矩阵进行十字链表结构的运算，采用十字链表结构对稀疏矩阵实现十字链表的建立、相加和输出操作，要求以三元组形式输入。2.算法分析：十字链表的结点分两类：一类是表结
13、点，由5个域组成，其中i和j代表结点所在的行和列所在的域，right和down所在的域用来指向十字链表中该结点在行和列上的下一个结点的指针，v用于存放元素的值；另一类是表头结点，也由5个域组成，其中行、列的值均为0，无实际意义，right和down用于在行方向和列方向上指向表结点，next指针域用于指向下一个表头结点。结点结构为：#defineMAXSIZE1000/*定义非0元素的最大值*/ typedefintelemtype; typedefstructnode inti,j; structnode*down,*right; union structnode*next;/*结点使用next域*/ elemtypev;/*结点使用v值域*/ val; crosslink; 十字链表的每一行和每一列链表都构成一个循环链表，可以将行和列链表共享一个表头结点，即第i行和第i列共用同一个表头结点，第j行和第j列共用同一个表头结点。【精品文档】第 5 页