1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Στον προγραμματισμό, θα πρέπει συχνά να αποτελούν τους καταλόγους των τιμών,

2
00:00:10,050 --> 00:00:12,840
όπως τα ονόματα των μαθητών σε ένα τμήμα

3
00:00:12,840 --> 00:00:15,100
ή τις επιδόσεις τους στις τελευταίες κουίζ.

4
00:00:15,100 --> 00:00:17,430
>> Στη γλώσσα C, δήλωσε συστοιχίες μπορούν να χρησιμοποιηθούν

5
00:00:17,430 --> 00:00:19,160
να αποθηκεύετε τις λίστες.

6
00:00:19,160 --> 00:00:21,200
Είναι εύκολο να απαριθμήσει τα στοιχεία μιας λίστας

7
00:00:21,200 --> 00:00:23,390
αποθηκεύονται σε μια σειρά, και αν χρειάζεται να αποκτήσετε πρόσβαση

8
00:00:23,390 --> 00:00:25,050
ή να τροποποιήσει το i-στοιχείο της λίστας

9
00:00:25,050 --> 00:00:27,570
για κάποια αυθαίρετη δείκτη Ι,

10
00:00:27,570 --> 00:00:29,910
αυτό μπορεί να γίνει σε σταθερό χρόνο,

11
00:00:29,910 --> 00:00:31,660
συστοιχίες, αλλά έχουν μειονεκτήματα, πάρα πολύ.

12
00:00:31,660 --> 00:00:33,850
>> Όταν τους δηλώνουν, είμαστε υποχρεωμένη να πείτε

13
00:00:33,850 --> 00:00:35,900
μπροστά πόσο μεγάλη είναι,

14
00:00:35,900 --> 00:00:38,160
δηλαδή, πόσα στοιχεία μπορούν να αποθηκεύσουν

15
00:00:38,160 --> 00:00:40,780
και πόσο μεγάλη είναι αυτά τα στοιχεία, η οποία καθορίζεται από τον τύπο τους.

16
00:00:40,780 --> 00:00:45,450
Για παράδειγμα, int arr (10)

17
00:00:45,450 --> 00:00:48,220
μπορεί να αποθηκεύσει 10 αντικείμενα

18
00:00:48,220 --> 00:00:50,200
που είναι το μέγεθος ενός int.

19
00:00:50,200 --> 00:00:52,590
>> Δεν μπορούμε να αλλάξουμε το μέγεθος μιας συστοιχίας μετά από δήλωση.

20
00:00:52,590 --> 00:00:55,290
Πρέπει να κάνουμε μια νέα σειρά, αν θέλουμε να αποθηκεύουν περισσότερα στοιχεία.

21
00:00:55,290 --> 00:00:57,410
Ο λόγος που υπάρχει αυτός ο περιορισμός είναι ότι μας

22
00:00:57,410 --> 00:00:59,040
πρόγραμμα αποθηκεύει ολόκληρη η συστοιχία

23
00:00:59,040 --> 00:01:02,310
ως ένα συνεχές κομμάτι της μνήμης.

24
00:01:02,310 --> 00:01:04,500
Πείτε αυτό είναι το ρυθμιστικό όπου θα αποθηκεύονται στον πίνακα μας.

25
00:01:04,500 --> 00:01:06,910
Μπορεί να υπάρχουν άλλες μεταβλητές

26
00:01:06,910 --> 00:01:08,310
Βρίσκεται ακριβώς δίπλα στη συστοιχία

27
00:01:08,310 --> 00:01:10,060
στη μνήμη, έτσι δεν μπορούμε να

28
00:01:10,060 --> 00:01:12,060
μόλις κάνει την σειρά μεγαλύτερο.

29
00:01:12,060 --> 00:01:15,700
>> Μερικές φορές θα θέλαμε να το εμπόριο γρήγορη ταχύτητα πρόσβασης της συστοιχίας των δεδομένων

30
00:01:15,700 --> 00:01:17,650
για λίγο μεγαλύτερη ευελιξία.

31
00:01:17,650 --> 00:01:20,380
Εισάγετε τη συνδεδεμένη λίστα, μια άλλη βασική δομή δεδομένων

32
00:01:20,380 --> 00:01:22,360
μπορεί να μην είναι τόσο εξοικειωμένοι με.

33
00:01:22,360 --> 00:01:24,200
Σε ένα υψηλό επίπεδο,

34
00:01:24,200 --> 00:01:26,840
α συνδεδεμένη λίστα αποθηκεύει δεδομένα σε μια ακολουθία των κόμβων

35
00:01:26,840 --> 00:01:29,280
που συνδέονται μεταξύ τους με συνδέσμους,

36
00:01:29,280 --> 00:01:31,760
εξ ου και η ονομασία «συνδεδεμένη λίστα.

