🔥线性表

• 线性表是具有相同数据类型（每个元素占用空间一样大）的n（n≥0）个数据元素的有限序列，n为表长，n=0时是一个空表。
  

🔥顺序表

顺序表定义

用顺序存储的方式实现线性表顺序存储。逻辑上相邻的元素存储在物理位置也相邻的存储单元中。实现分为 静态分配 和 动态分配 举例：

• 静态分配

#define MaxSize 10              //定义最大长度
typedef struct{
    ElemType data[MaxSize];      //静态数组存放数据元素
    int length;                     //顺序表当前长度
}SqList;                        //顺序表类型定义

• 动态分配

L.data = (ElemType *)malloc(sizeof(ElemType)* InitSize);
free(L.data);

• 如上用 malloc 和 free 函数可以为链表获取空间和释放空间，两者必须成对出现，否则内存没法释放

#define InitSize 10
typedef struct{
    ElemType *data;         //指示动态分配数组的指针
    int MaxSize;            //顺序表最大容量
    int length;             //顺序表当前长度
}SeqList;                   //顺序表类型定义（动态分配方式）

• 顺序表特点：

1. 随机访问，可在常数级时间内查到第i个元素
2. 存储密度高，每个节点只存储数据元素
3. 可拓展，但不方便
4. 插入、删除不方便，要移动大量元素

顺序表插入

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--)        //第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;          //第i个位置放入e
    L.length++;
    return true;
}

顺序表删除

bool ListDelete(SqList &L,int i,int &e){
    if(i<1||i>L.length+1)       //判断范围有效
        return false;
    e=L.data[i-1];              //删除的元素赋值给e
    for(int j=i;j<=L.length;j++)        //第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    L.data[i-1]=e;          //第i个位置放入e
    L.length--;
    return true;
}

顺序表查找

• 分为 按位查找 和 按值查找
  

🔥单链表

单链表定义

数据存储位置不连续，需要有后继指针next指向下一个节点，最后一个结点指向NULL（是一个空指针）

typedef struct LNode{           //定义单链表结点类型
    ElemType data;          //每个节点存放一个数据元素（数据域）
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L){     //初始化单链表
    L = NULL;       //空表
    returnt true;
}
void test(){
    LinkList L;         //声明一个指针指向单链表
    InitList(L);        //初始化单链表
    //后续……
}

• 和顺序表一样，可以用malloc函数添加节点，p指针指向该节点

struct LNode * p = (struct LNode *)malloc(sizeof(struct LNode));

• 两种实现方式：带头结点、不带头结点
• 带头结点不存储数据，相当于创造一个“第0个结点”作为引入，只是为了操作方便

单链表插入

• 带头结点
  

• 不带头结点
  

• 将两个方法中的在某个位置后面插入一个元素封装成函数
  

• 或者前插也行，但方法有所不同：
  

单链表删除

单链表查找

• 按位查找

LNode * GetElem(LinkList L, int i){
    if(i<0>)
        return NULL;
    LNode *p;       //p指向扫描到的结点
    int j=0;        //当前指向的结点索引（第几个）
    p = L;          //L指向头结点
    while(p!=NULL && j<i){      //循环直到第i个点
        p=p->next;
        j++;
    }
    return p;
}

• 按值查找

LNode * LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    //从第1个结点开始查找数据为e的结点
    while(p!=NULL && p->data!=e)
        p = p->next;
    return p;       //找到返回指针，否则NULL
}

单链表建立

• 尾插法
  

• 头插法
  

🔥双链表

• 链表中既有后继指针next又有前驱指针prior，使链表可以向两个方向遍历，不重点记录
  

🔥循环链表

• 循环单链表：单链表最后一个结点的next指向头结点即成为循环单链表，使得链表从任意结点出发都可以找到任何其他结点

• 循环双链表：表头结点的prior指针指向表尾结点，表尾结点的next指针指向表头结点（形成双闭环）
  

🔥静态链表

• 分配一整片连续的空间，各个结点集中安置
• 用-1标记最后一个结点，-2标记空闲结点
• 静态链表用于不支持指针的语言、数据元素数量固定不变的场景（现在很少用）
  

#define MaxSize 10          //静态链表最大长度
struct Node{                //静态链表结构类型定义
    ElemType data;          //存储数据元素
    int next;               //下一个元素的数组下标（物理位置）
} 

🔥顺序表和链表比较

• 链表：表长不确定，增删比较多（餐厅取号）
• 顺序表：表长稳定，查询操作多（课堂点名）