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

數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)（C語(yǔ)言版）習(xí)題1.4，試仿照三元組的抽象數(shù)據(jù)類(lèi)型分別寫(xiě)出抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)）。復(fù)數(shù)：ADTTriplet{D={r,i|r,i為實(shí)數(shù)} R={<r,i>} InitComplex(&C,re,im) }ADTComplex有理數(shù)：ADTTriplet{D={c1,c2,c3|c1,c2,c3∈Z,c3≠0};數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第2頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第2頁(yè)。C3=c1/c2;}ADTTriplet1.9假設(shè)n為2的乘冪，并且n＞2，試求下列算法的時(shí)間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。intTime(intn){count=0;x=2;while(x＜n/2){x*=2;count++;}return(count)}//Time解：count=1.16試寫(xiě)一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X，Y和Z的值。Voidbubble-sort(inta[X,Y,Z],inti){數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第3頁(yè)。for(i=n-1,change=TRUE;i≥數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第3頁(yè)。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描述以下三個(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ǔ)位置即稱之為頭指針數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第4頁(yè)。首元結(jié)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第4頁(yè)。（1）在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置有關(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í)行下列各程序段，并畫(huà)出結(jié)果示意圖。數(shù)據(jù)結(jié)構(gòu)作業(yè)數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第5頁(yè)。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;}數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第6頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第6頁(yè)。2.5畫(huà)出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖。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;數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第7頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第7頁(yè)。for(i=1;i<=3;i++)Del-LinkList(L,i);解：2.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)(4)(1)C．在表首S結(jié)點(diǎn)的語(yǔ)句序列是：(5)(12)D．在表尾S結(jié)點(diǎn)的語(yǔ)句序列是：(9)(1)(6)（1）P->next=S;(2)P->next=P->next->next;數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第8頁(yè)。(3)數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第8頁(yè)。(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)數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第9頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第9頁(yè)。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)數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第10頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第10頁(yè)。 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++; }數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第11頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)(C語(yǔ)言版)習(xí)題全文共12頁(yè)，當(dāng)前為第11頁(yè)。}3.1.解：(1)123231321213132(2)可以得到135426的出站序列，但不