"磨棱角，褪優(yōu)越，沉下心"
"不止于心動，更付諸于行動，執(zhí)行力！“
前言
繼續(xù)之前的學習梳理，已經(jīng)停了一段時間了，這段時間主要是中途去做一個項目被耽擱了，現(xiàn)在將繼續(xù)學習整理，好記性不如爛筆頭，還是得寫寫記記，東西太多，記憶總是有限的。上一篇主要梳理了線性表的順序存儲的基本的概念和代碼的實現(xiàn)，本文將接著前面的梳理，主要涉及順序表的按值查找元素的位置、在線性表中任意位置插入元素、在線性表中任意位置刪除元素的相關(guān)操作。
順序表的按值查找位置
思路：
從線性表L中查找與指定值e相同的數(shù)據(jù)元素的位置。從表的一端開始，逐個進行記錄的關(guān)鍵字和給定值的比較。找到，返回該元素的位置序號，未找到，返回0。
這里是查找指定元素的位置，和前面查找指定位置的元素區(qū)分開
代碼實現(xiàn)
說明：
- 使用的平臺：VC2010
- 這里代碼沿襲了上一章的代碼，在原來基礎(chǔ)上增加函數(shù)。（不能直接復制下述代碼運行）
//線性表中查找指定元素的位置信息
//法一
unsigned int LocatingEleme1(SqList L,ElemType e)
{
unsigned int i;
for(i = 0; i< L.length; i++)
{
if(L.elem[i] == e)
{
return (i+1);
}
}
return FALSE;
}
//法二
unsigned int LocatingEleme2(SqList L,ElemType e)
{
unsigned int i=0;
while(i< L.length && L.elem[i] != e)//如果在線性表長度范圍內(nèi)，未掃描到指定元素，則一直循環(huán)
{
i++;
//return i;
}
if(i < L.length)// 查詢成功，如果上面沒有查詢成功，i = L.length,不會進入這里，如果查詢成功，i需要加1輸出實際的位置
{
return i + 1;
}
return FALSE;
}
運行結(jié)果：
從算法復雜度簡要分析上述操作：
查找的基本操作為：將記錄的關(guān)鍵字同給定值進行比較，然后輸出位置。
（固定值在表中的位置不確定下，可能是第一個一下子就找出來，可能是最后一個或者不存在那就要把表中的元素全部輪詢一遍）
下面引入：
平均查找長度ASL（Average Search Length）：為確定記錄在表中的位置，需要與給定值進行比較的關(guān)鍵字的個數(shù)的期望值叫做查找算法的平均查找長度。
對含有n個記錄的表，查找成功時：
Pi 是第i個記錄被查找的概率，Ci 是找到第i個記錄需比較的次數(shù)。
順序查找的平均查找長度：
假設每個記錄的查找概率相等：Pi = 1/n 。
順序表插入新元素
思路：
插入新元素是在順序表的第i（1<=i+1<length+1）位置上，新增一個結(jié)點e,使長度為n的線性表變成長度為n+1的線性表。
和前面那些操作一樣，我們需要去考慮操作位置的合理性。
算法步驟
- 判斷插入位置i是否合法。
- 判斷順序表的存儲空間是否已滿，若已滿返回ERROR。
- 將第n至第i位的元素依次向后移動一個位置，空出第i個位置。
- 將要插入的新元素e放入第i個位置。
- 表長加1，插入成功返回OK。
注：就是需要處理的是插入位置后面的元素要一一往后跑的操作！
代碼實現(xiàn)：
說明：
- 使用的平臺：VC++2010
- 這里代碼沿襲了上一章的代碼，在原來基礎(chǔ)上增加函數(shù)。（不能直接復制下述代碼運行）
- 主要是學習方法思路，代碼設計上其實還存在一些瑕疵，可以優(yōu)化完善的
//線性表中指定位置插入新結(jié)點元素
unsigned int InsertElement(SqList *L, int i,ElemType e)
{
int j;
//判斷指定位置是否合法
if(i < 1 || i > L->length+1)
{
return FALSE;
}
//如果線性表的空間已經(jīng)存滿
if(L->length == MAXSIZE)
{
return FALSE;
}
//插入位置及以后的元素后移(從最后一個開始依次移動)
for(j = L->length - 1; j >= i - 1; j--)//注意j=0的情況，j=0會執(zhí)行循環(huán)，執(zhí)行后j會減1
{
L->elem[j + 1] = L->elem[j];
printf("j = %d;i = %d\n",j,i);
}
L->elem[i - 1] = e;//將新元素e放入第i個位置
L->length++;//表長增1
return OK;
}
代碼運行結(jié)果：
注意
在上面這個代碼調(diào)試書寫中，需要注意程序中的i和j的類型，最開始兩個值我寫了無符號數(shù)類型，在1號位置插值發(fā)生錯誤，原因就在我之前分享的有無符號數(shù)大小比較問題里面，那里j=0執(zhí)行循環(huán)后，會減1再和表達式2比較判斷，如果是無符號數(shù)，減1 后變成了最大值，然后又會滿足條件，具體可以實操試試看看..............
調(diào)試出現(xiàn)錯誤的結(jié)果：
從算法復雜度簡要分析上述操作：
上述中，插入位置不同，for循環(huán)執(zhí)行的次數(shù)不一樣，在最后一個位置插入時，不用執(zhí)行循環(huán)即可插入，依次往前，次數(shù)會增加；插在第一個位置時需要將所有元素都往后移動，耗時最多。算法時間主要用于移動元素去了。
分析出現(xiàn)的情況有n+1種，復雜度計算：
平均時間復雜度為：O（n）;
刪除順序表指定元素
思路：
刪除和插入類似，刪除元素是在順序表的第i（1<=i+1<length+1）位置上，刪除一個結(jié)點e,使長度為n的線性表變成長度為n-1的線性表。
算法步驟
- 判斷刪除位置i是否合法
- 將欲刪除的元素保留在e中。
- 將第i+1至第n位的元素依次向前移動一個位置。
- 表長減1，刪除成功返回OK。
代碼實現(xiàn)
- 使用的平臺：VC++2010
- 這里代碼沿襲了上一章的代碼，在原來基礎(chǔ)上增加函數(shù)。（不能直接復制下述代碼運行）
- 主要是學習方法思路，代碼設計上其實還存在一些瑕疵，可以優(yōu)化完善的
//線性表中指定位置刪除元素
unsigned int DeleteElement(SqList *L, int i)
{
int j;
//判斷指定位置是否合法
if(i < 1 || i > L->length+1)
{
return FALSE;
}
//被刪除的元素依次往前移動占位(從靠近刪除元素的位置開始依次移動)
for(j = i; j <= L->length+1; j++)//注意j=0的情況，j=0會執(zhí)行循環(huán)，執(zhí)行后j會減1
{
L->elem[j - 1] = L->elem[j];
printf("j = %d;i = %d\n",j,i);//調(diào)試使用
}
L->length--;//表長減1
return OK;
}
運行結(jié)果
![]()
從算法復雜度簡要分析上述操作：
算法時間主要耗費在移動元素的操作上。
若刪除尾結(jié)點，則根本無需移動（特別快）；若刪除首結(jié)點，則表中n-1個元素全部前移（特別慢）；
順序表插入算法的平均時間復雜度為O(n)。
小結(jié)
本節(jié)主要記錄了線性表的按值查找元素的位置、表中增加新結(jié)點、刪除結(jié)點的三個操作。后兩個思路都差不多，都是要去移動操作位置后面的元素。根據(jù)思路可以自行寫代碼實現(xiàn)?？偨Y(jié)幾個小點：
- 傳入的順序表參數(shù)，需要傳入地址，不能直接傳入L（SqList L）。
- 在循環(huán)語句中作比較時需要考慮數(shù)據(jù)類型不同
- 減減操作一定要特別注意變量0減1后將會什么值
- 在插入結(jié)點設計時需要判斷儲存表的長度，存儲的空間是否還有空位存
- 上述的代碼主要學習思路，處理的方法，部分細節(jié)還有待優(yōu)化！
寫到這里，線性表的順序存儲方式差不多記錄完畢了，下一章將開始進行鏈式存儲的學習記錄了，也是很重要的知識點。
參考資料：
青島大學.王卓.數(shù)據(jù)結(jié)構(gòu)與算法
《數(shù)據(jù)結(jié)構(gòu) C語言版》.嚴蔚敏
歡迎關(guān)注本人微信公眾號：那個混子
記錄自己學習的過程，分享樂趣、技術(shù)、想法、感悟、情感！
單片機類嵌入式交流學習可加企鵝群：120653336
