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

发布于：2025-07-29 ⋅ 阅读:(24) ⋅ 点赞:(0)

单向循环链表

单向循环链表是一种特殊的单向链表，尾节点的指针指向头节点，形成一个闭环。适用于需要循环访问的场景，如轮询调度。

  • 结构特点：每个节点包含数据域和指向下一个节点的指针，尾节点的指针指向头节点而非空值。
  • 操作复杂度：
    • 插入/删除头节点：O(1)
    • 插入/删除尾节点：O(n)（需遍历到尾部）
  • 代码示例（C++）：
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

双向链表

双向链表的每个节点包含前驱和后继指针，支持双向遍历，但需要更多内存存储指针。

  • 结构特点：节点包含前驱指针（prev）、数据域和后续指针（next）。
  • 操作复杂度：
    • 任意位置插入/删除：O(1)（已知前驱节点时）
    • 按值查找：O(n)
  • 代码示例（C++）：
struct DNode {
    int data;
    DNode* prev;
    DNode* next;
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

 
作业：

 1.双向链表的部分操作

#include "linklist.h"

int main(int argc, const char *argv[])
{
	//定义一个头
	linklistptr headptr=NULL;

	//定义循环变量
	int i;

	//定义位置变量
	int seat;

	//头的初始化
	headptr=LinklistHeadnodeApply();

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

	//调用双向链表的遍历函数next
	LinklistShownext(headptr);


	//调用双向链表的遍历函数front
	LinklistShowfront(headptr);

	//循环输入数据
	for(i=0;i<5;i++)
	{
		puts("请输入一个数：");
		scanf(" %d",&nwedata);
		//双向链表的尾插函数
		LinklistTailinsert(headptr,nwedata);
	}
	
	//调用双向链表的遍历函数next
	LinklistShownext(headptr);
	
	//调用双向链表的头删函数
	LinklistHeaddelete(headptr);

	//调用双向链表的遍历函数next
	LinklistShownext(headptr);
	
	//调用双向链表的尾删函数
	LinklistTaildelete(headptr);

	//调用双向链表的遍历函数next
	LinklistShownext(headptr);

	//分别输入位置和新数据
	puts("输入想插入的位置：");
	scanf(" %d",&seat);
	puts("输入想插入的数据：");
	scanf(" %d",&nwedata);
	//调用双向链链表按位置插入函数
	LinklistSeatinsert(headptr,seat,nwedata);
	
	//调用双向链表的遍历函数next
	LinklistShownext(headptr);
	
	//输入位置
	puts("输入想删除的位置：");
	scanf(" %d",&seat);
	//调用双向链链表按位置插入函数
	LinklistSeatdelete(headptr,seat);
	
	//调用双向链表的遍历函数next
	LinklistShownext(headptr);
	
	//分别输入位置和新数据
	puts("输入想要修改的位置：");
	scanf(" %d",&seat);
	puts("输入想改成的数据：");
	scanf(" %d",&nwedata);
	//调用双向链链表按位置修改函数
	LinklistSeatalter(headptr,seat,nwedata);
	
	//调用双向链表的遍历函数next
	LinklistShownext(headptr);

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

	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 *front;
	//后向指针域
	struct Node *next;
}linklist,*linklistptr;

//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void);

//普通节点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata);

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

//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr);

//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr);

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

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

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

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

//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat);

//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata);

//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat);

#endif
#include "linklist.h"

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

//普通点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata)
{
	//普通节点堆区申请
	linklistptr comptr=(linklistptr)malloc(sizeof(linklist));
	//判断申请是否成功
	if(comptr==NULL)
	{
		return NULL;
	}
	//初始化
	comptr->data=nwedata;
	comptr->front=NULL;
	comptr->next=NULL;
	return comptr;
}

//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata)
{
	//定义普通节点指针
	linklistptr comptr=NULL;
	//判断是否为null
	if(headptr==NULL)
	{
		return FAULSE;
	}
	//普通节点申请
	comptr=LinklistComnodeApply(nwedata);
	//申请判断
	if(comptr==NULL)
	{
		return FAULSE;
	}
	//头插
	comptr->next=headptr->next;
	comptr->front=headptr;
	//判断是否为首个数据
	if(headptr->next)
	{
		headptr->next->front=comptr;
	}
	headptr->next=comptr;
	//个数自增
	headptr->len++;
	return SUCCESS;
}

//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr)
{
	//定义链表指针
	linklistptr ptr=NULL;
	//定义循环变量
	int i;
	//判断是否为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;
}

//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr)
{
	//定义链表指针
	linklistptr ptr=NULL;
	//定义循环变量
	int i;
	//判断是否为NULL
	//判断链表是否为空
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//找尾部
	ptr=headptr->next;
	while(ptr->next)
	{
		ptr=ptr->next;
	}
	//输出
	puts("逆序链表现有数据：");
	while(ptr!=headptr)
	{
		printf("%d ",ptr->data);
		ptr=ptr->front;
	}
	putchar(10);
	return SUCCESS;
}

//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata)
{
	//定义链表指针和普通节点指针
	linklistptr ptr=NULL,comptr=NULL;
	//判断头是否为null
	if(headptr==NULL)
	{
		return FAULSE;
	}
	//找尾部
	ptr=headptr;
	while(ptr->next)
	{
		ptr=ptr->next;
	}
	//初始化普通节点
	comptr=LinklistComnodeApply(nwedata);
	//判断申请是否成功
	if(comptr==NULL)
	{
		return FAULSE;
	}
	//尾插
	ptr->next=comptr;
	comptr->front=ptr;
	//个数自增
	headptr->len++;
	return SUCCESS;
}
//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr)
{
	//定义链表指针和将删节点指针
	linklistptr deltr=NULL,ptr=NULL;
	//判断头是否为null
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//找到要删除的数据第一个节点
	deltr=headptr->next;
	//头删
	headptr->next=deltr->next;
	//判断是否只有一个节点
	if(deltr->next)
	{
		deltr->next->front=headptr;
	}
	free(deltr);
	deltr=NULL;
	//个数自减
	headptr->len--;
	return SUCCESS;
}

//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr)
{
	//定义链表指针和将删节点指针
	linklistptr deltr=NULL,ptr=NULL;
	//判断头是否为null
	if(headptr==NULL||headptr->len==0)
	{
		return FAULSE;
	}
	//找尾部
	ptr=headptr;
	while(ptr->next)
	{
		ptr=ptr->next;
	}
	ptr->front->next=NULL;
	free(ptr);
	ptr=NULL;
	headptr->len--;
	return SUCCESS;
}

//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata)
{
	//定义循环变量
	int i;
	//定义链表指针和普通节点指针
	linklistptr ptr=NULL,comptr=NULL;
	//判断头是否为NULL
	//判断位置是否合法
	if(headptr==NULL||seat<=0||seat>headptr->len+1)
	{
		return FAULSE;
	}
	//找到对应位置的前一个位置
	ptr=headptr;
	for(i=0;i<seat-1;i++)
	{
		ptr=ptr->next;
	}
	//初始化普通节点
	comptr=LinklistComnodeApply(nwedata);
	//
	if(comptr==NULL)
	{
		return FAULSE;
	}
	//插入
	comptr->next=ptr->next;
	comptr->front=ptr;
	if(ptr->next!=NULL)
	{
		ptr->next->front=comptr;
	}
	ptr->next=comptr;
	headptr->len++;
	return SUCCESS;
}

//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat)
{
	//定义循环变量
	int i;
	//定义链表指针和将删节点指针
	linklistptr deltr=NULL,ptr=NULL;
	//判断是否为NULL
	//判断链表是否为空
	//判断位置是否合法
	if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len)
	{
		return FAULSE;
	}
	//找到对应位置的前一个位置
	ptr=headptr;
	for(i=0;i<seat-1;i++)
	{
		ptr=ptr->next;
	}
	deltr=ptr->next;
	ptr->next=deltr->next;
	if(deltr->next!=NULL)
	{
		deltr->next->front=deltr->front;
	}
	free(deltr);
	deltr=NULL;
	headptr->len--;
	return SUCCESS;
}

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

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

运行示例：


2.牛客网刷题

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布