Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 121, средняя оценка - 4.88
Diplomat
0 / 0 / 0
Регистрация: 11.06.2011
Сообщений: 33
#1

Связанные списки - C++

15.06.2012, 13:53. Просмотров 18104. Ответов 44
Метки нет (Все метки)

Составить программу, работающую со связанными списками. Мы будем рассматривать связанный список как объект, содержащий связанный список данных и операций (методов), которые вы можете с ними выполнять. Связанный список данных состоит из указателей на начало («голову») и конец («хвост») связанного списка (в нашем примере из-за его гибкости используется двунаправленный связанный список). Каждый элемент связанного списка представляет собой реализацию отдельного объекта. Возможности, необходимые для использования связанного списка, предоставляют следующие операции:
• создание связанного списка (выделение для него памяти);
• уничтожение связанного списка (освобождение используемой памяти);
• инициализация связанного списка;
• деинициализация связанного списка;
• вставка элемента в середину списка перед существующим элементом;
• присоединение элемента к концу связанного списка;
• удаление элемента из связанного списка;
• возвращение первого элемента связанного списка;
• возвращение последнего элемента связанного списка.
Необходимо иметь в виду, что создание и инициализация, а также уничтожение и деинициализация методов — это не синонимы. При создании и уничтожении методы create и destroy выделяют и освобождают память для объекта (связанного списка), а методы инициализации и деинициализации initialize и deinitialize только инициализируют и деинициализируют ранее выделенные экземпляры объекта. Вы можете видеть, как объект связанного списка наследуется объектами стека или очереди, поскольку очередь и стек можно реализовать как связанный список с ограниченным числом операций. Например, можно реализовать очередь в виде связанного списка, в котором элементы могут добавляться к концу и извлекаться из начала. Если вы таким образом реализуете очередь, то нужно запретить наследуемые методы связанного списка, которые для очереди недопустимы (например, вставку в середину списка).

Добавлено через 2 часа 22 минуты
По ходу никто не сможет помочь
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2012, 13:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Связанные списки (C++):

связанные списки - C++
плиз помогите написать задачку: Запросить у пользователя число n. Построить связный список из n элементов, заполненный случайными...

Связанные списки - C++
Вопросы в комментариях #include <iostream> #include <conio.h> #include <string.h> using namespace std; class NameDataSet { ...

Связанные списки - C++
Здравствуйте! Не очень сложное задание, но так как я начинающий, запуталась немного... особенно с указателями и ссылками. В общем...

Связанные списки С++ - C++
Здравствуйте, изучаю С++ и возникли проблемы с пониманием как работают списки. Вот код: #include <cstdio> #include <cstdlib> ...

Связанные списки (переделать программу) - C++
Как переделать программу, чтобы можно было вводить самому ключи и не было Access Violation? #include <iostream> #include <time.h> ...

Односвязанные и двух-связанные списки - C++
Должны быть следующие функции: 1) Ввод количества элементов и заполнение списка случайными значениями 2) Вывод списка на экран 3)...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BumerangSP
4286 / 1408 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 02:23 #16
alsav22, я просто чуть исправил готовую функцию. Это односвязный линейный список, не очередь.
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 02:42 #17
Цитата Сообщение от Sher_vud Посмотреть сообщение
alsav22 спасибо, я понял суть метода, но вот механизм пока не удается осмыслить.
запутался в этих строках:
else rear -> next = newlink; // если список не пустой, то в конец
rear = newlink; // rear конец списка
Два указателя first и rear. Один указывает на начало списка, другой на конец. Сначала оба на NULL. Создаётся новый элемент, на него указывает newlink. Если список пустой, то значение newlink присваивается указателю на начало списка - first. Это произойдёт одни раз. В следующие разы заход будет уже только в else. То есть first в дальнейшем меняться не будет, и он будет указывать на начало списка. В первый раз else пропускается, после него указателю rear присваивается значение newlink, то есть, пока элемент в списке один, начало и конец списка совпадают. При добавлении следующего элемента заход только в else. После этого элемент, который до этого был в конце списка, будет содержать указатель на добавляемый элемент (rear -> next = newlink), а rear присваивается адресс нового элемента (rear = newlink), т.е. новый элемент становится концом списка, адресс которого находится в rear.

