Как написать функцию внутри функции (list_map)

Question

Здравствуйте, я недавно задал несколько вопросов о связанных списках в C.
Ссылка была найдена здесь

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

void list_map( INTLIST *list, void (*f)(void *) );
/*Applies a function to each element of the list */

Итак, я написал ему об этом по электронной почте и сказал:

Другой вопрос: в заголовочном файле вы не определили функцию сортировки, нужно ли нам написать функцию сортировки с прототипом и, наконец, что такое list_map

И он ответил:

Вас просят реализовать функцию сортировки f, которая вызывается через list_map (list, f). Надеюсь, это очистит ваши сомнения.

Мои единственные сомнения в том, что этому не научили полностью. Я могу понять, как отсортировать связанный список на самом деле вот какой-то псевдокод:

tmp=head;

while(tmp!=NULL)
{
   tmp2=tmp->next; //pointer to next node
   while(tmp2!=NULL)
    {
     if (tmp2->data < tmp->data)
        {
         int x = tmp2->data;
         tmp2->data = tmp->data;
         tmp2->data = x;
        }
     tmp2=tmp2->next;
    }
   tmp=tmp->next;
}

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

У меня вопрос, у меня есть функция сортировки (в случае профессора он называет ее f). Как бы я назвал эту функцию сортировки, если подпись:

void list_map(INTLIST* list, void (*f) (void*));

Могу ли я просто сказать:

list_map(myList, f()); //apply function f to the current linked list

Или мне действительно нужно где-то определить list_map? Я не типичный студент, просто ищу кого-то, кто будет выполнять мою работу. Я действительно пытаюсь понять это как можно лучше.

Спасибо всем вам.

[РЕДАКТИРОВАТЬ ЧАСТЬ]

Я хотел бы добавить, что на одном из плакатов Калеб П. сказал

"Таким образом, ваша задача - создать сортировку функция, которую вы передадите list_map. Обратите внимание, что правильный синтаксис для передачи его будет: "

Итак, мой код должен быть таким:

в файле .h я создаю прототип функции как:

void myCustomSort(void*);

А потом в .cpp становится:

void myCustomSort(void*f)
{
tmp=f->head; 

while(tmp!=NULL) 
{
   tmp2=tmp->next; //pointer to next node 
   while(tmp2!=NULL) 
   { 
     if (tmp2->data < tmp->data) 
        { 
         int x = tmp2->data; 
         tmp2->data = tmp->data; 
         tmp2->data = x; 
        } 
     tmp2=tmp2->next; 
    } 
   tmp=tmp->next; 
} 
}

И чтобы назвать это в основном, я бы просто сделал:

list_map(myListPointer, &myCustomSort); 

Но разве мне не нужно нигде определять list_map? Поскольку он находится в файле .h, мне не нужно его определять?

Answer 1

Предполагается, что list_map реализован так, давая f каждый узел в последовательном порядке,

void list_map(INTLIST *list, void (*f)(void *)) {
    INTLIST *node;
    for (node = list; node; node = node->next)
        f(node);
}

Вы можете реализовать сортировку выбора

void list_sort(INTLIST *list) {
    list_map(list, swap_head_with_smallest);
}

, где void swap_head_with_smallest(void *) меняет базовую точку данного узла с наименьшим из данных любых узлов, следующих за ним в списке.

---

Поскольку это домашнее задание, я стараюсь не выдавать полного решения.

void swap_head_with_smallest(void *list) {
    INTLIST *head = list;
    INTLIST *smallest;

    /* set smallest the smallest node of
         head, head->tail, head->tail->tail, etc. */

    /* swap head->datum and smallest->datum */
}

Answer 2

Ваш профессор пытается научить вас концепции, которая распространена в функциональном программировании, которая является идеей функции высшего порядка . Функция высшего порядка может принимать другие функции в качестве параметров, вроде

list_of_cosines = map(cos, list_of_inputs)

, где list of inputs - серия значений с плавающей запятой, а cos - нормальная функция косинуса. Функция map будет вызывать cos для каждого значения в list_of_inputs и возвращать список соответствующих результатов.

Функции C не могут принимать другие типы функций в качестве параметров, но они могут принимать указатели на функции в качестве параметров (обычно называемые callback ); каноническим примером является библиотечная функция qsort(), которая принимает в качестве одного из своих параметров указатель на функцию, которая принимает два указателя на void и возвращает -1, 0 или 1 в зависимости от того, v1 v2 соответственно. Например:

int compareIntValues(const void *v1, const void *v2)
{
  int lv1 = *(int *) v1; // convert inputs from pointers to void
  int lv2 = *(int *) v2; // to the type we're actually interested in
  if (lv1 < lv2) return -1;
  if (lv1 > lv2) return 1;
  return 0;
}

int main(void)
{
  int values[] = {3, 1, 4, 5, 7, 9, 6, 2};
  ...
  qsort(values,                             // buffer containing items to sort
        sizeof values / sizeof values[0],   // number of items to sort
        sizeof values[0],                   // size of each item
        compareIntValues);                  // comparison function
  ... 
}

