现在的位置: 首页 > 综合 > 正文

容器query与list

2018年02月19日 ⁄ 综合 ⁄ 共 6328字 ⁄ 字号 评论关闭

简单了写了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;
}

抱歉!评论已关闭.