C语言实现带头节点的单向链表库

谁借莪１个温暖的怀抱￠ 2022-05-28 00:52 175阅读 0赞

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

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

SingleList.h

/******************************************************************************** * @文件名: NodeList.h * @文件描述: 该文件为带头结点的单链表库函数的头文件,包含链表节点类型的声明，功能函数的声明 * @编辑人: 王廷云 * @编辑日期: 2017-11-21 * @修改日期: 2018-2-1 ********************************************************************************/
     
    #ifndef _NODELIST_H_
    #define _NODELIST_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(const Node_t *h);
    
    /** * @函数名: searchList * @函数功能: 在链表中查找数据 * @参数: h:链表头结点的地址 data:待查找的数据 * @返回值: 查找成功返回数据所在节点的地址,失败返回NULL */
    Node_t *searchList(const 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 "NodeList.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->next;	// 先改变自己的指针
    	h->next = 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->next != NULL)
    	{ 
    		i = i->next;
    	}
    	
    	/* 第四步：把新节点插入到链表尾 */
    	i->next = 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 *fast = h->next; // 快指针 
    	Node_t *slow = h; 		// 慢指针 
    	while (fast != NULL)
    	{ 
    		if (fast->data >= value)
    		{ 
    			break;			// 找到直接跳出来，剩下的交由下一步来做
    		}
    		slow = fast;
    		fast = fast->next;
    	}
    	
    	/* 第四步：把新节点插入到链表的合适位置 */
    	newNode->next = slow->next;
    	slow->next = newNode;
    
    	return 0;				// 成功返回0
    }
    
    /** * @函数名: traverseList * @函数功能: 遍历链表所有数据 * @参数: h:链表头结点的地址 * @返回值: void */
    void traverseList(Node_t h)
    { 
    	Node_t *i;
    
    	/* 检查是否为空链表 */
    	if (h->next == NULL)
    	{ 
    		printf("Empty list!\n");
    		return;
    	}
    	
    	/* 遍历链表 */
    	for (i = h->next; i != NULL; i = i->next)
    	{ 
    		printf("%d ", i->data);
    	}
    	putchar('\n');
    }
    
    /** * @函数名: searchList * @函数功能: 在链表中查找数据,如果有多个匹配则返回第一个 * @参数: h:链表头结点的地址 data:待查找的数据 * @返回值: 查找成功返回数据所在节点的地址,失败返回NULL */
    Node_t *searchList(const Node_t *h, int value)
    { 
    	Node_t *i;
    
    	for (i = h->next; i != NULL; i = i->next)
    	{ 
    		if (i->data == value)
    		{ 
    			return i;
    		}
    	}
    
    	return NULL;
    }
    
    /** * @函数名: deleteListOne * @函数功能: 在链表中删除指定值的节点，如果有多个匹配只删除第一个 * @参数: h:链表头结点的地址 data:待删除的数据 * @返回值: void */
    void deleteListOne(Node_t *h, int value)
    { 
    	Node_t *slow = h;		// 慢指针
    	Node_t *fast = h->next;	// 快指针
    
    	for ( ; fast != NULL; slow = fast, fast = fast->next)
    	{ 
    		if (fast->data == value)
    		{ 
    			slow->next = fast->next;	// 通过摘掉节点
    			free(fast);					// 和释放节点空间达到删除目的
    			break;
    		}
    	}	
    }
    
    /** * @函数名: deleteList * @函数功能: 在链表中删除指定值的节点，如果有多个匹配则删除全部 * @参数: h:链表头结点的地址 data:待删除的数据 * @返回值: void */
    void deleteList(Node_t *h, int value)
    { 
    	Node_t *slow = h;		// 慢指针
    	Node_t *fast = h->next;	// 快指针
    	
    	for ( ; fast != NULL; slow = fast, fast = fast->next)
    	{ 
    		if (fast->data == value)
    		{ 
    			slow->next = fast->next;
    			free(fast);
    			fast = slow;	// 这样做的目的是避免再次使用释放掉的空间
    		}
    	}		
    }
    
    /** * @函数名: reverseList * @函数功能: 把链表所有节点的排列顺序逆转 * @参数: h:链表头结点的地址 * @返回值: void */
    void reverseList(Node_t *h)
    { 
    	Node_t *temp;
    	Node_t *next;
    
    	temp = h->next;		      // 保存第一个节点地址
    	h->next = NULL;		      // 打断链表
    	
    	while (temp != NULL)
    	{ 
    		next = temp->next;    // 保存下一个节点
    		
    		/* 使用头插入节点的方法达到逆转链表的目的 */	
    		temp->next = h->next;
    		h->next = temp;
    		
    		temp = next;          // 恢复下一个节点
    	}
    }