顺序链表与单链表的C++实现

た入场券 2022-05-27 00:48 187阅读 0赞

对于顺序链表的实现：

//顺序表
    # include <iostream> 
    # include <cstring>
    using namespace std;
    class orderlink{
    	private:
    		int data[100];
    		int length;
    	public:
    		orderlink(){
    			length=0;
    			memset(data,0,sizeof(data));
    			
    		}
    		bool isempty(){
    		    if(length==0)
    				return true;
    			else
    				return false;
    		}
    		int returnlength(){
    			return length;
    		}
    		bool insert(int position, int num);
    		bool chuqu (int position);
    		int returnnum (int position);
    };
    	bool orderlink:: insert (int position, int num){
    		if(position>length+1)
    		 return false;
    		else if(position>length){
    			data[position]=num;
    			length++;
    		}
    		else{
    			for(int i=length;i>=position;i--){
    				data[i+1]=data[i];
    			}
    			data[position]=num;
    			length++;
    		}
    		return true;
    	}
    	bool  orderlink::chuqu (int position){
    		if(position>length)
    		     return false;
    		else if(position==length){
    			length--;
    		}
    		else{
    			for(int i=position;i<length;i++){
    				data[i]=data[i+1];
    			}
    			length--;     
    	        }
    	    return true;    
        }
        int orderlink::returnnum (int position){
        	if(position>length){
        		cout<<"范围超出"<<endl; 
    		}
    		else{
    			return data[position];
    		}
    	}
    int main(){
    	orderlink a;
    	for(int i=1,j=10;i<20;i++,j++){
    		a.insert(i,j);
    	}
    	
    	for(int i=1;i<=a.returnlength();i++){
    		cout<<a.returnnum(i)<<" ";
    	}
    	cout<<endl;
    	a.insert(9,520);
    	for (int i=1;i<=a.returnlength();i++){
    		cout<<a.returnnum(i)<<" ";
    	}
    	cout<<endl;
    
    	a.chuqu(8);
    	for(int i=1;i<=a.returnlength();i++){
    		cout<<a.returnnum(i)<<" ";
    	}
    	cout<<endl;
    	return 0;
    }

对于单链表的实现：

//单链表
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    struct node{
    	int data1;
    	node *next;
    }; 
    class singlelink{
    	private:
    		node data;
    		int length;
    	public:
    		singlelink(){
    			length=0;
    			data.data1=0;
    			data.next=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);
    		
    };
    	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=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; 
    			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){
    		node* probe=&data;
    		node* newnode=new node;
    		newnode->data1=num;
    		newnode->next=probe->next;
    		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;
    		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;
    		return 0;
    	}

对于单链表的实现过程中遇到了一点点小麻烦，因为一开始在删除节点的时候只用到了一个指针，无法删除节点。

同时还要注意(\*a).data与a->data等效。