当前位置： 首页 > article >正文

数据结构------单向链表。

article 2025/2/21 6:00:04

一.实现单向链表的头插，头删，尾插，尾删，按位置插，按位置删，按位置修改，按元素查找，按元素修改，按元素删除，单链表的逆置，查找倒数第几个元素，释放内存。

头文件:head.h

 #ifndef __HEAD_H__                                                         
 #define __HEAD_H__                                                         
 #include <stdio.h>                                                         
 #include <string.h>                                                        
 #include <stdlib.h>                                                        
 typedef int datatype;                                                      
                                                                            
 enum passble{success,false=-1};                                            
                                                                            
 typedef struct Node                                                        
 {                                                                          
     datatype data;                                                         
     struct Node* next;                                                     
 }*Linklist;                                                                
                                                                            
 Linklist Create_Node();                                                    
                                                                            
 Linklist head_insert(Linklist head,datatype element);                      
                                                                            
 void show(Linklist head);                                                  
                                                                            
 Linklist head_delete(Linklist head);                                       
                                                                            
 Linklist tail_insert(Linklist head,datatype element);                      
                                                                            
 Linklist tail_delete(Linklist head);                                       
                                                                            
 int getlen(Linklist head);                                                 
                                                                            
 Linklist pos_insert(Linklist head,int pos,datatype element);               
                                                                            
 Linklist delete_index(Linklist head,int pos);                              
                                                                            
 Linklist change_index(Linklist head,int pos,datatype element);             
                                                                            
 int find_index(Linklist head,int pos);                                     
                                                                            
 int value(Linklist head,datatype element);                                 
                                                                            
 Linklist change_value(Linklist head,datatype element,datatype data1);      
                                                                            
 Linklist delete_value(Linklist head,datatype element);                     
                                                                            
 int find_value(Linklist head,int pos);                                     
                                                                            
 Linklist swap(Linklist head);                                              
                                                                            
 void free_list(Linklist head);                                             
 #endif

测试文件（test.c）

#include"head.h"

//创建节点
Linklist Create_Node()
{
	Linklist s=(Linklist)malloc(sizeof(struct Node));
	if(NULL==s)
		return NULL;
	s->data=0;
	s->next=NULL;
	return s;
}
//头插
Linklist head_insert(Linklist head,datatype element)
{
	Linklist s=Create_Node();
	s->data=element;
	if(NULL==head)
		head=s;
	else
	{
		s->next=head;
		head=s;
	}
	return head;
}

//头删
Linklist head_delete(Linklist head)
{
	if(NULL==head)
		return NULL;
	Linklist p=head;
	head=head->next;
	free(p);
	p=NULL;
	return head;
}

//尾插
Linklist tail_insert(Linklist head,datatype element)
{
	Linklist s=Create_Node();
	s->data=element;
	if(NULL==head)
	{
		head=s;
	}
	{
		Linklist p=head;
		while(p->next)
		{
			p=p->next;
		}
		p->next=s;
	}
	return head;
}

//尾删
Linklist tail_delete(Linklist head)
{
	if(NULL==head)
		return NULL;
	else if(head->next==NULL)
	{
		free(head);
		head=NULL;
	}
	else
	{
		Linklist p=head;
		while(p->next->next!=NULL)
		{
			p=p->next;
		}
		free(p->next);
		p->next=NULL;
	}
	return head;
}

//计算链表的长度
int getlen(Linklist head)
{
	int count=0;
	Linklist p=head;
	while(p)
	{
		count++;
		p=p->next;
	}
	return count;
}

//按位置插入值
Linklist pos_insert(Linklist head,int pos,datatype element)
{
	Linklist s=Create_Node();
	s->data=element;
	Linklist p=head;
	if(pos<1||pos>getlen(head)+1)
	return head;
	if(pos==1)
	{
		head=head_insert(head,element);
		return head;
	}
	for(int i=1;i<pos-1;i++)
	{
		p=p->next;
	}
	s->next=p->next;
	p->next=s;
	return head;
}

//按位置删除
Linklist delete_index(Linklist head,int pos)
{
	if(pos<1||pos>getlen(head))
		return head;
	if(pos==1)
	{
		head=head_delete(head);
		return head;
	}
	Linklist p=head;
	for(int i=1;i<pos-1;i++)
	{
		p=p->next;
	}
	Linklist del=p->next;
	p->next=del->next;
	free(del);
	del=NULL;
	return head;
}

//按位置修改
Linklist change_index(Linklist head,int pos,datatype element)
{
	//判断修改的位置是否合法
	if(pos<1||pos>getlen(head))
	{
		return head;
	}
	Linklist p=head;
	for(int i=1;i<pos;i++)
	{
		p=p->next;
	}
	p->data=element;
	return head;

}

//按位置查找返回值
int find_index(Linklist head,int pos)
{
	if(NULL==head)
	return 0;
	if(pos<1||pos>getlen(head))
	{
		return 1 ;
	}
	Linklist p=head;
	for(int i=1;i<pos;i++)
	{
		p=p->next;
	}
	return p->data;
}

//按值查找返回位置
int value(Linklist head,datatype element)
{
	if(NULL==head)
	return 0;
	Linklist p=head;
	for(int i=1;i<=getlen(head);i++)
	{
		if(p->data==element)
		{
			return i;
		}
		p=p->next;
	}
	return 0;
}

