20 вариант - Структуры и алгоритмы обработки данных
Описание файла
Документ из архива "20 вариант - Структуры и алгоритмы обработки данных", который расположен в категории "". Всё это находится в предмете "введение в специальность" из 3 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "введение в специальность" в общих файлах.
Онлайн просмотр документа "20 вариант - Структуры и алгоритмы обработки данных"
Текст из документа "20 вариант - Структуры и алгоритмы обработки данных"
МОСКВОСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ
ОТЧЕТ
О выполнении домашней работы по дисциплине «Структуры и алгоритмы обработки данных»
ВЫПОЛНИЛ:
студент 1-го курса гр ИТ-6
Кульнев А.М. №студ 100516
ПРОВЕРИЛ:
доцент кафедры ИТ-6
Филатов В.В.
г.Москва 2011г.
Задание: 100516 mod 44 = 20 Вариант20: «Стек, естественное двухпутевое слияние».
ЛИСТИНГ:
headers.h
#include <iostream>
#include <stdlib.h>
#include <clocale>
#include <time.h>
#include <fstream>
#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"
ofstream file("result.txt");
enum {STACK_SIZE = 32};
void stack_print(ofstream& file, MyStack& Stack);
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, "");
MyStack Stack1, Stack2;
// заполнение стека худшим вариантом
file << "==========" << endl
<< "Исходный стек: худший вариант, размер стека=" << STACK_SIZE << endl;
bool flag = true;
for(int count=1, i=0, j=(STACK_SIZE/2)+STACK_SIZE%2; count<=STACK_SIZE; count++){
if (flag){
i++;
Stack1.PutValue(i);
}
else{
j++;
Stack1.PutValue(j);
}
flag = !flag;
}
stack_print(file, Stack1);
file << "==========" << endl << endl;
int natural_length=0;
int clock_start = clock();
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);
file << natural_length << endl;
stack_merge(Stack2, natural_stack_1, natural_stack_2);
if (Stack1.IsEmpty()){
Stack1 = Stack2;
MyStack tmp;
Stack2 = tmp;
}
}
file << "==========" << endl << "Результат сортировки: " << endl;
stack_print(file, Stack1);
file << "==========" << endl << endl ;
file << "----------" << endl << "время сортировки: " << endl;
file << " " << clock()-clock_start << " мс" << endl;
file << "----------";
file.close();
ShellExecuteA(NULL, "open", "notepad++.exe", "result.txt", NULL, SW_SHOWNORMAL);
}
void stack_print(ofstream& file, MyStack& Stack){
MyStack tmp;
while(!Stack.IsEmpty())
tmp.PutValue(Stack.GetValue());
for(dataType value; !tmp.IsEmpty(); ){
value=tmp.GetValue();
Stack.PutValue(value);
file<<value<<" ";
}
file << endl;
}
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());
}
}
}
РАСЧЕТ ТРУДОЁМКОСТИ:
headers.h
#include <iostream>
#include <stdlib.h>
#include <clocale>
#include <time.h>
#include <fstream>
#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(); +1
~MyStack(); 6n+1
void PutValue(dataType Value); +9
dataType GetValue(); +10
dataType Value(); +3
bool IsEmpty(); +2
MyStack& operator = (const MyStack& tmp); +4
};
mystack.cpp
#include "headers.h"
#include <stdlib.h>
MyStack::MyStack():Head(NULL){} +1
MyStack::~MyStack(){ 6n+1
while(Head){ +1+n(+1
stack_element *current = Head; +2
Head=current->Next; +2
free(current); +1
} )
}
void MyStack::PutValue(const dataType Value){ +9
stack_element *newElement = static_cast<stack_element*>(new stack_element); +4
newElement->Data=Value; +2
newElement->Next=Head; +2
Head=newElement; +1
}
dataType MyStack::GetValue(){ +10
if (!Head) +1
return NULL;
stack_element *currentElement = Head; +2
dataType Value = currentElement->Data;+3
Head = Head->Next; +2
free(currentElement); +1
return Value; +1
}
dataType MyStack::Value(){ +3
if (!Head) +1
return NULL;
return Head->Data; +2
}
bool MyStack::IsEmpty(){ +2
return Head==NULL; +2
}
MyStack& MyStack::operator = (const MyStack& tmp){ +4
this->Head = tmp.Head; +2
return *this; +2
}
main.cpp
#include "headers.h"
ofstream file("result.txt");
enum {STACK_SIZE = 32};
void stack_print(ofstream& file, MyStack& Stack);
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, ""); +1
MyStack Stack1, Stack2; +2
// заполнение стека худшим вариантом
file << "==========" +1
<< endl +1
<< "Исходный стек: худший вариант, размер стека=" << STACK_SIZE +2
<< endl; +1
bool flag = true; +1
for( +10+12n
int c=1, i=0, j=(STACK_SIZE/2)+STACK_SIZE%2; +9
c<=STACK_SIZE; +1+n(
c++){ +1
if (flag){ +1
i++; +1
Stack1.PutValue(i); +9
}
else{
j++;
Stack1.PutValue(j);
}
flag = !flag; +2
} )
stack_print(file, Stack1); +3
file << "==========" << endl << endl; +3
int natural_length=0; +3
int clock_start = clock(), step_count=0;+3
+1+44
+45(n(log2n)-n)
while(natural_length!=STACK_SIZE){ +1+
)(+1+
natural_length=0; +1
MyStack natural_stack_1, natural_stack_2; +2
if (Stack1.IsEmpty()){ +2+ )(+2
Stack1 = Stack2; +4
MyStack tmp; +1
Stack2 = tmp; +1
} )
} )
file << "----------" << endl << "время сортировки: " << endl; +4
file << " " << clock()-clock_start << " мс" << endl; +5
file << "----------"; +1
file.close(); +1
ShellExecuteA(NULL, "open", "notepad++.exe", "result.txt", NULL, SW_SHOWNORMAL);+1
}
void stack_print(ofstream& file, MyStack& Stack){ +7+45n
MyStack tmp; +1
while(!Stack.IsEmpty()) +2+n(+2
tmp.PutValue(Stack.GetValue()); +19)
for(dataType value; !tmp.IsEmpty(); ){ +1+2+n(+2
value=tmp.GetValue(); +11
Stack.PutValue(value); +9
file<<value<<" "; +2
} )
file << endl; +1
}
void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length){+31i+21c
фактически i = количеству вызовов stack_get_natural а с = длине стека new_stack
if (Stack.IsEmpty()) +1
return;
natural_length++; +1
new_stack.PutValue(Stack.GetValue()); +19
while(!(Stack.IsEmpty() || Stack.Value() > new_stack.Value())){+10+c(+10
natural_length++; +1
new_stack.PutValue(Stack.GetValue()); +10
} )
}
void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2){ +i+24c
фактически i = количеству вызовов stack_merge а с = длине стека new_stack
while(true){ +1+n(+1
if (nat_stack_1.IsEmpty()) { +3
while(!nat_stack_2.IsEmpty())
result_stack.PutValue(nat_stack_2.GetValue());
break;
} else if (nat_stack_2.IsEmpty()) { +3
while(!nat_stack_1.IsEmpty())
result_stack.PutValue(nat_stack_1.GetValue());
break;
} else {
if (nat_stack_2.Value() <= nat_stack_1.Value() +7
result_stack.PutValue(nat_stack_2.GetValue()); +10
else
result_stack.PutValue(nat_stack_1.GetValue());
}
} )
}
F(n) = 44 + 12n + 57 + 45(n(log2n)-n)
O(F(n))= n(log2n)
