首页 > 其他分享 >双向链表的实现

双向链表的实现

时间：2024-08-02 15:54:16浏览次数：22  
标签：实现 next 链表 LTNode phead 双向 newnode prev plist

1、双向链表示意图

 

2、双向链表实现

（1）结构体定义

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;	
}LTNode;

（2）初始化

/****************初始化*****************/
LTNode* ListInit(LTNode* phead)
{
	//哨兵位头结点 
	phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead; 	
}

（3）打印数据

/****************打印*****************/
void ListPrint(LTNode* phead)
{
	assert(phead); 
	LTNode* cur = phead->next;//跳过头结点，头结点无数据 
	while(cur != phead)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}
	printf("\n");
}

（4）开辟内存

/****************开辟内存*****************/
LTNode* ListCreat(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;	
	
	return newnode; 	
}

（5）销毁内存

/****************销毁内存*****************/
void ListDestroy(LTNode* phead)
{
	assert(phead); 
	LTNode* cur = phead->next;
	while(cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

（6）尾插

/*****************尾插*****************/
void ListPushBack(LTNode* phead,LTDataType x)
{
	assert(phead); 
	LTNode* newnode = ListCreat(x);
	
	//phead->prev尾，找尾 
	LTNode* tail = phead->prev;
	
	//链接 
	tail->next = newnode;
	newnode->prev = tail;
	
	newnode->next = phead;
	phead->prev = newnode;	
	
	//第二种方法：ListInsertBefore(phead,x); 		
}

（7）尾删

/*****************尾删*****************/
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//链表为空不能删除，保留头结点 
	//找尾 
	LTNode* tail = phead->prev;
	
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
	
	//第二种方法；ListErase(phead->prev); 	
}

（8）头插

/*****************头插*****************/
void ListPushFront(LTNode* phead,LTDataType x)
{
	assert(phead); 
	LTNode* newnode = ListCreat(x);
	
	//phead->next头，找头 
	LTNode* head = phead->next;
	
	//链接
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = head;
	head->prev = newnode;
	
	//第二种方法；ListInsertBefore(phead->next,x);				
}

（9）头删

/*****************头删*****************/
void ListPopFront(LTNode* phead)
{
	assert(phead); 
	assert(phead->next != phead);//链表为空不能删除，保留头结点
	//找头 
	LTNode* head = phead->next;

	phead->next = head->next;
	head->next->prev = phead;  
	free(head);	
	
	//第二种方法；ListErase(phead->next); 
		
}

（10）查找

/*****************查找 *****************/
LTNode* ListFind(LTNode* phead,LTDataType x)
{
	assert(phead);
	
	LTNode* cur = phead->next;
	while(cur!= phead)
	{
		if(cur->data == x)
		{
			return cur;
		} 
		cur = cur->next;
	}	
	
	return NULL;//没有找到 
}

（11）指定位置插入

/*****************指定位置之前插入*****************/
void ListInsertBefore(LTNode* pos,LTDataType x) 
{
	assert(pos); 
	LTNode* newnode = ListCreat(x);
	LTNode* last = pos->prev;//保存前一个 
	
	last->next = newnode;
	newnode->prev = last;
	
	newnode->next = pos;
	pos->prev = newnode;		
}


/*****************指定位置之后插入 *****************/
void ListInsertAfter(LTNode* pos,LTDataType x)
{
	assert(pos); 
	LTNode* newnode = ListCreat(x);
	LTNode* Next = pos->next;//保存后一个 
	
	pos->next = newnode;
	newnode->prev = pos;
	
	newnode->next = Next;
	Next->prev = newnode;	
}

（12）指定位置删除

/*****************指定位置删除*****************/
void ListErase(LTNode* pos)
{
	assert(pos); 
	LTNode* Last = pos->prev;//保存前一个 
	LTNode* Next = pos->next;//保存后一个 
	
	Last->next = Next;
	Next->prev = Last;
	free(pos);
}

3、函数

（1）main.c

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



void ListTest1()
{
	LTNode* plist = ListInit(plist);
	
	//尾插 
	ListPushBack(plist,1);
	ListPushBack(plist,2);
	ListPushBack(plist,3);
	ListPushBack(plist,4);
	ListPrint(plist);
	
	//尾删 
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	
	//头插 
	ListPushFront(plist,1);
	ListPushFront(plist,2);
	ListPushFront(plist,3);
	ListPushFront(plist,4);
	ListPrint(plist);
	
	//头删 
	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	
	//销毁链表 
	ListDestroy(plist);
	plist = NULL;
}



void ListTest2()
{
	LTNode* plist = ListInit(plist);
	
	//尾插 
	ListPushBack(plist,1);
	ListPushBack(plist,2);
	ListPushBack(plist,3);
	ListPushBack(plist,4);
	ListPushBack(plist,3);
	ListPushBack(plist,2);
	ListPrint(plist);
	
	//找到并删除  
	LTNode* pos = ListFind(plist,3);
	while(pos != NULL)
	{
		 ListErase(pos);
		 pos = ListFind(plist,3); 
	}
	ListPrint(plist); 
	
	//找到并改变  
	LTNode* pos1 = ListFind(plist,2);
	while(pos1 != NULL)
	{
		 pos1->data = 7;
		 pos1 = ListFind(plist,2); 
	}
	ListPrint(plist); 
	
	ListDestroy(plist);
	plist = NULL; 
}



int main(int argc, char *argv[]) 
{
	//ListTest1();
	ListTest2();
	return 0;
}

（2）List.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h> 
#include "List.h"



/****************初始化*****************/
LTNode* ListInit(LTNode* phead)
{
	//哨兵位头结点 
	phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead; 	
}



/****************打印*****************/
void ListPrint(LTNode* phead)
{
	assert(phead); 
	LTNode* cur = phead->next;//跳过头结点，头结点无数据 
	while(cur != phead)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}
	printf("\n");
}



