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

day21 链表

article 2024/12/2 1:45:46

顺序表的优缺点

1.优点：将数据元素进行连续存储，能够实现随机访问（可以通过下标快速定位）

                进行查找和修改时效效率较高

2.不足：对于插入和删除操作，需要一定大量的元素，效率较低

                对于少量元素而言，申请空间比较方便，对于大量的数据而言，想要申请连续的空间不易实现

                致命缺点：元素存储有上限，当顺序表长度达到容器最大容量后，不能添加元素

链表引入

1.为了解决顺序表的不足，引入链表

2.链表：链式存储的线性表

        链式存储：逻辑上相邻的元素物理内存不一定相邻

        线性表：数据元素之间存在一对一的关系

3.原理：将每个数据元素，独立封装成一个数据的存储单位（节点），多个节点通过成员指针进行连接在一起，串成一个链表

struct Node//节点类型
{
    datatype data;//存储数据元素的数据域
    struct Node *next;//指向下一个节点的指针域
};
struct header
{
    int len;//记录节点个数
    struct Node *next;//指向节点的指针
};

struct Node
{
    union//共用体
    {
        int len;//头节点数据域表示链表长度
        datatype data;//普通节点数据域

    }；
        struct Node *next;

};

链表相关概念

1.链表分类

        单向链表：只能从头节点或第一个阶段出发，单向访问其后继节点的链表称为单向链表

        双向链表：从任意一个节点出发，都能访问其前驱和后继节点（第一个节点没有前驱，最后一个节点没有后继）

        循环链表：从任意一个节点出发，都能访问所有节点

概念

        节点：由数据域和指针域组成的链表的基本单元称为节点

        数据域：存储数据元素的空间

        指针域：用于记录下一个节点的指针变量

        头指针：定义一个节点类型的指针变量，指向链表的第一一个节点

        头节点：虚设的一个节点，其数据用于表示链表的长度（也可以弃置），指针域指向第一个节点

节点类型

1.既可以完成头节点的定义，也可以实现普通节点的定义

2.节点中的数据域是一个共用体变量，头节点使用len，普通节点使用data

typedef char datatype;   //数据元素类型
//定义节点类型
typedef struct Node
{
    union
    {
        int len;    //头结点数据域
        datatype data;  //普通结点数据域
    };

    struct Node *next;   //指针域
}Node, *Node_ptr;

单向链表的操作

创建单向链表

1.原理：只需要创建一个头节点并初始化即可

2.功能：在堆区申请一个头节点的空间，并对其进行初始化操作

        参数：无

        返回值：成功申请返回头节点的地址，失败返回NULL

#include"linklist.h"

//创建链表
Node_ptr list_create()
{
    //在堆区申请一个头结点的空间
    Node_ptr L = (Node_ptr)malloc(sizeof(Node));
    if(NULL == L)
    {
        printf("链表创建失败\n");
        return NULL;
    }

    //程序执行至此，一个头结点就申请成功
    //有了头结点就有了一条链表
    //初始化操作
    L->len = 0;       //表示链表长度为0
    L->next = NULL;   //防止野指针

    printf("链表创建成功\n");
    return L;
}

链表判空

//如果链表为空，返回1，非空返回0
int list_empty(Node_ptr L)
{
    //判断逻辑
    if(NULL == L)
    {
        printf("链表不合法\n");
        return -1;
    }

    return L->nexti==NULL ? 1: 0;
}

申请节点封装数据

//定义申请结点封装数据函数
static Node_ptr node_apply(datatype e)
{
    //在堆区申请一个结点的空间
    Node_ptr p = (Node_ptr)malloc(sizeof(Node));
    if(NULL == p)
    {
        printf("结点申请失败\n");
        return NULL;
    }

    //将数据封装进结点的数据域
    p->data = e;
    p->next = NULL;        //防止野指针

    return p;     //将封装好的结点地址返回
}

单向链表头插

