这代码应该怎么改？能不能顺便解释一下s->next = t;的作用

Z时代
2024-01-10
分类：技术分享

实现单链表逆置的算法
图片说明

#include <iostream>
using namespace std;
template<class T>
struct Node//结点
{
T data;//数据域
Node<T>* next;//指针域：下一个元素的地址
};
template<class T>
class LinkList//线性表类
{
public:
LinkList();
LinkList(T a[], int n);
~LinkList();
void PrintList();
T Get(int i);
void Insert(int i, T x);
void Delete(int i);
public:
Node<T>* first;//单链表（线性表的第一个元素？）
};
template<class T>
LinkList<T>::LinkList()//默认构造函数
{
first = new Node<T>;//第一个元素为新创建结点对象
first->next = NULL;//第一个元素对象的指针域为空
}
template<class T>
LinkList<T>::LinkList(T a[], int n)//构造函数
{
first = new Node<T>;
Node<T>* r = first;//当前的结点指向线性表的第一个结点/元素
for (int i = 0; i < n; i++)
{
Node<T>* s = new Node<T>;//创建下一个结点
s->data = a[i];//结点的数据域为数组a的第i个元素
r->next = s;//当前结点的指针域指向新创建的结点s
r = s;//当前结点向后移
}
r->next = NULL;//最后一个结点的指针域为空
}
template<class T>
LinkList<T>::~LinkList()
{
while (first != NULL)//一个个删除结点
{
Node<T>* q = first;//q赋值为当前结点
first = first->next;//first赋值为下一个结点
delete q;//删除当前结点
}
}
template<class T>
void LinkList<T>::PrintList()
{
Node<T>* p = new Node<T>;//p为新创建的结点
p = first->next;//？？？工作指针p初始化，p指向当前结点的指针域/当前结点？？？
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
}
template<class T>
T LinkList<T>::Get(int i)
{
Node<T>* p = first->next;
int count = 1;
while (p != NULL && count < i)
{
p = p->next;
count++;
}
if (p == NULL) throw "查找位置异常";
else return p->data;
}
template<class T>
void LinkList<T>::Insert(int i, T x)
{
Node<T>* p = first;
int count = 0;
while (p != NULL && count < i - 1)
{
p = p->next;
count++;
}
if (p == NULL) throw "插入位置异常";
else
{
Node<T>* s = new Node<T>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
template<class T>
void LinkList<T>::Delete(int i)
{
Node<T>* p;
int j;
p = first; j = 0;  //工作指针p初始化
while (p != NULL && j < i - 1)  //查找第i-1个结点
{
p = p->next;
j++;
}
if (p == NULL || p->next == NULL) throw "删除位置异常";  //结点p不存在或结点p的后继结点不存在
else {
Node<T>* q;
T x;
q = p->next; x = q->data;  //暂存被删结点
p->next = q->next;  //摘链
delete q;
}
}
template<class T>        //复制单链表
Node<T>* Copy(Node<T>* s)//返回一个结构体？
{
Node<T>* head = new Node<T>;
Node<T>* r = head;//新线性表p的工作指针
Node<T>* p = s;//线性表a的工作指针
p = p->next;//p移到第一个结点
while (p != NULL)
{
Node<T>* t = new Node<T>;//创造一个新结点
t->data = p->data;//复制线性表a中的值
r->next = t;//当前结点指向新创造的结点
r = t;//工作指针移到新的结点
p = p->next;//线性表a中的工作指针后移，同一个指针后移：p=p->next
}
r->next = NULL;
return head;
}
template<class T>        //单链表逆置
void Reverse(Node<T>* s)//s为线性表a头结点
{
Node<T>* p = s->next；//p指向第一个结点
s->next = NULL;//头结点指向空
while (p != NULL)
{
Node<T>* t = p;//t为工作指针
p = p->next;//p后移
t->next = s->next;//
s->next = t;//???
}
}
int main()
{
int a[] = { 1,2,3,4,5 };
LinkList<int> test(a, 5);
cout << "线性表a的初始状态：" << endl;
test.PrintList();
cout << endl << "复制线性表a到线性表p,再逆置线性表a。" << endl;
Node<int>* p = new Node<int>;
p = Copy(test.first)->next;//Copy返回一个结点
Reverse(test.first);
cout << "线性表a的状态：" << endl;
test.PrintList();
cout << endl << "线性表p的状态：" << endl;
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
getchar();
return 0;
}