`
阿尔萨斯
  • 浏览: 4108199 次
社区版块
存档分类
最新评论

数据结构 - 单链表的实现(C++)

 
阅读更多
// ------SingleLinkedList.h------

// Implement Single Linked List.
// Time complexities of find an element, insert an element, remove an element, copy a single linked list and clear single linked list are all O(n).
// Decrease the dependencies between member functions as far as possible when design the class.

#ifndef SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_H

template<class T>
struct Node
{
	T data;
	Node<T> *next;
};

template<class T>
class SingleLinkedList
{
public:
	SingleLinkedList();
	SingleLinkedList(const SingleLinkedList<T> &pList);
	~SingleLinkedList();
	SingleLinkedList<T>& operator=(const SingleLinkedList<T> &pList);
	void insert_head(const T &element);  // Insert before the head of list.
	void insert_tail(const T &element);  // Insert at the tail of list.
	bool first(T &element);  // Get the data of the first node.
	inline bool getNext(T &element);  // Get the data of the next node.
	bool find(const T &element);  // Find data.
	bool retrieve(T &element);  // Retrieve data.
	bool replace(const T &newElement);  // Change data.
	bool remove(T &element);
	bool isEmpty() const;
	void makeEmpty();
private:
	Node<T> *head;
	Node<T> *current;
	inline void deepCopy(const SingleLinkedList<T> &original);
};

#endif
// ------SingleLinkedList.cpp------

#include "SingleLinkedList.h"

template<class T>
SingleLinkedList<T>::SingleLinkedList()
{
	head = current = NULL;
}

template<class T>
SingleLinkedList<T>::SingleLinkedList(const SingleLinkedList<T> &pList)
{
	deepCopy(pList);
}

template<class T>
SingleLinkedList<T>::~SingleLinkedList()
{
	makeEmpty();
}

template<class T>
SingleLinkedList<T>& SingleLinkedList<T>::operator =(const SingleLinkedList<T> &pList)
{
	if(this == &pList)
	{
		return this;
	}

	makeEmpty();
	deepCopy(pList);

	return this;
}

// Insert (T &element) at the head of list.
template<class T>
void SingleLinkedList<T>::insert_head(const T &element)
{
	current = NULL;
	Node<T> *newNode = new Node<T>;
	newNode->data = element;
	newNode->next = head;
	head = newNode;
}

// Insert at the tail of list.
template<class T>
void SingleLinkedList<T>::insert_tail(const T &element)
{
	current = NULL;
	Node<T> *newNode = new Node<T>;
	newNode->data = element;
	newNode->next = NULL;
	Node<T> *temp;
	T item;
	if(head == NULL)
	{
		head = newNode;
		temp = head;
		return;
	}

	temp = head;
	while(temp->next != NULL)
	{
		temp = temp->next;
	}

	temp->next = newNode;
}

// Put the first node into element, and set the position of the first node current.
template<class T>
bool SingleLinkedList<T>::first(T &element)
{
	if(head == NULL)
	{
		return false;
	}

	current = head;
	element = head->data;

	return true;
}

// Put the node (current->next) into element, and set current to the next node.
template<class T>
bool SingleLinkedList<T>::getNext(T &element)
{
	if(current == NULL)
	{
		return false;
	}

	if(current->next == NULL)
	{
		current = NULL;
		return false;
	}

	element = current->next->data;
	current = current->next;

	return true;
}

// True if element found; otherwise, false. Current is set in getNext().
template<class T>
bool SingleLinkedList<T>::find(const T &element)
{
	T item;
	if(!first(item))
	{
		return false;
	}

	do
	{
		if(item == element)
		{
			return true;
		}
	}while(getNext(item));

	return false;
}

template<class T>
bool SingleLinkedList<T>::retrieve(T &element)
{
	if(!find(element))
	{
		return false;
	}

	element = current->data;

	return true;
}

template<class T>
bool SingleLinkedList<T>::replace(const T &newElement)
{
	if(current == NULL)
	{
		return false;
	}

	current->data = newElement;

	return true;
}

template<class T>
bool SingleLinkedList<T>::remove(T &element)
{
	current = NULL;
	if(head == NULL)
	{
		return false;
	}

	Node<T> *ptr = head;
	if(head->data == element)
	{
		element = head->data;
		head = ptr->next;
		delete ptr;
		return true;
	}

	while(ptr->next != NULL)
	{
		if(ptr->next->data == element)
		{
			Node<T> *tempptr = ptr->next;
			element = tempptr->data;
			ptr->next = tempptr->next;
			delete tempptr;
			return true;
		}

		ptr = ptr->next;
	}

	return false;
}

template<class T>
bool SingleLinkedList<T>::isEmpty() const
{
	return head == NULL;
}

template<class T>
void SingleLinkedList<T>::makeEmpty()
{
	while(head != NULL)
	{
		current = head;
		head = head->next;
		delete current;
	}

	current = NULL;
}

template<class T>
void SingleLinkedList<T>::deepCopy(const SingleLinkedList<T> &original)
{
	head = current = NULL;
	if(original.head == NULL)
	{
		return;
	}

	Node<T> *copyptr = head = new Node<T>;
	Node<T> *originalptr = original.head;
	copyptr->data = originalptr->data;
	if(originalptr == original.current)
	{
		current = copyptr;
	}

	while(originalptr->next != NULL)
	{
		copyptr->next = new Node<T>;
		originalptr = originalptr->next;
		copyptr = copyptr->next;
		copyptr->data = originalptr->data;
		if(originalptr == original.current)
		{
			current = copyptr;
		}
	}

	copyptr->next = NULL;
}
// ------Entry Point------

#include <iostream>
#include "SingleLinkedList.cpp"
#include <string>

using namespace std;

void main()
{
	string str[6] = {"Hello","World","Welcome","To","Beijing"};

	// Initialize single linked list.
	SingleLinkedList<string> strLL;
	for(int ix=0;ix<5;++ix)
	{
		strLL.insert_tail(str[ix]);
	}

	cout << "Traverse single linked list: ";
	string element;
	if(strLL.first(element))
	{
		cout << element << " ";
	}

	while(strLL.getNext(element))
	{
		cout << element << " ";
	}

	cout << endl;
	SingleLinkedList<string> strLL2(strLL); // Invoke constructor
	SingleLinkedList<string> strLL3 = strLL; // Overload operator "="
	strLL2.first(element);
	cout << "element = " << element << endl;
	strLL3.first(element);
	cout << "element = " << element <<endl;
	if(strLL2.find(str[3]))
	{
		cout << "str[3] = " << str[3] << endl;
	}

	if(strLL3.retrieve(str[2]))
	{
		cout << "str[2] = " << str[2] << endl;
	}

	if(strLL.remove(str[1]))
	{
		strLL.first(element);
		cout << "element after remove is " << element << endl;
	}

	if(strLL.isEmpty())
	{
		cout << "List is Empty!" << endl;
	}

	strLL.makeEmpty();
	strLL2.makeEmpty();
	strLL3.makeEmpty();
}

// Output:
/*
Traverse single linked list: Hello World Welcome To Beijing
element = Hello
element = Hello
str[3] = To
str[2] = Welcome
element after remove is Hello
*/
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics