Вставка и выбор связанного списка - PullRequest
Новая
       1

Вставка и выбор связанного списка

0 голосов
/ 24 февраля 2012

Я определяю связанный список таким же образом, как он обычно используется, то есть с частью data и

указатель на себя. Моя логика вставки следующая: 

struct node
{
    int data; //or any type.
    struct node *nextPtr;
}*start = NULL;
//main
struct *newPtr = (struct node *)malloc(sizeof(struct node *));
scanf("%d", newPtr->data); //or cout
newPtr->nextPtr = NULL;
if(start == NULL)
    start = newPtr;
else
{
    while(tempPtr->nextPtr != NULL)
    {
        tempPtr = tempPtr->nextPtr;
    }
    tempPtr->nextPtr = newPtr;
}

i) Правильна ли эта логика?

ii) a) Возможно, я получаю ошибку run-time , когда я вставляю два узла (в одной системе) или три узла (в другой). б) Узлы вставляются в правильном порядке, каждый раз, когда я вставляю узел.

Является ли ошибка времени выполнения в результате этого кода ... ???

Ответы [ 3 ]

2 голосов
/ 24 февраля 2012

не обращайте внимания на ответ, так как это c ++, исходный вопрос был помечен c ++

Исходный код, как только небольшие проблемы решены (фактическое распределение узла, установка значения, определение временного указателя, чтобы помочь пройти список), должно работать. Но есть и другие подходы, которые вы можете использовать для упрощения кода (ну, не то, чтобы он был чрезвычайно сложным), который в основном подразумевает нахождение точки вставки перед созданием, а затем создание нового элемента: 

Node** insertPoint = &start;
while (*insertionPoint) 
   insertionPoint = &((*insertionPoint)->next);
*insertionPoint = new Node(value);

Используйте указатель на указатель, чтобы пройти по списку, инициализированный с адресом указателя головы, перемещайте его, пока он не обратится к Node*, где будет добавлен новый элемент (примечание, добавлено, не вставлено). Затем создайте новый узел в этой позиции. Это предполагает, что конструктор Node позаботится о копировании значения и инициализации указателя next.

В качестве альтернативы вы можете написать это рекурсивно и позволить компилятору выполнить оптимизацию хвоста для вас (это может быть немного проще для чтения, некоторые люди находят рекурсию проще, некоторые нет): 

void append( Node*& tail, Value value ) {
   if ( tail==NULL )
      list = new Node(value);
   else
      append( list->next, value );
}

Телефонный код: 

append( start, 100 ); // assuming nits contained in the list

В этом случае вместо двойного указателя мы можем использовать ссылку на указатель, поскольку нам не нужно изменять его

2 голосов
/ 24 февраля 2012 
struct node
{
    int data; //or any type.
    struct node *nextPtr;
}*start = NULL;
//main
struct *newPtr = (struct node *)malloc(sizeof(struct node));// You dont need * here

scanf("%d", newPtr->data); //or cout
newPtr->nextPtr = NULL;

if(start == NULL)
    start = newPtr;
else
{ 
    tempPtr = start; // you missed this.
    while(tempPtr->nextPtr != NULL)
    {
        tempPtr = tempPtr->nextPtr;
    }
    tempPtr->nextPtr = newPtr;
}
2 голосов
/ 24 февраля 2012 
struct node *newPtr, **hnd;

newPtr = malloc(sizeof *newPtr);
if (!newPtr) barf();

scanf("%d", &newPtr->data);
newPtr->nextPtr = NULL;

for(hnd = &start; *hnd; hnd = &(*hnd)->next) {;}

*hnd = newPtr;
...