顺序表的C语言实现与解析

引言

作者主页：共享家9527-CSDN博客

编辑代码结构概览

头文件（ ST.h ）要点

源文件要点

1. 顺序表初始化（ SeqListInit ）：

2. 顺序表销毁（ SeqListDestroy ）：

3. 顺序表打印（ SeqListPrint ）：

4. 检查并增容（ cheakfull ）：

5. 尾插法（ SeqListPushBack ）：

6. 头插法（ SeqListPushFront ）：

7. 头删法（ SeqListPopFront ）：

8. 尾删法（ SeqListPopBack ）：

9. 顺序表查找（ SeqListFind ）：

10. 在指定位置插入元素（ SeqListInsert ）：

编辑注意事项

引言

顺序表是一种线性数据结构，它使用一组连续的内存单元来存储数据元素。在C语言中，我们可以通过数组和一些辅助变量来实现顺序表。本文将详细解析上述提供的C语言代码，涵盖顺序表的初始化、销毁、插入、删除、查找等基本操作。

作者主页：共享家9527-CSDN博客

代码结构概览

整个代码分为两部分：头文件（ .h ）和源文件（ .c ）。头文件定义了顺序表的数据结构以及函数声明，源文件则包含了函数的具体实现。

头文件（ ST.h ）要点

c#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

1. 数据类型定义： SLDateType  被定义为 int ，这是顺序表中元素的数据类型。如果需要存储其他类型的数据，只需修改这一处定义。

2. 顺序表结构体： SeqList  结构体包含三个成员：

- a  是一个指向 SLDateType  类型的指针，用于动态分配内存来存储顺序表的元素。

- size  表示当前顺序表中已存储的元素个数。

- capacity  表示顺序表当前分配的内存容量，即最多能存储的元素个数。

3. 函数声明：声明了一系列对顺序表进行操作的函数，包括初始化、销毁、打印、插入、删除、查找等。这些函数的实现将在源文件中给出。

源文件要点


c#define _CRT_SECURE_NO_WARNINGS
#include"ST.h"void SeqListInit(SeqList* ps)
{assert(ps);ps->a = (SLDateType*)malloc(sizeof(SLDateType));if (ps->a == NULL){perror("malloc false");return;}ps->size = 0;ps->capacity = 4;
}

1. 顺序表初始化（ SeqListInit ）：

- 使用 assert(ps)  来确保传入的顺序表指针不为空。这是一种防御性编程，有助于在开发阶段发现潜在的空指针引用错误。

- 使用 malloc  函数为顺序表分配初始内存，大小为一个 SLDateType  类型的空间。如果 malloc  失败（返回 NULL ），使用 perror  打印错误信息并返回。

- 将 size  初始化为0，表示顺序表中还没有元素， capacity  初始化为4，表示初始分配的内存可以容纳4个元素。

 
cvoid SeqListDestroy(SeqList* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;ps = NULL;
}

2. 顺序表销毁（ SeqListDestroy ）：

- 同样使用 assert(ps)  确保指针有效。

- 使用 free  释放顺序表分配的内存，防止内存泄漏。

- 将 ps->a  置为 NULL ，避免悬空指针。同时将 size  和 capacity  置为0，并尝试将 ps  指针也置为 NULL （不过这在函数外部不会生效，因为函数参数是值传递）。

 
cvoid SeqListPrint(SeqList* ps)
{assert(ps);for (int i = 0;i < ps->size;i++){printf("%d ", ps->a[i]);}printf("\n");
}

3. 顺序表打印（ SeqListPrint ）：

- 通过遍历顺序表，从索引0到 size - 1 ，打印每个元素的值，最后换行。

 
cvoid cheakfull(SeqList* ps)
{assert(ps);if (ps->capacity == ps->size){SLDateType* tmp = (SeqList*)realloc(ps->a, ps->capacity * 2);if (tmp == NULL){perror("realloc false");return;}ps->a = tmp;ps->capacity *= 2;printf("增容成功\n");}
}