37
00:01:31,760 --> 00:01:33,840
Όπως θα δούμε, αυτή η διαφορά στο σχεδιασμό

38
00:01:33,840 --> 00:01:35,500
οδηγεί σε διαφορετικά πλεονεκτήματα και μειονεκτήματα

39
00:01:35,500 --> 00:01:37,000
από μια συστοιχία.

40
00:01:37,000 --> 00:01:39,840
>> Εδώ είναι μερικά κώδικα C για μια σχέση πολύ απλή λίστα των ακεραίων.

41
00:01:39,840 --> 00:01:42,190
Μπορείτε να δείτε ότι έχουμε εκπροσωπούνται σε κάθε κόμβο

42
00:01:42,190 --> 00:01:45,520
στη λίστα ως ένα struct που περιέχει 2 πράγματα,

43
00:01:45,520 --> 00:01:47,280
ένας ακέραιος για την αποθήκευση ονομάζεται «val»

44
00:01:47,280 --> 00:01:50,460
και ένα σύνδεσμο στον επόμενο κόμβο της λίστας

45
00:01:50,460 --> 00:01:52,990
που εμείς εκπροσωπούμε ως δείκτη που ονομάζεται «επόμενο».

46
00:01:54,120 --> 00:01:56,780
Με αυτό τον τρόπο, μπορούμε να εντοπίσουμε ολόκληρη τη λίστα

47
00:01:56,780 --> 00:01:58,790
με ένα μόνο δείκτη στο πρώτο κόμβο,

48
00:01:58,790 --> 00:02:01,270
και στη συνέχεια μπορούμε να ακολουθήσουμε τα επόμενα δείκτες

49
00:02:01,270 --> 00:02:03,130
στο 2ο κόμβο,

50
00:02:03,130 --> 00:02:05,280
στο 3ο κόμβο,

51
00:02:05,280 --> 00:02:07,000
στο 4ο κόμβο,

52
00:02:07,000 --> 00:02:09,889
και ούτω καθεξής, μέχρι να φτάσουμε στο τέλος της λίστας.

53
00:02:10,520 --> 00:02:12,210
>> Ίσως να είναι σε θέση να βλέπετε 1 πλεονέκτημα αυτό έχει

54
00:02:12,210 --> 00:02:14,490
πάνω από την στατική δομή συστοιχίας - με μια συνδεδεμένη λίστα,

55
00:02:14,490 --> 00:02:16,450
δεν χρειαζόμαστε ένα μεγάλο κομμάτι της μνήμης συνολικά.

56
00:02:17,400 --> 00:02:20,530
Το 1ο κόμβο της λίστας θα μπορούσε να ζήσει σε αυτό το χώρο στη μνήμη,

57
00:02:20,530 --> 00:02:23,160
και ο 2ος κόμβος θα μπορούσε να είναι σε όλη τη διαδρομή εδώ.

58
00:02:23,160 --> 00:02:25,780
Μπορούμε να πάρουμε σε όλους τους κόμβους ανεξάρτητα από το πού στη μνήμη θα είναι,

59
00:02:25,780 --> 00:02:28,890
διότι ξεκινώντας από το πρώτο κόμβο, το επόμενο δείκτη κάθε κόμβου

60
00:02:28,890 --> 00:02:31,700
μας λέει ακριβώς πού να πάει δίπλα.

61
00:02:31,700 --> 00:02:33,670
>> Επιπλέον, δεν έχουμε να πούμε εκ των προτέρων

62
00:02:33,670 --> 00:02:36,740
πόσο μεγάλη είναι μια συνδεδεμένη λίστα θα είναι ο τρόπος που κάνουμε με στατικές συστοιχίες,

63
00:02:36,740 --> 00:02:39,060
αφού μπορούμε να συνεχίσουμε να προσθέτουμε κόμβους σε μια λίστα

64
00:02:39,060 --> 00:02:42,600
εφ 'όσον υπάρχει χώρος κάπου στη μνήμη για νέους κόμβους.

65
00:02:42,600 --> 00:02:45,370
Ως εκ τούτου, συνδεδεμένες λίστες είναι εύκολο να αλλάξετε το μέγεθος δυναμικά.

66
00:02:45,370 --> 00:02:47,950
Πείτε, αργότερα στο πρόγραμμα θα πρέπει να προσθέσετε περισσότερους κόμβους

67
00:02:47,950 --> 00:02:49,350
στη λίστα μας.

68
00:02:49,350 --> 00:02:51,480
Για να εισάγετε ένα νέο κόμβο στην λίστα μας on the fly,

69
00:02:51,480 --> 00:02:53,740
το μόνο που έχουμε να κάνουμε είναι να εκχωρήσει μνήμη για αυτόν τον κόμβο,