Добавлено через 6 минут
Цитата Сообщение от BumerangSP Посмотреть сообщение
Это односвязный линейный список, не очередь.
Я и имел ввиду список. Просто в разных источниках это всё по разному называется, где очередь, где список. Односторонняя очередь, двусторонняя. Односвязанный список, двусвязанный список. Сути это не меняет. Я не спорю, просто поясняю. Тут можно увязнуть в определениях.
0
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 02:47 #18
Цитата Сообщение от alsav22 Посмотреть сообщение
В первый раз else пропускается, после него указателю rear присваивается значение newlink
alsav22 спасибы, наконец то дошло. я видимо пересидел уже.. смотрел и представлял:
C++
1
2
3
4
5
else  
{
rear -> next = newlink; 
rear = newlink;
}
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 03:08 #19
Хитрость этой конструкции в том, чтобы при первом проходе выполнилось только rear = newlink; , а при втором и далее - и rear -> next = newlink;, и rear = newlink;
0
BumerangSP
4286 / 1408 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 12:24 #20
Просто в разных источниках это всё по разному называется, где очередь, где список
alsav22, это да. Но у меня именно односвязный список Просто делая функцию, я ни о каком другом виде не думал. И, опять же: будь это очередь, ее элементы при выборке исчезали бы (как в стеке или деке). Исправьте, если неправ.
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 13:45 #21
Цитата Сообщение от BumerangSP Посмотреть сообщение
Но у меня именно односвязный список
И у меня. Мне кажется, тут дело в определениях. Чем, собственно, отличается список от очереди я точно не знаю. Есть ли, вообще, точные определения? Если почитать первый пост:
...Вы можете видеть, как объект связанного списка наследуется объектами стека или очереди, поскольку очередь и стек можно реализовать как связанный список с ограниченным числом операций. Например, можно реализовать очередь в виде связанного списка, в котором элементы могут добавляться к концу и извлекаться из начала. Если вы таким образом реализуете очередь, то нужно запретить наследуемые методы связанного списка, которые для очереди недопустимы (например, вставку в середину списка)...
, то получается, что очередь - это один из видов списка, в котором запрещено применение некоторых методов (например, вставка в середину списка). Или наоборот: список - частный вид очереди. Сути это не меняет. Задана некая последовательность, с определёнными свойствами и методами. И это надо реализовать. Я так понимаю. А как это называть, можно договориться, или создать определения, если их нет. Повторяю, может они и есть, но я точно не знаю.
0
BumerangSP
4286 / 1408 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 14:07 #22
alsav22, односвязный - это значит у него один указатель (на следующий элемент).
очередь - это один из видов списка, в котором запрещено применение некоторых методов (например, вставка в середину списка). Или наоборот: список - частный вид очереди.
Скорей очередь, как частный вид. У очереди (если опустить всевозможные реализации на основе списков и т.д.) принцип FIFO, (первый пришёл — первый вышел). Как раз функция добавления именно такая. И у очереди, конечно, есть указатель на конец. А у моего списка нет. Поэтому он и оказался нерациональным))
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 14:46 #23
Цитата Сообщение от BumerangSP Посмотреть сообщение
Скорей очередь, как частный вид.
Может быть.
Цитата Сообщение от BumerangSP Посмотреть сообщение
И у очереди, конечно, есть указатель на конец.
Получается, что не только у очереди. Из первого поста:
Цитата Сообщение от Diplomat Посмотреть сообщение
Связанный список данных состоит из указателей на начало («голову») и конец («хвост») связанного списка
Цитата Сообщение от BumerangSP Посмотреть сообщение
У очереди (если опустить всевозможные реализации на основе списков и т.д.) принцип FIFO
Почему это надо опускать? Если очередь на основе списков, то это уже, по вашему, не очередь?

