線性順序表的實現
題外話
數據結構確實是與計算機不相關專業學生頭疼的一門課，大致可以了解清楚，但是卻不知道怎麼實現。這裡我將我的想法和一些代碼開源，供大家討論，如有錯誤，請指出，哈哈，廢話少說，咱們今天先來看一看線性表的順序實現吧！
什麼是線性順序表
線性表就是數據排成一條鏈的表，例如a->b->c->d->e->f......，是吧。很簡單，最簡單的線性順序表就是數組（我是這麼認為的）。實現它的時候只需要開闢一段連續的空間，然後將前後關聯起來，實現一些基本的操作，像查找、插入、刪除、遍歷、初始化、清空等。。。。。。
如何構造一個順序表？
順序表就是一個數組，所以我們需要一個數組，然後再拿一個整數來記錄它的大小就可以了。所以這是一個新的數據類型，就要用到結構體。結構體像這樣：
typedef struct list{ int *data; int len;}l;
data是一個指針，指向整數的，我們為它開闢一段連續的空間就可以當作數組使用啦！len是用來記錄這個表的大小的。下面我們一個一個來實現它的基本操作。以下的代碼全都是c語言代碼，可以複製直接使用。
初始化一個線性順序表
int init_list(l *a) { a->data = (int *)malloc( sizeof(int) * length); a->len = 0; memset(a->data,a,sizeof(int)*length); if(!a->data) { printf( "List init error!
"); return ER; } else { printf( "List has init!
"); return OK; } }
這裡實現順序表要用到指針的知識，如果不會的小夥伴請仔細看教程哦！
l *a是將a的首地址傳入init_list函數，然後就可以對a這個結構體進行操作了，先實用malloc函數分配length這麼大的空間，length這裡我取的100，然後將len設為0,再將數組所有元素設置為『a』，你們知道為什麼嗎？這裡留一個懸念，哈哈！
如果data是空的，就代表沒有成功，返回錯誤，這裡ER我設為1,OK設為0,如果成功則返回OK。至此順序表的初始化就完成了。接下來我著重講一講插入、刪除、遍歷。
線性表的插入
int insert_elem(l *a,int i,int n) { int j; if(a->len <= length - 1 && i < length && i >= 1) { for(j = a->len -1;j > i-2;j--) a->data[j+1] = a->data[j]; a->data[i-1] = n; if( i> a->len) a->len = i; else a->len ++; printf("you have inserted %d
",n); return OK; } else { printf("error!
"); return ER; } }
在進行插入之前我們要判斷表的長度是否在插入之後會超過總長度，這裡就是判斷len是否小於等於length-1，還要判斷需要插入的下標是否在總長度之內，不能超過總長度，也不能小於1,滿足以上條件則說明可以進行插入操作，否在就輸出錯誤信息，返回錯誤。
插入的情況有兩種，1。如果它裡面本來就是n個元素，在n個元素裡面進行插入，那麼就只需要將插入位置及其以後的位置向後移一位，然後將插入位置賦值為插入的值，然後len加一。2。如果插入的元素在這n個元素之後，那麼需要將要插入的下標賦值給len，然後就完事兒了。返回正確信息。
線性表的刪除
這裡是刪除操作的代碼
int delete_elem(l *a,int n) { int i,j; if(locate_elem(a,n,&i) && !isempty(a)) return ER; for(j = i;j<a->len;j++) a->data[j-1] = a->data[j]; a->data[a->len - 1] = a; a->len --; chaxun(a); return OK; }
與插入操作相似，我們在進行刪除操作之前，需要判斷我們刪除的元素是否在這個表裡面，就是locate_elem這個函數：
int locate_elem(l *a,int n,int *i) { int b,c = 0; for(b = 0;b < a->len;b++ ) { if(a->data[b] == n) { c = 1; *i = b+1; printf("the location is %d
",*i); return OK; } } if( c == 0) return ER; }
該函數是查詢一個元素是否在這個表裡面，如果在就返回這個元素在表裡面的下標，如果不在就返回錯誤信息。
然後我們再判斷這個表是否是空表，如果是空表那還刪除啥，直接返回錯誤就行，判斷是否是空表很簡單，我就不貼代碼了，哈哈，放心總的代碼我會給出來的。
滿足上述條件之後就可以刪除啦，找到需要刪除的位置，然後將該位置後面的元素一一往前移一個位置，之前的最後一個位置我們需要將它置為『a』，為什麼？這裡和上面一樣，賣個關子。
大家也看到了，我刪除元素的代碼裡面有個chaxun函數，這是用來幹什麼的呢？我來解釋一下，假如當前表內有n個數，以前大家寫的代碼都是默認插入位置不會超過n，所以沒有將表的值初始化為特定的值，這裡我們考慮到如果插入位置超過n了怎麼辦？我的想法是，在初始化的時候就將表內元素全部設定為『a』，然後在插入的時候，如果插入位置超過n（n為當前已經有的元素個數），則將插入位置賦值給len就好了，在刪除的時候要考慮出現則中情況：10aaa89aaa，這時我們就需要將最後的aaa去掉，我的辦法是利用遞歸的方式從最後開始查詢，如果最後一個是a，len就減一，這樣一來就保證了不會輸出a了。
我的chaxun函數代碼如下：
int chaxun(l *a){ int i; if((char)a->data[a->len - 1] == a) { a->len --; chaxun(a); } else return OK;}
線性表的遍歷
首先貼出我的代碼：
int tra_list(l *a) { int i; if(!isempty(a)) { printf( "it is empty!
"); return ER; } for( i = 0;i<a->len;i++) { if((char)a->data[i] != a) printf( "%d ",a->data[ i]); else printf( "0 "); } printf( "
"); return OK; }
先判斷表是否是空的，如果不是空的就一個一個輸出，我們最初設置的初值是『a』，如果遇到a則輸出0,否則就輸出元素。
還有線性表的其他操作請大家參考我的代碼或是其他人的代碼進行理解啦，當然我的代碼也是很垃圾，請看了之後在心裡默念sb就行，別說出來，傷和氣（笑哭）！
我的代碼在github上哦！lijunhon/data_structure
推薦閱讀：