學習順序線性表

來自專欄 前端數據結構與演算法

這是開專欄發的第一篇文章，有點小激動啊~因為不是計算機專業想掌握一下數據結構與演算法所以開了這樣一個專欄，順便複習一下c的語法。其實學習數據結構和演算法也不是必須看c實現的，但是畢竟c涉及到了內存分配釋放，不會像js一樣後台都做好了...所以覺得還是了解一下。by the way，數據結構是在MOOC里聽了浙江大學陳姥姥和何大大的課，個人感覺講的很好的！

本文主要是用c語言表示一下順序線性表這種數據結構，源碼在這裡，要是有不對的地方也歡迎大家提出來，我會虛心學習並改正的。

首先來介紹一下線性表，線性表是由同類型數據元素構成有序序列的線性結構，表中元素個數稱為線性表的長度，線性表中沒有元素時，稱為空表。表的起始位置稱表頭，表結束位置稱表尾。

而順序線性表就是內存中連續存放的線性表，可以理解成它的存放地址是一個數組。

所以就有了這樣的數據結構：

typedef struct { ElementType Data[MAXSIZE]; int Last;}List;

這裡用typedef struct定義了一個結構體，這個結構體里的Data數組是連續的存儲位置，Last可以理解為指向最後一個元素的指針類似物...MAXSIZE可以指定為想存放元素的最大個數，ElementType可以指定為任意類型，如int，float等，而List則是這個結構體的名稱。

在這裡有兩種方法可以訪問結構體內乃至線性表內的元素，若是將List「實例化」，就像下面這樣：

List L;

則說明L是List類型的變數，此時可以用L.Data[i]來訪問下標為i的元素，用L.Last+1訪問到線性表的長度。

但是也可以定義一個結構體指針變數，像下面這樣：

List *PtrL;

這裡的PtrL就指向了線性表的初始位置，此時可以用PtrL->Data[i]來訪問下標為i的元素，用PtrL->Last+1訪問長度。（至於為什麼加1可以看下面的代碼，其實也可以定義成不加1）

本文使用的是後者，其實是一樣的大家都可以試一下。

初始化空的線性表

List *MakeEmpty() { List *PtrL; PtrL = (List *)malloc(sizeof(List));// 分配空間 PtrL -> Last = -1;// 沒有元素，尾地址賦值為-1 return PtrL;}

函數上面加了*是因為返回的PtrL是指針類型，這裡的Last指向了-1，所以在第一個元素進去之後才會變成0，自然長度就是Last+1啦~

這裡還要注意的是malloc函數，這個函數是分配空間函數，會返回分配後的首地址。這個函數是在頭文件<stdlib.h>中定義的，所以不要忘了調個包。

PtrL = (List *)malloc(sizeof(List));

這句的意思是分配List長度的空間然後返回首地址再將其轉換為List類型返回給PtrL。

插入（時間複雜度為O(n)）

void Insert(ElementType X, int i, List *PtrL) { int j; if (PtrL -> Last == MAXSIZE -1) { printf("表滿"); return; } if (i < 1 || i > PtrL -> Last + 2) { printf("位置不合法"); return; } for (j = PtrL -> Last; j >= i - 1; j--) { PtrL -> Data[j + 1] = PtrL -> Data[j]; } PtrL -> Data[i - 1] = X; PtrL -> Last++; return;}

因為沒有定義返回值，所以函數類型是void，但也可以自行定義幾個標識符，然後作為標誌返回一下。

這裡的插入考慮了位置不準確，表滿了等情況，其實表滿了的話可以定義一個餘量再行分配。注意到了嗎在插入的時候每個指定位置後面的元素都要向後移...這就是c和js數組存儲的不同。

查找（時間複雜度為O(n)）

int Find(ElementType X, List *PtrL) { int i = 0; while (i <= PtrL -> Last && PtrL -> Data[i] != X) i++; if (i > PtrL -> Last) return -1;// 找不到則返回-1 else return i;}

這種存儲方式按下標查找的話要簡單一些，要是按值查找則需要挨著遍歷一下下。

刪除（時間複雜度為O(n)）

void Delete(int i, List *PtrL) { int j; if (i < 1 || i > PtrL -> Last + 1) { printf("不存在第%d個元素", i); return; } for (j = i; j <= PtrL -> Last; j++) { PtrL -> Data[j - 1] = PtrL -> Data[j]; } PtrL -> Last--;}

這是按下標刪除，之所以時間複雜度是O(n)完全是因為後面的元素要挨個前移。

要是在js中則直接用數組實現比這不知道方便到哪裡去了...比如初始化就是定義一個數組，插入就是某個下標對應某個值，刪除可以用splice，查找就更不用說了。但是依然想了解一下呀，畢竟多了解也沒有壞處。

不過這樣的代碼是無法編譯運行的呀，畢竟c需要一個main函數，那就順便當測試了。

void main() { List *l = MakeEmpty(); Insert(2, 1, l); Insert(3, 2, l); Insert(4, 3, l); int a = Find(3, l); printf("%d", a);// 1 int b = Find(5, l); printf("%d", b);// -1 Delete(1, l); int c = Find(2, l);//-1 printf("%d", c);}

本文暫時結束，有不足之處歡迎評論或私信指出！

推薦閱讀：