首页 > 其他分享 >线性表——链表(c语言)

线性表——链表(c语言)

时间:2024-07-19 19:28:52浏览次数:12  
标签:node current 结点 线性表 list 链表 linkedlist 语言

链表

概念篇

在这里插入图片描述
对顺序表知识感兴趣的朋友可以看一下线性表-顺序表(c语言)
对栈感兴趣的朋友可以看一下顺序表实现栈
想进一步学习链表的朋友可以看下链表实现栈这篇文章。

示意图

1. 单向链表

在这里插入图片描述

2.双向链表

在这里插入图片描述

3.循环链表

在这里插入图片描述

4.链表的元素插入

在这里插入图片描述

5.链表的元素删除

在这里插入图片描述

代码篇

代码只展示单向链表的写法,其他链表的代码部分改动即可。下面的代码中没有头结点,是否定义头结点全凭个人的喜好。

1.链表的定义

1.链表由多个结点组成的,在定义链表之前要先声明结点。
2.通过结构体把一些属性封装起来表示结点和链表。
typedef struct node
{
	int data;
	//存放数据
	struct node*next;
	//指向后继结点的指针
}node;
typedef struct linkedlist
{
	node*head;
	//始终指向第一个结点的指针
	size_t size;
	//元素个数
}linkedlist;

2.链表的创建

linkedlist_create(linkedlist*list)
{
	list->head=NULL;
	//初始时链表为空,头指针为NULL 
	list->size=0;
	//初始时链表的元素个素为0
}

3.链表的销毁

链表的销毁就是释放所有结点所占有的内存空间。
linkedlist_destory(linkedlist*list)
{
	while(list->head)//为空时说明已经遍历到了最后一个结点
	{
		node*newnode=list->head;
		// 通过头指针的当前位置获取当前结点 
		list->head=list->head->next;
		// 更新头指针,使其指向下一个结点  
		free(newnode);
		//释放当前结点。
	}
}

4.链表的元素插入

1.判断插入的位置是否合法
2.处理插入的位置在第一个结点前面的情况
3.处理插入的位置不在第一个结点前面的情况
	linkedlist_insert(linkedlist*list,int index,int elements)
	{
		node*newnode=(node*)malloc(sizeof(node));
		//声明一个指向结点的指针,并为该指针分配内存
		newnode->data=elements;
		//将elements的值赋给该结点的data成员  
		if(index<0||index>list->size)
    	{
        	printf("invalid index\n");
        	return;
        	//插入的下标不合法则打印非法插入,返回。
    	}
		if(index==0)
		{
			//如果插入的位置在最前面
			newnode->next=list->head;
			//将新结点的next指针指向头指针指向的结点(第一个结点)
			list->head=newnode;
			//更新头指针
		}
		else
		{
			node*current=list->head;
			//初始化一个指针current指向链表的的一个结点
			for(int i=0;i<index-1;i++) 
				current=current->next;
				// 使用for循环来移动current指针,使其指向第 index-1 个节点
			newnode->next=current->next;
			//将新节点的next指针指向current节点的下一个节点
			current->next=newnode;
			//将新节点插入到current节点之后
		}
		list->size++;
		//更新链表的元素个素
	}

5.链表的元素删除

1.判断删除的位置是否合法
2.处理删除的结点是第一个结点的情况
3.处理删除的结点不是第一个结点前面的情况
void linkedlist_delete(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
    {
        printf("invalid index\n");
        return;
    }
    if(index==0)
    {
        node*newnode=list->head->next;
        //声明一个指针来指向链表的第二个结点
        free(list->head);
        //释放第一个结点的内存空间
        list->head=newnode;
        //更新头指针
    }
    else
    {
        node*current=list->head;
        for(int j=0;j<index-1;j++)
            current=current->next;
            // 循环直到找到要删除节点的前一个节点  
        node*newnode=current->next->next;
        //声明一个指针指向要删除结点的下一个结点。
         free(current->next); 
       // 释放要删除的结点的内存空间  
        current->next=newnode;
       // 将要删除节点的前一个节点的next指针指向要删除节点的下一个节点
    }
    list->size--;
    //更新链表的元素个数
}

6.链表的元素查找

逐个遍历,满足条件就返回该结点
node* linkedlist_find(linkedlist*list,int value)
{
    node*current=list->head;
    while(current)
    {
        if(current->data==value)
            return current;
        current=current->next;
        //如果当前没找到就继续遍历
    }
    return NULL;
}

7.链表下标对应的结点

