計(jì)算機(jī)軟件技術(shù)基礎(chǔ)習(xí)題一解答-文庫(kù)吧在線文庫(kù)
【正文】 。如果采用鏈接存儲(chǔ)表示，一個(gè)表的存儲(chǔ)空間可以連續(xù)，可以不連續(xù)。 /*數(shù)據(jù)域：整型*/ struct mynode *next。 while(p != NULL){ len++。 /*表未初始化，或?yàn)榭毡?/ p = Lnext。試將該線性鏈表分解為兩個(gè)線性鏈表，其中一鏈表中的結(jié)點(diǎn)值均為負(fù)整數(shù)，而另一鏈表中結(jié)點(diǎn)的值均為正整數(shù)，并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn)。 /*L為空指針或L為空表*/p = Lnext。 /*記錄當(dāng)前結(jié)點(diǎn)的后繼，以便刪除當(dāng)前結(jié)點(diǎn)*/ free(p)。【解答】void linklistMerge(linklisttype *LA,linklisttype *LB ){/*合并有序鏈表LA與LB,結(jié)果存入LA中，并釋放LB的頭結(jié)點(diǎn) */ linklisttype *pa, *pb , *pre ,*pn。amp。 free(LB)。while (pa != NULL amp。LCnext = pb。LCnext = pb。 p = CLnext。}, 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 135426：若借助?？捎奢斎胄蛄?, 2, 3, …, n得到一個(gè)輸出序列p1, p2, p3, …, pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i j k，使得pj pk pi。兩個(gè)棧均從兩端向中間增長(zhǎng)。 else retrun(DStop1 = MAXSIZE)。}刪除算法elemtype PushDoubleStack(DoubleStack * DS,int StackNo){/*從StackNo棧中刪除并返回一個(gè)元素，若?？眨瑒t返回NULL*/ if(DoubleStackEmpty(DS,StackNo)) return(NULL)。 //棧滿，做溢出處理 Stop ++。 //刪去原數(shù)組 MAXSIZE *= 3。 運(yùn)算符 。前者將連續(xù)退出位于棧頂?shù)倪\(yùn)算符，直到遇到“(”為止。 39。 39。 a x * 5 b操作數(shù)F 直接輸出, 讀下一符號(hào)。 / 39。 ) icp ( 39。 39。 a x * b x 2^/ F 結(jié)束（序號(hào)從1到70），經(jīng)過(guò)一系列入隊(duì)和退隊(duì)運(yùn)算后，有：（1）front=15，rear=46；（2）front=45，rear=10問(wèn)在上述兩種情況下，循環(huán)隊(duì)列中各有多少個(gè)元素？【解答】(1) 隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rearfront) %MAXSIZE = (70+4615)%70=31(2) 隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rearfront) %MAXSIZE = (70+1045)%70=35，要求可在表的兩端插入，但限制只能在表的一端刪除。 if(Qrear==Qfront) Qrear = p。 x = pdata。算法如下：int palindrome (string S) {stacktype * st。 break。B[j*(j+1)/2+i]，對(duì)所有的ij.(str,str1,str2)，將主串str中所有子串str1替換為str2。 else if ( s e ) return 1。 /*掃描字符串，所有字符進(jìn)棧*/} i = 0。}，是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。}}elemtype deletequeue(queuetype *Q){ elemtype x。p=(node *)malloc(sizeof(node))。 ) icp ( 39。 /a x * b x 2^ F isp ( 39。 /^a x * b x 9 2操作數(shù)F 直接輸出, 讀下一符號(hào)。/39。 39。 *A 3 x操作數(shù)F 直接輸出, 讀下一符號(hào)。 進(jìn)棧, 讀下一符號(hào)。其它運(yùn)算符進(jìn)入棧中后優(yōu)先數(shù)都升1，這樣可體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級(jí)的運(yùn)算符自左向右計(jì)算的要求。(2) 同上。 //創(chuàng)建體積大二倍的數(shù)組 for ( int i = 0。 return(DSdata[DStop11])。 DSdata[top0]=x。【解答】bot[0] top[0] top[1] bot[1] 雙棧的類型定義如下：typedef struct{ int top0,top1。此時(shí)具有中間值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj pi pk, 不可能出現(xiàn)pj pk pi的情形；④ i進(jìn)棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧，i出棧。 (2) 不能得到435612和154623這樣的出棧序列。 p = pnext。}，并將該結(jié)點(diǎn)移到第一個(gè)結(jié)點(diǎn)之前。LCnext = pa。LCnext = pa?！窘獯稹縇inklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB ){/*合并有序鏈表LA與LB,結(jié)果存入LC中，并釋放LA、LB的頭結(jié)點(diǎn) ,函數(shù)返回LC*/ linklisttype *pa, *pb , *p。pb = pn。 retrun。 free(L)。}elseif(pdata 0){ /*將p鏈入鏈表LB的pb后*/ pbnext = p。pa = LA。 /*當(dāng)前結(jié)點(diǎn)的后繼改為指向其原來(lái)的前驅(qū)*/ pre = p , p=next。試設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。 int len。 (3) 應(yīng)采用順序存儲(chǔ)表示。如果采用順序存儲(chǔ)表示，必須在一個(gè)連續(xù)的可用空間中為這n個(gè)表分配空間。試問(wèn)： (1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)? (2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用哪種存儲(chǔ)表示？為什么？ (3) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？【解答】(1) 順序存儲(chǔ)表示是將數(shù)據(jù)元素存放于一個(gè)連續(xù)的存儲(chǔ)空間中，實(shí)現(xiàn)順序存取或(按下標(biāo))直接存取。 tmp = Ldata[i]。} LClength = k。} while( i LAlength){ /*當(dāng)LA表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/LCdata[k] = value1。amp。 int i,j,k。 i + j Llength。 /*表長(zhǎng)減1*
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1