2.3 双链表

1.双链表 1.1 双链表的初始化(带头结点)

#include 
#include 

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinklist;

//初始化双链表
bool InitDLinkList(DLinklist &L){
    //分配一个头结点
    L = (DNode *)malloc(sizeof(DNode));
    if (L==NULL){
        return false;
    }
    //头结点的prior永远指向NULL
    L->prior = NULL;
    //头结点之后暂时还没有结点
    L->next = NULL;
    return true;
}

void testDLinkList(){
    //初始化双链表
    DLinklist L;
    InitDLinkList(L);
}

//判断双链表是否为空（带头结点）
bool Empty(DLinklist L){
    if (L->next == NULL){
        return true;
    } else{
        return false;
    }
}

1.2 双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if (p==NULL||s==NULL){
        return false;
    }
    s->next = p->next;
    if (p->next != NULL){
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

1.3 双链表的删除

void DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while (L->next!=NULL){
        DeleteNextDNode(L);
    }
    //释放头结点
    free(p);
    //头指针指向NULL
    L = NULL;
}

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if (p==NULL){
        return false;
    }
    DNode *q = p->next;
    if(q==NULL){
        return false;
    }
    p->next = q->next;
    if (q->next!=NULL){
        q->next->prior = p;
    }
    free(q);
    return true;
}

1.4 双链表的遍历

void ergodic(DNode *p){
    //1.后向遍历
    while (p!=NULL){
        p = p->next;
    }
    //2.前向遍历
    while (p!=NULL){
        p = p->prior;
    }
    //3.前向遍历（跳过头结点）
    while (p->prior!=NULL){
        p = p->prior;
    }
}

2.循环链表 2.1循环单链表 2.1.1 定义

循环单链表和单链表的区别在于，表中最后一个结点不是NUL，而改为头结点，使得整个链表首尾相接形成一个环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wzY0BA20-1648388581512)(C:/Users/86189/AppData/Roaming/Typora/typora-user-images/image-20220306132028558.png)]

2.1.2 实现

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,LinkList;

//初始化一个循环单链表
bool InitList(LinkList &L){
    //分配一个头结点
    L = (LNode *)malloc(sizeof(LNode));
    //内存不足，分配失败
    if (L==NULL){
        return false;
    }
    //头结点next指向头结点
    L->next = L;
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L){
    if(L->next == l){
        return true;
    } else{
        return false;
    }
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
    if (p->next==L){
        return true;
    } else{
        return false;
    }
}

2.1.3 单链表与循环单链表的比较

• 单链表：从一个结点出发只能找到后续的各个结点

• 循环单链表：从一个结点出发可以找到其他任何一个结点

  • 从尾部找到头部，时间复杂度为O(1)

2.2 循环双链表 2.2.1 循环双链表的初始化

//循环双链表的初始化
typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinklist;
//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
    //分配一个头结点
    L = (DNode *) malloc(sizeof(DNode));
    if (L==NULL){
        return false;
    }
    //头结点的prior指向头结点
    L->prior = L;
    //头结点的next指向头结点
    L->next = L;
    return true;
}

//判断双链表是否为空
bool Empty(DLinklist L){
    if (L->next==L){
        return true;
    }
    else{
        return false;
    }
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(DLinklist L,DNode *p){
    if (p->next==L){
        return true;
    } else{
        return false;
    }
}

2.2.2 双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}

2.2.3 双链表的删除

p->next = q->next;
q->next->prior = p;
free(q);

2.2.4 顺序表和链表的比较

1. 存取（读写）方式

​ 顺序表可以顺序存取，也可以随机存取

​ 链表只能从表头顺序存取元素

2. 逻辑结构与物理结构

​ 顺序存储，逻辑上相邻的元素，对应物理位置也相邻

​ 链式存储，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的

3. 查找、插入和删除 *** 作

​ 按值查找：顺序表无序，时间复杂度都为O(n)

​ 顺序表有序，可采用折半查找，时间复杂度为O(log₂n)

​ 按序查找：顺序表支持随机访问，时间复杂度为O(1)，链表时间复杂度为O(n)

4. 空间分配

​ 顺序存储在静态存储分配下，空间满，不能扩充，若加入新元素，出现栈溢出

​ 动态存储可扩充存储空间，但是需要移动大量元素，导致 *** 作效率变低，若内存中没有更大块的连续存储空间，则会导致分配失败

​ 链式存储的结点空间只在需要时申请分配，只要有内存就可分配， *** 作灵活高效

2.2.5 在实际中怎样选取存储结构

1. 基于存储的考虑

​ 线性表长度未知，不采用顺序表

​ 链式存储密度低

2. 基于运算考虑

​ 经常做运算使用顺序表

3. 基于环境的考虑

​ 顺序表实现容易，任何高级语言中都有数组类型

​ 链表的 *** 作是基于指针
加入新元素，出现栈溢出

​ 动态存储可扩充存储空间，但是需要移动大量元素，导致 *** 作效率变低，若内存中没有更大块的连续存储空间，则会导致分配失败

​ 链式存储的结点空间只在需要时申请分配，只要有内存就可分配， *** 作灵活高效

2.2.6 在实际中怎样选取存储结构

1. 基于存储的考虑

​ 线性表长度未知，不采用顺序表

​ 链式存储密度低

2. 基于运算考虑

​ 经常做运算使用顺序表

3. 基于环境的考虑

​ 顺序表实现容易，任何高级语言中都有数组类型

​ 链表的 *** 作是基于指针