写这个函数是为了下面修改元素方便
node* linkedlist_index(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
        printf("invalid index\n");
    node*current=list->head;
    for(int j=0;j<index;j++)
        current=current->next;
    return current;
}

8.链表元素的修改

通过链表下标对应的结点函数找到索引对应的结点,直接修改结点的data成员
void linkedlist_alter(linkedlist*list,int index,int elements)
{
    node*newnode=linkedlist_index(list,index);
    // 通过索引找到链表中的结点,并将返回的指针赋值给newnode 
    if(newnode)
    //指针不为空
        newnode->data=elements;
}

9.链表的打印

逐个遍历结点,打印元素
void linkedlist_print(linkedlist*list)
{
    node*current=list->head;
    //初始化一个指针current指向链表的的一个结点
    while(current)
    {
        printf("%d->",current->data);
        current=current->next;
        
    }
    printf("NULL\n");
}

10.完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int data;
	//存放数据
	struct node*next;
	//指向后继结点的指针
}node;
typedef struct linkedlist
{
	node*head;
	//始终指向第一个结点的指针
	size_t size;
	//元素个数
}linkedlist;
linkedlist_create(linkedlist*list)
{
	list->head=NULL;
	//初始时链表为空,头指针为NULL 
	list->size=0;
	//初始时元素个数为0
}
linkedlist_destory(linkedlist*list)
{
	while(list->head)//为空时说明已经遍历到了最后一个结点
	{
		node*newnode=list->head;
		// 通过头指针的当前位置获取当前结点 
		list->head=list->head->next;
		// 更新头指针,使其指向下一个结点  
		free(newnode);
		//释放当前结点。
	}
}
linkedlist_insert(linkedlist*list,int index,int elements)
{
	node*newnode=(node*)malloc(sizeof(node));
	//声明一个指向结点的指针并为指针分配内存空间
	newnode->data=elements;
	//将elements的值赋给该结点的data成员  
	if(index<0||index>list->size)
    {
        printf("invalid index\n");
        return;
        //插入的下标不合法则打印非法插入,返回。
    }
	if(index==0)
	{
		//如果插入的位置在最前面
		newnode->next=list->head;
		//将新结点的next指针指向头指针指向的结点(第一个结点)
		list->head=newnode;
		//更新头指针
	}
	else
	{
			node*current=list->head;
			//初始化一个指针current指向链表的第一个结点
			for(int i=0;i<index-1;i++) 
				current=current->next;
				// 使用for循环来移动current指针,使其指向第 index-1 个节点				 
			newnode->next=current->next;
			//将新节点的next指针指向current节点的下一个节点
			current->next=newnode;
			//将新节点插入到current节点之后
	}
	list->size++;
	//更新链表的元素个素
}
void linkedlist_delete(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
    {
        printf("invalid index\n");
        return;
    }
    if(index==0)
    {
        node*newnode=list->head->next;
        //声明一个指针来指向链表的第二个结点
        free(list->head);
        //释放第一个指针的内存空间
        list->head=newnode;
        //更新头指针
    }
    else
    {
        node*current=list->head;
        for(int j=0;j<index-1;j++)
            current=current->next;
            // 循环直到找到要删除节点的前一个节点  
        node*newnode=current->next->next;
        //声明一个结点指针来存放要删除的结点的后一个结点
         free(current->next); 
       // 释放要删除的结点的内存空间  
        current->next=newnode;
       // 将要删除节点的前一个节点的next指针指向要删除节点的下一个节点
    }
    list->size--;
    //更新链表的元素个数
}
node* linkedlist_find(linkedlist*list,int value)
{
    node*current=list->head;
    while(current)
    {
        if(current->data==value)
            return current;
        current=current->next;        
        //如果当前没找到就继续遍历
    }
    return NULL;
}
node* linkedlist_index(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
        printf("invalid index\n");
    node*current=list->head;
    for(int j=0;j<index;j++)
        current=current->next;
    return current;
}
void linkedlist_alter(linkedlist*list,int index,int value)
{
    node*node=linkedlist_index(list,index);
    // 通过索引找到链表中的结点,并将返回的指针赋值给newnode 
    if(node)
    //指针不为空
        node->data=value;
}
void linkedlist_print(linkedlist*list)
{
    node*current=list->head;
    //初始化一个指针current指向链表的的一个结点
    while(current)
    {
        printf("%d->",current->data);
        current=current->next;
    }
    printf("NULL\n");
}
int main()
{
    linkedlist list;
    linkedlist_create(&list);
    linkedlist_insert(&list,0,10);
    linkedlist_insert(&list,1,20);
    linkedlist_insert(&list,2,30);
    linkedlist_insert(&list,3,40);
    printf("original list:");
    linkedlist_print(&list);
    linkedlist_delete(&list,2);
    linkedlist_alter(&list,1,100);
    printf("now list:");
    linkedlist_print(&list);
    return 0;
}

