1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [القسم 6: أقل راحة]

2
00:00:02,730 --> 00:00:05,040
[نيت Hardison] [جامعة هارفارد]

3
00:00:05,040 --> 00:00:07,320
[هذا CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
حسنا. مرحبا بكم في القسم 6.

5
00:00:11,840 --> 00:00:14,690
هذا الاسبوع، ونحن ذاهبون الى الحديث عن هياكل البيانات في القسم،

6
00:00:14,690 --> 00:00:19,780
في المقام الأول لأن المشكلة هذا الاسبوع تعيين على spellr

7
00:00:19,780 --> 00:00:24,410
لا في مجمله مجموعة من مختلف استكشاف بنية البيانات.

8
00:00:24,410 --> 00:00:26,520
هناك مجموعة من الطرق المختلفة التي يمكن أن تذهب مع مجموعة المشكلة،

9
00:00:26,520 --> 00:00:31,570
وهياكل أكثر البيانات التي يعرفون، أكثر الأشياء باردة يمكنك القيام به.

10
00:00:31,570 --> 00:00:34,990
>> لذلك دعونا نبدأ. أولا نحن ذاهبون الى الحديث عن المداخن،

11
00:00:34,990 --> 00:00:37,530
المكدس والطابور هياكل البيانات التي نحن بصدد الحديث عنها.

12
00:00:37,530 --> 00:00:40,560
مداخن وطوابير هي مفيدة حقا عندما نبدأ بالحديث عن الرسوم البيانية،

13
00:00:40,560 --> 00:00:44,390
الذي نحن لن تفعل الكثير من الحق الآن.

14
00:00:44,390 --> 00:00:52,820
ولكنهم حقا جيدة لفهم واحدة من هياكل البيانات الأساسية كبيرة من CS.

15
00:00:52,820 --> 00:00:54,880
وصف المشكلة في مواصفات مجموعة،

16
00:00:54,880 --> 00:00:59,260
إذا كنت سحب عنه، كما يتحدث عن مداخن أقرب إلى

17
00:00:59,260 --> 00:01:05,239
كومة من صواني الطعام التي لديك في الكافتيريا في قاعات الطعام

18
00:01:05,239 --> 00:01:09,680
حيث عندما يأتي الطعام والموظفين يضع الصواني تناول الطعام خارج المنزل بعد تنظيفها انهم لهم،

19
00:01:09,680 --> 00:01:12,000
أنها رصها واحدة فوق الأخرى.

20
00:01:12,000 --> 00:01:15,050
وبعد ذلك عندما تأتي في الأطفال للحصول على الغذاء،

21
00:01:15,050 --> 00:01:19,490
انهم سحب قبالة الصواني، أولا رأس واحد، ثم أقل من واحد، ثم أن أقل من واحد.

22
00:01:19,490 --> 00:01:25,190
لذلك، في الواقع، درج الأولى التي تناول الطعام موظفي اخماد هو آخر واحد أن يحصل على اقلعت.

23
00:01:25,190 --> 00:01:32,330
آخر واحد أن موظفي وضعت على الطعام هو أول واحد أن يحصل على اقلعت لتناول العشاء.

24
00:01:32,330 --> 00:01:38,100
في مجموعة المواصفات المشكلة، والتي يمكنك تحميل إذا كنت لم تقم بذلك بالفعل،

25
00:01:38,100 --> 00:01:46,730
نتحدث عن النمذجة والبيانات stucture مكدس باستخدام هذا النوع من البنية.

26
00:01:46,730 --> 00:01:51,070
>> ذلك ما لدينا هنا، وهذا هو على غرار ما قدم في المحاضرة،

27
00:01:51,070 --> 00:01:58,120
إلا في محاضرة قدمنا ​​هذا مع رجات بدلا من حرف S *.

28
00:01:58,120 --> 00:02:06,250
هذه ستكون كومة يقوم بتخزين ما؟

29
00:02:06,250 --> 00:02:09,009
دانيال؟ ما نحن في تخزين هذا المكدس؟

30
00:02:09,009 --> 00:02:15,260
[دانيال] سلاسل؟ نحن >> تخزين السلاسل في هذا المكدس، بالضبط.

31
00:02:15,260 --> 00:02:20,950
كل ما عليك أن يكون من أجل خلق كومة عبارة عن صفيف

32
00:02:20,950 --> 00:02:23,920
قدرة خاصة، وهو في هذه الحالة،

33
00:02:23,920 --> 00:02:28,020
القدرة سيكون في كل مباراة دولية لأنها ثابتة.

34
00:02:28,020 --> 00:02:36,340
ثم بالإضافة إلى مجموعة، كل ما نحتاج إليه هو لتتبع الحجم الحالي للمجموعة.

35
00:02:36,340 --> 00:02:38,980
شيء واحد أن نلاحظ هنا أن هذا النوع من بارد

36
00:02:38,980 --> 00:02:47,060
هو أننا بصدد إنشاء بنية البيانات مكدسة فوق بنية بيانات أخرى، الصفيف.

37
00:02:47,060 --> 00:02:50,110
هناك طرق مختلفة لتنفيذ رزمة.

38
00:02:50,110 --> 00:02:54,250
ونحن لن نفعل ذلك تماما حتى الآن، ولكن نأمل بعد القيام المشاكل المرتبطة قائمة،

39
00:02:54,250 --> 00:03:00,520
سترى كيف يمكنك بسهولة تنفيذ كومة على رأس قائمة مرتبطة أيضا.

40
00:03:00,520 --> 00:03:02,640
لكن في الوقت الراهن، سنقوم التمسك صفائف.

41
00:03:02,640 --> 00:03:06,350
ذلك مرة أخرى، كل ما نحتاجه هو مجموعة ونحن بحاجة فقط لتتبع حجم الصفيف.

42
00:03:06,350 --> 00:03:09,850
[سام] عذرا، لماذا هو ان قلت كومة من على قمة السلاسل؟

43
00:03:09,850 --> 00:03:13,440
بالنسبة لي يبدو لك أن السلاسل داخل المكدس.

44
00:03:13,440 --> 00:03:16,790
[Hardison] نعم. نحن نخلق، ونحن مع بنيتنا بيانات مجموعة -

45
00:03:16,790 --> 00:03:22,130
هذا هو السؤال الكبير. وبالتالي فإن السؤال هو لماذا، للناس الذين يشاهدون هذا عبر الإنترنت،

46
00:03:22,130 --> 00:03:24,140
لماذا نقول أن على رأس كومة من السلاسل،

47
00:03:24,140 --> 00:03:27,990
لأن هنا يبدو أن السلاسل داخل كومة؟

48
00:03:27,990 --> 00:03:31,050
وهو تماما في القضية.

49
00:03:31,050 --> 00:03:34,660
ما كان يشير إلى أن لدينا بنية بيانات صفيف.

50
00:03:34,660 --> 00:03:39,290
لدينا مجموعة من شار * S، هذه مجموعة من السلاسل،

51
00:03:39,290 --> 00:03:45,300
ونحن نذهب لإضافة إلى أنه من أجل إنشاء بنية البيانات مكدسة.

52
00:03:45,300 --> 00:03:48,620
>> حتى كومة قليلا أكثر تعقيدا من صفيف.

53
00:03:48,620 --> 00:03:51,890
يمكننا استخدام مجموعة لبناء المكدس.

54
00:03:51,890 --> 00:03:55,810
ولهذا نقول إن حيث تم بناء مكدس على رأس مجموعة.

55
00:03:55,810 --> 00:04:02,510
وبالمثل، كما قلت سابقا، يمكننا أن نبني كومة على رأس قائمة مرتبطة.

56
00:04:02,510 --> 00:04:04,960
بدلا من استخدام مجموعة عناصر لعقد لدينا،

57
00:04:04,960 --> 00:04:10,070
يمكن أن نستخدم قائمة مرتبطة بعقد لدينا عناصر وبناء كومة حول ذلك.

58
00:04:10,070 --> 00:04:12,420
دعونا المشي من خلال بضعة أمثلة، والنظر في بعض التعليمات البرمجية،

59
00:04:12,420 --> 00:04:14,960
لمعرفة ما يحدث في الواقع هنا.

60
00:04:14,960 --> 00:04:23,400
على اليسار، لقد القيت I أسفل كومة ما أن البنية ستبدو في الذاكرة

61
00:04:23,400 --> 00:04:28,330
إذا تم تعريف # القدرة على أن تكون الأربعة.

62
00:04:28,330 --> 00:04:33,490
لدينا لدينا أربعة عنصر الصفيف * شار.

63
00:04:33,490 --> 00:04:38,110
لدينا سلاسل [0]، سلاسل [1]، سلاسل [2]، سلاسل [3]،

64
00:04:38,110 --> 00:04:43,800
ثم أن الفضاء الماضي لعدد صحيح حجمنا.

65
00:04:43,800 --> 00:04:46,270
هل هذا معقول؟ حسنا.

66
00:04:46,270 --> 00:04:48,790
هذا هو ما يحدث إذا ما أقوم به على الحق،

67
00:04:48,790 --> 00:04:55,790
الذي سيكون قانون بلدي، هو مجرد اعلان البنية، والبنية مكدسة دعا ق.

68
00:04:55,790 --> 00:05:01,270
هذا هو ما نحصل عليه. ينص عليها هذا الأثر في الذاكرة.

69
00:05:01,270 --> 00:05:05,590
السؤال الأول هنا هو ما هي محتويات هذه البنية المكدس؟

70
00:05:05,590 --> 00:05:09,250
الآن انهم لا شيء، لكنها ليست شيئا على الإطلاق.

71
00:05:09,250 --> 00:05:13,300
انهم مثل هذا النوع من القمامة. ليس لدينا أي فكرة ما هو فيها.

72
00:05:13,300 --> 00:05:17,000
عندما نعلن ق مكدس، نحن فقط أن رمي أسفل على رأس الذاكرة.

73
00:05:17,000 --> 00:05:19,840
انه نوع من مثل اعلان الباحث الأول وليس تهيئة ذلك.

74
00:05:19,840 --> 00:05:21,730
كنت لا تعرف ما هو في هناك. يمكنك أن تقرأ ما في هناك،

75
00:05:21,730 --> 00:05:27,690
ولكن قد لا يكون سوبر مفيدة.

76
00:05:27,690 --> 00:05:32,680
شيء واحد كنت تريد أن نتذكر دائما القيام به هو تهيئة كل ما يحتاج إلى تهيئة.

77
00:05:32,680 --> 00:05:35,820
في هذه الحالة، ونحن في طريقنا لتهيئة حجم لتكون صفر،

78
00:05:35,820 --> 00:05:39,960
لأن ذلك سوف تتحول إلى أن تكون مهمة جدا بالنسبة لنا.

79
00:05:39,960 --> 00:05:43,450
يمكننا المضي قدما وتهيئة جميع المؤشرات، وجميع ليالي * شار،

80
00:05:43,450 --> 00:05:49,670
أن يكون بعض القيمة مفهومة، ربما فارغة.

81
00:05:49,670 --> 00:05:58,270
ولكنها ليست ضرورية تماما أن نفعل ذلك.

82
00:05:58,270 --> 00:06:04,200
>> الآن، عمليات الرئيسيان على أكوام هي؟

83
00:06:04,200 --> 00:06:07,610
تذكر أي شخص من محاضرة ما تفعله مع مداخن؟ نعم؟

84
00:06:07,610 --> 00:06:09,700
[ستيلا] دفع وظهرت؟ بالضبط >>.

85
00:06:09,700 --> 00:06:13,810
وظهرت دفع عمليات هي الرئيسيان على مداخن.

86
00:06:13,810 --> 00:06:17,060
وماذا تفعل دفعة؟ و>> يضع شيئا على الجزء العلوي

87
00:06:17,060 --> 00:06:19,300
من المكدس، ثم ظهرت خلعه.

88
00:06:19,300 --> 00:06:23,150
[Hardison] بالضبط. دفع ذلك يدفع شيئا على أعلى المكدس.

89
00:06:23,150 --> 00:06:27,700
انها مثل وضع الطعام موظفي صينية الطعام لأسفل على وصفة طبية.

90
00:06:27,700 --> 00:06:33,630
وظهرت تتخذ صينية الطعام الخروج من المكدس.

91
00:06:33,630 --> 00:06:36,460
دعونا المشي من خلال بضعة أمثلة على ما يحدث

92
00:06:36,460 --> 00:06:39,720
عندما كنا دفع الامور الى المكدس.

93
00:06:39,720 --> 00:06:45,110
إذا كنا لدفع سلسلة 'مرحبا' على كومة لدينا،

94
00:06:45,110 --> 00:06:49,760
هذا ما لدينا مخطط ستبدو الآن.

95
00:06:49,760 --> 00:06:53,410
انظر ماذا يحدث؟

96
00:06:53,410 --> 00:06:56,530
دفع نحن في العنصر الأول من الصفيف سلاسل لدينا

97
00:06:56,530 --> 00:07:01,420
ونحن نعول مرفوع لدينا أن يكون حجم 1.

98
00:07:01,420 --> 00:07:05,340
إذا كان الأمر كذلك ننظر إلى الفرق بين الشرائح اثنين، كان هنا 0، وهنا قبل الدفع.

99
00:07:05,340 --> 00:07:08,690
هنا بعد دفع.

100
00:07:08,690 --> 00:07:13,460
قبل دفع، بعد دفع.

101
00:07:13,460 --> 00:07:16,860
والآن لدينا عنصر واحد في المكدس لدينا.

102
00:07:16,860 --> 00:07:20,970
انها سلسلة "مرحبا"، وهذا كل شيء.

103
00:07:20,970 --> 00:07:24,440
كل شيء آخر في الصفيف، في مجموعة سلاسل لدينا، لا تزال القمامة.

104
00:07:24,440 --> 00:07:27,070
نحن لم تهيئة.

105
00:07:27,070 --> 00:07:29,410
دعونا نقول اننا دفع سلسلة أخرى على كومة لدينا.

106
00:07:29,410 --> 00:07:32,210
ونحن في طريقنا لدفع "العالم" على هذا الوقت.

107
00:07:32,210 --> 00:07:35,160
حتى تستطيع أن ترى "العالم" هنا يذهب على رأس "مرحبا"،

108
00:07:35,160 --> 00:07:40,040
والعدد يرتفع حجم إلى 2.

109
00:07:40,040 --> 00:07:44,520
الآن يمكننا دفع "CS50"، والتي سوف تذهب على رأس مرة أخرى.

110
00:07:44,520 --> 00:07:51,110
إذا عدنا، يمكنك أن ترى كيف أننا ندفع الأمور على أعلى المكدس.

111
00:07:51,110 --> 00:07:53,320
والآن نصل إلى موسيقى البوب.

112
00:07:53,320 --> 00:07:58,910
ماذا حدث عندما كنا برزت شيء الخروج من المكدس،؟

113
00:07:58,910 --> 00:08:01,540
أي شخص ترى الفرق؟ انها جميلة خفية.

114
00:08:01,540 --> 00:08:05,810
[طالب] حجم. نعم >>، تغيير الحجم.

115
00:08:05,810 --> 00:08:09,040
>> وماذا كان يتوقع منك أن تتغير؟

116
00:08:09,040 --> 00:08:14,280
[طالب] والسلاسل، أيضا. الحق >>. الجمل أيضا.

117
00:08:14,280 --> 00:08:17,110
تبين أنه عندما كنت أفعل ذلك بهذه الطريقة،

118
00:08:17,110 --> 00:08:21,960
لأننا لسنا نسخ العناصر في كومة لدينا،

119
00:08:21,960 --> 00:08:24,670
ونحن في الواقع لم يكن لديك لتفعل أي شيء، ونحن يمكن فقط استخدام حجم

120
00:08:24,670 --> 00:08:28,630
لتتبع عدد من الأمور في مجموعتنا

121
00:08:28,630 --> 00:08:33,780
بحيث أننا عندما البوب ​​مرة أخرى، ومرة ​​أخرى نحن فقط إنقاص حجمنا وصولا الى 1.

122
00:08:33,780 --> 00:08:39,440
ليس هناك حاجة للذهاب في الواقع أي شيء والكتابة.

123
00:08:39,440 --> 00:08:41,710
نوع من غير تقليدي.

124
00:08:41,710 --> 00:08:46,520
اتضح أننا عادة مجرد ترك الأمور وحدها لأنها أقل إعمل لدينا للقيام به.

125
00:08:46,520 --> 00:08:50,060
إذا لم يكن لدينا للعودة والكتابة شيء، ثم لماذا تفعل ذلك؟

126
00:08:50,060 --> 00:08:54,150
حتى عندما كنا البوب ​​قبالة مرتين من المكدس، كل ما يفعله هو إنقاص حجم بضع مرات.

127
00:08:54,150 --> 00:08:59,120
ومرة أخرى، وهذا هو فقط لأننا لسنا نسخ الأمور في كومة لدينا.

128
00:08:59,120 --> 00:09:01,320
نعم؟ المضي قدما.

129
00:09:01,320 --> 00:09:04,460
[طالبة، غير مفهومة] >> ثم ماذا يحدث عند دفع شيء مرة أخرى؟

130
00:09:04,460 --> 00:09:08,570
عند دفع شيء مرة أخرى، حيث أنها لا تذهب؟

131
00:09:08,570 --> 00:09:12,390
حيث أنها لا تذهب، باسل؟ إلى سلاسل >> [1]؟ الحق >>.

132
00:09:12,390 --> 00:09:14,530
لماذا لا تذهب إلى سلاسل [3]؟

133
00:09:14,530 --> 00:09:19,410
[باسل] لأنه نسي أن هناك أي شيء في سلاسل [1] و [2]؟

134
00:09:19,410 --> 00:09:24,040
[Hardison] بالضبط. مكدس لدينا، أساسا، "نسيت" انها تحتجز إلى أي شيء

135
00:09:24,040 --> 00:09:29,480
في سلاسل [1] أو سلاسل [2]، وذلك عندما ندفع "WOOT"،

136
00:09:29,480 --> 00:09:36,670
فإنه يضع مجرد أن في عنصر في السلاسل [1].

137
00:09:36,670 --> 00:09:41,590
هل هناك أي أسئلة عن كيفية عمل ذلك، على المستوى الأساسي؟

138
00:09:41,590 --> 00:09:45,160
[سام] لذلك هذه ليست بأي شكل من الأشكال الحيوية، من حيث كمية

139
00:09:45,160 --> 00:09:47,620
أو من حيث حجم المكدس؟

140
00:09:47,620 --> 00:09:56,750
[Hardison] بالضبط. هذا هو - نقطة هو أن هذا لم يكن كومة تنموا بشكل حيوي.

141
00:09:56,750 --> 00:10:02,850
هذا هو كومة التي يمكن أن تعقد، في معظم، وأربعة ليالي * شار، في أكثر الأشياء الأربعة.

142
00:10:02,850 --> 00:10:07,580
لو كنا في محاولة لدفع شيء الخامسة، ما رأيك يجب أن يحدث؟

143
00:10:07,580 --> 00:10:11,870
[طلاب، غير مفهومة]

144
00:10:11,870 --> 00:10:14,600
[Hardison] بالضبط. هناك عدد من الأشياء التي يمكن أن يحدث.

145
00:10:14,600 --> 00:10:19,330
يمكن أن SEG ربما خطأ، اعتمادا على ما كنا -

146
00:10:19,330 --> 00:10:22,530
بالضبط كيف كنا تنفيذ الخلفية.

147
00:10:22,530 --> 00:10:31,740
يمكن أن الكتابة. يمكن أن يكون هذا تجاوز سعة المخزن المؤقت الذي تحدثنا عنه في الفصل.

148
00:10:31,740 --> 00:10:35,240
ماذا سيكون الشيء الأكثر وضوحا التي قد تكون الكتابة

149
00:10:35,240 --> 00:10:42,370
إذا حاولنا أن يدفع شيئا إضافيا على كومة لدينا؟

150
00:10:42,370 --> 00:10:44,550
ذكر ذلك لك وتجاوز سعة المخزن المؤقت.

151
00:10:44,550 --> 00:10:47,870
ماذا يمكن أن يكون الشيء الذي سوف تحصل على كتب أو داس على

152
00:10:47,870 --> 00:10:52,320
إذا فاض علينا بطريق الخطأ من قبل في محاولة لدفع شيء إضافي؟

153
00:10:52,320 --> 00:10:54,730
[دانيال، غير مفهومة] >> الممكنة.

154
00:10:54,730 --> 00:10:58,440
ولكن في البداية، قد يحدث ما؟ ماذا لو حاولنا لدفع شيء الرابعة؟

155
00:10:58,440 --> 00:11:06,220
قد الكتابة فوق الحجم، على الأقل مع هذا المخطط الذاكرة التي لدينا.

156
00:11:06,220 --> 00:11:10,880
>> في مشكلة مواصفات مجموعة، وهو ما نحن في طريقنا إلى أن تنفيذ اليوم،

157
00:11:10,880 --> 00:11:16,030
ما نريد أن نفعله هو العودة فقط كاذبة.

158
00:11:16,030 --> 00:11:20,030
طريقة الدفع لدينا هو الذهاب لإرجاع قيمة منطقية،

159
00:11:20,030 --> 00:11:22,920
وسوف أن يكون صحيحا قيمة منطقية إذا نجح الضغط

160
00:11:22,920 --> 00:11:29,730
وكاذبة إذا لم نتمكن من دفع أي شيء أكثر لأن مكدس ممتلئ.

161
00:11:29,730 --> 00:11:33,620
دعونا من خلال المشي قليلا من التعليمات البرمجية في الوقت الحالي.

162
00:11:33,620 --> 00:11:36,400
وهنا لدينا وظيفة دفعة.

163
00:11:36,400 --> 00:11:40,380
وظيفتنا الضغط من أجل كومة سوف تتخذ في سلسلة لوضعه على المكدس.

164
00:11:40,380 --> 00:11:45,820
انه سيكون من العودة الحقيقية إذا تم دفع بنجاح سلسلة

165
00:11:45,820 --> 00:11:51,820
على خلاف ذلك مكدس وكاذبة.

166
00:11:51,820 --> 00:11:59,740
قد أي اقتراحات بشأن ما يكون أمرا جيدا أول من يفعل هنا؟

167
00:11:59,740 --> 00:12:20,630
[سام] إذا كان حجم يساوي القدرة ثم العودة كاذبة؟

168
00:12:20,630 --> 00:12:23,320
[Hardison] البنغو. لطيفة العمل.

169
00:12:23,320 --> 00:12:26,310
إذا كان حجم هو القدرة، ونحن في طريقنا للعودة كاذبة.

170
00:12:26,310 --> 00:12:29,270
لا يمكننا وضع أي شيء في كومة أكثر لدينا.

171
00:12:29,270 --> 00:12:36,900
خلاف ذلك، ونحن نريد أن نضع شيئا على الجزء العلوي من المكدس.

172
00:12:36,900 --> 00:12:41,670
ما هو "أعلى المكدس،" في البداية؟

173
00:12:41,670 --> 00:12:43,650
[دانيال] ضخم 0؟ الحجم >> 0.

174
00:12:43,650 --> 00:12:49,990
ما هو الجزء العلوي من المكدس بعد هناك شيء واحد في المكدس؟ ميسي، هل تعرف؟

175
00:12:49,990 --> 00:12:52,720
[ميسي] واحدة. الحجم >> هي واحدة، بالضبط. عليك أن تبقي إضافة إلى حجم،

176
00:12:52,720 --> 00:13:01,690
وفي كل مرة كنت في وضع العنصر الجديد في حجم المؤشر في الصفيف.

177
00:13:01,690 --> 00:13:05,470
يمكننا أن نفعل ذلك مع هذا النوع من الخطوط الملاحية المنتظمة واحد، إذا كان هذا الأمر يبدو معقولا تماما.

178
00:13:05,470 --> 00:13:11,910
لذلك نحن لدينا قد حصلت على مجموعة السلاسل، ونحن في طريقنا للوصول إليه في مؤشر الحجم،

179
00:13:11,910 --> 00:13:14,780
ونحن في طريقنا فقط لتخزين * لدينا في شار هناك.

180
00:13:14,780 --> 00:13:19,340
لاحظ كيف لم يكن هناك نسخ سلسلة يجري في هنا،

181
00:13:19,340 --> 00:13:29,680
لا التخصيص الحيوي من الذاكرة؟

182
00:13:29,680 --> 00:13:34,440
ومن ثم جلب ميسي حتى ما لدينا الآن القيام به،

183
00:13:34,440 --> 00:13:40,570
لأننا تخزين السلسلة في المكان المناسب في الصفيف،

184
00:13:40,570 --> 00:13:49,230
وقالت إن كان علينا أن زيادة حجم واحد بحيث نحن على استعداد لدفع المقبل.

185
00:13:49,230 --> 00:13:53,950
لذلك يمكننا أن نفعل ذلك مع s.size + +.

186
00:13:53,950 --> 00:13:59,330
عند هذه النقطة، لقد دفعت نحن في مجموعتنا. ما هو آخر شيء يتعين علينا القيام به؟

187
00:13:59,330 --> 00:14:10,110
[طالب] العودة الحقيقية. العودة الحقيقية >>.

188
00:14:10,110 --> 00:14:14,690
حتى انها بسيطة جدا، رمز بسيط جدا. ليس كثيرا.

189
00:14:14,690 --> 00:14:17,070
مرة واحدة لقد كنت ملفوفة حول رأسك كيف يعمل المكدس،

190
00:14:17,070 --> 00:14:21,910
هذا هو بسيط جدا لتنفيذ.

191
00:14:21,910 --> 00:14:26,390
>> الآن، الجزء التالي من هذا وظهرت سلسلة الخروج من المكدس.

192
00:14:26,390 --> 00:14:29,410
انا ذاهب الى ان نعطيكم بعض اللاعبين الوقت للعمل على هذا قليلا قليلا.

193
00:14:29,410 --> 00:14:34,320
انها اساسا تقريبا عكس ما فعلناه هنا في الدفع.

194
00:14:34,320 --> 00:14:38,510
ما قمت به هو في الواقع - عفوا.

195
00:14:38,510 --> 00:14:48,160
لقد تمهيد بي الأمر إلى الأجهزة أكثر من هنا، وفي الأجهزة،

196
00:14:48,160 --> 00:14:53,600
لقد سحبت عن المشكلة إنشاء 5 المواصفات.

197
00:14:53,600 --> 00:15:02,560
إذا كنا تكبير هنا، يمكننا أن نرى أنا في cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
لقد قمت بتحميل هذا الرمز أن الرجال وهو موجود هنا، section6.zip؟

199
00:15:08,590 --> 00:15:15,030
حسنا. إذا لم تكن قد فعلت ذلك، هل هذا الحق الآن، بسرعة حقا.

200
00:15:15,030 --> 00:15:22,130
سوف أفعل ذلك في إطار المحطة الطرفية بلدي.

201
00:15:22,130 --> 00:15:25,090
فعلت فعلا هنا. نعم.

202
00:15:25,090 --> 00:15:34,730
نعم، وسام؟ >> لدي سؤال حول لماذا قلت s.string لشرائح SIZE = شارع؟

203
00:15:34,730 --> 00:15:42,910
ما هو شارع؟ والتي حددت في مكان ما من قبل، أو - أوه، في شارع شار *؟

204
00:15:42,910 --> 00:15:47,160
[Hardison] نعم، بالضبط. هو أن الحجة. >> أوه، حسنا. آسف.

205
00:15:47,160 --> 00:15:49,470
[Hardison] نحن تحديد السلسلة لدفع فيها

206
00:15:49,470 --> 00:15:55,220
كان السؤال الأخرى التي قد تأتي لأننا لم نتحدث حقا عن هنا

207
00:15:55,220 --> 00:15:58,810
اتخذنا من المسلم به أن هذا كان لدينا متغير يسمى ق

208
00:15:58,810 --> 00:16:02,710
كان ذلك في نطاق والوصول إلينا.

209
00:16:02,710 --> 00:16:06,960
اتخذنا من المسلم به أن هذا كان هذا البنية بنية تخزين العناصر.

210
00:16:06,960 --> 00:16:08,930
يبحث ذلك مرة أخرى في دفع هذا الرمز،

211
00:16:08,930 --> 00:16:13,450
يمكنك أن ترى أن نقوم به مع الاشياء التي حصلت على هذه السلسلة صدر في

212
00:16:13,450 --> 00:16:19,210
ولكن بعد ذلك فجأة، ونحن الحصول على s.size، مثل، أين تأتي من؟

213
00:16:19,210 --> 00:16:23,020
في التعليمات البرمجية التي نحن في طريقنا للبحث في الأرشيف في القسم

214
00:16:23,020 --> 00:16:27,100
ومن ثم الاشياء التي عليك أن تفعل في مشكلتك مجموعات،

215
00:16:27,100 --> 00:16:32,440
لقد حققنا مكدس لدينا البنية متغير عمومي

216
00:16:32,440 --> 00:16:36,380
حتى نتمكن من الحصول على وظائف في مختلف لدينا جميع

217
00:16:36,380 --> 00:16:40,630
دون الحاجة إلى تمرير يدويا وتمريرها حول بالرجوع،

218
00:16:40,630 --> 00:16:44,870
تفعل كل هذا النوع من الاشياء لذلك.

219
00:16:44,870 --> 00:16:52,280
نحن الغش قليلا، اذا صح التعبير، لجعل الامور أجمل.

220
00:16:52,280 --> 00:16:57,430
وهذا شيء نقوم به هنا لأنه للمتعة، وأنه من الأسهل.

221
00:16:57,430 --> 00:17:02,800
في كثير من الأحيان، سترى الناس هذا إن كان لديهم بنية بيانات كبيرة

222
00:17:02,800 --> 00:17:07,750
يجري تشغيلها على أن داخل البرنامج.

223
00:17:07,750 --> 00:17:09,560
>> دعونا نعود الى الجهاز.

224
00:17:09,560 --> 00:17:15,240
لم يحصل الجميع بنجاح section6.zip؟

225
00:17:15,240 --> 00:17:20,440
الجميع فك الضغط عن الملف باستخدام section6.zip بفك؟

226
00:17:20,440 --> 00:17:27,200
إذا ذهبت إلى الدليل 6 القسم -

227
00:17:27,200 --> 00:17:29,220
آآآه، في كل مكان -

228
00:17:29,220 --> 00:17:32,840
وأنت ما في قائمة هنا، سترى أن كنت قد حصلت على ثلاثة مختلفة. ملفات ج.

229
00:17:32,840 --> 00:17:38,350
كنت قد حصلت على قائمة الانتظار، وSLL، وهو منفردة مرتبطة القائمة، وعلى كومة.

230
00:17:38,350 --> 00:17:44,600
إذا كنت تفتح stack.c،

231
00:17:44,600 --> 00:17:47,330
يمكنك أن ترى أن لدينا هذه البنية محددة بالنسبة لنا،

232
00:17:47,330 --> 00:17:51,330
البنية الدقيقة التي تحدثنا عنها في مجرد الشرائح.

233
00:17:51,330 --> 00:17:56,340
لقد وصلنا لدينا متغير عالمي لمكدس،

234
00:17:56,340 --> 00:18:00,110
لدينا لدينا وظيفة دفع،

235
00:18:00,110 --> 00:18:04,230
ثم لدينا لدينا وظيفة البوب.

236
00:18:04,230 --> 00:18:08,320
سوف أضع رمز لدفع احتياطية على الشريحة هنا،

237
00:18:08,320 --> 00:18:10,660
ولكن ما أود يا رفاق القيام به هو، بكل ما أوتيت من قدرتك،

238
00:18:10,660 --> 00:18:13,790
اذهب وتنفيذ وظيفة البوب.

239
00:18:13,790 --> 00:18:18,480
بمجرد تنفيذ ذلك، يمكنك ترجمة هذا مع جعل مكدس،

240
00:18:18,480 --> 00:18:22,540
ثم قم بتشغيل الملف التنفيذي الناتجة مكدس،

241
00:18:22,540 --> 00:18:28,390
وسوف يتم تشغيل كل هذا لأسفل رمز اختبار هنا في هذا الرئيسي.

242
00:18:28,390 --> 00:18:31,060
ويعتني الرئيسي الواقع جعل عملية شد والبوب ​​المكالمات

243
00:18:31,060 --> 00:18:33,220
والتأكد من أن كل شيء يمر على ما يرام.

244
00:18:33,220 --> 00:18:36,820
فإنه أيضا تهيئة حجم مكدس هنا

245
00:18:36,820 --> 00:18:39,780
لذلك لم يكن لديك ما يدعو للقلق تهيئة ذلك.

246
00:18:39,780 --> 00:18:42,310
يمكنك أن تفترض انه تم تهيئته بشكل صحيح

247
00:18:42,310 --> 00:18:48,000
بحلول الوقت الذي يمكنك الوصول إليه في وظيفة البوب.

248
00:18:48,000 --> 00:18:53,530
هل هذا معقول؟

249
00:18:53,530 --> 00:19:00,100
حتى هنا نذهب. هناك رمز الدفع.

250
00:19:00,100 --> 00:19:13,210
سأعطيك الرجال 5 أو 10 دقائق.

251
00:19:13,210 --> 00:19:15,690
وإذا كان لديك أي أسئلة في هذه الأثناء بينما كنت الترميز،

252
00:19:15,690 --> 00:19:17,710
من فضلك اطلب منهم بصوت عال.

253
00:19:17,710 --> 00:19:23,080
إذا كان الأمر كذلك لتحصل على نقطة خلاف، فقط أسأل.

254
00:19:23,080 --> 00:19:26,030
اسمحوا لي أن أعرف، واسمحوا الجميع يعرف.

255
00:19:26,030 --> 00:19:28,160
العمل مع جارك أيضا.

256
00:19:28,160 --> 00:19:30,360
[دانيال] نحن فقط البوب ​​تنفيذ في الوقت الحالي؟ >> البوب ​​فقط.

257
00:19:30,360 --> 00:19:34,200
على الرغم من يمكنك نسخ تنفيذ دفعة إذا كنت ترغب

258
00:19:34,200 --> 00:19:37,780
بحيث اختبار العمل.

259
00:19:37,780 --> 00:19:41,940
لأنه من الصعب الحصول على أشياء لاختبار في -

260
00:19:41,940 --> 00:19:49,030
أو، فإنه من الصعب لاختبار ما ظهرت من كومة إذا لم يكن هناك أي شيء في كومة لتبدأ.

261
00:19:49,030 --> 00:19:55,250
>> ما هو البوب ​​المفترض أن تكون العودة؟ العنصر من الجزء العلوي من المكدس.

262
00:19:55,250 --> 00:20:01,260
أنه من المفترض أن تحصل على الخروج من عنصر أعلى المكدس

263
00:20:01,260 --> 00:20:05,780
وإنقاص ثم حجم المكدس،

264
00:20:05,780 --> 00:20:07,810
والآن كنت قد فقدت عنصر على القمة.

265
00:20:07,810 --> 00:20:11,420
ومن ثم يمكنك العودة العنصر على القمة.

266
00:20:11,420 --> 00:20:20,080
[طالبة، غير مفهومة]

267
00:20:20,080 --> 00:20:28,810
[Hardison] فماذا يحدث اذا كنت تفعل ذلك؟ [طالبة، غير مفهومة]

268
00:20:28,810 --> 00:20:34,000
ما يحدث هو ينتهي كنت الوصول إلى أي ربما

269
00:20:34,000 --> 00:20:37,350
لم يتم تهيئة أحد العناصر التي حتى الآن، لذلك لديك حساب

270
00:20:37,350 --> 00:20:39,990
من حيث العنصر الأخير هو إيقاف.

271
00:20:39,990 --> 00:20:46,260
حتى هنا، إذا لاحظت، في مسعى، ونحن في الوصول إلى سلاسل العنصر s.size

272
00:20:46,260 --> 00:20:48,560
لأنها مؤشر جديد.

273
00:20:48,560 --> 00:20:51,460
انها قمة جديدة من المكدس.

274
00:20:51,460 --> 00:21:01,100
في حين أنه في البوب، s.size ستكون المساحة المقبل،

275
00:21:01,100 --> 00:21:05,210
مساحة هذا على رأس جميع العناصر في الكدسة.

276
00:21:05,210 --> 00:21:10,050
ولذلك فإن العنصر الأكثر الأعلى ليست في s.size،

277
00:21:10,050 --> 00:21:14,930
ولكن بدلا من ذلك، فإنه من تحتها.

278
00:21:14,930 --> 00:21:19,640
>> والشيء الآخر القيام به عندما كنت - في البوب،

279
00:21:19,640 --> 00:21:22,030
ويجب عليك أن إنقاص الحجم.

280
00:21:22,030 --> 00:21:28,750
إذا كنت تتذكر مرة أخرى إلى الرسم البياني لدينا القليل هنا،

281
00:21:28,750 --> 00:21:30,980
حقا، الشيء الوحيد الذي شاهدناه يحدث عندما طالبنا البوب

282
00:21:30,980 --> 00:21:36,150
هو أن هذا الحجم تراجع، أولا إلى 2، ثم إلى 1.

283
00:21:36,150 --> 00:21:42,620
ثم عندما كنا دفعت عنصرا جديدا على، فإنه يذهب على الفور في المناسبة.

284
00:21:42,620 --> 00:21:49,610
[باسل] إذا كان s.size 2، ثم لن يذهب إلى العنصر 2،

285
00:21:49,610 --> 00:21:54,400
ثم كنت تريد أن عنصر البوب ​​قبالة؟

286
00:21:54,400 --> 00:21:59,510
إذا كان الأمر كذلك ذهبنا إلى - >> لذلك دعونا ننظر إلى هذا مرة أخرى.

287
00:21:59,510 --> 00:22:07,730
إذا كان هذا هو مكدس لدينا في هذه المرحلة

288
00:22:07,730 --> 00:22:12,130
وندعو البوب،

289
00:22:12,130 --> 00:22:16,150
في مؤشر الذي هو العنصر الأكثر الأعلى؟

290
00:22:16,150 --> 00:22:19,300
[باسل] في 2، لكنه سيحتاج لموسيقى البوب ​​3. الحق >>.

291
00:22:19,300 --> 00:22:24,220
ذلك حيث ان حجمنا هو 3، لكننا نريد لموسيقى البوب ​​العنصر في الفهرس 2.

292
00:22:24,220 --> 00:22:29,900
انها نموذجية من هذا النوع من جانب واحد من أن لديك مع الفهرسة الصفر من المصفوفات.

293
00:22:29,900 --> 00:22:36,430
لذلك كنت لا تريد لموسيقى البوب ​​العنصر الثالث، ولكن العنصر الثالث ليست في مؤشر 3.

294
00:22:36,430 --> 00:22:39,430
والسبب أننا لا نملك أن نفعل ذلك عندما 1 ناقص أننا ندفع

295
00:22:39,430 --> 00:22:44,120
ولأن في الوقت الحالي، لاحظت أن العنصر الأكثر الأعلى،

296
00:22:44,120 --> 00:22:47,600
إذا كان لنا أن دفع شيء آخر إلى المكدس في هذه المرحلة،

297
00:22:47,600 --> 00:22:50,360
ونحن نريد أن يدفع به في الفهرس 3.

298
00:22:50,360 --> 00:23:03,550
ومجرد أن ذلك يحدث لحجم ومؤشرات خط حتى عندما كنت تدفع.

299
00:23:03,550 --> 00:23:06,960
>> حصلت منظمة الصحة العالمية تنفيذ العمل المكدس؟

300
00:23:06,960 --> 00:23:09,690
كنت قد حصلت على كومة عمل واحد. هل لديك البوب ​​العمل حتى الآن؟

301
00:23:09,690 --> 00:23:11,890
[دانيال] نعم. أعتقد ذلك.

302
00:23:11,890 --> 00:23:14,610
تشغيل البرنامج >> وليس SEG يخطأ، انها طبع؟

303
00:23:14,610 --> 00:23:17,520
هل طباعة "النجاح" عند تشغيله؟

304
00:23:17,520 --> 00:23:22,630
نعم. جعل كومة، تشغيله، إذا كان بطباعة "النجاح"، ولا تذهب الطفرة،

305
00:23:22,630 --> 00:23:26,000
ثم كل شيء جيد.

306
00:23:26,000 --> 00:23:34,070
حسنا. دعونا نذهب الى الجهاز بسرعة حقا،

307
00:23:34,070 --> 00:23:46,100
وسنقوم من خلال هذا السير.

308
00:23:46,100 --> 00:23:51,110
إذا نظرنا إلى ما يحدث هنا مع البوب،

309
00:23:51,110 --> 00:23:55,220
دانيال، ما هو أول شيء قمت به؟

310
00:23:55,220 --> 00:23:58,850
[دانيال] إذا s.size أكبر من 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] حسنا. ولماذا فعلت ذلك؟

312
00:24:03,120 --> 00:24:05,610
[دانيال] للتأكد من أن هناك شيئا داخل المكدس.

313
00:24:05,610 --> 00:24:10,950
[Hardison] الحق. كنت ترغب في اختبار للتأكد من أن s.size أكبر من 0؛

314
00:24:10,950 --> 00:24:13,280
خلاف ذلك، ماذا تريد أن يحدث؟

315
00:24:13,280 --> 00:24:16,630
[دانيال] فارغة العودة؟ العودة >> فارغة، تماما.

316
00:24:16,630 --> 00:24:20,740
حتى إذا s.size أكبر من 0. ثم ما نحن فاعلون؟

317
00:24:20,740 --> 00:24:25,890
ماذا نفعل إذا كانت المجموعة ليست فارغة؟

318
00:24:25,890 --> 00:24:31,210
[ستيلا] أنت إنقاص حجم؟ يمكنك إنقاص >> الحجم، حسنا.

319
00:24:31,210 --> 00:24:34,440
فكيف فعلت ذلك؟ s.size >>--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] الكبرى. ثم ماذا فعلت؟

321
00:24:37,030 --> 00:24:44,140
[ستيلا] ثم قلت s.string العودة [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] الكبرى.

323
00:24:48,560 --> 00:24:51,940
إلا أن ترجع فارغة. نعم، وسام؟

324
00:24:51,940 --> 00:24:55,510
[سام] ولماذا لا يجب أن تكون s.size + 1؟

325
00:24:55,510 --> 00:24:58,430
[Hardison] زائد 1؟ نعم >>. حصلت >> ذلك.

326
00:24:58,430 --> 00:25:00,980
[سام] فكرت لأنك تتناولين 1 من،

327
00:25:00,980 --> 00:25:04,290
ثم كنت على وشك أن العودة ليست واحدة أنهم طلبوا.

328
00:25:04,290 --> 00:25:09,400
[Hardison] و كان هذا فقط ما كنا نتحدث عن هذه المسألة برمتها من 0 المؤشرات.

329
00:25:09,400 --> 00:25:11,380
حتى إذا كنا إعادة تكبير أكثر من هنا.

330
00:25:11,380 --> 00:25:15,650
إذا نظرنا إلى هذا الرجل هنا، يمكنك أن ترى أننا عندما البوب،

331
00:25:15,650 --> 00:25:19,340
نحن ظهرت العنصر في الفهرس 2.

332
00:25:19,340 --> 00:25:25,200
>> لذلك نحن لدينا انخفاض حجم أولا، ثم حجمنا مباريات فهرسنا.

333
00:25:25,200 --> 00:25:39,650
إذا كنا لا إنقاص حجم أولا، ثم علينا أن نفعل حجم -1 و ثم إنقاص.

334
00:25:39,650 --> 00:25:45,270
كبيرة. كل شيء جيد؟

335
00:25:45,270 --> 00:25:47,530
أي أسئلة حول هذا؟

336
00:25:47,530 --> 00:25:54,050
هناك عدد من الطرق المختلفة لكتابة هذا أيضا.

337
00:25:54,050 --> 00:26:03,290
في الواقع، يمكننا أن نفعل شيئا من ذلك - يمكننا القيام به لاحد الخطوط الملاحية المنتظمة.

338
00:26:03,290 --> 00:26:05,770
يمكننا أن نفعل عودة من سطر واحد.

339
00:26:05,770 --> 00:26:12,980
حتى نتمكن من إنقاص فعلا قبل أن يعود عن طريق القيام بذلك.

340
00:26:12,980 --> 00:26:18,320
وبالتالي فإن وضع - قبل s.size.

341
00:26:18,320 --> 00:26:22,060
الذي يجعل خط كثيفة حقا.

342
00:26:22,060 --> 00:26:30,940
حيث الفرق بين - حجم الصورة و. s.size--

343
00:26:30,940 --> 00:26:40,130
هو أن هذا POSTFIX - يسمونه POSTFIX لأن - يأتي بعد s.size--

344
00:26:40,130 --> 00:26:47,430
يعني أن يتم تقييم s.size لأغراض العثور على مؤشر

345
00:26:47,430 --> 00:26:50,410
كما هو حاليا عند تنفيذ هذا الخط،

346
00:26:50,410 --> 00:26:54,290
ثم هذا - يحدث بعد يعدم الخط.

347
00:26:54,290 --> 00:27:00,340
بعد الوصول إلى عنصر في المؤشر s.size.

348
00:27:00,340 --> 00:27:07,260
وهذا ليس ما نريد، لأننا نريد أن يحدث إنقاص الأولى.

349
00:27:07,260 --> 00:27:10,990
Othewise، ونحن في طريقنا إلى أن الوصول إلى مجموعة، على نحو فعال، خارج الحدود.

350
00:27:10,990 --> 00:27:16,850
ونحن في طريقنا إلى أن الوصول إلى عنصر واحد أعلاه أننا نريد فعلا الوصول إليها.

351
00:27:16,850 --> 00:27:23,840
نعم، وسام؟ هل >> أسرع أو استخدام كميات أقل من RAM لجعل في سطر واحد أم لا؟

352
00:27:23,840 --> 00:27:29,620
[Hardison] بصراحة، انها حقا يتوقف.

353
00:27:29,620 --> 00:27:34,220
[سام، غير مفهومة] >> نعم، فإنه يعتمد. يمكنك القيام الحيل مترجم

354
00:27:34,220 --> 00:27:41,580
للحصول على الاعتراف بأن المترجم، وعادة، وأتصور.

355
00:27:41,580 --> 00:27:44,840
>> حتى لقد ذكرنا قليلا عن هذه الاشياء الأمثل مترجم

356
00:27:44,840 --> 00:27:47,400
يمكنك أن تفعل ذلك في تجميع،

357
00:27:47,400 --> 00:27:50,580
وهذا هو النوع من الشيء الذي مترجم قد تكون قادرة على معرفة،

358
00:27:50,580 --> 00:27:54,710
مثل أوه، يا، ربما أستطيع أن أفعل كل هذا في عملية واحدة،

359
00:27:54,710 --> 00:27:59,420
بدلا من تحميل متغير الحجم في من ذاكرة الوصول العشوائي،

360
00:27:59,420 --> 00:28:03,770
decrementing ذلك، تخزين إعادته خارج، وتحميل ثم إعادته مرة أخرى

361
00:28:03,770 --> 00:28:08,000
لمعالجة ما تبقى من هذه العملية.

362
00:28:08,000 --> 00:28:10,710
ولكن عادة، لا، ليس هذا هو النوع من الشيء

