容器query与list

刺骨的言语ヽ痛彻心扉 2022-08-06 11:03 212阅读 0赞

简单了写了query和list的实现，特将代码放在这里，以备后续查看。

**query:**

QueryItem.h

#ifndef QUEUEITEM
    #define QUEUEITEM
    #include <iostream>
    using namespace std;
    template <typename Type> class Queue;
    
    template <typename T>
    ostream& operator<< (ostream&, const Queue<T> &);
    
    template <typename T>
    istream& operator>> (istream&, Queue<T> &);
    
    template <typename T>
    class QueueItem{
    	friend class Queue<T>;
    	friend ostream& operator<< <T>(ostream&, const Queue<T>&);
    	friend istream& operator>> <T>(istream&, Queue<T>&);
    
    	QueueItem(T val):value(val), next(0){}
    	T value;
    	QueueItem *next;
    };
    #endif

Query.h

#ifndef QUEUE
    #define QUEUE
    #include "QueueItem.h"
    #include <iostream>
    using namespace std;
    
    template <typename T>
    ostream& operator<<(ostream&, const Queue<T> &);
    
    template <typename T>
    istream& operator>> (istream&, Queue<T> &);
    
    template <typename T>
    class Queue{
    public:
    	Queue():head(0), tail(0){}
    	Queue(Queue &);
    	template <class Type> Queue(Type beg, Type end):head(0), tail(0){copy_elems(beg, end);};
    	template <class Type> void assin(Type beg, Type end){destroy(); copy_elems(beg, end);}
    	Queue operator=(Queue &);
        void push(T val);
    	void pop();
    	T& front();
    	bool empty(){return head==0;}
    	
    	~Queue(){destroy();}
    
    	friend ostream& operator<< <T>(ostream&, const Queue<T>&);
    	friend istream& operator>> <T>(istream&, Queue<T>&);
    private:
    	void destroy();
    	QueueItem<T> *head;
    	QueueItem<T> *tail;
    	template <typename Type> void copy_elems(Type beg, Type end);
    
    };
    #endif

Query.cpp

#include "Queue.h"
    template <typename T> 
    Queue<T>::Queue(Queue &que){
    	head = 0;
    	tail = 0;
    	for(QueueItem<T>*qt = que.head; qt; qt = qt->next){
    		push(qt->val);
    	}
    }
    
    template <typename T> 
    void  Queue<T>::push(T val){
    	QueueItem<T>* qt = new QueueItem<T>(val);
    	if(empty()){
    		head = tail = qt;
    	}else{
    		tail->next = qt;
    		tail = qt;
    	}
    }
    
    template <typename T> 
    void Queue<T>::pop(){         // 删除队头元素
    	QueueItem<T> *qt = head;
    	head = head->next;
    	delete qt;
    }
    
    template <typename T>
    void Queue<T>::destroy(){
    	while(!empty())pop();
    } 
    
    template <typename T>
    Queue<T> Queue<T>::operator=(Queue<T> &que){     //  没有检查自身赋值
    	destroy();
    	for(QueueItem<T>*qt = que.head; qt; qt = qt->next){
    		push(qt->val);
    	}
    	return *this;
    }
    
    template <typename T>
    T& Queue<T>::front(){
    	return head->value;
    }
    
    template <typename T>
    ostream& operator<<(ostream &os, const Queue<T>& q){
    	QueueItem<T> *qt;
    	os << "<";
    	for(qt= q.head; qt; qt= qt->next){
    		os << qt->value << " ";
    	}
    	os << ">";
    	return os;
    }
    
    template <typename T>
    istream& operator>> (istream &is,  Queue<T> &q){
    	T val;
    	while(is >> val){
    		q.push(val);}
    	return is;
    }
    
    template <typename T>
    template <typename Type>
    void Queue<T>::copy_elems(Type beg, Type end){
    	while(beg != end){
    		push(*beg);
    		beg++;
    	}
    }

**list:**

ListItem.h

#ifndef LISTITEM
    #define LISTITEM
    #include <iostream>
    using namespace std;
    
    template <typename T> class List;
    
    template <typename T>
    istream& operator>>(istream &is, List<T> &list);
    
    template <typename T>
    ostream& operator<<(ostream &os, const List<T> &list);
    
    template <typename T>
    class ListItem{
    	friend class List<T>;
    	ListItem(T val):value(val), next(0){}
    	T value;
    	ListItem *next;
    	friend istream& operator>> <T>(istream &is, List<T> &list);
    	friend ostream& operator<< <T>(ostream &os, const List<T> &list);
    };
    
    #endif

List.h

