c語言數據結構，你可能還不知道的順序表
數據結構順序表
順序表定義
1，前言
線性表的順序存儲又稱為順序表。它是用一組地址連續的存儲單元依次存儲線性表中的數據元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。其最大的特點就是：元素的邏輯順序與其物理順序相同。
線性表的順序存儲結構中任一元素都可以隨機存取，並且注意：線性表中元素的位序是從1 開始的，而數組中元素的下標是從0 開始的。假定線性表的元素類型為 EleType ，則線性表的順序存儲類型可以描述為：
#define MaxSize 50 //定義線性表的最大長度
typedef struct {
ElemType data[MaxSize]; //順序表的元素
int length; //順序表的當前長度
}SqList； //順序表的類型定義
2，動態實現
1，結構定義：
#define InitSize 10 //默認的最大長度
typedef struct{
int *data; //指示動態分配數組的指針
int MaxSize; //順序表的最大容量
int length; //順序表的當前長度
}SeqList；
2，初始化順序表：
void InitList(SeqList &L){
//用malloc函數申請一片連續的存儲空間
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
3，增加動態數組的長度：
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++)
L.data[i]=p[i]; //將數據複製到新區域，時間開銷很大
L.MaxSize=L.MaxSize+len; //順序表最大長度增加len
free(p); //釋放原來的記憶體空間
}
順序表上的基本操作
1，插入操作（Listsert(&L,i,e)
在表L 中的第i 個位置上插入指定元素e 。以下採用的是「靜態分配的方式實現。
以下給出實現的主要程式碼部分，便於我們閱讀理解：
#define MaxSize 10 //定義線性表的最大長度
typedef struct {
int data[MaxSize]; //用靜態的「數組」存放數據元素
int length; //順序表的當前長度
}SqList； //順序表的類型定義
bool ListInsert(Sqlist &L,int i,int e){
if(i<1||i>L.length+1)
return false;
if(L.length>=MaxSize) //當前存儲空間已滿，不能插入
return false;
for(int j=L.length;j>=i;j--) //將第i個元素及其後的元素後移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i處放入e
L.length++; //線性表的長度加1
return true;
int main(){
SqList L; //聲明一個順序表
InitList(L); //初始化順序表
//...此處省略插入幾個元素的程式碼
ListInsert(L,3,3);
return 0;
}
插入操作的時間複雜度分析：
通過觀察以上程式碼，我們分析時間複雜度時只需要關注最深層循環語句的執行次數與問題規模n 的關係。即語句「L.data[j]=L.data[j-1];」即可：
- 最好情況：新元素插入到表位，不需要移動元素，i=n+1，循環0次；最好的時間複雜度為O(1)
- 最壞情況：新元素插入到表頭，需要將原有的n 個元素全都向後移動，i =1，循環n 次；最壞的時間複雜度為O(n);
- 平均情況：假設新元素插入到任何一個位置的概率相同，概率為P=1/(n+1)。i=1，循環n 次；i =2 時，循環n-1次；i =3 ，循環n-2 次 ….. i =n+1 時，循環0 次。平均循環次數 =np+(n-1)p+(n-2)p+…..+1.p= n/2。即得平均時間複雜度= O(n)
提示：如果以上的分析i 的值和循環次數n 的關係不是太清楚，要回想下開頭提到的線性表中元素的位序是從1 開始的，而數組中元素的下標是從0 開始的。
2，刪除操作（ListDelete(SqList &L,int i,int &e)）
刪除順序表L 中的第i （1<=i<=L.length)個位置的元素，用引用變數e 返回。若輸入的i 不合法，則返回false ；否則，將被刪元素賦給引用變數e ，並將第i+1 個元素及其後的所有元素一次往前移動一個位置，返回true 。
下面給出部分程式碼，輔助我們理解閱讀：
bool ListDelete(SqList &L,int i,int &e){
if(i<1||i>L.length) //判斷i的範圍是否有效
return false；
e=L.data[i-1]; //將刪除元素賦給引用變數e
for(int j=i;j<L.length;j++) //將第i個位置後的元素前移
L.data[j-1]=L.data[j];//這裡再次提醒位序與數組下標的關係
L.length--; //線性表長度減1
return true;
}
int main(){
SqList L; //聲明一個順序表
InitList(L); //初始化
//.....省略一些程式碼
int e=-1; //用標量e將刪除的變數「帶回來」
if(ListDelete(L,3,3))
printf("已刪除第3個元素，刪除元素值為=%d\n",e);//試一下
else
printf("位序i不合法，刪除失敗\n");
return 0;
}
刪除操作的是時間複雜度分析：
通過觀察以上程式碼，我們分析時間複雜度時只需要關注最深層循環語句的執行次數與問題規模n 的關係。即語句「L.data[j-1]=L.data[j];」即可：
- 最好情況：刪除元素，不需要移動其他元素，i=n，循環0次；最好的時間複雜度為O(1)
- 最壞情況：刪除表頭元素，需要將後續的n-1個元素全都向前移動。i=1，循環n-1次；最壞時間複雜度= O(n)
- 平均情況：假設刪除任何一個元素的概率相同，及p=1/n，i=1，循環n-1次；i=2，循環n-2 次….. i=n 時，循環0次，故平均循環次數=(n-1)p+(n-2)p+…..+1.p=(n-1)/2.則時間複雜度為O(n)
3，按位查找（GetElem(L,i)）
獲取表L 中第i 個位置的元素的值。下面給出一段簡單的程式碼示例：
#define InitSize 10 //順序表的初始長度
typedef struct{
ElemType *data; //指示動態分配數組的指針
int MaxSize; //順序表中的最大容量
int length; //順序表的當前長度
}SeqList; //順序表的類型的定義（動態分配方式）
ElemType GetElem(SeqList L,int i){
return L.data[i-1];
}
由於順序表的各個元素在記憶體中連續存放，因此可以根據起始地址和數據元素大小立即找到第i 個元素，這也就是 隨機存取特性的體現。因此其時間複雜度可得為 O(1)。
4，按值查找（LocateElem( L, e) ）
在表L 中查找具有給定關鍵字的元素。如下給出在順序表L 中查找第一個元素值等於e 的元素，並返回其位序：
int LocateElem(SeqList L,ElemType e){
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1; //注意數組下標與順序表位序的關係
return 0; //退出循環，說明查找失敗
}
對於時間複雜度的分析：
通過觀察以上程式碼，我們分析時間複雜度時只需要關注最深層循環語句的執行次數與問題規模n 的關係。即語句「 if(L.data[i]==e 」即可：
- 最好情況：目標元素在表頭，循環1次；最好時間複雜度為O(1)
- 最壞情況：目標元素在表尾，循環n 次；最壞時間複雜度為O(n);
- 平均情況：假設目標元素出現在任何一個位置的概率相同，都是1/n，目標元素在第一位，循環1次；第2位，循環2次；……. 在第n 為，循環n 次，則平均循環次數 =1\n+2.1/n+….+n.1/n=(n+1)/2；則平均時間複雜度為O(n)。
關於順序表的一些知識先就說這麼多，共勉！
