| freidom | Дата: Среда, 14.09.2011, 20:45 | Сообщение # 1 |
 Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
|
- Список на Java. С методами:
- int length()
- String nth(int n)
- void insert(int n, String s)
- String delete(int n)
- find (String s) // -1 if not found
- Двусвязный список на Java.
- Очередь на Java. С методами:
- void put(String s);
- String get();
- Очередь на OCaml. С функциями:
- put : 'a queue -> 'a -> 'a
- get : 'a queue -> ('a option * 'a queue)
Это написал Штукенберг, и, по-моему, там ошибка. Или я неправильно переписал. Вероятно, должно быть как-то так:
- put : 'a queue -> 'a -> 'a queue
Кстати, интересен вопрос: почему мы должны реализовать очередь через двусвязные списки, если это прекрасно получается через небольшое расширение односвязных? Достаточно просто хранить отдельным полем указатель на последний элемент списка. Кстати, именно это я и сделал с двусвязными списками.
|
| |
| |
| Jack_WarGunOff | Дата: Вторник, 20.09.2011, 15:37 | Сообщение # 2 |
 Сержант
Группа: Друзья
Сообщений: 34
Статус: Offline
| Хм, а почему все конструкции только со строками? Непорядок, а как же generics? 
Мои варианты:
Список. Класс List в проекте Lists. // Я про него и забыл, сейчас быстренько написал, тесты было делать лень
- static void add(type a,List l) // делает из l a::l
- static void delete(List l) // делает из a::l l
- static int length(List l) // статичен, поэтому длину null'a считает 0 и не вылетает
- type nth(int n) // не статичен, поэтому пустой список(null) корректно работать не будет
Очередь. Класс Queue в проекте Queues.
Методы: // Я уж по старинке, push и pop назвал
- void push(type x)
- type pop()
В самой очереди я храню только ссылки на 1ый и последний элементы, но также есть класс QueueEl, в котором хранятся значение элемента и ссылка на следующий(да, да, это список, я реализовал примерно также, но о том, что это называется список, даже не подумал).
Двусвязный список. Класс DList проекта DLLists(Double Linked Lists).
Здесь я храню текущее значение и ссылки на левый и правый списки. Да, в теории это чудо может быть не совсем двусвязным списком, но, т.к. поля у меня защищенные, такого не случится.
Методы:
- void move_left()
- void move_right()
- static void delete(DList l) // Удаляет текущий элемент и конкатенирует левый и правый списки. По умолчанию указатель идет в левый
- void add_left(type x) // добавляет элемент между текущим и левым. Указатель остается на месте.
- void add_right(type x)
В этом проекте я даже сделал удобную систему для тестов(ну и в Queues, в общем-то тоже) 
OCaml если и будет, то позже.
Aquila non captat muscas - Орлы не ловят мух
|
| |
| |
