1

Добрый день!
Помогите, пожалуйста, разобраться. Не работает в простенькой программе вставка в конец(!) линейного списка. Никак не могу понять, в чем проблема.

#include <iostream>
#include <cstring>
using namespace std;

struct link         // один элемент списка
{
    int data;   
    link* next;     
};

class linklist  
{
private:
    link* first;
public:
    linklist()        
    { 
        first = NULL;
    }    
    void additem(int d); 
    void display();   
};

void linklist::additem(int d)    // добавление элемента (ЗДЕСЬ ПРОБЛЕМА)
{
    link* newlink = new link;      
    newlink -> data = d; 
    newlink -> next = NULL; 
    link* temp = new link;
    temp = first;
    while ( (temp -> next) != NULL)
    {
        temp = temp -> next;
    }
    temp -> next = newlink;
}

void linklist::display()
{
    link* current = first;              
    while(current)                      
    {
        cout << current->data << endl;
        current = current->next;        
    }
}

void main()
{
    linklist l;

    l.additem(1);   
    l.additem(2);
    l.additem(3);
    l.additem(4);

    l.display();     
}

3 ответа 3

4

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

while ( (temp -> next) != NULL)

Можно добавить условие

if ( first != NULL ) {
    temp = first;
    while ( (temp -> next) != NULL)
    {
        temp = temp -> next;
    }
    temp -> next = newlink;
}
else
        first = newlink;
0
4

@777Julia777, если Вы хотите вставлять элементы в конец односвязного списка, то имеет смысл завести в заголовке списка 2 указателя. Один на первый, а второй на последний элемент списка.

Если же список планируется только в качестве временного контейнера и порядок в нем не важен, то можно обойтись одним указателем на первый элемент и работать со списком только через этот указатель (как со стеком). Т.е. добавлять новые элементы всегда в начало (список при этом не надо просматривать) и удалять так же.

Не удержался, надергал и слегка причесал немного кода для работы с односвязными списками. Сразу хочу заметить, что это надо рассматривать в качестве некого шаблона, не стремясь к универсальности. Обычно подобный код даже не оформляется в виде функций (и уж никак не претендует на включение в библиотеки), иногда даже указатели tail и head не оформляются в отдельную структуру, а просто путешествует по исходникам, модифицируясь в зависимости от структур данных, связываемых в подобные списки.

Обратите внимание, что функции и макросы возвращают в качестве значения указатель на элемент, только что вставленный в список или удаленный из него. Это часто бывает удобно при написании кода.

// list2.c avp 2013 кусочки кода односвязных списков
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct elem {
  struct elem *next;
  char  *data;
};

struct list {
  struct elem *head,
    *tail;
};

struct elem *
add_tail (struct list *list, struct elem *item)
{
  item->next = 0;
  if (!(list->head))
    list->head = item;
  else
    list->tail->next = item;
  return list->tail = item;
}

struct elem *
add_head (struct list *list, struct elem *item)
{
  if (!(list->head)) {
    item->next = 0;
    return list->head = list->tail = item;
  }
  item->next = list->head;
  return list->head = item;
}

struct elem *
del_head (struct list *list)
{
  struct elem *t = list->head;
  if (t) 
    if (!(list->head = t->next))
      list->tail = 0;
  return t;
}

struct elem *
del_tail (struct list *list)
{
  struct elem *t = list->head, *p = 0;
  if (t) {
    while (t != list->tail) {
      p = t;
      t = t->next;
    }
    if (list->tail = p)
      p->next = 0;
    else
      list->head = p;
  }
  return t;
}

void
prilist (const char *msg, struct elem *e)
{
  puts(msg);

  while (e) {
    puts(e->data);
    e = e->next;
  }
}

inline struct elem *
mkelem (const char *txt)
{
  struct elem *res = (typeof(res))malloc(sizeof(*res));
  res->data = strdup(txt);
  res->next = 0;
  return res;
}

// не вызывать с самомодифицирующимся аргументом l !!!    
#define push_list(l,e) ({typeof (l) _e = (e); (_e)->next = (l); (l) = (_e);})
#define pop_list(l) ({typeof (l) _res = (l); (l) = (l) ? (l)->next: 0; _res;})

int
main ()
{
  struct list li;
  li.head = li.tail = 0; // init

  // первый элемент в список
  struct elem *el = add_head(&li, mkelem("elem2"));
  // добавим еще в голову и в конец
  add_head(&li, mkelem("elem1"));
  add_tail(&li, mkelem("elem3"));
  prilist("part:", el); // печатаем от "середины" до конца списка
  prilist("full:", li.head); // печатаем весь список
  // теперь удалим голову и хвост
  del_head(&li);
  del_tail(&li);
  prilist("mid:", li.head); // печатаем весь список
  // опять добавим голову и в конец
  add_head(&li, mkelem("elem1"));
  add_tail(&li, mkelem("elem3"));
  prilist("new list:", li.head); // печатаем весь список
  // удалим все и проверим печатью
  while(del_head(&li));
  prilist("after while(del_head()):", li.head);
  // новый список из 2-х элементов 
  add_head(&li, mkelem("elem1"));
  add_tail(&li, mkelem("elem3"));
  do 
    prilist("new del tail list:", li.head);
  // печатаем удаляя с конца
  while(del_tail(&li));
  prilist("after while(del_tail()):", li.head);

  struct elem *sl = 0;
  push_list(sl, mkelem("item1"));
  push_list(sl, mkelem("item2"));
  push_list(sl, mkelem("item3"));
  prilist("prilist() stack list:", sl);
  puts("print while pop()");
  while (el = pop_list(sl))
    puts(el->data);
  prilist("realy empty", sl);
}

Код компилируется как gcc, так и g++, но тщательно не тестировался, его части "надерганы" из разных контекстов (надеюсь работоспособных :)), так что заранее приношу извинения за возможные ошибки.

0
2
link* temp = new link;
temp = first;

Утечка

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.