বক্তা 1: ঠিক আছে, তাই এই হল এবং CS50 এই সপ্তাহে পাঁচ শেষে হয়. আর যে শেষবার কবে আমরা শুরু কল্পনাকারী ডাটা এ খুঁজছেন সমাধান করতে শুরু করে যে কাঠামো পরিচয় করিয়ে দিতে শুরু করে সমস্যার, নতুন সমস্যা, কিন্তু এই চাবিকাঠি থ্রেডিং ধরণের ছিল যে আমরা নোড থেকে নোড করতে শুরু করে. তাই অবশ্যই এই হল একটি একেলা লিঙ্ক তালিকা. আর করে একেলা, লিঙ্ক আমি শুধু একটা আছে মানে যারা নোড প্রতিটি মধ্যে থ্রেড. আপনি কল্পনাকারী না পারেন সক্রিয় আউট দোকর লিঙ্ক তালিকা ভালো জিনিস আপনি একটি তীর আছে যদ্দ্বারা , উভয় দিক থেকেই যাচ্ছে যা নির্দিষ্ট দক্ষতাসম্পন্ন সাহায্য করতে পারে. কিন্তু এই সমস্যার সমাধান? এই কি সমস্যার সমাধান হয়নি? আমরা সোমবার কেন নিয়েছে? কেন, তত্ত্ব, আমরা সোমবার গ্রাহ্য হয়নি? এটার কাজ কি? 

শ্রোতা: আমরা পরিবর্তনশীল এটা মাপ পরিবর্তন করতে পারেন. 

বক্তা 1: ঠিক আছে, আমরা করতে পারেন, তাই পরিবর্তনশীল এটা মাপ পরিবর্তন. আচ্ছা আপনি উভয় সম্পন্ন. তাই আপনি যদি এই পরিবর্তনশীল মাপ পরিবর্তন করতে পারেন ডাটা স্ট্রাকচার, একটি অ্যারের যেহেতু, রিকল, আপনি একটি জানা আছে অবরোহী কতটা স্থান আপনি চান এবং আপনি একটু বেশি প্রয়োজন হলে স্থান, আপনার ভাগ্য আউট ধরনের করছি. আপনি একটি সম্পূর্ণ নতুন অ্যারে তৈরি করা আছে. আপনি সব সরানো আছে আপনার এক থেকে অন্য তথ্য, অবশেষে পুরানো অ্যারে মুক্ত আপনি যা করতে পারেন, এবং তারপর যদি চালিয়ে যান তবে. যা শুধু খুব ব্যয়বহুল মতানুযায়ী এবং খুব অদক্ষ, এবং প্রকৃতপক্ষে এটা হতে পারে. কিন্তু এই সব ভাল নয়. আমরা একটি মূল্য দিতে, এক কি ছিল আরো সুস্পষ্ট দাম আমরা একটি লিঙ্ক তালিকা ব্যবহার করে দিতে? 

শ্রোতা: আমরা ব্যবহার করতে হবে প্রতিটি এক জন্য ডবল স্পেস. বক্তা 1: হ্যাঁ, তাই আমরা প্রয়োজন অন্তত দুবার অনেক স্থান হিসাবে. আসলে, আমি বুঝতে পেরেছি এই ছবি এর এমনকি সামান্য বিভ্রান্তিকর, কারণ আধুনিক অনেক মধ্যে CS50 আইডিই তে কম্পিউটার, একটি পয়েন্টার বা একটি ঠিকানা আসলে চার বাইট নয়. এটা খুব প্রায়ই এইসব কী দিন আট বাইট, যা নীচে মানে সবচেয়ে বাস্তবে আছে আয়তক্ষেত্র দ্বিগুণ হিসাবে ধরনের হয় আমি টানা করেছি কি হিসাবে বড়, যা আপনি তিনবার হিসাবে ব্যবহার করছেন মানে আমরা অন্যথায় থাকতে পারে যতটা স্থান. এখন একই সময়ে, আমরা করছি এখনও বাইট কথা, তাই না? আমরা অগত্যা কথা বলছি না মেগাবাইটের বা গিগাবাইট, এই তথ্য যদি না কাঠামো বড় পেতে. 

আর তাই আজ আমরা বিবেচনা শুরু আমরা তথ্য অন্বেষণ পারে কিভাবে আরো দক্ষতার মধ্যে যদি আসলে তথ্য পায় বড়. কিন্তু এর canonicalize করার চেষ্টা করা যাক প্রথম অপারেশন আপনি এই সাইটে কাজ করতে পারেন যে ডাটা স্ট্রাকচার ধরণের. একটি লিঙ্ক মত এত কিছু তালিকায় সাধারণত সমর্থন অপারেশন মুছে মত, সন্নিবেশ, এবং অনুসন্ধান. আর আমি যে দ্বারা কি বোঝাতে চেয়েছেন? যে শুধু, যে সাধারণত এর অর্থ মানুষ লিঙ্ক তালিকা ব্যবহার করে থাকেন তাহলে, তারা বা অন্য কেউ বাস্তবায়িত হয়েছে মুছে সন্নিবেশ মত ফাংশন, এবং অনুসন্ধান, আপনি যা করতে পারেন, তাই আসলে কিছু না ডাটা স্ট্রাকচার সাথে দরকারী. সুতরাং আসুন একটি দ্রুত কটাক্ষপাত করা যাক আমরা বাস্তবায়ন হতে পারে একটি লিঙ্ক তালিকা জন্য কোড হিসাবে অনুসরণ করে. 

সুতরাং এই মাত্র কিছু সি কোড, না এমনকি একটি সম্পূর্ণ প্রোগ্রাম আমি সত্যিই দ্রুত আপ বেত্রাঘাত যে. এটা বিতরণে অনলাইন না কোড, আসলে এটি চালানো হবে না, কারণ. কিন্তু আমি শুধু করেছি বিজ্ঞপ্তি একটি মন্তব্য বলেন, ডট ডট ডট, কিছু আছে সেখানে আছে, কিছু বিন্দু বিন্দু বিন্দু. আর এর ঠিক তাকান সরস অংশ কি. তাই লাইন তিনটি উপর, এই এখন যে প্রত্যাহার আমরা সর্বশেষ একটি নোড ঘোষণা করার প্রস্তাব সময়, যারা আয়তক্ষেত্রাকার বস্তুর এক. এটা আমরা এন ডাকবো যে কোন int আছে কিন্তু আমরা কিছু কল করতে পারে, এবং তারপর একটি struct নোড তারকা পরের বলা. আর শুধু, যে দ্বিতীয় স্পষ্ট করা লাইন, লাইন ছয় উপর, যে কি? এটা আমাদের জন্য কী করছে? এটা অবশ্যই আরো মনে হচ্ছে, কারণ আমাদের স্বাভাবিক ভেরিয়েবল চেয়ে রহস্যপূর্ণ. 

শ্রোতা: এটা এক উপর সরানো তোলে. 

বক্তা 1: এটা এক উপর সরানো তোলে. আর, আরো ভালো হবে এটা অঙ্ক সংরক্ষণ করবে হতে বোঝানো যে নোড অর্থগত পাশে, ডান? তাই এটা করা যাচ্ছে না অগত্যা কিছু সরানো. এটা শুধু যাচ্ছে যা, একটি মান সংরক্ষণ অঙ্ক হতে যাচ্ছে অন্য কিছু নোড, আমরা struct বলেন করেছি যে কেন নোড তারকা, তারকা বাচক একটি পয়েন্টার বা একটি ঠিকানা. ঠিক আছে, তাই এখন আপনি আমরা আছে অনুমান যদি আমাদের জন্য উপলব্ধ এই এন, ও এর দিন অন্য কেউ আছে অনুমান পূর্ণসংখ্যার আভা ঢোকানো একটি লিঙ্ক তালিকা মধ্যে. আর যে সংযুক্ত তালিকা কিছু পয়েন্ট দ্বারা জোরাল যে একটি পরিবর্তনশীল বলা তালিকা একটি প্যারামিটার হিসেবে এখানে সালে পাশ, কিভাবে আমি লাইন সম্পর্কে যান 14 অনুসন্ধান বাস্তবায়ন? অন্য কথায়, আমি বাস্তবায়ন করছি যদি জীবনে যার উদ্দেশ্য ফাংশন তারপর কোন int এবং নিতে হয় একটি লিঙ্ক তালিকা শুরুতে, যে লিঙ্ক তালিকায় একটি পয়েন্টার. প্রথম ভালো লেগেছে, আমি ডেভিড যারা মনে আমাদের স্বেচ্ছাসেবক, সোমবার ছিল তিনি এ নির্দেশ ছিল পুরো লিঙ্ক তালিকা, আমরা পার করছি যদিও এটা হিসাবে ডেভিড এখানে আমাদের আর্গুমেন্ট হিসাবে. কিভাবে আমরা এই তালিকায় ঘোরা সম্পর্কে যান? ওয়েল, দেখা যাচ্ছে যে, যদিও পয়েন্টার, আমাদের এখন তুলনামূলকভাবে নতুন আমরা তুলনামূলকভাবে এই কাজ করতে পারেন সরাসরি. 

আমি এগিয়ে যেতে চলেছি এবং একটি অস্থায়ী ভেরিয়েবল ডিক্লেয়ার যে কনভেনশন দ্বারা শুধু যাচ্ছে যাও, PTR পয়েন্টার বলা হয়, বা করা কিন্তু আপনি কিছু করতে চান তা বলতে পেরেছিলাম. আর আমি আরম্ভ করতে যাচ্ছি এটা তালিকার শুরুর করার. তাই আপনি যদি এই ধরনের মনে করতে পারেন আমার শিক্ষক হিসাবে অন্যান্য দিন, ধরনের কেউ এ ইশারা স্বেচ্ছাসেবী হিসাবে আমাদের মানুষের মধ্যে. তাই আমি যে একটি অস্থায়ী পরিবর্তনশীল আছি ঠিক একই জিনিস টার দিকে নির্দেশ আমাদের কাকতালীয়ভাবে নামে যে স্বেচ্ছাসেবক দায়ূদ ইশারা ছিল. এখন পয়েন্টার যখন নাল না, কারণ রিকল যে নাল কিছু বিশেষ সেন্টিনেলে মান তালিকার শেষ demarcates আমি এ ইশারা করছি না, তাই যখন আমাদের সর্বশেষ স্বেচ্ছাসেবক মত মাটিতে ছিল, আসুন এগিয়ে যান এবং নিচের কাজগুলো. পয়েন্টার এবং এখন যদি আমি ধরনের চান আমরা ছাত্র সঙ্গে কি কি করতে কাঠামো পয়েন্টার ডট পরের তাহলে সমান পয়েন্টার ডট এন, সমান বরং যদি পরিবর্তনশীল N, সমান এ পাশ হয়েছে যে যুক্তি, তারপর আমি এগিয়ে যেতে চান এবং সত্য ফিরে বলে. আমি ভেতরে সংখ্যা n পাওয়া যায় আমার লিঙ্ক তালিকা নোড এক. কিন্তু বিন্দু আর এই প্রেক্ষাপটে কাজ, পয়েন্টার, PTR, কারণ প্রকৃতপক্ষে একটি পয়েন্টার, একটি ঠিকানা, আমরা আসলে একটি wonderfully পারেন সিনট্যাক্স অবশেষে এক টুকরা ব্যবহার তোলে তজ্জাতীয় স্বজ্ঞাত অর্থে এবং আসলে থেকে যান, যার মানে, এখানে একটি তীর ব্যবহার সেখানে পূর্ণসংখ্যা যে অঙ্ক. সুতরাং যে ব্যক্তি অনুরূপ ডট অপারেটর আত্মা, কিন্তু পয়েন্টার একটি পয়েন্টার না থাকার কারণে এবং না একটি প্রকৃত struct নিজেই, আমরা শুধু তীর ব্যবহার. 

যদি তাই বর্তমান নোড যে আমি, অস্থায়ী পরিবর্তনশীল, এ ইশারা করছি এন, আমি কি করতে চাও না? ওয়েল, আমার মানুষের স্বেচ্ছাসেবকদের সঙ্গে আমরা অন্যান্য দিন এখানে ছিল যে, আমার প্রথম মানব এক আমি না হয় তাহলে চান, এবং হয়ত দ্বিতীয় মানব নয় আমি চাই এক, এবং তৃতীয়, আমি চলন্ত শারীরিকভাবে রাখা প্রয়োজন. চাই কিভাবে আমি একটি তালিকা মাধ্যমে পইঠা না? আমরা একটি অ্যারের ছিল, আপনি শুধু আমি প্লাস প্লাস চাই না. কিন্তু এই ক্ষেত্রে, এটা করার জন্য যথেষ্ট পরের, পয়েন্টার, পায়, পয়েন্টার না. অন্য কথায়, পরের ক্ষেত্রের বাম হাতের সব ভালো হয় সোমবার আমাদের মানব স্বেচ্ছাসেবকদের অন্য কিছু নোড এ নির্দেশ ব্যবহার ছিল. যারা তাদের পাশে প্রতিবেশীদের ছিল. 

আমি এই তালিকার মাধ্যমে পইঠা করতে চান তাহলে, আমি শুধু, আর আমি কি প্লাস প্লাস পারবেন না আমি পরিবর্তে বলার আছে আমি পয়েন্টার, যাচ্ছে পরবর্তী ক্ষেত্রে যাই হোক না কেন সমান, পরবর্তী ক্ষেত্রে, পরের ক্ষেত্রের কিছু r, হয় যারা বাম হাতের সমস্ত নিম্নলিখিত আমরা পর্যায়ে প্রতি নির্দেশ ছিল যে কিছু পরবর্তী মান. আর আমি মাধ্যমে পেতে হলে যে পুরো পুনরাবৃত্তির, এবং পরিশেষে, আমি না থাকার নাল আঘাত পাওয়া এন এখনও, আমি শুধু তাই ফিরে এলাম. তাই আবার, আমরা এখানে কি করছেন যে সব, একটি মুহূর্ত আগে ছবি অনুযায়ী, প্রতি নির্দেশ করে শুরু হয় সম্ভবতঃ তালিকা শুরুতে. এবং তারপর আমি পরীক্ষা, মান আমি নয়টি সমান খুঁজছি? যদি তাই হয়, আমি সত্য ফিরে এবং আমি কাজ করছি. যদি না হয়, আমি আমার হাত আপডেট, ওরফে পয়েন্টার, নির্দেশ পরের তীর এর অবস্থানে, এবং তারপর পরবর্তী তীর এর অবস্থান, এবং পরের. আমি কেবল এই অ্যারে মাধ্যমে হাঁটা করছি. 

