C++ Implémentation de l'implémentation de la liste chaînée

Question

J'essaie d'implémenter une liste chaînée pour une classe de structures de données et j'ai des difficultés avec la partie recherche de l'algorithme.

est en dessous du code incriminé, que j'ai essayé de mettre en œuvre après la pseudo-code dans l'introduction du MIT à des algorithmes texte:

// 
// Method searches and retrieves a specified node from the list 
// 
Node* List::getNode(unsigned position) 
{ 
    Node* current = m_listHead; 

    for(unsigned i = m_listSize-1; (current != 0) && (i != position); --i) 
      current = current->next; 

    return current; 
} 

La tête à ce stade du programme est le 4ème noeud, qui contient la valeur de int 5. le problème semble être dans le corps de la boucle for, où le pointeur vers l'objet nœud est assigné au nœud suivant. Mais cela va au-delà de la tête du nœud, donc il pointe essentiellement vers un emplacement aléatoire dans la mémoire (cela a du sens).

L'algorithme ne devrait-il pas être déplacé vers le nœud précédent au lieu du nœud suivant dans ce cas? Voici le pseudo-code:

LIST-SEARCH(L, k) 
    x <- head 
    while x != NIL and key != k 
     do x <- next[x] 
    return x 

En outre, voici le fichier d'en-tête pour ma mise en œuvre de la liste Linked. Je ne l'ai pas essayé de le mettre en œuvre sous forme de modèle encore juste pour garder les choses simples:

#ifndef linkList_H 
#define linkList_h 


// 
// Create an object to represent a Node in the linked list object 
// (For now, the objects to be put in the list will be integers) 
// 
struct Node 
{ 
    // nodes of list will be integers 
    int number; 
    // pointer to the next node in the linked list 
    Node* next; 
}; 


// 
// Create an object to keep track of all parts in the list 
// 
class List 
{ 
public: 

    // Contstructor intializes all member data 
    List() : m_listSize(0), m_listHead(0) {} 

    // methods to return size of list and list head 
    Node* getListHead() const { return m_listHead; } 
    unsigned getListSize() const { return m_listSize; } 

    // method for adding a new node to the linked list, 
    // retrieving and deleting a specified node in the list 
    void addNode(Node* newNode); 
    Node* getNode(unsigned position); 

private: 

    // member data consists of an unsigned integer representing 
    // the list size and a pointer to a Node object representing head 
    Node* m_listHead; 
    unsigned m_listSize; 
}; 

#endif 

Mise en œuvre de la méthode addNode:

// 
// Method adds a new node to the linked list 
// 
void List::addNode(Node* newNode) 
{ 
    Node* theNode = new Node; 

    theNode = newNode; 
    theNode->next; 
    m_listHead = theNode; 

    ++m_listSize; 
} 

Answer 1

Essayez ceci pour construire la liste:

void List::addNode(int number) 
{ 
    newNode = new Node; 
    newNode -> number = number; 
    newNode -> next = m_listHead ; 
    m_listHead = newNode; 
    ++m_listSize; 
} 

Il ajoutera des nœuds à la tête. Peut-être souhaitez-vous stocker le pointeur sur la queue et y insérer les nœuds.

Answer 2

Malheureusement votre code ne ressemble pas le code de pseudo que vous fournissez.

Le pseudo-code sert à rechercher une liste liée pour une clé, et non une position.

Le pseudo-code se lit comme:

Assign head to (node) x. 
while x isn't null and the key inside the current node (x) doesn't match k 
    assign x->next to x 
return x 

La valeur retournée est soit un pointeur vers le noeud qui contient k ou null

Si vous essayez de trouver le nœud à une position donnée votre boucle serait (notez ceci suppose que vous allez utiliser un indice de base zéro pour accéder à la liste):

Assign head to (node) x 
assign 0 to (int) pos 
while x isn't null and pos not equal to given position 
    assign x->next to x 
    increment pos 
return x 

le r esult sera soit un pointeur vers le noeud à la position donnée, soit null (si vous frappez la fin de la liste en premier)

Editer: Votre code est très proche de ce dernier si c'est ce que vous essayez de faire fais ... tu peux voir la différence?

Modifier parce que j'aime les devoirs où l'OP pose les bonnes questions :)

Node* List::getNodeContaining(int searchValue) 
{ 
    Node* current = m_listHead; 

    while (current != 0 && current->number != searchValue) 
    { 
     current = current->next; 
    } 
    return current; 
} 

Node* List::getNodeAtPos(int position) 
{ 
    Node* current = m_listHead; 
    int pos = 0; 

    while (current != 0 && pos != position) 
    { 
     current = current->next; 
     pos++; 
    } 

    return current; 
} 

Answer 3

Votre liste est très différente de ce à quoi ressemble une liste ADT normale. Plutôt que de renvoyer des nœuds, ce qui nécessiterait que le client soit au courant de l'implémentation de la liste, vous retournez et acceptez le type dont vous faites la liste.

Dans ce cas, vous faites une liste d'entiers, vous voudriez ssou

public: 
    void add(int num); //prepends an Item to the list 
    int get(int pos); 

Les implémentations des deux sont simples. Ajouter crée un nouveau noeud et le relie;

void List::add(int num) 
{ 
    Node *newNode = new Node; 
    newNode->number = num; 
    newNode->next = m_listHead; 
    m_listHead = newNode; 
    m_listSize++; 
} 

Alors obtenir est facile aussi:

int List::get(int pos) 
{ 
    if(pos>m_listSize) 
     ;//throw an error somehow 
    Node *tmp = m_listHead; 
    while(pos-->0) 
     tmp=tmp->next; 
    return m->number 
}