Видите, во что разговор превращается? Или есть точные определения (некий стрндарт) и тогда на них можно сослаться, или каждый трактует, как ему больше нравится.
0
BumerangSP
4286 / 1408 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 14:49 #24
alsav22, можно википедию почитать про очередь. Реализации есть конечно, но, по сути, у очередей есть свои "обязанности". Как по мне, если при просмотре элементов в очереди оные не удаляются, то это уже не очередь, а частный случай списка.
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 14:57 #25
Цитата Сообщение от BumerangSP Посмотреть сообщение
Поэтому он и оказался нерациональным))
Насчёт рациональности. Ваш код - одна из реализаций списка с одним указателем на начало, и по принципу: последний в конец. Мне кажется, что сама по себе такая реализация не рациональна. Представьте, что список очень большой и при каждом добавлении нового элемента будет пребор всех элементов списка, только чтобы найти конец. Напрашивается решение, чтобы просто был указатель на конец списка. Не согласны?
0
BumerangSP
4286 / 1408 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 15:00 #26
alsav22, согласен, почему нет? Повторюсь, я не стал дорабатывать функцию, а только исправил, ТС именно это нужно было
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 15:04 #27
Цитата Сообщение от BumerangSP Посмотреть сообщение
Как по мне, если при просмотре элементов в очереди оные не удаляются, то это уже не очередь, а частный случай списка.
Вот с этим я точно не согласен. Я таких очередей не встречал, что именно при просмотре происходило удаление. В чём смысл такой очереди? STL, queue, dequeue ? Это из литературы:
0
Миниатюры
Связанные списки  
BumerangSP
4286 / 1408 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 15:08 #28
alsav22, да, ей вполне присущи все вышеперечисленные функции. Ее даже просмотреть можно, только при этом заведя вторую очередь и перекидывая в нее выбранные из первой элементы. Потом перекинуть все содержимое опять в первую.
Вот из вики:
О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
И нас так учили.

Цитата из этой статьи на cyberguru
http://cyberguru.ru/pascal/turbopasc...ia-page21.html
Если значение указателя свободного места совпадает со значением указателя выбираемого элемента, то это означает, что в очереди нет событий. Следует помнить, что хотя функция выборки элемента из очереди в действительности не нарушает информацию в очереди, повторный доступ к ней невозможен и фактически она исчезает.
0
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 16:11 #29
Цитата Сообщение от BumerangSP Посмотреть сообщение
да, ей вполне присущи все вышеперечисленные функции. Ее даже просмотреть можно, только при этом заведя вторую очередь и перекидывая в нее выбранные из первой элементы. Потом перекинуть все содержимое опять в первую.
Если это про скрин, то вот ещё. И если эта очередь так организованна, то и просматривается она как связанный список, без всякого перекидывания.

Цитата Сообщение от BumerangSP Посмотреть сообщение
выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
Вы же не слово выборка употребили, а просмотр. С ним я и не согласился. Выборка здесь - это убрать из очереди.
0
Миниатюры
Связанные списки   Связанные списки  
alsav22
5419 / 4815 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 16:26 #30
И ещё насчёт просмотра. queue из STL как можно просмотреть? Разве только перебрасывая? Но ведь это классическая очередь.

Добавлено через 5 минут
Соглашусь, что очередь - вид связанного списка. FIFO, добавление только в конец, удаление только из начала. Реализация к понятию не относится.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 16:26
Привет! Вот еще темы с ответами:

Подскажите как отладить код (связанные списки) - C++
условие закомментировано в коде, подскажите, в чём ошибка? функция Sum Должна возвращать требуемое число // ВЫЧИСЛЯЕТ СУММУ ТЕХ ЭЛЕМЕНТОВ...

Списки, как склеить списки между собой? - C++
Ребят, привет всем, есть код, в классе которого описаны несколько методов: добавление элемента в список, удаление и просмотр списка, дак...

Связанные классы - C++
Есть несколько классов,каждый объект которого имеет объект другого класса в качестве элемента данных Это класс Dictionary,в состав...

Ошибки связанные с wininet - C++
Здравствуйте. Проект выглядит так: #include "stdafx.h" #include <windows.h> #include <stdio.h> #include <fstream> #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.09.2012, 16:26
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru