投稿
  1. 何大锤的博客首页
  2. 编程导航
  3. 数据结构

06 – 第二章数据结构线性表 – 顺序表代码实现（顺序表查找操作）

何大锤 • • 数据结构 • 阅读 15

线性表的基本操作（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;
}

运行结果：

06 - 第二章数据结构线性表 - 顺序表代码实现（顺序表查找操作）

代码实现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;
}

运行结果：

06 - 第二章数据结构线性表 - 顺序表代码实现（顺序表查找操作）

代码说明：

  • 动态内存分配：使用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;
}

输出结果

06 - 第二章数据结构线性表 - 顺序表代码实现（顺序表查找操作）

代码实现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;
}

运行结果：

06 - 第二章数据结构线性表 - 顺序表代码实现（顺序表查找操作）

注意事项：

  • 动态分配定义的线性表，不需要一开始赋值
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)

这些注意事项能确保动态顺序表在内存管理上的安全性和效率，避免常见的运行时错误（如崩溃、内存泄漏）。

本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客

赞 (0)
何大锤的头像何大锤管理团队
0 0

相关推荐

  • 第二章数据结构线性表 - 单链表动画演示 数据结构

    第二章数据结构线性表 – 单链表动画演示

    一、带头结点单链表 1、头插法创建-动画演示 2、尾插法创建-动画演示 3、插入操作 插入表头 插入中间 插入表尾

    何大锤的头像 何大锤
    2025年6月16日
    800
  • 第二章数据结构线性表 - 单链表的插入和删除操作 数据结构

    第二章数据结构线性表 – 单链表的插入和删除操作

    一、知识要点 1.1 按位序插入 – 带头结点 1.2 按位序插入 – 不带头结点 1.3 指定结点的后插操作 1.4 指定结点的前插操作 1.5 按位序删除（带头结点） 1.6 指定结点删除 1.7 封装的好处 二、单链表 – 插入操作 3.1 按位序插入（带头结点） – ListInsert(&L，…

    何大锤的头像 何大锤
    2025年6月16日
    300
  • 第二章数据结构线性表 - 单链表的定义与初始化 数据结构

    第二章数据结构线性表 – 单链表的定义与初始化

    一、单链表的定义和表示 – 知识要点 1.1 定义单链表 1.2 带头结点单链表的初始化 二、单链表 – 定义与初始化 1.1 带头结点代码实现 1.1.1 C语言实现 实现算法实现 测试主函数 运行结果 运行过程 带头结点单链表的初始化的注意点 1.1.2 C++单链表定义及初始化 运行结果 1.2 不带头结点代码实现 1.2.1 …

    何大锤的头像 何大锤
    2025年6月14日
    700
  • 第二章数据结构线性表 - 单链表概念 数据结构

    第二章数据结构线性表 – 单链表概念

    一、引言 1.1 知识框架 1.2 有了数组为什么还要链表？ 在前面我们介绍过数组，数组中元素是存储在连续的内存位置在声明数组时，我们可以指定数组的大小，但这将限制数组可以存储的元素数量 例如我们声明的是 int arr[10]，那么arr数组最多可以存储10个数据元素 但是我们事先不知道元素的大小呢？ 我们该如何去做？ 当然首先想到的是申请一个足够大的数组…

    何大锤的头像 何大锤
    2025年6月14日
    300
  • 08 - 数据结构基础知识补充 数据结构

    08 – 数据结构基础知识补充

    内存分类 一、静态 / 全局内存（程序运行期间一直存在） 特点：全局变量和静态变量（用static声明）的内存，在程序启动时分配，程序结束才释放。通俗理解：像「公共仓库」，一旦创建就一直存在，所有需要的地方都能访问（全局变量），或在特定范围内持续保留（静态变量）。 解释： 二、自动内存（栈内存，函数调用时临时创建） 特点：函数内的普通局部变量（不用stati…

    何大锤的头像 何大锤
    2025年6月6日
    1100

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

2211932694

在线咨询： QQ交谈

邮件：hdcblog1999@163.com

工作时间：周一至周五，9:30-18:30，节假日休息

关注微信
网站建设中ing......