363
00:28:10,710 --> 00:28:20,770
أن يحدث لجعل البرنامج بشكل أسرع.

364
00:28:20,770 --> 00:28:26,000
أي أسئلة أخرى على مداخن؟

365
00:28:26,000 --> 00:28:31,360
>> دفع ذلك وظهرت. إذا كنت تريد الرجال لمحاولة الخروج من الطبعة القراصنة،

366
00:28:31,360 --> 00:28:33,660
ما فعلناه في الطبعة القراصنة قد ولى فعلا

367
00:28:33,660 --> 00:28:37,670
وجعل هذا المكدس ينمو بشكل حيوي.

368
00:28:37,670 --> 00:28:43,190
التحدي هو في المقام الأول هناك حتى هنا في وظيفة دفع،

369
00:28:43,190 --> 00:28:48,820
لمعرفة كيفية جعل ذلك الصفيف تنمو

370
00:28:48,820 --> 00:28:52,450
كما كنت الاستمرار في دفع المزيد والمزيد من العناصر إلى المكدس.

371
00:28:52,450 --> 00:28:56,000
انها في الواقع ليست تعليمات برمجية إضافية أكثر من اللازم.

372
00:28:56,000 --> 00:29:00,080
مجرد دعوة لل- عليك أن تتذكر أن الحصول على دعوات لmalloc في هناك بشكل صحيح،

373
00:29:00,080 --> 00:29:03,310
وثم معرفة عندما كنت تريد الذهاب لاستدعاء realloc.

374
00:29:03,310 --> 00:29:06,090
وهذا هو التحدي متعة إذا كنت مهتما.

375
00:29:06,090 --> 00:29:11,550
>> ولكن في الوقت الراهن، دعنا ننتقل، ودعونا نتحدث عن قوائم الانتظار.

376
00:29:11,550 --> 00:29:15,680
انتقل من هنا.

377
00:29:15,680 --> 00:29:19,340
قائمة الانتظار هو أخ مقرب من المكدس.

378
00:29:19,340 --> 00:29:25,380
حتى في المكدس، وضعت الأشياء التي في آخر

379
00:29:25,380 --> 00:29:28,810
كانت أول الأشياء لثم يمكن استرجاع.

380
00:29:28,810 --> 00:29:33,600
ونحن قد حصلت على هذا الأخير في، لأول مرة، أو LIFO، وطلب.

381
00:29:33,600 --> 00:29:38,390
في حين أنه في قائمة الانتظار، كما كنت تتوقع من عندما كنت واقفا في الصف،

382
00:29:38,390 --> 00:29:41,980
أول شخص للحصول على الخط، فإن أول شيء للوصول الى قائمة الانتظار،

383
00:29:41,980 --> 00:29:47,630
هو الشيء الأول الذي يحصل على استرجاع من قائمة الانتظار.

384
00:29:47,630 --> 00:29:51,490
كما طوابير غالبا ما تستخدم عندما نتعامل مع الرسوم البيانية،

385
00:29:51,490 --> 00:29:55,560
مثل تحدثنا عن فترة وجيزة مع المداخن،

386
00:29:55,560 --> 00:30:00,260
وقوائم الانتظار أيضا مفيد لحفنة من الأشياء الأخرى.

387
00:30:00,260 --> 00:30:06,180
شيء واحد أن يأتي في كثير من الأحيان تحاول الحفاظ، على سبيل المثال،

388
00:30:06,180 --> 00:30:12,310
قائمة تم فرزها من العناصر.

389
00:30:12,310 --> 00:30:17,650
ويمكنك القيام بذلك مع مجموعة. يمكنك المحافظة على قائمة مصنفة من الأشياء في مجموعة،

390
00:30:17,650 --> 00:30:20,650
ولكن حيث أن يحصل صعبة ومن ثم يكون لديك دائما للعثور على

391
00:30:20,650 --> 00:30:26,160
المكان المناسب لإدراج الشيء التالي.

392
00:30:26,160 --> 00:30:28,250
إذا كان الأمر كذلك لديك مجموعة من الأرقام، من 1 إلى 10،

393
00:30:28,250 --> 00:30:31,630
ثم تريد توسيع ذلك لجميع الأرقام من 1 إلى 100،

394
00:30:31,630 --> 00:30:33,670
وكنت الحصول على هذه الأرقام في ترتيب عشوائي ومحاولة للحفاظ على كل شيء

395
00:30:33,670 --> 00:30:40,650
مصنفة كما تذهب من خلال، ينتهي بك الأمر إلى القيام بالكثير من التحول.

396
00:30:40,650 --> 00:30:43,910
مع أنواع معينة من قوائم الانتظار وأنواع معينة من هياكل البيانات الأساسية،

397
00:30:43,910 --> 00:30:46,670
يمكنك بالفعل تبقى من السهل إلى حد ما.

398
00:30:46,670 --> 00:30:50,640
لم يكن لديك لإضافة شيء ثم خلط كل شيء في كل مرة.

399
00:30:50,640 --> 00:30:56,770
ولا عليك أن تفعل الكثير من التحول من العناصر الداخلية حولها.

400
00:30:56,770 --> 00:31:02,990
عندما ننظر في قائمة الانتظار، ترى أن - في queue.c أيضا في التعليمات البرمجية القسم -

401
00:31:02,990 --> 00:31:10,950
البنية التي كانت لدينا منحك يشبه حقا أن البنية التي قدمناها لكم لكومة.

402
00:31:10,950 --> 00:31:13,770
>> هناك استثناء واحد لهذا، وهذا استثناء واحد

403
00:31:13,770 --> 00:31:21,700
هو أن لدينا هذا صحيحا إضافية تسمى الرأس،

404
00:31:21,700 --> 00:31:28,120
والرأس هنا لتتبع رئيس قائمة الانتظار،

405
00:31:28,120 --> 00:31:32,160
أو العنصر الأول في قائمة الانتظار.

406
00:31:32,160 --> 00:31:37,470
مع كومة، كنا قادرين على تتبع العنصر الذي كنا على وشك استرداد،

407
00:31:37,470 --> 00:31:40,800
أو الجزء العلوي من المكدس، وذلك باستخدام فقط من الحجم،

408
00:31:40,800 --> 00:31:44,220
في حين مع قائمة انتظار، ونحن الاضطرار إلى التعامل مع طرفي نقيض.

409
00:31:44,220 --> 00:31:49,000
ونحن نحاول أن تك الأشياء على في النهاية، ولكن الأمور تعود ثم من الأمام.

410
00:31:49,000 --> 00:31:54,640
بذلك على نحو فعال، مع رئيس، لدينا مؤشر لبداية قائمة الانتظار،

411
00:31:54,640 --> 00:31:58,920
وحجم يعطينا مؤشر لنهاية قائمة الانتظار

412
00:31:58,920 --> 00:32:03,730
حتى نتمكن من استرداد الأشياء من الرأس وإضافة أشياء إلى الذيل.

413
00:32:03,730 --> 00:32:06,890
في حين مع مكدس، كنا فقط من أي وقت مضى التعامل مع الجزء العلوي من المكدس.

414
00:32:06,890 --> 00:32:08,900
لم تكن لدينا للوصول إلى الجزء السفلي من المكدس.

415
00:32:08,900 --> 00:32:12,220
أضفنا فقط الأشياء إلى الأعلى وأخذت الأمور باتجاه آخر من الأعلى

416
00:32:12,220 --> 00:32:17,470
لذلك لم نكن بحاجة إلى أن حقل إضافي داخل البنية دينا.

417
00:32:17,470 --> 00:32:20,590
لا تجعل الشعور عموما؟

418
00:32:20,590 --> 00:32:27,670
حسنا. نعم، شارلوت؟ [شارلوت، غير مفهومة]

419
00:32:27,670 --> 00:32:32,660
[Hardison] هذا سؤال كبير، والتي كانت واحدة التي جاءت في المحاضرة.

420
00:32:32,660 --> 00:32:36,290
ربما سوف المشي خلال بضعة أمثلة توضح لماذا

421
00:32:36,290 --> 00:32:41,400
نحن لا نريد لاستخدام سلاسل [0] كرئيس لقائمة الانتظار.

422
00:32:41,400 --> 00:32:46,770
>> تخيل حتى يكون لدينا قائمة انتظار لدينا، ونحن في طريقنا أن نسميها قائمة الانتظار.

423
00:32:46,770 --> 00:32:49,210
في البداية، عندما كنا مثيل فقط،

424
00:32:49,210 --> 00:32:53,330
عندما أعلن لدينا فقط، ونحن لم تهيئة أي شيء.

425
00:32:53,330 --> 00:32:56,790
كل شيء القمامة. وذلك بطبيعة الحال نحن نريد أن نتأكد من أننا تهيئة

426
00:32:56,790 --> 00:33:00,950
كل من حجم ومجالات الرأس لتكون 0، شيء معقول.

427
00:33:00,950 --> 00:33:05,770
يمكن أن نذهب أيضا إلى الأمام وخالية من العناصر في قائمة الانتظار لدينا.

428
00:33:05,770 --> 00:33:09,930
ومناسبا لجعل هذا الرسم، لاحظ أن قائمة الانتظار لدينا الآن يمكن أن تعقد سوى ثلاث عناصر؛

429
00:33:09,930 --> 00:33:13,150
في حين لدينا كومة يمكن أن تعقد أربعة، يمكن أن قائمة الانتظار لدينا سوى ثلاث عقد.

430
00:33:13,150 --> 00:33:18,680
وهذا فقط لجعل تناسب الرسم التخطيطي.

431
00:33:18,680 --> 00:33:26,150
الشيء الأول الذي يحدث هنا هو أننا إدراج بقائمة الانتظار السلسلة "مرحبا".

432
00:33:26,150 --> 00:33:30,380
ومثلما فعلنا مع مكدس، لا شيء مختلف هنا بشكل رهيب،

433
00:33:30,380 --> 00:33:39,230
نلقي في السلسلة على سلاسل [0] وزيادة حجمنا بمقدار 1.

434
00:33:39,230 --> 00:33:42,720
نحن إدراج بقائمة الانتظار "وداعا"، ويحصل على وضعه على.

435
00:33:42,720 --> 00:33:45,870
ولذلك فإن هذا يبدو وكأنه كومة بالنسبة للجزء الاكبر.

436
00:33:45,870 --> 00:33:53,230
بدأنا هنا، عنصرا جديدا، عنصرا جديدا، حجم يبقي الصعود.

437
00:33:53,230 --> 00:33:56,330
ما يحدث في هذه المرحلة عندما نريد أن dequeue شيء؟

438
00:33:56,330 --> 00:34:01,280
عندما نريد أن dequeue، وهو العنصر الذي نريد أن dequeue؟

439
00:34:01,280 --> 00:34:04,110
[باسل] سلاسل [0]. صفر >>. صحيح تماما، باسل.

440
00:34:04,110 --> 00:34:10,960
نريد التخلص من السلسلة الأولى، هذا واحد، "مرحبا".

441
00:34:10,960 --> 00:34:13,170
فما كان الشيء الآخر الذي تغير؟

442
00:34:13,170 --> 00:34:17,010
إشعارا عند قيامنا برزت شيء الخروج من المكدس، فقط قمنا بتغيير حجم،

443
00:34:17,010 --> 00:34:22,080
ولكن هنا، لدينا اثنين من الأشياء التي تغير.

444
00:34:22,080 --> 00:34:27,440
لا يقتصر الأمر على تغيير الحجم، ولكن التغييرات الرأس.

445
00:34:27,440 --> 00:34:31,020
هذا هو الذهاب مرة أخرى إلى نقطة شارلوت في وقت سابق:

446
00:34:31,020 --> 00:34:38,699
لماذا لدينا هذا العنوان أيضا؟

447
00:34:38,699 --> 00:34:42,110
هل يعقل الآن، شارلوت؟ نوع >>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] نوع؟ فماذا حدث عندما كنا dequeued؟

449
00:34:47,500 --> 00:34:54,340
ماذا فعل رئيس نفعل ذلك الآن المثير للاهتمام؟

450
00:34:54,340 --> 00:34:56,449
[شارلوت] أوه، لأنه تغير - حسنا. فهمت.

451
00:34:56,449 --> 00:35:02,090
لأن الرأس - حيث يتم الإشارة إلى رئيس تغييرات من حيث الموقع.

452
00:35:02,090 --> 00:35:07,200
انها لم تعد دائما مؤشر واحد صفر. نعم >>، بالضبط.

453
00:35:07,200 --> 00:35:17,660
إذا كان ما حدث dequeueing العنصر عالية

454
00:35:17,660 --> 00:35:20,590
وقد تم ولم يكن لدينا هذا المجال الرأس

455
00:35:20,590 --> 00:35:26,880
لأننا كانوا ينادون دائما هذه السلسلة في 0 مؤشر رأس قائمة الانتظار لدينا،

456
00:35:26,880 --> 00:35:30,170
ثم كنا بد من الانتقال بقية قائمة الانتظار أسفل.

457
00:35:30,170 --> 00:35:36,010
كنا بد من الانتقال "وداعا" من سلاسل من [1] إلى سلاسل [0].

458
00:35:36,010 --> 00:35:38,760
والسلاسل [2] إلى أسفل إلى سلاسل [1].

459
00:35:38,760 --> 00:35:43,050
وسوف يترتب علينا أن نفعل ذلك للحصول على قائمة كاملة من العناصر،

460
00:35:43,050 --> 00:35:45,110
مجموعة كاملة من العناصر.

461
00:35:45,110 --> 00:35:50,490
وعندما نقوم بذلك مع صفيف، أن يحصل مكلفة حقا.

462
00:35:50,490 --> 00:35:53,340
حتى هنا، انها ليست صفقة كبيرة. لدينا فقط ثلاثة عناصر في مجموعتنا.

463
00:35:53,340 --> 00:35:57,230
ولكن إذا كان لدينا قائمة انتظار لعناصر ألف أو مليون العناصر،

464
00:35:57,230 --> 00:36:00,060
ثم فجأة، ونحن نبدأ صنع حفنة من dequeue يدعو جميع في حلقة،

465
00:36:00,060 --> 00:36:03,930
الامور تسير حقا أن يتباطأ في وقت تحول فيه كل شيء إلى أسفل باستمرار.

466
00:36:03,930 --> 00:36:07,320
تعلمون، والتحول بحلول 1، التحول من التحول، 1 من 1، تحول بمقدار 1.

467
00:36:07,320 --> 00:36:13,650
بدلا من ذلك، ونحن نستخدم هذا العنوان، ونحن نسميها "مؤشر" على الرغم من أنها ليست حقا مؤشر

468
00:36:13,650 --> 00:36:16,430
بالمعنى الدقيق للكلمة، بل ليست نوع مؤشر.

469
00:36:16,430 --> 00:36:19,410
انها ليست * الباحث * أو حرف أو أي شيء من هذا القبيل.

470
00:36:19,410 --> 00:36:28,930
لكنه يشير إلى يشير أو رئيس قائمة الانتظار لدينا. نعم؟

471
00:36:28,930 --> 00:36:38,800
>> [طالب] كيف تعرف dequeue لموسيقى البوب ​​قبالة كل ما هو على رأس؟

472
00:36:38,800 --> 00:36:43,620
[Hardison] كيف dequeue تعرف كيف انصرف كل ما هو على رأس؟ الحق >>، نعم.

473
00:36:43,620 --> 00:36:49,050
ما >> انها تبحث في كل ما هو مجرد مجال من المقرر أن رئيس.

474
00:36:49,050 --> 00:36:52,710
حتى في هذه الحالة الأولى، إذا ما نظرنا هنا،

475
00:36:52,710 --> 00:36:55,690
رؤوسنا هو 0 0 مؤشر. الحق >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] لذلك يقول فقط حسنا، حسنا، العنصر في الفهرس 0، السلسلة "مرحبا"،

