Структуры и алгоритмы обработки данных, страница 2
Описание файла
Документ из архива "Структуры и алгоритмы обработки данных", который расположен в категории "". Всё это находится в предмете "введение в специальность" из 3 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "введение в специальность" в общих файлах.
Онлайн просмотр документа "Структуры и алгоритмы обработки данных"
Текст 2 страницы из документа "Структуры и алгоритмы обработки данных"
4. Контрольный пример (принтскрин значений N, t, Nop):
5. Полный листинг кода программы:
<headers.h>
#include <iostream>
#include <stdlib.h>
#include <clocale>
#include <time.h>
#include "windows.h"
using namespace std;
typedef int dataType;
struct stack_element{
stack_element *Next;
dataType Data;
};
class MyStack{
private:
stack_element *Head;
public:
MyStack();
~MyStack();
void PutValue(dataType Value);
dataType GetValue();
dataType Value();
bool IsEmpty();
MyStack& operator = (const MyStack& tmp);
};
<mystack.cpp>
#include "headers.h"
#include <stdlib.h>
MyStack::MyStack():Head(NULL){}
MyStack::~MyStack(){
while(Head){
stack_element *current = Head;
Head=current->Next;
free(current);
}
}
void MyStack::PutValue(const dataType Value){
stack_element *newElement = static_cast<stack_element*>(new stack_element);
newElement->Data=Value;
newElement->Next=Head;
Head=newElement;
}
dataType MyStack::GetValue(){
if (!Head)
return NULL;
stack_element *currentElement = Head;
dataType Value = currentElement->Data;
Head = Head->Next;
free(currentElement);
return Value;
}
dataType MyStack::Value(){
if (!Head)
return NULL;
return Head->Data;
}
bool MyStack::IsEmpty(){
return Head==NULL;
}
MyStack& MyStack::operator = (const MyStack& tmp){
this->Head = tmp.Head;
return *this;
}
<main.cpp>
#include "headers.h"
enum {MAX_AVERAGE_COUNT=10, MAX_POWER=12};
int STACK_SIZE = 512, Nop=0;
void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length);
void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2);
void main(){
setlocale(LC_CTYPE, "");
for(int power=0; power < MAX_POWER; power++){
DWORD tick_start = GetTickCount();
Nop = 0;
for(int average_count=0; average_count<MAX_AVERAGE_COUNT; average_count++){
MyStack Stack1, Stack2;
srand(time(0));
for(int i=0; i<STACK_SIZE; i++)
Stack1.PutValue(100+rand()%900);
int natural_length=0;
while(natural_length!=STACK_SIZE){
natural_length=0;
MyStack natural_stack_1, natural_stack_2;
stack_get_natural(Stack1, natural_stack_1, natural_length);
stack_get_natural(Stack1, natural_stack_2, natural_length);
stack_merge(Stack2, natural_stack_1, natural_stack_2);
if (Stack1.IsEmpty()){
Stack1 = Stack2;
MyStack tmp;
Stack2 = tmp;
}
}
}
int tick_average = (GetTickCount()-tick_start)/MAX_AVERAGE_COUNT;
cout << "----------" << endl;
cout << " N = " << STACK_SIZE << endl;
cout << " t = " << tick_average << endl;
cout << " Nop = " << Nop/MAX_AVERAGE_COUNT << endl;
cout << "----------" << endl;
STACK_SIZE *= 2;
}
system("pause");
}
void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length){
if (Stack.IsEmpty())
return;
natural_length++;
new_stack.PutValue(Stack.GetValue());
while(!(Stack.IsEmpty()|| Stack.Value() > new_stack.Value())){
natural_length++;
new_stack.PutValue(Stack.GetValue());
}
}
void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2){
while(true){
if (nat_stack_1.IsEmpty()) {
while(!nat_stack_2.IsEmpty())
result_stack.PutValue(nat_stack_2.GetValue());
break;
} else if (nat_stack_2.IsEmpty()){
while(!nat_stack_1.IsEmpty()){
result_stack.PutValue(nat_stack_1.GetValue());
break;
} else {
if (nat_stack_2.Value() <= nat_stack_1.Value())
result_stack.PutValue(nat_stack_2.GetValue());
else
result_stack.PutValue(nat_stack_1.GetValue());
}
}
}
