[Powered by Google Translate] [Раздел 6: менее комфортно] [Nate Хардисон] [Harvard University] [Это CS50.] [CS50.TV] Хорошо. Добро пожаловать в раздел 6. На этой неделе мы собираемся говорить о структурах данных в разделе в первую очередь потому, что проблема на этой неделе установлены на spellr делает целый букет различных исследований структуры данных. Есть множество различных способов, вы можете пойти с проблемой набора, и более структур данных вы знаете о, тем больше интересных вещей можно сделать. 

Итак, давайте начнем. Сначала мы поговорим о стеки, стека и очереди структур данных, которые мы собираемся поговорить. Стеки и очереди действительно полезны, когда мы начинаем говорить о графиках, которые мы не собираемся делать так много сейчас. Но они очень хорошо понимают одной из крупных фундаментальных структур данных CS. Описание в спецификации поставленной задачи, если вы потяните его вверх, говорит о стеки сродни Куча столовой лотки, которые у вас есть в столовой за обеденным залам где, когда обеденный персонал приходит и ставит столовой лотков после они очищают их, они складывают их одна на другую. А потом, когда дети приходят, чтобы получить пищу, они тянут с лотков, сначала верхнюю, а затем один ниже его, то тот, что ниже. Так что, по сути, первый лоток, обеденный персонал положил является последней, которая получает сняты. Последним, что сотрудники столовой поставить на первое один, который получает сняты на ужин. В спецификации поставленной задачи, которые вы можете скачать, если вы этого еще не сделали, мы говорим о моделировании stucture стека данных с помощью такой структуры. 

Итак, что мы имеем здесь, это похоже на то, что была представлена ​​в лекции, кроме лекции мы представили это с целыми, а не символ * с. Это будет стек, который хранит и что? Дэниел? Что мы хранению в этом стеке? [Даниил] строк? >> Мы хранения строк в этом стеке, это точно. Все, что вам нужно иметь для того, чтобы создать стек представляет собой массив конкретной мощности, которая в данном случае, мощности будет во всех заглавных буквах, потому что это постоянно. И тогда в дополнение к массиву, все мы должны отслеживать это текущий размер массива. Одна вещь, чтобы отметить здесь, что это круто является то, что мы создаем сложены структуры данных на другую структуру данных, массив. Существуют различные способы реализации стеков. Мы не будем делать этого совсем еще, но, надеюсь, после выполнения связанного списка проблем, Вы увидите, как вы можете легко реализовать стек поверх связанного списка, а также. Но сейчас, мы будем придерживаться массивов. Итак, еще раз, все что нам нужно это массив, и мы просто необходимо отслеживать размер массива. [Сэм] Извините, почему это, что вы сказали, что стек находится на вершине строки? Мне кажется, что строки в стеке. [Хардисон] Да. Мы создаем, мы берем наш массив структуры данных - это большой вопрос. Таким образом, вопрос, почему, для людей, которые наблюдают за этим в Интернете, Поэтому мы говорим, что стек в верхней части строки, потому что здесь она выглядит как строки внутри стека? Который полностью деле. То, что я имел в виду, что у нас есть структуры массива данных. У нас есть массив символов * с, это массив строк, и мы собираемся добавить к этому, чтобы создать стек структуры данных. 

Таким образом, стек немного более сложным, чем массив. Мы можем использовать массив для создания стека. Так вот, когда мы говорим, что стек построен на вершине массива. Точно так же, как я сказал ранее, мы можем построить стек на начало связанного списка. Вместо того чтобы использовать массив для хранения наших элементы, мы могли бы использовать связанный список для хранения наших элементы и построить стек вокруг этого. Давайте рассмотрим несколько примеров, глядя на код, чтобы увидеть, что на самом деле здесь происходит. На левом, я бросил, что это стек структура будет выглядеть в памяти если емкость была # определяется как четыре. У нас есть наши четыре элемента массив символов *. У нас есть строки [0], строк [1], строк [2], струны [3], а затем, что в прошлом пространство для нашего размера целого числа. Имеет ли это смысл? Хорошо. Это то, что произойдет, если то, что я делаю на правую, который будет свой код, это просто объявить структуру, сложены структура называется с. Это то, что мы получаем. Она устанавливает этот след в памяти. Первый вопрос, вот то, что является содержанием этого стека структуры? Сейчас они ничего, но они не вполне ничего. Они такого мусора. Мы понятия не имеем, что в них. Когда мы объявляем стек S, мы просто бросали вниз, что в верхней части памяти. Это вроде как объявление Int я, а не его инициализации. Вы не знаете, что там. Вы можете прочитать, что там, но она не может быть супер полезным. Одна вещь, которую вы хотите всегда помнить, чтобы сделать это инициализировать все, что необходимо инициализировать. В этом случае, мы собираемся, чтобы инициализировать размер равным нулю, потому что это обернется очень важно для нас. Мы могли бы пойти дальше и инициализировать все указатели, все символ S * чтобы быть понятными некоторые значения, вероятно, нулевой. Но это не совершенно необходимо, чтобы мы это делаем. 

Теперь две основные операции по стеки? Кто-нибудь помнит из лекции, что вы делаете со стеками? Да? [Stella] Нажатие и хлопать? >> Именно так. Нажатие и появляются две основные операции по стеки. И что же толчок делать? >> Это ставит что-то на верхнем из стека, а затем хлопок снимает его. [Хардисон] Именно так. Таким образом, нажав толкает что-то на вершине стека. Это похоже на столовую персонала положить столовую поднос на столе. И появляются принимает столовой лоток из стека. Давайте рассмотрим несколько примеров того, что происходит Когда мы толкать вещи в стек. Если бы мы были нажать на строку "привет" на наш стек, это то, что наша схема будет выглядеть сейчас. Посмотрите, что происходит? Мы выдвинули на первый элемент нашего массива строк и мы увеличили количество наших размером равным 1. Таким образом, если мы посмотрим на разницу между двумя горками, здесь был 0, то вот перед толчком. Вот после толчка. Перед нажатием, после толчка. И теперь у нас есть один элемент в нашем стеке. Это строка "привет", и это все. Все остальное в массиве, на наш массив строк, еще мусор. Мы не инициализации. Скажем, мы нажимаем другую строку на наш стек. Мы собираемся нажать "мир" на этот раз. Таким образом, вы можете видеть "мир" здесь идет сверху "привет", и размер отсчет идет до 2. Теперь мы можем нажать "CS50», и что пойду на вершине снова. Если мы вернемся, вы можете увидеть, как мы нажатии вещи на вершине стека. А теперь мы перейдем к поп-музыки. Когда мы зашли что-то из стека, что случилось? Никто видите разницу? Это довольно тонкий. [Студент] размера. >> Да, размер изменился. 