477
00:37:00,500 --> 00:37:03,050
هو العنصر على رأس قائمة الانتظار لدينا.

478
00:37:03,050 --> 00:37:05,570
لذلك نحن ذاهبون الى dequeue هذا الرجل.

479
00:37:05,570 --> 00:37:09,800
وسوف يكون ذلك العنصر الذي يحصل عاد إلى الطالب.

480
00:37:09,800 --> 00:37:14,540
نعم، سعد؟ لذا >> يحدد رئيس أساسا - أين أنت ذاهب إلى مؤشر ذلك؟

481
00:37:14,540 --> 00:37:17,750
هذا هو بداية ذلك؟ نعم >>. حسنا >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] وهذا يصبح بداية جديدة لمجموعتنا.

483
00:37:22,900 --> 00:37:28,930
حتى عندما كنت dequeue شيء، كل ما عليك القيام به هو الوصول إلى عنصر في المؤشر q.head،

484
00:37:28,930 --> 00:37:32,240
وسوف يكون ذلك العنصر الذي تريد dequeue.

485
00:37:32,240 --> 00:37:34,930
لديك أيضا لإنقاص الحجم.

486
00:37:34,930 --> 00:37:39,430
سنرى في بعض الشيء حيث تصبح الأمور صعبة قليلا مع هذا.

487
00:37:39,430 --> 00:37:46,520
نحن dequeue، والآن، إذا كان لنا أن إدراج بقائمة الانتظار مرة أخرى،

488
00:37:46,520 --> 00:37:51,300
أين نحن إدراج بقائمة الانتظار؟

489
00:37:51,300 --> 00:37:55,000
أين العنصر التالي في قائمة الانتظار لدينا تذهب؟

490
00:37:55,000 --> 00:37:57,980
ويقول نريد أن إدراج بقائمة الانتظار السلسلة "CS".

491
00:37:57,980 --> 00:38:02,240
وإلى ذلك مؤشر الذي تذهب؟ [الطلاب] سلاسل [2]. >> الثانية.

492
00:38:02,240 --> 00:38:04,980
لماذا لا 2 و 0؟

493
00:38:04,980 --> 00:38:13,570
[باسل] لأن الرأس هو الآن 1، ذلك أن مثل بداية القائمة؟

494
00:38:13,570 --> 00:38:21,220
[Hardison] الحق. وما يدل على نهاية القائمة؟

495
00:38:21,220 --> 00:38:23,290
ما كنا باستخدام للدلالة على نهاية الطابور لدينا؟

496
00:38:23,290 --> 00:38:25,970
رئيس هو رئيس قائمة الانتظار لدينا، بداية قائمة الانتظار لدينا.

497
00:38:25,970 --> 00:38:29,530
ما هي نهاية قائمة الانتظار لدينا؟ [الطلاب] الحجم. الحجم >>، بالضبط.

498
00:38:29,530 --> 00:38:36,360
حتى عناصر جديدة لدينا في الذهاب في الحجم، والعناصر التي نتخذها تؤتي ثمارها على الفرار في الرأس.

499
00:38:36,360 --> 00:38:45,390
عندما كنا إدراج بقائمة الانتظار العنصر التالي، ونحن في وضعه في الحجم.

500
00:38:45,390 --> 00:38:48,530
[طالب] قبل وضع لكم في أن على الرغم من حجم كان 1، أليس كذلك؟

501
00:38:48,530 --> 00:38:55,690
[Hardison] الحق. حتى لا جدا في الحجم. + الحجم، لا +1، ولكن رئيس +.

502
00:38:55,690 --> 00:38:59,990
لأن كل شيء تحول ونحن بمقدار الرأس.

503
00:38:59,990 --> 00:39:14,270
حتى هنا، ونحن الآن قد حصلت على قائمة الانتظار من حجم 1 أن يبدأ في مؤشر 1.

504
00:39:14,270 --> 00:39:20,730
الذيل هو مؤشر 2. نعم؟

505
00:39:20,730 --> 00:39:25,780
>> [طالب] ماذا يحدث عند dequeue سلاسل [0]، وسلاسل "فتحات في الذاكرة

506
00:39:25,780 --> 00:39:29,420
مجرد الحصول على تفرغ، في الأساس، أو نسيان للتو؟

507
00:39:29,420 --> 00:39:34,700
[Hardison] نعم. في هذا المعنى، ونحن ننسى منهم فقط.

508
00:39:34,700 --> 00:39:42,640
إذا كنا تخزين نسخ منها ل-

509
00:39:42,640 --> 00:39:46,310
والعديد من هياكل البيانات تخزين في كثير من الأحيان نسخهم الخاصة من العناصر

510
00:39:46,310 --> 00:39:51,760
حتى أن الشخص إدارة بنية بيانات لا داعي للقلق

511
00:39:51,760 --> 00:39:53,650
حول أين كل تلك المؤشرات تسير.

512
00:39:53,650 --> 00:39:56,000
بنية البيانات يحمل على كل شيء، ويحمل على لنسخ جميع،

513
00:39:56,000 --> 00:39:59,580
للتأكد من أن كل شيء استمرت بشكل مناسب.

514
00:39:59,580 --> 00:40:03,140
ومع ذلك، في هذه الحالة، هذه الهياكل البيانات فقط، للتبسيط،

515
00:40:03,140 --> 00:40:05,580
لا صنع نسخ من أي شيء اننا تخزين فيها.

516
00:40:05,580 --> 00:40:08,630
[طالب] لذلك هو هذا مجموعة المستمر لل-؟ نعم >>.

517
00:40:08,630 --> 00:40:14,350
إذا نظرنا إلى الوراء في ما كان تعريف هذا الهيكل، هو عليه.

518
00:40:14,350 --> 00:40:19,110
انها مجرد مجموعة والقياسية مثل كنت قد رأيت،

519
00:40:19,110 --> 00:40:24,280
مجموعة من شار * S.

520
00:40:24,280 --> 00:40:26,340
يفعل ذلك -؟ نعم >>، كنت أتساءل فقط

521
00:40:26,340 --> 00:40:29,130
إذا عليك تشغيل في نهاية الأمر من الذاكرة، إلى حد ما،

522
00:40:29,130 --> 00:40:32,330
إذا كان لديك كل هذه البقع الفارغة في الصفيف الخاص بك؟

523
00:40:32,330 --> 00:40:36,390
[Hardison] نعم، هذا نقطة جيدة.

524
00:40:36,390 --> 00:40:41,530
>> إذا نظرنا إلى ما حدث الآن في هذه المرحلة،

525
00:40:41,530 --> 00:40:46,350
لدينا قائمة انتظار يملأ لدينا، يبدو.

526
00:40:46,350 --> 00:40:50,390
لكننا لم تملأ حقا لدينا قائمة انتظار

527
00:40:50,390 --> 00:40:57,710
لأن لدينا قائمة انتظار هذا حجم 2، ولكنه يبدأ في مؤشر 1،

528
00:40:57,710 --> 00:41:02,160
لانه المكان الرئيسي لدينا هو مؤشر.

529
00:41:02,160 --> 00:41:08,400
مثلك كانوا يقولون، ذلك العنصر في سلاسل [0]، في مؤشر 0، ليست هناك حقا.

530
00:41:08,400 --> 00:41:10,450
انها ليست في قائمة الانتظار لدينا بعد الآن.

531
00:41:10,450 --> 00:41:16,460
نحن فقط لم يكلف نفسه عناء الذهاب والكتابة فوقه عندما كنا dequeued ذلك.

532
00:41:16,460 --> 00:41:18,700
حتى على الرغم من أنه يبدو أننا قد نفد من الذاكرة، لدينا حقا لا.

533
00:41:18,700 --> 00:41:23,270
تلك البقعة هي المتاحة لنا للاستخدام.

534
00:41:23,270 --> 00:41:29,310
سلوك الملائم، إذا كان لنا أن محاولة وأول شيء dequeue

535
00:41:29,310 --> 00:41:34,420
مثل "وداعا"، التي من شأنها أن موسيقى البوب ​​قبالة داعا.

536
00:41:34,420 --> 00:41:38,460
لدينا قائمة انتظار الآن يبدأ في مؤشر 2 و هو من حجم 1.

537
00:41:38,460 --> 00:41:42,240
والآن إذا حاولنا إدراج بقائمة الانتظار شيء ومرة ​​أخرى، ويقول 50،

538
00:41:42,240 --> 00:41:47,880
يجب أن تذهب 50 في هذه البقعة في الفهرس 0

539
00:41:47,880 --> 00:41:51,270
لأنه لا تزال متاحة لنا. نعم، سعد؟

540
00:41:51,270 --> 00:41:53,630
[سعد] هل هذا يحدث تلقائيا؟

541
00:41:53,630 --> 00:41:56,150
[Hardison] ذلك لا يحدث تلقائيا تماما. عليك أن تفعل الرياضيات

542
00:41:56,150 --> 00:42:00,380
والعمل على انجاحه، ولكن ما فعلناه أساسا هو أننا قد اختتم أعماله مؤخرا حولها.

543
00:42:00,380 --> 00:42:04,070
[سعد] وهل هو بخير إذا كان هذا لديه ثقب في وسطها؟

544
00:42:04,070 --> 00:42:08,720
[Hardison] وكأن يمكننا أن نجعل الرياضيات العمل بها بشكل صحيح.

545
00:42:08,720 --> 00:42:15,470
>> وتبين أن هذا في الواقع ليس من الصعب أن تفعل مع المشغل وزارة الدفاع.

546
00:42:15,470 --> 00:42:20,040
لذلك تماما مثل فعلنا مع قيصر والاشياء التشفير،

547
00:42:20,040 --> 00:42:25,190
باستخدام وزارة الدفاع، يمكننا الحصول على الأشياء التفاف حولها والاستمرار

548
00:42:25,190 --> 00:42:28,090
وحول مع حولها وحول قائمة الانتظار لدينا،

549
00:42:28,090 --> 00:42:32,180
حفظ هذا المؤشر يتحرك الرأس.

550
00:42:32,180 --> 00:42:38,840
تلاحظ أن حجم واحترام دائما عدد من العناصر في الواقع ضمن قائمة الانتظار.

551
00:42:38,840 --> 00:42:43,110
وانها مجرد مؤشر الرأس التي تحافظ على ركوب الدراجات من خلال.

552
00:42:43,110 --> 00:42:49,660
إذا نظرنا إلى ما حدث هنا، إذا عدنا إلى البداية،

553
00:42:49,660 --> 00:42:55,020
وأنت مجرد مشاهدة ما يحدث في الرأس

554
00:42:55,020 --> 00:42:58,240
لم يحدث أي شيء عندما كنا إدراج بقائمة الانتظار شيء، في الرأس.

555
00:42:58,240 --> 00:43:00,970
لم يحدث أي شيء عندما كنا enqueued شيء آخر، في الرأس.

556
00:43:00,970 --> 00:43:04,130
في أقرب وقت ونحن dequeued شيئا، ورئيس ترتفع من جانب واحد.

557
00:43:04,130 --> 00:43:06,600
نحن enqueued شيء، لا شيء يحدث في الرأس.

558
00:43:06,600 --> 00:43:11,060
عندما كنا dequeue شيء، فجأة يحصل زيادة في الرأس.

559
00:43:11,060 --> 00:43:14,660
عندما كنا إدراج بقائمة الانتظار شيء، لا شيء يحدث في الرأس.

560
00:43:14,660 --> 00:43:20,240
>> ماذا سيحدث في هذه المرحلة إذا كان لنا أن dequeue شيء مرة أخرى؟

561
00:43:20,240 --> 00:43:23,240
أي أفكار؟ ماذا سيحدث في الرأس؟

562
00:43:23,240 --> 00:43:27,190
ما ينبغي أن يحدث في الرأس

563
00:43:27,190 --> 00:43:32,990
إذا كان لنا أن dequeue شيء آخر؟

564
00:43:32,990 --> 00:43:35,400
رئيس الآن هو مؤشر على 2،

565
00:43:35,400 --> 00:43:38,920
وهو ما يعني أن رئيس قائمة الانتظار سلاسل [2].

566
00:43:38,920 --> 00:43:44,280
[طالب] والتي ترجع 0؟ وينبغي أن تعود >> إلى 0. ينبغي أن يلتف حول العودة، بالضبط.

567
00:43:44,280 --> 00:43:48,440
حتى الآن، في كل مرة كنا نسميها dequeue، كنا إضافة واحدة في الرأس،

568
00:43:48,440 --> 00:43:50,960
إضافة واحد في الرأس، إضافة واحد في الرأس، إضافة واحد في الرأس.

569
00:43:50,960 --> 00:43:58,400
بمجرد أن يحصل على مؤشر رأس المؤشر في مجموعة مشاركة لدينا،

570
00:43:58,400 --> 00:44:05,650
ثم علينا أن التفاف حول إعادته إلى بداية، والعودة إلى 0.

571
00:44:05,650 --> 00:44:09,900
[شارلوت] ما الذي يحدد قدرة قائمة الانتظار في كومة؟

572
00:44:09,900 --> 00:44:13,120
[Hardison] في هذه الحالة، لقد تم للتو باستخدام تعريف ثابت #. حسنا >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] في الملف C الفعلية.، يمكنك الذهاب في الوحل ومعها قليلا

574
00:44:19,590 --> 00:44:21,710
وجعله كبيرة أو صغيرة كما تريد.

575
00:44:21,710 --> 00:44:25,310
[شارلوت] لذلك عندما كنت مما يجعلها قائمة الانتظار، كيف تجعل جهاز الكمبيوتر تعرف

576
00:44:25,310 --> 00:44:29,120
كيف كبيرة تريد أن تكون المكدس؟

577
00:44:29,120 --> 00:44:31,700
[Hardison] هذا سؤال كبير.

578
00:44:31,700 --> 00:44:34,800
هناك عدة طرق. واحد هو تحديد فقط في خط الهجوم

579
00:44:34,800 --> 00:44:42,050
وأقول هذا سيكون طابور لديها 4 عناصر أو 50 أو العناصر 10،000.

580
00:44:42,050 --> 00:44:45,430
الطريقة الأخرى هي أن تفعل ما الناس الطبعة القراصنة يفعلون

581
00:44:45,430 --> 00:44:52,310
وخلق وظائف لديها قائمة انتظار الخاص بك ينمو بشكل حيوي وأضاف الحصول على المزيد من الأشياء فيها.

582
00:44:52,310 --> 00:44:54,740
>> [شارلوت] حتى للذهاب مع الخيار الأول، ما الجملة التي تستخدمها

583
00:44:54,740 --> 00:44:57,830
لنقول للبرنامج ما هو حجم قائمة الانتظار؟

584
00:44:57,830 --> 00:45:04,780
[Hardison] آه. لذلك دعونا نخرج من هذا.

585
00:45:04,780 --> 00:45:12,650
ما زلت في stack.c هنا، لذلك أنا مجرد الذهاب إلى التمرير لأعلى إلى الأعلى هنا.

586
00:45:12,650 --> 00:45:17,920
يمكنك ان ترى هذا الحق هنا؟ هذا هو تعريف # سعة 10.

587
00:45:17,920 --> 00:45:24,600
وهذا يكاد يكون بناء الجملة بالضبط نفس التي لدينا لقائمة الانتظار.

588
00:45:24,600 --> 00:45:28,390
إلا في قائمة الانتظار، لقد وصلنا هذا المجال إضافية في البنية هنا.

589
00:45:28,390 --> 00:45:32,760
[شارلوت] أوه، كنت اعتقد قدرة يعني القدرة على السلسلة.

590
00:45:32,760 --> 00:45:36,770
[Hardison] آه. انه >> الحد الأقصى لطول الكلمة. حصلت >> ذلك.

591
00:45:36,770 --> 00:45:41,180
نعم. قدرة هنا - وهذا هو نقطة كبيرة.

