c语言——数据结构【链表：单向链表】

2024-12-17 08:14:50

上篇→快速掌握C语言——数据结构【创建顺序表】多文件编译-****博客

一、链表

二、单向链表

2.1 概念

2.2 单向链表的组成

2.3 单向链表节点的结构体原型

//类型重定义,表示存放的数据类型
typedef int DataType;

//定义节点的结构体类型
typedef struct node
{
    union
    {
        int len; //头结点的数据域，表示链表的长度
        DataType data;//普通节点的数据域
    };
    struct node *next; //节点的指针域
}linkList,*linkListPtr;

2.4 单向链表的相关操作（功能函数的封装）

1>创建

#include "test.h"

//创建链表==创建头结点
linklistPtr create()
{
	//在堆区申请节点大小空间，将地址放回给主程序使用
	linklistPtr H=(linklistPtr)malloc (sizeof(linklist));
	if (NULL==H)
	{
		printf("创建失败\n");
		return NULL;
	}
//申请成功，将头节点的数据域为0，指针域NULL
	H->len=0;
	H->next=NULL;

	printf("创建成功\n");
	return H;

}

2>判空

//判空
int  empty(linklistPtr H)
{
	if (NULL==H)
	{
		printf("判空失败");
		return -1;
	}
  return H->len==0;

}

3>申请节点，封装数据

//申请节点封装数据
linklistPtr create_node(int e)
{
	linklistPtr p=(linklistPtr)malloc (sizeof(linklist));
	if(NULL==p)
	{
		printf("申请失败");
		return NULL;
	}
	p->data=e;
	p->next=NULL;
	return p;
}

4>头插

//头插
int   head_add(linklistPtr H,int e)
{
	if (NULL==H)
	{
		printf("插入失败");
		return 0;

	}

//申请节点封装数据
	linklistPtr p=create_node(e);
//头插
	p->next =H->next;
	H->next =p;
//插入成功长度自增
	H->len++;
	return 1;
}

5>遍历

void show (linklistPtr H)
{
	
		if (NULL==H ||empty(H))
		{
			printf("遍历失败");
			return ;
		}
//定义一个指针指向头结点
		linklistPtr p =H;
		for (int i=0;i<H->len;i++)
		{
			p=p->next;
			printf("%d ",p->data);
		}
putchar(10);
}

6>尾插

//尾插
int tail_add(linklistPtr H,int e)
{
	if (NULL== H)
	{
		printf("插入失败");
		return 0;
	}
//申请节点封装数据
	linklistPtr p=create_node(e);

	linklistPtr q=H;
	while(q->next !=NULL)
	{
		 q= q->next;
	}
//尾插
 	 q->next =p;

//插入成功长度自增
	 H->len++;
	 return 1;
}

7>任意位置插入

//任意位置插入
int insert(linklistPtr H,int index , int e)
{
	//链表是否合法
	//插入位置是否合理
	if (NULL==H || index <1 ||index>H->len+1)
	{
		printf("插入失败\n");
		return 0;
	}
//申请节点封装数据 
	linklistPtr p=create_node(e);

//定义一个指针指向要插入位置的前一个节点
	linklistPtr q=H;

	for (int i=0;i<index-1;i++)
	{
		q=q->next ;
	}
	
//插入（头插）
	p->next =q->next;
	q->next =p;

//插入成功长度自增 
	H->len++;
	return 1;
}

8>头删

//头删
int head_del(linklistPtr H)
{
	//判空 
	//判断合法性
	if (NULL==H ||empty(H))
	{
		printf(" 删除失败\n");	
		return 0;
	}
	//定义一个指针指向普通节点的第一个节点
	linklistPtr q= H->next;

//删除 （孤立）
	H->next=q->next ;

//释放空间
	free(q);
	q=NULL;

//删除成功 链表长度自减
	H->len--;
	return 1;
}

9>尾删

//尾删
int tail_del(linklistPtr H)
{
	if(NULL==H ||empty(H))
	{
		printf("删除失败 ");
		return 0;
	}
//定义一个指针，指向 最后一个节点的 前一个节点
	linklistPtr q=H;

	for (int i=0;i<H->len-1;i++)
	{
		q=q->next;
	}
//删除
	free(q->next);
	q->next=NULL;
//删除成功 长度自减
	H->len--;
	return 1;
}

10>任意位置删除

//任意位置删除
int index_del(linklistPtr H ,int index)
{
	if (NULL==H ||empty(H)||index<0||index>H->len)
	{
		printf("删除失败");
		return 0;
	}

//定义指针，指向要删除的节点
	linklistPtr p=NULL;

//定义一个指针，指向要删除的前一个节点
	linklistPtr q=H;

	for (int i=0;i<index-1;i++)
	{
		q=q->next;
	}

	if (p=NULL)
	{
		printf("删除失败");
		return  0;
	}

//保存删除节点的位置
	p=q->next;

	q->next=p->next;

//删除节点的内存
	free (p);
//删除成功 长度自减
	H->len--;
	return 1;
}

