使用C语言对单向链表的操作

2024-09-05 02:58
文章标签 语言 使用 链表 操作 单向

本文主要是介绍使用C语言对单向链表的操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ 

<span style="font-size:24px;">//以下所有代码都经过实际上机测试，如果有不合适的地方，请指正，谢谢</span>
<span style="font-size:24px;">
</span>
<span style="font-size:24px;">#include <stdio.h>
#include <stdlib.h>
#include <mem.h>
typedef struct ListNode{int value;struct ListNode *pnext;}ListNode;
/* 1.初始化线性表，即置单链表的表头指针为空 */
void initLIST(ListNode **pnode) //此处如果传入listnode* 类型的参数，则在初始化的时候就会//使pnode 的副本的值置为NULL，而不是传入值的本身；
{*pnode = NULL;printf("链表初始化成功");
}
/* 2.创建线性表，此函数输入负数终止读取数据*/
ListNode *createList(ListNode *head) //传入头结点指针，返回创建完成后的头结点指针
{ListNode *p1,*p2;p1 = p2 = (ListNode*)malloc(sizeof(ListNode));//向系统申请一个新节点if(p1 == NULL ||p2 == NULL){printf("内存申请失败！");return 0;}memset(p1,0,sizeof(ListNode)); //把新节点的内容置为0printf("请输入需要存储节点的值,输入负数停止：");scanf("%d",&p1->value);p1 ->pnext = NULL;while(p1->value > 0){if(head == NULL) //如果表头为空，则接入表头{head = p1;}else //不为空则接入表尾{p2->pnext = p1;}p2 = p1;p1 = (ListNode *)malloc(sizeof(ListNode));if(p1 == NULL){printf("内存申请失败！");return 0;}memset(p1,0,sizeof(ListNode));printf("请输入需要存储节点的值,输入负数停止：");scanf("%d",&p1->value);p1->pnext = NULL;}printf("链表创建成功！");return head;
}
/*3.从头到尾打印一个链表，返回值是为了判断是否打印成功,也可以不添加*/
int printList(ListNode *head)
{int num = 0;if(head == NULL){printf("链表为空！");return 0;}while(head != NULL){printf("%d ",head->value);head = head->pnext;num++;}printf("共打印了%d个数字\n",num);return num;
}
/*4.在链表末尾插入一个节点*///如果需要在新的链表中插入一个节点，插入点就是头结点，需要修改节点的指针//所以传入的值必须为指向指针的指针//不能为头结点的副本
int addNode_Last(ListNode **head,int value) //返回值代表插入的个数
{ListNode *Node = NULL;ListNode *pNode;Node = (ListNode *)malloc(sizeof(ListNode));if(Node == NULL){printf("内存申请失败！");return 0;}Node->value = value;Node->pnext = NULL; //把新节点的下一个指针置为空if(*head == NULL) //判断头结点是否为空，如果为空，则插入点为头结点{*head = Node;}else{pNode = *head;          //找到尾节点，并添加新节点while(pNode->pnext != NULL){pNode = pNode->pnext;}pNode->pnext = Node;}return 1;
}
/*5.在链表中找到某个节点并删除*/
int deleteNode(ListNode **head,int key)//返回值表示删除节点的个数
{if(head == NULL && *head == NULL)return -1;ListNode *beDeleted = NULL;//记录要删除的节点if((*head)->value == key)  //如果要删除的节点为头结点{beDeleted = *head;*head = (*head)->pnext;free(beDeleted);       //释放删除节点的内存}else{ListNode *pNode = *head;while((pNode->pnext) != NULL && (pNode->pnext)->value != key){pNode = pNode->pnext;}if(pNode->pnext == NULL){printf("没有找到该节点！");return 0;}if(pNode->pnext->value == key){beDeleted = pNode->pnext;pNode->pnext = beDeleted->pnext;free(beDeleted);printf("节点已经删除！");}}return 1;
}
/*6.反向遍历链表（基于递归）*/
//（1.）递归本质上也是栈，但是如果使用栈，在C语言中必须自己构建，
// 所以使用递归，但本功能理论上使用显式栈更加安全，因为递归深度太大会导致栈溢出
//（2.）本功能还有一个解法，那就是把所有节点指针反转再顺序遍历，但一般不允许这样做
void PrintList_revers(ListNode *head)
{if(head != NULL){if(head->pnext != NULL){PrintList_revers(head->pnext);}printf("%d ",head->value);}
}
/*7.反向遍历链表（基于递归）*/
//（1.）递归本质上也是栈，但是如果使用栈，在C语言中必须自己构建，
// 所以使用递归，但本功能理论上使用显式栈更加安全，因为递归深度太大会导致栈溢出
//（2.）本功能还有一个解法，那就是把所有节点指针反转再顺序遍历，但一般不允许这样做，（请参照<span style="font-family: Arial, Helvetica, sans-serif;">第十个操作</span><span style="font-family: Arial, Helvetica, sans-serif;">）</span>
void PrintList_revers(ListNode *head)
{
if(head != NULL)
{
if(head->pnext != NULL)
{
PrintList_revers(head->pnext);
}
printf("%d ",head->value);
}
}
/*
8.在o(1)的时间内删除一个节点，前提是调用者确定这个节点在链表中，
否则如果需要遍历判断的话，那样时间效率就是o(n)了，
这个算法的主要思想就是如果得到了需要删除的节点，
那么直接使用下一个节点覆盖需要删除的节点，把下一个节点删除，
这样的话就不需要遍历查找了，
如果要删除的节点为尾节点，那么还是需要从头开始遍历链表，查找前一个节点
因为如果需要删除的链表只有一个节点，既是是头节点，又是尾节点，
那么就需要修改头结点的值，所以在传入头节点时是传入一个指向指针的指针。
*/
void deleteNode_o1(ListNode **listHead, ListNode *toBeDeleted)
{
if(listHead == NULL || toBeDeleted == NULL)
return;
if(toBeDeleted ->pnext != NULL) //如果传入的节点不是尾节点
{
ListNode *pNext = toBeDeleted->pnext;
toBeDeleted->value = pNext->value;
toBeDeleted->pnext = pNext->pnext;
free(pNext);
pNext = NULL;
}
else if(*listHead == toBeDeleted)//如果链表只有一个节点，
{                                //删除的节点既是头结点，也是尾节点
free(*listHead);
*listHead = NULL;
toBeDeleted = NULL;
}
else //如果链表有多个节点，但是传入的节点是尾节点
{
ListNode *preNode = *listHead;
while(preNode->pnext != toBeDeleted)
{
preNode = preNode->pnext;
}
preNode->pnext = NULL;
free(toBeDeleted);
toBeDeleted = NULL;
}
}
/*9.求链表中倒数第K个节点*/
/*
思路：
定义两个指针，第一个指针先走K-1步，然后第二个指针开始一起走，
当第一个指针走到尾节点的时候，第二个指针刚好是倒数第K个。
*/
ListNode *FindKthToTail(ListNode *listHead, unsigned int k)
{
if(listHead == NULL || k == 0)
return;
ListNode *pAhead = listHead;
ListNode *pBehind = listHead;
int i;
for(i = 0; i < k-1; i++)
{
if(pAhead->pnext != NULL)
{
pAhead = pAhead->pnext;
}
else
return NULL;
}
while(pAhead->pnext != NULL)
{
pAhead = pAhead->pnext;
pBehind = pBehind->pnext;
}
return pBehind;
}
/*10.反转一个链表，并返回头节点,使用修改指针的方法*/
/*
思路：
定义三个指针，分别指向当前节点，前一个节点和下一个节点
然后进行循环
*/
ListNode *ReversList(ListNode *listHead)
{
ListNode *preNode = NULL;
ListNode *headNode = listHead;
ListNode *nextNode = NULL;
while (headNode != NULL)
{
nextNode = headNode->pnext;
headNode->pnext = preNode;
preNode = headNode;
if(nextNode == NULL)
break;
headNode = nextNode;
}
return headNode;
}
/*11.合并两个排序的链表，并返回新链表的头结点*/
ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
{
if(pHead1 == NULL)
return pHead2;
if(pHead2 == NULL)
return pHead1;
ListNode *newListHead = NULL;
if(pHead1->value < pHead2->value)
{
newListHead = pHead1;
newListHead->pnext = Merge(pHead1->pnext,pHead2);
}
else
{
newListHead = pHead2;
newListHead->pnext = Merge(pHead1,pHead2->pnext);
}
return newListHead;
}


