實(shí)驗(yàn)一（必做,設(shè)計(jì)性實(shí)驗(yàn)，2學(xué)時(shí)）實(shí)驗(yàn)題目：順序表基本操作1、在非遞減有序順序表中插入一個(gè)元素x，保持順序表有序性(2.11)2、比較兩個(gè)順序表的大小（2.12）3、順序表元素的逆置(2.21)4、兩個(gè)（有序或無(wú)序）順序表的合并(書(shū)上算法2.1和2.2)實(shí)驗(yàn)?zāi)康模菏煜⑺惴ㄞD(zhuǎn)換成程序代碼的過(guò)程。了解順序表的邏輯結(jié)構(gòu)特性，熟練掌握順序表存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述方法。熟練掌握順序表的基本操作：查找、插入、刪除、合并等，掌握順序表的隨機(jī)存取特性。實(shí)驗(yàn)要求：1、要求用靜態(tài)分配的一維數(shù)組和動(dòng)態(tài)分配的一維數(shù)組來(lái)完成實(shí)驗(yàn)題目。分析靜態(tài)分配的一維數(shù)組和動(dòng)態(tài)分配的一維數(shù)組在順序表基本操作實(shí)現(xiàn)上的共同點(diǎn)和區(qū)別。2、對(duì)順序表插入的算法，要求用兩種方法實(shí)現(xiàn)：自己編寫(xiě)函數(shù)實(shí)現(xiàn)；調(diào)用順序表基本操作ListInsert(SqList&L,inti,ElemTypex)，比較使用自己編寫(xiě)的插入函數(shù)和調(diào)用順序表基本操作的函數(shù)兩種實(shí)現(xiàn)方法之間的優(yōu)缺點(diǎn)。3、對(duì)所編寫(xiě)的算法進(jìn)行時(shí)間復(fù)雜度分析。實(shí)驗(yàn)內(nèi)容和實(shí)驗(yàn)步驟：1動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)typedefstruct{Elemtype*elem;//存儲(chǔ)空間的基地址。intlength;//當(dāng)前長(zhǎng)度intlistsize;//當(dāng)前分配的存儲(chǔ)容量}SqList;靜態(tài)分配的存儲(chǔ)結(jié)構(gòu)#definen100ElemTypeL[n];共同點(diǎn)：都是順序存儲(chǔ)結(jié)構(gòu)，或數(shù)組不同點(diǎn)：存儲(chǔ)空間可變與否。2方法1intInsertOrderList1(SqList&L,intx){if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase) exit(OVERFLOW);//分配不成功L.elem=newbase;L.listsize+=LISTINCREMENT;}p=&(L.elem[L.length-1]);//指向表尾元素位置while(p>=&(L.elem[0])&&*p>x){*(p+1)=*p;--p;}*(p+1)=x; ++L.length;//完成插入，線性表長(zhǎng)度增1returnOK;}//InsertOrderList1方法2intInsertOrderList2(SqList&L,intx){ inti; i=1;//數(shù)組下標(biāo)從1開(kāi)始 while((i<=L.length)&&(x>L.elem[i])) i++;//查找i是插入位置 ListInsert_Sq(L,i,x);//插在第i個(gè)元素之前 returnOK;}//InsertOrderList2方法2更簡(jiǎn)單，代碼復(fù)用程度高，但是需要給出明確的接口參數(shù)。3算法時(shí)間復(fù)雜度主要由插入元素的位置和移動(dòng)元素的多少?zèng)Q定，如果表長(zhǎng)為n，則時(shí)間復(fù)雜度為O（n）。實(shí)驗(yàn)用測(cè)試數(shù)據(jù)和相關(guān)結(jié)果分析：（由學(xué)生填寫(xiě)）第一組：L：14567結(jié)果：014567X：0第二組：L：14567結(jié)果：0145678X：8第三組：L：14567結(jié)果：0144567X：4LX插入后分析第一組145670014567在特殊位置上的插入情況應(yīng)考慮到第二組145678145678正常第三組145674144567正常實(shí)驗(yàn)總結(jié)：（由學(xué)生填寫(xiě)）動(dòng)態(tài)分配的存儲(chǔ)結(jié)構(gòu)因?yàn)榭梢匀藶榭刂品峙淇臻g的大小，所以靈活，既不會(huì)浪費(fèi)空間，也不會(huì)產(chǎn)生溢出現(xiàn)象。而靜態(tài)分配存儲(chǔ)空間比較死板，必須事先指定所需空間大小，在存儲(chǔ)空間需求不定的時(shí)候無(wú)法使用。