从零开始学习数据结构--2.1线性表之顺序表

到这一章线性表，我们要掌握的就多了。

1.线性表的定义

线性表是n个具有相同特性的数据元素的有限序列。

我们可以理解为幼儿园排队，在幼儿园里面，每个小朋友都是有一定的序号的，小朋友可以领到他们的专属号码，比如说小明是一号，小花是二号......那么，我们就可以说幼儿园小朋友排队属于一个线性表。

2.线性表的分类

线性表按照不同的存储方式可以分为顺序表和链表

3.顺序表

顺序表是一种连续的存储结构，数据元素在内存中占据一块连续的存储空间。它可以通过下标来直接访问元素，因此支持随机访问。顺序表可以使用数组来实现，每个元素占据固定大小的内存空间。

特点就是顺序表逻辑上相邻的数据元素，在物理次序上也是相邻的

我们在学习顺序表一定要去实践，不能只是看，只是学习，一定要自己去动手去尝试，光看是学不会的

下面我们来讲顺序表的存储结构 

#define MAXSIZE 100    //定义最大长度为100
typedef struct{        //创造一个结构体
    ElemType* elem;    //定义数据类型
    int length;        //定义长度
}SqList;               //名字命名为SqList

我们要注意，有些地方会把ElemType* elem；写成ElemType data[MaxSize] 的形式

两个说法都是一样的只是一个是数组的静态分配，一个是数组的动态分配

ElemType* elem；            //数组的动态分配

ElemType data[MaxSize]；    //数组的静态分配

3.1.顺序表的一系列操作

我们针对顺序表有许多的操作，比如说初始化，获取，查找，插入，删除.....

首先先讲顺序表的初始化，大概的格式是这样的

Int InitSL(Sqlist *L,int length){            
    L->base = (SqlElemType *)malloc(sizeof (SqlElemType) * MAXSIZE);    //创造一个动态内存
    if(!L->base)
    return OVERFLOW;                //判断创建的顺序表是否会溢出
    L->length = 0;

    for(int i = 1; i < length + 1; i++){
    SqElemTtpe e;
    scanf(" %d", &e);                 //如果不溢出我们就创建我们的那个存储结构
    SqInsert(L, i , e);               //这个是顺序表的插入，我们后面会讲
    }
    return OK;                            //define OK 1
    }
    

之后是获取，如果我们定义的这个position<1或position不在我们的顺序表里面我们就返回ERROR

如果有，我们让我们要的指针e取到顺序表里面的位置-1，为什么呢，因为数组的长度=顺序表长度-1

int GetElem(Sqlist *L, int position , SqlElemType *e){    //定义一个查找函数
    if(position < 1 || position > L->length){          
    return ERROR;
    }else{
    *e = L->base[position - 1];
    return OK;
    }}

查找元素

我们要注意，查找元素指的是，我们要找的元素在顺序表里面的第几个，也就是说我们找到了他在数组【3】，那我们就返回4，因为我们数组长度=顺序表-1

int LocateElem(Sqlist *L, SqElemType e){
    for(int  = 0; i < L->length; i++){          //用一个for循环
    if(e == L->base[i])                         //如果我们找到了我们要找的数组
    return i +1;                                //我们就返回 i+1，因为顺序表里面，数组长度=顺序表长度-1
    }
    return 0;                                   //没有找到我们就返回0
    }

下一个操作就比较重要了

插入元素

算法思想

①判断插入位置 i 是否合法

②判断顺序表的存储空间是否已满，若已满返回ERROR

③将第 n 到第 i 位依次向后移动一个位置，空出第 i 个位置

④将要插入的新元素 e 放入第 i 个位置

⑤表长 + 1，插入成功返回OK

int SqlInsert(Sqlist *L, int position, SqlElemType e){
    if(position < 1 || position > L->length + 1)        //①判断插入位置 i 是否合法
    return ERROR;
    if(L->length == MAXSIZE)                            //②判断顺序表的存储空间是否已满
    return OVERFLOW;                                    //若已满返回OVERFLOW
    for(int i = L->length - 1; i >= position - 1; i--){ //③从最后一个元素开始，依次到第i个元素，那第i个元素的下标是i-1，也就是position - 1
    L ->base[i + 1] = L->base[i];                 //我们将前一个元素base【i】赋值给后一个元素base【i + 1】
    }                                    //④执行完毕后
    L->base[position -1] = e;            //将要插入的新元素 e 放入第 i 个位置，第i个位置的下标是i-1，也就是position-1
    L->length++;                                        //⑤表长 + 1
    return OK;                                          //返回OK
    }

这个我们要重点理解一下，顺序表这节里面插入元素是最重要的，也是最难的

我们理解了插入元素之后，后面的就比较简单了

删除元素

我们始终要记得，在代码里面和逻辑上是不一样的，数组长度 = 顺序表长度 - 1

int SqlDelete(Sqlist *L, int positon, SqlElemType *e) {
    if(position < 1||position > L->length)//判断删除位置是否合法
    return ERROR;
    for(int i = position; i < L->length; i++){ //我们进行for循环，
    L->base[i -1] = L->base[i];                //把position后面的位置开始都往前移一位
    }
    *e = L->base[position - 1];                //我们把position位置的值存放在e里面
    L->length--;                               //表长-1
    return OK;
    }

后面的就一起讲了

顺序表的销毁，清空，检查为空

int SqlDestroy(Sqlist *L){
    if(L->base == 0){            //判断销毁位置是否合法
    return ERROR;
    }
    else {                       //合法，咱就释放L里面的base 
    free(L->base);             
    return OK;
    }
}



void SqlClear(Sqlist *L) {
    L->length = 0;                //清空
    }


int SqlIsEmpty(Sqlist *L){
    if(L->length == 0){            //检查线性表是否为空
    return TRUE;
    }else{
    return FALSE;
    }

顺序表的优缺点

我们要想顺序表的优点是什么？

是不是直接划分一个区域就可以拿来当顺序表，所以不需要考虑逻辑关系而导致额外增加存储空间

可以快速的存取表中任意位置的元素。

那顺序表的缺点呢？

我们想一下，如果要进行线性表的插入删除是不是都要后面的元素往前移，往后移。所以很麻烦；

还有顺序表长度不确定的时候，我们划分的区域不够是不是还要增加一块存储空间？是不是也很麻烦。而且我们就算加了一块存储空间，没用完，假如我们这篇空间只用了一半，剩下一半是不是很浪费？

那该怎么办呢？欸，这就要用到我们下一节的链表了。

终于讲完了线性表里面重要的一节了，累死了，我们重点掌握这些就行了，后面的内容就是链表了