Что бы вы еще ожидали изменить? [Студент] строк, тоже. >> Праве. Строк тоже. Оказывается, что, когда вы делаете это таким образом, потому что мы не копируя элементы в нашем стеке, Мы на самом деле не нужно ничего делать, мы можем просто использовать размер отслеживать количество вещей в нашем массиве так что, когда мы всплывал снова, снова, мы просто уменьшаем нашу размером до 1. Там нет необходимости на самом деле пойти и переписать все. Вид обалденный. Получается, что мы обычно просто оставить вещи в покое, потому что это меньше работы для нас. Если мы не должны вернуться и переписать что-то, то зачем это делать? Поэтому, когда мы дважды всплывал из стека, все, что делает уменьшения размера пару раз. И опять же, это только потому, что мы не копировать вещи в нашем стеке. Да? Идем дальше. [Студент, неразборчиво] >> И что происходит тогда, когда вы нажимаете опять что-то? Когда вы нажимаете опять что-то, где оно девается? Куда оно девается, Василий? >> В строки [1]? >> Праве. Почему они не идут в строки [3]? [Василий], потому что забыл, что было что-то в строке [1] и [2]? [Хардисон] Именно так. Наш стек, по сути, "забыл", что он держался за что-то в строке [1] или строк [2], поэтому, когда мы нажимаем "Woot», он просто ставит, что в элемент строки [1]. Есть ли вопросы о том, как это работает, на базовом уровне? [Сэм] Так что это не динамический в любом случае, с точки зрения количества или в терминах размера стека? [Хардисон] Именно так. Это - Дело в том, что это не было динамически growning стека. Это стека, который может содержать не более четырех символов * с, не более четырех вещей. Если бы мы были, чтобы попытаться подтолкнуть 1/5 вещь, что вы думаете должно произойти? [Студенты, неразборчиво] [Хардисон] Именно так. Есть целый ряд вещей, которые могут случиться. Это могло сегментам вина, в зависимости от того, что мы были - как именно мы осуществляли заднем конце. Это может перезаписать. Он мог бы иметь, что переполнение буфера, что мы говорили в классе. Что было бы наиболее очевидные вещи, которые могут быть перезаписаны если бы мы пытались протолкнуть лишняя вещь на нашем стеке? Таким образом, вы упомянули переполнения буфера. Что может быть то, что бы получить письменное более или растоптал если мы переполнены случайно, пытаясь подтолкнуть лишняя вещь? [Даниил, неразборчиво] >> Возможно. Но на начальном этапе, что может случиться? Что, если мы пытались протолкнуть 1/4 вещь? Это может переписать размер, по крайней мере, с этой памятью схеме, что у нас есть. 

В описании множества проблем, что мы и собираемся реализации сегодня, то, что мы хотим сделать, это просто возвращение ложным. Наши метода принудительной собирается вернуть логическое значение, и что логическое значение будет истинным, если толчок успешно и ложно, если мы не можем выдвинуть ничего больше, потому что стек переполнен. Давайте рассмотрим немного, что код прямо сейчас. Вот наш толчок функции. Наши толчок функции для стека собирается взять в строке положить на стек. Он собирается вернуться верно, если строка была успешно вытеснили в стеке, а в противном случае. Любые предложения о том, что может быть хорошим первое, что нужно делать здесь? [Сэм] Если размер равен мощностью затем вернуться ложным? [Хардисон] Bingo. Хорошая работа. Если размер имеет потенциал, мы собираемся вернуться ложным. Мы не можем поместить больше ничего в нашем стеке. В противном случае, мы хотим положить что-то на вершине стека. Что такое "вершину стека," изначально? [Даниил] Размер 0? Размер >> 0. Что такое вершине стека после есть одна вещь, в стеке? Мисси, вы знаете? [Missy] One. >> Размер один, точно. Вы продолжайте добавлять к размеру, и каждый раз, когда вы помещаете в новый элемент на размер индекса в массиве. Мы можем сделать это с такой один-лайнер, если это имеет смысл. Итак, мы получили наш массив строк, мы собираемся получить к нему доступ на размер индекса, и мы только собираемся, чтобы сохранить наш символ * в там. Обратите внимание, что там нет строки копирование происходит здесь, нет динамического распределения памяти? А потом Missy воспитывали, что мы сейчас должны сделать, потому что мы хранить строку в соответствующее место в массиве, и она сказала, что мы должны были увеличивать размер одного, так что мы готовы для следующего толчка. Таким образом, мы можем сделать это с s.size + +. На данный момент, мы втолкнули в нашем массиве. Что это последнее, что мы должны делать? [Студент] Вернуться правда. >> Вернуться правда. Так что это довольно простой, очень простой код. Не слишком много. После того как вы обернуты вокруг головы, как стек работает, это довольно просто реализовать. 

Теперь, следующая часть этого появляются строки из стека. Я собираюсь дать вам, ребята некоторое время, чтобы работать над этим немного. Это почти по существу, обратное тому, что мы сделали здесь, в толчке. Что я сделал на самом деле - ой. Я загрузился прибора здесь, и в прибор, Я поднял проблемы установить 5 спецификации. Если мы увеличим здесь, мы можем видеть, что я нахожусь на cdn.cs50.net/2012/fall/psets/pset5.pdf. Разве вы, ребята, скачал этот код, что находится здесь, section6.zip? Хорошо. Если вы еще не сделали этого, сделайте это прямо сейчас, очень быстро. Я сделаю это в моем окне терминала. Я действительно сделал это здесь. Да. Да, Сэм? >> У меня есть вопрос о том, почему ты сказал s.string 'ы скобках размер = ул? Что такое СТО? Разве что определенная где-то раньше, или - о, в символ ул *? [Хардисон] Да, именно так. Это был аргумент. >> Ну, ладно. Извините. [Хардисон] Мы указанием строки нажать дюйма Другой вопрос, что может придумать, что мы действительно не говорим о здесь был Мы считали само собой разумеющимся, что у нас была эта переменная с , который был по своим масштабам и доступным для нас. Мы считали само собой разумеющимся, что было с этим стеком структуры. Таким образом, оглядываясь на этот толчок код, Вы можете видеть, что мы делаем вещи с этой строки, которые получили прошло в но потом все внезапно, мы доступе s.size, вроде бы, откуда ей пришел? В коде, который мы собираемся посмотреть в разделе Архив , а затем вещи, которые вы будете делать в вашей проблеме устанавливает, мы сделали наш стек строим глобальную переменную так что мы можем иметь доступ к нему во всех наших различных функций без необходимости вручную передавать его и передать его по ссылке, делать все в таком же роде к нему. Мы просто обманывает немного, если хотите, чтобы сделать вещи лучше. И это то, что мы здесь делаем, потому что это для удовольствия, это проще. Часто, вы увидите, люди делают это, если они имеют один большой структуры данных который эксплуатируется в рамках своих программ. 

