【数据结构】普通单链表的实现

链表

链表是数据结构中最基本的一种数据结构，是一种线性表，但是不同与数组的是，并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。

如图所示，链表结点常由两部分构成：数据域用于存储数据，指针域用于指向下一个结点。

链表的优点：        1.资源允许的情况下，规模可以不断的增长或减小。        2.删除和添加效率高，O（1）。         链表的缺点：         链表的遍历过程效率比较低。

list.h 头文件，接口声明

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TRUE (1) #define FALSE (0) typedef unsigned char Bool; typedef struct List_Node{ int data; //数据域（定义结构体时，建议先定义数据域） struct List_Node *next; //指针域 }List_Node; typedef List_Node *List_head; List_head init_list(void); //初始化链表 void destroy_list(List_head *head); //销毁链表 Bool push_front(List_head head, int value); //链表头插 Bool push_back(List_head head, int value); //链表尾插 Bool pop_front(List_head head); //删除头部结点 Bool pop_back(List_head head); //删除尾部节点 Bool delete_list_node(List_head head, List_Node *Node); //删除指定节点 Bool find_value_node(List_head head, int value, List_Node **Node); //找到对应值的地址 void sort_list_ascend(List_head head); void sort_list_descend(List_head head); //升序降序 void show_list(List_head head); //打印全部链表 int list_length(List_head head);

list.c 接口函数实现

#include "list.h" static List_Node *create_node(void); //创建结点 static void Swap(void *a, void *b, int length); //交换结点数据域 List_head init_list(void) { List_head head = NULL; head = create_node(); return head; } static List_Node *create_node(void) { List_Node *Node = NULL; Node = (List_Node *)malloc(sizeof(List_Node)); memset(Node,0,sizeof(List_Node)); return Node; } void destroy_list(List_head *head) { List_Node *p = NULL; List_Node *q = NULL; if(head == NULL || *head == NULL) { return; } p = *head; while(p != NULL) { q = p; p = p->next; free(q); } *head = NULL; } Bool push_front(List_head head, int value) { List_Node *Node; if(head == NULL) { return FALSE; } Node = create_node(); Node->data = value; Node->next = head->next; head->next = Node; return TRUE; } Bool push_back(List_head head, int value) { List_Node *Node; List_Node *p; if(head == NULL) { return FALSE; } Node = create_node(); Node->data = value; p = head; while(p->next != NULL) { p = p->next; } p->next = Node; return TRUE; } Bool pop_front(List_head head) { List_Node *Node = NULL; if(head == NULL || head->next == NULL) { return FALSE; } Node = head->next; head->next = head->next->next; free(Node); return TRUE; } Bool pop_back(List_head head) { List_Node *Node = NULL; if(head == NULL || head->next == NULL) { return FALSE; } Node = head; while(Node->next->next != NULL) { Node = Node->next; } free(Node->next); Node->next = NULL; return TRUE; } Bool delete_list_node(List_head head, List_Node *Node) { List_Node *p = NULL; if(head == NULL || head->next == NULL || Node == NULL) { return FALSE; } p = head; while(p->next != Node) { p = p->next; if(p == NULL) { break; } } if(p == NULL) { return FALSE; } p->next = Node->next; free(Node); return TRUE; } Bool find_value_node(List_head head, int value, List_Node **Node) { List_Node *p = NULL; if(head == NULL || head->next == NULL || Node == NULL) { return FALSE; } p = head->next; while(p != NULL) { if(p->data == value) { *Node = p; return TRUE; } p = p->next; } return FALSE; } #define POINTER_SIZE (sizeof(void *)) #define data_size(Node) (((char *)((Node) + 1) - (POINTER_SIZE)) - ((char *)(Node))) //计算数据域内存地址长度 static void Swap(void *a, void *b, int length) //内存拷贝函数实现数据域的交换 { void *temp = malloc(length); memcpy(temp, a, length); memcpy(a, b, length); memcpy(b, temp, length); free(temp); } void sort_list_ascend(List_head head) { List_Node *p = NULL; List_Node *q = NULL; if(head == NULL || head->next == NULL || head->next->next == NULL) { return; } for(p = head->next; p != NULL; p = p->next) { for(q = p->next; q != NULL; q = q->next) { if(p->data > q->data) { Swap(p, q, data_size(p)); } } } } void show_list(List_head head) { List_Node *p; if(head == NULL) { return; } p = head->next; while(p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } int list_length(List_head head) { List_Node *Node; int length; if(head == NULL) { return 0; } Node = head->next; while(Node != NULL) { length++; Node = Node->next; } return length; }

main.c 功能测试

#include "list.h" int main(int argc, char const* argv[]) { List_Node *list = NULL; list = init_list(); push_back(list, 5); push_back(list, 4); push_back(list, 3); push_back(list, 2); push_back(list, 1); push_back(list, 0); show_list(list); sort_list_ascend(list); show_list(list); int length = list_length(list); printf("%d\n", length); destroy_list(&list); return 0; }