C++双向链表的实现

深藏阁楼爱情的钟 2022-05-26 05:20 187阅读 0赞

用C++实现双向链表代码如下：

//双向链表 
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    struct node{
    	int data1;
    	node *next;
    	node *prior; 
    }; 
    class singlelink{
    	private:
    		node data;
    		int length;
    	public:
    		singlelink(){
    			length=0;
    			data.data1=0;
    			data.next=NULL;
    			data.prior=NULL;
    		}
    		~singlelink(){};
    		bool isempty(){
    			if(length==0)
    				return true;
    			else 
    			 	return false;
    		}
    		int returnlength(){
    			return length;
    		}
    		bool insert(int position, int num);
    		bool deletenode(int position);
    		int returnnum(int position);
    		bool deleteall();
    		void headinsert(int num);
    		void rearinsert(int num);
    		//int returnlast();
    		
    };
    /*	bool int returnlast(){
    		return 
    	}*/
    	bool singlelink::insert(int position, int num){
    		if(position>length+1)
    			return false;
    		else{
    			node* probe=&data;
    			for(int i=1;i<position;i++){
    				probe=probe->next;
    			}
    			node* newnode=new node;
    			newnode->data1=num;
    			newnode->next=probe->next;
    			probe->next->prior=newnode;
    			newnode->prior=probe;
    			
    			probe->next=newnode;
    			length++;
    		}
    		return true;
    	}
    	bool  singlelink::deletenode(int position){
    		if(position>length)
    			return false;
    		else{
    			node* probe=&data;
    			node* temp=NULL;
    			for(int i=1;i<position;i++){
    				probe=probe->next;
    			}
    			temp=probe->next;
    			probe->next=probe->next->next; 
    			temp->next->prior=probe;
    			free(temp);
    			length--;
    			return true;
    			
    		}	
    	}
    	int singlelink::returnnum(int position){
    		node* probe=&data;
    		for(int i=1;i<=position;i++){
    			probe=probe->next;
    		}
    		return probe->data1;
    	}
    	bool singlelink::deleteall(){
    		node* probehead=&data;
    		node* proberear=NULL;
    		while(probehead->next!=NULL){
    			proberear=probehead->next;
    			free(probehead);
    			probehead=proberear;
    			length--;
    		}
    		free(probehead);
    		if(length==0)
    			return true;
    		else
    			return false;
    	}
    	void singlelink::headinsert(int num){
             if(length==0){
                node* probe=&data;
                node* newnode=new node;
                newnode->data1=num;
               	newnode->next=probe->next;
                probe->next=newnode;
                newnode->prior=probe;                       
             }
             else{
    		node* probe=&data;
    		node* newnode=new node;
    		newnode->data1=num;
    		newnode->next=probe->next;
    		probe->next->prior=newnode;
    		newnode->prior=probe;
    		probe->next=newnode;
            }
    		length++;
    	}
    	void singlelink::rearinsert(int num){
    		node* probe=&data;
    		for(int i=1;i<=length;i++){
    			probe=probe->next;
    		}
    		node* newnode=new node;
    		newnode->data1=num;
    		newnode->next=NULL;
    		probe->next=newnode;
    		newnode->prior=probe;
    		length++;
    	}
    	int main(){
    		singlelink a1,a2;
    		if(a1.isempty())
    		cout<<"是空链表"<<endl;
    		for(int i=1, j=10;i<21;i++,j++){
    			a1.headinsert(j);
    			a2.rearinsert(j);
    		}
    		cout<<"a1，a2的长度分别是"<<a1.returnlength()<<"  "<<a2.returnlength()<<endl;
    		cout<<"a1成员为"<<endl; 
    		for (int i=1;i<=a1.returnlength();i++){
    		cout<<a1.returnnum(i)<<" ";
    		}
    		cout<<endl;
    		cout<<"a2成员为"<<endl; 
    		for (int i=1;i<=a2.returnlength();i++){
    		cout<<a2.returnnum(i)	<<" ";
    		}
    		cout<<endl;
    		a1.deletenode(9);
    		cout<<"删除第9node后a1成员为"<<endl; 
    		for (int i=1;i<=a1.returnlength();i++){
    		cout<<a1.returnnum(i)	<<" ";
    		}
    		cout<<endl;
    		a1.insert(9,520);
    		cout<<"插入第9node后a1成员为"<<endl; 
    		for (int i=1;i<=a1.returnlength();i++){
    		cout<<a1.returnnum(i)	<<" ";
    		}
    		cout<<endl;
    		if(a1.deleteall())
    		cout<<"删除a1成功"<<endl;
    		getchar();
    		return 0;
    		
    	}

实现的过程中遇到了一点小麻烦：

在实现头插法时因为这里加的有prior指针所以不能直接因为头结点而与其他节点同样处理，要单独处理。