嵌入式开发学习———Linux环境下数据结构学习（二）

链表是一种通过指针链接节点的线性数据结构，每个节点包含数据域和指针域。本文介绍了单向链表的基本概念和实现方法，包括插入、删除、查找、修改等核心操作。单向链表的特点是只能单向遍历，插入/删除时间复杂度为O(1)，但查找需要O(n)。文中提供了Python实现示例，并详细讲解了C语言实现中的各种操作函数，如头插、尾插、位置删除、数据查找等。最后展示了链表排序和逆置的实现方法，并附有完整的运行示例代码，

幻灭虚空

449人浏览 · 2025-07-23 21:57:58

幻灭虚空 · 2025-07-23 21:57:58 发布

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。与数组不同，链表中的元素在内存中不需要连续存储，而是通过指针动态链接。

单向链表的特点

每个节点包含数据和一个指向下一个节点的指针（next）。
只能单向遍历（从头节点到尾节点）。
插入和删除操作的时间复杂度为 $O(1)$（已知位置时），但查找需 $O(n)$。

单向链表的简单实现（Python示例）

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

核心操作

插入节点

def insert_at_end(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

删除节点

def delete_node(self, key):
    current = self.head
    if current and current.data == key:
        self.head = current.next
        return
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next
    if current:
        prev.next = current.next

优缺点

优点：动态大小，高效插入/删除。
缺点：随机访问慢，额外内存存储指针。

作业：

单向链表建立等一系列操作。

#include "linklist.h"

int main(int argc, const char *argv[])
{
	//
	int i;
	//
	int n;


	//头节点指针
	linklistptr headptr=NULL;



	//头节点申请
	headptr=HeadNodeApply();

	//定义一个新数据
	datatype nwedata;
	for(i=0;i<9;i++)
	{
		puts("请输入一个数：");
		scanf(" %d",&nwedata);
		//调用单向链表的头插函数
		LinklistHeadinsert(headptr,nwedata);
	}

	//调用单向链表的遍历函数
	LinklistShow(headptr);

	puts("请输入一个数：");
	scanf(" %d",&nwedata);
	//调用单向链表的尾插函数
	LinklistTailinsert(headptr,nwedata);


	//调用单向链表的遍历函数
	LinklistShow(headptr);

	//调用单向链表的尾删函数
	puts("尾删后：");
	LinklistTaildelete(headptr);
	
	//调用单向链表的遍历函数
	LinklistShow(headptr);

	//调用单向链表的头删函数
	puts("头删后：");
	LinklistHeaddelete(headptr);
	LinklistHeaddelete(headptr);

	//调用单向链表的遍历函数
	LinklistShow(headptr);

	puts("请输入一个数：");
	scanf(" %d",&nwedata);
	puts("请输插入的位置：");
	scanf(" %d",&n);
	//调用单向链表按位置插入函数
	LinklistSeatinsert(headptr,n,nwedata);
	
	//调用单向链表的遍历函数
	LinklistShow(headptr);

	puts("请输删除的位置：");
	scanf(" %d",&n);
	//调用单向链表按位置删除函数
	LinklistSeatdelete(headptr,n);

	//调用单向链表的遍历函数
	LinklistShow(headptr);
	
	puts("请输入一个数：");
	scanf(" %d",&nwedata);
	puts("请输修改的位置：");
	scanf(" %d",&n);
	//调用单向链表按位置修改函数
	LinklistSeatalter(headptr,n,nwedata);

	//调用单向链表的遍历函数
	LinklistShow(headptr);

	puts("请输查找的位置：");
	scanf(" %d",&n);
	//调用单向链表按位置查找函数
	LinklistSeatsift(headptr,n);

	//调用单向链表的逆置函数
	Linklistreverse(headptr);
		
	//调用单向链表的遍历函数
	LinklistShow(headptr);
	
	puts("请输查找的倒数位置：");
	scanf(" %d",&n);
	//调用单向链表按位置查找函数
	LinklistSeatreversesift(headptr,n);

	datatype olddata;
	puts("请输查找的数据：");
	scanf(" %d",&olddata);
	//调用单向链表按数据查找函数
	int seat=LinklistDatasift(headptr,olddata);
	LinklistSeatsift(headptr,seat);
	
	puts("请输入要修改的数据：");
	scanf(" %d",&olddata);
	puts("请输入修改后的数据：");
	scanf(" %d",&nwedata);
	//调用 单向链表按数据修改函数
	LinklistDataalter(headptr,olddata,nwedata);

	//调用单向链表的遍历函数
	LinklistShow(headptr);
	puts("请输入要删除的数据：");
	scanf(" %d",&olddata);
	//调用单向链表按数据删除函数
	LinklistDatadelete(headptr,olddata);

	//调用单向链表的遍历函数
	LinklistShow(headptr);

	//单向链表的排序函数
	LinklistSort(headptr);

	//调用单向链表的遍历函数
	LinklistShow(headptr);

	return 0;
}

#ifndef _LINKLIST_H__
#define _LINKLIST_H__

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

enum returntype
{
	//失败返回
	FAULSE=-1,
	//成功返回
	SUCCESS
};

//存储的数据的数据类型
typedef int datatype;

//单向链表的节点结构体
typedef struct Node
{
	//数据域
	union 
	{
		//头节点数据域
		int len;
		//普通节点数据域
		datatype data;
	}; 
	//指针域
	struct Node *next;
}linklist,*linklistptr;

//头节点申请函数
linklistptr HeadNodeApply(void);

//普通节申请函数
linklistptr CommonNodeApply(datatype nwedata);

//单向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata);

//单向链表的遍历函数
int LinklistShow(linklistptr headptr);

//单向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata);

//单向链表的尾删函数
int LinklistTaildelete(linklistptr headptr);

//单向链表的头删函数
int LinklistHeaddelete(linklistptr headptr);

//单向链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int n,datatype nwedata);

//单向链表按位置删除函数(作业)
int LinklistSeatdelete(linklistptr headptr,int n);

//单向链表按位置修改函数(作业)
int LinklistSeatalter(linklistptr headptr,int n,datatype nwedata);

//单向链表按位置查找函数(作业)
int LinklistSeatsift(linklistptr headptr,int n);

//单向链表的逆置函数
int Linklistreverse(linklistptr headptr);

//查找链表倒数第n个数据
int LinklistSeatreversesift(linklistptr headptr,int n);

//单向链表按数据查找
int LinklistDatasift(linklistptr headptr,datatype olddata);

//单向链表按数据修改函数
int LinklistDataalter(linklistptr headptr,datatype olddata,datatype nwedata);

//单向链表按数据删除函数
int LinklistDatadelete(linklistptr headptr,datatype olddata);

//单向链表的排序函数
int LinklistSort(linklistptr headptr);

#endif

#include "linklist.h"


//头节点申请函数
linklistptr HeadNodeApply(void)
{
	//堆区申请
	linklistptr headptr=(linklistptr)malloc(sizeof(linklist));
	//判断创建是否成功
	if(headptr==NULL)
	{
		return NULL;
	}
	//初始化
	headptr->next=NULL;
	headptr->len=0;
	//返回地址
	return headptr;
}

//普通节申请函数
linklistptr CommonNodeApply(datatype nwedata)
{
	//堆区申请
	linklistptr comptr=(linklistptr)malloc(sizeof(linklist));
	//判断创建是否成功
	if(comptr==NULL)
	{
		return NULL;
	}
	//赋值，初始化
	comptr->next=NULL;
	comptr->data=nwedata;
	//返回地址
	return comptr;
}


//单链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata)
{
	//判断头指针是否为空
	if(headptr==NULL)
	{
		return FAULSE;
	}
	//创建一个普通节点并初始化
	linklistptr comptr=CommonNodeApply(nwedata);
	//判断普通节点是否为NULL
	if(comptr==NULL)
	{
		return FAULSE;
	}
	//头插
	comptr->next=headptr->next;
	headptr->next=comptr;
	//链表长度自增
	headptr->len++;
	return SUCCESS;
}

//单向链表的遍历函数
int LinklistShow(linklistptr headptr)
{
	//定义一个链表指针
	linklistptr ptr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//赋值下一个节点地址
	ptr=headptr->next;
	//循环输出数据
	puts("链表现有数据：");
	while(ptr)
	{
		printf(" %d",ptr->data);
		ptr=ptr->next;  //
	}
	putchar(10);
	return SUCCESS;
}

//单向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata)
{
	//定义一个链表指针
	linklistptr ptr=NULL;
	//判断头指针是否为空
	if(headptr==NULL)
	{
		return FAULSE;
	}
	//赋值头结点地址
	ptr=headptr;
	//循环找到链表尾部
	while(ptr->next)
	{
		ptr=ptr->next;
	}
	//创建一个普通节点并初始化
	linklistptr comptr=CommonNodeApply(nwedata);
	//判断普通节点是否为空
	if(comptr==NULL)
	{
		return FAULSE;
	}
	//尾插
	comptr->next=ptr->next;
	ptr->next=comptr;
	//链表长度自增
	headptr->len++;
	return SUCCESS;
}

//单向链表的尾删函数
int LinklistTaildelete(linklistptr headptr)
{
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//赋值头结点地址
	ptr=headptr;
	//循环找到链表次尾部
	while(ptr->next->next)
	{
		ptr=ptr->next;
	}
	free(ptr->next);
	ptr->next=NULL;
	headptr->len--;
	return SUCCESS;
}

//单向链表的头删函数
int LinklistHeaddelete(linklistptr headptr)
{
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//赋值头结点地址
	ptr=headptr->next;
	headptr->next=headptr->next->next;
	//释放删除的空间
	free(ptr);
	ptr=NULL;
	headptr->len--;
	return SUCCESS;
}

//单向链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int n,datatype nwedata)
{
	//定义循环变量
	int i;
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	//判断n是否合法
	if(headptr==NULL||headptr->len==0||n<=0||n>headptr->len+1)
	{
		return FAULSE;
	}
	//循环找到链表对应位置
	ptr=headptr;
	for(i=0;i<n-1;i++)
	{
		ptr=ptr->next;
	}
	//创建一个普通节点并初始化
	linklistptr comptr=CommonNodeApply(nwedata);
	//判断普通节点是否为空
	if(comptr==NULL)
	{
		return FAULSE;
	}
	//进行插入
	comptr->next=ptr->next;
	ptr->next=comptr;
	headptr->len++;
	return SUCCESS;
}

//单向链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int n)
{
	//定义循环变量
	int i;
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	//判断n是否合法
	if(headptr==NULL||headptr->len==0||n<=0||n>headptr->len)
	{
		return FAULSE;
	}
	//循环找到链表对应位置
	ptr=headptr;
	for(i=0;i<n-1;i++)
	{
		ptr=ptr->next;
	}
	//进行删除
	qtr=ptr->next;
	ptr->next=ptr->next->next;
	free(qtr);
	qtr=NULL;
	headptr->len--;
	return SUCCESS;
}

//单向链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int n,datatype nwedata)
{
	//定义循环变量
	int i;
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	//判断n是否合法
	if(headptr==NULL||headptr->len==0||n<=0||n>headptr->len)
	{
		return FAULSE;
	}
	//找到对应位置
	ptr=headptr;
	for(i=0;i<n;i++)
	{
		ptr=ptr->next;
	}
	//赋值修改
	ptr->data=nwedata;
	return SUCCESS;
}

//单向链表按位置查找函数
int LinklistSeatsift(linklistptr headptr,int n)
{
	//定义循环变量
	int i;
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	//判断n是否合法
	if(headptr==NULL||headptr->len==0||n<=0||n>headptr->len)
	{
		return FAULSE;
	}
	//找到对应位置
	ptr=headptr;
	for(i=0;i<n;i++)
	{
		ptr=ptr->next;
	}
	printf("linklist[%d]=%d\n",n,ptr->data);
	return SUCCESS;
}

//单向链表的逆置函数
int Linklistreverse(linklistptr headptr)
{
	//定义循环变量
	int i;
	//定义两个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空或者只有一个数据
	if(headptr==NULL||headptr->len<=1)
	{
		return FAULSE;
	}
	//存储头指针指向并断开
	ptr=headptr->next;
	headptr->next=NULL;
	//循环头插
	for(i=0;i<headptr->len;i++)
	{
		qtr=ptr;
		ptr=ptr->next;
		qtr->next=headptr->next;
		headptr->next=qtr;
	}
	return SUCCESS;
}

//查找链表倒数第n个数据
int LinklistSeatreversesift(linklistptr headptr,int n)
{
	//定义循环变量
	int i;
	//定义两个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	//判断n是否合法
	if(headptr==NULL||headptr->len==0||n<=0||n>headptr->len)
	{
		return FAULSE;
	}
	//第一种单循环找倒数
	ptr=headptr->next;
	for(i=0;i<headptr->len-n;i++)
	{
		ptr=ptr->next;
	}
	printf("linklist[-%d]=%d\n",n,ptr->data);

	//第二种双循环找倒数
	ptr=headptr;
	qtr=headptr;
	for(i=0;i<n;i++)
	{
		qtr=qtr->next;
	}
	while(qtr)
	{
		ptr=ptr->next;
		qtr=qtr->next;
	}
	printf("linklist[-%d]=%d\n",n,ptr->data);
	return SUCCESS;
}

//单向链表按数据查找函数
int LinklistDatasift(linklistptr headptr,datatype olddata)
{
	//定义循环变量
	int i;
	//定义一个链表指针
	linklistptr ptr=NULL;
	//判断头指针是否为NULL
	//判断链表是否为空
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//赋值第一个节点位置并把位置置1
	ptr=headptr->next;
	int seat=1;
	for(i=0;i<headptr->len;i++)
	{
		if(ptr->data==olddata)
		{
			//返回位置
			return seat;
		}
		seat++;
		ptr=ptr->next;
	}
	return FAULSE;
}

//单向链表按数据修改函数
int LinklistDataalter(linklistptr headptr,datatype olddata,datatype nwedata)
{
	//定义位置变量
	int seat;
	//调用单向链表按数据查找函数并判断
	seat=LinklistDatasift(headptr,olddata);
	if(seat==FAULSE)
	{
		return FAULSE;
	}
	//调用单向链表按位置修改函数并判断
	if(LinklistSeatalter(headptr,seat,nwedata)==FAULSE)
	{
		return FAULSE;
	}
	return SUCCESS;
}

//单向链表按数据删除函数
int LinklistDatadelete(linklistptr headptr,datatype olddata)
{
	//定义位置变量
	int seat;
	//调用单向链表按数据查找函数并判断
	seat=LinklistDatasift(headptr,olddata);
	if(seat==FAULSE)
	{
		return FAULSE;
	}
	//调用单向链表按位置删除函数并判断
	if(LinklistSeatdelete(headptr,seat)==FAULSE)
	{
		return FAULSE;
	}
	return SUCCESS;
}

//单向链表的排序函数
int LinklistSort(linklistptr headptr)
{
	int i,j;
	datatype temp;
	//定义一个链表指针
	linklistptr ptr=NULL,qtr=NULL;
	ptr=headptr->next;
	for(i=0;i<headptr->len-1;i++)
	{
		qtr=ptr;
		for(j=0;j<headptr->len-1;j++)
		{
			if(qtr->data>qtr->next->data)
			{
				temp=qtr->data;
				qtr->data=qtr->next->data;
				qtr->next->data=temp;
			}
			qtr=qtr->next;
		}
	}
	return SUCCESS;
}

运行示例：