70
00:02:53,740 --> 00:02:55,630
γδούπο της αξίας των δεδομένων,

71
00:02:55,630 --> 00:02:59,070
και τοποθετήστε το στη συνέχεια, όπου θέλουμε με την προσαρμογή των κατάλληλων δεικτών.

72
00:02:59,070 --> 00:03:02,310
>> Για παράδειγμα, αν θέλαμε να τοποθετήσετε ένα κόμβο μεταξύ

73
00:03:02,310 --> 00:03:04,020
το 2ο και 3ο κόμβους της λίστας,

74
00:03:04,020 --> 00:03:06,800
 δεν θα πρέπει να μετακινήσετε το 2ο ή 3ο κόμβους καθόλου.

75
00:03:06,800 --> 00:03:09,190
Πείτε είμαστε εισάγοντας αυτό το κόκκινο κόμβο.

76
00:03:09,190 --> 00:03:12,890
Το μόνο που θα έχετε να κάνετε είναι δίπλα δείκτη του νέου κόμβου

77
00:03:12,890 --> 00:03:14,870
στο σημείο να τον 3ο κόμβο

78
00:03:14,870 --> 00:03:18,580
και στη συνέχεια επανακαλωδίωναν επόμενο δείκτη του 2ου κόμβου

79
00:03:18,580 --> 00:03:20,980
να επισημάνει νέο κόμβο μας.

80
00:03:22,340 --> 00:03:24,370
Έτσι, μπορούμε να αλλάξετε το μέγεθος των καταλόγων μας on the fly

81
00:03:24,370 --> 00:03:26,090
δεδομένου ότι ο υπολογιστής μας δεν βασίζεται σε ευρετηρίαση,

82
00:03:26,090 --> 00:03:28,990
αλλά μάλλον για τη σύνδεση με δείκτες για να τις αποθηκεύσετε.

83
00:03:29,120 --> 00:03:31,600
>> Ωστόσο, ένα μειονέκτημα της συνδεδεμένες λίστες

84
00:03:31,600 --> 00:03:33,370
είναι ότι, σε αντίθεση με μια στατική σειρά,

85
00:03:33,370 --> 00:03:36,690
ο υπολογιστής δεν μπορεί να πηδήξει μόνο στη μέση της λίστας.

86
00:03:38,040 --> 00:03:40,780
Δεδομένου ότι ο υπολογιστής έχει να επισκεφτεί κάθε κόμβο στην συνδεδεμένη λίστα

87
00:03:40,780 --> 00:03:42,330
για να φτάσουμε στο επόμενο,

88
00:03:42,330 --> 00:03:44,770
πρόκειται να λάβει περισσότερο χρόνο για να βρείτε ένα συγκεκριμένο κόμβο

89
00:03:44,770 --> 00:03:46,400
από ό, τι θα ήταν σε μία συστοιχία.

90
00:03:46,400 --> 00:03:48,660
Για να διασχίσει ολόκληρη η λίστα παίρνει χρόνο ανάλογο

91
00:03:48,660 --> 00:03:50,580
προς το μήκος του πίνακα,

92
00:03:50,580 --> 00:03:54,630
ή O (n) σε ασυμπτωτικό συμβολισμό.

93
00:03:54,630 --> 00:03:56,510
Κατά μέσο όρο, φθάνοντας σε κάθε κόμβο

94
00:03:56,510 --> 00:03:58,800
Επίσης, χρειάζεται χρόνο ανάλογο του n.

95
00:03:58,800 --> 00:04:00,700
>> Τώρα, ας γράψει πραγματικά κάποια κώδικα

96
00:04:00,700 --> 00:04:02,000
που λειτουργεί με συνδεδεμένες λίστες.

97
00:04:02,000 --> 00:04:04,220
Ας πούμε ότι θέλουμε μια συνδεδεμένη λίστα ακεραίων.

98
00:04:04,220 --> 00:04:06,140
Μπορούμε να αποτελέσει κόμβο στη λίστα μας και πάλι

99
00:04:06,140 --> 00:04:08,340
ως ένα struct με 2 πεδία,

100
00:04:08,340 --> 00:04:10,750
μια ακέραια τιμή που ονομάζεται «val»

101
00:04:10,750 --> 00:04:13,490
και ένα επόμενο δείκτη στον επόμενο κόμβο της λίστας.

102
00:04:13,490 --> 00:04:15,660
Λοιπόν, φαίνεται αρκετά απλό.

103
00:04:15,660 --> 00:04:17,220
>> Ας πούμε ότι θέλουμε να γράψουμε μια συνάρτηση

104
00:04:17,220 --> 00:04:19,329
που διατρέχει τον κατάλογο και εκτυπώνει το

105
00:04:19,329 --> 00:04:22,150
τιμή που είναι αποθηκευμένη στο τελευταίο κόμβο του καταλόγου.

106
00:04:22,150 --> 00:04:24,850
Λοιπόν, αυτό σημαίνει ότι θα πρέπει να διασχίσει όλους τους κόμβους στη λίστα

107
00:04:24,850 --> 00:04:27,310
για να βρείτε το τελευταίο, αλλά επειδή δεν είμαστε προσθέτοντας

108
00:04:27,310 --> 00:04:29,250
ή διαγράφοντας οτιδήποτε, δεν θέλουμε να αλλάξουμε

109
00:04:29,250 --> 00:04:32,210
η εσωτερική δομή των επόμενων δείκτες στη λίστα.

110
00:04:32,210 --> 00:04:34,790
>> Έτσι, θα χρειαστούμε ένα δείκτη ειδικά για την διάσχιση

111
00:04:34,790 --> 00:04:36,940
το οποίο θα καλέσουμε «ανίχνευσης».

112
00:04:36,940 --> 00:04:38,870
Θα ανιχνεύσουμε μέσα από όλα τα στοιχεία της λίστας

113
00:04:38,870 --> 00:04:41,190
ακολουθώντας την αλυσίδα των επόμενοι δείκτες.

114
00:04:41,190 --> 00:04:43,750
Το μόνο που έχετε αποθηκεύσει είναι ένας δείκτης στον κόμβο 1ο,

115
00:04:43,750 --> 00:04:45,730
ή «κεφαλή» της λίστας.

116
00:04:45,730 --> 00:04:47,370
Επικεφαλής σημεία στον κόμβο 1ο.

117
00:04:47,370 --> 00:04:49,120
Είναι του τύπου δείκτη-σε-κόμβο.

118
00:04:49,120 --> 00:04:51,280
>> Για να πάρετε την πραγματική 1ο κόμβο της λίστας,

119
00:04:51,280 --> 00:04:53,250
πρέπει να dereference αυτό το δείκτη,

120
00:04:53,250 --> 00:04:55,100
αλλά για να μπορέσουμε να το dereference, θα πρέπει να ελέγξετε

121
00:04:55,100 --> 00:04:57,180
αν ο δείκτης είναι μηδενική πρώτα.

122
00:04:57,180 --> 00:04:59,190
Αν είναι μηδενική, η λίστα είναι κενή,

123
00:04:59,190 --> 00:05:01,320
και θα πρέπει να εκτυπώσετε ένα μήνυμα που, επειδή η λίστα είναι κενή,

124
00:05:01,320 --> 00:05:03,250
δεν υπάρχει τελευταίο κόμβο.

125
00:05:03,250 --> 00:05:05,190
Αλλά, ας υποθέσουμε ότι η λίστα δεν είναι κενή.

126
00:05:05,190 --> 00:05:08,340
Αν δεν είναι, τότε θα πρέπει να ανιχνεύσουμε μέσα από ολόκληρη την λίστα

127
00:05:08,340 --> 00:05:10,440
μέχρι να φτάσουμε στο τελευταίο κόμβο της λίστας,

128
00:05:10,440 --> 00:05:13,030
και πώς μπορούμε να πει εάν ψάχνουμε στο τελευταίο κόμβο της λίστας;

129
00:05:13,670 --> 00:05:16,660
>> Λοιπόν, αν η επόμενη δείκτης ενός κόμβου είναι άκυρη,

130
00:05:16,660 --> 00:05:18,320
ξέρουμε ότι είμαστε στο τέλος

131
00:05:18,320 --> 00:05:22,390
δεδομένου ότι η τελευταία επόμενη δείκτης δεν θα έχει επόμενο κόμβο της λίστας να επισημάνω.

132
00:05:22,390 --> 00:05:26,590
Είναι καλή πρακτική να κρατήσει πάντα δίπλα δείκτη του τελευταίου κόμβου αρχικοποιείται σε null

133
00:05:26,590 --> 00:05:30,800
να έχουν μια τυποποιημένη ιδιότητα που μας ειδοποιεί όταν έχουμε φτάσει στο τέλος της λίστας.

134
00:05:30,800 --> 00:05:33,510
>> Έτσι, αν ερπυστριοφόρο → επόμενο είναι μηδενική,

135
00:05:34,120 --> 00:05:38,270
θυμηθείτε ότι η σύνταξη βέλος είναι μια συντόμευση για την εύρεση τιμών

136
00:05:38,270 --> 00:05:40,010
ένα δείκτη σε struct, στη συνέχεια, την πρόσβαση

137
00:05:40,010 --> 00:05:42,510
επόμενο πεδίο της ισοδυναμεί με την αμήχανη:

138
00:05:42,510 --> 00:05:48,750
(Ερπυστριοφόρο *). Επόμενη.

139
00:05:49,820 --> 00:05:51,260
Μόλις βρήκαμε τον τελευταίο κόμβο,

140
00:05:51,260 --> 00:05:53,830
θέλουμε να εκτυπώσετε ερπυστριοφόρο → val,

141
00:05:53,830 --> 00:05:55,000
η τιμή στον τρέχοντα κόμβο

142
00:05:55,000 --> 00:05:57,130
γνωρίζουμε ποια είναι η τελευταία.

143
00:05:57,130 --> 00:05:59,740
Διαφορετικά, αν δεν είμαστε ακόμα στο τελευταίο κόμβο της λίστας,

144
00:05:59,740 --> 00:06:02,340
πρέπει να προχωρήσουμε στο επόμενο κόμβο της λίστας

145
00:06:02,340 --> 00:06:04,750
και ελέγξτε αν αυτό είναι το τελευταίο.

146
00:06:04,750 --> 00:06:07,010
Για να το κάνετε αυτό, εμείς που απλώς δείκτη ανίχνευσης μας

147
00:06:07,010 --> 00:06:09,840
να επισημάνει στην επόμενη αξία του τρέχοντος κόμβου,

148
00:06:09,840 --> 00:06:11,680
δηλαδή, ο επόμενος κόμβος στη λίστα.

149
00:06:11,680 --> 00:06:13,030
Αυτό γίνεται με ρύθμιση

150
00:06:13,030 --> 00:06:15,280
ερπυστριοφόρο = ερπυστριοφόρο → επόμενη.

151
00:06:16,050 --> 00:06:18,960
Τότε επαναλάβουμε αυτή τη διαδικασία, με μια θηλιά, για παράδειγμα,

152
00:06:18,960 --> 00:06:20,960
μέχρι να βρούμε το τελευταίο κόμβο.

153
00:06:20,960 --> 00:06:23,150
Έτσι, για παράδειγμα, εάν ερπυστριοφόρα έδειχνε στο κεφάλι,

154
00:06:24,050 --> 00:06:27,710
θέτουμε ερπυστριοφόρο να επισημάνω με ερπυστριοφόρο → επόμενη,

155
00:06:27,710 --> 00:06:30,960
η οποία είναι η ίδια όπως στο επόμενο πεδίο του κόμβου πρώτο.

156
00:06:30,960 --> 00:06:33,620
Έτσι, τώρα ανίχνευσής μας είναι στραμμένη στο 2ο κόμβο,

157
00:06:33,620 --> 00:06:35,480
και, πάλι, επαναλαμβάνουμε αυτό με έναν βρόχο,

158
00:06:37,220 --> 00:06:40,610
μέχρι να βρεθεί το τελευταίο κόμβο, δηλαδή,

159
00:06:40,610 --> 00:06:43,640
όπου δίπλα δείκτης του κόμβου δείχνει σε null.

160
00:06:43,640 --> 00:06:45,070
Και εκεί έχουμε,

161
00:06:45,070 --> 00:06:47,620
βρήκαμε το τελευταίο κόμβο της λίστας, και να εκτυπώσετε την αξία του,

162
00:06:47,620 --> 00:06:50,800
χρησιμοποιούμε μόνο ερπυστριοφόρο → val.

163
00:06:50,800 --> 00:06:53,130
>> Διασχίζοντας δεν είναι τόσο κακή, αλλά τι γίνεται με την εισαγωγή;

164
00:06:53,130 --> 00:06:56,290
Ας υποθέσουμε ότι θέλετε να εισάγετε έναν ακέραιο στην 4η θέση

165
00:06:56,290 --> 00:06:58,040
σε έναν ακέραιο κατάλογο.

166
00:06:58,040 --> 00:07:01,280
Αυτό είναι μεταξύ των σημερινών 3ου και 4ου κόμβους.

167
00:07:01,280 --> 00:07:03,760
Πάλι, πρέπει να διασχίσει το λίστα μόνο για να

168
00:07:03,760 --> 00:07:06,520
φτάσετε στο 3ο στοιχείο, το ένα είμαστε μετά την εισαγωγή.

169
00:07:06,520 --> 00:07:09,300
Έτσι, δημιουργούμε ένα δείκτη ανίχνευσης και πάλι να διασχίσει τη λίστα,

170
00:07:09,300 --> 00:07:11,400
ελέγξτε αν ο δείκτης κεφάλι μας είναι μηδενική,

171
00:07:11,400 --> 00:07:14,810
και αν δεν είναι, το σημείο ανίχνευσης δείκτη μας στον κόμβο κεφάλι.

172
00:07:16,880 --> 00:07:18,060
Έτσι, είμαστε στο στοιχείο 1ο.

173
00:07:18,060 --> 00:07:21,020
Πρέπει να προχωρήσουμε 2 περισσότερα στοιχεία για να μπορέσουμε να εισάγετε,

174
00:07:21,020 --> 00:07:23,390
ώστε να μπορούμε να χρησιμοποιούμε ένα for loop

175
00:07:23,390 --> 00:07:26,430
int i = 1? i <3? i + +

176
00:07:26,430 --> 00:07:28,590
και σε κάθε επανάληψη του βρόχου,

177
00:07:28,590 --> 00:07:31,540
εκ των προτέρων δείκτη ανίχνευσής μας προς τα εμπρός με 1 κόμβο

178
00:07:31,540 --> 00:07:34,570
ελέγχοντας αν επόμενο πεδίο του τρέχοντος κόμβου είναι άκυρη,

179
00:07:34,570 --> 00:07:37,550
και αν δεν είναι, μετακινήστε το δείκτη του ανίχνευσής μας στον επόμενο κόμβο

180
00:07:37,550 --> 00:07:41,810
θέτοντας το ίσο με το επόμενο δείκτη του τρέχοντος κόμβου.

181
00:07:41,810 --> 00:07:45,210
Έτσι, αφού για το βρόχο μας λέει να κάνουμε ότι

182
00:07:45,210 --> 00:07:47,550
δύο φορές,

183
00:07:49,610 --> 00:07:51,190
έχουμε φτάσει στο 3ο κόμβο,

184
00:07:51,190 --> 00:07:53,110
και μόλις ο δείκτης ανίχνευσής μας έχει φτάσει στο κόμβο μετά

185
00:07:53,110 --> 00:07:55,270
που θέλουμε να εισάγετε νέα μας ακέραιο,

186
00:07:55,270 --> 00:07:57,050
πώς μπορούμε πραγματικά να κάνουμε την εισαγωγή;

187
00:07:57,050 --> 00:07:59,440
>> Λοιπόν, τα νέα μας ακέραιος πρέπει να εισαχθεί μέσα στον κατάλογο

188
00:07:59,440 --> 00:08:01,250
ως μέρος της δικής της struct node,

189
00:08:01,250 --> 00:08:03,140
δεδομένου ότι αυτό είναι πραγματικά μια ακολουθία κόμβων.

190
00:08:03,140 --> 00:08:05,690
Έτσι, ας κάνουμε ένα νέο δείκτη στον κόμβο

191
00:08:05,690 --> 00:08:08,910
που ονομάζεται «new_node,"

192
00:08:08,910 --> 00:08:11,800
και που να δείχνουν ότι η μνήμη τώρα διαθέσει

193
00:08:11,800 --> 00:08:14,270
στο σωρό για τον ίδιο κόμβο,

194
00:08:14,270 --> 00:08:16,000
και πόση μνήμη χρειαζόμαστε να διαθέσει;

195
00:08:16,000 --> 00:08:18,250
Λοιπόν, το μέγεθος ενός κόμβου,

196
00:08:20,450 --> 00:08:23,410
και θέλουμε να θέσουμε στον τομέα της val στο ακέραιο ότι θέλουμε να εισάγετε.

197
00:08:23,410 --> 00:08:25,590
Ας πούμε, 6.

198
00:08:25,590 --> 00:08:27,710
Τώρα, ο κόμβος περιέχει ακέραια τιμή μας.

199
00:08:27,710 --> 00:08:30,650
Είναι επίσης καλή πρακτική να προετοιμαστεί επόμενο πεδίο του νέου κόμβου

200
00:08:30,650 --> 00:08:33,690
να επισημάνω σε null,

201
00:08:33,690 --> 00:08:35,080
αλλά τώρα τι;

202
00:08:35,080 --> 00:08:37,179
>> Πρέπει να αλλάξουμε την εσωτερική δομή της λίστας

203
00:08:37,179 --> 00:08:40,409
και οι επόμενοι δείκτες που περιέχονται στην υφιστάμενη της λίστας

204
00:08:40,409 --> 00:08:42,950
3η και 4η κόμβους.

205
00:08:42,950 --> 00:08:46,560
Δεδομένου ότι οι επόμενοι δείκτες καθορίζουν τη σειρά της λίστας,

206
00:08:46,560 --> 00:08:48,650
και επειδή είμαστε εισαγωγή νέου κόμβου μας

207
00:08:48,650 --> 00:08:50,510
δεξιά στη μέση του καταλόγου,

208
00:08:50,510 --> 00:08:52,010
μπορεί να είναι λίγο δύσκολο.

209
00:08:52,010 --> 00:08:54,250
Αυτό συμβαίνει διότι, θυμηθείτε, ο υπολογιστής μας

210
00:08:54,250 --> 00:08:56,250
γνωρίζει μόνο τη θέση των κόμβων στη λίστα

211
00:08:56,250 --> 00:09:00,400
λόγω των επόμενοι δείκτες αποθηκεύονται στις προηγούμενες κόμβους.

