La suppression d'un nœud à partir d'une seule liste, lorsque seulement le pointeur vers le nœud donné

C'est une question que je me posais dans une interview.

"Une seule liste, il y a dans la mémoire. Vous devez supprimer un nœud. Vous avez besoin d'écrire une fonction pour supprimer ce nœud, qui ne prend que l'adresse du nœud d'être supprimé, comme l'entrée et rien d'autre(y compris la tête)"

J'ai donné la réponse similaire à celle de réponse ci-dessous post -- Copier le contenu du nœud suivant dans le nœud à supprimer et supprimer le suivant.

La suppression d'un milieu nœud à partir d'une seule liste liée lorsque le pointeur vers le nœud précédent n'est pas disponible

Mais l'interviewer a demandé de nouveau de moi, ce que si je passe l'adresse du dernier nœud. Je lui ai dit que, depuis que le prochain sera un NULL, copiez cette valeur NULL dans le champ de données ainsi que l'adresse vers le nœud suivant, qui est également NULLE. Puis il m'a dit il y aura un problème de pendre des pointeurs... que je n'ai pas comprendre un peu. Peut quelqu'un s'il vous plaît jeter la lumière sur ce problème ? Est-il un générique solution ?

Mise à jour (Deux jours plus tard) : Un petit peu plus. Vu qu'il n'y est pas de nœud spécial à la fin de la liste. Et le dernier nœud points à NULL et si ce nœud est donnée en entrée, comment faire de l'avant-dernier point de nœud à NULL. Ou est-ce impossible ?

Il suffit de mettre : Si un nœud est donnée en entrée à une fonction, comment faire le pointeur de la référence, du point de NULLE

Demandez-vous quel est le balançant pointeur de la question? ou comment le résoudre?
Les deux, en fait je veux savoir à propos balançant pointeur aussi..

OriginalL'auteur King | 2012-02-20

data-structures linked-list

9

Balançant Pointeur:

