顺序表就是用一段地址连续的存储单元依次存储数据元素，其物理的相连的。
是不是很类似数组的结构呢？
其优点就是可以通过下标直接随机访问。
代码实现：
顺序表结构封装和函数声明在List.h中，我实现的是动态开辟的，其中顺序表中的结构封装有data作为数据数组，length表示顺序表空间，size为元素个数；
#ifndef _LIST_H_
#define _LIST_H_
/*
动态分配线性表顺序存储结构
物理结构:存储结构相连
便于直接随机访问某个节点
*/
#define MAXSIZE 20//存储空间
#define OK 1//函数状态返回值,成功返回1,不成功返回0
#define ERROR 0//
#define TRUE 1//真假值，真为1,假为0
#define FALSE 0
typedef int Status;//Status是函数类型，其值是函数结果状态代码
typedef int ElemType;
typedef struct
{
ElemType *data;
size_t length;
size_t size;
}SeqList;
void InitList(SeqList*L);//初始化线性表
void Destory(SeqList *L);//销毁线性表
void ClearList(SeqList *L);//重置线性表
Status ListEmpty(SeqList L);//线性表是否为空
int ListLength(SeqList L);//返回线性表中元素的个数
ElemType *GetElem(SeqList *L, int i, ElemType *e);//取第i个元素的值返回给e
Status LocateElem(SeqList L, ElemType e);//在L中查找和e元素值相等的数据元素，不存在返回0，成功返回查找成功
Status ListInsert(SeqList *L, int i, ElemType e);//在线性表L中第i个位置插入新元素e
void ListDelete(SeqList *L, int i, ElemType *e);//删除线性表L中第i个位置元素e
void ListPrint(SeqList *L);
#endif
List.c函数实现文件：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"List.h"
void InitList(SeqList*L)
{
assert(L != NULL);
L->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
L->length = MAXSIZE;
L->size = 0;
}
void Destory(SeqList *L)
{
assert(L != NULL);
if (L->data != NULL)
{
free(L->data);
L->data = NULL;
}
L->size = 0;
L->length = 0;
}
void ClearList(SeqList *L)
{
assert(L != NULL);
L->size = 0;
}
Status ListEmpty(SeqList L)
{
return L.size == 0 ? TRUE : FALSE;
}
int ListLength(SeqList L)
{
return L.size;
}
ElemType* GetElem(SeqList *L, int i, ElemType *e)
{
assert(L != NULL &&i<=L->size);
*e=L->data[i - 1];
return e;
}
Status LocateElem(SeqList L, ElemType e)
{
int i = 0;
for (i = 0; i < L.size; i++)
{
if (L.data[i] == e)
{
return OK;//查找到与e相等的元素值
}
}
return ERROR;//没有与e元素值相等的值
}
Status ListInsert(SeqList *L, int i, ElemType e)
{
assert(L != NULL);
if (L->size + 1 > L->length)
{
L->length+= MAXSIZE;
ElemType* new = (ElemType*)realloc(L->data, sizeof(ElemType)*L->length);//扩容，增加分配空间
if (new == NULL)
{
return ERROR;
}
L->data = new;
}
int j = L->size;
for (j = L->size; j > i-1; j--)
{
L->data[j] = L->data[j-1];
}
L->size++;
L->data[j] = e;
return OK;
}
void ListDelete(SeqList *L, int i, ElemType *e)
{
assert(L != NULL);
if (i > L->size || i<=0)
{
return;
}
int j = 0;
*e = L->data[i - 1];
for (j = i - 1; j <= L->size; j++)
{
L->data[j] = L->data[j + 1];
}
L->size--;
}
void ListPrint(SeqList *L)
{
assert(L != NULL);
int i = 0;
for (i = 0; i <L->size; i++)
{
printf("%d ", L->data[i]);
}
printf("\n");
}
void TestList()//测试函数
{
SeqList sq;
ElemType val=0;
InitList(&sq);
ListPrint(&sq);
bool b=ListEmpty(sq);
printf("bool b:%d \n", b);
ListInsert(&sq, 1, 1);
ListInsert(&sq, 2, 2);
ListInsert(&sq, 3, 3);
ListInsert(&sq, 4, 4);
ListInsert(&sq, 5, 5);
ListPrint(&sq);
ListInsert(&sq, 3, 8);
ListPrint(&sq);
ListDelete(&sq, 2, &val);
printf("删除元素的数据为：%d\n", val);
ListPrint(&sq);
int n=ListLength(sq);
printf("sq中的元素个数为：%d\n", n);
b=ListEmpty(sq);
printf("bool b；%d\n", b);
b=LocateElem(sq, 10);
printf("bool b；%d\n", b);
b = LocateElem(sq, 4);
printf("bool b；%d\n", b);
Destory(&sq);
}
int main()
{
TestList();
return 0;
}
代码虽然已经实现，但是在实现过程中我们还要注意一些问题：
在插入元素的时候需要注意插入位置是否合理，是否满足0<i<=size+1,插入之前空间是否充足，是否需要扩容？
在删除第某个元素是，该下标是否存在 0<i<size
其中测试函数的打印结果为：
当然顺序表也有不足：
- 在插入和删除时时间复杂度为O(n)，
- 增容需要申请新空间，销毁旧空间，会有一定的消耗