Давайте вернемся к приборе. У каждого успешного получить section6.zip? Все распаковать его с помощью распаковать section6.zip? Если вы зайдете в раздел 6 каталогов - ааа, повсюду - и вы перечислите то, что здесь, вы видите, что у вас есть три разных. с файлами. У вас есть очереди, SLL, который является односвязный список, и стек. Если вы откроете stack.c, Вы видите, что у нас есть эта структура определена для нас, точные структуры, который мы только что говорили в слайдах. У нас есть наши глобальные переменные для стека, Мы получили наш толчок функции, а то у нас есть наша поп-функции. Я поставлю код отодвинуть на слайде здесь, но то, что я хотел бы вам, ребята, чтобы сделать это, в меру ваших возможностей, пойти и реализации поп-функции. После того как вы реализовали его, вы можете скомпилировать это с делать стек, , а затем запустить результирующий исполняемый стек, и что будет работать все это тестовый код сюда, это в основном. А главное заботится о деле делает толчок и поп-звонки и убедившись, что все идет через все в порядке. Он также инициализирует размер стека прямо здесь так что вам не придется беспокоиться о том, что инициализация. Можно предположить, что это было правильно инициализирован К тому времени, доступ к нему в поп-функции. Имеет ли это смысл? Таким образом, здесь мы идем. Там в толчок код. Я дам вам, ребята 5 или 10 минут. И если у вас есть какие-либо вопросы в промежуточном то время как вы кодирования, Пожалуйста, попросите их вслух. Так что если вы получите камень преткновения, просто спросите. Позвольте мне знать, пусть все остальные знают. Работа с вашим соседом тоже. [Даниил] Мы просто осуществлении поп прямо сейчас? >> Просто поп-музыки. Хотя Вы можете скопировать реализации толчок, если вы хотите так что тестирование будет работать. Потому что это трудно проверить вещи попасть в - или, трудно проверить появляться вещи из стека, если нет ничего в стек с самого начала. 

Что такое поп должно быть возвращение? Элемент из вершины стека. Он должен получить элемент с вершины стека , а затем уменьшать размер стека, и теперь вы потеряли элемент на вершине. И тогда вы вернетесь элемент на вершине. [Студент, неразборчиво] [Хардисон] Что случится, если вы это сделаете? [Студент, неразборчиво] Что в итоге происходит это вы, вероятно, доступ либо Элемент, который не был инициализирован, так что ваш расчет , где последний элемент выключен. Так вот, если вы заметили, в толчке, мы доступе строк в элементе s.size потому что это новый индекс. Это новая вершина стека. Если в поп, s.size будет следующий пространстве, пространство, которое находится на вершине всех элементов в стеке. Таким образом, самый верхний элемент не в s.size, но, скорее, это под ним. 

Другая вещь, чтобы сделать, когда вы - в поп, это у вас есть для уменьшения размера. Если вы помните, вернемся к нашей маленькой диаграмме прямо здесь, на самом деле, единственное, что мы видели, происходит, когда мы называли поп- было то, что этот размер упала, сначала в 2, то к 1. Потом, когда мы выдвинули новый элемент, он пойдет на на должном месте. [Василий] Если s.size равно 2, то не было бы перейти к элементу 2, и вы хотите, чтобы всплывал этот элемент прочь? Таким образом, если мы пошли в - >> Итак, давайте посмотрим на это еще раз. Если это наш стек на данный момент и мы называем поп, , при котором индекс самого верхнего элемента? [Василий] В 2, но это будет поп-3. >> Праве. Так вот, где наш размер 3, но мы хотим, чтобы совать элемент с индексом 2. Это очень типичный вид на единицу, что у вас с нулевой индексации массивов. Итак, вы хотите, чтобы совать третий элемент, а третий элемент не с индексом 3. И поэтому мы не должны делать это минус 1, когда мы нажатия происходит потому, что прямо сейчас, вы заметите, что самый верхний элемент, если бы мы были выдвинуть что-то еще в стек на данный момент, Мы хотели бы, чтобы подтолкнуть ее с индексом 3. И так уж случилось, что размер и индексы выстраиваются, когда вы нажимаете. 

У кого есть рабочая реализации стека? У вас есть рабочий стек один. Есть ли у вас поп рабочие еще? [Даниил] Да. Я так думаю. >> Программа работает, а не сегментам разломов, это распечатка? Есть ли распечатать "успех" при запуске? Да. Сделать стек, запустить его, если он печатает «успех» и не идет бум, то все хорошо. Хорошо. Давайте перейдем к устройству очень быстро, и мы пройдем через это. Если мы посмотрим на то, что происходит здесь с поп- Daniel, что было первое, что вы сделали? [Даниил] Если s.size больше 0. [Хардисон] Хорошо. А зачем вы это сделали? [Даниил] Чтобы убедиться в том, что что-то внутри стека. [Хардисон] Верно. Вы хотите, чтобы проверить, чтобы убедиться, что s.size больше 0; в противном случае, что вы хотите, чтобы произошло? [Даниил] Return нуль? >> Вернуться нулевой, это точно. Так что, если s.size больше 0. Тогда что же мы будем делать? Что мы будем делать, если стек не пуст? [Stella] Вы уменьшите размер? >> Вы уменьшения размера, все в порядке. Так как же вы это сделаете? >> S.size--. [Хардисон] Великий. А то, что ты сделал? [Stella] И тогда я сказал возвращения s.string [s.size]. [Хардисон] Великий. В противном случае вы вернетесь нулевой. Да, Сэм? [Сэм] Почему она не должна быть s.size + 1? [Хардисон] плюс 1? >> Да. >> Есть. [Сэм] Я думал, потому что вы принимаете 1 из, то вы будете возвращаться не тот, что они просили. [Хардисон] И это было именно то, что мы говорим о целом с этим вопросом от 0 индексов. Поэтому, если мы масштаб здесь. Если мы посмотрим на этого парня прямо здесь, вы можете увидеть, что когда мы поп, Мы появляться элемент с индексом 2. 