/****************开辟内存*****************/
LTNode* ListCreat(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;	
	
	return newnode; 	
}



/****************销毁内存*****************/
void ListDestroy(LTNode* phead)
{
	assert(phead); 
	LTNode* cur = phead->next;
	while(cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}


 
/*****************尾插*****************/
void ListPushBack(LTNode* phead,LTDataType x)
{
	assert(phead); 
	LTNode* newnode = ListCreat(x);
	
	//phead->prev尾，找尾 
	LTNode* tail = phead->prev;
	
	//链接 
	tail->next = newnode;
	newnode->prev = tail;
	
	newnode->next = phead;
	phead->prev = newnode;	
	
	//第二种方法：ListInsertBefore(phead,x); 		
}



/*****************头插*****************/
void ListPushFront(LTNode* phead,LTDataType x)
{
	assert(phead); 
	LTNode* newnode = ListCreat(x);
	
	//phead->next头，找头 
	LTNode* head = phead->next;
	
	//链接
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = head;
	head->prev = newnode;
	
	//第二种方法；ListInsertBefore(phead->next,x);				
}



/*****************尾删*****************/
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//链表为空不能删除，保留头结点 
	//找尾 
	LTNode* tail = phead->prev;
	
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
	
	//第二种方法；ListErase(phead->prev); 	
} 



/*****************头删*****************/
void ListPopFront(LTNode* phead)
{
	assert(phead); 
	assert(phead->next != phead);//链表为空不能删除，保留头结点
	//找头 
	LTNode* head = phead->next;

	phead->next = head->next;
	head->next->prev = phead;  
	free(head);	
	
	//第二种方法；ListErase(phead->next); 
		
} 



/*****************查找 *****************/
LTNode* ListFind(LTNode* phead,LTDataType x)
{
	assert(phead);
	
	LTNode* cur = phead->next;
	while(cur!= phead)
	{
		if(cur->data == x)
		{
			return cur;
		} 
		cur = cur->next;
	}	
	
	return NULL;//没有找到 
}



/*****************指定位置之前插入*****************/
void ListInsertBefore(LTNode* pos,LTDataType x) 
{
	assert(pos); 
	LTNode* newnode = ListCreat(x);
	LTNode* last = pos->prev;//保存前一个 
	
	last->next = newnode;
	newnode->prev = last;
	
	newnode->next = pos;
	pos->prev = newnode;		
}


/*****************指定位置之后插入 *****************/
void ListInsertAfter(LTNode* pos,LTDataType x)
{
	assert(pos); 
	LTNode* newnode = ListCreat(x);
	LTNode* Next = pos->next;//保存后一个 
	
	pos->next = newnode;
	newnode->prev = pos;
	
	newnode->next = Next;
	Next->prev = newnode;	
}



/*****************指定位置删除*****************/
void ListErase(LTNode* pos)
{
	assert(pos); 
	LTNode* Last = pos->prev;//保存前一个 
	LTNode* Next = pos->next;//保存后一个 
	
	Last->next = Next;
	Next->prev = Last;
	free(pos);
}

（3）List.h

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;	
}LTNode;


LTNode* ListInit(LTNode* phead);//初始化 
void ListPrint(LTNode* phead);//打印 
LTNode* ListCreat(LTDataType x);//开辟内存 
void ListDestroy(LTNode* phead);//销毁内存 