//按值修改
Linklist change_value(Linklist head,datatype element,datatype data1)
{
	
	int j=value(head,element);
	head=change_index(head,j,data1);
	return head;
}

//按值删除
Linklist delete_value(Linklist head,datatype element)
{
	int j=value(head,element);
	head=delete_index(head,j);
	return head;
}

//查找倒数第几个元素的值
int find_value(Linklist head,int pos)
{
	if(NULL==head)
		return 0;
	if(pos<1||pos>getlen(head))
		return 1;
	Linklist p=head;
	Linklist q=head;
	for(int i=1;i<pos;i++)
	{
		p=p->next;
	}
	while(p->next)
	{
		p=p->next;
		q=q->next;
	}
	return q->data;
}

//单链表的逆置
Linklist swap(Linklist head)
{
	if(NULL==head)
		return head;
	if(getlen(head)==1)
		return head;
	Linklist p=head->next;
	head->next=NULL;
	while(p)
	{
		Linklist s=p;
		p=p->next;
		s->next=head;
		head=s;
	}
	return head;
}

//释放内存
void free_list(Linklist head)
{
	Linklist s=head;
	while(s)
	{
		s=s->next;
		head=head_delete(head);
	}
	return ;
}

//输出
void show(Linklist head)
{
	if(NULL==head)
	{
		return;
	}
	Linklist p=head;
	while(p!=NULL)
	{
		printf("%d\t",p->data);
		p=p->next;
	}
	putchar(10);
}

主文件（main.c）

#include"head.h"
int main(int argc, const char *argv[])
{
                             	//头插
	Linklist head=NULL;
	int n;
	datatype element;
	printf("请输入头插要插入几个数据：");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("请输入头插插入的数据：");
		scanf("%d",&element);
	head=head_insert(head,element);
	}
	head=head_delete(head);      //头删
	show(head);

								//尾插
	printf("请输入尾插要插入几个数据：");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("请输入尾插插入的数据：");
		scanf("%d",&element);
	head=tail_insert(head,element);
	}
	head=tail_delete(head);       //尾删
	show(head);

	int pos;                     //任意位置插
	printf("请输入要插入数据的位置：");
	scanf("%d",&pos);
	printf("请输入插入的数据：");
	scanf("%d",&element);
	head=pos_insert(head,pos,element);
	show(head);

/*								//任意位置删
	printf("请输入要删除数据的位置：");
	scanf("%d",&pos);
	head=delete_index(head,pos);
	show(head);

								//任意位置修改
	printf("请输入要修改数据的位置：");
	scanf("%d",&pos);
	printf("请输入修改后的值：");
	scanf("%d",&element);
	head=change_index(head,pos,element);
	show(head);

								//按位置查找
	printf("请输入要查找的位置：");
	scanf("%d",&pos);
	datatype data=find_index(head,pos);
	if(data==0)
	{
		printf("链表为空\n");
	}
	else if(data==1)
	{
		printf("输入不合理\n");
	}
	else{
	printf("查找位置的值为：%d\n",data);
	}

                               //按值查找返回位置
	printf("请输入要查找的值：");
	scanf("%d",&element);
	pos=value(head,element);
	if(pos==0)
	{
		printf("没有这个元素\n");
	}
	else{
	printf("要查找的值的位置为：%d\n",pos);
	}

	//按值修改
	datatype data1;//修改后的值
	printf("请输入要修改的元素：");
	scanf("%d",&element);
	printf("请输入修改后的值：");
	scanf("%d",&data1);
	head=change_value(head,element,data1);
	show(head);
*/
				//按值删除
	printf("请输入要删除的元素：");
	scanf("%d",&element);
	head=delete_value(head,element);
	show(head);

				//查找倒数第几个元素的值
	printf("请输入倒数的位置：");
	scanf("%d",&pos);
	int k=find_value(head,pos);
	if(k==0)
	{
		printf("链表不存在");
	}
	else if(k==1)
	{
		printf("输入的位置不合理");
	}
	else
	{
		printf("%d\n",k);
	}

				//单链表的逆置
	head=swap(head);
	printf("链表逆置后的结果为：\n");
	show(head);

			//释放内存
	free_list(head);
	return 0;
}

运行结果：


http://www.kler.cn/a/549461.html

相关文章：

  • 苍穹外卖day4 redis相关简单知识 店铺营业状态设置
  • Linux 基础IO——重定向和缓冲区
  • 大疆无人机需要的kml文件如何制作kml导出（大疆KML文件）
  • Instagram与小红书的自动化运营
  • Vite入门指南
  • github用户名密码登陆失效了
  • Mac上搭建宝塔环境并部署PHP项目
  • Ubuntu 连接 air pods
  • ios中常见的设计原则和设计模式
  • ARINC 429详解
  • CSS Grid 网格布局，以及 Flexbox 弹性盒布局模型，它们的适用场景是什么？
  • VS Code User和System版区别【推荐使用System版本】and VSCode+Keil协同开发之Keil Assistant
  • 【ISO 14229-1:2023 UDS诊断（会话控制0x10服务）测试用例CAPL代码全解析③】
  • ffmpeg-cli-wrapper操作ffmpeg的工具
  • Anaconda +Jupyter Notebook安装（2025最新版）
  • 问卷数据分析|SPSS实操之量表描述性统计
  • 服务器硬件知识--------linux系统初识and安装
  • 探索Zephyr在汽车领域的应用潜力与挑战
  • 【LLM】13：大模型算法面试题库
  • kubectl exec 实现的原理