C语言实现带头指针的单向链表库

爱被打了一巴掌 2022-05-28 01:07 210阅读 0赞

该链表库比较简单，链表节点数据为整型，因为这只是为了模拟链表的原理，实际中一般不会使用单向链表来储存数据，链表头为一个指针。整个库包含两个文件：SingleList.h 和 SingleList.c

--------------------

SingleList.h

/******************************************************************************* * @文件名: NodeList.h * @文件描述: 该文件为带头指针的单链表库函数的头文件,包含链表节点类型的声明，功能函数的声明 * @编辑人: 王廷云 * @编辑日期: 2017-11-21 * @修改日期: 2018-2-1 ********************************************************************************/
     
    #ifndef _POINTERLIST_H_
    #define _POINTERLIST_H_
    
    /* 封装链表节点 */
    typedef struct node
    { 
    	int data;			// 节点数据指定为整型
    	struct node *next;	// 下一个节点
    } Node_t;
    
    /** * @函数名: appendListTop * @函数功能: 插入节点到链表头 * @参数: h:链表头指针的地址 data:待插入的数据 * @返回值：插入成功返回0，失败返回非零 */
    int appendListTop(Node_t **h, int vlude);
    
    /** * @函数名: appendListTail * @函数功能: 插入节点到链表尾 * @参数: h:链表头指针的地址 data:待插入的数据 * @返回值：插入成功返回0，失败返回非零 */
    int appendListTail(Node_t **h, int value);
    
    /** * @函数名: sortInsert * @函数功能: 按从小到大的排列顺序把节点插入到链表中 * @参数: h:链表头指针的地址 data:待插入的数据 * @返回值：插入成功返回0，失败返回非零 */
    int sortInsert(Node_t **h, int value);
    
    /** * @函数名: traverseList * @函数功能: 遍历链表所有数据 * @参数: h:链表头指针 * @返回值: void */
    void traverseList(Node_t *h);
    
    /** * @函数名: searchList * @函数功能: 在链表中查找数据 * @参数: h:链表头指针 data:待查找的数据 * @返回值: 查找成功返回数据所在节点的地址,失败返回NULL */
    Node_t *searchList(Node_t *h, int value);
    
    /** * @函数名: deleteListOne * @函数功能: 在链表中删除指定值的节点，如果有多个匹配只删除第一个 * @参数: h:链表头指针的地址 data:待删除的数据 * @返回值: void */
    void deleteListOne(Node_t **h, int value);
    
    /** * @函数名: deleteList * @函数功能: 在链表中删除指定值的节点，如果有多个匹配则删除全部 * @参数: h:链表头指针的地址 data:待删除的数据 * @返回值: void */
    void deleteList(Node_t **h, int value);
    
    /** * @函数名: reverseList * @函数功能: 把链表所有节点的排列顺序逆转 * @参数: h:链表头结点的地址 * @返回值: void */
    void reverseList(Node_t **h);
    
    #endif //_NODELIST_H

--------------------

SingleList.c