void ListPushBack(LTNode* phead,LTDataType x);//尾插 
void ListPopBack(LTNode* phead);//尾删 

void ListPushFront(LTNode* phead,LTDataType x);//头插 
void ListPopFront(LTNode* phead);//头删 

LTNode* ListFind(LTNode* phead,LTDataType x);//查找 
void ListErase(LTNode* pos);//指定位置删除 

void ListInsertBefore(LTNode* pos,LTDataType x);//指定位置之前插入 
void ListInsertAfter(LTNode* pos,LTDataType x);//指定位置之后插入

标签：实现,next,链表,LTNode,phead,双向,newnode,prev,plist
From： https://blog.csdn.net/qq_63057731/article/details/140871874

相关文章

  • HarmonyOS：如何实现自定义的Tabs,TabContent内部实现如何动态配置
    前言：最近做开发任务的时候，想把Tabs自定义了，并且动态配置TabContent里面的内容，不是写死一样的，这个问题困扰了很长时间，试过**@BuilderParam**（类似于vue的插槽）传组件方式的，但是**@BuilderParam只能传一个，我想要传递的是一个数组，找了很多Api最后找到了WrappedBuilder[]**这种方......
  • JAVA中实现队列和栈（Deque接口和ArrayDeque类）
    用什么来实现队列和栈首先JAVA中有一个Queue接口，用来实现队列。Deque其实就是双端队列，代表两端都可进可出的队列。ArrayDeque就是用数组来实现这个双端队列。（Deque由于是接口，只可以用于声明对象，但是没办法实例化，实例化还是要使用ArrayDeque类）这时可能就会产生疑惑，队列有了，......
  • iis安装数字证书ssl并实现http跳转https的301重定向
    iis安装数字证书ssl并实现http跳转https的301重定向为了增强网站的安全性，实现域名访问从HTTP自动跳转到HTTPS，您可以按照以下步骤操作：安装SSL证书：首先，您需要为您的网站获取一个SSL证书。这可以通过向证书颁发机构（CA）申请免费的证书（如Let'sEncrypt提供的证书）或购买商业证书来完成......
  • 为什么我在 Python 中的 Skip-Gram 实现会产生不正确的结果？
    我正在使用Python实现Word2Vec的Skip-Gram模型。然而，正如生成的嵌入及其可视化所示，我的模型似乎无法正常工作。这是嵌入的3D图的示例，它显示单词聚集在一起并重叠，因此很难区分它们：我怀疑问题在于我的实现而不是绘图函数。importnumpyasnpfromnltk.corpusimpor......
  • C# .NET ThreadPool 实现概述及
    微信公众平台(qq.com) 在.NET中，ThreadPool（线程池）是一个用于管理和优化线程使用的强大工具。线程池允许开发者在需要时创建线程，执行任务，并在任务完成后回收线程，从而避免了线程的频繁创建和销毁所带来的开销。ThreadPool是.NETFramework和.NETCore中并发编程的核心部分，广泛应......
  • TS中简单实现一下依赖注入
    依赖注入（DependencyInjection，DI）是一种设计模式，主要用于实现控制反转（InversionofControl，IoC）。它通过将对象的依赖关系从内部管理转移到外部容器来解耦组件，从而提高代码的可测试性、可维护性和灵活性。之前在使用nest.js中做开发的时候，被这种模式的简单性吸引，今天自己来使用TS简......
  • 创建一个简单的双链表
    1.ListNode.h头文件#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<string.h>typedefintLTDataType;typedefstructListNode{ structListNode*next; structListNode*prev; LTDataTypedata;}LN;//初始化......
  • 前端使用JS内置Blob实现下载各种形式的文件实例
    在前端开发中，JavaScript的Blob对象允许你创建一个包含原始数据的类文件对象。使用Blob可以轻松实现在客户端生成和下载各种类型的文件，例如文本文件、图片、CSV等。下面是一些使用Blob实现文件下载的示例：1.下载文本文件functiondownloadTextFile(filename,text){c......
  • 【leetcode232:用栈实现队列】
    leetcode232:用栈实现队列题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现MyQueue类：voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头移除并返回元素intpeek()返回队列开头的元素booleanemp......
  • c语言数据结构-单链表
    typedefstructLNode{   Elemtypedata;   structLNode*next;}LNode,*Linklist;//初始化单链表(不带头节点)boolInitList(LinkList&L){   L=NULL;   returntrue;}插入boolListInsert(LinkList&L,inti,Elemtypee){   if(i<1)  ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99