数据结构：单向链表

谁借莪１个温暖的怀抱￠ 2021-12-20 00:21 280阅读 0赞

### 数据结构：单向链表 ###

*  源代码
 *  输出结果

# 源代码 #

#include<iostream>
    using namespace std;
    
    template<class T>
    class node{ 
    	public:
    	node<T> *next;
    	T element;
    	node(){ 
    		next = NULL;
    	}
    	node(const T& element):element(element){ 
    		next = NULL;
    	}
    	node(const T& element, node<T>* next):element(element){ 
    		this->next = next;
    	}
    };
    
    template<class T>
    class link{ 
    	private:
    	node<T> *head;
    	int length;
    	public:
    	link(){ 
    		head = NULL;
    		length = 0;
    	}
    	~link(){ 
    		node<T>* current = head;
    		while(head){ 
    			current = head;
    			head = head->next;
    			delete current;
    		}
    	}
    	int size(){ 
    		return length;
    	}
    	bool empty(){ 
    		return head == NULL;
    	}
    	node<T>* getHead(){ 
    		return head;
    	}
    	void insert(int,const T&);
    	void erase(int);
    	int find(const T&);
    	T& get(int);
    	void output(){ 
    		node<T>* current=head;
    		while(current){ 
    			cout<<current->element<<" ";
    			current = current->next;
    		}
    	}
    };
    
    template<class T>
    void link<T>::insert(int index,const T& element){ 
    		if(length==0){ 
    			head = new node<T>(element);
    			length++;
    			return ;
    		}
    		// index 代表索引 从0开始
    		// index >=size时 元素默认放在最后面
    		node<T>* current=NULL;
    		if(index==0){ 
    			current = new node<T>(element,head);
    			head = current;
    			length ++;
    			return ;
    		}
    		current = head;
    		while(current->next&&--index){ 
    			current = current->next;
    		}
    		node<T>* p = new node<T>(element, current->next);
    		current->next = p;
    		length++; 
    }
    
    template<class T>
    void link<T>::erase(int index){ 
    		// index 代表索引 从0开始
    		if(index==0){ 
    			head = head->next;
    			length --;
    			return ;
    		}
    		if(index>=length)return ;
    		node<T>* current=head;
    		while(current&&--index){ 
    			current = current->next;
    		}
    		node<T>* p =current->next;
    		current->next = p->next;
    		delete p;
    		length--;
    }
    
    template<class T>
    int  link<T>::find(const T& element){ 
    	int index = 0;
    	node<T>* current = head;
    	while(current){ 
    		if(current->element==element)return index;
    		current = current->next;
    		index++;
    	}
    	return -1;
    }
    
    template<class T>
    T& link<T>::get(int index){ 
    	if(index>=length){ 
    		cout<<"索引不存在"<<endl;
    	}
    	node<T>* current = head;
    	while(current&&index--){ 
    		current = current->next;
    	}
    	return current->element;
    }
    
    
    int main(){ 
    	link<int> L;
    	for(int i=0;i<4;i++)L.insert(0,i+1);
    	cout<<"链表元素：";L.output();cout<<"\n";
    	cout<<"链表大小："<<L.size()<<"\n";
    	L.insert(2,5);
    	L.insert(10,6);
    	cout<<"链表元素：";L.output();cout<<"\n";
      cout<<"链表大小："<<L.size()<<"\n";
    	L.erase(0);
    	cout<<"删除索引0后，链表元素：";L.output();cout<<"\n";
    	L.erase(10);
    	cout<<"删除索引10后，链表元素：";L.output();cout<<"\n";
    	L.erase(2);
    	cout<<"删除索引2后，链表元素：";L.output();cout<<"\n";
    	cout<<"链表大小："<<L.size()<<"\n";
    	cout<<"链表索引为1："<<L.get(1)<<endl;
    }

# 输出结果 #

链表元素：4 3 2 1 
    链表大小：4
    链表元素：4 3 5 2 1 6 
    链表大小：6
    删除索引0后，链表元素：3 5 2 1 6 
    删除索引10后，链表元素：3 5 2 1 6 
    删除索引2后，链表元素：3 5 1 6 
    链表大小：4
    链表索引为1：5