（数据结构）顺序表及其应用实例——C语言实现

文章目录

• 前言
• 代码
• 总结

---

前言

学习记录《数据结构——从概念到C实现》
part1：顺序表的实现

---

代码

基于C语言实现顺序表的基本 *** 作函数，并调用各项函数来完成相应的功能。

#include 
#include 
// 静态分配存储
#define maxSize 100
typedef int DataType;
typedef struct
{
    DataType data[maxSize];
    int length;
} SeqList;

// //动态分配存储
// #define initSize 100
// typedef int DataType;
// typedef struct{
//     DataType * data;//指示动态分配数组的指针
//     int maxSize,n;//数组的最大容量和当前个数
// }SeqList;

//初始动态分配语句
// data = (DataType * )malloc(sizeof(DataType)*initSize);
// maxSize = initSize;n=0;

//初始化顺序表
void InitList(SeqList *L)
{
    L->length = 0;
}

//建立顺序表
int CreateList(SeqList *L, DataType a[], int n)
{
    if (n > maxSize)
    {
        printf("顺序表的空间不够，无法建立顺序表\n");
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        L->data[i] = a[i];
    }
    L->length = n;
    return 1;
}

//判空 *** 作
int Empty(SeqList *L)
{
    if (L->length == 0)
        return 1;
    else
        return 0;
}

//求长度
int Length(SeqList *L)
{
    return L->length;
}

//遍历
void PrintList(SeqList *L)
{
    for (int i = 0; i < L->length; i++)
    {
        printf("%d ", (*L).data[i]);
    }
    printf("\n");
}

//按值查找
int Locate(SeqList *L, DataType x)
{
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] == x)
            return i + 1;
    }
    return 0;
}

//按位查找
int Get(SeqList *L, int i, DataType *ptr)
{
    if (i < 1 || i > L->length)
    {
        printf("查找位置非法，查找失败\n");
        return 0;
    }
    else
    {
        *ptr = L->data[i - 1];
        return 1;
    }
}

//插入 *** 作
int Insert(SeqList *L, int i, DataType x)
{
    if (L->length >= maxSize)
    {
        printf("上溢错误，插入失败\n");
        return 0;
    } //不要忘记判断溢出情况
    if (i < 1 || i > L->length + 1)
    {
        printf("位置错误，插入失败\n");
        return 0;
    }
    for (int j = L->length; j >= i; j--)
    {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = x;
    L->length++;
    return 1;
}

//删除 *** 作
int Delete(SeqList *L, int i, DataType *ptr)
{
    if (L->length == 0)
    {
        printf("下溢错误，删除失败\n");
        return 0;
    }
    if (i < 1 || i > L->length)
    {
        printf("位置错误，删除失败\n");
        return 0;
    }
    *ptr = L->data[i - 1];
    for (int j = i; j < L->length; j++)
    {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return 1;
}

int main()
{
    int r[5] = {1, 2, 3, 4, 5}, i, x;
    SeqList L;
    CreateList(&L, r, 5);
    printf("当前线性表的数据为：");
    PrintList(&L);
    Insert(&L, 2, 8);
    printf("执行插入 *** 作后数据为：");
    PrintList(&L);
    printf("当前线性表的长度为：%d\n", Length(&L));
    printf("请输入查找的元素值：");
    scanf("%d", &x);
    i = Locate(&L, x);
    if (0 == i)
        printf("查找失败\n");
    else
        printf("元素%d的位置为：%d\n", x, i);
    printf("请输入查找第几个元素值：");
    scanf("%d", &i);
    if (Get(&L, i, &x) == 1)
        printf("第%d个元素值是%d\n", i, x);
    else
        printf("线性表中没有第%d个元素\n", i);
    printf("请输入要删除第几个元素：");
    scanf("%d", &i);
    if (Delete(&L, i, &x) == 1)
    {
        printf("删除第%d个元素是%d，删除后数据为：", i, x);
        PrintList(&L);
    }
    else
        printf("删除 *** 作失败\n");
    return 0;
}

---

总结

这个系列为我复习《数据结构》的学习记录过程，本篇介绍顺序表的基本 *** 作实现及范例程序，代码很简单，但是帮助我复习了很多C语言的使用（因为近一两年来基本都是使用python），也帮助我加深了对指针的理解（大一没好好学指针导致大三了还是不懂T_T）。