下面這張圖是線性表插入數據的原理圖：

算法2.3：一般情況下，在第（1<=i<=n）個元素之前插入一個元素時，需將第n至第i（共n-i+1）個元素向后移動一個位置。

我們來看看書上提供的偽代碼：

Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在順序線性表L的第i個元素之前插入新的元素e，// i的合法值為1≤i≤ListLength_Sq(L)+1ElemType *p;if (i < 1 || i > L.length+1) return ERROR; // i值不合法if (L.length >= L.listsize) { // 當前存儲空間已滿，增加容量ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType));if (!newbase) return ERROR; // 存儲分配失敗L.elem = newbase; // 新基址L.listsize += LISTINCREMENT; // 增加存儲容量}ElemType *q = &(L.elem[i-1]); // q為插入位置for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;// 插入位置及之后的元素右移*q = e; // 插入e++L.length; // 表長增1return OK; } // ListInsert_Sq
我們來分析下：

1.有一個叫Status的函數，顧名思義這是泛指某一狀態，因為c語言沒有泛型這個概念（C++中的tempate）所以書中用Status表示，可能是int，可能是double等等。

2.當i不再合法范圍時，我們看到了一個ERROR這個，我估計這是一個宏（#define）可能是-1或者其他值。

3.當存儲空間滿了時他調用了realloc函數，這個函數全稱是reallocate，顧名思義重新分配，

4.LISTINCREMENT是一個宏，值為10，意思是線性表增加10。

5.定義了兩個元素類型指針（一個是p，一個是q），先把q指向要插入的元素前面那個元素（里面的elem也是元素類型指針）。

6.for循環這塊，先把p指向順序表最后一個元素（從0開始，所以要L.length-1），當p指到q后面的元素時循環成立，然后，p不停的前移。

7.在for循環里面，依次i把元素后移。

下面是刪除

算法2.4：一般情況下，刪除第i（1<=i<=n）個元素時將從第i+1至第n（共n-i）個元素依次向前移動一個位置

偽代碼如下：

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 算法2.5// 在順序線性表L中刪除第i個元素，并用e返回其值。// i的合法值為1≤i≤ListLength_Sq(L)。ElemType *p, *q;if (i<1 || i>L.length) return ERROR; // i值不合法p = &(L.elem[i-1]); // p為被刪除元素的位置e = *p; // 被刪除元素的值賦給eq = L.elem+L.length-1; // 表尾元素的位置for (++p; p<=q; ++p) *(p-1) = *p; // 被刪除元素之后的元素左移--L.length; // 表長減1return OK; } // ListDelete_Sq
下面我們來分析下：

1.前面幾行到上面那了例子分析過來，在此不再分析。

2.因為下標是從0開始，所以刪除第i個元素時為L.elem[i-1]。

3.q=L.elem+L.length-1我們分析下。這個是使得q指向鏈表的尾部。

4.for循環里面p先+1，當p>q時循環才停止，而在循環中，可知把p的值網前一個覆蓋。

算法2.5：在線性表中查找指定元素的位置

下面是書上提供的偽代碼。

int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType)) {// 在順序線性表L中查找第1個值與e滿足compare()的元素的位序。// 若找到，則返回其在L中的位序，否則返回0。int i;ElemType *p;i = 1; // i的初值為第1個元素的位序p = L.elem; // p的初值為第1個元素的存儲位置while (i <= L.length && !(*compare)(*p++, e)) ++i;if (i <= L.length) return i;else return 0; } // LocateElem_Sq 下面我們來分析下：

1.這個LocateElem函數是看元素是坐落在哪，返回值是int說明他返回位置，一個參數是線性表，第二個參數是元素類型，第三個個參數我們可以理解為這是一個比較功能，并且我們從下面的那個while語句可以得知，這個compare函數當兩參數值不相等時返回0，相等時返回1。

2.還有，我們可以看見一個這程序的一個思路，當找不到，或者出現某種其他錯誤時，他返回0。

算法2.6：已知順序線性表La和Lb的元素按值非遞減排列，歸并La和Lb得到新的順序線性表Lc，Lc的元素也按值非遞減排列

下面是書上的代碼：

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa = La.elem; pb = Lb.elem;Lc.listsize = Lc.length = La.length+Lb.length;pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));if (!Lc.elem)exit(OVERFLOW); // 存儲分配失敗pa_last = La.elem+La.length-1;pb_last = Lb.elem+Lb.length-1;while (pa <= pa_last && pb <= pb_last) { // 歸并if (*pa <= *pb) *pc++ = *pa++;else *pc++ = *pb++;}while (pa <= pa_last) *pc++ = *pa++; // 插入La的剩余元素while (pb <= pb_last) *pc++ = *pb++; // 插入Lb的剩余元素 } // MergeList
分析如下：

1.函數為MergList_Sq什么我們這點這是混合鏈，參數可知Lc是要被修改的，與已知相符。

2.代碼中有一個exit(OVERFLOW)，這里面exit()里面的參數是一般是整數，所以我們可以知道這個OVERFLOW是宏，可能是-1，0，1，意思為溢出。

3.這里有一個算法，在第一個while里面把pa與pb指向的值進行比較，誰小把誰放到Lc，當有一個鏈到最后時，循環結束，進入第二個或第三個while，把另外那條鏈，剩下的加進去（都是非遞減排列的）。

總結

以上是生活随笔為你收集整理的2.2线性表的顺序表示和实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。