我想实现一个数据结构类的链表,我在搜索部分的算法有一些困难。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;
}
是List双链表?在内存中看起来如何? – Dave
我认为这个问题可能在addNode成员函数中。请提供该代码,以便我们确保列表构建正确。 –
上面提供的代码。 – dtg