[সঙ্গীত বাজানো] ডেভিড জে MALAN: ঠিক আছে. এটি CS50. এই সপ্তাহে পাঁচ অব্যাহত, এবং আমরা কিছু ভাল খবর এবং কিছু খারাপ খবর আছে. সুতরাং ভাল খবর হল যে CS50 হয় এই শুক্রবার আরম্ভ করা হয়. আপনি আমাদের সঙ্গে যোগদান করতে চান তাহলে, এখানে স্বাভাবিক URL এ নেতা. আরও ভাল খবর, কোন বক্তৃতা এই 13 সোমবার আসছে. সামান্য কম ভাল খবর, ব্যঙ্গ শূন্য পরের বুধবার. আরো বিস্তারিত হতে পারে এখানে এই URL এ খুঁজে পাওয়া যায়নি. এবং পরবর্তী কয়েক দিন ধরে আমরা ঐ খালি স্থান পূরণ করা হবে কক্ষ শুভেচ্ছা সঙ্গে আমরা সংরক্ষিত থাকবে. ভাল খবর আছে করব একটি কোর্স ব্যাপী পর্যালোচনা করা সময় এই আসছে সন্ধ্যায় সোমবার. অবশ্যই এর জন্য tuned থাকুন অবস্থান এবং বিস্তারিত তথ্যের জন্য ওয়েবসাইট. এটি একটি যদিও বিভাগে, ছুটির দিন, হিসাবে ভাল হবে. ভাল খবর, আগামী শুক্রবার বক্তৃতা. সুতরাং এই একটি ঐতিহ্য আমরা পাঠ্যক্রম অনুযায়ী, আছে. ঠিক করা এটা আশ্চর্যজনক হতে যাচ্ছে. আপনি ভালো জিনিস দেখতে হবে ধ্রুব সময় ডাটা স্ট্রাকচার এবং হ্যাশ টেবিল এবং গাছ এবং চেষ্টা করে. এবং আমরা জন্মদিন সমস্যা সম্পর্কে কথা বলতে পারবেন. স্টাফ একটি আভা পরের শুক্রবার awaits. ঠিক আছে. যাহাই হউক না কেন. তাই আমরা করেছি প্রত্যাহার কি এই ছবি উপর মনোযোগ নিবদ্ধ করে আমাদের কম্পিউটার এর মেমরি ভিতরে. তাই মেমরি বা RAM উপস্থিত যেখানে প্রোগ্রাম আপনি তাদের চালাচ্ছেন যখন বিদ্যমান. আপনি একটি ডবল ক্লিক করুন আইকন কিছু প্রোগ্রাম চালানো অথবা একটি ডবল ক্লিক করুন কিছু ফাইল খোলার জন্য আইকন, এটি আপনার হার্ড থেকে লোড এর ড্রাইভ বা সলিড স্টেট ড্রাইভ র্যাম, র্যান্ডম অ্যাক্সেস মেমরি, যেখানে মধ্যে ক্ষমতা যায় বন্ধ না হওয়া পর্যন্ত এটা জীবন ল্যাপটপ ঢাকনা, প্রচেষ্টা অথবা আপনি প্রোগ্রাম প্রস্থান. 

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

সুতরাং যখন আপনি ডবল ক্লিক করুন আপনার Mac বা PC মাইক্রোসফট ওয়ার্ড, আপনি বিন্দু যখন চালানো বা উপর মারিও কাট আপনার টার্মিনাল উইন্ডোর এ লিনাক্স কম্পিউটার, রচনা যে zeros এবং বেশী শব্দ বা মারিও সাময়িকভাবে সংরক্ষণ করা হয় তথাকথিত মধ্যে আপনার কম্পিউটার এর RAM উপস্থিত মধ্যে একটি নির্দিষ্ট প্রোগ্রামের জন্য টেক্সট সেগমেন্ট. যে যায় নীচে সক্রিয়া এবং uninitialized তথ্য. এই গ্লোবাল ভেরিয়েবল মত উপাদান, আমরা অনেক ব্যবহার করেছি না যে, কিন্তু অনুষ্ঠানে আমরা করেছি গ্লোবাল ভেরিয়েবল ছিল বা স্ট্যাটিক্যালি স্ট্রিং সংজ্ঞায়িত যে কঠিন "হ্যালো" মত শব্দ কোডেড হয় ব্যবহারকারীর কাছ থেকে নেওয়া না হয় যে আপনার প্রোগ্রাম হার্ড কোড করা হয়. 

এখন, নিচে নীচে আমরা তথাকথিত স্ট্যাকের আছে. এবং স্ট্যাকের, এ পর্যন্ত, আমরা চলেছি উদ্দেশ্য কি ধরণের জন্য ব্যবহার করে? স্ট্যাকের কি জন্য ব্যবহার করা হয়েছে? হ্যাঁ? 

শ্রোতা: কার্যাবলী. 

ডেভিড জে MALAN: ফাংশন জন্য? ফাংশন জন্য কি অর্থে? 

শ্রোতা: আপনি যখন একটি ফাংশন কল, আর্গুমেন্ট স্ট্যাকের মধ্যে কপি করা হয়. 