212
00:09:00,400 --> 00:09:03,940
Έτσι, αν έχουμε χάσει ποτέ κομμάτι από οποιαδήποτε από αυτές τις περιοχές,

213
00:09:03,940 --> 00:09:06,860
λένε αλλάζοντας ένα από τα επόμενα δείκτες στην λίστα μας,

214
00:09:06,860 --> 00:09:09,880
Για παράδειγμα, ας πούμε ότι άλλαξε

215
00:09:09,880 --> 00:09:12,920
επόμενο πεδίο του τρίτου κόμβου

216
00:09:12,920 --> 00:09:15,610
να επισημάνω σε κάποιο κόμβο εδώ.

217
00:09:15,610 --> 00:09:17,920
Θα ήθελα να είναι από την τύχη, γιατί δεν θα

218
00:09:17,920 --> 00:09:20,940
έχει καμία ιδέα πού να βρει το υπόλοιπο της λίστας,

219
00:09:20,940 --> 00:09:23,070
και ότι είναι προφανώς πολύ άσχημα.

220
00:09:23,070 --> 00:09:25,080
Έτσι, πρέπει να είμαστε πολύ προσεκτικοί σχετικά με την παραγγελία

221
00:09:25,080 --> 00:09:28,360
στην οποία θα χειριστείτε επόμενη δείκτες μας κατά τη διάρκεια της εισαγωγής.

222
00:09:28,360 --> 00:09:30,540
>> Έτσι, για να απλοποιηθεί αυτό, ας πούμε ότι

223
00:09:30,540 --> 00:09:32,220
4 πρώτους κόμβους μας

224
00:09:32,220 --> 00:09:36,200
ονομάζονται Α, Β, Γ, και Δ, με τα βέλη που αντιπροσωπεύουν την αλυσίδα από δείκτες

225
00:09:36,200 --> 00:09:38,070
που συνδέουν τους κόμβους.

226
00:09:38,070 --> 00:09:40,050
Έτσι, θα πρέπει να εισάγετε νέο κόμβο μας

227
00:09:40,050 --> 00:09:42,070
μεταξύ κόμβων στο C και D.

228
00:09:42,070 --> 00:09:45,060
Είναι ζωτικής σημασίας να το κάνει με τη σωστή σειρά, και θα σας δείξω γιατί.

229
00:09:45,060 --> 00:09:47,500
>> Ας ρίξουμε μια ματιά σε λάθος τρόπος για να το κάνει πρώτα.

230
00:09:47,500 --> 00:09:49,490
Γεια σου, ξέρουμε ο νέος κόμβος πρέπει να έρθει αμέσως μετά C,

231
00:09:49,490 --> 00:09:51,910
οπότε ας δίπλα δείκτη Γ

232
00:09:51,910 --> 00:09:54,700
στο σημείο να new_node.

233
00:09:56,530 --> 00:09:59,180
Εντάξει, φαίνεται εντάξει, εμείς απλά πρέπει να τελειώσει μέχρι τώρα από

234
00:09:59,180 --> 00:10:01,580
κάνοντας επόμενο σημείο δείκτη του νέου κόμβου στο Δ,

235
00:10:01,580 --> 00:10:03,250
αλλά περιμένετε, πώς μπορούμε να το κάνουμε αυτό;

236
00:10:03,250 --> 00:10:05,170
Το μόνο πράγμα που θα μπορούσε να μας πει πού ήταν D,

237
00:10:05,170 --> 00:10:07,630
ήταν ο επόμενος δείκτης προηγουμένως αποθηκευτεί στο C,

238
00:10:07,630 --> 00:10:09,870
αλλά εμείς ξαναέγραψε ακριβώς αυτό το δείκτη

239
00:10:09,870 --> 00:10:11,170
να επισημάνει στο νέο κόμβο,

240
00:10:11,170 --> 00:10:14,230
έτσι δεν έχουμε πλέον καμία ένδειξη όπου D είναι στη μνήμη,

241
00:10:14,230 --> 00:10:17,020
και έχουμε χάσει το υπόλοιπο της λίστας.

242
00:10:17,020 --> 00:10:19,000
Δεν είναι καλή σε όλα.

243
00:10:19,000 --> 00:10:21,090
>> Έτσι, πώς θα το κάνουμε αυτό το δικαίωμα;

244
00:10:22,360 --> 00:10:25,090
Κατ 'αρχάς, το σημείο δίπλα δείκτη του νέου κόμβου στο D.

245
00:10:26,170 --> 00:10:28,990
Τώρα, τόσο η νέα κόμβου και C επόμενοι δείκτες

246
00:10:28,990 --> 00:10:30,660
οδηγούν στον ίδιο κόμβο, D,

