链式线性表

开发环境：Eclipse

参考书籍：《数据结构》——清华大学出版社——殷人昆

 

 

LinkedList.h

/*
 * LinkedList.h
 *
 *  Created on: Jun 6, 2010
 *      Author: limx
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

#include<iostream.h>

template<class T>
struct Node {
	T data;
	Node<T> *next;
	Node(Node<T> * ptr = NULL) {
		next = ptr;
	}
	Node(const T& item, Node<T>*ptr = NULL) {
		data = item;
		next = ptr;
	}
};
template<class T>
class LinkedList {
private:
	Node<T> *head;
	Node<T> *tail;
	int size;
public:
	LinkedList() {
		head = tail = new Node<T> ;
		size = 0;
	}
	LinkedList(const T& x) {
		head = tail = new LinkedList<T> (x);
		size = 0;
	}
	bool insert(T& x);
	bool remove(T & x);
	Node<T> * locate(int i);
	bool remove(int i, T & x);
	int getSize() const;
	void output();
	virtual ~LinkedList();
};

#endif /* LINKEDLIST_H_ */

 

 

LinkedList.cpp

/*
 * LinkedList.cpp
 *
 *  Created on: Jun 6, 2010
 *      Author: limx
 */

#include "LinkedList.h"

//插入值为x的节点
template<class T>
bool LinkedList<T>::insert(T& x) {

	//	here must add an "*"
	Node<T> *newNode = new Node<T> (x);
	if (newNode == NULL) {
		cerr << "memory error!" << endl;
		exit(1);
	}
	newNode->next = tail->next;
	tail->next = newNode;
	tail = newNode;
	size++;
	return true;
}

//获得链表的元素个数
template<class T>
int LinkedList<T>::getSize() const {
	return size;
}
//删除值为x的链表元素
template<class T>
bool LinkedList<T>::remove(T & x) {
	Node<T>* current = head;
	Node<T>* del = NULL;
	while (current != NULL && current->next->data != x) {
		current = current->next;
	}
	del = current->next;
	current->next = del->next;
	delete del;
	size--;
	return true;
}

//定位到第i个链表元素，并返回元素的地址
template<class T>
Node<T> * LinkedList<T>::locate(int i) {
	/*if(i<0||i>length){
	 return NULL;
	 }*/
	if (i < 0) {
		return NULL;
	}
	Node<T> * current = head;
	int count = 0;
	while (current != NULL && count < i) {
		current = current->next;
		count++;
	}
	return current;
}

//删除第i个节点
template<class T>
bool LinkedList<T>::remove(int i, T & x) {
	//这个处理的很巧妙
	Node<T> *current = this->locate(i - 1);
	if (current == NULL || current->next == NULL) {
		return false;
	}
	Node<T>* del = current->next;
	current->next = del->next;
	x = del->data;
	delete del;
	size--;
	return true;
}

template<class T>
void LinkedList<T>::output() {
	Node<T> * current = head->next;
	int i = 0;
	cout << "the elements in the LinkedList are:" << endl;
	while (current != NULL) {
		cout << "#" << ++i << "#:" << current->data << endl;
		current = current->next;
	}
}
template<class T>
LinkedList<T>::~LinkedList() {
	// TODO Auto-generated destructor stub
}

 

 

main.cpp

/*
 * main.cpp
 *
 *  Created on: Jun 6, 2010
 *      Author: limx
 */
#include<iostream.h>
#include"LinkedList.cpp"
int main() {
	LinkedList<int> ll;
	int data;
	cout << "enter the element :" << endl;
	for (int i = 0; i < 5; i++) {
		cout << "#" << i + 1 << "#";
		cin >> data;
		ll.insert(data);
	}
	ll.output();
	int i;
	int x;
	cout << "which value you want to delete :" << endl;
	cin >> x;
	cout << "the value to delete is " << x << endl;
	ll.remove(x);
	ll.output();
	cout << "enter the location you want to delete:" << endl;
	cin >> i;
	if (ll.remove(i, x) == true) {
		cout << "the value of element to delete is:  " << x << endl;
	}
	ll.output();
	cout << "the size of LinkedList are:" << ll.getSize();
	return 0;

}

 

 

result:

enter the element :
#1#12
#2#30
#3#35
#4#16
#5#40
the elements in the LinkedList are:
#1#:12
#2#:30
#3#:35
#4#:16
#5#:40
which value you want to delete :
12
the value to delete is 12
the elements in the LinkedList are:
#1#:30
#2#:35
#3#:16
#4#:40
enter the location you want to delete:
2
the value of element to delete is:  35
the elements in the LinkedList are:
#1#:30
#2#:16
#3#:40
the size of LinkedList are:3