ডেভিড জে MALAN: যথাযথভাবে. আপনি যখন একটি ফাংশন কল, তার আর্গুমেন্ট স্ট্যাকের মধ্যে কপি করা হয়. তাই যে কোনো X বা Y এর বা এর একটি অথবা B এর আপনি একটি ফাংশন মধ্যে পার করছি সাময়িকভাবে আরোপ করা হয় তথাকথিত স্ট্যাকের, শুধু ইচ্ছাশক্তি Annenberg এক মত ডাইনিং হল ট্রে, এবং জিনিস স্থানীয় ভেরিয়েবল মত. যদি আপনার foo বিন্যাস ফাংশন বা আপনার swap ' ফাংশন স্থানীয় ভেরিয়েবল আছে, temp হয় মত, যারা দুই স্ট্যাক শেষ পর্যন্ত. এখন, আমরা সম্পর্কে খুব বেশী কথা বলতে হবে না তাদের, কিন্তু এই পরিবেশের নীচে আমরা একটি সময় আগে যখন দেখেছি আমি কীবোর্ড এক দিন এ futzing ছিল আমি কিছু জিনিস ব্যবহার শুরু argv হয় 100 বা argv হয় 1,000 মত, শুধু elements-- আমি ভুলবেন সংখ্যার কিন্তু যে আমার দ্বারা ব্যবহার করা অনুমিত হয় না. আমরা কিছু নিরীক্ষা শুরু পর্দায় ভীতু চিহ্ন. যারা তথাকথিত ছিল পরিবেশের গ্লোবাল সেটিংস মত আমার প্রোগ্রাম বা আমার কম্পিউটার না জন্য সাম্প্রতিক সম্পর্কহীন আমরা আলোচনা বাগ, ShellShock, যে হয়েছে বেশ কয়েকটি কম্পিউটার মহামারীর মত ছড়িয়ে পড়া. 

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

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

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

এখন, গল্প করে আমি বলার ছিল একটি মুহূর্ত আগে, যেখানে মেমরি গ, অথবা যারা 12 আপ শেষ হয়ে যাচ্ছে চর? শুধু পরিষ্কার করা. হ্যাঁ? 

শ্রোতা: স্ট্যাকের উপর. 

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

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

শ্রোতা: অন্তর্ভুক্ত নয় নাল অক্ষর জন্য রুম. ডেভিড জে MALAN: অন্তর্ভুক্ত নয় নাল অক্ষর জন্য রুম. সম্ভাব্য, অসদৃশ গত অনুশীলন এমনকি আমরা না একটি প্লাস 1, তাই হিসাবে অনেক যে নাল অক্ষর মিটমাট করা. কিন্তু এটা যে তুলনায় এমনকি খারাপ. কি কি আমরা করতে ব্যর্থ হয়? হ্যাঁ? 

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

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

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

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

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

কিন্তু এখন দ্রুত এগিয়ে চেষ্টা করুন. আমরা কি পাস ঘটতে সম্পর্কে গ সময়ের চেয়ে যে একটি স্ট্রিং বার? এবং আমরা যদি চেক না এটা সত্যিই আর 12 এর বেশী. এই ছবি কোন অংশ যাচ্ছে বাইট 0, 1, 2, 3 দ্বারা মুছে ফেলা পেতে, ডট ডট ডট, 11, এবং তারপর খারাপ, 12, 19 মাধ্যমে 13? কি, এখানে ঘটতে যাচ্ছে আপনি ক্রম থেকে অনুমান যদি যে গ বন্ধনী 0 উপরে হয় এবং গ বন্ধনী 11 নিচে সাজানোর ডান? হ্যাঁ? 

শ্রোতা: ওয়েল, এটা যাচ্ছে গৃহস্থালি * বার মুছে ফেলা. 

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

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

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

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

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

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

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

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

কিন্তু গাদা এখানে আপ হয়. এবং malloc যে সম্পর্কে চমৎকার কি যদি malloc এখানে মেমরি বরাদ্দ যখন, এটা জন্য, প্রভাবিত না স্ট্যাকের দ্বারা অধিকাংশ অংশ,. তাই কোনো ফাংশন অ্যাক্সেস করতে পারেন malloc'd হয়েছে যে মেমরি, এমনকি GetString মত একটি ফাংশন দ্বারা, এমনকি পরে এটি ফিরিয়ে দেওয়া হয়. 

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

এবং Valgrind, এক pset 4 চালু সরঞ্জাম, আপনার পক্ষে সব বিষয়ে এখন যে মত বাগ খুঁজে. কিন্তু সৌভাগ্যক্রমে pset 4 জন্য প্রয়োজন হবে না CS50 লাইব্রেরি বা GetString ব্যবহার করার জন্য. তাই মেমরি এর সাথে সম্পর্কিত কোন বাগ আছে শেষ পর্যন্ত আপনার নিজের হতে যাচ্ছে. 

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

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

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

শ্রোতা: [শ্রবণাতীত] 

ডেভিড জে MALAN: দুঃখিত? 

শ্রোতা: শেষ এটি. 

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

সুতরাং আপনি কি কি করতে পারে? ওয়েল, একবার আপনি বুঝতে , আকার সাত একটি অ্যারের প্রয়োজন আপনি শুধু একটি তৈরী করতে পারে আকার সাত অ্যারে তারপর ব্যবহার একটি লুপ বা যখন একটি লুপ জন্য, নতুন অ্যারের মধ্যে কপি, এবং তারপর একরকম ঠিক পরিত্রাণ পেতে এই অ্যারে বা শুধু এটি ব্যবহার করা বন্ধ. কিন্তু যে বিশেষ করে দক্ষ না. সংক্ষেপে, অ্যারে দেবেন না আপনি পরিবর্তনশীল মাপ পরিবর্তন. 

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

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

