Работы с двусвязным списом C++
Работаю с двусвязным списком. И у меня возникли проблемы с функциями добавления до определенного узла и после определенного узла. Никак не могу реализовать функции AddBefore и AddAfter.
Вот код:
#include <iostream>
using namespace std;
struct Node {
int data;
Node *pNext;
Node *pPrev;
};
int countNode = 0;
Node *head;
Node *tail;
void AddHead(int value)
{
Node* temp = new Node;
temp->pPrev = NULL;
temp->data = value;
if (head != NULL)
{
temp->pNext = head;
head->pPrev = temp;
head = temp;
countNode++;
}
else {
head = tail = temp;
head->pNext = NULL;
countNode++;
}
}
void AddTail(int value)
{
Node* temp = new Node;
temp->pNext = NULL;
temp->data = value;
if (head != NULL)
{
temp->pPrev = tail;
tail->pNext = temp;
tail = temp;
countNode++;
}
else
{
temp->pPrev = NULL;
head = tail = temp;
countNode++;
}
}
void AddBefore(int value, int position)
{
Node *newTemp = new Node;
Node* p = head;
newTemp->data = value;
if (position == 1) {
AddHead(value);
}
else {
for (int i = 0; i < position; i++)
{
//Проблема тут
if (i+1 == position - 1) {
p = p->pNext;
p->pNext = newTemp;
newTemp->pPrev = p->pPrev;
newTemp->pNext = p;
p->pPrev = newTemp;
countNode++;
}
else {
p = p->pNext;
}
}
}
}
void AddAfter(int value, int position)
{
Node* newTemp = new Node;
Node* p = head;
newTemp->data = value;
if (position == countNode) {
AddTail(value);
}
else {
for (int i = 0; i < position+1; i++)
{
//Проблема тут
p = p->pNext;
if (i+1 == position+1)
{
p = p->pNext;
p->pPrev->pNext = newTemp;
newTemp->pPrev = p->pPrev;
newTemp->pNext = p;
p->pPrev = newTemp;
countNode++;
}
}
}
}
void Search(int position) {
if (head == NULL) cout << "\nСписок пуст\n\n";
else {
Node* searchHead = head;
Node* searchTail = tail;
if (position <= (countNode / 2)) {
for (int i = 0; i < position; i++) {
if (i + 1 == position)
cout << searchHead->data << "\n";
searchHead = searchHead->pNext;
}
}
else {
for (int i = countNode; i >= position; i--) {
if (i == position)
cout << searchTail->data << "\n";
searchTail = searchTail ->pPrev;
}
}
}
}
int DeleteList(int position)
{
if (head == NULL)
{
cout << "\nСписок пуст\n\n"; return 0;
}
if (head->pNext == NULL)
{
delete head;
head = NULL;
countNode--;
}
else
{
Node* deleteHead = head;
Node* deleteTail = tail;
if (position <= (countNode / 2)) {
for (int i = 0; i < position; i++) {
if (i+1 == position)
{
if (i + 1 == 1) {
Node* temp = head;
head = temp->pNext;
temp->pNext->pPrev = NULL;
countNode--;
cout << "\nЭлемент удален..\n\n";
}
else {
deleteHead = deleteHead->pNext;
deleteHead->pPrev->pNext = deleteHead->pNext;
deleteHead->pNext->pPrev = deleteHead->pPrev;
delete deleteHead;
cout << "\nЭлемент удален..\n\n";
countNode--;
}
}
}
}
else {
for (int i = countNode; i >= position; i--) {
if (i == position)
{
if (i == countNode) {
Node* temp = tail;
tail = temp->pPrev;
temp->pPrev->pNext = NULL;
countNode--;
cout << "\nЭлемент удален..\n\n";
}
else {
deleteTail = deleteTail->pPrev;
deleteTail->pPrev->pNext = deleteTail->pNext;
deleteTail->pNext->pPrev = deleteTail->pPrev;
delete deleteTail;
cout << "\nЭлемент удален..\n\n";
countNode--;
}
}
}
}
}
}
void PrintList()
{
if (head == NULL) cout << "\nСписок пуст\n\n";
else
{
Node* a = head;
cout << "\nЭлементы списка: ";
do
{
cout << a->data << " ";
a = a->pNext;
} while (a != NULL); cout << "\n\n";
}
}
void main()
{
setlocale(LC_ALL, "RU");
int value, position, x;
do
{
cout << "1. Добавить элемент в начало списка" << endl;
cout << "2. Добавить элемент в конец списка" << endl;
cout << "3. Добавить элемент до заданного узла" << endl;
cout << "4. Добавить элемент после заданного узла" << endl;
cout << "5. Найти узел" << endl;
cout << "6. Удалить элемент" << endl;
cout << "7. Вывести список" << endl;
cout << "0. Выйти" << endl;
do {
cout << "\nНомер операции > "; cin >> x;
if (x > 7 || x < -1)
cout << "Ошибка! Введите корректный номер операции!";
} while (x > 7 || x < -1);
switch (x)
{
case 1:
cout << "Значение > "; cin >> value;
AddHead(value);
break;
case 2:
cout << "Значение > "; cin >> value;
AddTail(value);
break;
case 3:
cout << "\nКоличество элементов: " << countNode << "\n";
if (countNode != 0) {
do {
cout << "Введите позицию, до которой хотите расположить элемент > "; cin >> position;
if (position > countNode || position <= 0)
cout << "Ошибка! Введите корректную позицию!\n";
} while (position > countNode || position <= 0);
cout << "Значение > "; cin >> value;
AddBefore(value, position);
} else cout << "\nСписок пуст. Невозможно добавить элемент <до>\n\n";
break;
case 4:
cout << "\nКоличество элементов: " << countNode << "\n";
if (countNode != 0) {
do {
cout << "Введите позицию, после которой хотите расположить элемент > "; cin >> position;
if (position > countNode || position <= 0)
cout << "Ошибка! Введите корректную позицию!\n";
} while (position > countNode || position <= 0);
cout << "Значение > "; cin >> value;
AddAfter(value, position);
} else cout << "\nСписок пуст. Невозможно добавить элемент <после>\n\n";
break;
case 5:
cout << "\nКоличество элементов: " << countNode << "\n";
do {
cout << "Введите позицию > "; cin >> position;
if (position > countNode || position <= 0)
cout << "Ошибка! Введите корректную позицию для осуществления поиска!\n";
} while (position > countNode || position <= 0);
Search(position);
break;
case 6:
cout << "\nКоличество элементов: " << countNode << "\n";
do {
cout << "Введите позицию > "; cin >> position;
if (position > countNode || position <= 0)
cout << "Ошибка! Введите корректную позицию для осуществления поиска!\n";
} while (position > countNode || position <= 0);
DeleteList(position);
break;
case 7: PrintList();
break;
}
} while (x != 0);
}
Ответы (1 шт):
Автор решения: Sergey Tatarincev
→ Ссылка
на примере addbefore. Вы специально зацикливаете список?
p = p->pNext;
p->pNext = newTemp; // следующий за p будет новый
newTemp->pPrev = p->pPrev;
newTemp->pNext = p; // следующий за новым будет p
p->pPrev = newTemp;
countNode++;
А вообще по стилистике похоже на индусский г...код вы уж простите...
void AddBefore(int value, int position)
{
Node *newTemp = new Node;
Node* p = head;
newTemp->data = value;
if (position == 1) {
delete newTemp; // Зачем выделялась память если не использовать?? или освобождайте или выделяйте только когда надо.
AddHead(value);
}
else {
int i=0;
for (i = 0; i < position-1 && i<countNode; i++) // кто будет проверять границы??
p = p->pNext;
if(i+1!=position)
return;
p->pPrev->pNext=newTemp;
newTemp->pPrev = p->pPrev;
newTemp->pNext = p;
p->pPrev = newTemp;
countNode++;
}
}