11>按位置修改

//按位置修改
int index_change(linklistPtr H,int index ,int e)
{
	if (NULL==H||empty(H))
	{
		printf("修改失败");
		return 0;
	}
	
//定义一个指针，指向要修改的前一个节点
	linklistPtr q=H;
//定义指针，指向要修改的节点
	linklistPtr p=NULL;

	for (int i=0;i<index;i++)
	{
		q=q->next;
	}

//保存修改节点的位置
	p=q->next;

	//修改值
	p->data=e;

	return 1;
	
}

12>按值查找返回地址

//按值查找返回
linklistPtr  index_find(linklistPtr H,int e)
{
	if (NULL==H||empty(H))
	{
		printf("查找失败");
		return NULL;
	}
 //定义一个指针指向头结点 
	linklistPtr p=H->next;
	while(p!=NULL)
	{

		if (p->data==e)
		{
			printf("%p\n",p);
			return p;
			
		}
		p=p->next;
	}
	//没找到
	printf("没找到目标值\n");
	return NULL;
	
}

14>销毁

//销毁
void my_free(linklistPtr *H)
{
	if (NULL==*H)
	{
		printf("销毁失败");
		return;
	}
	free (*H);

	H=NULL;
	printf("销毁成功");
}

三、完整代码

1>头文件test.h

#ifndef __TEST_H__
#define __TEST_H__

#include <stdio.h>
#include <stdlib.h>

//定义节点的结构体类型
typedef struct node
{
	union
	{
		int len;//头结点的数据域，表示链表的长度
		int data;//普通节点的数据域
	};
    struct node *next;//节点的指针域
}linklist,*linklistPtr;

//创建链表==创建头结点
linklistPtr create();

int  empty(linklistPtr H);

linklistPtr create_node(int e);

int   head_add(linklistPtr How,int e);

void show (linklistPtr H);

int tail_add(linklistPtr H,int e);

int insert(linklistPtr H,int index , int e);

//头删
int head_del(linklistPtr H);


//尾删
int tail_del(linklistPtr H);

int index_del(linklistPtr H ,int index);
//按位置修改
int index_change(linklistPtr H,int index ,int e);
//按值查找返回
linklistPtr  index_find(linklistPtr H,int e);
#endif

2>源文件test.c

#include "test.h"

//创建链表==创建头结点
linklistPtr create()
{
	//在堆区申请节点大小空间，将地址放回给主程序使用
	linklistPtr H=(linklistPtr)malloc (sizeof(linklist));
	if (NULL==H)
	{
		printf("创建失败\n");
		return NULL;
	}
//申请成功，将头节点的数据域为0，指针域NULL
	H->len=0;
	H->next=NULL;

	printf("创建成功\n");
	return H;

}
//判空
int  empty(linklistPtr H)
{
	if (NULL==H)
	{
		printf("判空失败");
		return -1;
	}
  return H->len==0;

}
//申请节点封装数据
linklistPtr create_node(int e)
{
	linklistPtr p=(linklistPtr)malloc (sizeof(linklist));
	if(NULL==p)
	{
		printf("申请失败");
		return NULL;
	}
	p->data=e;
	p->next=NULL;
	return p;
}




//头插
int   head_add(linklistPtr H,int e)
{
	if (NULL==H)
	{
		printf("插入失败");
		return 0;

	}

//申请节点封装数据
	linklistPtr p=create_node(e);
//头插
	p->next =H->next;
	H->next =p;
//插入成功长度自增
	H->len++;
	return 1;
}

void show (linklistPtr H)
{
	
		if (NULL==H ||empty(H))
		{
			printf("遍历失败");
			return ;
		}
//定义一个指针指向头结点
		linklistPtr p =H;
		for (int i=0;i<H->len;i++)
		{
			p=p->next;
			printf("%d ",p->data);
		}
putchar(10);
}
//尾插
int tail_add(linklistPtr H,int e)
{
	if (NULL== H)
	{
		printf("插入失败");
		return 0;
	}
//申请节点封装数据
	linklistPtr p=create_node(e);

	linklistPtr q=H;
	while(q->next !=NULL)
	{
		 q= q->next;

	}
//尾插
 	 q->next =p;

//插入成功长度自增
	 H->len++;

	 return 1;
}
//任意位置插入
int insert(linklistPtr H,int index , int e)
{
	//链表是否合法
	//插入位置是否合理
	if (NULL==H || index <1 ||index>H->len+1)
	{
		printf("插入失败\n");
		return 0;
	}
//申请节点封装数据 
	linklistPtr p=create_node(e);

//定义一个指针指向要插入位置的前一个节点
	linklistPtr q=H;

	for (int i=0;i<index-1;i++)
	{
		q=q->next ;
	}
	
//插入（头插）
	p->next =q->next;
	q->next =p;

//插入成功长度自增 
	H->len++;
	return 1;
}


