Структуры данных... так как я их понимаю?

Ответ 1

Вы уже получили некоторые интересные ссылки и идеи. Надеюсь, я могу предложить немного другую точку зрения:

Я научился визуализировать и "любить" структуры данных, научившись тому, что компьютерная память похожа на действительно длинный список. Затем структуры имеют разную компоновку в памяти. Визуализируя структуры в памяти, мне стало очевидно (и интересно), как они работают. Знание макета данных в памяти невероятно важно для программиста, так как сегодня непрерывно растущие машины часто останавливаются путем доступа к памяти. Хорошая компоновка памяти облегчает загрузку данных из памяти, чтобы CPU не ожидал прибытия данных.

Структуры данных - это компоновка данных в памяти. Рассмотрим память как длинный список, как список покупок, но без записей.

0...
1...
2...
3...
4...
5...
6...

Когда вы помещаете структуры в память, они по существу заполняют эти слоты в памяти.

Список очень прост, он просто заполняет список памяти сверху и снизу:

0 Element 0
1 Element 1
2 Element 2
3 Element 3

Хотя иногда вы хотите изменить элемент 2 на что-то другое, может быть, ноль. То, как списки списков работают. Вы можете получить доступ к данным в структуре, зная их индекс (в этом случае 0.. 3).

Стеки разные. Вы можете получить доступ только к "вершине" стека, "нажимая" элемент на вершину или "выбирая" элемент сверху. Pushing означает добавление другого элемента, а старая вершина становится невидимой. Poping означает удаление верхнего элемента, а под ним становится видимым.

0   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
n   [ Hidden data ]
n+1 Element 4

Связанные списки разные. Связанный список содержит указатель (индекс в списке памяти) для данных и один указатель на следующий элемент:

0 Data: Memory index 0x00000100
1 Next: Memory index 6
2 
3 
4 
5 
6 Data: Memory index 104
7 Next: Memory index 8
...
100 Data pointed to from first member
101
102
103
104 Data pointed to from second member

Очередь похожа на более мощный стек, у вас есть доступ как к нижней, так и к верхней. Вы можете только нажимать элементы вверху, и вы можете только поместить элементы снизу.

0 (bottom) Element (ready to be popped)
1 [ Hidden data ]
2 [ Hidden data ]
3 [ Hidden data ]
.
.
.
n (top) (empty, ready to be pushed / be given data)

Визуализируя компоновку каждой структуры данных, они стали намного более очевидными для меня в том, как они требуют памяти и как они действительно работают (также в памяти). Я надеюсь, что мои примеры дадут вам несколько кратких исходных знаний для вас, чтобы основывать свои будущие исследования. В качестве окончательного примера в структурах данных я дам вам несбалансированное двоичное дерево, имеющее следующий порядок вставки элемента: 3, 2, 1, 10, 9, 8, 6, 5, 4, 7

Дерево начинается с адреса памяти 100, поскольку адрес памяти 0 недействителен, и я буду использовать его как "no pointer".

100 Value: "3"
101 Left ptr: 103
102 Right ptr: 109

103 Value: "2"
104 Left ptr: 106
105 Right ptr: 0

106 Value: "1"
107 Left ptr: 0
108 Right ptr: 0

109 Value: "10"
110 Left ptr: 112
111 Right ptr: 0

112 Value: "9"
113 Left ptr: 115
114 Right ptr: 0

115 Value: "8"
116 Left ptr: 118
117 Right ptr: 0

118 Value: "6"
119 Left ptr: 121
120 Right ptr: 127

121 Value: "5"
122 Left ptr: 124
123 Right ptr: 0

124 Value: "4"
125 Left ptr: 0
126 Right ptr: 0

127 Value: "7"
128 Left ptr: 0
129 Right ptr: 0

Надеюсь, что это поможет!

Ответ 2

Вот что помогло мне больше всего... Поскольку вы визуальный человек, Google некоторые визуализированные алгоритмы сортировки, обходы деревьев, хэширование и т.д., Чтобы получить общее представление о том, что происходит. После этого попробуйте сделать простую программу, используя разные структуры, и поэкспериментируйте с различными перестановками из них - возможно, например, вы можете создать связанный список, а затем сделать его круговым связанным списком, а затем сделать его дважды связанным списком, затем сделайте его дважды круговым связанным списком и так далее...

