C和数据结构——线性表

这篇文章围绕 C和数据结构——线性表 做一份便于复习和查阅的整理，内容以概念梳理、代码实现和关键细节为主。

核心代码

#include <stdio.h>
#include <stdlib.h>
//循序表实例
/* 逻辑顺序和物理顺序一致，连续存储，可以任意访问*
类型声名如下：*/
/*静态存储*/
#define LIST_INIT_SIZE 100 //存储空间的初始分配量,这是顺序存储的缺点
#define LIST_INCREMENT 10  // 存储空间的分配增量
typedef int ElemType;      //存储元素的数据类型，可以自定义
typedef struct
{
    ElemType *elem; //存储空间的基地址
    int length;     //当前长度
    int listsize;   // 当前分配的存储容量
} SqList;

//初始化线性表
int InitList_Sq(SqList &L)
{
    //构造一个空的先线性表
    L.elem = (ElementType *)malloc(LIST_INIT_SIZE * sizeof(ElementType)); //分配空间
    //测试分配是否成功
    if (!L.elem)
        return 0;
    //初始化
    L.length = 0;                //初始数据量为0
    L.listsize = LIST_INIT_SIZE; //初始存储量为最大
    return 1;
}

//销毁线性表:动态分配必须释放
int DestoryList(SqList &L)
{
    free(L.elem); //由INIT函数可以知道，此处可以直接一步释放
    //释放后不要忘记修改参数的值
    L.elem = NULL;
    L.length = 0;
    L.listsize = 0;
    return 1;
}

//求线性表的长度
int GetLength(SqList L)
{
    return L.length; //length里面记录了表中元素的个数
}

//求线性表中第i个元素
int GetElem(SqList L, int i, ElemType &e)
{
    //注意进行数据i是否合法的判断
    if (i < 1 || i > L.length)
    {
        return 0;
    }
    //返回对应的值
    e = *(L.elem + i - 1); //注意线性表中第i个元素的下标为i-1,下标为i的元素的下标为i+1
    return 1;
}

//按值查找求下标
ElemType LocateElem(SqList L, ElemType e)
{
    ElemType *p;
    int i = 1;
    p = L.elem;
    //循环遍历，比较查找
    while (i < L.length && (*p++ != e))
    {
        i++;
    }
    //判断返回值是否合理
    if (i <= L.length)
    {
        return i;
    }
    else
    {
        return 0;
    }
}

//插入数据
int ListInsert(SqList &L, ElemType e, int i)
{
    /*插入算法：
    first,将新元素e插入到L中逻辑序号为i的位置，对应于L.elem[i-1]
    second,判断i的值是否合法（1<=i<=L.length+1）
    third,second满足时，将L.elem[i-1...length-1]都后移一个位置
    然后在L.elem[i-1]处插入e,然后对表中相关参量进行修改。*/
    //这里先使用一种特别笨的算法进行插入操作，后续进一步学习会介绍更加简洁的算法，但是每一种算法的实现都要掌握

    //判断i是否合法
    ElemType *p;
    if (i < 1 || i > L.length + 1)
    {
        return 0;
    }
    //这是一个拓展功能，使得数据无论如何都可以呗被存储。可有可无，有的学校不讲
    if (L.length >= L.listsize)
    { //realloc函数自带释放原有空间的功能
        ElemType *newbase = (ElemType *)realloc(L.elem,
                                                (L.listsize + LIST_INCREMENT) * sizeof(ElemType));
        if (!newbase)
        { //判断是否拓展成功
            return 0;
        }
        L.elem = newbase;
        L.listsize += LIST_INCREMENT; //修改表中相关参数的值
    }
    ElemType *q = &(L.elem[i - 1]);                //q为插入的位置
    for (p = &(L.elem[L.length - 1]); p >= q; --p) //先让p指向最后一个位置，然后一直遍历到q,
    {
        *(p + 1) = *p; //等价于p--;
        *q = e;        //让新的元素e插入到第i个位置，也就是数组的i-1处。
        ++L.length;    //修改表中的相关参数
        return 1;
    }
}

//删除某个位置的元素
int ListDelete_Sq(SqList &L, int i, ElemType &e)
{
    /*
    1，删除顺序表中逻辑序号为i的元素
    2，判断输入i是否合法
    3，当2生效时，将L.elem[i.......length-1]的每一个
    元素都前移一个位置，然后修改表中的相关参数。
    */
    ElemType *p, *q;
    if (i < 1 || i > L.length)
    { //step 1,判断
        return 0;
    }
    p = &(L.elem[i - 1]);      //step 2，定位
    e = *p;                    //不是必须的
    q = L.elem + L.length - 1; //表末尾的位置
    for (++p; p <= q; ++p)
    { //step 3,修改
        *(p - 1) = *p;
    }
    --L.length; //重要！！
    return 1;
}

//显示当前表中的数据
void display(SqList L)
{
    for (int i = 1; i <= L.length; i++)
    {
        printf("%d", L.elem[i - 1]);
    }
}