實驗一（必做,設計性實驗，2學時）實驗題目：順序表基本操作1、在非遞減有序順序表中插入一個元素x，保持順序表有序性(2.11)2、比較兩個順序表的大小（2.12）3、順序表元素的逆置(2.21)4、兩個（有序或無序）順序表的合并(書上算法2.1和2.2)實驗目的：熟悉將算法轉換成程序代碼的過程。了解順序表的邏輯結構特性，熟練掌握順序表存儲結構的C語言描述方法。熟練掌握順序表的基本操作：查找、插入、刪除、合并等，掌握順序表的隨機存取特性。實驗要求：1、要求用靜態分配的一維數組和動態分配的一維數組來完成實驗題目。分析靜態分配的一維數組和動態分配的一維數組在順序表基本操作實現上的共同點和區別。2、對順序表插入的算法，要求用兩種方法實現：自己編寫函數實現；調用順序表基本操作ListInsert(SqList&L,inti,ElemTypex)，比較使用自己編寫的插入函數和調用順序表基本操作的函數兩種實現方法之間的優缺點。3、對所編寫的算法進行時間復雜度分析。實驗內容和實驗步驟：1動態存儲結構typedefstruct{Elemtype*elem;//存儲空間的基地址。intlength;//當前長度intlistsize;//當前分配的存儲容量}SqList;靜態分配的存儲結構#definen100ElemTypeL[n];共同點：都是順序存儲結構，或數組不同點：存儲空間可變與否。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;//完成插入，線性表長度增1returnOK;}//InsertOrderList1方法2intInsertOrderList2(SqList&L,intx){ inti; i=1;//數組下標從1開始 while((i<=L.length)&&(x>L.elem[i])) i++;//查找i是插入位置 ListInsert_Sq(L,i,x);//插在第i個元素之前 returnOK;}//InsertOrderList2方法2更簡單，代碼復用程度高，但是需要給出明確的接口參數。3算法時間復雜度主要由插入元素的位置和移動元素的多少決定，如果表長為n，則時間復雜度為O（n）。實驗用測試數據和相關結果分析：（由學生填寫）第一組：L：14567結果：014567X：0第二組：L：14567結果：0145678X：8第三組：L：14567結果：0144567X：4LX插入后分析第一組145670014567在特殊位置上的插入情況應考慮到第二組145678145678正常第三組145674144567正常實驗總結：（由學生填寫）動態分配的存儲結構因為可以人為控制分配空間的大小，所以靈活，既不會浪費空間，也不會產生溢出現象。而靜態分配存儲空間比較死板，必須事先指定所需空間大小，在存儲空間需求不定的時候無法使用。