線性表
定義:是最常用的,也是最簡單的數據結構,是長度為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的元素時不時的移動,耽誤時間。
故,當使用線性表表示數組或者集合等等吧,進行操作的時候,最好是先給表排序,或者有歸並,則歸並到新的空表。
到此,關於線性表裡的順序表的概念和常用算法就算分析完畢,經常用的操作的是初始化,銷毀,清空,判空,定位,插入,刪除,遍歷,前驅,後繼,賦值,得到元素,求長度,接下來分析的是經常用到的鏈表。