592
00:45:41,180 --> 00:45:44,000
وهذا شيء وهذا صعب

593
00:45:44,000 --> 00:45:49,480
لأن ما أعلن لدينا هنا هو مجموعة من شار * S.

594
00:45:49,480 --> 00:45:52,770
مجموعة من المؤشرات.

595
00:45:52,770 --> 00:45:56,690
هذا هو مجموعة من حرف.

596
00:45:56,690 --> 00:46:01,690
وربما هذا هو ما كنت قد رأيت عندما كنت قد تم إعلان مخازن للحصول على ملف I / O،

597
00:46:01,690 --> 00:46:06,840
عندما كنت قد تم إنشاء سلاسل يدويا على المكدس.

598
00:46:06,840 --> 00:46:09,090
ومع ذلك، ما لدينا هنا هو مجموعة من شار * S.

599
00:46:09,090 --> 00:46:13,400
لذلك فمن مجموعة من المؤشرات.

600
00:46:13,400 --> 00:46:18,350
في الواقع، إذا كان لنا أن إعادة تكبير بها ونحن ننظر إلى ما يجري هنا

601
00:46:18,350 --> 00:46:23,140
في العرض التقديمي، ترى أن العناصر الفعلية، والبيانات الشخصية

602
00:46:23,140 --> 00:46:26,180
لا يتم تخزين داخل مجموعة نفسها.

603
00:46:26,180 --> 00:46:42,690
ما المخزنة داخل مجموعتنا هنا المؤشرات إلى البيانات الشخصية.

604
00:46:42,690 --> 00:46:52,560
حسنا. حتى لقد رأينا كيف أن حجم قائمة الانتظار هو تماما مثل مع مكدس،

605
00:46:52,560 --> 00:46:58,670
حجم تحترم دائما عدد من العناصر حاليا في قائمة الانتظار.

606
00:46:58,670 --> 00:47:02,720
بعد القرارات 2 enqueues، وحجم هو 2.

607
00:47:02,720 --> 00:47:07,110
بعد إجراء dequeue حجم الآن 1.

608
00:47:07,110 --> 00:47:09,330
بعد إجراء آخر إدراج بقائمة الانتظار حجم يعود لتصل إلى 2.

609
00:47:09,330 --> 00:47:12,340
وبالتالي فإن حجم يحترم بالتأكيد عدد من العناصر في قائمة الانتظار،

610
00:47:12,340 --> 00:47:15,580
ثم رئيس وتبقي فقط ركوب الدراجات.

611
00:47:15,580 --> 00:47:20,210
وغني عن 0-1-2، 0-1-2، 0-1-2.

612
00:47:20,210 --> 00:47:25,620
وفي كل مرة ندعو dequeue، ويحصل على زيادة رأس المؤشر إلى مؤشر المقبل.

613
00:47:25,620 --> 00:47:29,930
وإذا كان رئيس على وشك أن يذهب أكثر، فإنه حلقات حول العودة إلى 0.

614
00:47:29,930 --> 00:47:34,870
حتى مع ذلك، يمكن أن نكتب وظيفة dequeue.

615
00:47:34,870 --> 00:47:40,200
ونحن في طريقنا لمغادرة ظيفة إدراج بقائمة الانتظار لليا رفاق لتنفيذ بدلا من ذلك.

616
00:47:40,200 --> 00:47:45,880
>> عندما كنا dequeue عنصر من قائمة الانتظار لدينا،

617
00:47:45,880 --> 00:47:55,490
ما هو أول شيء فعله دانيال عندما بدأنا الكتابة وظيفة البوب ​​لرزمة؟

618
00:47:55,490 --> 00:48:00,490
اسمحوا لي أن نسمع من شخص لم يتحدث حتى الان.

619
00:48:00,490 --> 00:48:06,710
دعونا نرى، سعد، هل تذكر ما دانيال كما فعل أول شيء عندما كتب البوب؟

620
00:48:06,710 --> 00:48:08,860
[سعد] وكان هناك، وكان - >> واختبارها عن شيء.

621
00:48:08,860 --> 00:48:12,140
[سعد] إذا كان حجم أكبر من 0. بالضبط >>.

622
00:48:12,140 --> 00:48:14,390
وماذا كان ذلك اختبار ل؟

623
00:48:14,390 --> 00:48:19,090
[سعد] الذي كان اختبار لمعرفة إذا كان هناك أي شيء داخل الصفيف.

624
00:48:19,090 --> 00:48:23,210
[Hardison] نعم. بالضبط. لذلك لا يمكنك البوب ​​أي شيء للخروج من كومة إذا كان فارغا.

625
00:48:23,210 --> 00:48:26,510
وبالمثل، لا يمكن dequeue أي شيء من قائمة انتظار ما اذا كان فارغا.

626
00:48:26,510 --> 00:48:30,420
ما هو أول شيء يتعين علينا القيام به في وظيفة dequeue لدينا هنا، هل تعتقد؟

627
00:48:30,420 --> 00:48:33,860
[سعد] إذا كان حجم أكبر من 0؟ نعم >>.

628
00:48:33,860 --> 00:48:37,710
في هذه الحالة، لقد اختبرت فعلا فقط لمعرفة ما اذا كان هو 0.

629
00:48:37,710 --> 00:48:42,240
إذا كان 0، يمكننا العودة فارغة.

630
00:48:42,240 --> 00:48:45,280
ولكن المنطق نفسه بالضبط.

631
00:48:45,280 --> 00:48:49,110
ودعونا نستمر في هذا.

632
00:48:49,110 --> 00:48:54,600
إذا كان حجم غير 0، حيث هو العنصر الذي نريد أن dequeue؟

633
00:48:54,600 --> 00:48:58,550
[سعد] في الرأس؟ بالضبط >>.

634
00:48:58,550 --> 00:49:01,720
يمكننا سحب للتو العنصر الأول في قائمة الانتظار لدينا

635
00:49:01,720 --> 00:49:07,040
عن طريق الوصول إلى عنصر في الرأس.

636
00:49:07,040 --> 00:49:14,630
مجنون لا شيء.

637
00:49:14,630 --> 00:49:19,620
بعد ذلك، ماذا علينا ان نفعل؟ ما يجب أن يحدث؟

638
00:49:19,620 --> 00:49:23,740
ما هو الشيء الآخر الذي تحدثنا عنه في dequeue؟

639
00:49:23,740 --> 00:49:28,130
شيئان يجب أن يحدث، لأن لدينا قائمة انتظار قد تغير.

640
00:49:28,130 --> 00:49:35,640
[دانيال] تقليل حجم. لدينا >> للحد من حجم، وزيادة رأس؟ بالضبط.

641
00:49:35,640 --> 00:49:40,600
لزيادة رأس، يمكننا ليس فقط زيادة رأس عمياء، تذكر.

642
00:49:40,600 --> 00:49:45,080
يمكننا القيام به ليس فقط queue.head + +.

643
00:49:45,080 --> 00:49:51,630
علينا أن تشمل أيضا هذه من قبل وزارة الدفاع القدرات.

644
00:49:51,630 --> 00:49:54,740
ولماذا نحن وزارة الدفاع من قبل القدرات، ستيلا؟

645
00:49:54,740 --> 00:49:58,680
[ستيلا] لانها التفاف حولها. بالضبط >>.

646
00:49:58,680 --> 00:50:04,750
نحن وزارة الدفاع على قدرة لأنه يحتوي التفاف حول العودة إلى 0.

647
00:50:04,750 --> 00:50:07,400
حتى الآن، في هذه المرحلة، يمكننا أن نفعل ما قال دانيال.

648
00:50:07,400 --> 00:50:12,700
يمكننا إنقاص الحجم.

649
00:50:12,700 --> 00:50:29,170
ومن ثم يمكن أن نعود فقط العنصر الذي كان في الجزء العلوي من قائمة الانتظار.

650
00:50:29,170 --> 00:50:34,000
يبدو نوع من gnarly في البداية. قد يكون لديك السؤال. آسف؟

651
00:50:34,000 --> 00:50:37,260
>> [سام] لماذا هذا أولا في الجزء العلوي من قائمة الانتظار؟ أين أن تذهب؟

652
00:50:37,260 --> 00:50:42,480
[Hardison] انها تأتي من السطر الرابع من أسفل.

653
00:50:42,480 --> 00:50:46,060
بعد أن اختبار للتأكد من أن لدينا قائمة انتظار ليست فارغة،

654
00:50:46,060 --> 00:50:54,100
انسحبنا * شار الأولى، ونحن سحب العنصر الذي يجلس على رأس مؤشر

655
00:50:54,100 --> 00:50:58,680
من مجموعة لدينا، لدينا خيوط >>، ومجموعة المكالمة التي الأول؟

656
00:50:58,680 --> 00:51:04,500
[Hardison] ونحن ندعو لأول مرة. نعم.

657
00:51:04,500 --> 00:51:09,850
فقط لمتابعة ذلك، لماذا تعتقد كان علينا أن نفعل ذلك؟

658
00:51:09,850 --> 00:51:18,270
[سام] كل الأول هو العودة فقط q.strings [q.head]؟ نعم >>.

659
00:51:18,270 --> 00:51:23,830
لأن >> نقوم به هذا التغير من q.head مع وظيفة وزارة الدفاع،

660
00:51:23,830 --> 00:51:27,810
وليس هناك طريقة للقيام بذلك ضمن خط العودة أيضا.

661
00:51:27,810 --> 00:51:31,640
[Hardison] بالضبط. كنت على الفور. سام كليا على الفور.

662
00:51:31,640 --> 00:51:36,800
السبب كان علينا أن سحب العنصر الأول في قائمة الانتظار لدينا وتخزينه في متغير

663
00:51:36,800 --> 00:51:43,030
لأن هذا الخط حيث كنا قد q.head فقط،

664
00:51:43,030 --> 00:51:47,030
هناك عامل وزارة الدفاع في وجود شيء لا يمكننا القيام به

665
00:51:47,030 --> 00:51:51,230
وأنها قد تصبح نافذة المفعول على الرأس دون - في سطر واحد.

666
00:51:51,230 --> 00:51:54,480
لذلك لدينا في الواقع لسحب العنصر الأول، ثم ضبط الرأس،

667
00:51:54,480 --> 00:52:00,430
ضبط حجم، ثم يعود العنصر الذي انسحبنا.

668
00:52:00,430 --> 00:52:02,680
وهذا هو الشيء الذي سنرى الخروج في وقت لاحق مع

669
00:52:02,680 --> 00:52:04,920
القوائم المرتبطة، كما لعبنا في جميع أنحاء معهم.

670
00:52:04,920 --> 00:52:08,410
في كثير من الأحيان عندما كنت تحرير أو التخلص من القوائم المرتبطة

671
00:52:08,410 --> 00:52:13,500
عليك أن تتذكر العنصر التالي، المؤشر التالي من قائمة مرتبطة

672
00:52:13,500 --> 00:52:16,330
قبل التخلص من النظام الحالي.

673
00:52:16,330 --> 00:52:23,580
لأن خلاف ذلك لك أن تتخلص من المعلومات من ما تبقى في القائمة.

674
00:52:23,580 --> 00:52:34,160
الآن، إذا ذهبت إلى الأجهزة الخاصة بك، يمكنك فتح queue.c-X للخروج من هذا.

675
00:52:34,160 --> 00:52:39,390
حتى لو كنت تفتح queue.c، اسمحوا لي تكبير هنا،

676
00:52:39,390 --> 00:52:44,970
سترى أن لديك ملف مماثلة المظهر.

677
00:52:44,970 --> 00:52:49,200
مماثلة ذات مظهر الملف إلى ما كان لدينا في وقت سابق مع stack.c.

678
00:52:49,200 --> 00:52:54,690
لقد وصلنا لدينا قائمة انتظار البنية المحددة فقط كما رأينا على الشرائح.

679
00:52:54,690 --> 00:52:59,870
>> لدينا لدينا وظيفة إدراج بقائمة الانتظار الذي هو بالنسبة لك أن تفعل.

680
00:52:59,870 --> 00:53:04,340
ونحن لدينا وظيفة dequeue هنا.

681
00:53:04,340 --> 00:53:06,870
ودون تنفيذ وظيفة dequeue في الملف،

682
00:53:06,870 --> 00:53:13,230
ولكن سوف أضع إعادته على برنامج PowerPoint بحيث يمكنك كتابته، إذا كنت ترغب.

683
00:53:13,230 --> 00:53:16,690
ذلك لمدة 5 دقائق القادمة أو نحو ذلك، يا رفاق العمل على إدراج بقائمة الانتظار

684
00:53:16,690 --> 00:53:22,570
الذي هو مجرد تقريبا على عكس dequeue.

685
00:53:22,570 --> 00:53:29,560
لم يكن لديك لضبط الرأس عندما كنت enqueueing، ولكن ماذا لديك لضبط؟

686
00:53:29,560 --> 00:53:38,920
الحجم. حتى عندما كنت إدراج بقائمة الانتظار، يبقى الرأس لم يمسها، يحصل تغيير الحجم.

687
00:53:38,920 --> 00:53:46,920
ولكن الأمر يستغرق قليلا من - سيكون لديك للعب مع حولها أن وزارة الدفاع

688
00:53:46,920 --> 00:53:57,560
لمعرفة بالضبط ما يجب أن يتم إدراج مؤشر العنصر الجديد في.

689
00:53:57,560 --> 00:54:03,080
لذلك سأعطيك الرجال قليلا، وطرح dequeue احتياطية على الشريحة،

690
00:54:03,080 --> 00:54:05,200
وكما يا رفاق لديك أسئلة، يصرخ بها حتى نستطيع

691
00:54:05,200 --> 00:54:09,220
كل الكلام عنهم كمجموعة.

692
00:54:09,220 --> 00:54:13,960
أيضا، مع الحجم الذي مش - عند ضبط حجم، يمكنك فقط دائما -

693
00:54:13,960 --> 00:54:18,720
هل لديك حجم وزارة الدفاع من أي وقت مضى؟ [دانيال] رقم >> ليس لديك إلى وزارة الدفاع حجم والحق.

694
00:54:18,720 --> 00:54:24,260
وذلك لأن حجم دائما، إذا أنت الآن - على افتراض أنك إدارة الأمور بشكل مناسب،

695
00:54:24,260 --> 00:54:30,840
وسوف يكون حجم دائما بين 0 و 3.

696
00:54:30,840 --> 00:54:38,680
أين وزارة الدفاع لديك عندما كنت تفعل إدراج بقائمة الانتظار؟

697
00:54:38,680 --> 00:54:41,060
[طالب] فقط على الرأس. فقط >> لرئيس، بالضبط.

698
00:54:41,060 --> 00:54:44,620
ولماذا لديك لوزارة الدفاع على الإطلاق في إدراج بقائمة الانتظار؟

699
00:54:44,620 --> 00:54:48,830
عندما هو الحالة التي كنت قد لوزارة الدفاع؟

700
00:54:48,830 --> 00:54:53,630
[طالب] إذا كان لديك الاشياء في أماكن، مثل مساحات في 1 و 2،

701
00:54:53,630 --> 00:54:55,950
وتحتاج بعد ذلك لك أن تضيف شيئا في 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] نعم، بالضبط. إذا كان الأمر كذلك المؤشر الرئيسي هو في النهاية،

703
00:55:02,570 --> 00:55:14,210
أو إذا كان حجم زائد رأسك هو أكبر، أو بدلا من ذلك، يتم الانتقال إلى بالالتفاف حول قائمة الانتظار.

704
00:55:14,210 --> 00:55:17,830
>> حتى في هذه الحالة أن لدينا هنا على الشريحة في الوقت الراهن،

705
00:55:17,830 --> 00:55:24,370
إذا كنت ترغب في إدراج بقائمة الانتظار شيء في الوقت الراهن،

706
00:55:24,370 --> 00:55:31,110
نريد أن إدراج بقائمة الانتظار شيء في مؤشر 0.

