線性表的順序存儲(chǔ)又稱順序表。
一組地址連續(xù)存放的存儲(chǔ)單元依次存放線性表的元素，從而使得邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰。
數(shù)組靜態(tài)分配
#define MaxSize 50
typeof struct{
????????Element date[MaxSize?];
? ? ????int length;
}SqList;
數(shù)組動(dòng)態(tài)分配
#define MaxSize 50
typeof struct{
????????Element *date;
????????int length;
}SqList;
動(dòng)態(tài)分配語(yǔ)句
C? ? ? ? ? ?L.data = (Elemtype*)malloc(sizeof(Elemtype)*InitSize);
C++? ? ??L.data?= new ElemType[InitSize];
順序表的定義
插入操作：
/**
?*? ? SqList?&L引用類型順序表L
?*? ? int?i? 開始插入的位置（使用前插法，對(duì)應(yīng)的不是數(shù)組下標(biāo)）
?*? ??Elemtype e? 要插入的數(shù)據(jù)
?*/
bool ListInsert(SqList &L,int i,Elemtype e){
? ? ? ? if(i<1 || i>L.length+1){
? ? ? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? if(L.length>=MaxSize){
? ? ? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? for(int j=L.length;j>=i;j--){
? ? ? ? ? ? ? ? L.data[j]=L.data[j-1];
? ? ? ? }
? ? ? ? L.data[i-1]=e;
? ? ? ? L.length++;
? ? ? ? return true;
}
// L.date總長(zhǎng)度為7，并且前面五個(gè)數(shù)據(jù)空間已經(jīng)存儲(chǔ)了“a,b,c,d,e”這五個(gè)數(shù)據(jù)
ListInsert[L,3,'e'];
最好情況：表尾插入i=n+1 ，不執(zhí)行語(yǔ)句 O(1)?
最壞情況：表頭插入i=1 ，n 條語(yǔ)句執(zhí)行O(n)
平均情況：插入一個(gè)結(jié)點(diǎn)的概率，p=i/(n+1) 平均移動(dòng)次數(shù) n/2. O(n)
刪除操作：
/**?
*? ? SqList?&L?引用類型順序表L?
*? ??int?i? 要?jiǎng)h除的位置（對(duì)應(yīng)的不是數(shù)組下標(biāo)）?
*? ??Elemtype &e? 要?jiǎng)h除數(shù)據(jù)的引用變量
*/?
bool ListDelete(SqList &L,int i,Elemtype &e){
? ? ? ? if(i<1||i>l.length){
? ? ? ? ? ? ? ? return false;
????????}
? ? ? ? e=L.data[i-1];
? ? ? ? for(int j=i;j>L.length;j++){
? ? ? ? ????????L.data[j-1]=L.data[j];
? ? ? ? }
? ??????L.length--;
? ? return true;
}
// L.date總長(zhǎng)度為7，并且前面五個(gè)數(shù)據(jù)空間已經(jīng)存儲(chǔ)了“a,b,c,d,e”這五個(gè)數(shù)據(jù)
ListInsert[L,3,e];?
最好情況：表尾刪除i ，不移動(dòng) O(1)?
最壞情況：表頭刪除，需要移動(dòng)n-1個(gè)元素，時(shí)間復(fù)雜度O(n)
平均情況：刪除一個(gè)結(jié)點(diǎn)的概率，p=1/n 移動(dòng)次數(shù) n-i 平均移動(dòng)次數(shù) n-1/2. O(n)
按值查找：
/**?
*? ? SqList L?需要查找的順序表
*? ??Elemtype e? ?要查找的數(shù)據(jù)
*/??
int?LocateElem(SqList L,ElemType e){
? ? ? ? int i;
? ? ? ? for(i=0;i<L.length;i++){
? ? ? ? ? ? ? ? if(L.data[i]==e){
? ? ? ? ? ? ? ? ? ? ????return i+1;?
? ? ? ? ? ? ? ? }
? ? ????}
? ? ? ? return 0;
}
最好情況：表頭i ,執(zhí)行一次? O(1)?
最壞情況：表尾，需要比較n個(gè)元素，時(shí)間復(fù)雜度O(n)
平均情況：查找一個(gè)結(jié)點(diǎn)的概率，p=1/n 查找次數(shù) i 平均查找次數(shù) n+1/2. O(n)
