【c++数据结构】单链表（带附加结点）

#include
#include
using namespace std;
template
struct LinkNode {
	T data;
	LinkNode* link;
	LinkNode(LinkNode* ptr = NULL)             { link = ptr; }
	LinkNode(const T& x, LinkNode* ptr = NULL) { data = x; link = ptr; }

};

template
class List {
private:
	LinkNode* first;               //附加头节点数据记录链表大小
public: 
	List()                          { first = new LinkNode(0); }
	List(const T& x)   { 
		first = new LinkNode(1);
		LinkNode* newNode = new LinkNode(x);
		first->link = newNode;
	}
	List(List& L);                  
	void makeEmpty();
	~List()                          { makeEmpty(); }             
	int Length()const                { return first->data; }
	LinkNode* getHead()const      { return first; }
	LinkNode* Search(T x);
	LinkNode* Locate(int i);
	LinkNode* FromendLocate(int k);
	void setData(int i, T x);
	bool Insert(int i, T x);
	bool Remove(int i, T& x);
	bool IsEmpty()const              { return first->link == NULL ? true : false; }
	void inputFront(T endTag);
	void inputRear(T endTag);
	void output();
	List& operator=(List& L);
	LinkNode* Reverse01();

};


template                         //复制构造
List::List(List& L) {
	T temp;
	LinkNode* srcptr = L.getHead();
	LinkNode* destptr = first = new LinkNode(srcptr->data);
	while (srcptr->link != NULL) {
		temp = srcptr->link->data;
		destptr->link=new LinkNode(temp);
		srcptr = srcptr->link;
		destptr = destptr->link;
	}
	destptr->link = NULL;
}


template                         //链表置空
void List::makeEmpty() {
	while (first->link != NULL) {
		LinkNode* q = first->link;
		first->link = q->link;
		delete q;
	}
	first->data = 0;
}


template                         //搜索含数据x的元素
LinkNode* List::Search(T x) {
	LinkNode* current = first;
	while (current->link != NULL) {
		current = current->link;
		if (current->data == x) return current;
	}
	return NULL;
}


template                         //定位第i个元素的地址
LinkNode* List::Locate(int i) {
	if (i<0 ||i > first->data) return NULL;
	int k = 0;
	LinkNode* current = first;
	while (k < i) { current = current->link; k++; }
	return current;
}


template                         //修改第i个元素的值
void List::setData(int i, T x) {
	if (i<0 || i > first->data) return;
	int k = 0;
	LinkNode* current = first;
	while (k < i) { current = current->link; k++; }
	current->data = x;
}


template                         //在第i个元素后插入x
bool List::Insert(int i, T x) {
	if (i<0 || i>first->data) return false;
	LinkNode* current = first; int k = 0;
	while (k < i) {
		current = current->link;
		k++;
	}
	LinkNode* newNode = new LinkNode(x);
	newNode->link = current->link;
	current->link = newNode;
	(int)(first->data)++;
	return true;
}


template                         //输出(头结点数值为链表长度)
void List::output() {
	LinkNode* current = first;
	while (current!= NULL) {
		cout << current->data << " ";
		current = current->link;
	}
	cout << endl;
}


template                         //头插法
void List::inputFront(T endtag) {
	T x; cout << "请输入头插的元素："; cin >> x;
	while (x != endtag) {
		LinkNode* newNode = new LinkNode(x);
		newNode->link = first->link;
		first->link = newNode;
		(int)(first->data)++;
		cout << endl<< "请输入头插的元素："; cin >> x;
	}
	cout << endl << "输入结束" << endl;
}


template                         //尾插法
void List::inputRear(T endtag) {
	T x; cout << "请输入尾插的元素："; cin >> x;
	LinkNode* rear = first;
	while (rear->link != NULL) rear = rear->link;
	while (x != endtag) {
		LinkNode* newNode = new LinkNode(x);
		rear->link = newNode;
		rear = rear->link;
		(int)(first->data)++;
		cout << "请输入尾插的元素："; cin >> x;
	}
	cout << endl << "输入结束" << endl;
}


template                         //删除第i个元素,通过x返回该元素的值，把被删结点从链中摘下
bool List::Remove(int i, T& x) {
	LinkNode* current = Locate(i - 1);
	if (current == NULL || current->link == NULL) return false;
	LinkNode* del = current->link;
	current->link = del->link;
	x = del->data; delete del;
	(int)(first->data)--;
	return true;
}


template                         //从尾到头输出(递归)
void FromendOutput(LinkNode* head) {
	if (head != NULL) {
		FromendOutput(head->link);
		cout << head->data << " ";
	}
}


template                         //快慢指针定位倒数第i个元素的地址
LinkNode* List::FromendLocate(int k) {
	if (k<1 || k>first->data) return NULL;
	LinkNode* slow = first->link;
	LinkNode* fast = Locate(k);
	while (fast->link != NULL) {
		fast = fast->link;
		slow = slow->link;
	}
	return slow;
};


template                         //迭代翻转链表
LinkNode* List:: Reverse01() {
	if (first->link == NULL) return first;
	LinkNode* current = first;
	LinkNode* prev = NULL;
	while (current != NULL) {
		LinkNode* next = current->link;
		current->link = prev;
		prev = current;
		current = next;
	}
	first = prev;
}