কিন্তু আমরা সৃষ্টি কি করে এই ক্ষেত্রে, তীর একরকম এই যে লিঙ্ক একসঙ্গে আয়তক্ষেত্র? প্রকৃতপক্ষে, আমরা একটি প্রযুক্তিগত দেখা করেছি একটি তীর এর আবির্ভাব. আমরা কি সাম্প্রতিক ব্যবহার করেছেন দিন যে, ফণা নীচে, একটি তীর প্রতিনিধি? একটি পয়েন্টার, ডান? 

তাই যদি, পরিবর্তে শুধু সংখ্যা সংরক্ষণ, মত 9, 17, 22, 26, 34, আমরা কি না সংরক্ষণ করা হলে শুধুমাত্র একটি সংখ্যা কিন্তু একটি পয়েন্টার প্রতিটি যেমন সংখ্যা পরের? সুতরাং যে অনেক আপনি একটি থ্রেড চাই ফ্যাব্রিক আভা মাধ্যমে সুই, একরকম বিস্তারিত tying জিনিস একসঙ্গে একভাবে করতে পারেন পয়েন্টার, হিসাবে আমরা এখানে তীরচিহ্ন দ্বারা incarnated, ধরনের একসঙ্গে বুনা এই স্বতন্ত্র আয়তক্ষেত্র কার্যকরভাবে একটি পয়েন্টার ব্যবহার করে প্রতিটি সংখ্যা পরের যে যে, কিছু পরবর্তী সংখ্যা পয়েন্ট ঘুরে, কিছু পরবর্তী সংখ্যা স্থানটিকে? তাই অন্য কথায়, কি আমরা আসলে চেয়েছিলেন ভালো কিছু বাস্তবায়ন করতে? ভাল দুর্ভাগ্যবশত, এই আয়তক্ষেত্র, 9 অন্তত এক, 17, 22 এ, এবং তাই ঘোষণা, এই আর একক সংখ্যার চমৎকার স্কোয়ার. নীচে, আয়তক্ষেত্র 9 নিচে, উদাহরণস্বরূপ, প্রতিনিধিত্ব করে কি করা উচিত একটি পয়েন্টার, 32 বিট হতে হবে. এখন, আমি কোনো তথ্য টাইপ সচেতন নই সি যে আপনি না কোন int দেয় কিন্তু একটি পয়েন্টার সম্পূর্ণভাবে. 

আমরা চাই, তাই যদি সমাধান কি এই আমাদের নিজস্ব উত্তর উদ্ভাবিত? হ্যাঁ? 

শ্রোতা: [শ্রবণাতীত] 

ডেভিড জে MALAN: কি যে? 

শ্রোতা: নতুন কাঠামো. 

ডেভিড জে MALAN: হ্যাঁ, কেন আমরা একটি নতুন কাঠামো তৈরি না, বা C, একটি struct মধ্যে? আমরা যদি সংক্ষেপে, আগে structs দেখা করেছি আমরা একটি ছাত্র কাঠামো সঙ্গে মোকাবিলা যেখানে এই মত একটি নাম এবং একটি ঘর ছিল. Pset মধ্যে 3 ব্রেকআউট আপনি একটি সম্পূর্ণ ব্যবহার structs-- GRect এবং GOvals গুচ্ছ স্ট্যানফোর্ড নির্মিত যে একসঙ্গে ক্লাস্টার তথ্য. তাই আমরা এই একই ধারণা নিতে হলে মূলশব্দ "typedef" এবং "struct,," এবং তারপর কিছু ছাত্র নির্দিষ্ট উপাদান, এবং নিম্নলিখিত মধ্যে এই অভিব্যক্ত: typedef struct নোড এবং নোড শুধু একটি খুব জেনেরিক কম্পিউটার বিজ্ঞান একটি তথ্য কাঠামো কিছু শব্দ, একটি তথ্য কাঠামো একটি ধারক. আমি দাবি একটি নোড আছে যাচ্ছে সম্পূর্ণ সহজবোধ্য কোন int n, এবং তারপর আরো cryptically একটু, এই দ্বিতীয় লাইন, struct নোড * পরবর্তী. কিন্তু কম প্রযুক্তিগত পদ, যে দ্বিতীয় লাইন কি কোঁকড়া ধনুর্বন্ধনী ভিতরে কোড? হ্যাঁ? 

শ্রোতা: [শ্রবণাতীত] ডেভিড জে MALAN: একটি অন্য একটি নোড পয়েন্টার. সুতরাং নিঃসন্দেহে, একটু রহস্যপূর্ণ সিনট্যাক্স. কিন্তু আপনি আক্ষরিক এটি পড়া, পরবর্তী একটি পরিবর্তনশীল এর নাম. তার তথ্য টাইপ কি? এটা, এই সময় একটু বাগাড়ম্বরপূর্ণ কিন্তু এটি টাইপ * struct নোড এর মধ্যে. আমরা কিছু তারা দেখা করেছেন কোন সময়, যে এটা যে ডাটা টাইপ একটি পয়েন্টার মানে. তাই পরবর্তী দৃশ্যত একটি হল একটি struct নোড পয়েন্টার. 

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

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

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

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

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

