单向链表的C实现

单向链表：

#include<sys/types.h> #include<sys/stat.h> #include<fcntl.h> #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct node { struct node* next; int index; int data; }node_t; typedef struct list { int len; node_t* p_head; }list_t; node_t *create_node(int index, int vData) { node_t *pNode = NULL; pNode = (node_t *)malloc(sizeof(node_t)); if (NULL == pNode) return NULL; pNode->index = index; pNode->data = vData; pNode->next = NULL; return pNode; } void destory_node(node_t * p_node) { if(p_node) free(p_node); return; } list_t *create_list(void) { list_t *p_list = NULL; p_list = malloc(sizeof(list_t)); if (NULL == p_list) return NULL; p_list->len = 0; p_list->p_head = NULL; return p_list; } void destory_list(list_t * p_list) //从头部开始删 { node_t *cur_node = NULL; node_t *temp_node = NULL; if(p_list) { cur_node = p_list->p_head; while(cur_node) { temp_node = cur_node; cur_node = cur_node->next; destory_node(temp_node); } free(p_list); } return; } int add_node_tail(list_t *p_list, node_t *p_node) //链尾添加节点 { node_t *p_cur_node = NULL; if(NULL == p_list || NULL == p_node) return -1; p_cur_node = p_list->p_head; if(NULL == p_cur_node) { p_list->p_head = p_node; goto node_out; } while(p_cur_node->next) { p_cur_node = p_cur_node->next; } p_cur_node->next = p_node; node_out: p_list->len++; return 1; } int del_node_index(list_t *p_list, int index) //删除节点 { node_t *p_cur_node = NULL; node_t *p_temp_node = NULL; node_t *pre_node = NULL; if(NULL == p_list) return 0; p_cur_node = p_list->p_head; if(NULL == p_cur_node) { return 0; } if (index == p_cur_node->index) { p_temp_node = p_cur_node->next; destory_node(p_cur_node); p_list->p_head = p_temp_node; p_list->len--; return 1; } else { while(NULL != p_cur_node && index != p_cur_node->index) { pre_node = p_cur_node; p_cur_node = p_cur_node->next; } if (NULL == p_cur_node) return 0; p_temp_node = p_cur_node->next; destory_node(p_cur_node); pre_node->next = p_temp_node; p_list->len--; return 1; } return 0; } int insert_node_ordered(list_t *p_list, node_t *p_node) //插入节点，有序链表 { node_t *p_cur_node = NULL; node_t *pre_node = NULL; if(NULL == p_list || NULL == p_node) return -1; p_cur_node = p_list->p_head; if(NULL == p_cur_node) { p_list->p_head = p_node; p_list->len++; return 1; } if (p_node->index < p_cur_node->index) { p_list->p_head = p_node; p_node->next = p_cur_node; p_list->len++; return 1; } while (NULL != p_cur_node && p_node->index >=p_cur_node->index) { if (p_node->index==p_cur_node->index)//相等时更新 { p_cur_node->data = p_node->data; return 1; } pre_node = p_cur_node; p_cur_node = p_cur_node->next; } pre_node->next = p_node; p_node->next = p_cur_node; p_list->len++; return 1; } node_t *get_node(list_t *p_list, int index) { node_t *curNode = NULL; if (p_list) { curNode = p_list->p_head; if(NULL == curNode) return NULL; while(curNode) { if (index == curNode->index) { break; } curNode = curNode->next; } return curNode; } return NULL; } /* 归并排序 （算法交换链表节点，时间复杂度O（nlogn）,不考虑递归栈空间的话空间复杂度是O（1）） 首先用快慢指针的方法找到链表中间节点，然后递归的对两个子链表排序， 把两个排好序的子链表合并成一条有序的链表。归并排序应该算是链表排序最佳的选择了， 保证了最好和最坏时间复杂度都是nlogn， 而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1) */ node_t* listMergeSort(node_t* head) //传入需要归并排序的链表的头指针 { int i=0; //一个元素就返回 if (NULL == head || head->next == NULL) return head; //使用 slow-fast方法找到链表的中间位置，注意这里写的链表的头节点是非空的，即头节点也是存贮数据的 node_t* fast = head->next; // fast指向第2个节点 node_t* slow = head; // slow指向第1个节点 while (fast != NULL&&fast->next != NULL) { fast = fast->next->next; //fast每次走两步 slow = slow->next; //slow每次走一步，这样slow就会到链表中点 } //slow最后指向有n个元素的链表的第n/2个元素。如一共6个元素，slow指向第3个，一共5个元素，slow指向第2个。 node_t* left = head; node_t* right = slow->next; slow->next = NULL; //但是实际上将链表截断，左边的部分从第1个开始，右边的要从第4个(共6个)或者第3个(共5个)开始，所以有right=slow->next; //假设上面截断的左右两个子链表调用归并排序后变成了排好序(new，新)的“新”左右两个链表，然后开始归并 printf("left head = %d_%d, right head = %d_%d\n", left->index, left->data, right->index, right->data); printf("left\n"); node_t* newLeft = listMergeSort(left); printf("right\n"); node_t* newRight = listMergeSort(right); printf("newLeft head = %d_%d, newRight head = %d_%d\n", newLeft->index, newLeft->data, newRight->index, newRight->data); node_t * newList ; //注意指针tail才是后面进行操作的指针，newList是为了保存起点 node_t * tail ; //printf ("i = %d\n", i++);//一直为0，说明递归时变量生存期只在函数内部 if (newLeft->data < newRight->data) { newList = newLeft; newLeft = newLeft->next; } else { newList = newRight; newRight = newRight->next; } tail=newList; tail->next = NULL; //以上代码是向newList的第一个节点存入左右两个链表的头节点的较小的元素 while (newLeft != NULL|| newRight != NULL) { if (newLeft == NULL) //左边全部接完了 { tail->next = newRight; //右边就直接整条链表接上去 newRight = NULL; } else if (newRight == NULL) { //同理，右边接完了 tail->next = newLeft; //左边就直接整条链表接上去，复杂度为O（1） newLeft = NULL; } else if (newLeft->data < newRight->data) { tail->next = newLeft; //上面接一整个链表，这里就是接链表中单个元素的操作 newLeft = newLeft->next; tail = tail->next; tail->next = NULL; } else { tail->next = newRight; newRight = newRight->next; tail = tail->next; tail->next = NULL; } } return newList; //返回新接好的List } void youxulist() { int index = 0; int value = 0; node_t *pNode = NULL; node_t *curNode = NULL; node_t *p_Node = NULL; list_t *plist = create_list(); node_t *p_temp_node = NULL; for(index = 0; index < 10; index++) { value = index * 2; pNode = create_node(index, value); if (NULL == pNode) return; printf("pNode index = %2d, value = %2d; ", pNode->index,pNode->data); insert_node_ordered(plist, pNode);//按从小到大顺序添加节点 printf("plist len = %2d\n", plist->len); } for(index = 100; index > 0; index --) { index--; value = index * 3; pNode = create_node(index, value); if (NULL == pNode) return; printf("pNode index = %2d, value = %2d; ", pNode->index,pNode->data); insert_node_ordered(plist, pNode);//按从小到大顺序添加节点 printf("plist len = %2d\n", plist->len); } for(index = 0; index < 101; index++) { p_temp_node = get_node(plist, index); if (p_temp_node) printf("p_temp_node index = %2d, data =%2d\n", p_temp_node->index, p_temp_node->data); } for(index = 100; index >= 0; index --) { if (del_node_index(plist, index)) printf("plist len = %2d\n", plist->len); } p_Node = plist->p_head; //按顺序打印节点 while(p_Node) { printf("p_Node index = %2d, value = %2d\n", p_Node->index,p_Node->data); p_Node = p_Node->next; } destory_list(plist); } void wuxulist() { int index = 0; int value = 0; node_t *pNode = NULL; node_t *curNode = NULL; node_t *p_Node = NULL; list_t *plist = create_list(); for(index = 0; index < 9; index++) { value = 9 - index; pNode = create_node(index, value); if (NULL == pNode) return; printf("pNode index = %2d, value = %2d; ", pNode->index,pNode->data); add_node_tail(plist, pNode); //依次添加节点 printf("plist len = %2d\n", plist->len); } /* for(index = 100; index > 0; index --) { index--; value = 1000 - index * 3; pNode = create_node(index, value); if (NULL == pNode) return; printf("pNode index = %2d, value = %2d; ", pNode->index,pNode->data); add_node_tail(plist, pNode); printf("plist len = %2d\n", plist->len); } */ p_Node = plist->p_head; //按顺序打印节点 while(p_Node) { printf("p_Node index = %2d, value = %2d\n", p_Node->index,p_Node->data); p_Node = p_Node->next; } printf("******************************************************\n"); plist->p_head = listMergeSort(plist->p_head); printf("******************************************************\n"); p_Node = plist->p_head; //按顺序打印节点 while(p_Node) { printf("p_Node index = %2d, value = %2d\n", p_Node->index,p_Node->data); p_Node = p_Node->next; } destory_list(plist); } void main() { //youxulist(); wuxulist(); return; } /*结构体定义*/ #define ERROR -1 #define OK 0 typedef int DataType typedef struct Node { DataType data; struct Node* next; }Node,*PNODE; /*初始化链表*/ void initList(PNODE *pHead) { if (NULL == p_Head) return; *pHead = NULL; } PNODE newNode(DataType vData) { PNODE newNode = NULL; newNode = (PNODE)malloc(sizeof(Node)); if (NULL == newNode) { return ERROR; } else { newNode->data = vData; newNode->next = NULL; } return newNode; } void popBack(PNODE *pHead)//尾删 { if (NULL == pHead) return; if (NULL == *pHead) return; if (NULL == (*pHead)->next)//只有头结点，删除头结点，释放内存 { PNODE tempnode = *pHead; free(tempnode); tempnode = NULL; *pHead = NULL; } else { PNODE curNode = *pHead; while(curNode->next->next) { curNode = curNode->next; } curNode->next = NULL; } } void pushBack(PNODE *pHead, DataType vData)//尾插 { if (NULL == pHead) return; if (NULL == *pHead) { *pHead = newNode(vData); } else { PNODE curNode = *pHead; while(curNode->next->next) { curNode = curNode->next; } curNode->next = newNode(vData); } } void popFront(PNODE *pHead)//头删 { if (NULL == pHead) return; if (NULL == *pHead) { return; } else if(NULL == (*pHead)->next) { *pHead = NULL; } else { PNODE preNode = *pHead; pHead = preNode->next; free(preNode); preNode = NULL; } } void pushFront(PNODE *pHead, DataType vData)//头插 { PNODE preNode = NULL; PNODE tempNode = NULL; if (NULL == pHead) return; tempNode = newNode(vData); preNode = *pHead; tempNode->next = preNode; *pHead = tempNode; } void insertList(PNODE pos, DataType vData)//data 后插入节点pos { PNODE preNode = NULL; PNODE tempNode = NULL; if (NULL == pos) return; preNode = pos; tempNode = newNode(vData); tempNode->next = preNode->next; preNode->next = tempNode; }

参考：http://www.cnblogs.com/wft1990/p/6718623.html