Таким образом, мы снижаем наш размер, а затем наш размер соответствует нашему индексу. Если мы не уменьшаем размер, а затем мы должны сделать размер -1, а затем декремента. Великий. Все хорошо? Есть вопросы по этому поводу? Есть много разных способов, чтобы написать это, а также. В самом деле, мы можем сделать что-то еще - мы можем сделать один-лайнер. Мы можем сделать одну линию возврата. Таким образом, мы действительно можем уменьшать прежде чем мы вернемся на этом. Таким образом, положив - до s.size. Это делает линию очень плотный. Где разница между -. С размером и s.size-- что это постфикс - они называют это постфикс, потому что - приходит после s.size-- означает, что s.size оценивается для целей нахождения индекса как в настоящее время, когда эта линия будет выполнена, и тогда это - происходит после строки запускается на выполнение. После того, как элемент s.size индекс доступен. И это не то, что мы хотим, потому что мы хотим декремент произойдет в первую очередь. Othewise, мы будем получать доступ к массиву, по сути, вне закона. Мы собираемся получать доступ к элементу выше той, что мы на самом деле хотим получить доступ. Да, Сэм? >> Это быстрее и использует меньше памяти, чтобы в одной строке или нет? [Хардисон] Честно говоря, это действительно зависит. [Сэм, неразборчиво] >> Да, это зависит от обстоятельств. Вы можете сделать компилятор трюки чтобы получить компилятор признать, что, как правило, я полагаю. 

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

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

Но на данный момент, давайте двигаться дальше, и давайте поговорим об очередях. Прокрутите здесь. Очередь близко родственный стека. Таким образом, в стеке, вещи, которые были введены в последнем были первыми вещами, чтобы потом быть восстановлена. У нас есть последний вошел, первый вышел, или ЛИФО, заказа. В то время как в очереди, как вы ожидали бы от того, когда вы стоите в очереди, Первым человеком, встать в очередь, первым делом, чтобы попасть в очередь, это первое, что получает извлекается из очереди. Очереди также часто используется, когда мы имеем дело с графиками, о которой мы говорили кратко стеки, и очередей также удобны для кучу других вещей. Одна вещь, которая приходит часто пытается поддерживать, например, отсортированный список элементов. И вы можете сделать это с помощью массива. Вы можете поддерживать отсортированный список вещей в массиве, однако там, где становится сложно тогда у вас всегда есть, чтобы найти соответствующее место, чтобы вставить следующую вещь. Так что если у вас есть массив чисел, от 1 до 10, и вы хотите расширить, что для всех чисел от 1 до 100, и вы получаете этих цифр в произвольном порядке и пытались держать все отсортировано как вы идете через, вы в конечном итоге приходится делать много передач. При некоторых типах очередей и некоторых видов базовых структур данных Вы можете фактически держать его довольно просто. Вы не имеете что-то добавить, а затем перераспределит все это каждый раз. Также вы должны сделать много смещение внутренних элементов вокруг. Когда мы смотрим на очереди, вы видите, что - и в queue.c в разделе кода - Структура, которую мы дали вам действительно похожа на структуру, которую мы дали вам за стека. 

Там в одно исключение из этого, и что за одним исключением является то, что у нас есть это дополнительные целое число, называемое головой, и голова здесь для отслеживания голове очереди, или первый элемент в очереди. С стек, мы смогли отслеживать элемент, который мы собирались получить, или на вершине стека, используя только размер, в то время как с очередью, мы иметь дело с противоположных концов. Мы пытаемся трека вещи на конце, а затем вернуть вещи с фронта. Таким образом, эффективно, с головой, у нас есть индекс начала очереди, и размер дает нам индекс конца очереди так что мы можем получить вещи из головы и добавить вещи на хвосте. В то время как со стеком, мы были только когда-либо дело с вершины стека. Мы никогда не имели доступа к нижней части стека. Мы только добавили вещи на верхние и взял вещи с верхней так что нам не нужно, что дополнительные поля внутри нашей структуры. Значит ли это вообще смысл? Хорошо. Да, Шарлотта? [Charlotte, неразборчиво] [Хардисон] Это большой вопрос, а что было одно, что пришли в лекции. Может быть, идя через несколько примеров проиллюстрировать, почему Мы не хотим, чтобы использовать строки [0] в качестве главы очереди. 

Итак, представьте, что у нас есть очередь, мы будем называть его очередь. В начале, когда мы только что создан он, когда мы только объявили его, мы не инициализирован ничего. Это все фигня. Поэтому, конечно, мы хотим убедиться, что мы инициализируем и размер, и глава поля равно 0, то разумно. Мы также могли бы пойти дальше и обнулять элементы в нашей очереди. А чтобы эта схема подходит, заметил, что теперь наша очередь может иметь только трех элементов; в то время как наш стек может провести четыре, наша очередь может иметь только три. И это только чтобы сделать схему нужным. Первое, что здесь происходит, что мы постановки в очередь строки "привет". И так же, как мы это делали со стеком, ничего не страшно здесь по-другому, мы бросаем строки, по крайней строки [0] и увеличиваем наш размер на 1. Мы постановки в очередь "до свидания", она будет надеть. Так это выглядит как стопка по большей части. Мы начали здесь, новый элемент, новый элемент, размером продолжает идти вверх. Что происходит в этот момент, когда мы хотим что-то из очереди? Когда мы хотим из очереди, которая является элементом, который мы хотим из очереди? [Василий] струнных [0]. >> Zero. Совершенно верно, Василий. Мы хотим, чтобы избавиться от первой строки, на этот раз, "привет". Так что же другая вещь, которая изменилась? Обратите внимание, когда мы что-то выскочил из стека, мы просто изменили размер, но здесь, у нас есть пара вещей, которые меняются. Не только изменить размер, но глава изменений. Это возвращаясь к точке Шарлотты ранее: почему мы должны это голова, а? Имеет ли смысл сейчас, Шарлотта? >> Вроде того. [Хардисон] Вид? Так что же произошло, когда мы из очереди? Что же глава сделать это сейчас интересно? [Charlotte] О, потому что она изменилась - все в порядке. Понимаю. Потому что голова - где голова указывает на изменения в плане расположения. Это уже не всегда нулевого индекса. >> Да, именно так. То, что произошло, если dequeueing высокого элемента было сделано, и у нас не было этой главы поля потому что мы всегда называл эту строку в 0 индекс глава нашей очереди, тогда мы должны перейти остальные очереди вниз. Мы должны перейти "до свидания" из из строк [1] ​​строки [0]. И строк [2] вплоть до строки [1]. И мы должны сделать это, чтобы весь список элементов, Весь массив элементов. И когда мы делаем это с помощью массива, который получает очень дорого. Так вот, это не имеет большого значения. Мы просто должны трех элементов в массиве. Но если у нас была очередь из тысяч элементов или миллион элементов, а затем все внезапно, мы начинаем делать кучу из очереди называет все в цикле, вещи действительно собирается замедляться, как он перекладывает все вниз постоянно. Вы знаете, переложить на 1, сдвиг на 1, сдвиг на 1, сдвиг на 1. Вместо этого, мы используем эту голову, мы называем это "указатель", хотя это не совсем указатель В строгом смысле, это не тип указателя. Это не Int * или символ * или что-нибудь подобное. Но это указания или с указанием главы нашей очереди. Да? 

