[数据结构与算法]带有头节点的双链表

#include<bits/stdc++.h>
using namespace std;
//带有头节点的双链表

struct LNode{
	int data;
	LNode *next;
	LNode *prior;	
}; 

//初始化链表
void InitList(LNode * &L){
	
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	L->prior=NULL;
	
}

//判断链表是否为空
bool isEmpty(LNode *L){
	if(L->next==NULL)
		return true;
	else 
		return false;
} 

//插入节点
void ListInsert(LNode * &L,int i,int value){
	
	if(i<1){
		cout<<"插入位置不合法"<<endl;
		return;
	}
	
	LNode *p=L;
	LNode *t=(LNode *)malloc(sizeof(LNode));
	int j=0;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL){
		cout<<"插入位置不合法"<<endl;
		return;
	}
	
	t->data=value;
	t->next=p->next;
	if(p->next!=NULL) //避免要插入的位置后面没有节点为空而产生错误 
		p->next->prior=t;
	p->next=t;
	t->prior=p;
	printf("%d插入成功\n",value);
}


//删除节点
void ListDelete(LNode * &L,int i){
	
	if(i<1){
		cout<<"删除位置不合法"<<endl;
		return;
	}
	
	LNode *p=L;
	int j=0;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	
	if(p==NULL||p->next==NULL){
		cout<<"删除位置不合法"<<endl;
		return;
	}
	
	if(p->next->next!=NULL) //避免要删除的节点后面没有节点为空而产生错误 
		p->next->next->prior=p;
	p->next=p->next->next;
	printf("第%d个节点删除成功\n",i); 
}


//修改节点
void ListUpdate(LNode * &L,int i,int value){

    if(i<1){
        cout<<"修改位置不合法"<<endl;
        return ;
    }

    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }

    if(p==NULL){
        cout<<"修改位置不合法"<<endl;
        return ;
    }

    p->data=value;
    printf("第%d个节点的数据修改为：%d\n",i,value); 
}


//查找节点
void GetElem(LNode *L,int i){

    if(i<1){
        cout<<"查找位置不合法"<<endl;
        return;
    }

    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }

    if(p==NULL){
        cout<<"查找位置不合法"<<endl;
        return;
    }

    int value=p->data;
    printf("查找成功，第%d个节点元素为：%d\n",i,value);
}


//遍历链表 
void ListShow(LNode * &L){

    LNode *T=L->next;
    while(T!=NULL){
        cout<<T->data<<" ";
        T=T->next;
    }
    cout<<endl;
}

int main(){
	
	LNode *L; //定义一个节点指针 
	
	InitList(L); //初始化链表 
	
	isEmpty(L)?cout<<"空"<<endl:cout<<"非空"<<endl; //判断链表是否为空 
	
	ListInsert(L,1,5); //插入节点 
	ListInsert(L,2,6);
	ListInsert(L,3,3);
	ListInsert(L,1,8);
	ListInsert(L,2,2);
	ListInsert(L,3,9);
	
	ListShow(L); //遍历链表 
	
	ListDelete(L,1); //删除节点
    ListDelete(L,9);
    ListDelete(L,4);

    ListShow(L); //遍历节点

    GetElem(L,1); //查找节点
    GetElem(L,2);
    GetElem(L,9);

    ListUpdate(L,1,6); //修改节点
    ListUpdate(L,3,9);
    ListUpdate(L,8,6);

    ListShow(L); //遍历节点
	
	isEmpty(L)?cout<<"空"<<endl:cout<<"非空"<<endl; //判断链表是否为空 
	
	return 0;
}