4. 检查并增容（ cheakfull ）：

- 检查顺序表当前元素个数 size  是否等于容量 capacity ，如果相等则表示顺序表已满，需要增容。

- 使用 realloc  函数将顺序表的内存容量扩大为原来的2倍。如果 realloc  失败，打印错误信息并返回。

- 更新 ps->a  指向新分配的内存，并将 capacity  更新为原来的2倍。

 
cvoid SeqListPushBack(SeqList* ps, SLDateType x)
{cheakfull(ps);assert(ps);ps->a[ps->size] = x;ps->size++;
}

5. 尾插法（ SeqListPushBack ）：

- 首先调用 cheakfull 函数检查顺序表是否已满并进行增容。

- 将元素 x 插入到顺序表的末尾（索引为 size 的位置），然后 size 加1。

 
cvoid SeqListPushFront(SeqList* ps, SLDateType x) 
{assert(ps);cheakfull(ps);for (int i = ps->size;i > 0;i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->size++;
}

6. 头插法（ SeqListPushFront ）：

- 检查顺序表是否需要增容。

- 通过循环将顺序表中已有的元素从后往前依次向后移动一位，然后将新元素 x 插入到索引0的位置，最后 size 加1。注意这里循环条件是 i > 0 ，而不是 i >= 0 ，否则会导致数组越界。

 
cvoid SeqListPopFront(SeqList* ps) {assert(ps);for (int i = 0;i < ps->size - 1;i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

7. 头删法（ SeqListPopFront ）：

- 通过循环将顺序表中从索引1开始的元素依次向前移动一位，覆盖掉原来索引0的元素，然后 size 减1。注意这里循环条件是 i < ps->size - 1 ，防止数组越界。

 
cvoid SeqListPopBack(SeqList* ps) {assert(ps);assert(ps->size>0);ps->size--;
}

8. 尾删法（ SeqListPopBack ）：

- 首先检查顺序表中是否有元素（ size > 0 ），然后直接将 size 减1，相当于逻辑上删除了最后一个元素，而不需要实际修改数组中的元素值。

 
c// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x) {assert(ps);assert(ps->size > 0);for (int i = 0;i < ps->size;i++){if (ps->a[i] == x){return i;}}return -1;
}

9. 顺序表查找（ SeqListFind ）：

- 遍历顺序表，从索引0到 size - 1 ，检查每个元素是否等于要查找的元素 x 。如果找到，返回该元素的索引；如果遍历完整个顺序表都没有找到，则返回 -1。

 
c// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x) {assert(ps);assert(ps->size >= pos);cheakfull(ps);for (int i = ps->size;i > pos;i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->size++;
}

10. 在指定位置插入元素（ SeqListInsert ）：

- 检查传入的位置 pos 是否合法（ pos 小于等于当前 size ）。

- 检查顺序表是否需要增容。

- 通过循环将从索引 size 到 pos + 1 的元素依次向后移动一位，然后将新元素 x 插入到索引 pos 的位置，最后 size 加1。

注意事项

1. 内存管理：在使用 malloc  和 realloc  分配内存时，一定要检查返回值是否为 NULL ，以防止内存操作错误。使用完内存后，要及时调用 free  释放内存，避免内存泄漏。

2. 边界检查：在进行插入、删除、查找等操作时，要仔细检查数组索引是否越界。使用 assert  进行参数合法性检查是一个很好的习惯，可以帮助在开发阶段发现潜在的错误。

3. 函数参数传递：注意C语言函数参数是值传递，如果需要修改传入的指针本身（如在 SeqListDestroy  中尝试将 ps  置为 NULL ），需要使用指针的指针或者返回修改后的指针。

通过上述对顺序表实现代码的详细解析，希望读者能够更好地理解顺序表这种数据结构在C语言中的实现方式以及相关操作的要点和注意事项。