তাই আবার, যারা বজায় রাখে? ভালো লেগেছে এই জন্য একটি উপাদান কি? ওয়েল, আমরা চালু প্রত্যাহার একটি স্ট্যাক এর ধারণা, যা হিসেবে এটি একটি বিমূর্ত তথ্য যতটা টাইপ হয় না একটি সি জিনিস, এটা একটি CS50 জিনিস না, এটি একটি বিমূর্ত ধারণা, এই ধারণা একে অপরের উপরে কিছু stacking যে প্রয়োগ করা যেতে পারে বিভিন্ন উপায়ে কাঁদি. আর আমরা প্রস্তাব একটি উপায় সঙ্গে ছিল একটি অ্যারের, বা একটি লিঙ্ক তালিকা. এবং এটি একটি, যে canonically সক্রিয় আউট স্ট্যাক অন্তত দুটি অপারেশন সমর্থন করে. এবং Buzz শব্দ, ধাক্কা স্ট্যাকের মধ্যে কিছু ধাক্কা, একটি নতুন ট্রে মত ডাইনিং হল, বা পপ, যা আগ অপসারণ মানে ডাইনিং স্ট্যাক থেকে ট্রে হল, এবং তারপর হয়তো কিছু অন্যান্য অপারেশন পাশাপাশি. তাই কিভাবে আমরা কাঠামো নির্ধারণ পারে আমরা এখন একটি স্ট্যাক আহ্বান করছি যে? 

ওয়েল, আমরা প্রয়োজনীয় সব আছে আমি বলতে সি আমাদের নিষ্পত্তি সিনট্যাক্স, আমার একটি টাইপ সংজ্ঞা দিতে একটি স্ট্যাকের ভিতরে একটি struct, আমি একটি, একটি অ্যারে বলতে যাচ্ছি পুরো সংখ্যার গুচ্ছ এবং তারপর আকার. তাই অন্য কথায়, যদি আমি চাই কোড এই বাস্তবায়ন, আমি গিয়ে শুধু ধরনের দিন এই কি বলছে না আঁকা. এই বলার অপেক্ষা রাখে না, তাই আমাকে একটি দিতে একটি অ্যারের পেয়েছিলাম যে কাঠামো, এবং আমি ক্ষমতা কি জানেন না এটা আমি করেছি যে দৃশ্যত কিছু ধ্রুবক অন্যত্র সংজ্ঞায়িত, এবং যে সূক্ষ্ম. কিন্তু, এটা শুধু একটা অনুমান দুই, তিন, চার, পাঁচ. তাই ক্ষমতা 5. ভিতর এই উপাদান আমার কাঠামো সংখ্যা বলা হবে. এবং তারপর আমি এক প্রয়োজন অন্যান্য পরিবর্তনশীল দৃশ্যত প্রথমে আমি যাচ্ছি যে বলা আকার শূন্য প্রারম্ভের উপপত্রিক. কিছুই আছে কি না তা স্ট্যাক, আকার, শূন্য এবং এটি সংখ্যায় আবর্জনা মান. আমি এখনও সেখানে কি কোন ধারণা আছে. 

আমি ধাক্কা চান তাই স্ট্যাকের মধ্যে কিছু, আমি ফাংশন ধাক্কা কল অনুমান, এবং আমি সংখ্যা 50 মত, 50 বলে ধাক্কা যেখানে আপনি উত্থাপন করা হবে আমি এই অ্যারের মধ্যে এটি আঁকা? পাঁচটি পৃথক সম্ভাব্য উত্তর আছে. কোথায় আপনি সংখ্যা 50 ধাক্কা চাও? এখানে লক্ষ্য যদি, আবার কল ফাংশন ধাক্কা, একটি আর্গুমেন্ট পাস 50 এর, যেখানে আমি এটি স্থাপন করা হয়? পাঁচ possible-- 20% সম্ভাবনা এর সঠিকভাবে অনুমান. হ্যাঁ? 

শ্রোতা: দূরে ডান. 

বক্তা 1: দূরে ডান. একটি 25% সম্ভাবনা এখন নেই এর সঠিকভাবে অনুমান. সুতরাং যে আসলে জরিমানা করা হবে. কনভেনশন দ্বারা, আমি একটি অ্যারের সাথে বলবো, আমরা সাধারণত, বাম থেকে খেলা আরম্ভ হবে কিন্তু আমরা অবশ্যই পারে ডানদিকে শুরু. সুতরাং এখানে ভক্ষক আমি হতে হবে সম্ভবত বাম এটা আঁকতে, শুধু একটি স্বাভাবিক অ্যারে যেখানে চান আমি ডানে বামে যাওয়া শুরু. কিন্তু আপনি টুসকি পারেন তাহলে গাণিতিক, সূক্ষ্ম. এটা শুধু প্রচলিত নয়. ঠিক আছে, আমি এক করতে হবে যদিও আরো পরিবর্তন. এখন আমি কিছু ধাক্কা করেছি যে স্ট্যাকের মধ্যে, কি করব? 

ঠিক আছে, আমি আকার বাড়ায় আছে. তাই আমাকে এগিয়ে এবং শুধু যেতে দিন শূন্য যা ছিল এই, আপডেট. এর পরিবর্তে এখন আমি যাচ্ছি মূল্য এক করা. এবং এখন আমি অন্য ধাক্কা অনুমান স্ট্যাকের মধ্যে সংখ্যা, 51 মত. ওয়েল, আমি আরও একটি করতে হবে আকার দুটি পর্যন্ত যা পরিবর্তন. এবং তারপর আমি আরো এক ধাক্কা অনুমান 61 ভালো স্ট্যাকের মধ্যে নম্বর, এখন আমি মাপ আপডেট করা দরকার আরও একটি সময়, এবং মাপ হিসাবে মান 3 পেতে. এবং এখন আমি পপ কল অনুমান. এখন কনভেনশন দ্বারা, পপ, একটি আর্গুমেন্ট গ্রহণ করা হয় না. একটি স্ট্যাক সঙ্গে, পুরো ট্রে রূপক বিন্দু আপনি বিচক্ষণতা আছে না হয় যে ট্রে পেতে যেতে, সব আপনি কি করতে পারেন থেকে আগ এক পপ হয় স্ট্যাক, মাত্র কারণ. এই তথ্য যে কাঠামো আছে কি. 

তাহলে যে যুক্তি দ্বারা তাই আমি পপ, তা বন্ধ আসে বলে? তাই 61. সত্যিই তাই কম্পিউটার কি মেমরি কাজ করতে যাচ্ছেন? কি আমার কোড কি আছে? আপনি কি উত্থাপন করা হবে আমরা পর্দায় পরিবর্তন? কি পরিবর্তন করা উচিত? দুঃখিত? তাই আমরা 61 এর পরিত্রাণ পেতে. তাই আমি স্পষ্টভাবে তা করতে পারে. আর আমি 61 পরিত্রাণ পেতে পারেন. এবং তারপর কি অন্যান্য পরিবর্তন ঘটতে প্রয়োজন? আকার সম্ভবত দুই ফিরে যেতে হয়েছে. আর তাই যে সূক্ষ্ম. কিন্তু একটি মিনিট, আকার অপেক্ষা একটি মুহূর্ত আগে তিনটি ছিল. এর মাত্র একটি দ্রুত বৈধতা না পরীক্ষা. আমরা কিভাবে আমরা জানি যে হয়নি 61 পরিত্রাণ পেতে চান? আমরা পপিং করছি. এবং তাই আমি এই দ্বিতীয় সম্পত্তি আকার আছে. 

আমি আছি, এক মিনিট অপেক্ষা করুন সপ্তাহে দুই ফিরে চিন্তা আমরা যে বিষয়ে কথা শুরু হলে এই পাঁচ শূন্য ছিল যেখানে অ্যারে, এই পাঁচ ছিল, এই অবস্থান ছিল দুই, এই পাঁচ তিন, চার, এটা দেখে মনে হচ্ছে আকার মধ্যে সম্পর্ক এবং আমি চাই যে উপাদান মুছে ফেলার জন্য অ্যারে থেকে শুধু কি উপস্থিত হতে পারে? আকার বিয়োগ এক. আর তাই যে কিভাবে মানুষের হিসাবে আমরা 61 প্রথম আসে জানেন. কিভাবে কম্পিউটার জানা যাচ্ছে? যখন আপনার কোড, যেখানে আপনি সম্ভবত আকার বিয়োগ এক কাজ করতে চান, তাই তিন বিয়োগ এক দুই, এবং যে হয় আমরা 61 এর পরিত্রাণ পেতে চান মানে. এবং তারপর আমরা প্রকৃতপক্ষে আপডেট করতে পারেন যে আকারের তাই আকার এখন মাত্র দুই থেকে তিন থেকে যায়. আর শুধু গোঁড়া হবে, আমি যাচ্ছি ঠিক আছে, আমি কাজ করছি যে উত্থাপন করা? আপনি intuitively প্রস্তাবিত সঠিকভাবে আমি 61 পরিত্রাণ পাওয়া উচিত. কিন্তু নেই আমি ধরনের সাজান 61 পরিত্রাণ অর্জিত? আমি কার্যকরভাবে বিস্মৃত করেছি যে এটা আসলে আছে. আপনি পড়তে করেছি, ফিরে Pset4 মনে ফরেনসিক সম্পর্কে নিবন্ধ, পিডিএফ আমরা ছিল যে আপনাকে বলছি পড়তে, অথবা আপনি Pset4 জন্য এই সপ্তাহে পড়তে হবে. এই করতে আসলে সঙ্গত যে প্রত্যাহার কম্পিউটার ফরেনসিক পুরো ধারণা. কি একটি কম্পিউটার সাধারণতঃ হয় কিছু হয় যেখানে এটি শুধু, ভুলে যায় কিন্তু এটা যান এবং মত না এটি বা ওভাররাইড স্ক্র্যাচ চেষ্টা zeros এবং বেশী সঙ্গে যারা বিট বা অন্য কিছু র্যান্ডম প্যাটার্ন আপনি যদি না নিজেকে তাই ইচ্ছাকৃতভাবে না. সুতরাং আপনার অনুভূতি ছিল ঠিক আছে, এর 61 পরিত্রাণ পেতে যাক. কিন্তু বাস্তবে আমরা বিরক্ত করতে হবে না. আমরা শুধু যে ভুলে যাওয়া প্রয়োজন এটা তোলে আমাদের আকার পরিবর্তন করে আছে. 

এখন এই স্ট্যাকের সঙ্গে একটা সমস্যা আছে. আমি ঠেলে জিনিস রাখা স্ট্যাকের মধ্যে, কি স্পষ্টত ঘটতে যাচ্ছে মাত্র কয়েক মুহূর্তের সময়? আমরা স্থান ফুরিয়ে যাচ্ছেন. এবং আমরা কি করতে পারি? আমরা কোন ধরনের মাতাল করছি. এই বাস্তবায়ন করতে দেওয়া হয় না ব্যবহার, কারণ আমাদের অ্যারের মাপ পরিবর্তন এই বাক্য গঠন, আপনি যদি সপ্তাহে দুই ফিরে মনে, আপনি ঘোষণা করেছি একবার একটি অ্যারের আকার, আমরা এখনো যেখানে একটি প্রক্রিয়া দেখা যায় নি আপনি অ্যারে মাপ পরিবর্তন করতে পারেন. এবং প্রকৃতপক্ষে সি যে বৈশিষ্ট্য নেই. আপনি যদি বলি আমার পাঁচটি দিতে Nths, তাদের সাথে যোগাযোগ করে নম্বর, যে আপনি এটি পেতে যাচ্ছেন সব. সুতরাং আমরা সোমবার হিসাবে এখন কি, আছে একটি সমাধান প্রকাশ করার ক্ষমতা যদিও, আমরা শুধু খামচি করতে হবে আমাদের স্ট্যাকের সংজ্ঞা কিছু হার্ড কোডেড অ্যারে হতে না করার জন্য, কিন্তু শুধু একটি ঠিকানা সংরক্ষণ. 

এখন এই হল কেন? এখন আমরা শুধু সঙ্গে আরামদায়ক হতে হবে আসলে আমার প্রোগ্রাম রান যখন যে, আমি সম্ভবতঃ যাচ্ছি মানুষের জিজ্ঞাসা আছে, কত নম্বর আপনি কি সেটি বদলাতে চান? তাই ইনপুট কোথাও থেকে আসা হয়েছে. কিন্তু আমি জানি যে একবার সংখ্যা, তারপর আমি যা করতে পারেন দিতে ফাংশন কি ব্যবহার আমার মেমরি একটি খণ্ড? আমি malloc ব্যবহার করতে পারেন. আর আমি কোনো সংখ্যা বলতে পারেন বাইট আমি ফিরে এই Nths জন্য চান. এবং সব আমি সংখ্যায় সঞ্চয় আছে এই struct ভিতরে এখানে পরিবর্তনশীল কি হওয়া উচিত? কি আসলে মধ্যে যায় এই দৃশ্যকল্প মধ্যে নম্বর? হ্যা, প্রথম একটি পয়েন্টার মেমরি যে তাল বাইট, বা আরো নির্দিষ্টভাবে, অঙ্ক যারা বাইট প্রথম. এটা এক যদি কোন ব্যাপার না বাইট বা বিলিয়ন বাইট, আমি শুধু প্রথম যত্নের প্রয়োজন. কারণ কি malloc নিশ্চয়তা ও আমার অপারেটিং সিস্টেম নিশ্চয়তা, যে মেমরি আমি খণ্ড পেতে, এটা সংলগ্ন হতে যাচ্ছে. ফাঁক হতে যাচ্ছে না. আমি 50 এর জন্য জিজ্ঞাসা করেছি, তাই যদি বাইট বা 1,000 বাইট, তারা সব হতে যাচ্ছেন ফিরে ফিরে যাও যাও যাও. আর এতক্ষণ আমি কিভাবে বড় মনে হিসাবে অনেক আমি আমার জানা দরকার, সব জন্য জিজ্ঞাসা প্রথম যেমন ঠিকানা. 

