C++简单的通用链表Demo

很早以前写的一个例子，简单的模仿STL实现一个链表。我想对于想使用C++写一个简单链表的初学者有帮助 ！

////////////////////////////////////////////////////////////////////////////////
//			简单的链表C++实现
// Aothor:	殷洪
// Date:	2006-06-18
// QQ:		47406310
// Email:	[e-mail]
////////////////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include <iostream>
#include <stdexcept>
#include <string>

using namespace std;

template <class T> class Node {
public:
	Node() {
#ifdef _DEBUG
		cout << "Node()" << endl;
#endif
	}
	~Node() {
#ifdef _DEBUG
		cout << "~Node()" << endl;
#endif
	}
	T		data;
	Node*	next;
};


template <class T> class Iterator {
public:
	Iterator() : m_head(0)
		, m_curr(0) {}
	Iterator(Node<T>* node) : m_head(node)
		, m_curr(node) {
#ifdef _DEBUG
		cout << "Iterator()" << endl;
#endif
	}
	
	~Iterator() {
#ifdef _DEBUG
		cout << "~Iterator()" << endl;
#endif
	}
	
	bool hasElement() const {
		if (!m_curr) {
			return false;
		}
		return true;
	}
	
	const T& nextElement() {
		T& data = m_curr->data;
		m_curr = m_curr->next;
		return data;
	}
private:
	Node<T>* m_head;
	Node<T>* m_curr;
};

template <class T> class Link {
public:	

	Link();
	~Link();
	void add(const T&);
	void remove(const T&);
	bool find(const T&);
	inline bool empty() const { return m_head ? true : false; }
	inline Iterator<T> getIterator() const { return Iterator<T>(m_head); }

protected:
	void destory();

private:
	Node<T>* m_head;
	Node<T>* m_curr;
};

template <class T>
Link<T>::Link() : 
	m_head(0)
	, m_curr(0) {
#ifdef _DEBUG
	cout << "Link<T>::Link()" << endl;
#endif
}

template <class T>
Link<T>::~Link() {
	destory();
#ifdef _DEBUG
	cout << "Link<T>::~Link()" << endl;
#endif
}

template <class T>
void Link<T>::add(const T& element) {
	if (!(m_head && m_curr)) {
		m_head = new Node<T>;
		if (!m_head)
			throw std::bad_alloc("can't allocate memory!");

		m_head->data = element;
		m_head->next = 0;
		m_curr = m_head;

	} else {

		Node<T>* node = new Node<T>;
		if (!node)
			throw std::bad_alloc("can't allocate memory!");

		node->data = element;
		node->next = 0;

		if (m_curr && (0 == m_curr->next)) {
			m_curr->next = node;
			m_curr = node;
		}
	}
}

template <class T>
void Link<T>::destory() {
	while (m_head) {
		Node<T>* next = m_head->next;
		delete m_head;
		m_head = next;
	}
}

template <class T>
void Link<T>::remove(const T& element) {
	
	Node<T>* prev = 0;
	Node<T>* ptr = 0;

	ptr = m_head;
	while (ptr) {
		if (m_head->data == element) {
			Node<T>* next = m_head->next;
			delete m_head;
			m_head = next;
			break;
		}		

		prev = ptr;
		ptr = ptr->next;

		if (ptr->data == element) {
			prev->next = ptr->next;
			delete ptr;
			break;
		}
	}
}

template <class T>
bool Link<T>::find(const T& element) {

	Iterator<T> iter = getIterator();
	while (iter.hasElement()) {
		if (iter.nextElement() == element) {
			return true;
		}
	}
	return false;
}

typedef struct Student {
	int id;
	std::string name;
	std::string sex;
	std::string remark;
} _student_t;

inline bool operator==(const _student_t& st1, const _student_t& st2) {
	return st1.id == st2.id && st1.name == st2.name &&
		st1.sex == st2.sex && st1.remark == st2.remark;
}

inline bool operator!=(const _student_t& st1, const _student_t& st2) {
	return !(st1 == st2);
}

void printElements(Link<_student_t>& link)
{
	Iterator<_student_t>& iter = link.getIterator();
	while (iter.hasElement()) {
		const _student_t& s = iter.nextElement();
		cout << "id = "		<< s.id		<< ", "
			<< "name = "		<< s.name << ", "
			<< "sex = "			<< s.sex	<< ", "
			<< "remark = "	<< s.remark << endl;
	}
}

int main(int argc, char* argv[])
{
	Link<_student_t> students;
	_student_t st1;
	_student_t target;

	char temp[255];
	for (int i=0; i<15; i++) {
		st1.id = i;
		sprintf(temp, "name-%d", i);
		st1.name = temp;
		
		if (i % 2) {
			st1.sex = "男";
		} else {
			st1.sex = "女";
		}

		sprintf(temp, "remark-just soso-%d", i);
		st1.remark = temp;
		students.add(st1);
		if (12 == i) {
			target = st1;
		}
	}

	cout << "all element: " << endl;
	printElements(students);

	Iterator<_student_t>& rmvIter = students.getIterator();
	int id = 0;
	while (rmvIter.hasElement()) {
		const _student_t& rmvElement = rmvIter.nextElement();
		if (4 == rmvElement.id) {
			students.remove(rmvElement);
		}
		/*
		//delete all elements
		if (id == rmvElement.id) {
			students.remove(rmvElement);
		}
		id++;
		*/
	}

	cout.setf(ios_base::boolalpha);
	cout << "is empty: "	<< students.empty() << endl;
	cout << "find(xxx): " << students.find(target) << endl;

	cout << "remove after:" << endl;
	printElements(students);

	Link<std::string> strs;

	strs.add("Hello");
	strs.add("long");
	strs.add("time");
	strs.add("see");
	strs.add("!!!");

	cout << "strs.empty() = " << strs.empty() << endl;
	cout << "strs.find(\"!!!\") = " << strs.find("!!!") << endl;
	strs.remove("!!!");

	Iterator<std::string> strIter = strs.getIterator();
	while (strIter.hasElement()) {
		cout << strIter.nextElement() << ", ";
	}
	cout << endl;
	return 0;
}

 

评论

4 楼 sdkjsdj 2010-01-22  

看起来写的还是不错的。但是有可能还欠缺一点功底。要不然啊你去看看其他人写的。

3 楼 tangfeng 2010-01-09  

这叫什么通用啊，你应该看看Linux里面的那个链表，那才经典！

2 楼 ph4nut 2010-01-02  

因為重載操作符== !== 里面是用具體的sex,id等等來做判斷，所以不具有通用性。

1 楼 gexialover 2009-10-26  

这是单链表，不是通用链表！