【正文】 課后習題解答 判斷題1．線性表的邏輯順序與存儲順序總是一致的。（）2．順序存儲的線性表可以按序號隨機存取。（√）3．順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。（）4．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此屬于同一數(shù)據(jù)對象。（√）5．在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。（）6．在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（√）7．線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。（）8．在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時移動元素的個數(shù)與該元素的位置有關(guān)。（√）9．線性表的鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。（√）10．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)。（）11．靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以它存取表中第i個元素的時間與i無關(guān)。（）12．線性表的特點是每個元素都有一個前驅(qū)和一個后繼。（） 算法設(shè)計題1．設(shè)線性表存放在向量A[arrsize]的前elenum個分量中，且遞增有序。試寫一算法，將x 插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度?！咎崾尽恐苯佑妙}目中所給定的數(shù)據(jù)結(jié)構(gòu)（順序存儲的思想是用物理上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長度的變量封裝成一個結(jié)構(gòu)體），因為是順序存儲，分配的存儲空間是固定大小的，所以首先確定是否還有存儲空間，若有，則根據(jù)原線性表中元素的有序性，來確定插入元素的插入位置，后面的元素為它讓出位置，（也可以從高下標端開始一邊比較，一邊移位）然后插入x ，最后修改表示表長的變量。int insert (datatype A[],int *elenum,datatype x) /*設(shè)elenum為表的最大下標*/{if (*elenum==arrsize1) return 0。 /*表已滿，無法插入*/else {i=*elenum。 while (i=0 amp。amp。 A[i]x) /*邊找位置邊移動*/{A[i+1]=A[i]。i。} A[i+1]=x。 /*找到的位置是插入位的下一位*/ (*elenum)++。return 1。 /*插入成功*/}}時間復雜度為O(n)。2．已知一順序表A，其元素值非遞減有序排列，編寫一個算法刪除順序表中多余的值相同的元素?！咎崾尽繉樞虮鞟，從第一個元素開始，查找其后與之值相同的所有元素，將它們刪除；再對第二個元素做同樣處理，依此類推。void delete(Seqlist *A){i=0。while(iAlast) /*將第i個元素以后與其值相同的元素刪除*/ {k=i+1。 while(k=Alastamp。amp。Adata[i]==Adata[k]) k++。 /*使k指向第一個與A[i]不同的元素*/ n=ki1。 /*n表示要刪除元素的個數(shù)*/ for(j=k。j=Alast。j++) Adata[jn]=Adata[j]。 /*刪除多余元素*/ Alast= Alast n。 i++。 }}3．寫一個算法，從一個給定的順序表A中刪除值在x~y(x=y)之間的所有元素，要求以較高的效率來實現(xiàn)?！咎崾尽繉樞虮鞟，從前向后依次判斷當前元素Adata[i]是否介于x和y之間，若是，并不立即刪除，而是用n記錄刪除時應(yīng)前移元素的位移量；若不是，則將Adata[i]向前移動n位。n用來記錄當前已刪除元素的個數(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]。 /*否則向前移動Adata[i]*/ i++。 }Alast=n。 }4．線性表中有n個元素，每個元素是一個字符，現(xiàn)存于向量R[n]中，試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來的存儲空間，元素移動次數(shù)最小?！咎崾尽繉€性表進行兩次掃描，第一次將所有的字母放在前面，第二次將所有的數(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．線性表用順序存儲，設(shè)計一個算法，用盡可能少的輔助存儲空間將順序表中前m個元素和后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é)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的，試寫一算法，將值為x 的結(jié)點插入到表L中，使得L仍然遞增有序，并且分析算法的時間復雜度。LinkList insert(LinkList L, int x) {p=L。 while(pnext amp。amp。 xpnextdata) p=pnext。 /*尋找插入位置*/ s=(LNode *)malloc(sizeof(LNode))。 /*申請結(jié)點空間*/ sdata=x。 /*填裝結(jié)點*/ snext=pnext。 pnext=s。 /*將結(jié)點插入到鏈表中*/ return(L)。} 7．假設(shè)有兩個已排序（遞增）的單鏈表A和B，編寫算法將它們合并成一個鏈表C而不改變其排序性。LinkList Combine(LinkList A, LinkList B){C=A。rc=C。pa=Anext。 /*pa指向表A的第一個結(jié)點*/pb=Bnext。 /*pb指向表B的第一個結(jié)點*/free(B)。 /*釋放B的頭結(jié)點*/while (pa amp。amp。 pb) /*將pa、pb所指向結(jié)點中，值較小的一個插入到鏈表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è)長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p為指向該鏈表中某一結(jié)點的指針，編寫算法刪除該結(jié)點的前驅(qū)結(jié)點?！咎崾尽坷醚h(huán)單鏈表的特點，通過s指針可循環(huán)找到其前驅(qū)結(jié)點p及p的前驅(qū)結(jié)點q，然后可刪除結(jié)點*p。viod delepre(LNode *s){LNode *p, *q。p=s。while (pnext!=s){q=p。 p=pnext。}qnext=s。free(p)。}9．已知兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲?！咎崾尽拷患傅氖莾蓚€單鏈表的元素值相同的結(jié)點的集合，為了操作方便，先讓單鏈表C帶有一個頭結(jié)點，最后將其刪除掉。算法中指針p用來指向A中的當前結(jié)點，指針q用來指向B中的當前結(jié)點，將其值進行比較，兩者相等時，屬于交集中的一個元素，兩者不等時，將其較小者跳過，繼續(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è)有一個雙向鏈表，每個結(jié)點中除有prior、data和next域外，還有一個訪問頻度freq域，在鏈表被起用之前，該域的值初始化為零。每當在鏈表進行一次Locata(L,x)運算后，令值為x的結(jié)點中的freq域增1，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的非遞增序列排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一個滿足上述要求的Locata(L,x)算法?！咎崾尽吭诙ㄎ徊僮鞯耐瑫r，需要調(diào)整鏈表中結(jié)點的次序：每次進行定位操作后，要查看所查找結(jié)點的freq域，將其同前面結(jié)點的freq域進行比較，同時進行結(jié)點次序的調(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é)點，使p指向它*/if(!p) return(NULL)。 /*若查找失敗，返回空指針*/pfreq++。 /*修改p的freq域*/while(pprior!=Lamp。amp。ppriorfreqpfreq) /*調(diào)整結(jié)點的次序*/ {k=ppriordata。ppriordata=pdata。pdata=k。k=ppriorfreq。ppriorfreq=pfreq。pfreq=k。p=pprior。 } return(p)。 /*返回找到的結(jié)點的地址*/} 課后習題解答 選擇題1．向一個棧頂指針為Top的鏈棧中插入一個p所指結(jié)點時，其操作步驟為（C）。 A．Topnext=p。 B．pnext=Topnext。Topnext=p。 C．pnext=Top。Top=p。 D．pnext=Top。Top=Topnext。2．對于棧操作數(shù)據(jù)的原則是（B）。A．先進先出 B．后進先出 C．