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; // 恢复下一个节点
}
}
上一篇: CentOS7安装telnet服务
下一篇: 链表---C实现(带头节点)