功能：将数据封装成节点，插入到链表的第一个位置上

        参数;链表头节点起始地址，要插入的元素

        返回值：成功返回0，失败返回-1

头插过后的数据元素是逆序的

//单向链表头插
int list_insert_head(Node_ptr L, datatype e)
{
    //判断逻辑
    if(NULL == L)
    {
        printf("链表不合法\n");
        return -1;
    }

    //申请结点封装数据
    Node_ptr p = node_apply(e);
    if(NULL==p)
    {
        return -1;
    }
    //程序执行至此，表示节点申请成功，并且e已经封装进结点

    //头插逻辑
    p->next = L->next;
    L->next = p;

    //表长变化
    L->len++;
    printf("插入成功\n");
    return 0;
}

通过位置查找并返回该节点的地址

1.功能：通过给定的位置，查找后返回该位置上的节点的起始地址

2.参数：链表头节点，要查找的位置

        返回值：成功返回该节点的地址，失败返回NULL

2.注意：由于链表不是连续存储的，所以不能直接通过指针偏移得到后面字节的地址

        只能通过每个节点的指针域依次向后查询每个节点


//单向链表的按位置查找返回结点
Node_ptr list_find_node(Node_ptr L, int pos)
{
    //判断逻辑
    if(NULL==L || pos<0 || pos>L->len)
    {
        printf("查找失败\n");
        return NULL;
    }

    //查找逻辑
    Node_ptr q = L;       //定义遍历指针从头结点出发
    for(int i=0; i<pos; i++)
    {
        //q++;             //向后偏移一个结点大小
        q = q->next;      //将指针偏移到下一个结点位置
    }
    
    //返回节点
    return q;
}

单向链表的遍历

//单向链表的遍历
void list_show(Node_ptr L)
{
    //判断逻辑
    if(list_empty(L))
    {
        printf("遍历失败\n");
        return ;
    }

    /*遍历所有结点
    printf("链表中的元素分别是：");
    for(int i=1; i<L->len; i++)
    {
        Node_ptr p = list_find_node(L, i); //找到第i个结点
        printf("%c\t", p->data);
    }*/

    printf("链表中的元素分别是：");
    Node_ptr q = L->next;        //定义遍历指针从第一个结点出发
    while(q)
    {
        //当前结点不为空，输出数据域
        printf("%c\t", q->data);

        q = q->next;    //继续遍历下一个结点
    }
    printf("\n");
}

单向链表的任意位置插入

1.功能：在链表中给定位置插入一个新数据

        参数：链表头节点，要插入的数据

        返回值：成功返回0，失败返回-1

2.注意事项

        1.必须找到要插入位置的前一个节点

        2.将前面那个节点当作头节点进行头插

//单向链表任意位置插入
int list_insert_pos(Node_ptr L, int pos, datatype e)
{
    //判断逻辑
    if(NULL==L || pos<1 || pos>L->len+1)
    {
        printf("插入失败\n");
        return -1;
    }

    //找到要插入位置的前一个结点
    Node_ptr q = list_find_node(L, pos-1);

    //申请结点封装数据
    Node_ptr p = node_apply(e);
    if(NULL==p)
    {
        return -1;
    }

    //插入逻辑
    p->next = q->next;
    q->next = p;

    
    //表长变化
    L->len++;

    printf("插入成功\n");
    return 0;
}

单向链表的头删操作

1.功能：每次删除链表的第一个节点

        参数：头节点起始地址

        返回值：成功删除返回0，失败返回-1

2.注意事项

1.不能删除第一个节点（头节点），否则会段链

//单向链表的头删
int list_delete_head(Node_ptr L)
{
    //判断逻辑
    if(NULL==L || list_empty(L))
    {
        printf("删除失败\n");
        return -1;
    }

    //删除逻辑
    Node_ptr p = L->next;    //标记第一个节点
    L->next = p->next;    //L->next = L->next->next
    free(p);               //释放
    p = NULL;

    //表长变化
    L->len--;

    printf("删除成功\n");
    return 0;
}

