數(shù)據(jù)結(jié)構(gòu)與算法課后習(xí)題答案(已修改)

　

【正文】 課后習(xí)題解答 判斷題1．線性表的邏輯順序與存儲(chǔ)順序總是一致的。（）2．順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。（√）3．順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰苿?dòng)。（）4．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此屬于同一數(shù)據(jù)對(duì)象。（√）5．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。（）6．在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（√）7．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（）8．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。（√）9．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中數(shù)據(jù)元素的。（√）10．在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。（）11．靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。（）12．線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（） 算法設(shè)計(jì)題1．設(shè)線性表存放在向量A[arrsize]的前elenum個(gè)分量中，且遞增有序。試寫(xiě)一算法，將x 插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度。【提示】直接用題目中所給定的數(shù)據(jù)結(jié)構(gòu)（順序存儲(chǔ)的思想是用物理上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長(zhǎng)度的變量封裝成一個(gè)結(jié)構(gòu)體），因?yàn)槭琼樞虼鎯?chǔ)，分配的存儲(chǔ)空間是固定大小的，所以首先確定是否還有存儲(chǔ)空間，若有，則根據(jù)原線性表中元素的有序性，來(lái)確定插入元素的插入位置，后面的元素為它讓出位置，（也可以從高下標(biāo)端開(kāi)始一邊比較，一邊移位）然后插入x ，最后修改表示表長(zhǎng)的變量。int insert (datatype A[],int *elenum,datatype x) /*設(shè)elenum為表的最大下標(biāo)*/{if (*elenum==arrsize1) return 0。 /*表已滿，無(wú)法插入*/else {i=*elenum。 while (i=0 amp。amp。 A[i]x) /*邊找位置邊移動(dòng)*/{A[i+1]=A[i]。i。} A[i+1]=x。 /*找到的位置是插入位的下一位*/ (*elenum)++。return 1。 /*插入成功*/}}時(shí)間復(fù)雜度為O(n)。2．已知一順序表A，其元素值非遞減有序排列，編寫(xiě)一個(gè)算法刪除順序表中多余的值相同的元素。【提示】對(duì)順序表A，從第一個(gè)元素開(kāi)始，查找其后與之值相同的所有元素，將它們刪除；再對(duì)第二個(gè)元素做同樣處理，依此類推。void delete(Seqlist *A){i=0。while(iAlast) /*將第i個(gè)元素以后與其值相同的元素刪除*/ {k=i+1。 while(k=Alastamp。amp。Adata[i]==Adata[k]) k++。 /*使k指向第一個(gè)與A[i]不同的元素*/ n=ki1。 /*n表示要?jiǎng)h除元素的個(gè)數(shù)*/ for(j=k。j=Alast。j++) Adata[jn]=Adata[j]。 /*刪除多余元素*/ Alast= Alast n。 i++。 }}3．寫(xiě)一個(gè)算法，從一個(gè)給定的順序表A中刪除值在x~y(x=y)之間的所有元素，要求以較高的效率來(lái)實(shí)現(xiàn)。【提示】對(duì)順序表A，從前向后依次判斷當(dāng)前元素Adata[i]是否介于x和y之間，若是，并不立即刪除，而是用n記錄刪除時(shí)應(yīng)前移元素的位移量；若不是，則將Adata[i]向前移動(dòng)n位。n用來(lái)記錄當(dāng)前已刪除元素的個(gè)數(shù)。void delete(Seqlist *A,int x,int y) {i=0。n=0。while (iAlast) {if (Adata[i]=x amp。amp。 Adata[i]=y) n++。 /*若Adata[i] 介于x和y之間，n自增*/ else Adata[in]=Adata[i]。 /*否則向前移動(dòng)Adata[i]*/ i++。 }Alast=n。 }4．線性表中有n個(gè)元素，每個(gè)元素是一個(gè)字符，現(xiàn)存于向量R[n]中，試寫(xiě)一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來(lái)的存儲(chǔ)空間，元素移動(dòng)次數(shù)最小。【提示】對(duì)線性表進(jìn)行兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(shù)字放在字母之后，其它字符之前。int fch(char c) /*判斷c是否字母*/{if(c=39。a39。amp。amp。c=39。z39。||c=39。A39。amp。amp。c=39。Z39。) return (1)。else return (0)。 }int fnum(char c) /*判斷c是否數(shù)字*/{if(c=39。039。amp。amp。c=39。939。) return (1)。 else return (0)。 }void process(char R[n]){low=0。high=n1。while(lowhigh) /*將字母放在前面*/ {while(lowhighamp。amp。fch(R[low])) low++。while(lowhighamp。amp。!fch(R[high])) high。if(lowhigh){k=R[low]。R[low]=R[high]。R[high]=k。} }low=low+1。 high=n1。while(lowhigh) /*將數(shù)字放在字母后面，其它字符前面*/ {while(lowhighamp。amp。fnum(R[low])) low++。 while(lowhighamp。amp。!fnum(R[high])) high。 if(lowhigh) {k=R[low]。R[low]=R[high]。R[high]=k。} }}5．線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換。即將線性表：（a1, a2, … , am, b1, b2, … , bn）改變?yōu)椋海╞1, b2, … , bn , a1, a2, … , am）。【提示】比較m和n的大小，若mn，則將表中元素依次前移m次；否則,將表中元素依次后移n次。void process(Seqlist *L,int m,int n) {if(m=n) for(i=1。i=m。i++) {x=Ldata[0]。 for(k=1。k=Llast。k++) Ldata[k1]=Ldata[k]。 Ldata[Llast]=x。 } else for(i=1。i=n。i++) {x=Ldata[Llast]。 for(k=Llast1。k=0。k ) Ldata[k+1]=Ldata[k]。 Ldata[0]=x。 }}6．已知帶頭結(jié)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫(xiě)一算法，將值為x 的結(jié)點(diǎn)插入到表L中，使得L仍然遞增有序，并且分析算法的時(shí)間復(fù)雜度。LinkList insert(LinkList L, int x) {p=L。 while(pnext amp。amp。 xpnextdata) p=pnext。 /*尋找插入位置*/ s=(LNode *)malloc(sizeof(LNode))。 /*申請(qǐng)結(jié)點(diǎn)空間*/ sdata=x。 /*填裝結(jié)點(diǎn)*/ snext=pnext。 pnext=s。 /*將結(jié)點(diǎn)插入到鏈表中*/ return(L)。} 7．假設(shè)有兩個(gè)已排序（遞增）的單鏈表A和B，編寫(xiě)算法將它們合并成一個(gè)鏈表C而不改變其排序性。LinkList Combine(LinkList A, LinkList B){C=A。rc=C。pa=Anext。 /*pa指向表A的第一個(gè)結(jié)點(diǎn)*/pb=Bnext。 /*pb指向表B的第一個(gè)結(jié)點(diǎn)*/free(B)。 /*釋放B的頭結(jié)點(diǎn)*/while (pa amp。amp。 pb) /*將pa、pb所指向結(jié)點(diǎn)中，值較小的一個(gè)插入到鏈表C的表尾*/ if(padatapbdata) {rcnext=pa。rc=pa。pa=panext。}else{rcnext=pb。rc=pb。pb=pbnext。}if(pa) rcnext=pa。 else rcnext=pb。 /*將鏈表A或B中剩余的部分鏈接到鏈表C的表尾*/return(C)。 }8．假設(shè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，p為指向該鏈表中某一結(jié)點(diǎn)的指針，編寫(xiě)算法刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。【提示】利用循環(huán)單鏈表的特點(diǎn)，通過(guò)s指針可循環(huán)找到其前驅(qū)結(jié)點(diǎn)p及p的前驅(qū)結(jié)點(diǎn)q，然后可刪除結(jié)點(diǎn)*p。viod delepre(LNode *s){LNode *p, *q。p=s。while (pnext!=s){q=p。 p=pnext。}qnext=s。free(p)。}9．已知兩個(gè)單鏈表A和B分別表示兩個(gè)集合，其元素遞增排列，編寫(xiě)算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲(chǔ)。【提示】交集指的是兩個(gè)單鏈表的元素值相同的結(jié)點(diǎn)的集合，為了操作方便，先讓單鏈表C帶有一個(gè)頭結(jié)點(diǎn)，最后將其刪除掉。算法中指針p用來(lái)指向A中的當(dāng)前結(jié)點(diǎn)，指針q用來(lái)指向B中的當(dāng)前結(jié)點(diǎn)，將其值進(jìn)行比較，兩者相等時(shí)，屬于交集中的一個(gè)元素，兩者不等時(shí)，將其較小者跳過(guò)，繼續(xù)后面的比較。LinkList Intersect(LinkList A, LinkList B){LNode *q, *p, *r, *s。 LinkList C。C= (LNode *)malloc(sizeof(LNode))。Cnext=NULL。r=C。p=A。 q=B。while (p amp。amp。 q ) if (pdataqdata) p=pnext。 else if (pdata==qdata) {s=(LNode *)malloc(sizeof(LNode))。 sdata=pdata。 rnext=s。 r=s。 p=pnext。 q=qnext。 }else q=qnext。rnext=NULL。 C=Cnext。 return C。}10．設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next域外，還有一個(gè)訪問(wèn)頻度f(wàn)req域，在鏈表被起用之前，該域的值初始化為零。每當(dāng)在鏈表進(jìn)行一次Locata(L,x)運(yùn)算后，令值為x的結(jié)點(diǎn)中的freq域增1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的非遞增序列排列，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一個(gè)滿足上述要求的Locata(L,x)算法。【提示】在定位操作的同時(shí)，需要調(diào)整鏈表中結(jié)點(diǎn)的次序：每次進(jìn)行定位操作后，要查看所查找結(jié)點(diǎn)的freq域，將其同前面結(jié)點(diǎn)的freq域進(jìn)行比較，同時(shí)進(jìn)行結(jié)點(diǎn)次序的調(diào)整。typedef struct dnode{datatype data。 int freq。 struct DLnode *prior,*next。}DLnode,*DLinkList。DlinkList Locate(DLinkList L, datatype x){p=Lnext。while(pamp。amp。pdata!=x) p=pnext。 /*查找值為x的結(jié)點(diǎn)，使p指向它*/if(!p) return(NULL)。 /*若查找失敗，返回空指針*/pfreq++。 /*修改p的freq域*/while(pprior!=Lamp。amp。ppriorfreqpfreq) /*調(diào)整結(jié)點(diǎn)的次序*/ {k=ppriordata。ppriordata=pdata。pdata=k。k=ppriorfreq。ppriorfreq=pfreq。pfreq=k。p=pprior。 } return(p)。 /*返回找到的結(jié)點(diǎn)的地址*/} 課后習(xí)題解答 選擇題1．向一個(gè)棧頂指針為Top的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，其操作步驟為（C）。 A．Topnext=p。 B．pnext=Topnext。Topnext=p。 C．pnext=Top。Top=p。 D．pnext=Top。Top=Topnext。2．對(duì)于棧操作數(shù)據(jù)的原則是（B）。A．先進(jìn)先出 B．后進(jìn)先出 C．