顺序表功能实现（增删查改）《数据结构(C语言版)》_m0_57859086

未知 02-07 6613

《数据结构(C语言版)》实战项目之顺序表（增删查改）功能实现：

博文内容：

数据结构（C语言版）之顺序表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

问题导引：

实现步骤：

P2—＜顺序表＞《数据结构(C语言版)》

顺序表（增删查改）功能实现：?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?源码如下，欢迎指正！

版本1：

Test.c：

SeqList.c：

SeqList.h：

版本2：

附用SeqListInsert、SeqListErase版

Test.c：

SeqList.c:

SeqList.h:

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！???????? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ——By 作者：新晓·故知

《数据结构(C语言版)》实战项目之顺序表（增删查改）功能实现：博文内容：数据结构（C语言版）之顺序表及其功能实现（增删查改）博文作者：新晓·故知注： ★博文转载请注明出处。 ★博文仅供学习交流，禁止用于商业用途。问题导引：

在学习线性表的之顺序表后，可以通过C语言实现顺序表的增、删、查、改功能。

实现步骤：

具体实现步骤参见链接：

P2—＜顺序表＞《数据结构(C语言版)》

https://blog.csdn.net/m0_57859086/article/details/123438461

顺序表（增删查改）功能实现：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?源码如下，欢迎指正！版本1： Test.c： #include "SeqList.h" //尾插测试 void TestSeqList1() { //尾插 SeqList s; SeqListInit(&s); //这里&是取地址 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 0); SeqListPrint(&s); SeqListPushBack(&s, 10); SeqListPushBack(&s, 20); SeqListPrint(&s); //如果不小心传了空指针，须使用断言进行报错查找 //SeqListPrint(NULL); //测试越界 //int a[10]; a[10] = 1; a[11] = 1; //a[12] = 1; a[100] = 1; } //尾删测试 void TestSeqList2() { //尾插 SeqList s; SeqListInit(&s); //这里&是取地址 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 0); SeqListPrint(&s); //尾删，删除最后两个数据 SeqListPopBack(&s); SeqListPopBack(&s); SeqListPrint(&s); //删除完毕，且删多了 SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPrint(&s); //再次尾插数据 SeqListPushBack(&s, 10); SeqListPushBack(&s, 20); SeqListPrint(&s); } //头插测试 void TestSeqList3() { //扩容测试 /*int* p = (int*)malloc(sizeof(int) * 10); printf("%p\n", p); int* p1 = (int*)realloc(p, sizeof(int) * 100); printf("%p\n", p1);*/ SeqList s; SeqListInit(&s); //尾插 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); //头插 SeqListPushFront(&s, 0); SeqListPushFront(&s, -1); SeqListPrint(&s); } //头删测试 void TestSeqList4() { SeqList s; SeqListInit(&s); //尾插 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); //头插 SeqListPushFront(&s, 0); SeqListPushFront(&s, -1); SeqListPrint(&s); //头删 SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPrint(&s); SeqListPopFront(&s); SeqListPrint(&s); //再次头删，删多了 SeqListPopFront(&s); SeqListPopFront(&s); SeqListPrint(&s); //再次头插 SeqListPushFront(&s, 0); SeqListPushFront(&s, -1); SeqListPrint(&s); } //pos指定位置插入测试 void TestSeqList5() { SeqList s; SeqListInit(&s); //尾插 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); //pos指定位置插入数据 SeqListInsert(&s, 10, 100); SeqListInsert(&s, 1, 20); SeqListInsert(&s, 5, 50); SeqListInsert(&s, 0, 50); SeqListPrint(&s); //销毁释放内存 SeqListDestroy(&s); } //pos指定位置删除测试 void TestSeqList6() { SeqList s; SeqListInit(&s); //尾插 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); //头插 SeqListPushFront(&s, 0); SeqListPushFront(&s, -1); SeqListPrint(&s); //pos指定位置删除 SeqListErase(&s, 4); SeqListPrint(&s); SeqListErase(&s, 0); SeqListPrint(&s); SeqListErase(&s, 1); SeqListPrint(&s); } int main() { SeqList s; SeqListInit(&s); //这里&是取地址 TestSeqList1(); TestSeqList2(); TestSeqList3(); TestSeqList4(); TestSeqList5(); TestSeqList6(); return 0; } SeqList.c： #include "SeqList.h" //打印顺序表 void SeqListPrint(SeqList* psl) { //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝 assert(psl); for (int i = 0; i < psl->size; ++i) { printf("%d ", psl->a[i]); } printf("\n"); } //顺序表初始化 void SeqListInit(SeqList* psl) { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; } //顺序表销毁、释放内存 void SeqListDestroy(SeqList* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; } //检查容量，降低冗余度 void SeqListCheckCapacity(SeqList* psl) { // ?? if (psl->size == psl->capacity) { //relloc扩容 size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; //因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可 SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity = newCapacity; } } } //顺序表尾插 void SeqListPushBack(SeqList* psl, SLDataType x) { assert(psl); SeqListCheckCapacity(psl); psl->a[psl->size] = x; psl->size++; } //顺序表尾删 void SeqListPopBack(SeqList* psl) { assert(psl); //psl->a[psl->size - 1] = 0; //此语句是将删除后的覆盖为0，但这样做不太好 //原因：1.若原有最后一个为0，意义不大 2.若类型不为int，而是double或char，覆盖为0有误 //因为size标识有效数据，因此即使删除，数据还在capacity，即使删除后没有被覆盖，但不会访问 if (psl->size > 0) { psl->size--; } } //顺序表头插 void SeqListPushFront(SeqList* psl, SLDataType x) { assert(psl); SeqListCheckCapacity(psl); // 挪动数据，腾出头部空间 int end = psl->size - 1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x; psl->size++; //SeqListInsert(psl, 0, x); } //顺序表头删 void SeqListPopFront(SeqList* psl) { assert(psl); if (psl->size > 0) { //挪动数据覆盖删除 int begin = 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; ++begin; } --psl->size; } } // 在pos(指定位置）插入x //void SeqListInsert(SeqList* psl, int pos, SLDataType x) //解决整型提升形成的死循环,解决1 void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) { // 暴力检查 assert(psl); // 温和检查 if (pos > psl->size) { printf("pos 越界：%d\n", pos); return; //exit(-1); //直接终止程序，没必要 } // 暴力检查 //assert(pos <= psl->size); //检查后，根据需要是否增容 SeqListCheckCapacity(psl); //解决整型提升形成的死循环,解决2 //int end = psl->size-1; //while (end >=(int)pos) //{ // psl->a[end+1] = psl->a[end]; // --end; //} //解决整型提升形成的死循环,解决3 size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1]; --end; } psl->a[pos] = x; psl->size++; } // 删除pos(指定位置）的数据 void SeqListErase(SeqList* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t begin = pos + 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; ++begin; } psl->size--; } //按值查找 int SeqListFind(SeqList* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; ++i) { if (psl->a[i] == x) { return i; } } return -1; } SeqList.h： #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> // 要求：存储的数据从0开始，依次连续存储 // 静态的顺序表 // 问题：开小了，不够用。开大了，存在浪费。 //#define N 10000 //struct SeqList //{ // int a[N]; // int size; // 记录存储了多少个数据 //}; typedef int SLDataType; // 动态的顺序表 typedef struct SeqList { SLDataType* a; int size; // 存储数据个数 int capacity; // 存储空间大小 }SL, SeqList; //void SLInit(SeqList* psl); //顺序表初始化 void SeqListInit(SeqList* psl); //顺序表销毁 void SeqListDestroy(SeqList* psl); //打印顺序表 void SeqListPrint(SeqList* psl); //检查容量，降低冗余度 void SeqListCheckCapacity(SeqList* psl); // 时间复杂度是O(1) //尾插 void SeqListPushBack(SeqList* psl, SLDataType x); //尾删 void SeqListPopBack(SeqList* psl); // 时间复杂度是O(N) //头插 void SeqListPushFront(SeqList* psl, SLDataType x); //头删 void SeqListPopFront(SeqList* psl); // 在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); // 删除pos位置的数据 void SeqListErase(SeqList* psl, size_t pos); // 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x);