#ifndef LIST
    #define LIST
    #include "ListItem.h"
    #include <iostream>
    using namespace std;
    
    template <typename T>
    istream& operator>>(istream &is, List<T> &list);
    
    template <typename T>
    ostream& operator<<(ostream &os, const List<T> &list);
    
    template <typename T>
    class List{
    public:
    	List():head(0), end(0){}
    	List(List &list):head(0), end(0){copy_elems(list);}
    	List& operator=(const List &list);
    
    	template <typename Type> List(Type beg, Type end):head(0), end(0){copy_elems(beg, end);}
    	void push_back(const T &val);
    	void pop_back();
    	void pop_front();
    	void push_front(const T &val);
    	T& front(){return head->value;}
    	T& back(){return end->value;};
    	bool empty(){return head == 0;}
    
    	template <typename Type> void assign(Type beg, Type end){destroy(); copy_elems(beg, end);}
    	void insert(ListItem<T> *ptr, const T& val);
    	void del(ListItem<T> *ptr);
    	ListItem<T> *find(const T &val);
    
    	~List(){destroy();}
    private:
    	ListItem<T> *head;
    	ListItem<T> *end;
    	void copy_elems(List &);
    	template <typename Type> void copy_elems(Type beg, Type end);
    	void destroy();
    	friend istream& operator>> <T>(istream &is, List<T> &list);
    	friend ostream& operator<< <T>(ostream &os, const List<T> &list);
    };
    #endif

List.cpp

#include "List.h"
    #include <iostream>
    using namespace std;
    
    
    template <typename T>
    void List<T>::push_back(const T &val){
    	ListItem<T> *lt = new ListItem<T>(val);
    	if(empty()){
    		head = end = lt;
    	}else{
    		end->next= lt;
    		end = lt;
    	}
    }
    
    template <typename T>
    void List<T>::push_front(const T &val){
    	ListItem<T> *lt = new ListItem<T>(val);
    	if(empty()){
    		head = end = lt;
    	}else{
    		lt->next = head;
    		head = lt;
    	}
    }
    
    template <typename T>
    void List<T>::pop_front(){
    	ListItem<T> *lt = head;
    	head = head->next;
    	delete lt;
    }
    
    template <typename T>
    void List<T>::pop_back(){
    	ListItem<T> *lt=head;
    	while(lt->next == end){
    		end = lt;
    		delete lt->next;
    	}
    }
    
    template <typename T>
    void List<T>::copy_elems(List<T> &list){
    	ListItem<T> *lt;
    	for(lt = list.head; lt; lt = lt->next){
    		push_back(lt->value);
    	}
    }
    
    template <typename T>
    void List<T>::destroy(){
    	while(!empty())
    		pop_front();
    }
    
    template <typename T>
    template <typename Type>
    void List<T>::copy_elems(Type beg, Type end){
    	while(beg != end){
    		push_back(*beg);
    		++beg;
    	}
    }
    
    template <typename T>
    ostream& operator<<(ostream &os, const List<T> &list){
    	os << "<";
    	ListItem<T> *lt;
    	for(lt = list.head; lt; lt = lt->next){
    		os << lt->value << " ";
    	}
    	os << ">";
    	return os;
    }
    
    template <typename T>
    istream& operator>>(istream &is, List<T> &list){
    	T val;
    	while(is >> val)
    		list.push_back(val);
    	return is;
    }
    
    template <typename T>
    List<T>& List<T>::operator=(const List<T> &){
    	destroy(); 
    	copy_elems(list); 
    	return *this;
    
    }
    
    template <typename T>
    void List<T>::insert(ListItem<T> *ptr, const T& val){
    	ListItem<T> *new_lt = new ListItem<T>(val);
    	ListItem<T> *lt= head;
    	if(lt == ptr){
    		new_lt->next = ptr;
    		head = new_lt;
    		return;
    	}
    	while(lt->next != ptr && lt != end){
    		lt = lt->next;
    	}
    	if(lt->next == ptr){
    		
    		new_lt->next = ptr;
    		lt->next = new_lt;
    	}
    }
    
    template <typename T>
    
    void List<T>::del(ListItem<T> *ptr){
    	ListItem<T> *lt= head;
    	if(lt == ptr){
    		head = lt->next;
    		delete lt;
    		return;
    	}
    	while(lt->next != ptr && lt != end){
    		lt = lt->next;
    	}
    	if(lt->next == ptr){
    		lt->next = ptr->next;
    		if(ptr == end) end = lt;
    		delete ptr;
    	}
    }
    
    template <typename T>
    ListItem<T>* List<T>::find(const T &val){
    	for(ListItem<T> *lt = head; lt; lt= lt->next)
    	{
    		if(lt->value == val){
    			return lt;
    		}
    	}
    	return 0;
    }

Main.cpp

#include "Queue.h"
    #include "Queue.cpp"       //  包含编译模型 模板的实例化在编译阶段 必须能访问到源代码，而普通的函数或者类只需要有声明就可以了，放在symbol table中
    #include <iostream>
    #include <vector>
    #include "List.h"
    #include "List.cpp"
    using namespace std;
    
    
    int main(){
    	/*Queue<int> q;
    	q.push(5);
    	q.push(2);
    
    	int a[]={1,2,3,4};
    	Queue<int> q2(a, a+4);
    	cout << q2 << endl;
    	//cout << q.empty()<< endl;
    	//cout << q << endl;
    	//cin >> q;             // 返回的结果左操作数
    	//operator>> (cin, q);
    	operator<<(cout, q);    
    
    	vector<int> vec;
    	int i;
    	/*while(cin >> i){
    		vec.push_back(i);
    	}
    
    	for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
    	{
    		cout << *iter << " ";
    	}
    	cout << endl;*/
    
    	List<int> list;
    	list.push_back(1);
    	int a[5] ={1,2,3,4,5};
    	list.assign(a, a+5);
    	list.find(5);
    	cout << list << endl;
    
    	return 0;
    }