## 一.順序表的定義 線性表的順序存儲有稱之為順序表。它是用一組地址連續的存儲單元，依次存儲線性表的數據元素，從而使得邏輯上相鄰的兩個元素在物理上也相鄰。第一個元素存儲在線性表的起始位置，第i個元素的存儲位置后面緊接著存儲的時第i+1個元素。 因此，順序表的特點時表中元素的邏輯順序與物理順序相同。 這里，我們假定元素類型為`ElemType`，線性表的順序存儲類型則可以描述為： ~~~ #define MaxSize 50; typedef struct{ ElemType data[MaxSize]; int length; }SqList; ~~~ 這種描述有時也稱為“柔性數組”。這里說明下，《數據結構與算法》中其他章節的描述部分均采用的是C語言。 一維數組可以是靜態分配的，也可以是動態分配的。 在靜態分配時，由于數組的大小和空間事先已經確定，一旦空間占滿，再加入新的數據將會產生溢出，導致程序崩潰。比如上述描述便是采用靜態分配。 當采用動態分配時，存儲數組的空間是在程序執行過程中通過動態存儲分配語句分配的，一旦數據空間占滿，可以另外開辟一塊更大的存儲空間，用以替換原來的空間，從而達到擴充數組空間的目的，因此不需要一次性劃分所有的所需空間給線性表，具體描述如下： ~~~ #define InitSize 100 typedef struct{ ElemType *data; int MaxSize, length; }SeqList; ~~~ 初始的動態分配語句為 ~~~ L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize); ~~~ **注：**動態分配并不是鏈式存儲，同樣屬于順序存儲結構，其物理結構并沒有發生變化，依然是隨機存取方式，只是在分配存儲空間時可以在運行決定。 因為順序表采用的時順序存儲，因此具有順序存儲的幾個重要特點： - 具有隨機訪問特性，即通過首地址和元素序號可以在O(1)的時間內找到指定元素； - 存儲密度高，每個節點只存儲數據元素； - 邏輯上相鄰的元素物理上同樣相鄰，所以插入和刪除操作需要移動大量元素。 ## 二.順序表上基本操作的實現 ### 2.1插入操作 在順序表L的第i(1≤i≤L.length+1)個位置插入新新元素e，如果i的輸入不合法，則返回-1，表示插入失敗；否則，將順序表的第i個元素以及其后的元素右移一個位置，騰出一個空位置插入新元素e，順序表長度加1，插入成功，返回0； ~~~ int ListInsert(SqList *L, int i, int e) { if(i<0||i>L->length){ printf("The postion is out of border! \n"); return -1; }else if(L->length>=MaxSize){ printf("The length more over MaxSize! \n"); return -1; }else{ int j; for(j=L->length;j>=i;j--){ L->data[j]=L->data[j-1]; } L->data[j]=e; L->length++; return 0; } } ~~~ 我們分析下時間復雜度： 最佳情況：在表尾直接插入（即i=n+1），無需移動任何元素，則時間復雜度為O(1)； 最壞情況：在表頭插入即（即i=1），每個元素后移一位，即移位語句執行n次，事件復雜度為O(n)； 平均情況：假設pi(pi=1(n+1))是在第i個位置上插入一個節點的概率，則在長度為n的線性表中插入一個節點時所需移動節點的平均次數為 ∑i=1n+1pi(n?i+1)=∑i=1n+11n+1(n?i+1)=1n+1∑i=1n+1(n?i+1)=1n+1n(n+1)2=n2 因此，線性插入算法的平均事件復雜度為O(n)。 ### 2.2刪除操作 刪除順序表L中第i(1≤i≤L.length)個位置的元素，成功返回0，否則返回-1，并將被刪除的元素采用指針調用的方式返回。 ~~~ int ListDelete(SqList *L, int i, ElemType *e) { if(i<0||i>L->length){ printf("The position over the border! \n"); return -1; } *e=L->data[i-1]; for(int j=i;j<L->length;j++){ L->data[j-1]=L->data[j]; } L->length--; return 0; } ~~~ 分析下時間復雜度： 最佳情況：刪除表尾元素（即i=n），無需移動任何元素，則時間復雜度為O(1)； 最壞情況：刪除表頭元素（即i=1），需要移動除第一個元素外的所有元素，即移位語句執行n次，事件復雜度為O(n)； 平均情況：假設pi(pi=1n)是刪除第i個位置上節點的概率，則在長度為n的線性表中刪除一個節點時所需移動節點的平均次數為 ∑i=1npi(n?i)=∑i=1n1n(n?i)=1n∑i=1n(n?i)=1nn(n?1)2=n?12 因此，線性刪除算法的平均事件復雜度為O(n)。 ### 2.3按值查找（順序查找） 在順序表L中查找第一個元素值等于e的元素，并返回其下標，否則返回-1. ~~~ int LocateElem(SqList *L, ElemType e) { for(int i=0;i<L->length;i++){ if(L->data[i]==e){ printf("The elem is found!The Postion is %d !", i+1); return i+1; } } printf("The elem isn't found!\n"); return -1; } ~~~ 最佳情況：需要查找的元素就在表頭，僅需比較一次，其時間復雜度為O(1)； 最壞情況：需要查找的元素就在表尾，需要比較n次，時間復雜度為O(n)； 平均情況：假設pi(pi=1n)是查找第i個位置上節點的概率，則在長度為n的線性表中查找值為e時所需比較的平均次數為 ∑i=1npi×i=∑i=1n1n×i=1n∑i=1n(n?i)=1n×n(n+1)2=n+12 因此，線性刪除算法的平均事件復雜度為O(n)。