Однонаправленные Списки (стэк)

Тема в разделе "C/C++/C#", создана пользователем kingl, 2 фев 2014.

  1. kingl

    kingl New Member

    Регистрация:
    30 окт 2013
    Сообщения:
    2
    Симпатии:
    0
    Написать программу по созданию, просмотру, добавлению и решению поставленной задачи для однонаправленного линейного списка (стек и/или очередь).
    Создать список из случайных целых чисел в диапазоне от 1 до 10, определить наиболее часто встречающееся число и удалить его.

    Как я понимаю после того как я ввел числа в стэк, мне их надо от туда извлечь, записать в строку, там удалить числа которые чаще всего повторяются и потом опять уже новую эту строку записать в стэк обратно??? Если так то подскажите как из стека преобразовать в строку, ну или может есть еще какие-то варианты?
    Код (C++):
    #include<stdio.h>//для работы с потоками ввода вывода
    #include<malloc.h>//для работы с динамической памятью
    #include<conio.h>//для работы с консолью
    #include<locale.h>//для подключения русского языка
    #include<stdlib.h>//стандартная библиотека

    struct Stack
    {
    int info;
    Stack *Next;
    };
    Stack *begin, *t;
    Stack* Create(Stack *);//функция типа Stack для создания стэка
    void prosm();//функция для просмотра содержимого стэка
    void exit();//функция выхода и освобождения памяти

    void main()//главная функция определяющая работу всей программы
    {
    int punkt,rp;//вводим целочисленные переменные: punkt-для определения пункта меню, rp-для выполнения цикла заполнения стэка
    setlocale(LC_CTYPE,"Russian");//подключаем русский язык
    do//начало цикла для работы меню программы
    {
    fflush(stdin);//чистим буфер
    system("cls");//чистим экран
    printf ("Выберите пункт меню:\n");
    puts("1-создание списка;");
    puts("2-просмотр списка;");
    puts("3-добавление элементов списка;");
    puts("4-решение поставленной задачи;");
    puts("0-выход;");
    scanf("%d",&punkt);//вводим число соответствующее пункту меню
    switch (punkt)//цикл выбранного пункта меню
    {
    case 1:case 3://если выбран пункт 1 или пункт 3
    {
    system("cls");//чистим экран
    rp=1;//присваиваем переменной значение 1 для осуществления работы цикла заполнения стэка
    if (punkt==1)//если меню 1
    {
    begin=NULL;//стэк пуст
    }
    while(rp)//пока значение переменной rp не 0 цикл будет работать
    {
    begin=Create(begin);//вершине стэка присваиваем значение t которое возвращает вызванная функция
    printf("Для прекращения ввода введите-0: ");
    scanf("%d",&rp);//вводим число для переменной rp по которому будет определена дальнейшая работа цикла
    }
    break;//прерываем цикл выходим в меню
    }
    case 2:prosm();break;//при выборе пункта меню 2 вызываем функцию просмотра содержимого стэка

    case 0: exit();break;//при выборе пункта меню 0 вызываем функцию выхода из программы
    }
    }
    while(1);//цикл меню программы выполняется бесконечно
    _getch();//ввод любой клавиши
    }
    Stack* Create(Stack *begin)
    {  
    Stack *t = (Stack*)malloc(sizeof(Stack));
    printf("\n Введите элемент списка:");
    scanf("%d", &t -> info);
    t -> Next = begin;
    return t;
    }

    void prosm()
    {  
    Stack *t = begin;
    if(begin == NULL) {        
    puts(" Стек пуст! ");
    return;
    }
    while( t != NULL) {
    printf(" %d \n", t->info);
    t = t -> Next;
    }
    _getch();
    }      

    void exit()//функция выхода
    {
    system("cls");//чистим экран
    while(begin!=NULL)//цикл будет работать пока стэк неопустеет
    {
    t=begin;//текущему значению присвоим значение вершины
    begin=t->Next;//вершине присвоим значение следующего элемента
    free(t);//очистим текущее значение
    }
    if(begin==NULL)//проверим стэк на наличие элементов
    puts("Память очищена! Нажмите любую клавишу для выхода!");//выводим сообщение
    _getch();//нажимаем любую клавишу
    exit(0);//выходим из программы
    }
    }
     
  2. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    неправильная у тебя программа.
    Над стеком по определению определяется лишь 2-3 операции -
    - добавить элемент в начало,
    - получить значение первого элемента
    - удалить первый элемент.

    Задание дал какой-то *цензура*. Никто не ищет в стеке самый часто встречающийся элемент.

    С очередью аналогично. Это примеры неправильного использования стандартных структур данных.

    Если дан произвольный однонаправленный список (не стек и не очередь) - то задание сойдет. Но укажи что именно не получается.

    Нахрена тебе строка? - я не вижу логики.
     
  3. kingl

    kingl New Member

    Регистрация:
    30 окт 2013
    Сообщения:
    2
    Симпатии:
    0
    Я заочник, мне это дали в универе задание, и я к тому про строку говорю, что просто из стека достать все элементы, записать их в строку, проделать над строкой операцию поиска и удаления наиболее повторяющихся элементов, а за тем эту строку опять записать в стэк, в таком порядке как я ее из стэка брал... Ну а задание надо выполнить, и не могу я сказать преподу что он *цензура*...
    Написать программу по созданию, просмотру, добавлению и решению поставленной задачи для однонаправленного линейного списка (стек и/или очередь). Здесь основная задача лабоаторной научиться работать со стэком или очередью(
     
  4. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Код (Text):
    #include <iostream>

    // узел односвязного списка
    struct Node {
    int val;
    Node *next;
    };

    void push(Node **phead, int val) {
    Node *pnhead = new Node;
    pnhead->next = *phead;
    pnhead->val = val;
    *phead = pnhead;
    }

    Node* pop(Node **phead) {
    Node *p = *phead;
    if (p == 0) return 0;
    *phead = (*phead)->next;
    return p;
    }

    int main() {
    Node *stack = 0;

    push(&stack, 1);
    push(&stack, 2);

    while (stack) {
    std::cout << pop(&stack)->val << std::endl;
    }
    }
    Вот набросок основных операций со стеком
     
  5. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    а дальше нужны костыли, т.к. нормальные люди не делают со стеком то, что делает ваш препод.

    подсчет числа вхождений элемента в стек:
    Код (Text):
    int count(Node *phead, int val) {
    if (0 == phead) return 0;
    return count(phead->next, val) + (phead->val == val);
    }
    выбор часто встречающегося:
    Код (Text):
    int mcval(Node *phead) {
    if (0 == phead) throw "bad ptr: mcval";
    if (0 == phead->next) return phead->val;

    int curc = count(phead, phead->val);
    int tailv = mcval(phead->next);
    int tailc = count(phead, tailv);

    if (curc > tailc) return phead->val;
    return tailv;
    }
     
  6. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Твоя задача целиком:
    Код (Text):
    #include <iostream>

    // узел односвязного списка
    struct Node {
    int val;
    Node *next;
    };

    void push(Node **phead, int val) {
    Node *pnhead = new Node;
    pnhead->next = *phead;
    pnhead->val = val;
    *phead = pnhead;
    }

    Node* pop(Node **phead) {
    Node *p = *phead;
    if (p == 0) return 0;
    *phead = (*phead)->next;
    return p;
    }

    int count(Node *phead, int val) {
    if (0 == phead) return 0;
    return count(phead->next, val) + (phead->val == val);
    }

    int mcval(Node *phead) {
    if (0 == phead) throw "bad ptr: mcval";
    if (0 == phead->next) return phead->val;

    int curc = count(phead, phead->val);
    int tailv = mcval(phead->next);
    int tailc = count(phead, tailv);

    if (curc > tailc) return phead->val;
    return tailv;
    }

    void rem(Node **phead, int val) {
    Node *p = pop(phead);
    if (0 == p) return;
    rem(phead, val);
    if (p->val != val)
    push(phead, p->val);
    }

    int main() {
    Node *stack = 0;

    push(&stack, 3);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 2);
    push(&stack, 2);
    push(&stack, 3);
    push(&stack, 3);
    push(&stack, 3);
    push(&stack, 3);
    push(&stack, 45);
    push(&stack, 1);
    push(&stack, 3);

    std::cout << "123 : " << count(stack, 123) << std::endl;
    std::cout << "1 : " << count(stack, 1) << std::endl;
    std::cout << "2 : " << count(stack, 2) << std::endl;
    std::cout << "1 : " << count(stack, 1) << std::endl;

    std::cout << "mcval: " << mcval(stack) << std::endl;

    rem(&stack, mcval(stack));

    while (stack) {
    std::cout << pop(&stack)->val << std::endl;
    }
    }
     
Загрузка...
Похожие Темы - Однонаправленные Списки (стэк)
  1. gx6060
    Ответов:
    0
    Просмотров:
    289
  2. shilovec5377
    Ответов:
    0
    Просмотров:
    1.187
  3. lmike
    Ответов:
    1
    Просмотров:
    1.869
  4. DNT
    Ответов:
    8
    Просмотров:
    4.019

Поделиться этой страницей