[Студент] Как йедиеие знать, чтобы просто палить все, что в голову? [Хардисон] Как йедиеие знаю, как палить все это в голове? >> Да, да. >> Что она смотрит на только что голова поле установлено. Таким образом, в первом случае, если мы посмотрим прямо здесь, наши головы равна 0, индекс 0. >> Праве. [Хардисон] Так что это просто говорит, хорошо, хорошо, элемент с индексом 0, строка "привет", является элементом во главе нашей очереди. Таким образом, мы собираемся из очереди этого парня. И это будет элемент, который получает вернулись к абоненту. Да, Саад? >> Так глава в основном задает - где вы собираетесь индексировать? Вот начало этого? >> Да. >> Хорошо. [Хардисон] Это становится новым началом для нашего массива. Итак, когда вы что-то из очереди, все что вам нужно сделать, это получить доступ к элементу по индексу q.head, и это будет элемент, который вы хотите из очереди. Вы также должны уменьшать размер. Мы увидим в бит, где все становится немного сложнее с этим. Мы из очереди, и теперь, если мы вновь поставить в очередь, где же мы поставить в очередь? Где следующего элемента пойти в нашей очереди? Скажем, мы хотим поставить в очередь строки "CS". В какой индекс он пойдет? [Студенты] струнных [2]. Два >>. Почему 2, а не 0? [Василий] Потому что сейчас голова 1, так что похоже на начало списка? [Хардисон] Верно. А что обозначает конец списка? Что мы используем для обозначения конца нашей очереди? Голова глава нашей очереди, в начале нашей очереди. Что в конце нашей очереди? [Студенты] Size. >> Размер, точно. Таким образом, наши новые элементы пойти, по крайней размер, и элементы, которые мы взлетаем оторваться на голову. Когда мы постановки в очередь на следующий элемент, мы помещаем его в в размерах. [Студент] Перед тем, как положить, что в, хотя, размер составлял 1, верно? [Хардисон] Верно. Так что не совсем по размеру. Размер +, а не +1, но + голова. Потому что мы перешли все по голове суммы. Так вот, теперь у нас есть очереди размером 1, который начинается с индексом 1. Хвост индекс 2. Да? 

[Студент] Что происходит, когда вы из очереди строки [0], и строки 'слотов памяти просто получить опустели, в основном, или просто забыли? [Хардисон] Да. В этом смысле, мы просто забыли их. Если бы мы были хранения копий их - многие структуры данных часто хранят свои собственные копии элементов так что человек управляет структурой данных не нужно беспокоиться о том, где все эти указатели собираются. Структура данных выполняется на всем, проводит на всех копиях, чтобы убедиться, что все сохраняется должным образом. Тем не менее, в данном случае, эти структуры данных только для простоты, не делаем копии всего, что мы хранении в них. [Студент] Так это непрерывный массив -? >> Да. Если мы оглянемся на то, что определение было этой структуры, это так. Это всего лишь стандартный набор, как вы видели, массив символов S *. Значит ли это -? >> Да, мне было просто интересно если вы в конечном итоге запустить из памяти, в определенной степени, если у вас есть все эти пустые места в вашем массиве? [Хардисон] Да, это хорошая точка. 

Если мы посмотрим на то, что произошло сейчас в этой точке, мы заполнили наши очереди, как он выглядит. Но мы действительно не заполнены нашими очереди потому что у нас очередь это размер 2, но он начинается с индекса 1, потому что там наши головы указатель. Как вы говорили, что элемент строки [0], индекс 0, на самом деле не существует. Это не в нашей очереди больше. Мы просто не потрудились пойти и переписать его, когда мы его из очереди. Поэтому, даже если это выглядит как мы запускаем из памяти, мы на самом деле не имеют. Это место доступно для нас, чтобы использовать. Соответствующее поведение, если бы мы пытались и первый из очереди что-то нравится "до свидания", что бы поп свидания с. Теперь наша очередь начинается с индексом 2 и имеет размер 1. И теперь, если мы будем пытаться поставить в очередь опять что-то, скажем, 50, 50 должны идти в это место с индексом 0 потому что он по-прежнему доступны для нас. Да, Саад? [Саад] Значит ли это происходить автоматически? [Хардисон] Это не происходит совершенно автоматически. Вы должны сделать математику чтобы заставить его работать, но по сути то, что мы сделали, мы только обернутый вокруг. [Саад] И это хорошо, если это имеет отверстие в середине этого? [Хардисон] Это если мы можем сделать математику работать должным образом. 

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

Что произойдет в этот момент, если бы мы из очереди опять что-то? Любые мысли? Что будет с головой? Что должно произойти в голову если бы мы из очереди что-то еще? Голова прямо сейчас с индексом 2, Это означает, что глава очередь строк [2]. [Студент] Какой возвращает 0? >> Она должна возвращать 0. Следует обернуть вокруг спины, точно. До сих пор, каждый раз, когда мы звонили из очереди, мы были добавив к нему один в голову, добавить к голове, добавьте один в голову, добавьте один в голову. Как только что голова указатель попадает на последний индекс в массиве, Затем мы должны обернуть его обратно к началу, вернитесь к 0. [Charlotte] Что определяет способность очереди в стеке? [Хардисон] В этом случае, мы просто использовали # определена постоянная. >> Хорошо. [Хардисон] В реальной. Файл C, вы можете пойти и сбросить с нее немного и сделать это как большой или как мало, как вы хотите. [Charlotte] Итак, когда вы делаете это очереди, как вы делаете компьютеру знаю насколько большой Вы хотите, чтобы стек быть? [Хардисон] Это большой вопрос. Есть несколько способов. Одним из них является просто определить его передняя и сказать, что это будет очереди, которая имеет 4 элемента или 50 элементов или 10.000. Другой способ сделать то, что люди, хакер издание делает и создать функции, чтобы ваша очередь динамично расти, как другие вещи добавляются дюйма 

