Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.426 RSS
←   Июнь 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.426 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Советник
Рейтинг: 10889
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 4329
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2515
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:1757
Дата выхода:08.06.2012, 16:00
Администратор рассылки:Киселёва Алёна aka Verena (Академик)
Подписчиков / экспертов:134 / 94
Вопросов / ответов:1 / 2

Консультация # 186319: Здравствуйте! Помогите пожалуйста, вот с такой программой:

Код :
#include <stdio.h>
#include <stdlib.h>

typedef struct NODE //Элемент стека
{
	struct NODE *previous;
	int value;
} Node;

typedef struct STACK //Стек
...

Консультация # 186319:

Здравствуйте! Помогите пожалуйста, вот с такой программой:

Код :
#include <stdio.h>
#include <stdlib.h>

typedef struct NODE //Элемент стека
{
	struct NODE *previous;
	int value;
} Node;

typedef struct STACK //Стек
{
  Node *head; //Дно
} Stack;

Node *CreateNode(Node *previous, int value) //Создаем элемент
{
  Node *node = (Node*)malloc(sizeof(Node)); //Выделяем память
	node->previous = previous;
	node->value = value;
	return node;
}

Stack *CreateStack() //Создаем стек
{
  Stack *stack = (Stack *)malloc(sizeof(Stack)); //Выделяем память
	stack->head = NULL;
	return stack;
}

void Push(Stack *s, int value) //"Толкнуть" в стек
{
	s->head = CreateNode(s->head, value);
}

int Top(Stack *s) //Просмотр элемента
{
	if(s->head == NULL)
	{
                //Стек пустой
		return 0;
	}
	return s->head->value;
}

int Pop(Stack *s) //Извлечь из стека
{
	Node *prevHead = s->head;
	int val;
	if(s->head == NULL) //Если стек пустой,
	{
	  return 0; //то нечего извлекать
	}
	val = s->head->value;
	s->head = s->head->previous;
	free(prevHead);
	return val;	
}

//Печать элемента
void PrintNode(Node *s) 
{
	if(s==NULL){
printf("NULL\n\n");
return;
}
	printf("%d  ---  ",s->value);
	PrintNode(s->previous);
}

//Печать стека
void PrintStack(Stack *s)
{
	PrintNode(s->head);
	return;
}


int main()
{
	int i,size;	
	int max=0;	
	int order=0;
	int orderMax=0;
	Stack *a=CreateStack();
	Stack *b=CreateStack();
	Stack *c=CreateStack();
	Stack *d=CreateStack();

        printf("Введите количество, пожалуйста: ");
        scanf("%d",&size);
        printf("\n");
        
        printf("Введите числа, пожалуйста: \n");
	while (order < size) { //Пока размер стека а позволяет, 
		scanf("%d",&i);
		Push(a,i); //записываем в него элементы
		order++;
	}
        printf("\n");
        
	while (size > 0) {             
		order=0;
		orderMax=0;
		max=0;

		while (a->head != NULL) { //Пока стек а не опустеет,
		  Push(d,Pop(a)); //"выталкиваем" элементы из а в d      
		}
                
		order=0;
		while (order < size) {
			if (Top(d) > max) {
				max = Top(d);
				orderMax = order+1;
			}
			Push(a,Pop(d)); //"Выталкиваем" элементы из d в a
			order++;        
		}

		printf("STACK a:  ");  
		PrintStack(a); //Печатаем стек а
 
		int first; 
		first = Pop(a);

		i=0;
		while (i < size - orderMax) {
		  Push(b,Pop(a)); //"Выталкиваем" элементы из a в b
			i++;        
		}
        
		Push(a,first);
		if (Top(b) == 0) {
		  Push(c,Top(a)); //"Выталкиваем" элементы из a в c
		}
		else
		  Push(c,Pop(b)); //"Выталкиваем" элементы из b в c

		while ( b->head != NULL) { //Пока стек b не опустеет,
		  Push(a,Pop(b));    //"выталкиваем" элементы из b в a
		}

		printf("STACK c:  ");
		PrintStack(c);
		printf("\n");
		size--;   
	}
        
        Pop(a);
        while (c->head != NULL) { //Пока стек c не опустеет,
	  Push(a,Pop(c)); // "выталкиваем" элементы из c в a
        }
        printf("~~~~~~~\n");
	printf("STACK a:  ");  
	PrintStack(a);
        printf("~~~~~~~\n");
        
        printf("Удалить элемент / выйти ( y / \\n ):  \n");
	while (((c=getchar())!='n')&&((c=getchar())!='\n')) { //Пока нет условия окончания 
	  if(a->head == NULL){                       //Когда стек а опустеет,
	    printf("Стек опустел, выход из программы\n"); //выходим
	    return 0;
	      }
	  Pop(a); //Выталкиваем элементы из a,
	  printf("\n STACK a:  ");
		PrintStack(a); //каждый раз печатая стек 
        }        
	return 0;
}


