检查单链表是否为空 c++
我试图找出确定单链表是否为空的最佳和最简单的方法。
我需要创建一个布尔方法吗？
感谢
Read 方法
void List::Read(istream& r) {
char c[13];
r >> c;
r >> numberOfInts;
Node *node = new Node();
for(int i = 0; i < numberOfInts; i++)
{
r >> node->data;
cout << node->data << endl;
node->next = new Node;
//node = node->next;
head = node;
}
}
else
{
if(node->data > head->data)
{
head->next;
}
else if(node->data < head->data)
{
Node* tempNode;
tempNode = head;
head->data = node->data;
node->data = tempNode->data;
}
}
system("pause");
}
头文件
class Node
{
public:
Node() {}
Node(int d, Node* q = 0) : data(d), next(q) {} //constructor with parameters data and next
int data; //holds data in node
Node* next;//pointer to next node
};
class List
{
public:
void Read(istream&);
void Write(ostream&);
void setReadSort(bool);
void sortOwn();
void insertionSort(Node*);
bool isEmpty();
bool _sortRead;
int numberOfInts;
List(void);
~List(void);
protected:
Node *head;
Node current;
};
I am trying to figure out what the best and simplest way is of determining if a singly linked list is empty or not.
Would I need to create a boolean method?
Thanks
Read Method
void List::Read(istream& r)
{
char c[13];
r >> c;
r >> numberOfInts;
Node *node = new Node();
for(int i = 0; i < numberOfInts; i++)
{
r >> node->data;
cout << node->data << endl;
node->next = new Node;
//node = node->next;
head = node;
}
}
else
{
if(node->data > head->data)
{
head->next;
}
else if(node->data < head->data)
{
Node* tempNode;
tempNode = head;
head->data = node->data;
node->data = tempNode->data;
}
}
system("pause");
}
Header file
class Node
{
public:
Node() {}
Node(int d, Node* q = 0) : data(d), next(q) {} //constructor with parameters data and next
int data; //holds data in node
Node* next;//pointer to next node
};
class List
{
public:
void Read(istream&);
void Write(ostream&);
void setReadSort(bool);
void sortOwn();
void insertionSort(Node*);
bool isEmpty();
bool _sortRead;
int numberOfInts;
List(void);
~List(void);
protected:
Node *head;
Node current;
};
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这完全取决于实施。然而，这通常可以通过检查第一个节点是否存在/具有内容/等等来非常快速地完成。
This completely depends on the implementation. However, this typically can be done very quickly by checking to see if the first node exists/has contents/etc.
是的。原因是：有时我们使用迭代器插入元素，通过迭代器处理元素的数量会非常不舒服（或不可能）。这就是为什么许多 STL 实现的
size_t size(void)函数具有线性时间的原因。boolempty(void)是检查列表是否为空且具有恒定时间的有效方法。只是要注意：当您使用 STL 时，更喜欢使用
boolempty(void)来代替size_t size(void)。更多信息请参见：Meyers：有效的 STL。该功能很简单：
就您而言：
Yes. The reason is: sometimes we use the iterator to insert element, it would be very uncomfortable (or impossible) to handle the number of the elements over the iterators. This is the reason why many STL implementation has linear time for
size_t size(void)function.bool empty(void)is an effective way to check if the list is empty and it has constant time.Just to note: when you use STL prefer to use
bool empty(void)againstsize_t size(void). More info in: Meyers: Effective STL.The function is simple:
In your case:
我没有测试这个，但它应该有效。
[编辑] 更改了程序以考虑始终存在的头部。
[编辑] 更改程序以考虑类，而不是结构
这将给出更正确的结果
还有一件事，我看到您正在使用 system("pause");。我知道这是家庭作业，但这是非常糟糕的做法。更好的方法是首先清除标准输入中的缓冲区（如果需要），然后忽略字符。一个例子是：
I didn't test this, but it should work.
[edit] Changed program to account for a head that always exists.
[edit] Changed program to account for class, instead of a struct
This will give a more proper result
One more thing, I see that you are using system("pause");. I know that this is homework, but that is extremely bad practice. A better method would be to first clear the buffer in stdin (if needed), then ignore a character. An example would be: