Лабораторные работы С++
- Задания по лабораторным работам
- Лабораторная работа №1 (одномерные массивы)
- Лабораторная работа №2 (двухмерные массивы)
- Лабораторная работа №3 (работа со строками)
- Лабораторная работа №4 (работа с текстовыми файлами)
- Лабораторная работа №5 (записи, знакомство со структурами данных)
- Лабораторная работа №6 (WinApi работа с массивами)
- Лабораторная работа №7 (динамические массивы)
- Лабораторная работа №8 (односвязанный список)
- Лабораторная работа №9 (двухсвязанный список)
- Лабораторная работа №10 (дерево поиска или двоичное дерево)
- Лабораторная работа №11 (ХЭШ)
- Лабораторная работа №12 (WinApi графика)
- Лабораторная работа №13 (оценка сложности алгоритмов)
Лабораторная работа №1 (одномерные массивы)
// lab1vB.cpp: определяет точку входа для консольного приложения.
//
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include "stdafx.h"
//Вариант B7
//После последнего нечетного элемента вставить 0.
//Пример: из массива A[5]: 1 3 8 3 5 должен получиться
//массив A[6]: 1 3 8 3 5 0.
int generate(int min, int max) {
return (double)rand() / (RAND_MAX + 1) * (max - min) + min;
}
class Task {
public:
int *a;
int sizeA;
Task(int size) {
sizeA = size;
a = new int[sizeA];
}
virtual ~Task() {
delete a;
}
void generateArray() {
for (int i = 0; i < sizeA; i++ ) {
a[i] = generate(0, 20);
}
}
void insertZiroByIndex(int index) {
int *newA = new int[sizeA + 1];
for (int i = 0; i <= index; i++ ) {
newA[i] = a[i];
}
newA[index + 1] = 0;
for (int i = index + 2; i < sizeA + 1; i++ ) {
newA[i] = a[i - 1];
}
delete a;
a = newA;
sizeA++;
}
void process() {
for (int i = sizeA; i >= 0; i--) {
if (a[i] % 2 == 1) {
insertZiroByIndex(i);
break;
}
}
}
void printArrayaA(char *message) {
printf("%s", message);
for (int i = 0; i < sizeA; i++ ) {
printf("%d ", a[i]);
}
printf("\n");
}
};
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(NULL));
Task t(5);
t.generateArray();
t.printArrayaA("before process: ");
t.process();
t.printArrayaA("after process: ");
_getch();
return 0;
}
Лабораторная работа №2 (двухмерные массивы)
// lab2v7C.cpp: определяет точку входа для консольного приложения.
//
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include "stdafx.h"
using namespace std;
//Вариант C7:
//Удалить те столбцы, максимальный элемент которых стоит на главной диагонали.
int generate(int min, int max) {
return (double)rand() / (RAND_MAX + 1) * (max - min) + min;
}
class Task {
public:
int **data;
int heightData;
int widthData;
Task(int height) {
heightData = height;
widthData = heightData;
data = new int *[heightData];
for (int i = 0; i < heightData; i++) {
data[i] = new int[heightData];
}
}
virtual ~Task() {
for (int i = 0; i < heightData; i++) {
delete data[i];
}
delete data;
}
void generateArray() {
for (int i = 0; i < heightData; i++ ) {
for (int j = 0; j < heightData; j++ ) {
data[i][j] = generate(10, 99);
}
}
}
int findMaxColumn(int indexColumn) {
int max = data[0][indexColumn];
for (int j = 1; j < heightData; j++) {
if (data[j][indexColumn] > max) {
max = data[j][indexColumn];
}
}
return max;
}
void delByIndex(int delIndex, int indexString) {
int *newData = new int[heightData - 1];
for (int i = 0; i < delIndex; i++) {
newData[i] = data[indexString][i];
}
for (int i = delIndex + 1; i < heightData; i++){
newData[i - 1] = data[indexString][i];
}
delete data[indexString];
data[indexString] = newData;
}
void deleteColumn(int delIndex) {
for (int i = 0; i < heightData; i++) {
delByIndex(delIndex, i);
}
heightData--;
}
void processArray() {
for (int i = widthData - 1; i >= 0; i--) {
if (data[i][i] == findMaxColumn(i)) {
deleteColumn(i);
}
}
}
void printArray() {
for (int i = 0; i < widthData; i++) {
for (int j = 0; j < heightData; j++) {
printf("%d ", data[i][j]);
}
printf("\n");
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(NULL));
int size;
cout << "input array size: ";
cin >> size;
Task t(size);
t.generateArray();
cout << "\nbefore process: \n";
t.printArray();
t.processArray();
cout << "\nafter process: \n";
t.printArray();
_getch();
return 0;
}
Лабораторная работа №3 (работа со строками)
// lab3v7C.cpp: определяет точку входа для консольного приложения.
//
//Вариант C7
//Удалить из всего текста самое короткое слово.
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "stdafx.h"
using namespace std;
class Task {
public:
Task() {
}
virtual ~Task() {
}
int strLen(char *&str) {
int res = 0;
for (; *str != 0; str++) {
res++;
}
return res;
}
void addCharToEnd(char *&str, char z) {
int len = strlen(str);
char *newStr = new char[len + 2];
strcpy(newStr, str);
newStr[len] = z;
newStr[len + 1] = 0;
delete str;
str = newStr;
}
void delLastChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, str, (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void inputString(char *&z) {
z = new char[1];
z[0] = 0;
while (true) {
char c = _getch();
if ((c == '\n') || (c == '\r')) {
break;
}
if ((c == '\b') && (z[0] != 0)) {
printf("\b ");
delLastChar(z);
} else {
addCharToEnd(z, c);
}
printf("%c", c);
}
}
bool isSeparator(char c) {
return (strchr(" .,\\\"!&", c) != NULL);
}
int findWordLength(char *str) {
int res = 0;
for (; *str != 0; str++) {
if (isSeparator(*str)) {
return res;
}
res++;
}
return res;
}
int findMinLen(char *&str) {
int min = strlen(str);
for (int i = 0; i < strlen(str); i++) {
if (strchr(" .,\\\"!&", str[i]) != NULL) {
continue;
}
int len = findWordLength(&str[i]);
if (len < min) {
min = len;
}
i += len;
}
return min;
}
void processStr(char *&str) {
int min = findMinLen(str);
for (int i = 0; i < strlen(str); i++) {
if (strchr(" .,\\\"!&", str[i]) != NULL) {
continue;
}
int len = findWordLength(&str[i]);
if (len == min) {
int newSize = strlen(str) - len + 1;
char *newStr = new char[newSize];
memmove(newStr, str, i * sizeof(char));
memmove(&newStr[i], &str[i + len], (strlen(str) - i - len) * sizeof(char));
newStr[newSize - 1] = 0;
delete str;
str = newStr;
break;
} else {
i += len;
}
}
}
};
int _tmain(int argc, _TCHAR* argv[]) {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
srand(time(NULL));
char *str;
Task t;
t.inputString(str);
printf("\ninput string : %s", str);
t.processStr(str);
printf("\nout string : %s", str);
delete str;
_getch();
return 0;
}
Лабораторная работа №4 (работа с текстовыми файлами)
// lab4C7.cpp: определяет точку входа для консольного приложения.
//
//Вариант C7
//Выделить угловыми скобками все слова, длина которых меньше
//половины длины самого длинного слова предпоследней строки.
//В выделенных словах все буквы слова, за исключением первой
//и последней, перевести в большие.
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "stdafx.h"
using namespace std;
class ProcessString {
public:
char *sepatator;
ProcessString() {
sepatator = " .,\\\"!&";
}
virtual ~ProcessString() {
}
void addCharToEnd(char *&str, char z) {
int len = strlen(str);
char *newStr = new char[len + 2];
strcpy(newStr, str);
newStr[len] = z;
newStr[len + 1] = 0;
delete str;
str = newStr;
}
void inputString(char *&z, FILE *&fin) {
z = new char[1];
z[0] = 0;
if (fin == NULL) {
return;
}
while (true) {
char c = fgetc(fin);
if (feof(fin)) {
break;
}
if ((c == '\n') || (c == '\r')) {
break;
}
addCharToEnd(z, c);
}
}
bool isSeparator(char c) {
return (strchr(sepatator, c) != NULL);
}
int findWordLength(char *str) {
int res = 0;
for (; *str != 0; str++) {
if (isSeparator(*str)) {
return res;
}
res++;
}
return res;
}
int findMaxLen(char *str) {
int max = 0;
int strLen = strlen(str);
for (int i = 0; i < strLen; i++) {
if (strchr(sepatator, str[i]) == NULL) {
int len = findWordLength(&str[i]);
if (len > max) {
max = len;
}
i += len;
}
}
return max;
}
bool isLower(char c) {
return (strchr("qwetyuiopasdfghjklzxcvbnm", c) != NULL);
}
void processStr(char *&str, int max) {
for (int i = 0; i < strlen(str); i++) {
if (strchr(sepatator, str[i]) != NULL) {
continue;
}
int len = findWordLength(&str[i]);
if (len < (max / 2)) {
char *word = new char[len + 3];
word[0] = '<';
memmove(&word[1], &str[i], len * sizeof(char));
word[len + 1] = '>';
word[len + 2] = 0;
for (int j = 2; j < len; j++) {
if (isLower(word[j])) {
word[j] = word[j] - 'a' + 'A';
}
}
int newSize = strlen(str) + 3;
char *newStr = new char[newSize];
memmove(newStr, str, i * sizeof(char));
memmove(&newStr[i], word, (strlen(word)) * sizeof(char));
memmove(&newStr[i + strlen(word)], &str[i + len],
(strlen(str) - i - len) * sizeof(char));
delete word;
newStr[newSize - 1] = 0;
delete str;
str = newStr;
i += len + 2;
} else {
i += len;
}
}
}
};
class ProcessFile {
public:
char **arrayStrings;
ProcessFile() {
str = new ProcessString;
}
virtual ~ProcessFile() {
delete str;
}
FILE *fin;
ProcessString *str;
int countStrings() {
fin = fopen("D:\\temp.txt", "rt");
if (fin == NULL) {
return 0;
}
int res = 0;
while (true) {
if (feof(fin)) {
break;
}
char *string;
str->inputString(string, fin);
res++;
delete string;
}
fclose(fin);
return res;
}
void inputArrayStrings() {
int countStr = countStrings();
arrayStrings = new char *[countStr];
fin = fopen("D:\\temp.txt", "rt");
for (int i = 0; i < countStr; i++) {
if (fin == NULL) {
return;
}
char *string;
str->inputString(string, fin);
int strLen = strlen(string) + 1;
arrayStrings[i] = new char[strLen];
memmove(&arrayStrings[i][0], string, (strLen - 1) * sizeof(char));
arrayStrings[i][strLen - 1] = 0;
printf("%s\n", arrayStrings[i]);
delete string;
}
fclose(fin);
}
void deleteMemory() {
for (int i = 0; i < countStrings(); i++) {
delete arrayStrings[i];
}
delete arrayStrings;
}
void processFile() {
if (countStrings() < 2) {
printf("count strings < 2");
return;
}
printf("before process:\n");
inputArrayStrings();
printf("\nafter process:\n");
int max = str->findMaxLen(arrayStrings[countStrings() - 2]);
deleteMemory();
printf("max len word: %d\n", max);
fin = fopen("D:\\temp.txt", "rt");
if (fin == NULL) {
return;
}
FILE *fout = fopen("D:\\out.txt", "wt");
if (fout == NULL) {
fclose(fin);
return;
}
while (true) {
char *string;
str->inputString(string, fin);
str->processStr(string, max);
fprintf(fout, "%s", string);
printf("%s\n", string);
delete string;
if (feof(fin)) {
break;
}
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
}
};
int _tmain(int argc, _TCHAR* argv[]) {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
ProcessFile *file = new ProcessFile;
file->processFile();
_getch();
delete file;
return 0;
}
Лабораторная работа №7 (динамические массивы)
Скачать проект лабораторной работы №7
// lab7v7.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include "stdafx.h"
#include "Input.cpp"
using namespace std;
//7. Ввести массив А. В массив В перенести все элементы массива А,
// стоящие правее максимального элемента,
// и имеющие нечетный индекс. Массив В отсортировать по возрастанию,
// используя метод шейкер-сортировки.
int findMaxIndex(const int* data, const int len) {
int maxIndex = 0;
for (int i = 1; i < len; i++) {
if (data[i] > data[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
void delByIndex(int* &src, int index, int &len) {
int* tempSrc = new int[len - 1];
memmove(tempSrc, src, index * sizeof(int));
memmove(&tempSrc[index], &src[index + 1], (len - index - 1) * sizeof(int));
delete src;
src = tempSrc;
len--;
}
void ShakerSort(int* data, int len) {
int last = len - 1;
int left = 1;
int right = len - 1;
do {
for (int j = right; j > 0; j--) {
if (data[j - 1] > data[j]) {
int temp = data[j - 1];
data[j - 1] = data[j];
data[j] = temp;
last = j;
}
}
left = last + 1;
for (int j = 1; j <= right; j++) {
if (data[j - 1] > data[j]) {
int temp = data[j - 1];
data[j - 1] = data[j];
data[j] = temp;
last = j;
}
}
right = last - 1;
} while (left < right);
}
void moveOddIndex(int* &src,int &len1, int *&dst, int &len2) {
int maxIndex = findMaxIndex(src, len1);
printf("max index: %d", maxIndex);
maxIndex += 1 + (maxIndex % 2);
int count = (len1 - maxIndex)/2;
int* tempDst = new int[len2 + count + 1];
memmove(tempDst, dst, len2 * sizeof(int));
for (int i = maxIndex; i < len1; i += 2) {
tempDst[len2++] = src[i];
delByIndex(src, i--, len1);
}
delete dst;
dst = tempDst;
}
int _tmain(/*int argc, _TCHAR* argv[]*/)
{
cout << "Enter size of array:\n";
int lenA = Input::getInt();
int lenB = 0;
int* A = new int[lenA];
int* B = new int[lenB];
for (int i = 0; i < lenA; i++) {
cout << "Enter " << i << "th element: ";
A[i] = Input::getInt();
}
moveOddIndex(A, lenA, B, lenB);
ShakerSort(B, lenB);
cout << "\n\nSource array:\n";
for (int i = 0; i < lenA; i++) {
cout << A[i] << ' ';
}
cout << "\nDestination array:\n";
for (int i = 0; i < lenB; i++) {
cout << B[i] << ' ';
}
cout << endl;
delete A;
delete B;
_gettch();
return 0;
}
// файл input.cpp
#include
#include
class Input {
public:
static int getInt() {
char *s = new char[1];
bool flag = true;
while (flag) {
flag = false;
inputString(s);
flag = !testValue(s);
(testValue(s) == false) ? printf(" error!\n") : printf("\n");
}
int res = atoi(s);
delete s;
return res;
}
static void inputString(char *&z) {
z = new char[1];
z[0] = 0;
while (true) {
char c = _getch();
if ((c == '\n') || (c == '\r')) {
break;
}
if ((c == '\b') && (z[0] != 0)) {
printf("\b ");
delLastChar(z);
} else {
addCharToEnd(z, c);
}
printf("%c", c);
}
}
static bool testValue(char *&str) {
while ((str[0] == '0') || (str[0] == '+')) {
if ((str[0] == '0') && (strlen(str) == 1))
break;
delFirstChar(str);
}
int len = strlen(str);
if ((len == 0) || (len > 10)) {
return false;
}
for (int i = 0; i < len; i++) {
/*if (strchr("1234567890", str[i]) == NULL) {
return false;
}*/
if ((str[i] < '0') || (str[i] > '9'))
return false;
}
return true;
}
private:
static void addCharToEnd(char *&str, char z) {
int len = strlen(str);
char *newStr = new char[len + 2];
strcpy(newStr, str);
newStr[len] = z;
newStr[len + 1] = 0;
delete str;
str = newStr;
}
static void delLastChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, str, (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
static void delFirstChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, &str[1], (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
};
Лабораторная работа №8 (односвязанный список)
// lab8v7.cpp: определяет точку входа для консольного приложения.
//
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include "stdafx.h"
//7. Из списка удалить первый из четных элементов.
using namespace std;
class TNode {
public:
int data;
TNode *next;
TNode(int _data, TNode *_next) {
data = _data;
next = _next;
}
};
class List {
public:
TNode *head;
List() {
head = NULL;
}
~List() {
while (head != NULL) {
TNode *temp = head;
head = head->next;
delete temp;
}
}
void addInt(int value) {
if (head == NULL) {
head = new TNode(value, NULL);
return;
}
TNode *temp = head;
for (; temp->next != NULL; temp = temp->next);
temp->next = new TNode(value, NULL);
}
void delFirsEvenValue() {
if (head == NULL) {
return;
}
if (head->data % 2 == 0) {
TNode *temp = head;
head = head->next;
delete temp;
return;
}
for (TNode *prevNode = head; prevNode->next != NULL; prevNode = prevNode->next) {
if (prevNode->next->data % 2 == 0) {
TNode *temp = prevNode->next;
prevNode->next = prevNode->next->next;
delete temp;
break;
}
}
}
void sort() {
bool wasChange;
do {
wasChange = false;
for (TNode *temp = head; temp->next != NULL; temp = temp->next) {
if (temp->data > temp->next->data) {
int res = temp->data;
temp->data = temp->next->data;
temp->next->data = res;
wasChange = true;
}
}
} while (wasChange == true);
}
void printList() {
for (TNode *temp = head; temp != NULL; temp = temp->next) {
printf("%d ", temp->data);
}
printf("\n");
}
void addCharToEnd(char *&str, char z) {
int len = strlen(str);
char *newStr = new char[len + 2];
strcpy(newStr, str);
newStr[len] = z;
newStr[len + 1] = 0;
delete str;
str = newStr;
}
void delLastChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, str, (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void delFirstChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, &str[1], (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void inputString(char *&z) {
z = new char[1];
z[0] = 0;
while (true) {
char c = _getch();
if ((c == '\n') || (c == '\r')) {
break;
}
if ((c == '\b') && (z[0] != 0)) {
printf("\b ");
delLastChar(z);
} else {
addCharToEnd(z, c);
}
printf("%c", c);
}
}
bool testValue(char *&str) {
while (str[0] == '0') {
delFirstChar(str);
}
int len = strlen(str);
if ((len == 0) && (len > 10)) {
return false;
}
for (int i = 0; i < len; i++) {
if (strchr(" .,\\\"!&<>?()-qwertyuiopasdfghjklzxcvbnm", str[i]) != NULL) {
return false;
}
}
return true;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
List *list = new List;
printf("Input size list: ");
char *str;
list->inputString(str);
bool wasChanged = false;
while (wasChanged == false) {
if (list->testValue(str) == false) {
char *newStr;
printf("\nerror!\n");
printf("Input size list: ");
list->inputString(newStr);
delete str;
str = newStr;
} else {
wasChanged = true;
}
}
int size = atoi(str);
delete str;
for (int i = 0; i < size; i++) {
char *temp;
printf("\nInput element %d list: ", (i + 1));
list->inputString(temp);
bool wasChanged = false;
while (wasChanged == false) {
if (list->testValue(temp) == false) {
char *newStr;
printf("\nerror!\n");
printf("\nInput element %d list: ", (i + 1));
list->inputString(newStr);
delete temp;
temp = newStr;
} else {
wasChanged = true;
}
}
int res = atoi(temp);
list->addInt(res);
delete temp;
}
printf("\nBefore process: \n");
list->printList();
list->delFirsEvenValue();
list->sort();
printf("After process: \n");
list->printList();
_getch();
delete list;
return 0;
}
Лабораторная работа №9 (двухсвязанный список)
// lab9.cpp: определяет точку входа для консольного приложения.
//
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include "stdafx.h"
class TNode {
public:
TNode *next;
TNode *prev;
int data;
TNode(int _data, TNode *_prev, TNode *_next) {
data = _data;
prev = _prev;
next = _next;
}
};
class LinkTwo {
public:
TNode *head;
TNode *tail;
LinkTwo() {
head = NULL;
tail = NULL;
}
void clear() {
while (head != NULL) {
if (head->next == NULL) {
delete head;
head = NULL;
} else {
head = head->next;
delete head->prev;
}
}
tail = NULL;
}
void addToHead(int newData) {
if (head == NULL) {
head = new TNode(newData, NULL, NULL);
tail = head;
return;
}
TNode *newHead = new TNode(newData, NULL, head);
head->prev = newHead;
head = newHead;
}
void printFromHead() {
TNode *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
void sort() {
bool wasChange;
do {
wasChange = false;
for (TNode *temp = head; temp->next != NULL; temp = temp->next) {
if (temp->data > temp->next->data) {
int res = temp->data;
temp->data = temp->next->data;
temp->next->data = res;
wasChange = true;
}
}
} while (wasChange == true);
}
};
class ReadString {
public:
ReadString() {
}
virtual ~ReadString() {
}
void addCharToEnd(char *&str, char z) {
int len = strlen(str);
char *newStr = new char[len + 2];
strcpy(newStr, str);
newStr[len] = z;
newStr[len + 1] = 0;
delete str;
str = newStr;
}
void delLastChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, str, (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void delFirstChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, &str[1], (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void inputString(char *&z) {
z = new char[1];
z[0] = 0;
while (true) {
char c = _getch();
if ((c == '\n') || (c == '\r')) {
break;
}
if ((c == '\b') && (z[0] != 0)) {
printf("\b ");
delLastChar(z);
} else {
addCharToEnd(z, c);
}
printf("%c", c);
}
}
bool testValue(char *&str) {
while ((str[0] == '0') || (str[0] == '+')) {
delFirstChar(str);
}
int len = strlen(str);
if ((len == 0) || (len > 10)) {
return false;
}
for (int i = 0; i < len; i++) {
if (strchr(" .,\\\"!&<>?()qwertyuiopasdfghjklzxcvbnm", str[i]) != NULL) {
return false;
}
}
return true;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
LinkTwo *list = new LinkTwo;
ReadString *string = new ReadString;
printf("Input size list: ");
char *str;
string->inputString(str);
bool wasChanged = false;
while (wasChanged == false) {
if ((string->testValue(str) == false) || (str[0] == '-')) {
char *newStr;
printf("\nerror!\n");
printf("Input size list: ");
string->inputString(newStr);
delete str;
str = newStr;
} else {
wasChanged = true;
}
}
int size = atoi(str);
delete str;
for (int i = 0; i < size; i++) {
char *temp;
printf("\nInput element %d list: ", (i + 1));
string->inputString(temp);
bool wasChanged = false;
while (wasChanged == false) {
if (string->testValue(temp) == false) {
char *newStr;
printf("\nerror!\n");
printf("\nInput element %d list: ", (i + 1));
string->inputString(newStr);
delete temp;
temp = newStr;
} else {
wasChanged = true;
}
}
int res = atoi(temp);
list->addToHead(res);
delete temp;
}
printf("\nBefore process: \n");
list->printFromHead();
list->sort();
printf("\nAfter process: \n");
list->printFromHead();
_getch();
list->clear();
delete list;
delete string;
return 0;
}
Лабораторная работа №10 (дерево поиска или двоичное дерево)
// lab10.cpp: определяет точку входа для консольного приложения.
//
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include "stdafx.h"
using namespace std;
int generate(int min, int max) {
return (double)rand() / (RAND_MAX + 1) * (max - min) + min;
}
class TNode {
public:
TNode *left;
TNode *right;
int data;
TNode(int _data, TNode *_left, TNode *_right) {
data = _data;
left = _left;
right = _right;
}
};
class StackNode {
public:
StackNode *next;
TNode *data;
StackNode(TNode *_data, StackNode *_next) {
data = _data;
next = _next;
}
};
class Stack {
public:
StackNode *head;
Stack() {
head = NULL;
}
void pushValue(TNode *data) {
head = new StackNode(data, head);
}
TNode *getValue() {
TNode *res = head->data;
StackNode *t = head;
head = head->next;
delete t;
return res;
}
bool isEmpty() {
return (head == NULL);
}
};
class BinaryTree {
public:
TNode *root;
BinaryTree() {
root = NULL;
}
void addRec(int data, TNode *&localRoot) {
if (localRoot == NULL) {
localRoot = new TNode(data, NULL, NULL);
return;
}
if (localRoot->data > data) {
addRec(data, localRoot->left);
} else {
addRec(data, localRoot->right);
}
}
void addNode(int data) {
addRec(data, root);
}
bool findNotRec(int searchValue) {
return findRec(searchValue, root);
}
void clear() {
clearTree(root);
}
void clearTree(TNode *&localRoot) {
if (localRoot == NULL) {
return;
}
clearTree(localRoot->left);
clearTree(localRoot->right);
delete localRoot;
localRoot = NULL;
}
bool findRec(int searchValue, TNode *localRoot) {
if (localRoot == NULL) {
return false;
}
if (localRoot->data == searchValue) {
return true;
}
if (localRoot->data > searchValue) {
return findRec(searchValue, localRoot->left);
} else {
return findRec(searchValue, localRoot->right);
}
}
int findMaxLen() {
int res = 0;
return findMaxLenRec(root, res);
}
void process() {
cout << "\nMax len tree:" << endl;
cout << findMaxLen() << endl;
}
int findMaxLenRec(TNode *localRoot, int res) {
if (localRoot == NULL) {
return res;
}
int leftR = findMaxLenRec(localRoot->left, res + 1);
int rightR = findMaxLenRec(localRoot->right, res + 1);
return (leftR > rightR) ? leftR : rightR;
}
void printRec(TNode *localRoot) {
if (localRoot == NULL) {
return;
}
printRec(localRoot->left);
cout << localRoot->data << ' ';
printRec(localRoot->right);
}
void print() {
printRec(root);
}
};
class ReadString {
public:
ReadString() {
}
virtual ~ReadString() {
}
void addCharToEnd(char *&str, char z) {
int len = strlen(str);
char *newStr = new char[len + 2];
strcpy(newStr, str);
newStr[len] = z;
newStr[len + 1] = 0;
delete str;
str = newStr;
}
void delLastChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, str, (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void delFirstChar(char *&str) {
int len = strlen(str);
char *newStr = new char[len];
memmove(newStr, &str[1], (len - 1) * sizeof(char));
newStr[len - 1] = 0;
delete str;
str = newStr;
}
void inputString(char *&z) {
z = new char[1];
z[0] = 0;
while (true) {
char c = _getch();
if ((c == '\n') || (c == '\r')) {
break;
}
if ((c == '\b') && (z[0] != 0)) {
printf("\b ");
delLastChar(z);
} else {
addCharToEnd(z, c);
}
printf("%c", c);
}
}
bool testValue(char *&str) {
while ((str[0] == '0') || (str[0] == '+')) {
if ((str[0] == '0') && (strlen(str) == 1))
break;
delFirstChar(str);
}
int len = strlen(str);
if ((len == 0) || (len > 10)) {
return false;
}
for (int i = 0; i < len; i++) {
/*if (strchr("1234567890", str[i]) == NULL) {
return false;
}*/
if ((str[i] < '0') || (str[i] > '9'))
return false;
}
return true;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
BinaryTree *tree = new BinaryTree;
ReadString *string = new ReadString;
printf("Input size tree: ");
char *str;
string->inputString(str);
bool wasChanged = false;
while (wasChanged == false) {
if ((string->testValue(str) == false) || (str[0] == '-')) {
char *newStr;
printf("\nerror!\n");
printf("Input size tree: ");
string->inputString(newStr);
delete str;
str = newStr;
} else {
wasChanged = true;
}
}
int size = atoi(str);
delete str;
for (int i = 0; i < size; i++) {
/*char *temp;
printf("\nInput element %d tree: ", (i + 1));
string->inputString(temp);
bool wasChanged = false;
while (wasChanged == false) {
if (string->testValue(temp) == false) {
char *newStr;
printf("\nerror!\n");
printf("\nInput element %d tree: ", (i + 1));
string->inputString(newStr);
delete temp;
temp = newStr;
} else {
wasChanged = true;
}
}
int res = atoi(temp);*/
tree->addNode(generate(0, 1000000));
//delete temp;
}
printf("\nBinary tree: \n");
//tree->print();
tree->process();
printf("\nInput number: ");
char *temp;
string->inputString(temp);
wasChanged = false;
while (wasChanged == false) {
if (string->testValue(temp) == false) {
char *newStr;
printf("\nerror!\n");
printf("\nInput number: ");
string->inputString(newStr);
delete temp;
temp = newStr;
} else {
wasChanged = true;
}
}
int value = atoi(temp);
delete temp;
cout << "\nEnter element to search for:" << endl;
cout << (tree->findNotRec(value) ? "true" : "false") << endl;
tree->clear();
delete tree;
delete string;
_getch();
return 0;
}