তাই আসুন এই চেষ্টা. এর এগিয়ে যান এবং 2 টাইপ করুন. এবং তারপর আমি যাচ্ছি সংখ্যা সন্নিবেশ, 9 বলে. লিখুন. এবং এখন আমার প্রোগ্রাম ঠিক হয় বলতে প্রোগ্রাম, তালিকা এখন 9. এখন, আমি এগিয়ে যান এবং আবার ঢোকান না, যাক আমাকে এগিয়ে যান এবং জুম আউট এবং 17 টাইপ. এখন আমার তালিকা তারপর, 17 9. আমি আবার সন্নিবেশ না, এর এক লাফালাফি করা যাক. পরিবর্তে 22, ছবি অনুযায়ী আমরা করেছি এখানে এ খুঁজছেন করা হয়েছে, আমাকে এগিয়ে তিড়িং লাফ দিন এবং পরবর্তী 26 সন্নিবেশ করুন. তাই আমি 26 টাইপ করতে যাচ্ছি. আমি আশা তালিকা. কিন্তু এখন, শুধু এই কোড যদি দেখতে নমনীয় হতে যাচ্ছে, এখন আমাকে টাইপ 22, যা অন্তত ধারণার দিক থেকে, আমরা যদি এই প্রকৃতপক্ষে, যা সাজানো পালন ডান এখন আরেকটি লক্ষ্য করা যাচ্ছে, 17 এবং 26 এর মধ্যে যেতে হবে. তাই আমি আঘাত লিখুন. প্রকৃতপক্ষে, যে কাজ করে. তাই এখন আমাকে সন্নিবেশ করা শেষ, ছবি, 34 প্রতি. 

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

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

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

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

শ্রোতা: আমরা একটি নোডের একটি পয়েন্টার প্রয়োজন. ডেভিড জে MALAN: একটি নোডের একটি পয়েন্টার. বিশেষ করে, যা নোড আপনার হবে সহজাত একটি পয়েন্টার রাখা হবে? 

শ্রোতা: প্রথম নোডের. 

ডেভিড জে MALAN: হ্যাঁ, সম্ভবত প্রথম. এবং, প্রথম লক্ষ্য নোড বিভিন্ন আকৃতি হয়. এটা struct, কেবলমাত্র অর্ধেক আকার, কারণ এটা সত্যিই শুধুমাত্র একটি পয়েন্টার. তাই আপনি যদি প্রকৃতপক্ষে কি করতে পারেন ঘোষণা করা হয় একটি লিঙ্ক তালিকা * টাইপ নোড হতে হবে. আর এর প্রথম কল করা যাক এবং নাল এটি আরম্ভ. তাই নাল, আবার, আসছে এখানে ছবি. নেই শুধু নাল একটি বিশেষ মত হিসাবে ব্যবহার করা হয় GetString ভালো জিনিস বিনিময়ে মূল্য এবং malloc, নাল এছাড়াও শূন্য পয়েন্টার, একটি পয়েন্টার অভাব, যদি আপনি হবে. এটা ঠিক কিছুই এখনো এখানে হয় না. এখন প্রথম, আমি করেছি পারে এই কিছু বলা. আমি "তালিকা" এটা বলা যেতে পারে বা অন্য যে কোনো সংখ্যা. কিন্তু আমি যে তাই "প্রথম" এটা আহ্বান করছি এই ছবি সঙ্গে এটি লাইন আপ. তাই শুধু একটি স্ট্রিং মত প্রতিনিধিত্ব করা যাবে তার প্রথম বাইট এর ঠিকানা দিয়ে, তাই একটি লিঙ্ক তালিকা করতে পারেন. এবং আমরা অন্যান্য তথ্য দেখতে পাবেন কাঠামো প্রতিনিধিত্ব করা মাত্র এক পয়েন্টার দিয়ে, একটি 32 বিট তীর, প্রতি নির্দেশ গঠন খুব প্রথম নোড. 

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

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

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

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

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

