双向链表相关代码

DLinkList.h

//
//  DLinkList.hpp
//  FirstP
//
//  Created by 赫赫 on 2023/10/31.
//  双向链表相关代码：双向链表、循环双向链表#ifndef DLinkList_hpp
#define DLinkList_hpp
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;#endif /* DLinkList_hpp *///双向链表结构体定义
typedef struct DLNode{int data;struct DLNode *prior,*next;
}DLNode,*DLinkList;
//DLNode *DL;
//DLinkList L;//初始化双向链表
bool initDList(DLinkList &L);//在已知的p结点后面插入newnode
bool InsertNextDNode(DLNode *p,DLNode *newnode);//在已知的p结点后面删除一个结点
bool DeleteNextDNode(DLNode *p);//简要的遍历操作
void findDNode(DLinkList &L);//------------------------------------------
//初始化循环双向链表
bool initCycleDLinkList(DLinkList &L);//判断循环双向链表为空
bool Empty(DLinkList &L);//循环双向链表中在已知结点p后面插入新节点
bool InsertNextDNodeCycle(DLNode *p,DLNode *newnode);//循环双向链表中删除已知结点p
bool DeleteDNodeCycle(DLNode *p);

DLinkList.cpp

//
//  DLinkList.cpp
//  FirstP
//
//  Created by 赫赫 on 2023/10/31.
//#include "DLinkList.hpp"//初始化双向链表
bool initDList(DLinkList &L){//创建头结点L=(DLNode *)malloc(sizeof(DLNode));if(L==NULL){//内存不足，创建失败return false;}L->prior=NULL;//头结点的前驱指针永远指向NULLL->next=NULL;return true;
}//在已知的p结点后面插入newnode
bool InsertNextDNode(DLNode *p,DLNode *newnode){if(p==NULL||newnode==NULL){return false;}//结点插入操作newnode->next=p->next;newnode->prior=p;if(p->next!=NULL){p->next->prior=newnode;}p->next=newnode;return true;
}//在已知的p结点后面删除一个结点
bool DeleteNextDNode(DLNode *p){if(p==NULL){return false;}DLNode *q=p->next;if(q==NULL){return false;}p->next=q->next;if(q->next!=NULL){q->next->prior=p;}free(q);return true;
}//简要的遍历操作
void findDNode(DLinkList &L){DLNode *p=L;//正序遍历while(p!=NULL){p=p->next;}//前向遍历(跳过对头结点的操作)while(p->prior!=NULL){p=p->prior;}//前向遍历(不带头结点的包含对头结点的操作)while(p!=NULL){p=p->prior;}
}//------------------------------------------
//初始化循环双向链表
bool initCycleDLinkList(DLinkList &L){L=(DLNode*)malloc(sizeof(DLNode));if(L==NULL){return false;}L->prior=L;L->next=L;return true;
}//判断循环双向链表为空
bool Empty(DLinkList &L){if(L->next==L){return true;}else{return false;}
}//循环双向链表中在已知结点p后面插入新节点
bool InsertNextDNodeCycle(DLNode *p,DLNode *newnode){if(p==NULL||newnode==NULL){return false;}newnode->next=p->next;p->next->prior=newnode;newnode->prior=p;p->next=newnode;return true;
}//循环双向链表中删除已知结点p
bool DeleteDNodeCycle(DLNode *p){if(p==NULL){return false;}//这里删除的是头结点也同样适用，并没指明头结点在哪p->prior->next=p->next;if(p->next!=NULL){p->next->prior=p->prior;}return true;
}