(http://en.wikipedia.org/wiki/Dangling_reference)

Balançant des pointeurs et sauvage des pointeurs dans la programmation informatique sont
les pointeurs qui ne pointent pas vers un objet valide du type approprié.
Ces sont des cas particuliers de la mémoire de violations de sécurité.

Balançant des pointeurs surviennent lorsqu'un objet est supprimé ou libéré,
sans modifier la valeur du pointeur de la souris, de sorte que le pointeur toujours
les points à l'emplacement de la mémoire de la désallocation de la mémoire. Comme le système
peut réallouer précédemment libéré de la mémoire d'un autre processus, si l'
programme d'origine puis déréférence le (maintenant) bancales pointeur,
le comportement imprévisible peut entraîner, comme la mémoire peut maintenant contenir
de données totalement différentes.

Dans votre réponse, pour supprimer le nœud que vous avez fait de supprimer les prochaine nœud, ce qui peut être référencé par un pointeur. C'est la façon bancale pointeur en cas de problème.

(1) Il n'existe pas en dehors des références à la liste, comme vous le préciser dans une note.
(2) Bancales pointeur problème peut se poser, que l'intervieweur dit.

À la fois (1) et (2) ne peut pas être correcte à la fois. Ce qui signifie qu'il y a un malentendu quelque part.

À propos de la Suppression du Dernier Nœud:

Mais l'interviewer a demandé de nouveau de moi, ce que si je passe l'adresse de l'
dernier nœud. Je lui ai dit, depuis que la prochaine sera une valeur NULL, copie NULL
dans le champ de données ainsi que l'adresse pour le prochain nœud qui est
aussi NULLE.

Je pense que vous confondez deux choses: (1) Un pointeur p qui pointe vers NULL, (2) UNE liste liée nœud qui a la valeur NULL dans son champ de données.

Supposons que la structure de données est a -> b -> c -> d. Écrit NULLE à d du champ de données ne sera pas magicly faire c d'avoir un pointeur NULL dans son next champ.

Vous pouvez supprimer le dernier nœud si la liste liée a toujours un spécial dernier nœud qui ne sera jamais supprimé. Par exemple, a -> b -> c -> d -> LAST DERNIER a une valeur particulière dans son champ de données qui indique qu'il est vraiment le dernier élément. Maintenant pour supprimer d, vous pouvez supprimer la DERNIÈRE et écrire la valeur spéciale en d du champ de données.

Peut-être que ce sont exactement ce que vous avez essayé de dire au cours de l'entrevue, auquel cas il doit y avoir un malentendu entre vous et le recruteur.

Merci pour le wiki et en-éclairage de moi sur le balançant pointeur de la question. À propos de la déclaration (1), c'est vrai qu'il n'existe pas en dehors de références. Et le seul nœud qui pointe vers le nœud nous sommes suppression est le nœud courant. Puisque nous sommes en copiant le contenu de la suivante (moyenne le nœud à supprimer) pour le nœud courant, maintenant on pointe vers le nœud à supprimer. Donc, pas de pendre pointeur question sera là quand on en a le supprimer. Ce point est clair. Concernant le dernier nœud, permettez-moi de modifier ma question, un peu dans un autre paragraphe à ce sujet
c'est ma réponse à la mise à jour de votre question: c'est impossible. Vous devriez peut-être poster une nouvelle question si vous voulez un deuxième avis.

OriginalL'auteur Ali Ferhat
12

Suit:
1. De copier des données d'un Nœud(i+1) au Nœud(i)
2. Copie de la PROCHAINE de la deuxième Noeud(i+1) dans une variable temporaire.
3. Maintenant Supprimer le deuxième Noeud(i+1) //il ne nécessite pas de pointeur vers le nœud précédent.
Fonction:
```
void delete_node(node* node)
{
    node->Data = node->Next->Data;
    node* temp = node->Next->Next;
    delete(node->Next);
    node->Next = temp;
}
```
OriginalL'auteur Saket Vatsa

puis il devrait y avoir un chèque d'un programme si le nœud donné est le dernier nœud ou pas.

void delete_node(node* node1)
{
    node* search=head;
    if(node1==head)
    {
        head=head->next;
        search->next=NULL;
        node1->next=NULL;
    }
    while(search->next != node1)
        search=search->next;
    if(node1->next==NULL)
    {
       search->next=NULL;
    }
    else
    {
       search->next=node1->next;
       node1->next=NULL;
    }
    delete node1;
}

OriginalL'auteur hallah shahid butt

2

Si il y a d'autres éléments qui pointent vers le nœud suivant qui sera copié vers le nœud actuel, puis supprimé, puis cette opération permettra d'introduire un bug. Donc, dans votre réponse, vous devriez avoir souligné que votre solution ne fonctionne que si il n'y a pas des références extérieures à la liste.

Votre solution fonctionne avec le dernier nœud que si la structure de données est augmentée avec un "noeud" de l'élément. (Si vous utilisez Smalltalk, vous pouvez écrire self become: nil Aucune autre langue a quelque chose de semblable)

Non, il n'existe pas de solution générique si il y a des références extérieures à la liste. Je pense que l'intervieweur voulais voir si vous êtes vraiment compétent dans le sujet ou l'ont été il suffit de répéter un mémorisé réponse.

C'est une simple liste, et aussi il n'y a pas en dehors de ses références. Ma question est au sujet de référence de pointeur NULL problème qui peut survenir lorsque vous essayez de copier le dernier nœud. Aussi, veuillez noter que dans une seule liste liée, le dernier nœud points à NULL

OriginalL'auteur Ali Ferhat
1

Probablement votre liste de liens traversant pourriez avoir besoin de supposer que tout nœud qui points à null est null nœud, indépendamment de la valeur...
```
a->b->c->d->NULL
```
donc d est null nœud et le nœud ne doit pas être considéré comme un nœud. de cette façon, vous pouvez économiser sur l'utilisation des valeurs spéciales, puisqu'elles ne sont pas correctes dans un sens générique. d'autres que vous n'aurez pas d'autre moyen pour le nœud précédent à point à null.

OriginalL'auteur nitsi

 public void removeNode(Node node){

        /* if no node return null */
        if(node==null) return;

        /* if only 1 node then delete node */
        if(node.getNext()==null) {
            node = null;
            return ;
        }

        /* copy next node data to this node */
        node.data = node.getNext().data();

        /* store the next next node */
        Node second = node.getNext().getNext();

        /* remove next node */
        removeNode(node.getNext());

        /* set the copied node as next */
        node.setNext(second);
     }

OriginalL'auteur sreeprasad

Vous devez vous connecter pour publier un commentaire.