1
struct address {
   char name[40];
   char street[40];
   struct address *next; 
} info;

void Add(struct address *i, struct address **last)
{
     if(!*last) *last = i; 
     else (*last)->next = i;
     i->next = NULL;
     *last = i;
}

Изучаю односвязные списки. Испытываю затруднения с функцией для добавления элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address, содержащую новую запись, и указатель на последний элемент списка. Я не хорош в указателях и не понимаю зачем нужен указатель на указатель в параметрах функции?

Я для себя не смог расшифровать только, что значит это действие: если последний элемент не равен нулю, тогда присвоить последнему передаваемое значение, иначе (*last)->next = i;. Потом следующему элементу даем нулевое значение, чтобы инициализировать его как, я понял, и зачем-то последняя строка. Помогите пожалуйста разобраться

3 ответа 3

2

зачем нужен указатель на указатель в параметрах функции?

Да очень просто! Потому что структура будет изменяться!

void Add(struct address *i, struct address **last)
{
  if (!*last) *last = i;  // если last=null -> i - первый элемент
  else (*last)->next = i; // иначе элементы в списке и есть и пришиваем текущий элемент i в конец списка.
  i->next = NULL;         // следующий элемент = NULL
  *last = i;              // записать в указатель last указатель на структуру i
}

Смотрите насчет указателей.

int f (int  x) {x = 0;}
int fp(int *x) {x = 0;}
int fr(int &x) {x = 3;}

...
int y = 1;
f(y);   // какое значение у y после выполнения f()?  y = 1!
fp(&y); // какое значение у y после выполнения fp()? y = 0!
fr(y);  // y = 3!
1

Для вашей задачи вам нужно определить еще два указателя - указатель на первый и последний элемент

struct data{ // Данные
char name[40];
char street[40];
}
struct list{ // Односвязанный список
data lable;
data *next
}

struct list *head = NULL, *last = NULL; // Указатель на начало и конец

void add(list *last, data& data){
list *newPtr = new list; // новый узел в списке
list->data = data;
if (head == NULL){ // если список пуст указатель на головной элемент будет //указателем на новый узел
head = newPtr;
last = newPtr;
}
else{ // Добавляем новый элемент в конец списка
last->next = newPtr;
last = newPtr;
}
}

Граничные ситуации и возможные исключения не предусмотренны

1

При таком использовании Add() идея простая.

Первый аргумент это адрес структуры, которая добавляется в конец. Второй адрес текущего конца (на самом деле адрес адреса !). Он (адрес конца) будет меняться на адрес добавляемого элемента при каждом вызове Add(). Поэтому (чтобы изменить аргумент 2) и передается адрес адреса (указатель на указатель (масло масляное)).

При первом вызове Add списка еще нет, поэтому передадим адрес указателя с нулевым значением. Это важно (иначе упадет). Этот вызов заменит нулевой адрес конца на адрес добавляемого (первый аргумент) элемента списка. И т.д.

Иногда функцию Add() пишут немного по другому (по моему удобнее)

struct address *Add (struct address *new_elem, struct address *tail)

и она возвращает свой первый аргумент (адрес вставленного в конец элемента), а при следующем вызове Add() используют результат предыдущего вызова как аргумент 2. А если списка еще нет, то 2-й аргумент - NULL.

Попробуйте, на самом деле удобно, особенно при манипуляции с несколькими списками.

1
  • Разумно. В частности, понравилась идея сохранять адрес последнего элемента списка (некоторая оптимизация по скорости добавления элементов).
    – gecube
    19 сен 2011 в 21:19

Ваш ответ

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

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