軟件綜合課程設(shè)計(jì) 特殊矩陣的壓縮存儲(chǔ)算法的實(shí)現(xiàn)二叉排序樹的實(shí)現(xiàn) 二一四 年 六 月一、特殊矩陣的壓縮存儲(chǔ)算法的實(shí)現(xiàn)1.問題陳述對(duì)于特殊矩陣可以通過壓縮存儲(chǔ)減少存儲(chǔ)空間?；疽螅?1.針對(duì)多種特殊矩陣進(jìn)行壓縮存儲(chǔ)，并能顯示壓縮后的相關(guān)地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應(yīng)的值；2.程序代碼#include#include #includestatic shangsanjiao(int n)int i,j,k,z,g;int L100100,SA100;cout請(qǐng)輸入您要壓縮矩陣的行列數(shù)n;cout請(qǐng)輸入您的矩陣內(nèi)元素：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壓縮存儲(chǔ)后：endl;for(k=0;kn*(n+1)/2+1;k+)coutk SAk;cout若要讀取矩陣的值請(qǐng)輸入100退出輸入000。z;for(g=0;g1000;g+)while(z=100)cout請(qǐng)您輸入未壓縮時(shí)所在行數(shù):i;cout請(qǐng)您輸入未壓縮時(shí)所在列數(shù):j;if(i=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;cout該地址的值為：endl;coutSAk;z=1;cout繼續(xù)請(qǐng)輸入100退出輸入000。z;break;static duichen(int n)int i,j,k,z,g;int L100100,SA100;cout請(qǐng)輸入您要壓縮矩陣的行列數(shù)n;cout請(qǐng)輸入您的矩陣內(nèi)元素：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壓縮存儲(chǔ)后：endl;for(k=0;kn*(n+1)/2;k+)coutk SAk;cout若要讀取矩陣的值請(qǐng)輸入100退出輸入000。z;for(g=0;g1000;g+)while(z=100)cout請(qǐng)您輸入未壓縮時(shí)所在行數(shù):i;cout請(qǐng)您輸入未壓縮時(shí)所在列數(shù):j;if(i=j)k=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;cout該地址的值為：endl;coutSAkendl;z=1;cout繼續(xù)請(qǐng)輸入100退出輸入000。z;break;static xiasanjiao(int n)int i,j,k,z,g;int L100100,SA100;cout請(qǐng)輸入您要壓縮矩陣的 行列數(shù)n;cout請(qǐng)輸入您的矩陣內(nèi)元素： 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壓縮存儲(chǔ)后：endl;for(k=0;kn*(n+1)/2+1;k+)coutk SAk;cout若要讀取矩陣的值請(qǐng)輸入100退出輸入000。z;for(g=0;g1000;g+)while(z=100)cout請(qǐng)您輸入未壓縮時(shí)所在行數(shù):i;cout請(qǐng)您輸入未壓縮時(shí)所在列數(shù):j;if(i=j)k=i*(i-1)/2+j-1;elsek=n*(n+1)/2;cout該地址的值為：endl;coutSAkendl;z=1;cout繼續(xù)請(qǐng)輸入100退出輸入000。z;break;int main()int n,d;int m;for(d=0;d100;d+)cout請(qǐng)選擇您要存儲(chǔ)的特殊矩陣類型：endl;cout1:對(duì)稱矩陣endl;cout2:上三角矩陣endl;cout3:下三角矩陣endl;cout退出請(qǐng)輸入0m;if(m=1)duichen(n);else if(m=2)shangsanjiao(n);else if(m=3)xiasanjiao(n);else if(m=0)break;elsecout對(duì)不起您輸入的選號(hào)錯(cuò)誤endl;3.運(yùn)行結(jié)果1.1運(yùn)行主窗口1.2對(duì)稱矩陣1.3上三角矩陣1.4下三角矩陣二、二叉排序樹的實(shí)現(xiàn)1.問題陳述用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu) (1)以回車(n)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；(3)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；2.需求分析（1）輸入一列數(shù)L，以回車(n)為輸入結(jié)束標(biāo)志,并將輸入的數(shù)列生成一棵二叉樹T。（2）調(diào)用函數(shù)，把生成的二叉樹進(jìn)行中序遍歷，并輸出最后的結(jié)果。（3）輸入一個(gè)數(shù)，在已有的二叉樹排序樹中查找，若沒有找到，則輸出沒有這個(gè)數(shù)，如果有，則輸出存在這個(gè)數(shù)。（4）如果有這個(gè)數(shù)，則調(diào)用刪除函數(shù)，刪除這個(gè)數(shù)生成一棵新的二叉樹，并以中序遍歷輸出新的結(jié)果。3.概要設(shè)計(jì) 要生成一個(gè)二叉樹T，元素類型是ElemType，初始化模塊：CreateBST()創(chuàng)建一棵二叉排序樹： int BSTInsert查找元素x：BSTSearch()中序遍歷二叉排序樹：inorder()4.詳細(xì)設(shè)計(jì)（1）主程序模塊#include typedef int KeyType;typedef char ElemType10;typedef struct tnode KeyType key; ElemType data; struct tnode *lchild,*rchild;BSTNode;定義全局變量、分配儲(chǔ)存空間（2）二叉樹初始化BSTNode *CreatBST(KeyType A,int n)/由數(shù)組中的關(guān)鍵字建立一棵二叉排序樹BSTNode *bt=NULL; /初始時(shí)bt為空樹int i=0;while(ikey=k)return(0);f=p;/*f指向*p結(jié)點(diǎn)的雙親結(jié)點(diǎn)*/if (p-keyk)p=p-lchild;/*在左子樹中查找*/elsep=p-rchild;/*在右子樹中查找*/p=new BSTNode;/*建立新結(jié)點(diǎn)*/p-key=k;p-lchild=p-rchild=NULL;if (bt=NULL)/*原樹為空時(shí),*p作為根結(jié)點(diǎn)插入*/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; /*初始時(shí)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指向待比較的結(jié)點(diǎn),f指向*p的雙親結(jié)點(diǎn)*/while (p!=NULL & p-key!=k) /*查找值域?yàn)閤的結(jié)點(diǎn)*/f=p;if (p-keyk) p=p-lchild; /*在左子樹中查找*/elsep=p-rchild; /*在右子樹中查找*/if (p=NULL) /*未找到key域?yàn)閗的結(jié)點(diǎn)*/return(0);else if (p-lchild=NULL) /*p為被刪結(jié)點(diǎn),若它無左子樹*/if (f=NULL) /*p是根結(jié)點(diǎn),則用右孩子替換它*/bt=p-rchild;else if (f-lchild=p) /*p是雙親結(jié)點(diǎn)的左孩子,則用其右子替換它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是雙親結(jié)點(diǎn)的右孩子,則用其右孩子替換它*/f-rchild=p-rchild;delete p;else if (p-rchild=NULL)/*p為被刪結(jié)點(diǎn),若它無右子樹*/if (f=NULL) /*p是根結(jié)點(diǎn),則用左孩子替換它*/bt=p-lchild;if (f-lchild=p) /*p是雙親結(jié)點(diǎn)的左孩子,則用其左孩子替換它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是雙親結(jié)點(diǎn)的右孩子,則用其左孩子替換它*/f-rchild=p-lchild;delete p;else /*p為被刪結(jié)點(diǎn),若它有左子樹和右子樹*/f1=p;r=p-lchild; /*查找*p的左子樹中的最右下結(jié)點(diǎn)*r*/while (r-rchild!=NULL)/*r一定是無右子樹的結(jié)點(diǎn),*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為根結(jié)點(diǎn)*/bt=r;/*被刪結(jié)點(diǎn)是根結(jié)點(diǎn)*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩子*/f-rchild=r;delete p;return(1);（7）主函數(shù)模塊設(shè)計(jì)void main()int n;BSTNode *bt=NULL,*p;KeyType a200,k;cout n;cout 請(qǐng)輸入數(shù)據(jù):; 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 已經(jīng)刪除值為k的結(jié)點(diǎn)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結(jié)點(diǎn)的雙親結(jié)點(diǎn)*/if (p-keyk)p=p-lchild;/*在左子樹中查找*/elsep=p-rchild;/*在右子樹中查找*/p=new BSTNode;/*建立新結(jié)點(diǎn)*/p-key=k;p-lchild=p-rchild=NULL;if (bt=NULL)/*原樹為空時(shí),*p作為根結(jié)點(diǎn)插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作為*f的左孩子*/elsef-rchild=p;/*插入*p作為*f的右孩子*/return(1);/*BSTNode *CreatBST(KeyType A,int n)/由數(shù)組中的關(guān)鍵字建立一棵二叉排序樹BSTNode *bt=NULL; /初始時(shí)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; /*初始時(shí)bt為空樹*/int i=0;while (ikey!=k)/*查找值域?yàn)閤的結(jié)點(diǎn)*/f=p;if (p-keyk) p=p-lchild;/*在左子樹中查找*/elsep=p-rchild;/*在右子樹中查找*/if (p=NULL)/*未找到key域?yàn)閗的結(jié)點(diǎn)*/return(0);else if (p-lchild=NULL) /*p為被刪結(jié)點(diǎn),若它無左子樹*/if (f=NULL)/*p是根結(jié)點(diǎn),則用右孩子替換它*/bt=p-rchild;else if (f-lchild=p)/*p是雙親結(jié)點(diǎn)的左孩子,則用其右子替換它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是雙親結(jié)點(diǎn)的右孩子,則用其右孩子替換它*/f-rchild=p-rchild;delete p;else if (p-rchild=NULL)/*p為被刪結(jié)點(diǎn),若它無右子樹*/if (f=NULL)/*p是根結(jié)點(diǎn),則用左孩子替換它*/bt=p-lchild;if (f-lchild=p)/*p是雙親結(jié)點(diǎn)的左孩子,則用其左孩子替換它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是雙親結(jié)點(diǎn)的右孩子,則用其左孩子替換它*/f-rchild=p-lchild;delete p;else/*p為被刪結(jié)點(diǎn),若它有左子樹和右子樹*/f1=p;r=p-lchild;/*查找*p的左子樹中的最右下結(jié)點(diǎn)*r*/while (r-rchild!=NULL)/*r一定是無右子樹的結(jié)點(diǎn),*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為根結(jié)點(diǎn)*/bt=r;/*被刪結(jié)點(diǎn)是根結(jié)點(diǎn)*/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