任意位置删除

1.功能：在单向链表中删除指定位置的节点

         参数：链表头节点、要删除的位置

        返回值：成功返回0，失败返回-1

2.注意：必须要找到要删除的节点的前驱节点，然后进行头删操作

//单向链表任意位置删除
int list_delete_pos(Node_ptr L, int pos)
{
    //判断逻辑
    if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
    {
        printf("删除失败\n");
        return -1;
    }

    //删除逻辑
    Node_ptr q = list_find_node(L, pos-1);  //找到前驱
    Node_ptr p = q->next;     //标记要删除的节点
    q->next = p->next;        //孤立要删除的节点
    free(p);                  //释放要删除的节点
    p = NULL;

    printf("删除成功\n");
    //表长变化
    L->len--;                  
    return 0;
}

单向链表按位置进行修改

1.功能：在给定的单向链表中，将指定位置上的数据修改

        参数：单向链表头结点地址、要修改节点的位置、要修改的值

        返回值：成功返回0，失败返回-1

//单向链表按位置进行修改
int list_update_pos(Node_ptr L, int pos, datatype e)
{
    //判断逻辑
    if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
    {
        printf("修改失败\n");
        return -1;
    }

    //查找指定节点
    Node_ptr p = list_find_node(L, pos);

    //进行修改
    p->data = e;

    printf("修改成功\n");
    return 0;
    
}

单向链表翻转

int list_reverse(Node_ptr L)
{
    //判断逻辑
    if(NULL==L || list_empty(L) || L->len==1)
    {
        printf("翻转失败\n");
        return -1;
    }

    //翻转逻辑
    Node_ptr H = L->next;   //用头指针托管链表
    L->next = NULL;         //清空当前链表

    while(H!=NULL)
    {
        Node_ptr p = H;       //挖墙脚
        H = H->next;          //管理下一位

        //以头插的形式将p插入到L中
        p->next = L->next;
        L->next = p;
    }

    printf("翻转成功\n");
    return 0;

}

销毁单向链表

注意：不是直接销毁头节点，需要先将所有的节点全部释放后然后释放头节点

//单向链表的释放
void list_destroy(Node_ptr L)
{
    //判断逻辑
    if(NULL == L)
    {
        printf("销毁失败\n");
        return;
    }

    //释放逻辑
    //将所有普通结点释放
    while(!list_empty(L))
    {
        //调用头删函数
        list_delete_head(L);
    }

    //释放头结点
    free(L);
    L = NULL;
    printf("销毁成功\n");
}

#include "linklist.h"

//创建链表
Node_p list_create()
{
//堆区申请空间
Node_p L=(Node_p)malloc(sizeof(Node));
      if(NULL==L)

	{
		printf("创建失败\n");
		return NULL;
	}
	  //程序至此一个头结点申请成功
	  //有头节点形成一条链表
	  //初始化操作
	  L->len=0;
	  L->next=NULL;//防止野指针

	  printf("链表创建成功");
	  return L;

}
int list_empty(Node_p L)
	//判空操作
	//链表为空返回1，非空返回0
{
	//判断逻辑
	if(NULL==L)
	{
		printf("链表不合法\n");
		return -1;
		
	}
	return L->next==NULL;
}

Node_p node_apply(datatype e)
{
	//在堆区申请节点空间
	Node_p p= (Node_p)malloc(sizeof(Node));
	if(NULL==p)
	{
		printf("节点申请失败");
		return NULL;
	
	}
	p->data=e;
	p->next=NULL;
	return p;
}

