«Сравнение и анализ алгоритмов сортировки двусвязного списка методом прямого включения»

Заказать уникальную курсовую работу
Тип работы: Курсовая работа
Предмет: Программирование
  • 53 53 страницы
  • 7 + 7 источников
  • Добавлена 15.06.2024
1 496 руб.
  • Содержание
  • Часть работы
  • Список литературы
Содержание 4
Введение 5
1. Постановка задачи и анализ предметной области 6
1.1. Основные понятия и определения 6
1.2. Постановка задачи на разработку программы 7
1.3. Анализ требований 7
1.3.1. Требования к интерфейсу пользователя 7
1.3.2. Требования к структуре данных 8
1.3.3. Требования к программным средствам 8
1.4. Технология разработки программного обеспечения 11
2. Проектирование программы 13
2.1. Модель Интерфейса 13
2.2. Проектирование структур данных 14
2.3. Структура программного обеспечения 14
3. Реализация программы 16
3.1. Кодирование 16
3.2. Диаграмма компонентов 17
4. Тестирование программы 20
4.1. Виды тестирование программных средств 20
4.2. Функциональное тестирование программы 21
5. Анализ результатов 29
Заключение 33
Список используемых источников 34
Приложение А. 35
Код программы 35

Фрагмент для ознакомления

dat", FileMode::Create);
if (f1->Length > 0) {
int N = f1->Length;
array^ buf = gcnew array(1000);

int L = 1; // Длина отсортированной части
while (L < N) { // Пока не отсортировано все
f2->Seek(0, SeekOrigin::Begin);
f1->Seek(L, SeekOrigin::Begin);
unsigned char V = f1->ReadByte();
// Ищем место вставки и сразу формируем файл с результатом вставки
int pos = 0;
f1->Seek(pos, SeekOrigin::Begin);
while (pos < L) {
unsigned char V1 = f1->ReadByte();
if (V < V1)
break;
f2->WriteByte(V1);
pos++;
}
f2->WriteByte(V);
f1->Seek(pos, SeekOrigin::Begin);
while (pos < L) {
int read = f1->Read(buf, 0, Math::Min(L - pos, buf->Length));
f2->Write(buf, 0, read);
pos += read;
}
pos++;
f1->Seek(pos, SeekOrigin::Begin);
// Дописываем в промежуточный файл неотсортированный остаток
while (pos < N) {
int read = f1->Read(buf, 0, Math::Min(N - pos, buf->Length));
f2->Write(buf, 0, read);
pos += read;
}
L++;
FileStream^ f = f1;
f1 = f2;
f2 = f;
}
if (Path::GetFileName(f1->Name)->Equals("temp.dat")) {
f1->Seek(0, SeekOrigin::Begin);
array^ data = gcnew array(f1->Length);
f1->Read(data, 0, data->Length);
f2->Seek(0, SeekOrigin::Begin);
f2->Write(data, 0, data->Length);
}
}
f2->Close();
f1->Close();
}

}

Файл MyForm.h
#pragma once

#include "sorts.h"

