数据结构-4-双链表

喜欢ヅ旅行 2022-05-27 02:35 196阅读 0赞

数据结构-4-双链表
      
       
      
       在单链表的实现中，我们可以清晰感觉到，要访问链表的尾时必须要遍历链表，这样效率就打了折扣，为了解决这一矛盾，就诞生了双链表。
      
       双链表：每一个节点不仅拥有存储数据的数据变量和指向数据的下一个变量的下一个指针变量，而且含有指向数据变量的前一个变量的一个先前指针变量。
      
       
      
       
    #include<stdio.h>
    #include<assert.h>
    #include<Windows.h>
    
    typedef int DataType;
    
    typedef struct DlistNode
    {
         
        struct DlistNode* next;
        struct DlistNode* prev;
        DataType data;
    }DlistNode;
    
    
    DlistNode* BuyDlistNode(DataType x);
    DlistNode* DListInit();
    void DListDestory(DlistNode* head);
    void DListPrint(DlistNode* head);
    
    void DListPushBack(DlistNode* head, DataType x);
    void DListPushFront(DlistNode* head, DataType x);
    void DListPopBack(DlistNode* head);
    void DListPopFront(DlistNode* head);
    
    DlistNode* DListFind(DlistNode* head, DataType x);
    void DListInsert(DlistNode* pos, DataType x);
    void DListErase(DlistNode* pos);
    
    void DListPrint(DlistNode* head);
    DlistNode* DListInit();
    
    void test1();
    void test2();
    
    DlistNode* BuyDlistNode(DataType x)
    {
         
        DlistNode*new = (DlistNode*)malloc(sizeof(DlistNode));
        assert(new);
    
        new->data = x;
        new->next = NULL;
        new->prev = NULL;
        return new;
    }
    DlistNode* DListInit()
    {
         
        DataType x = 10;
        DlistNode*list = BuyDlistNode(x);
    
        list->next = list;
        list->prev = list;
    
        return list;
    }
    void DListDestory(DlistNode*head)
    {
         
        DlistNode*cur = head->next;
        while (cur!=head)
        {
         
            DlistNode*next = cur->next;
            free(cur);
            cur = next;
        }
        free(head);
        head = NULL;
    }
    void DListPrint(DlistNode* head)
    {
         
        DlistNode*cur = head->next;
        while (cur != head)
        {
         
            printf("%d ", cur->data);
            cur = cur->next;
        }
        printf("head\n");
    }
    
    void DListPushBack(DlistNode* head, DataType x)
    {
         
        /*assert(head); DlistNode*tail = head->prev; DlistNode* newnode = BuyDlistNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = head; head->prev = newnode;*/
        DListInsert(head->prev, x);
    }
    
    void DListPopBack(DlistNode* head)
    {
         
        /*assert(head); DlistNode*tail = head->prev; DlistNode*prev = tail->prev; if (head->next == NULL) return; free(tail); tail = NULL; prev->next = head; head->prev = prev;*/
        DListErase(head->prev);
    }
    
    void DListPushFront(DlistNode* head, DataType x)
    {
         
        /*assert(head); DlistNode*next = head->next; DlistNode*newnode = BuyDlistNode(x); head->next = newnode; newnode->prev = head; newnode->next = next; next->prev = newnode;*/
        DListInsert(head, x);
    }
    
    void DListPopFront(DlistNode* head)
    {
         
        /*assert(head); DlistNode*next = head->next; DlistNode*newnext = next->next; free(next); next = NULL; head->next = newnext; newnext->prev = head;*/
    
        DListErase(head->next);
    }
    
    DlistNode* DListFind(DlistNode* head, DataType x)
    {
         
        assert(head);
        DlistNode*cur = head->next;
        if (x == cur->data)
            return cur;
        while (cur != head)
        {
         
            if (x == cur->data)
                return cur;
            cur = cur->next;
        }
        return NULL;
    }
    
    void DListInsert(DlistNode* pos, DataType x)
    {
         
        DlistNode*newnode = BuyDlistNode(x);
        DlistNode*next = pos->next;
        //pos newnode next
        pos->next = newnode;
        newnode->prev = pos;
    
        newnode->next = next;
        next->prev = newnode;
    }
    void DListErase(DlistNode* pos)
    {
         
        DlistNode*prev = pos->prev;
        DlistNode*next = pos->next;
        free(pos);
        pos = NULL;
        prev->next = next;
        next->prev = prev;
    }
    
    void test1()
    {
         
        DlistNode* list = DListInit();
        DListPushBack(list, 1);
        DListPushBack(list, 2);
        DListPushBack(list, 3);
        DListPushBack(list, 4);
        DListPushBack(list, 5);
        DListPrint(list);
    
        DListPopBack(list);
        DListPopBack(list);
        DListPrint(list);
    }
    
    void test2()
    {
         
        DlistNode* list = DListInit();
        DListPushFront(list, 1);
        DListPushFront(list, 2);
        DListPushFront(list, 3);
        DListPushFront(list, 4);
        DListPushFront(list, 5);
        DListPrint(list);
        printf("%d\n", DListFind(list, 3)->data);
    
        DListPopFront(list);
        DListPopFront(list);
        DListPrint(list);
    }
    
       
        
         1
         2
         3
         4
         五
         6
         7
         8
         9
         10
         11
         12
         13
         14
         15
         16
         17
         18
         19
         20
         21
         22
         23
         24
         25
         26
         27
         28
         29
         三十
         31
         32
         33
         34
         35
         36
         37
         38
         39
         40
         41
         42
         43
         44
         45
         46
         47
         48
         49
         50
         51
         52
         53
         54
         55
         56
         57
         58
         59
         60
         61
         62
         63
         64
         65
         66
         67
         68
         69
         70
         71
         72
         73
         74
         75
         76
         77
         78
         79
         80
         81
         82
         83
         84
         85
         86
         87
         88
         89
         90
         91
         92
         93
         94
         95
         96
         97
         98
         99
         100
         101
         102
         103
         104
         105
         106
         107
         108
         109
         110
         111
         112
         113
         114
         115
         116
         117
         118
         119
         120
         121
         122
         123
         124
         125
         126
         127
         128
         129
         130
         131
         132
         133
         134
         135
         136
         137
         138
         139
         140
         141
         142
         143
         144
         145
         146
         147
         148
         149
         150
         151
         152
         153
         154
         155
         156
         157
         158
         159
         160
         161
         162
         163
         164
         165
         166
         167
         168
         169
         170
         171
         172
         173
         174
         175
         176
         177
         178
         179
         180
         181
         182
         183
         184
         185
         186
         187
         188
         189
         190
         191
         192
         193
         194
         195
         196
         197
         198
         199
         200
         201
         202
        
      
       
    #include"fun.h"
    
    int main()
    {
         
        test2();
        system("pause");
        return 0;
    }