1

Всем привет! Дорогие друзья, кто сможет объяснить как найти минимальный элемент и поставить его после максимального?

Вот само задание:

Дан список из последовательности натуральных чисел. Добавить в список после максимального элемента минимальный.

Сам код: (без ф-ций нахождения максималтного минимального элем-а и перемещения)

struct Single_List {//структура данных
    int Data; //информационное поле
    Single_List *Next; //адресное поле
};

void main() {
    setlocale(0, "rus");
    Single_List *Head;//указатель на голову(первый эл.) списка

    Single_List *Current;//указатель на текущий элемент списка (при необходимости)

    Make_Single_List(6, &Head);
    Print_Single_List(Head);
    bool boo=Find_Item_Single_List(Head, 3);
    cout << boo << endl;

    system("pause");
}//main


void Make_Single_List(int n, Single_List** Head) {
    if (n > 0) {
        (*Head) = new Single_List();
        //выделяем память под новый элемент
        cout << "Введите значение ";
        cin >> (*Head)->Data;
        //вводим значение информационного поля
        (*Head)->Next = NULL;//обнуление адресного поля
        Make_Single_List(n - 1, &((*Head)->Next));
    }
}//end Make_Single_List


void Print_Single_List(Single_List* Head) {
    if (Head != NULL) {
        cout << Head->Data << "\t";
        Print_Single_List(Head->Next);
        //переход к следующему элементу
    }
    else cout << "\n";
}

//поиск элемента в однонаправленном списке
bool Find_Item_Single_List(Single_List* Head, int DataItem) {
    Single_List *ptr; //вспомогательным указатель
    ptr = Head;
    while (ptr != NULL) {//пока не конец списка
        if (DataItem == ptr->Data) return true;
        else ptr = ptr->Next;
    }
    return false;
}

Буду рад любой вашей помощи!!

8
  • 1
    Я не C++ программист, но может реализовать stack и перебором тупо ложить максимальное число в него, далее максимальное от оставшихся и т.д. а дальше берешь из stack (операция pop если не ошибаюсь), и в результате получаешь минимальное число а после максимальное.
    – Naumov
    22 мар 2016 в 21:37
  • С другой стороны это циклическая очередь, ладно сорри што путаю тебя
    – Naumov
    22 мар 2016 в 21:40
  • Ничего, я сам разбираюсь. Сейчас перебираю максимум и минимум элементы из списка и сохраняю их адреса. Надеюсь, к утру справлюсь :) 22 мар 2016 в 21:49
  • 1
    За один проход находите min и max и по ходу дела запоминаете указатели на предшествующие им элементы списка. Если предыдущего нет (голова), то например, запомните 0. Если vmin == vmax, то ничего делать не надо (все числа в списке одинаковые). Далее исключаете минимальный (зная указатель на предыдущий это совсем просто), потом вставляете этот исключенный элемент после максимального. Естественно, случай, когда один из них является головой, придется рассматривать особо.
    – avp
    22 мар 2016 в 22:25
  • 1
    @VladislavSolopov, когда пишете комментарий и хотите, чтобы человек, к которому Вы в нем обращаетесь увидел нотификацию об этом комментарии, пишите @nickname (например, @avp) в тексте комментария.
    – avp
    23 мар 2016 в 12:07

1 ответ 1

1

Ловите, примерчик работы (Linux, gcc/g++) с односвязными списками, думаю, разберетесь.

#include <stdio.h>
#include <stdlib.h>

struct data {
  struct data *next;
  int v;
};

struct data *
newelem (int v)
{
  struct data *p = (typeof(p))calloc(sizeof(*p), 1);
  if (p)
    p->v = v;
  return p;
}

struct data *
get_list (FILE *in)
{
  int v;
  struct data *list = 0, *p;

  while (fputs("> ", stdout), fscanf(in, "%d", &v) == 1) 
    if ((p = newelem(v))) {
      p->next = list;
      list = p;
    } else {
      fprintf(stderr, "Out of memory");
      exit(1);
    }

  return list;
}

void
get_minmax_ptrs (struct data *list, struct data **ppmin, struct data **ppmax)
{
  *ppmin = *ppmax = 0;
  if (list) {
    int vmin = list->v, vmax = list->v;
    struct data *p;

    for (p = list->next; p; p = p->next, list = list->next)
      if (p->v < vmin) {
        vmin = p->v;
        *ppmin = list;
      } else if (p->v > vmax) {
        vmax = p->v;
        *ppmax = list;
      }
  }
}

void
move_min (struct data **list, struct data *ppmin, struct data *ppmax)
{
  if (*list && ppmin != ppmax) {
    struct data *pmin = ppmin ? ppmin->next : *list,
      *pmax = ppmax ? ppmax->next : *list;
    // remove min
    if (pmin == *list)
      *list = pmin->next; // if min is first, correct list
    else
      ppmin->next = pmin->next;
    // insert min
    pmin->next = pmax->next;
    pmax->next = pmin;
  }
}

struct data *
rever_list (struct data *list)
{
  struct data *rev = 0, *n;

  for (; list; list = n) {
    n = list->next;
    list->next = rev;
    rev = list;
  }

  return rev;
}

int
main (int ac, char *av[])
{
  puts("Enter numbers");
  struct data *list = rever_list(get_list(stdin)),
    *ppmax, *ppmin;

  get_minmax_ptrs(list, &ppmin, &ppmax);
  move_min(&list, ppmin, ppmax);

  for (puts("result:"); list || (putchar('\n'), 0); list = list->next)
    printf("%d ", list->v);

  return puts("End") == EOF;
}

Если что-то непонятно, спрашивайте.

Ваш ответ

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

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