动态顺序表： 容量不够时 自动增容（静态顺序表的改进）
动态顺序表的结构：
typedef int DataType;
typedef struct SeqList
{
DataType* _array; //指向数据块的指针
size_t _size; //有效数据个数
size_t _capacity; //容量
}SeqList;
增容：
void _CheckCapacity(SeqList* pSeq)
{
if (pSeq->_size >= pSeq->_capacity)
{
//防止开始空间为0，而容量一直为0，所以多开辟一些空间。
pSeq->_capacity = 2 * pSeq->_capacity + 3;
pSeq->_array = (DataType *)realloc(pSeq->_array, pSeq- >_capacity*sizeof(DataType));
}
}
//顺序表中数据为空可用提示语句给出或者assert报错
void InitSeqList(SeqList* pSeq) //初始化 { assert(pSeq); //memset(pSeq->_array, 0, sizeof(DataType)*MAX_SIZE); pSeq->_array = NULL; pSeq->_size = 0; pSeq->_capacity = 0; } void PrintSeqList(SeqList* pSeq) { assert(pSeq); for (size_t i = 0; i<pSeq->_size; ++i) { printf("%d ", pSeq->_array[i]); } printf("NULL \n"); } void _CheckCapacity(SeqList* pSeq) { if (pSeq->_size >= pSeq->_capacity) { //防止开始空间为0，而容量一直为0，所以多开辟一些空间。 pSeq->_capacity = 2 * pSeq->_capacity + 3; pSeq->_array = (DataType *)realloc(pSeq->_array, pSeq->_capacity*sizeof(DataType)); } } void PushBack(SeqList* pSeq, DataType x) //尾插 { assert(pSeq); _CheckCapacity(pSeq); pSeq->_array[pSeq->_size++] = x; } void PopBack(SeqList* pSeq) { assert(pSeq); if (pSeq->_size) { pSeq->_array[pSeq->_size] = NULL; pSeq->_size--; } } void PushFront(SeqList* pSeq, DataType x) //头插 { assert(pSeq); _CheckCapacity(pSeq); //注意此处应用int而不能用size_t，否则会一直循环.size_t永远>=0 for (int i = pSeq->_size - 1; i >= 0; --i) { pSeq->_array[i + 1] = pSeq->_array[i]; } pSeq->_array[0] = x; pSeq->_size++; } void PopFront(SeqList* pSeq) { assert(pSeq); if (pSeq->_size <= 0) { printf("SeqList is empty\n"); return; } //assert(pSeq->_size); for (size_t i = 0; i < pSeq->_size; ++i) { pSeq->_array[i] = pSeq->_array[i + 1]; } pSeq->_size--; } void Insert(SeqList* pSeq, size_t pos, DataType x) //增 { assert(pSeq); assert(pos <= pSeq->_size); _CheckCapacity(pSeq); for (int i = pSeq->_size - 1; i >= (int)pos; --i) // 注意size_t永远>=0 { pSeq->_array[i + 1] = pSeq->_array[i]; } pSeq->_array[pos] = x; pSeq->_size++; } int Find(SeqList* pSeq, size_t pos, DataType x) { assert(pSeq); for (size_t i = pos; i < pSeq->_size; ++i) { if (pSeq->_array[i] == x) return i; } return -1; } void Erase(SeqList* pSeq, size_t pos) //删 { assert(pSeq); assert(pos<pSeq->_size); for (size_t i = pos + 1; i < pSeq->_size; ++i) { pSeq->_array[i - 1] = pSeq->_array[i]; } pSeq->_size--; } int Remove(SeqList* pSeq, DataType x) { assert(pSeq); int pos = Find(pSeq, 0, x); if (pos != -1) { Erase(pSeq, pos); } return pos; } void RemoveAll(SeqList* pSeq, DataType x) //清除 { int count = 0; assert(pSeq); for (size_t i = 0; i <pSeq->_size; i++) { if (pSeq->_array[i] == x) { count++; } else { pSeq->_array[i - count] = pSeq->_array[i]; } } pSeq->_size -= count; }测试：
//PushBack PopBack void Test1() { SeqList seq; InitSeqList(&seq); PushBack(&seq, 1); PushBack(&seq, 2); PushBack(&seq, 3); PushBack(&seq, 4); PushBack(&seq, 5); PushBack(&seq, 6); PrintSeqList(&seq); PopBack(&seq); PopBack(&seq); PopBack(&seq); PrintSeqList(&seq); PopBack(&seq); PopBack(&seq); PrintSeqList(&seq); } //PushBack PopBack void Test2() { SeqList seq; InitSeqList(&seq); PushFront(&seq, 1); PushFront(&seq, 2); PushFront(&seq, 3); PushFront(&seq, 4); PrintSeqList(&seq); PushFront(&seq, 0); PushFront(&seq, -1); PrintSeqList(&seq); PopFront(&seq); PopFront(&seq); PopFront(&seq); PrintSeqList(&seq); PopFront(&seq); PopFront(&seq); PopFront(&seq); PopFront(&seq); PrintSeqList(&seq); } // Insert/Find/Erase void Test3() { SeqList seq; InitSeqList(&seq); PushBack(&seq, 1); PushBack(&seq, 2); PushBack(&seq, 4); PushBack(&seq, 5); PrintSeqList(&seq); int tmp = Find(&seq, 0, 2); printf("%d\n", tmp); Insert(&seq, tmp, 100); Insert(&seq, 2, 10); Insert(&seq, 2, 3); PrintSeqList(&seq); //删除 tmp = Find(&seq, 0, 3); printf("%d\n", tmp); Erase(&seq, tmp); PrintSeqList(&seq); //添加 越界情况 tmp = Find(&seq, 0, 1); printf("%d\n", tmp); Insert(&seq, tmp, 100); PrintSeqList(&seq); } //Remove RemoveAll void Test4() { SeqList seq; InitSeqList(&seq); PushBack(&seq, 1); PushBack(&seq, 2); PushBack(&seq, 3); PushBack(&seq, 4); PushBack(&seq, 2); PrintSeqList(&seq); /*Remove(&seq, 3); PrintSeqList(&seq);*/ RemoveAll(&seq, 2); PrintSeqList(&seq); }本文出自 “娜些维度的雪” 博客，请务必保留此出处http://1536262434.blog.51cto.com/10731069/1753702
