2014表达式求值.docVIP

表达式求值问题 目 录 1、数据结构课程设计任务书 １ 1.1、题目 １ 1.2、要求 １ 2、总体设计 １ 2.1、功能模块设计 １ 2.2、所有功能模块的流程图 １ 3、详细设计 １ 3.1、程序中所采用的数据结构及存储结构的说明 １ 3.2、算法的设计思想 ２ 3.3、稀疏矩阵各种运算的性质变换 ２ 4、调试与测试： ２ 4.1、调试方法与步骤： ２ 4.2、测试结果的分析与讨论： ３ 4.3、测试过程中遇到的主要问题及采取的解决措施： ３ 5、时间复杂度的分析： ４ 6、源程序清单和执行结果 ４ 7、C程序设计总结 ８ 8、致谢 ８ 9、参考文献 ８ 1、数据结构课程设计任务书 1.1、题目 1.2、要求 （1）、； （2）； （3）； （4）、、2、总体设计 2.1、功能模块设计 根据课程设计题目的功能要求，各个功能模块的组成框图如下： 2.2、所有功能模块的流程图 3、详细设计 模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等； 3.1、程序中所采用的数据结构及存储结构的说明 以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。 //-----------稀疏矩阵的三元组顺序存储表示------------- #define MAXSIZE 100 /*假设非零元个数的最大值为20*/ typedef struct { int i,j; /*该非零元的行下标和列下标*/ int v; }Triple; typedef struct { Triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/ int mu,nu,tu; /*矩阵的行数,列数和非零元个数*/ }TSMastrix; 在此，data域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。 3.2、算法的设计思想 a) 相加运算 对于两个稀疏矩阵相加，即行与行，列与列相加 b）相乘运算 若设Q=M*N 其中M是m1*n1矩阵，N是m2*n2矩阵，只有当n1=m2时才可以相乘。 乘积矩阵Q中元素 Q（i，j）=∑M（i，k）*N（k，j） 1≤i≤m1，1≤j≤n2 在算法中，不论M（i，k）和 N（k，j）的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，只需在M.data和N.data中找到相应的各对元素(即M.data中的j值和 N.data中的i值相等的各对元素)相乘即可。 ?c) 转置运算 对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i）， 1≤i≤n，1≤j≤m。完成一个稀疏矩阵的转置分为三步： （1）将矩阵的行列值相互交换； （2）将每个三元组中的i和j相互调换； （3）重排三元组之间的次序便可实现矩阵的转置； 3.3、稀疏矩阵各种运算的性质变换 a)加法运算 两个稀疏矩阵的加和矩阵仍然是稀疏矩阵 b）乘法运算 两个稀疏矩阵的乘积矩阵不是稀疏矩阵 c）转置运算 一个稀疏矩阵的转置矩阵仍然是稀疏矩阵 4、调试与测试： 4.1、调试方法与步骤： 4.2、测试结果的分析与讨论： （测试要写出测试用例及每个用例结果的的截图） 4.3、测试过程中遇到的主要问题及采取的解决措施： （略） 5、时间复杂度的分析： a)加法运算 由于两矩阵行列相等，故时间复杂度为O（行*列） b）乘法运算 设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2） c）转置运算 时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即O（mu*nu） 6、源程序清单和执行结果 Typedef char DataType; Typedef struct { char data[100]; int front,rear; }Sequeue; //定义队列类型 void InitQueue(SeqQueue * Q) //初始化队列 { Q-front=0; Q-rear=0; } int QueueEmpty(SeqQueue Q) //判空队列 { return Q.rear= =Q.front; } void EnQueue(SeqQueue * Q,DataType x ) //入队列 { If((Q-rear +1) % QueueSize = =Q