|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
24.05.2015, 01:11 | #1 |
Пользователь
Регистрация: 19.10.2014
Сообщений: 49
|
Уважаемые форумчане,помогите пожалуйста. Попал я значит в беду.Прошли мы динамич.структуры данных,вернее, только списки лин. односвязные.По этой теме мы все получили задачи. Сейчас вы услышите моё отчаяние...У всех кроме меня задача плана: "Упорядочить список по возрастанию значения поля записи info"...
А мне дали вот такую задачу:" Пусть имеется N городов и задан список пар городов (i,j),между которыми существует прямая дорога.Напечатайте список городов ,которые напрямую сообщаются более чем с тремя городами." И да,я скажу честно.Я понятия не имею как её решать,не знаю даже с какого бока подойти.После рытья интернета я понял,что здесь что-то связано с графами и матрицой смежности.И вроде как я понял, это все должно быть в виде дерева? В общем помогите пожалуйста чем сможете.Хотя бы скажите как и в виде чего мне все это хранить.Я правда понятия не имею.Или может я не нашел какой-нибудь ресурс ,где есть разбор аналогичных задач.... Буду очень благодарен любой помощи. И все-таки не могу я понять,с какого бока подходить к этой задаче,как вообще её решать с помощью односвязного списка.Как хранить связь между городами ,(дан список пар городов). Это что дерево должно быть?Или что?Подскажите пожалуйста,уже неделю не могу её решить.Всем в моей группе дали примитивные задачи типа :"Упорядочить список по возрастанию значения поля info". А мне эту ,так я копал интернет и понял,что это вроде как через матрицу смежности должно решаться,но мы такого нигде ещё не проходили.На лекциях и практики были разбор только примитивных задач.Моя большая проблема в том,что я не понимаю,как это все хранить.Я буду очень признателен,если кто-нибудь сказал,а лучше бы показал как всю эту информацию хранить в списке...Алгоритм поиска городов,которые напрямую связаны не менее чем с тремя я попробую придумать сам.Мне правда очень нужна Ваша помощь.Помогите пожалуйста. P.s. Мне не лень решать задачи,я всегда подхожу к этому делу с интересом,но тут я стою на мертвой точке. Я даже к преподу подходил,но она мне толком и не смогла ничего сказать,только покивала,что-то на счет матрицы смежности. Просто я не могу понять,как хранить исходные данные ,вот я пытался на листке делать примерно так: Дано: 4 города например. Будем их так и называть: Город 1,город 2 и т.д А вот связь между ними: 1 2 1 4 2 4 3 4 И как эти пары мне в динамич. структуры запихнуть,если честно я вижу здесь 4 односвязных лин. списка или я что-то не понимаю... Из 1 -> 2 - >4 это ещё терпимо,но как мне из 2->4 и 3->4 загнать в единый целый список,дерево или что ещё может быть? В общем полный тупик и непонимание этой задачи... Последний раз редактировалось Stilet; 24.05.2015 в 06:53. |
24.05.2015, 01:50 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,322
|
Первое, что пришло в голову:
Считываем пары городов и помещаем в один линейный список, причем упорядочиваем номера городов в паре по возрастанию и при добавлении проверяем, что такой пары в списке еще не было. Затем N раз проходим по списку, чтобы выяснить, со сколькими городами связан i-й город. Второе: Заводим N списков и при считывании пары (i, j) в i-й список помещаем j-й город и наоборот, проверяя, что такого города еще нет в рассматриваемом списке. Затем выводим те города, соответствующие списки которых достаточно длинны.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 24.05.2015 в 01:52. |
24.05.2015, 02:12 | #3 |
Пользователь
Регистрация: 19.10.2014
Сообщений: 49
|
То есть,во втором варианте мы грубо говоря будем иметь матрицу примерно такого вида:
В - Волгоград , М - Москва , О - Орёл , Л - липецк Сама матрица будет я так понимаю из списков? Например первый элемент матрицы это список Head->|В,next|->|M,next|->Nill ? (В,М) (В,О) (М,О) (В,Л) Или я что то не понял, как то не могу вот это немного предстасить : "пары (i, j) в i-й список помещаем j-й город и наоборот". Вот у нас i-й список,мы ввели пару городов (М,В), мы берем и передвигаем указать на след. элемент,в нашем случае запись ->|Москва|->nill . А в j-й список |Волгоград| -> nill? То есть в матрице будет в (i,j) элемете храниться два разных списка ?Но что будет дальше как-то не могу понять. Допустим вводим след пару городов (В,Л) i-й : -> |Липецк| ->nill j-й : ->|Волгоград|->nill И тут мы сравниваем,если (i,j) = (j,i) ,хотя мне кажется я какой-то бред написал |
24.05.2015, 02:35 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,322
|
Пусть есть 3 города: 0; 1; 2
Соответствующие списки (массив списков): nil; nil; nil Подаются пары городов: (0, 1) Списки: 1->nil; 0->nil; nil (1, 2) Списки:1->nil; 0->2->nil; 1->nil (2, 1) Списки: не изменились, так как в списке 1го уже есть 2й город, в списке 2го - 1й И т.д.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
24.05.2015, 11:13 | #5 |
Пользователь
Регистрация: 19.10.2014
Сообщений: 49
|
спасибо большое.
А если бы мы добавили вместо (2,1) пару городов (2,4), то получилось бы: Списки: 1-> nil; 0->2->nil; 2-> nil; 0->2->4-> nil ? А Ваш первый вариант представляет собой : Пусть есть 3 города: 0; 1; 2 и список:nil; Подаются пары городов: (0,1) 0->1-nil (1,2) 0->1->2->nill Я так понял? Последний раз редактировалось Neostat; 24.05.2015 в 11:38. |
24.05.2015, 12:46 | #6 | ||
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,322
|
Цитата:
Во-вторых, номер 4го города должен был попасть в список 2го. То есть, списки выглядели бы так: 1->nil; 0->2->nil; 1->4->nil; nil; 2->nil (список 3го города пуст) Цитата:
(0, 1) Список: (0, 1) -> nil (0, 2) Список: (0, 1) -> (0, 2) -> nil (2, 1) Список: (0, 1) -> (0, 2) -> (1, 2) -> nil Элемент списка - пара чисел, а не одно число. UPD Пожалуйста
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 24.05.2015 в 23:10. |
||
24.05.2015, 22:51 | #7 |
Пользователь
Регистрация: 19.10.2014
Сообщений: 49
|
Все понял,ещё раз огромное спасибо.Извините за то,что так тупил.Оказывается я не так понял условие. Теперь все понятно.
|
24.05.2015, 23:16 | #8 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Первый вариант классный. Я сразу о 2-Ом подумал.
Можно тогда его еще сортануть и совсем ляпота выйдет. За один проход ответ получим |
24.05.2015, 23:26 | #9 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,322
|
Poma][a, чтобы за 1 проход получить ответ, придётся, пожалуй, сохранять в список не дорогу, а направление, то есть помещать в список пары (i, j) и (j, i). Тогда после сортировки легко будет определяться количество дорог (выходящих из города направлений).
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 24.05.2015 в 23:29. |
24.05.2015, 23:33 | #10 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Я именно это и имел в виду, видимо, я не совсем правильно прочитал Ваш вариант, пардон
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
задача по предмету алгоритмы и структуры данных | 3Doleg | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 01.10.2013 12:21 |
Задача Pascal на динамические структуры данных | Citromon | Помощь студентам | 10 | 16.04.2012 09:08 |
задача по теме Динамические структуры данных в Паскале | Klik_1602 | Помощь студентам | 0 | 04.01.2011 00:58 |
задача по динамич. программированию | Morsha | Помощь студентам | 4 | 02.12.2010 22:55 |
Проблема при создании списков(динамич. структуры) через отдельную функцию(вне main) | Aerial | Общие вопросы C/C++ | 1 | 22.09.2010 22:39 |