LCME Суббота, 18.11.2017, 14:44
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: anatoliy 
Форум » Домашние задания » Программирование » Домашнее задание от 14.09 (Структуры данных: список, двусвязный список, очередь)
Домашнее задание от 14.09
freidomДата: Среда, 14.09.2011, 20:45 | Сообщение # 1
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: 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



Кстати, интересен вопрос: почему мы должны реализовать очередь через двусвязные списки, если это прекрасно получается через небольшое расширение односвязных? Достаточно просто хранить отдельным полем указатель на последний элемент списка. Кстати, именно это я и сделал с двусвязными списками.
Прикрепления: myList.java(2Kb) · Java_Queue.zip(2Kb) · queue.ml(0Kb)
 
Jack_WarGunOffДата: Вторник, 20.09.2011, 15:37 | Сообщение # 2
Сержант
Группа: Друзья
Сообщений: 34
Репутация: 6
Статус: Offline
Хм, а почему все конструкции только со строками? Непорядок, а как же generics? poor
Мои варианты:

Список. Класс 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, в общем-то тоже) smile

OCaml если и будет, то позже.
Прикрепления: Lists.7z(2Kb) · Queues.7z(3Kb) · DLLists.7z(3Kb)


Aquila non captat muscas - Орлы не ловят мух
 
Форум » Домашние задания » Программирование » Домашнее задание от 14.09 (Структуры данных: список, двусвязный список, очередь)
Страница 1 из 11
Поиск:

Copyright Freidom © 2017 Хостинг от uCoz