數據結構—用c語言描述課后習題答案(已修改)

　

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