酷播亮新聞
非常人販2.jpg
通過第六篇文章的學習我們知道，線性表分為順序儲存和連式儲存兩種結構，他們各自有自己的儲存特點，在使用上也不同。
今天先學習下線性表的順序儲存，即數據結構中的
線性表
順序儲存的原理
我們在前邊將學習數據結構的物理結構時，學習到了線性表的順序儲存結構，應該對他的儲存原理有所瞭解了，即順序儲存，就是在儲存器中分配一段連續的儲存空間，邏輯上相鄰的資料元素，其物理儲存地址也是相鄰的，假如要用順序表來儲存4個字母，則需要在記憶體中分配4個連續的儲存單元
如下圖所示：
順序表儲存結構.png
我們看到，要儲存的4個字母被儲存到一段連續儲存空間中，由儲存空間的地址可以看出，這4個儲存單元是連續的，第一個儲存單元由序號0來標記，接下來的儲存單元依次遞增標記序號，這樣在查詢元素時，只要找到對應的索引就能找到嚴肅，非常的方便。
線性表的這種儲存方式成為順序儲存或者順序對映，又由於在邏輯上相鄰的兩個元素在對應的順序表中的儲存位置也相鄰，因此這種對映也成為直接對映。
在上方圖中，分配了4個儲存單元來儲存這4個字元，表的長度是4，容量也為4。但要注意的是，表的長度未必與容量相同，表的長度要小於等於表的容量，因為可能申請了4個儲存單元，但實際只存入3個元素。
順序表的特點
在順序儲存中，只要確定了線性表在儲存空間的起始位置，線性表中任何元素就都可以隨機存取，所以線性表的順序儲存結構是一種隨機存取的結構。在高階語言中，順序儲存使用陣列來實現的。
在順序儲存中，系統不需要為表元素之間的邏輯關係增加額外的儲存空間，而且在存取元素時，他可以根據給出的下表快速計算出元素的儲存位置，從而達到隨機讀取的目的。
例如，在上方的圖中，如果需要讀取第三個元素，因為他的序號為2，即與首元素的間隔為2，由記憶體段的起始位置0x001和元素間的差值可以快讀計算出這個元素的儲存地址為0x003,計算出地址後，就可以方便的操作該元素了。
但是，如果在順序表中插入或刪除元素，效率會特別低。
對於插入來說，只限於在表的長度小於表的容量的順序表，如果插入大量元素，很難保證控制元件是否充足。
而且一旦分配了儲存控制元件，如果想要擴充容量，需要重新分配控制元件，然後將原來的資料複製到新的控制元件中，非常麻煩；
另一方面，即使空間充足，在插入位置後的元素也必須要向後移動，效率非常低。
同理，如果要刪除大量元素，勢必會造成空間上的浪費，而且刪除元素後，後面的元素都要向前移動，效率也會非常低。
順序表（順序儲存）的實現
這裏我們用C語言完成一些順序表的基本操作，如：
查詢，插入，刪除等操作。
1、建立順序表
在建立順序表時，需要先建立一個頭結點l來存放順序表的長度、大小和地址等資訊，然後再建立順序表，同事將順序表的地址儲存到頭結點中，如下如示意圖所示：
順序表示意圖.png
實現思路如下：
（1）定義一個結構體struct來儲存順序表的資訊
（2）為頭結點分配空間
（3）為順序表分配空間，將順序表空間地址儲存在頭結點中。
（4）將頭結點地址返回給呼叫者。
ok，我們來看下程式碼
//第1步，建立結構體typeof struct SeqList{ //頭結點，記錄表的資訊 int capacity; //表容量 int length; //表長度 int *node; //node[capacity]即為指標陣列 }TSeqList;
//第2步，建立得到順序表的方法SeqList * seqList_Create(int capacity) //返回值為SeqList *型別，為順序表的地址{ int ret； TSeqList * temp=NULL; temp=(TSeqList *)malloc(sizeof(TSeqList));//為頭結點分配空間 if(temp==NULL) { ret=1; printf("func seqList_Create error:%dn",ret); return NULL; } memset(temp,0,sizeof(TSeqList)); temp->capacity=capacity; temp->length=0; temp->node=(int *)malloc(sizeof(void *)*capacity);//分配一個指標陣列 if(temp->node==NULL) { ret=2; printf("func SeqList_Create() error:%dn",ret); return NULL; } return temp;//返回建立好的順序表地址}
注：memset(temp,0,sizeof(TSeqList));該程式碼的意思是：將temp所指向的一塊記憶體區域中的前幾個元素地址的內容都設定為第二個引數的值，這裏即為把所有的元素的值都置為0。
順序表的實現並不難，且實現方式也很多，只要思路清晰，程式碼就很簡單了。
java當中的順序表最簡單的例子就是陣列了，java由於是高階語言，所以就不會像c語言一樣需要考慮地址了，這裏爲了方便大家理解地址相關的知識，所以採用c語言。
在實現順序表時，一般將順序表資訊儲存在頭結點中，因此求順序表容量時，只需要直接從頭結點獲取即可，程式碼如下
//求順序表容量 int seqList_Capacity(SeqList * list){ TSeqList * temp=NULL; if(list==NULL) { return; } temp=(TSeqList *)list; return temp->capacity; }
解釋下：
1、該方法的引數是順序表的地址
2、上方的判斷list是否為空做的是程式碼的健壯性判斷
和求順序表容量一樣，順序表長度也儲存在順序表頭結點中，所以可以直接獲取，程式碼如下：
//獲取順序表的長度 int seqList_Length(SeqList * list){ TSeqList * temp=NULL; if(list==NULL){ return; } temp=(TSeqList *)list; return temp->length; }
增刪改查是數據結構的核心操作，每種數據結構都要實現這幾種最基本的操作。在順序表中，如果要插入元素，則需要將插入位置後的所有元素向後移動，其示意圖如下
插入元素.png
移動元素.png
移動後空出位置.png
插入完成.png
我們看到，在插入元素時，需要將要插入元素位置的元素及其後邊的元素都要往後移動一個單位。
不過，在插入過程中，需要考慮一些異常情況：
-
當順序表已滿時，表中的元素無法向後移動，需要作出特別處理，比如當表滿時，就不在插入，或者是當表滿時，新開闢一塊更大的空間來儲存這些元素。
-
當插入的位置在空閒區域時，需要作出相應的處理。例如下圖情況：
在空閒區域插入元素.png
有了插入元素的思路後，接下來用程式碼來實現：
//插入元素int seqList_Insert(SeqList * list,SeqListNode * node,int pos){ int i; TSeqList * temp=NULL; if(list==NULL){ return -1; } temp=(TSeqList *)list; //如果順序表已滿 if(temp->length>=temp->capacity){ return -2; } //容錯 //如果給出的pos在長度之後，即中間有空餘，就修正到最後一個元素後邊 if(pos>temp->length) pos=temp->length; //如果pos在元素之間，那麼依次後移插入位置及之後的元素 for(i=temp->length;i>pos;i--) { temp->node[i]=temp->node[i-1]; } //插入元素，賦值，並增加表的長度 temp->node[i]=(int)node; temp->length++; return 0;}
解釋下引數分別為：書序表地址，要插入元素的地址，插入位置。
從順序表中刪除某一個元素，則將元素刪除後，需要將後邊的元素依次向前移動來補齊空位，刪除過程如下圖所示：
刪除元素.png
刪除過程相對來說還是沒有插入元素那個複雜，不必考慮記憶體是否足夠從而造成的「溢位問題」，但是因為要移動元素，效率也是比較低的，程式碼如下：
//刪除元素 SeqList * seqList_Delete(SeqList * list,int pos){ int i; TSeqList tlist=NULL; SeqListNode * temp=NULL; if(list==NULL){ return NULL; } tlist=(TSeqList *)list; if(pos<0||pos>=tlist->capacity){ printf("SeqList_Delete() errorn") } temp=(SeqListNode *)tlist->node[pos]; for(i=pos+1;ilength;i++){ tlist->node[i-1]=tlist->node[i]; } tlist->length--; return temp;}
在順序表中查詢某個元素是非常方便的，因為順序表在底層是以陣列來實現的，每個儲存單元都有索引標註，要查詢某個位置上的元素，直接按照索引來查詢即可。
程式碼如下：
SeqListNode * seqList_Get(SeqList * list,int pos){
TSeqList * tlist=NULL;
SeqListNode * temp=NULL;
if(list==NULL){
printf(“list is emptyn”);
return NULL;
}
tlist=(TSeqList *)list;
if(pos<0||pos>tlist->=capacity){
printf(“seqList_Get() errorn”);
return NULL;
}
temp=(SeqListNode *)tlist->Node[pos]
return temp;
}
清空順序表是將表中的內容全部置為0，請看程式碼
//清空順序表 void seqList_Clear(SeqList * list){ TSeqList * temp=NULL; if(list==NULL){ return; } temp=(TSeqList *)list; temp->length=0; //將書序表全部歸於0 memset(temp->node,0,(temp->capacity*sizeof(void *))); return; }
銷燬順序表是將整個表銷燬，不能在繼續使用。程式碼如下
//銷燬順序表 void seqList_Destory(SeqList * list){ TSeqList * temp=NULL; if(list==NULL){ return; } temp=(TSeqList *)list; if(temp->node!=NULL){ free(temp->node);//先釋放頭結點中的指標陣列 } free(temp);//再釋放頭結點 return； }
總結
至此，我們已經實現了一個順序表最基本的操作，可以完成簡單的增刪改查的功能了，接下來就可以將上方的程式碼複製到vs中即可。
我們可以根據自己實際中遇到的問題，通過我們剛纔學過的順序表進行程式設計。
本篇文章就到這裏，下篇文章我們一起學習鏈式表