template                         //递归翻转链表
LinkNode* Reverse02(LinkNode* head) {
	if (head->link==NULL) return head;
	LinkNode* newHead =Reverse02(head->link);
	head->link->link = head;
	head->link = NULL;
	return newHead;
}


template                         //合并两个已经排好序的链表
LinkNode* Merge(LinkNode* Afirst, LinkNode* Bfirst)     {
	LinkNode* Cfirst = new LinkNode(Afirst->data+Bfirst->data);
	LinkNode* Ccurrt = Cfirst;
	Afirst = Afirst->link; Bfirst = Bfirst->link;
	while (Afirst != NULL && Bfirst != NULL) {
		if (Afirst->data <= Bfirst->data) { 
			LinkNode* newNode = new LinkNode(Afirst->data); 
			Ccurrt->link = newNode;
			Afirst = Afirst->link;
		}
		else {
			LinkNode* newNode = new LinkNode(Bfirst->data);
			Ccurrt->link = newNode;
			Bfirst = Bfirst->link;
		}
		Ccurrt = Ccurrt->link;
	}
	while (Afirst != NULL) {
		LinkNode* newNode = new LinkNode(Afirst->data);
		Ccurrt->link = newNode;
		Ccurrt = Ccurrt->link;
		Afirst = Afirst->link;
	}
	while (Bfirst != NULL) {
		LinkNode* newNode = new LinkNode(Bfirst->data);
		Ccurrt->link = newNode;
		Ccurrt = Ccurrt->link;
		Bfirst = Bfirst->link;
	}
	LinkNode* del = Cfirst;
	Cfirst = Cfirst->link;
	delete del;
	return Cfirst;
}


template                         //找到两个单向链表相交的第一个公共点
LinkNode* FindFirstCommonNode(LinkNode Afirst, LinkNode Bfirst) {
	if (Afirst.link == NULL || Bfirst.link = NULL) return NULL;
	int substract = Afirst->data - Bfirst->data; int k = 0;
	LinkNode* slow; LinkNode* fast;
	if (substract>=0) {
		slow = Bfirst->link;
		fast = Afirst->link;
	}
	else {
		slow = Afirst->link;
	    fast = Bfirst->link;
	}
	while (k < abs(substract)) {
		k++;
		fast = fast->link;
	}
	while (slow!=NULL&&fast!=NULL) {
		if (slow->data == fast->data) return slow;
		slow = slow->link;
		fast = fast->link;
	}
		return NULL;
}


template                       //删除有序链表中重复元素(不考虑附加结点)
void deleteDuplicates(LinkNode* head) {
	if (head== NULL) return;
	LinkNode* currt = head;
	while (currt != NULL&&currt->link !=NULL) {
		if (currt->data == currt->link->data) {
			LinkNode* del = currt->link;
			currt->link = del->link;
			delete del;
		}
		currt = currt->link;
	}
}


template                         //重载=
List& List:: operator=(List& L) {
	LinkNode*srcptr = L.getHead();
	LinkNode* destptr = first = new LinkNode;
	first->data = srcptr->data;
	while (srcptr->link!= NULL) {
		srcptr = srcptr->link;
		T temp = srcptr->data;
		destptr->link = new LinkNode(temp);
		destptr = destptr->link;
	}
	destptr->link = NULL;
	return *this;
}

下面为测试代码

//void test01() {
//	List L1(10);
//	if (L1.Insert(0, 1))cout << "插入成功" << endl;
//	if (L1.Insert(2, 15))cout << "插入成功" << endl;
//	if (L1.Insert(1, 8))cout << "插入成功" << endl;
//	cout << "正序输出L1："; L1.output();
//	cout << "倒序输出L1："; FromendOutput(L1.getHead()); cout << endl;
//	List L2(L1);
//	int x;
//	if(L2.Remove(1, x)) cout <<"L2已成功删除第1个数："<< x << endl;
//	L2.inputRear(0);
//	List L3 = L2;
//	L3.output();
//	cout << "L3倒数第2个数为：" << L2.FromendLocate(2)->data << endl;
//	L3.Reverse01();
//	cout << "L3第一次迭代翻转后链表为："; L3.output();
//	LinkNode* FirstL3 = L3.getHead();
//	FirstL3 = Reverse02(FirstL3);
//	cout << "L3第二次递归翻转后链表为：";
//	while (FirstL3!=NULL) {
//		cout << FirstL3->data << " ";
//		FirstL3 = FirstL3->link;
//	}
//	cout << endl<<"合并L1和L2："; LinkNode* Cfirst=Merge(L1.getHead(), L2.getHead());
//	LinkNode* temp = Cfirst;
//	while (temp != NULL) {
//		cout << temp->data << " ";
//		temp = temp->link;
//	}
//	cout << endl << "删除重复元素后："; deleteDuplicates(Cfirst);
//	temp = Cfirst;
//	while (temp != NULL) {
//		cout << temp->data << " ";
//		temp = temp->link;
//	}
//}