動態分配的順序線性表的十五種操作—C語言實現
線性表
定義：是最常用的，也是最簡單的數據結構，是長度為n個數據元素的有序的序列。
含有大量記錄的線性表叫文件
記錄：稍微復雜的線性表裡，數據元素為若干個數據項組成，這時把一個數據元素叫記錄
結構特點：在非空有限的條件下，存在唯一的一個表頭結點，唯一的一個表尾結點，除去第一個元素之外，每個數據元素都只有一個前驅，除去最後一個元素之外，每一個數據元素都只有一個後繼。
注意：線性表中的數據元素可以是各種各樣的，但同一線性表中的元素必定具有相同特性（屬於同一數據對象，類似數組）。線性表的數據元素間有序偶關系。
線性表的順序表示和實現
有一組地址連續的內存單元，在這些連續的內存單元裡，順次地存儲線性表裡的數據元素
特點：邏輯地址和物理地址都是連續的，適合隨機存取。假設&a1為線性表的基址，每個數據元素占據L個存儲單位。那麼表裡第i個元素的存儲地址：
&a（i） = &a（1） + （i - 1）x L
線性表的順序表示結構（順序映象）也叫順序表，順序表中元素的邏輯關系和物理位置一致，是一種隨機存取的存儲結構。
（類似高級語言裡的數組，通常用數組描述數據結構的順序存儲結構）。
如果用數組表示順序表，那很簡單，也不實用，不能改變存儲容量，下面是動態分配的順序表的表示和操作
ADT.h頭文件
頭文件
ADTList.c文件
復制代碼
1 /************************************************************************/
2 /*函數定義在此文件 */
3 /************************************************************************/
4 #include "ADT.h"
5 /************************************************************************/
6 /*第一類：初始化操作，記住各種數據結構開始使用都要初始化 */
7 /************************************************************************/
8
9 //注意c數組下標從0開始，但是用戶並不知道，一般都是選擇從1到length的位置，以用戶的角度看問題
10
11 //1、線性表的初始化，構造一個空的線性表,因為要改變線性表，必須用指針做參數
12 int InitList(SqList *L)
13 {
14 //在堆中為線性表分配內存,初始化elem為該內存空間的首地址（基址）
15 L->elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));//結構裡只是存儲了表的地址值，而表本身存儲在其他地方
16 //判斷是否分配成功
17 if (!L->elem)//如果 !L->elem 為真（為空），執行下面代碼
18 {
19 printf("線性表內存分配失敗！退出程序。\n");
20 exit(1);//函數異常退出，返回給操作系統1
21 }
22 //表內存空間分配成功
23 L->length = 0;//開始是空表,沒有存儲任何元素，故表長置為0
24 //當前為線性表分配的存儲容量
25 L->listsize = LIST_INIT_SIZE;//初始化表的存儲容量，這是當前表最大的存儲量
26 return 0;//分配成功返回0
27 }
復制代碼
雖然在堆開辟了一塊內存空間給線性表，但是需要設置一個變量listsize，來顯式的表明表的最大存儲容量的數值，方便程序使用（分配的空間內存大小和表長是兩回事，表長是表內當前的元素個數，也就是此時線性表當前的存儲容量）
復制代碼
1 /************************************************************************/
2 /*第二類：銷毀操作，記住各種數據結構使用了都要有銷毀的步驟 */
3 /************************************************************************/
4
5 //2、釋放內存，銷毀表操作,直接把內存釋放的操作！類似free（）和c++的delete操作符
6 //注意：用malloc函數分配的空間在釋放時是連續釋放的，即將物理地址相鄰的若干空間全部釋放
7 //所以順序表銷毀可以只釋放基址，就自動釋放所有空間，而鏈表要一個一個的把節點刪除
8 void Destory(SqList *L)
9 {
10 if (L->elem)//如果當前表還存在
11 {
12 free(L->elem);//銷毀之
13 //內存都沒了，整個表也就不存在了，別的不用管。
14 printf("本線性表已銷毀！\n");
15 }
16 }
復制代碼
注意：用malloc函數分配的空間在釋放時是連續釋放的，即將物理地址相鄰的若干空間全部釋放,所以順序表銷毀可以只釋放基址自動釋放所有空間，而鏈表要一個一個的把節點刪除
復制代碼
1 /************************************************************************/
2 /* 第三類：引用型操作，操作不改變線性表裡的數據元素，也不改變他們之間的關系
3 /************************************************************************/
4
5 //3、判空操作
6 void ListEmpty(SqList L)
7 {
8 //判斷表是否存在
9 if (L.elem)
10 {
11 //判斷是否存儲了內容
12 if (0 == L.length)
13 {
14 puts("本表為空!");//自動換行
15 }
16 else
17 {
18 puts("表不為空！");
19 }
20 }
21 else
22 {
23 puts("表不存在!");
24 }
25 }
復制代碼
0 == L.length，個人喜歡這種寫法，避免出錯，如果一時疏忽，寫=，則編譯報錯！常量不能作為左值出現，來提醒自己
復制代碼
1 //4、求長度操作，若線性表已經存在，則返回表L中元素個數
2 int ListLength(SqList L)
3 {
4 if (L.elem)
5 {
6 return L.length;
7 }
8 puts("表不存在，無法求長度！");
9 return 0;
10 }
復制代碼
復制代碼
1 //5、定位操作：線性表 L 已存在，返回 L 中第 1 個與 e 滿足相等關系的元素位置。
2 int LocateElem(SqList L, int e)
3 {
4 int i;//定位
5 for (i = 0; i < L.length; i++)
6 {
7 //數組名本身就是數組的首地址
8 if (e == L.elem[i] && i < L.length)
9 {
10 printf("定位成功，該元素的位置 = %d\n", i + 1);
11 return i + 1;
12 }
13 }
14 puts("定位失敗！沒有找到該元素");
15 return 0;
16 }
復制代碼
個人覺得因為已經有初始化操作和判空操作，則其余函數不用再寫判斷表存在否的語句
c的數組下標從0開始，但是還是習慣1對應第一個數據元素，以此類推……
1、定位算法的時間復雜度分析
假設表長為n
最好的情況，如果第一個元素就滿足關系，那麼時間復雜度為0(1)
最壞的情況，如果最後一個元素滿足關系或者沒有滿足關系的（依然還是比較了），時間復雜度為0（n）
2、算法平均時間復雜度：
顯然是和表長成正比的，為0（n）
復制代碼
1 //6、求元素後繼，線性表 L 已存在。若 cur_e是 L 中的元素，返回後繼
2 void NextElem(SqList L, int cur_e)
3 {
4 int i = LocateElem(L, cur_e);//先定位參照元素的位置
5
6 if (0 != i)
7 {
8 if (i == L.length)
9 {
10 puts("這是最後一個元素，沒有後繼！");
11 }
12 else
13 {
14 printf("%d的後繼是%d\n", L.elem[i - 1], L.elem[i]);
15 }
16 }
17 else
18 {
19 puts("表中沒有這個元素！");
20 }
21 }
復制代碼
注意：區分數組角度看問題和用戶角度看問題，表長范圍等不要混淆。
復制代碼
1 //7、得到指定的元素值，線性表 L 已存在, e 返回 L 中第 i 個元素的值。
2 int GetElem(SqList L, int i, int e)
3 {
4 if (i < 1 || i > L.length)
5 {
6 puts("超出了查找范圍，重新輸入！");
7 return 0;
8 }
9 e = L.elem[i - 1];
10 return e;
11 }
復制代碼
這裡沒有打印，只是返回了值，不太好，因為出現了一個問題，函數內部的e是局部變量，且是值傳遞參數類型，函數執行完畢，e的內存消失，不再起作用，對實參沒有影響。在函數外打印e的值得不到正確值
復制代碼
1 int GetElem(SqList L, int i, int *e)
2 {
3 if (i < 1 || i > L.length)
4 {
5 puts("超出了查找范圍，重新輸入！");
6 return 0;
7 }
8 *e = L.elem[i - 1];
9 printf("%d\n", *e);
10 return *e;
11 }
復制代碼
改進：或者增加函數內的打印語句，或者把e變為指針類型的變量，可以修改實參，相應的聲明裡也要修改！
復制代碼
1 /8、求元素前驅，線性表L已經存在，若cur_e是L的數據,則返回前驅
2 void PriorElem(SqList L, int cur_e)
3 {
4 int i = LocateElem(L, cur_e);//如果定位失敗返回0
5
6 if (0 != i)
7 {
8 if (1 == i)
9 {
10 puts("這是第一個元素，沒有前驅！");
11 }
12 else
13 {
14 printf("找到了%d的前驅%d \n", L.elem[i - 1], L.elem[i - 2]);
15 }
16 }
17 else
18 {
19 puts("找不到這個元素！");
20 }
21 }
復制代碼
注意一下： L.elem[i - 1]和 L.elem[i - 2]與i的關系
復制代碼
1 //9、遍歷表中元素，線性表 L 已存在，打印出表中每個元素
2 void ListTraverse(SqList L)
3 {
4 int i;
5
6 for (i = 0; i < L.length; i++)
7 {
8 printf("%5d", L.elem[i]);
9 }
10
11 }
復制代碼
%5d，寬度為5打印輸出
復制代碼
1 /************************************************************************/
2 /* 第四類：加工型操作 */
3 /************************************************************************/
4
5 //10、把表清空（不釋放內存），線性表 L 已存在，將 L 重置為空表。
6 void ClearList(SqList *L)
7 {
8 if (L->elem)
9 {
10 L->length = 0;//順序表置空，表長為0即可
11 }
12 }
復制代碼
和銷毀內存區分
復制代碼
1 //11、給表元素賦值，線性表 L 已存在，1≤i≤LengthList(L)
2 //L 中第 i 個元素賦值為 e
3 void PutElem(SqList *L, int i, int e )
4 {
5 if (i < 1 || i > L->length)
6 {
7 puts("超出表范圍！");
8 }
9 L->elem[i - 1] = e;
10 }
復制代碼
常用的，也是比較重要的插入和刪除算法
復制代碼
1 //12、插入操作，線性表 L 已存在，1≤i≤LengthList(L)+1。在 L 的第 i 個元素之前插入新的元素 e，L 的長度增 1。
2 void ListInsert(SqList *L, int i, int e )
3 {
4 SqList *NL;//聲明一個額外的結構指針指向重新分配的表內存空間
5 int *j;
6 int *k;
7 //注意c數組下標從0開始，但是用戶並不知道，一般都是選擇從1到length的位置，以用戶的角度看問題
8 //在元素i之前插入，則把i和i後面的全部元素順次後移一位
9 if (i < 1 || i > L->length + 1)//最後一個元素後一位插入合法，不用移動直接插即可
10 {
11 puts("超出表范圍！");
12 }
13 //考慮問題要全，因為可能會不止一次插入操作，早晚會超出表的存儲容量
14 else if (L->length >= L->listsize)
15 {
16 //重新分配內存，增加存儲空間
17 NL->elem = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
18 if (!NL->elem)//分配失敗，返回NULL
19 {
20 exit(0);//退出
21 }
22 //分配成功
23 L->elem = NL->elem;//得到擴大之後的新基址
24 }
25 //指示用戶的實際插入位置
26 j = &(L->elem[i - 1]);//數組下標從0開始
27 //最後一個數據元素的實際位置是length-1
28 for (k = &(L->elem[L->length - 1]); k >= j; k--)//這裡k--不是1的減量！而是指針的減量操作，每次是int類型字節大小變化
29 {
30 *(k + 1) = *k;//從j到k的元素順次後移一位
31 }
32 *j = e;//完成插入
33 L->length++;//別忘表長加1
34 }
復制代碼
1、需要注意一下運算符優先級，箭頭（間接運算符）的優先級很高，高於取地址&
2、解析realloc函數
它可以對給定的指針所指的空間進行擴大或者縮小，原有內存的中內容將保持不變。對於縮小，則被縮小的那一部分的內容會丟失 ，realloc 並不保證調整後的內存空間和原來的內存空間保持同一內存地址。realloc 返回的指針很可能指向一個新的地址。因為realloc是從堆上分配內存，當擴大內存空間，realloc直接從堆上現存的數據後面的那些字節中獲得附加的字節，但如果數據後字節不夠，就用堆上第一個有足夠大小的自由塊，現存的數據被拷貝至新的位置，而老塊則放回到堆上。
在代碼中，如果我們采用i = (int*)realloc(i, 2*sizeof(int))的重新分配內存方式，有以下兩種情況：
分配成功：
realloc函數完成後，i 曾經指向的舊內存自動free掉。
分配失敗，返回NULL值：
此時，i 原來指向的內存還沒有被free掉，而現在又找不到地址，這樣就出現memory leak！
解決辦法：定義另一個指針j用於接收realloc返回值，判斷是否成功，成功則將 j 賦給 i
3、插入算法的時間復雜度分析：
問題規模是表的長度，值為 n。 算法的時間主要花費，在向後移動元素的 for 循環語句上。該語句的循環次數為 (n– i +1)，所需移動結點的次數不僅依賴於表的長度 n，而且還與插入位置 i 有關。
當插入位置在表尾 (i=n +1) 時，不需要移動任何元素；這是最好情況，其時間復雜度 O(1)。
當插入位置在表頭 (i = 1) 時，所有元素都要向後移動，循環語句執行 n 次，這是最壞情況，其時間復雜度 O(n)。
4、插入算法的平均時間復雜度：
設 pi 為第 i 個元素之前插入一個元素的概率，則在長度為 n 的線性表中插入一個元素時所需移動元素次數的期望值為
假設在n+1個位置上，插入的概率一樣，那麼pi = 1/(n+1)；
E = pi【（n）+（n-1）+ ……+ 3 + 2 + 1】 =pi x（ n（n+1）/ 2） = n / 2
由此可見，在順序表上做插入運算，平均要移動 一半元素。當表長 n 較大時，算法的效率相當低。 插入 算法的 平均時間復雜度為 O(n)。
復制代碼
1 //13、刪除操作，表 L 已存在且非空，1≤i≤LengthList(L)。刪除 L 的第 i 個元素，並用 e 返回其值，長度減 1。
2 void ListDelete(SqList *L, int i, int *e )
3 {
4 int *p;
5
6 if (i < 1 || i > L->length)
7 {
8 puts("i的值不合法！重新輸入！");
9 }
10 else
11 {
12 //找到被刪除元素的實際位置
13 p = &(L->elem[i - 1]);
14 *e = L->elem[i - 1];
15 //p（不包含p）後面的元素依次前移一位
16 for (; p < &(L->elem[L->length - 1]); p++)
17 {
18 *p = *(p + 1);
19 }
20 L->length--;
21 }
22 }
復制代碼
1、這裡e使用指針變量，這樣形參就可以修改實參！
2、刪除算法的時間復雜度分析
算法的時間主要花費在向前移動元素的 for 循環語句上。該語句的循環次數為 (n – i)。由此可看出，所需移動結點的次數不僅依賴於表的長度 n，而且還與刪除位置 i 有關。
當刪除位置在表尾 (i = n) 時，不需要移動任何元素；這是最好情況，其時間復雜度 O(1)。
當刪除位置在表頭 (i = 1) 時，有 n -1 個元素要向前移動，循環語句執行 n -1 次，這是最壞情況其時間復雜度 O(n)。
3、算法的平均時間復雜度：
設 qi 為刪除第 i 個元素的概率，則在長度為 n 的線性表中刪除一個元素時所需移動元素次數的期望值為
假設，每一個位置的元素被刪除的概率都一樣，那麼qi = 1 / n
E = qi【（n-1）+（n-2）+……+3+2+1】=1/n x （（n-1）n / 2）=（n - 1）/ 2
可見，在順序表上做刪除運算，平均也要移動表上 一半元素。當表長 n 較大時，算法的效率相當低。算法的平 均時間復雜度為 O(n)。
復制代碼
1 /************************************************************************/
2 /* 額外的幾個復雜操作 */
3 /************************************************************************/
4
5 //1、合並線性表AB，把在線性表B裡，但不存在於線性表A的元素插入到A中
6 //只改變A，不修改B
7 void Union(SqList *LA, SqList LB)
8 {
9 int i;
10 int e;
11 int lengthA = LA->length;
12 int lengthB = LB.length;
13
14 //在B裡依次取得每個數據元素，順序在A裡比較，若不存在則插入
15 for (i = 1; i <= lengthB; i++)
16 {
17 GetElem(LB, i, &e);
18 if (!LocateElem(*LA, e))//A裡沒有這個元素
19 {
20 //插入到A尾部
21 /*lengthA++;
22 ListInsert(LA, lengthA, e);*/
23 ListInsert(LA, ++lengthA, e);
24 }
25 }
26 Destory(&LB);
27 }
復制代碼
算法復雜度分析：
GetElem函數執行和表長沒有關系，插入函數每次都在最後一位插入，執行時間和表長也沒有關系，而LocateElem函數執行時間和表長有關系，無序合並算法的時間復雜度主要取決於LocateElem的執行時間，前面分析過，LocateElem時間復雜度：0（lengthA），那麼本算法的時間復雜度為：O（lengthA x lengthB）
復制代碼
1 //2、合並線性表AB，AB的元素按值非遞減有序的排列，要把A和B歸並為一個新表C，且C的元素依然是按照值非遞減的有序排列
2 void MergeList(SqList LA, SqList LB, SqList *LC)
3 {
4 InitList(LC);//構造新表c
5 int lengthA = LA.length;
6 int lengthB = LB.length;
7 int lengthC = LC->length;//C表初始化為空表,0
8 int i = 1;//i標記LA
9 int j = 1;//j標記LB
10 int iLA;
11 int jLB;
12
13 while ((i <= lengthA) && (j <= lengthB))
14 {
15 //分別取得元素值，比較
16 GetElem(LA, i, &iLA);
17 GetElem(LB, j, &jLB);
18 if (iLA <= jLB)//LA，LB都是非遞減排列
19 {
20 lengthC++;//總在末尾插入
21 ListInsert(LC, lengthC, iLA);
22 i++;
23 }
24 else
25 {
26 ListInsert(LC, ++lengthC, jLB);
27 j++;
28 }
29 }
30 //AB不會同時比完，一定會有一個表完全插入到c之後，另一表剩余
31 while (i <= lengthA)
32 {
33 GetElem(LA, i++, &iLA);
34 ListInsert(LC, ++lengthC, iLA);//本來AB就有序，直接全部插入到C末尾即可
35 }
36 //or
37 while (j <= lengthB)
38 {
39 GetElem(LB, j++, &jLB);
40 ListInsert(LC, ++lengthB, jLB);
41 }
42 }
復制代碼
算法時間復雜度分析：
不論表AB，哪個表，肯定有一個表先完全比完，比如是LA，比較了lengthA次。之後，兩個while語句，就執行一個，就是LB剩余的元素順次插入C表剩余次數的過程，加上之前LB和LA的比較次數，那麼綜合得其時間復雜度為0（lengthA + lengthB）
本算法的另一種思路，不依靠前面已經定義好，能拿來就用的函數，使用指針進行比較，賦值
復制代碼
1 //2、合並線性表AB，AB的元素按值非遞減有序的排列，要把A和B歸並為一個新表C，且C的元素依然是按照值非遞減的有序排列
2 void MergeList(SqList LA, SqList LB, SqList *LC)
3 {
4 //還是先構造表C，不用下標，只能使用指針來操作
5 LC->listsize = LA.length + LB.length;
6 LC->length = LA.length + LB.length;
7 int *c = (int *)malloc((LC->listsize) * sizeof(int));
8 int *a = LA.elem;
9 int *b = LB.elem;
10 int *lastA = LA.elem + (LA.length - 1) * sizeof(int);
11 int *lastB = LB.elem + (LB.length - 1) * sizeof(int);
12 LC->elem = c;
13 if (!LC->elem)
14 {
15 puts("c表構建失敗！");
16 exit(-1);
17 }
18 while (a <= lastA && b <= lastB)
19 {
20 if (*a <= *b)
21 {
22 *c++ = *a++;//從右到左運算，先計算*c = *a，後a++，c++
23 }
24 else
25 {
26 *c++ = *b++;
27 }
28 }
29 while (a <= lastA)
30 {
31 *c++ = *a++;
32 }
33 while (b <= lastB)
34 {
35 *c++ = *b++;
36 }
37 }
復制代碼
1、時間復雜度還是0（lengthA + lengthB）
2、這裡發現，當線性表的元素無序的時候，進行插入操作的時間復雜度比有序的時候的時間復雜度要大的多。
因為，有序的線性表AB，比如依次遞增（都不相等），則比較AB元素大小時，不用把B的每一個元素都和A比較！因為可以保證前面的元素肯定是小於後面的。這樣大大節省了運行時間！
3、還有發現如果是兩表歸並到新表裡，那麼新表開始就是空的，只需要依次插入即可（換句話說就是依次賦值即可），不用移動元素，而如果是A歸並到B裡（反之亦然），那麼保持有序的話，就需要B的元素時不時的移動，耽誤時間。
故，當使用線性表表示數組或者集合等等吧，進行操作的時候，最好是先給表排序，或者有歸並，則歸並到新的空表。
到此，關於線性表裡的順序表的概念和常用算法就算分析完畢，經常用的操作的是初始化，銷毀，清空，判空，定位，插入，刪除，遍歷，前驅，後繼，賦值，得到元素，求長度，接下來分析的是經常用到的鏈表。
