Семинары (1171138), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Для этого общую информациюрасположим в заголовочном файле calc.h, который будем по мере необходимости включать в другие файлы.В результате получим программу, файловая структура которой показана ниже:main.с:#include <stdio.h>#include <stdlib.h>#include "calc.h"#define MAXOP 100main() {...}calc.h:#define NUMBER '0'void push(double);double pop(void);int getop(char[]);int getch(void);void ungetch(int);getop.c:#include <stdio.h>#include <ctype.h>#include "calc.h"getop (){...}getch.c:#include <stdio.h>#define BUFSIZE 100char buf[BUFSIZE];intbufp = 0;int getch(void) {...}void ungetch(int) {...}stack.с:#include <stdio.h>#include "calc.h"#define MAXVAL 100int sp = 0;double val[MAXVAL];void push(double) {6...}double pop(void) {...}Задание 6:Методы сортировки должны быть реализованы в виде функций. Работу смассивами организовать через указатели.1. Написать программу сортировки массивов методом отбора и методом Шелла.

Сравнитьскорость работы указанных методов сортировки.2. Написать программу сортировки массивов методом вставки и с помощью быстройсортировки. Сравнить скорость работы указанных методов сортировки.3. Написать программу сортировки массивов методом отбора и методом быстройсортировки.

Сравнить скорость работы указанных методов сортировки.4. Написать программу сортировки массивов методом вставки и методом Шелла.Сравнить скорость работы указанных методов сортировки.Длявычислениевремениработыgettimeofday(&tv,NULL) из sys/time.hалгоритмаиспользоватьфункцию#include <sys/time.h>unsigned long GetTickCount(){struct timeval tv;gettimeofday(&tv,NULL);return (tv.tv_sec*1000+tv.tv_usec/1000);}Исходный код7Результат выполнения8Контрольные вопросы1.2.3.4.5.6.Сортировка массива методом пузырька?Сортировка массива методом отбора?Сортировка массива методом вставки?Сортировка массива методом Шелла?Быстрая сортировка?Сложность алгоритмов?СПИСОК ЛИТЕРАТУРЫ1.

Г. Шилдт Теория и практика С++: пер. с анг. – СПб.: BHV – Санкт-Петербург,1996ю – 416 с., ил.2. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ =Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс,2005. — 1296 с.3. Дейтел Х. М. Как программировать на С++: Пер. с англ. – М.: ЗАО «ИздательствоБИНОМ», 2000 г. – 1024 с.: ил.4. Страуструп Б. Язык программирования С++. Специальное издание: ++: Пер. с англ.– М.: ЗАО «Издательство БИНОМ», 2008 г.

