/************************************************************* 顺序表的实现之增删功能 实现文件 更新于2020年4月13日 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include "Seqlist.h" void SL_Initiate(SqList &L) // 顺序表的初始化，即构造一个空的顺序表 { L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE); L.length=0; } void SL_Free(SqList &L) // 释放顺序表 { free(L.elem); } bool SL_IsEmpty(SqList L) // 判断顺序表是否空 { return L.length==0; } bool SL_IsFull(SqList L) // 判断顺序表是否满 { return L.length==MAXSIZE; } void SL_Create(SqList &L,int n) // 输入n个数据元素，创建一个顺序表L { int i; L.length=n; for(i=0; i<n; i++) scanf("%d", &L.elem[i]); } void SL_Print(SqList L) // 输出整个顺序表 { if (L.length==0) { printf("The slist is empty.\n"); return; } for (int i=0; i<L.length; i++) printf("%d ", L.elem[i]); printf("\n"); } void SL_InsAt(SqList &L, int i, ElemType e) // 在顺序表的第i个位置插入新元素e, 即在元素L.elem[i-1]之前插入 // i的有效范围[1,L.length+1] { // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ } void SL_DelAt(SqList &L, int i) // 删除顺序表L的第i个元素 //i的有效范围[1,L.length] { // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ } void SL_DelValue(SqList &L, ElemType x) // 删除第一个值为x的元素 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ }

### 顺序表的插入和删除操作 #### 插入操作 在顺序表中实现插入功能时，通常需要考虑以下几个方面： - **位置合法性检查**：确保要插入的位置索引合法。 - **空间扩展**：如果当前顺序表已满，则需动态扩容以容纳新元素。 - **数据移动**：为了保持顺序表中原有数据的相对次序，在目标位置之后的数据需要向后移动一位。 以下是基于C语言的顺序表插入函数实现： ```c #include <stdio.h> #include <stdlib.h> #define INIT_SIZE 10 // 初始容量 #define SLDateType int // 数据类型定义 typedef struct { SLDateType *a; // 动态数组指针 size_t size; // 当前有效数据数量 size_t capacity; // 容量 } SeqList; // 初始化顺序表 void SeqListInit(SeqList *ps) { ps->a = (SLDateType *)malloc(INIT_SIZE * sizeof(SLDateType)); if (!ps->a) exit(-1); ps->capacity = INIT_SIZE; ps->size = 0; } // 扩容逻辑 void Resize(SeqList *ps, size_t new_capacity) { SLDateType *tmp = (SLDateType *)realloc(ps->a, new_capacity * sizeof(SLDateType)); if (!tmp) exit(-1); ps->a = tmp; ps->capacity = new_capacity; } // 插入元素到指定位置 int SeqListInsert(SeqList *ps, size_t pos, SLDateType value) { if (pos < 0 || pos > ps->size) return 0; // 检查位置是否越界 if (ps->size >= ps->capacity) { // 如果满了则扩容 Resize(ps, ps->capacity * 2); } for (size_t i = ps->size; i > pos; --i) { // 将后续元素右移 ps->a[i] = ps->a[i - 1]; } ps->a[pos] = value; // 插入新值 ++ps->size; // 更新有效数据数 return 1; } ``` 上述代码实现了顺序表的插入功能[^1]。其中`SeqListInsert`函数负责将给定值插入到指定位置，并调整原有数据结构来适应新的排列方式。 --- #### 删除操作 对于顺序表中的删除操作，主要涉及以下几点： - **位置合法性验证**：确认待删除位置是否存在有效数据。 - **数据覆盖**：从被删节点后的第一个元素起向前依次填补空位。 - **更新状态信息**：减少顺序表的有效数据计数值；当剩余空间过多时可选择缩减内存占用。 下面是具体的C语言实现方法： ```c // 删除指定位置上的元素 int SeqListErase(SeqList *ps, size_t pos) { if (pos < 0 || pos >= ps->size) return 0; // 越界检测失败返回错误标志 for (size_t i = pos; i < ps->size - 1; ++i) { // 向左平移后面的项填充空白处 ps->a[i] = ps->a[i + 1]; } --ps->size; // 减少记录数目 return 1; } // 销毁顺序表释放资源 void SeqListDestroy(SeqList *ps) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } ``` 此部分展示了如何安全有效地执行单个元素的移除过程[^2]^。注意这里并未立即缩小分配的空间大小，仅减少了实际使用的项目总数以便于未来可能再次利用这些区域而不必频繁申请额外存储区段。 --- ### 总结说明 以上分别介绍了两种基本的操作——插入与删除的具体算法思路以及对应的源码片段。它们共同构成了管理简单线性序列的核心工具集之一。通过合理运用这两种机制可以灵活构建满足特定需求的应用场景下的容器解决方案。