链表也是一种数据结构，它就是用来对链式
物理结构进行管理的
链表可以把链式物理结构的管理代码和其他
代码分隔开
链表的功能主要包含插入，删除，查找和遍历
/* 链表演示 */ #ifndef __04LINK_H__ #define __04LINK_H__ typedef struct node { int num; struct node *p_next; } node; typedef struct { node head, tail; } link; //初始化函数 void link_init(link *); //清理函数 void link_deinit(link *); //获得有效数字个数的函数 int link_size(const link *); //在链表头加入数字 void link_add_head(link *, int ); //在链表末尾追加数字 void link_append(link *, int ); //按顺序加入数字的函数 void link_insert_in_order(link *, int ); //删除最前边数字的函数 void link_remove_head(link *); //删除最后一个结点的函数 void link_remove_tail(link *); //获得最前面数字的函数 int link_get_head(const link *, int *); //获得最后一个数字的函数 int link_get_tail(link *, int *); #endif //__04LINK_H__ /* 链表演示 */ #include <stdlib.h> #include "04link.h" //初始化函数 void link_init(link *p_link) { p_link->head.p_next = &(p_link->tail); p_link->tail.p_next = NULL; } //清理函数 void link_deinit(link *p_link) { while (p_link->head.p_next != &(p_link->tail)) { node *p_first = &(p_link->head); node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; p_first->p_next = p_last; free(p_mid); p_mid = NULL; } } //获得有效数字个数的函数 int link_size(const link *p_link) { int cnt = 0; const node *p_node = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { const node *p_first = p_node; const node *p_mid = p_first->p_next; const node *p_last = p_mid->p_next; if (p_mid != &(p_link->tail)) { cnt++; } } return cnt; } //在链表头加入数字 void link_add_head(link *p_link, int num) { node *p_first = NULL, *p_mid = NULL, *p_last = NULL; node *p_tmp = (node *)malloc(sizeof(node)); if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; p_first = &(p_link->head); p_mid = p_first->p_next; p_last = p_mid->p_next; p_first->p_next = p_tmp; p_tmp->p_next = p_mid; } //在链表末尾追加数字 void link_append(link *p_link, int num) { node *p_tmp = (node *)malloc(sizeof(node)); node *p_node = NULL; if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_mid == &(p_link->tail)) { p_first->p_next = p_tmp; p_tmp->p_next = p_mid; break; } } } //按顺序加入数字的函数 void link_insert_in_order(link *p_link, int num) { node *p_node = NULL; node *p_tmp = (node *)malloc(sizeof(node)); if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_mid == &(p_link->tail) || p_mid->num > num) { p_first->p_next = p_tmp; p_tmp->p_next = p_mid; break; } } } //删除最前边数字的函数 void link_remove_head(link *p_link) { node *p_first = NULL, *p_mid = NULL, *p_last = NULL; p_first = &(p_link->head); p_mid = p_first->p_next; p_last = p_mid->p_next; p_first->p_next = p_last; free(p_mid); p_mid = NULL; } //删除最后一个结点的函数 void link_remove_tail(link *p_link) { node *p_node = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_last == &(p_link->tail)) { p_first->p_next = p_last; free(p_mid); p_mid = NULL; break; } } } //获得最前面数字的函数 int link_get_head(const link *p_link, int *p_num) { if (p_link->head.p_next == &(p_link->tail)) { return 0; } else { *p_num = p_link->head.p_next->num; return 1; } } //获得最后一个数字的函数 int link_get_tail(link *p_link, int *p_num) { node *p_node = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_last == &(p_link->tail)) { *p_num = p_mid->num; return 1; } } return 0; } /* 链表测试 */ #include <stdio.h> #include "04link.h" int main() { int num = 0; node *p_node = NULL; link lnk = {0}; link_init(&lnk); link_add_head(&lnk, 10); link_append(&lnk, 100); link_insert_in_order(&lnk, 70); link_insert_in_order(&lnk, 20); link_insert_in_order(&lnk, 40); link_insert_in_order(&lnk, 30); link_insert_in_order(&lnk, 50); printf("数字个数是%d ", link_size(&lnk)); for (p_node = &(lnk.head);p_node != &(lnk.tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_mid != &(lnk.tail)) { printf("%d ", p_mid->num); } } printf(" "); link_remove_head(&lnk); link_remove_tail(&lnk); link_get_head(&lnk, &num); printf("最前边的数字是%d ", num); link_get_tail(&lnk, &num); printf("最后边的数字是%d ", num); printf("数字个数是%d ", link_size(&lnk)); for (p_node = &(lnk.head);p_node != &(lnk.tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_mid != &(lnk.tail)) { printf("%d ", p_mid->num); } } printf(" "); link_deinit(&lnk); return 0; }
/* 链表演示 */ #ifndef __01LINK_H__ #define __01LINK_H__ typedef struct node { int num; struct node *p_next; struct node *p_prev; } node; typedef struct { node head, tail; node *p_cur; } link; //初始化函数 void link_init(link *); //清理函数 void link_deinit(link *); //获得有效数字个数的函数 int link_size(const link *); //在链表头加入数字 void link_add_head(link *, int ); //在链表末尾追加数字 void link_append(link *, int ); //按顺序加入数字的函数 void link_insert_in_order(link *, int ); //删除最前边数字的函数 void link_remove_head(link *); //删除最后一个结点的函数 void link_remove_tail(link *); //获得最前面数字的函数 int link_get_head(const link *, int *); //获得最后一个数字的函数 int link_get_tail(const link *, int *); //开始从前向后遍历所有结点 void link_begin(link *); //在遍历中获得下一个结点的数字 int link_next(link *, int *); //开始从后向前遍历所有结点 void link_rbegin(link *); //获得前一个数字的函数 int link_prev(link *, int *); #endif //__01LINK_H__ /* 链表演示 */ #include <stdlib.h> #include "01link.h" //初始化函数 void link_init(link *p_link) { p_link->head.p_next = &(p_link->tail); p_link->tail.p_next = NULL; p_link->tail.p_prev = &(p_link->head); p_link->head.p_prev = NULL; p_link->p_cur = NULL; } //清理函数 void link_deinit(link *p_link) { while (p_link->head.p_next != &(p_link->tail)) { node *p_first = &(p_link->head); node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; p_first->p_next = p_last; p_last->p_prev = p_first; free(p_mid); p_mid = NULL; } p_link->p_cur = NULL; } //获得有效数字个数的函数 int link_size(const link *p_link) { int cnt = 0; const node *p_node = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { const node *p_first = p_node; const node *p_mid = p_first->p_next; const node *p_last = p_mid->p_next; if (p_mid != &(p_link->tail)) { cnt++; } } return cnt; } //在链表头加入数字 void link_add_head(link *p_link, int num) { node *p_first = NULL, *p_mid = NULL, *p_last = NULL; node *p_tmp = (node *)malloc(sizeof(node)); if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; p_tmp->p_prev = NULL; p_first = &(p_link->head); p_mid = p_first->p_next; p_last = p_mid->p_next; p_first->p_next = p_tmp; p_tmp->p_prev = p_first; p_tmp->p_next = p_mid; p_mid->p_prev = p_tmp; p_link->p_cur = NULL; } //在链表末尾追加数字 void link_append(link *p_link, int num) { node *p_first = NULL, *p_mid = NULL, *p_last = NULL; node *p_tmp = (node *)malloc(sizeof(node)); if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; p_tmp->p_prev = NULL; p_first = p_link->tail.p_prev; p_mid = p_first->p_next; p_last = p_mid->p_next; p_first->p_next = p_tmp; p_tmp->p_prev = p_first; p_tmp->p_next = p_mid; p_mid->p_prev = p_tmp; p_link->p_cur = NULL; } /*void link_append(link *p_link, int num) { node *p_tmp = (node *)malloc(sizeof(node)); node *p_node = NULL; if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; p_tmp->p_prev = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_mid == &(p_link->tail)) { p_first->p_next = p_tmp; p_tmp->p_prev = p_first; p_tmp->p_next = p_mid; p_mid->p_prev = p_tmp; break; } } p_link->p_cur = NULL; }*/ //按顺序加入数字的函数 void link_insert_in_order(link *p_link, int num) { node *p_node = NULL; node *p_tmp = (node *)malloc(sizeof(node)); if (!p_tmp) { return ; } p_tmp->num = num; p_tmp->p_next = NULL; p_tmp->p_prev = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_mid == &(p_link->tail) || p_mid->num > num) { p_first->p_next = p_tmp; p_tmp->p_prev = p_first; p_tmp->p_next = p_mid; p_mid->p_prev = p_tmp; break; } } p_link->p_cur = NULL; } //删除最前边数字的函数 void link_remove_head(link *p_link) { node *p_first = NULL, *p_mid = NULL, *p_last = NULL; p_first = &(p_link->head); p_mid = p_first->p_next; p_last = p_mid->p_next; p_first->p_next = p_last; p_last->p_prev = p_first; free(p_mid); p_mid = NULL; p_link->p_cur = NULL; } //删除最后一个结点的函数 void link_remove_tail(link *p_link) { if (p_link->head.p_next != &(p_link->tail)) { node *p_first = p_link->tail.p_prev->p_prev; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; p_first->p_next = p_last; p_last->p_prev = p_first; free(p_mid); p_mid = NULL; } p_link->p_cur = NULL; } /*void link_remove_tail(link *p_link) { node *p_node = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_last == &(p_link->tail)) { p_first->p_next = p_last; p_last->p_prev = p_first; free(p_mid); p_mid = NULL; break; } } p_link->p_cur = NULL; }*/ //获得最前面数字的函数 int link_get_head(const link *p_link, int *p_num) { if (p_link->head.p_next == &(p_link->tail)) { return 0; } else { *p_num = p_link->head.p_next->num; return 1; } } //获得最后一个数字的函数 int link_get_tail(const link *p_link, int *p_num) { if (p_link->head.p_next == &(p_link->tail)) { return 0; } else { *p_num = p_link->tail.p_prev->num; return 1; } } /*int link_get_tail(const link *p_link, int *p_num) { node *p_node = NULL; for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) { node *p_first = p_node; node *p_mid = p_first->p_next; node *p_last = p_mid->p_next; if (p_last == &(p_link->tail)) { *p_num = p_mid->num; return 1; } } return 0; }*/ //开始从前向后遍历所有结点 void link_begin(link *p_link) { p_link->p_cur = &(p_link->head); } //在遍历过程中获得下一个数字 int link_next(link *p_link, int *p_num) { if (!(p_link->p_cur)) { return 0; } p_link->p_cur = p_link->p_cur->p_next; if (p_link->p_cur == &(p_link->tail)) { p_link->p_cur = NULL; return 0; } else { *p_num = p_link->p_cur->num; return 1; } } //开始从后向前依次遍历链表中所有结点 void link_rbegin(link *p_link) { p_link->p_cur = &(p_link->tail); } //在从后先前遍历过程中获得前一个数字 int link_prev(link *p_link, int *p_num) { if (!(p_link->p_cur)) { return 0; } p_link->p_cur = p_link->p_cur->p_prev; if (p_link->p_cur == &(p_link->head)) { return 0; } else { *p_num = p_link->p_cur->num; return 1; } } /* 链表测试 */ #include <stdio.h> #include "01link.h" int main() { int num = 0; link lnk = {0}; link_init(&lnk); link_add_head(&lnk, 10); link_append(&lnk, 100); link_insert_in_order(&lnk, 70); link_insert_in_order(&lnk, 20); link_insert_in_order(&lnk, 40); link_insert_in_order(&lnk, 30); link_insert_in_order(&lnk, 50); printf("数字个数是%d ", link_size(&lnk)); link_begin(&lnk); while (1) { if (link_next(&lnk, &num)) { printf("%d ", num); } else { break; } } printf(" "); link_remove_head(&lnk); link_remove_tail(&lnk); link_get_head(&lnk, &num); printf("最前边的数字是%d ", num); link_get_tail(&lnk, &num); printf("最后边的数字是%d ", num); printf("数字个数是%d ", link_size(&lnk)); link_begin(&lnk); while (1) { if (link_next(&lnk, &num)) { printf("%d ", num); } else { break; } } printf(" "); link_rbegin(&lnk); while (1) { if (link_prev(&lnk, &num)) { printf("%d ", num); } else { break; } } printf(" "); link_deinit(&lnk); return 0; }