Вам просто нужно поэкспериментировать со структурами, и, как вы это делаете, вы начнете видеть, какие структуры данных подходят для приложений, которые вы будете разрабатывать.

Вот несколько хороших ссылок для вас. Алгоритмы сортировки: http://www.sorting-algorithms.com/ Обходы дерева: http://nova.umuc.edu/~jarc/idsv/lesson1.html Обход графика: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html

Что касается эффективности (большой анализ O), то он придет к вам более или менее естественным образом, как только вы поймете, что происходит на алгоритмическом уровне каждой операции структуры данных.

Одна вещь, на которую мой университет подчеркивает, - это разработка собственной реализации структур данных (которая восходит к восходящему) без погружения в предварительно установленные шаблоны С++ (обучение сверху вниз). Сделав это с нуля, вы действительно понимаете накладные расходы, связанные с вставкой, удалением, поиском (перемещением) и доступом к данным из определенной структуры, и это поможет вашей интуиции при проектировании системы в будущем.

Ответ 3

Практика, практика, практика.

Первый совет, который у меня есть для вас, должен стать как можно более опытным на С++.

Структуры данных и программирование - это две разные темы. Если вы столкнетесь с программированием, маловероятно, что вы сможете понять структуры данных.

Как вы овладеете С++? Практика, практика, практика. Программируйте все. Узнайте все, что вы можете о нем. Напиши десятки небольших программ. Все, что вы можете сделать, чтобы стать комфортно с С++.

Если вы освоитесь на С++, я заверяю вас, что структура данных станет проще. (Заметьте, что я не сказал легко, я сказал проще:))

Ответ 4

Ключ к изучению структур данных - это начать с чего-то малого, а затем основываться на этом. Начнем с простой структуры C:

struct Person {
  char name[100];
  int age;
};

Эта структура данных представляет собой человека. Вам нужно убедиться, что вы понимаете простые концепции структуры, такие как эти, и затем вы можете перейти к более крупным вещам.

Когда вы начинаете говорить о структурах данных, таких как стеки и очереди, например, сначала попытайтесь понять концептуально, что делает структура данных. Например, с помощью стека мы используем принцип LIFO, то есть Last In First Out. В очереди мы используем принцип FIFO (сначала первый).

А потом там тот, который отправляет много людей, связанный список. Вам нужно хорошо понимать указатели для этого, поэтому, прежде чем пытаться решить связанные списки, начните с чего-то простого:

int* x;
int y = 10;
x = &y;

Вы должны иметь возможность посмотреть на этот код и сразу узнать, что он делает. Если вы не можете, то вы не готовы перейти к более продвинутым структурам данных, таким как связанные списки.

Главное, что я пытаюсь сделать, - это то, что вам нужно, чтобы основывались на холоде, а затем основывались на них. Также важно не отставать от класса очень старательно, спросить своего учителя или преподавателя, есть ли у вас проблемы, и следить за тем, чтобы вы были на ходу каждую неделю и не отставали.

Классы компьютерных наук очень похожи на классы математики, каждая неделя обычно основывается на всем, что вы узнали из предыдущих N недель. Поэтому, если вы не понимаете ключевую концепцию, например, указатели, то у вас будет большая борьба за оставшуюся часть семестра.

Ответ 5

Мне нравится dcp answer.

Лучший способ обернуть голову вокруг структур данных - написать мини-примеры. Даже если вы скопируете их из своей книги, если вы можете заставить их работать и компилироваться, и вы набрали их своими пальцами, вы узнаете много.

Когда вы читаете свою книгу и после каждой лекции напишите кратчайшие программы, которые вы можете создать и использовать (отображение, использование и т.д.) структуру данных, о которой вы только что узнали.

Затем, когда вам нужно выполнять свои фактические задания, вы узнаете еще больше, когда пытаетесь взять мини-примеры и подключите их к решению проблем с назначением.