– 1104 с. :ил.5. Шилдт Г. Полный справочник по С++: ++: Пер. с англ. – М.: Изд-во Вильямс, 2007г. – 800 с.: ил.6. Шилдт Г. С++: Базовый курс: ++: Пер. с англ. – М.: Изд-во Вильямс, 2008 г. – 624с.: ил.9датаОтчет по лабораторной работе №6«Основы C++, работа с памятью»ОценкаБонус за(max 5)сложностьподписьЦели работы:Изучение принципов динамической работы с памятью, работа со строками.Задачи работы:-ознакомление с понятием структуры на примере структуры стека и очереди-разработка программ на C++Краткий конспект теоретической части (ответы на контрольные вопросы)Статическая и динамическая память?_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Захват/освобождение памяти?____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Печать первых простых n чисел?_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Понятие структуры данных?________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Работа со структурами данных: объявление структур?___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Работа со структурами: нахождение векторного произведения векторов?___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Работа со структурами данных: поиск числа вершин дерева?_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________1Основы C++, работа с памятью.Пример 1: Выделение и освобождение памяти на примере программы печати первых nпростых чисел:#include <stdio.h>#include <stdlib.h>#include <math.h> //подключение модуля math, в котором содержиться описание//математических фугкцийint main() {int n; // Требуемое количество простых чиселint k; // Текущее количество найденных простых чиселint *a; // Указатель на массив найденных простыхint p; // Очередное проверяемое числоint r; // Целая часть квадратного корня из pint i; // Индекс простого делителяbool prime; // Признак простотыprintf("Введите число простых: ");scanf("%d", &n);if (n <= 0)// Некорректное значение =>return 1; // завершаем работу с кодом ошибки// Захватываем память под массив простых чиселa = (int *) malloc(n * sizeof(int));a[0] = 2; k = 1;// Добавляем двойку в массивprintf("%d ", a[0]); // и печатаем ееp = 3;while (k < n) {// Проверяем число p на простотуr = (int)(// Целая часть корняsqrt((double) p) + 0.001);i = 0;prime = true;while (i < k && a[i] <= r) {if (p % a[i] == 0) { // p делится на a[i]prime = false;// => p не простое,break;// выходим из цикла}++i; // К следующему простому делителю}if (prime) { // Если нашли простое число,a[k] = p; // то добавляем его в массив++k;// Увеличиваем число простыхprintf("%d ", p); // Печатаем простое числоif (k % 5 == 0) { // Переход на новую строкуprintf("\n"); // после каждых пяти чисел}}p += 2; // К следующему нечетному числу}if (k % 5 != 0) {printf("\n"); // Перевести строку}// Освобождаем динамическую памятьfree(a);return 0;}2Тестовые данныеРезультат работы программыПример 2: Выделение и освобождение памяти с помощью операторов new и delete.#include <stdio.h>#include <stdlib.h>int main() {{double *p = new double(1.5);//этот фрагмент эквивалентен фрагментуdouble *p = new double;*p = 1.5;double *a;int m = 100, n = 101;a = new double[m * n];return 0;}Задание 1:Модифицировать программу нахождения простых чисел из примера 1 с использованиемоператоров new и delete.Исходный кодТестовые данные3Результат выполненияПример 3: Пример объявления структуры:#include "stdafx.h"#include <stdio.h>#include <tchar.h>struct R3Vector { // Вектор трехмерного пространстваdouble x;double y;double z;};int _tmain(int argc, _TCHAR* argv[]){R3Vector u;printf("Input coordinate x for u \n");scanf("%lf",&u.x);printf("Input coordinate y for u \n");scanf("%lf",&u.y);printf("Input coordinate z for u \n");scanf("%lf",&u.z);printf("3D vector u:\n u.x = %3.2f u.y = %3.2f u.z = %3.2f \n",w.x, w.y, w.z);return 0;}Результат выполнения4Пример 4: Нахождение векторного произведения векторов:#include <stdio.h>struct R3Vector { // Вектор трехмерного пространстваdouble x;double y;double z;};int main(int argc, char* argv[]){R3Vector u, v, w;printf("Input coordinate x for u \n");scanf("%lf",&u.x);printf("Input coordinate y for u \n");scanf("%lf",&u.y);printf("Input coordinate z for u \n");scanf("%lf",&u.z);printf("Input coordinate x for v \n");scanf("%lf",&v.x);printf("Input coordinate y for v \n");scanf("%lf",&v.y);printf("Input coordinate z for v \n");scanf("%lf",&v.z);// Вычисляем векторное произведение w = u * vw.x = u.y * v.z - u.z * v.y;w.y = (-u.x) * v.z + u.z * v.x;w.z = u.x * v.y - u.y * v.x;printf("uXv: w.x = %3.2f w.y = %3.2f w.z = %3.2f \n", w.x, w.y,w.z);return 0;}Результат выполнения5Задание 2:Модифицировать программу нахождение векторного произведения векторов для нахожденияскалярного произведения.Исходный кодТестовые данныеРезультат выполнения6Пример 5: Поиск числа вершин дерева:ParentStructvalueRightLeft#include <stdio.h>// Описание структуры, представляющей вершину дереваstruct TreeNode {struct TreeNode *parent; // Указатель на отца,struct TreeNode *left;//на левого сына,struct TreeNode *right; //на правого сынаint value;// Значение в вершине};int numNodes(const struct TreeNode *root) {int num = 0;if (root == 0) { // Для нулевого указателя на кореньreturn 0;// возвращаем ноль}if (root->left != 0) {// Есть левый сын =>num += numNodes(root->left); // вызываем функцию}// для левого сынаif (root->right != 0) {// Есть правый сын =>num += numNodes(root->right); // вызываем ф-цию}// для правого сына}return num + 1; // Возвращаем суммарное число вершинint _tmain(int argc, _TCHAR* argv[]){TreeNode *root, *left, *right;root = new TreeNode;left = new TreeNode;right = new TreeNode;root->parent = NULL;root->value = 1;7root->left=left;root->right=right;left->parent = root;left->value = 2;left->left = NULL;left->right = NULL;right->parent = root;right->value = 3;right->left = NULL;right->right = NULL;printf("Num nodes = %d \n",numNodes(root));return 0;}Результат выполнения8Контрольные вопросы1.2.3.4.5.6.7.Статическая и динамическая память?Захват/освобождение памяти?Печать первых простых n чисел?Понятие структуры данных?Работа со структурами данных: объявление структур?Работа со структурами: нахождение векторного произведения векторов?Работа со структурами данных: поиск числа вершин дерева?СПИСОК ЛИТЕРАТУРЫ1.

Характеристики

Список файлов семинаров