还记得数据结构这个经典的分类图吧：
今天主要关注一下线性表。
什么是线性表
线性表的划分是从数据的逻辑结构上进行的。线性指的是在数据的逻辑结构上是线性的。即在数据元素的非空有限集中
(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_nSize=0;
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)优点：循环结构、删除时不需移动元素顺序队列的结构：
顺序队列的结构如下图所示：
存储结构定义如下： typedef struct
{
DataType *m_pData;
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--;
}顺序栈
一种特殊的线性表：只能在表的一端插入和删除，是后进先出的线性表；进栈和出栈顺序栈的结构：
结构如下图所示：
Typedef struct
{
DataType *m_pData;
int m_nMax;
int m_nTop;//插入数据的位置,空为-1,入栈+1,出栈-1
}Stack;