আমি আপনি এই খুঁজে না, আমি আছি কিছু করতে চান যাচ্ছে মত আমরা n পাওয়া ঘোষণা. এবং আমরা একটি হিসাবে যে ছেড়ে দেব মন্তব্য বা pseudocode হয় কোড. অন্যথায়, এবং এখানে আকর্ষণীয় অংশ, কি আমি বর্তমান নোড যদি কাজ করতে চান না আমি যত্ন সম্পর্কে যে n ধারণকারী করা হয় না? আমি কিভাবে নিম্নলিখিত অর্জন না? যদি আমার আঙুল মুহূর্ত PTR, এবং এটা যাই হোক না কেন নির্দেশ প্রথম, নির্দেশ করা হয় আমি আমার আঙুল সরাতে কিভাবে কোড পরবর্তী নোডের? ভাল, আমরা করছি ব্রেডক্রম্বে কি এই ক্ষেত্রে অনুসরণ করতে যাচ্ছে? শ্রোতা: [শ্রবণাতীত]. ডেভিড জে MALAN: হ্যাঁ, তাই পরবর্তী. আমি ফিরে যান তাই আমার এখানে কোড, প্রকৃতপক্ষে, আমি , পয়েন্টার এগিয়ে যান এবং বলতে যাচ্ছে যা এটি শুধু একটি অস্থায়ী ভেরিয়েবল হয় একটি অদ্ভুত নাম, ptr, কিন্তু এটা ঠিক temp-- মত আমি পয়েন্টার সেট করা যাচ্ছে না যাই হোক না কেন পয়েন্টার যাই সমান এবং আবার, এই একটি হতে যাচ্ছে পরবর্তী একটি মুহূর্ত ডট জন্য একটু বগী. অন্য কথায়, আমি নিতে যাচ্ছি আমার এই নোড এর প্রতি নির্দেশ করে যে আঙুল এখানে এবং আমি আপনি কি জানেন, বলতে যাচ্ছি কি, পরবর্তী ক্ষেত্র কটাক্ষপাত করা এবং আপনার আঙুল সরাতে যাই হোক না কেন এটা নির্দেশ করে. এবং এই যাচ্ছে , পুনরাবৃত্তি, পুনরাবৃত্তি পুনরাবৃত্তি. কিন্তু যখন আমার আঙুল আছে এ সব কিছু করছেন থামাতে? যত তাড়াতাড়ি কি কোড kicks এর লাইন হিসাবে? শ্রোতা: [শ্রবণাতীত] ডেভিড জে MALAN: যদি বিন্দু যখন পয়েন্টার নাল সমান হয় না. কিছু পয়েন্ট আমার আঙুল এর সময়ে নাল নির্দেশ করা যাচ্ছে এবং আমি বুঝতে পারছি করা যাচ্ছে না এই তালিকা যে শেষে. এখন, এই একটি সামান্য সরলতা জন্য সাদা মিথ্যা. এটা পরিনত হয় যে, যদিও আমরা শুধু এই বিন্দু স্বরলিপি শিখেছি কাঠামোর জন্য, পয়েন্টার একটি struct হয় না. ptr কি? শুধু আরো nitpicky হতে. এটি একটি নোডের একটি পয়েন্টার. এটি একটি নোড নিজেই না. আমি এখানে তারা ছিল, পয়েন্টার সুখেন্দু এটি একটি নোড. এই সপ্তাহে এক মত একটি পরিবর্তনশীল ঘোষণা, এমনকি শব্দ "নোড" নতুন যদিও. 

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

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

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

তাই এর এই না দেওয়া. আপনি এখানে মেজাজ আমার হবে না, আমি কি চাপ বল একটি গুচ্ছ আনা. আমি সংখ্যার একটি গুচ্ছ আনা. এবং আমরা মাত্র কয়েক স্বেচ্ছাসেবকদের পেতে পারে 9, 17, 20, 22, 29, এবং 34 প্রতিনিধিত্ব করতে? তাই মূলত সবাই এখানে যারা আজকে. যে, এক, দুই, তিন চার, পাঁচ, ছয় জনের. এবং আমি না, দেখতে go-- করতে বলা হয়েছে ফিরে এক তাদের হাত উত্থাপন. ঠিক আছে, এক, দুই, তিন, চার, পাঁচটি আমাকে ছয় balance-- লোড করা যাক. ঠিক আছে, আপনি ছয় উপর আসা. আমরা অন্য মানুষ প্রয়োজন হবে. আমরা অতিরিক্ত চাপ বল আনা. এবং আপনি যদি পারে, জন্য শুধু একটা মুহূর্ত, লাইন নিজের আপ ঠিক এখানে এই ছবি মত. 

ঠিক আছে. আপনার নাম কি, এর দেখতে দিন? 

শ্রোতা: অ্যান্ড্রু. 

ডেভিড জে MALAN: অ্যান্ড্রু, আপনি সংখ্যা 9 দ্বারা. দেখা হওয়ায় খুশী হলাম. এখানে আপনি যান. শ্রোতা: জেন. ডেভিড জে MALAN: জেন. ডেভিড. সংখ্যা 17. হ্যাঁ? 

শ্রোতা: আমি জুলিয়া আছি. 

ডেভিড জে MALAN: জুলিয়া, ডেভিড. সংখ্যা 20. শ্রোতা: খৃস্টান. ডেভিড জে MALAN: খৃস্টান, ডেভিড. সংখ্যা 22. এবং? 

শ্রোতা: জেপি. ডেভিড জে MALAN: জেপি. সংখ্যা 29. তাই উহু উহ এগিয়ে যান এবং in-- পেতে. ওহ উহ. স্ট্যান্ডবাইতে রাখুন. 20. যে কেউ একটি চিহ্নিতকারী আছে? শ্রোতা: আমি একটি Sharpie পেয়েছেন. ডেভিড জে MALAN: আপনি একটি Sharpie পেয়েছেন? ঠিক আছে. এবং যে কেউ এক টুকরা কাগজ আছে? বক্তৃতা সংরক্ষণ করুন. চলো. শ্রোতা: আমরা এটা পেয়েছেন. ডেভিড জে MALAN: আমরা পেয়েছি? সমস্ত অধিকার, আপনাকে ধন্যবাদ. আমরা এখানে. এই আপনি থেকে লেগেছে? আপনি শুধু দিন সংরক্ষিত. তাই 29. ঠিক আছে. আমি 29 misspelled, কিন্তু ঠিক আছে. এগিয়ে যান. সমস্ত অধিকার, আমি দেব আপনার কলম ফিরে প্রতিমুহূর্তে. তাই আমরা এখানে এইসব লোকেরা আছে. এর অন্য এক আছে. গেব, প্লে করতে চান না এখানে প্রথম উপাদান? আমরা নির্দেশ আপনার প্রয়োজন হবে এই সূক্ষ্ম ভাবেন এ. তাই 9, 17, 20, 22, সাজানোর 29, এবং তারপর 34. আমরা কেউ হারান? আমি একটি 34 আছে. যেখানে চায় did-- ঠিক আছে, 34 হতে? ঠিক আছে, 34, উপর আসা. সমস্ত অধিকার, এই হবে শীর্ষবিন্দু ভাল মূল্য. আপনার নাম কি? 

