目录
定义
线性表表的的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
如下：
线性表中每个数据元素的类型都相同，在c语言中，用一维数组来实现顺序存储结构
线性表的顺序存储的结构代码
typedef int SQdataType; typedef struct SeqList { SQdataType *data; //后面用动态开辟的方法对其进行开辟 int size; //线性表当前长度 int capacity; //线性表当前的内存容量 }SL;
顺序存储的结构需要三个要素：
1.存储空间的起始位置
2.线性表的存储容量：capacity
3.线性表的当前长度：size
所应具备的功能
//初始化 void SeqListInit(SL* ps); //尾插 void SeqListPushBack(SL* ps, SQdataType x); //头插 void SeqListPushFront(SL* ps, SQdataType x); //尾删 void SeqListPopBack(SL* ps, SQdataType x); //头删 void SeqListPopFront(SL* ps, SQdataType x); //任意位置的插入 void SeqListInsert1(SL* ps, int i, SQdataType x); void SeqListInsert2(SL* ps, int i, SQdataType x); //删除任意位置 void SeqListDelete1(SL* ps, int i, SQdataType x); void SeqListDelete2(SL* ps, int i, SQdataType x); //空间销毁 void SeqListDestory(SL* ps); //查 int SeqListSearch(SL* ps,SQdataType x); //改 void SeqListModify(SL* ps, SQdataType);
1.初始化
void SeqListInit(SL* ps) { ps->data = NULL; ps->size = 0; ps->capacity = 0; }
2.插入新元素
在增加元素前，应对容量进行检查，如果容量不够，应ralloc更大的空间
void SeqListCheckCapacity(SL* ps) { if (ps->size == ps->capacity) //判断元素是否达到最大容量 { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//若容量为零开辟4个空间 SQdataType* tmp = realloc(ps->data, sizeof(SQdataType) * newcapacity); if (tmp == NULL) //判断是否开辟成功 { printf("realloc fail\n"); exit(-1); } else //开辟成功 { ps->data = tmp; capacity=newcapacity; } } }
（1）在开头插入新元素
void SeqListPushFront(SL* ps, SQdataType x) { SeqListCheckCapacity(&ps);//插入前进行容量检查 int end = ps->size - 1; while (end >= 0) { ps->data[end + 1] = ps->data[end]; end--; } ps->size++; ps->data[0] = x; }
（2）在结尾插入新元素
void SeqListPushBack(SL* ps, SQdataType x) { SeqListCheckCapacity(&ps);//插入前进行容量检查 ps->data[ps->size] = x; ps->size++; }
（3）在任意处插入新元素
思路一：
void SeqListInsert1(SL* ps, int i, SQdataType x) { SeqListCheckCapacity(&ps); int k; if (i<1 || i>ps->size + 1) { printf("error\n"); return; } if (i <= ps->size) { for (k = ps->size - 1; k >= i - 1; k--) ps->data[k + 1] = ps->data[k]; } ps->data[i - 1] = x; ps->size++; }
思路二：
void SeqListInsert2(SL* ps, int i, SQdataType x) { SeqListCheckCapacity(&ps); assert(i< ps->size); int end = ps->size - 1; i -= 1; while (end >= i) { ps->data[end + 1] = ps->data[end]; --end; } ps->data[i - 1] = x; ps->size++; }
2.删除元素
（1）开头删除
void SeqListPopFront(SL* ps) { assert(ps->size > 0); int start = 1; while (start < ps->size) { ps->data[start - 1] = ps->data[start]; ++start; } ps->size--; }
（2）尾部删除
void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--; }
（3）任意位置删除
思路一：
void SeqListDelete1(SL* ps, int i, SQdataType x) { SeqListCheckCapacity(&ps); int k; if (i<1 || i>ps->size) { printf("error\n"); return; } if (i < ps->size) { for (k = i; k < ps->size; k++) ps->data[k - 1] = ps->data[k]; } ps->size--; }
思路二：
void SeqListDelete2(SL* ps, int i, SQdataType x) { int end = ps->size - 1; assert(i >= end); while (end > i) { ps->data[i - 1] = ps->data[i]; --i; } ps->size--; }
3.查找元素
int SeqListSearch(SL* ps,SQdataType x) { for (int i = 0; i < ps->size; i++) { if (ps->data[i] == x) return i; } return -1; }
4.修改元素
void SeqListModify(SL* ps, int pos, SQdataType x) { assert(pos < ps->size-1); ps->data[pos - 1] = x; }
线性表顺序存储结构的优缺点
优点:
无需为表示表中的元素之间的逻辑关系而增加额外的存储空间。
可以快速地存表中任一位置的元素。
缺点：
插入和删除操作需要移动大量元素
