数据结构 矩阵操作

运行时的显示界面，可选择相应操作#include/多用链表结点templatestruct DblNodeET data;/结点数据域，存储该结点的数据部分DblNode* next;/结点指针域，指示下一个节点的位置DblNode* back;/指向结点的前驱DblNode() next = NULL; back = NULL; /无参数结点构造函数，用于未给定参数时结点的初始化;/=/ 链表类 部分/=templateclass LinkListprotected:ET dataTmp;/用于临时存取数据，供成员函数使用int count, cTmp;/count用于计数表元素个数,即表长； cTmp用于临时计数用DblNode *head, *tail, *pTmp;/*head记录表头的位置； *tail记录表尾的位置； *pTmp记录每次操作结点的指针位置public:LinkList() count=cTmp=0; head = tail = pTmp = NULL;/链表构造函数LinkList() Clear();/链表析构函数/链表相关操作int Length() return count;/用于获取当前标的长度void Clear() while(count) DelHead(); /表清空void Show();/输出表中现有的所有元素void ReShow();/逆序输出表中现有的所有元素DblNode* GetPosP(int postion);/获取指向第postion个位置结点的指针void HeadInsert(ET &e);/从表头插入元素void TailInsert(ET &e);/从表尾插入元素void Insert(int position, ET &e);/向表中第postion个位置插入新的结点元素，元素总数加一void ReTailInsert(int position, ET &e);/重置表中第cTmp个位置元素的数据部分为e，元素总数不变void GetElem(int position, ET &e);/从表中获取第cTmp元素，写入e中，由e输出void DelHead();/删除表头void DelTail();/删除表尾void DelElem(int position);/删除表中第cTmp个位置的元素.元素减一void operator = (LinkList& cop);/赋值符重载函数，实现链表的复制功能void SUB(LinkList &A, LinkList &B);/实现链表相减，将仅存在于A中的元素写入当前链表void ADD(LinkList &A, LinkList &B);/实现链表相加，将表A 表B中的元素依次写入当前链表void Seprate();/奇偶分离函数，使得所有奇数均排列在偶数前void Sort();/对链表中的元素进行排序void KillDouble();/对链表中的元素进行排序去重void CinHelp();/提示输入函数，用于实现键盘输入交互式操作;templatevoid LinkList:Show()cTmp = count;pTmp = head;/指向头指针的第一个后继coutendl当前链表中共有count个元素,endl0 & count0)/当表中有元素时dataTmp = pTmp-data;coutdataTmpnext;/每输出一位向后移动一位coutendl;templatevoid LinkList:ReShow()cTmp = count;pTmp = tail;/指向头指针的第一个后继coutendl当前链表中共有count个元素,endl0 & count0)/当表中有元素时dataTmp = pTmp-data;coutdataTmpback;/每输出一位向后移动一位coutendl;templateDblNode* LinkList:GetPosP(int postion)cTmp = postion;if(cTmp1)coutendl操作无效! 请确保输入元素位置大于0count) cTmp = cTmp % count; if(cTmp = 0) cTmp = count; /当输入位置大于元素总数时取余数得对应位置if(cTmp 1) pTmp = pTmp-next; cTmp-;else/后count/2用back指针访问cTmp = count - cTmp + 1;pTmp = tail;/不断指向下一个结点，头指针所在位置为零while(cTmp1) pTmp = pTmp-back; cTmp-;return pTmp;templatevoid LinkList:ReTailInsert(int position, ET &e)cTmp = position;if(count = 0)coutendl表当前为空，无元素可修改data = e;/重置表中元素，元素总数不变templatevoid LinkList:HeadInsert(ET &e)if(count = 0)/向表中插入第一个结点元素 head = new DblNode; tail = pTmp = head; head-data = e;count+; else head-back = new DblNode; head-back-next = head; head = head-back; head-data = e;count+;templatevoid LinkList:TailInsert(ET &e)if(count = 0)/向表中插入第一个结点元素 tail = new DblNode; head = pTmp = tail; tail-data = e;count+; else tail-next = new DblNode;pTmp = tail-next;pTmp-back = tail;tail = pTmp; tail-data = e;count+;templatevoid LinkList:Insert(int position, ET &e)/在第pos个位置插入一个新结点int pos = position;/因为此成员函数调用了获取指针位置函数GetPosP()，而该函数使用了cTmp计数区间，故需使用其他空间计数if(pos1)coutendl操作无效! 请确保输入元素位置大于0count)/当输入位置大于元素总数时if(pos % count = 1) pos = count+1;/输入位置大于元素总数且取余后为1，将pos置为插入尾部else if(pos % count = 0) pos = count; else pos = pos % count;if(pos = 1) HeadInsert(e);else if(pos = count+1) TailInsert(e);else pTmp = GetPosP(pos-1);/获取指向第pos-1个结点的指针DblNode* posNext = pTmp-next;/获取指向第pos个结点的指针pTmp-next = new DblNode;/在pos-1后生成新结点pTmp-next-back = pTmp;/新结点前驱为第pos-1个结点pTmp-next-next = posNext;/新结点后继为原pos个结点pTmp-next-data = e;posNext-back = pTmp-next;/原pos个位置的结点前驱指向新结点count+;templatevoid LinkList:GetElem(int position, ET &e)cTmp = position;if(cTmp1)coutendl操作无效! 请确保输入元素位置大于0data;/获取指向第cTmp个结点的数据部分templatevoid LinkList:DelHead()if(count = 0)coutendl操作无效！当前表已为空next;delete head;head = pTmp;count-;templatevoid LinkList:DelTail()if(count = 0)coutendl操作无效！当前表已为空back;delete tail;tail = pTmp;count-;templatevoid LinkList:DelElem(int positon)/删除在第cTmp个位置的结点cTmp = positon;if(cTmpcount) cTmp = cTmp % count;if(count = 0)coutendl表当前为空，无元素可修改endl;else if(count = 1 | cTmp = 1)DelHead();else if(cTmp = count) DelTail();elsepTmp = GetPosP(cTmp-1);/获取指向第cTmp-1个结点的指针DblNode* pNext = pTmp-next;/获取指向第cTmp个结点的指针pTmp-next = pNext-next;/将第cTmp-1个结点的后继指向第cTmp个结点的后继pNext-next-back = pTmp;/将第cTmp+1个结点的前驱指向第cTmp-1个结点delete pNext;/将第cTmp个结点删除count-;/表元素元素总数减一templatevoid LinkList:operator = (LinkList& cop)/赋值符“ = ”重载Clear();/对当前链表先清空if(cop.count0)cTmp = cop.count;cop.pTmp = cop.head;/复制cop的头指针注意：cop.pTmp 不可换做 pTmp ？否则运行报错while(cTmp0)/当表中还有元素时dataTmp = cop.pTmp-data;/取出后继结点中的数据TailInsert(dataTmp);/生成新结点cTmp -;/计数元素总数减一cop.pTmp = cop.pTmp-next;/向后继结点移动一位templatevoid LinkList:SUB(LinkList &A, LinkList &B)Clear();/对当前链表先清空int countA=1, countB;ET elemA, elemB;DblNode* posA = A.head, * posB;while(countAdata;/依次获取A表中元素的数据部分posA = posA-next;countA+;while(countBdata;posB = posB-next;if(elemA=elemB) break;/将A中的每一个元素分别与B中的每一个元素进行比较，若相同则中断本次循环countB+;if(countBB.count) TailInsert(elemA);/若与B中所有元素均不相同时将该元素写入当前表中templatevoid LinkList:ADD(LinkList &A, LinkList &B)Clear();/对当前链表先清空int countA=1, countB=1;DblNode* posA = A.head, * posB= B.head;while(countAdata);/依次获取A表中元素的数据部分,写入当前链表posA = posA-next;countA+;while(countBdata);/依次获取B表中元素的数据部分posB = posB-next;countB+;templatevoid LinkList:Seprate()/奇偶分离函数，使得所有奇数均排列在偶数前int i=0, jb=0, jc=0;int *B = new intcount, *C = new intcount;/将链表中的元素按奇数、偶数分别存放到数组B、C中DblNode* pos = head;ET tmp;while(i data;pos = pos-next;if(tmp%2 = 1) Bjb = tmp; jb+;/jb用于计数奇数的个数else Cjc = tmp; jc+;/jc用于计数偶数的个数i+;i = 0;pos = head;while(i data = Bi; pos = pos-next;i+;i = 0;while(i data = Ci;pos = pos-next; i+;templatevoid LinkList:Sort()/对链表中的元素进行排序int i=1, j;DblNode* posi = head, * posj;/初始时让posi指向第一个元素ET tmp;while(i next;/初始时让posj指向第二个元素while(j data posj-data)/若前面的元素大于后面的元素，则交换两元素的数据部分tmp=posi-data; posi-data=posj-data; posj-data=tmp;posj = posj-next;j+;posi = posi-next;i+;templatevoid LinkList:KillDouble()Sort();/对链表中的元素进行排序int i=1;DblNode* pos = head;/初始时让pos指向第一个元素while(i data = pos-next-data) DelElem(i); /若第i个位置的元素和i+1个位置的元素数据部分相同时删除第i个元素else i+; pos=pos-next; /否则指针指向下一个元素templatevoid LinkList:CinHelp()int choice=1, tmp;while(choice)coutendl请选择链表相关操作:endlendl1.添加新的元素 2.插入数据元素 3.删除表元素 4.修改元素 5.逆序输出表元素 endlendl6.链表清空 7.数据链表奇前偶后分离 8.数据链表元素排序 9.数据链表元素排序去重endlendlchoice;switch(choice)case 1:coutendltmp;choice = count;/链表中原有的元素数不应在计数范围内coutendl请依次输入tmp个数据元素 空格间隔 Enter确认: endl;while(countdataTmp; TailInsert(dataTmp);Show();break;case 2:/插入表元素coutendldataTmptmp; if(tmp1)coutendl操作无效! 请确保输入元素位置大于0endl;elseInsert(tmp, dataTmp);Show();break;case 3:/删除表元素coutendltmp;if(count = 0)coutendl操作无效! 当前表为空count)/当输入位置大于元素总数时取余数得对应位置 tmp = tmp % count; if(tmp = 0) tmp = count; if(tmp1)coutendl操作无效! 请确保输入元素位置大于00)GetElem(tmp, dataTmp);/获取该位置的数据存入dataTmpDelElem(tmp);coutendl第tmp个位置的元素dataTmp已成功删除endl;Show();break;case 4:/修改元素coutendldataTmptmp; if(tmp1)coutendl操作无效! 请确保输入元素位置大于00)ReTailInsert(tmp, dataTmp);Show();break;case 5:coutendl链表顺序输出为：endl;Show();coutendl链表逆序输出为：endl;ReShow();break;case 6:/清空Clear();Show();break;case 7:/链表奇数和偶数分离coutendl链表奇数和偶数分离前;Show();Seprate();coutendl链表奇数和偶数分离后;Show();break;case 8:/数据链表元素排序coutendl链表元素排序前;Show();Sort();coutendl链表元素排序后;Show();break;case 9:/数据链表元素排序去重coutendl链表元素排序去重前;Show();KillDouble();coutendl链表元素排序去重后;Show();break;coutendlchoice;coutendlendlendl;/链表操作到此处结束/-/=/ 矩阵类 部分/=templateclass Matrix/数据结构pag 151protected:int rows, cols;/矩阵的行数和列数public:ET * elems;/指向存储矩阵元素的数组Matrix()rows=0, cols=0; elems=NULL;/没有给定矩阵的相关参数时线创建一个空的矩阵对象Matrix(int r, int c);/给定行和列 矩阵构造函数Matrix(Matrix & m);/给定一个矩阵 矩阵构造函数Matrix()if(elems!=NULL)delete elems; /矩阵析构函数int Rows() return rows;/获取矩阵的行数int Cols() return cols;/获取矩阵的列数ET & operator()(int i, int j);/重载运算符()用于对矩阵中的元素进行操作void operator=(Matrix m);/矩阵赋值重载函数Matrix operator+(Matrix m);/定义两个矩阵相加重载运算符+Matrix operator-(Matrix m);/定义两个矩阵相加重载运算符-Matrix operator*(Matrix m);/定义两个矩阵相加重载运算符*void show();/输出显示矩阵的内容void InputHelp();/矩阵输入辅助函数void Transpose();/实现矩阵的转置 转换矩阵为转置矩阵;templateMatrix:Matrix(int r, int c)/给定矩阵的行数和列数构造一个新的矩阵 if(r=1 & c=1) rows = r; cols = c; elems = new ETrows*cols;templateMatrix:Matrix(Matrix & m)/利用已有的矩阵初始化构造一个新的矩阵rows = m.Rows(); cols = m.Cols(); elems = new ETrows*cols;for(int i=0; i rows*cols; i+)elemsi = m.elemsi;templateET& Matrix:operator()(int i, int j)/返回对应元素的地址便可对指定元素直接进行操作if(i=1 & j=1)return elems(i-1)*cols + j-1;templatevoid Matrix:operator=(Matrix m)if(elems!=NULL)delete elems; rows=0; cols=0; /清空矩阵原有的元素if(m.Rows() =1 & m.Rows() =1)/对矩阵重新初始化大小 rows = m.Rows(); cols = m.Cols(); elems = new ETrows*cols;for(int i=0; i rows*cols; i+)/将新的元素逐个复制到矩阵中elemsi = m.elemsi;templateMatrix Matrix:operator+(Matrix m)if(m.Rows()=Rows() & m.Cols()=Cols()Matrix tmp(Rows(), Cols();for(int i=0; i Rows()*Cols(); i+)tmp.elemsi = m.elemsi + elemsi;return tmp;else Matrix tmp;return tmp;templateMatrix Matrix:operator-(Matrix m)if(m.Rows()=Rows() & m.Cols()=Cols()Matrix tmp(Rows(), Cols();for(int i=0; i Rows()*Cols(); i+)tmp.elemsi = elemsi - m.elemsi;return tmp;else Matrix tmp;return tmp;templateMatrix Matrix:operator*(Matrix m)if(Cols()=m.Rows()/两个矩阵能进行乘法的条件是 第一个矩阵的列数等于第二个矩阵的行数Matrix tmp(Rows(), m.Cols();/乘积矩阵的项数为 第一个矩阵的行数乘以第二个矩阵的列数for(int i=1; i = Rows(); i+)/行循环for(int j=1; j = m.Cols(); j+)/列循环tmp(i, j)=0;/初始化各乘积项for(int k=1; k = Cols(); k+)/乘积项生成循环tmp(i, j) += elems(i-1)*cols + k-1 * m(k, j);/将第一个矩阵的第(i, k)元素与第二个矩阵的第(k, j)元素相乘 累加到tmp的(i, j)项中return tmp;else Matrix tmp;return tmp;/空格填充函数 用于实现输出的规格化输出对齐，以最大位数n的位数为基准，位数不足时补充空格void SpaceFill(int m, int n)int a=m, b=n, ia=0, ib=0, i=0;while(a=10) a=a/10; ia+;while(b=10) b=b/10; ib+;if(ibia) ia=ib-ia;/计算数字m和n的位数之差，以此决定需要输出的空格数else ia=ia-ib;for(; iia; i+) cout ;templatevoid Matrix:show()int i, j, maxTmp=0;for(i=0; i maxTmp ) maxTmp = elemsi;for(i=1; i=rows; i+)for(j=1; j=cols; j+)cout elems(i-1)*cols + j-1 ;SpaceFill(elems(i-1)*cols + j-1, maxTmp);/为元素elems填充以maxTmp为位数基准的空格coutendl;templatevoid Matrix:InputHelp()/矩阵输入辅助函数if(elems!=NULL)delete elems;/当矩阵中元素非空时先对其清空coutrows;coutcols;if(rows=1 & cols=1)elems = new ETrows*cols;coutn请依次输入rowsxcols矩阵的 rows*cols个元素： （空格间隔）n;for(int i=0; ielemsi;coutn输入的矩阵为：n;show();else rows=0; cols=0;coutn矩阵的行列数应不小于1n;templatevoid Matrix:Transpose()if(elems!=NULL)/当矩阵中有元素时进行如下操作int i, j;ET * elemsTmp = elems;/用新的元素数组指针指向矩阵的数组元素elems = new ETrows*cols;/为矩阵生成新的存储数组for(i=1; i=rows; i+)for(j=1; j=cols; j+)elems(j-1)*rows + i-1 = elemsTmp(i-1)*cols + j-1;/将矩阵的第(i, j)位置的元素值存储到 新的数组空间的第(j, i)位置delete elemsTmp;/释放矩阵中原来的元素rows = rows + cols;/对行数和列数的值进行交换cols = rows - cols;rows = rows - cols;/=/ 三元组稀疏矩阵类 部分/=templatestruct Triple/定义 新类型Triple 引用形式同int、char 如：int m ; 对Triple型有：Triple m ;int row, col;/Triple型 包含行、列、ET value;/和矩阵的元素值Triple()row=0; col=0;Triple(int r, int c, ET v)row = r; col = c; value = v;/在已知元素值和元素所在行和列时，生成一个Triple型元素/引用形式为：Triple e(1, 2, 33) 定义一个Triple型元素e，行1 列2 元素值为33void operator=(Triple e)row = e.row; col = e.col; value = e.value;/重载运算符 = 实现Triple型元素的相互赋值/引用形式为：e1 = e2 e1、e2均为Triple型bool operator(Triple e)if(row e.row) return true; else if(row = e.row)if(col e.col) return true;else return false;else return false;bool operator=(Triple e)if(row = e.row & col = e.col) return true;else return false;templateclass TriSpaMatrix/Triple Sparse Matrix 三元组(行列值) 稀疏 矩阵protected:int rows, cols;/定义rows和cols 分别用于记录矩阵的行数和列数public:LinkList Triple list;/定义一个数据部分为Triple型的链表list 以链表存储所有三元组记录TriSpaMatrix()rows=0; cols=0;/无参数时，构造三元组稀疏矩阵，行数列数分别设定为0TriSpaMatrix(int r, int c)rows=r; cols=c;/给定行和列时 设定行列分别为对应值TriSpaMatrix()list.Clear();/析构函数 矩阵析构时 调用链表LinkList中声明的Clear()函数数对链表进行清空int Rows() return rows;/获取矩阵的行数int Cols() return cols;/获取矩阵的列数int GetNum() return list.Length();/获取矩阵中非零的元素个数 返回值为链表中存储的Triple型元素个数void SetElem(int r, int c, ET e);/设定矩阵中指定位置的元素值void GetElem(int r, int c, ET &e);/获取矩阵中指定位置的元素值存储到eMatrix cMatrix();/将稀疏矩阵转换为普通矩阵void inputHelp();/输入辅助函数void operator=(TriSpaMatrix m)rows=m.rows; cols=m.cols; list=m.list;/矩阵赋值重载函数;templatevoid TriSpaMatrix:SetElem(int r, int c, ET e)if(r=rows & c=cols & list.Length()rows*cols)/当设置的元素在矩阵表示的范围之内 且矩阵未满时进行元素如表操作Triple tmp(r, c, e);/生成一个三元组表项list.TailInsert(tmp);/将表项存入线性表中list.KillDouble();/删除链表中元素进行排序去重复位置templatevoid TriSpaMatrix:GetElem(int r, int c, ET &e)if(r=rows & c=cols)/当要取出的元素位置在矩阵中时Triple tmp(r, c, e), tmp1;/生成一个行列已知的三元组表项 和一个无参表项int i=1;while(i = list.Length() list.GetElem(i, tmp1);/将表中的每一个元素逐个获取到tmp1中if(tmp = tmp1) e=tmp1.value; break;/比较行列是否为r,c 是则将元素值存到e中i+;if(i=list.Length()+1) e=(ET)0;templateMatrix TriSpaMatrix:cM