1、順序表
線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。
順序存儲(chǔ)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。 簡言之，邏輯上相鄰，物理上也相鄰
順序存儲(chǔ)方法：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組 V[n] 來實(shí)現(xiàn)。
1.1 定義
順序表的類型定義
#define MAXSIZE 100 //最大長度
typedef struct {
? ? ElemType *elem;? ? //指向數(shù)據(jù)元素的基地址
? ? int length;? ? //線性表的當(dāng)前長度
}SqList；
ex：
#define MAXSIZE 10000 //圖書表可能達(dá)到的最大長度
typedef struct //圖書信息定義
{
?? char no[20]; //圖書 ISBN
?? char name[50]; //圖書名字
?? float price; //圖書價(jià)格
}Book;
typedef struct
{
?? Book *elem; //存儲(chǔ)空間的基地址
?? int length; //圖書表中當(dāng)前圖書個(gè)數(shù)
}SqList; //圖書表的順序存儲(chǔ)結(jié)構(gòu)類型為 SqList
補(bǔ)充：
1、C語言的動(dòng)態(tài)分配函數(shù)（<stdlib.h>）
malloc(m)：開辟M(fèi)字節(jié)長度的地址空間，并返回這段空間的首地址。
sizeof(x)：計(jì)算變量X的長度
free(p)：釋放指針P所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量
2、C++的動(dòng)態(tài)存儲(chǔ)分配
int *p1 = new int;或int *p1 = new int(10);
（1）new 類型名稱 T（初值列表）
功能：申請(qǐng)用于存放T類型對(duì)象的內(nèi)存空間，并依初值列表賦以初值
（2）結(jié)果值；
成功：T類型的指針，指向新分配的內(nèi)存
失?。?（NULL）
（3）delete 指針P
delete P；（釋放）
3、C++中的參數(shù)傳遞
函數(shù)調(diào)用時(shí)傳送給形參的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保持一致
參數(shù)傳遞有兩種方式：
1、傳值方式（參數(shù)為整型、實(shí)型、字符型等）
2、傳地址
參數(shù)為指針變量
參數(shù)為引用類型：&
（1）傳遞引用給函數(shù)與傳遞指針的效果是一樣的；形參變化，實(shí)參也發(fā)生變化
（2）引用類型作形參，在內(nèi)存中并沒用產(chǎn)生實(shí)參的副本，它直接對(duì)實(shí)參操作；而一般變量作參數(shù)，形參與實(shí)參就占用不同的存儲(chǔ)單元，所以形參變量的值是實(shí)參變量的副本。因此，當(dāng)參數(shù)傳遞的數(shù)據(jù)量較大時(shí)，用引用比用一般變量傳遞參數(shù)傳遞的時(shí)間和空間效率都好。
（3）指針參數(shù)雖然也能達(dá)到與使用引用的效果，但在被調(diào)函數(shù)中需要重復(fù)使用”*指針變量名“的形式進(jìn)行運(yùn)算，這很容易產(chǎn)生錯(cuò)誤且程序的閱讀性較差；另一方面，在主調(diào)函數(shù)的調(diào)用處，必須用變量的地址作為實(shí)參。
參數(shù)為數(shù)組名
1.2 基本操作
1 初始化
初始化線性表 L（參數(shù)用引用）
StatusInitList_Sq（SqList&L）{? ? //構(gòu)造一個(gè)空的順序表 L
? ? L.elem=newElemType[MAXSIZE];? //為順序表分配空間
? ? if（!L.elem）exit（OVERFLOW）;? ? //存儲(chǔ)分配失敗
? ? L.length=0;? ? ? ? ? ? ? ? ? ? ? ? //空表長度為 0
? ? returnOK;
}
初始化線性表 L （參數(shù)用指針）
StatusInitList_Sq（SqList*L）{? ? ? ? //構(gòu)造一個(gè)空的順序表 L
? ? L->elem=newElemType[MAXSIZE];? ? //為順序表分配空間
? ? if（!L->elem）exit（OVERFLOW）;//存儲(chǔ)分配失敗
? ? L->length=0;? ? ? ? ? ? ? ? ? ? ? //空表長度為 0
? ? returnOK;
}
銷毀
voidDestroyList（SqList&L）
{
? ? if（L.elem）delete[]L.elem;//釋放存儲(chǔ)空間
}
清空
voidClearList（SqList&L）
{
? ? L.length=0;//將線性表的長度置為 0
}
求表長
intGetLength（SqListL）
{
? ? return（L.length）;
}
判空
intIsEmpty（SqListL）
{
? ? if（L.length==0）return1;
? ? elsereturn0;
}
1.3 取值
intGetElem（SqListL，inti，ElemType&e）
{
//判斷 i 值是否合理，若不合理，返回 ERROR
? ? if（i<1||i>L.length）returnERROR;
? ? e=L.elem[i-1];//第 i-1 的單元存儲(chǔ)著第 i 個(gè)數(shù)據(jù)
? ? returnOK;
}
1.4 查找
intLocateELem（SqListL，ElemTypee）
{
for（i=0;i<L.length;i++）
? ? if（L.elem[i]==e）returni+1;
return0;
}
5插入
算法步驟：
1、判斷插入位置i是否合法
2、判斷順序表的存儲(chǔ)空間是否已滿
3、將第n至第i位的元素依次向后移動(dòng)一個(gè)位置，空出第i個(gè)位置
4、將要插入的新元素e放入第i個(gè)位置
5、表長加1
6、插入成功返回OK
StatusListInsert_Sq（SqList&L，inti，ElemTypee）{
if（i<1||i>L.length+1）returnERROR;//i 值不合法
if（L.length==MAXSIZE）returnERROR;//當(dāng)前存儲(chǔ)空間已滿
for（j=L.length-1;j>=i-1;j--）
? ? L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移
L.elem[i-1]=e;//將新元素 e 放入第 i 個(gè)位置
++L.length;//表長增 1
returnOK;
}
6 刪除
StatusListDelete_Sq（SqList&L，inti）{
if（（i<1）||（i>L.length））returnERROR;//i 值不合法
for（j=i;j<=L.length-1;j++）
? ? L.elem[j-1]=L.elem[j];//被刪除元素之后的元素前移
--L.length;//表長減 1
returnOK;
}
1.3 優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
存儲(chǔ)密度打大
可以隨機(jī)存取表中任一元素
缺點(diǎn)：
在插入、刪除某一元素時(shí)，需要移動(dòng)大量元素
浪費(fèi)存儲(chǔ)空間
屬于靜態(tài)存儲(chǔ)形式，數(shù)據(jù)元素的個(gè)數(shù)不能自由擴(kuò)充