/******************************************************* * @文件名: NodeList.c * @文件描述: 该文件为带头指针的单链表库函数中所有功能函数的实现 * @编辑人: 王廷云 * @编辑日期: 2017-11-21 * @修改日期: 2018-2-1 *********************************************************/
    
    #include <stdlib.h>
    #include <stdio.h>
    #include "pointerList.h"
    
    /** * @函数名: appendListTop * @函数功能: 插入节点到链表头 * @参数: h:链表头指针的地址 data:待插入的数据 * @返回值：插入成功返回0，失败返回非零 */
    int appendListTop(Node_t **h, int value)
    { 
    	Node_t *newNode;
    
    	/* 第一步：分配新节点空间 */
    	newNode = malloc(sizeof(Node_t));
    	if (newNode == NULL)
    	{ 
    		return -1;
    	}
    
    	/* 第二步：赋值给新节点 */
    	newNode->data = value;
    
    	/* 第三步：插入新节点到链表头 */
    	newNode->next = *h;		// 先改变自己的指针
    	*h = newNode;			// 再改变头节点的指针，顺序不能调
    
    	return 0;				// 成功返回0
    }
    
    /** * @函数名: appendListTail * @函数功能: 插入节点到链表尾 * @参数: h:链表头指针的地址 data:待插入的数据 * @返回值：插入成功返回0，失败返回非零 */
    int appendListTail(Node_t **h, int value)
    { 
    	Node_t *newNode;
    
    	/* 第一步：分配新节点空间 */
    	newNode = malloc(sizeof(Node_t));
    	if (newNode == NULL)
    	{ 
    		return -1;
    	}
    
    	/* 第二步：赋值给新节点 */
    	newNode->data = value;
    
    	/* 第三步：找到链表尾 */
    	Node_t **i = h;
    	while (*i != NULL)
    	{ 
    		i = &(*i)->next;
    	}
    	
    	/* 第四步：把新节点插入到链表尾 */
    	*i = newNode;			// 尾节点指向新节点
    	newNode->next = NULL;	// 新节点指向NULL，作为链表尾
    
    	return 0;				// 成功返回0
    }
    
    /** * @函数名: sortInsert * @函数功能: 按从小到大的排列顺序把节点插入到链表中 * @参数: h:链表头指针的地址 data:待插入的数据 * @返回值：插入成功返回0，失败返回非零 */
    int sortInsert(Node_t **h, int value)
    { 
    	Node_t *newNode;
    
    	/* 第一步：分配新节点空间 */
    	newNode = malloc(sizeof(Node_t));
    	if (newNode == NULL)
    	{ 
    		return -1;
    	}
    	
    	/* 第二步：赋值给新节点 */
    	newNode->data = value;
    
    	/* 第三步：找到合适的插入点 */
    	Node_t **i = h; 
    	while (*i != NULL)
    	{ 
    		if ((*i)->data >= value)
    		{ 
    			break;
    		}
    		
    		i = &(*i)->next;	// 下一个节点
    	}
    	
    	/* 第四步：把新节点插入到链表的合适位置 */
    	newNode->next = *i;
    	*i = newNode; 
    
    	return 0;				// 成功返回0
    }
    
    /** * @函数名: traverseList * @函数功能: 遍历链表所有数据 * @参数: h:链表头指针 * @返回值: void */
    void traverseList(Node_t *h)
    { 
    	/* 检查是否为空链表 */
    	if (h == NULL)
    	{ 
    		printf("Empty list!\n");
    		return;
    	}
    		
    	/* h本身也是一个局部指针变量 */
    	while (h != NULL)
    	{ 
    		printf("%d ", h->data);
    		h = h->next;
    	}
    	putchar('\n');
    }
    
    /** * @函数名: searchList * @函数功能: 在链表中查找数据,如果有多个匹配则返回第一个 * @参数: h:链表头指针 data:待查找的数据 * @返回值: 查找成功返回数据所在节点的地址,失败返回NULL */
    Node_t *searchList(Node_t *h, int value)
    { 
    	for ( ; h != NULL; h = h->next)
    	{ 
    		if (h->data == value)
    		{ 
    			return h;	// 成功返回节点地址
    		}
    	}
    
    	return NULL;		// 失败返回NULL
    }
    
    /** * @函数名: deleteListOne * @函数功能: 在链表中删除指定值的节点，如果有多个匹配只删除第一个 * @参数: h:链表头指针的地址 data:待删除的数据 * @返回值: void */
    void deleteListOne(Node_t **h, int value)
    { 
    	Node_t **slow = h;	// 慢指针
    	Node_t *fast;		// 快指针
    
    	while (*slow != NULL)
    	{ 
    		fast = *slow;	
    		if (fast->data == value)
    		{ 
    			*slow = fast->next;	// 通过摘掉节点
    			free(fast);			// 和释放节点空间达到删除目的
    			break;
    		}
    		slow = &(fast->next);
    	}	
    }
    
    /** * @函数名: deleteList * @函数功能: 在链表中删除指定值的节点，如果有多个匹配则删除全部 * @参数: h:链表头指针的地址 data:待删除的数据 * @返回值: void */
    void deleteList(Node_t **h, int value)
    { 
    	Node_t **slow = h;	// 慢指针
    	Node_t *fast;		// 快指针
    
    	while (*slow != NULL)
    	{ 
    		fast = *slow;
    		if (fast->data == value)
    		{ 
    			*slow = fast->next;
    			free(fast);
    			continue;	// 由于释放了fast指向的空间，所以不能往下走了
    		}		
    		slow = &(fast->next);		
    	}		
    }
    
    /** * @函数名: reverseList * @函数功能: 把链表所有节点的排列顺序逆转 * @参数: h:链表头结点的地址 * @返回值: void */
    void reverseList(Node_t **h)
    { 
    	Node_t *temp;
    	Node_t *next;
    
    	temp = *h;				// 指向第一个节点
    	*h = NULL;				// 打断链表
    	while (temp != NULL)
    	{ 		
    		next = temp->next;	// 保存下一个节点
    		
    		/* 头插入链表方法达到逆转目的 */
    		temp->next = *h;
    		*h = temp;
    		
    		temp = next;		// 恢复下一个节点
    	}
    }