তাই এখন আমরা কোড মধ্যে ক্ষমতা আছে. যদ্যপি এটা আমাদের নিতে যাচ্ছে আরো সময়, এই পর্যন্ত লিখতে আমরা এখন যে মেমরি বরাদ্দ করতে পারে শুধু আছে একটি ভিন্ন ঠিকানা সংরক্ষণ করা আমরা এমনকি একটি বড় বা চান মেমরি একটি ছোট খণ্ড. তাই এখানে একটি ট্রেড বন্ধ করার. এখন আমরা গতিশীলতা পেতে. আমাদের এখনো আছে contiguousness আমি দাবি করছি. যদি malloc আমাদের দিতে হবে, কারণ মেমরি সংলগ্ন অঞ্চলে. কিন্তু এই একটি ব্যথা হতে যাচ্ছে আমাদের জন্য ঘাড়, প্রোগ্রামার, আসলে আপ কোড. এটা শুধু আরো কাজ. আমরা আমি কি ছিল সদৃশ কোড প্রয়োজন শুধু একটা মুহূর্ত আগে আউট banging. অত্যন্ত doable কিন্তু এটা জটিলতা যোগ. আর তাই ডেভেলপার সময়, প্রোগ্রামার সময় এখনও অন্য সম্পদ আমরা ব্যয় করার প্রয়োজন হতে পারে যে কিছু সময় নতুন বৈশিষ্ট্য পেতে. এবং তারপর অবশ্যই একটি কিউ আছে. আমরা এই মধ্যে যেতে হবে না অনেক বিস্তারিতভাবে এক. কিন্তু এটা আত্মা খুব অনুরূপ. আমি একটি কিউ বাস্তবায়ন করতে পারে, এবং তার সংশ্লিষ্ট অপারেশন, সারিবদ্ধ বা dequeue, যোগ অথবা অপসারণ করতে চাই, এটা বলার অপেক্ষা রাখে না শুধু একটি কল্পনাকারী উপায় সারিবদ্ধ বা dequeue, হিসাবে অনুসরণ করে. আমি শুধু নিজেকে একটি struct দিতে পারেন যে আবার একটি সংখ্যা এর অ্যারে আছে, যে আবার একটি আকার আছে, কিন্তু কেন আমি এখন যা দরকার তা না একটি কিউ সামনে ট্র্যাক রাখতে? আমি জানতে হবে না আমার স্ট্যাকের সামনে. ওয়েল, যদি আমি আবার একটি queue-- শুধু কঠিন দিন পাঁচটি মত থাকার হিসাবে এটি কোড এখানে সম্ভাব্য মধ্যে পূর্ণসংখ্যার. সুতরাং এই শূন্য, এক, দুই, তিন, চার হয়. এই হতে যাচ্ছে আবার বলা নম্বর. এবং এই আকার বলা হবে. 

কেন এটা যথেষ্ট নয় শুধু আকার আছে? ওয়েল, এর ঐ একই নম্বর ধাক্কা দেওয়া. তাই আমি সারিবদ্ধ, অথবা ধাক্কা pushed--. এখন আমি তখন 50 সারিবদ্ধ, এবং করব 51, এবং তারপর 61, এবং বিন্দু বিন্দু বিন্দু. সুতরাং যে সারিবদ্ধ এর. আমি তখন 61, তারপর 50, 51 সারিবদ্ধ. আর যে অভিন্ন দেখায় এখন পর্যন্ত একটি স্ট্যাক, ছাড়া আমি একটা পরিবর্তন করা হবে না. আমি এই সাইজ আপডেট করা দরকার, তাই আমি যেতে এখন দুই থেকে তিন এক শূন্য থেকে. আমি কিভাবে dequeue না? কি dequeue সঙ্গে ঘটবে? কে প্রথম এই তালিকায় খসা উচিত এটা আপেল দোকান লাইনে যদি? তাই 50. সুতরাং এটা কোন ধরনের নবতারাগুলোর এই সময়. শেষ সময় যেহেতু এটি সুপার ছিল সহজ শুধু, আকার বিয়োগ এক করতে আমি কার্যকরভাবে আমার অ্যারের শেষে পেতে সংখ্যা, যেখানে এটা 61 সরিয়ে ফেলা হয়. কিন্তু আমি 61 সরাতে চান না. আমি 50 নিতে চান যারা 5:00 এ ছিল জন্য রেখায় আপ নতুন আইফোন বা যে কোন বস্তু. আর তাই আমি 50 এর পরিত্রাণ পেতে ঠিক ঠিক, এই কাজ করতে পারে না? আমি 50 ক্রুশ আউট করতে পারেন. কিন্তু আমরা শুধু বলেন এত মলদ্বারে করা হবে না হিসাবে আউট স্ক্র্যাচ বা তথ্য লুকান. যেখানে এটা আমরা শুধু ভুলে যেতে পারেন. 

কিন্তু আমি এখন আমার আকার পরিবর্তন করা হলে দুই, এই যথেষ্ট তথ্য নেই আমার কিউ 'র মধ্যে কি ঘটছে জানতে? আসলে তা না. আমার আকার, দুই মত কিন্তু কিউ যেখানে শুরু নেই, বিশেষ করে আমি এখনও আছে স্মৃতিতে সেই একই নম্বর. 50, 51, 61. তাই আমি মনে রাখা প্রয়োজন এখন সামনে যেখানে. তাই আমি প্রস্তাব হিসাবে সেখানে আমরা শুধু বলা আছে করব যার প্রাথমিক তম সামনে, মূল্য কি হওয়া উচিত ছিল? জিরো, তালিকা মাত্র শুরুতে. কিন্তু এখন ছাড়াও decrementing করতে আকার, আমরা শুধু সামনে বাড়ায়. এখন এখানে অন্য সমস্যা. তাই আমি যাব রাখতে একবার. এই সংখ্যা ধরুন মত 121, 124, এবং তারপর, সব dammit, আমি স্থান থেকে বাদ. কিন্তু আমি নই, একটি মিনিট অপেক্ষা করুন. গল্পের এই সময়ে, তাই, আকার এক, দুই যে অনুমান, তিন, চার, তাই আমি অনুমান যে আকার, সামনে এক, চার তাই 51 সামনে এ হয়. আমি এখানে অন্য একটি নম্বর লাগাতে চান, কিন্তু, সব dammit, আমি স্থান থেকে বাদ. কিন্তু আমি ঠিক আছে, সত্যিই নই? আমি কিছু কোথায় লাগাতে পারে 171 ভালো অতিরিক্ত মূল্য,? হ্যা, আমি আমার কর্তব্য শুধু ধরনের ঠিক আছে, ফিরে ওইখানে যান? এবং তারপর 50 ক্রুশ আউট, বা শুধু 171 সঙ্গে এটি মুছে ফেলা হয়. এবং আপনি কেন হতাশ করছি আমাদের সংখ্যা, তাই র্যান্ডম পেয়েছিলাম এই সাধারণত কম্পিউটার নেয়া হয় পরে CS50 হার্ভার্ড এ বিজ্ঞান কোর্স. কিন্তু যে একটি ভাল অপ্টিমাইজেশান ছিল, এখন, কারণ আমি স্থান নাশক করছি না. আমি এখনও মনে আছে কত বড় এই জিনিস মোট. এটা মোট পাঁচটি এর. কারণ আমি চাই না 51 মুছে শুরু. তাই এখন আমি এখনও স্থান বাইরে থাকি, তাই একই সমস্যা আগের মতোই. কিন্তু আপনি কিভাবে এখন দেখতে পারেন আপনার কোড, আপনি সম্ভবত আরো একটু লিখতে হবে জটিলতা যে ঘটতে. এবং সত্য, তা অপারেটর সি সম্ভবত দেয় আপনি magically এই গোলাকার না? হ্যা মডুলো অপারেটর, সাইন শতাংশ. সুতরাং একজন কিউ সম্পর্কে শীতল ধরনের কি, বাসায় ফিরে ড্রইং অ্যারে রাখতে যদিও এই মত সোজা লাইন হিসাবে, আপনি যদি ধরনের কুঁচন হিসেবে এই সম্পর্কে চিন্তা চারপাশে একটি বৃত্ত হিসাবে, তারপর শুধু intuitively, এটা কোন ধরনের মানসিকভাবে কাজ আমি আরো পরিচ্ছন্নভাবে একটু চিন্তা. আপনি এখনও বাস্তবায়ন করতে হবে কোড যে মানসিক মডেল. তাই না যে কঠিন, পরিণামে, বাস্তবায়ন কিন্তু আমরা এখনও বরং, size-- হারান আমরা যদি এমন ব্যবস্থা না ক্ষমতা, মাপ পরিবর্তন করতে. 

আমরা অ্যারে পরিত্রাণ পেতে আছে, আমরা একটি একক পয়েন্টার সঙ্গে এটি প্রতিস্থাপন, এবং তারপর কোথাও আমার কোড আমি পেয়েছেন একটি আসলে তৈরি করতে কাজ কি কল অ্যারে নামক সংখ্যার? Malloc, বা কিছু অনুরূপ ফাংশন, ঠিক. Stacks বা সারির উপর কোন প্রশ্ন. হ্যা? ভালো প্রশ্ন. কি modulo আপনি এখানে ব্যবহার করবেন. তাই সাধারণত, ব্যবহার করার সময় মুড, আপনি এটা করতে হবে মাপ সঙ্গে পুরো ডাটা স্ট্রাকচার. তাই কিছু পাঁচ বা ক্ষমতা, তাহলে ভালো এটা ধ্রুব এর, সম্ভবত জড়িত হয়. কিন্তু শুধু মডুলো পাঁচটি করছেন সম্ভবত, যথেষ্ট নয় আমরা জানা প্রয়োজন, কারণ আমরা না এখানে অথবা এখানে অথবা এখানে চারপাশে মোড়ানো. সুতরাং আপনি সম্ভবত এছাড়াও আছেন চাই জড়িত যাচ্ছে জিনিস মাপ, অথবা পাশাপাশি সামনে পরিবর্তনশীল. তাই এটা শুধু এই অপেক্ষাকৃত এর সহজ গাণিতিক এক্সপ্রেশন, কিন্তু মডুলো মূল উপাদান হতে হবে. 

তাই সংক্ষিপ্ত ফিল্ম, যদি আপনি হবে. একটি অ্যানিমেশন যে কিছু অন্য বিশ্ববিদ্যালয়ে ভাবেন আমরা করেছি যে একত্রে এই আলোচনার জন্য অভিযোজিত. এটা জ্যাক শেখার জড়িত queues এবং পরিসংখ্যান সম্পর্কে তথ্য. 

চলচ্চিত্র: একবার একটি সময় উপর, জ্যাক নামে একটি লোক ছিল. এটা বন্ধুদের তৈরীর যখন, জ্যাক একটি দক্ষতা আছে না. তাই জ্যাক সঙ্গে কথা বলতে গিয়েছিলাম সবচেয়ে জনপ্রিয় লোক সে জানত. তিনি লু গিয়েছিলাম এবং আমি কি করব, জিজ্ঞাসা? লু তার বন্ধু যে দেখেছি সত্যিই দুর্দশাগ্রস্ত ছিল. ওয়েল, সে শুধু, শুরু আপনি পরিহিত করছি কিভাবে দেখুন. যদি আপনার কোন কাপড় নেই একটি ভিন্ন চেহারা সঙ্গে? হ্যাঁ, জ্যাক বলেন. আমি অবশ্যই করি. আমার বাড়িতে আসা এবং আমি আপনাকে তাদের দেখাব. সুতরাং তারা জ্যাক এর গিয়েছিলাম বন্ধ. আর জ্যাক লু বক্সে দেখিয়েছেন যেখানে তিনি সব তার শার্ট রাখা এবং তার প্যান্ট, এবং তার মোজা. লু আমি আপনি দেখতে পাচ্ছি একটি গাদা সব জামাকাপড়. কেন আপনি কিছু পরেন না অল্প সময়ের মধ্যে একবার অন্যদের? 

জ্যাক বলেন, ভাল, যখন আমি , কাপড় ও মোজা অপসারণ আমি তাদের ধোয়া এবং করা তাদের দূরে বক্সে. তারপর পরের আসে সকালে, এবং আপ আমি প্রস্থান. আমি বক্সে যান এবং পেতে শীর্ষ বন্ধ আমার জামাকাপড়. লু দ্রুত উপলব্ধি জ্যাক সঙ্গে সমস্যা. তিনি, বস্ত্র, সিডি এর রাখা এবং স্ট্যাকের মধ্যে বই. তিনি পৌঁছেছেন কিছু পড়তে বা পরতে, তিনি উপরের বই বা আন্ডারওয়্যার নির্বাচন চাই. তারপর তিনি কখন দেওয়া হয়েছিল, তিনি ডান তা প্রতিহত করা হবে. এটি ফিরিয়ে স্ট্যাকের উপর, যেতে হবে. আমি সমাধান জানেন, একটি জয়যুক্ত অট্ট বলেন. আপনি শিখতে হবে একটি কিউ ব্যবহার শুরু. লু জ্যাক এর কাপড়-চোপড় নিয়ে এবং পায়খানা তাদের হ্যাঙ. তখন তিনি emptied ছিল যখন বক্স, তিনি শুধু এটি ক্ষতিগ্রস্থ. 

