[Powered by Google Translate] [Часть 6] [более комфортным]
[Rob Боуден] [Harvard University]
[Это CS50.] [CS50.TV]
>> Мы можем отправиться в нашем разделе вопросов.
Я послал URL для космических раньше.
В начале раздела вопросов говорите-
видимо я не совсем unsick-это очень простой вопрос
всего того, что Valgrind?
Что Valgrind делать?
Любой хочу сказать, что Valgrind делает?
[Студент] Проверка утечек памяти.
Да, Valgrind общая проверка памяти.
Это, в конце концов, говорит вам, если у вас есть какие-то утечки памяти,
который в основном то, что мы используем его для, потому что, если вы хотите
преуспеть в задаче набора или если вы хотите
получить на большой доске, вы должны иметь утечек памяти вообще,
и в случае, если есть утечки памяти, которые вы не можете найти,
Также имейте в виду, что всякий раз, когда вы открываете файл
и если вы не закроете его, что это утечка памяти.
>> Многие люди ищут для некоторых узлов, что они не освобождая
когда на самом деле, они не закрыть словарь в самый первый шаг.
Он также говорит вам, если у вас есть какие-то недействительным читает или пишет,
что означает, если вы пытаетесь установить значение
что это за конец кучи и это не произойдет в сегменте вина
но Valgrind ловит его, как вы на самом деле не должно быть письменно там,
и таким образом, вы определенно не должны иметь любой из этих тоже.
Как вы используете Valgrind?
>> Это общий вопрос
вид запустите ее и посмотрите на выходе.
Выход подавляющего много раз.
Там же, где весело ошибки, если у вас есть некоторые очень неправильные вещи
происходит в цикле, то она будет в конечном итоге сказать: "Слишком много ошибок.
Я собираюсь прекратить подсчет сейчас ".
Это в основном текстовый вывод, что вам придется разобрать.
В конце концов, он скажет вам любой утечки памяти, которые у вас есть,
сколько блоков, которые могут быть полезны, потому что
если это один блок unfreed, то она, как правило, легче найти
чем 1.000 блоков unfreed.
1000 блоков unfreed, вероятно, означает, что вы не освобождая
ваша связанные списки надлежащим или что-то.
Это Valgrind.
>> Теперь у нас есть раздел вопросов,
которые вам не нужны для загрузки.
Вы можете нажать на мое имя, и потянуть их в пространстве.
Теперь нажмите на меня.
1-я редакция будет стек, который мы делаем в первую очередь.
Пересмотр 2 будет очереди, и 3-я редакция будет однонаправленного списка.
Начав с нашим стеком.
Как сказано здесь, стек является одним из самых основных,
фундаментальные структуры данных, информатики.
Сам прототип примера
стопку тарелок в столовой.
Это в основном, когда вы вводятся в стек,
кто-то скажет: "О, как стек лотков".
Вы стек лотками.
Затем, когда вы идете вытащить лоток,
первый лоток, который становится вытащил является последней, которая была введена в стеке.
Стек также, как он говорит здесь-
у нас есть сегмент памяти, называемой стеком.
И почему это называется стеком?
>> Потому что, как структуры данных стека,
он толкает и появляется кадры стека в стек,
где кадры стека похожи на конкретный вызов функции.
И, как стек, вы всегда будете иметь, чтобы вернуться
от вызова функции, прежде чем спускаться в нижние кадры стека снова.
Вы не можете иметь главный вызов Foo Bar вызова и бар возвращение к основному напрямую.
Он всегда должны следовать правильным стек нажатия и появляются.
Две операции, как я уже сказал, толчок и поп-музыки.
Это универсальные термины.
Вы должны знать, толчок и поп-музыки с точки зрения стеки ни на что.
Мы увидим очереди вид другой.
Это действительно не имеет универсального термина, но толчок и поп являются универсальными для стеков.
Толчок просто положить на стек.
Поп-это взять из стека.
И мы видим, здесь у нас есть ЬурейеЕ стек структуры,
поэтому мы должны символов строки **.
Не пугайтесь любой **.
Это будет в конечном итоге массив строк
или массив указателей на символы, где
указателей на символы, как правило, строки.
Это не должны быть строками, но здесь они собираются быть строками.
>> У нас есть массив строк.
У нас есть размер, который представляет, сколько элементов в настоящее время в стеке,
и у нас есть потенциал, который, как многие элементы могут быть в стеке.
Емкость должна начаться как нечто большее, чем 1,
но размер будет начинаться как 0.
Сейчас, в основном существуют три различных способа вы можете думать о стеке.
Ну, есть, вероятно, больше, но два основных пути
Вы можете осуществить это с помощью массива, или вы можете реализовать его с помощью связанного списка.
Связанные списки являются своего рода тривиальная, чтобы стек с.
Это очень легко сделать стек с помощью связанных списков,
так вот, мы собираемся сделать стек с помощью массива,
а затем с помощью массивов, есть также два пути вы можете думать об этом.
Раньше, когда я сказал, у нас есть потенциал для стека,
так что мы можем соответствовать элементу в стеке.
>> Одной стороны, это могло произойти, как только вы нажмете 10 элементов, то вы сделали.
Возможно, вы знаете, что есть верхняя граница из 10 вещей в мире
что вы никогда не будете иметь больше, чем 10 вещей, на ваш стек,
В этом случае вы можете иметь верхнюю границу размера вашего стека.
Или вы могли бы ваш стек быть неограниченным,
Но если вы делаете массив, это означает, что каждый раз, когда вы попали 10 элементов,
тогда вы будете иметь, чтобы вырасти до 20 элементов, и когда вы попали 20 элементов,
Вам придется выращивать массива до 30 элементов и 40 элементов.
Вы будете нуждаться, чтобы увеличить пропускную способность, которая является то, что мы собираемся сделать здесь.
Каждый раз, когда мы достигаем максимального размера нашего стека,
когда мы нажимаем на что-то другое, мы будем нуждаться, чтобы увеличить пропускную способность.
Здесь мы толчок объявлены как BOOL толчок (символ * ул).
Char * ул представляет собой строку, мы добиваемся в стек,
и BOOL просто говорит ли мы успеха или неудачи.
>> Как мы можем потерпеть неудачу?
Что является единственным обстоятельством, что вы можете думать о
где мы должны были бы вернуться ложным?
Да.
[Студент] Если это полная и мы используем ограниченную реализацию.
Да, так как мы определяем, он ответил
если это полная и мы используем ограниченной реализации.
Тогда мы определенно вернемся ложным.
Как только мы попали 10 вещей, которые в массиве, мы не может поместиться 11, так что мы возвращаемся ложным.
Что, если она не ограничена? Да.
Если вы не можете расширить массив по некоторым причинам.
Да, так что память является ограниченным ресурсом,
и в конце концов, если мы продолжать настаивать вещи в стек снова и снова,
Мы собираемся попробовать и выделить больший массив, чтобы соответствовать
большую емкость, и таНос или любой другой мы используем собирается вернуться ложным.
Ну, таНос вернет NULL.
>> Помните, что каждый раз, когда вы звоните таНос, вы должны проверять, чтобы увидеть, если она
возвращает нулевой или еще что правильность вывода.
Так как мы хотим иметь неограниченный стека,
Единственный случай, мы собираемся возвращаться ложным, если мы попытаемся
увеличить мощность и таНос или что возвращает ложь.
Тогда поп не принимает аргументов,
и она возвращает строку, которая находится на вершине стека.
Каким бы ни был недавно в стек является то, что поп возвращается,
и он также удаляется из стека.
И заметил, что он возвращает нулевое значение, если нет ничего в стек.
Это всегда возможно, что стек пуст.
В Java, если вы привыкли к этому, или других языков,
пытаются поп из пустого стека может вызвать исключение или что-то.
>> Но в C, нулевые это своего рода много случаев, как мы справляемся с этими проблемами.
Возвращаясь нулевой, как мы собираемся, чтобы показать, что стек был пуст.
Мы предоставили код, который будет проверять функциональность вашего стека,
осуществление толкать и поп-музыки.
Это не будет много кода.
Я воли на самом деле, прежде чем мы это сделаем, намек, подсказка-
Если вы еще не видели его, таНос это не единственная функция
, которая выделяет память в куче для вас.
Есть семьи идентификатор функции.
Первый таНос, которые вы привыкли.
Тогда есть calloc, которая делает то же самое, что и таНос,
но это будет нулю все для вас.
Если вы когда-нибудь хотели, чтобы установить все до нуля после mallocing что-то
Вы должны просто использовать calloc, в первую очередь, а не писать
цикл обнулить весь блок памяти.
>> Realloc, как таНос и имеет много особых случаев,
но в основном то, что делает перераспределить
она принимает указатель, которые уже были выделены.
Realloc является функцией, которую необходимо обращать внимание на здесь.
Он принимает указатель, который уже вернулся из таНос.
Допустим, вы требовать от таНос указатель из 10 байт.
Позже вы осознаете, что вы хотели 20 байт,
так вы звоните перераспределить на этом указатель с 20 байт,
и перераспределить автоматически скопировать все за вас.
Если вы только что позвонил таНос вновь, как и у меня есть блок из 10 байт.
Теперь мне нужно блок из 20 байт,
так что если я таНос 20 байт, то мне придется вручную скопировать 10 байт из первой вещью
во вторую вещь, а затем освободить первое.
Realloc будет обрабатывать это для вас.
>> Обратите внимание, что подпись будет недействительной *,
который просто возвращает указатель на блок памяти,
Затем пустоты * указатель.
Вы можете думать о пустоте * как общий указатель.
Вообще, вы никогда не иметь дело с недействительными *,
но таНос возвращается пустота *, а затем просто использовать как
это на самом деле будет символ *.
* Предыдущие пустоту, которая была возвращена на таНос
Теперь будет передан перераспределить, а затем размер
это новое число байт вы хотите выделить, так что ваши новые мощности.
Я дам вам несколько минут, и сделать это в нашем пространстве.
Начните с пересмотра 1.
Я остановлю тебя после надеюсь, о достаточно времени для осуществления толчок,
и тогда я дам тебе еще один перерыв, чтобы сделать поп-музыки.
Но на самом деле это не так уж много кода.
Наиболее кода, вероятно, расширяет материал, расширение мощностей.
Хорошо, никакого давления, чтобы быть полностью сделано,
но пока вы чувствуете, что находитесь на правильном пути, это хорошо.
>> Кто-нибудь есть код, который они чувствуют себя комфортно со мной, потянув вверх?
Да, я хочу, а не кого-нибудь есть код я могу потянуть?
Хорошо, вы можете начать, сохраните его, что это такое?
Я всегда забываю, что шаг.
Ладно, глядя на толчок,
Вы хотите, чтобы объяснить свой код?
[Студент] Во-первых, я увеличил размер.
Я думаю, может быть, я должен иметь что-все равно, я увеличил размер,
и я не вижу, если он меньше, чем емкость.
И если это меньше, чем емкость, добавить в массив, что мы уже имеем.
А если это не так, я умножить мощность на 2,
и я перераспределить строк массива что-то с большей мощностью размер сейчас.
И потом, если это не удается, я говорю пользователя и вернуться ложным,
и если все нормально, то я ставлю строку в новом месте.
>> [Rob B.] Также обратите внимание, что мы использовали хороший оператор побитового здесь
умножить на 2.
Помните, что сдвиг влево всегда будет умножить на 2.
Сдвиг вправо делится на 2, пока вы помните, что это означает
делим на 2, как в целое число делится на 2.
Это может обрезать на 1 здесь или там.
Но сдвиг влево на 1 всегда будет необходимо умножить на 2,
если вы переполнения пределы целого, и тогда она не будет.
Стороны комментария.
Мне нравится делать-это не собирается менять кодирования любой форме,
Но я хотел бы сделать что-то вроде этого.
Это на самом деле происходит, чтобы сделать его немного дольше.
Может быть, это не идеальный случай, чтобы показать это,
но мне нравится сегменте его в эти блоки-
Хорошо, если это, если произойдет, то я буду что-то делать,
, а затем функция выполняется.
Мне не нужно, чтобы потом прокрутить мои глаза все, вплоть функции
, чтобы увидеть, что происходит после другого.
Это, если это, если произойдет, то я просто вернуться.
Она также имеет хорошее дополнительное преимущество все, что за этим
В настоящее время сдвигается влево один раз.
Я больше не нужно, если вы всегда рядом смешного длинные очереди,
Затем эти 4 байта может помочь, а также левее что-то есть,
меньше перегружены вы себя чувствовали, если хотите, хорошо, я должен помнить,
Я в настоящее время нахожусь в то время как цикл внутри другого внутри цикла.
Везде вы можете сделать это возвращение немедленно, я вроде как.
Это совершенно необязательным и не ожидал никак.
>> [Студент] Должны ли быть размером - в обязательном порядке условия?
Непременно условие здесь мы не смогли перераспределить, так что да.
Обратите внимание, что в обязательном порядке условие, по-видимому,
если мы бесплатно вещи позже, мы всегда будем на провал
независимо от того, сколько раз мы пытаемся подтолкнуть что-то.
Если мы будем продолжать настаивать, мы продолжаем увеличивая размер,
даже если мы не ставит ничего в стек.
Обычно мы не увеличиваем размер до
после того, как мы успешно положить его в стек.
Мы хотели бы это сделать, скажем, либо здесь и здесь.
И тогда вместо того чтобы сказать s.size ≤ потенциал, это меньше, чем мощность,
только потому, что мы переехали, где все было.
>> И помните, что единственное место, где мы могли бы вернуться ложным
Здесь, где перераспределить возвращается нуль,
и если Вы случайно не помните стандартная ошибка,
Может быть, вы могли бы рассмотреть этот случай, когда вы хотите печатать стандартные ошибки,
так Fprintf STDERR, а не просто печать непосредственно на стандартный вывод.
Опять же, это не ожидание, но если это ошибка,
Введите Printf, то вы можете сделать это печать на стандартной ошибки, а не стандартный вывод.
>> Любой, есть что-нибудь еще отметить? Да.
[Студент] Можете ли вы перейти на [неразборчиво]?
[Rob B.] Да, фактически binariness это или просто, что это такое?
[Студент] Таким образом, вы умножить на 2?
[Rob B.] Да, в основном.
В двоичной земли, у нас всегда есть наш набор цифр.
Переход этом левая на 1 основном вставляет его здесь, на правой стороне.
Вернуться к этому, просто помните, что все в двоичном
является степенью 2, так что это представляет 2 до 0,
это 2 к 1, это 2 к 2.
Добавляя 0 до правой стороны сейчас, мы просто переложить все кончено.
То, что было 2 до 0, в настоящее время 2 к 1, 2 к 2.
На правой стороне, что мы вставили
обязательно будет 0,
который имеет смысл.
Если вы когда-нибудь умножить число на 2, это не будет в конечном итоге нечетным,
так что 2 до 0 место должно быть 0,
и это то, что первое полугодие предупредил, прежде чем есть, если вы все-таки перейти
за количество бит в целое,
то это 1, будет в конечном итоге уходить.
Это единственное беспокойство, если вам случится иметь дело с действительно большими возможностями.
Но в этот момент, то вы имеете дело с массивом миллиарды вещей,
которая может не поместиться в памяти в любом случае.
>> Теперь мы можем добраться до поп-музыки, которая еще проще.
Вы можете сделать это нравится, если вам случится поп целая куча,
и теперь вы в половину мощности снова.
Вы могли бы перераспределить, чтобы уменьшить объем памяти у вас есть,
но вы не должны беспокоиться о том, что, таким образом, единственный случай, перераспределить будет
растущая памяти, никогда не сокращение памяти,
который собирается сделать поп-супер просто.
Сейчас в очереди, который будет, как стеки,
но для того, чтобы взять вещи на противоположное.
Простейший пример из очереди линии,
поэтому я думаю, если бы вы были на английском, я бы сказал,
Простейший пример из очереди в очередь.
Так как линия, если вы первый человек в линии,
Вы ожидаете, чтобы быть первым человеком из очереди.
Если вы последний человек в линии, вы собираетесь быть последним человеком в ремонт.
Мы называем это FIFO модели, в то время как стек LIFO шаблону.
Эти слова являются довольно универсальными.
>> Как стеки и в отличие от массивов, очередей обычно не допускают доступ к элементам в середине.
Здесь, стек, мы должны толкать и поп-музыки.
Здесь мы, случается, называют их постановки в очередь и удаления из очереди.
Кроме того, я слышал, как они называют сдвигом и Отменить замену.
Я слышал, люди говорят, толчок и поп применяются также к очередям.
Я слышал, вставки, удаления,
так толкать и поп, если вы говорите о стеки, вы толкаете и хлопать.
Если вы говорите об очередях, вы могли бы выбрать слова, которые вы хотите использовать
для вставки и удаления, и нет единого мнения о том, что они должны быть названы.
Но здесь, у нас есть поставить в очередь и удаления из очереди.
Теперь, структура выглядит почти идентично стек структуры.
Но мы должны следить за голову.
Я думаю, это говорит здесь, но почему мы нуждаемся в голову?
Прототипы в основном идентичны толкать и поп-музыки.
Вы можете думать об этом как толчок и поп-музыки.
Разница лишь в том поп возвращается, вместо последнего, он возвращает первый.
2, 1, 3, 4, или что-то еще.
И вот старт.
Наша очередь полностью заполнена, так что четыре элемента в нем.
В конце нашей очереди в настоящее время 2,
и теперь мы идем, чтобы вставить что-то другое.
>> Когда мы хотим, чтобы вставить что-то другое, что мы сделали для стека версия
это мы расширили наш блок памяти.
В чем проблема с этим?
[Студент] Вы двигаетесь 2.
Как я уже говорил о конце очереди,
это не имеет смысла, что мы начинаем с 1,
Затем мы хотим, чтобы из очереди 1, то из очереди 3, то из очереди 4,
то из очереди 2, то из очереди этого.
Мы не можем использовать перераспределить сейчас,
или, по крайней мере, вы должны использовать перераспределить по-другому.
Но вы, вероятно, не следует использовать только перераспределить.
Вы будете должны вручную скопировать памяти.
>> Есть две функции для копирования памяти.
Там в memcopy и memmove.
Я сейчас читаю человек страниц, чтобы увидеть, какой вы собираетесь хотите использовать.
Хорошо, memcopy, разница
что memcopy и memmove, один обрабатывает случае правильно
где вы копируете в регионе, что происходит перекрытие регионе
Вы копировании.
Memcopy не справиться. Memmove делает.
Вы можете думать о проблеме, как-
скажем, я хочу, чтобы скопировать этот парень,
эти четыре с этим парнем старше.
В конце концов, то, что массив должен выглядеть
после того, как копия 2, 1, 2, 1, 3, 4, а затем некоторые вещи в конце.
Но это зависит от порядка, в котором мы на самом деле копировать,
так как если мы не считаем тот факт, что регион мы копирования в
перекрывает один мы копировании,
Затем мы могли бы сделать, как начать здесь, копирование 2 в место, где мы хотим пойти,
затем переместить наши указатели вперед.
>> Теперь мы собираемся быть здесь и здесь, и теперь мы хотим, чтобы скопировать
этот парень за этим парнем, и переместить наши указатели вперед.
То, что мы собираемся в конечном итоге получить в 2, 1, 2, 1, 2, 1
вместо того, чтобы соответствующие 2, 1, 2, 1, 3, 4, потому что
2, 1 преодолел оригинальный 3, 4.
Memmove обрабатывает это правильно.
В этом случае, в основном всегда использовать memmove
потому что он работает правильно.
Как правило, он не выполняет хуже.
Идея состоит в том, а не с начала и копирования таким образом,
как мы только что сделали здесь, она начинается с конца и копирует в,
и в этом случае, вы не можете иметь проблемы.
Там производительность не потерял.
Всегда используйте memmove. Никогда не беспокойтесь о memcopy.
И вот, когда вы будете иметь отдельно memmove
обернутый вокруг части вашей очереди.
Не беспокойтесь, если не полностью сделано.
Это труднее, чем стек, толчок, и поп-музыки.
>> Любой, есть какие-либо кода мы могли бы работать?
Даже если полностью неполным?
[Студент] Да, это совершенно неполным, однако.
Полностью неполной прекрасно до тех пор, как мы, вы можете сэкономить пересмотра?
Я забываю, что каждый раз.
Хорошо, игнорируя то, что происходит, когда мы должны изменить размер вещи.
Полностью игнорировать изменения размера.
Объяснить этот код.
Я проверяю, прежде всего, если размер меньше, чем копия, прежде всего,
и после этого, я вставляю-я беру голову + размер,
и я убедиться, что она обтекает емкость массива,
и я вставить новую строку в этом положении.
Тогда я увеличить размер и вернуть истинный.
>> [Rob B.] Это, безусловно, один из тех случаев, когда вы захотите использовать мод.
Любой случай, когда вы обтекания, если вы думаете обтекания,
непосредственной мысль должна быть мода.
Как быстро оптимизации / сделать ваш код одну строку короче,
Вы заметили, что строки сразу после этого
только размер + +, так что вы объединяете, что в эту линию, размер + +.
Теперь здесь мы имеем случай
, где у нас не хватает памяти,
так мы увеличиваем нашу способность на 2.
Я думаю, вы могли бы иметь те же проблемы, но мы можем игнорировать это сейчас,
, где, если вы не смогли увеличить мощность,
то вы будете хотеть, чтобы уменьшить емкость на 2 снова.
Другой короткую записку так же, как вы можете сделать, + =,
Вы также можете сделать << =.
Почти все, что может пойти до равных, + =, | =, & =, << =.
Char * новый наш новый блок памяти.
О, здесь.
>> Что люди думают о типе наш новый блок памяти?
[Студент] Он должен быть символ **.
Вспоминая нашу структуру здесь,
строк то, что мы перераспределения.
Мы делаем совершенно новый динамической памяти для элементов в очереди.
То, что мы собираемся назначении на ваши строки является то, что мы mallocing прямо сейчас,
и так новая будет символ **.
Это будет массив строк.
Тогда в чем же дело, по которому мы собираемся вернуться ложным?
[Студент] мы должны делать символов *?
[Rob B.] Да, хороший вызов.
[Студент] Что это было?
[Rob B.] Мы хотели сделать размер символов *, потому что мы уже не-
это фактически будет очень большая проблема, потому что SizeOf (Char) будет 1.
Sizeof символ * будет 4,
так много раз, когда вы имеете дело с целыми,
Вы, как правило, все сойдет с рук, потому что размер Int и размер Int *
на 32-разрядные системы будет то же самое.
Но здесь, SizeOf (Char) и SizeOf (Char *) теперь будет то же самое.
>> Что такое обстоятельство, где мы вернуться ложным?
[Студент] Новый равен нулю.
Да, если новый пустой, мы возвращаемся ложными,
и я собираюсь бросить здесь-
[Студент] [неразборчиво]
[Rob B.] Да, это прекрасно.
Вы можете либо делать 2 раза мощность или емкость сдвиг 1, а затем только установить его здесь или любой другой.
Мы сделаем это, как у нас было.
Емкость >> = 1.
И вы никогда не придется беспокоиться о потере 1-Место
потому что вы оставили сдвинут на 1, поэтому 1-Место обязательно 0,
так прямо сдвиг на 1, вы все еще будет хорошо.
[Студент] Вам необходимо сделать это до возвращения?
[Rob B.] Да, это не имеет абсолютно никакого смысла.
>> Теперь предположим, что мы собираемся в конечном итоге возвращается истинным до конца.
Как мы собираемся сделать это memmoves,
Мы должны быть осторожны с тем, как мы их делаем.
Кто-нибудь есть какие-либо предложения о том, как мы их делаем?
Вот наш старт.
Безусловно, мы хотим начать с самого начала еще раз
и копии вещей в Оттуда, 1, 3, 4, 2.
Как вы это сделали?
Во-первых, я должен смотреть на мужчину страницы для memmove снова.
Memmove, порядок аргументов всегда важно.
Мы хотим, чтобы наше назначение первого, второго источника, размера третьего.
Есть много функций, которые обратном источника и назначения.
Направление, источник, как правило, соответствует несколько.
Move, что это возвращение?
Она возвращает указатель к месту назначения, по какой причине вы, возможно, захотите этого.
Я могу себе читать, но мы хотим двигаться в нашем назначения.
>> То, что наш пункт назначения будет?
[Студент] New.
[Rob B.] Да, и где мы копировании?
Первое, что мы копируем это 1, 3, 4.
Что такое-это 1, 3, 4.
Что такое адрес этого 1?
Что это адрес, что 1?
[Студент] [неразборчиво]
[Rob B.] Руководитель + адрес первого элемента.
Как мы можем получить первый элемент в массиве?
[Студент] Queue.
[Rob B.] Да, q.strings.
Помните, что здесь, наши головы 1.
Штопать его. Я просто думаю, что это волшебно-
Здесь наши головы 1. Я собираюсь менять свой цвет тоже.
А вот строки.
Это, мы можем либо написать его, как мы сделали здесь
с главами + q.strings.
Много людей также писать и q.strings [глава].
В действительности это не любое менее эффективным.
Вы можете думать об этом, как вы разыменования его, а затем получить адрес,
но компилятор собирается перевести его на то, что мы были представлены во всяком случае, q.strings + голова.
В любом случае вы хотите, чтобы думать об этом.
>> И сколько байт мы хотим, чтобы скопировать?
[Студент] Мощность - голова.
Вместимость - голова.
И тогда вы всегда можете написать пример
чтобы выяснить, если это так.
[Студент] Она должна быть разделена на 2, то.
Да, поэтому я думаю, мы могли бы использовать размер.
У нас еще есть размер бытия-
с использованием размера, у нас есть размер, равный 4.
Наш размер 4. Наши головы 1.
Мы хотим, чтобы скопировать эти 3 элемента.
Это здравомыслие проверить, что размер - голова правильно 3.
И возвращаться сюда, как мы уже говорили,
если бы мы использовали потенциал, то мы должны были бы разделить на 2
потому что мы уже выросли наши возможности, поэтому вместо этого мы собираемся использовать размер.
Это копий этой части.
Теперь нам нужно скопировать другая часть, часть, что осталось от самого начала.
>> Это собирается memmove в каком положении?
[Студент] Большие размеры - голова.
Да, так мы уже скопировали в размере - глава байт,
и поэтому там, где мы хотим скопировать оставшиеся байты нового
, а затем размер минус, ну, количество байт, мы уже скопировали дюйма
А потом куда мы копировании?
[Студент] Q.strings [0].
[Rob B.] Да, q.strings.
Мы могли либо сделать и q.strings [0].
Это значительно реже, чем это.
Если он просто будет 0, то вы будете склонны видеть q.strings.
Вот где мы копировании.
Сколько байт у нас осталось скопировать? >> [Студент] 10.
Право.
[Студент] Должны ли мы умножим 5 - 10 раз больше байта или еще что-нибудь?
Да, так это где-то, что именно мы копирования?
[Студент] [неразборчиво]
Какой тип вещь, которую мы копирования?
[Студент] [неразборчиво]
Да, так что символ * ы, что мы копирования, мы не знаем, где те и откуда.
Ну, где они указывают на, как струны, мы в конечном итоге нажав на нее в очередь
или enqueuing на очереди.
Где те, и откуда, мы понятия не имеем.
Нам просто нужно следить за символ * с себя.
Мы не хотим, чтобы скопировать размера - начальник байт.
Мы хотим, чтобы скопировать размера - начальник символ * с,
так что мы собираемся умножить это на SizeOf (Char *).
То же самое здесь, внизу, голова * SizeOf (Char *).
>> [Студент] А [неразборчиво]?
Это прямо здесь?
[Студент] Нет, ниже, размер - голова.
[Rob B.] Это прямо здесь?
Указатель арифметика.
Как арифметика указателей будет работать это
он автоматически умножается на размер типа, что мы имеем дело с.
Так же, как здесь, новая + (размер - голова)
точно соответствует и новая [размер - начальник]
пока мы не ожидаем, что работает правильно,
так как если мы имеем дело с Int массива, то мы не делаем индекс INT-
или, если это размер из 5, и вы хотите 4-й элемент, то индекс в
Int массива [4].
Вы не-[4] * размер Int.
, Который обрабатывает его автоматически, и этот случай
Буквально эквивалентны, поэтому кронштейн синтаксиса
только собирается быть преобразован в этом, как только вы компиляции.
Это то, что вы должны быть осторожны, что
при добавлении размеров - голова
Вы добавляете не один байт.
Вы добавляете один символ *, который может быть одним байт или любой другой.
>> Другие вопросы?
Так, из очереди будет легче.
Я дам вам минуту, чтобы реализовать.
Да, и я предполагаю, что это та же самая ситуация, где
что епдиеие случае, если мы enqueuing нулевой,
Может быть, мы хотим справиться с этим, может быть, мы не знаем.
Мы не будем делать это снова здесь, но так же, как наш стек случае.
Если поставить в очередь нулевые, мы могли бы на него внимания.
Любой, есть некоторый код, я могу потянуть?
[Студент] Я просто из очереди.
Версия 2 является то, что, все в порядке.
Вы хотите, чтобы объяснить?
[Студент] Во-первых, вы убедитесь, что есть что-то в очереди
и что размер понижается на 1.
Вы должны сделать это, а затем вернуть его голову
а затем переместить голову 1.
Итак, есть уголок случае мы должны рассмотреть. Да.
[Студент] Если ваша голова находится на последнем элементе,
то вы не хотите голову, чтобы указать пределы массива.
>> Да, так, как только голова касается конце нашего массива,
Когда мы из очереди, наша голова должна быть мода на 0.
К сожалению, мы не можем сделать это за один шаг.
Я думаю, так, как я бы, вероятно, исправить это
это будет символ *, то, что мы возвращаемся,
Независимо от вашего имени переменной хочет быть.
Затем мы хотим мода головы наших возможностей
, а затем вернуться в отставке.
Многие люди здесь, они могли бы сделать-
это случай-вы будете видеть, как люди делать, если голова
больше емкость, сделать голову - емкость.
И это только рабочая вокруг того, что мод.
Глава МО = емкость намного чище
из обтекание, чем если бы голова больше, чем мощность головой - емкость.
>> Вопросы?
Ладно, последняя вещь, которую мы оставили наш связанного списка.
Вы могли бы быть использованы для некоторых из связанного списка поведение, если вы сделали
связанных списков в вашей хэш-таблицы, если вы сделали хэш-таблицы.
Я настоятельно рекомендую делать хэш-таблицы.
Возможно, вы уже сделали виде дерева,
но пытается труднее.
В теории, они асимптотически лучше.
Но посмотрите на большой доске,
и старается никогда не делать лучше, и они занимают больше памяти.
Все о попытке заканчивает тем, что еще хуже для дополнительной работы.
Это то, что решение David Malan всегда является
он всегда свои сообщения Trie решение, и давайте посмотрим, где он в настоящее время.
Что он под землей, David J?
Он № 18, так что это не очень плохо,
и что это будет один из лучших пытается Вы можете думать
или одна из лучших пытается из Trie.
Это даже не его оригинальное решение?
Я чувствую, как Trie решения, как правило, больше в этой области использования оперативной памяти.
>> Спуститесь на самый верх, и оперативной памяти находится в одной цифры.
Спуститесь вниз к нижней, а затем вы начинаете видеть пытается
где вы получите абсолютно массивной оперативной памяти,
и пытается труднее.
Не совсем, но стоит это образовательный опыт, если вы сделали один.
Последнее, что наша связанного списка,
и эти три вещи, стеки, очереди и связанные списки,
любая будущая что можно сделать в области компьютерных наук
Предположим у вас есть знакомство с этими вещами.
Они просто таким фундаментальным ко всему.
>> Связанные списки, и здесь мы однонаправленного списка будет наша реализация.
Что односвязный значит, в отличие от двусвязный? Да.
[Студент] Это только указывает на следующий указатель, а не указателей,
как тот перед ним и после нее.
Да, так и в формате изображения, что я только что сделал?
У меня есть две вещи. У меня есть картины и фотографии.
В формате изображения, наши однонаправленного списка,
Безусловно, у нас есть какой-то указатель на главу нашего списка,
, а затем в наш список, мы просто указатели,
и, возможно, это указывает на нуль.
Это будет ваш типичный рисунок однонаправленного списка.
Дважды связанный список, вы можете пойти в обратном направлении.
Если я дам вам любой узел в списке, то вы можете всегда получить в
любой другой узел в список, если он дважды связанный список.
Но если я вам третьего узла в списке, и это однонаправленный список,
никоим образом не вы когда-нибудь, чтобы добраться до первого и второго узлов.
И есть преимуществ и недостатков, и один очевидный
это вы занимают больше размером, и вы должны отслеживать, где эти вещи должны быть обращены сейчас.
Но мы заботимся только о односвязанны.
>> Несколько вещей, которые мы собираемся иметь реализовать.
Ваша ЬурейеЕ узла структуры, Int I: Структура узла * следующий; узла.
Это ЬурейеЕ должны быть сожжены в вашем уме.
Викторина 1 следует хотели дать определение типа связанного списка узлов,
и вы должны быть в состоянии немедленно строчить, что вниз
даже не задумываясь об этом.
Я думаю, пара вопросов, почему мы должны построим здесь?
Почему мы не можем сказать узла *?
[Студент] [неразборчиво]
Да.
Единственное, что определяет узел, как вещь
является ЬурейеЕ себя.
Но на данный момент, когда мы вроде разбора через это определение узла структуры,
Мы еще не закончили нашу ЬурейеЕ еще, так что с ЬурейеЕ не закончена,
узел не существует.
Но структура узла делает, и этот узел сюда,
это также можно назвать что-либо еще.
Это можно назвать с.
Это можно было бы назвать связанный список узлов.
Его можно назвать что угодно.
Но эта структура узел должен быть названо же самое, что эта структура узла.
Что вы называете это должно быть здесь,
и так, что также отвечает на второй точке вопрос
Именно поэтому-много раз, когда вы видите структур и определения типов из структуры,
Вы увидите, анонимные структуры, где вы увидите только ЬурейеЕ структуры,
реализация структуры, словарь, или Что угодно.
>> Почему здесь мы должны сказать узла?
Почему она не может быть анонимной структуры?
Это почти тот же ответ.
[Студент] Вам нужно ссылаться на него в пределах структуры.
Да, в пределах структуры, необходимо обратиться к структуре самого.
Если вы не даете структуры имени, если это анонимная структура, вы не можете ссылаться на него.
И последнее, но не менее все они должны быть несколько прямолинейно,
и они должны помочь вам понять, если вы пишете это вниз
что вы делаете что-то неправильно, если такого рода вещи не имеют смысла.
Последнее, но не менее важно, почему это должна быть структура узла *?
Почему это не может быть просто строим узла дальше?
[Студент] Указатель на следующую структуру.
Это неизбежно, что мы хотим.
Почему бы это никогда не будет структура узла дальше?
Почему это должна быть структура узла * дальше? Да.
[Студент] Это как бесконечный цикл.
Да.
[Студент], что все будет в одном.
Да, просто думаю о том, как мы будем делать размера или что-то.
Размер структуры в основном + или - некоторые картины здесь или там.
Это в основном будет сумма размеры вещей в структуре.
Это прямо здесь, ничего не меняя, размер будет легко.
Размер структуры узла будет размером я + размер следующего.
Размер мне будет 4. Размер следующий будет 4.
Размер структуры узла будет 8.
Если мы не будем иметь *, думая о SizeOf,
Затем SizeOf (I) будет 4.
Размер структуры узла следующий будет размером я + размер структуры узла следующего
+ Размер я + размер структуры узла следующего.
Было бы бесконечной рекурсии узлов.
Вот почему все это так должно быть.
>> Опять же, обязательно запомните, что,
или, по крайней мере, понять, достаточно того, что вы можете быть в состоянии
Причиной через то, что она должна выглядеть.
То, что мы собираемся хотим реализовать.
Если длина списка
Вы можете обманывать и держать вокруг
глобальные длины или что-то, но мы не собираемся этого делать.
Мы собираемся, чтобы подсчитать длину списка.
Мы содержится, так что это в основном, как поиск,
поэтому у нас есть связанный список целых чисел, чтобы увидеть, если это число находится в связанном списке.
Присоединение будет вставить в начале списка.
Append собирается включить в конце.
Insert_sorted будет вставить в упорядоченные позиции в списке.
Insert_sorted вид предполагает, что вы никогда не использовали начало или конец в плохих отношениях.
>> Insert_sorted, когда вы реализуете insert_sorted-
скажем, у нас есть связанный список.
Это то, что в настоящее время он выглядит, 2, 4, 5.
Я хочу, чтобы вставить 3, так как пока сам список уже отсортирован,
легко найти, где 3 принадлежит.
Я начинаю в 2.
Ладно, 3 больше, чем 2, поэтому я хочу, чтобы продолжать идти.
Ах, 4 слишком большой, так что я знаю 3 будет идти между 2 и 4,
и у меня есть, чтобы исправить указатели и все такое.
Но если мы не будем использовать строго insert_sorted,
хотелось давайте просто скажем, я предварять 6,
Затем мой связанного списка станет этим.
В настоящее время она не имеет никакого смысла, поэтому для insert_sorted, можно только предположить,
что список отсортирован, хотя существуют операции
которые могут привести к не быть отсортированы, вот и все.
Найти полезным вставка-так это те основные вещи, которые вы будете иметь реализовать.
>> Сейчас, найдите минутку, чтобы сделать длину и содержит,
и те должны быть относительно быстро.
Близится время закрытия, так что у кого ничего длину или содержит?
Они собираются, чтобы быть почти идентичными.
[Студент] Длина.
Давайте посмотрим, пересмотр.
Хорошо.
Вы хотите, чтобы объяснить?
[Студент] Я просто создать указатель узлов и инициализировать его к первому, который является нашей глобальной переменной,
а потом проверить, если это нулевой, поэтому я не получаю сегменте вина и возвращать 0, если это так.
В противном случае, я цикле, отслеживание в течение целого
Сколько раз я обращался к следующему элементу списка
и в том же операцию приращения также доступ к этой фактической элемент,
и тогда я непрерывно сделать проверку, чтобы увидеть, если это NULL,
и если он нулевой, то он прерывает и просто возвращает количество элементов я доступен.
>> [Rob B.] Кто-нибудь есть какие-либо комментарии на что-нибудь?
Это выглядит прекрасно правильность мудро.
[Студент] Я не думаю, что вам нужно узла == NULL.
Да, так что если узел == NULL 0 возвращению.
Но если узел == NULL, то это-о-о, есть корректности вопроса.
Это было просто вы возвращении я, но это не входит в комплект прямо сейчас.
Вам просто нужно Int я, так что я = 0.
Но если узел является нулевым, то я по-прежнему будет 0,
и мы собираемся возвращать 0, так что этот случай является одинаковым.
Другая распространенная вещь, чтобы сохранить декларацию
узлов внутри цикла.
Можно сказать, что-о-о, нет.
Давайте держать это как это.
Я бы, наверное положить Int = 0 здесь,
Затем узел * = первый узел здесь.
И это, наверное, как-избавиться от этого сейчас.
Это, наверное, как бы я написал.
Кроме того, можно-смотря на это, как это.
Этот цикл структура прямо здесь
должна быть почти столь же естественно для вас, как и для Int я = 0
Я меньше, чем длина массива я + +.
Если это, как вы итерации по массиву, это, как вы итерацию по списку.
>> Это должно быть второй натурой в некоторой точке.
Имея это в виду, это будет почти то же самое.
Вы собираетесь хотите перебрать связанного списка.
Если узел-я понятия не имею, что величина называется.
Я узла.
Если значение в этом узле = я вернусь, правда, и это все.
Обратите внимание, что только так мы когда-нибудь вернуться ложным
, если мы перебора всей связанный список и никогда не возвращаться правда,
так это то, что она делает.
Как примечание стороны, мы, вероятно, не получите, чтобы добавить начале или в конце.
>> Быстрый последней ноты.
Если Вы видите статическую ключевым словам, так скажем статического количество Int = 0,
Затем мы делаем фото + +, вы можете в основном думают о нем как о глобальной переменной,
хотя я только что сказал, что это не так, как мы собираемся реализовать длины.
Я делаю это здесь, а потом рассчитывать + +.
В любом случае, мы можем войти узла в нашем связанного списка мы увеличивая наш счет.
Суть этого является то, что статическая ключевое слово значит.
Если бы я только что соипЬ = 0, что будет регулярно старых глобальных переменных.
Что статического Int количество средств является то, что глобальная переменная за этот файл.
Это невозможно для некоторых других файлов,
хотелось думать о PSET 5, если вы начали.
Вы оба speller.c, и у вас есть dictionary.c,
и если вы просто объявить глобальную вещь, то ничего в speller.c
можно получить в dictionary.c и наоборот.
Глобальные переменные доступны любому. Файл с,
но статические переменные доступны только внутри самого файла,
так что внутри проверку орфографии или внутри dictionary.c,
это вроде как бы я заявляю о своем переменной для размера моей массива
или размер моего количество слов в словаре.
Так как я не хочу, чтобы объявить глобальную переменную, что кто-то имеет доступ,
Я действительно заботятся только о нем для моих собственных целей.
>> Хорошая вещь об этом также весь материал столкновения имя.
Если некоторый другой файл пытается использовать глобальную переменную с именем графа, все идет очень, очень неправильно,
так что это хорошо держит вещи безопасны, и только вы можете получить к нему доступ,
и никто другой не может, и если кто-то заявляет, глобальная переменная называется граф,
то он не будет вмешиваться в вашу статической переменной кол.
Это то, что является статическим. Это файл глобальных переменных.
>> Вопросы о чем-нибудь?
Все готово. Пока.
[CS50.TV]