2011-10-10 184 views
2

我想实现一个数据结构类的链表,我在搜索部分的算法有一些困难。C++链接列表实现崩溃

下面是有问题的代码,我试图实现以下伪代码在MIT算法导论文字:

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

在程序中的该点的头部是4节点,包含int 5的值。问题出现在for循环的主体中,其中指向节点对象的指针被分配给下一个节点。但是这超出了节点的头部,所以它基本上指向了内存中的某个随机位置(这是有道理的)。

在这种情况下算法不应该移动到前一个节点而不是下一个节点?下面是伪代码:

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

另外,这里是我的链接列表实现的头文件。我还没有尝试实现它的模板形式还只是为了让事情变得简单:

#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 

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

是List双链表?在内存中看起来如何? – Dave

+0

我认为这个问题可能在addNode成员函数中。请提供该代码,以便我们确保列表构建正确。 –

+0

上面提供的代码。 – dtg

回答

1

试试这个构建列表:

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

将节点添加到头部。也许你可能希望将指针存储到尾部,并在那里插入节点。

0

不幸的是你的代码并不像您所提供的伪代码。

伪代码用于搜索链接列表中的键而不是位置。

的伪代码读作:

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 

返回的值是一个指向包含k或空节点

如果你试图找到节点在给定位置你的循环将是(注意,这是假设你要使用一个从零开始的索引来访问列表):

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 

将R esult要么是指向给定位置或空节点(如果你打的列表的末尾第一)

编辑:你的代码是非常接近后者,如果这就是你想要什么做...你能看出差异吗?

编辑,因为我喜欢的功课,其中OP问正确的问题:)

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

嗯。我将密钥理解为循环索引和客户端代码提供的位置k。在我的脑海中,似乎... – dtg

+0

啊,我明白了。节点的关键字段应该是给定节点中的元素是什么? (例如,数字列表中的“int number”) – dtg

+0

Right :)如果您的方法应该搜索节点内*的内容,则需要比较传递给每个节点内容的值('Node- > number') –

0

您的列表与ADT的正常列表非常不同。不是返回节点,而是要求客户端知道列表实现的情况,而是返回并接受你正在列表的类型。

在这种情况下,你正在做一个整数列表,SOU你想要

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

两者的实现很简单。添加一个新节点,并将其链接到;

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

然后得到的是一件容易的事:

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 
}