代码运行效果

在这里插入图片描述
以上是我对链表的见解,希望路过的大佬能指正错误并补充没涉及的知识,万分感谢!

标签:node,current,结点,线性表,list,链表,linkedlist,语言
From: https://blog.csdn.net/2301_79893984/article/details/140419514

相关文章

  • 链表(Linked List)-Python实现-使用类和使用函数
    链表链表(LinkedList)单链表(SinglyLinkedList)节点类(NodeClass)链表类(LinkedListClass)使用链表类不用类的方法实现链表实现单链表使用函数实现链表具体讲解类的方法实现链表Node类LinkedList类不用类的方法实现链表创建节点添加节点删除节点搜索节点显示链表总......
  • 【c语言】日日练-通讯录
    通讯录题目解析(实现过程+要点)代码test.c(测试功能)contact.c(通讯录相关的实现)contact.h(通讯录相关的声明)题目实现一个通讯录,人的信息包括(姓名、年龄、性别、电话、地址)实现功能:1、存放100个人的信息2、增加联系人3、删除指定联系人4、查找联系人5、修改联系......
  • 链表。。。
    模板题AcWing826.单链表实现一个单链表,链表初始为空,支持三种操作:向链表头插入一个数;删除第k个插入的数后面的数;在第k个插入的数后插入一个数。现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。注意:题目中第k个插入的数并不是指当前链表的第......
  • 微调 Florence-2 - 微软的尖端视觉语言模型
    微调Florence-2-微软的尖端视觉语言模型 Florence-2是微软于2024年6月发布的一个基础视觉语言模型。该模型极具吸引力,因为它尺寸很小(0.2B及0.7B)且在各种计算机视觉和视觉语言任务上表现出色。Florence开箱即用支持多种类型的任务,包括:看图说话、目标检测、O......
  • C语言运算符
    1.算术运算符+加法-减法*乘法/除法%取余 计算时,数据类型不一样的不能直接运算,需要转换成一样的才能运算,有两种转换方式。1.1隐式转换把一个取值范围小的,转换为取值范围大的,隐式转换是计算机自己就可以完成的,不会产生错误的。数据类型从大的到小的顺序为:double>float>lon......
  • 02线性表 - 链表
    这里是只讲干货不讲废话的炽念,这个系列的文章是为了我自己以后复习数据结构而写,所以可能会用一种我自己能够听懂的方式来描述,不会像书本上那么枯燥和无聊,且全系列的代码均是可运行的代码,关键地方会给出注释^_^全文1W+字版本:C++17编译器:Clion2023.3.24暂时只给出代码,不会涉......
  • 【代码随想录训练营第42期 Day3打卡 LeetCode 203.移除链表元素,707.设计链表,206.反转
    一、做题感受今天是打卡的第三天,前两天题目主要考察数组相关知识,现在已经来到了链表的学习。题目共有三道,都是以考察单链表为主,整体来说难度不大,但是思路很灵活,尤其是反转链表的考察,双指针的新用法。今天做题总体感觉不错,能有自己的思考和理解。二、链表相关知识1.常见链表......
  • C语言函数详解
    函数的概念不同于数学上的函数,在C语言中,函数(function)就是一个完成某项特定任务的一段代码,所以函数也叫子程序。函数的分类库函数为了提高写代码的效率,C语言的国际标准ANSIC规定了一些常用的函数的标准,被称为标准库。不同的编译器厂商根据ANSI提供的标准就给出了一系列函数......
  • Datawhale AI 夏令营 task2语言包陷入困境
     一、了解机器翻译在运行task1时,我仅仅只是按照教程一步步走下去,不理解每一步的意义,也不懂什么叫做机器翻译。于是在task2中碰了壁。1.机器翻译的含义机器翻译(MT)是自然语言处理领域的一个重要分支,其目标是将一种语言的文本自动转换为另一种语言的文本。机器翻译的发展经历......
  • C语言基础(二)
    数据类型    数据类型介绍:            整型类型来描述整数,字符类型来描述字符,浮点型类型来描述小数;    字符型:char//character[signed]char//有符号的unsignedchar//⽆符号的    整型://短整型short[int][signed]s......