[数据结构与算法]线性表（数据结构）

线性表定义：是具有相同数据类型的（n>=0）个数据元素的有限序列，其中n为表长。

??????????? 特点：除第一个元素之外，每个元素有且只有一个直接前驱，除最后一个元素之外，每个元素有且只有一个后继。

线性表的基本操作：

????????????? InitList(&L):初始化链表，构造一个空的线性表

?????????????? Length(L):求表长，返回线性表L的长度。

?????????????? LocateElem(L,e):按值查找操作

?????????????? GetElem(L,i):按位查找操作

??????????????? ListInsert(&L,i,e)：插入操作 在表L中第i个位置插入元素e

?????????????? ListDelete(&L,i,&e):删除操作，删除表L中第i个位置元素，并用e返回删除元素的值

??????????????? PrintList(L):输出操作

???????????????? Empty(L)；判空操作

???????????????? DestoryList(&L):销毁操作

线性表的顺序表示：

??????? 线性表的顺序存储结构

#define Maxsize 50
typedef struct{
    ElemType data[Maxsize];//顺序表的元素
    int length;//顺序表的长度
} Sqlist;          //顺序表的类型定义

一维数组可以是静态分配的，也可以是动态分配的，在静态分配时，由于数组的大小和空间，事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

而在动态分配中，存储数组的空间是在程序执行过程中通过动态存储分配语句，一旦数据空间占满，就另外开辟一块更大的空间，用以替换原来的存储空间，从而达到扩充数组存储空间的问题。

#define InitSize 100
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;

顺序表的基本操作实现

??????? 1插入操作：在顺序表L的第i个位置插入新的元素e，若i的值不合法返回false,表示插入失败，否则将第i个元素及其后的所有元素往后移动一个位置。

bool ListInsert( SqlList &L,Elemtype e){
    if(i<1||i>L.length){
        return false;
    }
    if(L.length>MaxSize){
        return false;
    }

    for (int j=L.length;j>=i;j--){
        L.data[j-1]=L.data[j];
    }
    L.data[i-1]=e;
    L.length ++;
    return true;

}

??????????????? 最好情况：表尾插入，时间复杂度O(1)

???????????????? 最坏情况：表头插入，时间复杂度O(n)

??????????????? 平均情况：n/2? 时间复杂度O（n）

??????? 删除操作：?????????

bool ListDelete(SqlList &L ,ElemType &e){
    if(i<1||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;
}

??????????????? 最好情况：表尾删除，时间复杂度O(1)

??????????????? 最坏情况：表头删除，时间复杂度O(n)

?????????????????平均情况：n-1/2? 时间复杂度O（n）

?? 按值查找：

int LocateElem(SqlList &L,ElemType e){

    int i;
    for (i=0;i<L.length;i++){
        if(L.data[i]==e){
            return i+1;
        }
    }
    return 0;

}

?

????????????????最好情况：表头查找，时间复杂度O(1)

??????????????? 最坏情况：表头查找，时间复杂度O(n)

?????????????????平均情况：n+1/2? 时间复杂度O（n）

?

?

?