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

數據結構作業(yè)(C語言版)習題數據結構作業(yè)(C語言版)習題全文共12頁，當前為第1頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第1頁。數據結構作業(yè)（C語言版）習題1.4，試仿照三元組的抽象數據類型分別寫出抽象數據類型復數和有理數的定義（有理數是其分子、分母均為自然數且分母不為零的分數）。復數：ADTTriplet{D={r,i|r,i為實數} R={<r,i>} InitComplex(&C,re,im) }ADTComplex有理數：ADTTriplet{D={c1,c2,c3|c1,c2,c3∈Z,c3≠0};數據結構作業(yè)(C語言版)習題全文共12頁，當前為第2頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第2頁。C3=c1/c2;}ADTTriplet1.9假設n為2的乘冪，并且n＞2，試求下列算法的時間復雜度及變量count的值（以n的函數形式表示）。intTime(intn){count=0;x=2;while(x＜n/2){x*=2;count++;}return(count)}//Time解：count=1.16試寫一算法，自大至小依次輸出順序讀入的三個整數X，Y和Z的值。Voidbubble-sort(inta[X,Y,Z],inti){數據結構作業(yè)(C語言版)習題全文共12頁，當前為第3頁。for(i=n-1,change=TRUE;i≥數據結構作業(yè)(C語言版)習題全文共12頁，當前為第3頁。change=FALSE;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j+1]←→a[j]change=TRUE;}}}//bubble-sort解：intmax3(intx,inty,intz){ if(x>y) if(x>z)returnx; elsereturnz; else if(y>z)returny; elsereturnz;}2.1描述以下三個概念的區(qū)別：頭指針，頭結點，首元結點（第一個元素結點）。頭結點：在單鏈表的第一個結點之前附設一個結點，即稱之為頭結點頭指針：鏈表中第一個結點的存儲位置即稱之為頭指針數據結構作業(yè)(C語言版)習題全文共12頁，當前為第4頁。首元結點：數據結構作業(yè)(C語言版)習題全文共12頁，當前為第4頁。（1）在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。（2）順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。（3）在單鏈表中，除了首元結點外，任一結點的存儲位置由其直接前驅結點的鏈域的性指示。（40在單鏈表中設置頭結點的作用是插入或刪除首元素不必進行特殊處理。2.4對以下單鏈表分別執(zhí)行下列各程序段，并畫出結果示意圖。數據結構作業(yè)數據結構作業(yè)(C語言版)習題全文共12頁，當前為第5頁。22573864Q=P->next;L=P->next;R->data=P->data;R->data=P->next->data;P->next->next->next->data=P->data;T=P;While(T!=NULL){T->data=T->data*2;T=t->next;}(7)T=PWhile(T->next!=NULL){T->data=T->data*2;T=T->next;}數據結構作業(yè)(C語言版)習題全文共12頁，當前為第6頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第6頁。2.5畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(LNode));P=LFor(i=1;i<=4;i++){p->next=(LinkList)malloc(sizeof(LNode));P=P->next;p->data=i*2-1;}P->next=NULL;數據結構作業(yè)(C語言版)習題全文共12頁，當前為第7頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第7頁。for(i=1;i<=3;i++)Del-LinkList(L,i);解：2.6已知L是無表頭結點的單鏈表，且P結點既不是首元結點，也不是尾元結點，試從下列提供的答案中選擇合適的語句序列。A．在P結點后S結點的語句序列是：(4)(1)B．在P結點前S結點的語句序列是：(7)(11)(8)(4)(1)C．在表首S結點的語句序列是：(5)(12)D．在表尾S結點的語句序列是：(9)(1)(6)（1）P->next=S;(2)P->next=P->next->next;數據結構作業(yè)(C語言版)習題全文共12頁，當前為第8頁。(3)數據結構作業(yè)(C語言版)習題全文共12頁，當前為第8頁。(4)S->next=P->next;(5)S->next==L;(6)S->next=NULL;(7)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;a.(11)(3)(14)b.(10)(12)(8)(11)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e(9)(11)(3)(14)a.(7)(12)(6)(3)b.(8)(13)(5)(4)數據結構作業(yè)(C語言版)習題全文共12頁，當前為第9頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第9頁。d.(16)(2)(10)(18)e.(9)(14)(17)StatusDeleteK(SqList&a,inti,intk){ intj; if(i<0||i>a.length-1||k<0||k>a.length-i)returnINFEASIBLE; for(j=0;j<=k;j++) a.elem[j+i]=a.elem[j+i+k]; a.length=a.length-k; returnOK;}2.13.解：intLocateElem_L(LinkList&L,ElemTypex)數據結構作業(yè)(C語言版)習題全文共12頁，當前為第10頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第10頁。 inti=0; LinkListp=L; while(p&&p->data!=x){ p=p->next; i++; } if(!p)return0; elsereturni;}2.14.解：intListLength_L(LinkList&L){ inti=0; LinkListp=L; if(p)p=p-next; while(p){ p=p->next; i++; }數據結構作業(yè)(C語言版)習題全文共12頁，當前為第11頁。數據結構作業(yè)(C語言版)習題全文共12頁，當前為第11頁。}3.1.解：(1)123231321213132(2)可以得到135426的出站序列，但不