特殊矩阵的压缩存储算法的实现

软件综合课程设计 特殊矩阵的压缩存储算法的实现二叉排序树的实现 二一四 年 六 月一、特殊矩阵的压缩存储算法的实现1.问题陈述对于特殊矩阵可以通过压缩存储减少存储空间。基本要求： 1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值； 2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值；2.程序代码#include#include #includestatic shangsanjiao(int n)int i,j,k,z,g;int L100100,SA100;cout请输入您要压缩矩阵的行列数n;cout请输入您的矩阵内元素：endl;for(i=1;in+1;i+)for(j=1;jLij;if(i=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;SAk=Lij;cout您输入的矩阵为：endl;for(i=1;in+1;i+)for(j=1;jn+1;j+)coutLij ;coutendl;cout压缩存储后：endl;for(k=0;kn*(n+1)/2+1;k+)coutk SAk;cout若要读取矩阵的值请输入100退出输入000。z;for(g=0;g1000;g+)while(z=100)cout请您输入未压缩时所在行数:i;cout请您输入未压缩时所在列数:j;if(i=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;cout该地址的值为：endl;coutSAk;z=1;cout继续请输入100退出输入000。z;break;static duichen(int n)int i,j,k,z,g;int L100100,SA100;cout请输入您要压缩矩阵的行列数n;cout请输入您的矩阵内元素：endl;for(i=1;in+1;i+)for(j=1;jLij;if(i=j)k=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;SAk=Lij;cout您输入的矩阵为：endl;for(i=1;in+1;i+)for(j=1;jn+1;j+)coutLij ;coutendl;cout压缩存储后：endl;for(k=0;kn*(n+1)/2;k+)coutk SAk;cout若要读取矩阵的值请输入100退出输入000。z;for(g=0;g1000;g+)while(z=100)cout请您输入未压缩时所在行数:i;cout请您输入未压缩时所在列数:j;if(i=j)k=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;cout该地址的值为：endl;coutSAkendl;z=1;cout继续请输入100退出输入000。z;break;static xiasanjiao(int n)int i,j,k,z,g;int L100100,SA100;cout请输入您要压缩矩阵的 行列数n;cout请输入您的矩阵内元素： endl;for(i=1;in+1;i+)for(j=1;jLij;if(i=j)k=i*(i-1)/2+j-1;elsek=n*(n+1)/2;SAk=Lij;cout您输入的矩阵为：endl;for(i=1;in+1;i+)for(j=1;jn+1;j+)coutLij ;coutendl;cout压缩存储后：endl;for(k=0;kn*(n+1)/2+1;k+)coutk SAk;cout若要读取矩阵的值请输入100退出输入000。z;for(g=0;g1000;g+)while(z=100)cout请您输入未压缩时所在行数:i;cout请您输入未压缩时所在列数:j;if(i=j)k=i*(i-1)/2+j-1;elsek=n*(n+1)/2;cout该地址的值为：endl;coutSAkendl;z=1;cout继续请输入100退出输入000。z;break;int main()int n,d;int m;for(d=0;d100;d+)cout请选择您要存储的特殊矩阵类型：endl;cout1:对称矩阵endl;cout2:上三角矩阵endl;cout3:下三角矩阵endl;cout退出请输入0m;if(m=1)duichen(n);else if(m=2)shangsanjiao(n);else if(m=3)xiasanjiao(n);else if(m=0)break;elsecout对不起您输入的选号错误endl;3.运行结果1.1运行主窗口1.2对称矩阵1.3上三角矩阵1.4下三角矩阵二、二叉排序树的实现1.问题陈述用顺序和二叉链表作存储结构 (1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；2.需求分析（1）输入一列数L，以回车(n)为输入结束标志,并将输入的数列生成一棵二叉树T。（2）调用函数，把生成的二叉树进行中序遍历，并输出最后的结果。（3）输入一个数，在已有的二叉树排序树中查找，若没有找到，则输出没有这个数，如果有，则输出存在这个数。（4）如果有这个数，则调用删除函数，删除这个数生成一棵新的二叉树，并以中序遍历输出新的结果。3.概要设计 要生成一个二叉树T，元素类型是ElemType，初始化模块：CreateBST()创建一棵二叉排序树： int BSTInsert查找元素x：BSTSearch()中序遍历二叉排序树：inorder()4.详细设计（1）主程序模块#include typedef int KeyType;typedef char ElemType10;typedef struct tnode KeyType key; ElemType data; struct tnode *lchild,*rchild;BSTNode;定义全局变量、分配储存空间（2）二叉树初始化BSTNode *CreatBST(KeyType A,int n)/由数组中的关键字建立一棵二叉排序树BSTNode *bt=NULL; /初始时bt为空树int i=0;while(ikey=k)return(0);f=p;/*f指向*p结点的双亲结点*/if (p-keyk)p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/p=new BSTNode;/*建立新结点*/p-key=k;p-lchild=p-rchild=NULL;if (bt=NULL)/*原树为空时,*p作为根结点插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作为*f的左孩子*/elsef-rchild=p;/*插入*p作为*f的右孩子*/return(1);void CreateBST(BSTNode *&bt,KeyType str,int n)bt=NULL; /*初始时bt为空树*/int i=0;while (ilchild);coutkeyrchild);（5）查找元素模块BSTNode *BSTSearch(BSTNode *bt,KeyType k)BSTNode *p=bt;while (p!=NULL & p-key!=k)if (kkey) p=p-lchild; /*沿左子树查找*/else p=p-rchild; /*沿右子树查找*/return(p);（6）删除元素模块int BSTDelete(BSTNode *&bt,KeyType k)BSTNode *p=bt,*f,*r,*f1;f=NULL;/*p指向待比较的结点,f指向*p的双亲结点*/while (p!=NULL & p-key!=k) /*查找值域为x的结点*/f=p;if (p-keyk) p=p-lchild; /*在左子树中查找*/elsep=p-rchild; /*在右子树中查找*/if (p=NULL) /*未找到key域为k的结点*/return(0);else if (p-lchild=NULL) /*p为被删结点,若它无左子树*/if (f=NULL) /*p是根结点,则用右孩子替换它*/bt=p-rchild;else if (f-lchild=p) /*p是双亲结点的左孩子,则用其右子替换它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它*/f-rchild=p-rchild;delete p;else if (p-rchild=NULL)/*p为被删结点,若它无右子树*/if (f=NULL) /*p是根结点,则用左孩子替换它*/bt=p-lchild;if (f-lchild=p) /*p是双亲结点的左孩子,则用其左孩子替换它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其左孩子替换它*/f-rchild=p-lchild;delete p;else /*p为被删结点,若它有左子树和右子树*/f1=p;r=p-lchild; /*查找*p的左子树中的最右下结点*r*/while (r-rchild!=NULL)/*r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=r-rchild;if (f1-lchild=r)/*r是*f1的左孩子,删除*r*/f1-lchild=r-rchild;else if (f1-rchild=r)/*r是*f1的右孩子,删除*r*/f1-rchild=r-lchild;r-lchild=p-lchild;/*以下语句是用*r替代*p*/r-rchild=p-rchild; if (f=NULL)/*f为根结点*/bt=r;/*被删结点是根结点*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩子*/f-rchild=r;delete p;return(1);（7）主函数模块设计void main()int n;BSTNode *bt=NULL,*p;KeyType a200,k;cout n;cout 请输入数据:; for(int i=0;iai;CreateBST(bt,a,n);coutBST:; BSTdisp(bt);coutendl;cout中序遍历二叉排序树:endl;inorder(bt);coutn;/cout先序遍历二叉排序树:;/preorder(bt);/coutn;coutk;p=BSTSearch(bt,k);if(p!=NULL)BSTDelete(bt,k);cout 已经删除值为k的结点endl;cout中序遍历二叉排序树:; inorder(bt);elsecout无kn;5.程序代码#include typedef int KeyType;typedef char ElemType10;typedef struct tnodeKeyType key;ElemType data;struct tnode *lchild,*rchild;BSTNode;void BSTdisp(BSTNode *b);BSTNode *BSTSearch(BSTNode *bt,KeyType k)BSTNode *p=bt;while (p!=NULL & p-key!=k)if (kkey) p=p-lchild; /*沿左子树查找*/else p=p-rchild; /*沿右子树查找*/return(p);int BSTInsert(BSTNode *&bt,KeyType k)BSTNode *f,*p=bt;while (p!=NULL)if (p-key=k)return(0);f=p;/*f指向*p结点的双亲结点*/if (p-keyk)p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/p=new BSTNode;/*建立新结点*/p-key=k;p-lchild=p-rchild=NULL;if (bt=NULL)/*原树为空时,*p作为根结点插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作为*f的左孩子*/elsef-rchild=p;/*插入*p作为*f的右孩子*/return(1);/*BSTNode *CreatBST(KeyType A,int n)/由数组中的关键字建立一棵二叉排序树BSTNode *bt=NULL; /初始时bt为空树int i=0;while(in)if(BSTInsert(bt,Ai) /将Ai插入二叉排序树T中count 第i+1步，插入:Ai;DispBST(bt); printf(n);i+;return bt; /返回建立的二叉排序树的根指针*/void CreateBST(BSTNode *&bt,KeyType str,int n)bt=NULL; /*初始时bt为空树*/int i=0;while (ikey!=k)/*查找值域为x的结点*/f=p;if (p-keyk) p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/if (p=NULL)/*未找到key域为k的结点*/return(0);else if (p-lchild=NULL) /*p为被删结点,若它无左子树*/if (f=NULL)/*p是根结点,则用右孩子替换它*/bt=p-rchild;else if (f-lchild=p)/*p是双亲结点的左孩子,则用其右子替换它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它*/f-rchild=p-rchild;delete p;else if (p-rchild=NULL)/*p为被删结点,若它无右子树*/if (f=NULL)/*p是根结点,则用左孩子替换它*/bt=p-lchild;if (f-lchild=p)/*p是双亲结点的左孩子,则用其左孩子替换它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其左孩子替换它*/f-rchild=p-lchild;delete p;else/*p为被删结点,若它有左子树和右子树*/f1=p;r=p-lchild;/*查找*p的左子树中的最右下结点*r*/while (r-rchild!=NULL)/*r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=r-rchild;if (f1-lchild=r)/*r是*f1的左孩子,删除*r*/f1-lchild=r-rchild;else if (f1-rchild=r)/*r是*f1的右孩子,删除*r*/f1-rchild=r-lchild;r-lchild=p-lchild;/*以下语句是用*r替代*p*/r-rchild=p-rchild; if (f=NULL)/*f为根结点*/bt=r;/*被删结点是根结点*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩子*/f-rchild=r;delete p;return(1);/先序遍历/*void preorder(BSTNode *t) if(t!=0) coutkeylchild);preorder(t-rchild);*/中序遍历void inorder(BSTNode *t) if(t!=0) inorder(t-lchild);coutkeyrchild);void BSTdisp(BSTNode *bt)if(bt!=NULL)coutkey;if(bt-lchild !=NULL|bt-rchild !=NULL)coutlchild );if(bt