数据结构与算法之线性表（C语言）

线性表C语言实现

具体代码实现如下：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h> //包含exit函数

//定义结构体类型，保持顺序表（数组），
typedef struct Arr
{
    int *pBase; //描述的数组第一个元素的地址
    int len;    //描述数组的长度
    int cnt;    //当前数组有效元素的个数
} Array;

void init_arr(Array *pArr, int length);         //初始化顺序表
int append_arr(Array *pArr, int val);           //向顺序表里末尾追加新元素
int insert_arr(Array *pArr, int pos, int val);  //向顺序表里插入元素
int delete_arr(Array *pArr, int pos, int *val); //删除表里元素
int is_empty(Array *pArr);                      //判断是否空表
int is_full(Array *pArr);                       //判断是否满表
void sort_arr(Array *pArr);                     //排序表里元素
void inversion_arr(Array *pArr);                //表内元素排列顺序反转
void show_arr(Array *pArr);                     //显示打印表里元素

int main()
{
    int val;            //表示被删除元素的值
    Array arr;          //定义结构体变量
    init_arr(&arr, 10); //初始化长度为10的数组
    append_arr(&arr, 5);
    append_arr(&arr, 4);
    append_arr(&arr, 3);
    append_arr(&arr, 2);
    append_arr(&arr, 1);
    // insert_arr(&arr, 6, 6);
    show_arr(&arr);
    sort_arr(&arr);
    // inversion_arr(&arr);
    show_arr(&arr);
    delete_arr(&arr, 3, &val);
    //删除测试
    // delete_arr(&arr, 3, val);
    // printf("显示被删%d", val);
    printf("\n主函数显示被删元素%d\n", val);
    show_arr(&arr);
}

//初始化顺序表
void init_arr(Array *pArr, int length)
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if (NULL == pArr->pBase)
    {
        printf("动态内存分配失败！\n");
        exit(-1); //终止整个程序
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
    }
    return;
}

//向顺序表里添加元素
int append_arr(Array *pArr, int val)
{
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return 1; //1表示追加成功
}

int is_empty(Array *pArr)
{
    if (pArr->cnt == 0)
    {
        return 1; //表示为空表
    }
    else
    {
        return 0; //非空
    }
}

//判断表满
int is_full(Array *pArr)
{
    if (pArr->cnt == pArr->len)
    {
        return 1; //表满
    }
    else
    {
        return 0; //非满
    }
}

//插入元素
int insert_arr(Array *pArr, int pos, int val)
{
    //判断是否为满表
    if (is_full(pArr))
    {
        printf("表满无法插入。\n");
        return 0;
    }
    //判断插入是否合法
    if (pos < 1 || pos > pArr->cnt + 1)
    {
        printf("插入位置不合法。\n");
        return 0; //表示插入失败
    }
    else
    {
        int i;
        for (i = pArr->cnt; i >= pos; i--)
        {
            pArr->pBase[i] = pArr->pBase[i - 1];
        }
        pArr->pBase[pos - 1] = val;
        pArr->cnt++;
        return 1; //表示插入·成功
    }
}

//删除元素
int delete_arr(Array *pArr, int pos, int *val)
//删除第pos位置元素，值保存给val
{
    if (is_empty(pArr))
    {
        printf("表为空无法删除。\n");
        return 0;
    }
    if (pos < 1 || pos > pArr->cnt)
    {
        printf("删除位置不合法。\n");
        return 0;
    }
    else
    {
        int i;
        *val = pArr->pBase[pos - 1]; //val记录了地址，*则取值，相当于val开辟了一个指针地址，可以存要删除元素的地址，然后把地址传到主函数的val，这时候*val已经取到了值，然后进行后面的移位操作。这其中还有待探究！
        // printf("赋地址显示被删%d\n", val);
        for (i = pos; i < pArr->cnt; i++)
        {
            pArr->pBase[i - 1] = pArr->pBase[i];
        }
        // printf("更改后显示被删%d\n", val);

        pArr->cnt--;

        return 1; //删除成功
    }
}

//冒泡排序
void sort_arr(Array *pArr)
{

    int i, j;
    int temp;
    for (i = 0; i < pArr->cnt - 1; i++)
    {
        for (j = 0; j < pArr->cnt - i - 1; j++)
        {
            if (pArr->pBase[j] > pArr->pBase[j + 1])
            {
                temp = pArr->pBase[j];
                pArr->pBase[j] = pArr->pBase[j + 1];
                pArr->pBase[j + 1] = temp;
            }
        }
    }
}

//顺序表元素反转
void inversion_arr(Array *pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int temp;
    while (i < j)
    {
        temp = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = temp;
        i++;
        j--;
    }
    return;
}

//打印元素
void show_arr(Array *pArr)
{
    int i;
    if (is_empty(pArr))
    {
        printf("该表为空表。\n");
    }
    else
    {
        for (i = 0; i < pArr->cnt; i++)
            printf("%d\t", pArr->pBase[i]);
    }
}