int main()
{ListNode *ListHead = NULL;initLIST(&ListHead);ListHead = createList(ListHead);printList(ListHead);/*addNode_Last(&ListHead,21);printList(ListHead);deleteNode(&ListHead,21);printList(ListHead);*/PrintList_revers(ListHead);return 0;
}
</span>

这篇关于使用C语言对单向链表的操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1137781。

相关文章

基于Python实现多语言朗读与单词选择测验

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、
阅读更多...
如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件

如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件

《如何使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件》本文介绍了如何使用Docker部署FTP服务器和Nginx,并通过HTTP访问FTP中的文件,通过将FTP数据目录挂载到N... 目录docker部署FTP和Nginx并通过HTTP访问FTP里的文件1. 部署 FTP 服务器 (
阅读更多...
MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、
阅读更多...
Python中配置文件的全面解析与使用

Python中配置文件的全面解析与使用

《Python中配置文件的全面解析与使用》在Python开发中,配置文件扮演着举足轻重的角色,它们允许开发者在不修改代码的情况下调整应用程序的行为,下面我们就来看看常见Python配置文件格式的使用吧... 目录一、INI配置文件二、YAML配置文件三、jsON配置文件四、TOML配置文件五、XML配置文件
阅读更多...
Go使用pprof进行CPU,内存和阻塞情况分析

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手：启用 pprof3. CPU Profiling：分析 C
阅读更多...
MySQL InnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据

MySQL InnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据

《MySQLInnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据》mysql的ibdata文件被误删、被恶意修改,没有从库和备份数据的情况下的数据恢复,不能保证数据库所有表数据... 参考：mysql Innodb表空间卸载、迁移、装载的使用方法注意！此方法只适用于innodb_fi
阅读更多...
Python中conda虚拟环境创建及使用小结

Python中conda虚拟环境创建及使用小结

《Python中conda虚拟环境创建及使用小结》本文主要介绍了Python中conda虚拟环境创建及使用小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录0.前言1.Miniconda安装2.conda本地基本操作3.创建conda虚拟环境4.激活c
阅读更多...
Spring中@Lazy注解的使用技巧与实例解析

Spring中@Lazy注解的使用技巧与实例解析

《Spring中@Lazy注解的使用技巧与实例解析》@Lazy注解在Spring框架中用于延迟Bean的初始化,优化应用启动性能,它不仅适用于@Bean和@Component,还可以用于注入点,通过将... 目录一、@Lazy注解的作用（一）延迟Bean的初始化（二）与@Autowired结合使用二、实例解
阅读更多...
SpringBoot使用Jasypt对YML文件配置内容加密的方法(数据库密码加密)

SpringBoot使用Jasypt对YML文件配置内容加密的方法(数据库密码加密)

《SpringBoot使用Jasypt对YML文件配置内容加密的方法(数据库密码加密)》本文介绍了如何在SpringBoot项目中使用Jasypt对application.yml文件中的敏感信息（如数... 目录SpringBoot使用Jasypt对YML文件配置内容进行加密（例：数据库密码加密）前言一、J
阅读更多...
Spring Boot 中正确地在异步线程中使用 HttpServletRequest的方法

Spring Boot 中正确地在异步线程中使用 HttpServletRequest的方法

《SpringBoot中正确地在异步线程中使用HttpServletRequest的方法》文章讨论了在SpringBoot中如何在异步线程中正确使用HttpServletRequest的问题,... 目录前言一、问题的来源：为什么异步线程中无法访问 HttpServletRequest？1. 请求上下文与线
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2