qsort() вызовет compareIntValues, чтобы упорядочить элементы в values. Подобно выражениям массива, тип функции-указателя будет неявно преобразован из «функции, возвращающей T» в «указатель на функцию, возвращающую T» в зависимости от контекста.

На данный момент я предполагаю, но мне кажется, что ваш профессор хочет, чтобы вы написали функцию list_map, чтобы она вызывала функцию сортировки f со списком в качестве параметр, что-то вроде следующего:

void list_map(INTLIST *list, void (*f)(void *))
{
  // sort the list by passing it to f
  f(list); // or (*f)(list);
}

void sortListAscending(void *ptr)
{
  INTLIST *ilptr = ptr;
  /**
   * sort the list in ascending order
   */
}

void sortListDescending(void *ptr)
{
  INTLIST *ilptr = ptr;
  /**
   * sort the list in descending order
   */
}

int main(void)
{
  INTLIST *theList;
  ...
  list_map(theList, sortListAscending); // sort the list in ascending order
  ...
  list_map(theList, sortListDescending); // sort the list in descending order
  ...
}

Интерфейс, предоставленный вашим профессором, немного запутан; либо указатель списка и параметр для f () должны быть void * (в этом случае вы можете использовать list_map для сопоставления функций с различными типами списка), либо указатель списка и параметр для f должны быть INTLIST * ( так как вы, кажется, имеете дело с типами INTLIST).

Если я прав, то упражнение на поверхности немного бессмысленно (почему бы не вызвать функцию сортировки напрямую?), Но, возможно, ваш профессор выстраивает что-то более общее. В конце концов, нет причины, по которой f должна быть функцией сортировки; это может быть функция для отображения списка, или сохранения списка в файл, или что-то еще.

У меня есть другой пример того, как использовать обратные вызовы для сортировки списка здесь ; это может помочь проиллюстрировать, почему этот метод полезен.

EDIT

Пример того, что нужно сделать для list_map, вероятно, гораздо ближе к тому, что задумал ваш профессор, чем к тому, что я написал.

Answer 3

Второй параметр list_map - это указатель на функцию, возвращающую void и принимающую указатель void . Поскольку list_map представляется функцией map , я предполагаю, что она вызовет f (указатель на функцию) для каждого элемента списка.

Таким образом, ваша задача - создать функцию сортировки, которую вы передадите в list_map. Обратите внимание, что правильный синтаксис для его передачи будет:

void yourCustomSort(void*);
list_map(myList, yourCustomSort);

Я бы предположил , что void*, передаваемый в вашу функцию сортировки, вероятно будет принадлежать узлу в связанном списке.

MergeSort - хороший выбор для сортировки связанных списков.

Answer 4

Если в вашем узле есть указатель на начало списка, вы должны использовать указатель на список как frontier . Позвольте мне объяснить.

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

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

Теперь у вас есть задание.

• Вы не можете получить какие-либо данные из примененной функции (она возвращает void)
• Вы должны пройти до конца списка, передавая каждый узел функции, выполняющей сортировку.
• Бесполезно сортировать список, который вы еще не посещали, так как вы продолжаете сортировать его для каждого узла (сортировка уже отсортированного набора не слишком умен для меня);)
• Ваша прикладная функция получает один указатель. Это ясно указывает на то, что этот указатель (узел, на котором вы находитесь) представляет собой линию: слева (от головы) находится часть списка, уже отсортированная, справа (от хвоста) находятся дикие элементы.
• Поскольку ваша прикладная функция получает в качестве входных данных просто пустое пространство *, я думаю, что лучше оставить указатели в покое и обменяться полезной нагрузкой узлов

Сказал, что псевдокод для вашей функции сортировки, одной из возможных, может быть:

void ascendingSort(void*f)
{
  cursor=f->head; 
  placed=false;

  while(!placed and cursor!=f) { 
    if (cursor->data < f->data) {
      cursor = cursor->next;
    } else {
      swap( cursor->data, f->data);
      placed=true;
    }
  }

  while(cursor!=f) { 
      cursor = cursor->next;
      swap(cursor->data, f->data);
  }

}

Или, в более краткой форме:

void ascendingSort(void*f)
{
  cursor=f->head; 

  while(cursor!=f) { 
    if (cursor->data > f->data) {
      swap( cursor->data, f->data);
    }
    cursor = cursor->next;
  }
}

Answer 5

Я считаю, что функция list_map вызывает указатель функции f (), который является указателем на функцию, которая принимает указатель void и возвращает void. Если это так, то это безумный способ реализовать сортировку, но выполнимо.

Определить функцию как

void Test(void *)
{...}

И передать его в list_map () примерно так:

list_map(listptr,Test);

Я предполагаю, что ваша функция Test вызывается для каждого элемента в списке.