线性表--链式存储结构--双向链表

作者: 我可能是个假开发 | 来源:发表于2018-03-29 19:26 被阅读156次

    双向链表

    一、双向链表结构

    双向链表结点结构

    typedef struct DualNode
    {
        ElemType data;
        struct DualNode *prior;  //前驱结点
        struct DualNode *next;   //后继结点
    } DualNode, *DuLinkList;
    
    双向链表结点结构.png

    既然单链表可以有循环链表,那么双向链表当然也可以有。

    非空的双循环链表.png

    由于这是双向链表,那么对于链表中的某一个结点p,它的后继结点的前驱结点是它本身。

    二、双向链表的插入操作

    插入操作.jpg

    代码实现:

    s->next = p;    
    s->prior = p->prior;    
    p->prior->next = s; 
    p->prior = s;
    

    关键在于交换的过程中不要出现矛盾,例如第四步先被执行了,那么p->prior就会提前变成s,使得插入的工作出错。

    三、双向链表的删除操作

    删除操作.png

    代码实现:

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

    双向链表可以有效提高算法的时间性能,说白了就是用空间来换取时间。

    四、双向链表的实践

    要求实现用户输入一个数使得26个字母的排列发生变化,例如用户输入3,输出结果:
    DEFGHIJKLMNOPQRSTUVWXYZABC
    同时需要支持负数,例如用户输入-3,输出结果:
    XYZABCDEFGHIJKLMNOPQRSTUVW

    代码实现:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define OK 1
    #define ERROR 0
    
    typedef char ElemType;
    typedef int Status;
    typedef struct DualNode{
        ElemType data;
        struct DualNode *prior;
        struct DualNode *next;
    }DualNode,*DuLinkList;
    
    Status InitList(DuLinkList *L){
        DualNode *p,*q;
        int i;
    
        *L = (DuLinkList)malloc(sizeof(DualNode));
        if(!(*L)){
            return ERROR;
        }
         
        (*L)->next = (*L)->prior = NULL;
        p = (*L);
    
        for(i=0;i<26;i++){
            q = (DualNode *)malloc(sizeof(DualNode));
            if(!q){
                return ERROR;
            }
    
            q->data = 'A'+i;
            q->prior = p;
            q->next = p->next;
            
            p = q;
    
        }
    
        p->next = (*L)->next;
        (*L)->next->prior = p;
    
        return OK;
    }
    
    void Caesar(DuLinkList *L,int i){
        if(i>0){
            do{
                (*L) = (*L)->next;
            }while(--i);
        }
    
        if(i<0){
            do{
                (*L) = (*L)->next;
            }while(++i);
        }
    }
    
    int main(){
        DuLinkList L;
        int i,n;
    
        InitList(&L);
    
        printf("请输入一个整数:");
        scanf("%d",&n);
        printf("\n");
        Caesar(&L,n);
        
        for(i=0;i<26;i++){
            L = L->next;
            printf("%c",L->data);
        }
        printf("\n");
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:线性表--链式存储结构--双向链表

        本文链接:https://www.haomeiwen.com/subject/wwdvcftx.html