//单向链表头插
int list_insert_head(Node_p L,datatype e)
{
	//判断逻辑
	if(NULL==L)
	{
		printf("链表不合法");
		return -1;
	}
	//申请节点封装数据
	Node_p p=node_apply(e);
	if(NULL==p)
	{
	return -1;
	}
	p->next=L->next;
	L->next=p;
	L->len++;
	printf("插入成功\n");
	return 0;
	
}
//单向链表按位置查找返回节点
Node_p list_find_node(Node_p L,int pos)
{
	//判断逻辑
	if(NULL==L||pos<0||pos>L->len)
	{
		printf("查找失败\n");
		return NULL;
	}
	//查找逻辑
	Node_p q=L;//定义遍历指针从头节点出发
	for (int i=0;i<pos;i++)
	{
		q=q->next;//将指针偏移到下一个节点的位置
		//q++; //偏移一个节点的大小
	}
	return q;
}

//单向链表的遍历
void list_show(Node_p L)
{
	//判断逻辑
	if(list_empty(L))
	{
		printf("遍历失败\n");
		return ;
	}
	//遍历所有节点
	/*printf("链表中的元素是：\n");
	for (int i=1;i<L->len;i++)
	{
		Node_p p=list_find_node(L ,i);
		//找到第i个节点；
		printf("%c",p->data);

	}*/
	printf("链表中的元素是：\n");
	Node_p q=L->next;
	while(q)
	{
	printf("%c\t",q->data);
	q=q->next;
	}printf("\n");

}

//单向链表的任意位置插入
int list_insert_pos(Node_p L,int pos,datatype e)
{
	//判断逻辑
	if(NULL==L||pos<1||pos>L->len+1)
	{
		printf("插入失败\n");
			return -1;
	}
	//找到插入位置的前一个节点
	Node_p q=list_find_node(L,pos-1);

	//申请节点封装数据
	Node_p p =node_apply(e);
	if(NULL==p)
	{
	return -1;
	}
	//插入逻辑
	p->next=q->next;
	q->next=p;

	L->len++;
	printf("插入成功\n");
	return 0;
}
int list_head_delete(Node_p L)
{
	//判断逻辑
	if(NULL==L||list_empty(L))
	{	printf("删除失败\n");
	return -1;
	}
	//删除逻辑
	Node_p p=L->next;
	L->next=p->next;
	free(p);
	p=NULL;

	L->len--;
	printf("删除成功\n");
	return 0;
}
int list_delete_pos(Node_p L,int pos)
{
	if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
    {
        printf("删除失败\n");
        return -1;
    }
	Node_p q=list_find_node(L,pos-1);//找到前驱节点
	Node_p p=q->next;
	q->next=p->next;
	free(p);
	p=NULL;

	printf("删除成功\n");
	L->len--;
	return 0;
}
//单向链表按位置修改
int list_update_pos(Node_p L,int pos,datatype e)
{
	//判断逻辑
    if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
    {
        printf("修改失败\n");
        return -1;
    }
	Node_p p=list_find_node(L,pos);
	//找到指定节点
	p->data=e;
	//修改值
	printf("修改成功\n");
	return 0;
}

