数据结构-线性表顺序存储(C语言实现)

1. 导入头文件

编写代码过程中，涉及动态内存分配等常用的函数，需要引入如下头文件

#include<stdio.h>
#include<stdlib.h>

2. 存储结构体的定义

顺序存储所使用的内存是连续的，本质就是使用数组来存储数据，定义的结构体中使用 pData 来存放添加的数据，pData 表示是一个指针变量，指向数组的首地址，len表示数组的容量，cnt表示数组中元素的个数

// 定义一个 结构体
struct ArrayList
{
    int * pData;    // 数据存放数组
    int len;        // 数组长度
    int cnt;        // 元素个数
};

3. 对操作进行声明

void init(struct ArrayList * pArr, int length);    // 初始化
int isEmpty(struct ArrayList * pArr); // 是否为空
void show(struct ArrayList * pArr);    // 列出所有元素
int isFull(struct ArrayList * pArr);   // 是否满了
void append(struct ArrayList * pArr, int val);      // 追加
void insert(struct ArrayList * pArr, int pos, int val);  // 插入
void delete(struct ArrayList * pArr, int pos, int * pVal);  // 删除

4. 初始化

初始化操作就是根据传入的 length 生成一个数组，sizeof 会根据编译器来计算所占的字节数，不同编译器大小不一样，不能写死，使用 malloc 函数分配内存时需要进行强转，目的是对内配的内存进行大小划分，如果不加 (int *) 则只是返回这块内存的初始地址，不清楚这块内存要按多大切分使用。初始化时要对 len 和 cnt 进行初始化。

void init(struct ArrayList * pAarr, int length)
{
    pAarr->pData = (int * )malloc(sizeof(struct ArrayList) * length);
    if (NULL == pAarr->pData)
    {
        printf("memory allocate failed!");
        exit(-1);
    } else
    {
        pAarr->len = length;
        pAarr->cnt = 0;
    }
}

5. 判断是否为空

初始化时 cnt = 0，如果 cnt = 0 表示数组是空的

int isEmpty(struct ArrayList * pArr)
{
    if (pArr->cnt == 0)
    {
        return 1;
    }
    return 0;
}

6. 展示所有元素

void show(struct ArrayList * pArr)
{
    if (isEmpty(pArr))
    {
        printf("数组元素为空");
    } else
    {
        for (int i = 0; i < pArr->cnt; ++i) {
            printf("%d ", pArr->pData[i]);
            printf("\n");
        }
    }
}

7. 是否满了

数组的容量 pArr-len 是固定的，当元素个数 pArr->cnt == 容量时，则表示数组已满

int isFull(struct ArrayList * pArr)
{
    if (pArr->len == pArr->cnt)
    {
        return 1;
    }
    return 0;
}

8. 追加元素

元素追加后确保计数 cnt 也增加

void append(struct ArrayList * pArr, int val)
{
    if (isFull(pArr))
    {
        printf("数组已满!\n");
        return;
    }
    pArr->pData[pArr->cnt] = val;
    pArr->cnt++;
}

9. 指定位置插入元素

如果插入的是中间位置，如果将该位置后的元素进行后移，后移之后将元素插入

void insert(struct ArrayList * pArr, int pos, int val)
{

    int i;
    // 判断是否 full
    if (isFull(pArr))
    {
        printf("数组已满!\n");
        return;
    }
    // 检查 pos 取值
    if (pos< 1 || pos > pArr->cnt+1)
    {
        printf("invalid pos!\n");
        return;
    }

    for (i = pArr->cnt ; i > pos-1 ; --i) {
        pArr->pData[i] = pArr->pData[i-1];
    }
    pArr->pData[pos-1] = val;
    pArr->cnt++;

}

10. 指定位置删除元素

需要将删除的元素返回，所以参数中 pVal 用来存储删除元素

void delete(struct ArrayList * pArr, int pos, int * pVal)
{
    int i;
    if (isEmpty(pArr))
    {
        printf("数组为空!\n");
        return;
    }

    if (pos < 1 || pos > pArr->cnt)
    {
        printf("invalid pos!\n");
        return;
    }

    *pVal = pArr->pData[pos-1];
    for (i = pos; i < pArr->cnt; ++i) {
        pArr->pData[i-1] = pArr->pData[i];
    }
    pArr->cnt--;
}

main函数

int main()
{
    int val;
    struct ArrayList array;
    init(&array, 5);
    append(&array,1);
    append(&array,2);
    append(&array,3);
    append(&array,4);
    insert(&array, 5 ,5);
    show(&array);
    printf("#################\n");
    delete(&array, 6, &val);
    show(&array);
    return 0;
}

数据结构-线性表顺序存储(C语言实现)

原文：https://www.cnblogs.com/sugare/p/13141187.html