В данной программе реализована процедура поиска и удаления максимального элемента в стеке, сортировка - линейный выбор.

Хотелось бы поподробнее разобраться с некоторыми моментами программы:
1) За что конкретно отвечает функция Top()?Она возвращает значение "дна" стека или "крышки"?(иными словами, действительно ли *head в программе - указатель на "дно"?)
2)
Код :
order=0;
		while (order < size) {
			if (Top(d) > max) {
				max = Top(d);
				orderMax = order+1;
			}
			Push(a,Pop(d)); //"Выталкиваем" элементы из d в a
			order++;

Код :
int first; 
		first = Pop(a);

		i=0;
		while (i < size - orderMax) {
		  Push(b,Pop(a)); //"Выталкиваем" элементы из a в b
			i++;        
		}
        
		Push(a,first);
		if (Top(b) == 0) {
		  Push(c,Top(a)); //"Выталкиваем" элементы из a в c
		}
		else
		  Push(c,Pop(b)); //"Выталкиваем" элементы из b в c

		while ( b->head != NULL) { //Пока стек b не опустеет,
		  Push(a,Pop(b));    //"выталкиваем" элементы из b в a
		}


За что отвечают эти циклы?

3)* Можно ли изменить(дописать) программу так, чтобы в ней осуществлялась сортировка слиянием и выполнялось слияние 2х стеков?

Огромное спасибо!

С уважением,
Иван.

Дата отправки: 05.06.2012, 14:39
Вопрос задал: Барс Иван (Посетитель)
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Асмик Гаряка (Советник):

Здравствуйте, Барс Иван!

1) За что конкретно отвечает функция Top()?Она возвращает значение "дна" стека или "крышки"?(иными словами, действительно ли *head в программе - указатель на "дно"?)
Нет, это указатель на "крышку". Дно в стеке и не нужно, хотя можно было его добавить в структуру.
2)

Код :

    order=0;
    while (order < size) {
    if (Top(d) > max) {
    max = Top(d);
    orderMax = order+1;
    }
    Push(a,Pop(d)); //"Выталкиваем" элементы из d в a
    order++;


Ищется максимальный элемент, при этом стек переводится из d в a. Так как предварительно его перевели из a в d, стек остается в первоначальном положении.

Код :
    int first;
    first = Pop(a);
    i=0;
    while (i < size - orderMax) {
    Push(b,Pop(a)); //"Выталкиваем" элементы из a в b
    i++;
    }
    Push(a,first);
    if (Top(b) == 0) {
    Push(c,Top(a)); //"Выталкиваем" элементы из a в c
    }
    else
    Push(c,Pop(b)); //"Выталкиваем" элементы из b в c
    while ( b->head != NULL) { //Пока стек b не опустеет,
    Push(a,Pop(b)); //"выталкиваем" элементы из b в a
    }


Элементы выталкиваются в b, вплоть до максимального. Теперь максимальный находится на верхушке b. first = Pop(a); мне кажется, излишне.
Затем максимальный элемент переводится в c, а остальные элементы вовращаются в a. Таким образом, в c накапливаются элементы в порядке убывания.


3)* Можно ли изменить(дописать) программу так, чтобы в ней осуществлялась сортировка слиянием и выполнялось слияние 2х стеков?
Можно. smile

Консультировал: Асмик Гаряка (Советник)
Дата отправки: 05.06.2012, 16:40
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Кирилл (1-й класс):

Здравствуйте, Барс Иван!

1) За что конкретно отвечает функция Top()?Она возвращает значение "дна" стека или "крышки"?(иными словами, действительно ли *head в программе - указатель на "дно"?)

Функция int Top() выводит значение последнего добавленного элемента - вершины стека. *head - указатель на вершину стека. Дном здесь и не пахнет, поскольку постольку void Push() "толкает" в стек элементы, каждый раз записывая вершину в область памяти, на которую указывает указатель *head.

Код :

Код :
s->head = CreateNode(s->head, value);



2) За что отвечают эти циклы?

Первый цикл ищет максимальный элемент и записывает его в max, толкая при этом стек d обратно в стек a.
Второй цикл сначала отрезает часть стека а в стек b до максимального элемента, затем максимальный эл емент помещает в с, затем стек b присоединяет обратно к стеку а. Таким образом реализуется сортировка - линейный выбор

3)* Можно ли изменить(дописать) программу так, чтобы в ней осуществлялась сортировка слиянием и выполнялось слияние 2х стеков?

Да, конечно можно. Для начала модифицировал код программы.

Код :
///Доработка программы by Saradomin
///Добавим новую функцию void push_stack_to_stack(stack*, stack*)
///Заменим все конструкции следующего вида:
///Push(X,Pop(Y)); //"Выталкиваем" элементы из Y в X
///На конструкции следующего вида:
///push_stack_to_stack(Y,X);

