问题描述 :

目的：使用C++模板设计单链表的抽象数据类型（ADT）。并在此基础上，使用单链表ADT的基本操作，设计并实现单链表的简单算法设计。

内容：（1）请使用模板设计单链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的ADT原型文件。）

（2）ADT的简单应用：使用该ADT设计并实现单链表应用场合的一些简单算法设计。

应用：假设用单链表 A存储m个整数，结点的结构为(data,next)，且|data|<=N（N为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表A中的数据元素data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。

参考函数原型：

template
void Delete_Equal_Node( LinkList &A, int N );

输入说明 :

第一行：单链表A的长度 限定值N （以空格分隔）

第二行：单链表A的数据元素（数据元素之间以空格分隔）

输出说明 :

第一行：单链表A的遍历结果

空行

第二行：提纯后单链表A的遍历结果

单链表ADT模板简单应用算法设计：单链表的连接

#include<iostream>
using namespace std;
typedef int Elemtype;
//定义单链表结点类型
typedef struct LNode {
	Elemtype data;//每个节点存放一个数据元素
	struct LNode* next;//指针指向下一个元素
}LNode, * LinkList;
//正向建立单链表
LinkList List_TailInsert(LinkList& L, int length) {
	Elemtype x;
	L = new LNode;//建立头结点
	LNode* s, * r = L;//r为表尾指针
	for (int i = 0; i < length; i++) {
		cin >> x;
		s = new LNode;
		s->data = x;
		r->next = s;
		r = s;//r指向新的表尾结点
	}
	r->next = NULL;//尾结点指针置空
	return L;
}
//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode* p, Elemtype e) {
	if (p == NULL)
		return false;
	LNode* s = new LNode;
	if (s == NULL)//内存分配失败
		return false;
	s->data = e;//用结点s保存数据元素e
	s->next = p->next;
	p->next = s;//将结点s连接到p之后
	return true;
}
//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode* p, Elemtype e) {
	if (p == NULL)
		return false;
	LNode* s = new LNode;
	if (s == NULL)
		return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;

}
//输出单链表
void ListCout(LNode* p) {
	p = p->next;
	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
}
//删除指定结点p
bool DeleteNode(LNode* p) {
	if (p == NULL)
		return false;
	LNode* q = p->next;//令q指向p的后继结点
	p->data = p->next->data;//和后继结点交换数据域
	p->next = q->next;//将*q结点从链中“断开”
	free(q);//释放后继结点的存储空间
	return true;
}
//求表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != NULL) {
		p = p->next;
		len++;
	}
	return len;
}
//按位序删除（带头结点）
bool ListDelete(LinkList& L, int i) {
	if (i < 1)
		return false;
	LNode* p;//指针p指向当前扫描到的结点
	int j = 0;//当前p指向的是第几个结点
	p = L;//L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)//i值不合法
		return false;
	if (p->next == NULL)//第i-1个结点之后已无其他结点
		return false;
	LNode* q = p->next;
	//e = q->data;//用e返回元素的值
	p->next = q->next;//将*q结点从链中”断开“
	free(q);//释放结点的存储空间
	return true;//删除成功
}
//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
	int j = 1;
	LNode* p = L->next;
	if (i == 0)
		return L;
	if (i < 1)
		return NULL;
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
void Delete_Equal_Node(LinkList L)//测试数据限定为整数。实际应用时，不受其限制
{
	int len = Length(L);
	for (int i = 1; i < Length(L); i++) {
		for (int j = i + 1; j <= Length(L); j++) {
			if (abs(GetElem(L, i)->data) == abs(GetElem(L, j)->data))
				ListDelete(L, j);
		}
	}
	for (int i = 1; i < Length(L); i++) {
		for (int j = i + 1; j <= Length(L); j++) {
			if (abs(GetElem(L, i)->data) == abs(GetElem(L, j)->data))
				ListDelete(L, j);
		}
	}
	ListCout(L);
}
int main() {
	LinkList L;
	int length1;
	cin >> length1;

	int N;
	cin >> N;

	List_TailInsert(L, length1);
	ListCout(L);
	cout << endl << endl;
	Delete_Equal_Node(L);
	return 0;
}