তারপর তিনি জ্যাক শেষে, এখন, বলেন প্রতিদিন, বাম আপনার জামাকাপড় করা আপনি তাদের দূরে রাখা হলে. তারপর কাল সকালে যখন আপনি আপনার কাপড় পেতে, রৌদ্র দেখতে লাইনের শেষে থেকে ডান, উপর. আপনি দেখতে পাচ্ছেন না? লু বলেন. এটা এত সুন্দর হতে হবে. আপনি একবার সবকিছু পরিধান করব আগে আপনি দুইবার কিছু পরতে. এবং সারির মধ্যে সবকিছু তার পায়খানা এবং বালুচর, জ্যাক অনুভব করতে শুরু নিজেকে পুরোপুরি নিশ্চিত. লু সব ধন্যবাদ এবং তাঁর চমৎকার কিউ. বক্তা 1: ঠিক আছে, এটি আরাধ্য. সত্যিই তাই যাওয়া হয়েছে তা এখন ফণা নীচে? আমরা পয়েন্টার আছে, আমরা malloc আছে, আমরা তৈরি করার ক্ষমতা আছে নিজেদের জন্য মেমরি অংশ পরিবর্তনশীল. সুতরাং এই একটি ছবি আমরা হয় শুধু অন্যান্য দিন glimpsed. আমরা সত্যিই বাস করা হয়নি এটা, কিন্তু এই ছবি নীচে আছে যাওয়া হয়েছে এখন সপ্তাহের জন্য হুড. এবং সে জন্য এই প্রতিনিধিত্ব আমরা টানা করেছি যে একটি আয়তক্ষেত্র, আপনার কম্পিউটার এর মেমরি. এবং হয়ত আপনার কম্পিউটার, বা CS50 আইডি, মেমরি বা র্যাম একটি গিগাবাইট আছে অথবা দুই গিগাবাইট বা চার. এটা কোন ব্যাপার না. আপনার অপারেটিং সিস্টেম উইন্ডোজ বা ম্যাক OS বা লিনাক্স, মূলত আপনার প্রোগ্রামকে এটা এক্সেস আছে মনে সম্পূর্ণতা যাও আপনার কম্পিউটার এর মেমরি, এমনকি আপনি চলমান হতে পারে, যদিও একযোগে একাধিক প্রোগ্রাম. তাই বাস্তবে, যে সত্যিই কাজ করে না. কিন্তু এটা মায়া ধরনের আপনার প্রোগ্রামের সব দেওয়া. তাই আপনি যদি এই RAM- র দুটি যোগাড় ছিল কম্পিউটার এটা মনে হতে পারে কিভাবে হয়. 

এখন, কাকতালীয়ভাবে এই এক কিছু স্মৃতি এই খন্ডের এক, একটি স্ট্যাক বলা হয়. এবং প্রকৃতপক্ষে যে কোনো সময় এ পর্যন্ত লেখা কোড আপনি বলা আছে যে একজন উদাহরণস্বরূপ প্রধান জন্য ফাংশন. কোন সময় আমি করেছি যে প্রত্যাহার টানা কম্পিউটার এর মেমরি, আমি সবসময় ধরণের আঁকা এখানে একটি আয়তাকার অর্ধেক এবং কথা বলা মাথা ঘামান না উপরে কি সম্পর্কে. প্রধান ডাকা হয়, যখন আমি দাবি কারণ আপনি মেমরি এই কাঠের ছিলকা পেতে যে যে এখানে নিচে চলে যায়. প্রধান যদি একটি ফাংশন বলা swap 'র মত, ভাল অদল-বদলের কাজটি এখানে যায়. আর তা যে, দেখা যাচ্ছে যেখানে এটা শেষ পর্যন্ত হচ্ছে. একটি স্ট্যাক কিছু বলা উপর আপনার কম্পিউটার এর মেমরি ভিতরে. এখন দিনের শেষে, এই মাত্র ঠিকানাগুলি হয়. এটা, বাইট শূন্য মত বাইট এক বাইট 2 বিলিয়ন. কিন্তু আপনি এটি সম্পর্কে চিন্তা এই আয়তক্ষেত্রাকার বস্তুর হিসাবে, সব আমরা ভাষার করছেন সময় আমরা একটি ফাংশন কল মেমরি নতুন ছে layering. আমরা একটি ফালি যে ফাংশন প্রদান করছি নিজস্ব মেমরি সঙ্গে কাজ করতে. 

এবং এই গুরুত্বপূর্ণ যে এখন প্রত্যাহার. আমরা আছে না কারণ যদি swap 'র মত কিছু A এবং B এবং মত ও দুটি স্থানীয় ভেরিয়েবল আমরা এক ও দুই থেকে সেই মান পরিবর্তন দুই ও এক পুনরাহ্বান অদল-বদল ফেরৎ যখন যে, এটা এই ছে হিসাবে যদিও এর মেমরি ধ্বংস হয়ে গিয়েছে. বাস্তবে, এটা এখনও সেখানে forensically. আর কিছু আসলে এখনও আছে. কিন্তু ধারণার, এটা যেমন এর যদিও এটি সম্পূর্ণরূপে চলে গেছে. তাই প্রধান কাজ কোন না জানি যে, যে swap 'র ফাংশন মধ্যে সম্পন্ন করা হয় এটা আসলে যারা এর মধ্যে পাস তবে পয়েন্টার দ্বারা বা রেফারেন্স দ্বারা আর্গুমেন্ট. এখন, মৌলিক সমাধান swap 'র সঙ্গে যে সমস্যা অঙ্ক দ্বারা অনেক কিছু ক্ষণস্থায়ী হয়. কিন্তু এটা খুব, কি, দেখা যাচ্ছে যে অংশ উপরে যাওয়া হয়েছে আয়তাকার সব এই সময় এখনো আরো মেমরি আছে আছে. আর যখন আপনি পরিবর্তনশীল মেমরি বরাদ্দ, এটা কি GetString, ভেতরে কিনা যা আমরা CS50 মধ্যে আপনার জন্য কাজ করছি গ্রন্থাগার, অথবা আপনাকে বলছি যদি malloc কল এবং জিজ্ঞাসা একটি খণ্ড জন্য অপারেটিং সিস্টেম মেমরি, এটি স্ট্যাক থেকে আসে না. অন্য এক জায়গায় থেকে আসে আপনার কম্পিউটার এর মেমরি যে গাদা বলা হচ্ছে. আর যে কোন আলাদা না. এটা একই RAM- র. এটা একই মেমরি. এটা আপ যে RAM- র সেখানে পরিবর্তে নিচে এখানে. 

আর তাই যে কি মানে? ওয়েল, আপনার কম্পিউটার হয়েছে থাকে মেমরি একটি নির্দিষ্ট পরিমাণ এবং স্ট্যাকের তাই, উদ্ভিন্ন হয় কথা বলতে, এবং গাদা, অনুযায়ী এই তীর, নিচে ক্রমবর্ধমান হয়. অন্য কথায়, যে সময় আপনি malloc কল, আপনি একটি ফালি দেওয়া হচ্ছে মেমরি উপরে থেকে, একটু পরে, নিম্ন তারপর হয়তো একটু কম, আপনি malloc কল প্রতিটি সময়, গাদা, এটা ব্যবহার আছে, ধরনের ক্রমবর্ধমান হয়, কি কাছাকাছি এবং কাছাকাছি ক্রমবর্ধমান? স্ট্যাক. সুতরাং এই একটি ভাল ধারণা ভালো মনে হচ্ছে না? এটা সত্যিই পরিষ্কার না যেখানে আমি বলতে চাচ্ছি, আপনি কি কি আপনি শুধুমাত্র তাহলে কি করতে পারেন মেমরি একটি নির্দিষ্ট পরিমাণ আছে. কিন্তু এই নিশ্চয় খারাপ. যারা দুই তীর একটি হয় পরস্পরের প্রতি অবশ্যই বিপর্যস্ত. 

আর তা যে খারাপ লোক, যারা ভাবেন সক্রিয় আউট , প্রোগ্রামিং সঙ্গে বিশেষভাবে ভালো হয় এবং কম্পিউটারের মধ্যে হ্যাক করার চেষ্টা করুন, এই বাস্তবতা শোষণ করা যাবে. বস্তুত, এর বিবেচনা করা যাক সামান্য স্নিপেট. সুতরাং এই যে আপনি পড়তে পারেন একটি উদাহরণ সম্পর্কে উইকিপিডিয়ার আরো বিস্তারিতভাবে. আমরা এ নির্দেশ করব নিবন্ধটি যদি জানতে. কিন্তু আক্রমনের সাধারণত আছে বাফার ওভারফ্লো হিসাবে পরিচিত যে মানুষের যতদিন অস্তিত্ত্বকে করেনি নিপূণভাবে ক্ষমতা ছিল বিশেষ করে সি কম্পিউটার এর মেমরি, তাই এটি একটি খুব নির্বিচারে প্রোগ্রাম, কিন্তু এর নিচ থেকে এটা পড়া যাক. Argc গৃহস্থালি তারকা argv মধ্যে প্রধান. তাই এটি লাগে একটি প্রোগ্রাম কমান্ড লাইন আর্গুমেন্ট. এবং সব প্রধান দৃশ্যত কল করে একটি ফাংশন, সরলতা জন্য F কল. আর এটা কি পাস? এক argv. সুতরাং এটা এফ মধ্যে পাস যাই হোক না কেন শব্দ ব্যবহারকারী টাইপ করা যে হয় পরে প্রম্পটে প্রোগ্রাম এর নাম এ সব. এত সিজার বা Vigenere, মত যা আপনি argv সাথে করছেন প্রত্যাহার করা হতে পারে. 

তাই ফল কি? এফ একটি স্ট্রিং লাগে তার একমাত্র যুক্তি হিসাবে, ওরফে একটি গৃহস্থালি তারকা, একই জিনিস, পংক্তিরূপে উল্লিখিত হয়. এবং এটা ইচ্ছামত বলা হচ্ছে এই উদাহরণে বার. এবং তারপর গৃহস্থালির সি 12, ঠিক সাধারণ লোক এর ভাষায় বলতে গেলে, আমাদের জন্য করছেন গৃহস্থালি গ বন্ধনী 12 কি? কি এটা? বিশেষভাবে, মেমরি বণ্টন 12 অক্ষর জন্য 12 বাইট. ঠিক. এবং তারপর শেষ লাইন, এবং আলোড়ন কপি, আপনি সম্ভবত দেখা যায় না করেছি. এটি একটি স্ট্রিং অনুলিপি জীবনে যার উদ্দেশ্য ফাংশন তার দ্বিতীয় যুক্তি কপি করা তার প্রথম আর্গুমেন্ট মধ্যে, কিন্তু শুধুমাত্র একটি আপ বাইট নির্দিষ্ট সংখ্যক. তাই তৃতীয় যুক্তি, বলেছেন আপনি কত বাইট কপি করা উচিত? বার দৈর্ঘ্য, যাই হোক না কেন টাইপ ব্যবহারকারী. এর এবং বিষয়বস্তু হয়, যে স্ট্রিং বার মেমরিতে কপি সি এ এ তীক্ষ্ন 

সুতরাং এই ধরনের মূঢ় মনে, এবং তা হয়ে যায়. এটি একটি কল্পিত উদাহরণ, কিন্তু এটা প্রতিনিধি আক্রমণ ভেক্টর একটি বর্গ, একটি প্রোগ্রাম আক্রমণ একটি উপায়. সমস্ত জরিমানা এবং ব্যবহারকারী যদি ভাল হয় 11 অক্ষর যে একটি শব্দ ধরনের কম, প্লাস ব্যাকস্ল্যাশ শূন্য বা. কি আর ব্যবহারকারী ধরনের আরো যদি 11 বা 12 বা 20 বা 50 অক্ষর? কাজ করতে যাচ্ছেন এই প্রোগ্রাম কি? সম্ভাব্য seg দোষ. এটা যাচ্ছে অন্ধভাবে আপ বারে সবকিছু কপি করার যা তার দৈর্ঘ্য, এর আক্ষরিক বারে সবকিছু, ঠিকানা মধ্যে সি কিন্তু সি এ তীক্ষ্ন শুধুমাত্র যাও preemptively 12 বাইট হিসাবে দেওয়া হয়েছে. কিন্তু কোন অতিরিক্ত বার করো. শর্ত যদি কোন নেই. এখানে চেক কোন ত্রুটি আছে. 

আর তাই এই প্রোগ্রাম কি কাজ করতে যাচ্ছেন অন্ধভাবে হয় অন্য এক জিনিস কপি. আর তাই আমরা এই আঁকা তাহলে একটি ছবি হিসাবে, এখানে মেমরি স্পেস শুধু একটি কাঠের ছিলকা. সুতরাং আমরা নিচের দিকে লক্ষ্য স্থানীয় পরিবর্তনশীল বার আছে. স্টোরে যাচ্ছে যে পয়েন্টার তাই যে যে স্থানীয় যুক্তি বরং স্ট্রিং বার সংরক্ষণ করে যাচ্ছে. এবং তারপর মাত্র লক্ষ্য এটা উপরে একটি স্ট্যাকের মধ্যে, কারণ আপনার জিজ্ঞাসা প্রতি সময় স্ট্যাক মেমরি জন্য, এটি একটি সামান্য বিট যায় pictorially এটা উপরে, আমরা এখন পর্যন্ত 12 বাইট পেয়েছেন যে নোটিশ. উপরের বাম এক সি বন্ধনী শূন্য এবং হয় নীচের অংশে ডানদিকে এক সি বন্ধনী 11. শুধু কিভাবে কম্পিউটারের কী এটা খুঁজে রাখা যাচ্ছে. সুতরাং শুধুমাত্র intuitively বার আরও আছে যদি সহ মোট 12 টি অক্ষর, চেয়ে যেখানে ব্যাকস্ল্যাশ শূন্য, 12 বা সি বন্ধনী 12 যেতে যাচ্ছে? বরং বা যেখানে 12th হয় অক্ষর বা 13 অক্ষর, যাচ্ছে শততম চরিত্র ছবি আপ করা শেষ করতে? উপরে বা নীচে? 