//头删
int head_del(linklistPtr H)
{
	//判空 
	//判断合法性
	if (NULL==H ||empty(H))
	{
		printf(" 删除失败\n");	
		return 0;
	}
	//定义一个指针指向普通节点的第一个节点
	linklistPtr q= H->next;

//删除 （孤立）
	H->next=q->next ;

//释放空间
	free(q);
	q=NULL;

//删除成功 链表长度自减
	H->len--;
	return 1;
}
//尾删
int tail_del(linklistPtr H)
{
	if(NULL==H ||empty(H))
	{
		printf("删除失败 ");
		return 0;
	}
//定义一个指针，指向 最后一个节点的 前一个节点
	linklistPtr q=H;

	for (int i=0;i<H->len-1;i++)
	{
		q=q->next;
	}
//删除
	free(q->next);
	q->next=NULL;
//删除成功 长度自减
	H->len--;
	return 1;
}

//任意位置删除
int index_del(linklistPtr H ,int index)
{
	if (NULL==H ||empty(H)||index<0||index>H->len)
	{
		printf("删除失败");
		return 0;
	}

//定义指针，指向要删除的节点
	linklistPtr p=NULL;

//定义一个指针，指向要删除的前一个节点
	linklistPtr q=H;

	for (int i=0;i<index-1;i++)
	{
		q=q->next;
	}

	if (p=NULL)
	{
		printf("删除失败");
		return  0;
	}

//保存删除节点的位置
	p=q->next;

	q->next=p->next;

//删除节点的内存
	free (p);
//删除成功 长度自减
	H->len--;
	return 1;
}

//按位置修改
int index_change(linklistPtr H,int index ,int e)
{
	if (NULL==H||empty(H))
	{
		printf("修改失败");
		return 0;
	}
	
//定义一个指针，指向要修改的前一个节点
	linklistPtr q=H;
//定义指针，指向要修改的节点
	linklistPtr p=NULL;

	for (int i=0;i<index;i++)
	{
		q=q->next;
	}

//保存修改节点的位置
	p=q->next;

	//修改值
	p->data=e;

	return 1;
	
}
//按值查找返回
linklistPtr  index_find(linklistPtr H,int e)
{
	if (NULL==H||empty(H))
	{
		printf("查找失败");
		return NULL;
	}
 //定义一个指针指向头结点 
	linklistPtr p=H->next;
	while(p!=NULL)
	{

		if (p->data==e)
		{
			printf("%p\n",p);
			return p;
			
		}
		p=p->next;
	}
	//没找到
	printf("没找到目标值\n");
	return NULL;
	
}

//反转 
 

//销毁
void my_free(linklistPtr *H)
{
	if (NULL==*H)
	{
		printf("销毁失败");
		return;
	}
	free (*H);

	H=NULL;
	printf("销毁成功");
}

3>测试文件main.c

#include "test.h"

int main(int argc, const char *argv[])
{
	//创建
	linklistPtr H=create();

//头插 
	head_add(H,10);
	head_add(H,20);
	head_add(H,30);
	head_add(H,40);
	head_add(H,50);
	
    show(H);
//尾插 
	tail_add(H,11);
	tail_add(H,22);
	tail_add(H,33);
	tail_add(H,44);
	tail_add(H,55);
	show(H);
	
    
//任意位置插入
	insert(H,3,888);

	show (H);	

//头删  	
	head_del(H);
	show(H);

	head_del(H);
	show(H);

	tail_del(H);
	show(H);


	index_del(H,3);
	show(H);


	index_change (H,5,666);
	show(H);

	index_find (H,666);
	
	return 0;
}

码农公寓

上篇→快速掌握C语言——数据结构【创建顺序表】多文件编译-****博客

一、链表

二、单向链表

2.1 概念

2.2 单向链表的组成

2.3 单向链表节点的结构体原型

2.4 单向链表的相关操作 （功能函数的封装）

1>创建

2>判空

3>申请节点，封装数据

4>头插

5>遍历

6>尾插

7>任意位置插入

8>头删

9>尾删

10>任意位置删除

11>按位置修改

12>按值查找返回地址

14>销毁

三、完整代码

1>头文件test.h

2>源文件test.c

3>测试文件main.c

相关文章

2.4 单向链表的相关操作（功能函数的封装）