順序存儲定義
今天來總結(jié)一下線性表的順序存儲結(jié)構(gòu)拿诸。首先來看下順序存儲結(jié)構(gòu)的定義圃庭。
線性表的順序存儲結(jié)構(gòu)鹰溜，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素序芦。
舉個簡單的例子愧沟，藺老師在給九班學生安排座位之前蔬咬，會讓學生們從矮到高按照身高的高矮升序排列，假如藺老師的班上只有十個學生沐寺，而全班共有50個座位林艘，那藺老師會把這10個學生，連續(xù)的安排在教室的前兩排之內(nèi)混坞，每個人都有自己的同桌狐援，連續(xù)的10個座位，那么這10個學生所占用的就是一片連續(xù)的座位。相當于內(nèi)存中有50個數(shù)據(jù)元素的空間啥酱，而10個學生只占用了中間的連續(xù)十個大小的空間场钉。
因為線性表中，存儲的數(shù)據(jù)元素的類型都相同懈涛，而存儲空間又是連續(xù)的逛万，那么我們可以用一維數(shù)組來實現(xiàn)線性表的存儲結(jié)構(gòu)。
因為班上一共有50個座位批钠，所以藺老師在安排座位時宇植，也沒必要一定從第一個座位開始安排，可以從第二排或者第三排來安排座位埋心，選定座位之后指郁，學生一個挨一個的坐進去就可以了。所以選定線性表時拷呆，在內(nèi)存中找一塊地闲坎，于是這塊地的第一個位置就非常關(guān)鍵，它為存儲空間的起始位置茬斧。
每天放學回家腰懂，藺老師會要求這10個學生排隊走出校門，而并不是每個學生每天都會上學项秉，比如彤彤這樣的學生绣溜，每天放學要去等藺老師下班，那么隊伍里可能只有九個人娄蔼，而這九個人還是排成了一列怖喻，誰在前誰在后關(guān)系依舊很明確，只是少了彤彤而已岁诉。而這個例子锚沸，就表示了線性表一一對應(yīng)的特點，就像排隊涕癣，在整隊的時候隨著每天的放學排隊哗蜈，大家很清楚自己該出現(xiàn)在哪個位置。
順序存儲結(jié)構(gòu)的代碼
我們來看線性表順序存儲結(jié)構(gòu)的結(jié)構(gòu)代碼：
#define MAXSIZE 10 //存儲空間的初始化分配
typedef int ElementType; //定義線性表元素數(shù)據(jù)類型 這里假設(shè)為int
typedef struct
{
ElementType data[MAXSIZE]; //線性表存儲數(shù)據(jù)元素
int length; //線性表的長度
}SqList;
這里我們能看到順序存儲結(jié)構(gòu)所需要的三個屬性：
存儲空間的起始位置：數(shù)組data属划，它的存儲位置就是存儲空間的存儲位置
線性表的最大容量恬叹，數(shù)組長度MAXSIZE
線性表的當前長度： length
我們對每個線性表位置的存入或取出的數(shù)據(jù)，對于計算機來說都是相等的時間同眯，也就是一個常數(shù)绽昼。因此用上一次討論的算法時間復(fù)雜度的概念來說，線性表的時間復(fù)雜度為O(1)须蜗。我們通常把具有這一特點的存儲結(jié)構(gòu)稱為隨機存儲結(jié)構(gòu)硅确。
順序存儲結(jié)構(gòu)的插入或刪除
在討論順序存儲結(jié)構(gòu)的實現(xiàn)方式之前目溉，我們先來定義一下函數(shù)運行的狀態(tài)代碼，用來返回線性表運行的狀態(tài)菱农。
/**
* 函數(shù)運行的狀態(tài)代碼
*
*
*/
#define SUCCESS 1
#define ERROR 0
typedef int Status; //狀態(tài)代碼的類型
這段代碼我們定義了Status為狀態(tài)代碼的類型缭付，返回SUCCESS代表1，返回ERROR代表0循未。本文之后的所有狀態(tài)代碼就不再詳述了陷猫。
創(chuàng)建線性表（初始化）
在上面我們已經(jīng)定義好了線性表的屬性，并確定了線性表的最大存儲容量的妖，那么我們在剛開始時绣檬，對線性表進行初始化，創(chuàng)建一個線性表嫂粟。
/**
線性表的初始化 并分配存儲單元
- returns: SqList*
*/
SqList * initSqList()
{
SqList * list = (SqList *)malloc(sizeof(SqList));
list->length = 0 ;
return list;
}
在這里我們還是用C語言來操作娇未，創(chuàng)建了一張線性表，用malloc分配存儲空間星虹，定義當前線性表長度為0零抬，最后返回值為本張線性表。
獲得元素操作
//獲取線性表中的元素
Status GetElem (SqList * L , int i , ElementType e)
{
if (L->length == 0 || i < 1 || i > L->length ) {
return ERROR;
}
e = L->data[i-1];
return SUCCESS;
}
在獲取元素的操作中呢宽涌，我們定義了一個e平夜，用來返回L中第i個元素的值。
插入操作
在這里先不放代碼护糖，先來討論一下線性表的插入概念褥芒。比如我在火車站排隊等著取票嚼松，排了很久的隊終于快輪到我了嫡良，這時候有一個很漂亮的姑娘過來，可憐兮兮的對我說：帥哥献酗，我的車還有幾分鐘
就開了寝受，能讓我先取一下么『辟耍可能我會“以貌取人”很澄，答應(yīng)了這個漂亮姑娘的要求，于是這個姑娘排到了我的前面颜及，可是我畢竟有女朋友甩苛，再加上男女授受不親，我又不想回家跪鍵盤俏站，于是我得往后退一步讯蒲，讓出一個空間給姑娘排在我前面，我后面的人也得跟著我的步伐往后退一步肄扎。這時候墨林，就類似于線性表的插入算法的思路：
如果插入的位置不合理赁酝，拋出異常
如果線性表的長度大于數(shù)組長度，拋出異承竦龋或者動態(tài)增加存儲空間
從最后一個元素酌呆，向前遍歷到第i個位置，分別將它們都向后移動一個位置搔耕。
將要插入的元素插入到位置i
表長+1
代碼的話隙袁，我用了兩種方式，一種是線性表以棧的方式加入數(shù)據(jù)元素弃榨，即為每一次都加在隊列的最后面藤乙，一種是按照要求，添加到指定的位置中惭墓。
棧的方式插入數(shù)據(jù)元素的實現(xiàn)代碼：
//線性表以棧的方式加入數(shù)據(jù)
Status pushElement(ElementType e, SqList * list)
{
int length = list->length;
if (length < 0 || length > MAXSIZE) {
return ERROR;
}
list->data[length] = e;
list->length++;
return SUCCESS;
}
在指定位置插入數(shù)據(jù)元素的代碼實現(xiàn)如下：
/**
* 在線性表中的第i個位置插入之前新的元素數(shù)據(jù)e坛梁，線性表的長度+1
*
*/
Status insertElementWithLocation(ElementType e, SqList * list, int i)
{
int k;
//判斷線性表的存儲空間是否已滿
if (list->length == MAXSIZE) {
return ERROR;
}
//判斷i的合理性
if (i < 1 || i > list->length) {
return ERROR;
}
//將要插入的位置后面的數(shù)據(jù)向后移動一位
if (i <= list->length) {
for (k = list->length - 1; k >= i-1; k--) {
list->data[k+i] = list->data[k];
}
}
list->data[i-1] = e; //插入新元素
list->length++;
return SUCCESS;
}
刪除操作
講完了插入的概念以及實現(xiàn)巧勤，應(yīng)該對刪除操作的行為也有了理解瓦呼，即為從指定位置，刪除需要刪除的元素氧映。
所以刪除算法的思路：
如果刪除位置不合理钧萍，拋出異常
取出刪除元素
從刪除元素開始褐缠，之后的元素至最后一個元素的存儲位置向前挪動一個位置
表長-1
我們同樣用棧的刪除模式和指定位置刪除的模式來實現(xiàn)代碼。
棧的方式刪除元素风瘦，即為每次都刪除最后一個元素的代碼實現(xiàn)：
/**
* 按照棧的方式刪除元素 e用來接收刪除出來的值
*/
Status popElement(ElementType e, SqList *list)
{
int length = list->length;
//判斷線性表的合法性
if (length < 0 || length > MAXSIZE) {
return ERROR;
}
e = list->data[length - 1];
list->length -- ;
return SUCCESS;
}
在指定位置刪除元素的代碼實現(xiàn)如下:
/**
* 在線性表中的第i個位置刪除元素 線性表的長度減一
*/
Status deleteElementWithLocation(ElementType e, int i , SqList * list)
{
//判斷線性表的合法性
if (list->length < 0 || list->length > MAXSIZE ) {
return ERROR;
}
//判斷刪除位置的合法性
if (i < 1 || i > list->length) {
return ERROR;
}
e = list->data[i-1];
if (i < list->length) {
//將刪除位置的后繼元素前移
for (int k = i; k < list->length; k++) {
list->data[k-1] = list->data[k];
}
}
list->length -- ;
return SUCCESS;
}
遍歷線性表
最后為了方便我們等下來驗證代碼的正確性队魏，我們寫一個函數(shù)來遍歷線性表，代碼如下：
/**
* 遍歷線性表
*/
Status displayList(SqList * list)
{
if (list->length < 0 || list->length > MAXSIZE) {
return ERROR;
}
printf("***************************\n");
for (int i = 0; i < list->length; i++) {
printf("數(shù)值 = %d , 地址 = %p\n",list->data[i], &list->data[i]);
}
printf("***************************\n");
return SUCCESS;
}
驗證代碼正確性
在驗證代碼的正確性時万搔，我用了Objective-C語言來寫胡桨，大體思路如果是使用C語言的程序員，也是能完全看懂的瞬雹。
我先創(chuàng)建了一個線性表昧谊，并且遍歷它，打印地址來驗證順序結(jié)構(gòu)存儲空間的連續(xù)性酗捌。
//把1-8按順序入棧
SqList * list = initSqList();
NSLog(@"把1-8按順序入棧");
int j = 1;
for (int i = 0; i <8 ; i++) {
pushElement(j, list);
++j;
}
displayList(list);
因為存儲空間總大小為10個元素單位呢诬，而我要求把1-8共8個數(shù)按順序存入線性表中。打印結(jié)果如下：
***************************
數(shù)值 = 1 , 地址 = 0x1002014d0
數(shù)值 = 2 , 地址 = 0x1002014d4
數(shù)值 = 3 , 地址 = 0x1002014d8
數(shù)值 = 4 , 地址 = 0x1002014dc
數(shù)值 = 6 , 地址 = 0x1002014e0
數(shù)值 = 7 , 地址 = 0x1002014e4
數(shù)值 = 8 , 地址 = 0x1002014e8
***************************
我們可以看到胖缤，數(shù)值以及存儲空間都是連續(xù)的尚镰，說明我們用棧的方式插入線性表是創(chuàng)建成功的。
我又要求往第八個位置插入724這個數(shù)字
//往第8個位置插入724;
insertElementWithLocation(724, list, 8);
運行結(jié)果如下哪廓，可以清楚的看到第八位是724狗唉，而原先的元素后移一位。
第八位增加724
***************************
數(shù)值 = 1 , 地址 = 0x100101320
數(shù)值 = 2 , 地址 = 0x100101324
數(shù)值 = 3 , 地址 = 0x100101328
數(shù)值 = 4 , 地址 = 0x10010132c
數(shù)值 = 5 , 地址 = 0x100101330
數(shù)值 = 6 , 地址 = 0x100101334
數(shù)值 = 7 , 地址 = 0x100101338
數(shù)值 = 724 , 地址 = 0x10010133c
數(shù)值 = 8 , 地址 = 0x100101340
***************************
驗證刪除操作的時候撩独，我們命令把第五位的數(shù)據(jù)刪除（以原始數(shù)據(jù)為例）
// 把第五位的數(shù)據(jù)刪除
deleteElementWithLocation(0, 5, list);
得到結(jié)果如下:
刪除第五位
***************************
數(shù)值 = 1 , 地址 = 0x1002014d0
數(shù)值 = 2 , 地址 = 0x1002014d4
數(shù)值 = 3 , 地址 = 0x1002014d8
數(shù)值 = 4 , 地址 = 0x1002014dc
數(shù)值 = 6 , 地址 = 0x1002014e0
數(shù)值 = 7 , 地址 = 0x1002014e4
數(shù)值 = 8 , 地址 = 0x1002014e8
***************************
至此敞曹，我們可以得出結(jié)論我們創(chuàng)建的線性表是正確的账月，連續(xù)的，具備線性表的屬性的澳迫。而我們在對線性表的順序存儲結(jié)構(gòu)的插入和刪除的操作也是正確的局齿，實現(xiàn)了功能。所以今天的線性表的順序存儲結(jié)構(gòu)橄登，就講到這里抓歼，以上代碼我已經(jīng)上傳到Github上，若有講的不清楚的地方拢锹，也可以下載Github上的代碼來參考谣妻。
