手写C版本的deque

记录一个小demo，留着以后批判。

实现了除了运算符重载以外的所有功能(大概),这里的deque没有使用map做中控器，然后也没有使用分断(512字节)的形式，直接写成了普通的链表,其他的都没什么问题。vector使用的是const static dequetfuntion deque **类似于C++的namespace**中的通用接口。

用到的宏

1
#define TYPE int

data定义

1
2
3
4
5
typedef struct dequenode{
    struct dequenode*next;
    struct dequenode*prev;
    TYPE val;
}dequenode;

头节点定义

1
2
3
4
5
typedef struct dequenode{
    struct dequenode*next;
    struct dequenode*prev;
    TYPE val;
}dequenode;

funtion定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
typedef struct dequefuntion{
    dequehead* (*initdeque)(TYPE);
    //element
    TYPE (*at)(dequehead*,unsigned int);
    TYPE (*front)(dequehead*);
    TYPE (*back)(dequehead*);
    //iterator
    dequenode* (*begin)(dequehead*);
    const dequenode* (*cbegin)(dequehead*);
    dequenode* (*end)(dequehead*);
    const dequenode* (*cend)(dequehead*);
    //capacity
    unsigned int (*empty)(dequehead*);
    unsigned int (*size)(dequehead*);
    //sort
    void (*merge)(dequehead*);
    void (*bubble)(dequehead*);
    void (*quick)(dequehead*);
    //modiflers
    void (*clear)(dequehead*);
    void (*insert)(dequehead*,TYPE,unsigned int);
//    void (*erasebyvalue)(dequehead*,TYPE);
    void (*erasebypos)(dequehead*,unsigned int);
    void (*push_back)(dequehead*,TYPE);
    void (*pop_back)(dequehead*);
    void (*push_front)(dequehead*,TYPE);
    void (*pop_front)(dequehead*);
    void (*print)(dequehead*);
    void (*reverse)(dequehead*);
}dequefuntion;

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dequetest(void){
    dequehead* t = deque.initdeque(20);
    deque.push_back(t,200);
    deque.push_front(t,10);
    deque.insert(t,23,5);
    deque.print(t);
    if(!deque.empty(t))
        printf("size = %d\n",deque.size(t));
    const dequenode* node = deque.cbegin(t);
    printf("node = %d\n",node->val);
    deque.erasebypos(t,2);
    deque.print(t);
    deque.reverse(t);
    deque.print(t);
    dbubblenode(t);
    deque.print(t);
//    printf("at 3 = %d\n",deque.at(t,2));
}

完整代码

Deque.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
//
//  deque.c
//  CwithSTL
//
//  Created by echo on 2021/2/23.
//  Copyright © 2021 echo. All rights reserved.
//

#include "deque.h"
#include "stdio.h"
#include "stdlib.h"


/*deque是一个双口容器，支持双口查看，随机查看元素
 *提供bulbble，quick，merge等三种排序方式
 *支持双端插入删除操作，提供双口指针((const and non const)初级迭代器)
 *支持empty，size操作
 */



dequehead* initdeque(TYPE val){
    dequehead* this = (dequehead*)malloc(sizeof(dequehead));
    dequenode * node = (dequenode*)malloc(sizeof(dequenode));
    node->next = this->head;
    node->prev = this->tail;
    node->val = val;
    this->head = node;
    this->tail = node;
    this->size = 1;
    return  this;
}

void dclear(dequehead* this){
    dequenode* travel = this->head;
    while(travel->next){
        dequenode * tmp = travel;
        travel = travel->next;
        free(tmp);
        tmp->prev = NULL;
        tmp->next = NULL;
    }
    this->head = NULL;
    this->tail = NULL;
    free(this);
}

