数据结构(二)——线性表(双链表)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构(二)——线性表(双链表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2.3.3 双链表

单链表：单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历,无法逆向检索，有时候不太方便

双链表的定义：双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继
表头结点的prior域和尾结点的next域都是NULL。
数据结构(二)——线性表(双链表),考研408,数据结构

双链表结点类型描述如下：

typedef struct DNode{            //定义双链表结点类型
    ElemType data;                //数据域
    struct DNode *prior, *next;    //前驱和后继指针
} DNode, *DLinklist;

双链表在单链表结点中增加了一个指向其前驱的指针 prior

双链表的初始化 (带头结点)：

typedef struct DNode{       //D表示double
    ElemType data;     
    struct DNode *prior, *next;
}DNode, *DLinklist;

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

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

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

双链表的插入操作：

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

bool InsertNextDNode(DNode *p, DNode *s){ 
    if(p==NULL || s==NULL)  
        return false;         
    s->next = p->next;       // 将结点s插入到结点p之后
    if (p->next != NULL)       // 判断结点p之后是否有后继结点  
        p->next->prior = s; //p结点的后置结点的前向指针指向新插入的s
    s->prior = p;   //把s的前向指针指向p结点
    p->next = s;     //把p结点的后向指针指向s结点
    return true;
}

双链表的删除操作：

// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){   
    if(p==NULL)           
        return false;      
    DNode *q =p->next;       // 找到p的后继结点q 
    if(q==NULL)          //p没有后继就返回false
        return false;    
    p->next = q->next;   //q结点不是最后一个结点
    if(q->next != NULL) 
        q->next->prior=p;  
    free(q);             //释放结点空间
    return true;
}

// 销毁一个双链表
bool DestoryList(DLinklist &L){ 
    // 循环释放各个数据结点   
    while(L->next != NULL){    
        DeletNextDNode(L);      
        free(L);            //释放头结点
        L=NULL;             // 头指针指向NULL
    }
}

双链表的遍历：

// 向后遍历
while(p!=NULL){    
    // 对结点p做相应处理    
    p = p->next;
}

// 向前遍历
while(p!=NULL){    
    // 对结点p做相应处理 
    p = p->prior;
}

// 跳过头结点的遍历
while(p->prior!=NULL){ 
    //对结点p做相应处理    
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)
数据结构(二)——线性表(双链表),考研408,数据结构

2.3.4 循环链表

循环单链表

数据结构(二)——线性表(双链表),考研408,数据结构

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环
在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针L。

循环单链表的实现：

typedef struct LNode{           //定义单链表结点类型
    ElemType data;                  
    struct LNode *next;     //指针指向下一个元素
}DNode, *Linklist;

// 初始化循环单链表
bool InitList(LinkList &L){    
    L = (LNode *)malloc(sizeof(LNode));      //分配一个头结点
    if(L==NULL)             //内存不足，分配失败
        return false;    
    L->next = L;           // 最后一个结点的next指针指向头结点    
    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)          //看p结点的下一个结点是否是头结点
        return true;      
    else            
        return false;
}

单链表:从一个结点出发只能找到后续的各个结点
循环单链表:从一个结点出发可以找到其他任何一个结点

循环双链表
数据结构(二)——线性表(双链表),考研408,数据结构

循环双链表的初始化

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;    
    L->prior = L;           //头结点的prior指针指向最后一个结点
    L->next = L;         //最后一个结点的next指针指向头结点 
}

void testDLinkList(){
    //初始化循环双链表
    DLinkList L;
    InitDLinkList(L);
    //...
}

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

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

循环双链表的插入

// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){  
    s->next = p->next;   
    //循环双链表不用担心p结点的下一个结点为空   
    p->next->prior = s;  
    s->prior = p;     
    p->next = s;
}

循环双链表的删除

// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){  
    // 找到p的后继结点q       
    DNode *q =p->next;        
    //循环双链表不用担心q结点的下一个结点为空  
    p->next = q->next;    
    q->next->prior=p;    
    free(q);      
    return true;
}

2.3.5 静态链表

静态链表：用数组的方式实现的链表

优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不可变

适用场景：
①不支持指针的低级语言；
②数据元素数量固定不变的场景(如操作系统的文件分配表FAT）

数据结构(二)——线性表(双链表),考研408,数据结构
静态链表是用数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对地址(数组下标)，又称游标。

静态链表的定义

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

// 用数组定义多个连续存放的结点
void testSLinkList(){    
    struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node    
    ...
}

王道书上是这么定义的，侧重于强调 a 是一个静态链表而非数组。

#define MaxSize 10        //静态链表的最大长度
typedef struct{           //静态链表结构类型的定义       
    ELemType data;        //存储数据元素     
    int next;             //下一个元素的数组下标
}SLinkList[MaxSize];

void testSLinkList(){      
    SLinkList a;
}

静态链表基本操作实现

初始化静态链表:
把a[0]的next 设为-1
把其他结点的next 设为一个特殊值用来表示结点空闲，如-2

查找结点：
从头结点出发挨个往后遍历结点

插入位序为 i 的结点：
①找到一个空的结点，存入数据元素
②从头结点出发找到位序为 i-1 的结点
③修改新结点的 next
④修改 i-1 号结点的 next

删除某个结点：
①从头结点出发找到前驱结点
②修改前驱结点的游标
③被删除结点 next 设为 -2文章来源地址https://www.toymoban.com/news/detail-838570.html

到了这里，关于数据结构(二)——线性表(双链表)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！