1.顺序表概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。
2.顺序表分类：
2.1 静态顺序表：使用定长数组存储元素。（不实用）
2.2动态顺序表：使用动态开辟的数组存储。
3.实现动态顺序表
3.1 初始化顺序表 SLInit
void SLInit(SL* ps) { assert(ps != NULL); ps->a = NULL; ps->size = ps->capacity = 0; }
3.2 检查顺序表容量 SLCheckCapacity
void SLCheckCapacity(SL* ps) { assert(ps != NULL); // 检查容量空间，满了扩容 if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); //exit(-1); return; } ps->a = tmp; ps->capacity = newCapacity; } }
3.3 打印顺序表 SLPrint
void SLPrint(SL* ps) { assert(ps != NULL); //assert(ps); for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("\n"); }
3.4 尾插 SLPushBack
void SLPushBack(SL* ps, SLDataType x) { assert(ps != NULL); SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; //SLInsert(ps, ps->size, x); }
3.5 头插 SLPushFront
void SLPushFront(SL* ps, SLDataType x) { assert(ps != NULL); SLCheckCapacity(ps); // 挪动数据 int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; //SLInsert(ps, 0, x); }
3.7 头删 SLPopFront
void SLPopFront(SL* ps) { assert(ps != NULL); assert(ps->size > 0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; //SLErase(ps, 0); }
3.8 顺序表查找 SLFind
int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; ++i) { if (ps->a[i] == x) return i; } return -1; }
3.9 顺序表修改 SLModify
void SLModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
4. 顺序表总结
4.1 顺序表优化
使用SLInsert函数实现 尾插，头插
使用SLErase函数实现 尾删，头删
void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); // 挪动数据 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; }
void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); //两种方法实现 //int begin = pos; //while (begin < ps->size-1) //{ // ps->a[begin] = ps->a[begin + 1]; // ++begin; //} int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }
4.2 顺序表的缺点
由于头插和头删需要移动数据，所以时间复杂度为O(N），所以后面引入链表实现。