版本1测试示例：

版本2：附用SeqListInsert、SeqListErase版 Test.c： #include "SeqList.h" //附用SeqListInsert、SeqListErase版测试 void TestSeqList7() { SeqList s; SeqListInit(&s); //尾插 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPrint(&s); //头插 SeqListPushFront(&s, -1); SeqListPushFront(&s, -2); SeqListPrint(&s); //头删 SeqListPopFront(&s); SeqListPopFront(&s); SeqListPrint(&s); //尾删 SeqListPopBack(&s); SeqListPopBack(&s); SeqListPrint(&s); } int main() { SeqList s; SeqListInit(&s); //这里&是取地址 TestSeqList7(); return 0; } SeqList.c: #include "SeqList.h" //打印顺序表 void SeqListPrint(SeqList* psl) { //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝 assert(psl); for (int i = 0; i < psl->size; ++i) { printf("%d ", psl->a[i]); } printf("\n"); } //顺序表初始化 void SeqListInit(SeqList* psl) { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; } //顺序表销毁、释放内存 void SeqListDestroy(SeqList* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; } //检查容量，降低冗余度 void SeqListCheckCapacity(SeqList* psl) { // ?? if (psl->size == psl->capacity) { //relloc扩容 size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; //因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可 SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity = newCapacity; } } } //顺序表尾插--附用SeqListInsert版 void SeqListPushBack(SeqList* psl, SLDataType x) { assert(psl); SeqListInsert(psl, psl->size, x); } //顺序表尾删—附用SeqListErase版 void SeqListPopBack(SeqList* psl) { assert(psl); SeqListErase(psl, psl->size - 1); } //顺序表头插--附用SeqListInsert版 void SeqListPushFront(SeqList* psl, SLDataType x) { assert(psl); SeqListInsert(psl, 0, x); } //顺序表尾头删—附用SeqListErase版 void SeqListPopFront(SeqList* psl) { assert(psl); SeqListErase(psl, 0); } // 在pos(指定位置）插入x //void SeqListInsert(SeqList* psl, int pos, SLDataType x) //解决整型提升形成的死循环,解决1 void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) { // 暴力检查 assert(psl); // 温和检查 if (pos > psl->size) { printf("pos 越界：%d\n", pos); return; //exit(-1); //直接终止程序，没必要 } // 暴力检查 //assert(pos <= psl->size); //检查后，根据需要是否增容 SeqListCheckCapacity(psl); //解决整型提升形成的死循环,解决2 //int end = psl->size-1; //while (end >=(int)pos) //{ // psl->a[end+1] = psl->a[end]; // --end; //} //解决整型提升形成的死循环,解决3 size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1]; --end; } psl->a[pos] = x; psl->size++; } // 删除pos(指定位置）的数据 void SeqListErase(SeqList* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t begin = pos + 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; ++begin; } psl->size--; } //按值查找 int SeqListFind(SeqList* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; ++i) { if (psl->a[i] == x) { return i; } } return -1; } SeqList.h: #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> // 要求：存储的数据从0开始，依次连续存储 // 静态的顺序表 // 问题：开小了，不够用。开大了，存在浪费。 //#define N 10000 //struct SeqList //{ // int a[N]; // int size; // 记录存储了多少个数据 //}; typedef int SLDataType; // 动态的顺序表 typedef struct SeqList { SLDataType* a; int size; // 存储数据个数 int capacity; // 存储空间大小 }SL, SeqList; //void SLInit(SeqList* psl); //顺序表初始化 void SeqListInit(SeqList* psl); //顺序表销毁 void SeqListDestroy(SeqList* psl); //打印顺序表 void SeqListPrint(SeqList* psl); //检查容量，降低冗余度 void SeqListCheckCapacity(SeqList* psl); // 时间复杂度是O(1) //尾插 void SeqListPushBack(SeqList* psl, SLDataType x); //尾删 void SeqListPopBack(SeqList* psl); // 时间复杂度是O(N) //头插 void SeqListPushFront(SeqList* psl, SLDataType x); //头删 void SeqListPopFront(SeqList* psl); // 在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); // 删除pos位置的数据 void SeqListErase(SeqList* psl, size_t pos); // 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x);

附用SeqListInsert、SeqListErase测试示例：?

后记： ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！ ???????? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ——By 作者：新晓·故知

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。