交换单链表中的节点
我试图交换两个节点。 例如,如果节点是a
和b
我正在传递指针
(a-1)->next
和(b-1)->next
,它们基本上是节点a
和b
。
void swap(struct stack **a,struct stack **b) { struct stack *temp1 = *a, *temp2 = *b, *temp3 = *b; *a = *b; (*b)->next = (temp1)->next; temp2 = temp1; (temp2)->next = temp3->next; }
我究竟做错了什么? 当我在调用函数后尝试打印节点时,它是一个无限循环。 请帮忙。
为什么无限循环?
无限循环是因为调用swap()
函数后列表中的自循环。 在swap()
代码中,以下语句是错误的。
(*b)->next = (temp1)->next;
为什么? :因为在swap()
函数中赋值语句后, temp1
的下一个开始指向b
节点。 node[b]
的下一个指向循环。 自循环是无限循环的原因,在代码中的某个位置遍历链表。
下面我将展示swap()
如何逐步工作。 可能这有助于您了解您的错误 :
你没有提到,但我假设链接列表在a
和b
之间有以下关系:( 阅读红色评论 )
(步骤1):
+----+----+----+ +---+----+----+ | one |----->| two | +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | *a | *b | | temp1 temp2, temp3 "after assignment to temp variables" (step-2): ^ | *a = *b | *a "<--- next step"
(步骤3):车辆声明
(*b)->next = (temp1)->next; "Change link: (temp1)->next; is `two` node" " *b is `two`, So Self loop" +----+----+----+ +---+----+----+ <---| | one | | two |-----| +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp1 temp2, temp3 " after assignment to temp"
见(temp1)->next;
实际上是b
你正在分配(*b)->next = (*b)
做(*b)->next = (temp1)->next;
因此添加了一个自循环。
(第4步):
我认为使用图表可以很容易地理解swap()
代码的最后两行:
temp2 = temp1; (temp2)->next = temp3->next;
以下是这两行的图表:
temp2 = temp1; +----+----+----+ +---+----+----+ <---| | one | | two |-----| "<--- Self loop" +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp2 = temp1; temp3
(步骤5):即使你的函数swap()
最后一行左循环如下:
(temp2)->next = temp3->next; " last line of your code" +----+----+----+ +---+----+----+ <---| | one |----->| two |-----| "<-- Self loop" +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp2 = temp1; temp3
所以循环仍然在two
节点那么无限循环。
如何在单个链表中交换两个节点?
一种方法是交换节点的数据,而不是交换节点在链表中自己的位置( 正如我对你的问题所评论 )。 但是你想在列表中交换节点的位置。
好吧,这个好! 如果节点数据大小较大,那么它更好地交换节点的位置而不是交换节点的数据( 交换数据将是不好的选择 )
因为您有单个链表 ,要交换列表中的任意两个任意节点,您也需要 先前的节点地址 。 ( 这是您在交换逻辑中不考虑的一点 )
为什么需要以前的指针? :
假设在一些成功的插入(推送)操作之后,您的列表变为如下:
0 <--------TOP - "head" 9 <--p 2 6 <--q 5
水平图 - 假设您要交换说两个节点(q)
和(p)
:
+---+ +---+ +---+ +---+ +---+ | 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |--- +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ null | | | | (q) (p) (head)
正如我所说,交换我们需要先前的指针。 你需要考虑以下
( 理论上,我正在为特定节点(p)
和(q)
编写,只是为了使解释简单。但我的实现是退出一般 ):
在列表中的前一个指针:
node[0] points to node[9] that is (q), and node[2] points to node[6] that is (p)
和
node[9] points to node[2] node[6] points to node[5]
注意:如果要交换两个节点,如node[ 9 ]
和node[ 6 ]
,则应使用这两个节点之前的节点的指针。
例如:两个交换node[ 9 ]
和[ 6 ]
,您还需要在上图中更改node[ 0 ]
下一个指针和node[ 2 ]
下一个指针。
交换这两个节点后列表怎么样?
+---+ +---+ +---+ +---+ +---+ | 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |--- +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ null | | | | (p) (q) (head)
现在在以前的节点[o]
和[2]
什么?
交换后,列出以前的指针
node[0] points to node[6] that is (q), and node[2] points to node[9] that is (p)
和
node[9] points to node[5] node[6] points to node[2]
所以如果你想交换两个节点; 前一个节点也有效果,因为列表是单链接列表,你也需要先前的指针。
如何找到以前的节点指针?
假设您要交换任意两个节点node[p]
和node[q]
那么您可以使用head pointer
来查找上一个节点。
所以交换函数语法 ( 在我的实现中 )就像:
void swap(struct stack **head, // head node struct stack **a, // first candidate node to swap struct stack **b); // first candidate node to swap
你会称之为以下function:
swap(&head, &p, &q);
定义:( 要理解代码,请阅读我几乎每行添加的评论 )
void swap(struct stack **head, struct stack **a, struct stack **b){ // first check if a agrgument is null if( (*head) == NULL || // Empty list (*a) == NULL || (*b) == NULL){ // one node is null // Nothing to swap, just return printf("\n Nothing to swap, just return \n"); return; } // find previos nodes struct stack* pre_a = get_prevnd(*head, *a); struct stack* pre_b = get_prevnd(*head, *b); //Now swap previous node's next if(pre_a) pre_a->next = (*b); // a's previous become b's previous, and if(pre_b) pre_b->next = (*a); // b's previous become a's previous //Now swap next fiels of candidate nodes struct stack* temp = NULL; temp = (*a)->next; (*a)->next = (*b)->next; (*b)->next = temp; //change head: if any node was a head if((*head)==(*a)) *head = *b; else if((*head)==(*b)) *head = *a; }
在swap()
函数中你可以注意到我调用了一个辅助函数get_prevnd(, );
。 此函数返回列表中上一个节点的地址。 在函数get_prevnd(, );
,第一个参数是列表头,第二个参数是您要查找的节点。
// find previous node function() struct stack* get_prevnd( struct stack* head, struct stack* a ){ if(head == a){ // node[a] is first node return NULL; } struct stack* temp = head; // temp is current node struct stack* pre_a = NULL; while(temp && temp!=a){ //search while not reach to end or the node pre_a = temp; // find previous node temp = temp->next; } if(temp!=a){// node[a] not present in list fprintf(stderr, "\n error: node not found!\n"); exit(EXIT_FAILURE); // bad technique to exit() } return pre_a; }
幸运的是代码是工作:)。 以下是此代码在线测试的链接。 我测试了各种输入。
CodePad: 在单个链表中交换节点。 请检查输出。
抱歉英语不好
我希望剪切和粘贴代码,但没有找到它。 如果有人仍然感兴趣,这就是答案。 我对所有3个案例进行了蛮力分析。
// swaps nodes at locations *sp and *tp struct stack *s = *sp; // store locations to prevent overwritten bugs struct stack *t = *tp; if(&t->next == sp) { // order u (tp)-> t (sp)-> s -> ... t->next = s->next; s->next = t; *tp = s; } else if(&s->next == tp) { // order u (sp)-> s (tp)-> t -> ... s->next = t->next; t->next = s; *sp = t; } else { // disconnected u (sp)->s -> ..., v (tp)->t -> ... struct stack *next = s->next; s->next = t->next; t->next = next; *sp = t; *tp = s; } // If you track the end of your list, it be the one pointing to NULL. if(s->next == NULL) { end = &s->next; } else if(t->next == NULL) { end = &t->next; }
注意:如果sp == tp,此代码有效,但假设您没有BOTH&s-> next == tp &&&t-> next == sp(以循环开始)的病态情况。
"KING KHAN"
SwapanyTwoNodeData(int, int);
这个函数取两个整数作为参数并交换它们
节点数据。
1->2->6->3->4->5
SwapanyTwoNodeData (2,4);
1->3->6->2->4->5
100%的工作function。 。 。 。 请享用。
void Swap_Any_Two_Locations_data(int x,int x1){ if(head!=NULL){ int count=1,count1=1; Node *temp,*temp1; temp=head; temp1=head; while(temp->next!=NULL && count!=x ){ temp=temp->next; count++; } while(temp1->next!=NULL && count1!=x1){ temp1=temp1->next; count1++; } if(count==x && count1==x1){ int z=0; z=temp->info; temp->info=temp1->info; temp1->info=z; cout<<"Data Swapped"<