Шпаргалка по языку СИ. Конспект Лекций «программирование На Языке Высокого Уровня Си» П. Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления
 Скачать 1.25 Mb.
|
|
else { Ptr->next = head; Head->back = ptr; Head = ptr; } Добавление в хвост списка и после текущего узла списка (или перед текущим) делается аналогично: int s list tail; list* ptr = new list; ptr->value = val; ptr->next = NULL; ptr->back = NULL; if (tail == NULL) tail = ptr //список пустой? else { tail->next = ptr; prt->back = tail; tail = ptr; } Удаление узла из списка При удалении узла из списка нужно рассмотреть следующие ситуации: 1. Удаляемый узел является головой списка. 2. Удаляемый узел является хвостом списка. 3. Удаляемый узел единственный в списке. 4. Удаляемый узел не является ни головой, ни хвостом, ни единственным в списке. В конце процедуры удаления обязательно необходимо освободить ранее выделенную динамическую память для удаляемого узла с помощью стандартной процедуры free(). Разберем подробно последний случай 4, когда удаляется узел не с краев, а внутри списка (табл.16). 153 Таблица 16. Удаление узла внутри списка № Действие Иллюстрация 1. На текущий узел указывает предыдущий узел. Этот указатель нужно «перекинуть» на следующий за текущим узел: cur->back->next =cur->next; 2. Следующий узел за текущим после удаления текущего узла должен будет указывать на предыдущий от текущего узла. Заменяем этот указатель: cur->next->back = cur->back; 3. Запомним указатель на текущий элемент во временном указателе tail: tail = cur; 4. Текущим элементом списка будет теперь следующий за ним узел: cur = cur->next; 5. Освобождаем память, выделенную динамически для удаляемого узла списка: free(tail); 154 cur Cur->back cur->back->next Cur->next cur->next->back cur Cur->back cur->back->next Cur->next cur->next->back back Cur->back cur->back->next Cur->next cur->next->back tail cur Cur->back cur->back->next Cur->next cur->next->back tail cur cur //удаление узла в списке list head,tail,cur, temp; // проверяем является ли узел единственным в списке? if ((cur->next == NULL) && (cur->back = NULL)) { head = NULL; tail = NULL; // делаем список пустым free(cur); cur = NULL; //освобождаем память } else if (cur->next == NULL) // текущий узел является хвостом? { tail = tail->back; // Хвостом теперь станет предпоследний узел tail->next = NULL; free (cur); cur = tail; } else if (cur->back == NULL) // текущий узел является головой? { head = head->next; // головой становится второй узел списка head->back = NULL; free (cur); cur = head; } else //узел ни голова, ни хвост, ни единственный в списке { cur->back->next = cur->next; cur->next->back = cur->back; temp = cur; cur = cur->next; free (temp); }; } Обход списка и переход к узлу по номеру от головы списка Обход списка осуществляется с целью анализа, обработки и поиска данных находящихся в списке. Заметим, что переход к следующему узлу осуществляется присваиванием указателю C на текущий узел значения указателя на следующий узел cur->next. Но по определению списка, последний узел в списке содержит пустой указатель на следующий узел. А значит это и является признаком конца обхода списка. Таким образом, стандартный алгоритм обхода списка прост: 3. Выполнять в цикле: 4. Обработать текущий узел. 5. Перейти к следующему узлу. 6. До тех пор пока указатель на следующий узел станет пустым. 155 Пример 34. Напишем процедуру обохода списока с целью вывода его содержимого на экран и поиска совпадающей строки, а также функцию перехода к узлу списка по номеру. void PrintSearchList (list head, int val) //Head – указатель на голову списка, str – искомая строка { bool lfound = false; // признак того, что строка найдена tail = &head; //начинаем с головы списка while (tail != NULL)// если указатель на текущий элемент списка не пуст { printf("%d\n", tail->value); //выводим информационное поле списка if (tail->value = val) lfound = true; //совпадает с искомой строкой? tail = tail->next; //переходим к следующему узлу списка } if (lfound) printf("Элемент в списке найден!"); else printf("Элемент в списке не найден!"); } list GotoNode (list head, int cnt) //Cnt – номер узла, начиная с 1, к которому нужно перейти { int i = 1; tail = &head; while ((tail->next != NULL) && (i < cnt)) { i++; tail = tail->next; } return(*tail); } Стек, очередь, дек Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Говорят, что стек реализует дисциплину обслуживания LIFO (Last In – First Out, последним пришел – первым ушел). Физически стек может быть реализован на основе массива или на основе односвязанного линейного списка, в котором все операции осуществляются только с головой списка. Этот элемент в стеке называется верхушкой стека и на него указывает указатель стека ptrStack (рис.43). Если указатель стека – пустой, то стек считается пустым. Стек должен поддерживать следующие операции: push – добавить (положить) в верхушку стека новый элемент; pop – извлечь из верхушки стека элемент; isEmpty – проверка, пуст ли стек; top – узнать (прочитать) значение верхушки стека (не удаляя ее); 156 size – узнать количество элементов в стеке; clear – очистить стек (удалить из него все элементы). Поскольку стек с точки зрения программной реализации является частным случаем односвязного линейного списка, то на языке Паскаль стек можно описать с помощью следующих структур: struct st // объявление типа stack { char info; информационная часть struct st *ps; // указатель на предыдущий (более нижний) элемент стека } stack; Стек имеет очень широкое применение в программировании. Особенно часто он используется при решении системных задач, задач компиляции и анализа выражений. Рассмотрим наиболее характерный пример использования стека при переводе выражений в обратную польскую запись. Обратная польская запись (ОПЗ) – это способ записи выражений (как правило алгебраических) в так называемом постфиксном (или суффиксном) виде, т.е. в таком виде, когда сначала записываются все операнды, а потом выполняемые над ними операции, т.е. для обычных бинарных операций сложения, вычитания, умножения и деления знак операции располагается после операндов, а не между ними как в привычном «инфиксном» виде. Одна из особенностей ОПЗ – отсутствие скобок, что позволяет вычислять ОПЗ за один проход слева направо. ОПЗ как правило используется в трансляторах и компиляторах для преобразования выражений в машинный код, их последующего вычисления, а также для анализа и трансляции синтаксических конструкций языка к виду, удобному для генерации машинного кода. ptrStack Верхушка стека 157 Рис.43. Графическое изображение стека Пример 35. Представим выражение (a+b)/(c/a*c – e*d) в постфиксном виде: ОПЗ: ab+ca/c*ed*–/ . Вычислим ОПЗ слева на право, при вычислении пользуемся правилом: «в операции участвуют два операнда, расположенные слева от знака операции». 1. Первое вычисление: R 1 = ab+ = a+b , подставляем в исходную строку вместо ab+ вычисленный результат R 1 получается ОПЗ: R 1 ca/c*ed*–/ 2. Второе действие: R 2 = ca/ = c/a ОПЗ: R 1 R 2 c*ed*–/ 3. Третье действие: R 3 = R 2 c* = R 2 *c = c/a*c ОПЗ: R 1 R 3 ed*–/ 4. Четвертое действие: R 4 = ed* = e*d ОПЗ: R 1 R 3 R 4 –/ 5. Пятое действие: R 5 = R 3 R 4 – = R 3 –R 4 = c/a*c–e*d ОПЗ: R 1 R 5 / 6. Шестое действие: R 6 = R 1 R 5 / = R 1 /R 5 =(a+b)/(c/a*c–e*d) ОПЗ: R 6 ОПЗ вычислено и его значением стало значение выражения R 6 Наиболе известным алгоритмом перевода простого алгебраического выражения в ОПЗ является алгоритм Дейкстры (Э́дсгер Ви́бе Де́йкстра, 1930 – 2002 , – выдающийся нидерландский ученый, идеи которого оказали огромное влияние на развитие компьютерной индустрии). Идея алгоритма основывается на использовании стека и анализе приоритета операций и заключается в следующем: 1. Исходная строка просматривается посимвольно, слева направо до достижения конца строки. 2. Если встречается символ операция, то эта операция при определенных условиях помещается в стек (затем при определенных условиях операции выталкиваются в выходную строку). 158 3. Если встречаются символы операндов, то они из входной строки поступают сразу в выходную строку. 4. Если встречается открывающаяся скобка, то она всегда помещается в стек. 5. Закрывающаяся скобка ни в стек, ни в выходную строку не помещается. Когда она встречается во входной строке, то из стека выталкиваются все символы до первой встречной открывающейся скобки включительно. При этом знаки операций выталкиваются в выходную строку, а открывающаяся скобка просто удаляется из стека. 6. Необходимо использовать следующие приоритеты операций (табл. 17). Чем больше значение приоритета, тем сильнее операция связывает операнды: Таблица 17. Приоритеты операций для вычисления ОПЗ Операции ( + – * / Приоритет 0 1 1 2 2 7. Если во входной строке текущий символ – знак операции, то сравниваются приоритеты операций из строки и верхушки стека. 8. Если приоритет операции из входной строки больше приоритета операции из верхушки стека, то операция из входной строки стека перемещается в стек. 9. В противном случае из стека выталкиваются все операции с приоритетами большими либо равными приоритету операции из входной строки. После чего операция из входной строки помещается в стек. 10. При встрече конца входной строки содержимое стека выталкивается в выходную строку. Пример 36. Напишем программу перевода входной строки в ОПЗ. /* Описание стpуктуpы(элемента стека) */ struct st { char c; struct st *next; }; struct st *push(struct st *, char); /* Пpототипы функций */ char DEL(struct st **); int PRIOR(char); void main(void) { // Стек опеpаций пуст struct st *OPERS = NULL; char a[80], outstring[80]; 159 int k, point; do { puts("Введите выражение (в конце поставте '=') : "); fflush(stdin); // Ввод аpифметического выpажения gets(a); k = point = 0; // Повтоpяем , пока не дойдем до '=' while(a[k] != '\0' && a[k] != '=') { if(a[k] == ')') // Если очеpедной символ - ')', то выталкиваем из // стека в выходную стpоку все знаки опеpаций до // ближайшей откpывающей скобки { while((OPERS->c) != '(') outstring[point++] = DEL(&OPERS); DEL(&OPERS); // Удаляем из стека саму откpывающую скобку } if(a[k] >= 'a' && a[k] <= 'z') // Если очеpедной символ - буква , то // пеpеписываем её в выходную стpоку outstring[point++] = a[k]; if(a[k] == '(') // Если очеpедной символ - '(' , то заталкиваем её //в стек OPERS = push(OPERS, '('); // Если следующий символ - знак опеpации , то: if(a[k] == '+' || a[k] == '-' || a[k] == '/' || a[k] == '*') { if(OPERS == NULL) // если стек пуст записываем в него опеpацию OPERS = push(OPERS, a[k]); else // если не пуст // если пpиоpитет поступившей опеpации больше пpиоpитета опеpации на веpшине стека заталкиваем поступившую опеpацию на стек if(PRIOR(OPERS->c) < PRIOR(a[k])) OPERS = push(OPERS, a[k]); // else // если пpиоpитет меньше пеpеписываем в выходную стpоку все // опеpации с большим или pавным пpиоpитетом { while((OPERS != NULL) && (PRIOR(OPERS->c) >= PRIOR(a[k]))) // outstring[point++] = DEL(&OPERS); OPERS = push(OPERS, a[k]); // записываем в стек поступившую // опеpацию } } k++; // Пеpеход к следующему символу входной стpоки } // После pассмотpения всего выpажения пеpеписываем все опеpации из стека в выходную стpоку и печатаем её while(OPERS != NULL) outstring[point++] = DEL(&OPERS); outstring[point] = '\0'; printf("\n%s\n", outstring); fflush(stdin); puts("\Повторить (y/n)?"); } while(getchar() != 'n'); } /* Функция push записывает на стек (на веpшину котоpого указывает HEAD) символ a. Возвpащает указатель на новую веpшину стека */ struct st *push(struct st *HEAD, char a) { st* PTR = new st; // Выделение памяти PTR->c = a; // Инициализация созданной веpшины PTR->next = HEAD; // Подключение её к стеку 160 return PTR;// PTR - новая веpшина стека } /* Функция DEL удаляет символ с веpшины стека. Возвpащает удаляемый символ. Изменяет указатель на веpшину стека */ char DEL(struct st **HEAD) { struct st *PTR; char a; if(*HEAD == NULL) return '\0'; // Если стек пуст, возвpащается '\0' PTR = *HEAD; // в PTR - адpес веpшины стека a = PTR->c; *HEAD = PTR->next; // Изменяем адpес веpшины стека free(PTR); // Освобождение памяти return a; // Возвpат символа с веpшины стека } // Функция PRIOR возвpащает пpиоpитет аpифметической опеpации int PRIOR(char a) { switch(a) { case '*': case '/': return 3; case '-': case '+': return 2; case '(': return 1; } } Приведем пример использования Алгоритма Дейкстры для входной строки (a+b*c)*(a–b)/(d– (a+b*d)). Для удобства отображения стека в таблице «транспонируем» его, т.е. разместим стек в строке, развернув по часовой стрелке на 90 градусов, так чтобы вершина стека располагалась в конце строки справа (табл.18). В программировании, кроме списков и стека часто используются подобные динамические структуры, программная реализация которых похожа на списки и стек, но дисциплина доступа к ним и набор типовых операций несколько видоизменены, к ним относятся очередь и дек. Очередью (aнгл. queue) называется структура данных, в которой элементы кладутся в конец, а 161 Таблица 18. Пример построения ОПЗ . Вх c имвол Стек Вых строка ( ( a ( A + (+ A b (+ Ab * (+* ab c (+* abc ) Пусто abc*+ * * abc*+ ( *( abc*+ a *( abc*+a - *(- abc*+a b *(- abc*+ab ) * abc*+ab- / / abc*+ab-* ( /( abc*+ab-* d /( abc*+ab-*d - /(- abc*+ab-*d ( /(-( abc*+ab-*d a /(-( abc*+ab-*da + /(-(+ abc*+ab-*da b /(-(+ abc*+ab-*dab * /(-(+* abc*+ab-*dab d /(-(+* abc*+ab-*dabd ) /(- abc*+ab-*dabd*+ ) / abc*+ab-*dabd*+- Конец строки Пусто abc*+ab-*dabd*+-/ извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других. Говорят, что очередь реализует дисциплину обслуживания FIFO (First In – First Out, первым пришел – первым ушел). Очередь можно рассматривать как однонаправленный список, в котором можно удалять только из начала, а добавлять только в конец. Основные операции над очередью – такие же, что и над стеком: включение, исключение, определение размера, очистка, обход, чтение. Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Таким образом, дек может быть и стеком, и очередью, и комбинацией этих структур. Наиболее часто дек представляется структурой с ограничением на вход или выход: дек с ограниченным входом (только одна позиция доступна для добавления элемента) и дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека). Стандартные операции над деком: включение элемента справа; включение элемента слева; исключение элемента справа; исключение элемента слева; определение размера; очистка. На практике также используются модификации приведенных структур, например циклическая очередь, замкнутый или кольцевой список и т.п. В таких структурах, как правло последний элемент замыкается указателем на первый (и наоборот, – первый ссылается на последний, при двухсторонней связи), что позволяет рассматривать структуру как замкнутое кольцо. |