要求:
将一个已知的单向循环链表进行逆置运算,如(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;
}
运行结果如下图所示: