還記得資料結構這個經典的分類圖吧：
今天主要關注一下線性表。
什麼是線性表
線性表的劃分是從資料的邏輯結構上進行的。線性指的是在資料的邏輯結構上是線性的。即在資料元素的非空有限集中
(1) 存在唯一的一個被稱作“第一個”的資料元素，(2) 存在唯一的一個被稱作“最後一個”的資料元素，(3) 除第一個外，集合中的每個資料元素均隻有一個前繼元素，(4)除最後一個外，集合中的每個資料元素均隻有一個後繼元素。
那麼對于線性表，從存儲結構上分，可以有順序存儲結構和鍊式存儲結構。順序存儲結構包括順序表、順序隊列和順序棧；鍊式存儲結構包括連結清單、鍊隊列和鍊棧。所有這些分類資料結構的實作，後續的博文将陸續進行介紹。
順序表(數組,向量)
順序表的結構：
順序表的結構如下圖所示：
從結構上可以看出，順序表實際上就是一個動态數組，在C++的标準模闆庫（STL）中類似的對應着vector模闆類。是以了解順序表對于使用vector進行進階應用的開發有着極為重要的作用。
存儲結構定義如下：
typedef struct
{
DataType *m_pData;
int m_nMax,m_nSize;
}SeqList;
typedef int DataType;
順序表的基本操作及其實作
有了資料的結構定義，就必須有對應的方法實作從來進行相關的操作，基本的運算函數如下：
Void SetList(SeqList *L,int n);// 構造函數,建立數組長是n的空表
Void FreeList(SeqList *L); //
析構函數,釋放數組空間
int ListSize(SeqList *L) //
求表的長度
int IsEmpty(SeqList *L); //
判斷數組是否空,1:空,0滿
int IfFull(SeqList *L); //
判斷數組是否滿
DataType GetData(int pos); //
擷取數組某元素
int Locate(SeqList *L,DataTypeitem); //
判斷元素位置
Void SetData(SeqList *L,DataTypeitem,int pos); //元素位置指派
Void Insert(SeqList *L,int pos,DataType item); //在某位置插入元素
void InsertRear(SeqList *L,DataType&item); //
在末尾插入元素
void Delete(SeqList *L,int pos);//删除某位置元素
void ClearList(SeqList *L); //
清表,表中的元素個數是0;
Void DeleteBetween(SeqList *L,intstart, int end)
對應某些函數方法的實作如下：
voidSetList(SeqList *L,int n)
L->m_pData=newDataType[n];
if(L->m_pData==NULL)
cout<<”overflow”<<endl;exit(1);
}
L->m_nMax=n;
L->m_nSize=0;
Void FreeList(SeqList *L)
delete [ ]L->m_pData;
L->m_nMax=0;
void Insert(SeqList *L,DataType item,int pos)
//在順序表中在pos處插入item
i=1;
if(L->m_nSize==L->m_nMax){printf(“SeqListis FULL\n”);exit(1)}
if(pos<=0||pos>L->m_nSize)
{
printf(“Pos is out of range”);exit(1);
}
for(i=L->m_nSize-1;i>=pos;i--)
L->m_nData[i+1]=L->m_nData[i];
L->m_nData[pos]=item;
L->m_nSize++;
順序表的應用：動态字元串
C語言字元串
char str[13]=“Hello, world!”;
char *pStr = str;
字元串函數
gets(char *str);
puts(char *str);
strcpy(char *str1, char *str2); //字元串拷貝
strcat(char *str1, char *str2); //字元串連接配接,str1必須足夠大
strcmp(char *str1, char *str2); //字元串比較
strlen(char *str); //字元串求長,不包含’\0’的長度
動态字元串：
Typedef struct
{
int m_nSize;//不含結束符的長度
char*m_pStr;
}String;
基本運算： Concat(), SubString(), Insert(),Delete(),Clear()…
順序隊列
一種特殊的線性表：隻能在表的一端插入，另一端删除，是先進先出的線性表；頭指針(删除位置)和尾指針(插入位置)
First come, first serve(FIFO)
優點：循環結構、删除時不需移動元素
順序隊列的結構：
順序隊列的結構如下圖所示：
int m_nMax;
int m_nFront,m_nRear, m_nSize;
}Queue;
順序隊列的基本操作及其實作
Void SetQueue(Queue *Q,int n); // 構造函數
void FreeQueue(Queun *Q); // 析構函數
int QSize(Queue *Q); // 隊列長度
int QEmpty(Queue *Q); // 判斷隊列是否空
int QFull(Queue *Q); // 判斷隊列是否滿
DataType QGetData(Queue *Q); // 擷取資料
int QInsert(Queue *Q,DataType item); // 進隊列
DataType QDelete(Queue *Q); // 出隊列
void QClear(); // 清空
隊列删除操作：
DataTypeQDelete(Queue *Q)
DataType item;
if(Q->m_nSize==0)
printf(“隊列空\n”);
Exit(1);
item=Q->m_pData[Q->m_nFront];
Q->m_nFront=(Q->m_nFront+1)%Q->m_nMax;
Q->m_nSize--;
順序棧
一種特殊的線性表：隻能在表的一端插入和删除，是後進先出的線性表；進棧和出棧
順序棧的結構：
結構如下圖所示：
順序棧的基本操作
順序棧的基本操作如下：
CStack()/CStack(int n); // 構造函數
~CStack(); // 析構函數
int SetSize(int n); // 設定棧的大小
int Free(); // 釋放空間
int Size(); // 棧的大小
int Empty(); // 判斷是否空
int Full(); // 判斷是否滿
int Push(DataType item); // 壓棧
DataType Pop(); // 出棧
DataType GetPeek(); // 取棧頂元素
int Clear(); // 清空棧
順序棧的基本運算函數聲明如下：
Void SetStack(Stack *S,int n);
Void FreeStack(Stack *S);
Int StackEmpty(Stack *S);
Int StackFull(Stack *S);
Void Push(Stack *S,DataType item);
DataType Pop(Stack *S);
Void ClearStack(Stack *S);
DataType Peek(Stack *S);