题目描述
设计如下样式的链表类模板list，并对其进行简单使用。
template class list{
／／类模板 list，使用类型形参 T
struct node{
／／结构体 node 类型用来定义链表表项（的具体数播项）
T data;
／／每一表项的 data 数据域的类型由类型形参T 所指定
node·next;
／／通过推针 next，将多个表项“链接”成一个链表
)*head,*tail;
／／数据成员 head 与 tail.为链表的首尾指针
public:
list（）；／／构造函数，创建“空链表”
void Insert (T item); ／／生成链表项插入到原链的链首
void Append（T item）；／／生成链表项附加到原链的链尾
int count();
void htot();
void ttoh();
void display();
void sortList();
／／返固当前链表的项数
／／把链表首项移到链尾
／／把链表尾项移到链首
／／将各链表项数据 data 显示在屏幕上
／／将各链表项数据 data 排序后显示在屏基上
};
八个成员函数的具体功能描述如下：
1．list ():构造函数，将head与tail 均置为NULL，意味着创建出一个“空链表”。
2．void Insert（T item）；动态生成一块链表项空间，并将T类型的数据item放入该链表项的data域，而后将新生成的该链表项播入到原链的链首（链表的“栈式用法）。
3．void Append（T item）：动态生成一块链表项空间，并将T类型的数据 item 放入该链表项的data域，而后将新生成的该链表项附加到原链的链尾（链表的队列式用法）。
4．int count()：“数出”并返回当前链表的数据项数：空链时返回0；链表非空时，意味着要“遍历”链表，即从头到尾“数”出链表的项数后返回。
5．void htot（）：把链表首项移到链尾：空链或仅一项时无须移动：否则，要将原链菌项“接到”其尾项之后，而后马上调整新链首指针 head 以及新链尾指针 tail.
6．void ttoh（）：把链表尾项移到链首：空链或仅一项时无须移动：否则，要将原链尾项“挪到”链首，而后马上调整新链首指针 head以及新链尾指针 tail.
7．void display()：将各链表项数据 data 显示在屏幕上：空链时输出“emptylist”；否则要对链表进行“遍历”，从头到尾逐项对其data数据进行显示（输出元素之间用一个空格隔开）。
8.void SortList():
将各链表项数据 data 排序后显示在屏幕上：首先按照链表的数据从大到小顺序（按ASCII码排序）进行排序，并将其输出的结果。
要求：
在主函数中，需要创建两个链表link1和link2，将输入的所有链表元素依次通过Append加到link1中，并依次通过Insert加到link2中，必须用链表实现，否则0分。
输入
输入一共有三行，第一行为链表类型（只需考虑int／char，均为小写即可）：第二行为链表长度：第三行依次输入链表元素。
输出
输出有七行：
第一行为link1．count()的结果：
第二行为link1．display()的结果：
第三行为link1经过ttoh()后，link1．display()的结果：
第四行为link2．count()的结果：
第五行为link2．display()的结果：
第六行为link2经过htot()后，link2．Display()的结果：
第七行为link1或者link2 SortList()的结果：
样例输入1
int
5
52341
样例输出1
5
52341
15234
5
14325
43251
54321
样例输入2
Char
3
bac
样例输出2
3
bac
cba
3
cab
abc
cba
你自己能做多少呢？
#include <iostream>
using namespace std;
template <class T>
class list {
// 定义链表节点结构体
struct node {
T data; // 数据域
node *next; // 指向下一个节点的指针
} *head, *tail; // 链表的头尾指针
public:
// 构造函数，创建空链表
list() : head(NULL), tail(NULL) {}
// 在链表头插入新节点
void Insert(T item) {
// 动态分配新节点空间
node *newNode = new node{item, head};
// 将新节点插入到链表头
head = newNode;
// 如果链表为空，则更新尾指针
if (tail == NULL) tail = newNode;
}
// 在链表尾添加新节点
void Append(T item) {
// 动态分配新节点空间
node *newNode = new node{item, NULL};
// 如果链表为空，则更新头尾指针
if (tail == NULL) {
head = newNode;
tail = newNode;
} else {
// 否则将新节点添加到链表尾
tail->next = newNode;
tail = newNode;
}
}
// 计算并返回链表中的节点数
int count() {
int cnt = 0;
for (node *p = head; p != NULL; p = p->next) ++cnt;
return cnt;
}
// 将链表首项移到链尾
void htot() {
if (head == NULL || head->next == NULL) return;
node *p = head;
head = head->next;
tail->next = p;
tail = p;
p->next = NULL;
}
// 将链表尾项移到链首
void ttoh() {
if (head == NULL || head->next == NULL) return;
node *p = head;
while (p->next != tail) p = p->next;
tail->next = head;
head = tail;
tail = p;
p->next = NULL;
}
// 显示链表中的数据项
void display() {
if (head == NULL) cout << "emptylist";
for (node *p = head; p != NULL; p = p->next)
cout << p->data << ' ';
}
// 对链表中的数据项进行排序并显示结果
void sortList() {
for (node *p1 = head; p1 != NULL; p1 = p1->next)
for (node *p2 = p1->next; p2 != NULL; p2 = p2->next)
if (p1->data < p2->data) swap(p1->data, p2->data);
}
};
int main() {
string type; cin >> type;
if (type == "int") {
list<int> link1, link2;
int n; cin >> n;
for (int i=0; i<n; ++i) {
int x; cin >> x;
link1.Append(x);
link2.Insert(x);
}
cout << link1.count() << endl;
link1.display(); cout << endl;
link1.ttoh();
link1.display(); cout << endl;
cout << link2.count() << endl;
link2.display(); cout << endl;
link2.htot();
link2.display(); cout << endl;
link1.sortList();
link1.display(); cout << endl;
} else if (type == "char") {
list<char> link1, link2;
int n; cin >> n;
for (int i=0; i<n; ++i) {
char x; cin >> x;
link1.Append(x);
link2.Insert(x);
}
cout << link1.count() << endl;
link1.display(); cout << endl;
link1.ttoh();
link1.display(); cout << endl;
cout << link2.count() << endl;
link2.display(); cout << endl;
link2.htot();
link2.display(); cout << endl;
link1.sortList();
link1.display(); cout << endl;
}
}