线性表的基本操作（GetElem&LocateElem）
一、GetElem(L,i,&e)
按位查找：获取表L中第 i 个位置元素的值
代码实现1 – 静态分配方式
#include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 10 // 顺序表最大容量
// 顺序表结构体定义
typedef struct {
int data[MAXSIZE]; // 存储数据元素的数组
int length; // 当前长度
} SqList;
/**
* 按位查找操作：获取顺序表中第i个位置的元素
* @param L 顺序表
* @param i 要查找的位置（从1开始计数）
* @param e 用于存储查找到的元素的指针
* @return 查找成功返回true，失败返回false
*/
bool GetElem(SqList L, int i, int *e) {
// 检查位置有效性：i应在1到length之间，且顺序表不为空
if (i < 1 || i > L.length) {
return false;
}
*e = L.data[i - 1]; // 数组下标从0开始，第i个元素对应下标i-1
return true;
}
// 测试主函数
int main() {
SqList list = { // 初始化一个顺序表
.data = {10, 20, 30, 40, 50},
.length = 5
};
int position = 3; // 要查找的位置（第3个元素）
int element;
if (GetElem(list, position, &element)) {
printf("顺序表中第%d个元素是：%d\n", position, element);
} else {
printf("查找失败！位置%d超出顺序表有效范围\n", position);
}
return 0;
}
运行结果：
代码实现2 – 动态分配方式
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义一个顺序表
typedef struct {
int* data; // 注意这里是动态数组的指针
int length;
int MaxSize;
}SeqList;
/**
* 初始化顺序表
* @param list 顺序表指针
* @param initCapacity 初始容量
* @return 初始化成功返回true，失败返回false
*/
bool InitList(SeqList* L, int initCapacity)
{
L->data = (int*)malloc(initCapacity * sizeof(int));
if (L->data == NULL) // 内存不足
{
return false;
}
L->length = 0;
L->MaxSize = initCapacity;
return true;
}
/**
* 按位查找操作：获取顺序表中第i个位置的元素
* @param list 顺序表指针
* @param i 要查找的位置（从1开始计数）
* @param e 用于存储查找到的元素的指针
* @return 查找成功返回true，失败返回false
*/
bool GetElem(SeqList* L, int i, int* e)
{
// 检查位置有效性：
if (i<1 || i>L->length)
{
return false;
}
*e = L->data[i - 1];
return true;
}
/**
* 释放顺序表内存
* @param list 顺序表指针
*/
void DestroyList(SeqList* L)
{
free(L->data);
L->data = NULL;
L->length = 0;
L->MaxSize = 0;
}
// 测试
int main()
{
SeqList list;
if (!InitList(&list, 10))
{
printf("内存分配失败\n");
return 1;
}
// 初始化测试数据
for (int i = 0;i < 5;i++)
{
list.data[i] = (i + 1) * 10;
list.length++;
}
int pos = 3;//查找第三个元素
int result;
if (GetElem(&list, pos, &result))
{
printf("第%d个元素是：%d\n",pos, result);
}
else{
printf("位置无效\n");
}
DestroyList(&list);
return 0;
}运行结果：
代码说明：
- 动态内存分配：使用
malloc分配内存，支持按需调整容量 - 结构体改进：增加
capacity字段跟踪最大容量 - 关键函数：
InitList：初始化顺序表并分配初始内存GetElement：按位查找（与静态版本逻辑相同）DestroyList：释放动态分配的内存
- 内存安全：
- 使用
malloc/free管理内存 - 包含错误处理（内存分配失败检查）
- 防止内存泄漏（通过
DestroyList释放资源）
- 使用
- 测试用例：创建包含 5 个元素的顺序表，查找第 3 个元素（值为 30）
注意点：
- *e = L->data[i – 1]; 数组从0开始，线性表位序从1开始
- 动态分配方式下初始化线性表
bool InitList(SeqList* L, int initCapacity)
{
L->data = (int*)malloc(initCapacity * sizeof(int));
if (L->data == NULL) // 内存不足
{
return false;
}
L->length = 0;
L->MaxSize = initCapacity;
return true;
}- 动态分配方式定义线性表，定义的是动态数组的指针
typedef struct {
int* data; // 注意这里是动态数组的指针
int length;
int MaxSize;
}SeqList;- 区分动态和静态分配定义的顺序表的名称：前者为SeqList,后者为SqList
- Seq 是 Sequential 的缩写，意为 “顺序的”。
- List 表示 “列表”。
- SeqList 直译为 Sequential List，强调元素按顺序存储的特性。
动态顺序表（SeqList）
typedef struct {
int *data; // 动态分配数组
int length;
int capacity;
} SeqList;静态顺序表（SqList）
typedef struct {
int data[MAX_SIZE]; // 固定大小数组
int length;
} SqList;二、LocateElem(L,e)
按值查找：在表L中查找具有给定关键字值的元素
代码实现1 – 静态分配方式
#include <stdio.h>
#define MAX_SIZE 100 // 顺序表最大容量
typedef int ElemType; // 元素类型（可根据需求修改）
// 顺序表结构体定义
typedef struct {
ElemType data[MAX_SIZE]; // 存储数据的数组
int length; // 当前长度（有效元素个数）
} SqList;
/**
* 按值查找元素的位置（1-based）
* @param L 顺序表实例（输入）
* @param e 要查找的目标值
* @return 第一个匹配元素的位置（1~length），未找到返回0
*/
int LocateElem(const SqList* L, ElemType e) {
// 遍历顺序表的有效元素
for (int i = 0; i < L->length; i++) {
if (L->data[i] == e) { // 值匹配判断
return i + 1; // 转换为1-based位置
}
}
return 0; // 遍历完未找到
}
// 测试主函数
int main() {
SqList list = {
.data = {5, 12, 8, 3, 15}, // 初始化数据
.length = 5 // 有效元素个数
};
// 测试用例1：存在的元素
ElemType target1 = 8;
int pos1 = LocateElem(&list, target1);
printf("查找元素 %d，位置：%d\n", target1, pos1); // 应输出3
// 测试用例2：不存在的元素
ElemType target2 = 20;
int pos2 = LocateElem(&list, target2);
printf("查找元素 %d，位置：%d\n", target2, pos2); // 应输出0
return 0;
}
输出结果
代码实现2 – 动态分配方式
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElemType; // 元素类型（可根据需求修改为float/char等）
// 动态顺序表结构体（优化类型定义）
typedef struct {
ElemType* data; // 动态存储数组
int length; // 当前元素个数（用int更安全）
int max_size; // 最大容量（用int更合理）
} SeqList;
/**
* 初始化动态顺序表
* @param L 顺序表指针
* @param init_capacity 初始容量（建议>=1）
* @return 初始化成功返回true，失败返回false
*/
bool InitList(SeqList* L, int init_capacity) {
if (init_capacity <= 0) { // 增加参数校验
printf("错误：初始容量必须大于0\n");
return false;
}
L->data = (ElemType*)malloc(init_capacity * sizeof(ElemType));
if (!L->data) {
printf("错误：内存分配失败\n");
return false;
}
L->length = 0;
L->max_size = init_capacity;
return true;
}
/**
* 按值查找元素位置（优化逻辑）
* @param L 顺序表指针
* @param e 目标元素值
* @return 第一个匹配元素的索引（0-based，未找到返回-1）
*/
int LocateElem(const SeqList* L, ElemType e) {
if (L->length == 0) { // 空表快速判断
return -1;
}
for (int i = 0; i < L->length; i++) {
if (L->data[i] == e) {
return i; // 返回0-based索引（更符合数组特性）
}
}
return -1; // 明确用-1表示未找到（避免0歧义）
}
/**
* 销毁顺序表（增强安全性）
* @param L 顺序表指针
*/
void DestroyList(SeqList* L) {
if (L->data) { // 避免重复释放
free(L->data);
L->data = NULL; // 置空指针防止野指针
}
L->length = 0;
L->max_size = 0;
}
// 测试主函数（补充完整测试逻辑）
int main() {
SeqList L;
const int INIT_CAPACITY = 5; // 定义初始容量
// 初始化测试
if (!InitList(&L, INIT_CAPACITY)) {
return 1; // 初始化失败直接退出
}
// 插入测试数据（模拟实际使用场景）
ElemType test_data[] = {10, 20, 30, 40, 50};
for (int i = 0; i < INIT_CAPACITY; i++) {
L.data[i] = test_data[i]; // 假设表未满（实际需添加扩容逻辑）
L.length++;
}
// 查找存在的元素（测试1）
ElemType target = 30;
int pos = LocateElem(&L, target);
if (pos != -1) {
printf("元素 %d 找到，索引（0-based）：%d\n", target, pos); // 输出2
} else {
printf("元素 %d 未找到\n", target);
}
// 查找不存在的元素（测试2）
target = 99;
pos = LocateElem(&L, target);
if (pos != -1) {
printf("元素 %d 找到，索引（0-based）：%d\n", target, pos);
} else {
printf("元素 %d 未找到\n", target); // 输出未找到
}
// 查找空表情况（测试3）
SeqList empty_list;
InitList(&empty_list, 2); // 初始化空表（length=0）
pos = LocateElem(&empty_list, 10);
printf("空表查找结果：%d\n", pos); // 输出-1
// 释放内存
DestroyList(&L);
DestroyList(&empty_list);
return 0;
}
运行结果：
注意事项：
- 动态分配定义的线性表，不需要一开始赋值
SeqList L;三、动态分配方式注意事项
动态分配顺序表时需特别注意内存管理的安全性和正确性，以下是核心注意事项及具体说明：
1. 内存分配时的空指针检查
动态分配（malloc/realloc）可能因内存不足返回空指针，必须强制检查返回值，避免后续操作访问空指针导致程序崩溃。
示例：
ElemType* data = (ElemType*)malloc(capacity * sizeof(ElemType));
if (data == NULL) { // 必须检查
printf("内存分配失败！");
exit(EXIT_FAILURE); // 或返回错误码
}
2. 避免内存泄漏
动态分配的内存必须显式释放（通过free），否则会造成内存泄漏（尤其在循环或长期运行的程序中）。
注意：
- 释放后需将指针置空（
data = NULL），避免后续误操作访问已释放的内存（野指针）。 - 多次调用
free同一指针会导致未定义行为（需确保只释放一次）。
3. 容量管理的合理性
- 初始容量：根据实际需求设置（如初始容量过小会频繁扩容，过大会浪费内存）。
- 扩容策略（如需动态扩容）：
- 常用倍增法（如每次扩容为当前容量的 2 倍），减少扩容次数（时间复杂度均摊 O (1)）；
- 避免线性扩容（如每次 + 1），否则插入操作时间复杂度退化为 O (n)。
示例（扩容函数）：
bool ResizeList(SeqList* L, int new_capacity) {
ElemType* new_data = (ElemType*)realloc(L->data, new_capacity * sizeof(ElemType));
if (new_data == NULL) return false; // 扩容失败
L->data = new_data;
L->max_size = new_capacity; // 更新最大容量
return true;
}
4. 防止越界访问
顺序表的有效元素范围是[0, length-1]，所有操作（如查找、插入）必须严格限制在该范围内，避免访问data[length]及之后的内存（越界会导致未定义行为）。
示例（查找函数的安全检查）：
int LocateElem(const SeqList* L, ElemType e) {
if (L->length == 0) return -1; // 空表直接返回
for (int i = 0; i < L->length; i++) { // 严格限制i < length
if (L->data[i] == e) return i;
}
return -1;
}
5. realloc的特殊注意事项
realloc可能移动内存块（原内存被释放，新内存地址不同），因此必须用临时变量接收返回值，避免原指针丢失。
错误示例：
// 错误：若realloc失败，原data指针会被覆盖为NULL
L->data = realloc(L->data, new_capacity * sizeof(ElemType));
正确示例：
ElemType* temp = realloc(L->data, new_capacity * sizeof(ElemType));
if (temp != NULL) { // 扩容成功
L->data = temp;
L->max_size = new_capacity;
} // 扩容失败时原data指针仍有效
6. 类型与内存对齐
malloc的参数必须是元素个数 × sizeof(元素类型)，确保内存大小正确。- 若
ElemType是结构体，需注意结构体的内存对齐（malloc会自动处理对齐，无需额外操作）。
7. 生命周期匹配
动态分配的内存生命周期由程序控制，需确保：
- 顺序表使用期间（如查找、插入）内存未被释放；
- 顺序表不再使用时（如程序结束前）及时释放内存。
总结表格
| 注意事项 | 具体操作 |
|---|---|
| 空指针检查 | malloc/realloc后检查返回值是否为NULL |
| 内存泄漏避免 | 不再使用时调用free，并将指针置空 |
| 容量管理 | 合理设置初始容量，扩容采用倍增法（如 2 倍） |
| 越界访问防止 | 所有操作限制在0 ≤ i < length范围内 |
realloc安全使用 | 用临时变量接收返回值，避免原指针丢失 |
| 类型与内存对齐 | malloc参数为元素个数 × sizeof(ElemType) |
这些注意事项能确保动态顺序表在内存管理上的安全性和效率，避免常见的运行时错误（如崩溃、内存泄漏）。
本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