707
00:55:31,110 --> 00:55:35,450
حتى إذا كنت تبحث في ال 50 حيث يذهب، وأدعو إدراج بقائمة الانتظار 50،

708
00:55:35,450 --> 00:55:40,840
وتنخفض هناك في الأسفل. وغني عن 0 مؤشر.

709
00:55:40,840 --> 00:55:44,160
فإنه يستبدل "مرحبا" الذي dequeued بالفعل.

710
00:55:44,160 --> 00:55:46,210
[دانيال] لا تأخذ الرعاية من ذلك في dequeue بالفعل؟

711
00:55:46,210 --> 00:55:50,550
لماذا يفعل أي شيء مع الرأس في إدراج بقائمة الانتظار؟

712
00:55:50,550 --> 00:55:55,770
[Hardison] أوه، حتى أنك لا تعديل الرأس، آسف.

713
00:55:55,770 --> 00:56:02,310
ولكن لديك لاستخدام مشغل وزارة الدفاع عندما كنت الحصول على

714
00:56:02,310 --> 00:56:04,250
العنصر الذي تريد إدراج بقائمة الانتظار عندما كنت الحصول على

715
00:56:04,250 --> 00:56:06,960
العنصر التالي في قائمة الانتظار الخاصة بك.

716
00:56:06,960 --> 00:56:10,960
[باسل] لم أفعل ذلك، وأنا حصلت على "النجاح" هناك.

717
00:56:10,960 --> 00:56:13,370
[دانيال] أوه، أنا أفهم ما تقوله.

718
00:56:13,370 --> 00:56:16,240
[Hardison] لذلك أنت didn't - فعلتم فقط في q.size؟

719
00:56:16,240 --> 00:56:20,670
[باسل] نعم. لم أكن مجرد تغيير الجانبين، أستطيع أن أفعل أي شيء مع الرأس.

720
00:56:20,670 --> 00:56:24,300
[Hardison] ليس لديك فعلا لإعادة الرأس إلى أن يكون أي شيء،

721
00:56:24,300 --> 00:56:31,650
ولكن عندما كنت في مؤشر مجموعة السلاسل،

722
00:56:31,650 --> 00:56:39,500
لديك فعلا على المضي قدما وحساب العنصر التالي حيث هو،

723
00:56:39,500 --> 00:56:44,230
وكان العنصر التالي في الكدسة لمجدل المكدس، دائما

724
00:56:44,230 --> 00:56:48,740
في مؤشر المقابلة لحجم.

725
00:56:48,740 --> 00:56:55,850
إذا كان لنا أن ننظر إلى الوراء حتى في كومة لدينا وظيفة دفع،

726
00:56:55,850 --> 00:57:03,100
يمكننا دائما غطس في العنصر الجديد الحق في حجم الفهرس.

727
00:57:03,100 --> 00:57:06,710
في حين مع قائمة الانتظار، لا يمكننا أن نفعل ذلك

728
00:57:06,710 --> 00:57:10,340
لأنه إذا نحن في هذه الحالة،

729
00:57:10,340 --> 00:57:18,130
وإذا كنا enqueued دينا 50 سلسلة جديدة يسير في الاتجاه الصحيح في سلاسل [1]

730
00:57:18,130 --> 00:57:20,540
ونحن لا نريد أن نفعل.

731
00:57:20,540 --> 00:57:41,200
نحن نريد أن يكون سلسلة جديدة تذهب في مؤشر 0.

732
00:57:41,200 --> 00:57:44,320
>> أي شخص لا - نعم؟ [طالب] لدي سؤال ولكن هذا لا علاقة حقا.

733
00:57:44,320 --> 00:57:48,160
ماذا يعني عندما يقوم شخص ما يدعو فقط شيء من هذا القبيل مؤشر PRED؟

734
00:57:48,160 --> 00:57:51,260
ما هو هذا الاسم اختصار ل؟ وأنا أعلم أنه مجرد اسم.

735
00:57:51,260 --> 00:57:59,110
[Hardison] مؤشر PRED؟ دعونا نرى. وفي أي سياق؟

736
00:57:59,110 --> 00:58:01,790
[طالب] وكان لإدراج. يمكن أن أطلب منكم إذا كنت تريد في وقت لاحق

737
00:58:01,790 --> 00:58:03,920
لأنه لا علاقة حقا، ولكن فقط I -

738
00:58:03,920 --> 00:58:07,300
[Hardison] من رمز إدراج داود من محاضرة؟

739
00:58:07,300 --> 00:58:10,860
يمكننا سحب ما يصل والحديث عن ذلك.

740
00:58:10,860 --> 00:58:15,550
سوف نتحدث عن ذلك القادم، والحصول على قوائم لمرة واحدة ونحن المرتبطة.

741
00:58:15,550 --> 00:58:21,440
>> لذلك دعونا بسرعة حقا ننظر إلى ما وظيفة إدراج بقائمة الانتظار يبدو.

742
00:58:21,440 --> 00:58:26,530
ما هو أول شيء أن الناس حاولوا القيام به في الخط الخاص بك إدراج بقائمة الانتظار؟ في قائمة الانتظار هذه؟

743
00:58:26,530 --> 00:58:29,960
على غرار ما فعلت لدفع المكدس.

744
00:58:29,960 --> 00:58:32,080
ماذا فعلت، ستيلا؟

745
00:58:32,080 --> 00:58:35,050
[ستيلا، غير مفهومة]

746
00:58:35,050 --> 00:58:45,700
[Hardison] بالضبط. إذا كان (q.size == القدرات) -

747
00:58:45,700 --> 00:58:54,720
لست بحاجة لوضع الأقواس بلدي في المكان المناسب - عودة كاذبة.

748
00:58:54,720 --> 00:59:01,370
تكبير قليلا. حسنا.

749
00:59:01,370 --> 00:59:03,800
الآن ما هو الشيء التالي الذي كان علينا أن نفعل؟

750
00:59:03,800 --> 00:59:11,370
تماما مثل مع مكدس، وإدراج في المكان المناسب.

751
00:59:11,370 --> 00:59:16,010
وذلك ما كان في المكان المناسب لإدراج ذلك؟

752
00:59:16,010 --> 00:59:23,170
مع مكدس كان حجم المؤشر، مع هذا انها ليست تماما أن.

753
00:59:23,170 --> 00:59:30,210
[دانيال] لدي q.head-أو - q.strings >>؟ نعم >>.

754
00:59:30,210 --> 00:59:40,470
q.strings [+ q.head q.size وزارة الدفاع CAPACITY]؟

755
00:59:40,470 --> 00:59:42,740
[Hardison] ونحن ربما تريد وضع أقواس حول هذا

756
00:59:42,740 --> 00:59:48,830
بحيث نحن نحصل على أسبقية المناسبة وذلك أن cleart للجميع.

757
00:59:48,830 --> 00:59:55,800
وتعيين أن المساواة؟ ل>> شارع؟ ل>> شارع. كبيرة.

758
00:59:55,800 --> 01:00:00,160
والآن ما هو الشيء الأخير الذي يتعين علينا القيام به؟

759
01:00:00,160 --> 01:00:06,780
مثلما فعلنا في المكدس. >> بزيادة قيمة حجم؟ >> بزيادة قيمة حجم.

760
01:00:06,780 --> 01:00:13,830
الازدهار. وبعد ذلك، منذ بداية رمز عاد لتوه كاذبة افتراضيا،

761
01:00:13,830 --> 01:00:27,460
نحن نريد تغيير هذا إلى true اذا سارت الامور من خلال وسارت الامور بشكل جيد.

762
01:00:27,460 --> 01:00:33,050
حسنا. وهذا هو الكثير من المعلومات عن القسم.

763
01:00:33,050 --> 01:00:39,480
نحن لسنا أكثر من غاية. نريد أن نتحدث حقا عن منفردة بسرعة المرتبطة القوائم.

764
01:00:39,480 --> 01:00:44,010
سوف أضع هذا الأمر حتى نتمكن من العودة إليها في وقت لاحق.

765
01:00:44,010 --> 01:00:50,850
ولكن دعونا نعود إلى العرض الذي قدمناه لمجرد عدد قليل من أكثر الشرائح.

766
01:00:50,850 --> 01:00:53,790
إدراج بقائمة الانتظار حتى هو TODO، والآن لقد فعلنا ذلك.

767
01:00:53,790 --> 01:00:57,430
>> الآن دعونا نلقي نظرة على قوائم منفردة مرتبطة.

768
01:00:57,430 --> 01:01:00,040
تحدثنا عن هذه أكثر قليلا في المحاضرة.

769
01:01:00,040 --> 01:01:02,540
ورأى عدد من رفاق التجريبي حيث كان لدينا شخص

770
01:01:02,540 --> 01:01:08,220
مشيرا إلى برعونة كل الأرقام الأخرى وعقد؟ كان >> I في ذلك.

771
01:01:08,220 --> 01:01:16,620
>> ماذا يعتقد الرجال؟ فعل ذلك، إزالة الغموض عن هذه نأمل قليلا قليلا؟

772
01:01:16,620 --> 01:01:25,990
مع قائمة، تبين أن نتعامل مع هذا النوع الذي نحن في طريقنا للدعوة الى العقدة.

773
01:01:25,990 --> 01:01:32,520
في حين مع قائمة الانتظار وكان لدينا كومة من البنيات التي كنا ندعو في قائمة الانتظار المكدس،

774
01:01:32,520 --> 01:01:34,860
كان لدينا قائمة انتظار جديدة في هذه الأنواع المكدس،

775
01:01:34,860 --> 01:01:39,240
هنا هو في الحقيقة قائمة حتى أدلى به للتو من مجموعة من العقد.

776
01:01:39,240 --> 01:01:45,920
في بنفس الطريقة التي السلاسل ليست سوى حفنة من حرف اصطف جميع بجانب بعضها البعض.

777
01:01:45,920 --> 01:01:50,650
قائمة مرتبطة هو مجرد عقدة عقدة وآخر وآخر وعقدة عقدة أخرى.

778
01:01:50,650 --> 01:01:55,080
وبدلا من تحطيم كافة العقد معا، وتخزينها بشكل متاخم

779
01:01:55,080 --> 01:01:58,090
كل الحق بجانب بعضها البعض في الذاكرة،

780
01:01:58,090 --> 01:02:04,470
وجود هذا المؤشر التالي يسمح لنا لتخزين العقد في أي مكان، على نحو عشوائي.

781
01:02:04,470 --> 01:02:10,500
ثم النوع من الأسلاك لهم جميعا معا إلى نقطة واحدة من واحدة إلى أخرى.

782
01:02:10,500 --> 01:02:15,850
>> وكان ما ميزة كبيرة أن هذا كان أكثر من مجموعة؟

783
01:02:15,850 --> 01:02:21,680
على كل شيء متاخم تمسك تخزين فقط بجانب بعضها البعض؟

784
01:02:21,680 --> 01:02:24,190
تذكرين؟ نعم؟ تخصيص الذاكرة >> الحيوية؟

785
01:02:24,190 --> 01:02:27,220
تخصيص الذاكرة الديناميكية >> بأي معنى؟

786
01:02:27,220 --> 01:02:31,780
[طالب] في أن تتمكن من الحفاظ مما يجعلها أكبر ولم يكن لديك لنقل مجموعة الخاص بك كامل؟

787
01:02:31,780 --> 01:02:40,940
[Hardison] بالضبط. حتى مع مجموعة، عندما تريد وضع عنصر جديد في وسطها،

788
01:02:40,940 --> 01:02:45,320
لديك لتحويل كل شيء لجعل الفضاء.

789
01:02:45,320 --> 01:02:47,880
وتحدثنا عن مثل مع قائمة الانتظار،

790
01:02:47,880 --> 01:02:50,080
هذا هو السبب في أن نبقي هذا المؤشر الرأس،

791
01:02:50,080 --> 01:02:52,050
بحيث أننا لا تتبدل باستمرار الأشياء.

792
01:02:52,050 --> 01:02:54,520
لأن هذا يحصل مكلفة إذا كنت قد حصلت على مجموعة كبيرة

793
01:02:54,520 --> 01:02:57,130
وكنت تفعل باستمرار هذه الإدراج عشوائي.

794
01:02:57,130 --> 01:03:00,820
في حين مع قائمة، كل ما عليك القيام به هو رميها على عقدة جديدة،

795
01:03:00,820 --> 01:03:06,330
ضبط المؤشرات، والانتهاء من ذلك.

796
01:03:06,330 --> 01:03:10,940
ما تمتص عن هذا؟

797
01:03:10,940 --> 01:03:16,830
وبصرف النظر عن حقيقة انه ليس من السهل العمل مع كصفيف؟ نعم؟

798
01:03:16,830 --> 01:03:22,980
[دانيال] حسنا، أعتقد أنها أكثر صعوبة في الوصول إلى عنصر معين في قائمة مرتبطة؟

799
01:03:22,980 --> 01:03:30,470
[Hardison] لا يمكنك القفز إلى عنصر التعسفي في منتصف قائمة مرتبطة.

800
01:03:30,470 --> 01:03:33,800
كيف يمكنك أن تفعل ذلك بدلا من ذلك؟ لديك >> إلى الخطوة من خلال الشيء بأكمله.

801
01:03:33,800 --> 01:03:35,660
[Hardison] نعم. عليك أن تذهب من خلال واحدة في وقت واحد، واحد في وقت واحد.

802
01:03:35,660 --> 01:03:38,480
انها ضخمة - هذا الألم.

803
01:03:38,480 --> 01:03:41,550
ما هو آخر - هناك آخر سقوط لذلك.

804
01:03:41,550 --> 01:03:45,340
[باسل] لا يمكنك المضي قدما وإلى الخلف؟ عليك أن تذهب اتجاه واحد؟

805
01:03:45,340 --> 01:03:48,570
[Hardison] نعم. لذلك كيف يمكننا حل ذلك، في بعض الأحيان؟

806
01:03:48,570 --> 01:03:53,370
[باسل] المضاعفة المرتبطة القوائم؟ بالضبط >>. هناك قوائم مزدوجة مرتبطة.

807
01:03:53,370 --> 01:03:55,540
هناك أيضا - آسف؟

808
01:03:55,540 --> 01:03:57,620
>> [سام] هل هذا هو نفس الشيء باستخدام PRED ذلك -

809
01:03:57,620 --> 01:04:01,090
تذكرت للتو، ليست ما هو الشيء PRED عنه؟

810
01:04:01,090 --> 01:04:05,850
ليست في مضاعفة بين ومنفردة؟

811
01:04:05,850 --> 01:04:10,020
[Hardison] دعونا ننظر في بالضبط ما كان يقوم به.

812
01:04:10,020 --> 01:04:15,760
حتى هنا نذهب. هنا هو رمز القائمة.

813
01:04:15,760 --> 01:04:25,620
هنا لدينا predptr، هنا. هل هذا ما كنت تتحدث عنه؟

814
01:04:25,620 --> 01:04:30,750
لذلك كان هذا - انه تحرير قائمة وانه يحاول تخزين مؤشر إلى ذلك.

815
01:04:30,750 --> 01:04:35,000
ليست هذه هي مضاعفة، منفردة مرتبطة قوائم.

816
01:04:35,000 --> 01:04:40,090
يمكن أن نتحدث أكثر عن هذا في وقت لاحق لأن هذا هو يتحدث عن تحرير قائمة

817
01:04:40,090 --> 01:04:42,900
وأريد أن أثبت بعض الأشياء الأخرى أولا.

818
01:04:42,900 --> 01:04:51,480
ولكن هذا فقط - انها تذكر قيمة PTR

819
01:04:51,480 --> 01:04:54,170
[طالب] أوه، أنها مؤشر الآنفة الذكر؟ نعم >>.

820
01:04:54,170 --> 01:05:04,070
حتى نتمكن من زيادة ثم PTR نفسها قبل أن الحرة ثم ما هو predptr.

