工大數(shù)據(jù)結(jié)構(gòu)作業(yè)

數(shù)據(jù)結(jié)構(gòu)與算法上機作業(yè)第二章線性表、選擇題1、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新的元素算法的時間復(fù)雜度為。A.O(log2n) B.O(1)C.O(n) D.O(n2)2、以下關(guān)于線性表的說法中，不正確的是 。A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、結(jié)構(gòu)等不同類型B.線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的C.線性表中的每一個結(jié)點都有且只有一個直接前驅(qū)和直接后繼(單項鏈表)D.存在這樣的線性表：表中各結(jié)點都沒有直接前驅(qū)和直接后繼(數(shù)組實現(xiàn))3、在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為 。A.O(1)B.O(n)C.O(n2) D.O(log2n)4、等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點操作，需平均移動的結(jié)點數(shù)目為A.nB.(n-1)/2C,n/2D.(n+1)/2已經(jīng)有N個點了，再加一個就是N+1個.假設(shè)新加的結(jié)點插在第i位,那么后面N+1-i個結(jié)點都要往后移動.i的取值服從1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移動N/2個結(jié)點期望有計算公式，這里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/25、在一個長度為n的順序存儲的線性表中查找值為x的元素時，平均查找長度(及x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等)為。A.nB,n/2C.(n+1)/2D,(n-1)/26、在順序表中，只要知道 ，就可以求出任一結(jié)點的存儲地址。A.基地址B.結(jié)點大小C.向量大小D.基地址和結(jié)點大小TOC\o"1-5"\h\z7、將兩個各有n個元素的有序表歸并為一個有序表，其最少的比較次數(shù)是 。A.nB.2n-1C.2nD.n-18、線性表采用鏈表存儲時其存儲地址要求 。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.必須是不連續(xù)的 D.連續(xù)的和不連續(xù)的都可以9、下面關(guān)于線性表的描述中，錯誤的是 。A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B.線性表采用順序存儲，便于進行插入和刪除操作C.線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D.線性表采用鏈式存儲，便于插入和刪除操作10、向具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是O(1)B.O(n)C.O(n2) D.O(log2n)11、語句是 。A.HL=p;p->next=HL;C.p->next=HL;p=HL;A.HL=p;p->next=HL;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;HL為鏈表的頭指針。HL指示鏈表中第一個節(jié)點的存儲位置，在表頭插入一個由指針p指向的節(jié)點后，頭指針指向p，p的指針域指向原鏈表中第一個節(jié)點12、在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行的語句是p=q->next;p->next=q->next;p=q->next;q->next=p;p=q->next;q->next=p->next;q->next=q->next->next;q->next=q;順序進入一個棧結(jié)構(gòu)的站臺，下列不可能的出棧順13、設(shè)有編號為1,2,3,4的4輛列車，序為。順序進入一個棧結(jié)構(gòu)的站臺，下列不可能的出棧順A.1234B,1243C,1324D,1423至少有14種。①全進之后再出情況只有1種：4,3,2，1②進3個后再出的情況有3種3,4,2,1 3,2,4,13,2,1,4③進2個后再出的情況有5種2,4,3,12,3,4,1 2,1,3,42,1,4,32,1,3,4④進1個后再出的情況，有5種1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,314、4個元素按A,B,C,D順序進入S棧，執(zhí)行兩次Pop(S,x)運算后，棧頂元素的值是一。A.AB.BC.CD.D15、從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(yīng)執(zhí)行下列 命令。A.x=top;top=top->next; B.top=top->next;x=top->data;C.x=top->data; D.x=top->data;top=top->next;16、向順序棧中輸入元素時 。A.先存入元素，后移動棧頂指針 B.先移動棧頂指針，后存入元素C.誰先誰后無關(guān)緊要 D.同時進行17、設(shè)有一個順序棧，元素A,B,C,D,E,F依次進棧，如果6個元素出棧的順序是B,D,C,F,E,A，則棧的容量至少為。A.3B.4C.5D.6順序如下A入棧B入棧然后B出棧,C入棧D入棧,D出棧,C出棧,E入棧,F入棧,F出棧,E出棧.棧里元素最多時候就是acd和aef,所以3個就夠了18、設(shè)已將元素A,B,C依次入棧，元素D正等待進棧。那么下列4個序列中不可能出現(xiàn)的出棧順序為。CADBB.CBDAC.CDBAD.DCBA19、棧和隊列的相同之處是 。A.元素的進出滿足先進后出 B.元素的進出滿足后進先出C.只允許在端點進行插入和刪除操作 D.無共同點棧Insert(L,n+1,x)Delete(L,n)而棧只允許在表尾一端進行插入和刪除隊列Insert(L,n+1,x)Delete(L,1)隊列只允許在表尾一端進行插入，在表頭一端進行刪除20、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過棧，一個元素出棧后即進入隊列Q,若6個元素出隊的序列是e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是 。A.6B.4C.3D.2設(shè)棧長度為s,起始為0因為棧后進先出，隊列先進先出.又因為元素E1..E6是順序入棧,那么分析過程如下：按照出棧過程分析,因為給定出棧順序：E2,E4,E3,E6,E5,E1,E2要進棧，所以E1必須進棧，進棧順序：E1,E2,所以s為2下面E2出棧,打印出E2,剩余結(jié)果為E4,E3,E6,E5,E1,因為E2出棧了，所以當前棧容量為2,但是只是用了1個，存放E1,下面繼續(xù)E3進棧,E4進棧，此時s為3,根據(jù)出棧結(jié)果，那么E4出棧,E3出棧,此時棧容量為3但是只有E1在棧中，剩余結(jié)果為E6,E5,E1,同理,E5進棧,E6進棧，此時棧被填滿,容量為3,后E6出棧,E5出棧,E1出棧，?？杖芰繛?.所以S的容量至少為3.21、隊列通常采用的兩種存儲結(jié)構(gòu)是()。A.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu) B.散列方式和索引方式C.鏈表存儲結(jié)構(gòu)和線性存儲結(jié)構(gòu) D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)22、循環(huán)隊列SQ隊滿的條件是 。A.SQ->rear==SQ->front B.(SQ->rear+1)%MAXLEN==SQ->frontSQ->rear==0 D.SQ->front==0隊空:Q.front=Q.rear隊滿:(Q.rear+1)%MAXQSIZE=Q.front23、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3和0，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為。A.5和1B.4和2C.2和4D.1和5TOC\o"1-5"\h\z24、鏈棧與順序棧相比，有一個較為明顯的優(yōu)點是 。A.通常不會出現(xiàn)滿棧的情況 B.通常不會出現(xiàn)棧空的情況C.插入操作更加方便 D.刪除操作更加方便25、設(shè)用一個大小為M=60的順序表A[M]表示一個循環(huán)隊列，如果當前的尾指針rear=32,頭指針front=15,則當前循環(huán)隊列的元素的個數(shù)為 。A.42B.16C.17D.4126、串是一種特殊的線性表，其特殊性體現(xiàn)在 。A.可以順序存儲 B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲 D.數(shù)據(jù)元素可以是多個字符27、設(shè)主串的長度為n，模式串的長度為m，則串匹配的KMP算法的時間復(fù)雜度為 。A.O(m)B,O(n)C,O(m+n)D,O(mXn)28、已知串S="abab"，其Next數(shù)組值為。A.0123B.0121C.0112D.012229、若字符串"ABCDEFG”采用不帶表頭的鏈式存儲，每個結(jié)點保存一個字符。假設(shè)每個字符占用1個字節(jié)，每個指針占用兩個字節(jié)，則該字符串的存儲密度為 。A.20%B.40%C.50%D.33.3%存儲密度;結(jié)點數(shù)據(jù)本身所占的存儲量/結(jié)點結(jié)構(gòu)所占的存儲量 1/(1+3)30、在雙向鏈表中，在指針p所指的結(jié)點前插入一個指針q所指向的結(jié)點，操作是 。p->Prior=q;q->Next=p;p->Prior->next=q;q->Prior=q;p->Prior=q;p->Prior->next=q;q->next=p;q->Prior=p->Prior;q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;q->Prior=p->Prior;q->Next=q;p->Prior=q;p->Next=q;TOC\o"1-5"\h\z31、已知循環(huán)隊列存儲在一維數(shù)組A[0…n-1]中，且隊列非空時front和rear分別指向?qū)︻^元素和隊尾元素，且要求第一個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是 。A.0,0 B,0,n-1C,n-1,0D.n-1,n-132、某隊列允許在兩端進行入隊操作，但僅允許在一端進行出隊操作(稱為輸出受限的雙端隊列)，若a,b,c,d,e元素依次進隊，則不可能得到的順序是 。A.bacdeB.dbaceC.dbcaeD.ecbad33、在雙向鏈表中間插入一個結(jié)點時，需要修改修改個指針域。A.1B.2C.3D.434、在按行優(yōu)先順序存儲的三元組表中，下述陳述錯誤的是 。A.同一行的非零元素，是按列號遞增次序存儲的B.同一列的非零元素，是按行號遞增次序存儲的C.三元組表中三元組行號是非遞減的D.三元組表中三元組列號是非遞減的35、在稀疏矩陣的三元組表示法中，每個三元組表示 。A.矩陣中非零元素的值B.矩陣中數(shù)據(jù)元素的行號和列號C.矩陣中數(shù)據(jù)元素的行號、列號和值D.矩陣中非零數(shù)據(jù)元素的行號、列號和值36、對特殊矩陣采用壓縮存儲的目的主要是為了。A.表達變得簡單 B.對矩陣元素的存取變得簡單C.去掉矩陣中的多余元素D,減少不必要的存儲空間TOC\o"1-5"\h\z37、廣義表是線性表的推廣，它們之間的區(qū)別在于 。A.能否使用子表 B.能否使用原子項C.表的長度 D.是否能為空38、已知廣義表(a,b,c,d)的表頭是 ，表尾是 。A.aB.()C,(a,b,c,d)D,(b,c,d)39、下面說法不正確的是 。A.廣義表的表頭總是一個廣義表 B,廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結(jié)構(gòu)表示 D.廣義表可以是一個多層次的結(jié)構(gòu)40、若廣義表A滿足Head(A)=Tail(A)，則A為。A.()B.(())C.((),())D.((),(),())二、填空題1、線性表中結(jié)點的集合是有限的，結(jié)點之間的關(guān)系是一對一 關(guān)系。2、順序表中訪問任一個結(jié)點的時間復(fù)雜度為—0(1) 。3、線性表中第一個結(jié)點沒有直接前驅(qū)，稱為 頭 結(jié)點。4、在一個長度為n的順序表中刪除第i個元素，要移動—n-i 個元素。5、在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移—n-i-1一個元素，在插入操作中，移動元素的均值為 （n+1）/2。6、根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成單向鏈表和雙向鏈表7、鏈式存儲的特點是利用指針 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。8、靜態(tài)鏈表（線性表的游標實現(xiàn)）是指用數(shù)組下標 表示單鏈表的指針。9、在靜態(tài)鏈表中，一般都有一個變量available表示的結(jié)點鏈，其中的結(jié)點為空閑結(jié)點。10、在棧中，可進行插入和刪除操作的一端稱 棧頂 。11、在進棧運算時，應(yīng)先判別棧是否一滿—。在出棧運算時應(yīng)先判別棧是否_空—。當棧中元素為n個時，進棧運算時發(fā)生上溢，則說明該棧的最大容量為—n 。12、設(shè)有一空棧，現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過push,push,pop,push,pop,push,push,pop,pop之后，輸出序列為2354。13、對于循環(huán)向量的循環(huán)隊列，求隊列長度的公式為 （rear-front+n+1）%n14、棧的邏輯特點是先進后出 。隊列的邏輯特點是先進先出兩者的共同特點是只允許在它們的 端點 出插入和刪除數(shù)據(jù)元素，區(qū)別是TOC\o"1-5"\h\z棧在棧頂進行插入刪除，隊列在兩端操作，隊尾插入，隊首刪除 。15、鏈隊列LQ為空時，LQ->front->next=NULL.16、在一個鏈隊列中，若隊首指針為front，隊尾指針為rear，則判斷該隊列只有一個結(jié)點的條件為 front.next==rear 。17、設(shè)串S="Ilikecomputer"，T=“com”，則ULength（S）=13。Index（S,T）= 6。18、在KMP算法中，next用只與—王—串有關(guān)，而與主串 無關(guān)。19、字符串“ababaab”的Next數(shù)組值是, 011234220、稀疏矩陣一般壓縮存儲的方式有三種，分別是三原組存儲、行指針鏈表和十字鏈表21、二維數(shù)組M中每個元素的長度是3字節(jié)，行下標i從0?7,列下標j從0?9,從首地址&M[0][0]開始連續(xù)存放在存儲器中。若按行優(yōu)先的方式存放，元素M[7][5]的起始地址為 M[0][0]+225 ；若按列優(yōu)先方式存放，元素M[7][5]的起始地址為M[0][0]+14122、廣義表(a,(a,b),d,e,((i,j),k))的長度是■—5 ，深度是_3_23、設(shè)廣義表A(((),(a,(b),c))),則Cal(Cdr(Cal(Cdr(Cal(A))))=(b)三、寫一個算法合并兩個已排序的線性表。（用兩種方法：數(shù)組表示的線性表（順序表）和指針表示的線性表（鏈表））要求：1、定義線性表節(jié)點的結(jié)構(gòu)，并定義節(jié)點的型和位置的型。2、定義線性表的基本操作3、在1,2的基礎(chǔ)上，完成本題。4、在main函數(shù)中進行測試：先構(gòu)建兩個有序的線性表，然后合并這兩個線性表。四、已知一個單向鏈表，試給出復(fù)制該鏈表的算法。要求：1、定義線性表的節(jié)點的結(jié)構(gòu)以及節(jié)點的型和位置的型。2、定義線性表的基本操作3、在1,2的基礎(chǔ)上，完成本題。4、在main函數(shù)中進行測試：先構(gòu)建一個線性表，并定義一個空線性表，然后進行復(fù)制。五、寫出從一個帶表頭的單鏈表中刪除其值等于給定值x的結(jié)點的算法函數(shù)：intdelete(LIST&L,intx);如果x在該鏈表中，則刪除對應(yīng)結(jié)點，并返回其在鏈表中的位置(邏輯位置，第一個結(jié)點的邏輯位置為1)，否則返回-1。要求：1、定義線性表的節(jié)點的結(jié)構(gòu)以及節(jié)點的型和位置的型。2、定義線性表的基本操作3、在1，2的基礎(chǔ)上，完成本題。4、在main函數(shù)中進行測試：先構(gòu)建一個線性表，然后調(diào)用函數(shù)刪除值等于給定值的節(jié)點。三，四，五#include<iostream>usingnamespacestd;typedefintelementtype;/^素類型structcelltype//鏈表節(jié)點{elementtypeelements;celltype*next;);typedefcelltype*LIST;typedefcelltype"position;//線性表的“型”與位置的“型”相同positionEnd(LISTL)〃返回L中指向最后一個節(jié)點的指針{positionp;p=L;while(p->next!=NULL)p=p->next;returnp;)voidInsert(elementtypex,positionp,LIST&L)//創(chuàng)建元素x的節(jié)點插在p的后面{positionqq=newcelltypeq->elements=xq->next=p->nextp->next=q)〃時間復(fù)雜性：O(1)positionLocate(elementtypex,LISTL)//i返回元素x在線性表中的位置{positionpp=Lwhile(p->next!=NULL)if(p->next->elements==x)returnpelsep=p->next;returnp)〃時間復(fù)雜性：O(n)elementtypeRetrieve(positionp,LISTL){return(p->next->elements);)〃時間復(fù)雜性：O(1)voidDelete(positionp,LIST&L)/刪除位置p的下一個節(jié)點{positionqif(p->next!=NULL){q=p->nextp->next=q->nextdeleteq))〃時間復(fù)雜性：O(1)positionPrevious(positionp,LISTL)//返回位置p的前驅(qū)元素{positionqif(p==L->next)8a<<"不存在前驅(qū)元素！"<<endl;else{q=Lwhile(q->next!=p)q=q->nextreturnq})〃時間復(fù)雜度O(n)positionNext(positionp,LISTL)/返回位置p的后驅(qū)元素{positionqif(p->next==NULL)cout<<"不存在后繼元素！"<<endl;else{q=p->next;returnq}}〃時間復(fù)雜度O(1)positionMakeNull(LIST&L){L=newcelltypeL->next=NULL;returnL}〃時間復(fù)雜性：O(1)positionFirst(LISTL){returnL;}〃時間復(fù)雜性：O(1)voidTravel(LISTL)/遍歷線性表元素{positionpp=L->nextwhile(p!=NULL){cout<<p->elements<<endl;p=p->next}}〃=================================================voidMerge(LIST&L,LISTL1,LISTL2)〃合并兩個線性表(鏈表)，將L1,L2合并到L中(positionp1=0,p2=0,p3=0;for(p3=L1;p3;p3=p3->next)(p1=newcelltype;p1->elements=p3->elements;If(L==0)(L=p1;p2=p1;)else(p2->next=p1;p2=p1;))for(p3=L2;p3;p3=p3->next){p1=newcelltype;p1->elements=p3->elements;if(L==0){L=p1;p2=p1; }else{p2->next=p1;p2=p1;}}p2->next=NULL;}〃==============================================〃復(fù)制鏈表voidcopy(LIST&L1,LISTL2){positionp1=0,p2=0,p3=0;for(p3=L2;p3;p3=p3->next){p1=newcelltype;p1->elements=p3->elements;If(L1==0){L1=p1;p2=p1; }else{p2->next=p1;p2=p1;}}p2->next=NULL;}//=====================================================//刪除指定元素的節(jié)點intDelete(LIST&L,intx)(intm=1;//指定元素在線性表中的位置positionp1=0,p2=0;if(L->elements==x){p1=L;L=L->next;deletep1;returnm;)else{p1=p2=L;while(p1->elements!=x&&p1->next!=NULL){p2=p1;m++;p1=p1->next;)p2->next=p1->next;deletep1;returnm;)return-1;//不存在元素x}voidRead(LIST&L,inti)//輸入數(shù)據(jù){cout<<"請輸入第"<<1<<"個線性表"<<endl;LISTp1=0,p2=0;elementtypex;for(;;){cout<<”請輸入數(shù)據(jù)(-1作為結(jié)束標志):"；cin>>x;if(x==-1)break;p1=newcelltype;p1->elements=x;if(L==0){L=p1;p2=p1; }else{p2->next=p1;p2=p1;}}p2->next=NULL;}voidWrite(LISTL)//輸出{positionp=L;for(;p;p=p->next)cout<<p->elements<<'\t';cout<<endl;}voidmain()(cout<<"本次測試的類型為int"<<endl;LISTL=NULL,L1=NULL,L2=NULL;Read(L1,1);cout<<"L1的元素為："<<endl;Write(L1);Read(L2,2);cout<<"L2的元素為："<<endl;Write(L2);Merge(L,L1,L2);cout<<"L1,L2合并后L的元素為："<<endl;Write(L);/*LISTL=NULL,L1=NULL;read(L);cout<<"原有的元素："；write(L);copy(L1,L);cout<<"復(fù)制之后的元素：”；write(L1);LISThead=NULL;read(head);cout<<"刪除前：";write(head);cout<<"請輸入要刪除的數(shù)據(jù):";Elementtypex;cin>>x;intm=Delete(head,x);cout<<"刪除后："；write(head);if(m==-1)cout<<"需要刪除的數(shù)不存在"<<endl;elsecout<<"需要刪除的數(shù)是第"<<m<<"個"<<endl;*/}〃線性表的數(shù)組實現(xiàn)-線性表的合并#include<iostream>usingnamespacestd;#definemaxlength100typedefintposition;/4位置類型typedefintElementtype;//下標類型structLIST(Elementtypeelements[maxlength];intlast;//最后一個元素的下標};positionEnd(LISTL)〃線性表的長度(return(L.last+1);)voidInsert(Elementtypex,positionp,LIST&L)/在表L的位置p處插入x(positionq;if(L.last>=maxlength-1)cout<<"listisfull"<<endl;elseif((p>L.last+1)||(p<1))cout<<"positiondoesnotexist"<<endl;else{for(q=L.last;q>=p;q--)L.elements[q+1]=L.elements[q];L.last=L.last+1;L.elements[p]=x;))voidDelete(positionp,LIST&L)//刪除位置p處的元素{positionq;if((p>L.last+1)||(p<1))cout<<"positiondoesnotexist"<<endl;else{L.last=L.last-1;for(q=p;q<=L.last;q++)L.elements[q]=L.elements[q+1];})positionLocate(Elementtypex,LISTL)/返回x在表L中的位置{positionq;for(q=0;q<L.last;q++)if(L.elements[q]==x)returnq;return(L.last+1);//x不存在}ElementtypeRetrive(positionp,LISTL)/返回L中位置為p的元素{if((p<1)||(p>L.last+1)){cout<<"positiondoesnotexist"<<endl;return-1;}returnL.elements[p];}//======================================================//將兩個線性表合并voidMerge(LIST&L,LISTL1,LISTL2){positionp,p1,p2;positionlen1=End(L1);//L1的長度positionlen2=End(L2);//L2的長度L.last=len1+len2-1;/^并后L的最后一個元素的位置p=p1=p2=0for(;p1<len1;)//#L1的元素寫進L{L.elements[p]=L1.elements[p1];p++;p1++;}for(;p2<len2;)//繼續(xù)將L2的元素寫進L{L.elements[p]=L2.elements[p2];p++;p2++;})voidRead(LIST&L,inti)//輸入線性表{cout<<"請輸入第"<<1<<"個線性表的長度:";cin>>L.last;L.last--;cout<<"請輸入第"<<1<<"個線性表的元素："<<endl;for(positionp=0;p<=L.last;p++)cin>>L.elements[p];}voidWrite(LISTL)//輸出線性表{cout<<"線性表的長度為："<<End(L)<<endl;cout<<"線性表的元素為："<<endl;for(positionp=0;p<=L.last;p++)cout<<L,elements[p]<<'\t';cout<<endl;}voidmain(){cout<<"本次測試的類型為int"<<endl;LISTL,L1,L2;Read(L1,1);Read(L2,2);Merge(L,L1,L2);Write(L);}六、寫出一個將兩個靜態(tài)鏈表(屬于同一個存儲池)合并的算法函數(shù)：voidMerge(cursorM,cursorN);合并的方法是將N鏈表中的所有結(jié)點添加到M鏈表的后面，并將N鏈表的表頭結(jié)點添加到空閑結(jié)點鏈表中。要求：1、定義靜態(tài)鏈表的結(jié)點的結(jié)構(gòu)以及結(jié)點的型SPACE以及位置(position)和游標(cursor)的型。2、定義靜態(tài)鏈表的基本操作：voidInitialize();初始化，將所有存儲池中的結(jié)點設(shè)置為空閑；cursorGetNode();從空閑鏈中獲取一個結(jié)點；voidFreeNode(cursorq);將結(jié)點q加入到空閑鏈；voidInsert(elementtypex,positionp,cursorM);在鏈表M中的位置為p的元素后面添加一個值為x的結(jié)點；voidDelete(cursorM,positionp);在鏈表M中刪除位置為p的元素的后一個元素。3、在1、2的基礎(chǔ)上完成本題。4,在main函數(shù)中進行測試：先構(gòu)建一個存儲池，然后在該存儲池中創(chuàng)建兩個靜態(tài)表，最后將這兩個靜態(tài)表合并。#include<iostream>usingnamespacestd;#definemaxsize100typedefintelementtype;typedefstruct{elementtypeelementintnext}spacestr;/*結(jié)點類型*/spacestrSPACE[maxsize]/*存儲池*/typedefintposition,cursor;cursoravailable;/*標識線性表/空閑池*/voidInitialize(){intj;/*依次鏈接池中結(jié)點*/for(j=0;j<maxsize-1;j++)SPACE[j].next=j+1;SPACE[j].next=-1;/*最后一個接點指針域為空*/available=0;/*標識線性表，將所有存儲池中的結(jié)點設(shè)置為空閑，avilable為頭結(jié)點，不利用*/}//可用空間的分配操作，從空閑鏈中獲取一個結(jié)點cursorGetNode()//q=newspacest{cursorp;if(SPACE[available].next==-1)p=-1;else{p=SPACE[available].nextSPACE[available].next=SPACE[p].next}returnp;}/*將空閑池頭結(jié)點的下一個節(jié)點從空閑池中刪除*/voidFreeNode(cursorq)//deleteq;{SPACE[q].next=SPACE[available].nextSPACE[available].next=q}/*將q指向的節(jié)點放回池中*///在位置p后面插入元素值為x的結(jié)點voidInsert(elementtypex,positionp){positionqq=GetNode()SPACE[q].element=xSPACE[q].next=SPACE[p].nextSPACE[p].next=q}//刪除位置p后的一個結(jié)點voidDelete(positionp){positionq；if(SPACE[p].next!=-1){q=SPACE[p].next；SPACE[p].next=SPACE[q].next；FreeNode(q)}}〃創(chuàng)建靜態(tài)鏈表voidCreate(cursorM){elementtypeinput;positionp=M;while(1)(cout<<"請輸入靜態(tài)鏈表的值，輸入-1結(jié)束："<<endl;cin>>input;if(input!=-1)(Insert(input,p);p=SPACE[p].next;)elsebreak;))voidMerge(cursorM,cursorN)〃連接兩個鏈表，將N鏈表中的所有結(jié)點添加到M鏈表的后面，并將N鏈表的表頭結(jié)點添加到空閑結(jié)點鏈表中(positionp;p=M;while(SPACE[p].next!=-1)p=SPACE[p].next;positionq;q=SPACE[N].next;SPACE[p].next=q;FreeNode(N);)〃輸出靜態(tài)鏈表voidPrint(cursorM){positionp;p=M;while(SPACE[p].next!=-1){cout<<SPACE[SPACE[p].next].element<<'\t';p=SPACE[p].next;}cout<<endl;}voidmain(){spacestrs;Initialize();positionp=GetNode();cursorM=GetNode();SPACE[M].next=-1;cursorN=GetNode();SPACE[N].next=-1;cout<<"創(chuàng)建靜態(tài)鏈表M："<<endl;Create(M);Print(M);cout<<"創(chuàng)建靜態(tài)鏈表N："<<endl;Create(N);Print(N);cout<<"#M和N合并后："<<endl;Merge(M,N);Print(M);)七、利用指針表示的線性表(鏈表)表示一個多項式，并實現(xiàn)兩個多項式的相加和相乘運算。假設(shè)多項式形式為：A(x)=atem+axem_1+...+ax)m m-1 1其中，系數(shù)叫，0，指數(shù)ei滿足em>em1>...>e2>e1>=0。要求：1、定義多項式每一項的結(jié)構(gòu)。。2、定義兩個多項式的相加和相乘運算函數(shù)。3、在main函數(shù)中，構(gòu)建兩個多項式，并測試相加和相乘運算。#ifndefPOLYNOMIAL_H#definePOLYNOMIAL_H#include<stdlib.h>#include<stdio.h>#include<float.h>〃鏈表結(jié)構(gòu)typedefstructNode{structNode*next;doublecoefficient;intexponent;}Node,"Polynomial; 〃鏈表初始化voidinitList(Polynomial*L){ 〃頭結(jié)點if(NULL==*L){*L=(Polynomial)malloc(sizeof(Node));(*L)->coefficient=0.0;(*L)->exponent=-1;(*L)->next=NULL;}else{8a<<"表已經(jīng)存在！"；}} 〃判斷指數(shù)同否intcompareExponent(PolynomialnodeA,PolynomialnodeB){inta=nodeA->exponent;intb=nodeB->exponent;if(a==b)return0;)else(returna>b?1:-1;))〃系數(shù)判斷boolisZeroByCoefficient(Polynomialnode)(if(node->coefficient>=-LDBL_EPSILON&&node->coefficient<=LDBL_EPSILON)(returntrue;)else(returnfalse;))//判斷2〃系數(shù)判斷boolisZeroByDouble(doublea)(if(a>=-LDBL_EPSILON&&a<=LDBL_EPSILON)(returntrue;else(returnfalse;)) 〃尾插法建表voidcreatListByTail(Polynomial*L,intn)(〃頭結(jié)點if(NULL==*L)(*L=(Polynomial)malloc(sizeof(Node));(*L)->coefficient=0.0;(*L)->exponent=-1;(*L)->next=NULL;Polynomialtail=NULL;Polynomialptr=*L;//初始化？if(NULL==(*L)->next)(Cout<<"請按照指數(shù)升幕，連續(xù)的輸入項的系數(shù)(double)和指數(shù)6nt)：(中間 空格隔開)"<<endl;〃循環(huán)建表for(inti=0;i<n;i++)(tail=(Polynomial)malloc(sizeof(Node));tail->next=NULL;scanf("%lf%d",&tail->coefficient,&tail->exponent);while(getchar()!='\n')(continue;)//鏈接ptr->next=tail;〃移動指針ptr=ptr->next;〃尾結(jié)點))else(Cout<<"表已經(jīng)建立！"<<endl;))else(Cout<<"表頭已經(jīng)存在！"<<endl;))〃遍歷voidtraverseList(PolynomialL)(Polynomialptr=L->next;inti=1;while(ptr!=NULL)(Cout<<”一元多項式的第％4項：%gXA%d\n"<<i<<ptr->coefficient<<ptr->exponentendl;i++;ptr=ptr->next;))〃求最高階數(shù)intgetMaxExp(PolynomialL)(Polynomialptr=L;while(ptr->next!=NULL)(ptr=ptr->next;)returnptr->exponent;}〃刪除結(jié)點，刪除L中ptr指向的結(jié)點voiddeleteNode(PolynomialL,Polynomialptr)(Polynomialp=L;while(p->next!=ptr)(p=p->next;}ptr=p->next;p->next->next=ptr->next;free(ptr);ptr=NULL;165}〃多項式相加，本質(zhì)是鏈表的歸并算法〃可以另外開辟空間，也可以使用已存在的空間存儲，這里使用后者的算法voidaddPolynomial(PolynomialLA,PolynomialLB){〃不再開辟內(nèi)存Polynomiala=LA->next;Polynomialb=LB->next;PolynomialLC=LB;Polynomialtail=LC;while(a!=NULL&&b!=NULL){〃判斷指數(shù)的關(guān)系a>b?1:-1else0switch(compareExponent(a,b)){case1:tail->next=b;tail=tail->next;b=b->next;break;case-1:tail->next=a;tail=tail->next;a=a->next;break;default:doubletemp=a->coefficient+b->coefficient;//0？if(isZeroByDouble(temp))a=a->next;b=b->next;〃刪除deleteNode(LC,tail->next);)else(tail->next=b;tail=tail->next;b->coefficient=temp;a=a->next;b=b->next;}//endofif}//endofswitch}//endofwhile〃一表比完if(NULL==a)(tail->next=b;}else(tail->next=a;}//endofiffree(LA);LA=NULL;}〃多項式相乘voidmulPolynomial(PolynomialLA,PolynomialLB,PolynomialLC)(Polynomiala=LA->next;Polynomialb=LB->next;Polynomialc=LC;Polynomialptr=NULL;〃兩多項式的階數(shù)intnumA=getMaxExp(LA);intnumB=getMaxExp(LB);〃結(jié)果多項式的階數(shù)intmaxNum=numA+numB;〃動態(tài)開辟數(shù)組空間double*receive=(double*)malloc((maxNum+1)*sizeof(double));〃為數(shù)組賦值for(inti=0;i<maxNum+1;i++)//i相當于指數(shù)，數(shù)組值就是相應(yīng)指數(shù)的系數(shù)receive[i]=0.0;)〃指數(shù)及數(shù)組下標intexpBylndex=0;//順次掃描Awhile(a!=NULL){//A不空，順次掃描Bwhile(b!=NULL){〃兩項做乘法之后的指數(shù)和expByIndex=a->exponent+b->exponent;〃系數(shù)之間做乘，結(jié)果保存到對應(yīng)的指數(shù)下(下標)，receive[expByIndex]+=(a->coefficient)*(b->coefficient);b=b->next;)b=LB->next;a=a->next;}//endofwhile〃數(shù)組保存的是全部項，兩兩分別乘法之后的結(jié)果，保存在對應(yīng)的下標(數(shù)組位置)for(inti=0;i<maxNum+1;i++){//0？if(isZeroByDouble(receive[i])){//notdosth}else{〃生成結(jié)點ptr=(Polynomial)malloc(sizeof(Node));〃接到LC表c->next=ptr;c=c->next;〃賦值c->coefficient=receive[i];c->exponent=i;}//endofif}//endofforc->next=NULL;}〃鏈表銷毀voiddestroyList(Polynomial*L){Polynomialptr=NULL;while(*L!=NULL)ptr=(*L)->next;free(*L);*L=ptr;)//*L=NULL;cout<<"銷毀完畢"endl;)#endif八、試編寫一個整數(shù)進制轉(zhuǎn)換的通用函數(shù)convert(intnum,STACKS,intn),要求將整數(shù)m轉(zhuǎn)換為n進制數(shù)，n進制數(shù)的各位依次存放在棧S中。并在主函數(shù)中進行測試。要求：1、定義棧以及棧的型。2、定義棧的各種操作。3、實現(xiàn)函數(shù)converto4、在main函數(shù)中，通過調(diào)用函數(shù)convert將num的n進制數(shù)存放到一個棧中，并通過出棧的方法輸出該n進制數(shù)〃棧的數(shù)組實現(xiàn)〃此處將棧底規(guī)定在數(shù)組的底部，即讓maxlength-1指向棧底的第一個元素#include<iostream>usingnamespacestd;#definemaxlength100//棧的容量typedefintElementtype;structSTACK//定義整型線性數(shù)組棧(inttop;Elementtypeelements[maxlength];);boolisEmpty(STACKS)//棧是否為空(if(S.top>=maxlength)returntrue;elsereturnfalse;)voidmakeNull(STACK&S)//棧置空(S.top=maxlength;)Elementtypetop(STACKS)/返回棧頂元素(if(isEmpty(S))cout<<"棧為空！"<<endl;elsereturn(S.elements[S.top]);)voidpop(STACK&S)//出棧,刪除棧頂元素(if(isEmpty(S))cout<<"棧為空！"<<endl;elseS.top++;)voidpush(STACK&S,Elementtypex)/進棧(if(S.top==0)8a<<"棧已滿！"<<endl;else(--S.top;S.elements[S.top]=x;))voidconvert(intnum,STACK&S,intn)/進制轉(zhuǎn)換函數(shù)(while(num!=0)(push(S,num%n);num/=n;))voidprint(STACKS)//輸出轉(zhuǎn)后的結(jié)果(while(!isEmpty(S))(cout<<S,elements[S.top];++S.top;)cout<<endl;)voidmain()(STACKS;makeNull(S);intnum=1024;intn=2;cout<<"轉(zhuǎn)化前的十進制數(shù)為："<<num<<endl;cout<<"轉(zhuǎn)化后的"<<n<<"進制數(shù)為："；convert(num,S,n);print(S);)九、設(shè)有一個循環(huán)隊列Queue,只有頭指針front,不設(shè)尾指針，另設(shè)一個含有元素個數(shù)的計數(shù)器count，試寫出相應(yīng)的判斷隊列空、判斷隊列滿、出隊算法和入隊算法。要求：1、定義相應(yīng)的循環(huán)隊列的型(只有頭指針，沒有尾指針，但有一個元素個數(shù)的計數(shù)器)；2、定義該隊列的四個算法：判斷隊列空、判斷隊列滿、出隊算法和入隊算法；3、在main函數(shù)驗證算法的正確性?！]有尾指針的隊列，但有一個計數(shù)器，所以尾指針rear可以用頭指針表示出來#include<iostream>usingnamespacestd;#definemaxlength20typedefintelementtype;structQUEUE(elementtypeelements[maxlength];intfront;intcountJ/元素個數(shù)計數(shù)器：rear=(front+count-1)%maxlength);intaddone(inti)//指針后移(return((i+1)%maxlength);)boolisEmpty(QUEUEQ)//隊列是否為空(if(Q.count==0)returntrue;elsereturnfalse;)boolisFull(QUEUEQ)〃隊列是否已滿(if(Q.count==maxlength)returntrue;elsereturnfalse;)elementtypefront(QUEUEQ"/返回隊頭元素(if(isEmpty(Q))returnNULL;elsereturn(Q.elements[Q.front]);)voidenQueue(elementtypex,QUEUE&Q)//隊列后插入一個元素，入隊(if(isFull(Q))cout<<"隊列已滿"<<endl;else(Q.count++;Q.elements[(Q.front+Q.count-1)%maxlength]=x;))voiddeQueue(QUEUE&Q)〃刪除隊頭元素，出隊(if(isEmpty(Q))cout<<"隊列為空"；else(Q.front=addone(Q.front);Q.count--;))voidprint(QUEUEQ)for(intj=0;j<Q.count;j++)cout<<Q.elements[(Q.front+j)%maxlength]<<"\t";cout<<endl;)voidmain()(QUEUEQ;Q.front=0;Q.count=0;for(inti=1;i<10;i++)enQueue(i,Q);cout<<"隊頭："<<front(Q)<<endl;print(Q);for(i=0;i<6;i++)deQueue(Q);cout<<"刪除前六個元素后的隊列："<<endl;print(Q);)十、設(shè)主串T="abcaabbabcabaacbacba“，模式為p="abcabaa”。1、計算模式p的nextval函數(shù)值2、不寫算法，只畫出利用KMP算法進行模式匹配時，每一趟的匹配過程。要求：1、寫出模式p的nextval值；2、畫出KMP算法的每一趟匹配過程(可參照教材P61從第8行開始的內(nèi)容)；3、不需要編寫程序。Nextval：abcabaa0110132第一趟匹配：i=5,j=5abcaabbabcabaacbacbaabcab(匹配失敗)第二趟匹配：i=5,j=1abcaabbabcabaacbacbaabc(匹配失敗)第三趟匹配：i=7,j=1abcaabbabcabaacbacbaa(匹配失敗)第四趟匹配：i=8,j=1Abcaabbabcabaacbacbaabcabaa匹配成功！十一、假設(shè)表達式中允許包含三種括號：圓括號、方括號和大括號。設(shè)計一個算法采用順序棧(用數(shù)組表示的棧)判斷表達式中的括號是否正確配對。要求：1、定義棧以及棧的型，棧中所存放元素的類型為字符型，定義枚舉類型Boolean，其中兩個元素分別為TRUE和FALSE。2、定義棧的各種操作。3、定義函數(shù)Booleancheck(char*s);判斷s中的括號是否正確配對，如果正確配對，返回TRUE，否則返回FALSEo4、在主函數(shù)中驗證所編寫函數(shù)的正確性?！５臄?shù)組實現(xiàn)〃此處將棧底規(guī)定在數(shù)組的底部，即讓maxlength-1指向棧底的第一個元素#include<iostream>usingnamespacestd;#definemaxlength100〃棧的容量//typedefintElementtypel/數(shù)制轉(zhuǎn)換中元素類型為inttypedefcharElementtype;/^號匹配中元素類型為字符型charenumBoolean{TRUE,FALSE};structSTACK//定義整型線性數(shù)組棧{inttop;Elementtypeelements[maxlength];};boolisEmpty(STACKS)//棧是否為空{(diào)if(S.top>=maxlength)returntrue;elsereturnfalse;}voidmakeNull(STACK&S)//棧置空{(diào)S.top=maxlength;}Elementtypetop(STACKS)//返回棧頂元素if(isEmpty(S))returnNULL;elsereturn(S.elements[S.top]);)voidpop(STACK&S)//出棧,刪除棧頂元素(if(isEmpty(S))cout<<"棧為空！"<<endl;elseS.top++;)voidpush(STACK&S,Elementtypex)/進棧(if(S.top==0)8a<<"棧已滿！"<<endl;else(--S.top;S.elements[S.top]=x;))〃==================================數(shù)制轉(zhuǎn)換voidconvert(intnum,STACK&S,intn)/進制轉(zhuǎn)換函數(shù)(while(num!=0)(push(S,num%n);num/=n;))voidprint(STACKS)//輸出轉(zhuǎn)后的結(jié)果(while(!isEmpty(S))(cout<<S,elements[S.top];++S.top;)cout<<endl;//=================================括號匹配Booleancheck(char*s)(STACKS;makeNull(S);intj=0;while(s[j]!='\0')(switch(s[j])(case'(':push(S,'(');break;case')':if(top(S)=='(')pop(S);elsereturnFALSE;break;case'[':push(S,'[');break;case']':if(top(S)=='[')pop(S);elsereturnFALSE;break;case'{':push(S,'{');break;case'}':if(top(S)=='{')pop(S);elsereturnFALSE;break;}j++;}if(isEmpty(S))returnTRUE;elsereturnFALSE;)voidmain(){/*STACKS;makeNull(S);intnum=1024;intn=2;cout<<"轉(zhuǎn)化前的十進制數(shù)為："<<num<<endl;cout<<"轉(zhuǎn)化后的"<<n<<"進制數(shù)為："；convert(num,S,n);print(S);*/char*s="{((ab)b[cf])}";char*p="{{(sd)asdf{}]”;if(check(s)==TRUE)cout<<"{((ab)b[cf])}括號匹配！"<<endl;elsecout<<"{((ab)b[cf])}括號不匹配！"<<endl;if(check(p)==TRUE)cout<<"{{(sd)asdf{}]括號匹配！"<<endl;elsecout<<"{{(sd)asdf{}]括號不匹配！"<<endl;}十二、設(shè)有一個帶頭結(jié)點的雙向鏈表h,設(shè)計一個算法用于查找第一個元素之為x的結(jié)點，并將其與其前驅(qū)結(jié)點進行交換。要求：1、定義帶頭結(jié)點的雙向鏈表的型DLISTo2、定義雙向鏈表DLIST的基本操作。3、定義函數(shù)intswap(elementtypex,DLIST&h)，查找第一個元素之為x的結(jié)點，如果在鏈表中存在元素值為x的結(jié)點，并其與其前驅(qū)結(jié)點進行交換，并返回1,否則返回0o4、在主函數(shù)中測試所編寫函數(shù)的正確性?！◣ь^結(jié)點的雙向鏈表h,設(shè)計一個算法用于查找第一個元素之為x的結(jié)點，并將其與其前驅(qū)結(jié)點進行交換。#include<iostream>usingnamespacestd;typedefintElementtype;structcelltype{ElementtypeelementJ/數(shù)據(jù)域celltype*previous,*next;//前驅(qū)和后驅(qū));typedefcelltype"positionJ/位置的型typedefcelltype*DLIST;//雙向鏈表的型〃插入元素，在p后面插入voidinsert(positionp,Elementtypex)(if(p->next){positionq=newcelltype;q->element=x;q->next=p->next;q->previous=p;p->next->previous=q;p->next=q;)else{positionq=newcelltype;q->element=x;q->next=p->next;q->previous=p;p->next=q;))〃刪除中間結(jié)點voidDelete(positionp){if(p->next!=NULL&&p->previous!=NULL)〃刪除的不是頭尾結(jié)點{p->previous->next=p->next;p->next->previous=p->previous;deletep;)elsecout<<"不能刪除頭尾結(jié)點！"<<endl;)voidcreate(DLIST&head)//創(chuàng)建雙向鏈表{head->previous=NULL;//讓頭結(jié)點的前驅(qū)指向自己head->next=NULL;positionp=head;intx=0,i=1;while(1){cout<<"請輸入第"<<1++<<"個插入的元素(輸入-1結(jié)束創(chuàng)建)："<<endl;cin>>x;if(x!=-1){insert(p,x);p=p->next;)elsebreak;))voidprint(DLISThead)//輸出鏈表元素{positiontemp=head;while(temp->next){temp=temp->next;cout<<temp->element<<'\t';)cout<<endl;)intswap(Elementtypex,DLIST&head)//查找交換{positiontemp,L;temp=head;while(temp->next){temp=temp->next;if(temp->element==x&&temp->previous!=head)//元素匹配并且前驅(qū)不能是頭結(jié)點{L=temp->previous;L->previous->next=temp;temp->previous=L->previous;L->next=temp->next;temp->next->previous=L;L->previous=temp;temp->next=L;return1;))return0;voidmain()(DLISThead=newcelltype;create(head);print(head);Elementtypex;cout<<"請輸入你想查找的元素："<<endl;cin>>x;if(swap(x,head))(cout<<"查找交換成功！"<<endl;print(head);)elsecout<<"查找失??！"<<endl;)十三、試編寫一個求三元組順序表示的稀疏矩陣對角線元素之和的算法十四、當具有相同行值和列值的稀疏矩陣A和B均以三元組順序表方式存儲時，試寫出矩陣相加的算法，其結(jié)果存放在以行邏輯鏈接順序表方式存儲的矩陣C中。十三，十四算法分析：矩陣相加就是將兩個矩陣中同一位置的元素值相加。由于兩個稀疏矩陣的非零元素按三元組表形式存放，在建立新的三元組表C時，為了使三元組元素仍按行優(yōu)先排列，所以每次插入的三元組不一定是A的，按照矩陣元素的行列去找A中的三元組，若有，則加入C，同時，這個元素如果在B中也有，則加上B的這個元素值，否則這個值就不變;如果A中沒有，則找B，有則插入C，無則查找下一個矩陣元素?！ㄈM表示的稀疏矩陣對角線元素相加，以及稀疏矩陣相加#include<iostream>usingnamespacestd;#defineNumVertices6/稀疏矩陣非零元素個數(shù)structnode{introwJ/行intcol;〃列intdata;//值);typedefnodetripleJ/三元組voidInput(triple2[])//輸入三元組(cout<<”請輸入系數(shù)矩陣的行、列數(shù)和非零元素個數(shù)："<<endl;cin>>a[0].row>>a[0].col>>a[0].data;if(a[0].row!=a[0].col)cout<<"請注意您輸入的系數(shù)矩陣不是n階矩陣，無法求對角元素的和！"<<endl;for(inti=1;i<=a[0].data;i++)(cout<<"請以按行優(yōu)先的規(guī)則依次輸入第<々<<個非零元素的下標和值："<<endl;cin>>a[i].row>>a[i].col>>a[i].data;))voidInit(triplea[])//初始化三元祖(a[0].row=4;a[0].col=4;a[0].data=6;a[1].row=0;a[1].col=0;a[1].data=50;a[2].row=1;a[2].col=0;a[2].data=10;a[3].row=1;a[3].col=2;a[3].data=20;a[4].row=3;a[4].col=0;a[4].data=-30;a[5].row=3;a[5].col=2;a[5].data=-60;a[6].row=3;a[6].col=3;a[6].data=5;)intFind(triplea[],introw,intcoly/判斷三元組A所標示的稀疏矩陣是否存在下標[row][col]的非零元素，存在的話返回該非零元素(for(inti=1;i<=a[0].data;i++){if(a[i].row==row&&a[i].col==col)returna[i].data;)return0;)intSum(triplea[])//求對角矩陣對角元素的和{inti,sum=0;if(a[0].row!=a[0].col)cout<<"此稀疏矩陣不是n*n矩陣，無法求對角元素和"<<endl;elsefor(i=1;i<=a[0].data;i++)if(a[i].row==a[i].col11a[i].row+a[i].col==a[0].row-1)sum+=a[i].data;returnsum;)voidPrint(triple*a)//輸出三元組(for(intj=0;j<=a[0].data;j++)cout<<a[j].row<<'\t'<<a[j].col<<'\t'<<a[j].data<<endl;)voidPrintMT(triple*a)//輸出三元組所表示的稀疏矩陣(fo