[C++知识库]C++模拟单链表

呜，刚开始学数据结构，原来c++没学过，有点困难，不过肯定能学好的，我要加油。以下代码借鉴了我两位聪明帅气的室友，qcj和wyz。也许有很多不完善的地方，因为我刚学，知道了会马上改过来。

#include <iostream>

using namespace std;

typedef int ElementType;

class LinkList
{
private:
	class Node
	{
	public:
		ElementType data;
		Node* next;
		Node() :next(0) {}// 默认构造函数
		Node(ElementType dataValue) :data(dataValue), next(0) {} // 显值构造函数
	};
public:
	typedef Node* NodePointer;
	LinkList(); // 构造函数
	LinkList(const LinkList& origList); // 复制构造函数
	~LinkList();
	const LinkList& operator = (const LinkList& rightSide);
	bool empty();
	void insert(ElementType dataVal, int idex);
	void erase(int index);
	NodePointer search(ElementType dataVal);
	// ostream 是iostream库中的一个类，cerr，cout，clog是ostream类中的对象
	// 引用形参ostream& out能允许使用带有不同ostream对象的display（）
	// 如LinkList.display(cerr); LinkList.display(cout);
	void display(ostream& out) const;
	int nodeCount();
	void reverse();
	bool ascendingOrder();
	void ListMerge(LinkList& templist);
	void MergeList(LinkList& listA, LinkList& listB);
	ElementType get(NodePointer temp);
private:
	NodePointer first;
	int mySize;
	// 外部类访问不到重载运算符的类的私有变量，通过friend声明
	// 可以使被修饰的类访问到本类的私有变量
	// 友元函数是一种特殊的函数，需要在类体内进行说明，可以访问类的成员，但不是类的成员函数

	// 可以用成员函数display将类LinkList直接输出，为LinkList重载函数operator<<() 更方便,不需要中断 <<的链式使用
	// operator()<<是普通函数，不是成员函数，cout<<LinkList被看作普通函数调用operator<<(cout, LinkList)
	// 所以，operator()需有两个形参，ostream形参必须是引用形参，为实参的别名
	// 第二个形参使用一个常引用形参，省去创建副本的开销，const保护对应的实参
	friend ostream& operator<<(ostream& out, const LinkList& List);
	// 输入操作，要改变链表，删掉const
	friend istream& operator>>(istream& in, LinkList& List);
};

