線性表

順序存儲結構的插入與刪除

獲得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/* Status是函數的類型，其值是函數結果狀態代碼，如OK等 */
/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e返回L中第i個數據元素的值 */
Status GetElem(SqList L, int i, ElemType *e)
{if (L.length == 0 || i < 1 || i > L.length)return ERROR;*e = L.data[i - 1];return OK;
}
復制代碼

插入操作

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L)， */
/* 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 */
Status ListInsert(SqList *L, int i, ElemType e)
{int k;/* 順序線性表已經滿 */if (L->length == MAXSIZE)                       return ERROR;/* 當i不在范圍內時 */if (i < 1 || i >L->length + 1)                  return ERROR;/* 若插入數據位置不在表尾 */if (i <= L->length)                             {/*將要插入位置后數據元素向后移動一位 */for (k = L->length - 1; k >= i - 1; k--)    L->data[k + 1] = L->data[k];}/* 將新元素插入 */L->data[i - 1] = e;                             L->length++;return OK;
}
復制代碼

刪除操作

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{int k;/* 線性表為空 */if (L->length == 0)                    return ERROR;/* 刪除位置不正確 */if (i < 1 || i > L->length)            return ERROR;*e = L->data[i - 1];/* 如果刪除不是最后位置 */if (i < L->length)                     {/* 將刪除位置后繼元素前移 */for (k = i; k < L->length; k++)    L->data[k - 1] = L->data[k];}L->length--;return OK;
}
復制代碼

線性表的順序存儲結構，在存、讀數據時，不管是哪個位置，時間復雜度都是O(1)；而插入或刪除時，時間復雜度都是O(n)。

線性表順序存儲結構的優缺點

歡迎掃描下方二維碼，持續關注：

互聯網工程師（id:phpstcn），我們一起學習，一起進步