數(shù)據(jù)結(jié)構(gòu)作業(yè)1/2數(shù)據(jù)結(jié)構(gòu)作業(yè)：1簡(jiǎn)述下列術(shù)語：線性表，順序表，鏈表。線性表：注意常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表示n個(gè)數(shù)據(jù)元素的有限序列。順序表：是指用一組連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表中的數(shù)據(jù)元素。鏈表：邏輯結(jié)構(gòu)相鄰的數(shù)據(jù)元素物理結(jié)構(gòu)不一定相鄰。采用指針的形式連接起來。2何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)合適?各自的主要優(yōu)缺點(diǎn)是什么?不需要經(jīng)常大量的修改表或需要隨機(jī)存取的情況下可以選用順序表；相反需要經(jīng)常大量的修改表，但不是頻繁的隨機(jī)的存取的情況下可選用鏈?zhǔn)奖怼?在順序表中插入和刪除一個(gè)結(jié)點(diǎn)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?平均需要移動(dòng)n/2個(gè)結(jié)點(diǎn)。具體的移動(dòng)次數(shù)取決于表的長(zhǎng)度和要插入的位置4鏈表所表示的元素是否有序?如有序，則有序性體現(xiàn)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的?有序表的有序性又如何理解?數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第1頁(yè)。有序。有序性體現(xiàn)在通過指針數(shù)據(jù)元素有序的相連。物理上下一定要相鄰。數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第1頁(yè)。5設(shè)順序表L是遞增有序表，試寫一算法，將x插入到L中并使L仍是遞增有序表。StatusListInsert(SqList&L,inti,ElemTypee){If(i>L.length+1||i<1)returnERROR;If(L.length>=L.listsize){Newbase=(ElemType*)realloc((L.listsize=LISTINCRMENT)*sizeof(ElemType));If(!mewbase)exit(-1);}Lelem=newbase;Listsize+=LISTINCREMENT;}ElemType*q,*p;q=&Lelem[i-1];for(p=&L.elem[L.length-1];p>=q;p--)*(p+1)=*p;*q=e;L.length++;returnOK;}數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第2頁(yè)。6寫一求單鏈表的結(jié)點(diǎn)數(shù)目ListLength(L)數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第2頁(yè)。IntListLength(L){inti=0;ElemType*p;p=&L;if(!p)exit(-1);if(p.next==NULL)return0;elsewhile(p.next!=NULL){p++;i++;}returni;}7寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果鏈表中所有結(jié)點(diǎn)的值均不相同。voidDeletElem(SqListL){ElemType*p,*q,*s;inti=1;intj;p=&L.next.next;數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第3頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第3頁(yè)。{q=&L.next;for(j=1;j<=i;j++){if(q->data==p->data){p.next=(p-1).next;s=p;p++;free(s);}}if(j>i)P++;}}8寫一算法從一給定的向量A刪除值在x到y(tǒng)(x≤y)之間的所有元素(注意：x和y是給定的參數(shù)，可以和表中的元素相同，也可以不同)。voidDeletElem(SqListL,intx,inty){數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第4頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第4頁(yè)。inti=0;intj;p=&L.next;for(i;i<L.length;i++){if(p.data>=x||p.data<=y){q=p;(p-1).next=p.next;p++;free(q);}elsep++;}9設(shè)A和B是兩個(gè)按元素值遞增有序的單鏈表，寫一算法將A和B歸并為按按元素值遞減有序的單鏈表C，試分析算法的時(shí)間復(fù)雜度。voidListInsert(SqlistA,SqListB,SqListC){ElemType*p,*q,*s;數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第5頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第5頁(yè)。q=&C;s=&C;while(p.next!=NULL||q.next!=NULL){if(p.next.data<=q.next.data){if(s.next!=NULL){p.next=s.next;s.next=p.next;P++;}else{if(s.next!=NULL)q.next=s.next;s.next=q.next;q++;}}while(p.next!=NULL){p.next=s.next;數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第6頁(yè)。數(shù)據(jù)結(jié)構(gòu)作業(yè)全文共7頁(yè)，當(dāng)前為第6頁(yè)。}w