[Charlotte] Так, чтобы пойти с первым вариантом, какой синтаксис вы используете указать программе, что размер очереди? [Хардисон] Ah. Итак, давайте из этого. Я все еще в stack.c здесь, так что я просто хочу, чтобы прокрутить до самого верха здесь. Вы можете увидеть это прямо здесь? Это # определить емкость 10. И это почти точно такой же синтаксис, который мы имеем для очереди. За исключением очередь, мы получили, что дополнительное поле структуры здесь. [Charlotte] О, я думал, что мощность означает способность к строке. [Хардисон] Ah. >> Что это максимальная длина слова. >> Есть. Да. Емкость здесь - это отличная точка. И это нечто, что сложно потому что мы объявили здесь массив символов S *. Массив указателей. Это массив символов. Это, наверное, то, что вы видели, когда вы были ваши объявления буферов для файлового ввода / вывода, когда вы создавали строки вручную в стеке. Однако то, что мы имеем здесь представляет собой массив символов S *. Так что это массив указателей. На самом деле, если мы масштаб, и мы посмотрим, что тут происходит В презентации, вы видите, что фактические элементы, характер данных не хранится в массиве себя. Что хранится в нашем массиве здесь являются указателями на символьные данные. Хорошо. Таким образом, мы видели, как размер очереди такой же, как со стеком, Размер всегда с уважением относится к числу элементов в настоящее время в очереди. После того, как 2 ставит в очередь, размер 2. После того, как из очереди размере Сейчас 1. После того, как другой постановки в очередь Размер обратно до 2. Так что размер, безусловно уважает число элементов в очереди, , а затем голову просто держит на велосипеде. Это идет от 0-1-2, 0-1-2, 0-1-2. И каждый раз, когда мы называем из очереди, руководитель получает указатель увеличится к следующему индексу. И если голова собирается переходить, он возвращается назад около 0. Так с этим, мы можем написать функцию из очереди. И мы собираемся оставить функцию постановки в очередь для вас, ребята, а не для реализации. 

Когда мы из очереди элемента из нашей очереди, то, что было первое, что сделал Даниил, когда мы начали писать поп-функции для стеков? Дай мне услышать от кого-то, кто не говорил еще. Давайте посмотрим, Саад, ты помнишь, что Даниэль сделал так, как первое, что когда он писал поп? [Саад] Там было, это было - >> Он испытал что-то. [Саад] Если размер больше, чем 0. >> Именно так. И то, что было, что тестирование на? [Саад] Это было испытание, чтобы посмотреть, есть ли что-нибудь внутри массива. [Хардисон] Да. Именно так. Таким образом, вы не можете поп что-нибудь из стека, если она пуста. Кроме того, вы не можете ничего из очереди из очереди, если она пуста. Что такое первое, что мы должны сделать в нашей йедиеие функции здесь, как вы думаете? [Саад] Если размер больше 0? >> Да. В этом случае, я на самом деле просто проверял, чтобы увидеть, если она равна 0. Если он равен 0, мы можем вернуться нулевой. Но точно такая же логика. И давайте продолжим с этим. Если размер не равен 0, где находится элемент, который мы хотим из очереди? [Саад] В голове? >> Именно так. Мы можем просто взять и вынуть первый элемент в нашей очереди при обращении к элементу в голову. Ничего не сумасшедший. После этого, что мы должны делать? Что должно произойти? Какова была другая вещь, о которых мы говорили в йедиеие? Две вещи должны произойти, потому что наша очередь изменился. [Даниил] Уменьшение размера. >> Мы должны уменьшить размер и увеличить голову? Именно так. Для увеличения головы, мы не можем слепо увеличить голову, помню. Мы не можем просто сделать queue.head + +. Мы должны также включать этот мод по мощности. И почему мы мода на мощность, Stella? [Stella] Потому что он имеет, чтобы обернуть вокруг. >> Именно так. Мы мод по мощности, поскольку она имеет обернуть обратно к 0. Так вот, на данный момент, мы можем делать то, что сказал Дэниел. Мы можем уменьшать размер. И тогда мы можем просто вернуть элемент, который был в начале очереди. Это выглядит рода угловатый на первый взгляд. Вы можете есть вопрос. Простите? 

[Сэм] Почему это сначала в начало очереди? Где это пойти? [Хардисон] Оно происходит от четвертой строке снизу. После того как мы проверить, чтобы убедиться, что наша очередь не пуста, Мы вытащить символ * Во-первых, мы вытащить элемент, который сидит во главе индекса нашего массива, наши строк массива, >> и вызов, который в первую очередь? [Хардисон] И мы называем это в первую очередь. Да. Просто следить за что, почему вы думаете, мы должны были это сделать? [Сэм] Каждый первый просто возвращение q.strings [q.head]? >> Да. >> Потому что мы делаем это изменение q.head с модом функции, и нет никакого способа сделать это в обратной линии тоже. [Хардисон] Именно так. Ты пятно на. Сэм совершенно местом на. Причина мы должны были вытащить первый элемент в нашей очереди и сохранить его в переменную потому, что это линия, где мы только что q.head, есть мод оператора там не то, что мы можем сделать и она вступит в силу на голове без - в одну линию. Таким образом, мы на самом деле нужно вытащить первый элемент, а затем настроить голову, изменить размер, а затем вернуть элемент, который мы вытащили. И это то, что мы увидим придумали позже связанные списки, как мы поиграть с ними. Часто, когда вы освобождении или утилизации связанные списки Вы должны помнить, следующий элемент, следующий указатель связанный список Перед утилизацией текущего. Потому что в противном случае вы выбросите информацию о том, что осталось в списке. Теперь, если вы идете в прибор, вы откроете queue.c--х из этого. Так что, если я открываю queue.c, позвольте мне увеличить здесь, Вы увидите, что у вас есть подобный вид файла. Похожие вид файла, что мы имели раньше с stack.c. У нас есть наша структура для очереди определяется так же, как мы видели на слайдах. 

У нас есть поставить в очередь функцию, которая для вас сделать. А у нас из очереди функций здесь. Йедиеие функции в файле невыполненными, Но я положу его обратно на PowerPoint, так что вы можете ввести его, если вы хотите. Таким образом, в течение следующих 5 минут или около того, вы, ребята работают на постановки в очередь которая почти прямо противоположна из очереди. Вы не должны регулировать голову, когда вы enqueueing, но то, что вы должны настроить? Размер. Итак, когда вы постановки в очередь, голова остается нетронутой, размер не меняется. Но для этого надо немного - вам придется поиграть с этим мод , чтобы выяснить точно, что индекс нового элемента должно быть вставлен в. Поэтому я дам вам, ребята немного, положил обратно из очереди на слайде, и как вы, ребята, есть вопросы, кричать их, так что мы можем все разговоры о них как о группе. Кроме того, с размером вы не - при настройке размера, вы всегда можете просто - Вы должны мода размер когда-либо? [Даниил] Нет >> Вы не должны мода размера, правы. Поскольку размер будет всегда, если вы - предполагается, что вы все правильно управлять, Размер всегда будет между 0 и 3. Где вы должны мода, когда вы делаете постановки в очередь? [Студент] Только для головы. >> Только за голову, точно. И почему вы должны мода на все постановки в очередь? Когда ситуация, в которой вам придется мода? [Студент] Если у вас есть вещи в пространстве, как на пространствах 1 и 2, , а затем вам нужно добавить что-то в 0. [Хардисон] Да, именно так. Таким образом, если ваша голова указатель находится в самом конце, или если ваш размер плюс ваша голова больше, или, скорее, будет обернуть вокруг очереди. 