namespace sortings {

using namespace System;
using namespace System::ComponentModel;
using namespace System::Collections;
using namespace System::Windows::Forms;
using namespace System::Data;
using namespace System::Drawing;

///


/// Сводка для MyForm
///

public ref class MyForm : public System::Windows::Forms::Form
{
public:
MyForm(void)
{
InitializeComponent();
//
//TODO: добавьте код конструктора
//
}

protected:
///
/// Освободить все используемые ресурсы.
///

~MyForm()
{
if (components)
{
delete components;
}
}
private: System::Windows::Forms::Button^ btStart;
private: System::Windows::Forms::GroupBox^ groupBox1;



private: System::Windows::Forms::GroupBox^ groupBox2;
private: System::Windows::Forms::RadioButton^ rbPartialSorted;


private: System::Windows::Forms::RadioButton^ rbRevSorted;
private: System::Windows::Forms::RadioButton^ rbSorted;
private: System::Windows::Forms::RadioButton^ rbRandom;
private: System::Windows::Forms::DataVisualization::Charting::Chart^ Chart;



private: System::Windows::Forms::GroupBox^ groupBox3;
private: System::Windows::Forms::CheckedListBox^ cbNums;


private: System::Windows::Forms::DataGridView^ Grid;
private: System::Windows::Forms::CheckedListBox^ cbMethods;
private: System::Windows::Forms::Label^ label2;
private: System::Windows::Forms::NumericUpDown^ nmPercent;

private: System::Windows::Forms::Label^ label1;

protected:

private:
///
/// Обязательная переменная конструктора.
///

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code
///
/// Требуемый метод для поддержки конструктора — не изменяйте
/// содержимое этого метода с помощью редактора кода.
///

void InitializeComponent(void)
{
this->btStart = (gcnew System::Windows::Forms::Button());
this->groupBox1 = (gcnew System::Windows::Forms::GroupBox());
this->cbMethods = (gcnew System::Windows::Forms::CheckedListBox());
this->groupBox2 = (gcnew System::Windows::Forms::GroupBox());
this->label2 = (gcnew System::Windows::Forms::Label());
this->nmPercent = (gcnew System::Windows::Forms::NumericUpDown());
this->label1 = (gcnew System::Windows::Forms::Label());
this->rbPartialSorted = (gcnew System::Windows::Forms::RadioButton());
this->rbRevSorted = (gcnew System::Windows::Forms::RadioButton());
this->rbSorted = (gcnew System::Windows::Forms::RadioButton());
this->rbRandom = (gcnew System::Windows::Forms::RadioButton());
this->Chart = (gcnew System::Windows::Forms::DataVisualization::Charting::Chart());
this->groupBox3 = (gcnew System::Windows::Forms::GroupBox());
this->cbNums = (gcnew System::Windows::Forms::CheckedListBox());
this->Grid = (gcnew System::Windows::Forms::DataGridView());
this->groupBox1->SuspendLayout();
this->groupBox2->SuspendLayout();
(cli::safe_cast(this->nmPercent))->BeginInit();
(cli::safe_cast(this->Chart))->BeginInit();
this->groupBox3->SuspendLayout();
(cli::safe_cast(this->Grid))->BeginInit();
this->SuspendLayout();
//
// btStart
//
this->btStart->Location = System::Drawing::Point(12, 471);
this->btStart->Name = L"btStart";
this->btStart->Size = System::Drawing::Size(223, 28);
this->btStart->TabIndex = 0;
this->btStart->Text = L"Запуск сортировок";
this->btStart->UseVisualStyleBackColor = true;
this->btStart->Click += gcnew System::EventHandler(this, &MyForm::btStart_Click);
//
// groupBox1
//
this->groupBox1->Controls->Add(this->cbMethods);
this->groupBox1->Location = System::Drawing::Point(12, 12);
this->groupBox1->Name = L"groupBox1";
this->groupBox1->Size = System::Drawing::Size(223, 132);
this->groupBox1->TabIndex = 1;
this->groupBox1->TabStop = false;
this->groupBox1->Text = L" Методы сортировки ";
//
// cbMethods
//
this->cbMethods->FormattingEnabled = true;
this->cbMethods->Items->AddRange(gcnew cli::array< System::Object^ >(3) { L"Простым слянием", L"Естественным слиянием", L"Поглощением" });
this->cbMethods->Location = System::Drawing::Point(6, 19);
this->cbMethods->Name = L"cbMethods";
this->cbMethods->Size = System::Drawing::Size(210, 106);
this->cbMethods->TabIndex = 0;
//
// groupBox2
//
this->groupBox2->Controls->Add(this->label2);
this->groupBox2->Controls->Add(this->nmPercent);
this->groupBox2->Controls->Add(this->label1);
this->groupBox2->Controls->Add(this->rbPartialSorted);
this->groupBox2->Controls->Add(this->rbRevSorted);
this->groupBox2->Controls->Add(this->rbSorted);
this->groupBox2->Controls->Add(this->rbRandom);
this->groupBox2->Location = System::Drawing::Point(11, 150);
this->groupBox2->Name = L"groupBox2";
this->groupBox2->Size = System::Drawing::Size(224, 132);
this->groupBox2->TabIndex = 2;
this->groupBox2->TabStop = false;
this->groupBox2->Text = L" Данные ";
//
// label2
//
this->label2->AutoSize = true;
this->label2->Location = System::Drawing::Point(200, 108);
this->label2->Name = L"label2";
this->label2->Size = System::Drawing::Size(19, 16);
this->label2->TabIndex = 8;
this->label2->Text = L"%";
//
// nmPercent
//
this->nmPercent->Location = System::Drawing::Point(142, 105);
this->nmPercent->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 1, 0, 0, 0 });
this->nmPercent->Name = L"nmPercent";
this->nmPercent->Size = System::Drawing::Size(58, 22);
this->nmPercent->TabIndex = 7;
this->nmPercent->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) { 50, 0, 0, 0 });
//
// label1
//
this->label1->AutoSize = true;
this->label1->Location = System::Drawing::Point(8, 107);
this->label1->Name = L"label1";
this->label1->Size = System::Drawing::Size(127, 16);
this->label1->TabIndex = 6;
this->label1->Text = L"Упорядоченность:";
//
// rbPartialSorted
//
this->rbPartialSorted->AutoSize = true;
this->rbPartialSorted->Location = System::Drawing::Point(8, 80);
this->rbPartialSorted->Name = L"rbPartialSorted";
this->rbPartialSorted->Size = System::Drawing::Size(198, 20);
this->rbPartialSorted->TabIndex = 5;
this->rbPartialSorted->Text = L"Частично упорядоченные";
this->rbPartialSorted->UseVisualStyleBackColor = true;
//
// rbRevSorted
//
this->rbRevSorted->AutoSize = true;
this->rbRevSorted->Location = System::Drawing::Point(8, 60);
this->rbRevSorted->Name = L"rbRevSorted";
this->rbRevSorted->Size = System::Drawing::Size(192, 20);
this->rbRevSorted->TabIndex = 2;
this->rbRevSorted->Text = L"Обратно упорядоченные";
this->rbRevSorted->UseVisualStyleBackColor = true;
//
// rbSorted
//
this->rbSorted->AutoSize = true;
this->rbSorted->Location = System::Drawing::Point(8, 41);
this->rbSorted->Name = L"rbSorted";
this->rbSorted->Size = System::Drawing::Size(133, 20);
this->rbSorted->TabIndex = 1;
this->rbSorted->Text = L"Упорядоченные";
this->rbSorted->UseVisualStyleBackColor = true;
//
// rbRandom
//
this->rbRandom->AutoSize = true;
this->rbRandom->Checked = true;
this->rbRandom->Location = System::Drawing::Point(8, 21);
this->rbRandom->Name = L"rbRandom";
this->rbRandom->Size = System::Drawing::Size(102, 20);
this->rbRandom->TabIndex = 0;
this->rbRandom->TabStop = true;
this->rbRandom->Text = L"Случайные";
this->rbRandom->UseVisualStyleBackColor = true;
//
// Chart
//
this->Chart->Location = System::Drawing::Point(242, 24);
this->Chart->Name = L"Chart";
this->Chart->Size = System::Drawing::Size(804, 313);
this->Chart->TabIndex = 3;
this->Chart->Text = L"Графики времени";
//
// groupBox3
//
this->groupBox3->Controls->Add(this->cbNums);
this->groupBox3->Location = System::Drawing::Point(11, 288);
this->groupBox3->Name = L"groupBox3";
this->groupBox3->Size = System::Drawing::Size(224, 177);
this->groupBox3->TabIndex = 4;
this->groupBox3->TabStop = false;
this->groupBox3->Text = L" Число элементов ";
//
// cbNums
//
this->cbNums->FormattingEnabled = true;
this->cbNums->Items->AddRange(gcnew cli::array< System::Object^ >(7) {
L"500", L"1000", L"5000", L"10000", L"30000", L"40000",
L"50000"
});
this->cbNums->Location = System::Drawing::Point(8, 22);
this->cbNums->Name = L"cbNums";
this->cbNums->Size = System::Drawing::Size(210, 140);
this->cbNums->TabIndex = 0;
//
// Grid
//
this->Grid->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;
this->Grid->Location = System::Drawing::Point(242, 344);
this->Grid->Name = L"Grid";
this->Grid->RowHeadersWidth = 51;
this->Grid->RowTemplate->Height = 24;
this->Grid->Size = System::Drawing::Size(804, 150);
this->Grid->TabIndex = 5;
//
// MyForm
//
this->AutoScaleDimensions = System::Drawing::SizeF(8, 16);
this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
this->ClientSize = System::Drawing::Size(1058, 507);
this->Controls->Add(this->Grid);
this->Controls->Add(this->groupBox3);
this->Controls->Add(this->Chart);
this->Controls->Add(this->groupBox2);
this->Controls->Add(this->groupBox1);
this->Controls->Add(this->btStart);
this->FormBorderStyle = System::Windows::Forms::FormBorderStyle::FixedSingle;
this->MaximizeBox = false;
this->Name = L"MyForm";
this->StartPosition = System::Windows::Forms::FormStartPosition::CenterScreen;
this->Text = L"Внешние сортировки";
this->groupBox1->ResumeLayout(false);
this->groupBox2->ResumeLayout(false);
this->groupBox2->PerformLayout();
(cli::safe_cast(this->nmPercent))->EndInit();
(cli::safe_cast(this->Chart))->EndInit();
this->groupBox3->ResumeLayout(false);
(cli::safe_cast(this->Grid))->EndInit();
this->ResumeLayout(false);

}
#pragma endregion
// Вызывается при нажатии кнопки запуска
private: System::Void btStart_Click(System::Object^ sender, System::EventArgs^ e) {
// Считаем количество методов
int nMethods = 0;
for (int i = 0; i < cbMethods->Items->Count; i++) {
if (cbMethods->GetItemChecked(i))
nMethods++;
}
// Считаем количество градаций размера
int nNums = 0;
for (int i = 0; i < cbNums->Items->Count; i++) {
if (cbNums->GetItemChecked(i))
nNums++;
}
// Настраиваем таблицу с результатами
if (nMethods == 0) { // Если не заданы методы
MessageBox::Show("Не выбрано ни одного метода");
return; // то выходим
}
if (nNums == 0) { // Если не заданы количества
MessageBox::Show("Не выбрано ни одного количества элементов данных");
return; // то выходим
}
Grid->Rows->Clear();
if (nMethods == 0)
nMethods = 1;
if (nNums == 0)
nNums = 1;
// Настраиваем график
Grid->RowCount = nMethods;
Grid->ColumnCount = nNums;
Chart->Series->Clear();
Chart->ChartAreas->Clear();
Chart->ChartAreas->Add("Main");
Chart->Legends->Clear();
Chart->Legends->Add("MainLegend");
for (int i = 0; i < cbMethods->Items->Count; i++) {
if (cbMethods->GetItemChecked(i)) {
Chart->Series->Add(cbMethods->Items[i]->ToString());
Chart->Series[Chart->Series->Count - 1]->ChartType = System::Windows::Forms::DataVisualization::Charting::SeriesChartType::Line;
}
}
// Цикл по количествам элементов
int column = 0;
for (int i = 0; i < cbNums->Items->Count; i++)
if (cbNums->GetItemChecked(i)) {
int N = Convert::ToInt32(cbNums->Items[i]); // Число элементов
FileStream^ SRC = gcnew FileStream("src.dat", FileMode::Create); // Исходная последовательность
Random^ rnd = gcnew Random();
if (rbPartialSorted->Checked) { // Частичная упорядоченность
// Длина каждого упорядоченного участка
int part_length = 1 + (N - 1) * Convert::ToInt32(nmPercent->Value) / 100;
int count = 0;
while (count < N) {
unsigned char val = 0;
SRC->WriteByte(val);
count++;
int rest = part_length - 1;
// Создаем прочие элементы упорядоченного участка
while (rest > 0 && count < N) {
val = (part_length - rest) * 255 / part_length;
SRC->WriteByte(val);
rest--;
count++;
}
}
}
else { // Прочие виды набора данных
for (int i = 0; i < N; i++) {
unsigned char val =
rbSorted->Checked ? i*255/N :
(rbRevSorted->Checked ? (N - i)*255/N :
rnd->Next(256));
SRC->WriteByte(val);
}
}
SRC->Close();
Grid->Columns[column]->HeaderText = cbNums->Items[i]->ToString();
int row = 0;
// Цикл по методам
for (int j = 0; j < cbMethods->Items->Count; j++) {
if (cbMethods->GetItemChecked(j)) {
File::Copy("src.dat", "processing.dat", true);
DateTime^ dt = DateTime::Now; // ЗАсечка времени
// Сортировка j-м методом
switch (j) {
case 0:
simple_merge_sort("processing.dat");
break;
case 1:
nature_merge_sort("processing.dat");
break;
case 2:
eating_sort("processing.dat");
break;
}
// Считаем затраченное время
DateTime^ dt2 = DateTime::Now; // ЗАсечка времени
int time = Convert::ToInt32((dt2->Subtract(*dt)).Milliseconds);
// Заносим время в таблицу
Grid->Rows[row]->Cells[column]->Value = time;
Grid->Rows[row]->HeaderCell->Value = cbMethods->Items[j]->ToString();
// Отмечаем время на графике
Chart->Series[row]->Points->AddXY(N, time);
row++;
}
}
column++;
}
Grid->RowHeadersWidth = Grid->Width / 3;
}
};
}








5

1. И.А. Казакова, С.В. Самуйлов «Структуры данных. Учебное пособие» Пенза, Издательство ПГУ, 2011 г. (дата обращения: 6.10.2023)
2. C# documentation [электронный ресурс] URL: https://learn.microsoft.com/ en-us/dotnet/csharp/ (дата обращения: 7.10.2023)
3. Рутковская, Д., Пилиньский, М., Рутковский, Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия – Телеком, 2013.
4. Методология разработки RAD [электронный ресурс] https://gb.ru/posts/rad_methodology (дата обращения: 8.10.2023)
5. Функциональное тестирование [электронный ресурс] https://sky.pro/media/kak-provodit-funkczionalnoe-testirovanie/ (дата обращения 18.10.2023)
6. Системное тестирование [электронный ресурс] https://www.zaptest.com/ru/что-такое-системное-тестирование-глу (дата обращения 18.10.2023)
7. Тестирование производительности [электронный ресурс] https://sky.pro/media/chto-takoe-testirovanie-proizvoditelnosti/ (дата обращение 18.10.2023)