Я новичок в указателях и немного запутался.
Я написал функцию, которая объединяет и сортирует два отсортированных связанных списка. Однако, когда я печатаю список после вызова функции, он не имеет всех значений нового объединенного списка. При отладке кода и проверке переменных и областей памяти, похоже, что он пропускает места и просто переходит к последней ячейке памяти. После выполнения функции мне нужно сохранить значения в новом списке, оставив list1 и list2 пустыми. Это мой метод в заголовочном файле:
template <class Type>
void orderedLinkedList<Type>::mergeLists(orderedLinkedList<Type> &list1, orderedLinkedList<Type> &list2)
{
nodeType<Type> *lastSmall; //pointer to the last node of the merged list.
nodeType<Type> *first1 = list1.first;
nodeType<Type> *first2 = list2.first;
if (list1.first == NULL){ //first sublist is empty
this->first = list2.first;
list2.first = NULL;
}
else if (list2.first == NULL){ // second sublist is empty
this->first = list1.first;
list1.first = NULL;
}
else{
if (first1->info < first2->info){ //Compare first nodes
this->first = first1;
first1 = first1->link;
lastSmall = this->first;
}
else{
this->first = first2;
first2 = first2->link;
lastSmall = this->first;
}
while (first1 != NULL && first2 != NULL)
{
if(first1->info < first2->info){
lastSmall->link = first1;
lastSmall = lastSmall->link;
first1 = first1->link;
}
else{
lastSmall->link = first2;
lastSmall = lastSmall->link;
first2 = first2->link;
}
} //end while
if (first1 == NULL) //first sublist exhausted first
lastSmall->link = first2;
else //second sublist exhausted first
lastSmall->link = first1;
list1.first = NULL;
list1.last = NULL;
list2.first = NULL;
list2.last = NULL;
}
}
Тогда в моем main.cpp у меня есть:
int main()
{
orderedLinkedList<int> list1;
orderedLinkedList<int> list2;
orderedLinkedList<int> newList;
list1.insert(2);
list1.insert(6);
list1.insert(7);
list2.insert(3);
list2.insert(5);
list2.insert(8);
newList.mergeLists(list1, list2);
newList.print();
return 0;
}
Моя функция печати на всякий случай:
template <class Type>
void linkedListType<Type>::print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current so that it points to
//the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
}//end print
Может ли кто-нибудь сказать мне, что я здесь не так делаю? Выход должен быть 2 3 5 6 7 8, но вместо этого 2 3 7 8.
Спасибо
EDIT:
Вот моя функция вставки. Обратите внимание, что эта функция из книги, с которой я работаю. Он включен в тот же класс, к которому мне нужно добавить метод mergeLists. Написано специально для упорядоченных списков:
template<class Type>
void orderedLinkedList<Type>::insert(const Type& newItem)
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
nodeType<Type> *newNode;
bool found;
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
//case1 list is empty
if(this->first == NULL)
{
this->first = newNode;
this->last = newNode;
this->count++;
}
else //if the list is not empty
{
current = this->first;
found = false;
while(current != NULL && !found)
{
if(current->info >= newItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
//case2 insert newNode at the head
if(current == this->first)
{
newNode->link = this->first;
this->first = newNode;
this->count++;
}
else //case 3
{
trailCurrent->link = newNode;
newNode->link = current;
if(current == NULL)
this->last = newNode;
this->count++;
}
}
}
}
3 случая, согласно книге:
Дело 1:
Список изначально пуст. Узел, содержащий новый элемент, является единственным узлом
и, таким образом, первый узел в списке.
Дело 2:
Новый элемент меньше самого маленького элемента в списке. Новый предмет идет в
начало списка. В этом случае нам нужно настроить указатель заголовка списка -
то есть во-первых. Кроме того, счет увеличивается на 1.
Дело 3:
Элемент должен быть вставлен где-то в списке.
Дело 3а:
Новый элемент больше, чем все элементы в списке. В этом случае новый
элемент вставляется в конец списка. Таким образом, значение тока равно NULL
и новый элемент вставляется после trailCurrent. Кроме того, счет увеличивается
на 1.
Дело 3b:
Новый элемент должен быть вставлен где-то посередине списка. В этом
В этом случае новый элемент вставляется между trailCurrent и текущим.
Кроме того, счет увеличивается на 1.