145 lines
3 KiB
C
145 lines
3 KiB
C
|
#include <stdio.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <assert.h>
|
||
|
|
|
||
|
|
typedef struct node {
|
||
|
|
int element;
|
||
|
|
struct node* prev;
|
||
|
|
struct node* next;
|
||
|
|
} *Nodeptr, Node;
|
||
|
|
|
||
|
|
typedef struct list {
|
||
|
|
Nodeptr head, tail, current_node;
|
||
|
|
} *List;
|
||
|
|
|
||
|
|
List dll_create();
|
||
|
|
void dll_insertafter(List l, int element);
|
||
|
|
int dll_find_next(List l);
|
||
|
|
int dll_find_prev(List l);
|
||
|
|
void dll_insertbefore(List l, int element);
|
||
|
|
int dll_find(List l, int element);
|
||
|
|
void dll_find_first(List l);
|
||
|
|
void dll_find_last(List l);
|
||
|
|
int dll_retrieve(List l);
|
||
|
|
void dll_update(List l, int element);
|
||
|
|
void dll_clear(List l);
|
||
|
|
|
||
|
|
List dll_create() {
|
||
|
|
List l = malloc(sizeof(struct list));
|
||
|
|
l->head = NULL;
|
||
|
|
l->tail = NULL;
|
||
|
|
l->current_node = NULL;
|
||
|
|
return l;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dll_insertafter(List l, int element) {
|
||
|
|
Nodeptr n = malloc(sizeof(Node));
|
||
|
|
n->element = element;
|
||
|
|
n->next = NULL;
|
||
|
|
n->prev = NULL;
|
||
|
|
if(l->head == NULL) {
|
||
|
|
l->head = l->tail = n;
|
||
|
|
} else {
|
||
|
|
n->next = l->current_node->next;
|
||
|
|
if(l->current_node == l->tail) {
|
||
|
|
l->tail = n;
|
||
|
|
} else {
|
||
|
|
l->current_node->next->prev = n;
|
||
|
|
}
|
||
|
|
l->current_node->next = n;
|
||
|
|
n->prev = l->current_node;
|
||
|
|
}
|
||
|
|
l->current_node = n;
|
||
|
|
}
|
||
|
|
|
||
|
|
int dll_find_next(List l) {
|
||
|
|
if(l->current_node == l->tail) return 0;
|
||
|
|
l->current_node = l->current_node->next;
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
int dll_find_prev(List l) {
|
||
|
|
if(l->current_node == l->head) return 0;
|
||
|
|
l->current_node = l->current_node->prev;
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dll_insertbefore(List l, int element) {
|
||
|
|
if(l->head == NULL) {
|
||
|
|
dll_insertafter(l,element);
|
||
|
|
} else if(!dll_find_prev(l)) {
|
||
|
|
Nodeptr n = malloc(sizeof(Node));
|
||
|
|
n->element = element;
|
||
|
|
n->next = l->head;
|
||
|
|
n->prev = NULL;
|
||
|
|
l->head->prev = n;
|
||
|
|
l->head = n;
|
||
|
|
l->current_node = n;
|
||
|
|
} else {
|
||
|
|
dll_insertafter(l,element);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int dll_find(List l, int element) {
|
||
|
|
dll_find_first(l);
|
||
|
|
do {
|
||
|
|
if(dll_retrieve(l) == element) return 1;
|
||
|
|
} while(dll_find_next(l));
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dll_find_first(List l) {
|
||
|
|
assert(l->head != NULL);
|
||
|
|
l->current_node = l->head;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dll_find_last(List l) {
|
||
|
|
assert(l->tail != NULL);
|
||
|
|
l->current_node = l->tail;
|
||
|
|
}
|
||
|
|
|
||
|
|
int dll_retrieve(List l) {
|
||
|
|
assert(l->current_node != NULL);
|
||
|
|
return l->current_node->element;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dll_update(List l, int element) {
|
||
|
|
assert(l->current_node != NULL);
|
||
|
|
l->current_node->element = element;
|
||
|
|
}
|
||
|
|
|
||
|
|
void dll_clear(List l) {
|
||
|
|
Nodeptr tmp, iter;
|
||
|
|
iter = l->head;
|
||
|
|
while(iter != NULL) {
|
||
|
|
tmp = iter;
|
||
|
|
iter = iter->next;
|
||
|
|
free(tmp);
|
||
|
|
}
|
||
|
|
|
||
|
|
l->head = NULL;
|
||
|
|
l->tail = NULL;
|
||
|
|
l->current_node = NULL;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main( int argc, char *argv[] ) {
|
||
|
|
List l = dll_create();
|
||
|
|
for(int i = 0; i < 10; i++) {
|
||
|
|
dll_insertafter(l,i);
|
||
|
|
}
|
||
|
|
|
||
|
|
dll_find(l,5);
|
||
|
|
|
||
|
|
do {
|
||
|
|
printf("%d\n", dll_retrieve(l));
|
||
|
|
} while(dll_find_next(l));
|
||
|
|
|
||
|
|
dll_find_first(l);
|
||
|
|
do {
|
||
|
|
printf("%d\n", dll_retrieve(l));
|
||
|
|
} while(dll_find_next(l));
|
||
|
|
|
||
|
|
dll_clear(l);
|
||
|
|
return 0;
|
||
|
|
}
|