描述
设计如下样式的链表类模板list,并对其进行简单使用。
template <class T> 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();
//将各链表项数据 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 数据进行显示(输出元素之间用一个空格隔开)。
要求:在主函数中,需要创建两个链表link1和link2,将输入的所有链表元素依次通过Append加到link1中,并依次通过Insert加到link2中。
输入
输入一共有三行,第一行为链表类型 (只需考虑int/char,均为小写即可);
第二行为链表长度;
第三行依次输入链表元素。
输出
输出有六行,第一行为link1.count()的结果;
第二行为link1.display()的结果;
第三行为link1经过ttoh()后,link1.display()的结果;
第四行为link2.count()的结果;
第五行为link2.display()的结果;
第六行为link2经过htot()后,link2.display()的结果。
样例输入
int
5
1 2 3 4 5
样例输出
5
1 2 3 4 5
5 1 2 3 4
5
5 4 3 2 1
4 3 2 1 5
#include<iostream>
#include<string>
using namespace std;
template <class T> class list {
struct node {
T data;
node * next;
} *head, *tail;
public:
list();
void Insert(T item);
void Append(T item);
int count();
void htot();
void ttoh();
void display();
};
template <class T> list<T>::list() {
head = NULL;
tail = NULL;
}
template <class T> void list<T>::Append(T item) {
node *p;
p = new node;
p->data = item;
p->next = NULL;
if (tail) {
tail->next = p;
}
tail = p;
if (head == NULL) {
head = tail;
}
}
template <class T> void list<T>::Insert(T item) {
node *p;
p = new node;
p->data = item;
p->next = NULL;
if (head) {
p->next = head;
}
head = p;
if (tail == NULL) {
tail = head;
}
}
template <class T> int list<T>::count() {
node *p = head;
int num = 0;
while (p) {
num++;
p = p->next;
}
return num;
}
template<class T> void list<T>::htot() {
if (tail != NULL) {
tail->next = head;
tail = head;
head = head->next;
tail->next = NULL;
}
}
template<class T> void list<T>::ttoh() {
node *q, *p = head;
q = p;
if (p != NULL) {
while (p->next) {
q = p;
p = p->next;
}
tail->next = head;
head = tail;
tail = q;
tail->next = NULL;
}
}
template<class T> void list<T>::display() {
node *p = head;
while (p) {
cout << p->data;
p = p->next;
if (p != NULL) {
cout << " ";
}
}
if (head == NULL) {
cout << "emptylist";
}
cout << endl;
}
int main() {
string type;
cin >> type;
if (type == "char") {
list <char> link1;
list <char> link2;
int num;
cin >> num;
for (int i = 0; i < num; i++) {
char d;
cin >> d;
link1.Append(d);
link2.Insert(d);
}
cout << link1.count() << endl;
link1.display();
link1.ttoh();
link1.display();
cout << link2.count() << endl;
link2.display();
link2.htot();
link2.display();
}
if (type == "int") {
list <int> link1;
list <int> link2;
int num;
cin >> num;
for (int i = 0; i < num; i++) {
int d;
cin >> d;
link1.Append(d);
link2.Insert(d);
}
cout << link1.count() << endl;
link1.display();
link1.ttoh();
link1.display();
cout << link2.count() << endl;
link2.display();
link2.htot();
link2.display();
}
return 0;
}