শ্রোতা: পিটার. 

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

তাই এখন আপনি ডান অলঙ্কৃত করা যদি ছবি মত নিজের এখানে, এগিয়ে যান এবং বিন্দু গেব সঙ্গে, প্রতিটি অন্যান্য সময়ে এ বিশেষ ইশারা মধ্যে 9 নম্বর তালিকায় প্রতিনিধিত্ব করতে. ঠিক আছে, সংখ্যা 34, আপনার বাম হাত শুধু মেঝে নির্দেশ করা উচিত. 

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

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

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

তাই এই আমাদের গল্প শুরু. এবং এখন এই, শুধু সহজবোধ্য যদিও সিনট্যাক্স নতুন. ধারণার দিক থেকে এই মাত্র রৈখিক অনুসন্ধান. 9 সমান 55 হয়? অথবা এর পরিবর্তে, এর 9 কম বলে. আমি চেষ্টা করছি কারণ 55 করা চিন্তা করা যেখানে. 9 এর চেয়ে কম, কম 17 কম 20 কম 22 কম 29, কম 34, কোন. তাই এখন আমরা কেস মধ্যে আছেন অন্তত তিনটি এক. 

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

তাই এখন কি পরবর্তী যদি দৃশ্যকল্প, বরাবর আসে এবং আমরা সন্নিবেশ করতে চান শুরু এই তালিকা মাথা? এবং আপনার নাম, সংখ্যা 55 কি? 

শ্রোতা: জ্যাক. 

ডেভিড জে MALAN: জ্যাক? ঠিক আছে, আপনি দেখা করতে চমৎকার. জাহাজের উপরে স্বাগতম. তাই এখন আমরা চলুন , বলে, 5 নম্বর সন্নিবেশ করুন. এখানে দ্বিতীয় ক্ষেত্রে তিন আমরা আগে নিয়ে এসেছেন. তাই 5 শুরুতে জন্যে যদি, আমরা যে খুঁজে বের করে দেখুন. আমি আমার ptr আরম্ভ আবার সংখ্যা 9 পয়েন্টার. এবং আমি 5 কম 9, ওহ, বুঝতে পেরেছি. তাই আমাদের জন্য এই ছবি ঠিক. যার হাত, গেব বা ডেভিড এর or-- সংখ্যা 9 এর নাম কি? 

শ্রোতা: জেন. 

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

সমস্ত অধিকার, তাই now-- এবং একটি সরাইয়া, নাম হিসাবে আমি এর স্পষ্ট উল্লেখ তৈরীর করছি না এখন, Pred পয়েন্টার, পয়েন্টার পূর্বসুরী এবং নতুন পয়েন্টার, যে শুধু নাম দেওয়া পয়েন্টার নমুনা কোড বা ধরনের প্রায় প্রতি নির্দেশ করে যে আমার হাতে. আপনার নাম কি? 

শ্রোতা: ক্রিস্টিন. 

ডেভিড জে MALAN: ক্রিস্টিন. জাহাজের উপরে স্বাগতম. ঠিক আছে, তাই এর এখন বিবেচনা করা যাক একটি সামান্য আরো বিরক্তিকর দৃশ্যকল্প, আমি সন্নিবেশ করতে চান যদ্দ্বারা এই মধ্যে 26 ভালো কিছু. 20? কি? এই আমরা এই কলম আছে ভাল জিনিস are--. সমস্ত অধিকার, 20. কেউ অন্য টুকরা পেতে পারে কাগজ ঠিক সব ঠিক ক্ষেত্রেই এ, প্রস্তুত. ওহ, আকর্ষণীয়. আচ্ছা এই একটি উদাহরণ একটি বক্তৃতা বাগ. ঠিক আছে, তাই আপনার নাম আবার কি? শ্রোতা: জুলিয়া. ডেভিড জে MALAN: জুলিয়া, আপনি পপ করতে পারেন আউট এবং সাজা আপনি না ছিল? ঠিক আছে, এই কি না. আপনাকে ধন্যবাদ. তাই আমরা সন্নিবেশ চাই এই লিঙ্ক তালিকায় জুলিয়া. তিনি সংখ্যা 20. এবং অবশ্যই সে এ অন্তর্গত যাচ্ছে begin-- এখনো কিছু নির্দেশ করে না. সুতরাং আপনার হাত ধরনের হতে পারে নিচে নাল বা কিছু আবর্জনা মান. এর দ্রুত গল্প বলা যাক. আমি 5 নম্বর এই সময় নির্দেশ করে না. তারপর আমি 9 বার করো. তারপর আমি 17 বার করো. তারপর আমি 22 বার করো. এবং আমি খুশি, জুলিয়া বুঝতে 22 আগে যেতে প্রয়োজন. তাই কি কি করা প্রয়োজন? যার হাত পরিবর্তন করতে হবে? জুলিয়া এর, খনি, or-- আপনার নাম আবার কি? 

শ্রোতা: খৃস্টান. 

