数据结构笔记：线性表.md

线性表的定义与特点

定义

由 $n(n\geq 0) $个数据特性相同的元素构成的有限序列，称为线性表。
通俗的说：线性表是$n$个数据元素的有限序列，其中$n$个数据是相同数据类型的。

特点

线性表中元素的个数$n(n\gt0)$定义为线性表的长度，当$n=0$时称之为空表
对于非空的线性表或线性结构，其特点是:

• 存在唯一的一个被称作“第一个”的数据元素;
• 存在唯一的一个被称作“最后一个”的数据元素;
• 除第一个元素外，结构中的每个数据元素均只有一个前驱:
• 除最后一个元素外，结构中的每个数据元素均只有一个后继。

线性表的顺序表示与实现-顺序表

用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的。

顺序表-存储结构

#define MAXSIZE100
typedef int ElemType;

typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SeqList;

顺序表-初始化

#define MAXSIZE100
typedef int ElemType;

typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SeqList;

void initList(SeqList *L){
    L->length = 0;
}

顺序表-在尾部添加元素

int appendElem(SeqList *L,ElemType e){
    if(L->length>=MAXSIXZE){
        printf("顺序表已满\n");
        return 0;
    }
    L->data[L->length]=e;
    L->length++;
    return 1;
}

顺序表-遍历

void listElem(SqeList *L){
    for(int i=0;i<L->length;i++){
        printf("%d ",L->data[i]);
    }
    printf("\n");
}

顺序表-插入元素

int insertElem(SeqList *L,int pos,ElemType e){
    if(pos<=L->length){
        for(int i=L->length-1;i>=pos-1;i--){
            L->data[i+1]=L->data[i];
        }
        L=data[pos-1]=e;
        L->length++;
    }
    return 1;
}

顺序表插入数据的最好时间复杂度是O(1)：在倒数第二个位置插入元素
顺序表插入数据的最坏时间复杂度是O(n)：在第一个位置插入元素

顺序表-删除元素

int deleteElem(SeqList *L, int pos,ElemType *e){
    *e = L->data[pos-1];
    if(pos<L->length){
        for(int i=pos;i<L->length;i++){
            L->data[i-1]=L->data[i];
        }
    }
    L->length--;
    return 1;
}

顺序表-查找

int findElem(SeqList *L,ElemType e){
    for(int i=0;i<L->length;i++){
        if(L->data[i]==e){
            return i+1;
        }
    }
    return 0;
}

顺序表-动态分配内存地址初始化

typedef struct{
    ElemType *data;
    int length;
}SeqList;

SeqList* initList(SeqList *L){
    SeqList *L=(SeqList*)malloc(sizeof(SeqList));
    L->data=(ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    L->length =0;
    return L;
}

线性表的链式表示与实现-链表

线性表的应用