C语言中双链表的基本操作
目录
- 带头结点的双向循环链表
- 基本操作
- 创建
- 销毁
- 打印
- 尾插法
- 尾删
- 头插
- 头删
- 查找元素位置
- 任意位置插入
- 任意位置删除
- 完整代码及测试
- 总结
带头结点的双向循环链表
链表结构如下:
每个节点都有一个数据域和两个指针域,这两个指针分别指向链表的前驱节点和后继节点,头节点的前驱节点是链表的最后一个节点,链表最后一个节点的后继节点是头节点。
正因为如此,带头结点的双向循环链表没有空节点,在进行遍历时,循环条件也与单链表不同:
单链表用cur->next为空判断当前节点是否为最后一个节点,带头的双向循环链表则需判断cur->next是否等于头节点。
定义:
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; }
销毁
使用链表时会申请内存空间,所使用完毕后要进行释放,避免内存泄漏,这里销毁链表用了头删的思想,每次删除链表中的第一个节点并释放空间,具体过程如图:
循环执行上述过程,直到链表为空,最后再释放头节点空间。
程序如下:
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指向新节点
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节点从链表中移除出来,最后一步则释放内存空间
- 如图:
程序
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
程序
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指向头节点,成为新的第一个节点
- 释放删除节点的空间
程序
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指向新节点
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占用的内存空间
程序
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; }
测试结果:
总结
以上为个人经验,希望开发者_JS培训能给大家一个参考,也希望大家多多支持我们。
精彩评论