内容导读
2.12双链表的元素查找,若找到目的值i则返回其地址pos,否则返回NULL
2.13双链表的元素查找修改,若找到目的值i则将i修改成e,并返回其地址,否则返回NULL
1.什么是双链表
1.1 双链表概述
在线性表的链式存储结构中,每个物理结点增加一个指向后继结点的指针域(后指针)和一个指向前驱结点的指针域(前指针) ->双链表。
举个栗子:带头结点双链表结构
1.2循环链表
循环链表是另一种形式的链式存储结构形式。
所以说双链表的形式就会有多种啦,比如循环双链表,带头结点的双链表,带头结点的循环双链表,带头结点的双链表等等。不过本质都是一样的,只需要学会任意一种,其他的只要注意一些不同的细节也能轻松实现。
1.3 双链表的优点
- 从任一结点出发可以快速找到其前驱结点和后继结点;
- 从任一结点出发可以访问其他结点。
双链表相比于单链表来说,双链表能够从任何一个结点访问其他任意结点,而单链表只能单方向访问下一个结点。虽然双链表的结构较比与单链表要复杂,但是双链表的操作要相比于单链表简单。
在本文中,双链表所有实现方式以带头结点的循环双链表为基础实现。
2.双链表的定义以及常见功能的实现
2.0双链表定义以及常见功能头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ListType;
typedef struct ListNode //声明双链表结点结构
{
ListType data; //存储数据:data
struct ListNode* prev; //指向前驱结点:前指针
struct ListNode* next; //指向后继结点:后指针
}ListNode;
//实现双链表增删查改接口
//双链表的初始化
ListNode* ListInit();
//双链表的打印
void ListPrint(ListNode* phead);
//双链表的头插
void ListPushFront(ListNode* phead,ListType x);
//双链表的头删
void ListPopFront(ListNode* phead);
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x);
//双链表的尾删
void ListPopBack(ListNode* phead);
//双链表结点的扩容
ListNode* BuyListNode(ListType x);
//双链表的位置pos(已知)前插入
void ListInsert( ListNode* pos, ListType x);
//双链表的位置pos(已知)删除
void ListErase( ListNode* pos);
//双链表的元素查找,若找到目的值i则返回其地址pos,否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i);
//双链表的元素查找修改,若找到目的值i则将i修改成e,并返回其地址,否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e);
2.1双链表定义(声明)
对于双链表,采用类似于单链表的类型定义,其结点类型ListNode声明如下:
typedef int ListType;
typedef struct ListNode //声明双链表结点结构
{
ListType data; //存储数据:data
struct ListNode* prev; //指向前驱结点:前指针
struct ListNode* next; //指向后继结点:后指针
}ListNode;
2.2双链表内存申请及扩容
//双链表结点申请及扩容
ListNode* BuyListNode(ListType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); //新结点内存申请
if (newNode == NULL) {
printf("申请内存失败!");
return NULL;
}
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = x;
return newNode; //将新申请的结点的前后指针置空,存入数据,返回新结点的地址
}
2.3双链表初始化
//双链表的初始化
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0); //申请新结点作为头指针
phead->next = phead; //初始化的双链表前后指针均指向本身
phead->prev = phead;
return phead; //返回指针地址
}
2.4双链表的打印
需要打印双链表中的每个数据,就需要遍历整个双链表,需要遍历双链表,那就要找到遍历双链表的条件,由于我是以带头结点的循环双链表为基础,那么遍历终结的条件不是指向NULL,而是指向头结点地址,因为当遍历完一次后,指针就会指向初始结点。
//双链表的打印
void ListPrint(ListNode* phead)
{
assert(phead); //判断传入的地址是否为空,为空强制结束程序
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
2.5双链表的插入与删除操作理论
双链表插入操作
双链表删除操作
2.6双链表头插操作代码实现
双链表的头插相当于在第一个数据前插入
//双链表的头插
void ListPushFront(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* next = phead->next; //保存第一个数据地址
phead->next = newNode;
newNode->prev = phead;
next->prev = newNode;
newNode->next = next;
}
2.7双链表尾插操作代码实现
双链表的尾插相当于在头结点前插入
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* tail = phead->prev; //保存最后一个数据地址
phead->prev = newNode;
newNode->next = phead;
tail->next = newNode;
newNode->prev = tail;
}
2.8双链表的位置pos(已知)前插入操作代码实现
//双链表的位置pos(已知)前插入
void ListInsert(ListNode* pos, ListType x)
{
assert(pos);
ListNode* newNode= BuyListNode(x);
ListNode* posPrev = pos->prev;
pos->prev = newNode;
newNode->next = pos;
posPrev->next = newNode;
newNode->prev = posPrev;
}
2.9双链表的头删操作代码实现
双链表头删相当于删除第一个数据
//双链表的头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}
2.10双链表尾删操作代码实现
双链表尾删相当于删除最后一个数据
//双链表的尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
}
2.11双链表的位置pos(已知)删除操作代码实现
//双链表的位置pos(已知)删除
void ListErase( ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
}
2.12双链表的元素查找,若找到目的值i则返回其地址pos,否则返回NULL
//双链表的元素查找,若找到目的值i则返回其地址pos,否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
return cur;
cur = cur->next;
}
return NULL;
}
2.13双链表的元素查找修改,若找到目的值i则将i修改成e,并返回其地址,否则返回NULL
//双链表的元素查找修改,若找到目的值i则将i修改成e,并返回其地址,否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
{
cur->data = e;
return cur;
}
cur = cur->next;
}
return NULL;
}
终:代码合集
#include "List.h"
//双链表的初始化
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//双链表的打印
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//双链表的头插
void ListPushFront(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* next = phead->next;
phead->next = newNode;
newNode->prev = phead;
next->prev = newNode;
newNode->next = next;
}
//双链表的头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
}
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x)
{
assert(phead);
ListNode* newNode = BuyListNode(x);
ListNode* tail = phead->prev;
phead->prev = newNode;
newNode->next = phead;
tail->next = newNode;
newNode->prev = tail;
}
//双链表的尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != NULL);
ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
}
//双链表结点的扩容
ListNode* BuyListNode(ListType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) {
printf("申请内存失败!");
return NULL;
}
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = x;
return newNode;
}
//双链表的位置pos(已知)前插入
void ListInsert(ListNode* pos, ListType x)
{
assert(pos);
ListNode* newNode= BuyListNode(x);
ListNode* posPrev = pos->prev;
pos->prev = newNode;
newNode->next = pos;
posPrev->next = newNode;
newNode->prev = posPrev;
}
//双链表的位置pos(已知)删除
void ListErase( ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
}
//双链表的元素查找,若找到目的值i则返回其地址pos,否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
return cur;
cur = cur->next;
}
return NULL;
}
//双链表的元素查找修改,若找到目的值i则将i修改成e,并返回其地址,否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
if (cur->data == i)
{
cur->data = e;
return cur;
}
cur = cur->next;
}
return NULL;
}