Шпаргалка по языку СИ. Конспект Лекций «программирование На Языке Высокого Уровня Си» П. Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления
 Скачать 1.25 Mb.
|
|
#include using namespace std; class Node { public: int number; Node* next; Node* last; }; void main() { short action = -1; Node* head = NULL; Node* tail = NULL; Node* ptrLast = NULL; while (1) { puts("1. Добавить Элемент\n"); puts("2. Просмотр Списка слева направо\n"); 189 puts("3. Просмотр Списка направа слево\n"); puts("4. Удалить головной элемент\n"); puts("5. Удалить последний элемент\n"); puts("6. Поиск элемента\n"); puts("0. Выход\n\n"); puts("Ваш выбор: "); cin>>action; if (action == 0) { system("CLS"); break; } if (action == 1) { system("CLS"); int numb = -1; puts("Введите число: "); cin>>numb; Node* ptr = new Node; ptr->number = numb; ptr->next = NULL; tail = ptr; if (head == NULL) { head = ptr; ptrLast = ptr; ptr->last = NULL; system("CLS"); continue; } ptr->last = ptrLast; ptrLast->next = ptr; ptrLast = ptr; system("CLS"); continue; } if (action == 2) { system("CLS"); Node* ptr = NULL; if (head == NULL) { puts("\t!!! Список пуст !!!\n\n"); system("PAUSE"); system("CLS"); continue; } puts("* * * * * Список: слева направо * * * * *\n\n"); ptr = head; while (1) { cout< number<<" "; if (ptr->next == 0) break; ptr = ptr->next; } cout<<"\n\n"; system("PAUSE"); system("CLS"); continue; } 190 if (action == 3) { system("CLS"); Node* ptr = NULL; if (head == NULL) { puts("\t!!! Список пуст !!!\n\n"); system("PAUSE"); system("CLS"); continue; } puts("* * * * * Список: справа налево * * * * *\n\n"); ptr = tail; while (1) { cout< number<<" "; if (ptr->last == 0) break; ptr = ptr->last; } cout<<"\n\n"; system("PAUSE"); system("CLS"); continue; } if (action == 4) { system("CLS"); Node* ptrDelete = NULL; if (head == NULL) { puts("\t!!! Список пуст !!!\n\n"); system("PAUSE"); system("CLS"); continue; } if (head->next == NULL) { head = NULL; tail = NULL; delete head; continue; } ptrDelete = head; head = ptrDelete->next; head->last = NULL; delete ptrDelete; continue; } if (action == 5) { system("CLS"); Node* ptrDelete = NULL; if (tail == NULL) { puts("\t!!! Список пуст !!!\n\n"); system("PAUSE"); system("CLS"); continue; } if (tail->last == NULL) 191 { head = NULL; tail = NULL; delete tail; continue; } ptrDelete = tail; tail = ptrDelete->last; tail->next = NULL; ptrLast = tail; delete ptrDelete; continue; } if (action == 6) { system("CLS"); Node* ptr = NULL; int key = -1; if (head == NULL) { puts("\t!!! Список пуст !!!\n\n"); system("PAUSE"); system("CLS"); continue; } puts("Введите искомый элемент: "); cin>>key; ptr = head; while (1) { if (key == ptr->number) { puts("\n\t!!! Элемент найден !!!\n"); break; } if (ptr->next == NULL) { puts("\n\t!!! Элемент не найден !!!\n"); break; } ptr = ptr->next; } system("PAUSE"); system("CLS"); continue; } if (action > 6) { system("CLS"); puts("\t!!! Неверный выбор. Повторите ввод !!!\n\n"); system("PAUSE"); system("CLS"); continue; } } } Результат выполнения программы (меню программы) 1. Добавить Элемент 2. Просмотр Списка слева направо 192 3. Просмотр Списка направа слево 4. Удалить головной элемент 5. Удалить последний элемент 6. Поиск элемента 0. Выход Ваш выбор: Пример 10. Процедуры для организации очередей и работы с ними. class Node { public: int number; Node* last; Node* next; }; int main() { Node* head = NULL; Node* tail = NULL; Node* ptrLast = NULL; short action = -1; while(1) { printf("1. Добавить Элемент\n"); printf("2. Просмотр Очереди\n"); printf("3. Удалить Элемент\n"); printf("4. Поиск Элемента\n"); printf("0. Выход\n\n"); printf("Ваш Выбор: "); cin>>action; if (action == 0) { system("CLS"); break; } if (action == 1) { system("CLS"); int numb = -1; printf("Введите Число: "); cin>>numb; Node* ptr = new Node; ptr->number = numb; ptr->next = NULL; tail = ptr; if (head == NULL) { head = ptr; ptrLast = ptr; 193 ptr->last = NULL; system("CLS"); continue; } ptr->last = ptrLast; ptrLast->next = ptr; ptrLast = ptr; system("CLS"); continue; } if (action == 2) { system("CLS"); Node* ptr = NULL; if (head == NULL) { printf("\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("* * * * * ОЧЕРЕДЬ * * * * *\n\n"); ptr = tail; while (1) { cout< number<<" "; if (ptr->last == 0) break; ptr = ptr->last; } cout<<"\n\n"; system("PAUSE"); system("CLS"); continue; } if (action == 3) { system("CLS"); Node* ptrDelete = NULL; if (head == NULL) { printf("\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n"); system("PAUSE"); system("CLS"); continue; } if (head->next == NULL) { head = NULL; tail = NULL; delete tail; continue; } ptrDelete = head; head = ptrDelete->next; head->last = NULL; delete ptrDelete; continue; } if (action == 4) { 194 system("CLS"); Node* ptr = NULL; int key = -1; if (head == NULL) { printf("\t!!! СПИСОК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("Введите Элемент Для Поиска: "); cin>>key; ptr = head; while (1) { if (key == ptr->number) { printf("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n"); break; } if (ptr->next == NULL) { printf("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n"); break; } ptr = ptr->next; } system("PAUSE"); system("CLS"); continue; } if (action > 4) { system("CLS"); printf("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n"); system("PAUSE"); system("CLS"); continue; } } } Результат выполнения программы (меню программы) 1. Добавить Элемент 2. Просмотр Очереди 3. Удалить Элемент 4. Поиск Элемента 0. Выход Ваш выбор: Пример 11. Процедуры для организации и работы со стеками. #include 195 #include #include #include #include #include using namespace std; class Node { public: int number; Node* last; }; int main() { Node* ptrLast = NULL; Node* top = NULL; short action = -1; while (1) { printf("1. Затолкнуть В Стек\n"); printf("2. Вытолкнуть Из Стека\n"); printf("3. Вершина Стека\n"); printf("4. Содержимое Стека\n"); printf("0. Выход\n\n"); printf("Ваш Выбор: "); cin>>action; if (action == 0) { system("CLS"); break; } if (action == 1) { system("CLS"); int numb = -1; printf("Введите Число: "); cin>>numb; Node* ptr = new Node; ptr->number = numb; if (top == NULL) { ptr->last = NULL; top = ptr; ptrLast = ptr; system("CLS"); continue; } top = ptr; ptr->last = ptrLast; ptrLast = ptr; system("CLS"); continue; } if (action == 2) { system("CLS"); Node* ptrDelete = NULL; 196 if (top == NULL) { printf("\t!!! СТЕК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } ptrDelete = top; if (ptrDelete->last == NULL) { top = NULL; delete ptrDelete; system("CLS"); continue; } top = ptrDelete->last; ptrLast = top; delete ptrDelete; continue; } if (action == 3) { system("CLS"); if (top == NULL) { printf("\t!!! СТЕК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("Вершина Стека: "); cout< system("PAUSE"); system("CLS"); continue; } if (action == 4) { system("CLS"); Node* ptr = NULL; if (top == NULL) { printf("\t!!! СТЕК ПУСТ !!!\n\n"); system("PAUSE"); system("CLS"); continue; } printf("* * * * * СОДЕРЖИМОЕ СТЕКА * * * * *\n\n"); ptr = top; while (1) { cout< number< if (ptr->last == NULL) { system("PAUSE"); system("CLS"); break; } ptr = ptr->last; } } 197 if (action > 4) { system("CLS"); printf("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n"); system("PAUSE"); system("CLS"); continue; } } } Результат выполнения программы (меню программы) 1. Затолкнуть В Стек 2. Вытолкнуть Из Стека 3. Вершина Стека 4. Содержимое Стека 0. Выход Ваш выбор: Пример 12. Алгоритм решения задачи «Ханойская башня». Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее. Эту известную игру придумал французский математик Эдуард Люка, в 1883 году её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Коллеж Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа − не более чем анаграмма фамилии изобретателя игры − профессора Люка (Lucas) из коллежа Сен-Луи (Saint Louis). Не рекурсивный алгоритм решения задачи Ханойская башня. #include #include #include #include #include 198 int y = 0; int N; // Количество дисков int dest; // На какой стержень перекладываем int step = 0; // Номер текущего шага int max_steps = 0; // Необходимое количество шагов int first_on = 1; // На каком стержне находится первый диск // Состояние объекта управления - "содержимое" стержней char s[4][100] = { "", "1", "", "" }; void hanoy(int from, int to, int disk_num); int move(int disk, int from, int to); int disk_on(int s_num); // Переложить первый диск по часовой стрелке void z1() { int from = first_on; int i; // Определить номер следующего стержня if ((dest == 2 && N%2 != 0) || (dest == 3 && N%2 == 0)) first_on = (from + 1)%3; // Порядок стержней 1-2-3 else first_on = (from + 2)%3; // Порядок стержней 1-3-2 if (first_on == 0) first_on = 3; move(1, from, first_on); } // Переложить единственный возможный диск, кроме наименьшего void z2() { int i, j; int disk_from, disk_to; // Определить перекладываемый диск for (i = 1; i <= 3; i++) { disk_from = disk_on(i); if (disk_from > 1) // Определить, на какой стержень перекладывать for (j = 1; j <= 3; j++) { disk_to = disk_on(j); if (disk_to == 0 || disk_from < disk_to) { move(disk_from, i, j); return; } } } } // Вернуть номер диска на указанном стержне int disk_on(int s_num) { return atoi(s[s_num]); } // Проверить, завершено ли перекладывание int x1() { return step >= max_steps; } 199 // Переложить заданный диск int move(int disk, int from, int to) { char *str_pos = strchr( s[from], '-' ); if (str_pos == NULL) s[from][0] = 0; else strcpy(s[from], str_pos+1); if (s[to][0] == 0) sprintf(s[to], "%d", disk); else { strcpy(s[0], s[to]); sprintf(s[to], "%d-%s", disk, s[0]); } step++; printf("Шаг %d. Диск %d: %d -> %d\n", step, disk, from, to); return 0; } void hanoy(int from, int to, int disk_num) { int i; N = disk_num; max_steps = (1 << N) - 1; dest = to; // Заполнить первый стержень дисками for (i = 2; i <= N; i++) { sprintf(s[0], "-%d", i); strcat(s[1], s[0]); } do switch (y) { case 0: z1(); y = 1;break; case 1: if (x1()) y = 0; else { z2(); z1(); } break; } while (y != 0); // Вывести результат printf("\nРезультат:\n"); for (i = 1; i <= 3; i++) printf("%d: %s\n", i, s[i]); } int main() { int n = 4; printf("Введите количество дисков : "); scanf("%d",&n); printf("\nХаной с %d дисками :\n", n); hanoy(1, 3, n); getch(); } 200 Результат выполнения программы Введите количество дисков : 4 Ханой с 4 дисками : Шаг 1. Диск 1: 1 -> 2 Шаг 2. Диск 2: 1 -> 3 Шаг 3. Диск 1: 2 -> 3 Шаг 4. Диск 3: 1 -> 2 Шаг 5. Диск 1: 3 -> 1 Шаг 6. Диск 2: 3 -> 2 Шаг 7. Диск 1: 1 -> 2 Шаг 8. Диск 4: 1 -> 3 Шаг 9. Диск 1: 2 -> 3 Шаг 10. Диск 2: 2 -> 1 Шаг 11. Диск 1: 3 -> 1 Шаг 12. Диск 3: 2 -> 3 Шаг 13. Диск 1: 1 -> 2 Шаг 14. Диск 2: 1 -> 3 Шаг 15. Диск 1: 2 -> 3 Результат: 1: 2: 3: 1-2-3-4 Рекурсивный алгоритм решения задачи Ханойская башня. #include #include #include #include #include void move(int i, int j, int d) { int m; for(m = 0; m < d; m++) printf(" "); printf("перемещение(%d,%d)\n", i, j); } void hanoy(int i, int j, int k, int d) { // для отладки //int m ; //for (m = 0; m < d; m++) printf(" "); //printf("hanoy(%d,%d,%d)\n", i, j, k); if (k == 1) move(i, j, d); else { hanoy(i, 6-i-j, k-1, d+1); hanoy(i, j, 1, d+1); hanoy(6-i-j, j, k-1, d+1); } } int main() 201 |