///Добавим новую функцию void merger_stack2_to_stack1()

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

typedef struct NODE //Элемент стека
	{
		struct NODE *previous;
		int value;
	} Node;
	
typedef struct STACK //Стек
	{
		Node *head; //Вершина
	} Stack;

	///Определили стек и его элемент
	
	Node *CreateNode(Node *previous, int value) //Создание элемента
	{
		Node *node = (Node*)malloc(sizeof(Node)); //Выделяем память
		node->previous = previous;
		node->value = value;
		return node;
	}
	
	Stack *CreateStack() //Создание стека
	{
		Stack *stack = (Stack *)malloc(sizeof(Stack)); //Выделяем память
		stack->head = NULL;
		return stack;
	}

	void Push(Stack *s, int value) //"Толкнуть" в стек
	{
		s->head = CreateNode(s->head, value);
	}

	int Top(Stack *s) //Просмотр вершины
	{
		if(s->head == NULL) 	//Если стек пустой,
			{
			return 0; //то извлекать нечего
			}
		return s->head->value;
	}

	int Pop(Stack *s) //Извлечь из стека
	{
		Node *prevHead = s->head;
		int val;
		if(s->head == NULL) //Если стек пустой,
			{
			return 0; //то нечего извлекать
			}
		val = s->head->value;
		s->head = s->head->previous;
		free(prevHead);
		return val;
	}

	void PrintNode(Node *s) //Печать элемента
	{
		if(s==NULL)
			{
				printf("NULL\n\n");
				return;
			}
		printf("%d --- ",s->value);
		PrintNode(s->previous);
	}///Вспомогательная для PrintStack()

	void PrintStack(Stack *s)
	{
		PrintNode(s->head);
		return;
	}
	
	void push_stack_to_stack(Stack *first, Stack *second) ///Толкаем первый стек во второй поэлементно
	{
		Push(second,Pop(first));
		return;
	}
	
	void merger_stack2_to_stack1(Stack *stack_01, Stack *stack_02) ///Слияние двух стеков и запись в первый стек
	{
		Stack *temp_stack=CreateStack();
		while(stack_02->head != NULL) {
			push_stack_to_stack(stack_02,temp_stack);
		}
		while(temp_stack->head != NULL) {
			push_stack_to_stack(temp_stack,stack_01);
		}
		return;
	}
	
	int main()
	{
		int i,size;
		int max=0;
		int order=0;
		int orderMax=0;
		Stack *a=CreateStack();
		Stack *b=CreateStack();
		Stack *c=CreateStack();
		Stack *d=CreateStack();
		
		printf("Введите количество, пожалуйста: ");
		scanf("%d",&size);
		printf("\n");
		printf("Введите числа, пожалуйста: \n");
		
		while (order < size) 	//Пока размер стека а позволяет,
		{
			scanf("%d",&i);
			Push(a,i); //записываем в него элементы
			order++;
		}
		
		printf("\n");
		
		while (size > 0) ///Линейный выбор
		{
			order=0;
			orderMax=0;
			max=0;
			
			while (a->head != NULL)		//Пока стек а не опустеет,
			{
				//Push(d,Pop(a)); //"выталкиваем" элементы из а в d
				push_stack_to_stack(a,d);
			}
			
			order=0;
			while (order < size)
			{
				if (Top(d) > max)
				{
					max = Top(d);
					orderMax = order+1;
				}
				push_stack_to_stack(d,a);
				order++;
			}
			
			printf("STACK a: ");
			PrintStack(a); //Печатаем стек а
			
			i=0;
			
			while (i < size - orderMax+1)
			{
				push_stack_to_stack(a,b);
				i++;
			}
			
			if (Top(b) == 0) {
				push_stack_to_stack(a,c);
			}
			else {
				push_stack_to_stack(b,c);
			}

			while ( b->head != NULL) { //Пока стек b не опустеет,
				push_stack_to_stack(b,a);
			}
			
			printf("STACK c: ");
			PrintStack(c);
			printf("\n");
			
			size--;
		}
		
		Pop(a);
		
		while (c->head != NULL) { //Пока стек c не опустеет,
			push_stack_to_stack(c,a);
		}
		
		printf("~~~~~~~\n");
		printf("STACK a: ");
		PrintStack(a);
		printf("~~~~~~~\n");
		printf("Удалить элемент / выйти ( y / \\n ): \n");
		
		while (((c=getchar())!='n')&&((c=getchar())!='\n')) { //Пока нет условия окончания
			if(a->head == NULL){ //Когда стек а опустеет,
				printf("Стек опустел, выход из программы\n"); //выходим
				return 0;
			}
			
			Pop(a); //Выталкиваем элементы из a,
			printf("\n STACK a: ");
			PrintStack(a); //каждый раз печатая стек
		}
		return 0;
	}

Консультировал: Кирилл (1-й класс)
Дата отправки: 05.06.2012, 19:44
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012
В избранное