রাইট, যদিও কারণ স্ট্যাকের নিজেই, ঊর্ধ্বাভিমুখী বৃদ্ধি আপনি কাপড় রেখেছি একবার এটা নকশা কারণে, উপর থেকে নীচ পর্যন্ত মেমরি রাখে. আপনি আরো বেশী 12 বাইট পেয়েছেন তাই, আপনি বার মুছে ফেলা শুরু করতে যাচ্ছেন. এখন যে একটি বাগ, কিন্তু এটা না সত্যিই একটি বড় চুক্তি. নেই, কারণ কিন্তু এটি একটি বড় চুক্তি, হয় মেমরি যাওয়া আরো স্টাফ. তাই এখানে কিভাবে আমরা প্রতাপ এর পরিষ্কার করা, হ্যালো করা. আমি প্রম্পটে হ্যালো টাইপ করা হলে. এইচ-ই-এল-এল-হে ব্যাকস্ল্যাশ শূন্য, মধ্যে শেষ পর্যন্ত যারা 12 বাইট, এবং আমরা সুপার নিরাপদ আছেন. সবকিছু ঠিক আছে. কিন্তু আমি কিছু টাইপ করুন আর, সম্ভাব্য এটা বার স্পেস মধ্যে হামাগুড়ি যাচ্ছে. কিন্তু এখনো খারাপ, এটি সক্রিয় সব এই সময় আউট, আমরা স্বপ্ন করেছি, এমনকি যদিও এটি স্ট্যাক অন্যান্য উপাদান ব্যবহার করা হয়. এটা শুধু স্থানীয় ভেরিয়েবল না. 

সি একটি অত্যন্ত নিম্ন স্তরের ভাষা. এবং এটি ধরণের গোপনে এছাড়াও স্ট্যাক ব্যবহার যখন মনে রাখবেন একটি ফাংশন, তা বলা হয় অঙ্ক, আগের ফাংশন হয় তাই এটি ফিরে যে ফাংশন ঝাঁপ পারেন. তাই প্রধান কল মধ্যে, অদলবদল যখন জিনিষ স্ট্যাকের মধ্যে push করা শুধু, স্থানীয় ভেরিয়েবল বিনিময়সমূহ না বা তার আর্গুমেন্ট, গোপনে ধাক্কা স্ট্যাকের মধ্যে প্রতিনিধিত্ব হিসেবে এখানে লাল ফালি করে, মূল ঠিকানা শারীরিকভাবে হয় আপনার কম্পিউটার এর মেমরি, যাতে অদল-বদলের কাজটি করা সম্ভব হলে, কম্পিউটার আমি প্রধান ফিরে যেতে হবে জানে এবং প্রধান ফাংশন নির্বাহ শেষ. তাই এই, এখন বিপজ্জনক কারণ যদি হ্যালো চেয়ে ভাল আরো ব্যবহারকারী ধরনের, ব্যবহারকারীর ইনপুট clobbers যে যেমন অথবা, যে লাল অধ্যায় মুছে ফেলা হয় কথাটি যদি কম্পিউটার এর অন্ধভাবে অনুমান করা যাচ্ছে যে লাল ছে বাইট হয় এটি ফেরত পাঠাবেন যা করার ঠিকানা, বিপক্ষ কি তাহলে যথেষ্ট স্মার্ট বা বাইটের একটি ক্রম করা যথেষ্ট ভাগ্যবান সেখানে একটি ঠিকানা মত দেখায় যে, কিন্তু এটি কোড এর ঠিকানা সে কম্পিউটার চায় পরিবর্তে প্রধান চালানো? 

অন্য কথায়, কি তাহলে ব্যবহারকারী প্রম্পটে টাইপ করা হয় শুধু কিছু নয় হ্যালো, নির্দোষ মত কিন্তু এটা সমতুল্য যে কোড আসলে সব এই ব্যবহারকারীর ফাইল মুছে দিতে পারবো? অথবা আমাকে তাদের পাসওয়ার্ড ইমেইল? অথবা লগ ইন শুরু তাদের কি-স্ট্রোক, ডান? একটা উপায় আছে, এর আজ চুক্তির শর্ত দেওয়া তারা হ্যালো না শুধু টাইপ করতে পারে যে বিশ্বের বা তাদের নাম, তারা মূলত পারা কোড, শূন্য পাস এবং বেশী, যে কম্পিউটার কোড এবং একটি ঠিকানা উভয় জন্য ভুল. যদ্যপি তাই কিছুটা বলিবেন, তাহলে যথেষ্ট adversarial কোড ব্যবহারকারী ধরনের আমরা এখানে যেমন সাধারণের বোধগম্য হবে যে উ: একটি আক্রমণ বা প্রতিপক্ষ নয়. তাই শুধু খারাপ জিনিস. আমরা যত্নশীল না সংখ্যা বা শূন্য বা বেশী আজ, আপনি যেমন যে শেষ পর্যন্ত যে লাল অধ্যায় মুছে, বাইটের যে ক্রম লক্ষ্য. হে 835 সি শূন্য আট শূন্য. আর এখন এখানে উইকিপিডিয়ার নিবন্ধ হিসাবে আসলে আপনি এখন শুরু হলে, প্রস্তাব করা হয়েছে আপনার কম্পিউটার এর মধ্যে বাইট লেবেল মেমরি, উইকিপিডিয়া নিবন্ধ কি উপস্থাপক হয়, যে কি অঙ্ক যদি যে উপরের বাম বাইট 80 সি 0 3508 হয়. 

অন্য কথায়, খারাপ লোক হয় তাহলে তার কোড সঙ্গে যথেষ্ট স্মার্ট আসলে এখানে একটি সংখ্যা লাগাতে যে কোড ঠিকানায় অনুরূপ সে ইনজেকশনের কম্পিউটারের মধ্যে, আপনি কম্পিউটার রত পারেন কিছু করছেন মধ্যে. , ফাইল মুছে ইমেল কিছু আপনার ট্রাফিক আঘ্রাণ আক্ষরিক কিছু হতে পারে কম্পিউটারের মধ্যে ইনজেকশনের. আর তাই একটি বাফার ওভারফ্লো তার অন্তঃস্থলে আক্রমণ শুধু একটি স্টুপিড হয় একটি অ্যারের অগ্রাহ্য করে তার গণ্ডি চেক আছে কি না. এবং এই সুপার বিপজ্জনক কি এবং একই সাথে অতি শক্তিশালী সি আমরা প্রকৃতপক্ষে আছে না যে স্মৃতিতে যে কোন জায়গা থেকে এক্সেস. এটা আমাদের উপর নির্ভর করে, প্রোগ্রামার, যারা মূল কোড লিখুন কোনো অভিশাপ দৈর্ঘ্য বার আমরা সাধিত করছি যে অ্যারে. তাই পরিষ্কার করা, ফিক্স কি? আমরা এই ফিরে গুটানো কোড, আমি না থাকা উচিত ঠিক বার দৈর্ঘ্য পরিবর্তন, তা অন্য আমি চেক করা উচিত? আমি আর কী করতে কাজ করা উচিত সম্পূর্ণরূপে এই আক্রমণ প্রতিরোধ? আমি অন্ধভাবে বলতে চাই না আপনি হিসাবে অনেক বাইট কপি উচিত যে হিসাবে বার দৈর্ঘ্য হয়. আমি যেমন, কপি বলতে চাই হিসাবে অনেক বাইট বারে হয় বরাদ্দ আপ মেমরি, বা সর্বাধিক 12. তাই আমি শর্ত যদি কিছু প্রয়োজন যে বার দৈর্ঘ্য পরীক্ষা আছে, কিন্তু 12, আমরা শুধু হার্ড কোড অতিক্রম করে সর্বোচ্চ সম্ভব দূরত্ব হিসাবে 12. অন্যথা তথাকথিত বাফার ওভারফ্লো আক্রমণ ঘটতে পারে. যারা স্লাইড নীচে, আপনি আরো পড়তে জানতে আগ্রহী হন তাহলে প্রকৃত মূল নিবন্ধ আপনি দেখে নিতে চাই. 

কিন্তু এখন, দাম মধ্যে অকার্যকরই এখানে ছিল প্রদত্ত. সুতরাং যে একটি দ্রুত ছিল এ নিম্ন স্তর বর্ণন কি সমস্যা যে আমরা এখন দেখা দিতে পারে কম্পিউটার এর মেমরি এক্সেস আছে. কিন্তু সমস্যা অন্য জায়গায় আমরা ইতিমধ্যে সোমবার পদস্খলিত শুধু অদক্ষতা ছিল একটি লিঙ্ক তালিকা. আমরা ফিরে রৈখিক সময় হয়. আমরা আর একটি সংলগ্ন অ্যারে আছে. আমরা র্যান্ডম অ্যাক্সেস না থাকে. আমরা বর্গাকার বন্ধনী নোটেশন ব্যবহার করা যাবে না. আমরা আক্ষরিক যখন একটি লুপ ব্যবহার করতে হবে এক মত আমি একটি মুহূর্ত আগে লিখেছিলেন. কিন্তু সোমবার, আমরা যেতে পারে যে দাবি দক্ষতা অন্তর্জগৎ মধ্যে হামাগুড়ি কিছু যে অর্জন লগারিদমিক হয়তো, বা ভাল এখনো, যে এমনকি কিছু ধ্রুব সময় তথাকথিত. তাই আমরা এই নতুন ব্যবহার যে কত না পারেন সরঞ্জাম, এই ঠিকানাগুলি, এই পয়েন্টার, এবং আমাদের নিজস্ব কিছু থ্রেডিং? ওয়েল, আমি অনুমান যে এখানে, এই একটি গুচ্ছ আমরা একটি মধ্যে সংরক্ষণ করতে চান যে সংখ্যার দক্ষতার ডাটা স্ট্রাকচার ও অনুসন্ধান. আমরা একেবারে সপ্তাহে গুটিয়ে পারেন দুই, একটি অ্যারের মধ্যে এইসব নিক্ষেপ এবং বাইনারি অনুসন্ধান ব্যবহার তাদের অনুসন্ধান. ভাগ অতিক্রম করা. এবং আসলে আপনি লিখেছেন PSET3 বাইনারি অনুসন্ধান, যেখানে আপনি খুঁজে পেতে প্রোগ্রাম বাস্তবায়ন. কিন্তু আপনি কি জানেন. আরো কয়েক ধরনের আছে এই কাজ করার চতুর উপায়. এটা একটা সামান্য আরো অত্যাধুনিক এবং এটি সম্ভবত আমাদের কেন বাইনারি দেখতে পারবেন অনুসন্ধান অনেক দ্রুত, তাই হয়. প্রথমত, এর পরিচয় করিয়ে দেওয়া একটি বৃক্ষ এর ধারণা. যা এমনকি যদিও বাস্তবতা গাছ ধরনের কম্পিউটার জগতে, এই মত বাড়া তারা ধরনের নিম্নগামী বাড়া বিজ্ঞান আপনি যেখানে একটি পরিবার গাছ, মত আপনার নানীরা বা মহান grandparents বা যে কোন বস্তু উপরের কুলপতি এ ও পরিবারের মা ও কর্ত্রী, মাত্র এক রুট, নোড, নীচের তথাকথিত তার সন্তানদের যা হয়, যা নিচে তার সন্তান, অথবা তার বংশধরদের আরো সাধারণভাবে. আর কেউ বন্ধ ঝুলন্ত পরিবারের নীচে বৃক্ষ, ছাড়াও পরিবারের কনিষ্ঠ, এছাড়াও শুধু জেনেরিক হতে পারে বৃক্ষের পাতা বলা. 

সুতরাং এই মাত্র একটি গুচ্ছ হয় শব্দ এবং সংজ্ঞা কিছু কম্পিউটার একটি গাছ বলা বিজ্ঞান, একটি পরিবার গাছ মত অনেক. কিন্তু কল্পনাকারী সমগ্র আদর্শের আছে গাছ, যার মধ্যে একটি বাইনারি অনুসন্ধান বৃক্ষ বলা হয়. এবং আপনি পারেন আঁচড়ান ধরনের এই জিনিস সরাইয়া কি. ওয়েল, এটা কোন অর্থে বাইনারি? যেখানে বাইনারি এখানে কোথা থেকে এসেছে? দুঃখিত? এটা এত একটি হয় বা না. এটা নোড প্রতিটি কোন হয়েছে আরো দুটির বেশি সন্তান থাকলে, আমরা এখানে দেখতে হিসেবে. সাধারণ, একটি ট্রি যাও এবং আপনার বাবা এবং grandparents অনেক বাচ্চাদের থাকতে পারে বা নাতিনাতনির তারা আসলে চান হিসাবে, এবং তাই উদাহরণস্বরূপ সেখানে আমরা তিন আছে ডানহাতে ওটা নোডের বন্ধ শিশুদের, কিন্তু একটি বাইনারি ট্রি, একটি নোড আছে সর্বাধিক শূন্য, এক, দুই বা শিশু. আর যে, একটা চমৎকার সম্পত্তি দুজন লাভের কারণ যদি, আমরা সক্ষম হতে যাচ্ছেন একটু লগ বেস পেতে দুই কর্ম এখানে শেষ পর্যন্ত যাওয়া. সুতরাং আমরা লগারিদমিক কিছু আছে. কিন্তু একটি মুহূর্ত যে আরো. অনুসন্ধান বৃক্ষ সংখ্যার মানে হল যে ব্যবস্থা যেমন যে বাম সন্তানের মূল্য রুট তার চেয়ে অনেক বেশী. এবং তার ডান সন্তানের হয় রুট চেয়ে বড়. অন্য কথায়, আপনি কোনো নিতে হলে নোড, এই ছবিতে বৃত্ত, এবং তার বাম দিকে তাকায় শিশু ও তার ডান সন্তান, প্রথমত, এর চেয়ে কম হওয়া উচিত দ্বিতীয় তার চেয়ে অনেক বেশী হওয়া উচিত. সুতরাং বৈধতা 55 বার. এটা সন্তানের বাম এর 33 হয়. এর চেয়ে কম. 55, তার অধিকার বাচ্চাকে 77. এটা তার চেয়ে অনেক বেশী. এবং যে একটি রিকার্সিভ সংজ্ঞা. আমরা যারা প্রতি এক পরীক্ষা পারে নোড এবং রাখা হবে একই প্যাটার্ন. 

