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

Привет, я недавно задал несколько вопросов по связанным спискам в 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 data) { int x = tmp2->data; tmp2->data = tmp->data; tmp2->data = x; } tmp2=tmp2->next; } tmp=tmp->next; } в tmp=head; while(tmp!=NULL) { tmp2=tmp->next; //pointer to next node while(tmp2!=NULL) { if (tmp2->data data) { int x = tmp2->data; tmp2->data = tmp->data; tmp2->data = x; } tmp2=tmp2->next; } tmp=tmp->next; } в tmp=head; while(tmp!=NULL) { tmp2=tmp->next; //pointer to next node while(tmp2!=NULL) { if (tmp2->data 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 где-нибудь? Я не типичный ученик, просто ищущий, чтобы кто-то выполнял мою работу. Я действительно пытаюсь понять это, насколько смогу.

Всем спасибо.

[EDIT PORTION]

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

«Таким образом, ваша задача – создать функцию сортировки, которую вы передадите в 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 data) { int x = tmp2->data; tmp2->data = tmp->data; tmp2->data = x; } tmp2=tmp2->next; } tmp=tmp->next; } } в void myCustomSort(void*f) { tmp=f->head; while(tmp!=NULL) { tmp2=tmp->next; //pointer to next node while(tmp2!=NULL) { if (tmp2->data data) { int x = tmp2->data; tmp2->data = tmp->data; tmp2->data = x; } tmp2=tmp2->next; } tmp=tmp->next; } } в void myCustomSort(void*f) { tmp=f->head; while(tmp!=NULL) { tmp2=tmp->next; //pointer to next node while(tmp2!=NULL) { if (tmp2->data 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, я не должен его определять?

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

 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 */ } 

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

 list_of_cosines = map(cos, list_of_inputs) 

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

Функции C не могут принимать другие типы функций в качестве параметров, но они могут принимать указатели на функции как параметры (обычно называемые обратным вызовом ); канонический пример представляет собой библиотечную функцию 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 функцию 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).

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

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

РЕДАКТИРОВАТЬ

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

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

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

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

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

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

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

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

 void Test(void *) {...} 

И передайте его в list_map () так

 list_map(listptr,Test); 

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

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

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

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

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

  • Вы не можете получить какие-либо данные из прикладной функции (она возвращает void)
  • Вам нужно спуститься до конца списка, передавая каждый отдельный узел функции, которая выполняет сортировку.
  • Сортировать список, который вы еще не посещали, бесполезно, так как вы будете сортировать его для каждого узла (сортировка уже отсортированного набора, это не слишком умно для меня);)
  • Ваша прикладная функция получает один указатель. Это ясно указывает на то, что этот указатель (узел, на котором вы находитесь) представляет собой линию: слева от него (до головы) есть часть уже отсортированного списка, справа (к хвосту) есть дикие элементы.
  • Поскольку ваша прикладная функция получает в качестве входных данных просто простую 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; } }