數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實訓(xùn)第五章

1、第5章其他線性數(shù)據(jù)結(jié)構(gòu)這一章主要介紹串和多維數(shù)組,多維數(shù)組中重點是二維數(shù)組5.1習(xí)題解析【習(xí)題1】串的模式匹配題目要求：串的模式匹配又稱子串定位操作.是各種串處理中最重要的操作之一輸入主串竽口子串T,假設(shè)在主串S中存在和T相等的子串,那么返回在S中出現(xiàn)的第一個和T相等的子串在S中的位置,否那么返回0.注意T不能是空串.結(jié)構(gòu)說明：在串的順序定長存儲結(jié)構(gòu)上實現(xiàn),結(jié)構(gòu)設(shè)定如下所示.#defineMAXSIZE100typedefstructharchMAXSIZE;字串最大長度限定為99intlen;SEQSTRING;【解答】#include"datastru.h"#inclu

2、de<stdio.h>intindex(SEQSTRINGs,SEQSTRINGt)/*模式匹配*/inti=1,j=1;while(i<=s.len&&j<=t.len)if(s.chi=t.chj)i+;j+;elsei=i-j+2;j=1;if(j>t.len)returni-t.len;elsereturn0;)main()SEQSTRINGs,t;inti;charch;printf(n請輸入主串,回車鍵結(jié)束：)；ch=getchar();i=1;while(ch!=n")s.chi=ch;i+;/*主串從s.ch的下標(biāo)1開始放

3、起*/ch=getchar();s.len=i-1;/*主串長度放在s.len中*/printf(n請輸入子串,回車鍵結(jié)束：)；ch=getchar();i=1;while(ch!=n").chi=ch;i+;/*子串從t.ch的下標(biāo)1開始放起*/ch=getchar();t.len=i-1;/*子串長度放在t.len中*/i=index(s,t);/*匹配操作算法*/if(i=0)printf(n子串不在主串中n)；elseprintf(n子串在主串中,從位置d開始n,i);【習(xí)題2】稀疏矩陣轉(zhuǎn)置題目要求：對一個稀疏矩陣而言,按提示輸入其行號、列號及每一個元素值,程序?qū)⒔⑾∈杈仃?/p>

4、的三元組存儲結(jié)構(gòu),并將三元組存儲結(jié)構(gòu)的稀疏矩陣轉(zhuǎn)置.程序還將顯示轉(zhuǎn)置前后稀疏矩陣的三元組結(jié)構(gòu).結(jié)構(gòu)說明：三元組存儲結(jié)構(gòu)的稀疏矩陣結(jié)構(gòu)說明如下所示.#defineMAXLEN40#defineDATATYPE1inttypedefstructnti,j;/*一個三元組單元中放入非零元素的行號、列號*/DATATYPE®/*及該非零元素的值*/NODE;typedefstructntm,n,t;/*稀疏矩陣的行號、列號、非零元素個數(shù)*/NODEdataMAXLEN;/*三元組向量*/SPMATRIX;稀疏矩陣中非零元素值設(shè)定為整型量,非零元素個數(shù)最多40個.圖5.1(a)5.1(c)以一

5、個5行6列7個非零元素的稀疏矩陣為例,顯示了程序輸入矩陣數(shù)據(jù)及三元組結(jié)構(gòu)的稀疏矩陣轉(zhuǎn)置的過程.素素素素素素麥素素素素素素素素泰虎元元元元元元元元元元元元元元元元元KxC臉輸輸輸輸葡,輛輸輸就狗貓葡畸.軻飄釉.1234561234561234rj-7O-90oud60005圖5.1(a)稀疏矩陣轉(zhuǎn)置程序示意(1)Jnl2d000L|L|23苜看臂MS©值值值期-1a/'S甘直區(qū)-一f一一一二一n二_61234561234561234561234569I9I_1933J9f«9-90«,99f14-R-Bl91222222333333444444555555一

6、a一一二_二S一一=士_=一=一一一=_-秦素素泰素索秦秦素素素素表素<素素素素素羲素嘉泰案元元元元元元元元元元元元元元元元一7rl元元元元元元元元/人入八入入/XAAA?.A?入/入入(劃前.前,4朝前.r.舸一句阿.阿-W匐叫時前俞,俞,司、珂-劉J聞俞俞、間日珂,情,鼎鋪卻骸票布鼎舄和既吊兼刑李1.鄧鼎泉胃第醺哥醺牛即知圖5.1(b)稀疏矩陣轉(zhuǎn)置程序示意(2)ZI口|圍E3|直(百Aj亞稀聯(lián)矩陣三元組表示：7623LT-C.J45匚2=-=-一一一=-值值值索素泰案爰素和元元元元元元元3231513=-=I一=-號號號號號號號?.另.122?355=-一一_=二號號號號號號號一丁一

7、丁-T丁丁一丁一丁1234567甘置后稀疏距障三元組表示：-n-=-«IJ_J1234567.L-.-_號號號號號號列列列列列列列112333-kj-=一二一=-號號號號號號一T_r一丁-r54273622-5erf25一一=一I二二二一值值值值值素素素素善崇素元元元元元元元357-1253kydrl1uuot圖5.1(c)稀疏矩陣轉(zhuǎn)置程序示意(3)#includedatastru.h#include<malloc.h>#include<stdio.h>SPMATRIXtranspose(SPMATRIXa)/*稀疏矩陣(三元組存儲結(jié)構(gòu))轉(zhuǎn)置算法*/intp,

8、q,col;SPMATRIXb;b.m=a.n;b.n=a.m;b.t=a.t;if(.t!=0)q=1;for(ol=1;col<=a.n;col+)/*a稀疏矩陣的列數(shù)即為轉(zhuǎn)置后稀疏矩陣的行數(shù)*/for(p=1;p<=a.t;p+)if(.datap.j=col)b.dataq.j=a.datap.i;b.dataq.i=a.datap.j;b.dataq.v=a.datap.v;q+;returnb;voidprintmatrix(SPMATRIXc)/*稀疏矩陣(三元組存儲結(jié)構(gòu))顯示*/intn,i;n=c.t;for(i=1;i<=n;i+)printf(%曲=%d

9、列號=%d元素值n,i,c.datai.i,cdatai.j,c.datai.v);)main()PMATRIXa;SPMATRIXb;inti,j,r,c,t,n;n=1;printf(nn輸入矩陣行號數(shù)：)；scanf(d,&r);printf(nn輸入矩陣列號數(shù)：)；scanf(d,&c);a.m=r;a.n=c;printf(n);for(i=0;i<r;i+)/*輸入矩陣各元素值*/for(j=0;j<c;j+)printf(輸入元素%d,%d值：,i+1,j+1);scanf(d,&t);if(t!=0)a.datan.i=i+1;/*將非零元素

10、存入稀疏矩陣三元組存儲結(jié)構(gòu)中*/a.datan.j=j+1;a.datan.v=t;n=n+1;)n=n-1;a.t=n;/*a.t中為稀疏矩陣非零元素個數(shù)*/printf(nn稀疏矩陣三元組表示n)；printmatrix(a);/*稀疏矩陣(三元組存儲結(jié)構(gòu))轉(zhuǎn)置*/b=transpose(a);printf(nn轉(zhuǎn)置后稀疏矩陣三元組表示n)；printmatrix(b);printf(n);5.2實練習(xí)習(xí)題【習(xí)題3】兩順序串判等題目要求：判斷兩順序串是否相等的含義為兩順序串的長度必須相等和兩順序串各對應(yīng)位置上的字符相等【習(xí)題4】稀疏矩陣相加題目要求：矩陣相加必須是在兩個具有相同行號和列號的矩陣上進行.對稀疏矩陣而言,可用三元組表存放稀疏矩陣.兩稀疏矩陣相加的結(jié)果存放在一個新三元組表內(nèi).算法思路提示如下所示.(1)稀疏矩陣用三元組表存放(以行優(yōu)先存放)具有以下的特點：元組中的個數(shù)就是非零元素的個數(shù)；元組中的第一列按行號的順序由小到大排列；元組中的第二列是列