尾插法构建双链表并遍历(C语言)

阳光穿透心脏的1/2处 2022-12-06 12:41 81阅读 0赞

#### 前言 ####

双链表是指，不光有后缀指针，还有前缀指针，需要注意的是，要与双向循环链表区别，在双链表中，表头结点的前缀指向NULL,表尾结点的后缀指向NULL；

#### 双链表的定义 ####

typedef struct Dnode{
        
        struct Dnode *next;
        struct Dnode *prior;
        int data;
    }Dnode,*DnodeLinkedList;

#### 双链表的构造(尾插法) ####

//构造双链表
        DnodeLinkedList DL = (DnodeLinkedList)malloc(sizeof(Dnode));
        DL->prior = NULL;
        Dnode *s,*r = DL;
        int input_data;
        scanf("%d",&input_data);
        while(input_data!=-999)
        {
        
            s = (Dnode*)malloc(sizeof(Dnode));
            s->data = input_data;
            r->next = s;
            s->prior= r;
            r = s;
            scanf("%d",&input_data);
    
        }
        r->next = NULL;

#### 遍历 ####

// 从前向后遍历
        printf("从前向后遍历 ");
        Dnode *p = DL;
        while(p->next!=NULL)
        {
        
            p = p->next;
            printf("%d ",p->data);
        }
    
        // 从尾部向前遍历
        printf("尾部向前遍历 ");
        Dnode *q = r;
        printf("%d ",q->data);
        while(q->prior!=DL)
        {
        
            q = q->prior;
            printf("%d ",q->data);
        }

#### 完整程序 ####

#include <stdio.h>
    #include <stdlib.h>
    typedef struct Dnode{
        
        struct Dnode *next;
        struct Dnode *prior;
        int data;
    }Dnode,*DnodeLinkedList;
    
    
    int main()
    {
        
    
        //构造双链表
        DnodeLinkedList DL = (DnodeLinkedList)malloc(sizeof(Dnode));
        DL->prior = NULL;
        Dnode *s,*r = DL;
        int input_data;
        scanf("%d",&input_data);
        while(input_data!=-999)
        {
        
            s = (Dnode*)malloc(sizeof(Dnode));
            s->data = input_data;
            r->next = s;
            s->prior= r;
            r = s;
            scanf("%d",&input_data);
    
        }
        r->next = NULL;
    
        // 从前向后遍历
        printf("从前向后遍历 ");
        Dnode *p = DL;
        while(p->next!=NULL)
        {
        
            p = p->next;
            printf("%d ",p->data);
        }
    
        // 从尾部向前遍历
        printf("尾部向前遍历 ");
        Dnode *q = r;
        printf("%d ",q->data);
        while(q->prior!=DL)
        {
        
            q = q->prior;
            printf("%d ",q->data);
        }
    
        return 0;
    }

#### 运行结果 ####

![在这里插入图片描述][20200913105620903.png_pic_center]

[20200913105620903.png_pic_center]: /images/20221123/1f3a34c3661f4b81a9f87d5e77aa1a2e.png