সুতরাং একটি চমৎকার কি বাইনারি অনুসন্ধান বৃক্ষ, হয় যে এক, আমরা তা বাস্তবায়ন করতে পারেন একটি struct সঙ্গে, শুধু ভালো. আর আমরা নিক্ষেপ করছি যদিও আপনার এ স্ট্রাকচার অনেক, তারা কিছুটা আছেন স্বজ্ঞাত এখন আশা. সিনট্যাক্স, এখনও নিশ্চিত করার জন্য গোপনীয় হয় কিন্তু এই একটি নোড বিষয়বস্তু context-- এবং আমরা রাখতে শব্দ নোড ব্যবহার করে, এটি একটি আয়তক্ষেত্র কিনা পর্দা বা বৃত্তের উপর, এটি শুধু কিছু জেনেরিক ধারক এক মত একটি গাছের এই ক্ষেত্রে, এ আমরা একটি পূর্ণসংখ্যা প্রয়োজন, দেখেছি নোড প্রত্যেকটি এবং তারপর আমি দুই পয়েন্টার প্রতি নির্দেশ প্রয়োজন বাম শিশু এবং অধিকার সন্তানের, যথাক্রমে. সুতরাং এটা কিভাবে আমরা প্রতাপ একটি struct যে বাস্তবায়ন. এবং কিভাবে আমি কোড তা বাস্তবায়ন হতে পারে? ওয়েল, এর একটি দ্রুত নিতে দিন এই ক্ষুদ্র উদাহরণ তাকান. এটা কার্যকরী নয়, কিন্তু আমি করেছি কপি এবং যে কাঠামো আটকানো. আর যদি একটি বাইনারি জন্য আমার ফাংশন অনুসন্ধান বৃক্ষ, অনুসন্ধান বলা হয় এবং এই দুটি আর্গুমেন্ট লাগে, একটি পূর্ণসংখ্যা এন এবং একটি পয়েন্টার গাছ থেকে একটি নোড, তাই একটি পয়েন্টার বা গাছের শিকড় এর একটি পয়েন্টার, কিভাবে আমি এন অনুসন্ধানের সম্পর্কে যান? আচ্ছা, প্রথম, আমি নই, কারণ পয়েন্টার সাথে ডিল, আমি একটি মানসিক সুস্থতা চেক করতে যাচ্ছি. বৃক্ষ সমান সমান নাল তাহলে, এন হয় এই বৃক্ষ অথবা না এই গাছ? এটা ঠিক আছে, হতে পারে না? আমি নাল গত থাকি যদি, সেখানে কিছুই নেই. আমি বল হিসাবে ভাল শুধু অন্ধভাবে মিথ্যা ফিরে বলে. আপনি আমাকে কিছুই দিতে হও, আমি অবশ্যই না করতে পারেন কোন সংখ্যা এন এটি অন্য তাই আমি বল এখন দেখ? আমি ভাল অন্য এন হয় তাহলে বলতে যাচ্ছি বৃক্ষ নোড যাই হোক না কেন কম আমি এন মূল্য হস্তান্তর করে থাকেন যে. অন্য কথায়, সংখ্যা আমি যদি এন, খুঁজছেন, নোড কম হয় আমি দেখছি যে. এবং নোড আমি থাকবো গাছ বলা হয় এ, এবং আগের উদাহরণ থেকে প্রত্যাহার একটি পয়েন্টার মধ্যে মান পেতে, আমি তীর স্বরলিপি ব্যবহার. এন বৃক্ষ তীর কম হলে তাই এন, আমি ধারণার বাম যেতে চান. আমি কিভাবে বাম অনুসন্ধানও এক্সপ্রেস না? এই যদি, পরিষ্কার করা প্রশ্নে ছবি, এবং আমি পাশ করে থাকেন আগ যে নিচে যে ইশারা তীর. যে আমার বৃক্ষ পয়েন্টার. আমি গাছের শিকড় এ ইশারা করছি. আর আমি, বলে থাকবো ইচ্ছামত সংখ্যা 44. তুলনায় 44 কম বা স্পষ্টত 55 তার চেয়ে অনেক বেশী? তাই এর চেয়ে কম. আর তাই এই যদি অবস্থা প্রযোজ্য. তাই ধারণার, আমি কি চাই না আমি 44 খুঁজছি তাহলে পরের অনুসন্ধান? হ্যা? 

ঠিক, আমি চাই বাম সন্তানের অনুসন্ধান, বা এই ছবি বাম সাব-ট্রি. এবং সত্য, আমাকে যেতে দাও নিচে এখানে ছবি মাত্র কয়েক মিনিটের জন্য, যেহেতু আমি এই আউট স্ক্র্যাচ পারবেন না. আমি 55 এ এখানে শুরু, এবং যদি আমি জানি যে মূল্য 44 করার জন্য আমি থাকবো বাম, এটা ধরনের এর মধ্যে ফোন বই বিচ্ছিন্নকরণ মত অর্ধেক বা অর্ধেক গাছ বিচ্ছিন্নকরণ. আমি আর যত্নের আছে বৃক্ষ এই সমগ্র অর্ধেক. এবং এখনো অদ্ভুতভাবে শর্তাবলী কাঠামো, এখানে যে ধরে এই জিনিস 33 দিয়ে শুরু হয় নিজেই যে একটি বাইনারি অনুসন্ধান বৃক্ষ. আমি কারণ আগে শব্দ রিকার্সিভ বলেন প্রকৃতপক্ষে এটি একটি ডাটা স্ট্রাকচার যে সংজ্ঞা দ্বারা রিকার্সিভ হয়. আপনি কি এই যে একটি বৃক্ষ থাকতে পারে বড়, কিন্তু তার সন্তানদের প্রতি এক ছোট অল্পমাত্র একটি বৃক্ষ প্রতিনিধিত্ব করে. এর পরিবর্তে এটি এর দাদু হচ্ছে বা নানী, এখন এটি শুধু মায়ের or-- আমি মায়ের না কথাই পারবেন না অথবা বাবা, যে অদ্ভুত হবে. পরিবর্তে দুই শিশু ভাই এবং সহোদর মত হবে. পরিবারের গাছ একটি নতুন প্রজন্মের. কিন্তু গঠনের এটা একই ধারণা. এবং এটা আমি একটি ফাংশন আছে দেখা যাচ্ছে যা দিয়ে আমি একটি বাইনারি অনুসন্ধান অনুসন্ধান করতে পারেন বৃক্ষ. এটা অনুসন্ধান বলা হয়. আমি বৃক্ষ তীর বাম n জন্য অনুসন্ধান এন চেয়ে বেশী অন্যথায় যদি যে আমি বর্তমানে আছি. একটি মুহূর্ত আগে গল্পের 55. আমি নামক একটি ফাংশন আছে অনুসন্ধান যে আমি ঠিক করতে পারেন এন এই পাস এবং পৌনঃপুনিকভাবে অনুসন্ধান সাব-ট্রি ও ঠিক ফিরে যাই হোক না কেন যে উত্তরটি. অন্যথায় আমি এখানে কিছু চূড়ান্ত বেস কেস পেয়েছেন. 

চূড়ান্ত ক্ষেত্রে কি? বৃক্ষ হয় নাল. আমি হয় খুঁজছি মান যে বেশী তা কম বা তার অধিক অথবা এটা সমান. আর আমি সমান বলতে পারে সমান, কিন্তু কথাটি এটা শুধু এখানে অন্য বলছে সমতূল্য. সুতরাং সত্য আমি কিছু খুঁজে কিভাবে হয়. তাই আশা করছি এই একটি হল এমনকি আরো আকর্ষক উদাহরণস্বরূপ মূঢ় সিগমা ফাংশন তুলনায় আমরা ফিরে কয়েকটি বক্তৃতা করেনি যেখানে এটি একটি লুপ ব্যবহার ঠিক যেমন সহজ ছিল এক থেকে সমস্ত সংখ্যা গণনা একটি ডাটা স্ট্রাকচার সাথে এখানে এন করার নিজেই পৌনঃপুনিকভাবে যে আমরা এখন, সংজ্ঞায়িত এবং পৌনঃপুনিকভাবে টানা নিজেদের প্রকাশ করার ক্ষমতা আছে কোড নিজেই রিকার্সিভ যে. তাই এই এখানে সঠিক একই কোড. 

তাই আমরা কি অন্যান্য সমস্যার সমাধান করতে পারে? দূরে থেকে তাই একটি দ্রুত পদক্ষেপ মাত্র কয়েক মিনিটের জন্য গাছ. এখানে, জার্মান পতাকা বলতে. এবং পরিষ্কারভাবে আছে একটি এই পতাকা প্যাটার্ন. আর প্রচুর আছে বিশ্বের পতাকা যে পরিপ্রেক্ষিতে এই হিসাবে হিসাবে সহজ হয় তাদের রং এবং নকশার. কিন্তু এই একটি হিসেবে সংরক্ষণ করা হয় যে অনুমান .GIF, বা কোন JPEG, বা বিটম্যাপ, বা পিং, কোনো গ্রাফিক্যাল ফাইল ফরম্যাট যা দিয়ে আপনি পরিচিত হন আমরা করছি যা কিছু Pset4 সঙ্গে বাজানো. এই দোকান থেকে লাভবানই বলে মনে হচ্ছে না কালো পিক্সেল, কালো পিক্সেল, কালো পিক্সেল, বিন্দু, বিন্দু, বিন্দু, আভা প্রথম scanline জন্য কালো পিক্সেল, বা সারি, তারপর আভা একই, তারপর আভা তারপর একই, এবং লাল পিক্সেল আভা, লাল পিক্সেল, লাল পিক্সেল, তারপর একটি সম্পূর্ণ হলুদ হলুদ পিক্সেল গুচ্ছ, ডান? 

যেমন অদক্ষতা আছে এখানে. কিভাবে intuitively আপনি would জার্মান পতাকা কম্প্রেস একটি ফাইল হিসাবে এটি বাস্তবায়ন হলে? কি তথ্য মত আমরা না পারেন যাতে সংরক্ষণ করা ডিস্কের উপর বিরক্ত ভালো থেকে আমাদের ফাইলের আকার হ্রাস করা একটি কিলোবাইট, কিছু করার জন্য একটি দিন মেগাবাইটে ছোট? তথায় অতিরেক মিথ্যা এখানে স্পষ্ট করা? আপনি কী করতে পারেন? হ্যা? ঠিক. কেন না বরং মনে রাখবেন প্রতি অভিশাপ পিক্সেল রঙ শুধু আপনি pset4 করছেন মত বিটম্যাপ ফাইল ফরম্যাট সঙ্গে, কেন আপনি শুধু প্রতিনিধিত্ব করেন না উদাহরণস্বরূপ পিক্সেল একেবারে বামের কলামে, কালো পিক্সেল একটি গুচ্ছ, একটি গুচ্ছ লাল, হলুদ এবং একটি গুচ্ছ, এবং তারপর ঠিক একরকম সঙ্কেতাক্ষরে লিখা পুনরাবৃত্ত ধারণা এই 100 বার বা এই 1,000 বার পুনরাবৃত্তি? যেখানে 100 বা 1,000 শুধু একটি পূর্ণসংখ্যা, আপনি এ শুধু একটি একক সংখ্যা দিয়ে পার পেতে পারেন পরিবর্তে শত শত বা হাজার হাজার অতিরিক্ত পিক্সেল. এবং প্রকৃতপক্ষে, যে কিভাবে আমরা এর জার্মান পতাকা কম্প্রেস করতে পারে. এবং ফরাসি পতাকা সম্পর্কে এখন কি? কিছু ধরণের আর একটু মানসিক ব্যায়াম, যা পতাকা ডিস্কে আরও সংকুচিত করা যেতে পারে? জার্মান পতাকা বা ফরাসি পতাকা, আমরা যে অভিগমন? জার্মান পতাকা আছে, কারণ আরো অনুভূমিক অতিরেক. এবং নকশা দ্বারা অনেক গ্রাফিক্যাল ফাইল ফরম্যাটের প্রকৃতপক্ষে হিসাবে স্ক্যান লাইন কাজ না অনুভূমিকভাবে. তারা কাজ করতে পারে উল্লম্বভাবে, শুধু মানবতার সিদ্ধান্ত বছর আগে যে আমরা করব সাধারণত কিছু সারির মনে কলাম দ্বারা সারিতে পরিবর্তে কলাম দ্বারা. তাই প্রকৃতপক্ষে হলে ফাইল তাকান একটি জার্মান পতাকা এবং একটি ফরাসি আকার পতাকা, এতক্ষণ রেজল্যুশন হিসাবে একই, একই প্রস্থ এবং উচ্চতা, এই এক এখানে, বড় হতে যাচ্ছে আপনাকে কারণ নিজেকে তিনবার পুনরাবৃত্তি আছে. আপনি নীল, পুনরাবৃত্ত নির্দিষ্ট করা আছে নিজেকে, সাদা, লাল, নিজেকে পুনরাবৃত্তি নিজেকে পুনরাবৃত্তি. আপনি শুধু সব হয়ে যেতে পারে না ডান উপায়. এবং একটি সরাইয়া হিসাবে, করতে কম্প্রেশন পরিষ্কার এইসব হয় তাহলে, সর্বত্র হয় একটি video-- থেকে চার ফ্রেম আপনি একটি সিনেমা যে প্রত্যাহার করা হতে পারে অথবা ভিডিও সাধারণত হয় প্রতি সেকেন্ডে 29 বা 30 ফ্রেম মত. এটা একটা সামান্য উল্টানো বই মত যেখানে আপনি শুধু ইমেজ, ইমেজ, ইমেজ, ইমেজ দেখতে, ছবিটি শুধু সুপার ফাস্ট তাই এটা দেখে মনে হচ্ছে পর্দায় অভিনেতা চলন্ত হয়. এখানে একটি ভোমরা উপর ফুলের গুচ্ছ উপরের. এবং এটা কোন ধরনের হতে পারে, যদিও প্রথম নজরে দেখতে কঠিন, চলন্ত শুধু এই মুভি মৌমাছি. 