void dinsert(dequehead*this,TYPE val,unsigned int pos){//有点问题
    dequenode* node = (dequenode*)malloc(sizeof(dequenode));
    node->val = val;//构建插入节点
    if(pos > this->size){//当插入位置大于节点数量时，放在尾部
        this->tail->next = node;
        node->prev = this->tail;
        node->next = NULL;
        this->tail = node;//更新尾节点
        this->size++;
        return;
    }
    dequenode * tarvel = this->head;
    while(pos-- > 1)tarvel = tarvel->next;//走到插入位置
    node->next = tarvel->next;//插入节点的next指针指向遍历节点的下一节点
    tarvel->next->prev = node;//遍历节点的下一节点的prev指针指向插入节点
    node->prev = tarvel;//插入节点的上一节点为遍历节点
    tarvel->next = node;//遍历节点的next指针指向node
    this->size++;
}

void derase(dequehead* this,unsigned int pos){
    if(pos > this->size){
        printf("error: pos > size!\n");
        return;
    }
    this->size--;
    dequenode* travel = this->head;
    while (pos--) travel = travel->next;
    travel->prev->next = travel->next;//travel的前驱的next指针指向travel的后继
    travel->next->prev = travel->prev;//travel的后继的prev指针指向travel的前驱
    travel->prev = NULL;
    travel->next = NULL;
    free(travel);
}

void dpush_back(dequehead* this,TYPE val){
    dequenode* node = (dequenode*)malloc(sizeof(dequenode));
    node->val = val;
    this->tail->next = node;
    node->prev = this->tail;
    node->next = NULL;//新的尾节点指空
    this->tail = node;
    this->size++;
}

void dpop_back(dequehead* this){
    dequenode * node = this->tail;
    this->tail = this->tail->prev;//尾节点改为尾节点的前一节点
    this->tail->next = NULL;
    node->prev = NULL;
    node->next = NULL;
    free(node);
}

void dpush_front(dequehead* this,TYPE val){
    dequenode* node = (dequenode*)malloc(sizeof(dequenode));
    node->val = val;
    node->prev = NULL;
    node->next = this->head;//节点连接
    this->head->prev = node;
    this->head = node;//变更头节点
    this->size++;
}

void dpop_front(dequehead* this){
    dequenode* node = this->head;
    this->head = this->head->next;
    this->head->prev = NULL;
    this->size--;
    node->next = NULL;
//    node->prev = NULL;
    free(node);
}

dequenode* dbegin(dequehead* this){
    if(!this->head)return NULL;
    return this->head;
}

const dequenode* cdbegin(dequehead* this){
    if(!this->head)return NULL;
    return this->head;
}

dequenode* dend(dequehead* this){
    if(!this->tail)return NULL;
    return this->tail;
}

const dequenode* dcend(dequehead* this){
    if(!this->tail)return NULL;
    return this->tail;
}

unsigned int dsize(dequehead* this){
    return this->size;
}

unsigned int dempty(dequehead* this){
    return this->size == 0 ? 1 : 0;
}

TYPE dat(dequehead* this,unsigned int pos){
    if(pos > this->size){
        printf("error: pos > size,return 0\n");
        return 0;
    }
    dequenode* travel = this->head;
    while (pos--) travel = travel->next;
    return travel->val;
}

TYPE dfront(dequehead* this){
    if(!this->head)
        return this->head->val;
    else{
        printf("error: head is NULL return 0!\n");
        return 0;
    }
}

TYPE dback(dequehead* this){
    if(!this->tail){
        printf("error: tail is NULL return 0!\n");
        return 0;
    }
    return this->tail->val;
}

void dmerge(dequehead* this){
    //do something
}

void dbubble(dequehead* this){
    //swap by val
    int i = 0, j = 0;
    dequenode* nodep = this->head,*nodeq = NULL;
    TYPE tmp = 0;
    for(i = 0; i < this->size - 1; i++, nodep = nodep->next){
        for(j = i,nodeq = nodep->next; j < this->size - 1; j++, nodeq = nodeq->next){
            if(nodeq->val < nodep->val){
                tmp = nodeq->val;
                nodeq->val = nodep->val;
                nodep->val = tmp;
            }
        }
    }
}

void dbubblenode(dequehead* this){
    int i = 0, j = 0;//有错误
    dequenode *p = this->head, *q = NULL, *tmp = NULL;
    for(i = 0; i < this->size - 1; i++, p = p->next){
        for(j = i, q = p->next; j < this->size - 1; j++, q = q->next){
            if(q->val < p->val){
                if(i == 0)
                    this->head = p;
                if(i == this->size - 1)
                    this->tail = p;
                tmp = q;
                q = p;
                p = tmp;
            }
        }
    }
}

