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 that you have read and understand our privacy policy and code of conduct.

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