【正文】 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題參考答案第一章 緒論 (1) O(n)(2) (2) O(n)(3) (3) O(n)(4) (4) O(n1/2)(5) (5) 執(zhí)行程序段的過(guò)程中，x,y值變化如下：循環(huán)次數(shù) x y0（初始） 91 1001 92 1002 93 100…… …… ……9 100 10010 101 10011 91 9912 92 100…… …… ……20 101 9921 91 98…… …… ……30 101 9831 91 97 到y(tǒng)=0時(shí)，要執(zhí)行10*100次，可記為O（10*y）=O（n） 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章 線性表(參考答案)在以下習(xí)題解答中，假定使用如下類型定義：（1）順序存儲(chǔ)結(jié)構(gòu)：define MAXSIZE 1024typedef int ElemType。// 實(shí)際上，ElemType可以是任意類型 typedef struct{ ElemType data[MAXSIZE]。int last。 // last表示終端結(jié)點(diǎn)在向量中的位置 }sequenlist。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（單鏈表）typedef struct node{ElemType data。 struct node *next； }linklist。（3）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（雙鏈表）typedef struct node{ElemType data。struct node *prior,*next；}dlinklist。（4）靜態(tài)鏈表typedef struct{ElemType data。int next。}node。node sa[MAXSIZE]。 頭指針：指向鏈表的指針。因?yàn)閷?duì)鏈表的所有操均需從頭指針開(kāi)始，即頭指針具有標(biāo)識(shí)鏈表的作用，所以鏈表的名字往往用頭指針來(lái)標(biāo)識(shí)。如：鏈表的頭指針是la，往往簡(jiǎn)稱為“鏈表la”。頭結(jié)點(diǎn)：為了鏈表操作統(tǒng)一，在鏈表第一元素結(jié)點(diǎn)（稱為首元結(jié)點(diǎn)，或首結(jié)點(diǎn)）之前增加的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，其數(shù)據(jù)域不無(wú)實(shí)際意義（當(dāng)然，也可以存儲(chǔ)鏈表長(zhǎng)度，這只是副產(chǎn)品），其指針域指向頭結(jié)點(diǎn)。這樣在插入和刪除中頭結(jié)點(diǎn)不變。開(kāi)始結(jié)點(diǎn)：即上面所講第一個(gè)元素的結(jié)點(diǎn)。 只設(shè)尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問(wèn)鏈表上的任何結(jié)點(diǎn)。23 void insert(ElemType A[],int elenum,ElemType x)// 向量A目前有elenum個(gè)元素，且遞增有序，本算法將x插入到向量A中，并保持向量的遞增有序。{ int i=0,j。 while (ielenum amp。amp。 A[i]=x) i++。 // 查找插入位置 for (j= elenum1。j=i。j) A[j+1]=A[j]。// 向后移動(dòng)元素 A[i]=x。 // 插入元素 } // 算法結(jié)束24 void rightrotate(ElemType A[],int n,k)// 以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的n個(gè)元素循環(huán)右移k位，且只用一個(gè)輔助空間。{ int num=0。 // 計(jì)數(shù)，最終應(yīng)等于n int start=0。 // 記錄開(kāi)始位置（下標(biāo)） while (numn) { temp=A[start]。 //暫存起點(diǎn)元素值，temp與向量中元素類型相同 empty=start。 //保存空位置下標(biāo) next=(startK+n) %n。 // 計(jì)算下一右移元素的下標(biāo) while (next !=start) { A[empty]=A[next]。// 右移 num++。 // 右移元素?cái)?shù)加1 empty=next。 next=(nextK+n) %n。 // 計(jì)算新右移元素的下標(biāo) } A[empty]=temp。 // 把一輪右移中最后一個(gè)元素放到合適位置 num++。 start++。 // 起點(diǎn)增1，若numn則開(kāi)始下一輪右移。 }} // 算法結(jié)束 算法二 算法思想：先將左面nk個(gè)元素逆置，接著將右面k個(gè)元素逆置，最后再將這n個(gè)元素逆置。void rightrotate(ElemType A[],int n,k)// 以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的n個(gè)元素循環(huán)右移k位，且只用一個(gè)輔助空間。{ ElemType temp。 for(i=0。i(nk)/2。i++) //左面nk個(gè)元素逆置 {temp=A[i]。 A[i]=A[nk1i]。 A[nk1i]=temp。 }for(i=1。i=k。i++) //右面k個(gè)元素逆置 {temp=A[nki]。 A[nki]=A[ni]。 A[ni]=temp。 }for(i=0。in/2。i++) //全部n個(gè)元素逆置 {temp=A[i]。 A[i]=A[n1i]。 A[n1i]=temp。 }} // 算法結(jié)束 25void insert(linklist *L,ElemType x)// 帶頭結(jié)點(diǎn)的單鏈表L遞增有序，本算法將x插入到鏈表中，并保持鏈表的遞增有序。{ linklist *p=Lnext, *pre=L，*s。// p為工作指針，指向當(dāng)前元素，pre為前驅(qū)指針，指向當(dāng)前元素的前驅(qū) s=(linklist *)malloc(sizeof(linklist))。//申請(qǐng)空間，不判斷溢出sdata=x。 while (p amp。amp。 pdata=x) {pre=p。 p=pnext。} // 查找插入位置 prenext=s。 snext=p。 // 插入元素 } // 算法結(jié)束 26void invert(linklist *L)// 本算法將帶頭結(jié)點(diǎn)的單鏈表L逆置。 //算法思想是先將頭結(jié)點(diǎn)從表上摘下，然后從第一個(gè)元素結(jié)點(diǎn)開(kāi)始，依次前插入以L為頭結(jié)點(diǎn)的鏈表中。{ linklist *p=Lnext,*s。// p為工作指針，指向當(dāng)前元素，s為p的后繼指針 Lnext=null。//頭結(jié)點(diǎn)摘下，指針域置空。算法中頭指針L始終不變 while (p) {s=pnext。 // 保留后繼結(jié)點(diǎn)的指針 pnext=Lnext。 // 逆置 Lnext=p。 p=s。 // 將p指向下個(gè)待逆置結(jié)點(diǎn) }} // 算法結(jié)束 27(1) int length1(linklist *L)// 本算法計(jì)算帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度 { linklist *p=Lnext。 int i=0。// p為工作指針，指向當(dāng)前元素，i 表示鏈表的長(zhǎng)度 while (p) { i++。 p=pnext。 } return(i)。} // 算法結(jié)束(2) int length1(node sa[MAXSIZE])// 本算法計(jì)算靜態(tài)鏈表s中元素的個(gè)數(shù)。{ int p=sa[0].next, i=0。// p為工作指針，指向當(dāng)前元素，i 表示元素的個(gè)數(shù)，靜態(tài)鏈指針等于1時(shí)鏈表結(jié)束 while (p！=1) { i++。 p=sa[p].next。 } return(i)。} // 算法結(jié)束 28void union_invert(linklist *A,*B,*C)// A和B是兩個(gè)帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法將兩表合并成 // 一個(gè)帶頭結(jié)點(diǎn)的遞減有序單鏈表C，利用原表空間。{ linklist *pa=Anext,*pb=Bnext,*C=A,*r。// pa,pb為工作指針，分別指向A表和B表的當(dāng)前元素，r為當(dāng)前逆置//元素的后繼指針, 使逆置元素的表避免斷開(kāi)。 //算法思想是邊合并邊逆置，使遞增有序的單鏈表合并為遞減有序的單鏈表。 Cnext=null。//頭結(jié)點(diǎn)摘下，指針域置空。算法中頭指針C始終不變 while (pa amp。amp。 pb) // 兩表均不空時(shí)作 if (padata=pbdata) // 將A表中元素合并且逆置 { r=panext。 // 保留后繼結(jié)點(diǎn)的指針 panext=Cnext。 // 逆置 Cnext=pa。 pa=r。 // 恢復(fù)待逆置結(jié)點(diǎn)的指針 }else // 將B表中元素合并且逆置 { r=pbnext。 // 保留后繼結(jié)點(diǎn)的指針 pbnext=Cnext。 // 逆置 Cnext=pb。 pb=r。 // 恢復(fù)待逆置結(jié)點(diǎn)的指針 } // 以下while (pa)和while (pb)語(yǔ)句，只執(zhí)行一個(gè) while (pa) // 將A表中剩余元素逆置 { r=panext。 // 保留后繼結(jié)點(diǎn)的指針 panext=Cnext。 // 逆置 Cnext=pa。 pa=r。 // 恢復(fù)待逆置結(jié)點(diǎn)的指針 } while (pb) // 將B表中剩余元素逆置 { r=pbnext。 // 保留后繼結(jié)點(diǎn)的指針 pbnext=Cnext。 // 逆置 Cnext=pb。 pb=r。 // 恢復(fù)待逆置結(jié)點(diǎn)的指針 }free(B)。//釋放B表頭結(jié)點(diǎn)} // 算法結(jié)束 29 void deleteprior(linklist *L)// 長(zhǎng)度大于1的單循環(huán)鏈表，既無(wú)頭結(jié)點(diǎn)，也無(wú)頭指針，本算法刪除*s 的前驅(qū)結(jié)點(diǎn){ linklist *p=snext,*pre=s。 // p為工作指針，指向當(dāng)前元素，// pre為前驅(qū)指針，指向當(dāng)前元素*p的前驅(qū) while (pnext!=s) {pre=p。 p=pnext。} // 查找*s的前驅(qū) prenext=s。 free(p)。 // 刪除元素 } // 算法結(jié)束 210void one_to_three(linklist *A,*B,*C)// A是帶頭結(jié)點(diǎn)的的單鏈表，其數(shù)據(jù)元素是字符字母、字符、數(shù)字字符、其他字符。本算法//將A表分成 // 三個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表A、B和C，分別含有字母、數(shù)字和其它符號(hào)的同一類字符，利用原表空間。{ linklist *p=Anext,r。// p為工作指針，指向A表的當(dāng)前元素，r為當(dāng)前元素的后繼指針,使表避免斷開(kāi)。 //算法思想是取出當(dāng)前元素，根據(jù)是字母、數(shù)字或其它符號(hào)，分別插入相應(yīng)表中。 B=(linklist *)malloc(sizeof(linklist))。//申請(qǐng)空間，不判斷溢出 Bnext=null。 // 準(zhǔn)備循環(huán)鏈表的頭結(jié)點(diǎn) C=(linklist *)malloc(sizeof(linklist))。//申請(qǐng)空間，不判斷溢出 Cnext=null。 // 準(zhǔn)備循環(huán)鏈表的頭結(jié)點(diǎn) while(p) { r=pnext。 // 用以記住后繼結(jié)點(diǎn) if (pdata=’a’amp。amp。pdata=’z’||pdata=’A’amp。amp。 pdata=’Z’) {p next=Anext。 Anext=p。} // 將字母字符插入A表 else if (pdata=’0’amp。amp。pdata=’9’) {pnext=Bnext。 Bnext=p。} // 將數(shù)字字符插入B 表 else {pnext=Cnext。 Cnext=p。}// 將其