কী সংরক্ষণকারী সম্পর্কে বোবা ভিডিও uncompressed? এটা ভিডিও ধারণ করার জন্য একটি বর্জ্য ধরনের চার প্রায় অভিন্ন চিত্র হিসাবে যে শুধুমাত্র যতটা মৌমাছি যেখানে যেমন ভিন্ন. আপনি বর্জন করা যেতে পারে সবচেয়ে যে তথ্য এবং শুধুমাত্র মনে, উদাহরণস্বরূপ, প্রথম ফ্রেম ও শেষ ফ্রেম, আপনি করেছি তাহলে কী ফ্রেম কখনও, শব্দ শোনা এবং শুধু সঞ্চয় মৌমাছি যেখানে মাঝখানে. এবং যদি আপনি করতে হবে না , গোলাপী সব সঞ্চয় নীল, এবং এবং সবুজ মান হিসাবে ভাল. সুতরাং এই মাত্র যে বলতে হয় কম্প্রেশন সর্বত্র হয়. এটা আমরা প্রায়ই ব্যবহার একটি টেকনিক এই দিন হালকাভাবে বা নিতে. 

কিন্তু কিভাবে আপনি টেক্সট কম্প্রেস না? কিভাবে আপনি টেক্সট সংকুচিতকারী যেতে না? ওয়েল, প্রতিটি অক্ষরের মধ্যে ASCII এক বাইট, বা আট বিট. এবং যে ধরনের মূক, ঠিক? আপনি সম্ভবত একটি টাইপ কারণ এবং ই ও আমি এবং o, u অনেক আরো প্রায়ই ওয়াট বা প্রশ্ন বা Z মত চেয়ে, ভাষার উপর নির্ভর করে যা আপনি অবশ্যই লেখার. এবং তাই কেন আমরা ব্যবহার করছেন প্রতিটি অক্ষর এবং আট বিট, অন্তত সহ জনপ্রিয় অক্ষর, ডান? কেন কম বিট ব্যবহার করবেন সুপার জনপ্রিয় অক্ষর, ই ভালো, কিছু আপনি অনুমান প্রথম ফরচুন র চাকা, এবং এর জন্য আরো বিট ব্যবহার কম জনপ্রিয় অক্ষর? কেন? আমরা শুধু চলুন, কারণ কম ঘন ঘন তাদের ব্যবহার. 

ওয়েল, এটা আছে যে দেখা যাচ্ছে এই কাজ করতে প্রচেষ্টা হয়েছে. এবং যদি আপনি গ্রেড থেকে প্রত্যাহার হলে স্কুল বা উচ্চ বিদ্যালয়, জলহস্তী কোড. জলহস্তী কোড বিন্দু আছে এবং ড্যাশ হতে পারে একটি তারের হিসাবে বরাবর প্রেরণ করা শব্দ বা কিছু ধরণের সংকেত. কিন্তু জলহস্তী কোড একটি সুপার পরিষ্কার. এটা একটি বাইনারি সিস্টেম ধরনের যে আপনি বিন্দু বা ড্যাশ আছে. কিন্তু আপনি, উদাহরণস্বরূপ, দুটি বিন্দু দেখতে পারেন. অথবা আপনি অপারেটর ফিরে মনে করেন যারা, হুইসেল, হুইসেল, হুইসেল মত যায় হুইসেল, একটু ট্রিগার চাপার যে একটি সংকেত প্রেরণ করে, আপনি যদি, প্রাপক, দুটি পায় বিন্দু, কি বার্তা পেয়েছি? সম্পূর্ণ অবাধ. 

আমি? আমি? অথবা কি about-- বা আমি? হয়তো এটা শুধু দুটি ই এর সঠিক ছিল? তাই এই সমস্যা আছে জলহস্তী সঙ্গে decodability এর কোড, যদ্দ্বারা তবে আপনার বার্তা পাঠানোর ব্যক্তি আসলে তাই আপনাকে সাজাতে পারেন pauses দেখতে বা অক্ষর মধ্যে ফাঁক শুনতে, এটা শুধু যথেষ্ট নয় zeros এবং বেশী একটি স্ট্রিম পাঠান, বা বিন্দু এবং ড্যাশ, অস্পষ্টতা আছে, কারণ. ই একটি একক বিন্দু, তাই আপনি যদি দুটি বিন্দু দেখতে বা দুটি বিন্দুর শুনতে, হয়তো এটা দুই ই এর বা হয়তো এটা এক আই এর সুতরাং আমরা একটি যে একটি সিস্টেম প্রয়োজন যে বেশী চালাক সামান্য. সুতরাং একজন মানুষ নামক Huffman বছর আগে ঠিক এই নিয়ে এসেছেন. তাই আমরা ঠিক যাচ্ছেন এক ঝলকে নেওয়া কিভাবে এ গাছ এই সঙ্গত হয়. এই কিছু যে ধরুন আপনি পাঠাতে চান মূঢ় বার্তা, শুধু একটি, বি গঠিত, সি এর ডি 'র এবং এর ই, কিন্তু অতিরেক একটি অনেক আছে এখানে. এটা ইংরেজি হতে বোঝানো না. এটি এনক্রিপ্ট না. এটা স্রেফ একটি বার্তা পুনরাবৃত্তি প্রচুর সঙ্গে. আপনি আসলে গণনা হলে তাই সব একটি এর, বি এর, সি এর, D 'গুলি, এবং এর ই, এখানে ফ্রিকোয়েন্সি. অক্ষর 20% হয় ক-এর, অক্ষর 45% ই এর, এবং তিনটি অন্যান্য ফ্রিকোয়েন্সি হয়. আমরা নিজে সেখানে আপ গণনা এবং শুধু গণিত করেনি. 

সুতরাং দেখা যাচ্ছে যে, যাও Huffman, কিছু সময় আগে, আপনি জানেন, যে উপলব্ধি কি, আমি বিল্ডিং শুরু হলে একটি বৃক্ষ, বা গাছ বন, যদি আপনি হবে, নিম্নরূপ, আমি নিচের কাজগুলো করতে পারেন. আমি প্রতিটি একটি নোডের দিতে যাচ্ছি আমি যত্নশীল যে চিঠি এবং আমি দোকান থেকে যাচ্ছি যে নোড ভেতরে একটি ফ্লোটিং পয়েন্ট হিসাবে ফ্রিকোয়েন্সি মূল্য, অথবা আপনি খুব, একটি N এটি ব্যবহার করতে পারে কিন্তু আমরা শুধু এখানে একটি float ব্যবহার করব. এবং এলগরিদম যে তিনি আপনাকে যে প্রস্তাব একক নোড এই বন নেওয়া গাছ, তাই সুপার সংক্ষিপ্ত গাছ, এবং আপনার সাথে তাদের সংযোগ শুরু নতুন গ্রুপ, নতুন বাবা, যদি আপনি হবে. এবং যদি আপনি চয়ন করে এই কাজ একটি সময়ে দুটি ক্ষুদ্রতম ফ্রিকোয়েন্সি. তাই আমি 10% এবং 10% নেন. আমি একটি নতুন নোড নির্মাণ. আর আমি নতুন নোডের 20% কল. 

যা দুই নোড আমি পরের একত্রিত? এটা একটা সামান্য দ্ব্যর্থক এর. তাই কিছু কোণ ক্ষেত্রে আছে বিবেচনা, কিন্তু সুন্দর জিনিষ রাখতে, আমি 20% নিন যাচ্ছি - আমি এখন শিশুদের উপেক্ষা. আমি 20% নিন যাচ্ছি এবং 15% এবং দুটি নতুন প্রান্ত আঁকা. আর এখন যা দুটি নোড আমি যুক্তি একত্রিত না? সব শিশুদের, সব উপেক্ষা নাতি, শুধু শিকড় তাকান এখন. যা দুই নোড আমি একসাথে গিঁট না? পয়েন্ট দুটি এবং 0.35. তাই আমাকে দুটি নতুন প্রান্ত আঁকা যাক. এবং তারপর আমি শুধুমাত্র এক বাম পেয়েছেন. তাই এখানে একটি গাছ আছে. এবং এটি ইচ্ছাকৃতভাবে টানা হয়েছে ধরনের চমত্কার চেহারা, কিন্তু প্রান্ত আছে বিজ্ঞপ্তি শূন্য এবং এক লেবেল করা. সুতরাং বাম প্রান্ত সব শূন্য হয় ইচ্ছামত, কিন্তু ধারাবাহিকভাবে. সকল ডান প্রান্ত বেশী. 

আর তাই হফম্যান, হয় প্রস্তাবিত কি আপনি একটি বি প্রতিনিধিত্ব করতে চান, হিসাবে সংখ্যা 66 প্রতিনিধিত্ব বদলে আট সমগ্র বিট যা একটি ASCII, আপনি কি শুধু দোকান জানেন প্যাটার্ন শূন্য, শূন্য, শূন্য, শূন্য যে পথ, কারণ আমার বৃক্ষ থেকে, জনাব Huffman এর ট্রি, রুট থেকে পাতার. আপনি একটি সঞ্চয় করতে চান তাহলে ই, বৈসাদৃশ্য দ্বারা, না একটি ই প্রতিনিধিত্বকারী আট বিট পাঠান পরিবর্তে, বিট কি প্যাটার্ন পাঠাতে? এক. আর এই বিষয়ে চমৎকার কি যে ই সবচেয়ে জনপ্রিয় চিঠি, এবং আপনি ব্যবহার করছেন এটা জন্য কম কোড. পরবর্তী সবচেয়ে জনপ্রিয় চিঠি এটা দেখে মনে হচ্ছে উ ছিল এবং তাই কতগুলি বিট তিনি যে জন্য ব্যবহার উত্থাপন হয়নি? শূন্য, এক. 

আর এটা বাস্তবায়িত কারণ এই ট্রি হিসাবে, এখন জন্য আমার আছে চুক্তির শর্ত দেওয়া জলহস্তী হিসাবে কোন অস্পষ্টতা কোড, সব কারণ আপনি যত্নশীল অক্ষর এই প্রান্ত শেষে হয়. সুতরাং যে শুধু এক একটা গাছের আবেদন. এই হচ্ছে ÑÑ আমি তরঙ্গ করব এই সময়ে আমার হাতে কিভাবে আপনি একটি সি কাঠামো হিসেবে এই বাস্তবায়ন হতে পারে. আমরা শুধু একত্রিত করতে হবে প্রতীক, একটি গৃহস্থালি মত, এবং ফ্রিকোয়েন্সি বাম এবং ডান. কিন্তু এর দুই তাকান চূড়ান্ত উদাহরণ যে আপনি পাবেন পরে সঙ্গে বেশ পরিচিত পেতে সমস্যা ব্যঙ্গ শূন্য পাঁচটি সেট. 

তাই ডাটা স্ট্রাকচার নেই একটি হ্যাশ টেবিল হিসাবে পরিচিত. এবং একটি হ্যাশ টেবিল ধরনের হয় এটা বালতি আছে ঠান্ডা. আর চার buckets আছে অনুমান এখানে, মাত্র চার ফাঁকা স্পেস. এখানে হয় কার্ডের একটি ডেক, এবং ক্লাব, কোদাল, ক্লাব, ফুল, ক্লাব, হীরা, ক্লাব, ফুল, clubs-- তাই এই র্যান্ডম হয়. হৃদয়, hearts-- তাই আমি আছি এখানে ইনপুট সব bucketizing. এবং একটি হ্যাশ টেবিল চাহিদা আপনার ইনপুট তাকান, এবং তারপর একটি নির্দিষ্ট এটি করা আপনি দেখতে কি উপর ভিত্তি করে লিখুন. এটা একটি অ্যালগরিদম. আর আমি একটি সুপার ব্যবহার করা হয়েছিল সহজ চাক্ষুষ অ্যালগরিদম. যা hardest অংশ ছিল ছবি ছিল তা মনে. তারপর চার মোট জিনিষ আছে. 

এখন stacks এর, ক্রমবর্ধমান হয়, যা এখানে একটি ইচ্ছাকৃত নকশা জিনিস. কিন্তু আমি অন্য কি কি হতে পারে? তাই আসলে এখানে আমরা একটি পুরানো স্কুল পরীক্ষার বই গুচ্ছ. একটি গুচ্ছ যে ধরুন ছাত্র নাম এখানে আছে. এখানে একটি বড় হ্যাশ টেবিল. পরিবর্তে চার বালতি নিয়ে, আমি এর 26 বলে দেওয়া আছে. আর আমরা 26 ধার যেতে চান না বাইরে [থেকে জিনিষ? Annenberg এ?], তাই এখানে প্রতিনিধিত্বকারী পাঁচটি এর জেড মাধ্যমে এবং যদি আমি , যার নাম একটি দিয়ে শুরু হয় একজন ছাত্র দেখতে আমি সেখানে তার ব্যঙ্গ করা যাচ্ছে না. কেউ সি দিয়ে শুরু হয়, তাহলে ওইখানে, ছাগু karigor.com আসলে, যে কাজ করতে চান না. বি এখানে ধরে যায়. তাই আমি একটি পেয়েছেন এবং বি এবং সি আর এখন এখানে অন্য একটি ছাত্র এর. কিন্তু এই হ্যাশ টেবিল হয় তাহলে একটি অ্যারের সাথে বাস্তবায়িত, আমি কোন ধরনের মাতাল করছি এই সময়ে, ঠিক আছে? আমি এই ধরনের কোথাও করা প্রয়োজন. 

তাই আমি এই সমাধান করতে পারে একটি উপায় সব, হয় ঠিক আছে, একটি সি ব্যস্ত, বি ব্যস্ত, ব্যস্ত. আমি এ তাই ডি তাকে রাখা যাচ্ছি প্রথমত, আমি র্যান্ডম তাত্ক্ষণিক এক্সেস আছে ছাত্রদের জন্য বালতি প্রতিটি. কিন্তু এখন এটা কোন ধরনের devolved হচ্ছে কিছু রৈখিক মধ্যে, আমি কেউ জন্য অনুসন্ধান করতে চান, কারণ যার নাম একটি দিয়ে শুরু হয়, আমি এখানে চেক করুন. কিন্তু এই একটি নয় যদি আমি চাই ছাত্র, আমি ধরনের পরীক্ষণের শুরু আছে বালতি, আমি কি কারণ এর সুসংগত সাজান ছিল ডাটা স্ট্রাকচার তদন্ত. শুধু চেহারা বলছে একটি মূঢ় উপায় প্রথম উপলব্ধ খোলার জন্য, এবং, তাই কথা বলতে, একটি পরিকল্পনা বি থেকে যত করা বা এই ক্ষেত্রে পরিকল্পনা ডি, মূল্য পরিবর্তে যে অবস্থানে. এই যে আপনি করেছি মাত্র, তাই হয় 26 অবস্থানে এবং কোন ছাত্র পেয়েছিলাম নাম প্রশ্ন বা Z, বা কিছু সঙ্গে যে, অন্তত আপনি স্পেস ব্যবহার করছেন. 

