數(shù)據(jù)結構作業(yè)C語言版習題

1、數(shù)據(jù)結構作業(yè)（C語言版）習題1.4，試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復數(shù)和有理數(shù)的定義（有理數(shù)是 其分子、分母均為自然數(shù)且分母不為零的分數(shù)）。復數(shù)：ADT TripletD=r,i|r,i 為實數(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假設n為2的乘幕，并且n> 2,試求下列算法的時間復雜度及變量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 試寫一算法，自大至小依次輸出順序讀入的三個整數(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描述以下三個概念的區(qū)別：頭指針，頭結點，首元結點(第一個元素結點)。頭結點：在單鏈表的第一個結點之前附設一個結點，即稱之為頭結點頭指針：鏈表中第一個結點的存儲位置即稱之為頭指針首元結點：首元結點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素al的結點2.2填空題(1) 在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與表長和該元素

4、在表中的位置有關。(2) 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理 位置不一定相鄰。(3) 在單鏈表中，除了首元結點外，任一結點的存儲位置由其直接前驅結點的鏈域的性指示。(40在單鏈表中設置頭結點的作用是插入或刪除首元素不必進行特殊處理。2.4對以下單鏈表分別執(zhí)行下列各程序段，并畫出結果示意圖。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í)行下列各行語句后各指針及鏈表的示意圖。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是無表頭結點的單鏈表，且P結點既不是首元結點，也不是尾元結點，試從下列提供的答案中選擇合適的語句序列。A. 在P結點后S結點的語句序列是：(4) (1)B. 在P結點前S結點的語句序列是：(7) (11) (8)(1)C. 在表首S結點的語句序列是：(5) (12)D. 在表尾S結點的語句序列是：(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 的出站序列。因為 4356 出站說明 12 已經在棧中， 1