欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-21 14:23:10
...

该链表库比较简单,链表节点数据为整型,因为这只是为了模拟链表的原理,实际中一般不会使用单向链表来储存数据,链表头为一个指针。整个库包含两个文件: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;		// 恢复下一个节点
	}
}