目录题目解法一、双向链表题目解法一、双向链表#include stdio.h #include stdlib.h #include stdbool.h /**********************************************************************/ struct list_node { int val; struct list_node *prev; struct list_node *next; }; struct list_node list_nodes[1000000]; struct list { struct list_node *head; struct list_node *nodes; }; struct list_node *list_node(struct list *list, int val) { return list-nodes[val]; } struct list_node *list_alloc_node(struct list *list, int val) { struct list_node *node list_node(list, val); node-val val; node-prev NULL; node-next NULL; return node; } struct list *list_init(int len) { struct list *list malloc(sizeof(*list)); struct list_node *tail NULL; struct list_node *node NULL; list-nodes list_nodes; list-head list_alloc_node(list, 0); tail list-head; for (int i 0; i len; i) { node list_alloc_node(list, i 1); node-prev tail; tail-next node; tail node; } return list; } struct list_node *list_find(struct list *list, int val) { struct list_node *node list_node(list, val); if (!node-prev) return NULL; return node; } void list_remove(struct list *list, int val) { struct list_node *curr_node list_find(list, val); if (!curr_node) return; struct list_node *prev_node curr_node-prev; struct list_node *next_node curr_node-next; prev_node-next next_node; if (next_node) next_node-prev prev_node; curr_node-next NULL; curr_node-prev NULL; } void list_left_insert(struct list *list, int val1, int val2) { struct list_node *node list_find(list, val1); struct list_node *curr_node list_find(list, val2); struct list_node *prev_node curr_node-prev; if (node prev_node) return; if (node curr_node) return; list_remove(list, node-val); node list_alloc_node(list, val1); node-prev prev_node; prev_node-next node; node-next curr_node; curr_node-prev node; } void list_right_insert(struct list *list, int val1, int val2) { struct list_node *node list_find(list, val1); struct list_node *curr_node list_find(list, val2); struct list_node *next_node curr_node-next; if (node next_node) return; if (node curr_node) return; list_remove(list, node-val); node list_alloc_node(list, val1); node-prev curr_node; curr_node-next node; if (next_node) { node-next next_node; next_node-prev node; } } bool list_is_empty(struct list *list) { return list-head-next ? false : true; } void list_for_each(struct list *list, void (*func)(struct list_node *, void *), void *param) { for (struct list_node *n list-head-next; n; n n-next) func(n, param); } /**********************************************************************/ struct opt_info { int opt; int x; int y; }; void read_num(int *num) { scanf(%d, num); } void read_opt_info(struct opt_info *opt_info) { scanf(%d, opt_info-opt); if (opt_info-opt ! 3) scanf(%d %d, opt_info-x, opt_info-y); else scanf(%d, opt_info-x); } /**********************************************************************/ void print_node(struct list_node *node, void *param) { printf(%d , node-val); } int main(void) { int init_len; int opt_num; struct opt_info opt_info; struct list *list NULL; read_num(init_len); list list_init(init_len); read_num(opt_num); for (int i 0; i opt_num; i) { read_opt_info(opt_info); switch (opt_info.opt) { case 1: list_left_insert(list, opt_info.x, opt_info.y); break; case 2: list_right_insert(list, opt_info.x, opt_info.y); break; case 3: list_remove(list, opt_info.x); break; default: break; } } if (!list_is_empty(list)) list_for_each(list, print_node, NULL); else printf(Empty!); return 0; }
【洛谷 B4323】【模板】双向链表
目录题目解法一、双向链表题目解法一、双向链表#include stdio.h #include stdlib.h #include stdbool.h /**********************************************************************/ struct list_node { int val; struct list_node *prev; struct list_node *next; }; struct list_node list_nodes[1000000]; struct list { struct list_node *head; struct list_node *nodes; }; struct list_node *list_node(struct list *list, int val) { return list-nodes[val]; } struct list_node *list_alloc_node(struct list *list, int val) { struct list_node *node list_node(list, val); node-val val; node-prev NULL; node-next NULL; return node; } struct list *list_init(int len) { struct list *list malloc(sizeof(*list)); struct list_node *tail NULL; struct list_node *node NULL; list-nodes list_nodes; list-head list_alloc_node(list, 0); tail list-head; for (int i 0; i len; i) { node list_alloc_node(list, i 1); node-prev tail; tail-next node; tail node; } return list; } struct list_node *list_find(struct list *list, int val) { struct list_node *node list_node(list, val); if (!node-prev) return NULL; return node; } void list_remove(struct list *list, int val) { struct list_node *curr_node list_find(list, val); if (!curr_node) return; struct list_node *prev_node curr_node-prev; struct list_node *next_node curr_node-next; prev_node-next next_node; if (next_node) next_node-prev prev_node; curr_node-next NULL; curr_node-prev NULL; } void list_left_insert(struct list *list, int val1, int val2) { struct list_node *node list_find(list, val1); struct list_node *curr_node list_find(list, val2); struct list_node *prev_node curr_node-prev; if (node prev_node) return; if (node curr_node) return; list_remove(list, node-val); node list_alloc_node(list, val1); node-prev prev_node; prev_node-next node; node-next curr_node; curr_node-prev node; } void list_right_insert(struct list *list, int val1, int val2) { struct list_node *node list_find(list, val1); struct list_node *curr_node list_find(list, val2); struct list_node *next_node curr_node-next; if (node next_node) return; if (node curr_node) return; list_remove(list, node-val); node list_alloc_node(list, val1); node-prev curr_node; curr_node-next node; if (next_node) { node-next next_node; next_node-prev node; } } bool list_is_empty(struct list *list) { return list-head-next ? false : true; } void list_for_each(struct list *list, void (*func)(struct list_node *, void *), void *param) { for (struct list_node *n list-head-next; n; n n-next) func(n, param); } /**********************************************************************/ struct opt_info { int opt; int x; int y; }; void read_num(int *num) { scanf(%d, num); } void read_opt_info(struct opt_info *opt_info) { scanf(%d, opt_info-opt); if (opt_info-opt ! 3) scanf(%d %d, opt_info-x, opt_info-y); else scanf(%d, opt_info-x); } /**********************************************************************/ void print_node(struct list_node *node, void *param) { printf(%d , node-val); } int main(void) { int init_len; int opt_num; struct opt_info opt_info; struct list *list NULL; read_num(init_len); list list_init(init_len); read_num(opt_num); for (int i 0; i opt_num; i) { read_opt_info(opt_info); switch (opt_info.opt) { case 1: list_left_insert(list, opt_info.x, opt_info.y); break; case 2: list_right_insert(list, opt_info.x, opt_info.y); break; case 3: list_remove(list, opt_info.x); break; default: break; } } if (!list_is_empty(list)) list_for_each(list, print_node, NULL); else printf(Empty!); return 0; }