ডেভিড জে MALAN: খৃস্টান বা? 

শ্রোতা: অ্যান্ডি. 

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

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

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

এখন, অবশ্যই অন্য কিছু আছে আমরা বাস্তবায়ন হতে পারে অপারেশন. এবং এখানে এই ছবি শুধু বর্ণা আমরা কি শুধু মানুষের সাথে হয়নি. কি অপসারণের সম্পর্কে? আমি করতে চান, উদাহরণস্বরূপ, সংখ্যা অপসারণ 34 বা 55, আমি, কোড একই ধরনের হতে পারে কিন্তু আমি এক বা দুই ধাপ প্রয়োজন যাচ্ছি. নতুন কি কারণ? আমি শেষে কেউ অপসারণ, সংখ্যা মত 55 এবং তারপর 34, কি আমি যে কি পরিবর্তন হয়েছে? আমি evict-- না আছে আপনার নাম আবার কি? 

শ্রোতা: জ্যাক. 

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

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

তাই তালিকা মাথা যখন , যার হাত এখন পরিবর্তন প্রয়োজন মুছে ফেলা? আপনার নাম আবার কি? 

শ্রোতা: ক্রিস্টিন. 

ডেভিড জে MALAN: আমি ভয়াবহ আছি নামের এ, দৃশ্যত. তাই Christine এবং গেব, যার হাত পরিবর্তন করতে হবে আমরা ক্রিস্টিন অপসারণ করার চেষ্টা করুন, ছবি থেকে 5 নম্বর? ঠিক আছে, তাই এর গেব না দেওয়া. গেব নির্দেশ করে যাচ্ছে, সম্ভবতঃ, সংখ্যা 9 এ. কিন্তু পরের কি করা উচিত? শ্রোতা: ক্রিস্টিন উচিত [শ্রবণাতীত] নাল হতে. ডেভিড জে MALAN: ঠিক আছে, আমরা সম্ভবত উচিত make-- আমি কোথাও "নাল" শোনা. শ্রোতা: শূন্য এবং তার বিনামূল্যে. ডেভিড জে MALAN: কি শূন্য? শ্রোতা: শূন্য এবং তার বিনামূল্যে. ডেভিড জে MALAN: শূন্য এবং তার বিনামূল্যে. তাই এই খুবই সহজ. এবং এটি আপনি এখন কেমন আছেন যে নিখুঁত এর অন্তর্গত, সেখানে না দাঁড়িয়ে. আপনি চলেছি কারণ তালিকা থেকে decoupled. আপনি কার্যকরভাবে হয়েছে তালিকা থেকে এতিম. এবং তাই আমরা ভাল এখন বিনামূল্যে কল ছিল ক্রিস্টিন যে মেমরি ফেরত দিতে. অন্যথা প্রতিটি সময় আমরা তালিকা থেকে একটি নোড মুছে দিন আমরা তালিকা তৈরি করা হতে পারে খাটো, কিন্তু আসলে কমে না মেমরি আকার. এবং তাই আমরা যোগ রাখা এবং , যোগ তালিকায় কিছু যোগ, আমার কম্পিউটার ধীর পেতে পারে এবং ধীর এবং ধীর, আমি চলমান আউট করছি, কারণ মেমরি, আমি আসলে না, এমনকি যদি ক্রিস্টিন এর বাইট ব্যবহার করে মেমরি আর. 

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

[সাধুবাদ] 

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

এক, এবং আমরা এটা বলেন আগে, চলমান কি একটি জন্য অনুসন্ধান সময় বড় হে শর্তাবলী তালিকা? কি চলমান একটি ঊর্ধ্ব আবদ্ধ একটি লিঙ্ক তালিকা অনুসন্ধান সময় এখানে আমাদের স্বেচ্ছাসেবকদের দ্বারা হিসাবে প্রয়োগ? এটা বড় হে n র, রৈখিক না. , সবচেয়ে খারাপ ক্ষেত্রে, কারণ উপাদান, 55 মত, আমরা যেখানে হতে পারে জন্য খুঁজছেন হতে পারে জ্যাক, শেষে সব উপায়. এবং দুর্ভাগ্যবশত, একটি অ্যারের অসদৃশ আমরা এই সময় অভিনব পেতে পারে না. আমাদের মানুষের সব ছিল, যদিও ছোট উপাদান, 5 থেকে সাজানো, বড় উপাদান পর্যন্ত সব পথ, 55, যে সাধারণত একটি ভাল জিনিস. কিন্তু যে ধৃষ্টতা কি আর আমাদের করার অনুমতি দেয়? শ্রোতা: [শ্রবণাতীত] ডেভিড জে MALAN: আবার বলুন? শ্রোতা: র্যান্ডম এক্সেস. ডেভিড জে MALAN: র্যান্ডম এক্সেস. এবং ঘুরে যে কোন আমরা করতে পারেন এর মানে হল আর, দুর্বল শূন্য, অনুভূতি ব্যবহার বাইনারি ব্যবহার করে এবং স্পষ্টতা অনুসন্ধান ও বিভক্ত করা এবং জেতা. কারণ যদিও আমরা মানুষের সম্ভবত পারা অ্যান্ডি বা খৃস্টান ছিল দেখতে প্রায় তালিকা মাঝখানে, আমরা কেবল একটি হিসাবে জানি যে তালিকা skimming দ্বারা কম্পিউটার খুব শুরুতে থেকে. তাই আমরা যে র্যান্ডম অ্যাক্সেস আপনি. 

