數(shù)據(jù)結(jié)構(gòu)作業(yè)C語(yǔ)言版習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)作業(yè)（C語(yǔ)言版）習(xí)題1.4，試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是 其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)）。復(fù)數(shù)：ADT TripletD=r,i|r,i 為實(shí)數(shù)R=<r,i>In itComplex(&C,re,im)ADT Complex有理數(shù)：ADT TripletD=c1,c2,c3 | c1,c2,c3 Z,c3 豐 0;R=<c1,c2>C3=c1/c2;ADT Triplet1.9假設(shè)n為2的乘幕，并且n> 2,試求下列算法的時(shí)間復(fù)雜度及變量count的值(以n的函數(shù)形式表示)。int Time

2、 (int n)coun t=0;x=2;while(x v n/2)x*=2;co un t+;return(co unt)/Time解：o(log 2 n)count= log2 n2X, Y和Z的值。1.16 試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)Void bubble-sort(int aX,Y,Z,int i)for (i=n-1,cha nge=TRUE; i> &&cha nge; -i)chan ge=FALSE;» ajchange=TRUE;for(j=0;j<i;+j) if(aj>aj+1)aj+1</bubbl

3、e-sort解：int max3(i nt x,i nt y,i nt z)if(x>y)if(x>z) retur n x;else return z;elseif(y>z) retur n y; else return z;2.1描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn))。頭結(jié)點(diǎn)：在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，即稱之為頭結(jié)點(diǎn)頭指針：鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置即稱之為頭指針首元結(jié)點(diǎn)：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素al的結(jié)點(diǎn)2.2填空題(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素

4、在表中的位置有關(guān)。(2) 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理 位置不一定相鄰。(3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的性指示。(40在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入或刪除首元素不必進(jìn)行特殊處理。2.4對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。6-6-4(1)Q=P-> next;(2)L=P->n ext;(3)R->data=P->data;(4)R->data=P->n ext->data;(5)P->n ext->n ext- >n ext-

5、>data=P->data;(6)T=P;While(T!=NULL)T->data=T->data*2;T=t-> next;T=PL(7) LPPPPWhile(T->n ext!=NULL)T->data=T->data*2;T=T->n ext;2.5畫出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖。L=(L in kList)malloc(sizeof(LNode);P=LFor(i=1;i<=4;i+)p->n ext=(L in kList)malloc(sizeof(LNode); P=P-> next;p-&g

6、t;data=i*2-1;P-> next=NULL;for(i=4;i>=1;i-;)In s-Li nkList(L,i+1,i*2); for(i=1;i<=3;i+)Del-Lin kList(L,i);7AI7 TIPL L2.6已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。A. 在P結(jié)點(diǎn)后S結(jié)點(diǎn)的語(yǔ)句序列是：(4) (1)B. 在P結(jié)點(diǎn)前S結(jié)點(diǎn)的語(yǔ)句序列是：(7) (11) (8)(1)C. 在表首S結(jié)點(diǎn)的語(yǔ)句序列是：(5) (12)D. 在表尾S結(jié)點(diǎn)的語(yǔ)句序列是：(9) (1) (6)(1) P-&g

7、t;next=S;(2) P->n ext=P->n ext- >n ext;(3) P-> next=S-> next;(4) S-> next=P-> next;(5) S-> next=L;(6) S-> next=NULL;Q=P(8) while(P-> next!=Q)P=P-> next;(9) while(P-> next!=NULL)P=P-> next;(10) P=Q(11) P=L;(12) L=S;(13) L=P;2.7a. (11)(3)(14)b. (10)(12)(8)(11)(3)

8、(14)c. (10)(12)(7)(3)(14)d. (12)(11)(3)(14)e(9)(11)(3)(14)2.8a. (7)(12)(6)(3)b. (8)(13)(5)(4)c. (15)(1)(11)(18)d. (16)(2)(10)(18)e. (9)(14)(17)2.10Status DeleteK(SqList &a,int i,int k)int j; if(i<0|i>a.length-1|k<0|k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j+)a.elemj+i=a.elemj

9、+i+k;a.length=a.length-k;return OK;2.13. 解：int LocateElem_L(LinkList &L,ElemType x)int i=0;LinkList p=L;while(p&&p->data!=x)p=p->next;i+;if(!p) return 0;else return i;2.14. 解：int ListLength_L(LinkList &L)int i=0;LinkList p=L;if(p) p=p-next;while(p)p=p->next;i+;return i;3.1. 解： (1)123 231 321 213 132(2) 可以得到 135426 的出站序列，但不能得到 435612 的出站序列。因?yàn)?4356 出站說(shuō)明 12 已經(jīng)在棧中， 1