一、线性表

线性表的基本概念

数据结构的三要素：逻辑结构、数据的运算、存储结构（物理结构)

线性表的定义

线性表是具有相同数据类型的n(n>=0)个元素的有限序列。

线性表的基本操作

什么时候要传入参数的引用“&”？

一种是值类型，使用时会直接复制原值，修改参数不会影响原值

一种是引用类型，使用时操作的是原值，修改时直接修改原值！（C语言不支持这种引用类型！）

为什么要实现对数据结构的基本操作？

团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）
将常用的操作/运算封装称函数，避免重复工作，降低出错风险。

总结

注意⚠️：位序是用1开始计算的！！！

二、顺序表

顺序表的基本概念

顺序表的定义

顺序表的初始化

静态分配

具体实现：

//初始化(静态分配)
void InitList(SqList &L){
    for (int i = 0; i < MaxSize; i++) {
        L.data[i]=0;//将所有元素的初始值默认设置为0
        //这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响
    }
    L.length=0;
}

问题反思

如果“数组”存满留怎么办？

可以放弃治疗，顺序表长刚开始确定后就无法更改（存储空间是静态的）

如果一开始就声明一个很大的内存空间呢？会存在什么问题？

浪费，会造成大量的浪费。

动态分配

具体实现方式

//初始化（动态方式）
bool InitList(SeqList &L){
    //用 malloc 函数申请一片连续的存储空间
    L.data=(int *)malloc(InitSize*sizeof(int));
    if (L.data==NULL)
        //要细心呀，这里不小心写成了赋值语句，但是没有报错，找了半天错误！
        return false;
    //(int *) 是指针的强制类型转换
    L.length=0;
    L.MaxSize=InitSize;
    return true;
}

总结

顺序表的基本操作

插入

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

详细实现方式：

优化之后：

bool ListInsert(SqList &L,int i,int e){
    //判断插入的位置是否合法，
    if (i<1||i>L.length+1)
        return false;
    //判断表是否存满了
    if (L.length>=MaxSize)
        return false;

    //后面的元素后移
    for (int j = L.length; j >=i ; j--) {
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

插入操作的时间复杂度分析

删除

//删除
bool ListDelete(SqList &L,int i,int &e){
    //判断i的位置是否合法
    if(i<0||i>L.length){
        return false;
    }
    //取出将要被删除的数
    e=L.data[i-1];
    //将其后的数据前移
    for (int j = i; j <=L.length ; j++) {
        L.data[j-1]=L.data[j];
    }
    //线性表长度减一
    L.length--;
    return true;
}

删除操作的时间复杂度分析

总结反思

查找

按位查找

GetElem(L,i):按位查找操作，获取表L中第i个位置的元素的值

静态分配状态下的实现方式

动态分配状态下的实现方式

用指针加数组下标的方式取数据的时候，数组类型决定着取数据时取几个字节！！

//按位查找
int GetElem(SeqList L,int i){
    //判断是否越界
    if (i<0||i>L.length)
        return -1;
    return L.data[i-1];
}

按位查找的时间复杂度分析

按值查找

//按值查找
int LocateElem(SeqList L,int e){
    //循环出查找
    for (int i = 0; i <L.length ; i++) {
        if (L.data[i]==e)
            return i+1; //返回位序
    }
    return -1;
}