《数据结构与算法》Chapter 2 线性表——顺序存储的c语言实现

《数据结构与算法》Chapter 2 线性表——顺序存储的c语言实现

直接上代码！（没有写main函数，主要是各个基本 *** 作的实现）

#include 
#include 
#include 

#define OVERFLOW _OVERFLOW
#define OK 1
#define True 1
#define False -1

#define LIST_INIT_SIZE 100 //线性表储存空间的初始分配量
#define LISTINCREMENT 10   //线性表储存空间的分配增量

typedef int ElemType;
typedef int Status;

struct SqList
{
    ElemType *elem; //存储空间基址
    int length = 0; //当前长度（初始为0）
    int listsize;   //当前分配的存储容量
};

//----------------函数目录-------------------------
Status InitList_Sq(SqList &L);                               //创建一个空的顺序表L
Status DestoryList(SqList &L);                               //销毁顺序表L
Status ClearList(SqList &L);                                 //将L置为空表
Status ListEmpty(SqList &L);                                 //判断L是否为空表，是的话返回True，反之返回False
Status ListLength(SqList &L);                                //返回L中数据元素个数
Status GetElem(SqList &L, int i, ElemType &e);               //用e返回L中第i个数据元素
Status LocateElem(SqList L, int e);                          //返回第一个与e相等的元素的位置，没有的话返回0
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e); //若cur_e是L的数据元素则用pre_e返回其前驱，不存在则返回0
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e); //若cur_e是L的数据元素则用next_e返回其后继，不存在则返回0
Status ListInsert(SqList &L, ElemType i, ElemType e);        //把e插入到第i位，之后的元素依次后移
Status ListDelete(SqList &L, ElemType i);                    //删除第i个元素

Status InitList_Sq(SqList &L)
{
    L.elem = (ElemType *)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
    if (!L.elem)
        return OVERFLOW; //存储分配失败
    L.listsize = LIST_INIT_SIZE;
    return OK;
}
Status DestoryList(SqList &L)
{
    free(L.elem);
    L.length = 0;
    L.listsize = 0;
    return OK;
}
Status ClearList(SqList &L)
{
    DestoryList(L);
    InitList_Sq(L); //先销毁再创建就好啦
    return OK;
}
Status ListEmpty(SqList &L)
{
    if (L.length == 0)
        return True;
    else
        return False;
}
Status ListLength(SqList &L)
{
    return L.length; //这个函数真的好多余……但谁让书上这么写了呢
}
Status GetElem(SqList &L, int i, ElemType &e)
{
    e = L.elem[i - 1];
    return OK;
}
Status LocateElem(SqList L, ElemType e)
{
    int pos;
    pos = 0;
    for (int i = 0; i < L.length; i++)
    {
        if (L.elem[i] == e)
        {
            pos = i + 1;
            break;
        }
    }
    return pos;
}
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e)
{
    int pos = LocateElem(L, cur_e);
    if (pos < 2) //第一个元素没有前驱
    {
        return 0;
    }
    else
    {
        pre_e = L.elem[pos - 2];
        return OK;
    }
}
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e)
{
    int pos = LocateElem(L, cur_e);
    if (pos < 2) //第一个元素没有前驱
    {
        return 0;
    }
    else
    {
        next_e = L.elem[pos - 2];
        return OK;
    }
}
Status ListInsert(SqList &L, ElemType i, ElemType e)
{
    if (i < 1 || i > L.length + 1)
        return False;
    if (L.length >= L.listsize)
    {
        ElemType *newbase;
        newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase)
            return False;
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    L.length++;
    for (int j = L.length; j >= i; j--)
    {
        L.elem[j] = L.elem[j - 1];
    }
    L.elem[i - 1] = e;
    return OK;
}
Status ListDelete(SqList &L, ElemType i)
{
    int e;
    if (i < 1 || i > L.length)
        return False;
    e = L.elem[i - 1];
    L.length--;
    for (int j = i; j <= L.length; j++)
    {
        L.elem[j - 1] = L.elem[j];
    }
    return e;
}