Таким образом, в этой ситуации, что мы получили здесь, на слайде прямо сейчас, если я хочу что-то поставить в очередь прямо сейчас, Мы хотим поставить в очередь что-то по индексу 0. Так что если вы посмотрите, где в 50 идет, и я призываю епдиеие 50, она идет там на дне. Он идет в индекс 0. Он заменяет «привет», которая уже была удалена из очереди. [Даниил] Не вы заботитесь о том, что в йедиеие уже? Почему он ничего сделать с головой постановки в очередь? [Хардисон] Ах, так вы не изменив головой, извините. Но вы должны использовать мод оператора, когда вы обращаетесь элемент, который вы хотите поставить в очередь, когда вы обращаетесь Следующий элемент в очереди. [Василий] я этого не сделал, и я получил "Успех" там. [Даниил] О, я понимаю, что вы говорите. [Хардисон] Таким образом, вы didn't - вы только что сделали в q.size? [Василий] Да. Я просто перешла на другую сторону, я ничего не делал с головой. [Хардисон] Вы на самом деле не имеют для сброса головой быть что угодно, но когда вы индекс в массиве строк, Вы на самом деле нужно идти вперед и вычислить, где следующий элемент, потому что лоза стека, следующий элемент в стеке всегда была на индекс, соответствующий размер. Если мы оглянемся назад в нашем функцией нажатия стека, Мы всегда мог швырнуть в нашем новом элементе права на размер индекса. В то время как с очередью, мы не можем сделать это потому что, если мы в этой ситуации, если мы в очереди 50 наших новая строка будет идти прямо на строки [1] которые мы не хотим делать. Мы хотим, чтобы новая строка пойти на индекс 0. 

Кто-нибудь - да? [Студент] У меня есть вопрос, но это на самом деле не связаны между собой. Что это значит, когда кто-то просто вызывает что-то вроде PRED указатель? Что это название сокращенно? Я знаю, это просто название. [Хардисон] Pred указатель? Давайте посмотрим. В каком контексте? [Студент] Это было для вставки. Я могу задать вам позже, если вы хотите потому что это на самом деле не связаны, но я просто - [Хардисон] Из вставки кода Давид из лекции? Мы можем тянуть, что и говорить об этом. Мы поговорим об этом в следующий, как только мы доберемся до связанных списков. 

Так что давайте действительно быстро взглянуть на то, что функция постановки в очередь выглядит. Какой была первая вещь, которую люди пытались сделать в вашей постановки в очередь строки? В этой очереди? Как и то, что вы сделали для стека нажатием. Что вы делали, Стелла? [Stella, неразборчиво] [Хардисон] Именно так. Если (q.size == вместимости) - Мне нужно поставить мою скобки в нужном месте - вернуться ложным. Увеличить немного. Хорошо. Теперь то, что следующая вещь, которую мы должны были сделать? Так же, как со стеком, и вставляется в нужное место. И то, что было в нужном месте, чтобы вставить это? С стек это был размер индекса, с этим не совсем так. [Даниил] У меня есть q.head--или - q.strings? >> >> Да. q.strings [q.head + q.size мод качестве]? [Хардисон] Мы, вероятно, хотят поставить скобки вокруг этого так что мы получаем соответствующий приоритет и так вот cleart для всех. И установлено, что равны? Чтобы >> ул? Чтобы >> ул. Великий. А теперь то, что последняя вещь, которую мы должны сделать? Так же, как мы это делали в стеке. >> Приращение размера? >> Приращение размера. Boom. А затем, поскольку стартовый код только что вернулся ложной по умолчанию, Мы хотим изменить это верно, если все проходит и все идет хорошо. Хорошо. Это очень много информации для раздела. Мы не совсем закончена. Мы хотим говорить о действительно быстро односвязный списки. Я положу это так, мы можем вернуться к нему позже. Но давайте вернемся к нашей презентации всего за несколько слайдов. Так епдиеие является TODO, теперь мы сделали это. 

Теперь давайте взглянем на односвязный списки. Мы говорили об этом немного больше в лекции. Как многие из вас, ребята увидели демо, где у нас были люди неловко указывая друг к другу и проведение цифры? >> Я была в этом. >> Что вы думаете, ребята? Разве что, как мы надеемся прояснить это немного? В списке, то получается, что мы имеем дело с этим типом, который мы будем называть узлом. В то время как с очередью и стеком у нас были структуры, которые мы назвали бы очереди в стеке, у нас были эти новые очереди в стеке типа, Здесь список на самом деле просто состоит из кучу узлов. Таким же образом, что строки просто набор символов все выстроились рядом друг с другом. Связанный список всего узла и другой узел, а другой узел, а другой узел. И вместо того, разбив все узлы вместе, и хранить их непрерывно все рядом друг с другом в памяти, с этой следующий указатель позволяет хранить узлах, где, в случайном порядке. А потом вроде проводов их все вместе, чтобы указать от одного к другому. 

И то, что было большим преимуществом, что это было более чем массив? За хранение все непрерывно просто застрял рядом друг с другом? Вы помните? Да? >> Динамическое распределение памяти? >> Динамическое распределение памяти в каком смысле? [Студент], что вы можете сделать его еще больше, и вы не должны переместить весь массив? [Хардисон] Именно так. Таким образом, с массивом, когда вы хотите поставить новый элемент в середине, Вы должны перейти все, чтобы освободить место. И, как мы говорили с очередью, Вот почему мы держим голову, что указатель, так что мы не постоянно меняются вещи. Потому что становится дорогим, если у вас есть большой массив и вы постоянно делаете эти случайные вставки. В то время как со списком, все что вам нужно сделать, это выбросить его на новый узел, настроить указатели, и вы сделали. Что сосет по этому поводу? Помимо того, что это не так просто, как работать с массивом? Да? [Даниил] Ну, я думаю, это гораздо труднее получить доступ к определенному элементу в связанном списке? [Хардисон] Вы не можете просто перейти к произвольному элементу в середине вашего связанного списка. Как вы должны это сделать вместо этого? >> Вы должны пошагово всю вещь. [Хардисон] Да. Вы должны пройти по одному, по одному за раз. Это огромная - это боль. Что с другой - есть еще один крушение к этому. [Василий] Вы не можете пойти вперед и назад? Вы должны идти в одном направлении? [Хардисон] Да. Так как же нам решить, что иногда? [Василий] двунаправленного списков? >> Именно так. Есть дважды связанные списки. Есть также - жаль? 

