一.插入：插入前先移動(dòng)后面的元素

1.圖解：

在b和d之間插入c，此時(shí)就需要把d，e，f都向后移一位，騰出一個(gè)位置后插入c。

2.代碼實(shí)現(xiàn)：

#include<stdio.h>
#define MaxSize 10 //定義最大長(zhǎng)度typedef struct
{int data[MaxSize]; //用靜態(tài)的"數(shù)組"存放數(shù)據(jù)元素int length; //順序表的當(dāng)前長(zhǎng)度 
}SqList; //順序表的類型定義
?
?
//基本操作 - 初始化一個(gè)順序表
void InitList(SqList &L)
{for(int i=0;i<MaxSize;i++){L.data[i]=0; //將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值 }L.length=0; //順序表初始長(zhǎng)度為0 ，因?yàn)橐婚_始沒存元素 
} 
?
?
//插入 
void ListInsert(SqList &L,int i,int e) //i必須在1到Length+1上才有效，/*比如長(zhǎng)度為5，要加在第6個(gè)位置上，往后移動(dòng)一個(gè)位置就長(zhǎng)度為6，此時(shí)可添加在第6個(gè)位置上，如果仍長(zhǎng)度為5，要加在第7個(gè)位置上，往后移動(dòng)一個(gè)位置就長(zhǎng)度為6，沒有第7個(gè)位置，添加失敗*///元素存滿時(shí)也不能繼續(xù)插入數(shù)據(jù) ? 
{for(int j=L.length ; j>=i ; j--) //將第i個(gè)元素及之后的元素后移 {L.data[j]=L.data[j-1];}L.data[i-1]=e; //在位置i處放入eL.length++; //長(zhǎng)度加1，因?yàn)槎嗔艘粋€(gè)元素 
} 
?
?
int main()
{SqList L; //聲明一個(gè)順序表InitList(L); //初始化順序表//...此處省略一些代碼，插入幾個(gè)元素ListInsert(L,3,3); return 0;
}
/*位序從1開始，數(shù)組索引從0開始 */ 

代碼優(yōu)化：

#include<stdio.h>
#include<stdbool.h>
#define MaxSize 10 //定義最大長(zhǎng)度typedef struct
{int data[MaxSize]; //用靜態(tài)的"數(shù)組"存放數(shù)據(jù)元素int length; //順序表的當(dāng)前長(zhǎng)度 
}SqList; //順序表的類型定義
?
?
//基本操作 - 初始化一個(gè)順序表
void InitList(SqList &L)
{for(int i=0;i<MaxSize;i++){L.data[i]=0; //將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值 }L.length=0; //順序表初始長(zhǎng)度為0 ，因?yàn)橐婚_始沒存元素 
} 
?
?
//插入 
bool ListInsert(SqList &L,int i,int e) //i必須在1到Length+1上才有效，/*比如長(zhǎng)度為5，要加在第6個(gè)位置上，往后移動(dòng)一個(gè)位置就長(zhǎng)度為6，此時(shí)可添加在第6個(gè)位置上，如果仍長(zhǎng)度為5，要加在第7個(gè)位置上，往后移動(dòng)一個(gè)位置就長(zhǎng)度為6，沒有第7個(gè)位置，添加失敗*///元素存滿時(shí)也不能繼續(xù)插入數(shù)據(jù) ? 
{if(i<1||i>L.length+1) //判斷i的范圍是否有效 {return false;}if(L.length>=MaxSize) //判斷當(dāng)前存儲(chǔ)空間是否已滿，以決定能否繼續(xù)插入 {return false;}//走到這兒說(shuō)明能插入數(shù)據(jù) for(int j=L.length ; j>=i ; j--) //將第i個(gè)元素及之后的元素后移 {L.data[j]=L.data[j-1];}L.data[i-1]=e; //在位置i處放入eL.length++; //長(zhǎng)度加1，因?yàn)槎嗔艘粋€(gè)元素 return true;
} 
?
?
int main()
{SqList L; //聲明一個(gè)順序表InitList(L); //初始化順序表//...此處省略一些代碼，插入幾個(gè)元素ListInsert(L,3,3); return 0;
}
/*位序從1開始，數(shù)組索引從0開始 */ 

3.時(shí)間復(fù)雜度：

問(wèn)題規(guī)模n=L.length(表長(zhǎng))，當(dāng)添加一個(gè)元素后，長(zhǎng)度為n+1，

所以在第一個(gè)位置添加元素時(shí)，要把前n個(gè)元素后移，空出第一個(gè)位置，此時(shí)長(zhǎng)度為n+1。

---

二.刪除：刪除后先移動(dòng)前面的元素

1.圖解：

刪除c后，后面的d,e,f都要前移一個(gè)，數(shù)組長(zhǎng)度減一。

2.代碼實(shí)現(xiàn)：

#include<stdio.h>
#include<stdbool.h>
#define MaxSize 10 //定義最大長(zhǎng)度
?
?
typedef struct
{int data[MaxSize]; //用靜態(tài)的"數(shù)組"存放數(shù)據(jù)元素int length; //順序表的當(dāng)前長(zhǎng)度 
}SqList; //順序表的類型定義
?
?
//基本操作 - 初始化一個(gè)順序表
void InitList(SqList &L)
{for(int i=0;i<MaxSize;i++){L.data[i]=0; //將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值 }L.length=0; //順序表初始長(zhǎng)度為0 ，因?yàn)橐婚_始沒存元素 
} 
?
?
//刪除
bool ListDelete(SqList &L,int i,int &e) 
/*參數(shù)&L:代表要?jiǎng)h除的順序表；參數(shù)i:代表要?jiǎng)h除的第i個(gè)元素;參數(shù)&e:代表把刪除的元素返回*/
{if(i<1||i>L.length) //判斷i的范圍是否有效 (判斷語(yǔ)句為或:全假才假->才不走if;只要有一個(gè)是真就是真->就走if)//本例i為3，L.length為0，所以i>L.length為真，走if {return false;}//走到這兒說(shuō)明i有效，能刪除數(shù)據(jù)e=L.data[i-1]; //將被刪除的元素賦值給efor(int j=i;j<L.length;j++) //將第i個(gè)位置后的元素前移 {L.data[j-1]=L.data[j];} L.length--; //線性表長(zhǎng)度減一return true; 
} 
?
?
?
int main()
{SqList L; //聲明一個(gè)順序表InitList(L); //初始化順序表//...此處省略一些代碼，插入幾個(gè)元素int e=-1; //用變量e把刪除的元素"帶回來(lái)"if( ListDelete(L,3,e) ){printf("已刪除第3個(gè)元素，刪除的元素的值為=%d \n",e);}else{printf("位序i不合法，刪除失敗 \n");} return 0;
}

ListDelete第三個(gè)參數(shù)有個(gè)&，這樣就使得main函數(shù)里的e和ListDelete函數(shù)里的e是同一個(gè)e，

不加&，main函數(shù)里的e和ListDelete函數(shù)里的e就不是同一個(gè)e了，執(zhí)行完ListDelete函數(shù)后，main函數(shù)里的e的值沒發(fā)生改變。

3.時(shí)間復(fù)雜度：

例如i為2時(shí)，剩下n-2個(gè)，然后剩下的n-2個(gè)依次循環(huán)。

---

三.總結(jié)：

---