线性表的基本应用(三):单向循环链表的逆置

要求:

将一个已知的单向循环链表进行逆置运算,如(a,b,c,d,e)变为(e,d,c,b,a)。

思路:

首先建立一个带头结点的单循环链表并遍历输出,然后将其逆序操作后再遍历输出。
逆序操作的实现:设pre为当前结点p的前驱,则需要将p的后继改为pre,然后将pre修改为指向p,将p修改为指向p原先的后继。
带头结点的单向循环链表表尾的判别:如果p的后继为头结点,则p为表尾结点。

#include <bits/stdc++.h>
using namespace std;

typedef struct Node {
    int data;
    struct Node * pNext;
}NODE,*PNODE;

class LpList {
private:
    PNODE pHead;
    PNODE pTail;
    int cnt;
public:
    LpList(int cnt);
    void traverse();
    void invertOrder();
};

LpList::LpList(int cnt) {
    PNODE p = NULL;
    pHead = new Node();
    pTail = pHead;
    for (int i = 1; i<=cnt; i++) {
        p = new Node();
        printf("请输入第%d个结点的值:",i);
        scanf("%d",&(p->data));
        pTail->pNext = p;
        pTail = p;
        pTail->pNext = NULL;
    }
    pTail->pNext = pHead;
    this->cnt = cnt;
}

void LpList::traverse() {
    PNODE p = NULL;
    p = pHead->pNext;
    while (p != pHead) {
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");
}

//倒置
void LpList::invertOrder() {
    PNODE pre,p,q;
    pre = pHead;
    p = pre->pNext;
    //进行倒置操作
    while (p != pHead) {
        q = p->pNext; //用q存储p的后继结点
        p->pNext = pre; //使得p的后继为pre
        //将pre修改为指向p,将p修改为指向p原先的后继(即q),以便进行后面的倒序
        pre = p;
        p = q;
    }
    pHead->pNext = pre; //执行该行之前,pHead->pNext仍指向原顺序的首结点,故需要调整为逆序后的首结点
}

int main() {
    LpList lplList(6);
    lplList.traverse();
    lplList.invertOrder();
    lplList.traverse();
    return 0;
}

运行结果如下图所示:

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注