void dquick(dequehead* this){
    //do something
}

void dprint(dequehead* this){
    dequenode* travel = this->head;
    int index = 0;
    while(travel){
        index ++;
        if(index % 10 == 0)
            printf("\n");
        printf("%d\t",travel->val);
        travel = travel->next;
    }
    if(index % 10 != 0) printf("\n");
}

void dreverse(dequehead* this){
    dequenode* left = NULL,*right = this->head,*tmp = NULL;
    this->tail = this->head;
    while(right){
        tmp = right->next;
        right->next = left;
        left = right;
        right = tmp;
    }
    this->head = left;
}

const dequefuntion deque = {
    initdeque,dat,dfront,dback,dbegin,cdbegin,dend,dcend,dempty,dsize,dmerge,dbubble,dquick,dclear,dinsert,derase,dpush_back,dpop_back,dpush_front,dpop_front,dprint,dreverse
};

void dequetest(void){
    dequehead* t = deque.initdeque(20);
    deque.push_back(t,200);
    deque.push_front(t,10);
    deque.insert(t,23,5);
    deque.print(t);
    if(!deque.empty(t))
        printf("size = %d\n",deque.size(t));
    const dequenode* node = deque.cbegin(t);
    printf("node = %d\n",node->val);
    deque.erasebypos(t,2);
    deque.print(t);
    deque.reverse(t);
    deque.print(t);
    dbubblenode(t);
    deque.print(t);
//    printf("at 3 = %d\n",deque.at(t,2));
}

Duque.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
//
//  deque.h
//  CwithSTL
//
//  Created by echo on 2021/2/23.
//  Copyright © 2021 echo. All rights reserved.
//

#ifndef deque_h
#define deque_h
#define TYPE int
#include <stdio.h>
typedef struct dequenode{
    struct dequenode*next;
    struct dequenode*prev;
    TYPE val;
}dequenode;

typedef struct dequehead{
    struct dequenode *head;
    struct dequenode *tail;
    unsigned int size;
}dequehead;

typedef struct dequefuntion{
    dequehead* (*initdeque)(TYPE);
    //element
    TYPE (*at)(dequehead*,unsigned int);
    TYPE (*front)(dequehead*);
    TYPE (*back)(dequehead*);
    //iterator
    dequenode* (*begin)(dequehead*);
    const dequenode* (*cbegin)(dequehead*);
    dequenode* (*end)(dequehead*);
    const dequenode* (*cend)(dequehead*);
    //capacity
    unsigned int (*empty)(dequehead*);
    unsigned int (*size)(dequehead*);
    //sort
    void (*merge)(dequehead*);
    void (*bubble)(dequehead*);
    void (*quick)(dequehead*);
    //modiflers
    void (*clear)(dequehead*);
    void (*insert)(dequehead*,TYPE,unsigned int);
//    void (*erasebyvalue)(dequehead*,TYPE);
    void (*erasebypos)(dequehead*,unsigned int);
    void (*push_back)(dequehead*,TYPE);
    void (*pop_back)(dequehead*);
    void (*push_front)(dequehead*,TYPE);
    void (*pop_front)(dequehead*);
    void (*print)(dequehead*);
    void (*reverse)(dequehead*);
}dequefuntion;
void dequetest(void);
#endif /* deque_h */

Main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "queue.h"
#include "stack.h"
#include "vector.h"
#include "deque.h"
#define list_entry(ptr, type, member) \
    ((type*)((char*)(ptr)-(char*)&(((type*)0)->member)))
extern const struct VectorFuntion vector;
//貌似sort有点小问题，排序貌似不支持01开始
extern const struct stackFuntion stack;
//貌似deque有点小问题，不支持扩容，最大容量通过修改stack.c中的SIZE宏来确定
extern const struct queuefuntion queue;
// queue没有使用deque容器，使用过程中没有发现问题
extern const struct dequefuntion deque;
//暂时还没有实现几个排序方法(merge和quick sort)
int main(){
  dequetest();
}