【文章內(nèi)容簡(jiǎn)介】 emType mina, maxa。 int i, j, ii, jj。 for (i = 0。 i m。 i ++) //找出每一行的最小元素，判斷它是否也是該列最大元素{ mina = A[i][0]。 //設(shè)每行第一個(gè)元素為該行最小元素 jj = 0。 //記錄該最小元素所在列 for (j = 1。 j n。 j ++) //尋找該行最小元素 if (A[i][j] mina){ mina = A[i][j]。 //mina記錄最小元素 jj = j。 //jj記錄最小元素所在列} maxa = A[i][jj]。 //假設(shè)A[i][jj]也是所在列的最大元素 ii = 0。 //記錄該列最大元素所在行 while (ii m amp。amp。 maxa = A[ii][jj]) ii ++。 if (ii m 1) //找到鞍點(diǎn)A[i][jj] return A[i][jj]。}printf (\nThere is no saddle!\n)。 //不存在鞍點(diǎn)，給出提示信息}6．解答：define MaxN 100void TransForm (ElemType A[][MaxN], int m, int n, ElemType TA[][3]){ int i, j, t = 0。 TA[0][0] = m。 //記錄稀疏矩陣總行數(shù) TA[0][1] = n。 //記錄稀疏矩陣總列數(shù) for (i = 0。 i m。 i ++) for (j = 0。 j n。 j ++) if (A[i][j] != 0) //若A[i][j]為非零元素{ TA[++ t][0] = i。 //記錄非零元素在稀疏矩陣中的行號(hào) TA[t][1] = j。 //記錄非零元素在稀疏矩陣中的列號(hào) TA[t][2] = A[i][j]。 //記錄非零元素的值} TA[0][2] = t。 //稀疏矩陣中非零元素的總數(shù)目}7．解答：在計(jì)算兩個(gè)稀疏矩陣相加時(shí)，要考慮到兩個(gè)稀疏矩陣的非零元素不是一一對(duì)應(yīng)的，在建立新的三元組表C時(shí)，為了使三元組元素仍按行優(yōu)先排列，所以每次插入的三元組不一定是A的，按照矩陣元素的行列去找A中的三元組，若有，則加入C，同時(shí)，這個(gè)元素如果在B中也有，則加上B的這個(gè)元素值，否則這個(gè)值就不變；如果A中沒(méi)有，則找B，有則插入C，無(wú)則查找下一個(gè)矩陣元素。算法及測(cè)試程序如下：include define MaxSize 10 typedef int Datatype。 //定義三元組typedef struct{ int i,j。 Datatype v。}TriTupleNode。//定義三元組表typedef struct{ TriTupleNode data[MaxSize]。 int m,n,t。 //矩陣行，列及三元組表長(zhǎng)度}TriTupleTable。//輸出稀疏矩陣void showMatrix(TriTupleTable *a){ int p,q。 int t=0。 for(p=0。pam。p++) { for(q=0。qan。q++) { if(adata[t].i==pamp。amp。adata[t].j==q) { printf(%d ,adata[t].v)。 t++。 } else printf(0 )。 } printf(\n)。 }}///////////////////以下為矩陣加算法 ////////////void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C){ //三元組表表示的矩陣A,B相加 int p,q,k,l。 Cm=Am。//矩陣行數(shù) Cn=An。//矩陣列數(shù) Ct=0。 //三元組表長(zhǎng)度 Cdata[Ct].v=0。 //三元組元素初值 k=0。 l=0。for(p=0。pCm。p++) //行 for(q=0。qCn。q++) //列 if(Adata[k].i==pamp。amp。Adata[k].j==q) { //如果該元素在A表中有 Cdata[Ct].v=0。//初始化三元組值 Cdata[Ct].i=p。 Cdata[Ct].j=q。 Cdata[Ct].v+=Adata[k].v。 if(Bdata[l].i==pamp。amp。Bdata[l].j==q) { //同時(shí)在B中也有 Cdata[Ct].v+=Bdata[l].v。 l++。 //指向B表下一元素 } k++。Ct++。//指向A表下一元素，C表長(zhǎng)增1 } else if(Bdata[l].i==pamp。amp。Bdata[l].j==q) { //若A中無(wú)，而B中有該元素 Cdata[Ct].v=0。//初始化三元組值 Cdata[Ct].i=p。 Cdata[Ct].j=q。 Cdata[Ct].v+=Bdata[l].v。 l++。Ct++。//指向B表下一元素，C表長(zhǎng)增1 } }//以下為測(cè)試程序//主程序void main(){ TriTupleTable A={1,3,4,2,2,4,2,4,3,3,3,9}。 TriTupleTable B={2,3,4,2,4,5}。 TriTupleTable C。 =5。 =5。 =4。 =5。 =5。 =2。 printf(The Matrix A:\n\n)。 showMatrix(amp。A)。 printf(The Matrix B:\n\n)。 showMatrix(amp。B)。 AddTriTuple(amp。A,amp。B,amp。C)。 printf(The Matrix C:\n\n)。 showMatrix(amp。C)。}第5章 樹與二叉樹一、填空題1．根結(jié)點(diǎn)2．31，8，163．n0－1，n－2n0＋14．，2i，2i＋15．2n，n－1，n＋16．先序遍歷，中序遍歷，后序遍歷，層次遍歷7．HIDJEBFGCA8．前驅(qū)9．最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度WPL最短的二叉樹，越近10．ABDCEGF，DBAEGCF，DBGEFCA二、選擇題1．C2．B3．B4．C5．A三、解答題1．解答：前序遍歷序列為：ABCEGDFH，該二叉樹如圖51所示。2．解答：WPL＝34＋64＋73＋112＋152＋202＝149622636111516209763ABDCEFGH 圖51 第1題 圖52 第2題3．哈夫曼樹如圖53所示。圖53 第3題根據(jù)上圖可得編碼表：a:0010 b:10 c:00000 d:0001e:01 f:00001 g:11 h:0011四、上機(jī)操作題1．解答：要交換各結(jié)點(diǎn)的左右子樹，最方便的辦法是用后序遍歷算法，每訪問(wèn)一個(gè)結(jié)點(diǎn)時(shí)把兩棵子樹的指針進(jìn)行交換，最后一次訪問(wèn)是交換根結(jié)點(diǎn)的子樹。//交換子樹void ChangeBinTree(BinTree *T){ if(*T) { //這里以指針為參數(shù)使得交換在實(shí)參的結(jié)點(diǎn)上進(jìn)行 //后序遍歷 BinTree temp。 ChangeBinTree(amp。(*T)lchild)。 ChangeBinTree(amp。(*T)rchild)。 temp=(*T)lchild。 (*T)lchild=(*T)rchild。 (*T)rchild=temp。 } }//以前序序列打印結(jié)點(diǎn)數(shù)據(jù)void PrintNode(BinTree T){ if(T) { printf(%c,Tdata)。 PrintNode(Tlchild)。 PrintNode(Trchild)。 }}//測(cè)試程序void main(){ BinTree root。 CreatBinTree(amp。root)。//建立二叉鏈表 PrintNode(root)。 //輸出原表 printf(\n)。 ChangeBinTree(amp。root)。//交換子樹 PrintNode(root)。 //輸出新表 printf(\n)。}2．解答：以向量為存儲(chǔ)結(jié)構(gòu)的完全二叉樹，其存儲(chǔ)在向量中的結(jié)點(diǎn)其實(shí)是按層次遍歷的次序存放的。include typedef char DataType。//設(shè)結(jié)點(diǎn)數(shù)據(jù)類型為chardefine M 100//設(shè)結(jié)點(diǎn)數(shù)不超過(guò)100typedef DataType BinTree[M]。//以向量結(jié)構(gòu)建立完全二叉樹void CreatBinTree(BinTree *T){ int n。 int i。 printf(輸入結(jié)點(diǎn)個(gè)數(shù)及結(jié)點(diǎn)值:)。 scanf(%d ,amp。n)。//輸入結(jié)點(diǎn)個(gè)數(shù) (*T)[0]=n。 //下標(biāo)為0的結(jié)點(diǎn)存儲(chǔ)結(jié)點(diǎn)個(gè)數(shù) for(i=1。i=n。i++) { //輸入每個(gè)結(jié)點(diǎn)數(shù)據(jù) (*T)[i]=getchar()。 }}void PrintTree(BinTree T){ int i。 for(i=1。 i=T[0]。i++) printf(%c,T[i])。}//前序遍歷算法void Preorder(BinTree T){ int n=T[0]。 char p[M]。//設(shè)置一隊(duì)列存放結(jié)點(diǎn)值 int i,j。 for(i=1。i=n。i++) { if (i==1)//根結(jié)點(diǎn) j=1。 else