[C++知识库]双链表的插入、删除、查找等操作

#include<iostream>
#include<cstring>
#include <set>
#include <map>
#include <ctime>
#include <bitset>
#include <sstream>
#include <algorithm>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>//getch()的头文件
#include<vector>
#include<queue>
#include<stack>
using namespace std;
// 带头结点的双链表的创建、遍历、删除
typedef struct DNode{
	int data; // 数据域
	struct DNode *prior,*next;// 前驱和后继指针 
}DNode,*DLinkList; 
void isEmpty(DLinkList &L){// 判断双链表是否为空 
	if(L->next==NULL){
		cout<<"当前双链表为空"<<endl;
	}else{
		cout<<"当前双链表非空"<<endl; 
	}
}
bool InsertNextDNode(DNode *p,DNode *s){// 插入后续结点的函数,其中p为任意结点，s为插入结点 
	if(p==NULL||s==NULL){
		return false;
	}
	s->next=p->next;
	if(p->next!=NULL){// 如果p 是最后一个结点 
		p->next->prior=s;
	}
		s->prior=p;
		p->next=s;
	return true;
}
bool DeleteNextNode(DNode *p){// 删除结点p的后继结点的函数,其中p为任意结点 
	if(p==NULL) return false;// 如果这个待删除结点为NULL 返回false 
	DNode *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 ReadDLinkList(DLinkList &L){// 传递的是地址的引用,这里的L为双链表的头接点 
	DNode * M= (DNode*) malloc(sizeof(DNode));// 初始化一个结点指针，并且该结点指针指向头结点L  
	M=L;
	while(M->next!=NULL){
		M=M->next;// 头结点不携带任何数据，因此一开始需要后移 
		cout<<M->data<<"\t";
	}
	cout<<endl;
} 

DLinkList InitDLinkList(DLinkList &L){// 初始化双链表 
	L = (DNode *) malloc(sizeof(DNode));
	if(L==NULL){
		return false;
	}
	L->prior=NULL;// 头结点的前驱永远为NULL 
	L->next=NULL;// 头结点的后继为NULL表示暂时还没有后继元素 
	cout<<"依次输入整形的数据作为双链表的结点数据，并且以-1作为输入结束。"<<endl;
	int data;
	cin>>data;
	DNode * M =(DNode *) malloc(sizeof(DNode));// 这个结点作为L头结点的移动结点
	M=L;// M指向头结点L 
	while(-1!=data){
		DNode *temp = (DNode *) malloc(sizeof(DNode));// 初始化一个结点作为下一个插入结点
		temp->data=data;
		InsertNextDNode(M,temp);// 将这个结点插在M 结点后面
		M=M->next;// 结点M后移 
		cin>>data;
	}
	return L;
}


int GetLinkListLength(DLinkList &L){// 获取链表的长度
if(L->next==NULL)
	return 0;
int length=0;
// 为了不移动头结点，因此需要一个辅助结点来进行移动
DLinkList M=(DNode *) malloc (sizeof(DNode));
M = L;
while(M->next!=NULL){
	M = M->next;
	length++;
} 
return length;
}

void  SearchByPosition(DLinkList &L,int x){// 实现按位查找 
	int length = GetLinkListLength(L);
	if(length==0){
		cout<<"当前双链表的长度为0"<<endl;
		return ;
	}else{
// 为了不移动头结点，因此需要一个辅助结点来进行移动
DLinkList M=(DNode *) malloc (sizeof(DNode));
M = L;
int i =0;
while(x>length){// 如果 
	cout<<"\n查找位置超出链表长度,情重新输入。"<<endl;
cin>>x;
if(x<0){
	cout<<"\n输入非法，输入的值不能小于0，请重新输入。"<<endl;
	cin>>x;
} 
}
while(i<x){
M=M->next;
i++;
}
cout<<M->data;
}
return ;
}
void VerifyValue(DLinkList &L,int value){// 验证值是否在双链表中 
// 为了不移动头结点，因此需要一个辅助结点来进行移动
DLinkList M=(DNode *) malloc (sizeof(DNode));
M = L;
M=M->next;// 因为头结点一开始不携带数据 
while(M->data!=value&&M->next!=NULL){// 如果当前结点的值不为要查找的值，并且存在下一个结点 
M=M->next; 
if(M->data==value){
	cout<<"该值在链表中"<<endl; 
	return ;
}
}
cout<<"该值不在链表中"<<endl;
}



int main()
{	
	DNode *L;// 声明头结点指针L 
	L = InitDLinkList(L);// 初始化这个头结点
	ReadDLinkList(L);
	isEmpty(L);
	cout<<"\n按位查找，请输入要查找的第n个结点的值"<<endl;
	int i;
	cin>>i;
	SearchByPosition(L,i);
	cout<<"\n按值查找，请输入要验证的值"<<endl;
	int j;
	cin>>j;
	VerifyValue(L,j);
	cout<<"\n对双链表进行删除操作…"<<endl;
	while(L->next!=NULL){// 此操作删除了除头结点外的所有后继节点 
		DeleteNextNode(L);
	}
	isEmpty(L);
	free(L);	
	
return 0;
}

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读