程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 動態分配的順序線性表的十五種操作—C語言實現

動態分配的順序線性表的十五種操作—C語言實現

編輯:關於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的元素時不時的移動,耽誤時間。   故,當使用線性表表示數組或者集合等等吧,進行操作的時候,最好是先給表排序,或者有歸並,則歸並到新的空表。       到此,關於線性表裡的順序表的概念和常用算法就算分析完畢,經常用的操作的是初始化,銷毀,清空,判空,定位,插入,刪除,遍歷,前驅,後繼,賦值,得到元素,求長度,接下來分析的是經常用到的鏈表。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved