Методы программирования
Задание состоит из двух частей, первая из которых обязательна для выполнения, вторую необходимо выполнить для получения отличной оценки. Выполнение обеих частей сводится к созданию односвязного списка и реализации методов добавления элементов в этот список. Срок сдачи задания — 25 сентября.
а. Сортировка чисел при помощи односвязного списка.
Теория
Односвязным списком называется структура данных, построенная следующим образом:
typedef struct _s int data;
struct _s *next;
> s;
В переменной head хранится 0 (список пуст) либо указатель на первый элемент списка. Таким образом, список представляет из себя структуру следующего вида:
Добавление элемента в начало списка производится следующим образом:
s *p = (s *)malloc(sizeof(s));
/* выделение памяти под новый элемент списка */
p->data = 7;
/* присваиваем значение полю данных */
p->next = head;
/* следующий элемент — тот, который ранее был первым, либо 0, если список был пуст */
head = p;
/* теперь наш добавленный элемент — первый */
Для добавления элемента в середину списка необходимо иметь указатель на предыдущий элемент. Обозначив его через q , получаем следующий код:
s *p = (s *)malloc(sizeof(s));
/* выделение памяти под новый элемент списка */
p->data = 7;
/* присваиваем значение полю данных */
p->next = q->next;
/* следующий элемент — тот, который ранее следовал за q (возможно, 0) */
q->next = p;
/* теперь наш новый элемент следует за q */
Для поиска элемента в списке необходимо обойти список в цикле, например, так:
p = head;
while (p) if (p->data == 7) /* сделать необходимые действия */
>
p = p->next;
/* переход на следующий элемент */
>
Второй вариант — аналогичный, но более короткий:
for (p = head; p; p = p->next) if (p->data == 7) /* сделать необходимые действия */
>
>
В обоих случаях переменная p имеет тип s * и является аналогом параметра цикла в обычном понимании.
Для удаления списка и освобождения памяти можно использовать следующий код:
while (head) /* пока список не пуст */
p = head->next;
/* запомнили следующий элемент */
free(head);
/* удалили первый элемент */
head = p;
/* теперь первым является тот, который был следующим */
>
Формулировка задания
Во входном файле input.txt в первой строке находится количество чисел N , в следующих N строках находятся целые числа (тип int ) по одному в строке. Написать две программы, которые выводят в выходной файл output.txt : первая — числа, отсортированные по возрастанию, вторая — числа, отсортированные по возрастанию без повторений.
Примеры
| Ввод: input.txt 7 1 5 2 2 3 3 4 |
Вывод 1: output.txt 1 2 2 3 3 4 5 |
Вывод 2: output.txt 1 2 3 4 5 |
b. * Реализация хэш-таблицы с разрешением коллизий при помощи списков
Теория
Хэш-таблицей называется структура данных, для поиска в которой от ключа вычисляется некоторая функция («хэш-функция»), которая указывает расположения ключа в памяти.
Целью задания является реализация системы хранения переменных и значений. Именем переменной (ключом) является строка размером до 5 символов, значением — целое число. Введем соответствующий тип данных. Поле next предназначено для создания односвязного списка:
typedef struct _variable char name[6];
int value;
struct _variable *next;
> variable;
Будем считать, что количество различных переменных ограничено 1000 . Создадим массив из 2000 (в 2 раза больший) указателей на тип variable . Позаботьтесь о заполнении массива нулями (это будет сделано автоматически, если массив задан вне какой-либо функции).
#define SIZE 2000 variable *table[SIZE];
Создадим функцию, которая по имени переменной будет возвращать значение от 0 до 1999. Например, как показано ниже (этот вариант — далеко не самый лучший):
unsigned int RND[5] = < 3, 11051, 511, 2047, 29 >; /* абсолютно произвольные числа */
unsigned int hash(char *s)
unsigned int res = 0;
for (int i = 0; s[i]; i++) res += s[i] * RND[i % 5];
res %= SIZE;
>
return (res);
>
Ясно, что одно и то же имя переменной будет всегда иметь один и тот же код, возвращаемый функцией hash . В то же время, несколько переменных могут иметь одинаковый код. Значением элемента table[i] будет являться как раз список переменных, имена которых имеют код i .
Теперь, если необходимо найти в таблице переменную с именем s , будем смотреть список, началом (головой) которого является table[hash(s)] . Например, чтобы узнать значение переменной «test» , используем следующий код:
int c = hash(«test»);
variable *p = table[c];
while (p) if (!strcmp(p->name, «test»)) /* нашли; p->value — искомое значение */
break;
>
p = p->next;
>
Формулировка задания
Во входном файле input.txt в первой строке находится количество записей N , в следующих N строках находятся записи вида имя значение , причем имена могут повторяться. В файл output.txt выдать итоговые значения всех переменных в произвольном порядке.
Примеры
| Ввод: input.txt 5 a 10 b 20 a 15 c 25 b 11 |
Вывод: output.txt a 15 c 25 b 11 |
Как добавить элемент в начало списка Python
Чтобы добавить элемент в начало списка, можно воспользоваться методом insert , который вставляет элемент в список перед указанным индексом. Следовательно, в первом параметре нужно указать индекс 0 . Смотрите пример:
lst = [‘ab’, ‘cd’, ‘ef’] lst.insert(0, ’12’) print(lst)
Результат выполнения кода:
[’12’, ‘ab’, ‘cd’, ‘ef’]
С помощью метода оператора +
Вставить элемент в начало списка можно путем его конкатенации с нужным списком. При этом сам элемент должен находиться в квадратных скобках, т.е. представлять собой список, состоящий из одного элемента. Смотрите пример:
lst = [‘ab’, ‘cd’, ‘ef’] print([‘1’] + lst)
Результат выполнения кода:
[‘1’, ‘ab’, ‘cd’, ‘ef’]
С помощью метода extend
Также можно добавить элемент в начало списка из объекта (списка, кортежа, множества), состоящего из одного элемента. Для этого используем метод extend Смотрите пример:
lst1 = [‘ab’, ‘cd’] lst2 = [‘1’] lst2.extend(lst1) print(lst2)
Результат выполнения кода:
Смотрите также
- метод insert ,
который добавляет элемент в список перед указанным индексом - метод extend ,
который добавляет в список элементы из указанного объекта
Как добавить элемент в начало списка c
Контейнер list представляет двухсвязный список, то есть такой список, где каждый элемент имеет указатели на предыдущий и последовательный элемент. Благодаря чему мы можем перемещаться по списку как вперед, так и назад. Для использования списка необходимо подключить заголовочный файл list .
std::list list1; // пустой список std::list list2(5); // список list2 состоит из 5 чисел, каждый элемент имеет значение по умолчанию std::list list3(5, 2); // список list3 состоит из 5 чисел, каждое число равно 2 std::list list4< 1, 2, 4, 5 >; // список list4 состоит из чисел 1, 2, 4, 5 std::list list5 = < 1, 2, 3, 5 >; // список list5 состоит из чисел 1, 2, 4, 5 std::list list6(list4); // список list6 - копия списка list4 std::list list7 = list4; // список list7 - копия списка list4
Получение элементов
В отличие от других контейнеров для типа list не определена операция обращения по индексу или функция at(), которая выполняет похожую задачу.
Тем не менее для контейнера list можно использовать функции front() и back() , которые возвращают соответственно первый и последний элементы.
Чтобы обратиться к элементам, которые находятся в середине (после первого и до последнего элементов), придется выполнять перебор элементов с помощью циклов или итераторов:
#include #include int main() < std::listnumbers< 1, 2, 3, 4, 5 >; int first ; // 1 int last < numbers.back() >; // 5 std::cout std::cout
Размер списка
Для получения размера списка можно использовать функцию size() :
std::list numbers< 1, 2, 3, 4, 5 >; int size = numbers.size(); // 5
Функция empty() позволяет узнать, пуст ли список. Если он пуст, то функция возвращает значение true, иначе возвращается значение false:
std::list numbers< 1, 2, 3, 4, 5 >; if (numbers.empty()) std::coutС помощью функции resize() можно изменить размер списка. Эта функция имеет две формы:
- resize(n) : оставляет в списке n первых элементов. Если список содержит больше элементов, то он усекается до первых n элементов. Если размер списка меньше n, то добавляются недостающие элементы и инициализируются значением по умолчанию
- resize(n, value) : также оставляет в списке n первых элементов. Если размер списка меньше n, то добавляются недостающие элементы со значением value
Изменение элементов списка
Функция assign() позволяет заменить все элементы списка определенным набором. Она имеет следующие формы:
- assign(il) : заменяет содержимое контейнера элементами из списка инициализации il
- assign(n, value) : заменяет содержимое контейнера n элементами, которые имеют значение value
- assign(begin, end) : заменяет содержимое контейнера элементами из диапазона, на начало и конец которого указывают итераторы begin и end
Функция swap() обменивает значениями два списка:
std::list list1< 1, 2, 3, 4, 5 >; std::list list2< 6, 7, 8, 9>; list1.swap(list2); // list1 = < 6, 7, 8, 9>; // list2 = < 1, 2, 3, 4, 5 >;
Добавление элементов
Для добавления элементов в контейнер list применяется ряд функций.
- push_back(val) : добавляет значение val в конец списка
- push_front(val) : добавляет значение val в начало списка
- emplace_back(val) : добавляет значение val в конец списка
- emplace_front(val) : добавляет значение val в начало списка
- emplace(pos, val) : вставляет элемент val на позицию, на которую указывает итератор pos. Возвращает итератор на добавленный элемент
- insert(pos, val) : вставляет элемент val на позицию, на которую указывает итератор pos, аналогично функции emplace. Возвращает итератор на добавленный элемент
- insert(pos, n, val) : вставляет n элементов val начиная с позиции, на которую указывает итератор pos. Возвращает итератор на первый добавленный элемент. Если n = 0, то возвращается итератор pos.
- insert(pos, begin, end) : вставляет начиная с позиции, на которую указывает итератор pos, элементы из другого контейнера из диапазона между итераторами begin и end. Возвращает итератор на первый добавленный элемент. Если между итераторами begin и end нет элементов, то возвращается итератор pos.
- insert(pos, values) : вставляет список значений values начиная с позиции, на которую указывает итератор pos. Возвращает итератор на первый добавленный элемент. Если values не содержит элементов, то возвращается итератор pos.
Функции push_back() , push_front() , emplace_back() и emplace_front() :
std::list numbers< 1, 2, 3, 4, 5 >; numbers.push_back(23); // < 1, 2, 3, 4, 5, 23 >numbers.push_front(15); // < 15, 1, 2, 3, 4, 5, 23 >numbers.emplace_back(24); // < 15, 1, 2, 3, 4, 5, 23, 24 >numbers.emplace_front(14); //
Добавление в середину списка с помощью функции emplace() :
std::list numbers< 1, 2, 3, 4, 5 >; auto iter = ++numbers.cbegin(); // итератор указывает на второй элемент numbers.emplace(iter, 8); // добавляем после первого элемента numbers = < 1, 8, 2, 3, 4, 5>;
Добавление в середину списка с помощью функции insert() :
std::list numbers1< 1, 2, 3, 4, 5 >; auto iter1 = numbers1.cbegin(); // итератор указывает на первый элемент numbers1.insert(iter1, 0); // добавляем начало списка //numbers1 = < 0, 1, 2, 3, 4, 5>; std::list numbers2< 1, 2, 3, 4, 5 >; auto iter2 = numbers2.cbegin(); // итератор указывает на первый элемент numbers2.insert(++iter2, 3, 4); // добавляем после первого элемента три четверки //numbers2 = < 1, 4, 4, 4, 2, 3, 4, 5>; std::list values < 10, 20, 30, 40, 50 >; std::list numbers3< 1, 2, 3, 4, 5 >; auto iter3 = numbers3.cbegin(); // итератор указывает на первый элемент // добавляем в начало все элементы из values numbers3.insert(iter3, values.begin(), values.end()); //numbers3 = < 10, 20, 30, 40, 50, 1, 2, 3, 4, 5>; std::list numbers4< 1, 2, 3, 4, 5 >; auto iter4 = numbers4.cend(); // итератор указывает на позицию за последним элементом // добавляем в конец список из трех элементов numbers4.insert(iter4, < 21, 22, 23 >); //numbers4 = < 1, 2, 3, 4, 5, 21, 22, 23>;
Удаление элементов
Для удаления элементов из контейнера list могут применяться следующие функции:
- clear(p) : удаляет все элементы
- pop_back() : удаляет последний элемент
- pop_front() : удаляет первый элемент
- erase(p) : удаляет элемент, на который указывает итератор p. Возвращает итератор на элемент, следующий после удаленного, или на конец контейнера, если удален последний элемент
- erase(begin, end) : удаляет элементы из диапазона, на начало и конец которого указывают итераторы begin и end. Возвращает итератор на элемент, следующий после последнего удаленного, или на конец контейнера, если удален последний элемент
std::list numbers < 1, 2, 3, 4, 5 >; numbers.pop_front(); // numbers = < 2, 3, 4, 5 >numbers.pop_back(); // numbers = < 2, 3, 4 >numbers.clear(); // numbers =<> numbers = < 1, 2, 3, 4, 5 >; auto iter = numbers.cbegin(); // указатель на первый элемент numbers.erase(iter); // удаляем первый элемент // numbers = < 2, 3, 4, 5 >numbers = < 1, 2, 3, 4, 5 >; auto begin = numbers.begin(); // указатель на первый элемент auto end = numbers.end(); // указатель на последний элемент numbers.erase(++begin, --end); // удаляем со второго элемента до последнего //numbers =
Добавление элемента в начало списка в Python
Часто возникает ситуация, когда требуется добавить элемент в начало списка в Python. Самый популярный метод для работы со списками — append() , позволяет добавить элемент в конец списка. Но что делать, если нужно добавить элемент в начало?
Допустим, есть список чисел:
numbers = [1, 2, 3, 4, 5]
И задача — добавить число 0 в начало этого списка.
Использование метода insert()
Один из способов — использовать метод insert() , который позволяет вставить элемент в указанную позицию. Чтобы добавить элемент в начало списка, необходимо указать позицию 0:
numbers.insert(0, 0)
Теперь список numbers выглядит так:
[0, 1, 2, 3, 4, 5]
Использование оператора сложения
Другой способ — использовать оператор сложения. Python позволяет «складывать» списки, что приводит к их объединению. Это также можно использовать для добавления элемента в начало списка:
numbers = [0] + numbers
Список numbers после выполнения этой операции:
[0, 1, 2, 3, 4, 5]
Оба этих способа эффективны для небольших списков. Однако стоит учесть, что на больших списках они могут быть неэффективны, так как требуют перемещения всех элементов списка.