[Powered by Google Translate] [6 هفته ادامه]
[دیوید J. مالان] [دانشگاه هاروارد]
[این CS50.] [CS50.TV]
این CS50 است و این است که در پایان هفته 6.
بنابراین CS50x، یکی از دوره های اول دانشگاه هاروارد که در طرح EDX
در واقع عرضه این دوشنبه گذشته.
اگر شما می خواهم نگاهی اجمالی به آنچه که دیگران در اینترنت
در حال حاضر به دنبال همراه با، شما می توانید به x.cs50.net سر.
که شما را به جای مناسب در edx.org هدایت،
که بود که در آن این و دوره های دیگر از MIT و برکلی در حال حاضر زندگی می کنند.
شما باید ثبت نام برای یک حساب کاربری پیدا خواهید کرد که مواد تا حد زیادی همان
شما تا به حال این ترم، البته از چند هفته به تعویق افتاد، که ما همه چیز آماده است.
اما آنچه که دانش آموزان در CS50x هم اکنون خواهید دید، رابط کاربری کاملا شبیه به این است.
این، برای مثال، Zamyla پیشرو walkthrough برای مجموعه مشکل 0 است.
پس از ورود به edx.org، یک دانشجوی CS50x می بیند چیزها
شما انتظار می رود تا در یک دوره را مشاهده کنید: سخنرانی برای روز دوشنبه،
سخنرانی برای چهارشنبه، شلوارک های مختلف، مجموعه مشکل، walkthroughs، پی دی اف.
در علاوه بر این، همانطور که شما اینجا را ببینید، ترجمه ماشین
از رونوشت های انگلیسی به چینی، ژاپنی، اسپانیایی، ایتالیایی،
و یک دسته کامل از زبان های دیگر است که قطعا ناقص
که ما آنها را رول از برنامه نویسی با استفاده از چیزی به نام API،
و یا برنامه رابط برنامه نویسی، از گوگل
است که به ما اجازه می دهد برای تبدیل زبان انگلیسی به این زبان های دیگر.
اما به لطف روح فوق العاده از صد به علاوه برخی از داوطلبان،
مردم به طور تصادفی بر روی اینترنت که با مهربانی پیشنهاد برای درگیر شدن
در این پروژه، ما به تدریج خواهید بهبود کیفیت از آن ترجمه می شود
با داشتن انسانها در اصلاح اشتباهات است که رایانه های ما را ساخته اند.
>> بنابراین به نظر می رسد خارج ما چند دانش آموزان نشان می دهد تا به حال در تاریخ دوشنبه از ما در ابتدا انتظار می رود.
در واقع، در حال حاضر CS50x دارای 100،000 نفر همراه پس از در خانه می باشد.
بنابراین شما همه بخشی از تحقق این کلاس افتتاحیه این دوره در علم کامپیوتر
آموزش و پرورش به طور کلی تر، گسترده تر، در دسترس است.
و واقعیت این است در حال حاضر با برخی از این دوره ها گسترده آنلاین،
همه آنها با این ارقام بسیار بالا شروع می شود، همانطور که ما به نظر می رسد که در اینجا انجام داده است.
اما هدف، در نهایت، برای CS50x است واقعا به مردم به عنوان بسیاری از به خط پایان به عنوان امکان پذیر است.
طراحی، CS50x رفتن به از این دوشنبه گذشته ارائه می شود
تمام راه را از طریق آوریل 15 2013، به طوری که مردمی که به تعهدات مدرسه در جای دیگر،
کار، خانواده، درگیری و مانند آن، انعطاف پذیری کمی بیشتر
که با آن به شیرجه رفتن به این دوره، که، کافی است برای گفتن،
کاملا ممنوعه انجام می شود در صورتی که فقط در طول این دوره از سه ماه در طول یک ترم معمول است.
اما این دانش آموزان خواهد شد مقابله با مجموعه مشکل مشابه، مشاهده محتوا،
داشتن دسترسی به همان شورت و مانند آن است.
به طوری که همه ما واقعا در این را با هم تحقق بخشد.
و یکی از اهداف پایان CS50x است فقط برای گرفتن مردمی به عنوان بسیاری از
به خط پایان و به آنها این درک تازه کشف شده در علوم کامپیوتر را
و برنامه نویسی بلکه به آنها این تجربه مشترک.
یکی از ویژگی های از 50 تعریف در محوطه دانشگاه، ما امیدواریم که،
این نوع تجربه جمعی، بوده است، گاهی اوقات برای بهتر شدن یا بدتر شدن
اما پس از این مردم را به به سمت چپ و به سمت راست به نوبه خود،
و ساعات اداری و hackathon و عادلانه است.
از آن کمی سخت تر برای انجام این کار است که در شخص با مردمی آنلاین،
اما CS50x در ماه آوریل با اولین CS50 نمایشگاه نتیجه گیری،
که تطابق آنلاین از نظر ما در این نمایشگاه خواهد بود
که در آن این هزاران نفر از دانش آموزان دعوت خواهد شد به ارائه 1 - فیلم 2 دقیقه ای،
یا یک ضبط ویدیویی از صفحه از پروژه نهایی و یا تصویری خود را از آنها با تکان دادن خوش آمدید
و صحبت کردن در مورد پروژه خود و demoing آن،
بسیار شبیه به پیشینیان خود را در اینجا در این نمایشگاه در محوطه دانشگاه انجام می شود.
به طوری که در پایان ترم، به این امید است که یک نمایشگاه جهانی
پروژه های نهایی دانش آموزان CS50x، بسیار شبیه به آن است که در انتظار شما دسامبر امسال در محوطه دانشگاه.
بنابراین بیشتر در مورد که در ماههای آینده است.
>> با 100.000 دانش آموزان، هر چند، می آید نیاز به چند CA های دیگر است.
با توجه که شما بچه ها دنباله دنباله در اینجا و گرفتن CS50
چند هفته پیش از انتشار این مواد را به مردمی در EDX،
درک عشق ما را به عنوان بسیاری از دانش آموزان خود ما که ممکن است در این ابتکار شامل،
هر دو در طول ترم و همچنین این زمستان و این بهار آینده.
بنابراین اگر شما می خواهم برای درگیر شدن در CS50x،
به ویژه پیوستن در CS50x بحث، نسخه EDX CS50 گفتگو
که بسیاری از شما در محوطه دانشگاه شده اند با استفاده از تخته بولتن آنلاین،
لطفا سر به آن URL، به ما اطلاع دهید که شما،
چون ما دوست داریم برای ساخت یک تیم از دانشجویان و کارکنان و اعضای هیات علمی به طور یکسان
در محوطه دانشگاه که به سادگی بازی همراه و کمک است.
و هنگامی که آنها را ببینید سوال که آشنا به آنها،
شما می شنوید یک دانش آموز در گزارش برخی از اشکال در جایی خارج وجود دارد در برخی از کشور بر روی اینترنت،
و بل که حلقه به خاطر شما هم همین مسئله بود که
خود را در D-سالن چند وقت پیش، امیدوارم پس از آن شما می توانید در صدای سنج ایجاد کردن و به اشتراک گذاشتن تجربه خود را.
پس از انجام لطفا شریک اگر شما می خواهم.
>> دروس علوم کامپیوتر در دانشگاه هاروارد، یک بیت از یک سنت،
CS50 در میان آنها، داشتن برخی از پوشاک، برخی از لباس ها، که شما می توانید با افتخار پوشیدن
در پایان ترم، گفت: کاملا با افتخار است که شما به پایان رسید CS50
و در زمان CS50 و مانند آن است، و ما همیشه سعی کنید به دانش آموزان شامل
در این فرآیند به عنوان آنجا که ممکن است، به موجب آن دعوت می کنیم،
در اطراف این زمان ترم، دانش آموزان به ارائه طرح
با استفاده از فتوشاپ یا هر نرم افزار بهترین انتخاب شما می خواهم به استفاده از
اگر شما یک طراح، به ارائه طرح برای تی شرت و میگذارند
و چتر و bandanas کمی برای سگ ما در حال حاضر و مانند آن.
و همه چیز - برندگان در هر سال پس از آن به نمایش گذاشته شده
در وب سایت دوره store.cs50.net.
همه چیز در هزینه وجود دارد به فروش می رسد، اما وب سایت خود را اجرا می کند
و اجازه می دهد تا مردم را به انتخاب رنگ و طرح است که آنها دوست دارند.
بنابراین من فکر می کنم ما فقط می خواهم اشتراک گذاشتن برخی از طرح های سال گذشته
که بر روی وب سایت علاوه بر این یکی در اینجا است که یک سنت سالانه است.
"هر روز من SEG Faultn" یکی از مطالب ارسالی سال گذشته،
که هنوز هم در دسترس وجود دارد برای فارغ التحصیلان.
ما تا به حال این یکی، CS50، تاسیس سال 1989. "
یکی از Bowdens ما، چپاول، بسیار محبوب بود در سال گذشته است.
"تیم Bowden" متولد شد، این طرح، در میان پرفروش ترین ها ارائه شد.
در حالی بود که این یکی در اینجا. بسیاری از مردم، "تب Bowden" با توجه به سیاهههای مربوط به فروش.
این را فهم کنید که در حال حاضر می تواند طراحی خود را بر روی اینترنت.
جزئیات بیشتر در مورد این مشکل بعدی این مجموعه آمده است.
>> یکی دیگر از ابزار: شما تا به حال برخی از در معرض این بیماری قرار گرفتن رخ می دهند و خوشبختانه در حال حاضر
برخی از تجربه دست با GDB،
است که، البته، دیباگر و به شما اجازه می دهد تا به دستکاری
برنامه خود را در یک سطح نسبتا کم، انجام چه نوع از همه چیز؟
چه GDB به شما اجازه انجام این کار؟
آره؟ به من چیزی بدهد. [پاسخ دانشجویی، ناخوانا]
خوب است. گام به تابع، بنابراین شما نه تنها باید به نوع اجرا
و ضربه برنامه را از طریق تمامیت آن، چاپ کردن همه چیز را به خروجی استاندارد است.
در عوض، شما می توانید از طریق آن خط خط به گام، یا تایپ بعدی
برای رفتن به خط خط به خط و یا گام به شیرجه رفتن به یک تابع، به طور معمول یکی است که شما نوشت.
چه چیز دیگری می کند GDB به شما اجازه انجام این کار؟ آره؟ [پاسخ دانشجویی، ناخوانا]
چاپ متغیر است. بنابراین اگر شما می خواهید برای انجام یک درون گرایی کمی در داخل برنامه شما
بدون نیاز به توسل به نوشتن بیانیه printf در همه جا،
شما فقط می توانید یک متغیر را چاپ و یا نمایش یک متغیر است.
چه چیز دیگری می تواند شما را با یک دیباگر مثل GDB انجام دهید؟
[پاسخ دانشجویی، ناخوانا]
دقیقا. شما می توانید تعیین نقاط شکست، شما می توانید اعدام استراحت می گویند
در تابع اصلی یا عملکرد صنایع غذایی.
شما می توانید از اعدام استراحت در خط 123 می گویند.
نقاطانفصال هستند واقعا یک تکنیک قدرتمند
چرا که اگر شما یک حس کلی از جایی که مشکل شما را دارند
احتمالا شما مجبور به اتلاف وقت قدم به قدم از طریق به طور کامل این برنامه.
شما اساسا می تواند به سمت راست وجود دارد پرش و سپس شروع به تایپ -
قدم به قدم از طریق آن با مرحله و یا در کنار و یا مانند.
اما گرفتن با چیزی شبیه به GDB این است که این به شما کمک می کند، انسان،
پیدا کردن مشکلات خود و پیدا کردن اشکالات خود را.
آن را لزوما آنها را بسیار برای شما خواهد شد.
>> بنابراین ما معرفی style50 روز دیگر، کوتاه است که یک ابزار خط فرمان
است که تلاش می کند تا سبک خاصی دراوردن کد خود را کمی بیشتر پاک از شما، انسان، ممکن است انجام داده اند.
اما این، بیش از حد است، واقعا فقط یک چیز زیبایی است.
اما به نظر می رسد از این ابزار دیگر به نام Valgrind است که کمی پیچیده تر به استفاده از وجود دارد.
خروجی آن است atrociously مرموز در نگاه اول می باشد.
اما زیبا و مفید است، به خصوص در حال حاضر که ما در بخشی از این اصطلاح
جایی که شما در حال شروع به استفاده از malloc و تخصیص حافظه پویا.
چیزهایی که واقعا، واقعا اشتباه می تواند به سرعت.
از آنجا که اگر شما فراموش نکنید که به حافظه آزاد خود را، و یا شما dereference برخی از اشاره گر NULL،
و یا شما dereference برخی از اشاره گر زباله است، چه به طور معمول نشانه است که نتایج؟
SEG گسل. و شما می توانید این فایل اصلی برخی از شماره کیلوبایت یا مگابایت
است که نشان دهنده وضعیت حافظه برنامه خود را هنگامی که آن سقوط کرد،
اما برنامه های خود را در نهایت SEG گسل، تقسیم بندی گسل،
به این معنی است که اتفاق بدی افتاده است تقریبا همیشه مربوط
به اشتباه مرتبط با حافظه است که شما ساخته شده است در جایی.
بنابراین Valgrind کمک می کند تا چیزهایی مثل این را پیدا کنید.
این ابزاری است که شما را اجرا، مانند GDB، بعد از شما وارد برنامه شما،
اما به جای اجرای برنامه های خود را به طور مستقیم، شما را اجرا Valgrind
و شما را به آن منتقل می کند برنامه های خود را، درست مثل شما با GDB.
در حال حاضر، استفاده، برای بدست آوردن بهترین نوع خروجی،
کمی طولانی است، به طوری که سمت راست وجود دارد در بالای از صفحه نمایش شما Valgrind-V را ببینید.
"V" تقریبا جهانی به معنی دراز زمانی که شما با استفاده از برنامه بر روی یک کامپیوتر لینوکس است.
بنابراین آن را به معنی تف داده ها بیش از شما ممکن است به طور پیش فرض است.
"- نشت چک = کامل است." این فقط گفت: چک برای نشت حافظه،
اشتباهات که من ممکن را ساخته اند. این، بیش از حد، یک پارادایم مشترک با برنامه های لینوکس است.
به طور کلی، اگر شما یک آرگومان خط فرمان است که یک "تعویض" است،
که قرار است به منظور تغییر رفتار این برنامه است، و آن را تنها یک حرف است،
آن را V، اما در صورتی که تغییر، فقط طراحی شده توسط برنامه نویس،
یک کلمه یا مجموعه ای کامل از کلمات، آرگومان خط فرمان شروع می شود -.
اینها فقط کنوانسیون انسان است، اما شما می توانید آنها را به طور فزاینده ای را ببینید.
و سپس، در نهایت، "a.out" نام دلخواه برای برنامه در این مثال خاص می باشد.
و در اینجا برخی از نماینده خروجی است.
>> قبل از اینکه ما در آنچه که ممکن است به معنی نگاه کنید، به من اجازه رفتن به یک قطعه از کد را در اینجا.
و اجازه دهید از این حرکت من از راه، به زودی،
و اجازه دهید یک نگاهی به memory.c است، که این مثال های کوتاه در اینجا.
بنابراین در این برنامه، به من اجازه زوم در توابع و پرسش.
ما باید یک عملکرد اصلی است که فراخوانی یک تابع، f،
و پس از آن چه F اقدام به انجام این کار، به زبان انگلیسی کمی فنی؟
چه F اقدام به انجام؟
چگونه در مورد من با خط 20 شروع، و محل سکونت ستاره مهم نیست،
اما من فقط سازگار باشد در اینجا با سخنرانی گذشته است.
خط 20 را برای ما؟ در سمت چپ. ما می خواهیم آن را شکستن بیشتر است.
هوشمند *: X: چه کاری انجام دهید؟
باشه. این اعلام یک اشاره گر است، و حالا حتی بیشتر فنی است.
به چه معنی است، بسیار مشخص است، یک اشاره گر به اعلام؟ شخص دیگری؟
آره؟ [پاسخ دانشجو، ناخوانا] بیش از حد.
بنابراین شما در حال خواندن به سمت راست علامت مساوی است.
اجازه بدهید تمرکز درست در سمت چپ، فقط در نوع int * X است.
این بدان "اعلام" یک اشاره گر است، اما در حال حاضر بیایید در عمیق تر به این تعریف شیرجه رفتن.
چه که مشخص، از نظر فنی چیست؟ آره؟
[پاسخ دانشجویی، ناخوانا]
باشه. آماده شدن برای نجات یک آدرس در حافظه است.
خوب است. و اجازه دهید این یک مرحله دیگر آن اعلام یک متغیر x، که 32 بیت است.
و من می دانم که این 32 بیت به دلیل -؟
به این دلیل است که آن را از نوع int، زیرا این یک اشاره گر را در این مورد نیست.
تصادفی نیست که آن را یکی و همین کار را با بین المللی،
اما این واقعیت است که این ستاره وجود دارد به معنای این است که یک اشاره گر وجود دارد
و در دستگاه، با بسیاری از کامپیوترها، اما نه همه، اشاره گر 32 بیت هستند.
بر روی سخت افزار های مدرن تر مانند مکینتاش، رایانه های شخصی، شما ممکن است اشاره گر 64 بیتی داشته باشد،
اما در دستگاه، این چیز ها 32 بیت.
کنیم که در آن استاندارد است. مشخص، داستان می رود به شرح زیر است:
ما "اعلام" یک اشاره گر؛ چه معنا است؟
ما آماده برای ذخیره یک آدرس حافظه است.
به چه معنا است؟
متغیر x نامیده می شود که طول می کشد تا 32 بیت ایجاد می کنیم
که به زودی آدرس یک عدد صحیح را ذخیره کنید.
و این احتمالا به عنوان دقیق که می توانید.
خوب در حال حرکت رو به جلو به ساده و فقط می گویند به اعلام یک اشاره گر به نام X است.
تعریف اشاره گر، اما تحقق و درک آنچه در واقع در رفتن
حتی در فقط کسانی که چند کاراکتر است.
>> در حال حاضر، این یکی تقریبا یک کمی آسان تر است، حتی اگر آن را در یک عبارت طولانی تر است.
بنابراین این انجام می دهند، که برجسته شده در حال حاضر: "malloc (10 * sizeof (INT))؛" آره؟
[پاسخ دانشجویی، ناخوانا]
خوب است. و من آن را وجود دارد. این تخصیص یک تکه از حافظه به مدت ده عدد صحیح است.
و حالا شیرجه در کمی عمیق تر اجازه دهید آن را به تخصیص یک تکه از حافظه به مدت ده عدد صحیح است.
چه malloc و سپس بازگشت؟
آدرس که تکه های، یا، مشخص تر، آدرس بایت اول که تکه.
پس چگونه من، برنامه نویس، می دانم که که آن تکه از حافظه به پایان می رسد؟
من می دانم که آن را به هم پیوسته است. Malloc، با تعریف شما را یک تکه به هم پیوسته از حافظه است.
شکاف در آن وجود ندارد. شما دسترسی برای هر بایت در آن تکه،
برگشت به پشت به پشت، اما چگونه من می دانم که در آن از پایان این قطعه از حافظه است؟
هنگامی که malloc استفاده می کنید؟ [پاسخ دانشجو، ناخوانا] خوب.
شما نمی کنند. شما باید به یاد داشته باشید.
من را به خاطر داشته باشید که من با استفاده از مقدار 10، و من حتی به نظر می رسد که انجام داده است که در اینجا.
اما این تعهد به طور کامل بر روی من. Strlen، که ایم کمی متکی به رشته ها تبدیل شده است،
با این نسخهها کار فقط به این دلیل از این کنوانسیون از داشتن \ 0
یا این شخصیت خاص پوچ، پوچ، در پایان یک رشته.
که فقط برای تکه های دلخواه از حافظه را نگه نمی.
آن را به شما است. بنابراین خط 20، پس از آن، اختصاص یک تکه از حافظه
است که می تواند ده عدد صحیح، ذخیره سازی و آن را ذخیره آدرس اولین بایت
که تکه های حافظه در متغیر x به نام.
بنابر این، است که یک اشاره گر است. بنابراین خط 21، متاسفانه، یک اشتباه بود.
اما در ابتدا، آنچه در آن است انجام شده است؟ این فروشگاه گفت: در محل 10، 0 ایندکس،
تکه از حافظه به نام X 0 ارزش است.
>> یک زن و شوهر از چیزهایی که در حال رفتن به اطلاع می دهد.
حتی اگر X یک اشاره گر است، از چند هفته پیش به یاد
است که شما هنوز هم می توانید آرایه به سبک مربع علامت کروشه استفاده کنید.
چرا که در واقع نماد برای حساب بیشتر مرموز، به دنبال اشاره گر کوتاه دست است.
که در آن ما را چیزی شبیه به این را انجام دهید: نگاهی به آدرس X، حرکت 10 نقاط بیش از،
پس از آن وجود دارد که به هر آدرس در آن محل ذخیره شده است بروید.
اما صادقانه بگویم، این است که فقط همین به خواندن و راحت با.
بنابراین جهان به طور معمول با استفاده از براکت مربع فقط به خاطر اینکه آن را خیلی بیشتر انسان دوستانه به خواندن.
اما این چیزی است که واقعا در زیر هود؛
X یک آدرس، یک آرایه، و در هر سه است.
پس این است که ذخیره سازی 0 در محل 10 در X است.
چرا این بد است؟ آره؟
[پاسخ دانشجویی، ناخوانا] دقیقا.
ما فقط اختصاص داده ده نوع داده int، اما ما از 0 تعداد در هنگام برنامه نویسی در C،
بنابراین شما باید دسترسی به 0 10 1 2 3 4 5 6 7 8 9، اما نه.
بنابراین یا این برنامه رفتن به گسل SEG یا آن نیست.
اما ما واقعا نمی دانند که این نوع رفتار nondeterministic.
این واقعا در مورد اینکه آیا ما خوش شانس بستگی دارد.
اگر آن را معلوم می کند که سیستم عامل مهم نیست اگر من استفاده از آن بایت اضافی،
حتی اگر آن را به من داده نشده است، برنامه ممکن است سقوط.
خام، حشره دار، اما شما ممکن است این علامت را نمی بینید،
و یا شما ممکن است آن را تنها یک بار در در حالی که.
اما واقعیت این است که اشکال است، در واقع، وجود دارد.
و این واقعا مشکل اگر شما نوشته شده است برنامه ای است که شما می خواهید می شود درست است،
که شما به فروش می رسد برنامه ای است که مردم در حال استفاده از آن در هر یک بار در در حالی که سقوط کرد
از آنجا که، البته، این خوب نیست. در واقع، اگر شما یک تلفن همراه آندروید یا آیفون
و برنامه های شما دانلود این روزها، اگر شما تا به حال یک برنامه ترک،
تمام آن را به طور ناگهانی ناپدید می شود، که تقریبا همیشه نتیجه برخی از موضوع های مربوط به حافظه،
که در آن برنامه نویس پیچ و بصورت غیر مرجع اشاره گر
که او یا او نباید داشته باشد، و در نتیجه از در iOS یا Android است که فقط به کشتن این برنامه به طور کلی
به جای رفتار با ریسک تعریف نشده و یا به نوعی از سازش امنیت.
>> یک اشکال دیگر در این برنامه علاوه بر این یکی وجود دارد.
چه چیز دیگری که من در این برنامه پیچ؟
من تمرین آنچه که من موعظه. آره؟
[پاسخ دانشجو، ناخوانا] خوب.
من به حافظه آزاد است. بنابراین قاعده کلی در حال حاضر
است که باید در هر زمان با شما تماس malloc، شما باید تماس رایگان هنگامی که شما انجام می شود با استفاده از این حافظه است.
در حال حاضر، زمانی که من می خواهم این حافظه به آزاد؟
احتمالا، با فرض این خط اول درست بود، من می خواهم در اینجا به آن را انجام دهد.
از آنجا که من می توانم به عنوان مثال، نه، این کار را انجام را در اینجا. چرا؟
فقط از دامنه. بنابراین حتی اگر ما در حال صحبت کردن در مورد اشاره گر،
این هفته 2 یا 3 شماره، که در آن X است تنها در محدوده داخل آکولاد که در آن اعلام شد.
بنابراین شما قطعا می تواند این برنامه رایگان نیست وجود دارد. تنها شانس من این برنامه رایگان است که تقریبا بعد از خط 21.
این یک برنامه نسبتا ساده است، آن را نسبتا آسان بود، هنگامی که شما از نوع پیچیده و ذهن شما را
پیرامون آنچه که این برنامه انجام می دهند، که در آن اشتباهات بود.
و حتی اگر آن را در ابتدا نمی بینم، امیدوارم آن را کمی واضح در حال حاضر
که این اشتباهات خیلی به راحتی حل شده و به راحتی ساخته شده است.
اما هنگامی که یک برنامه است که به طول بیش از 12 خط 50 خط طولانی، 100 صف های طولانی،
راه رفتن را از طریق خط کد شما خط، از طریق آن فکر منطقی،
امکان پذیر است، اما به ویژه سرگرم کننده برای انجام این کار، به طور مداوم به دنبال اشکالات،
و آن را نیز به سختی انجام دهد، و به همین دلیل است که یک ابزار مانند Valgrind وجود دارد.
اجازه دهید من به جلو بروید و این کار: اجازه باز کردن پنجره ترمینال من من،
و من نه تنها اجرا حافظه، به دلیل حافظه به نظر می رسد خوب است.
من خوش شانس. رفتن که بایت های اضافی در پایان از آرایه
به نظر نمی رسد بیش از حد مشکل است.
اما به من اجازه دهید، با این حال، انجام یک بررسی سلامت عقل، که تنها به معنی چک
یا نه این است که در واقع درست است.
>> بنابراین اجازه دهید valgrind-V - نشت بررسی = کامل،
و پس از آن به نام برنامه در این مورد، حافظه، a.out است.
پس جلو بروید و اجازه دهید این کار را انجام. آمار را وارد کنید.
عزیز خدا. این خروجی آن است، و این همان چیزی است که من تا قبل از آن اشاره است.
اما، اگر شما یاد می گیرید را از طریق تمام مزخرف را در اینجا بخوانید،
بسیاری از این فقط خروجی تشخیصی است که که جالب نیست.
چه چشم خود را واقعا می خواهد به دنبال هر گونه اشاره ای به خطا یا نامعتبر است.
کلماتی را که نشان می دهد مشکلات.
و در واقع، بیایید ببینید چه خبر است اینجا کلیک کنید یا با اشتباه پایین.
من خلاصه ای از برخی از مرتب کردن بر اساس، در استفاده از خروجی: 40 بایت در 1 بلوک "
من واقعا مطمئن نیست آنچه که به یک بلوک است با این حال، اما 40 کلمه در ادامه متن
در واقع احساس می کنم توانستم بفهمم که در آن است که از.
40 بایت است. چرا 40 بایت استفاده در خروج؟
و بیشتر به طور خاص، اگر ما در پایین حرکت کنید در اینجا،
چرا که من قطعا از دست داده 40 بایت؟ آره؟
[پاسخ دانشجویی، ناخوانا] کامل. بله، دقیقا.
ده اعداد صحیح وجود دارد، و هر یک از آن ها به اندازه 4 یا 32 بیت،
بنابراین من از دست داده ایم دقیقا 40 بایت است، زیرا شما را به عنوان پیشنهاد من به نام آزاد نیست.
این یک اشکال است، و در حال حاضر اجازه دهید نگاه کردن کمی بیشتر کنید و ببینید که در کنار این،
"نامعتبر از اندازه 4 ارسال." در حال حاضر این چیست؟
این آدرس بیان شده است نماد پایگاه، ظاهرا؟
این هگزادسیمال است، و هر زمان به شما یک شماره با 0x آغاز،
هگزادسیمال، به این معنی است که ما راه برگشت، من فکر می کنم، بخش pset 0 از سوالات،
بود که فقط انجام یک ورزش warmup چون، تبدیل دهدهی به هگزا دسیمال به باینری و غیره.
هگزادسیمال، فقط با کنوانسیون انسان، است که معمولا مورد استفاده قرار گیرد برای نشان دادن اشاره گر
یا، به طور کلی، آدرس. این فقط یک کنوانسیون،
زیرا آن را کمی ساده تر برای خواندن، آن را کمی جمع و جور تر از چیزی شبیه به دهدهی،
و باینری به بی فایده است برای بسیاری از انسان ها را به استفاده از.
بنابراین در حال حاضر به چه معنی است؟ خب، به نظر می رسد مثل نوشتن نامعتبر وجود دارد
اندازه 4 در خط 21 از memory.c.
بنابراین بازگشت به خط 21، و در واقع، در اینجا این است که نوشتن نامعتبر است.
بنابراین Valgrind است که قصد ندارم به طور کامل به دست من و به من بگویید چه ثابت است،
اما این تشخیص است که من انجام می دهند نوشتن نامعتبر است.
من دست زدن به 4 بایت است که من نباید باشد، و ظاهرا به این دلیل که،
به عنوان که شما اشاره کردید، من انجام می دهند [10] به جای [9] حداکثر
[0] یا چیزی در میان است.
با Valgrind، تحقق بخشیدن به هر زمان شما در حال حاضر نوشتن یک برنامه
است که با استفاده از اشاره گر و استفاده از حافظه، و malloc بیشتر به طور خاص،
قطعا به عادت در حال اجرا این مدت
اما به راحتی کپی و جا به جا فرمان Valgrind
برای دیدن برخی از اشتباهات در آنجا وجود دارد.
و قریب به اتفاق قربانیان آن خواهید بود هر زمان که شما خروجی،
اما تنها از طریق تجزیه و تحلیل بصری خروجی و ببینید اگر شما می بینید اشاره از اشتباهات
و یا هشدار و یا نامعتبر است و یا از دست داده است.
هر واژه ای که صدا مانند شما screwed تا جایی.
پس متوجه باشید که یک ابزار جدید در جعبه ابزار خود را دارد.
>> در حال حاضر در تاریخ دوشنبه، ما تا به حال یک دسته از مردمی می آیند تا در اینجا
و نشان دادن مفهوم یک لیست پیوندی است.
و ما معرفی لیست پیوندی به عنوان یک راه حل چه مشکلی؟
آره؟ [پاسخ دانشجو، ناخوانا] خوب.
آرایه ها نیست می تواند حافظه به آنها اضافه شده است.
اگر شما اختصاص آرایه ای از اندازه 10، که شما می توانید.
شما می توانید یک تابع مانند بازتخصیص اگر شما در ابتدا به نام malloc تماس بگیرید،
و که می توانید سعی کنید به رشد آرایه اگر فضا به سمت انتهای آن وجود دارد
که هیچ کس به دیگری با استفاده از، و اگر وجود دارد، آن را فقط به شما یک تکه بزرگتر در جایی دیگر.
اما سپس آن را به تمام کسانی که بایت به آرایه جدید کپی کنید.
این برای تلفن های موبایل مانند یک راه حل بسیار درست است.
چرا این غیرجذاب است؟
منظور من آن را با این نسخهها کار، انسان را به حل این مشکل است.
چرا ما نیاز به آن در روز دوشنبه حل و فصل با لیست های پیوندی؟ آره؟
[پاسخ دانشجویی، ناخوانا] این می تواند مدت زمان طولانی را.
در واقع، هر زمان که شما خواستار malloc یا بازتخصیص یا calloc است، که در عین حال یکی دیگر از،
هر زمان شما، این برنامه، در حال صحبت کردن به سیستم عامل،
شما تمایل به سرعت برنامه پایین.
و اگر شما در حال انجام این نوع از چیز ها را در حلقه، شما واقعا کاهش چیزهایی پایین.
شما در حال رفتن به اطلاع این ساده "سلام جهان" نوع برنامه،
اما در برنامه های بسیار بزرگتر و درخواست از سیستم عامل را دوباره و دوباره برای حافظه
و یا به آن بازگشت دوباره و دوباره تمایل به یک چیز خوب است.
علاوه بر این، فقط مرتب کردن بر اساس عقل - این یک اتلاف وقت است.
چرا به حافظه اختصاص دهد بیشتر و بیشتر، خطر کپی کردن همه چیز را به آرایه جدید،
اگر شما یک جایگزین است که به شما اجازه می دهد تا به حافظه اختصاص دهد تنها به همان اندازه که شما در واقع نیاز است؟
پس مثبت و منفی در اینجا وجود دارد.
یکی از علامت + در حال حاضر این است که پویایی می باشد.
مهم نیست که در آن تکه از حافظه هستند که آزاد هستند،
من فقط می تواند از ایجاد مرتب سازی بر اساس این خرده نان از طریق اشاره گر
به تمام رشته مرتبط فهرست من با هم.
اما من پرداخت حداقل یک قیمت است.
>> چه چیزی من را در به دست آوردن لیست های پیوندی؟
آره؟ [پاسخ دانشجو، ناخوانا] خوب.
شما نیاز به حافظه بیشتر. حالا من نیاز به فضا برای این اشاره گر،
و در مورد این لیست فوق العاده ساده مرتبط
است که تنها در تلاش برای ذخیره اعداد صحیح، که 4 بایت هستند، ما حفظ و گفت
خب، یک اشاره گر 4 بایت است، بنابراین در حال حاضر من به معنای واقعی کلمه دو برابر
مقدار حافظه فقط برای ذخیره این لیست است.
اما باز هم، این معاوضه مداوم در علم کامپیوتر است
بین زمان و فضا و توسعه، تلاش ها و منابع دیگر.
یکی دیگر از حرکت نزولی با استفاده از یک لیست پیوندی چه خبر؟ آره؟
[پاسخ دانشجویی، ناخوانا]
خوب است. به عنوان آسان برای دسترسی به. ما دیگر نمی توانیم اهرم
هفته 0 اصول مانند تقسیم و حل.
و بیشتر به طور خاص، جستجو دودویی. چرا که حتی اگر ما انسان ها
تقریبا می توانید ببینید که در آن میانه از این لیست است،
کامپیوتر تنها می داند که این لیست پیوندی در آدرس ابتدا فراخوانی میشود شروع می شود.
و این 0x123 یا چیزی شبیه به آن است.
و تنها راه این برنامه می تواند عنصر میانی پیدا کنید
است که در واقع جستجو در کل لیست.
و حتی پس از آن، آن را به معنای واقعی کلمه را به جستجو در فهرست کل به دلیل
حتی یک بار عنصر میانی به شما برسد پس از اشاره گر،
شما، برنامه، هیچ نظری ندارم که چه مدت این لیست است، به طور بالقوه،
تا زمانی که شما به پایان رسید از آن، و چگونه شما می دانید برنامه نویسی
که شما در پایان یک لیست پیوندی هستید؟
یک اشاره گر NULL، تا دوباره، یک کنوانسیون وجود دارد.
به جای استفاده از این اشاره گر، ما قطعا نمی خواهید که برخی از ارزش زباله به
اشاره کردن مرحله در جایی که ما می خواهیم آن را به طرف پایین، NULL،
به طوری که در حال حاضر این پایانه در این ساختار داده را بنابراین ما می دانیم که در آن به پایان می رسد.
>> چه می شود اگر ما می خواهیم به دستکاری این؟
ما بیشتر از این بصری، و با انسان،
اما چه می شود اگر ما می خواهیم به درج؟
پس لیست اصلی، 9، 17، 20، 22، 29، 34 بود.
چه اگر ما پس از آن به فضای malloc برای شماره 55، یک گره را برای آن می خواست،
و پس از آن ما می خواهیم برای وارد کردن 55 به لیست همانطور که ما در روز دوشنبه انجام داد؟
چگونه این کار را انجام دهید؟ خوب، آنیتا آمد و او اساسا راه می رفت این فهرست است.
او در عنصر اول آغاز شده است، پس از آن بعد، بعد از، بعد از، بعد از، بعد از.
در نهایت سمت چپ تمام راه را به پایین ضربه
و متوجه شدم آه، این NULL است. پس چه دستکاری اشاره گر مورد نیاز که باید انجام شود؟
کسی بود که در پایان، شماره 34، نیاز به دست چپ خود را مطرح
به نقطه در 55، 55 نیاز به دست چپ خود را با اشاره به NULL ترمیناتور جدید. انجام شد.
بسیار آسان برای وارد کردن 55 را به یک لیست طبقه بندی شده اند.
و چگونه ممکن است این نگاه می کنید؟
>> اجازه بدهید من به جلو بروید و باز کردن برخی از کد مثال در اینجا.
من باز کردن gedit، و به من اجازه باز کردن دو فایل برای اولین بار.
یکی از list1.h، و اجازه دهید من فقط یادآوری می کنند که این قطعه از کد
که ما استفاده می شود به نمایندگی از یک گره است.
یک گره داشته باشد که هر دو از نوع int به نام N و یک اشاره گر به نام بعدی که فقط نقاط به کار بعدی در لیست است.
که در حال حاضر در یک فایل در ساعت است. چرا؟
این کنوانسیون وجود دارد، و در حال حاضر استفاده از این مقدار زیادی خودمان،
اما کسی که توابع printf و دیگر نوشت
داد به عنوان یک هدیه است که جهان از آن دسته از توابع با نوشتن یک فایل به نام stdio.h.
و سپس string.h وجود دارد، و پس از آن map.h وجود دارد، و تمام این فایل ها H وجود دارد
که شما ممکن است دیده می شود و یا در مدت نوشته شده توسط افراد دیگر استفاده می شود.
به طور معمول در آن ساعت فایل تنها چیزهایی هستند که مانند تعریف نوعهای
اعلامیه های سفارشی و یا انواع اعلامیه های ثابت است.
شما پیاده سازی توابع در فایل هدر قرار داده است.
شما قرار داده، به جای آن، فقط نمونه های اولیه خود را.
شما چیزهایی که شما می خواهید برای به اشتراک گذاشتن با جهان آنچه آنها نیاز دارند قرار داده است
به منظور کامپایل کد خود را. پس فقط به این عادت کنید،
ما تصمیم به انجام همان چیزی. بسیار در list1.h وجود دارد نیست،
اما ما چیزی است که ممکن است مورد علاقه باشد در جهان به مردم قرار داده است
که می خواهند به استفاده از پیاده سازی لیست ما داشته باشد.
در حال حاضر، در list1.c، من نمی خواهد رفتن را از طریق تمام این چیز
زیرا آن را کمی طولانی است، این برنامه، اما اجازه دهید آن را اجرا کنید واقعی به سرعت در اعلان.
اجازه دهید list1 کامپایل من، به من اجازه پس از آن اجرا list1، و آنچه که شما خواهید دید
ایم و شبیه سازی یک برنامه ساده کوچک در اینجا
که به من اجازه می دهد برای اضافه کردن و حذف اعداد به یک لیست است.
پس اجازه دهید من به جلو بروید و نوع 3 برای 3 گزینه منو.
من می خواهم به وارد کردن شماره - اجازه دهید شماره اول، که بود (9).
و در حال حاضر من گفت: این لیست در حال حاضر 9.
اجازه دهید من به جلو بروید و انجام دیگر درج، بنابراین من ضربه گزینه منو 3.
چه تعداد را من می خواهم برای وارد کردن؟ 17.
را وارد کنید. و من فقط یک انجام دهید.
اجازه بدهید شماره 22 درج کنم.
بنابراین ما باید در ابتدای لیست پیوندی است که ما در فرم کشویی به حال یک لحظه قبل است.
چگونه است که این درج در واقع اتفاق می افتد؟
در واقع، 22 است که در حال حاضر در انتهای لیست.
پس داستان ما در صحنه در روز دوشنبه گفت: و فقط در حال حاضر تاکید
باید واقع اتفاق می افتد در کد.
بیایید نگاهی به. اجازه دهید من در پایین حرکت کنید در این فایل.
ما براق خواهید بیش از برخی از توابع،
اما ما رو به پایین، به می گویند، تابع را وارد کنید.
>> بیایید ببینید که چگونه ما در مورد قرار دادن یک گره جدید به این لیست پیوندی.
فهرست اعلام شده؟ خوب، اجازه دهید حرکت تمام راه را تا در بالا،
و توجه کنید که مرتبط فهرست است که در اصل به عنوان یک اشاره گر که در ابتدا NULL اعلام شده است.
بنابراین من با استفاده از یک متغیر جهانی، که به طور کلی ما در برابر موعظه ام
به دلیل آن را می سازد کد خود را کمی کثیف به حفظ،
مرتب کردن بر اساس آن است تنبل، معمولا، اما آن را تنبل نیست و اشتباه نیست و این بد نیست
اگر تنها هدف برنامه های خود را در زندگی این است که به شبیه سازی یک لیست پیوندی است.
که دقیقا همان چیزی است که ما در حال انجام است.
بنابراین به جای این اعلام را در بخش اصلی و پس از آن باید آن را منتقل می کند به هر تابع
ما در این برنامه نوشته شده است، ما به جای درک اوه، اجازه دهید فقط آن را جهانی
زیرا هدف از این برنامه این است که برای نشان دادن یک و تنها یک لیست مرتبط است.
به طوری که احساس می کند درست است. در اینجا نمونه های اولیه من است، و ما نمی خواهد رفتن را از طریق تمام این،
اما من یک تابع حذف، یک تابع پیدا کنید، یک تابع را وارد کنید، و پیمودن یک تابع نوشت.
اما اجازه دهید در حال حاضر رفتن به پایین به تابع درج
و ببینید که چگونه این یکی کار می کند در اینجا.
درج بر روی خط - در اینجا ما بروید.
درج کنید. پس از آن هیچ استدلال را ندارد، چرا که ما قصد داریم به درخواست
در داخل این تابع تعداد آنها می خواهند برای وارد کردن است.
اما در ابتدا، ما آماده به برخی از آنها فضا را.
این نوع از کپی و پیست کنید و از مثال دیگر است.
در آن صورت، ما تخصیص بین المللی، این زمان ما در حال اختصاص یک گره است.
من واقعا به یاد داشته باشید که چگونه بسیاری از بایت یک گره است، اما خوب است.
Sizeof که می تواند رقم برای من.
و چرا من را برای NULL در خط 120 چک کردن؟
آنچه می تواند به اشتباه در خط 119 است؟ آره؟
[پاسخ دانشجویی، ناخوانا]
خوب است. فقط می تواند صورتی که من بیش از حد حافظه پرسیده
یا چیزی اشتباه است و سیستم عامل بایت به اندازه کافی به من را نداشته باشند،
پس از آن، سیگنال به همان اندازه با بازگشت NULL، و اگر من برای آن بررسی نمی
و من فقط کورکورانه اقدام به استفاده از آدرس بازگشت، آن می تواند تهی باشد.
این می تواند برخی از ارزش نیست، چیز خوبی نیست مگر اینکه I -
در واقع نمی خواهد یک مقدار نامعلوم است. این می تواند NULL، بنابراین من نمی خواهم
به سوء استفاده از آن و بصورت غیر مرجع آن را در معرض خطر است.
در صورتی که اتفاق می افتد، من فقط و بازگشت خواهیم وانمود مثل من می کنید هر حافظه در همه.
>> در غیر این صورت، من به کاربر یک شماره برای وارد کردن به من به من بدهید، من اسمش دوست قدیمی ما GetInt،
و سپس به این نحو است که در روز دوشنبه معرفی شده بود.
newptr-> N "به معنای آدرس است که شما با استفاده از malloc داده شد
که نشان دهنده اولین بایت از یک شیء گره جدید،
و پس از آن به زمینه به نام N بروید.
کمی چیزهای بی اهمیت سوال: معادل این است که به چه خط بیشتر مرموز از کد؟
به چه روش دیگری می تواند به من نوشته اند؟ می خواهم یک چاقو را به؟
[پاسخ دانشجویی، ناخوانا]
خوب است. با استفاده از ازت، اما آن را کاملا به عنوان به عنوان ساده نیست.
چه من برای اولین بار نیاز به انجام؟ [پاسخ دانشجویی، ناخوانا]
خوب است. من نیاز به انجام newptr.n *.
پس این است که می گوید اشاره گر جدید بدیهی است که یک آدرس است. چرا؟
از آنجا که آن را با استفاده از malloc بازگردانده شد. * گفت newptr "وجود دارد،"
و پس از آن هنگامی که شما وجود دارد، پس از آن شما می توانید بیشتر آشنا N استفاده کنید،
اما این فقط کمی زشت به نظر می رسد، به خصوص اگر ما انسان ها در حال رفتن به
قرعه کشی اشاره گر با فلش تمام وقت و جهان در مورد این نماد فلش استاندارد،
که دقیقا همان چیزی است.
> نماد زمانی که چیزی در سمت چپ یک اشاره گر است - بنابراین شما فقط استفاده کنید.
در غیر این صورت، اگر آن را یک ساختار واقعی، استفاده از ازت.
و پس از آن این است: چرا من مقداردهی اولیه newptr بعدی> NULL؟
ما می توانم در یک دست آویزان کردن سمت چپ از پایان مرحله را نمی خواهم.
ما می خواهیم به آن اشاره راست پایین، که به معنی پایان این لیست
می تواند به طور بالقوه در این گره باشد، بنابراین ما بهتر است مطمئن شوید که آن را NULL است.
و به طور کلی، مقدار دهی اولیه متغیر خود و یا خود را داده اعضا و ساختمانها
به چیزی است که فقط تمرین خوبی است.
فقط اجازه زباله ها وجود دارد و همچنان وجود دارد به طور کلی به شما می شود در مشکل
اگر شما فراموش نکنید که برای انجام کاری به بعد در.
>> در اینجا چند مورد. این، دوباره، تابع درج،
و اولین چیزی که من برای بررسی این است که اگر متغیر به نام برای اولین بار
که متغیر جهانی NULL است، این بدان معناست که هیچ ارتباط وجود دارد.
ما در هر شماره درج شده نیست، بنابراین آن را بی اهمیت برای وارد کردن این شماره در حال حاضر
به این فهرست، چرا که آن را فقط در آغاز از لیست به آن تعلق دارد.
بنابراین این بود که آنیتا فقط ایستاده بود تا به اینجا به تنهایی، وانمود
هیچ کس دیگری بود تا به روی صحنه تا زمانی که ما اختصاص داده شده است یک گره،
پس از آن او می تواند دست او را برای اولین بار بالا می برد،
اگر هر کس دیگری در مرحله بعد از او آمده بود در روز دوشنبه است.
در حال حاضر در اینجا، این یک چک کوچک که در آن من باید بگویم این است که اگر مقدار گره جدید N
<مقدار ازت در گره اول،
این بدان معناست که یک لیست پیوندی است که شروع شده است وجود دارد.
حداقل یک گره در لیست وجود دارد، اما این پسر جدید
به آن تعلق دارد قبل از آن، بنابراین ما نیاز به حرکت در اطراف.
به عبارت دیگر، در صورتی که لیست فقط با شروع، اجازه دهید می گویند،
فقط شماره 17، که - در واقع، ما می توانیم این را با وضوح بیشتری انجام دهد.
اگر ما شروع داستان ما با یک اشاره گر در ابتدا فراخوانی،
و در ابتدا آن را NULL، و شماره 9 درج می کنیم.
شماره 9 به وضوح در آغاز از لیست به آن تعلق دارد.
بنابراین وانمود اجازه دهید ما فقط به malloced آدرس یا شماره 9 قرار داده و آن را در اینجا.
اگر اولین بار است که 9 به طور پیش فرض، سناریو اول مورد بحث ما فقط به معنای اجازه دهید این پسر در اینجا،
ترک این را به عنوان NULL، در حال حاضر در حال حاضر شماره 9.
شماره آینده ما می خواهیم برای وارد کردن 17 است.
17 به آن تعلق دارد در اینجا، بنابراین ما قصد داریم به برخی از پله های منطقی را از طریق این کار را انجام دهند.
بنابراین به جای آن اجازه دهید، قبل از ما انجام این کار، بیایید وانمود کنیم که ما می خواستیم به وارد کردن شماره 8.
>> پس فقط به خاطر راحتی است، من قصد دارم به منظور جلب.
اما به یاد داشته باشید، malloc می توانید آن را در هر نقطه قرار داده است.
اما به خاطر طراحی است، من آن را در اینجا قرار داده است.
پس من فقط گره شماره 8 اختصاص داده وانمود NULL است به طور پیش فرض می باشد.
آنچه اکنون اتفاق می افتد؟ یک زن و شوهر از همه چیز.
ما این اشتباه را به روی صحنه در دوشنبه ساخته شده است که در آن ما یک اشاره گر مانند این به روز رسانی،
پس از آن این را، و پس از آن ما ادعا کرد - ما یتیم هر کس دیگری روی صحنه.
از آنجا که شما نمی توانند - منظور از عملیات در اینجا مهم است،
چون در حال حاضر ما از دست داده ایم به این 9 گره است که فقط نوع شناور در فضا.
بنابراین این رویکرد درست در روز دوشنبه نمی شود.
ما در مرحله اول باید به انجام این کار چیز دیگری است.
دولت از جهان به نظر می رسد مثل این. در ابتدا، 8 اختصاص یافته است.
یک راه بهتر از قرار دادن 8 چه خواهد بود؟
به جای به روز رسانی این اشاره گر برای اولین بار، فقط این یکی در اینجا به جای به روز رسانی.
بنابراین ما نیاز به یک خط از کد است که به نوبه خود این کاراکتر NULL
به یک اشاره گر واقعی که اشاره به گره 9،
و پس از آن ما با خیال راحت می توانید اولین در این مرد نکته در اینجا است.
در حال حاضر ما باید یک لیست، یک لیست پیوندی از دو عنصر است.
و چه این در واقع مثل اینجا نگاه کنید؟
اگر ما نگاهی به کد نگاه کنید، توجه کنید که دقیقا همان است که من انجام داده ام.
من گفت: newptr، و در این داستان، newptr اشاره در این مرد بود.
>> بنابراین اجازه دهید یک چیز بیشتر جلب کنم، و من باید جا کمی بیشتر برای این است.
بنابراین نقاشی کوچک ببخشند.
این مرد به نام newptr.
این متغیر به ما اعلام کرد که چند خط قبل، در خط - فقط بالای 25.
و آن را با اشاره به 8 است. بنابراین، هنگامی که من می گویم newptr بعدی>، این بدان معناست که به ساختار
که در توسط newptr اشاره کرد، بنابراین در اینجا ما هستند، به وجود دارد.
سپس فلش است گفت: زمینه آینده، و پس از آن = می گوید قرار دادن چه مقدار وجود دارد؟
ارزش بود که برای اولین بار در چه مقدار برای اولین بار در؟
اولین اشاره در این گره شده بود، بنابراین این بدان معناست که این در حال حاضر باید در این گره نقطه.
به عبارت دیگر، آنچه به نظر می رسد البته ظروف سرباز یا مسافر مضحک با دست خط من،
یک ایده ساده و فقط در حال حرکت این فلش در سراسر
ترجمه به کد فقط با این بوش.
فروشگاه چیزی است که در اولین بار در زمینه آینده و پس از آن به روز رسانی 1 واقع است.
اجازه دهید به جلو بروید و به سرعت رو به جلو را از طریق برخی از این
و نگاه در حال حاضر فقط در درج این دم.
فرض کنید من به نقطه ای که در آن پیدا کنم که زمینه برخی از گره NULL آورید.
و در این نقطه در داستان، با جزئیات است که من glossing بیش از
این است که من به معرفی یکی دیگر از اشاره گر تا اینجا در خط 142، اشاره گر سلف.
اساسا، در این نقطه در داستان، یک بار لیست می شود طولانی،
من نوع نیاز به آن را با دو انگشت راه بروند چرا که اگر بیش از حد،
به یاد داشته باشید در یک لیست واحد طول، شما نمی توانید به عقب.
بنابراین این ایده از predptr انگشت سمت چپ من است، و newptr - newptr نیست.
یکی دیگر از اشاره گر است که در اینجا، انگشت دیگر من است، و من فقط نوع راه رفتن این فهرست است.
به همین دلیل است که وجود دارد. اما اجازه دهید که تنها یکی از موارد ساده تر در اینجا در نظر.
اگر میدان بعدی که اشاره گر NULL است، چه مفهوم منطقی است؟
اگر شما در حال عبور این لیست و به شما رسید یک اشاره گر NULL است؟
شما در انتهای لیست هستید، و بنابراین کد به آن اضافه این یک عنصر اضافی
مرتب سازی بر اساس حسی که گره که در کنار اشاره گر NULL،
پس از این است که در حال حاضر NULL، و آن را تغییر دهید، هر چند، به آدرس گره جدید است.
بنابراین ما فقط در کد طراحی فلش است که ما در صحنه با بالا بردن دست چپ کسی را به خود جلب کرد.
>> و در صورتی که من تو دست من در حال حاضر موج،
فقط به خاطر اینکه من فکر می کنم آن را آسان به گم که ما آن را انجام دهید در این نوع از محیط زیست،
برای چک کردن قرار دادن در وسط لیست.
اما فقط به طور مستقیم، چه اتفاقی باید بیفتد اگر شما می خواهید برای کشف کردن
که در آن برخی از شماره به آن تعلق دارد در وسط این است که شما باید آن را به راه رفتن
با بیش از یک انگشت، بیش از یک اشاره گر،
که در آن با چک کردن به آن تعلق دارد این عنصر کمتر از یک جریان،
> در حال حاضر، و در هنگامی که شما در پیدا کردن این محل،
پس از آن شما را مجبور به انجام این نوع از پوسته بازی که در آن شما حرکت اشاره گر را در اطراف با دقت بسیار.
و این پاسخ، اگر شما می خواهم به همین دلیل از طریق این دوست در خانه را آن گونه که مایلید تغییر دهید،
جوش پایین فقط به این دو خط کد است، اما منظور از آن خطوط فوق العاده مهم است.
از آنجا که اگر دست کسی شما را رها کردن و بالا بردن شخص دیگری در جهت اشتباه است،
باز هم، شما می توانید تا پایان یتیم این فهرست است.
به طور خلاصه از نظر مفهومی، درج در دم نسبتا سر راست است.
درج در سر نیز نسبتا سرراست است،
اما شما نیاز به اشاره گر دیگر این زمان به روز رسانی
به فشار شماره 5 در اینجا، به لیست
و سپس قرار دادن در وسط شامل تلاش و حتی بیشتر،
بسیار با دقت در محل صحیح خود قرار دادن شماره 20،
است که بین 17 و 22.
بنابراین شما نیاز به چیزی شبیه به گره جدید 20 تا 22،
و پس از آن، اشاره گر که گره نیاز به به روز رسانی و زمان آخرین؟
این 17 است، در واقع آن را درج کنید.
بنابراین دوباره، من کد واقعی که برای اجرای خاص تسلیم.
>> در نگاه اول، کمی سخت و طاقت فرسا است، اما واقعا فقط یک حلقه بی نهایت
که حلقه، حلقه، حلقه، حلقه، و شکستن به محض این که شما ضربه اشاره گر NULL،
که در آن شما می توانید درج لازمه را انجام دهد.
این، پس از آن، نماینده مرتبط با لیست کد درج شده است.
این نوع از بسیاری بود، و آن را احساس می کند که یکی از مشکلات ما را حل،
اما ما به معرفی کل یک دیگر است. صادقانه بگویم، ما صرف این همه زمان
در بزرگ O و Ω و در حال اجرا، تلاش برای حل مشکلات با سرعت بیشتری،
و در اینجا ما در حال گرفتن یک گام بزرگ به عقب، آن را احساس می کند.
و در عین حال، اگر هدف این است که برای ذخیره اطلاعات،
آن را مانند جام مقدس احساس می کند، همانطور که ما در روز دوشنبه گفت، واقعا خواهد بود
برای ذخیره همه چیز فورا.
>> در واقع، فرض کنید که ما لیست کنار گذاشته مرتبط برای یک لحظه
و ما به جای معرفی مفهوم یک جدول است.
و بهتر است فقط از یک جدول فکر می کنم برای یک لحظه به عنوان یک آرایه است.
این آرایه و این مورد در اینجا 26 عناصر 0 تا 25،
و فرض کنید که شما برخی از تکه های ذخیره سازی برای نام های مورد نیاز:
آلیس و باب و چارلی و مانند آن.
و شما نیاز به برخی از ساختمان داده به ذخیره آن نام است.
خب، شما می توانید چیزی شبیه به یک لیست پیوندی استفاده کنید
و شما می توانید لیست قرار دادن آلیس قبل از باب و چارلی پس از باب راه رفتن و غیره.
و، در واقع، اگر شما می خواهید برای دیدن کد به آن را به عنوان به کنار،
می دانم که در list2.h، دقیقا همان است که ما انجام می دهیم.
ما نمی خواهد از طریق این کد، اما این است که یک نوع از مثال اول
است که به معرفی یک ساختار دیگر ما که قبل از دانش آموزان به اصطلاح دیده می شود،
و پس از آن چیزی است که آن را در واقع در لیست پیوندی ذخیره یک اشاره گر به ساختار دانشجویی
به جای یک عدد صحیح ساده کوچک، N.
بنابراین درک کد وجود دارد وجود دارد که شامل رشته های واقعی،
اما اگر هدف در دست واقعا در حال حاضر است که برای رسیدگی به مشکل بهره وری،
آن را نه خوب می شود اگر ما با توجه به یک شی به نام آلیس،
ما می خواهیم تا او را به محل مناسب در ساختار داده ها قرار داده است،
آن را احساس می کند مانند آن را واقعا خوب می شود فقط با قرار دادن آلیس،
که نام شروع می شود با A، در مکان اول است.
و باب که نامش با B شروع می شود، در مکان دوم است.
با استفاده از یک آرایه، و یا اجازه دهید که آن را به یک جدول، یک جدول هش را در آن،
دقیقا همان است که ما می توانیم انجام دهیم. اگر ما با توجه به نام مثل آلیس،
یک رشته مانند آلیس، که در آن A-L-I-C-E شما قرار داده است؟
ما نیاز به یک hueristic. ما نیاز به یک تابع را به برخی از ورودی مانند آلیس
و بازگشت پاسخ، "آلیس در این مکان قرار دهید."
و این تابع، این جعبه سیاه و سفید، به نام یک تابع هش.
>> یک تابع هش چیزی است که طول می کشد یک ورودی، مانند "آلیس" است،
و بازده به شما، به طور معمول، محل سکونت عددی در برخی از ساختمان داده که در آن آلیس به آن تعلق دارد.
در این مورد، تابع هش ما باید نسبتا ساده است.
تابع هش ما باید گفت، اگر شما با توجه به "آلیس"، که شخصیت باید در مورد مراقبت؟
یکی از اولین. بنابراین من در [0] نگاه کنید، و پس از آن من می گویم اگر [0] کاراکتر A، بازگشت به شماره 0.
اگر B، بازگشت 1. اگر C آن، بازگشت 2، و غیره.
شاخص 0، و این که به من اجازه می دهد به قرار دادن آلیس و باب و سپس چارلی و غیره
به این ساختار داده ها. اما یک مشکل وجود دارد.
چه می شود اگر آنیتا می آید همراه دوباره؟
کجا می توانم آنیتا ما را؟ نام او، بیش از حد، با حرف A شروع می شود،
و آن را احساس می کند مانند ظروف سرباز یا مسافر حتی بزرگتر از این مشکل را ساخته ایم.
ما در حال حاضر به درج فوری، قرار دادن زمان ثابت، به ساختار داده ها
به جای بدتر مورد خطی،
اما آنچه که می تواند ما را با آنیتا در این مورد کاری انجام دهید؟
چه هستند این دو گزینه، واقعا؟ آره؟
[پاسخ دانشجو، ناخوانا] خوب، به طوری که ما می تواند ابعاد دیگری داشته باشد.
این خوب است. بنابراین ما می توانیم مسائل را ساختن در 3D مثل ما صحبت شفاهی در روز دوشنبه است.
ما می تواند یکی دیگر از دسترسی را در اینجا اضافه کنید، اما فرض کنید که هیچ، من در تلاش برای حفظ این ساده.
هدف در اینجا این است که دسترسی فوری ثابت زمان،
به طوری که با اضافه کردن پیچیدگی بیش از حد است.
گزینه های دیگر که در هنگام تلاش برای وارد کردن آنیتا به این ساختار داده ها چه هستند؟ آره؟
[پاسخ دانشجو، ناخوانا] خوب. بنابراین ما می توانیم هر کس دیگری به پایین حرکت می کند،
مانند nudges چارلی پایین باب و آلیس، و پس از آن ما را آنیتا جایی که او واقعا می خواهد.
>> البته، در حال حاضر، یک عارضه جانبی از این وجود دارد.
این ساختار داده ها است که احتمالا به این دلیل نیست که ما می خواهیم برای وارد کردن مردم یک بار
بلکه به این دلیل که ما می خواهیم به بررسی کنید که آیا آنها بعد از
اگر ما می خواهیم برای چاپ کردن همه نامها در ساختار داده ها.
ما قصد داریم برای انجام کاری با این داده ها در نهایت.
بنابراین در حال حاضر ما از نوع پیچ بیش از آلیس، که دیگر جایی که او تصور می شود.
نه باب است، و نه چارلی است.
شاید این یک ایده خوب نیست.
اما در واقع، این یک گزینه است. ما می توانیم همه را تغییر
یا هک، آنیتا دیر به بازی آمد، چرا ما نه تنها آنیتا قرار داده است
نه در اینجا، اینجا نه، اینجا نه، اجازه دهید فقط او را کمی پایین تر در فهرست.
اما پس از آن این مشکل شروع می شود به واگذاردن دوباره.
شما ممکن است قادر به پیدا کردن آلیس بلافاصله، بر اساس نام و نام خانوادگی خود را.
و باب، بلافاصله، و چارلی. اما پس از آن شما برای آنیتا نگاه کنید،
و شما می بینید، HMM، آلیس در راه است.
خوب، اجازه دهید من زیر آلیس چک کنید. باب آنیتا نیست.
چارلی آنیتا نیست. اوه، آنیتا وجود دارد.
و اگر شما همچنان که قطار از منطق تمام راه،
بدترین زمان در حال اجرا از پیدا کردن و یا قرار دادن آنیتا به این ساختار داده های جدید؟
O (n) است، درست است؟
از آنجا که در بدترین حالت، آلیس، باب، چارلی وجود دارد. است. است.
تمام راه را به فردی به نام "Y"، به طوری که تنها یک نقطه وجود دارد را ترک کردند.
خوشبختانه، هیچ کس به نام "Z"، بنابراین ما آنیتا در سطح بسیار پائین قرار داده است.
>> ما واقعا به حل این مشکل است.
بنابراین شاید ما نیاز به این بعد سوم را به شما معرفی.
و معلوم، اگر ما معرفی این بعد سوم،
ما می توانیم این کار را انجام دهند نه کاملا، اما جام مقدس است که رفتن به گرفتن
قرار دادن زمان ثابت و پویا اضافه به طوری که
ما لازم نیست که به کد سخت مجموعه ای از اندازه 26.
ما می توانیم به عنوان بسیاری از نام های وارد که ما می خواهیم، ​​اما اجازه دهید 5 دقیقه استراحت ما در اینجا
و پس از آن به درستی انجام دهد.
بسیار خوب. من مجموعه ای از داستان خیلی مصنوعی وجود دارد
با انتخاب آلیس و چارلی باب و پس از آن بعد از آن و پس از آن آنیتا،
که نام واضح است که قرار بود با آلیس برخورد می کنند.
اما سوال ما در روز دوشنبه به پایان رسید این است که چقدر احتمال آن است که
که شما می توانید این نوع از برخورد را دریافت کنم؟ به عبارت دیگر،
اگر ما شروع به استفاده از این ساختار جدولی است که واقعا فقط یک آرایه،
در این مورد از 26 مکان،
چه می شود اگر ورودی ما به جای توزیع یکنواخت؟
این مصنوعی آلیس و باب و چارلی و دیوید و به همین ترتیب حروف الفبا،
آن را بطور یکنواخت از طریق Z. بیش از یک توزیع
>> شاید ما فقط خوش شانس دریافت است و ما قصد داریم به دو یا دو B
با احتمال بسیار بالا است، اما به عنوان کسی که اشاره کرد،
اگر ما تعمیم این مشکل و نه از 0 تا 25
اما، می گویند، 0 تا 364 یا 65، در اغلب موارد تعداد روزها در یک سال معمولی،
و سوال پرسید: "چه احتمال این که دو نفر از ما در این اتاق همان روز تولد؟
از آن راه دیگری قرار داده، چه احتمال این که دو نفر از ما یک نام شروع با؟
مرتب کردن بر اساس سوال همان است، اما این فضای آدرس،
این فضای جستجو، بزرگتر است در مورد تولد،
از آنجا که ما روز بسیار زیادی در سال از حروف الفبا.
احتمال برخورد چه خبر؟
خب، ما می توانیم این کار را بدانند ریاضی راه مخالف فکر می کنم.
احتمال هیچ برخورد چه خبر؟
خوب، این عبارت در اینجا می گوید که احتمال
اگر فقط یک نفر در این اتاق، که آنها را منحصر به فرد تولد وجود دارد؟
این 100٪ است. زیرا اگر تنها یک نفر در اتاق وجود دارد،
و یا تاریخ تولد خود می تواند هر یک از 365 روز از سال است.
بنابراین 365/365 گزینه به من می دهد یک مقدار از 1.
بنابراین احتمال در مورد در حال حاضر فقط 1 است.
اما اگر فرد دوم در اتاق وجود دارد،
احتمال که تاریخ تولد آنها متفاوت است؟
تنها 364 روز، بدون در نظر گرفتن سال کبیسه وجود دارد،
برای روز تولد خود را با افراد دیگر برخورد می کنند.
بنابراین 364/365. اگر یک شخص سوم در می آید، آن را 363/365، و غیره.
پس ما را ضرب با هم این فراکسیون، که در حال گرفتن کوچک و کوچکتر،
به شکل از آنچه احتمال است که همه ما جشن های تولد منحصر به فرد است؟
اما پس از آن ما می توانیم، البته، فقط جواب تلنگر آن را در سراسر
و 1 منهای تمام از آن، بیان ما در نهایت خواهید
اگر شما به یاد داشته باشید پشت کتاب ریاضی خود را، آن را به نظر می رسد چیزی کمی شبیه به این،
است که بسیار آسان تر از تفسیر گرافیکی.
و این گرافیک بر روی محور X شماره تولد،
و یا تعدادی از افراد مبتلا به متولد، و در محور Y احتمال یک مسابقه است.
و آنچه در این گفت این است که اگر شما، اجازه دهید بگویم، حتی،
اجازه دهید چیزی شبیه به 22، 23 را انتخاب کنید.
اگر 22 یا 23 نفر در اتاق وجود دارد،
احتمال این که دو نفر از این افراد بسیار کمی در حال رفتن به تولد
است که در واقع بالا فوق العاده، combinatorially.
50 شانس٪ است که در یک کلاس فقط 22 نفر، سمینار، عملا،
2 از این افراد در حال رفتن به تولد.
چرا که راه های زیادی وجود دارد که در آن شما می توانید تاریخ تولد یکسانی داشته باشند.
حتی بدتر از آن، اگر شما در سمت راست نمودار نگاه کنید،
در زمانی که شما یک کلاس با 58 دانش آموز در آن،
احتمال 2 نفر داشتن یک تولد فوق العاده، فوق العاده بالا، نزدیک به 100٪ است.
در حال حاضر، که مرتب سازی بر اساس یک واقعیت جالب در مورد زندگی واقعی است.
>> اما مفاهیم، ​​در حال حاضر، برای سازه های داده و اطلاعات ذخیره سازی
بدان معنی است که فقط با فرض شما خوب، پاک، توزیع یکنواخت داده ها
و شما باید یک آرایه به اندازه کافی بزرگ یک دسته از مسائل به جا
به این معنا نیست که شما در حال رفتن به مردم در مکان های منحصر به فرد است.
شما در حال رفتن به برخورد. بنابراین این مفهوم از هش کردن، آن را به عنوان نامیده می شود،
گرفتن ورودی مانند "آلیس" و ماساژ آن را در برخی از راه
و پس از آن جواب مثل 0 یا 1 یا 2.
به دست آوردن برخی از خروجی آن تابع است با این احتمال برخورد گرفتار شده است.
پس چگونه می تواند کسانی که برخورد ما رسیدگی؟
خب، در یک مورد، ما می توانیم این ایده که پیشنهاد شد.
ما فقط می تواند همه را تغییر و یا شاید کمی ساده تر،
نه از همه حرکت دیگری، اجازه دهید فقط حرکت آنیتا به پایین از نقطه ای در دسترس است.
بنابراین اگر آلیس در 0، باب 1، چارلی در 2،
ما فقط آنیتا در محل 3 قرار داده است.
و این روش در ساختمان های داده به نام کاوش خطی است.
خطی زیرا شما فقط پیاده روی این خط، و شما در حال مرتب کردن بر اساس کاوش
برای لکه های موجود در ساختار داده ها.
البته، این devolves به O (n) است.
اگر ساختمان داده واقعا کامل است، 25 نفر در آن وجود دارد در حال حاضر،
و سپس آنیتا به همراه می آید، او به پایان می رسد تا در چه خواهد بود محل سکونت Z، و این خوب است.
او هنوز هم متناسب است، و ما می توانیم او را بعد از پیدا کردن.
>> اما این خلاف به هدف از سرعت چیز بود.
پس چه می شود اگر ما به جای معرفی این بعد سوم؟
این روش به طور کلی زنجیره ای جداگانه نامیده می شود، و یا داشتن زنجیر است.
و چه یک جدول هش در حال حاضر، این ساختار جدولی،
جدول شما فقط یک آرایه ای از اشاره گرها.
اما آنچه که اشاره گر اشاره به حدس بزن چی شده است؟
لیست پیوندی. پس چه در صورتی که هر دو از این دنیا (دنیای شخصی ودنیای هنری) را اجرامی کنید ما را؟
ما با استفاده از آرایه ها برای شاخص های اولیه
به ساختار داده تا ما فورا می توانید به [0] [1]، [30] و یا غیره،
اما به طوری که ما باید برخی از انعطاف پذیری و ما می توانیم آنیتا و آلیس و آدم جا
و هر یک نام،
ما به جای رشد محور دیگر خودسرانه کنیم.
و ما در نهایت، به عنوان روز دوشنبه، که توانایی بیانی با لیست پیوندی.
ما می توانیم یک ساختار داده ها خودسرانه رشد می کنند.
متناوبا، ما فقط می تواند یک آرایه 2 بعدی بزرگ را،
اما برای رفتن به یک وضعیت افتضاح اگر یکی از ردیف ها را در یک آرایه 2 بعدی
برای شخص دیگری که نام اتفاق می افتد با A. شروع به اندازه کافی بزرگ نیست
خدای ناکرده ما را به دوباره اختصاص 2 بعدی ساختار بزرگ
فقط به خاطر اینکه بسیاری از مردم وجود دارد به نام،
به ویژه هنگامی که تعداد کمی از مردم به نام چیزی Z وجود دارد.
این فقط برای رفتن به ساختمان داده بسیار پراکنده است.
پس از آن به هر وسیله مناسب نیست، اما در حال حاضر ما حداقل توانایی
فورا به پیدا کردن جایی که آلیس یا آنیتا به آن تعلق دارد،
حداقل در شرایط استفاده از محور عمودی،
و پس از آن ما فقط باید تصمیم بگیرید که در آن برای قرار دادن آنیتا یا آلیس در سرزمین این لیست پیوندی.
اگر ما در مورد مرتب سازی کارها اهمیتی نمی دهند، چگونه به سرعت می تواند آلیس ما وارد را به یک ساختار شبیه به این؟
این زمان ثابت است. ما را به [0] صفحه اول، و اگر وجود دارد هیچ کس،
آلیس می رود در آغاز که لیست های پیوندی می باشد.
اما این یک معامله بزرگ است. از آنجا که اگر آنیتا پس از آن می آید همراه
برخی از تعدادی از مراحل بعد، که در آن آنیتا تعلق دارد؟
خب، [0]. OOP. آلیس در حال حاضر در آن لیست پیوندی.
>> اما اگر ما در مورد مرتب سازی بر این نام برام مهم نیست،
ما فقط می تواند آلیس بر این، قرار دادن آنیتا، حرکت می کند، اما حتی که زمان ثابت است.
حتی اگر آلیس و آدم و همه این نام وجود دارد،
واقعا آنها را تغییر فیزیکی است. چرا؟
از آنجا که ما فقط در اینجا با لیست پیوندی، که می داند که آیا این گره ها شد به هر حال؟
همه شما باید انجام دهید این است که حرکت خرده نان.
حرکت از فلش در اطراف، شما لازم نیست که به صورت فیزیکی انتقال هر گونه داده در اطراف.
بنابراین ما می توانیم آنیتا، قرار دادن در آن صورت، فورا. زمان ثابت است.
بنابراین ما باید زمان مراجعه، ثابت و زمان ثابت درج کسی مثل آنیتا.
اما نوع ساده انگاشت جهان.
اگر ما بعدا می خواهید برای پیدا کردن آلیس؟
چگونه بسیاری از مراحل است که رفتن را؟
[پاسخ دانشجویی، ناخوانا]
دقیقا. تعداد زیادی از مردم قبل از آلیس در لیست پیوندی.
پس از آن کاملا بی نقص نیست، چرا که ساختار داده های ما، دوباره، این دسترسی عمودی
و سپس آن را تا به این لیست های پیوندی حلق آویز - در واقع، اجازه دهید آن را یک آرایه قرعه کشی نیست.
این به این لیست های پیوندی حلق آویز کردن از آن است که به نظر می رسد چیزی کمی مانند این.
اما مشکل این است که اگر آلیس و آدم و این همه نام
تا پایان بیشتر و بیشتر به بیش از وجود دارد،
پیدا کردن کسی می تواند در نهایت گرفتن یک دسته از مراحل،
bcause شما را مجبور به گذشتن از لیست پیوندی
که یک عملیات خطی است.
پس در واقع، پس از آن، زمان درج در نهایت O (N)، که در آن n تعداد عناصر در لیست است.
تقسیم، اجازه دهید خودسرانه متر، که در آن M است که تعدادی از لیست های پیوندی
که ما در این محور عمودی داشته باشد.
به عبارت دیگر، اگر ما واقعا فرض توزیع یکنواخت از نام،
کاملا غیر واقعی است. بدیهی است برخی از حروف نسبت به دیگران وجود دارد.
>> اما اگر ما برای لحظه ای یک توزیع یکنواخت فرض کنیم،
و در حال حاضر نفر از مردم در کل، و متر زنجیر ها
در دسترس به ما، پس از آن در طول هر یک از این زنجیره ها
نسبتا به سادگی رفتن به کل، N تقسیم شده توسط تعدادی از زنجیره.
پس N / m است. اما در اینجا که در آن ما می تواند ریاضی باهوش است.
م ثابت است، چرا که تعداد ثابتی از این وجود دارد.
شما در حال رفتن به تعریف آرایه خود را در آغاز،
و ما در حال تغییر محور عمودی نیست. با این تعریف، که ثابت باقی می ماند.
این تنها محور افقی، پس به صحبت می کنند، که در حال تغییر است.
بنابراین از لحاظ فنی، این ثابت شده است. بنابراین در حال حاضر، زمان درج
خیلی O (n) است.
به طوری که احساس نمی کند که بسیار بهتر است.
اما آنچه در حقیقت در اینجا؟ خب، تمام این مدت، هفته،
گفته ایم که O (n ²). O (N)، 2 X N ² - N، تقسیم بر 2. است. است. ech.
این فقط ² N است. اما در حال حاضر، در این بخش از ترم،
ما می توانیم شروع به صحبت کردن در مورد دنیای واقعی دوباره است.
و N / M است کاملا سریعتر از فقط یک نفر به تنهایی است.
اگر شما از یک هزار نام، و آنها را شکست شما را به سطل های متعدد
به طوری که شما فقط به ده نام در هر یک از این زنجیره ها،
کاملا جستجوی ده چیز است که در حال رفتن به سریع تر از هزار چیز.
و به این ترتیب یکی از مجموعه های مشکل آینده قصد دارد شما را به چالش می کشند
فکر می کنم در مورد دقیقا همان است که حتی اگر، آره،
مجانبی و ریاضی، این است که هنوز فقط خطی،
که بمکد به طور کلی زمانی که در تلاش برای پیدا کردن چیزهایی است.
در واقع، آن را سریع تر از آن باشد
با توجه به این تقسیم.
و بنابراین دوباره وجود دارد برای رفتن به این تجارت
و این تضاد میان تئوری و واقعیت،
و یکی از دستگیره عطفی در این نقطه آغاز خواهد شد در ترم
بیشتر از یک واقعیت به عنوان نوعی از آماده شدن برای پایان semster،
جهان برنامه نویسی وب را معرفی می کنیم،
که در آن در واقع، عملکرد رفتن به دفعات مشاهده شده است که کاربران خود را در حال رفتن به
شروع به احساس و درک تصمیمات طراحی فقیر.
>> پس چگونه می توانم شما را در مورد اجرای مرتبط - با 31 عنصر جدول هش؟
و مثال قبلی خودسرانه تولدهای بود.
اگر کسی تا به تولد 1 ماه ژانویه یا فوریه 1، ما آنها را در این سطل قرار داده است.
اگر آن را ژانویه فوریه 2، 2، 2 مارس، ما آنها را در این سطل قرار داده است.
که چرا آن 31 سال بود. چگونه یک جدول هش به شما اعلام؟
این می تواند خیلی ساده، جدول گره * نام دلخواه من برای آن، [31] است.
این به من می دهد 31 اشاره گر به گره،
و اجازه می دهد که به من 31 اشاره گر به لیست های پیوندی
حتی اگر این زنجیره در ابتدا NULL است.
چه من می خواهم برای قرار دادن اگر من می خواهم به فروشگاه "آلیس"، "باب"، "چارلی"؟
خب، ما نیاز به کسانی که همه چیز را در یک ساختار بسته بندی
از آنجا که ما نیاز به آلیس به باب اشاره، به نقطه را به چارلی، و غیره.
ما فقط نمی تواند به نام تنهایی، به طوری که من می تواند یک ساختار جدید به نام گره در اینجا ایجاد کنید.
>> یک گره واقعی چیست؟ گره در این لیست جدید مرتبط است؟
اولین چیزی که به نام کلمه، نام شخص.
طول، احتمالا مربوط به حداکثر طول نام یک انسان،
هر چه که است، 20، 30 و 40 کاراکتر در موارد گوشه ای دیوانه،
+1 و برای چه؟ این فقط شخصیت NULL اضافی، \ 0.
بنابراین این گره بسته بندی "چیزی" را به داخل خود،
اما آن را نیز اعلام کرد که یک اشاره گر به نام آینده
به طوری که ما می تواند زنجیره آلیس به باب به چارلی و غیره.
می تواند NULL، اما لزوما باید.
هر گونه سؤال در این جداول مخلوط؟ آره؟
پرسش و پاسخ [دانشجویی، ناخوانا] آرایه - سوال خوبی است.
چرا این کلمه char در یک آرایه به جای * کاراکتر؟
در این مثال تا حدودی خودسرانه، من نمی خواست مجبور به توسل
به malloc برای هر یک از نام های اصلی است.
من می خواستم به اعلام یک مقدار حداکثر حافظه برای رشته
به طوری که من می تواند به ساختار کپی آلیس \ 0 و لازم نیست که برای مقابله با malloc و آزاد و مانند آن.
اما من که می تواند در صورتی که من می خواستم به استفاده از فضای آگاهانه تر انجام دهد. خوب سوال.
بنابراین سعی کنید برای تعمیم به دور از این
و تمرکز باقی مانده از امروز بر روی ساختمان های داده به طور کلی
و مشکلات دیگری که ما می توانیم حل با استفاده از اصول مشابه
حتی اگر ساختارهای داده ای خود ممکن است در خاص خود متفاوت است.
>> پس از آن معلوم میشود که در علوم کامپیوتر، درخت ها بسیار رایج است.
و شما می توانید از مرتب کردن بر اساس درخت مانند درخت خانواده فکر می کنم،
که در آن برخی از ریشه ها، برخی از مادر و یا ایلخانی وجود دارد،
مادر بزرگ یا پدر بزرگ یا زودتر برگشت،
زیر که مادر و پدر و یا خواهر و برادر های مختلف و یا می خواهم.
بنابراین یک ساختار درختی گره ها و کودکان بوده است.
معمولا 0 یا بیشتر بچه ها برای هر گره است.
و برخی از اصطلاحات مخصوص یک صنف است که شما را در این عکس می بینید
است هر یک از بچه های کوچک و یا grandkids در لبه
که هیچ فلش ناشی از آنها،
کسانی که به اصطلاح برگ، و هر کسی که در داخل
یک گره درونی است و شما می توانید آن را هر چیزی در امتداد آن خطوط تماس بگیرید.
اما این ساختار بسیار رایج است. این یکی کمی خودسرانه است.
در حال حاضر یکی از بچه ها در سمت چپ، ما دارای سه فرزند در سمت راست،
دو فرزند در پایین سمت چپ.
بنابراین ما می تواند در اندازه های مختلف درختان داشته باشد، اما اگر ما شروع به استانداردسازی همه چیز،
و شما ممکن است از این ویدیو پاتریک در جستجوی دودویی از کوتاه قبلی به یاد
آنلاین، جستجو باینری را ندارد که با یک آرایه اجرا شود
و یا تکه های کاغذ را بر روی تخته سیاه.
فرض کنید که شما می خواهید برای ذخیره شماره های خود را در یک ساختار داده های پیچیده تر.
شما می توانید یک درخت شبیه به این را ایجاد کنید.
شما می توانید یک گره اعلام شده در C، و آن گره می تواند حداقل دو عنصر در داخل آن داشته باشند.
یکی از این شماره شما می خواهید برای ذخیره است، و از سوی دیگر - خب، ما نیاز به یک است.
دیگر کودکان آن است.
بنابراین در اینجا یکی دیگر از ساختمان داده. در این زمان، یک گره به عنوان ذخیره کردن یک شماره تعریف شده N
و سپس دو اشاره گر فرزند چپ و فرزند راست.
و آنها خودسرانه نیست. چه جالب در مورد این درخت؟
>> چه الگوی ایم گذاشته از این و یا چگونه پاتریک آن را گذاشته در ویدئو های خود را؟
این نوع آشکار است که برخی از مرتب سازی در اینجا وجود دارد،
اما چه قاعده ساده است؟ آره؟
[پاسخ دانشجویی، ناخوانا]
کامل. اگر شما را در این نگاه، شما را اعداد کوچک در سمت چپ،
اعداد بزرگ در سمت چپ، اما این درست است برای هر گره است.
برای هر گره فرزند چپ خود را کمتر از آن است، و فرزند راست آن بیشتر از آن است.
این به این معنی در حال حاضر این است اگر من می خواهم به جستجو در این ساختمان داده، می گویند، شماره 44،
من باید در ریشه شروع کنید، چرا که به عنوان با تمام از این پیچیده تر از ساختمان های داده در حال حاضر،
ما تنها یک اشاره گر به یک چیز است، شروع می شود.
و در این مورد، ابتدا ریشه است. این سمت چپ نیست،
ریشه این ساختار است. بنابراین من در اینجا 55، و من به دنبال به مدت 44.
کدام جهت را من می خواهم برای رفتن؟
خوب، من می خواهم برای رفتن به سمت چپ، به دلیل بدیهی است، به سمت راست خواهد بود بیش از حد بزرگ است.
بنابراین متوجه در اینجا، شما در حال مرتب کردن بر اساس مفهومی سفت درخت در نصف
زیرا شما هرگز به پایین به سمت راست.
بنابراین در حال حاضر من از از 55 تا 33. این یک عدد خیلی کوچک است.
من به دنبال 44، اما در حال حاضر من می دانم که اگر 44 را در این درخت، من به وضوح می تواند به سمت راست بروید.
بنابراین دوباره، من هرس درخت در نصف.
این تا حد زیادی یکسان مفهومی به دفترچه تلفن است.
این یکسان به آنچه که ما با مقالات بر روی تخته سیاه،
اما آن را به یک ساختار پیچیده تر است که اجازه می دهد تا ما را به واقع
این تقسیم و حل طراحی الگوریتم
و در واقع، تراورس یک ساختار شبیه به این - اوه.
عبور یک ساختار شبیه به این است، که در آن تنها "برو این راه و یا بروید که راه،
به این معنی است که کد است که ذهن خود را برای اولین بار در خم هنگامی که اجرای آن در بخش
و یا راه رفتن را از طریق آن در خانه، برای جستجوی باینری با استفاده از بازگشت یا تکرار،
درد در گردن است. یافتن عنصر میانی، و سپس گرد خود را به بالا یا پایین انجام دهد.
>> زیبایی وجود دارد به این دلیل ما در حال حاضر می توانید با استفاده از بازگشت دوباره،
اما خیلی بیشتر پاک. در واقع، اگر شما را در شماره 55 هستید و می خواهید برای پیدا کردن 44،
شما به سمت چپ در این مورد، پس چه کار میکنید؟ شما اجرا الگوریتم دقیقا همان است.
ارزش گره بررسی کنید، و سپس شما را به سمت چپ یا راست.
سپس مقدار گره را چک می کنید، به سمت چپ یا راست.
این کاملا به بازگشت مناسب است.
بنابراین حتی اگر در گذشته انجام داده ایم برخی از نمونه های نسبتا خودسرانه مربوط به بازگشت
که آیا نیازی به بازگشتی، با stuctures داده،
به ویژه درختان، آن را یک برنامه کامل از این ایده که یک مشکل است،
کاهش آن، و سپس حل از همان نوع، اما کوچکتر، برنامه.
>> بنابراین یکی دیگر از ساختمان داده است که ما می توانیم معرفی وجود دارد.
این است که در نگاه اول به نگاه مرموز طراحی شده است، اما این یکی از شگفت انگیز است.
بنابراین این یک ساختمان داده به نام درخت، درخت است که از بازیابی کلمه به ارث برده است،
دوباره امتحان کنید VAL تلفظ نیست، اما این چیزی است که جهان خواستار این چیزها. تلاش می کند. T-R-I-e.
این یک ساختار درختی از نوعی است، اما هر یک از گره ها در درخت
به نظر می رسد چه؟ و این است که کمی گمراه کننده است، زیرا این نوع از مخفف است.
اما به نظر می رسد مثل هر گره در این درخت است که در واقع یک آرایه است.
و حتی هر چند نویسنده از این نمودار نشان داده نشده است،
در این مورد، این درخت ساختار داده ها است که هدف در زندگی است برای ذخیره کلمات
مانند A-L-I-C-E و B-O-B.
و روشی که در آن این اطلاعات فروشگاه آلیس و باب و چارلی و آنیتا و غیره
آن را با استفاده از یک آرایه که در آن برای ذخیره آلیس در سرزمین درخت،
ما در گره ریشه است که به نظر می رسد مثل یک آرایه شروع،
و آن را در نماد مختصر نوشته شده است.
نویسنده حذف abcdefg چون هیچ نامهای با آن وجود دارد.
آنها نه تنها نشان داد M و P و T است، اما در این مورد،
اجازه دهید به دور از آلیس و باب و چارلی به برخی از اسامی که اینجا هستید.
ماکسول است که در واقع در این نمودار.
پس چطور فروشگاه نویسنده M-A-x-W-e-L-L؟
او در گره ریشه آغاز شده است، و رفت و به [M]، به طوری که تقریبا 13 محل سکونت: 13TH در آرایه.
سپس از آنجا، یک اشاره گر وجود دارد.
یک اشاره گر که منجر به یکی دیگر از آرایه.
از نویسنده وجود دارد که به آرایه در محل نمایه، در بالا سمت چپ نشان داده شده،
و پس از آن او به دنبال که اشاره گر به یک آرایه،
و به اشاره گر را در محل X. رفت
سپس در محل آرایه بعدی W، E، L، L، و غیره،
و در نهایت، اجازه دهید در واقع سعی کنید برای قرار دادن یک عکس به این.
چه نگاه گره مانند در کد؟
گره در درخت دارای یک آرایه از اشاره گر به گره.
اما هم وجود دارد باید به نوعی از ارزش های بولی، حداقل در این پیاده سازی است.
من اتفاق می افتد به آن را is_word. چرا؟
زیرا هنگامی که شما در حال قرار دادن ماکسول، شما در حال قرار دادن
هر چیزی را به این ساختار داده ها.
شما در حال M. نوشتن نیست شما X. نوشتن نیست
همه شما در حال انجام است که پس از اشاره گر است.
اشاره گر است که نشان دهنده M، سپس اشاره گر است که نشان دهنده یک،
سپس اشاره گر است که نشان دهنده X، سپس W، E، L، L،
اما آنچه شما نیاز دارید در پایان مرتب کردن بر اساس بروید، بررسی، من به این مکان رسید.
کلمه ای که در اینجا به پایان می رسد در ساختار داده ها وجود دارد.
>> پس چه درخت واقعا با پر و نویسنده، تصمیم گرفت برای نشان دادن
این terminuses با مثلث های کوچک.
این فقط بدان معنی است که این واقعیت این مثلث در اینجا، این مقدار بولی واقعی
معنی است که اگر شما به عقب در درخت،
این بدان معناست که یک کلمه به نام ماکسول در این است.
اما صنایع غذایی کلمه، به عنوان مثال،
در درخت نیست، چرا که اگر من در گره ریشه شروع در بالا،
هیچ اشاره گر F، هیچ اشاره گر O، هیچ اشاره گر O وجود دارد. FOO نام در این فرهنگ نیست.
اما در مقابل، تورینگ، t-u-R-I-N-G. باز هم، من T یا U و یا یک تحقیق و یا من یا N یا G را ذخیره نمی کند.
اما من در این ساختار داده را ذخیره یک مقدار از راه درست را در اینجا در این گره - در درخت
با تنظیم این مقدار بولی is_word درست است.
نوع درخت از این ساختار متا بسیار جالب است،
که در آن شما واقعا نمی ذخیره سازی کلمات خود را برای این نوع از فرهنگ لغت.
برای روشن باشد، شما فقط ذخیره سازی بله یا نه، یک کلمه وجود دارد که در اینجا به پایان می رسد.
>> حالا چه مفهوم است؟
اگر شما 150.000 کلمات موجود در فرهنگ لغت است که شما در حال تلاش برای در حافظه ذخیره
با استفاده از چیزی شبیه به یک لیست پیوندی،
شما در حال رفتن به 150،000 گره در لیست پیوندی خود.
و پیدا کردن یکی از این کلمات بر اساس حروف الفبا می تواند زمان O (n) را.
زمان خطی است. اما در مورد یک درخت،
زمان در حال اجرا از پیدا کردن یک کلمه؟
به نظر می رسد از زیبایی در اینجا این است که حتی اگر شما دارای 149،999 کلمه در حال حاضر در این فرهنگ،
با این ساختار داده ها اجرا شده است،
چه مدت آن را به پیدا کردن و یا قرار دادن یک نفر به آن، مانند آلیس، آلیس؟
خوب، آن را تنها 5، شاید 6 گام برای شخصیت عقبی.
از آنجا که حضور نام های دیگر در ساختار
در راه قرار دادن آلیس می کنید.
علاوه بر این، پیدا کردن آلیس یک بار 150،000 کلمات موجود در این فرهنگ لغت وجود دارد
در راه خود را برای پیدا کردن آلیس نه در همه،
چون آلیس است. است. است. است. است. در اینجا، چون که من پیدا کردم یک مقدار بولی است.
و اگر هیچ بولی درست باشد، پس آلیس وجود دارد این است که در این ساختار داده ها از کلمات نیست.
به عبارت دیگر، مدت زمان در حال اجرا برای پیدا کردن اشیاء و قرار دادن همه چیز به این جدید
ساختمان داده درخت O است - آن را به ñ هنوز.
از آنجا که حضور 150،000 نفر دارای هیچ اثر آلیس، آن را به نظر می رسد.
بنابراین اجازه دهید آن را K، که در آن K است که حداکثر طول یک کلمه در زبان انگلیسی
است که به طور معمول بیش از 20 چیزی کاراکتر است.
بنابراین K یک ثابت است. پس جام مقدس ما به نظر می رسد پیدا کرده اند در حال حاضر
این است که از یک درخت، زمان ثابت برای درج، برای متغیر، برای حذف.
از آنجا که تعدادی از چیزهایی که در حال حاضر در ساختار،
که حتی از لحاظ جسمی وجود ندارد. باز هم، آنها فقط نوع از چک کردن، آری یا نه،
هیچ تاثیری بر آینده آن زمان در حال اجرا است.
>> اما آنجا به گرفتن، در غیر این صورت ما را نمی اتلاف زمان بسیار
در تمام این ساختارهای داده ای دیگر فقط به در نهایت به یک راز شگفت انگیز دریافت کنید.
پس چه قیمت ما پرداخت برای رسیدن به این عظمت در اینجا؟ فضا.
این چیزی است که عظیم است. و به همین دلیل است که نویسنده
آن را در حال حاضر در اینجا، توجه کنید که همه این چیزهایی را که مانند آرایه ها نگاه کنید،
او بقیه از درخت، دیگر از درخت قرعه کشی نیست،
زیرا آنها فقط مربوط به داستان نیست.
اما همه از این گره های فوق العاده گسترده ای هستند، و هر گره در درخت طول می کشد تا
26 یا در واقع، می تواند 27 کاراکتر چون در این مورد من از جمله فضا برای آپوستروف
به طوری که ما می تواند کلمات apostrophized داشته باشد.
در این مورد، این آرایه وسیعی هستند. بنابراین حتی اگر آنها در حال picutured نیست،
این طول می کشد تا مقدار عظیمی از RAM است.
که ممکن است خوب، especilly در سخت افزار های مدرن،
اما این معاوضه است. ما زمان کمتری صرف فضای بیشتری است.
پس کجاست این همه رفتن؟
خوب، اجازه دهید - اجازه دهید اینجا را ببینید.
رفتن به این پسر اینجا.
>> باور کنید یا نه، به عنوان بسیار سرگرم کننده به عنوان C شده است برای برخی از زمان بوده است که در حال حاضر،
ما در حال رسیدن به نقطه در ترم که در آن زمان به انتقال به چیزهای مدرن تر است.
چیزهایی که در یک سطح بالاتر است. و حتی اگر برای چند هفته آینده
ما هنوز هم می خواهید به خودمان غوطه ور در جهان اشاره گرها و مدیریت حافظه ادامه
به این راحتی که ما پس از آن می توانید بر روی ساخت،
پایان بازی است که در نهایت به معرفی، جالب، این زبان نیست.
خواهیم صرف کنند، 10 دقیقه صحبت کردن در مورد HTML.
HTML یک زبان نشانه گذاری است، و آنچه که یک زبان نشانه گذاری است
این سری از براکت براکت باز و بسته که می گویند: "این ضخیم 'است
این کج (ایتالیک) 'را در این محور است.
این همه که فکری جالب نیست، اما آن را فوق العاده مفید است.
و این قطعا در همه جا حاضر است این روزها.
اما آنچه قدرتمند جهان از HTML، و برنامه نویسی وب به طور کلی،
ساختن چیزهایی پویا، نوشتن کد در زبان هایی مانند PHP یا پایتون یا روبی یا جاوا یا C #.
واقعا، به هر زبانی خود را از انتخاب است، و تولید HTML به صورت پویا.
ایجاد چیزی به نام CSS به صورت پویا.
شیوه نامه های آبشاری، که آن هم درباره زیبایی شناسی است.
و بنابراین حتی اگر امروز، اگر من به برخی از وب سایت مانند Google.com آشنا،
و من برای مشاهده، توسعه دهنده، منبع این دیدگاه، که شاید شما قبل از رفتن،
اما با رفتن به نمایش مبدأ، احتمالا این مسائل به نظر می رسد بسیار مرموز است.
اما این کد اساسی است که پیاده سازی Google.com است.
در بخش جلویی است. و در واقع همه این کرکی مسائل زیبایی شناسی است.
این CSS است تا اینجا. اگر من در حفظ و نوار پیمایش پایین خواهیم برخی از مواد رنگی را دریافت کنید.
HTML است. کد گوگل به نظر می رسد مثل یک ظرف غذا، اما اگر من در واقع باز کردن پنجره های مختلف،
ما می توانیم برخی از ساختار به این را مشاهده کنید.
اگر من برای باز کردن این تا اینجا، توجه، آن را کمی بیشتر قابل خواندن است.
ما قصد داریم تا قبل از اینکه طولانی این برچسب، [کلمه] برچسب،
HTML، سر، بدن، دیو، اسکریپت، ناحیه متن، دهانه، محور، دیو.
و این هم از مرموز، به دنبال مرتب کردن، در نگاه اول
اما همه از این آشفته بازار به دنبال الگوهای خاص، و الگوهای تکرار،
به طوری که زمانی که ما اصول اولیه، شما قادر خواهید بود برای نوشتن کد مثل این
و سپس کد مانند این استفاده از یک زبان، به نام جاوا اسکریپت را دستکاری کنند.
و جاوا اسکریپت یک زبان است که اجرا می شود به داخل یک مرورگر است
امروز که ما در دوره های هاروارد، استفاده از ابزار البته خرید که نقشه های گوگل استفاده می کند
برای شما یک دسته کامل از پویایی می دهد، فیس بوک به شما می دهد برای نشان دادن به روز رسانی وضعیت از طریق مسنجر،
توییتر از آن استفاده می کند به شما نشان می دهد توییت فورا.
همه از این ما آغاز خواهد شد به خودمان غوطه ور شوید.
اما برای رسیدن به آنجا، ما نیاز به درک چیزی کمی در مورد اینترنت.
این کلیپ در اینجا فقط یک دقیقه طولانی، و اجازه دهید فرض کنیم در حال حاضر این است که، در واقع،
اینترنت چگونه کار می کند به عنوان یک تیزر برای آنچه که در مورد آمده است. من به تو "رزمندگان خالص است."
>> [♫ موسیقی کر آهسته ♫]
[راوی پسر او با پیام آمد.
با پروتکل تمام خود را است.
[♫ سریعتر موسیقی الکترونیک ♫]
او به جهان از فایروال سرد آمد، uncaring روتر،
و خطرات به مراتب بدتر از مرگ است.
او سریع است. او قوی است. TCP / IP، و او را به آدرس شما.
سربازان خالص.
[مالان] هفته بعد، و سپس. اینترنت می باشد. برنامه نویسی وب. این CS50 است.
[CS50.TV]