247
00:10:30,660 --> 00:10:32,290
αλλά αυτό είναι εντάξει.

248
00:10:32,290 --> 00:10:35,680
Τώρα μπορούμε να επισημάνω επόμενο δείκτη Γ στο νέο κόμβο.

249
00:10:37,450 --> 00:10:39,670
Έτσι, έχουμε κάνει αυτό χωρίς να χάσει όλα τα δεδομένα.

250
00:10:39,670 --> 00:10:42,280
Σε κώδικα, το C είναι ο τρέχων κόμβος

251
00:10:42,280 --> 00:10:45,540
ότι η διάσχιση δείκτης ανίχνευσης δείχνει να,

252
00:10:45,540 --> 00:10:50,400
και D εκπροσωπείται από τον κόμβο υποδεικνύεται από επόμενο πεδίο της τρέχουσας κόμβου,

253
00:10:50,400 --> 00:10:52,600
ή ερπυστριοφόρο → επόμενη.

254
00:10:52,600 --> 00:10:55,460
Έτσι, θέτουμε πρώτη επόμενη δείκτη του νέου κόμβου

255
00:10:55,460 --> 00:10:57,370
να επισημάνω με ερπυστριοφόρο → επόμενη,

256
00:10:57,370 --> 00:11:00,880
με τον ίδιο τρόπο που είπαμε επόμενο δείκτη new_node θα πρέπει να

257
00:11:00,880 --> 00:11:02,780
δείχνουν Δ στην εικόνα.

258
00:11:02,780 --> 00:11:04,540
Στη συνέχεια, μπορούμε να θέσουμε επόμενο δείκτη του τρέχοντος κόμβου

259
00:11:04,540 --> 00:11:06,330
στο νέο κόμβο μας,

260
00:11:06,330 --> 00:11:10,980
ακριβώς όπως έπρεπε να περιμένουμε να επισημάνω C έως new_node στο σχέδιο.

261
00:11:10,980 --> 00:11:12,250
Τώρα όλα είναι σε τάξη, και δεν χάσαμε

262
00:11:12,250 --> 00:11:14,490
παρακολούθηση όλων των δεδομένων, και ήμασταν σε θέση να μόλις

263
00:11:14,490 --> 00:11:16,200
κολλήσει νέος κόμβος μας στη μέση της λίστας

264
00:11:16,200 --> 00:11:19,330
χωρίς την ανοικοδόμηση της όλο αυτό το πράγμα ή ακόμα και οποιαδήποτε αλλαγή στοιχείων

265
00:11:19,330 --> 00:11:22,490
ο τρόπος με τον οποίο θα έπρεπε να με σύμβαση ορισμένου μήκους πίνακα.

266
00:11:22,490 --> 00:11:26,020
>> Έτσι, συνδεδεμένες λίστες είναι μια βασική, αλλά σημαντικό, δυναμική δομή δεδομένων

267
00:11:26,020 --> 00:11:29,080
που έχει τόσο πλεονεκτήματα όσο και μειονεκτήματα

268
00:11:29,080 --> 00:11:31,260
σε σύγκριση με πίνακες και άλλες δομές δεδομένων,

269
00:11:31,260 --> 00:11:33,350
και όπως συμβαίνει συχνά στην επιστήμη των υπολογιστών,

270
00:11:33,350 --> 00:11:35,640
Είναι σημαντικό να γνωρίζουμε πότε να χρησιμοποιήσει κάθε εργαλείο,

271
00:11:35,640 --> 00:11:37,960
ώστε να μπορείτε να επιλέξετε το σωστό εργαλείο για τη σωστή δουλειά.

272
00:11:37,960 --> 00:11:40,060
>> Για περισσότερες πρακτική, προσπαθήστε να γράψετε λειτουργίες

273
00:11:40,060 --> 00:11:42,080
διαγραφή κόμβων από μια συνδεδεμένη λίστα -

274
00:11:42,080 --> 00:11:44,050
θυμηθείτε να είναι προσεκτικοί σχετικά με τη σειρά με την οποία μπορείτε να αναδιατάξετε

275
00:11:44,050 --> 00:11:47,430
επόμενοι δείκτες σας για να εξασφαλίσετε ότι δεν χάνετε ένα μεγάλο κομμάτι της λίστας σας -

276
00:11:47,430 --> 00:11:50,200
ή μια λειτουργία για την καταμέτρηση των κόμβων σε μια συνδεδεμένη λίστα,

277
00:11:50,200 --> 00:11:53,280
ή ένα διασκεδαστικό, να αντιστρέψετε τη σειρά του όλους τους κόμβους σε μια συνδεδεμένη λίστα.

278
00:11:53,280 --> 00:11:56,090
>> Το όνομά μου είναι Steinkamp Jackson, αυτό είναι CS50.