开发者

C语言中双链表的基本操作

目录
  • 带头结点的双向循环链表
  • 基本操作
    • 创建
    • 销毁
    • 打印
    • 尾插法
    • 尾删
    • 头插
    • 头删
    • 查找元素位置
    • 任意位置插入
    • 任意位置删除
  • 完整代码及测试
    • 总结

      带头结点的双向循环链表

      链表结构如下:

      每个节点都有一个数据域和两个指针域,这两个指针分别指向链表的前驱节点和后继节点,头节点的前驱节点是链表的最后一个节点,链表最后一个节点的后继节点是头节点。

      正因为如此,带头结点的双向循环链表没有空节点,在进行遍历时,循环条件也与单链表不同:

      单链表用cur->next为空判断当前节点是否为最后一个节点,带头的双向循环链表则需判断cur->next是否等于头节点。

      C语言中双链表的基本操作

      定义:

      typedef int DataType;
      typedef struct ListNode
      {
      	DataType data;//数据域
      	struct ListNode* next;//指向下一个节点
      	struct ListNode* prev;//指向前一个节点
      }ListNode;
      

      基本操作

      创建

      创建链表需要先申请一段内存,然后再进行赋值,这里BuyListNode函数用于申请内存空间,在插入节点时,也需要调用BuyListNode函数。

      申请节点:

      static ListNode* BuyListNode(int x)
      {
      	ListNode* newNode = NULL;
      	newNode = (ListNode*)malloc(sizeof(ListNode));//为节点动态申请一段内存
      	if (NULL == newNode)
      	{
      		assert(0);
      		return NULL;
      	}
      	//为申请的节点赋值
      	newNode->data = x;
      	newNode->next = NULL;
      	newNode->prev = NULL;
      	return newNode;
      }
      

      创建链表:

      ListNode* ListCreate()
      {
      	ListNode*head=BuyListNode(0);//调用申请节点的函数
      	//为头节点指针域赋值,链表为空时,prev和next都指向头节点
      	head->next = head;
      	head->prev = head;
      	return head;
      }
      

      销毁

      使用链表时会申请内存空间,所使用完毕后要进行释放,避免内存泄漏,这里销毁链表用了头删的思想,每次删除链表中的第一个节点并释放空间,具体过程如图:

      C语言中双链表的基本操作

      循环执行上述过程,直到链表为空,最后再释放头节点空间。

      程序如下:

      void ListDestory(ListNode** plist)
      {
      	assert(plist);
      	ListNode* cur = (*plist)->next;
      	while (cur!=(*plist))
      	{
      		(*plist)->next = cur->next;
      		free(cur);
      		cur = (*plist)->next;
      	}
      	free(*plist);
      	*plist = NULL;
      }
      

      这里需要注意的是,销毁链表要改变链表头结点的指向,所以传参时需要传二级指针。在对带头结点的双链表的操作中,只有销毁会改变指向头结点的指针plist的指向,所以只有销毁时需要传二级指针,其余操作传一级指针即可。

      打印

      链表打印的思想比较简单,只需要遍历打印即可。

      程序:

      void ListPrint(ListNode* plist)
      {
      	assert(plist);
      	ListNode* cur = plist->next;
      	while (cur != plist)//遍历的循环条件
      	{
      		printf("%d--->", cur->data);
      		cur = cur->next;
      	}
      	printf("\n");
      }
      

      尾插法

      步骤

      • 申请新节点newNode
      • 对newNode的prev和next进行赋值
      • 使原链表最后一个节点的next指向新节点
      • 链表头指针的prev指向新节点

      C语言中双链表的基本操作

      void ListPushBack(ListNode* plist, DataType x)
      {
      	assert(plist);
      	ListNode* newNode =BuyListNode(x);
      	nwww.devze.comewNode->prev = plist->prev;
      	newNode->next = plist;
      	plist->prev->next = newNode;
      	plist->prev = newNode;
      }
      

      尾删

      删除节点时需要先判断链表是否为空,先写出链表判空的方法

      链表判空

      看plist->next是否等于plist即可判断链表是否为空

      static int IsEmpty(ListNode*plist)
      {
      	assert(plist);
      	if (plist->next == plist)
      	{
      		return 1;//链表为空,返回1
      	}
      	return 0;//链表非空,返回0
      }
      

      尾删法

      步骤

      • 用del标记最后一个节点
      • 使del前一qKOaNQG个节点的next指向头节点
      • 头结点的prev指向del的前一个节点
      • 释放del的空间
      • 这里中间两步将del节点从链表中移除出来,最后一步则释放内存空间
      • 如图:

      C语言中双链表的基本操作

      程序

      void ListPopBack(ListNode * plist)
      {
      	assert(plist);
      	if (IsEmpty(plist))
      	{
      		return;
      	}
      	ListNode* del = plist->prev;
      	del->prev->next = plist;
      	plist->prev = del->prev;
      	free(del);
      	del = NULL;
      }
      

      头插

      步骤

      • 申请新节点newNode
      • 使新节点的prev指向头节点
      • 令新节点的next指向原来链表第二个节点
      • 令原来第二个节点的prev指向newNode
      • 令头节点的next指向newNode

      C语言中双链表的基本操作

      程序

      void ListPushFront(ListNode* plist, DataType x)
      {
      	assert(plist);
      	ListNode* newNode = BuyListNode(0);
      	newNode->prev = plist;
      	newNode->next = plist->next;
      
      	plist->next->prev = newNode;
      	plist->next = newNode;
      }
      
      

      头删

      • 用del标记链表的第一个节点
      • 令头结点的next指向del->next
      • 原链表中第二个节点的prev指向头节点,成为新的第一个节点
      • 释放删除节点的空间

      C语言中双链表的基本操作

      程序

      void ListPopFront(ListNode* plist)
      {
      	assert(plist);
      	if (IsEmpty(plist))//先判空
      	{
      		return;
      	}
      	ListNode* del = plist->next;
      
      	plist->next = del->next;
      	del->next->prev = plist;
      
      	free(del);
      	del = NULL;
      }
      

      查找元素位置

      对链表进行遍历,比对,找到与目标值相等的数时,返回当前的地址

      ListNode* ListFind(ListNode* plist, DataType x)
      {
      	assert(plist);
      	ListNode* cur = plist->next;
      	while (cur != plist)
      	{
      		if (cur->data == x)
      		{
      			return cur;
      		}
      		cur = cur->next;
      	}
      	return NULL;
      }
      

      任意位置插入

      由于双链表有两个指针域,所以可以在pos位置的前面进行插入

      步骤

      • 申请一个新节点newNode
      • 为新节点的prev和next赋值,使其分别指向pos的前一个节点和pos
      • 使原来pos前一个节点的next指向新节点
      • 令pos的prev指向新节点

      C语言中双链表的基本操作

      void ListInsert(ListNode* pos, DataType x)
      {
      	assert(pos);
      	ListNode* newNode = BuyListNode(x);
      	//在pos前面插入
      	newNode->prev = pos->prev;
      	newNode->next = pos;
      
      	pos->prev->next = newNode;
      	pos->prev = newNode;
      }
      

      任意位置删除

      删除给定的节点pos

      • pos前一个节点的next指向pos的下一个节点
      • pos下一个节点的prev指向pos的前一个节点
      • 释放pos占用的内存空间

      C语言中双链表的基本操作

      程序

      void ListErase(ListNode* pos)
      {
      	assert(pos);
      	pos->prev->next = pos->next;
      	pos->next->prev = pos->prev;
      	free(pos);
      	pos = NULL;	
      }
      

      完整代码及测试

      work.h

      #pragma once
      #include<stdio.h>
      #include<stdlib.h>
      #include<assert.h>
      #include<Windows.h>
      typedef int DataType;
      typedef struct ListNode
      {
      	DataType data;
      	struct ListNode* next;
      	struct ListNode* prev;
      }ListNode;
      
      ListNode* ListCreate();// 创建返回链表的头结点.
      void ListDestory(ListNode** plist);// 双向链表销毁
      void ListPrint(ListNode* plist);// 双向链表打印
      void ListPushBack(ListNode* plist, DataType x);// 双向链表尾插
      void ListPopBack(ListNode* plist);// 双向链表尾删
      void ListPushFront(ListNode* plist, DataType x);// 双向链表头插
      void ListPopFront(ListNode* plist);// 双向链表头删
      ListNode* ListFind(ListNode* plist, DataType x);// 双向链表查找
      void ListInsert(ListNode* pos, DataType x);// 双向链表在pos的前面进行插入
      void ListErase(ListNode* pos);// 双向链表删除pos位置的节点
      

      work.c

      #include"work.h"
      
      //申请节点
      static ListN编程客栈ode* BuyListNode(int x)
      {
      	ListNode* newNode = NULL;
      	newNode = (ListNode*)malloc(sizeof(ListNode));//为节点动态申请一段内存
      	if (NULL == newNode)
      	{
      		assert(0);
      		return NULL;
      	}
      	//为申请的节点赋值
      	newNode->data = x;
      	newNode->next = NULL;
      	newNode->prev = NULL;
      	return newNode;
      }
      
      
      //创建链表
      ListNode* ListCreate()
      {
      	ListNode*head=BuyListNode(0);//调用申请节点的函数
      	//为头节点指针域赋值,链表为空时,prev和next都指向头节点
      	head->next = head;
      	head->prev = head;
      	return head;
      }
      
      //销毁链表
      void ListDestory(ListNode** plist)
      {
      	assert(plist);
      	ListNode* cur = (*plist)->next;
      	while (cur!=(*plist))
      	{
      		(*plist)->next = cur->next;
      		free(cur);
      		cur = (*plist)->next;
      	}
      	free(*plist);
      	*plist = NULL;
      }
      
      // 打印链表
      void ListPrint(ListNode* plist)
      {
      	assert(plist);
      	ListNode* cur = plist->next;
      	while (cur != plist)
      	{
      		printf("%d--->", cur->data);
      		cur = cur->next;
      	}
      	printf("\n");
      }
      
      //尾插法
      void ListPushBack(ListNode* plist, DataType x)
      {
      	assert(plist);
      	ListNode* newNode =BuyListNode(x);
      	newNode->prev = plist->prev;
      	newNode->next = plist;
      	plist->prev->next = newNode;
      	plist->prev = newNode;
      }
      
      //判断链表是否为空
      static int IsEmpty(ListNode*plist)
      {
      	assert(plist);
      	if (plist->next == plist)
      	{
      		return 1;
      	}
      	return 0;
      }
      
      // 尾删法
      void ListPopBack(ListNode * plist)
      {
      	assert(plist);
      	if (IsEmpty(plist))
      	{
      		return;
      	}
      	ListNode* del = plist->prev;
      	del->prev->next = plist;
      	plist->prev = del->prev;
      	free(del);
      	del = NULL;
      }
      
      // 双向链表头插
      void ListPushFront(ListNode* plist, DataType x)
      {
      	assert(plist);
      	ListNode* newNode = BuyListNode(0);
      	newNode->prev = plist;
      	newNode->next = plist->next;
      
      	plist->next->prev = newNode;
      	plist->next = newNode;
      }
      
      // 双向链表头删
      void ListPopFront(ListNode* plist)
      {
      	assert(plist);
      	if (IsEmpty(plist))
      	{
      		return;
      	}
      	ListNode* del = plist->next;
      
      	plist->next = del->next;
      	del->next->prev = plist;
      
      	free(del);
      	del = NULL;
      }
      
      // 查找元素位置
      ListNode* ListFind(ListNode* plist, DataType x)
      {
      	assert(plist);
      	ListNode* cur = plist->next;
      	while (cur != plist)
      	{
      		if (cur->data == x)
      		{
      			return cur;
      		}
      		cur = cur->next;
      	}
      	return NULL;
      }
      
      // 任意位置插入
      void ListInsert(ListNode* pos, DataType x)
      {
      	assert(pos);
      	ListNode* newNode = BuyListNode(x);
      	//在pos前面插入
      	newNode->prev = pos->prev;
      	newNode->next = pos;
      
      	pos->prev->next = newNode;
      	pos->prev = newNode;
      }
      
      //任意位置删除
      void ListErase(ListNode* pos)
      {
      	assert(pos);
      	pos->prev->androidnext = pos->next;
      	pos->next->prev = pos->prev;
      	free(pos);
      	pos = NULL;
      	
      }
      

      main.c

      #include"work.h"
      int mapythonin()
      {
      	ListNode*plist= ListCreate();//创建一个双向非循环链表
      
          //尾插五个节点
      	ListPushBack(plist, 1);
      	ListPushBack(plist, 2);
      	ListPushBack(plist, 3);
      	ListPushBack(plist, 4);
      	ListPushBack(plist, 5);
      	ListPrint(plist);
          //头插一个节点
      	ListPushFront(plist, 0);
      	ListPrint(plist);
          //尾删一个节点
      	ListPopBack(plist);
      	ListPrint(plist);
          //头删一个节点
      	ListPopFront(plist);
      	ListPrint(plist);
          //在元素3前面插入一个节点
      	ListInsert(ListFind(plist,3),9);
      	ListPrint(plist);
          //删除值为9的节点
      	ListErase(ListFind(plist,9));
      	ListPrint(plist);
          //销毁链表
      	ListDestory(&plist);
      	system("pause");
      	return 0;
      }
      

      测试结果:

      C语言中双链表的基本操作

      总结

      以上为个人经验,希望开发者_JS培训能给大家一个参考,也希望大家多多支持我们。

      0

      上一篇:

      下一篇:

      精彩评论

      暂无评论...
      验证码 换一张
      取 消

      最新开发

      开发排行榜