线性表 - C语言实现

一、基本概念

线性表（Linear List）是最常用且最简单的一种数据结构，它是由 n 个数据元素（结点）组成的有限序列。

  • 线性表的基本操作包括：初始化、判空、判满、追加、插入、遍历 等

二、结构体定义

1
2
3
4
5
6
struct Arr
{
    int * pBase; //存储的是数组第一个元素的地址
    int len;     //数组所能容纳的最大元素的个数
    int cnt;     //当前数组有效元素的个数
};
成员 含义
pBase 指向动态分配数组的指针
len 线性表的最大容量
cnt 当前有效元素的个数

三、函数声明

1
2
3
4
5
6
void init_arr(struct Arr * pArr, int length);  //初始化线性表
void show_arr(struct Arr * pArr);              //显示线性表所有元素
bool append_arr(struct Arr * pArr, int val);   //在尾部追加元素
bool is_full(struct Arr * pArr);               //判断线性表是否已满
bool is_empty(struct Arr * pArr);              //判断线性表是否为空
bool insert_arr(struct Arr * pArr, int pos, int val); //在指定位置插入元素

四、功能函数实现

1. 初始化线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void init_arr(struct Arr * pArr, int length)
{
    //为动态数组分配内存空间，大小（字节数） = sizeof(int) * length
    pArr->pBase = (int *) malloc(sizeof(int) * length);
    
    //分配内存也有可能不成功
    if (pArr->pBase == NULL)
    {
        printf("内存分配不成功！！");
        exit(-1);
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
    }
}

2. 判空操作

1
2
3
4
5
6
7
bool is_empty(struct Arr * pArr)
{
    if (pArr->cnt == 0)
        return true;
    else
        return false;
}

3. 判满操作

1
2
3
4
5
6
7
bool is_full(struct Arr * pArr)
{
    if (pArr->cnt == pArr->len)
        return true;
    else
        return false;
}

4. 追加元素（在尾部添加）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool append_arr(struct Arr * pArr, int val)
{
    //如果数组已经满了，不能够添加元素
    if (is_full(pArr))
    {
        printf("数组已满，添加失败");
        return false;
    }
    else
    {
        pArr->pBase[pArr->cnt] = val;
        pArr->cnt++;
        return true;
    }
}

5. 插入元素（在指定位置插入）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool insert_arr(struct Arr * pArr, int pos, int val)
{
    int i;
    
    if (is_full(pArr))
        return false;
        
    if (pos < 1 || pos > pArr->cnt + 1)
        return false;
        
    //从后往前移动元素，空出插入位置
    for (i = pArr->cnt - 1; i >= pos - 1; --i)
    {
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    
    pArr->pBase[pos - 1] = val;
    pArr->cnt++;
    return true;
}

注意：pos 的值从 1 开始计数

6. 遍历显示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void show_arr(struct Arr * pArr)
{
    int i = 0;
    
    if (is_empty(pArr))
    {
        printf("数组为空！！");
    }
    else
    {
        for (i = 0; i < pArr->cnt; i++)
        {
            printf("%d", pArr->pBase[i]);
        }
        printf("\n");
    }
}

五、使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    struct Arr arr;
    
    //初始化一个容量为6的线性表
    init_arr(&arr, 6);
    
    //在尾部追加元素
    append_arr(&arr, 1);
    append_arr(&arr, 2);
    append_arr(&arr, 3);
    
    //显示当前线性表
    show_arr(&arr);  //输出: 1 2 3
    
    //在第8个位置插入元素99（实际插入会失败，pos无效）
    insert_arr(&arr, 8, 99);
    
    //正确示例：在第4个位置插入元素99
    insert_arr(&arr, 4, 99);
    show_arr(&arr);  //输出: 1 2 3 99
    
    return 0;
}

六、图解插入操作

1
2
3
4
5
6
初始状态: [1, 2, 3]           (cnt = 3)

在位置2插入99:
  从后往前移动: [1, 2, 3, 3] → [1, 2, 2, 3] → [1, 2, 99, 3]
  
插入后: [1, 2, 99, 3]          (cnt = 4)

七、涉及的头文件

头文件 作用
stdio.h 标准输入输出
malloc.h 动态内存分配
stdlib.h exit() 函数
stdbool.h 布尔类型 (true/false)

八、关键知识点

  1. 动态内存分配：使用 malloc() 函数在堆区分配内存
  2. 指针操作：通过结构体指针访问成员（pArr->cnt）
  3. 边界检查：插入/追加前需检查线性表是否已满
  4. 位置索引：用户使用的位置从 1 开始，代码中需转换为 0 开始的下标

九、完整代码下载

源代码文件：Linear-List-from-Scratch-with-C.c