কিন্তু আমরা ইতিমধ্যে আরও দেখা করেছি এখানে চতুর সমাধান, ডান? আপনি যদি এর পরিবর্তে কী করবেন আপনি একটি সংঘর্ষের আছে? দুটি মানুষ থাকে নাম একটি, কি হবে একটি স্মার্ট বা বেশি হয়েছে শুধু চেয়ে স্বজ্ঞাত সমাধান ডি হতে অনুমিত হয় যেখানে একটি নির্বাণ? কেন আমি শুধু যেতে হবে না বাইরে [? Annenberg এ?], যদি malloc, অন্য একটি নোড মত, এটা করা এখানে, এবং তারপর এখানে একটি ছাত্র যে করা. আমি মূলত আছে তাই একটি অ্যারের কিছু, বা আমরা করছি হিসেবে হয়তো আরো elegantly একটি লিঙ্ক তালিকা দেখতে শুরু. 

আর তাই একটি হ্যাশ টেবিল একটি কাঠামো যে, শুধু এই ভালো হত কিন্তু আরো চালাকি, আপনি কিছু বলা পৃথক chaining, যদ্দ্বারা একটি হ্যাশ টেবিল জবাবটা একটি অ্যারের প্রতিটি, হয় যার উপাদান একটি সংখ্যা নয়, একটি লিঙ্ক তালিকা নিজেই. আপনি সুপার দ্রুত অ্যাক্সেস পেতে যাতে যেখানে আপনার মান হ্যাশ মীমাংসাকারী. অনেক কার্ড উদাহরণসহ মত, আমি দ্রুত সিদ্ধান্ত. হৃদয় ফুল এখানে যায়, এখানে যায়. এখানে একই, একটি এখানে যায়, ডি বি এখানে যায়, এখানে যায়. তাই অতি দ্রুত বর্ণন আপগুলি, এবং যদি আপনি একটি মামলা পাতিত ঘটতে যেখানে আপনি পেয়েছেন দুর্ঘটনায় দুই একই নামের সঙ্গে মানুষ, ভাল, তারপর আপনি শুধু তাদের একসঙ্গে লিঙ্ক শুরু. আর হয়তো আপনি তাদের সাজানো রাখতে বর্ণানুক্রমে, হতে পারে আপনি তা চান না. কিন্তু অন্তত এখন আমরা গতিশীলতা আছে. তাই একদিকে আমরা সুপার ফাস্ট আছে ধ্রুব সময়, এবং রৈখিক সময় ধরনের এই লিঙ্ক তালিকা যদি জড়িত একটু দীর্ঘ পেতে শুরু. 

সুতরাং একটি নিরীহ এই ধরনের, আগে, geeky তামাশা বছর. CS50 হ্যাক একটি thon এ, ছাত্র চেক যখন, কিছু TF অথবা সিএ প্রতি বছর মনে এটা করা মজার এই মত একটি চিহ্ন, যেখানে এটি শুধু আপনার নাম একটি A দিয়ে শুরু হয়, তাহলে এর মানে হল, এই দিকে যান. আপনার নাম শুরু হয়, তাহলে একটি বি, আপাততঃ ঠিক আছে যান, এটা হতে পারে পরবর্তী সেমিস্টারে মজার. কিন্তু অন্য আছে খুব, এই কাজ করার উপায়. যে ফিরে আসতে. 

সুতরাং এই কাঠামো আছে. আর এটাই আমাদের শেষ হয় আজকের জন্য কাঠামো, যা একটি trie কিছু বলা হয়. কিছু কারণে স্বল্প যা টি-আর-আমি-ই, আহরণ জন্য, কিন্তু এটা Trie বলা হচ্ছে. সুতরাং একটি trie অন্য আকর্ষণীয় এই ধারণা অনেক সংমিশ্রণ. এটা আমরা দেখা করেছি, যা একটি গাছ, না. এটি একটি বাইনারি অনুসন্ধান বৃক্ষ নয়. এটা শিশুদের যে কোন সংখ্যার সঙ্গে একটি গাছ এর কিন্তু একটি trie শিশুদের প্রতিটি একটি অ্যারে. আকারের একটি অ্যারে, 26 বা হয়তো 27 বলে আপনি hyphenated নাম সমর্থন করতে চান তাহলে বা মানুষ এর নাম মধ্যে Apostrophes. 

আর তাই এই একটি ডাটা স্ট্রাকচার. যদি আপনি এটির উপরে থেকে দেখুন তাহলে নীচে, আপনি যদি চান হয় সেখানে উপরের নোড, এম এ দেখুন সেখানে একেবারে বামের জিনিস প্রতি নির্দেশ, যা পরে একটি, এক্স, ওয়াট, ই, এল, এল এই হয় শুধু একটি ডাটা স্ট্রাকচার যে ইচ্ছামত মানুষ এর নাম সংরক্ষণ করা হয়. ম্যাক্সওয়েল মাত্র অনুসরণ করে সংরক্ষণ করা হয় অ্যারের অ্যারের অ্যারের একটি পাথ. একটি trie সম্পর্কে কিন্তু আশ্চর্যজনক কি , যে একটি লিঙ্ক তালিকা যেহেতু এবং এমনকি একটি অ্যারের, আমরা কখনও অর্জিত করেছি সেরা রৈখিক সময় বা লগারিদমিক সময় খুঁজছি কেউ আপ. একটি trie এই ডাটা স্ট্রাকচার, যদি ইন আমার ডাটা স্ট্রাকচার এটা এক নাম আছে এবং আমি ম্যাক্সওয়েল খুঁজছি, আমি আছি প্রশংসনীয় দ্রুত তাকে খুঁজে পাওয়া যাচ্ছে. আমি শুধু এম একটি এক্স-ওয়াট-ই-এল-এল-এর জন্য দেখুন. যদি এই ডাটা স্ট্রাকচার, বিপরীতভাবে, একটি আছে, n, একটি মিলিয়ন যদি এই তথ্য কাঠামো মিলিয়ন নাম, ম্যাক্সওয়েল এখনও হতে যাচ্ছে ডিসকভারেবেল শুধু এম একটি এক্স-ওয়াট-ই-এল-এল পরে ধাপ. আর ডেভিড ডি-একটি-ভী আমি ডি পদক্ষেপ. অন্য কথায়, নির্মাণের দ্বারা যে একটি ডাটা স্ট্রাকচার পেয়েছিলাম এই অ্যারে সব, সব যা নিজেদের, র্যান্ডম এক্সেস সমর্থন আমি মানুষ এর দিকে তাকিয়ে শুরু করতে পারেন যে সময় একটি পরিমাণ ব্যবহার করে নাম না সংখ্যা সমানুপাতিক তথ্য কাঠামো জিনিস, মত একটি মিলিয়ন বিদ্যমান নাম. এটা বের করতে আমার সময় লাগে সময় পরিমাণ এম-একটি-এক্স-ওয়াট-ই-এল-এল এই তথ্য কাঠামো হয় সমানুপাতিক না করতে ডাটা স্ট্রাকচার এর আকার, কিন্তু নাম দৈর্ঘ্যের. এবং বাস্তবধর্মী নাম আমরা আপ খুঁজছেন না ঐসব গোনাহর পাগল হতে যাচ্ছি. হয়তো কেউ একজন 10 অক্ষর আছে , 20 অক্ষর নাম নাম. এটা ঠিক আছে, অবশ্যই সমাপিকা? পৃথিবীতে একজন মানুষ আছে যারা দীর্ঘতম সম্ভব নাম আছে, কিন্তু যে নাম একটি ধ্রুবক মান দৈর্ঘ্য, ডান? এটা কোন অর্থে পরিবর্তিত হয় না. তাই এই ভাবে, আমরা করেছি একটি ডাটা স্ট্রাকচার অর্জন যে ধ্রুব বর্ণন সময়-আপ হয়. এটা পদক্ষেপ গ্রহণ করা আছে ইনপুট দৈর্ঘ্যের উপর নির্ভর করে, নামের কিন্তু সংখ্যা তথ্য কাঠামো. আমরা নাম সংখ্যা দ্বিগুণ যদি তাই একটি বিলিয়ন বিলিয়ন থেকে দুই থেকে পরের বছর, খোঁজ ম্যাক্সওয়েল নিতে যাচ্ছে সাত ধাপ সঠিক একই সংখ্যা তাকে খুঁজে পেতে. আর তাই আমরা অর্জন করেছি বলে মনে হচ্ছে সময় চলমান আমাদের পবিত্র ঈপ্সিত বস্তু. 

তাই দ্রুত ঘোষণা একটি দম্পতি. ব্যঙ্গ শূন্য আপ আসছে. অবশ্যই এর ওয়েবসাইটে যে আরও আগামী কয়েকদিনের ওভার. সোমবারের এটি একটি ছুটির দিন lecture-- এখানে হার্ভার্ড এ সোমবার. এটা নিউ হ্যাভেন না তাই আমরা ক্লাসে গ্রহণ করছেন সোমবার বক্তৃতা করার জন্য নিউ হ্যাভেন থেকে. সবকিছু শুট করা হবে এবং যথারীতি লাইভ স্ট্রিম কিন্তু এর আজ শেষ দিন একটি 30 দ্বিতীয় ক্লিপ দিয়ে বলা "ডিপ থটস" Daven Farnham, দ্বারা যা শনিবার দ্বারা গত বছরের অনুপ্রাণিত হয়েছিলাম নাইট লাইভ এর "ডিপ থটস" জ্যাক কুশলী, দ্বারা যা এখন জানার উচিত. 

চলচ্চিত্র: আর এখন, "ডিপ Daven Farnham দ্বারা থটস ". হ্যাশ টেবিল. 

বক্তা 1: ঠিক আছে, যে এখন জন্য এটি. আমরা আগামী সপ্তাহে আপনি দেখতে পাবেন. 

ডগ: এটিকে অ্যাকশনে দেখুন. সুতরাং আসুন এই মুহূর্তে যে কটাক্ষপাত করা যাক. তাই এখানে, আমরা একটি পাঁচমিশালী অ্যারে আছে. 

ইয়ান: ডগ, আপনি এগিয়ে এবং পুনর্সূচনা যেতে পারেন মাত্র এক দ্বিতীয় জন্য এই, দয়া করে. ঠিক আছে, ক্যামেরা, তাই ঘূর্ণায়মান হয় কর্ম আপনি ডগ, প্রস্তুত যখনই, ঠিক আছে? ডগ: ঠিক আছে, তাই কি আমরা এখানে আছে একটি পাঁচমিশালী অ্যারে. আর আমি উপাদানের সমস্ত রঙ্গিন করেছি এটা আসলে, যে ইঙ্গিত লাল, পাঁচমিশালী. তাই সর্বপ্রথম যে আমরা প্রত্যাহার আমরা অ্যারের বাম অর্ধেক বাছাই হয়. তারপর আমরা ডান সাজানোর অ্যারে অর্ধেক. আগে-হ্যাঁ, আস-হ্যাঁ, আস-দা, আমরা তাদের একসঙ্গে একত্রীকরণ. আর আমরা একটি সম্পূর্ণ সাজানো অ্যারে আছে. সুতরাং যে কাজ সাজান একত্রীকরণ কিভাবে. 

ইয়ান: দাঁড়ান, ইশ! কাট, কাট, কাট, কাটা. ডগ, আপনি শুধু আস-দা না পারেন, আস-দা, আস-হ্যাঁ, একত্রীকরণ সাজানোর মাধ্যমে আপনার উপায়. 

ডগ: আমি ঠিক করেছিলাম. এটা ভাল. আমরা যেতে ভাল. এর মাত্র ঘূর্ণায়মান রাখা যাক. তাই যাহাই হউক না কেন, 

ইয়ান: আপনি ব্যাখ্যা করতে হবে এটা আরো সম্পূর্ণরূপে যে বেশী. যে শুধু যথেষ্ট নয়. ডগ: ইয়ান, আমরা না এক ফিরে যেতে হবে. এটা ভাল. তাই যাহাই হউক না কেন, আমরা merge-- অগ্রসর যদি ইয়ান, আমরা চিত্রগ্রহণ মাঝখানে আছেন. 

ইয়ান: আমি জানি. আর আমরা শুধু আস-দা না পারেন, আস-দা, পুরো প্রক্রিয়ার মাধ্যমে আস-হ্যাঁ,. আপনি কিভাবে ব্যাখ্যা করতে হবে দুই পক্ষই একসাথে মার্জ পেতে. 

ডগ: কিন্তু আমরা ইতিমধ্যেই করেছি ব্যাখ্যা কিভাবে দুই sides-- 

ইয়ান: আপনি শুধু দেখানো করেছি তাদের একটি একত্রীকরণ অ্যারে. ডগ: তারা প্রসেস জানা. তারা ভাল আছে. আমরা এটা ধরে দশ গুণ সর্বস্বান্ত করেছি. 

ইয়ান: আপনি এটা উপর রাইট এড়ানো. আমরা এক ফিরে যাচ্ছেন, আপনি এটি উপর আপনি আস-হ্যাঁ, আস-দা না পারেন. ফিরে এক ঠিক আছে,. 

ডগ: আমি ফিরে যেতে হবে স্লাইড সব দিয়ে? আমার ঈশ্বর. এটা ষষ্ঠ সময়, ইয়ান মত. এটা ভাল. 

ইয়ান: ঠিক আছে. তুমি প্রস্তুত? গ্রেট. কর্ম.