|
Читайте также: |
При выборе режима счета необходимо ввести длину последовательности, также, как в режиме отладки (число должно быть не менее 1 и не более 100).
После ввода систему сгенерирует 4 последовательности указанной длины: первая содержит уже отсортированные по неубыванию элементы, вторая — упорядоченные в обратном порядке (по невозрастанию) и две сгенерированы с помощью генератора псевдослучайных чисел. Результаты сортировки (количество сравнений и обменов) будут выведены в виде таблицы.
Далее можно нажать Enter для ввода длины новых последовательностей и добавления результатов в таблицу либо Esc для возврата в предыдущее меню.
Текст программы на языке Borland С++ 3.1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <time.h>
const int NORM_TEXT_ATTR = 23;
const int SELECTED_TEXT_ATTR = 112;
const short MENU_CENTER_X = 25;
const short FIRST_MENU_Y = 10;
const int CENTER_DATE_X = 35;
// globalnie (kak trebuetsia v metodichke) schetchiki sravnenii i obmenov
int comparisons;
int swaps;
// structura Data
struct Date
{
int day;
int month;
int year;
Date(int d = 1, int m = 1, int y = 1): day(d), month(m), year(y)
{ }
};
// element odnonapravlenogo sviaznogo spiska
struct ListItem
{
Date date;
ListItem* next; // ukazatel na sled. element
ListItem(const Date* _date = NULL, ListItem* _next = NULL): date(*_date), next(_next)
{ }
};
// vstavka elementa v konec spiska
void InsertToList(ListItem *&head, const Date &val)
{
if(head == NULL)
head = new ListItem(&val);
else
{
ListItem* temp = head;
while(temp->next!= NULL)
temp = temp->next;
temp->next = new ListItem(&val);
}
}
// poluchenie znachenija elementa spiska po nomeru (neobhodimo dlia Bistroi Nerekursiv sortirovki)
Date GetItem(ListItem *head, int number)
{
ListItem* tempItem = head;
while(tempItem && number!= 0)
{
tempItem = tempItem->next;
number--;
}
return tempItem->date;
}
// obmen znachenii 2 elementov spiska
void ListSwapElements(ListItem *head, int i,int j)
{
// schetchik peremeshenii
swaps++;
ListItem *t1 = head;
ListItem *t2 = head;
// ishem pervii element
while(i!= 0)
{
t1 = t1->next;
i--;
}
// ishem vtoroi element
while(j!= 0)
{
t2 = t2->next;
j--;
}
// obmen znachenii
Date temp = t1->date;
t1->date = t2->date;
t2->date = temp;
}
// obmen znachenii 2 elementov massiva
void ArrSwapElement(Date *arr, int i, int j)
{
// schetchik peremeshenii
swaps++;
Date temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// funcija sravnenija dat
// Vozvrashaet:
// -1 - esli d1 < d2
// 0 - esli d1 == d2
// 1 - esli d1 > d2
int DateCompare(Date d1, Date d2)
{
// schetchik sravnenii
comparisons++;
if (d1.year < d2.year)
return -1;
else if (d1.year == d2.year && d1.month < d2.month)
return -1;
else if (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day)
return -1;
else if (d1.year == d2.year && d1.month == d2.month && d1.day == d2.day)
return 0;
else
return 1;
}
// funkcija bistroi nerekursivnoi sortirovki spiska
void quickSort(ListItem* lst, int n)
{
long i, j;
long lb, ub; // granici otsortirovonogo fragmenta
const int MAXSTACK = 100;
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // stack "zaprosov"
// zapros zadaetsia paroi znachenii:
// levoi (lbstack) i pravoi (ubstack) granicami
long stackpos = 1; // tekushaja pozicija stacka
long ppos; // seredina masiva
Date pivot; // opornii element
Date temp;
lbstack[1] = 0;
ubstack[1] = n - 1;
do
{
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
do
{
ppos = (lb + ub) / 2;
i = lb;
j = ub;
pivot = GetItem(lst, ppos);
do
{
while (DateCompare(GetItem(lst, i), pivot) == -1)
i++;
while (DateCompare(pivot, GetItem(lst, j)) == -1)
j--;
if (i <= j)
{
ListSwapElements(lst, i, j);
i++;
j--;
}
} while (i <= j);
if (i < ppos)
{
if (i < ub)
{
stackpos++;
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j;
}
else
{
if (j > lb) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while (lb < ub);
} while (stackpos!= 0);
}
// funkcija puzirkovoi sortirovki massiva
void BubbleSort(Date* arr, int n)
{
for (int i = n - 1; i > 0; i--)
for (int j = 0; j < i; j++)
if (DateCompare(arr[j], arr[j + 1]) == 1)
ArrSwapElement(arr, j, j + 1);
}
// skrivat' kursor
void HideCursor()
{
_setcursortype(_NOCURSOR);
}
// pokazivat kursor
void ShowCursor()
{
_setcursortype(_NORMALCURSOR);
}
// vvod dlini posledovatelnosti
int InputLength()
{
ShowCursor();
const char* textStr = "DLINA POSLEDOVATELNOSTI: ";
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(1, 1);
cprintf("%s", "Vvod dlini posledovatelnosti");
gotoxy(1, 2);
cprintf("%s", "Esc - vozvrat v menu, strelki vlevo/vpravo - kursor, Del i Backspace - udalenie, Enter - konec vvoda");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y);
cprintf("%s", textStr);
const int INPUT_START_X = MENU_CENTER_X + strlen(textStr);
const int CELLS_COUNT = 3;
char digits[CELLS_COUNT + 1] = { 0 };
int currCell = 0;
int key = 0;
do
{
gotoxy(INPUT_START_X, FIRST_MENU_Y);
for(int j = 0; j < CELLS_COUNT; j++)
{
if (digits[j]!= 0)
cprintf("%c", digits[j]);
else
cprintf(" ");
}
gotoxy(INPUT_START_X + currCell, FIRST_MENU_Y);
key = getch();
// klavishi strelok vozvrashaiut snachalo 0 (ili 224 na num chasti klaviaturi),
// a zatem 72 (vverh), 80 (vniz), 75 (vlevo) ili 77 (vpravo)
if (key == 0 || key == 224)
key = getch();
switch(key)
{
case 75: // strelka vlevo
{
if (currCell > 0)
currCell--;
}
break;
case 77: // strelka vpravo
{
if (currCell < CELLS_COUNT)
currCell++;
}
break;
case 83: // del
{
int i;
for(i = currCell; i < CELLS_COUNT; i++)
{
digits[i] = digits[i + 1];
}
digits[i] = 0;
}
break;
case 8: // backspace
{
if (currCell > 0)
{
currCell--;
digits[currCell] = 0;
}
}
break;
default:
{
if (currCell < CELLS_COUNT)
{
digits[currCell] = key;
currCell++;
}
}
break;
}
} while ((key!= 13) && (key!= 27));
HideCursor();
if (key == 13)
{
return atoi(digits);
}
else
return -1;
}
// vvod posledovatelnosti iz n dat. Vozvrashaet ukazatel na massiv
// ili NULL esli polzovatel' vibral vihod (najal Esc)
Date* InputDateArr(int n)
{
ShowCursor();
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(1, 1);
cprintf("Vvod %d elementov posledovatelnosti (dat DD.MM.YY)", n);
gotoxy(1, 2);
cprintf("%s", "Esc - vozvrat v menu, strelki vlevo/vpravo - kursor, Del i Backspace - udalenie, Enter - konec vvoda");
int const FIRST_INPUT_ROW_Y = 8;
Date* dateArr = new Date[n];
int const CELLS_PER_ROW = 6;
int currRow = 0;
int currCell = 0;
char** digits = new char*[n];
for(int i = 0; i < n; i++)
{
digits[i] = new char[CELLS_PER_ROW + 1];
memset(digits[i], 0, CELLS_PER_ROW + 1);
}
int key = 0;
int isAllDatesCorrect = 0;
do
{
do
{
gotoxy(15, 5);
cprintf("%d row %d cell", currRow, currCell);
for (int i = 0; i < n; i++)
{
gotoxy(CENTER_DATE_X, FIRST_INPUT_ROW_Y + i);
for (int j = 0; j < CELLS_PER_ROW; j++)
{
cprintf("%c", digits[i][j] == 0? ' ': digits[i][j]);
if (j == 1 || j == 3)
cprintf(".");
}
}
gotoxy(CENTER_DATE_X + currCell + (currCell > 3? 2: (currCell > 1? 1: 0)), FIRST_INPUT_ROW_Y + currRow);
key = getch();
// klavishi strelok vozvrashaiut snachalo 0 (ili 224 na num chasti klaviaturi),
// a zatem 72 (vverh), 80 (vniz), 75 (vlevo) ili 77 (vpravo)
if (key == 0 || key == 224)
key = getch();
switch(key)
{
case 27:
{
return NULL;
}
case 75: // strelka vlevo
{
currCell--;
if (currCell < 0)
{
if (currRow == 0)
currCell = 0;
else
{
currCell = CELLS_PER_ROW - 1;
currRow--;
}
}
}
break;
case 77: // strelka vpravo
{
currCell++;
if (currCell > CELLS_PER_ROW - 1)
{
if (currRow < n - 1)
{
currRow++;
currCell = 0;
}
else
currCell = CELLS_PER_ROW;
}
}
break;
case 72: // strelka vverh
{
if (currRow > 0)
currRow--;
}
break;
case 80: // strelka vniz
{
if (currRow < n - 1)
currRow++;
}
break;
case 83: // del
{
}
break;
case 8: // backspace
{
if (!(currCell == 0 && currRow == 0))
{
currCell--;
if (currCell < 0)
{
currRow--;
currCell = CELLS_PER_ROW - 1;
}
digits[currRow][currCell] = 0;
}
}
break;
default:
{
if (key >= '0' && key <= '9')
{
if (currCell < CELLS_PER_ROW)
{
digits[currRow][currCell] = key;
currCell++;
if (currCell > CELLS_PER_ROW - 1)
{
if (currRow < n - 1)
{
currRow++;
currCell = 0;
}
else
currCell = CELLS_PER_ROW;
}
}
}
}
}
} while (key!= 13);
gotoxy(MENU_CENTER_X, FIRST_INPUT_ROW_Y - 2);
isAllDatesCorrect = 1;
const int CELLS_PER_NUMBER = CELLS_PER_ROW / 3;
char numStrings[3][CELLS_PER_NUMBER + 1];
for (int i = 0; i < n && isAllDatesCorrect == 1; i++)
{
memset(numStrings, 0, sizeof(char) * 3 * (CELLS_PER_NUMBER + 1));
for(int ii = 0; ii < 3; ii++)
for(int j = 0; j < CELLS_PER_NUMBER; j++)
numStrings[ii][j] = digits[i][ii * 2 + j];
dateArr[i].day = atoi(numStrings[0]);
dateArr[i].month = atoi(numStrings[1]);
dateArr[i].year = atoi(numStrings[2]);
if (dateArr[i].day == 0)
{
isAllDatesCorrect = 0;
cprintf("Data #%d, vi ne vveli chislo ", i + 1);
currCell = 0;
currRow = i;
}
else if (dateArr[i].month == 0)
{
isAllDatesCorrect = 0;
cprintf("Data #%d, vi ne vveli mesiac ", i + 1);
currCell = 2;
currRow = i;
}
else if (dateArr[i].year == 0)
{
isAllDatesCorrect = 0;
cprintf("Data #%d, vi ne vveli god ", i + 1);
currCell = 4;
currRow = i;
}
// nebolshaia proverka dati
else if (dateArr[i].day < 1 || dateArr[i].day > 31)
{
isAllDatesCorrect = 0;
cprintf("Data #%d, nekorrektnoe chislo ", i + 1);
currCell = 0;
currRow = i;
}
else if (dateArr[i].month < 1 || dateArr[i].month > 12)
{
isAllDatesCorrect = 0;
cprintf("Data #%d, nekorrektnii mesiac ", i + 1);
currCell = 2;
currRow = i;
}
else if (dateArr[i].year < 1 || dateArr[i].year > 99)
{
isAllDatesCorrect = 0;
cprintf("Data #%d, nekorrektnii god ", i + 1);
currCell = 4;
currRow = 0;
}
}
} while (isAllDatesCorrect == 0);
HideCursor();
return dateArr;
}
// rejim otladki
void DebugMode(int punkt)
{
int n;
do
{
n = InputLength();
if (n == -1)
return;
if (n < 1 || n > 15)
{
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(MENU_CENTER_X, FIRST_MENU_Y);
cprintf("%s", "Nekorrektnoe chislo. Doljno bit ot 1 do 15");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 2);
cprintf("%s", "Najmite liubuju klavishu dlia povtornogo vvoda");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 3);
cprintf("%s", "ili Esc dlia vozvrata v menu");
if (getch() == 27)
return;
}
} while (n < 1);
Date* inputArr = InputDateArr(n);
if (inputArr == NULL)
return;
clrscr();
const int FIRST_OUTPUT_ROW_Y = 4;
comparisons = 0;
swaps = 0;
// massiv, puzirkovaja
if (punkt == 0)
{
gotoxy(MENU_CENTER_X, FIRST_OUTPUT_ROW_Y - 2);
cprintf("Puzirkovaia sortirovka");
BubbleSort(inputArr, n);
for (int i = 0; i < n; i++)
{
gotoxy(CENTER_DATE_X, FIRST_OUTPUT_ROW_Y + i);
cprintf("%d.%d.%d", inputArr[i].day, inputArr[i].month, inputArr[i].year);
}
}
// spisok, bistraya nerekursivnaia
else if (punkt == 1)
{
gotoxy(MENU_CENTER_X, FIRST_OUTPUT_ROW_Y - 1);
cprintf("Bistraya nerekursivnaia sortirovka");
ListItem *lst = NULL;
for(int i = 0; i < n; i++)
InsertToList(lst, inputArr[i]);
quickSort(lst, n);
int j = 0;
for(ListItem* tmp = lst; tmp!= NULL; tmp = tmp->next, j++)
{
gotoxy(CENTER_DATE_X, FIRST_OUTPUT_ROW_Y + j);
cprintf("%d.%d.%d", tmp->date.day, tmp->date.month, tmp->date.year);
}
}
gotoxy(MENU_CENTER_X, FIRST_OUTPUT_ROW_Y + n + 1);
cprintf("Sravnenii: %d", comparisons);
gotoxy(MENU_CENTER_X, FIRST_OUTPUT_ROW_Y + n + 2);
cprintf("Obmenov: %d", swaps);
gotoxy(MENU_CENTER_X, FIRST_OUTPUT_ROW_Y + n + 4);
cprintf("%s", "Press any key to continue...");
getch();
}
// rejim scheta
void CountMode(int punkt)
{
const int FIRST_TABLE_ROW_Y = 6;
const int TABLE_X = 10;
int key = 13;
int resultsArr[20][9];
int resCount = 0;
do
{
if (key == 13) // Enter
{
int n;
do
{
n = InputLength();
if (n == -1)
return;
if (n < 1 || n > 100)
{
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(MENU_CENTER_X, FIRST_MENU_Y);
cprintf("%s", "Nekorrektnoe chislo. Doljno bit ot 1 do 15");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 2);
cprintf("%s", "Najmite liubuju klavishu dlia povtornogo vvoda");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 3);
cprintf("%s", "ili Esc dlia vozvrata v menu");
if (getch() == 27)
return;
}
} while (n < 1);
resultsArr[resCount][0] = n;
srand (time(NULL));
// massiv, puzirkovaja
if (punkt == 0)
{
Date* arr = new Date[n];
int i;
// uje otsortirovanaia
for (i = 0; i < n; i++)
arr[i] = Date(1, 1, i);
comparisons = 0;
swaps = 0;
BubbleSort(arr, n);
resultsArr[resCount][1] = comparisons;
resultsArr[resCount][5] = swaps;
// v obratnom poriadke
for (i = 0; i < n; i++)
arr[i] = Date(1, 1, 99 - i / 2);
comparisons = 0;
swaps = 0;
BubbleSort(arr, n);
resultsArr[resCount][2] = comparisons;
resultsArr[resCount][6] = swaps;
// dve sluchainie
for (int k = 0; k < 2; k++)
{
for (i = 0; i < n; i++)
arr[i] = Date(1, 1, rand() % 99 + 1);
comparisons = 0;
swaps = 0;
BubbleSort(arr, n);
resultsArr[resCount][3 + k] = comparisons;
resultsArr[resCount][7 + k] = swaps;
}
}
// spisok, bistraya nerekursivnaia
else if (punkt == 1)
{
ListItem *lst = NULL, *tmp;
int i;
// uje otsortirovanaia
for (i = 0; i < n; i++)
InsertToList(lst, Date(1, 1, i));
comparisons = 0;
swaps = 0;
quickSort(lst, n);
resultsArr[resCount][1] = comparisons;
resultsArr[resCount][5] = swaps;
// v obratnom poriadke
for (i = 0, tmp = lst; i < n; i++, tmp = tmp->next)
tmp->date = Date(1, 1, 99 - i / 2);
comparisons = 0;
swaps = 0;
quickSort(lst, n);
resultsArr[resCount][2] = comparisons;
resultsArr[resCount][6] = swaps;
// dve sluchainie
for (int k = 0; k < 2; k++)
{
for (i = 0, tmp = lst; i < n; i++, tmp = tmp->next)
tmp->date = Date(1, 1, rand() % 99 + 1);
comparisons = 0;
swaps = 0;
quickSort(lst, n);
resultsArr[resCount][3 + k] = comparisons;
resultsArr[resCount][7 + k] = swaps;
}
}
resCount++;
}
clrscr();
gotoxy(1, 1);
cprintf("Rejim scheta");
gotoxy(1, 2);
cprintf("Najmite Enter dlia vvoda dlini i dobavlenia rezultatov v tablicu");
gotoxy(1, 3);
cprintf("libo Esc dlia vihoda");
gotoxy(1, 5);
cprintf("%s", punkt == 0? "Puzirkovaia sortirovka": "Bistraia nerekursivnaia sortirovka");
gotoxy(TABLE_X, FIRST_TABLE_ROW_Y);
cprintf("n | parametr | Nomer posledovatelnosti | srednee");
gotoxy(TABLE_X, FIRST_TABLE_ROW_Y + 1);
cprintf(" | 1 | 2 | 3 | 4 |");
for (int i = 0, y = FIRST_TABLE_ROW_Y + 2; i < resCount; i++, y += 2)
{
int j, s;
gotoxy(TABLE_X, y);
cprintf("%-3d| sravnenii |", resultsArr[i][0]);
for(j = 0, s = 0; j < 4; j++)
{
cprintf(" %-5d |", resultsArr[i][1 + j]);
s += resultsArr[i][1 + j];
}
cprintf(" %d", s / 4);
gotoxy(TABLE_X, y + 1);
cprintf(" | obmenov |");
for(j = 0, s = 0; j < 4; j++)
{
cprintf(" %-5d |", resultsArr[i][5 + j]);
s += resultsArr[i][5 + j];
}
cprintf(" %d", s / 4);
}
key = getch();
} while (key!= 27);
}
// vibor rejima
void ChooseMode(int punkt)
{
short otladka = 1;
int key = 0;
do
{
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(1, 1);
cprintf("%s", "Vibor rejima");
gotoxy(1, 2);
cprintf("%s", "Esc - vozvrat v menu, probel - smena rejima, Enter - vibor");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y);
cprintf("%s", "REJIM: ");
textattr(SELECTED_TEXT_ATTR);
cprintf("%s", (otladka == 1? "OTLADKA": "SCHET"));
textattr(NORM_TEXT_ATTR);
key = getch();
switch (key)
{
case 32: // probel
{
otladka = otladka == 1? 0: 1;
}
break;
case 13: // Enter
{
if (otladka) // otladka
{
DebugMode(punkt);
}
else // schet
{
CountMode(punkt);
}
}
break;
}
}
while (key!= 27);
}
// osnovnoe menu
void MainMenu()
{
HideCursor();
const int N = 6;
char strmenu[N][40];
strcpy(strmenu[0], "Metod puzir'ka");
strcpy(strmenu[1], "Bistraya sortirovka, nerekursivnii");
strcpy(strmenu[2], "Shakernaia sortirovka");
strcpy(strmenu[3], "Sortirovka vstavkami");
strcpy(strmenu[4], "Metod Shella");
strcpy(strmenu[5], "Vihod");
int punkt = 0;
int key = 0;
do
{
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(1, 1);
cprintf("%s", "Osnovnoe menu");
gotoxy(1, 2);
cprintf("%s", "Esc - vihod, strelki vverh/vniz i Enter - vibor punkta");
for (int i = 0; i < N; i++)
{
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + i);
cprintf("%s", strmenu[i]);
}
textattr(SELECTED_TEXT_ATTR);
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + punkt);
cprintf("%s", strmenu[punkt]);
textattr(NORM_TEXT_ATTR);
key = getch();
// klavishi strelok vozvrashaiut snachalo 0 (ili 224 na num chasti klaviaturi),
// a zatem 72 (vverh), 80 (vniz), 75 (vlevo) ili 77 (vpravo)
if (key == 0 || key == 224)
key = getch();
switch (key)
{
case 72: // strelka vverh
{
punkt--;
if (punkt < 0)
punkt = N - 1;
}
break;
case 80: // strelka vniz
{
punkt++;
if (punkt == N)
punkt = 0;
}
break;
case 13: // Enter
{
if (punkt < 2) // realizovanie metodi
{
ChooseMode(punkt);
}
else if (punkt == N - 1) // vihod
{
key = 27;
}
else // ostalnie punkti
{
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(MENU_CENTER_X, FIRST_MENU_Y);
cprintf("%s", "Metod ne realizovan.");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 2);
cprintf("%s", "Press any key to continue...");
getch();
}
}
break;
}
} while (key!= 27);
}
void About()
{
textattr(NORM_TEXT_ATTR);
clrscr();
gotoxy(MENU_CENTER_X, FIRST_MENU_Y);
cprintf("Kursovaya rabota po kursu");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 1);
cprintf("\"Programmiirovanie i osnovi algoritmizacii\"");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 2);
cprintf("Variant 8");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 3);
cprintf("Vipolnil Pechenkin Mihail Yurevich");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 4);
cprintf("Ver. 1.0");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 5);
cprintf("16.12.2012");
gotoxy(MENU_CENTER_X, FIRST_MENU_Y + 7);
cprintf("%s", "Press any key to continue...");
getch();
}
int main()
{
About();
MainMenu();
return 0;
}
Дата добавления: 2015-07-12; просмотров: 51 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Режим отладки | | | Назначение |