Я думаю, что писать кратчайший/наименьший возможный фрагмент рабочего кода для отдельных структур данных очень полезен. Кроме того, не бойтесь копировать код (для вашего собственного наставления, а не для вашего обращения). Если вы копируете, набирая и не копируя вставку, вы в конечном итоге много учитесь, так как это заставляет вас посмотрите на каждый символ в коде.

Если целые структуры данных выглядят "слишком много", чтобы обернуть голову, начните с написания мини-примеров компонентов структур данных. Поэтому сохраните название книги с указателем. Затем сохраните многие названия книг с указателями на указатели. Прочитайте название книги с квадратной скобкой и арифметикой указателя. Используйте рекурсию в простых функциях, где ясно, что происходит..... Например, рекурсия для отображения факториала числа проще обернуть вокруг вас, чем рекурсия, чтобы показать двоичное дерево (на мой взгляд).....

Вы увидите, в чем состоят ваши проблемные области, и попытайтесь изолировать их как можно меньше и конкретнее, а затем напишите как короткую программу, с которой вы можете справиться с этой проблемной областью. а затем создайте.

Ваши лекции посвящены целым структурам данных... гигантским облачным банкам Cummulus теории.... так что, по сути, они сверху вниз. Изолирование небольших проблем синтаксиса и использования в мини-проблемах происходит снизу вверх. Так что ваш учитель помогает атаковать сверху, вы атакуете снизу, практикуя, и довольно скоро там ничего нет в середине!

Ответ 6

Единственный способ осмысленно изучить структуры данных и алгоритмы - увидеть их применительно к реальным проблемам и использовать их для решения реальных проблем. Кодирование их в рабочие приложения - даже если они надуманные - укрепит теоретические знания, так что у вас будет больше шансов сохранить идеи и интегрировать их в ваш личный подход к решению проблем.

Ответ 7

Я бы рекомендовал получить хорошую книгу по алгоритмам ( "Введение в алгоритмы" Cormen и др. было бы моей рекомендацией). Через книгу вы будете разрабатывать и использовать разные структуры данных, и вы, скорее всего, поймете, для чего каждая структура хороша. Структуры данных полезны только как средство достижения другой цели: решение конкретной проблемы.

В зависимости от того, сколько времени у вас есть или вы хотите потратить на него, вы можете попытаться получить проблемы от различных конкурсов программирования, таких как ACM ICPC. Большинство проблем потребуют от вас знания. Обратите внимание, что как алгоритмы, так и структуры данных являются агностиками языка, поэтому, если вы хорошо знаете какой-либо другой язык, просто используйте его.

Ответ 8

На мой взгляд, эти вещи лучше изучаются на рабочем месте или через опыт, чем в теории. В большинстве случаев, в то время как я был в школе, работая трудно оставаться впереди кривой была важная часть, которую я думаю, что похож на тот опыт, который вы пережили. Хотя похвально, что вы хотите понять это полностью, до тех пор, пока вы знаете, где найти хороший справочный материал, когда вам это нужно, курс достиг своей цели.

Большинство классов будут основываться на знаниях, которые вы приобрели в прошлых классах. Вы снова столкнетесь с этими деталями в своих исследованиях, и ваши профессора должны быть в состоянии помочь вам применить то, что вы узнали в прошлом, к вашей текущей работе. Как интерактивный ученик, офисные часы, стажировки и возможности для наставников кажутся лучшими способами получения необходимой информации.

Удачи!

Ответ 9

Одна вещь, которую вы всегда должны помнить, заключается в том, что структуры данных не просто существуют. Они были изобретены, чтобы соответствовать потребностям, что означает, что они хороши по некоторым причинам, но не для других.
Узнайте, каковы эти причины, какова структура данных, и попытайтесь выяснить Big O для операций, прежде чем вам скажут. Всегда сравнивайте структуры данных. Даже с простейшим из них - массив. Возьмите это как отправную точку и сравните каждую структуру данных, которую вы найдете в массиве. Иногда вы найдете небольшие трюки, которые помогут вам избежать использования большой структуры данных в целом.
Для меня то, что помогло мне понять множество структур данных и алгоритмов, было апплетами здесь, и я надеюсь, что это тоже поможет: Апплет

Ответ 10

Если вы можете визуализировать реализацию структур данных в реальной жизни или решать проблемы с реальной жизнью, тогда вам будет легче понять.

