一、动态顺序表结构定义
//数组顺序表的结构定义 typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size;//有效数据 int capacity;//空间容量 }SL;
二、动态顺序表初始化
//动态顺序表的初始化 void SLInit(SL* psl) { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; }
三、动态顺序表打印
//动态顺序表的打印 void SLPrint(SL psl) { for (int i = 0; i < psl.size; i++) { printf("%d ", psl.a[i]); } printf("\n"); }
四、动态顺序表尾插
//动态顺序表的尾插 void SLPushBack(SL* psl, SLDataType x) { assert(psl); if (psl->size == psl->capacity) { //SLDataType* p = (SLDataType*)realloc(psl->a, psl->capacity == 0 ? 4 : 2 * psl->capacity * sizeof(SLDataType)); int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDataType* p = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType)); if (p == NULL) { perror("realloc fail"); exit(-1); } else { psl->a = p; psl->capacity = newcapacity; } } psl->a[psl->size++] = x; }
五、封装扩容函数
//封装扩容函数 void checkcapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; SL* p = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType)); if (p == NULL) { perror("realloc fail"); exit(-1); } else { psl->a = p; psl->capacity = newcapacity; } } }
六、动态顺序表头插
//动态顺序表头插 void SLPushFront(SL* psl, SLDataType x) { assert(psl); checkcapacity(psl); for (int i = psl->size; i > 0; i--) { psl->a[i] = psl->a[i - 1]; } psl->a[0] = x; psl->size++; }
七、动态顺序表的尾删
//动态顺序表的尾删 void SLPopBack(SL* psl) { assert(psl); assert(psl->size > 0); psl->size--; }
八、动态顺序表的头删
//动态顺序表的头删 void SLPopFront(SL* psl) { assert(psl); assert(psl->size > 0); for (int i = 0; i < psl->size - 1; i++) { psl->a[i] = psl->a[i + 1]; } psl->size--; }
九、动态顺序表任意位置插入
//动态顺序表任意位置插入 void SLInsert(SL* psl, int pos, SLDataType x) { assert(psl); assert(pos >= 1 && pos <= psl->size); checkcapacity(psl); for (int i = psl->size; i > pos - 1; i--) { psl->a[i] = psl->a[i - 1]; } psl->a[pos - 1] = x; psl->size++; }
十、动态顺序表任意位置删除
//动态顺序表任意位置删除 void SLErase(SL* psl, int pos) { assert(psl); assert(pos >= 1 && pos <= psl->size); for (int i = pos - 1; i < psl->size - 1; i++) { psl->a[i] = psl->a[i + 1]; } psl->size--; }
十一、动态顺序表销毁
//动态顺序表销毁 void SLDestroy(SL* psl) { assert(psl); if (psl->a != NULL) { free(psl->a); psl->a = NULL; psl->capacity = 0; psl->size = 0; } }
十二、测试代码
void test01() { //定义动态顺序表 SL psl; //初始化动态顺序表 SLInit(&psl); //尾插 SLPushBack(&psl, 1); SLPushBack(&psl, 2); SLPushBack(&psl, 3); SLPushBack(&psl, 4); SLPushBack(&psl, 5); //打印 SLPrint(psl); //头插 SLPushFront(&psl, 1); SLPushFront(&psl, 2); SLPushFront(&psl, 3); SLPushFront(&psl, 4); SLPushFront(&psl, 5); //打印 SLPrint(psl); //尾删 SLPopBack(&psl); SLPopBack(&psl); SLPopBack(&psl); //打印 SLPrint(psl); //头删 SLPopFront(&psl); SLPopFront(&psl); SLPopFront(&psl); //打印 SLPrint(psl); //任意位置插入 SLInsert(&psl, 2, 10); SLInsert(&psl, 2, 11); SLInsert(&psl, 2, 12); //打印 SLPrint(psl); //任意位置删除 SLErase(&psl, 2); SLErase(&psl, 2); SLErase(&psl, 2); //打印 SLPrint(psl); //销毁 SLDestroy(&psl); } int main() { test01(); return 0; }
