qq_45735316 2020-09-24 21:21 采纳率: 94.1%
浏览 154
已采纳

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

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

#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;
}

  • 写回答

2条回答 默认 最新

  • 泡视界 2020-09-25 11:37
    关注

    整个while循环里面实现的就是链表的反转。
    t 可以想作是temp的简写,意思就是是零时的节点指针。

    如何反转呢?
    1.让temp node指向current node,就是用temp记录下当前node。
    2.让current node指向next node; ,之前node由temp记录下来了,所以current指针功能上就解放出来可以用于记录下一个node。
    3. 将temp node,也就是实际的当前node的next成员(t->next)指向last node也就是上一个节点,这样就可以实现当前节点的反转。
    4.将用于记录last node的指针指向temp node, 之前已经反转了当前node,所以记录last node的指针功能上就解放出来,可以用于记录下一次反转的last node。
    5. 循环直到,temp node为空

    所以你看代码
    用s->next作为上述过程第4步种用于记录last node的指针。
    s->next = t 这句话就是实现了上述步骤的第4步

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题