Scambia i nodes in una lista collegata singolarmente

Sto cercando di scambiare due nodes. Ad esempio se i nodes sono a e b sto passando i puntatori
(a-1)->next e (b-1)->next che sono sostanzialmente nodes a e 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; } 

Che cosa sto facendo di sbagliato? Quando provo a stampare i nodes dopo aver chiamato la funzione, si tratta di un ciclo infinito. Per favore aiuto.

Perché ciclo infinito?

Il ciclo infinito è dovuto al loop automatico nella tua lista dopo aver chiamato la funzione swap() . Nel codice di swap() seguente dichiarazione è bacata.

 (*b)->next = (temp1)->next; 

Perché? : Perché dopo l’istruzione di assegnazione nella funzione swap() , il successivo di temp1 punta a b node. E il node[b] punta a se stesso in un ciclo. E il ciclo autonomo è motivo di loop infinito , da qualche parte nel codice in cui si attraversa la lista collegata.

Di seguito ho disegnato per mostrare come swap() funziona passo dopo passo. Questo può aiutarti a capire il tuo errore :

Non hai menzionato, ma presumo che la lista collegata abbia una relazione tra b : ( leggi i commenti in rosso )

(passo 1):

 +----+----+----+ +---+----+----+ | one |----->| two | +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | *a | *b | | temp1 temp2, temp3 "after assignment to temp variables" (step-2): ^ | *a = *b | *a "<--- next step" 

(passaggio 3): la dichiarazione buggy

 (*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" 

Vedi (temp1)->next; è in realtà b e stai assegnando (*b)->next = (*b) facendo (*b)->next = (temp1)->next; quindi aggiungendo un auto loop.

(step-4):
Penso che con lo schema puoi facilmente capire quali sono le ultime due righe del tuo codice swap() :

 temp2 = temp1; (temp2)->next = temp3->next; 

Di seguito è riportato il mio diagramma per queste due righe:

 temp2 = temp1; +----+----+----+ +---+----+----+ <---| | one | | two |-----| "<--- Self loop" +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp2 = temp1; temp3 

(step-5): Anche l'ultima riga del tuo ciclo di funzione swap() sinistra come sotto:

  (temp2)->next = temp3->next; " last line of your code" +----+----+----+ +---+----+----+ <---| | one |----->| two |-----| "<-- Self loop" +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp2 = temp1; temp3 

Quindi loop ancora lì a two nodes in modo ciclo infinito.

Come scambiare due nodes nella singola lista collegata?

Un modo è quello di scambiare i dati del nodo invece di scambiare la posizione del nodo stesso nella lista collegata ( come ho commentato alla tua domanda ). Ma tu vuoi scambiare la posizione del nodo nella lista.
Bene bene! se la dimensione dei dati del nodo è maggiore, è meglio in quel momento scambiare la posizione del nodo piuttosto che scambiare i dati del nodo ( scambiare i dati sarà una ctriggers scelta )

Dato che hai una sola lista collegata , per scambiare due nodes arbitrari nella lista devi avere anchegli indirizzi dei nodes precedenti . ( questo è il punto che non consideri nella tua logica di scambio )

PERCHÉ hanno bisogno di indicazioni precedenti? :
Supponiamo che dopo alcune operazioni di inserimento (push) riuscite, l'elenco diventi il ​​seguente:

  0 <--------TOP - "head" 9 <--p 2 6 <--q 5 

Un diagramma orizzontale- Supponiamo di voler scambiare dire due nodes (q) e (p) :

 +---+ +---+ +---+ +---+ +---+ | 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |--- +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ null | | | | (q) (p) (head) 

Come ho detto, per scambiare abbiamo bisogno di indicazioni precedenti. Devi pensare al seguito
( In teoria, sto scrivendo per specifici nodes (p) e (q) solo per mantenere semplice la spiegazione, ma la mia implementazione è stata abbandonata in generale ):

Nella lista puntatori precedenti:

 node[0] points to node[9] that is (q), and node[2] points to node[6] that is (p) 

E

 node[9] points to node[2] node[6] points to node[5] 

AVVISO: se si desidera scambiare due nodes, ad esempio node[ 9 ] e node[ 6 ] è necessario utilizzare i puntatori dei nodes precedenti a questi due nodes.
Ad esempio: due node[ 9 ] scambio node[ 9 ] e [ 6 ] , è inoltre necessario modificare il prossimo puntatore del node[ 0 ] e il prossimo puntatore del node[ 2 ] nel diagramma sopra.

Come sarebbe la lista dopo aver scambiato questi due nodes?

 +---+ +---+ +---+ +---+ +---+ | 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |--- +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ null | | | | (p) (q) (head) 

Cosa è ora nei nodes precedenti [o] e [2] ?
Dopo lo scambio, nell'elenco elenca i puntatori precedenti

 node[0] points to node[6] that is (q), and node[2] points to node[9] that is (p) 

E

 node[9] points to node[5] node[6] points to node[2] 

Quindi se vuoi scambiare due nodes; ci sono anche effetti immediati sul nodo precedente e poiché la lista è un elenco di collegamenti singoli è necessario anche il puntatore precedente.

Come trovare precedenti puntatori di nodes?

Supponiamo di voler scambiare qualsiasi node[p] due nodes node[p] e node[q] quindi puoi usare il head pointer a head pointer per trovare il nodo precedente.

Quindi la syntax della funzione di scambio ( nella mia implementazione ) è simile a:

 void swap(struct stack **head, // head node struct stack **a, // first candidate node to swap struct stack **b); // first candidate node to swap 

E chiamerai funzione come:

 swap(&head, &p, &q); 

Definizione: ( per comprendere il codice, leggi i commenti che ho aggiunto in quasi tutte le righe )

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

Nella funzione swap() puoi notare che chiamo una funzione helper get_prevnd(, ); . Questa funzione restituisce l'indirizzo del nodo precedente nell'elenco. In La funzione get_prevnd(, ); , il primo argomento è list head e il secondo argomento è il nodo per il quale si sta cercando.

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

E fortunatamente il codice sta FUNZIONANDO :). Di seguito è riportato il link per il test online di questo codice. Ho testato vari tipi di input.

CodePad: per scambiare il nodo nel singolo elenco collegato. Si prega di controllare l'output.

E mi dispiace per il cattivo inglese

Speravo nel codice del copia-incolla, ma non l’ho trovato. Se qualcuno è ancora interessato, questa è la risposta. Ho fatto l’analisi della forza bruta di tutti e 3 i casi.

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

Nota: questo codice funziona se sp == tp, ma si presuppone che non si abbia il caso patologico dove ENTRAMBE & s-> next == tp && & t-> next == sp (che inizia con il ciclo).

  "KING KHAN" 

SwapanyTwoNodeData(int, int); questa funzione prende due interi come parametro e li scambia

dati del nodo.

 1->2->6->3->4->5 

SwapanyTwoNodeData (2,4);

 1->3->6->2->4->5 

Funzione di lavoro al 100%. . . . Godere.

 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"<