Двусвязный Список

  • Автор темы DenisNN
  • Дата начала
D

DenisNN

#1
Здравствуйте! Подскажите пожалуйста,что означает строка tail->prev->next = pNode; в добавлении элемента в конец списка,зачем писать tail->prev->next = pNode, почему нельзя просто tail->prev = pNode ?

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
main

#include "dlist.h"


int main()
{

List L(8);
L.add_from_rfont(22);
L.add_from_rfont(34);
L.add_from_tail(8);
L.add_from_tail(78);
L.add_from_tail(92);
L.shov_from_foront();

getch();
return 0;
}




//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
dlist

#include "dlist.h"

List::List() // Пустой список.
{
head = tail = new Node;
tail->next = 0;
tail->prev = 0;
}
List::List(int dta)
{

head = tail = new Node;
tail->next = 0;
tail->prev = 0;
List::add_from_rfont(dta);
}
List::Node::Node(int dta):data(dta)
{
nodeCount++;
}

void List::add_from_rfont(int dta)
{
Node *pNode = new Node(dta);
pNode->next = head;
pNode->prev = 0;
head->prev = pNode;
head = pNode;
}

void List::add_from_tail(int dta)
{
Node *pNode = new Node(dta);
pNode->next = tail;
pNode->prev = tail->prev;
tail->prev->next = pNode; //////////////////////////////////// !!! Вот эта строка не понятна !!! \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
tail->prev = pNode;
}

void List::shov_from_foront()
{
Node *pn;
pn = head;
while(pn!=tail)
{
cout << pn->data << endl;
pn = pn->next;
}
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
h

#pragma once

#include <iostream>
#include <conio.h>

using namespace std;

static int nodeCount = 0; // Количество созданных объектов.

class List
{
class Node
{
//friend class List;
public:
int data;
Node *next;
Node *prev;
int n; // № элемента.
Node(int);
Node(){};
~Node();
};

Node *head;
Node *tail;

public:

void add_from_rfont(int);
void add_from_tail(int);
void shov_from_foront(); // Показать от начала.
void shov_from_tail(); // Показать от хвоста.
void show_from_nth(int); // Показать от заданного элемента.

List(int);
List();
~List(){}

};
 
R

rrrFer

#2
Здравствуйте! Подскажите пожалуйста,что означает строка tail->prev->next = pNode; в добавлении элемента в конец списка,зачем писать tail->prev->next = pNode, почему нельзя просто tail->prev = pNode ?
нарисуй список и посмотри в чем разница
 
D

DenisNN

#3
Я уже рисовал,и логичнее получается без второго указателя, но без него не корректно работает L.shov_from_foront(). Я пытаюсь понять - почему tail->prev->next = pNode; и
tail->prev = pNode; указывают в одно и тоже место,для чего это нужно!Возможно для устранения неоднозначности?
 

ixoyz

Member
12.05.2012
16
0
#4
У тебя есть 2 элемента идущих друг за другом.
Пусть *p1, *p2; где p2 = p1->prev;
таким образом
p1->prev == p2
p2->next == p1
функция добавляет 3-й элемент между этими двумя
пусть *np;
в результате выполнения функции должно получиться
p1 -> prev == np
np -> prev == p2
p2 -> next == np
np -> next == p1
или
p1 -> prev -> prev == p2
p2 -> next -> next == p1

данная строка отвечает за то, что
p2 -> next == np
без неё получается
p1 -> prev -> prev == p2
p2 -> next == p1
а это не верно, т.к. не будет выполняться условие
np -> prev -> next == np
 
D

DenisNN

#5
Блин!Завтра все переварю,поздно уже!Здесь насамом деле без рисунка не понятно,с ним правдо тоже!)))Спасибо!
 
R

rrrFer

#6
Я пытаюсь понять - почему tail->prev->next = pNode; и
tail->prev = pNode; указывают в одно и тоже место,для чего это нужно
на рисунке должно быть хорошо видно что ваше утверждение ложно (утверждение что что-то там "указывает в одно и тоже место"). Если не видно - у вас плохой рисунок.