稀疏矩阵
实现稀疏矩阵压缩存储，并实现矩阵转置和求和。 输入矩阵时，首先需要输入非零元素的个数，然后分别输入矩阵的 行号，列号和值。 输完2个矩阵后，自动进行计算第一个矩阵的转置以及两个矩阵的和。 例如：输入如下： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148#include <iostream>using namespace std;struct Tripl...
稀疏矩阵的压缩存储
存储方式设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数（即s≤m×n），则称 A 为稀疏矩阵。e=s/(m*n),为矩阵的稀疏因子。有人认为 e≤0.05 时称之为稀疏矩阵。 每一个三元组 (i, j, aij) 唯一确定了矩阵A的一个非零元素。因此，稀疏矩阵可由表示非零元的一系列三元组及其行列数唯一确定。 三元组结构体 12345678910111213#include <iostream>using namespace std;struct Triple{ //三元组 int row, col; //非零元素行号/列号 int value; //非零元素的值 void operator=(Triple &R) //赋值 { row = R.row; col = R.col; value = R.value; }...
特殊矩阵的压缩矩阵
特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。 特殊矩阵的分类： 对称矩阵（aij=aji） 储存上三角矩阵 储存下三角矩阵 三对角矩阵 下三角矩阵 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组B共有n + ( n - 1 ) +…… + 1 =n*(n+1)／2 个元素 若i>=j，数组元素A[i][j]在数组B中的存放位置为1 + 2 +……+ i + j = (i + 1)* i / 2 + j 上三角矩阵 数组B共有n + ( n - 1 ) +…… + 1 =n*(n+1)／2 个元素 若i <=j，数组元素A[i][j]在数组B中的存放位置为 n + (n-1) + (n-2) +……+ (n-i+1) + j-i 三对角矩阵 特点： 三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2（n>2）个非...
栈的应用——中缀表达式求值
原理：使用两个栈操作符栈OPTR (operator)，操作数栈OPND(operand)，为了实现这种计算，需要考虑各操作符的优先级 代码思路： 建立并初始化OPTR栈和OPND栈，然后在OPTR栈中压入一个“#” 扫描中缀表达式，取一字符送入ch。 当ch != ‘#’ 或OPTR栈的栈顶 != ‘#’时, 执行以下工作, 否则结束算法。在OPND栈的栈顶得到运算结果。 循环过程： 若ch是操作数，进OPND栈，读下一字符到ch； 若ch是操作符，比较icp(ch)的优先级和isp(OPTR)的优先级： 若icp(ch) > isp(OPTR)，则ch进OPTR栈，读下一字符到ch； 若icp(ch) < isp(OPTR)，则从OPND栈退出a2和a1，从OPTR栈退出θ, 形成运算指令 (a1)θ(a2)，结果进OPND栈,不读入下一字符而是继续比较栈顶元素； 若icp(ch) == isp(OPTR) 且ch == ‘)’，则从OPTR栈退出’(‘，对消括号，然后从中缀表达式取下一字符送入ch； 代码实现：...
栈的应用——表达式转换
中缀->后缀先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。 中缀->前缀先对中缀表达式按运算优先次序通统加上括号，再把操作符前移到左括号前并以就近移动为原则，最后将所有括号消去。 代码实现中缀转为后缀原理： isp叫做栈内(in stack priority)优先数 icp叫做栈外(in coming priority)优先数。 icp>isp则入栈；icp<isp则出栈、输出；icp=isp只出栈 (的栈外优先级最高，一来即入栈；入栈后优先级极低，这样其他操作符可以入栈。 其他操作符进入栈后优先级升1，这样可以保证相同优先级的从左到右计算。 优先级相同:( ) # # 算法： 操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。 重复执行以下步骤，直到ch = ‘#’，同时栈顶的操作符也是‘#’，停止循环。 循环过程： 若ch是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp： ...
栈的应用——表达式求值
表达式的三种表示方法设 Exp = S1 OP S2 OP S1 S2 为前缀表示法 S1 OP S2 为中缀表示法 S1 S2 OP 为后缀表示法 前缀式的运算规则为: 连续出现的两个操作数和在它们之前且紧靠它们的一个运算符构成一个最小表达式; 后缀式的运算规则为: 连续出现的两个操作数和在它们之后且紧靠它们的一个运算符构成一个最小表达式; 利用栈从后缀式求值原理：遇到运算数则入栈，遇到操作符则出栈2个数，计算，结果入栈 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118...
栈的应用——进制转换
算法基于原理：N = (N div d)×d + N mod d 代码思路： 初始化栈 输入要转化的数据N 当N不为0，把N%8取余的结果入栈 当栈不为空，输出 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <iostream>using namespace std;class steak;class StackNode{ friend class LinkedStack;public: StackNode* link; int data;public: StackNode(StackNode* ptr = NULL) { link = ptr; } StackNo...
括号匹配（栈）
用栈实现：输入一行符号,以#结束，判断其中的括号是否匹配。括号包括： {} [] () <> 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144#include <iostream>using namespace std;class steak;class StackNode{ friend class LinkedStack;public: ...
一元多项式的基本运算
实验二：一元多项式的基本运算 实验目的：掌握用线性表实现一元多项式的基本运算。 实验内容：使用链式存储实现一元多项式的加法、减法、乘法和求导。即： C(x)= A(x)+B(x)；C(x)= A(x)-B(x) C(x)= A(x)*B(x) C(x)= A’(x) 菜单： 1)C ：分别创建两个多项式A(x)和B(x)，其中 输入时按照 指数的升序顺序输入，遇到系数为0则停止。例如：输入 ： 1 2 3 4 5 6 7 8 2 3 4 5 6 7 0 则生成的多项式分别为： A(x)=x^2+3x^4+5x^6+7x^8 B(x)=2x^3+4x^5+6x^7 2)P:计算C(x)= A(x)+B(x)，计算完毕后输出C(x)的 结果 3)S: 计算C(x)= A(x)-B(x)，计算完毕后输出C(x)的 结果 4)M: 计算C(x)= A(x)*B(x)，计算完毕后输出C(x)的 结果 5)D: 计算C(x)= A’(x)，计算完毕后输出C(x)的 结果 6)V: 首先输入一...
链表
实习目的：熟练掌握链表的建立及基本操作 问题描述： 1）实现链表的排序(升序) 提交前请将所有的提示信息去掉，只保留最后的输出结果。例如运行时：从键盘直接输入： 2 1 23 1 2 3 输出结果为： 123 分别表示第一个链表元素个数为2，元素分别为 1,2 ；第二个链表元素个数为3，元素分别为1,2,3。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135#include <iostream>using namespace s...