N এর এত বড় হে এখন উপরের হয় আমাদের অনুসন্ধান সময় আবদ্ধ. কি আমাদের অনুসন্ধান ওমেগা সম্পর্কে? নিম্ন পরিসর অনুসন্ধানের কি এই তালিকায় কিছু সংখ্যক জন্য? শ্রোতা: [শ্রবণাতীত] ডেভিড জে MALAN: আবার বলুন? শ্রোতা: এক. ডেভিড জে MALAN: এক. তাই সময় ধ্রুবক. সেরা ক্ষেত্রে, Christine হয় প্রকৃতপক্ষে তালিকা প্রারম্ভে. এবং আমরা খুঁজছি 5 নম্বর, তাই আমরা তার পাওয়া গেছে. তাই কোন বড় চুক্তি. কিন্তু সে সময়ে হবে না এর এই ক্ষেত্রে তালিকার শুরুতে. ভালো কিছু সম্পর্কে কি মুছবেন? আপনি একটি উপাদান মুছে ফেলতে কি চান? কি সর্বোচ্চ সীমা এবং নিম্ন আবদ্ধ একটি লিঙ্ক থেকে কিছু মুছে ফেলার উপর তালিকা? শ্রোতা: [শ্রবণাতীত] ডেভিড জে MALAN: আবার বলুন? শ্রোতা: এন. ডেভিড জে MALAN: n হল আবদ্ধ প্রকৃতপক্ষে উপরের. সবচেয়ে খারাপ ক্ষেত্রে আমরা চেষ্টা করুন, কারণ আমরা শুধু ভালো, জ্যাক মুছে দিন. তিনি শেষে সব উপায়. সব সময় প্রবেশ করুন আমাদের লাগে, বা n ধাপ তাকে খুঁজে পেতে. সুতরাং যে একটি ঊর্ধ্ব আবদ্ধ. এটা নিশ্চিত, রৈখিক না. এবং সেরা ক্ষেত্রে সময় চলমান, বা সেরা ক্ষেত্রে নিম্ন সীমার ধ্রুব সময় হবে. হয়তো আমরা মুছে ফেলতে চেষ্টা করুন, কারণ ক্রিস্টিন, এবং আমরা পেতে ভাগ্যবান তিনি শুরুতে আছে. এখন একটি মিনিট অপেক্ষা করুন. গেব, শুরুতে ছিল এবং আমরা গেব আপডেট ছিল. সুতরাং যে মাত্র এক ধাপ ছিল না. সুতরাং এটি প্রকৃতপক্ষে ধ্রুবক সময়, সেরা ক্ষেত্রে, ক্ষুদ্রতম উপাদান মুছে ফেলার জন্য? এটি দুটি হতে পারে, যদিও এটা হয়, কোড তিনটি, অথবা এমনকি 100 লাইন, এটি একই সংখ্যা যদি না কিছু লুপ লাইন,, এবং আকার স্বাধীন তালিকার একেবারে. উপাদান মুছে ফেলার পদ্ধতি তালিকার শুরুতে, আমরা মোকাবেলা করতে হবে, এমনকি যদি গেব, এখনও সময় ধ্রুবক. 

সুতরাং এই একটি মত মনে হয় পিছন দিকে বিশাল পদক্ষেপ. এবং সময় কি একটি বর্জ্য , যদি এক সপ্তাহ এবং সপ্তাহে শূন্য আমরা না শুধুমাত্র ছিল pseudocode হয় কোড কিন্তু প্রকৃত কোড লগ যে কিছু বাস্তবায়ন বেস এন, অথবা লগ ইন করুন, বরং, n এর, বেস 2, তার চলমান সময় পদ. তাই নরক আমরা শুরু করতে চান কেন একটি লিঙ্ক তালিকা মত ব্যবহার করে? হ্যাঁ. 

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

আমরা স্থান খরচ করছেন. কি অর্থে একটি লিঙ্ক করা আরো ব্যয়বহুল তালিকা একটি অ্যারের তুলনায় স্থান পদ? যেখানে অতিরিক্ত স্থান থেকে আসছে? হ্যাঁ? 

শ্রোতা: [শ্রবণাতীত] পয়েন্টার. 

ডেভিড জে MALAN: হ্যাঁ, আমরা এছাড়াও পয়েন্টার আছে. তাই এই minorly বিরক্তিকর যে আর am আমি কোন int সংরক্ষণ কোন int প্রতিনিধিত্ব করতে. আমি কোন int এবং একটি সংরক্ষণ করছি এছাড়াও যা 32 বিট পয়েন্টার,. তাই আমি আক্ষরিক দ্বিগুনের করছি স্থান পরিমাণ জড়িত. সুতরাং যে একটি ট্রেড বন্ধ, কিন্তু যে কোন int ক্ষেত্রে এর. , আপনি কোন int সংরক্ষণ করছি না যে ধরুন কিন্তু এই আয়তক্ষেত্র প্রতিটি অনুমান বা এই মানুষের প্রতিটি প্রতিনিধিত্বমূলক ছিল একটি শব্দ, একটি ইংরেজি শব্দ যে পাঁচটি অক্ষর, 10 হতে পারে অক্ষর, এমনকি আরো. তারপর শুধু আরো 32 বিট যোগ একটি বড় চুক্তি কম হতে পারে. 

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