我正在尝试创建一个函数,以将整数插入到双向链接列表中,同时保留列表的递增顺序。即如果我将10、5、4、3传递到列表,则顺序为:3、4、5、10。但是,当我尝试打印函数时,没有任何输出。我没有收到任何错误,我想我没有正确使用“->”,因为它们对我来说很新。
这是我到目前为止拥有的三个文件:
#include <iostream>
#include "SortedList.h"
using namespace std;
int main() {
SortedList dLL;
dLL.insertItem(10);
system("pause");
}
#ifndef SORTEDLIST_H
#define SORTEDLIST_H
#include <iostream>
class SortedList {
private:
typedef struct node {
int data;
node* next;
node* prev;
}* nodePtr;
int theSize;
nodePtr head;
nodePtr temp;
nodePtr tail;
public:
SortedList();
void insertItem(int inData);
void deleteItem(int delData);
/*friend ostream& operator <<(ostream& ot, const SortedList& sL);*/
int size() const;
bool empty() const;
};
#endif
#include <cstdlib>
#include <iostream>
#include "SortedList.h"
using namespace std;
SortedList::SortedList() {
//Set pointers equal to NULL
head = NULL;
temp = NULL;
tail = NULL;
theSize = 0;
head = new node; //create new node of 3 parts: head, data and prev
tail = new node; //create new node of 3 parts: head, data and prev
head->next = tail; //next partition points to tail
head->prev = NULL; //not necessary to put in?
tail->prev = head; //prev partition points to head
tail->next = NULL; //not necessary to put in?
/*temp->next = tail; //access the node the temp pointer is pointing to, set the 'next' part equal to tail*/
}
void SortedList::insertItem(int inData) {
bool insert = false;
temp->next = head; //Set temp pointer to first node in linked list (head)
while (temp->next != NULL) { //traverse entire list, stop when temp pointer reaches the end
if (inData > temp->data) { //If inData is greater than the data of the node temp is currently pointing to move forward
temp = temp->next; //set temp pointer to the next pointer of the node temp is currently pointing at (move temp pointer forward to next node)
}
if (inData <= temp->data) { //if inData is <= the data of the node temp is currently pointing to, insert inData before this node
nodePtr n = new node; //create new node with new pointer to it 'n'
n->next = temp->next; //set the 'next' partition to what our temp pointer's 'next' is pointing to
n->prev = temp->prev; //set the 'prev'partition to what our temp pointer's 'prev' is pointing to
n->data = inData; //fill node n data with the int data we wish to insert
temp->prev->next = n; //set the next pointer of the prev node to n
temp->next->prev = n; //set the prev pointer of the next node to n
insert = true; //set insert boolean variable to true since value was inserted
}
}
if (insert == false) { //if no data was found in list to compare insert node inbetween head and tail
nodePtr n = new node;
n->next = temp->next;
n->prev = temp->prev;
n->data = inData;
temp->prev->next = n;
temp->next->prev = n;
}
//Print List
temp = head; //set temporary pointer equal to head
while (temp->next != NULL) { //traverse linked list until next pointer points to nothing
cout << temp->data << " "; //print data from node temp pointer is currently pointing to
temp = temp->next; //move temp pointer forwardd
}
return;
}
void SortedList::deleteItem(int delData)
{
}
int SortedList::size() const
{
return 0;
}
bool SortedList::empty() const
{
return false;
}
我提供了很多注释,这些注释解释了我认为每一行背后的逻辑,因此希望它可以使我更容易理解我对任何事物的误解。
您的节点插入功能有几个缺陷。
temp = head
而不是temp->next = head
。if-else
进行插入位置检查。temp = head->next;
开头并使用while (temp != tail)
。在插入功能之后进行更改以使其正常工作。
void SortedList::insertItem(int inData) {
bool insert = false;
temp = head;
while ((temp->next != NULL) && !insert) {
if (inData > temp->data) {
// Not the right insertion place, move forward
temp = temp->next;
}
else {
// Insert node in between of two nodes
nodePtr n = new node;
n->next = temp;
n->prev = temp->prev;
n->data = inData;
temp->prev->next = n;
temp->prev = n;
insert = true;
}
}
// List tail reached but node has not been inserted.
// Add node at list tail
if (insert == false) {
nodePtr n = new node;
n->next = temp;
n->prev = temp->prev;
n->data = inData;
temp->prev->next = n;
tail->prev = n;
}
//Print List
temp = head->next;
while (temp != tail) {
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
return;
}
附加说明:
temp
节点添加为类SortedList
的成员。在使用它的范围内定义它。head
和tail
分配节点对象。只需将它们用作指向列表的第一个和最后一个节点的指针,或者如果列表为空,则将其设置为nullptr
。