Вот несколько

• FIFO Linked List - это диск в McDonalds
• Связанный список LIFO - стопка обеденных тарелок
  • Поиск и сортировка - это rolodex (если вы стары, что вы действительно видели одну из этих вещей)

Ответ 11

Вот вам хорошая статья, чтобы вы начали: http://www.codeproject.com/KB/cpp/linked_list.aspx. Начните с простого связанного списка. Это очень легко, и вы поймете это намного проще, чем другие структуры данных. Стеки и очереди, возможно, концептуально еще проще, но они основаны на простом связанном списке. Затем вы можете перейти к двойным связанным спискам и деревьям. С нетерпением ждем ваших вопросов по кодированию, Удачи!:)

Ответ 12

Если вы являетесь визуальным учеником, попросите своего инструктора для получения дополнительных диаграмм. Вы можете попросить других студентов, если вы сможете учиться вместе с ними. Возможно, один из них может объяснить вам вещи таким образом, чтобы вы могли легче понять.

Ответ 13

Хороший ресурс NIST словарь алгоритмов и структур данных. Вы не собираетесь садиться и запоминать всю эту информацию, и вы не должны использовать ее, чтобы не кодировать свои собственные структуры, что полностью аннулирует ценность класса, но этот сайт служит отличной ссылкой, поскольку он связывает структуры данных с алгоритмами, которые их используют, а также показывает некоторые варианты, которые дают представление о том, как вы можете изменять структуры для других целей.

Надеюсь, что это поможет. Удачи.

Ответ 14

Я помню свой первый курс структур данных. Я помню, что я был сначала перегружен.

Я был скорее визуальным учеником. Чтобы лучше понять материал, он действительно помог увидеть фотографии. Раньше я делал шаги по вставке, удалению и итерации через структуры данных, такие как связанный список или очередь. Перед тем, как я закончил, у меня появилось много бумаги, но это стоило того.

Как только я начал рисовать процесс вставки и что не замечал, переход к фактическому программированию структуры данных был намного проще.

Возможность визуализации того, что происходило в памяти, действительно помогла. И, как говорили другие передо мной: практика, практика, практика!

Это большая часть успеха.

Удачи!

Ответ 15

Не уверен, что это какая-то помощь, действительно, но это может быть несколько обнадеживающим.

Я был в той же лодке, когда я взял Data Structures 4 года назад. Я прошел через класс с достаточным количеством знаний, чтобы пройти и получить B, по крайней мере, в классе, хотя я не очень его понял.

Я не понимал шаблонов, связанных списков, указателей 'this' и действительно не понимал указателей в целом, что тоже хорошо, что сильно мешало моим способностям. Я чудесным образом сделал то, что требовалось на домашнем задании и тестах (хотя результаты тестов были все еще низкими для всех, и мой учитель закончил их изгибы) и закончил с B.

После этого я продолжил несколько лет на других занятиях. Я обнаружил, что в этих классах изучались разные концепции, которые помогли мне лучше понять их. Алгоритмы больше рассказывали о сортировке и Big O, Ассамблея больше рассказывала о том, что происходит "под капотом" компьютера, что помогло мне понять указатели и т.д.

Я понял второй в прошлом семестре моего пятого года, что я в значительной степени знал все концепции из Data Structures, и я даже не потратил никаких дополнительных усилий на их изучение, по крайней мере, не с точки зрения возвращения и попыток особенно для понимания структур данных, если это имеет смысл.

Без каких-либо реальных усилий я запустил создание шаблона, связанного списка стека и очереди для нескольких домашних заданий в операционных системах, и я их понял. Это оттолкнуло меня. Я уверен, что для вас это будет одинаково. Дайте ему время и сосредоточьтесь на других классах, и все это щелкнет. Казалось, что навсегда навсегда зацепиться за меня, но это произошло.

Надеюсь, что это поможет.

Ответ 16

Честно говоря, я сам программист на С++ (с моей основной ссылкой - код общедоступного кода Source game engine от Half-Life 2), и я многое узнал о том, что привело меня через Data Structures, составив диаграмм и комментариев и кода чтения.

