【正文】 =s。L){ DuLNode *p。pnextnext!=L){ pnext=pnextnext。 p=pnext。 for(p=L。}，每個結(jié)點除有prior、data和next三個域外，還有一個訪問頻度域frep。L,int x){ DuLNode *p=Lnext,*q。 if(p){ pfrep++。q!=L) q=qprior。pnext=qnext。解：棧是只能在一端進行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最先入隊的元素最先刪除，故隊列也稱先進先出表。在循環(huán)隊列下，通常采用“犧牲一個存儲空間”的方法解決“隊滿”和“隊空”的判定問題。：若借助棧由輸入序列1，2，…，得到序列，…，(它是輸入序列的一個全排列)，則在輸出序列中不可能出現(xiàn)下列情形：存在著，使得。，函數(shù)內(nèi)定義的局部變量在函數(shù)的2次調(diào)用期間是否占用同一數(shù)據(jù)區(qū)？為什么？解：函數(shù)遞歸調(diào)用自身時，函數(shù)內(nèi)定義的局部變量在函數(shù)的2次調(diào)用期間不占用同一數(shù)據(jù)區(qū)。typedef struct{ElemType *elem。（1）初始狀態(tài): ==0。解：既不能由輸入受限的雙端隊列得到，又不能由輸出受限的雙端隊列得到的輸出序列是：4，2，3，1。 while(!StackEmpty(S)){n++。i=n。InitStack(T)。Push(S,d)。InitStack(T)。EnQueue(Q,d)。，識別依次讀入的一個以為結(jié)束符的字符序列是否為形如“序列1amp。amp。39。 while((c=getchar())!=39。 while((c=getchar())!=39。 if(x!=c)return 0。解：typedef char SS[MAX]。表示硬席,39。 p=train。H39。存入棧中 else *(q++)=*p。 } while(!StackEmpty(s)){ Pop(s,c)。接在后部 }}，并消除遞歸：解：int F_recursive(int n,int amp。 s=n*s。}node。}SqStack。 if(n0) exit(0)。=n/2。 while(!StackEmpty(T)){ Pop(T,t)。sum){ int x。 else{test(sum)。 scanf(%d,amp。x)。}}。 else if(a[n1]MaxValue(a,n1))max=a[n1]。解：(1)void InitQueue(CirLinkList amp。rear, ElemType x){ LNode *s。 rearnext=s。x){ LNode *s。//s指向隊頭元素 rearnextnext=snext。}“回文”，試寫一個算法判別讀入的一個億為結(jié)束符的字符序列是否是“回文”。 ElemType a,b。39。 DeQueue(Q,b)。解：void process(LinkList amp。 p=Lnext。} while (!StackEmpty(s)){Pop(s,x)。//動態(tài)分配存儲空間 int length。Q,ElemType x){ //帶length域的循環(huán)隊列入隊算法 if(==MAX)return ERROR。 return OK。 if(==0)return ERROR。 return OK。 =0。解：串是有限的字符序列，從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)?？崭翊怯煽崭窠M成的串，其長度等于空格的個數(shù)。解：串可看作由以下兩部分組成：和，設(shè)這兩部分分別叫串s1和s2，要設(shè)法從、中得到這兩部分，然后使用連接操作連接s1和s2得到。//求串在串中的起始位置，串中后是s2=substr(,j+3,length()j2)。算法從左到右掃描字符串S1，找到第一個非空格字符，計數(shù)到n，第n個拷入字符串S2的字符不能為空格，然后將余下字符復(fù)制到字符串S3中。\039。 39。){printf(字符串S1為空串或空格串\n)。amp。p++。){printf(字符串S1沒有%d個有效字符\n,n)。){//若最后一個字符為空格，則需要向后找到第一個非空格字符 p。amp。//往后查找一個非空格字符作為串S2的尾字符 if(*p== 39。} *q=*p。p++。q++。//置串S3結(jié)束標記}，編寫算法，求串的含不同字符的總數(shù)和每個字符的個數(shù)。void StrAnalyze(SString S){//統(tǒng)計串S中字符的種類和個數(shù) int i,j。i=S[0]+1。i=S[0]。amp。T[j].num=1。}//StrAnalyze，編寫算法，從串中刪除所有和串相同的子串。 for(i=1。amp。k=s[0]t[0]。 } }//for}//Delete_SubString，實現(xiàn)堆存儲結(jié)構(gòu)的串的置換操作Replace(amp。 num){//堆結(jié)構(gòu)串上的置換操作,返回置換次數(shù) int i,j,k,m。kamp。 if(k==) { //找到了與T匹配的子串:分三種情況處理 if(==) for(m=1。m=i+。m++)[i+m]=[m]。 for(m=0。 i+=。解：void HString_Concat(HString s1,HString s2,HString amp。 for(i=1。j=。解：int LString_Palindrome(LString L) {//判斷以塊鏈結(jié)構(gòu)存儲的串L是否為回文序列,是則返回1,否則返回0 InitStack(S)。 //i指示元素在塊中的下標,k指示元素在整個序列中的序號(從1開始) for(k=1。 //將后半段的字符與棧中的元素相匹配 if(pch[i]!=c) return 0。 //成功匹配}//LString_Palindrome，試分別求出它們的next函數(shù)值和nextval函數(shù)值。已知A的基地址為1000，計算：(1)數(shù)組A共占用多少存儲單元；(2)數(shù)組A的最后一個元素的地址；(3)按行存儲時元素A53的地址；(4)按列存儲時元素A53的地址。(4) 按列存儲時元素A53的地址d53=1000+（4*7+2）*6=1180，同時又是第j列中的最大值，則稱此元素為該矩陣中的一個馬鞍點。im。 //求一行中的最小值 for(j=0。k++) if(minA[k][j]) flag=0。解：假設(shè)數(shù)組B的下標從1開始則：u=ij+2, v=j。解：void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix amp。 pa=1。x=。amp。 [pc].e=ce。 } }//if else if([pa].j[pb].j) { [pc].i=x。pc++。pc++。pc++。 pb++。解：void OLMatrix_Add(OLMatrix amp。 //向量cp存儲每一列當(dāng)前最后一個元素的指針 for(i=1。pre=NULL。 pright=pa。pe=pbe。 pdown=cp[pj]down。 pa=paright。 pb=pbright。pa=paright。 }//else }//while }//for}//OLMatrix_Add：(1)GetHead((a,b),(c,d))(2)GetTail(a,b,(c,d))(3)GetHead(GetTail((a,b),(c,d)))(4)GetTail(GetHead(a,b,(c,d)))(5)GetTail(GetHead(GetTail(a,(b,(c,d)))))解：(1) (a,b)； (2) (b,(c,d))； (3) (c,d)；(4) NULL；(5) ((c,d))。(3) GetHead(GetHead(GetTail(a,(b,(c,d)))))。操作結(jié)果: 取廣義表L的頭 GList h。!L){ printf(空表無表頭!)。 htag=Ltag。 return h。 return NULL。 T=NULL。解：int CopyGList(Glist amp。 if(Ltag==ATOM)Tatom=Latom。} CopyGList習(xí)題6？解：樹與二叉樹邏輯上都是樹形結(jié)構(gòu)，區(qū)別有三點：（1）二叉樹的度至多為2，樹無此限制。？至多有多少個結(jié)點？解：至少有個結(jié)點，至多有個結(jié)點。[1..n]是一棵順序存儲的完全二叉樹，如何求出A[i]和A[j]的最近的共同祖先？解：根據(jù)順序存儲的完全二叉樹的性質(zhì)，編號為i的結(jié)點的雙親的編號為235。退出while后，若i/2=0，則最近共同祖先為根結(jié)點，否則共同祖先為i/2。這是最后一個分支結(jié)點，在它之后是第一個葉子結(jié)點，故序號最小的葉子結(jié)點的下標是235。(2)因為該樹上每層上均有kh1個結(jié)點，從根開始編號為1，則結(jié)點i的從右向左數(shù)第2個孩子的結(jié)點編號為ki。(3)結(jié)點(n1)的前一結(jié)點編號為n1（其最右邊子女編號是(n1)*k+1），故結(jié)點n的第i個孩子的編號是(n1)*k+1+i。除根結(jié)點外，其余n1個結(jié)點均有指針所指，故空指針數(shù)為n*m(n1)=n*(m1)+1。(3)若先序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹。解：按層次遍歷，第一個結(jié)點（樹不空）為根，該結(jié)點在中序序列中把序列分成左右兩部分——左子樹和右子樹。：ABCDEFGHIJKL。(1)試畫出該二叉樹；(2)試畫出該二叉樹的中序線索樹；(3)試畫出該二叉樹對應(yīng)的森林。其哈夫曼樹為：，寫出計算該算術(shù)表達式值的算法。//只取+、*、/ struct Node *lchild,*rchild }BiNode,*BiTree。// switch(toptr){ case 39。 case 39。 case 39。 case 39。 } }return value。 if(t1==NULLamp。 else{ like1=Like(t1lchild,t2lchild)。 }}，編寫遞歸算法，將二叉樹中所有結(jié)點的左、右子樹相互交換。tlchild=trchild。}}。i++){ temp=0。} if(tempmaxdepth)maxdepth=temp。 LinkQueue Q。 while(!QueueEmpty(Q)){ DeQueue(Q,p)。 }//while }//if return num。//中序遍歷左子樹 if(tlchild==NULLamp。 headrchild=t。tlchild=pre。 prerchild=NULL。 if(tlchild!=NULL||trchild!=NULL){ printf(()。 printf())。trchild==NULL)printf(%c ,tdata)。解：int Ancestor(BiTree t,ElemType x){ if(t==NULL)return 0。 }}，編寫算法，輸出所有葉子結(jié)點到根結(jié)點的路徑。//棧指針初始化 if(t){ do{ while(t){ //t的所有左結(jié)點進棧 top++。 //p指向棧頂結(jié)點的前一個已訪問的結(jié)點 flag=1。 //出棧 if(trchild==p){ if(tlchild==NULLamp。i) printf(%c,St[i]data)。//p指向剛訪問過的結(jié)點 } else{ t=trchild。 }}，將二叉樹的順序存儲結(jié)構(gòu)轉(zhuǎn)化為二叉鏈表存儲結(jié)構(gòu)。//左右孩子指針}SqBTree。39。 tlchild=Trans(a,2*i)。解：在后序序列中，若結(jié)點p有右子女，則右子女是其前驅(qū)，若無右子女而有左子女，則左子女是其前驅(qū)。 if(pRTag==0)q=prchild。amp。 //僅右單支樹（p是葉子），已上到根結(jié)點，p結(jié)點無后序前驅(qū) } return q。 if(plchild!=NULLamp。}BiThrTree RightMost(BiThrTree t){//求結(jié)點t的最右子孫的右線索 BiThrTree p=t。prchild!=t)return(prchild)。 if(fatheramp。}void PostOrderInThr(BiThrTree t){/