// （cout << x ) << y; operator << (cout, x) << y, 要变成cout << y
// 因此第一个函数调用要返回ostream类的cout，out是cout的别名
// 所以函数operator（）能返回修改过的ostream
ostream& operator<<(ostream& out, const LinkList& List)
{
	LinkList::NodePointer ptr = List.first; //为什么前面要声明是LinkList类？？是非成员函数的原因吗
	while (ptr != 0)
	{
		out << ptr->data << ' ';
		ptr = ptr->next;
	}
	out << endl;
	return out;
}
istream& operator>> (istream& in, LinkList& List)
{
	// a为输入的节点个数，b为 输入的值
	ElementType a, b;
	in >> a;
	for (int i = 0; i < a; i++)
	{
		in >> b;
		List.insert(b, i);
	}
	return in;
}
LinkList::LinkList()
{
	mySize = 0;
	first = 0;
}
LinkList::LinkList(const LinkList& rightSide)
{
	if (rightSide.mySize == 0)
	{
		first = 0;
		mySize = 0;
		return;
	}
	this->mySize = rightSide.mySize;
	NodePointer ptr = new Node(rightSide.first->data);
	// 先给first指针赋地址
	first = ptr;
	int index = 0;
	for (ptr = rightSide.first->next; ptr != 0; ptr = ptr->next)
	{
		index++;
		this->insert(ptr->data, index);
	}
}
// 析构函数的目的是释放链表的每一节点，包括头节点，因此用first判空
LinkList::~LinkList()
{
	NodePointer p = first;
	while (first != 0)
	{
		p = first;
		first = first->next;
		delete p; // 单独删除，析构函数是针对LinkList类的
	}
}
const LinkList& LinkList::operator=(const LinkList& rightSide)
{
	int index = 0;
	if (rightSide.mySize == 0)
	{
		first = 0;
		mySize = 0;
		// 函数要返回LinkList类
		return *this;
	}
	NodePointer ptr = new Node(rightSide.first->data);
	this->first = ptr;
	this->mySize = rightSide.mySize;
	for (ptr = rightSide.first->next; ptr != 0; ptr = ptr->next)
	{
		index++;
		this->insert(ptr->data, index);
	}
	return *this;
}
bool LinkList::empty()
{
	if (mySize) return 1;
	else return 0;
}
void LinkList::insert(ElementType dataVal, int index)
{
	NodePointer ptr = new Node(dataVal);
	if (index > mySize+ 1)
	{
		cout << "链表越界" << endl;
		// cerr能将输入直接放到屏幕，cout先放到缓冲区
	    // 不能写成cout << ".....\n" ;
		// 也可以用endl刷新缓冲区
	}
	// 单独给first赋值
	else if (index == 0)
	{
		mySize++;
		first = ptr;
	}
	// 创建一个链表是在链表尾部插入的操作
	else if (index == mySize)
	{
		mySize++;
		NodePointer p2 = first;
		while (p2->next != 0)
			p2 = p2->next;
		ptr->next = p2->next;
		p2->next = ptr;
	}
	// 在链表的中间部分插入
	else
	{
		int size = 0;
		NodePointer p2 = first;
		while (size != index - 1)
		{
			size++;
			p2 = p2->next;
		}
		ptr->next = p2->next;
		p2->next = ptr;
	}
}
void LinkList::erase(int index)
{
	NodePointer predptr = first;
	if (first == 0)
	{
		cout << "链表为空无法进行删除" << endl;
		return;
	}
	if (index > mySize)
	{
		cout << "链表越界" << endl;
		return;
	}
	if (index == 0)
	{
		NodePointer ptr = first;
		first = first->next;
		mySize--;
		delete ptr; // 将节点返回给堆
	}
	else
	{
		int index2 = 0;
		for (predptr = first; predptr != 0; predptr = predptr->next)
		{
			index2++;
			if (index2 == index)
			{
				mySize--;
				NodePointer ptr = predptr->next;
				predptr->next = ptr->next;
				delete ptr; //将节点返回给堆
			}
		}
	}
}
LinkList::NodePointer LinkList::search(ElementType dataVal)
{
	NodePointer ptr = first;
	while (ptr != 0)
	{
		if (ptr->data == dataVal) return ptr;
	}
}
void LinkList::display(ostream& out) const
{
	for (NodePointer ptr = first; ptr != 0; ptr = ptr->next)
	{
		out << ptr->data << " ";
	}
	out << endl;
}
int LinkList::nodeCount()
{
	return mySize;
}
void LinkList::reverse()
{
	LinkList b;
	b.mySize = mySize;
	// 从头开始遍历链表，将其摘下放到新链表的最前端，最后将新链表赋给旧链表
	NodePointer p = first, p2;
	while (p->next != 0)
	{
		p2 = new Node(p->data);
		p2->next = b.first;
		b.first = p2;
		p = p->next;
	}
	p2 = new Node(p->data);
	p2->next = b.first;
	b.first = p2;
	(*this).~LinkList();  // 不用析构可以不？
	*this = b;
}
bool LinkList::ascendingOrder()
{
	NodePointer fiptr = first, secptr = fiptr->next;
	bool flag = 1;
	while (secptr != 0)
	{
		if (fiptr->data > secptr->data)
		{
			flag = 0;
			return flag;
		}
		fiptr = fiptr->next;
		secptr = secptr->next;
	}
	return flag;
}
void LinkList::ListMerge(LinkList& templist)
{
	if (first == 0)
	{
		new (this) LinkList(templist); 
	}
	else
	{
		NodePointer p2 = this->first;
		while (p2->next != 0)
			p2 = p2->next;
		LinkList* p = new LinkList(templist);
		mySize += templist.mySize;
		p2->next = p->first;
	}
}
void LinkList::MergeList(LinkList& ListA, LinkList& ListB)
{
	this->ListMerge(ListA);
	this->ListMerge(ListB);
}
ElementType LinkList::get(NodePointer temp)
{
	return temp->data;
}

int main()
{
	LinkList ListA;
	ListA.insert(0, 0);
	ListA.insert(10, 1);
	ListA.insert(20, 2);
	ListA.insert(30, 3);
	cout << "display测试  " << endl;
	ListA.display(cout);
	ListA.insert(25, 3);
	cout << "插入测试" << '\n' << ListA << endl;
	if (ListA.empty()) cout << "链表非空" << endl;
	else cout << "链表为空" << endl;
	ListA.erase(1);
	cout << "删除测试" << '\n' << ListA << endl;
	cout << "节点个数  " << ListA.nodeCount() << endl;
	ListA.reverse();
	cout << "反转测试  " << ListA << endl;
	if (ListA.ascendingOrder()) cout << "升序" << endl;
	else cout << "非升序" << endl;
	cout << "查找指定值测试" << '\n' << ListA.get(ListA.search(30)) << endl;
	LinkList ListB;
	cin >> ListB;
	ListA.ListMerge(ListB);
	cout << "合并测试  " << ListA << endl;
	LinkList ListC;
	cin >> ListC;
	ListA.MergeList(ListC, ListB);
	cout << "3个合并测试  " << ListA << endl;

	return 0;
}