//单向链表的翻转
int list_reverse(Node_p L)
{
	if(NULL==L || list_empty(L) || L->len==1)
	{
		printf("翻转失败\n");
		return -1;
	}
	//翻转逻辑
	Node_p H=L->next;
	L->next=NULL;

	while(H!=NULL)
	{
	Node_p p=H;
	H=H->next;

	p->next=L->next;
	L->next=p;

	}printf("翻转成功\n");
}
void list_destory(Node_p L)
{
	//判断逻辑
    if(NULL == L)
    {
        printf("销毁失败\n");
        return;
    }

	//释放逻辑
	//先将普通节点全部释放
	while(!list_empty(L))
	{
	//头删
	list_head_delete(L);
	}
	//释放头节点
	free(L);
	L=NULL;
	printf("销毁成功\n");
	
}
//单向链表的尾插
int list_tail_insert(Node_p L,datatype e)
{
	if(NULL==L||list_empty(L))
	{
	printf("尾插失败\n");
	return -1;
	}
	Node_p p=node_apply(e);
	//申请节点封装数据
	Node_p q =list_find_node(L,L->len);
	//查找到最后一个节点；
	q->next=p;
	L->len++;
	printf("尾插成功\n");

	return 0;
}
//单向链表的尾删
int list_tail_delete(Node_p L)
{
	if(NULL==L||list_empty(L))
	{
	printf("尾删失败\n");
	return -1;
	}
	Node_p p=list_find_node(L,L->len-1);
	Node_p q=p->next;
	//找到最后一个节点的前一个节点
	p->next=NULL;
	free(q);
	q=NULL;
	L->len--;
	printf("尾删成功\n");
	return 0;

}
//单向链表按值查找返回位置
int list_data_sreach(Node_p L,datatype e)
{
	
	if(NULL==L||list_empty(L))
	{
	printf("查找失败\n");
	return -1;
	}
	Node_p p=L->next;
	int i;
	for ( i=0;i<L->len;i++)
	{
	if(p->data==e)
	{
		return i+1;
	}
	p=p->next;
	}
	if(i==L->len)
	{
		printf("查找失败\n");
		return -1;
	}
}
int list_paixu(Node_p L)
{
	if(NULL==L||list_empty(L)||L->len==1)
	{
		printf("排序失败\n");
	return -1;
	}

	for (int i=1;i<L->len;i++)
	{
		for (Node_p p=L->next;p->next!=NULL;p=p->next)
		{
			if(p->data>p->next->data)//生序排列
			{
			datatype temp=p->data;
			p->data=p->next->data;
			p->next->data=temp;
			}
		}
		
	}
	printf("排序成功\n");
	return 0;
}
//单向链表的去重
int list_unique(Node_p L)
{	
	if(NULL==L||list_empty(L),L->len==1)
	{
		printf("去重失败\n");
		return -1;

	}
	Node_p p=L->next;
	for (p=L->next;p->next!=NULL;p=p->next)
	{
		if(p->data=p->next->data);
		{
			Node_p q=p->next;
			p->next=q->next;
				free(q);
				L->len--;
				return 0;

		}
		//定义一个q标记要删除的节点
	}

}
int list_clear(Node_p L)
{
	while(L->next!=NULL)
	{
	list_head_delete(L);
	L->len--;
	}
	return 0;
}
int list_len(Node_p L)
{
	return L->len;

}


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

相关文章：

  • 单链表---移除链表元素
  • TiDB 无统计信息时执行计划如何生成
  • Flink四大基石之Time (时间语义) 的使用详解
  • 零拷贝相关知识点（一）
  • Linux：文件系统inode
  • 利用Matlab进行分布函数回归分析
  • 免费搭建一个属于自己的个性化博客(Hexo+Fluid+Github)
  • Rk3588 onnx转rknn，出现 No module named ‘rknn‘
  • 【大数据学习 | 面经】HDFS的三副本机制和编码机制
  • Microsoft Excel如何插入多行
  • 【阿来来gis规划师工具箱说明书】h07四分标注
  • 管家婆工贸ERP BR044.当前库存余额表
  • 【kafka04】消息队列与微服务之Kafka 图形工具
  • Vue 2.0-＞3.0学习笔记（Vue 3 （三）- 其它 Composition API）
  • 【Pytorch】优化器（Optimizer）模块‘torch.optim’
  • QUICK 调试camera-xml解析
  • 神经网络中常见的激活函数Sigmoid、Tanh和ReLU
  • 三十一：HTTP多种重定向跳转方式的差异
  • 《FPGA开发工具》专栏目录
  • 【Rust 学习笔记】Rust 基础数据类型介绍（一）
  • idea根据实体类生成数据库表
  • 【面试题】2025年百度校招Java后端面试题
  • PDF view | Chrome PDF Viewer |Chromium PDF Viewer等指纹修改
  • .net core 创建linux服务，并实现服务的自我更新
  • 【AI日记】24.11.30 kaggle 比赛 Titanic-3
  • 万字长文解读深度学习——多模态模型BLIP2