[Сэм] Это то же самое, что и использование PRED то, что - Я только что вспомнил, это не то, что PRED вещь, это? Разве это не между двух-и поодиночке? [Хардисон] Давайте посмотрим, что именно он делает. Таким образом, здесь мы идем. Вот список кода. Здесь мы имеем predptr, здесь. Это то, что вы говорите? Так что это было - он освобождая список, и он пытается сохранить указатель на него. Это не дважды, отдельно связанные списки. Мы можем поговорить об этом позже, так как это говорит об освобождении список и я хочу показать некоторые другие вещи первой. но это просто - это помнить значение PTR [Студент] О, это предыдущей указатель? >> Да. Так что мы можем увеличить PTR себя, прежде чем мы тогда бесплатно, что является predptr. Поскольку мы не можем бесплатно PTR, а затем вызвать PTR = PTR дальше, не так ли? Это было бы плохо. Итак, давайте посмотрим, вернемся к этому парню. 

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

Просто очень быстро, когда мы диаграмму из этих списков, Обычно мы проводим на голову списка или первый указатель списка и отметить, что это является истинным указателем. Это просто 4 байт. Это не самого узла. Таким образом, вы видите, что он не имеет целочисленное значение в ней, не следующего указателя в нем. Это буквально указатель. Это будет указывать на то, что фактическая структура узла. [Сэм] указатель называется узел? >> Это - нет. Это указатель на что-то типа узла. Это указатель на узел структуры. >> Ну, ладно. Диаграмма слева, код справа. Мы можем установить его в нуль, который является хорошим способом для начала. При схеме, вы либо написать его в качестве нулевого или вы положите линии, проходящей через это так. 

Один из самых простых способов работы со списками, и мы просим Вас как добавляем и добавляем увидеть различия между ними, но добавляя, безусловно, легче. Когда вы предварять, это, где вы - когда вы добавляем (7), Вы идете и создать узел структуры и вы установили первым указал на это, потому что сейчас, так как мы добавляется его, это будет в начале списка. Если мы добавляем (3), что создает еще один узел, но теперь 3 идет до 7. Таким образом, мы существенно нажатием вещи на нашем списке. Теперь вы можете видеть, что начало, конец, иногда люди называют его толкать, потому что вы нажимаете новый элемент на вашем списке. Это также легко удалить в передней части списка. Таким образом, люди часто называют это поп-музыки. И в этом случае, вы можете эмулировать стек с помощью связанного списка. Возгласы. К сожалению, сейчас мы входим в добавление. И вот мы добавляется (7), теперь мы добавляем (3). Если добавляется что-то еще на этот список, если мы добавляется (4), Затем мы должны были бы 4, а затем 3, а затем 7. И тогда мы могли бы поп-и удалить 4, удалить 3, удалить 7. Часто более интуитивный способ думать об это с добавление. Так что я диаграмме, что она будет выглядеть с добавить здесь. Здесь прилагается (7) не выглядит по-другому потому что есть только один элемент в списке. И добавления (3) ставит его в конце. Может быть, вы можете увидеть прямо сейчас трюк с добавление является то, что, так как мы только знаем, где в начале списка, добавить в список, нужно пройти весь путь до конца списка чтобы добраться до конца, остановить, а затем построить свой узел и бухнуть все вниз. Соедините все вещи вверх. Так что с начало, конец, как мы только что разорвал это действительно быстро, При предварять в список, это довольно просто. 

Вы делаете свой новый узел, включают некоторые динамического распределения памяти. Итак, вот что мы делаем узел структуры использованием таНос. Так таНос мы используем, потому что будет выделено памяти для нас, для последующего потому что мы не хотим этого - мы хотим, чтобы эта память сохранится в течение длительного времени. И мы получаем указатель на место в памяти, что мы просто выделены. Мы используем размер узла, мы не подвести поля. Мы не вручную генерировать количество байтов, вместо этого мы используем SizeOf, так что мы знаем, мы получаем соответствующее количество байтов. Мы заботимся о том, чтобы проверить, что наш таНос вызова удалось. Это то, что вы хотите сделать в целом. На современных машинах, уходит из памяти это не то, что легко если вы выделении тонны материала и вносят огромный список, Но если вы строите вещи, скажем, как iPhone или Android, у вас есть ограниченность ресурсов памяти, особенно если вы делаете что-то интенсивно. Так что это хорошо, чтобы получить на практике. 

Обратите внимание, что я использовал несколько различных функций здесь что вы видели, что это своего рода новое. Так Fprintf такой же, как Printf кроме ее первый аргумент является поток, в который вы хотите напечатать. В этом случае, мы хотим, чтобы печатать на стандартную строку ошибки , который отличается от стандартного outstream. По умолчанию она появляется в том же месте. Она также выводит на терминал, а можно - с помощью этих команд вы узнали о, методы перенаправления Вы узнали о в видео Томми проблемой для множества 4, Вы можете направлять ее в различных областях, а затем выйти, прямо здесь, выходит вашу программу. Это, по существу, как возвращался из главных, за исключением мы используем выход, потому что здесь возвращение не будет ничего делать. Мы не в основной, так что возвращаться не выйти из программы, как мы хотим. Поэтому мы используем функцию выхода и дать ему код ошибки. Тогда здесь мы устанавливаем значение нового узла поля, его я поля равным я, а потом подключить его. Мы установили следующий указатель нового узла, чтобы указать на первый, , а затем первым будет указывать на новый узел. Эти первые строки кода, мы фактически строительство нового узла. Не две последние строки этой функции, но первый из них. Вы действительно можете выйти в функцию, во вспомогательную функцию. Это часто, что я делаю, я вытащить его в функцию, Я называю это что-то вроде узла сборки, и что держит добавляем функцию довольно небольшой, это просто 3 линии тогда. Я делаю вызов моей функции узла сборки, а потом я провода все вверх. 

Последнее, что я хочу показать вам, и я дам вам сделать добавление и все, что на свой собственный, как для перебора списка. Есть множество различных способов для перебора списка. В этом случае, мы собираемся, чтобы найти длину списка. Итак, мы начинаем с длиной = 0. Это очень похоже на написание StrLen для строки. Это то, что я хочу показать вам, это цикл прямо здесь. Это выглядит своего рода фанк, это не обычная Int я = 0, <что угодно, я + +. Вместо этого он инициализацию нашей переменной п будет в начале списка. И потом, когда наш итератор переменной не является нулевым, мы продолжаем. Это потому, что, по соглашению, в конце нашего списка будет нулевым. И тогда, чтобы увеличить, а не делать + +, Связанный список эквиваленте + + п = п-> дальше. 

Я дам вам заполнить пробелы здесь, потому что мы находимся вне времени. Но имейте это в виду, как вы работаете на psets spellr. Связанные списки, если вы реализуете хэш-таблицы, , безусловно, очень удобен. И с этой идиомой цикл над вещами сделает жизнь намного проще, надеюсь. Любые вопросы, быстро? [Сэм] Будете ли вы отправить заполненную SLL и ПК? [Хардисон] Да. Я буду посылать завершена слайды и завершил стек SLL и queue.cs. [CS50.TV]