數(shù)據結構的第4-7習題的答案(編輯修改稿)
2025-07-16 16:39 本頁面
【文章內容簡介】 pop(s,c)。 if(e!=c) return 0。 cine。} if(!StackEmpty(s)) return 0。 return 1。 }//IsReverse 隊列回顧 第六章隊列知識要點： 隊列類型的定義：（ a1,a2,?,an ），只在隊首進行刪除操作，在隊尾進行插入操作，先進先出。 隊列的存儲形式： 鏈式存儲： 順序存儲：循環(huán)隊列 循環(huán)隊列的優(yōu)點是什么？如何判別它的空和滿？ 由于隊列的順序存儲結構中從隊尾入隊、從隊首出隊，可能會造成存儲空間實際未滿，但又數(shù)據元素無法入隊的情況，即虛溢出現(xiàn)象，而循環(huán)隊列將整個隊列看成一個環(huán)，則可以解決虛溢出問題。 對于循環(huán)隊列 Q，其存儲空間大小為 MAXQSIZE，則： 隊空條件： == 隊滿條件： (+1)%MAXQSIZE== 設長度為 n的鏈隊列用循環(huán)單鏈表表示，若只設頭指針，則入列操作、出列操作實現(xiàn)的時間開銷是多少？若只設尾指針呢？ 若只設頭指針：入列、出列操作實現(xiàn)時間開銷分別為 O(n)和 O(1) 若只設尾指針：入列、出列操作實現(xiàn)時間開銷分別為 O(1)和 O(1) 用兩個棧實現(xiàn)一個隊列，并分析你的算法的時間復雜度。 思路：利用棧 S1和 S2模擬一個隊列，其中 S1棧用于插入元素，S2棧用于刪除元素時輔助空間，每次刪除元素時將 S1棧的所有元素出棧并進棧到 S2棧中。算法實現(xiàn)為： Status EnQueue(stack amp。s1,ElemType x) { if(==n1) return 0。 else {Push(s1,x)。 return 1。}} 時間復雜度 T(n)=O(1) Status DeQueue(stack amp。s1,Stack amp。s2,ElemType amp。x) { ElemType y。 While(!StackEmpty(S1)) {Pop(S1,y)。 Push(S2,y)。} Pop(S2,x)。 While(!StackEmpty(S2)) {Pop(S2,y)。 Push(S1,y)。}} 時間復雜度 T(n)=O(n) 簡述下列算法的功能（假設棧和隊列的元素類型均為 int類型）。 Void alg(Queue Q) { stack S。 int e。 InitStack(S)。 while(!QueueEmpty(Q)) {DeQueue(Q,e)。 push(S,e)。} while(!StackEmpty(S)) {Pop(Q,e)。 EnQueue(S,e)。} } 實現(xiàn)功能：將隊列 Q逆置。 串回顧 第七章串知識要點： 串類型的定義：“ a1,a2,?,an” 串的存儲形式： 順序存儲： 堆存儲： 鏈式存儲：塊鏈結構 ： S1 = ”I’m a girl.” ， S2 = ”girl” ，S3 = ” is very nice.” ，試求下列各運算的結果： StrIndex(S1, S2)。 StrLength (S1)。 Concat (S, S2, S3)； 答： StrIndex(S1, S2)=7 StrLength (S1)=11 Concat (S, S2, S3)=” girl is very nice.” 將串的各字符均相同且長度大于 1的子串稱為該串的一個等值子串。試寫算法實現(xiàn)：輸入字符串 S，以 ’ ’ 為結束符；如果串 S中不存在等值子串，則輸出“無等值子串”，否則輸出串 S的一個長度最大的等值子串。如，若 S = “ abc345b6a7c” ，則輸出“無等值子串”；若 S = “ abcaaabbac” ，則輸出 “ aaa” 。 void EqSubString(char s[]) { int i,j,k,head,max,count。 printf(“ 請輸入字符串： ” )。 for(k=0。k++) //輸入串 {scanf(“%c”,amp。s[k])。 if(s[k]==’’) break。} for(i=0,j=1,head=0,max=1。s[i]!=’’amp。amp。s[j]!=’’。i=j,j++) {//找等值子串 count=1。 while(s[i]==s[j]) {j++。count++。} if(countmax) {head=i。 max=count。} } if(max1) { printf(“ 最大等值子串： ” )。 for(k=head。k(head+max)。k++) printf(“%c”,s[k])。 } else printf(“ 無等值子串 !”)。 printf(“/n”)。 } 試編寫一個算法，將兩個字符串 S1和 S2進行比較，若 S1 S2則輸出一個正數(shù)；若 S1 = S2，則輸出 0；若 S1 S2則輸出一個負數(shù)（要求：不允許利用 C的庫函數(shù) strcpy）。 int CmpString(char s1[],char s2[]) { int i=0。 while((s1[i]==s2[i])amp。amp。(s1[i]!=’ \0’)amp。amp。(s2[i]!=’\0’)) i++。 if((s1[i]==’ \0’)amp。amp。( s2[i]==’ \0’)) return 0。 else if (s1[i]==’ \0’
教學教案相關推薦
鄂ICP備17016276號-1