0x00数据结构——C语言实现（单向循环链表）
/*filename:circular_list.h*//* 循环链表(circular list)是另一种形式的表示线性表的链表，与单链表不同的是， 表尾结点的link域中不是NULL而是存放指向链表开始结点的指针。 Functions: 创建一个空线性表 计算表长度 返回附加头结点的地址 搜索函数：找x在表中的位置，返回表项位置 定位函数：返回第i个表项在表中的位置 取第i个表项的值 用x修改第i个表项的内容 插入x在表中第i个表项之后，函数返回成功标志 删除表中第i个表项，通过x返回删除表项的值，函数返回成功标志 判断表空，空返回真，否则返回假 判断表满：满返回真，否则返回假 对当前的表排序*/#ifndef CIRCULAR_LIST#define CIRCULAR_LIST//假定每个表项的类型为Ttypedef int T;#define MAXLEN 100typedef enum { false = 0, true} BOOL;//循环链表结点的数据结构struct node;typedef struct node cnode;typedef struct node *to_node;typedef to_node c_list;typedef to_node pos;//创建一个空循环链表c_list create_list(void);//将链表置为空表BOOL set_empty(c_list l);//计算表长度int calc_length(c_list l);//返回附加头结点的地址pos head_addr(c_list l);//搜索函数：找x在表中的位置，返回表项位置pos search(c_list l, T x);//定位函数：返回第i个表项在表中的位置pos locate(c_list l, int i);//取第i个表项的值T get_val(c_list l, int i);//用x修改第i个表项的内容BOOL change_val(c_list l, int i, const T x);//插入x在表中第i个表项之后，函数返回成功标志BOOL insert_val(c_list l, int i, const T x);//删除表中第i个表项，通过x返回删除表项的值，函数返回成功标志BOOL delete_val(c_list l, int i, T *x);//判断表空，空返回真，否则返回假BOOL isempty(c_list l);//输出void output(c_list l);//对当前的表排序BOOL sort(c_list l);#endif /*filename:circular_list.c*/#include #include #include "circular_list.h"/*循环链表结点的数据结构*/struct node{ T val; struct node *next;};/*struct node;typedef struct node cnode;typedef struct node *to_node;typedef to_node c_list;typedef to_node pos;*///该循环链表带头节点，头节点的val域存储链表的长度/* -->{(头节点)|val|next|}->|val|next|->|val|next|->|val|next|->|val|next|-- | | ---------------------------------------------------------------*///创建一个空线性表c_list create_list(void){ c_list l = (c_list)malloc(sizeof(cnode)); l->next = l; l->val = 0; return l;}//将链表置为空表BOOL set_empty(c_list l){ pos tmp = l->next, ttemp; while(tmp!=l){ ttemp = tmp->next; free(tmp); tmp = ttemp; } l->next = l; l->val = 0; return true;}//计算表长度int calc_val(c_list l){ return l->val;}//返回附加头结点的地址pos head_addr(c_list l){ return l;}//搜索函数：找x在表中的位置，返回表项位置pos search(c_list l, T x){ int i = 1; pos tmp; tmp = l->next; while(tmp != l && tmp->val != x && i<=l->val){ tmp = tmp->next; i++; } if(i>l->val) return NULL; else return tmp;}//定位函数：返回第i个表项在表中的位置pos locate(c_list l, int i){ if(i<=l->val && i>0){ pos tmp; tmp = l; while(--i>=0){ tmp = tmp->next; if(tmp == l) break; } return tmp; } else { printf("can not access the %d'th element\n", i); return NULL; }}//取第i个表项的值T get_val(const c_list l, int i){ if(i<=l->val && i>0){ pos tmp; tmp = l; while(--i>=0){ tmp = tmp->next; if(tmp == l) break; } return tmp->val; } else { printf("can not access the %d'th element\n", i); return -1; }}//用x修改第i个表项的内容BOOL change_val(c_list l, int i, const T x){ if(i<=l->val && i>0){ pos tmp; tmp = l; while(--i>=0){ tmp = tmp->next; if(tmp == l) break; } tmp->val = x; return true; } else { return false; }}//插入x在表中第i个表项之后，函数返回成功标志BOOL insert_val(c_list l, int i, const T x){ if(i<=l->val && i>=0){ pos tmp; tmp = l; while(--i>=0){ tmp = tmp->next; if(tmp == l) break; } to_node t = (to_node)malloc(sizeof(cnode)); t->next = tmp->next; t->val = x; tmp->next = t; l->val++; return true; } else { return false; }}//删除表中第i个表项，通过x返回删除表项的值，函数返回成功标志BOOL delete_val(c_list l, int i, T *x){ if(i<=l->val && i>0){ i--; pos tmp; tmp = l; while(--i>=0){ tmp = tmp->next; if(tmp == l) break; } *x = (tmp->next)->val; tmp->next = (tmp->next)->next; l->val--; return true; } else { return false; }}//判断表空，空返回真，否则返回假BOOL isempty(const c_list l){ return (l->val == 0 ? true:false);}//输出void output(const c_list l){ pos tmp = NULL; int i = 1; tmp = l->next; while(tmp!=l){ printf("the %dth element is %d\n", i++, tmp->val); tmp = tmp->next; }}//对当前的表排序BOOL sort(const c_list l){ if(l->val < 2) { return true; } //冒泡排序 pos tmp, tmp1, tmp2; int i; tmp = l->next; while(tmp->next != l) { tmp1 = l->next; tmp2 = tmp1->next; while(tmp2 != l) { if(tmp1->val > tmp2->val) { i = tmp1->val; tmp1->val = tmp2->val; tmp2->val = i; } tmp1 = tmp1->next; tmp2 = tmp2->next; } tmp = tmp->next; } return true; //快速排序 //归并排序}