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

kingl

New Member
30.10.2013
2
0
#1
Написать программу по созданию, просмотру, добавлению и решению поставленной задачи для однонаправленного линейного списка (стек и/или очередь).
Создать список из случайных целых чисел в диапазоне от 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);//выходим из программы
}
}
 
R

rrrFer

Гость
#2
неправильная у тебя программа.
Над стеком по определению определяется лишь 2-3 операции -
- добавить элемент в начало,
- получить значение первого элемента
- удалить первый элемент.

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

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

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

Как я понимаю после того как я ввел числа в стэк, мне их надо от туда извлечь, записать в строку, там удалить числа которые чаще всего повторяются и потом опять уже новую эту строку записать в стэк обратно??? Если так то подскажите как из стека преобразовать в строку, ну или может есть еще какие-то варианты?
Нахрена тебе строка? - я не вижу логики.
 

kingl

New Member
30.10.2013
2
0
#3
Я заочник, мне это дали в универе задание, и я к тому про строку говорю, что просто из стека достать все элементы, записать их в строку, проделать над строкой операцию поиска и удаления наиболее повторяющихся элементов, а за тем эту строку опять записать в стэк, в таком порядке как я ее из стэка брал... Ну а задание надо выполнить, и не могу я сказать преподу что он *цензура*...
Написать программу по созданию, просмотру, добавлению и решению поставленной задачи для однонаправленного линейного списка (стек и/или очередь). Здесь основная задача лабоаторной научиться работать со стэком или очередью(
 
R

rrrFer

Гость
#4
Код:
#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;
}
}
Вот набросок основных операций со стеком
 
R

rrrFer

Гость
#5
а дальше нужны костыли, т.к. нормальные люди не делают со стеком то, что делает ваш препод.

подсчет числа вхождений элемента в стек:
Код:
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;
}
 
R

rrrFer

Гость
#6
Твоя задача целиком:
Код:
#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;
}
}