Chp2-1 线性表

注：数据结构三要素一一逻辑结构、数据的运算、存储结构（物理结构）；储存的方式不同，运算实现的方式不同

顺序表一一用顺序存储(一般使用数组)的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理
位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

而在数组分配上又可再进一步的分为动态数组分配与静态数组分配。

#include
#include

#define MaxiSize  10    //默认顺序表的最大长度

//使用静态数组分配顺序表

typedef struct SAList
{
    int data[MaxiSize];     //使用静态数组存放数据
    int length;                 //顺序表当前长度
} SASqList;                     //顺序表的定义（静态分配方式）

//使用动态分配顺序表

typedef struct MAList
{
    int *data;                  //指示动态分配数组的指针
    int MaxSize;            //顺序表的最大容量
    int length;             //顺序表的当前长度
}MASqList;

//静态数组顺序表初始化函数
void SAInitList(SASqList *L){
    printf("<-------静态顺序表初始化函数------->n");
    for (int i = 0; i < MaxiSize; i++)
    {
        //全部数组赋初值为0
        L->data[i] = 0;
    }
    //顺序表初始长度为0
    L->length = 0;
    printf("<-------静态顺序表初始化结束------->n");
}

void MAInitList(MASqList *L){
    printf("<-------动态顺序表初始化函数------->n");
    //用malloc申请一片连续的数组空间
    L->data = (int *)malloc(MaxiSize * sizeof(int));
    //顺序表初始长度为0
    L->length = 0;
    L->MaxSize = MaxiSize;
    printf("<-------静态顺序表初始化结束------->n");
}

void MAIncreaseSize(MASqList *L,int len){
    int *p = L->data;                               //用一个指针暂存当前顺序表的数组指针
    //重新给L顺序表分配空间(变大了)
    L->data = (int *)malloc((L->MaxSize + len) * sizeof(int));
    for (int i = 0; i < L->MaxSize; i++)
    {
        L->data[i] = p[i];                          //将原来L顺序表中的元素赋值到新的区域
    }
    L->MaxSize = L->MaxSize + len;  //顺序表最大长度增加 len
    free(p);                                        //释放原来的内存空间
}

int main(){
    SASqList SAL;            //声明一个静态顺序表
    SAInitList(&SAL);       //初始化静态顺序表

    MASqList MAL;       //声明一个动态顺序表
    MAInitList(&MAL);
    return 0;
}

功能代码是在静态分配方式下实现的，动态分配也雷同

bool SAListInsert(SASqList *L,int i,int e){
    if(i<1||i>(L->length)+1)    //判断 i 的合法性
        return false;
    if(L->length>=MaxiSize) //如果空间已满则也不能插入
        return false;
    //将第 i 个元素及之后的元素后移
    for (int j = L->length; j >= i; j--)
    {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;     //在位序 i 处放入e
    L->length++;           //长度+1
    return true;
}

bool SAListDelete(SASqList *L,int i , int *e){
    if(i<1||i>L->length)                        //判断 i 的合法性
        return false;
    *e = L->data[i-1];                          //将需要删除的元素的值赋到e
    for (int j = i; j < L->length;j++){
        L->data[j - 1] = L->data[j];    //将第 i 各位之后的元素前移
    }
    L->length--;                               //线性表长度-1
    return true;
}

int SAGetElem(SASqList *L,int i ){
    if(i<1||i>L->length)    //判断位序的合法性
        return -1;
    return L->data[i - 1]; //与数组的使用无异
}

int SALocateElem(SASqList *L,int e){
    for (int i = 0; i < L->data;I++){
        if(L->data[i]==e)       	//如果匹配到对应的值
            return i + 1;           //范围对应的位序
    }
    return -1;                     //如果没有查询到，则返回-1
}