Возможно, я просто вундеркинд или что-то в этом роде, потому что мне всегда казалось, что это относительно легко для меня, но я узнал за много времени, потраченного на чтение, размышление и анализ того, какими могут быть конкретные применения каждой структуры, и почему каждая структура существует как нечто отдельное от других структур данных в первую очередь.

Написав несколько серьезных проектов кода (т.е. Connect Four и простреливающий космический шутер, а также 3D-изометрические плоттеры и программы 2D-рисования) на сильно ограниченном калькуляторе TI-83 Plus в старшей школе (ps, используя TI -Basic, а не Assembly), я понял, какие операции были более эффективными, и я понял, насколько ограничена встроенная система списков (базовый вектор) для хранения данных в определенных ситуациях. Я также выяснил, как Big-O работал, когда я пытался синхронизировать время выполнения программы с разными размерами входов.

Практикуйте, думайте о вещах, как вы их делаете, и пытайтесь выяснить, как и почему они работают, и никогда не бойтесь спускаться и пакаться при тестировании. В конце концов, что такое наука без экспериментов?

Ответ 17

Когда я преподавал программирование, я всегда направлял книги Demystified своим ученикам.

Я предлагаю вам прочитать:
- Структуры данных Demystified
- Ооп демистифицированный

Эти две книги хорошо справляются с разбивкой структур данных и принципом ООП в простых простых для чтения условиях, с легкостью следовать примерам. Это хороший обзор, но он не входит в структуры данных, предоставляемые STL.

Ответ 18

Дональд Кнут "Искусство компьютерного программирования" , том 1.

Ответ 19

Практически, я нахожу, что структуры данных требуют четкого понимания указателей и памяти.

Например, вы должны быть в состоянии понять, почему ниже связанный список не работает менее чем за минуту.

Но, чтобы понять, почему это не работает, вы должны понять, как память выложена на C и С++, и интуитивно понять концепцию указателя.

Некоторые люди любят картинки и рисуют картины. Другие люди любят смотреть MIT OpenCourseware - я рекомендую попробовать хотя бы попробовать.

class node
{

  int data;
  node* next;

  node* addnode()
  {
    node newnode;
    this->next = &newnode;

    return &newnode;
  }
};

Это приблизительная (связанная с ошибкой) реализация связанного списка, который я написал около 10 лет назад, когда я изучал структуры данных.

И, как последнее замечание, практика и теория - это инь и ян качественного программиста/разработчика/компьютерного ученого. Вы не можете быть действительно опытными без них.

Ответ 20

Если у вас проблемы с O-нотацией, то "Введение в алгоритмы" Cormen et.al. вводит эти теоретические концепции в легко понятном стиле. Ну, эта книга в основном является библией для базовых структур данных. Доказательства границ времени выполнения/пространства всегда представлены очень поучительно.

Как всегда, если вы изучаете такую ​​книгу, не просто читайте ее, но и старайтесь работать над большинством упражнений. Обычно это очень эффективно для изучения материала.

Еще одна общая техника: попробуйте присоединиться к местной исследовательской группе из 2-3 других учеников - обычно, обсуждая материал с другими (лицом к лицу) и, пытаясь объяснить самоанализируемый материал для сверстников, дает вам много подсказки, которые вам нужно охватить больше.

Чтобы освоить С++ для упражнений, "Язык программирования С++" Stroustrup дает хорошее представление и ссылки на различные языковые концепции. Так как С++ - такой язык с несколькими парадигмами, новички часто путают то, что на самом деле фактически используют на практике для решения определенных проблем. Чтобы помочь с этим "Эффективным С++" Скоттом Майерсом, это хорошее начало.

Если ваш курс сильно использует STL, тогда есть "Эффективный STL". Стиль письма Скотта Майерса обычно считается очень "подходящим" для начинающих.

Ответ 21

Для меня лучшая книга, которую я нашел (до сих пор) для понимания структур данных, - Стивен Скиена Руководство по разработке алгоритмов.
Помимо первого алгоритма анализа алгоритмов, алгоритмов и структур данных вторая часть абсолютно бесценна в поиске (или, по крайней мере, сужении) правильной структуры данных/алгоритма решения проблемы.