1 /** 2 * @brief 线性表的链式表示与实现 3 * 4 * @author amur-leopard 5 * 6 * @date 2014/06/01 7 */ 8 #include <stdio.h> 9 #include <stdlib.h> 10 11 //-----------------预定义常量和类型------------------- 12 #define OK 1 13 #define ERROR 0 14 #define OVERFLOW -1 15 16 typedef int status; // 函数类型,其值是函数结果状态代码 17 18 19 //--------------线性表的单链表存储结构---------------- 20 struct node 21 { 22 int data; 23 struct node *next; 24 }; 25 26 typedef struct node node; 27 typedef struct node *link_list; 28 29 30 //------------------基本操作的声明-------------------- 31 status init(link_list &list); // 初始化线性表 32 status insert(link_list &list, int i, int e); // 向线性表中某个位置前插入新元素 33 status list_delete(link_list &list, int i, int &e); // 删除线性表中某个位置的元素 34 status print(link_list list); // 打印线性表 35 36 37 //------------------基本操作的实现-------------------- 38 /** 39 * @brief 初始化线性表 40 * 41 * @param 待初始化的线性表 42 * 43 * @return 函数状态 44 */ 45 status init(link_list &list) 46 { 47 list = (node *)malloc(sizeof(node)); 48 if(!list) 49 { 50 exit(OVERFLOW); 51 } 52 list->next = NULL; 53 return OK; 54 } 55 56 /** 57 * @brief 向线性表中某个位置前插入新元素 58 * 59 * @param list 待插入的线性表(list != NULL) 60 * @param i 插入位置(1<=i<=list_length+1) 61 * @param e 待插入的元素 62 */ 63 status insert(link_list &list, int i, int e) 64 { 65 int j; // 用于计数 66 node *p; // 用于遍历并最终指向插入结点的前驱 67 node *n; // 用于存储新结点 68 if(!list) 69 { 70 return ERROR; 71 } 72 if(i < 1) 73 { 74 return ERROR; 75 } 76 for(p = list, j = 0; p && j < i - 1; p = p->next, ++j) // 寻找插入结点的前驱 77 { 78 } 79 if(!p) // i > list_length + 1; 80 { 81 return ERROR; 82 } 83 n = (node *)malloc(sizeof(node)); 84 if(!n) 85 { 86 exit(OVERFLOW); 87 } 88 n->data = e; 89 n->next = p->next; 90 p->next = n; 91 return OK; 92 } 93 94 /** 95 * @brief 删除线性表中某个位置的元素 96 * 97 * @param list 待删除元素所在的线性表(list != NULL) 98 * @param i 删除位置(1<=i<=list_length) 99 * @param e 用于返回待删除元素 100 * 101 * @return 函数状态 102 */ 103 status list_delete(link_list &list, int i, int &e) 104 { 105 int j; //用于计数 106 node *p; // 用于遍历并最终指向待删除结点的前驱 107 node *temp; // 用于指向待删除结点 108 if(!list) 109 { 110 return ERROR; 111 } 112 if(i < 1) 113 { 114 return ERROR; 115 } 116 for(p = list, j = 0; p->next && j < i - 1; p = p->next, ++j) // 寻找删除结点的前驱 117 { 118 } 119 if(!p->next) // i > list_length 120 { 121 return ERROR; 122 } 123 temp = p->next; 124 p->next = temp->next; 125 e = temp->data; 126 free(temp); 127 return OK; 128 } 129 130 /** 131 * @brief 打印线性表 132 * 133 * @param 待打印的线性表 134 * 135 * @return 函数状态 136 */ 137 status print(link_list list) 138 { 139 node *p; // 用于遍历 140 if(!list) 141 { 142 return ERROR; 143 } 144 p = list->next; 145 if(p) 146 { 147 printf("%d", p->data); 148 p = p->next; 149 while(p) 150 { 151 printf(" %d", p->data); 152 p = p->next; 153 } 154 printf("\n"); 155 } 156 return OK; 157 } 158 159 160 //----------------------测试-------------------------- 161 /** 162 * @brief 测试函数 163 */ 164 void main() 165 { 166 int e; link_list list = NULL; init(list); 167 168 if(OK == print(list)) printf("print succeed!\n"); 169 170 if(OK == insert(list, 1, 11)) printf("insert (1, 11) succeed!\n"); print(list); 171 if(OK == insert(list, 2, 22)) printf("insert (2, 22) succeed!\n"); print(list); 172 if(OK == insert(list, 1, 33)) printf("insert (1, 33) succeed!\n"); print(list); 173 if(OK == insert(list, 2, 44)) printf("insert (2, 44) succeed!\n"); print(list); 174 if(OK == insert(list, 3, 55)) printf("insert (3, 55) succeed!\n"); print(list); 175 176 if(OK == list_delete(list, 5, e)) printf("delete (5, %d) succeed!\n", e); print(list); 177 if(OK == list_delete(list, 2, e)) printf("delete (2, %d) succeed!\n", e); print(list); 178 if(OK == list_delete(list, 1, e)) printf("delete (1, %d) succeed!\n", e); print(list); 179 if(OK == list_delete(list, 1, e)) printf("delete (1, %d) succeed!\n", e); print(list); 180 if(OK == list_delete(list, 1, e)) printf("delete (1, %d) succeed!\n", e); print(list); 181 182 if(OK == print(list)) printf("print succeed!\n"); 183 184 system("pause"); 185 }
原文:http://www.cnblogs.com/amur-leopard/p/link_list.html