821
01:05:04,070 --> 01:05:09,130
لأن لا يمكننا PTR حرة وثم استدعاء PTR = PTR المقبل، أليس كذلك؟

822
01:05:09,130 --> 01:05:11,260
من شأنها أن تكون سيئة.

823
01:05:11,260 --> 01:05:20,940
لذلك دعونا نرى، مرة أخرى إلى هذا الرجل.

824
01:05:20,940 --> 01:05:23,900
>> والشيء الآخر سيئة عن القوائم هو انه في حين مع مجموعة

825
01:05:23,900 --> 01:05:26,520
لدينا فقط جميع العناصر نفسها مكدسة بجانب بعضها البعض،

826
01:05:26,520 --> 01:05:29,050
هنا لدينا أيضا عرض هذا المؤشر.

827
01:05:29,050 --> 01:05:34,060
ولذلك لا يوجد على قطعة إضافية من الذاكرة أننا الحاجة إلى استخدام

828
01:05:34,060 --> 01:05:37,910
لكل عنصر اننا تخزين في قائمتنا.

829
01:05:37,910 --> 01:05:40,030
نحصل على المرونة، لكنه يأتي في التكلفة.

830
01:05:40,030 --> 01:05:42,230
لأنه يأتي مع الوقت هذه التكلفة،

831
01:05:42,230 --> 01:05:45,270
وأنه يأتي مع هذه التكلفة الذاكرة أيضا.

832
01:05:45,270 --> 01:05:47,800
الوقت بمعنى أن لدينا الآن للذهاب من خلال كل عنصر في مجموعة

833
01:05:47,800 --> 01:05:58,670
العثور على واحد في الفهرس 10، أو التي كانت 10 في مؤشر صفيف.

834
01:05:58,670 --> 01:06:01,230
>> فقط بسرعة حقا، عندما كنا الرسم البياني للخروج هذه القوائم،

835
01:06:01,230 --> 01:06:05,980
عادة نحن الابقاء على رئيس القائمة أو المؤشر الأول من القائمة

836
01:06:05,980 --> 01:06:08,010
ونلاحظ أن هذا هو مؤشر حقيقي.

837
01:06:08,010 --> 01:06:11,100
انها مجرد 4 بايت. انها ليست العقدة الفعلية نفسها.

838
01:06:11,100 --> 01:06:17,120
لذلك أنت ترى أنه لا قيمة له الباحث في ذلك، لا مؤشر القادمة فيه.

839
01:06:17,120 --> 01:06:20,790
انها حرفيا مجرد مؤشر.

840
01:06:20,790 --> 01:06:23,550
انه سيكون للإشارة إلى شيء ما هو البنية عقدة الفعلية.

841
01:06:23,550 --> 01:06:28,480
[سام] مؤشر تسمى العقدة؟ هذا هو >> - لا. هذا هو مؤشر إلى شيء من عقدة نوع.

842
01:06:28,480 --> 01:06:32,540
بل هو مؤشر إلى البنية عقدة. >> أوه، حسنا.

843
01:06:32,540 --> 01:06:36,870
الرسم على الرمز، اليسار إلى اليمين.

844
01:06:36,870 --> 01:06:42,190
يمكننا تعيين إلى فارغة، الذي هو وسيلة جيدة للبدء.

845
01:06:42,190 --> 01:06:49,850
عند الرسم عليها، إما أن تكتب لاغيا أو يمكنك وضع خط من خلال ذلك من هذا القبيل.

846
01:06:49,850 --> 01:06:53,910
>> واحدة من أسهل الطرق للعمل مع القوائم،

847
01:06:53,910 --> 01:06:57,430
ونحن نطلب من كل من كنت prepend وإلحاق لمشاهدة الفرق بين الاثنين،

848
01:06:57,430 --> 01:07:01,320
ولكن معلق مسبقا أسهل بالتأكيد.

849
01:07:01,320 --> 01:07:05,790
عند prepend، وهذا هو المكان الذي - عند prepend (7)،

850
01:07:05,790 --> 01:07:10,050
تذهب وإنشاء البنية عقدة

851
01:07:10,050 --> 01:07:13,870
وقمت بتعيين أول من أشار إلى ذلك، لأنه الآن، لأننا إرفاق مسبقا عليه،

852
01:07:13,870 --> 01:07:17,240
انها ستكون في بداية القائمة.

853
01:07:17,240 --> 01:07:22,540
إذا كنا prepend (3)، التي تخلق عقدة أخرى، ولكن الآن 3 يأتي قبل 7.

854
01:07:22,540 --> 01:07:31,130
ذلك أننا ندفع الأمور أساسا على قائمتنا.

855
01:07:31,130 --> 01:07:34,720
الآن، يمكنك أن ترى أن prepend، وأحيانا يدفع الناس يسمونه،

856
01:07:34,720 --> 01:07:39,600
لأنك تدفع عنصر جديد على القائمة الخاصة بك.

857
01:07:39,600 --> 01:07:43,270
كما انها سهلة لحذف في الجزء الأمامي من قائمة.

858
01:07:43,270 --> 01:07:45,650
لذلك سوف ندعو الناس في كثير من الأحيان أن البوب.

859
01:07:45,650 --> 01:07:52,200
وبهذه الطريقة، يمكنك محاكاة باستخدام كومة قائمة مرتبطة.

860
01:07:52,200 --> 01:07:57,880
يصيح. آسف، ونحن الآن نخوض إلحاقي. وها نحن إرفاق مسبقا (7)، ونحن الآن prepend (3).

861
01:07:57,880 --> 01:08:02,600
إذا كنا إرفاق مسبقا شيء آخر على هذه القائمة، إذا كنا إرفاق مسبقا (4)،

862
01:08:02,600 --> 01:08:06,540
ثم كنت دينا 4 ثم 3 ثم 7.

863
01:08:06,540 --> 01:08:14,220
لذلك فإننا يمكن أن موسيقى البوب ​​وإزالة 4، إزالة 3، إزالة 7.

864
01:08:14,220 --> 01:08:16,500
في كثير من الأحيان أكثر سهولة طريقة للتفكير وهذا هو مع إلحاق.

865
01:08:16,500 --> 01:08:20,310
حتى لقد كنت خارج تخطيطي ما سيبدو مع إلحاق هنا.

866
01:08:20,310 --> 01:08:23,380
هنا، إلحاق (7) لا يبدو مختلفا

867
01:08:23,380 --> 01:08:25,160
لأنه لا يوجد سوى عنصر واحد في القائمة.

868
01:08:25,160 --> 01:08:28,620
وإلحاق (3) يقول في نهاية المطاف.

869
01:08:28,620 --> 01:08:31,020
ربما يمكنك أن ترى الآن الحيلة مع إلحاقي

870
01:08:31,020 --> 01:08:36,600
هو أن نعرف فقط منذ بداية حيث كانت القائمة،

871
01:08:36,600 --> 01:08:39,450
لإلحاق إلى قائمة عليك أن تسير على طول الطريق من خلال قائمة

872
01:08:39,450 --> 01:08:46,500
لنصل الى نهاية، ووقف، ثم بناء العقدة الخاص بك وكل شيء نقر بانخفاض.

873
01:08:46,500 --> 01:08:50,590
سلك كل الاشياء حتى.

874
01:08:50,590 --> 01:08:55,170
حتى مع prepend، ونحن من خلال هذا فقط انفجرت بسرعة حقا،

875
01:08:55,170 --> 01:08:58,170
عند prepend إلى قائمة، انها بسيطة الى حد كبير.

876
01:08:58,170 --> 01:09:02,960
>> جعل لكم عقدة الجديد الخاص بك، تنطوي على بعض تخصيص الذاكرة الديناميكية.

877
01:09:02,960 --> 01:09:09,830
وها نحن نحقق في البنية عقدة باستخدام malloc.

878
01:09:09,830 --> 01:09:14,710
حتى malloc نستخدمه لأن ذلك سوف تخصص الذاكرة بالنسبة لنا في وقت لاحق

879
01:09:14,710 --> 01:09:20,350
لأننا لا نريد هذا - نحن نريد من هذه الذاكرة أن تستمر لفترة طويلة.

880
01:09:20,350 --> 01:09:25,350
ونحصل على مؤشر إلى مساحة في ذاكرة أننا المخصصة فقط.

881
01:09:25,350 --> 01:09:29,260
نستخدم حجم العقدة، ونحن لا جمع الحقول.

882
01:09:29,260 --> 01:09:31,899
نحن لا تولد يدويا عدد البايتات،

883
01:09:31,899 --> 01:09:39,750
بدلا من ذلك نستخدم sizeof بحيث نعرف نحن نحصل على العدد المناسب من وحدات البايت.

884
01:09:39,750 --> 01:09:43,660
أن نتأكد من أن لاختبار دعوتنا malloc نجحت.

885
01:09:43,660 --> 01:09:47,939
هذا هو ما كنت تريد أن تفعل بشكل عام.

886
01:09:47,939 --> 01:09:52,590
على الأجهزة الحديثة، ينفد من الذاكرة ليست شيئا من السهل

887
01:09:52,590 --> 01:09:56,610
إلا إذا كنت تخصيص طن من الاشياء ووضع قائمة ضخمة،

888
01:09:56,610 --> 01:10:02,220
ولكن إذا كنت بناء الاشياء ل، ويقول، مثل اي فون أو أندرويد و،

889
01:10:02,220 --> 01:10:05,230
كنت لديها موارد محدودة الذاكرة، خاصة إذا كنت تفعل شيئا مكثفة.

890
01:10:05,230 --> 01:10:08,300
لذلك من الجيد أن يحصل على أرض الواقع.

891
01:10:08,300 --> 01:10:10,510
>> تلاحظ أن كنت تستخدم زوجين من الوظائف المختلفة هنا

892
01:10:10,510 --> 01:10:12,880
أن كنت قد رأيت التي هي نوع من جديد.

893
01:10:12,880 --> 01:10:15,870
fprintf ذلك هو تماما مثل printf

894
01:10:15,870 --> 01:10:21,320
إلا حجتها الأول هو التيار الذي تريد طباعته.

895
01:10:21,320 --> 01:10:23,900
في هذه الحالة، ونحن نريد لطباعة إلى سلسلة الخطأ المعياري

896
01:10:23,900 --> 01:10:29,410
الذي يختلف عن outstream القياسية.

897
01:10:29,410 --> 01:10:31,620
افتراضيا فإنه يظهر في نفس المكان.

898
01:10:31,620 --> 01:10:34,600
فإنه يطبع أيضا إلى المحطة، ولكن يمكن لك -

899
01:10:34,600 --> 01:10:38,790
باستخدام هذه الأوامر تعلمت عن وتقنيات إعادة توجيه

900
01:10:38,790 --> 01:10:42,290
تعلمت عنها في الفيديو لمجموعة تومي المشكلة 4، يمكنك توجيهها

901
01:10:42,290 --> 01:10:47,900
إلى مناطق مختلفة؛ ثم الخروج، هنا، إنهاء البرنامج الخاص بك.

902
01:10:47,900 --> 01:10:50,440
انها في الأساس مثل العائدين من الرئيسي،

903
01:10:50,440 --> 01:10:53,600
إلا نستخدم الخروج بسبب عودة هنا لن تفعل أي شيء.

904
01:10:53,600 --> 01:10:57,140
نحن لسنا في الرئيسية، بحيث لا يعود الخروج من البرنامج مثل نريد.

905
01:10:57,140 --> 01:11:03,020
لذلك نحن استخدام وظيفة الخروج واعطائها رمز خطأ.

906
01:11:03,020 --> 01:11:11,890
قم بتعيين حقل هنا نحن عقدة جديدة للقيمة، أنا مجالها لتكون مساوية الأول، وبعد ذلك سلك عنه.

907
01:11:11,890 --> 01:11:15,530
وضعنا مؤشر عقدة جديدة القادم للإشارة إلى الأول،

908
01:11:15,530 --> 01:11:20,460
وبعد ذلك سوف أول نقطة الآن إلى عقدة جديدة.

909
01:11:20,460 --> 01:11:25,120
هذه الأسطر الأولى من التعليمات البرمجية، ونحن في الواقع بناء عقدة جديدة.

910
01:11:25,120 --> 01:11:27,280
ليس آخر سطرين من هذه الوظيفة ولكن تلك الأولى.

911
01:11:27,280 --> 01:11:30,290
يمكنك سحب فعلا إلى وظيفة، وظيفة في مساعد.

912
01:11:30,290 --> 01:11:32,560
هذا غالبا ما أقوم به هو، وأنا تخلعها في وظيفة،

913
01:11:32,560 --> 01:11:36,040
أسميها عقدة شيء من هذا القبيل بناء،

914
01:11:36,040 --> 01:11:40,410
والتي تحافظ على وظيفة prepend صغيرة جدا، انها مجرد 3 خطوط الحين.

915
01:11:40,410 --> 01:11:48,710
أقوم بإجراء مكالمة لمهامي عقدة الإنشاء، وبعد ذلك كل شيء حتى الأسلاك.

916
01:11:48,710 --> 01:11:51,970
>> الشيء الأخير أريد أن تظهر لك،

917
01:11:51,970 --> 01:11:54,030
وسوف تتيح لك القيام إلحاقي وأن جميع لوحدك،

918
01:11:54,030 --> 01:11:57,500
هو كيفية تكرار عبر قائمة.

919
01:11:57,500 --> 01:12:00,780
هناك مجموعة من الطرق المختلفة لتكرار عبر قائمة.

920
01:12:00,780 --> 01:12:03,140
في هذه الحالة، ونحن في طريقنا للعثور على طول القائمة.

921
01:12:03,140 --> 01:12:06,570
حتى نبدأ مع طول = 0.

922
01:12:06,570 --> 01:12:11,580
هذه هي مشابهة جدا لكتابة التوابع strlen للسلسلة.

923
01:12:11,580 --> 01:12:17,780
هذا ما أريد أن تظهر لك، هذه لحلقة هنا.

924
01:12:17,780 --> 01:12:23,530
يبدو كيندا غير تقليدي، بل ليست المعتادة كثافة العمليات ط = 0، I <أيا كان، أنا + +.

925
01:12:23,530 --> 01:12:34,920
بدلا من ذلك انها تهيئة ن لدينا متغير ليكون بداية القائمة.

926
01:12:34,920 --> 01:12:40,620
ثم لدينا متغير بينما هو مكرر غير فارغة، ونحافظ على الذهاب.

927
01:12:40,620 --> 01:12:46,340
هذا هو لأنه، حسب الاتفاقية، نهاية قائمتنا ستكون فارغة.

928
01:12:46,340 --> 01:12:48,770
ومن ثم إلى زيادة، بدلا من القيام + +،

929
01:12:48,770 --> 01:12:57,010
ما يعادل من قائمة مرتبطة + + هو ن = ن> المقبل.

930
01:12:57,010 --> 01:13:00,410
>> سادعك سد الثغرات هنا لأننا من الوقت.

931
01:13:00,410 --> 01:13:09,300
ولكن يبقى هذا الأمر في الاعتبار أثناء العمل على psets spellr الخاص بك.

932
01:13:09,300 --> 01:13:11,650
القوائم المرتبطة، إذا كنت تنفيذ جدول التجزئة،

933
01:13:11,650 --> 01:13:14,010
بالتأكيد سوف يأتي في سهل للغاية.

934
01:13:14,010 --> 01:13:21,780
وسوف تواجه هذا المصطلح لحلقات أكثر الأشياء التي تجعل الحياة أسهل كثيرا، ونأمل.

935
01:13:21,780 --> 01:13:25,910
أي أسئلة، بسرعة؟

936
01:13:25,910 --> 01:13:28,920
[سام] هل ترسل SLL المنجزة والشوري؟

937
01:13:28,920 --> 01:13:38,360
[Hardison] نعم. أنا ترسل الشرائح المنجزة والانتهاء كومة SLL وqueue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]