如何将圆形链表移到左侧？ [英] How do I shift a circular linked list to the left?
问题描述
我有我的程序，这是一项差不多完成的任务。但我似乎无法获得使链表正确移动的代码。每次更改内容时都会出现太多错误。
这是代码的一部分，仅来自主文件。如果你看到
下的代码void circular_llist :: play_game（）这是我无法得到的部分。
我需要它会像这样转变。 1< -2< -3< -4< -5< -3< -3< -4< -5< -1
Hi, I've got my program, which is an assignment almost done. But I can't seem to get the code to shift the linked list correct. Too many errors every time I change something.
Here's part of the code, just from the main file. If you see the code under
"void circular_llist::play_game()" that's the part I can't get.
I need it to shift like this. 1<-2<-3<-4<-5 to 2<-3<-4<-5<-1
void circular_llist::create_node(string value)
{
struct node *temp;
temp = new(struct node);
temp->info = value;
if (last == NULL)
{
last = temp;
temp->next = last;
}
else
{
temp->next = last->next;
last->next = temp;
last = temp;
}
}
/*
Insert player at the front
*/
void circular_llist::add_begin(string value)
{
if (last == NULL)
{
cout<<" First Create the queue."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->info = value;
temp->next = last->next;
last->next = temp;
}
/*
Insert player anywhere
*/
void circular_llist::add_after(string value, int pos)
{
if (last == NULL)
{
cout<<" Create queue first."<<endl;
return;
}
struct node *temp, *s;
s = last->next;
for (int i = 0;i < pos-1;i++)
{
s = s->next;
if (s == last->next)
{
cout<<" There are less than ";
cout<<pos<<" in the queue"<<endl;
return;
}
}
temp = new(struct node);
temp->next = s->next;
temp->info = value;
s->next = temp;
/*Inserted player at the end*/
if (s == last)
{
last=temp;
}
}
/*
Delete players in queue
*/
void circular_llist::delete_element(string value)
{
struct node *temp, *s;
s = last->next;
/* If List has only one element*/
if (last->next == last && last->info == value)
{
temp = last;
last = NULL;
free(temp);
return;
}
/*First Element Deletion*/
if (s->info == value)
{
temp = s;
last->next = s->next;
free(temp);
return;
}
while (s->next != last)
{
/*Delete the elements in between*/
if (s->next->info == value)
{
temp = s->next;
s->next = temp->next;
free(temp);
cout<<" Player "<<value;
cout<<" deleted from the queue"<<endl;
return;
}
s = s->next;
}
/*Delete the last element*/
if (s->next->info == value)
{
temp = s->next;
s->next = last->next;
free(temp);
last = s;
return;
}
cout<<" Player "<<value<<" not found in the queue"<<endl;
}
/*
Simulate the jump
*/
void circular_llist::play_game()
{
// SHIFT THE CIRCULAR LINKED LIST TO THE LEFT
// For Example:
// 1<-2<-3<-4<-5 to 2<-3<-4<-5<-1
}
/*
Display the queue
*/
void circular_llist::display_list()
{
struct node *s;
if (last == NULL)
{
cout<<" Queue is empty, nothing to display"<<endl;
return;
}
s = last->next;
cout<<"\n Players in queue: \n"<<endl;
while (s != last)
{
cout<<s->info<<" <- ";
s = s->next;
}
cout<<s->info<<endl;
}
推荐答案
目前尚不清楚你称之为左。如果左轮换与next相同，则转换类似于current = current-> next。如果左方向相反，我建议您使用双链接列表并使用current-> previous。没有这样的会员？让我告诉你：如果你要转向相反的方向，甚至很少，这将使双链接超过实际。
替代方案， sillier方法将重复current-> next操作N-1次，其中N是当前的元素数量。
每次操作都不支持这个数字甚至更傻。在这种情况下，您需要记住初始指针，并且移位N次，而不是N - 1。只有这样，在不知道N的情况下，您可以检测到您执行了往返。在这种情况下，您必须记住堆栈变量中的前一个指针。往返后，你会想起这个变量。这是你的答案。
所以，我描述了三种不同的算法，从最先使用大多数冗余和最合理的算法到第三，没有冗余，实际上几乎是愚蠢的。 :-)
-SA
It's not clear what do you call "left". If the "left" rotation is the same asnext, the shift would be something likecurrent = current->next. If left direction is opposite, I would suggest you have double-linked list and usecurrent->previous. Don't have such member? Let me tell you: if you are going to do shift in the opposite direction ever, even rarely, this will make double-link more than practical.
Alternative, the sillier approach would be repeatingcurrent->nextoperationN − 1times, whereNis the current number of elements.
Not supporting this number on each operation would be even sillier. In this case, you would need to remember initial pointer, and do shiftsNtimes, notN − 1. Only this, way, without knowingN, you can detect that you performed the round trip. And in this case, you have to remember the previous pointer in the stack variable. After the round trip, you recall this variable. This is your answer.
So, I described you three different algorithms, ranging from first, using most redundancy and most reasonable, to the third, using no redundancy and almost idiotic in practical terms. :-)
—SA
你说的是循环链表（没有加倍链接）列表）所以我假设一个单链表。对于左，我假设您的意思是 - 对于序列ABC - 您想要BCA，其中项目按从左到右的顺序排列。
主要优势链接列表是你可以通过改变指针而不是复制整个对象来移动东西。
附注：不要混合新的和免费的。使用new / delete。
You said "circular" linked list (not doubly linked list) so I'll assume a singly linked list. For "left", I'll assume you mean - for the sequence ABC - you want BCA where the items are arranged in left to right order.
The main advantage of linked lists is you can move things around by changing pointers instead of copying entire objects.
Side note: don't mix new and free. Use new / delete.
struct Node
{
Node *next;
std::string value;
};
Node *last = NULL;
指针last指向最后一个节点。如果last不为null，则last-> next指向第一个节点。
示例：零节点，last为null。
示例：一个节点A，其中最后一个指向A，指向A。
示例：两个节点A和B，其中最后一个点到B指向A指向B.
示例：三个节点A，B，C其中最后指向C指向A指向B指向C指回A.
插入/删除节点的代码需要执行以下规则：
last为null或指向最后一个节点。
节点总是形成一个循环图。
改变整个事物离开，最后移到A.
在代码中，
Your pointer "last" points to the last node. If last is not null, last->next points to the first node.
Example: zero nodes, last is null.
Example: one node A where last points to A which points back to A.
Example: two nodes A and B where last points to B which points to A which points back to B.
Example: three nodes A, B, C where last points to C points to A points to B points to C points back to A.
Your code to insert / remove nodes will need to enforce the following rules:
last is null or points to the last node.
The nodes always form a cyclic graph.
To shift the whole thing left, move last to A.
In code,
if (last != NULL) last = last->next;
就是这样！
That's it!
这篇关于如何将圆形链表移到左侧？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
