[数据结构]-[线性结构]知识点：顺序表、链表、栈、队列的基本操作及应用，串。

【还没写完】

1.顺序表

1.基础知识点

1.顺序表存在唯一的首元素和尾元素，除了首元素外每个元素都只有一个直接前驱，除了尾元素外每个元素都只有一个直接后继。

2.数组：

优点：下标访问速度快，存储密度高。

缺点：大小不能改，插入删除需要移动元素。

顺序表实际上就是在数组的基础上增加了自动扩容，增删改查等。

3.顺序存储结构

优点：

（1）是一种随机存取结构，存取任何元素的时间都是常数，速度快。

（2）结构简单，逻辑上相邻的元素物理上也相邻。

（3）不使用指针，节省存储空间。存储密度大，相比链表少了指针域。

缺点：

（1）插入删除要移动大量元素，浪费时间。

（2）需要一个连续的存储空间。

（3）插入元素可能会溢出。

（4）自由区的存储空间不能被其他数据占用/共享。

2.实现

1.ADT

typedef int ElemType;
typedef struct{
    ElemType *data; 
    int length; 
    int size;
}SqList;

2.建立与销毁

//初始化
bool Init(SqList *L,int size){
    L->data = (ElemType*) calloc(size,sizeof(ElemType));
    if(L->data == NULL)
        return false;//存储分配失败
    L->length = 0;//空表长度为0
    L->size = size;//初始存储容量
    return true;
}
//销毁
void Destroy(SqList* L){
    free(L->data);
    L->data = NULL;
    L->length = 0;
    L->size = 0;
}

3.判断空、判断满、查长度

//判断空
bool IsEmpty(SqList L){
    return L.length == 0;
}
//判断满
bool IsFull(SqList L){
    return L.length == L.size;
}
//元素个数
int Length(SqList L){
    return L.length;
}

4.遍历

//遍历
void Traverse(SqList L){
    int i;
    for(i = 0;i<L.length;i++){
        printf("-%d",L.data[i]);
    }
    printf("\n");
}

5.扩容

//扩容
bool Expand(SqList *L){
    ElemType* ndata = (ElemType *) realloc(L->data,L->size*2*sizeof(ElemType));
    if(ndata!=NULL){
        L->data = ndata;
        L->size = L->size*2;
        return true;
    }else return false;
}

6.插入和删除（重点）

//插入
bool Insert(SqList *L,int i,ElemType e){
    //判断满如果满了扩容
    if(i>=1&&i<=L->length+1&&(IsFull(*L)?Expand(L):true)){
            int k;
        //所有元素往后移
        for(k = L->length;k>=i;k--){
            L->data[k] = L->data[k-1];}
        //设置i处为插入元素e
        L->data[i-1] = e;
        L->length ++; //表长加1
        return true;
    }else return false;
}
//删除
bool Delete(SqList *L,int i,ElemType *e){
    if(i<1 || i> L->length) return false; //i值不合法
    //把删除的这个数给e
    *e = L->data[i-1];
    //所有数往前移
    for(;i<L->length;i++){
        L->data[i-1] = L->data[i];
    }
    L->length--; //表长减1
    return true;
}

2.链表