1
00:00:00,000 --> 00:00:02,832
>> [Παίζει μουσική]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: Εντάξει, έτσι ώστε σε
αυτό το σημείο στην πορεία,

4
00:00:08,560 --> 00:00:15,300
έχουμε καλύψει πολλά από τα βασικά στοιχεία του C.
Γνωρίζουμε πολλά για τις μεταβλητές, πίνακες,

5
00:00:15,300 --> 00:00:17,610
δείκτες, όλα αυτά καλά πράγματα.

6
00:00:17,610 --> 00:00:21,610
Αυτά είναι όλα χτισμένα είδους
για να δείτε και τις βασικές αρχές,

7
00:00:21,610 --> 00:00:23,880
αλλά μπορούμε να κάνουμε περισσότερα, έτσι δεν είναι;

8
00:00:23,880 --> 00:00:27,930
Μπορούμε να συνδυάσουμε τα πράγματα
μαζί με ενδιαφέροντες τρόπους.

9
00:00:27,930 --> 00:00:31,010
>> Και έτσι ας το κάνουμε αυτό, ας ξεκινήσουμε
για την επέκτασή τους από ό, τι μας δίνει C,

10
00:00:31,010 --> 00:00:35,270
και να αρχίσει να δημιουργήσετε το δικό μας δεδομένα
δομές που χρησιμοποιούν τα κτίρια αυτά

11
00:00:35,270 --> 00:00:40,590
μπλοκ μαζί για να κάνουμε κάτι
πραγματικά πολύτιμη, χρήσιμες.

12
00:00:40,590 --> 00:00:43,420
Ένας τρόπος για να γίνει αυτό είναι
για να μιλήσουμε για συλλογές.

13
00:00:43,420 --> 00:00:48,360
Έτσι μέχρι τώρα είχαμε ένα είδος δεδομένων
δομή για την αναπαράσταση των συλλογών

14
00:00:48,360 --> 00:00:51,030
του αρέσει αξίες, παρόμοιες τιμές.

15
00:00:51,030 --> 00:00:52,350
Αυτό θα ήταν ένας πίνακας.

16
00:00:52,350 --> 00:00:57,020
Έχουμε συλλογές των ακεραίων, ή
συλλογές των χαρακτήρων και ούτω καθεξής.

17
00:00:57,020 --> 00:01:00,890
>> Δομές είναι επίσης ένα είδος δεδομένων
δομή για τη συλλογή πληροφοριών,

18
00:01:00,890 --> 00:01:03,220
αλλά δεν είναι για τη συλλογή, όπως τιμές.

19
00:01:03,220 --> 00:01:08,090
Συνδυάζει συνήθως διαφορετικούς τύπους δεδομένων
μαζί μέσα από ένα ενιαίο κουτί.

20
00:01:08,090 --> 00:01:10,750
Αλλά δεν είναι η ίδια
που χρησιμοποιούνται για την αλυσίδα μαζί

21
00:01:10,750 --> 00:01:16,920
ή συνδεθείτε μαζί παρόμοιες
αντικείμενα, όπως μια σειρά.

22
00:01:16,920 --> 00:01:20,960
Οι πίνακες είναι μεγάλη για
στοιχείο κοιτάζω προς τα πάνω, αλλά ανάκληση

23
00:01:20,960 --> 00:01:24,262
ότι είναι πολύ δύσκολο
για την εισαγωγή σε μια σειρά,

24
00:01:24,262 --> 00:01:26,470
εκτός και αν είμαστε εισαγωγή στο
το τέλος του εν λόγω πίνακα.

25
00:01:26,470 --> 00:01:29,730
>> Και το καλύτερο παράδειγμα που έχω
γι 'αυτό είναι το είδος εισαγωγής.

26
00:01:29,730 --> 00:01:31,650
Αν θυμάστε το βίντεο μας
σε ταξινόμηση με εισαγωγή,

27
00:01:31,650 --> 00:01:34,110
υπήρχε πολλή
τα έξοδα που απαιτούνται με

28
00:01:34,110 --> 00:01:37,970
για να πάρει στοιχεία, και μεταφορά τους
έξω από το δρόμο για να χωρέσει κάτι

29
00:01:37,970 --> 00:01:41,290
στη μέση του πίνακα σας.

30
00:01:41,290 --> 00:01:44,690
Πίνακες υποφέρουν επίσης από το άλλο
πρόβλημα, το οποίο είναι η ακαμψία.

31
00:01:44,690 --> 00:01:47,150
Όταν δηλώνουμε έναν πίνακα,
παίρνουμε έναν πυροβολισμό σε αυτό.

32
00:01:47,150 --> 00:01:49,790
Παίρνουμε να πω, θέλω
αυτό πολλά στοιχεία.

33
00:01:49,790 --> 00:01:51,940
Μπορεί να είναι 100, θα μπορούσε να
είναι 1.000, θα μπορούσε να

34
00:01:51,940 --> 00:01:55,930
είναι x όπου χ είναι ένας αριθμός ο χρήστης
μας έδωσε σε μια γραμμή ή στη γραμμή

35
00:01:55,930 --> 00:01:56,630
γραμμή.

36
00:01:56,630 --> 00:01:59,905
>> Αλλά έχουμε πάρει μόνο έναν πυροβολισμό σε αυτό, εμείς
Δεν έχετε να στη συνέχεια να πω OH, πραγματικά μου

37
00:01:59,905 --> 00:02:04,360
απαιτούνται 101, ή χρειαζόμουν x συν 20.

38
00:02:04,360 --> 00:02:07,910
Πάρα πολύ αργά, έχουμε ήδη δηλώσει το
σειρά, και αν θέλουμε να πάρουμε 101 ή x

39
00:02:07,910 --> 00:02:12,050
συν 20, θα πρέπει να δηλώσουν
μια εντελώς διαφορετική σειρά,

40
00:02:12,050 --> 00:02:15,540
αντιγράψτε όλα τα στοιχεία του πίνακα
πάνω, και στη συνέχεια έχουμε αρκετά.

41
00:02:15,540 --> 00:02:19,880
Και τι θα γίνει αν είμαστε πάλι λάθος, τι
αν πράγματι χρειαζόμαστε 102 ή x συν 40,

42
00:02:19,880 --> 00:02:21,970
πρέπει να το κάνουμε αυτό και πάλι.

43
00:02:21,970 --> 00:02:26,250
Έτσι είναι πολύ άκαμπτη
για την αλλαγή μεγέθους των δεδομένων μας,

44
00:02:26,250 --> 00:02:29,360
αλλά αν συνδυάσουμε μαζί μερικά
από τα βασικά στοιχεία που έχουμε ήδη

45
00:02:29,360 --> 00:02:33,230
έμαθαν για τους δείκτες και τις δομές,
ιδίως με τη χρήση δυναμικής μνήμης

46
00:02:33,230 --> 00:02:36,180
κατανομή με malloc, εμείς
μπορεί να βάλει αυτά τα κομμάτια μαζί

47
00:02:36,180 --> 00:02:40,960
Για να δημιουργήσετε μια νέα δεδομένα structure-- ένα
μεμονωμένα συνδεδεμένη λίστα θα μπορούσαμε να say--

48
00:02:40,960 --> 00:02:45,400
ότι μας επιτρέπει να αναπτυχθούν και να
συρρικνωθεί μια συλλογή των τιμών

49
00:02:45,400 --> 00:02:48,800
και δεν θα έχουμε καμία σπατάλη χώρου.

50
00:02:48,800 --> 00:02:53,320
>> Έτσι και πάλι, καλούμε αυτήν την ιδέα,
Η έννοια αυτή, μια συνδεδεμένη λίστα.

51
00:02:53,320 --> 00:02:56,320
Ειδικότερα, σε αυτό το βίντεο είμαστε
μιλάμε για μεμονωμένα συνδεδεμένη λίστα,

52
00:02:56,320 --> 00:02:59,185
και στη συνέχεια ένα άλλο βίντεο θα μιλήσουμε
για διπλά συνδεδεμένες λίστες, οι οποίες

53
00:02:59,185 --> 00:03:01,560
είναι απλά μια παραλλαγή σε ένα θέμα εδώ.

54
00:03:01,560 --> 00:03:05,200
Αλλά ένα μεμονωμένα συνδεδεμένη λίστα
αποτελείται από κόμβους,

55
00:03:05,200 --> 00:03:08,559
κόμβοι είναι απλώς μια αφηρημένη term--
είναι απλώς κάτι καλώ

56
00:03:08,559 --> 00:03:10,350
αυτό είναι ένα είδος
δομή, βασικά, είμαι;

57
00:03:10,350 --> 00:03:16,190
Απλά πρόκειται να την ονομάσω ένα node-- και αυτό
κόμβος έχει δύο μέλη, ή δύο πεδία.

58
00:03:16,190 --> 00:03:20,300
Έχει δεδομένων, συνήθως μια
ακέραιος, ο πλωτήρας χαρακτήρα,

59
00:03:20,300 --> 00:03:23,790
ή θα μπορούσε να είναι κάποιο άλλο τύπο δεδομένων
ότι έχετε ορίσει με έναν τύπο def.

60
00:03:23,790 --> 00:03:29,290
Και περιέχει ένα δείκτη σε
άλλος κόμβος του ίδιου τύπου.

61
00:03:29,290 --> 00:03:34,710
>> Έτσι έχουμε δύο πράγματα στο εσωτερικό του
Αυτός ο κόμβος, δεδομένων και ένα δείκτη

62
00:03:34,710 --> 00:03:36,380
σε άλλο κόμβο.

63
00:03:36,380 --> 00:03:39,370
Και αν αρχίσουν να απεικονίσει
αυτό, μπορείτε να το σκεφτείτε

64
00:03:39,370 --> 00:03:42,280
σαν μια αλυσίδα των κόμβων που
συνδέονται μεταξύ τους.

65
00:03:42,280 --> 00:03:45,070
Έχουμε την πρώτη κόμβος,
περιέχει δεδομένα, και ένα δείκτη

66
00:03:45,070 --> 00:03:49,110
στον δεύτερο κόμβο, το οποίο περιέχει
δεδομένων, και ένα δείκτη στον τρίτο κόμβο.

67
00:03:49,110 --> 00:03:52,940
Και έτσι αυτό είναι ο λόγος που το αποκαλούμε ένα
συνδεδεμένη λίστα, από όπου και αν συνδέονται μεταξύ τους.

68
00:03:52,940 --> 00:03:56,070
>> Τι κάνει αυτή την ειδική
δομή κόμβου μοιάζει;

69
00:03:56,070 --> 00:04:01,120
Λοιπόν, αν θυμάστε από το βίντεο μας
Ορισμός των ειδικών τύπων, με τον τύπο def,

70
00:04:01,120 --> 00:04:05,400
μπορούμε να ορίσουμε μια structure-- και
πληκτρολογήστε καθορίσει μια δομή σαν αυτή.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, και τότε είμαι
χρησιμοποιώντας την τιμή λέξη εδώ αυθαίρετα

72
00:04:11,240 --> 00:04:13,891
να αναφέρουν οποιοδήποτε τύπο δεδομένων πραγματικά.

73
00:04:13,891 --> 00:04:16,890
Θα μπορούσατε να δώσετε έναν ακέραιο ή πλωτήρα,
θα μπορούσατε να έχετε ό, τι θέλετε.

74
00:04:16,890 --> 00:04:19,389
Δεν είναι μόνο να περιορίζεται
ακέραιοι, ή κάτι τέτοιο.

75
00:04:19,389 --> 00:04:22,790
Έτσι, η τιμή είναι απλά μια αυθαίρετη
τύπο δεδομένων, και στη συνέχεια ένα δείκτη

76
00:04:22,790 --> 00:04:26,310
σε άλλο κόμβο του ίδιου τύπου.

77
00:04:26,310 --> 00:04:29,690
>> Τώρα, υπάρχει μια μικρή αλιευμάτων
εδώ με τον καθορισμό μιας δομής

78
00:04:29,690 --> 00:04:33,030
όταν πρόκειται για μια δομή εαυτού αναφορική.

79
00:04:33,030 --> 00:04:35,340
Θα πρέπει να έχουν προσωρινό
όνομα για τη δομή μου.

80
00:04:35,340 --> 00:04:37,640
Στο τέλος της ημέρας Ι
σαφώς θέλετε να το ονομάσετε

81
00:04:37,640 --> 00:04:43,030
SLL κόμβο, αυτό είναι τελικά το νέο
Ονομα μέρος του ορισμού του τύπου μου,

82
00:04:43,030 --> 00:04:47,450
αλλά δεν μπορώ να χρησιμοποιήσω SLL κόμβο
στη μέση αυτού.

83
00:04:47,450 --> 00:04:51,430
Ο λόγος είναι, δεν έχω
δημιούργησε έναν τύπο που ονομάζεται SLL κόμβου

84
00:04:51,430 --> 00:04:55,200
μέχρι να χτυπήσει αυτό το τελικό σημείο εδώ.

85
00:04:55,200 --> 00:04:59,720
Μέχρι εκείνο το σημείο, πρέπει να έχω
ένας άλλος τρόπος για να αναφερθεί σε αυτό το είδος των δεδομένων.

86
00:04:59,720 --> 00:05:02,440
>> Και αυτό είναι μια αυτο
αναφορών τύπο δεδομένων.

87
00:05:02,440 --> 00:05:06,314
Είναι? S έναν τύπο δεδομένων ενός
δομή που περιέχει ένα δεδομένων,

88
00:05:06,314 --> 00:05:08,480
και ένα δείκτη σε ένα άλλο
δομή του ίδιου τύπου.

89
00:05:08,480 --> 00:05:11,750
Γι 'αυτό και πρέπει να είναι σε θέση να αναφερθεί σε
Αυτός ο τύπος δεδομένων τουλάχιστον προσωρινά,

90
00:05:11,750 --> 00:05:14,910
δίνοντας έτσι την προσωρινή
Το όνομά του struct sllist

91
00:05:14,910 --> 00:05:18,540
μου επιτρέπει να πω στη συνέχεια, θέλω ένα
δείκτη σε άλλο struct sllist,

92
00:05:18,540 --> 00:05:24,690
ένα αστέρι struct sllist, και στη συνέχεια,
αφού έχω ολοκληρώσει τον ορισμό,

93
00:05:24,690 --> 00:05:27,220
Μπορώ τώρα να καλέσετε αυτό το είδος ένα κόμβο SLL.

94
00:05:27,220 --> 00:05:30,520
>> Έτσι, γι 'αυτό θα δείτε εκεί
ένα προσωρινό όνομα εδώ,

95
00:05:30,520 --> 00:05:31,879
αλλά μια μόνιμη όνομα εδώ.

96
00:05:31,879 --> 00:05:33,920
Μερικές φορές μπορεί να δείτε
ορισμοί της δομής,

97
00:05:33,920 --> 00:05:36,570
για παράδειγμα, ότι δεν είναι
αυτο αναφορών, ότι

98
00:05:36,570 --> 00:05:39,390
Δεν έχει ένα όνομα προσδιοριστικό εδώ.

99
00:05:39,390 --> 00:05:43,040
Θα ήθελα απλώς να πω typedef struct,
ανοίξτε σγουρά στήριγμα και στη συνέχεια να την ορίσουμε.

100
00:05:43,040 --> 00:05:45,620
Αλλά αν είστε struct είναι αυτο
αναφορών, καθώς αυτό είναι,

101
00:05:45,620 --> 00:05:49,010
θα πρέπει να καθορίσετε ένα
προσωρινό όνομα τύπου.

102
00:05:49,010 --> 00:05:51,310
Αλλά τελικά, τώρα
ότι έχουμε κάνει αυτό,

103
00:05:51,310 --> 00:05:53,620
απλά μπορεί να αναφέρεται σε
Αυτοί οι κόμβοι, οι μονάδες αυτές,

104
00:05:53,620 --> 00:05:57,900
όπως SLL κόμβων για σκοπούς
από το υπόλοιπο αυτού του βίντεο.

105
00:05:57,900 --> 00:06:00,900
>> Εντάξει, έτσι ώστε να γνωρίζουν πώς να
δημιουργήσετε μια συνδεδεμένη λίστα κόμβων.

106
00:06:00,900 --> 00:06:03,240
Ξέρουμε πώς να καθορίσει
μια συνδεδεμένη λίστα κόμβων.

107
00:06:03,240 --> 00:06:06,670
Τώρα, αν θα πάμε για να ξεκινήσετε
τη χρήση τους για τη συλλογή πληροφοριών,

108
00:06:06,670 --> 00:06:10,360
υπάρχει ένα ζεύγος πράξεων που
πρέπει να κατανοήσουν και να εργαστεί με.

109
00:06:10,360 --> 00:06:12,860
Πρέπει να ξέρετε πώς να δημιουργήσετε
μια συνδεδεμένη λίστα από αέρα κοπανιστό.

110
00:06:12,860 --> 00:06:14,901
Εάν δεν υπάρχει κατάλογος ήδη,
θέλουμε να αρχίσουμε μία.

111
00:06:14,901 --> 00:06:16,960
Γι 'αυτό και πρέπει να είναι σε θέση
για να δημιουργήσετε μια συνδεδεμένη λίστα,

112
00:06:16,960 --> 00:06:19,130
θα πρέπει να αναζητήσετε πιθανώς
στη λίστα σύνδεσμο

113
00:06:19,130 --> 00:06:21,830
για να βρείτε ένα στοιχείο που ψάχνουμε.

114
00:06:21,830 --> 00:06:24,430
Πρέπει να είμαστε σε θέση να εισαγάγετε
νέα πράγματα στη λίστα,

115
00:06:24,430 --> 00:06:25,930
θέλουμε λίστα μας να είναι σε θέση να αναπτυχθούν.

116
00:06:25,930 --> 00:06:28,638
Και ομοίως, θέλουμε να είναι σε θέση
για να διαγράψετε τα πράγματα από τη λίστα μας,

117
00:06:28,638 --> 00:06:30,250
θέλουμε λίστα μας να είναι σε θέση να συρρικνωθεί.

118
00:06:30,250 --> 00:06:32,160
Και στο τέλος μας
προγραμμάτων, ιδίως

119
00:06:32,160 --> 00:06:34,550
αν θυμηθούμε ότι είμαστε
δυναμική εκχώρηση μνήμης

120
00:06:34,550 --> 00:06:38,337
για την κατασκευή αυτών των καταλόγων κατά κανόνα,
θέλουμε να ελευθερώσουμε το σύνολο των εν λόγω μνήμη

121
00:06:38,337 --> 00:06:39,670
όταν τελειώσετε την εργασία με αυτό.

122
00:06:39,670 --> 00:06:44,627
Και έτσι πρέπει να είμαστε σε θέση να διαγράψετε ένα
ολόκληρη η συνδεδεμένη λίστα σε ένα αποτύχει προσγειωνόμαστε.

123
00:06:44,627 --> 00:06:46,460
Ας πάμε μέσα
ορισμένες από αυτές τις

124
00:06:46,460 --> 00:06:51,192
και πώς θα μπορούσαμε να τα απεικονίσει,
μιλώντας σε κώδικα ειδικά ψευδοκώδικα.

125
00:06:51,192 --> 00:06:53,150
Έτσι θέλουμε να δημιουργήσουμε μια
συνδεδεμένη λίστα, οπότε ίσως θα

126
00:06:53,150 --> 00:06:56,480
θέλουμε να ορίσουμε μια συνάρτηση
με αυτό το πρωτότυπο.

127
00:06:56,480 --> 00:07:01,690
SLL κόμβο αστέρων, δημιουργούν, και περνώ
σε ένα επιχείρημα, κάποια αυθαίρετη δεδομένα

128
00:07:01,690 --> 00:07:05,530
πληκτρολογήστε ξανά, από κάποια αυθαίρετη τύπο δεδομένων.

129
00:07:05,530 --> 00:07:10,482
Αλλά είμαι returning-- αυτή τη λειτουργία θα πρέπει να
να επιστρέψει σε μένα ένα δείκτη, σε μεμονωμένα

130
00:07:10,482 --> 00:07:11,190
συνδεδεμένη λίστα κόμβων.

131
00:07:11,190 --> 00:07:14,050
Και πάλι, προσπαθούμε να δημιουργήσουμε
μια συνδεδεμένη λίστα από το πουθενά,

132
00:07:14,050 --> 00:07:17,900
γι 'αυτό χρειάζεται ένα δείκτη
ο κατάλογος αυτός όταν είμαι γίνει.

133
00:07:17,900 --> 00:07:19,420
>> Έτσι, ποια είναι τα βήματα που εμπλέκονται εδώ;

134
00:07:19,420 --> 00:07:20,960
Λοιπόν, το πρώτο πράγμα που είμαι
πρόκειται να κάνουμε είναι δυναμικά

135
00:07:20,960 --> 00:07:22,550
διατεθεί χώρος για ένα νέο κόμβο.

136
00:07:22,550 --> 00:07:26,689
Και πάλι, είμαστε αυτό δημιουργεί εκ του μηδενός
αέρα, γι 'αυτό πρέπει να malloc χώρο για αυτό.

137
00:07:26,689 --> 00:07:28,480
Και φυσικά, άμεσα
αφού malloc,

138
00:07:28,480 --> 00:07:31,692
πάντα βεβαιωθείτε ότι μας
pointer-- δεν πήραμε πίσω null.

139
00:07:31,692 --> 00:07:33,650
Διότι αν προσπαθήσουμε και
υποχώρηση ένα κενό δείκτη,

140
00:07:33,650 --> 00:07:36,190
θα πάμε να υποστούν μια
segfault και εμείς δεν το θέλουμε αυτό.

141
00:07:36,190 --> 00:07:39,510
>> Στη συνέχεια, θέλουμε να συμπληρώσει το πεδίο,
θέλουμε να προετοιμάσει το πεδίο τιμής

142
00:07:39,510 --> 00:07:41,690
και να προετοιμάσει το επόμενο πεδίο.

143
00:07:41,690 --> 00:07:45,450
Και μετά θέλουμε to-- τελικά η
πρωτότυπο λειτουργία indicates-- θέλουμε

144
00:07:45,450 --> 00:07:49,940
να επιστρέψει ένα δείκτη σε ένα κόμβο SLL.

145
00:07:49,940 --> 00:07:51,710
Έτσι, αυτό που κάνει αυτό μοιάζουν οπτικά;

146
00:07:51,710 --> 00:07:55,230
Λοιπόν, πρώτα θα πάμε να δυναμικά
διατεθεί χώρος για ένα νέο κόμβο SLL,

147
00:07:55,230 --> 00:07:58,320
γι 'αυτό είναι ότι malloc--
μια οπτική αναπαράσταση

148
00:07:58,320 --> 00:08:00,020
του κόμβου που μόλις δημιουργήσαμε.

149
00:08:00,020 --> 00:08:02,757
Και βεβαιωθείτε
δεν είναι null-- σε αυτή την περίπτωση,

150
00:08:02,757 --> 00:08:04,840
η εικόνα δεν θα έχει
δείξει μέχρι αν ήταν άκυρη,

151
00:08:04,840 --> 00:08:07,298
θα είχαμε ξεμείνει από μνήμη,
έτσι είμαστε καλοί να πάτε εκεί.

152
00:08:07,298 --> 00:08:10,200
Έτσι, τώρα είμαστε στο βήμα C,
προετοιμάσει το πεδίο κόμβους αξία.

153
00:08:10,200 --> 00:08:12,280
Λοιπόν, με βάση αυτή τη λειτουργία
καλέστε είμαι με τη χρήση εδώ,

154
00:08:12,280 --> 00:08:16,700
Μοιάζει θέλω να μεταφέρω σε 6,
Γι 'αυτό θα 6 στο πεδίο της τιμής.

155
00:08:16,700 --> 00:08:18,865
Τώρα, να προετοιμάσει το επόμενο πεδίο.

156
00:08:18,865 --> 00:08:21,640
Λοιπόν, τι θα πάω να κάνω εκεί,
δεν υπάρχει τίποτα δίπλα, δεξιά,

157
00:08:21,640 --> 00:08:23,600
αυτό είναι το μόνο πράγμα στη λίστα.

158
00:08:23,600 --> 00:08:27,206
Ποιο είναι λοιπόν το επόμενο πράγμα στη λίστα;

159
00:08:27,206 --> 00:08:29,660
>> Δεν θα πρέπει να επισημάνω κάτι, σωστά.

160
00:08:29,660 --> 00:08:33,600
Δεν υπάρχει τίποτα άλλο εκεί, οπότε ό, τι είναι
η έννοια που γνωρίζουμε ότι είναι nothing--

161
00:08:33,600 --> 00:08:35,638
δείκτες σε τίποτα;

162
00:08:35,638 --> 00:08:37,929
Θα πρέπει να είναι ίσως θέλουμε
για να τεθεί ένα κενό δείκτη εκεί,

163
00:08:37,929 --> 00:08:40,178
και θα αντιπροσωπεύουν το null
pointer όπως ακριβώς ένα κόκκινο κουτί,

164
00:08:40,178 --> 00:08:41,559
δεν μπορούμε να προχωρήσουμε περαιτέρω.

165
00:08:41,559 --> 00:08:44,430
Όπως θα δούμε λίγο αργότερα,
θα έχουμε τελικά αλυσίδες

166
00:08:44,430 --> 00:08:46,330
βέλη που συνδέουν
Αυτοί οι κόμβοι μαζί,

167
00:08:46,330 --> 00:08:48,480
αλλά όταν χτύπησε το
κόκκινο κουτί, αυτό είναι μηδενική,

168
00:08:48,480 --> 00:08:51,150
δεν μπορούμε να προχωρήσουμε περαιτέρω,
αυτό είναι το τέλος της λίστας.

169
00:08:51,150 --> 00:08:53,960
>> Και τέλος, θέλουμε απλώς να
επιστρέφει ένα δείκτη σε αυτόν τον κόμβο.

170
00:08:53,960 --> 00:08:56,160
Γι 'αυτό και θα το ονομάζουμε νέα,
και θα επιστρέψει νέα

171
00:08:56,160 --> 00:08:59,370
έτσι ώστε να μπορεί να χρησιμοποιηθεί σε
Όποια και αν είναι η λειτουργία το δημιούργησε.

172
00:08:59,370 --> 00:09:03,100
Έτσι εκεί πάμε, Έχουμε δημιουργήσει ένα μεμονωμένα
συνδεδεμένη λίστα κόμβων από το πουθενά,

173
00:09:03,100 --> 00:09:05,920
και τώρα έχουμε μια λίστα μπορούμε να εργαστούμε με.

174
00:09:05,920 --> 00:09:08,260
>> Τώρα, ας πούμε ήδη
έχουν μια μεγάλη αλυσίδα,

175
00:09:08,260 --> 00:09:09,800
και θέλουμε να βρούμε κάτι σε αυτό.

176
00:09:09,800 --> 00:09:12,716
Και θέλουμε μια λειτουργία που πρόκειται
να επιστρέψει αληθής ή ψευδής, ανάλογα

177
00:09:12,716 --> 00:09:15,840
σχετικά με το εάν υπάρχει η τιμή στον εν λόγω κατάλογο.

178
00:09:15,840 --> 00:09:18,160
Ένα πρωτότυπο λειτουργία, ή
δήλωση για την εν λόγω λειτουργία,

179
00:09:18,160 --> 00:09:23,320
Μπορεί να μοιάζει με this-- bool βρείτε, και
τότε θα θέλετε να περάσετε σε δύο επιχειρήματα.

180
00:09:23,320 --> 00:09:26,996
>> Το πρώτο, είναι ένας δείκτης για την
πρώτου στοιχείου της συνδεδεμένης λίστας.

181
00:09:26,996 --> 00:09:29,620
Αυτό είναι πραγματικά κάτι που θα
θέλουν πάντα να παρακολουθείτε,

182
00:09:29,620 --> 00:09:33,110
και στην πραγματικότητα θα μπορούσε να είναι κάτι που
Μπορείτε ακόμη και να θέσει σε μια καθολική μεταβλητή.

183
00:09:33,110 --> 00:09:35,360
Αφού δημιουργήσετε μια λίστα,
μπορείτε πάντα, πάντα

184
00:09:35,360 --> 00:09:38,990
θέλετε να παρακολουθείτε την πολύ
πρώτο στοιχείο της λίστας.

185
00:09:38,990 --> 00:09:43,690
Με αυτόν τον τρόπο μπορείτε να ανατρέξετε σε όλα τα άλλα
στοιχεία από μόνο μετά την αλυσίδα,

186
00:09:43,690 --> 00:09:47,300
χωρίς να χρειάζεται να κρατήσει δείκτες
άθικτα σε κάθε μεμονωμένο στοιχείο.

187
00:09:47,300 --> 00:09:50,920
Το μόνο που χρειάζεται να παρακολουθείτε την πρώτη
ένα, αν είναι όλα δεμένους.

188
00:09:50,920 --> 00:09:52,460
>> Και στη συνέχεια το δεύτερο πράγμα που
είμαστε περνώντας και πάλι

189
00:09:52,460 --> 00:09:54,376
είναι αυθαίρετα some--
ανεξάρτητα από τον τύπο των δεδομένων είμαστε

190
00:09:54,376 --> 00:09:59,640
ψάχνετε εκεί είναι μέσα
ελπίζουμε ότι ένας από τους κόμβους της λίστας.

191
00:09:59,640 --> 00:10:00,980
Έτσι, ποια είναι τα βήματα;

192
00:10:00,980 --> 00:10:04,250
Λοιπόν, το πρώτο πράγμα που κάνουμε είναι
δημιουργούμε ένα εγκάρσιο δείκτη

193
00:10:04,250 --> 00:10:06,015
που δείχνουν προς το κεφάλι τους καταλόγους.

194
00:10:06,015 --> 00:10:08,890
Λοιπόν, γιατί να το κάνουμε αυτό, έχουμε ήδη
έχουν ένα δείκτη στο κεφάλι τους καταλόγους,

195
00:10:08,890 --> 00:10:10,974
γιατί δεν μπορούμε απλά να μεταφερθεί η μία γύρω;

196
00:10:10,974 --> 00:10:13,140
Λοιπόν, όπως είπα,
Είναι πραγματικά σημαντικό για εμάς

197
00:10:13,140 --> 00:10:17,580
να κρατούν πάντα κομμάτι της
πρώτο στοιχείο στη λίστα.

198
00:10:17,580 --> 00:10:21,270
Και γι 'αυτό είναι πραγματικά καλύτερα
για να δημιουργήσετε ένα αντίγραφο από αυτό,

199
00:10:21,270 --> 00:10:25,350
και να τις χρησιμοποιούν για να μετακινούνται έτσι δεν μπορούμε ποτέ
μετακινήσετε κατά λάθος μακριά, ή εμείς πάντα

200
00:10:25,350 --> 00:10:30,430
έχουν ένα δείκτη σε κάποιο σημείο που είναι
δεξιά στο πρώτο στοιχείο της λίστας.

201
00:10:30,430 --> 00:10:33,290
Έτσι είναι καλύτερα να δημιουργηθεί μια
δεύτερο που χρησιμοποιούμε για να προχωρήσουμε.

202
00:10:33,290 --> 00:10:35,877
>> Στη συνέχεια συγκρίνει μόνο αν
το πεδίο αξία αυτού του κόμβου

203
00:10:35,877 --> 00:10:38,960
είναι αυτό που ψάχνετε, και αν είναι
όχι, απλά να προχωρήσουμε στο επόμενο κόμβο.

204
00:10:38,960 --> 00:10:41,040
Και συνεχίζουμε να το κάνουμε αυτό
πάνω, και πάνω, και πάνω,

205
00:10:41,040 --> 00:10:44,811
μέχρι να βρείτε είτε
το στοιχείο, ή χτυπάμε

206
00:10:44,811 --> 00:10:47,310
null-- έχουμε φτάσει στο τέλος
του καταλόγου και δεν είναι εκεί.

207
00:10:47,310 --> 00:10:50,540
Αυτό πρέπει να χτυπήσει ένα κουδούνι αισίως
για να σας, όπως ακριβώς γραμμική αναζήτηση,

208
00:10:50,540 --> 00:10:54,430
είμαστε απλά αναπαράγει σε
ένα μεμονωμένα συνδεδεμένη δομή καταλόγου

209
00:10:54,430 --> 00:10:56,280
αντί να χρησιμοποιεί μια σειρά για να το κάνουμε.

210
00:10:56,280 --> 00:10:58,210
>> Έτσι, εδώ είναι ένα παράδειγμα της
ένα μεμονωμένα συνδεδεμένη λίστα.

211
00:10:58,210 --> 00:11:00,043
Αυτός αποτελείται από
πέντε κόμβους, και έχουμε

212
00:11:00,043 --> 00:11:04,330
ένας δείκτης στο κεφάλι της
κατάλογο, το οποίο ονομάζεται λίστα.

213
00:11:04,330 --> 00:11:07,385
Το πρώτο πράγμα που θέλουμε να κάνουμε είναι να
και πάλι, να δημιουργήσει αυτό το δείκτη διάσχισης.

214
00:11:07,385 --> 00:11:09,760
Έτσι, έχουμε τώρα δύο δείκτες
ότι το σημείο για το ίδιο πράγμα.

215
00:11:09,760 --> 00:11:15,025
>> Τώρα, εδώ παρατηρήσετε επίσης, δεν το έκανα
Πρέπει να malloc κανένα χώρο για Trav.

216
00:11:15,025 --> 00:11:18,970
Δεν είπα Trav ισούται με malloc
κάτι, αυτός ο κόμβος υπάρχει ήδη,

217
00:11:18,970 --> 00:11:21,160
ότι ο χώρος στη μνήμη υπάρχει ήδη.

218
00:11:21,160 --> 00:11:24,290
Έτσι, όλα είμαι πραγματικά κάνει είναι
δημιουργώντας έναν άλλο δείκτη σε αυτό.

219
00:11:24,290 --> 00:11:28,210
Δεν είμαι mallocing πρόσθετη
χώρο, έχουν μόλις τώρα δίποντα

220
00:11:28,210 --> 00:11:31,370
που δείχνουν προς το ίδιο πράγμα.

221
00:11:31,370 --> 00:11:33,710
>> Έτσι είναι 2 αυτό που ψάχνω;

222
00:11:33,710 --> 00:11:37,220
Λοιπόν, όχι, έτσι ώστε αντί να είμαι
πρόκειται να κινηθεί στο επόμενο.

223
00:11:37,220 --> 00:11:41,740
Έτσι, βασικά θα έλεγα,
Trav Trav ισούται με το επόμενο.

224
00:11:41,740 --> 00:11:43,630
Είναι 3 τι ψάχνω, όχι.

225
00:11:43,630 --> 00:11:45,780
Γι 'αυτό και συνεχίζουν να πάει
μέσω, μέχρι που τελικά

226
00:11:45,780 --> 00:11:48,690
φτάσετε στο 6 το οποίο είναι αυτό που ψάχνω
για βασίζονται στην κλήση της συνάρτησης

227
00:11:48,690 --> 00:11:51,600
Έχω στην κορυφή
εκεί, και έτσι είμαι γίνει.

228
00:11:51,600 --> 00:11:54,150
>> Τώρα, τι εάν το στοιχείο είμαι
αναζητάτε δεν είναι στη λίστα,

229
00:11:54,150 --> 00:11:55,510
Είναι ακόμα πρόκειται να λειτουργήσει;

230
00:11:55,510 --> 00:11:57,120
Λοιπόν, παρατηρήστε ότι ο κατάλογος
εδώ είναι ελαφρά διαφορετική,

231
00:11:57,120 --> 00:11:59,410
και αυτό είναι ένα άλλο πράγμα που είναι
σημαντικό με συνδεδεμένες λίστες,

232
00:11:59,410 --> 00:12:01,780
δεν χρειάζεται να διατηρηθεί
τους σε κάποια συγκεκριμένη σειρά.

233
00:12:01,780 --> 00:12:05,390
Μπορείτε, αν θέλετε, αλλά
μπορεί να έχετε ήδη παρατηρήσει

234
00:12:05,390 --> 00:12:09,310
ότι δεν είμαστε παρακολούθηση των
ποιος είναι ο αριθμός των στοιχείων βρισκόμαστε.

235
00:12:09,310 --> 00:12:13,150
>> Και αυτό είναι το είδος του ένα εμπόριο που θα
έχουν με συνδεδεμένη λίστα στίχους συστοιχίες,

236
00:12:13,150 --> 00:12:15,300
είναι ότι δεν έχουμε
τυχαίας προσπέλασης πια.

237
00:12:15,300 --> 00:12:18,150
Δεν μπορούμε απλά να πω, θέλω
να πάει στο 0th στοιχείο,

238
00:12:18,150 --> 00:12:21,410
ή η 6η στοιχείο του πίνακα μου,
το οποίο μπορώ να κάνω σε μια σειρά.

239
00:12:21,410 --> 00:12:25,080
Δεν μπορώ να πω ότι θέλω να πάω να το
0th στοιχείο, ή το 6ο στοιχείο,

240
00:12:25,080 --> 00:12:30,360
ή το 25ο στοιχείο της συνδεδεμένης λίστας μου,
δεν υπάρχει δείκτης που συνδέονται με αυτά.

241
00:12:30,360 --> 00:12:33,660
Και γι 'αυτό δεν έχει τόση σημασία
αν διατηρούμε κατάλογο μας σε τάξη.

242
00:12:33,660 --> 00:12:36,080
Αν θέλετε να σας
σίγουρα μπορεί, αλλά δεν υπάρχει

243
00:12:36,080 --> 00:12:38,567
κανένας λόγος για τον οποίο πρέπει να
να συντηρηθεί με οποιαδήποτε σειρά.

244
00:12:38,567 --> 00:12:40,400
Έτσι και πάλι, ας προσπαθήσουμε και
βρείτε 6 σε αυτή τη λίστα.

245
00:12:40,400 --> 00:12:43,200
Λοιπόν, ξεκινάμε με το
αρχίζουν, δεν βρίσκουμε 6,

246
00:12:43,200 --> 00:12:47,690
και στη συνέχεια θα συνεχίσουν να μην εύρεση
6, μέχρι να φτάσουμε τελικά εδώ.

247
00:12:47,690 --> 00:12:52,790
Έτσι τώρα Trav σημεία στον κόμβο
που περιέχουν 8, έξι δεν είναι εκεί.

248
00:12:52,790 --> 00:12:55,250
>> Έτσι, το επόμενο βήμα θα είναι
για να μεταβείτε στον επόμενο δείκτη,

249
00:12:55,250 --> 00:12:57,440
έτσι λένε Trav Trav ισούται με το επόμενο.

250
00:12:57,440 --> 00:13:00,750
Λοιπόν, Trav επόμενο, που υποδεικνύεται από
το κόκκινο κουτί εκεί, είναι μηδενική.

251
00:13:00,750 --> 00:13:03,020
Έτσι, δεν υπάρχει πουθενά αλλού να
πάει, και έτσι σε αυτό το σημείο

252
00:13:03,020 --> 00:13:06,120
μπορούμε να συμπεράνουμε ότι πετύχαμε
το τέλος του συνδεδεμένη λίστα,

253
00:13:06,120 --> 00:13:07,190
και 6 δεν είναι εκεί.

254
00:13:07,190 --> 00:13:10,980
Και θα πρέπει να επιστραφεί
ψευδείς σε αυτή την περίπτωση.

255
00:13:10,980 --> 00:13:14,540
>> Εντάξει, πώς θα τοποθετήσετε μια νέα
κόμβου στη συνδεδεμένη λίστα;

256
00:13:14,540 --> 00:13:17,310
Έτσι είμαστε σε θέση να δημιουργήσουμε
μια συνδεδεμένη λίστα από το πουθενά,

257
00:13:17,310 --> 00:13:19,370
αλλά πιθανόν να θέλετε να
οικοδομήσουμε μια αλυσίδα και δεν

258
00:13:19,370 --> 00:13:22,620
δημιουργήσετε ένα μάτσο ξεχωριστοί κατάλογοι.

259
00:13:22,620 --> 00:13:25,700
Θέλουμε να έχουμε μια λίστα που
έχει μια δέσμη των κόμβων σε αυτό,

260
00:13:25,700 --> 00:13:28,040
όχι μια χούφτα των καταλόγων με ένα μόνο κόμβο.

261
00:13:28,040 --> 00:13:31,260
Γι 'αυτό και δεν μπορεί να κρατήσει μόνο χρησιμοποιώντας Δημιουργία
συνάρτηση που ορίζεται νωρίτερα, τώρα είμαστε

262
00:13:31,260 --> 00:13:33,860
θέλετε να εισάγετε σε μια
κατάλογο που ήδη υπάρχει.

263
00:13:33,860 --> 00:13:36,499
>> Έτσι αυτή την περίπτωση, θα πάμε
για να περάσει σε δύο επιχειρήματα,

264
00:13:36,499 --> 00:13:39,290
ο δείκτης στο κεφάλι του ότι
συνδεδεμένη λίστα που θέλετε να προσθέσετε στο.

265
00:13:39,290 --> 00:13:40,910
Και πάλι, γι 'αυτό είναι τόσο
σημαντικό να έχουμε πάντα

266
00:13:40,910 --> 00:13:43,400
Παρακολουθήστε αυτό, επειδή
Είναι ο μόνος τρόπος που μπορούμε πραγματικά

267
00:13:43,400 --> 00:13:46,690
πρέπει να αναφέρονται στο σύνολο καταλόγου είναι
μόνο με ένα δείκτη προς το πρώτο στοιχείο.

268
00:13:46,690 --> 00:13:49,360
Θέλουμε, λοιπόν, να περάσει σε ένα
δείκτη σε αυτή πρώτο στοιχείο,

269
00:13:49,360 --> 00:13:52,226
και ανεξάρτητα από την αξία μας
θέλετε να προσθέσετε στη λίστα.

270
00:13:52,226 --> 00:13:54,600
Και τελικά αυτή η λειτουργία
πρόκειται να επιστρέψει ένα δείκτη

271
00:13:54,600 --> 00:13:57,980
με το νέο επικεφαλής μιας συνδεδεμένης λίστας.

272
00:13:57,980 --> 00:13:59,700
>> Ποια είναι τα βήματα που εμπλέκονται εδώ;

273
00:13:59,700 --> 00:14:02,249
Λοιπόν, ακριβώς όπως με τη δημιουργία,
θα πρέπει να κατανέμει δυναμικά

274
00:14:02,249 --> 00:14:05,540
χώρος για ένα νέο κόμβο, και ελέγξτε για να βεβαιωθείτε
βέβαιος ότι δεν τρέχουν έξω από τη μνήμη, και πάλι,

275
00:14:05,540 --> 00:14:07,150
επειδή είμαστε χρησιμοποιώντας malloc.

276
00:14:07,150 --> 00:14:09,080
Στη συνέχεια, θέλουμε να συμπληρώσετε
και τοποθετήστε τον κόμβο,

277
00:14:09,080 --> 00:14:12,730
έτσι που ο αριθμός, ανεξαρτήτως
val είναι μέσα στον κόμβο.

278
00:14:12,730 --> 00:14:17,310
Θέλουμε να εισάγετε τον κόμβο στο
η αρχή της συνδεδεμένης λίστας.

279
00:14:17,310 --> 00:14:19,619
>> Υπάρχει ένας λόγος για τον οποίο εγώ
θέλετε να το κάνετε αυτό, και

280
00:14:19,619 --> 00:14:21,910
θα μπορούσε να αξίζει να ρίξουμε μια δεύτερη
για να διακόψετε το βίντεο εδώ,

281
00:14:21,910 --> 00:14:25,860
και σκεφτείτε γιατί θα ήθελα να
ένθετο κατά την έναρξη ενός συνδεδεμένου

282
00:14:25,860 --> 00:14:26,589
κατάλογο.

283
00:14:26,589 --> 00:14:28,630
Και πάλι, ανέφερα νωρίτερα
ότι πραγματικά δεν το κάνει

284
00:14:28,630 --> 00:14:33,020
σημασία αν το διατηρήσουμε σε οποιαδήποτε
Προκειμένου, οπότε ίσως αυτό είναι μια ένδειξη.

285
00:14:33,020 --> 00:14:36,040
Και είδες τι θα συνέβαινε αν
ήθελε to-- ή από μόλις ένα δευτερόλεπτο

286
00:14:36,040 --> 00:14:37,360
πριν, όταν πηγαίναμε
μέσω της αναζήτησης σας

287
00:14:37,360 --> 00:14:39,235
μπορούσα να δω τι θα μπορούσε να
συνέβαινε αν προσπαθούσαμε

288
00:14:39,235 --> 00:14:41,330
να προστεθεί στο τέλος της λίστας.

289
00:14:41,330 --> 00:14:44,750
Επειδή δεν έχουμε ένα
δείκτη στο τέλος της λίστας.

290
00:14:44,750 --> 00:14:47,490
>> Έτσι, ο λόγος για τον οποίο θα ήθελα
για να εισαγάγετε στην αρχή,

291
00:14:47,490 --> 00:14:49,380
είναι γιατί μπορώ να το κάνω αμέσως.

292
00:14:49,380 --> 00:14:52,730
Έχω ένα δείκτη στην αρχή, και
θα δούμε αυτό σε μια οπτική σε ένα δευτερόλεπτο.

293
00:14:52,730 --> 00:14:55,605
Αλλά αν θέλετε να εισάγετε στο τέλος,
Πρέπει να ξεκινήσουμε από την αρχή,

294
00:14:55,605 --> 00:14:58,760
διασχίζουν όλη τη διαδρομή προς το
τέλος, και στη συνέχεια να το θέτει.

295
00:14:58,760 --> 00:15:01,420
Έτσι, αυτό θα σήμαινε ότι
εισάγοντας στο τέλος της λίστας

296
00:15:01,420 --> 00:15:04,140
θα γίνει ο ν
λειτουργία, πηγαίνοντας πίσω

297
00:15:04,140 --> 00:15:06,720
στη συζήτησή μας της
υπολογιστική πολυπλοκότητα.

298
00:15:06,720 --> 00:15:10,140
Θα ήθελα να γίνει ένα o Ν λειτουργίας, όπου
όπως η λίστα μεγάλωσε και μεγαλύτερες,

299
00:15:10,140 --> 00:15:13,310
και μεγαλύτερα, αυτό θα γίνεται όλο και
πιο δύσκολο να αναστρέψει κάτι

300
00:15:13,310 --> 00:15:14,661
on στο τέλος.

301
00:15:14,661 --> 00:15:17,410
Αλλά είναι πάντα πολύ εύκολο να
καρφί κάτι από την αρχή,

302
00:15:17,410 --> 00:15:19,060
είστε πάντα στην αρχή.

303
00:15:19,060 --> 00:15:21,620
>> Και θα δούμε μια οπτική του ξανά.

304
00:15:21,620 --> 00:15:24,100
Και στη συνέχεια, όταν θα τελειώσετε, μία φορά
έχουμε εισαχθεί το νέο κόμβο,

305
00:15:24,100 --> 00:15:26,880
θέλουμε να επιστρέψουμε στο δείκτη μας
ο νέος επικεφαλής μιας συνδεδεμένης λίστας, η οποία

306
00:15:26,880 --> 00:15:29,213
δεδομένου ότι είμαστε η εισαγωγή σε
ξεκινώντας, θα είναι πράγματι

307
00:15:29,213 --> 00:15:31,060
ένα δείκτη προς τον κόμβο που μόλις δημιουργήσαμε.

308
00:15:31,060 --> 00:15:33,280
Ας απεικονίσει αυτό,
γιατί πιστεύω ότι θα βοηθήσει.

309
00:15:33,280 --> 00:15:36,661
>> Τόσο εδώ είναι λίστα μας, αποτελείται από
τέσσερα στοιχεία, ένας κόμβος που περιέχει 15,

310
00:15:36,661 --> 00:15:38,410
η οποία οδηγεί σε ένα κόμβο
που περιέχουν 9, η οποία

311
00:15:38,410 --> 00:15:41,370
επισημαίνει σε έναν κόμβο που περιέχει 13,
η οποία οδηγεί σε ένα κόμβο που περιέχει

312
00:15:41,370 --> 00:15:44,840
10, η οποία έχει την μηδενική
δείκτη επόμενο δείκτης της

313
00:15:44,840 --> 00:15:47,010
έτσι ώστε να είναι το τέλος της λίστας.

314
00:15:47,010 --> 00:15:50,200
Έτσι θέλουμε να εισαγάγετε ένα
νέος κόμβος με την τιμή 12

315
00:15:50,200 --> 00:15:52,720
στην αρχή αυτού του
λίστα, τι κάνουμε;

316
00:15:52,720 --> 00:15:58,770
Λοιπόν, πρώτα malloc χώρο για την
κόμβος, και στη συνέχεια βάζουμε 12 εκεί.

317
00:15:58,770 --> 00:16:02,211
>> Έτσι τώρα έχουμε φτάσει ένα
σημείο λήψης απόφασης, έτσι δεν είναι;

318
00:16:02,211 --> 00:16:03,960
Έχουμε ένα ζευγάρι των
δείκτες που θα μπορούσαμε να

319
00:16:03,960 --> 00:16:06,770
κίνηση, η οποία θα πρέπει να προχωρήσουμε πρώτα;

320
00:16:06,770 --> 00:16:09,250
Θα πρέπει να κάνουμε για να το σημείο 12
ο νέος επικεφαλής της list--

321
00:16:09,250 --> 00:16:13,020
ή με συγχωρείτε, πρέπει να κάνουμε 12
επισημαίνουν την παλιά κεφαλή της λίστας;

322
00:16:13,020 --> 00:16:15,319
Ή μήπως πρέπει να πούμε ότι η
Λίστα τώρα αρχίζει στις 12.

323
00:16:15,319 --> 00:16:17,110
Υπάρχει μια διάκριση
εκεί, και θα εξετάσουμε

324
00:16:17,110 --> 00:16:19,870
σε ό, τι συμβαίνει με τα δύο σε ένα δευτερόλεπτο.

325
00:16:19,870 --> 00:16:23,350
>> Αλλά αυτό οδηγεί σε ένα
μεγάλο θέμα για την πλαϊνή μπάρα,

326
00:16:23,350 --> 00:16:26,280
η οποία είναι ότι ένα από τα
δυσκολότερο πράγματα με συνδεδεμένες λίστες

327
00:16:26,280 --> 00:16:30,980
είναι να οργανώσει τους δείκτες
με τη σωστή σειρά.

328
00:16:30,980 --> 00:16:34,520
Αν τα πράγματα κινούνται εκτός λειτουργίας,
μπορείτε να καταλήξετε λάθος

329
00:16:34,520 --> 00:16:36,050
ορφανούς το υπόλοιπο της λίστας.

330
00:16:36,050 --> 00:16:37,300
Και εδώ είναι ένα παράδειγμα.

331
00:16:37,300 --> 00:16:40,540
Έτσι, ας πάμε με την ιδέα of--
Λοιπόν, έχουμε δημιουργήσει μόλις 12.

332
00:16:40,540 --> 00:16:43,180
Ξέρουμε 12 πρόκειται να είναι
ο νέος επικεφαλής της λίστας,

333
00:16:43,180 --> 00:16:47,660
και έτσι γιατί δεν μπορούμε απλά μετακινήστε
ο δείκτης κατάλογο στο σημείο εκεί.

334
00:16:47,660 --> 00:16:49,070
>> Εντάξει, έτσι ώστε να είναι καλή.

335
00:16:49,070 --> 00:16:51,560
Έτσι τώρα, όπου κάνει 12 επόμενο σημείο;

336
00:16:51,560 --> 00:16:54,580
Θέλω να πω, οπτικά μπορούμε να δούμε
ότι θα δείχνει 15,

337
00:16:54,580 --> 00:16:57,250
καθώς οι άνθρωποι είναι πραγματικά προφανές για μας.

338
00:16:57,250 --> 00:17:00,300
Πώς ξέρει ο υπολογιστής;

339
00:17:00,300 --> 00:17:02,720
Δεν έχουμε τίποτα
που δείχνουν προς 15 πια, σωστά;

340
00:17:02,720 --> 00:17:05,869
>> Έχουμε χάσει κάθε ικανότητα να αναφερθώ 15.

341
00:17:05,869 --> 00:17:11,460
Δεν μπορούμε να πούμε νέα βέλος δίπλα ίσων
κάτι, δεν υπάρχει τίποτα εκεί.

342
00:17:11,460 --> 00:17:13,510
Στην πραγματικότητα, έχουμε μείνει ορφανά
το υπόλοιπο της λίστας

343
00:17:13,510 --> 00:17:16,465
με αυτόν τον τρόπο, έχουμε
κατά λάθος σπάσει την αλυσίδα.

344
00:17:16,465 --> 00:17:18,089
Και σίγουρα δεν θέλουμε να το κάνουμε αυτό.

345
00:17:18,089 --> 00:17:20,000
>> Ας πάμε πίσω και δοκιμάστε ξανά.

346
00:17:20,000 --> 00:17:24,060
Ίσως το σωστό πράγμα που κάνει
είναι να βρίσκεται δίπλα του δείκτη 12

347
00:17:24,060 --> 00:17:28,290
στην παλιά κεφαλή του πρώτου καταλόγου,
τότε μπορούμε να προχωρήσουμε πάνω από τη λίστα.

348
00:17:28,290 --> 00:17:30,420
Και στην πραγματικότητα, αυτή είναι η
σωστή σειρά ώστε να

349
00:17:30,420 --> 00:17:32,836
πρέπει να ακολουθήσουν όταν είμαστε
σε συνεργασία με μεμονωμένα συνδεδεμένη λίστα.

350
00:17:32,836 --> 00:17:36,460
Εμείς πάντα θέλουμε να συνδέσετε το
νέο στοιχείο στη λίστα,

351
00:17:36,460 --> 00:17:41,010
πριν πάρουμε αυτό το είδος του
σημαντικό βήμα της αλλαγής

352
00:17:41,010 --> 00:17:43,360
όπου ο επικεφαλής της συνδεδεμένης λίστας είναι.

353
00:17:43,360 --> 00:17:46,740
Και πάλι, αυτό είναι ένα τέτοιο βασικό πράγμα,
δεν θέλουμε να χαθούν τα ίχνη του.

354
00:17:46,740 --> 00:17:49,310
>> Έτσι θέλουμε να βεβαιωθείτε ότι
όλα δεμένους,

355
00:17:49,310 --> 00:17:52,040
πριν προχωρήσουμε αυτό το δείκτη.

356
00:17:52,040 --> 00:17:55,300
Και έτσι αυτό θα ήταν η σωστή σειρά,
η οποία είναι η σύνδεση 12 στη λίστα,

357
00:17:55,300 --> 00:17:57,630
τότε λένε ότι ο κατάλογος ξεκινά μια 12.

358
00:17:57,630 --> 00:18:00,860
Αν λέγαμε η λίστα ξεκινά στις 12 και
Στη συνέχεια προσπάθησε να συνδέσει 12 στον κατάλογο,

359
00:18:00,860 --> 00:18:02,193
έχουμε ήδη δει τι συμβαίνει.

360
00:18:02,193 --> 00:18:04,920
Χάνουμε τη λίστα κατά λάθος.

361
00:18:04,920 --> 00:18:06,740
>> Εντάξει, έτσι ένα ακόμη πράγμα που πρέπει να συζητήσουμε.

362
00:18:06,740 --> 00:18:09,750
Τι γίνεται αν θέλουμε να απαλλαγούμε από
μια ολόκληρη συνδεδεμένη λίστα με τη μία;

363
00:18:09,750 --> 00:18:11,750
Και πάλι, είμαστε mallocing
όλα αυτά χώρο, και έτσι

364
00:18:11,750 --> 00:18:13,351
Πρέπει να την απελευθερώσει όταν τελειώσουμε.

365
00:18:13,351 --> 00:18:15,350
Έτσι, τώρα θέλουμε να διαγράψετε
ολόκληρη η συνδεδεμένη λίστα.

366
00:18:15,350 --> 00:18:16,850
Λοιπόν, τι θέλουμε να κάνουμε;

367
00:18:16,850 --> 00:18:20,460
>> Αν έχουμε φτάσει στο null pointer,
θέλουν να σταματήσουν, αλλιώς, απλά να διαγράψετε

368
00:18:20,460 --> 00:18:23,420
το υπόλοιπο της λίστας και, στη συνέχεια, με ελευθερώσει.

369
00:18:23,420 --> 00:18:28,890
Διαγράψτε το υπόλοιπο του καταλόγου,
και στη συνέχεια ελευθερώσει την τρέχοντα κόμβο.

370
00:18:28,890 --> 00:18:32,850
Τι κάνει αυτό ακούγεται σαν,
ποια τεχνική έχει μιλήσαμε

371
00:18:32,850 --> 00:18:35,440
περίπου στο παρελθόν Μήπως αυτό ακούγεται σαν;

372
00:18:35,440 --> 00:18:39,560
Διαγραφή όλοι οι άλλοι, τότε
έρχονται πίσω και να διαγράψετε μου.

373
00:18:39,560 --> 00:18:42,380
>> Αυτό είναι αναδρομή, κάναμε το
πρόβλημα λίγο μικρότερο,

374
00:18:42,380 --> 00:18:46,910
λέμε να διαγράψετε όλους
άλλο, τότε μπορείτε να μου διαγράψετε.

375
00:18:46,910 --> 00:18:50,940
Και περαιτέρω κάτω από το δρόμο, ο κόμβος
Θα πω, διαγράψτε όλους τους άλλους.

376
00:18:50,940 --> 00:18:53,940
Αλλά τελικά θα φτάσουμε το
σημείο όπου η λίστα είναι μηδενική,

377
00:18:53,940 --> 00:18:55,310
και αυτό είναι βασικό μας.

378
00:18:55,310 --> 00:18:57,010
>> Έτσι, ας ρίξουμε μια ματιά σε αυτό,
και πώς αυτό θα μπορούσε να λειτουργήσει.

379
00:18:57,010 --> 00:18:59,759
Τόσο εδώ είναι λίστα μας, είναι το ίδιο
λίστα ήμασταν ακριβώς μιλάμε,

380
00:18:59,759 --> 00:19:00,980
και εκεί τα βήματα.

381
00:19:00,980 --> 00:19:04,200
Υπάρχει πολλή κειμένου εδώ, αλλά
ελπίζουμε ότι η οπτικοποίηση θα βοηθήσει.

382
00:19:04,200 --> 00:19:08,557
>> Γι 'αυτό και have-- και εγώ, επίσης, τράβηξε
μέχρι καρέ stack μας εικόνα

383
00:19:08,557 --> 00:19:10,890
το βίντεο σχετικά με στοίβες κλήση,
και ελπίζουμε ότι όλα αυτά

384
00:19:10,890 --> 00:19:13,260
μαζί θα σας δείξει τι συμβαίνει.

385
00:19:13,260 --> 00:19:14,510
Τόσο εδώ είναι ψευδοκώδικας κωδικό μας.

386
00:19:14,510 --> 00:19:17,830
Αν φτάσουμε σε μηδενική
δείκτης, να σταματήσει, διαφορετικά,

387
00:19:17,830 --> 00:19:21,320
θα διαγράψει το υπόλοιπο της λίστας,
να ελευθερώσετε τον τρέχοντα κόμβο.

388
00:19:21,320 --> 00:19:25,700
Έτσι τώρα, list--
ο δείκτης που είμαστε

389
00:19:25,700 --> 00:19:28,410
περνώντας να καταστρέψει σημεία 12.

390
00:19:28,410 --> 00:19:33,340
12 δεν είναι ένα κενό δείκτη, έτσι είμαστε
πρόκειται να διαγράψει το υπόλοιπο της λίστας.

391
00:19:33,340 --> 00:19:35,450
>> Ποια είναι η διαγραφή
εμάς τους υπόλοιπους που συμμετέχουν;

392
00:19:35,450 --> 00:19:37,950
Λοιπόν, αυτό σημαίνει ότι κάνοντας μια
καλούν να καταστρέψει, λέγοντας

393
00:19:37,950 --> 00:19:42,060
ότι το 15 είναι η αρχή της
υπόλοιπο της λίστας θέλουμε να καταστρέψουμε.

394
00:19:42,060 --> 00:19:47,480
Και έτσι η κλήση για την καταστροφή
12 είναι το είδος του σε αναμονή.

395
00:19:47,480 --> 00:19:52,690
Είναι παγώσει εκεί, περιμένοντας για το
καλούν να καταστρέψει 15, για να τελειώσει τη δουλειά του.

396
00:19:52,690 --> 00:19:56,280
>> Λοιπόν, 15 δεν είναι ένα κενό δείκτη, και
γι 'αυτό πρόκειται να πω, εντάξει,

397
00:19:56,280 --> 00:19:58,450
καλά, διαγράψτε το υπόλοιπο της λίστας.

398
00:19:58,450 --> 00:20:00,760
Το υπόλοιπο της λίστας ξεκινά
στις 9, και έτσι απλά θα

399
00:20:00,760 --> 00:20:04,514
περιμένετε μέχρι να διαγράψετε όλα ότι
πράγματα, στη συνέχεια να επανέλθει και να διαγράψει εμένα.

400
00:20:04,514 --> 00:20:06,680
Καλά 9 πρόκειται να πείτε, καλά,
Δεν είμαι ένα μηδενικό δείκτη,

401
00:20:06,680 --> 00:20:09,020
έτσι θα διαγράψει το υπόλοιπο της λίστας από εδώ.

402
00:20:09,020 --> 00:20:11,805
Και έτσι πρέπει να δοκιμάσετε και να καταστρέψουν 13.

403
00:20:11,805 --> 00:20:15,550
13 λέει, δεν είμαι κενό δείκτη,
ίδιο πράγμα, το μεταθέτει.

404
00:20:15,550 --> 00:20:17,930
10 δεν είναι null pointer, 10
περιέχει ένα κενό δείκτη,

405
00:20:17,930 --> 00:20:20,200
αλλά 10 δεν είναι η ίδια
null pointer τώρα,

406
00:20:20,200 --> 00:20:22,470
και γι 'αυτό το μεταθέτει πάρα πολύ.

407
00:20:22,470 --> 00:20:25,560
>> Και τώρα απαριθμήσει τα σημεία εκεί,
πραγματικά θα ήθελε να some--

408
00:20:25,560 --> 00:20:28,710
αν είχα περισσότερο χώρο στην εικόνα,
θα επισημάνω κάποια τυχαία χώρο

409
00:20:28,710 --> 00:20:29,960
ότι δεν ξέρουμε τι είναι.

410
00:20:29,960 --> 00:20:34,680
Είναι το κενό δείκτη όμως, η λίστα
είναι κυριολεκτικά τώρα είναι τιμές null.

411
00:20:34,680 --> 00:20:36,820
Είναι που δείχνει δεξιά μέσα σε αυτό το κόκκινο κουτί.

412
00:20:36,820 --> 00:20:39,960
Έχουμε φτάσει σε ένα κενό δείκτη, έτσι
μπορούμε να σταματήσουμε, και τελειώσατε.

413
00:20:39,960 --> 00:20:46,230
>> Και έτσι ώστε μοβ πλαίσιο είναι now-- κατά τη
κορυφή της stack-- που είναι το ενεργό πλαίσιο,

414
00:20:46,230 --> 00:20:47,017
αλλά έχει κάνει.

415
00:20:47,017 --> 00:20:48,600
Αν έχουμε φτάσει σε ένα κενό δείκτη, να σταματήσει.

416
00:20:48,600 --> 00:20:51,290
Εμείς δεν κάνουμε τίποτα,
δεν μπορούν να απελευθερώσουν ένα κενό δείκτη,

417
00:20:51,290 --> 00:20:55,070
δεν είχαμε οποιαδήποτε malloc
χώρο, και έτσι τελειώσαμε.

418
00:20:55,070 --> 00:20:57,590
Έτσι αυτό το πλαίσιο λειτουργίας
καταστρέφεται, και εμείς

419
00:20:57,590 --> 00:21:00,930
resume-- έχουμε πάρει όπου είχαμε μείνει
μακριά με το επόμενο υψηλότερο, το οποιο

420
00:21:00,930 --> 00:21:02,807
Είναι αυτό το σκούρο μπλε πλαίσιο εδώ.

421
00:21:02,807 --> 00:21:04,390
Έτσι παίρνουμε δεξιά όπου φύγαμε μακριά.

422
00:21:04,390 --> 00:21:06,598
Θα διαγραφεί το υπόλοιπο του
λίστα ήδη, έτσι και τώρα είμαστε

423
00:21:06,598 --> 00:21:08,000
πρόκειται να απελευθερώσει τις τρέχουσες κόμβους.

424
00:21:08,000 --> 00:21:12,920
Έτσι τώρα μπορούμε να ελευθερώσουμε τον κόμβο αυτό, και τώρα
έχουμε φτάσει στο τέλος της λειτουργίας.

425
00:21:12,920 --> 00:21:16,810
Και έτσι ώστε το πλαίσιο λειτουργίας καταστρέφεται,
και εμείς pick up στο φως μπλε.

426
00:21:16,810 --> 00:21:20,650
>> Γι 'αυτό says-- έχω ήδη done--
διαγράφοντας το υπόλοιπο της λίστας, έτσι

427
00:21:20,650 --> 00:21:23,140
απελευθερώσει το τρέχοντα κόμβο.

428
00:21:23,140 --> 00:21:26,520
Και τώρα το κίτρινο πλαίσιο είναι
πίσω στην κορυφή της στοίβας.

429
00:21:26,520 --> 00:21:29,655
Και έτσι όπως βλέπετε, είμαστε τώρα
καταστρέφοντας τη λίστα από δεξιά προς τα αριστερά.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Τι θα είχε συμβεί, αν και,
αν είχαμε κάνει τα πράγματα με λάθος τρόπο;

432
00:21:37,280 --> 00:21:39,410
Ακριβώς όπως όταν προσπαθήσαμε
για να προσθέσετε ένα στοιχείο.

433
00:21:39,410 --> 00:21:41,909
Αν μπέρδεμα της αλυσίδας, εφόσον
δεν είχαμε συνδέσει τις υποδείξεις

434
00:21:41,909 --> 00:21:44,690
με τη σωστή σειρά, αν θέλουμε
απλά ελευθέρωσε το πρώτο στοιχείο,

435
00:21:44,690 --> 00:21:47,420
αν θέλουμε απλά να απελευθερωθεί η
επικεφαλής της λίστας, τώρα

436
00:21:47,420 --> 00:21:49,642
δεν έχουν τρόπο να αναφερθώ
το υπόλοιπο της λίστας.

437
00:21:49,642 --> 00:21:51,350
Και έτσι θα έχουμε
ορφανά τα πάντα,

438
00:21:51,350 --> 00:21:53,880
θα είχαμε ό, τι είναι
ονομάζεται διαρροή μνήμης.

439
00:21:53,880 --> 00:21:56,800
Αν θυμάστε από το βίντεο μας
για δυναμική κατανομή μνήμης,

440
00:21:56,800 --> 00:21:58,650
αυτό δεν είναι πολύ καλό πράγμα.

441
00:21:58,650 --> 00:22:00,810
>> Έτσι, όπως είπα, υπάρχει
είναι αρκετές λειτουργίες

442
00:22:00,810 --> 00:22:04,010
ότι πρέπει να χρησιμοποιήσουμε για να εργαστούν
με συνδεθεί αποτελεσματικά λίστα.

443
00:22:04,010 --> 00:22:08,430
Και μπορεί να έχετε παρατηρήσει έχω παραλείψει ένα,
Διαγραφή ενός στοιχείου από ένα συνδεδεμένο

444
00:22:08,430 --> 00:22:09,064
κατάλογο.

445
00:22:09,064 --> 00:22:10,980
Ο λόγος που το έκανε αυτό
είναι στην πραγματικότητα το είδος του

446
00:22:10,980 --> 00:22:14,360
δύσκολο να σκεφτούμε πώς να διαγράψετε
ένα ενιαίο στοιχείο από μεμονωμένα

447
00:22:14,360 --> 00:22:15,600
συνδεδεμένη λίστα.

448
00:22:15,600 --> 00:22:19,950
Πρέπει να είμαστε σε θέση να υπερπηδήσει
κάτι στη λίστα, η οποία

449
00:22:19,950 --> 00:22:22,975
σημαίνει να πάμε σε μια point-- μας
θέλετε να διαγράψετε αυτό το node--

450
00:22:22,975 --> 00:22:25,350
αλλά για να το κάνει έτσι
δεν χάνουν καμία πληροφορία,

451
00:22:25,350 --> 00:22:30,530
θα πρέπει να συνδέσετε αυτό
κόμβος εδώ, εδώ.

452
00:22:30,530 --> 00:22:33,390
>> Γι 'αυτό ίσως να έκανε λάθος ότι
από οπτικής απόψεως.

453
00:22:33,390 --> 00:22:36,830
Έτσι είμαστε στην αρχή μας
κατάλογο, είμαστε προχωρά μέσω,

454
00:22:36,830 --> 00:22:40,510
που θέλετε να διαγράψετε αυτό το κόμβο.

455
00:22:40,510 --> 00:22:43,440
Αν θέλουμε απλά να το διαγράψετε,
έχουμε σπάσει την αλυσίδα.

456
00:22:43,440 --> 00:22:45,950
Αυτός ο κόμβος εδώ
αναφέρεται σε οτιδήποτε άλλο,

457
00:22:45,950 --> 00:22:48,260
περιέχει την αλυσίδα από εδώ και πέρα.

458
00:22:48,260 --> 00:22:51,190
>> Έτσι, αυτό που πρέπει να κάνουμε πραγματικότητα
αφού φτάσει σε αυτό το σημείο,

459
00:22:51,190 --> 00:22:56,670
είναι ότι πρέπει να κάνουν ένα βήμα πίσω ένα, και
συνδέστε τον κόμβο αυτό πάνω σε αυτόν τον κόμβο,

460
00:22:56,670 --> 00:22:58,590
έτσι ώστε να μπορέσουμε στη συνέχεια να διαγράψετε
το ένα στη μέση.

461
00:22:58,590 --> 00:23:02,120
Αλλά απλά συνδεδεμένες λίστες δεν
μας παρέχουν έναν τρόπο για να πάει προς τα πίσω.

462
00:23:02,120 --> 00:23:05,160
Γι 'αυτό πρέπει είτε να κρατήσει
δίποντα, και να τους μετακινεί

463
00:23:05,160 --> 00:23:09,527
το είδος των off βήμα, το ένα πίσω από το
άλλα, όπως πάμε, ή να φτάσουμε σε ένα σημείο

464
00:23:09,527 --> 00:23:11,110
και στη συνέχεια να στείλει ένα άλλο δείκτη μέσα.

465
00:23:11,110 --> 00:23:13,150
Και όπως μπορείτε να δείτε,
μπορεί να πάρει λίγο βρώμικο.

466
00:23:13,150 --> 00:23:15,360
Ευτυχώς, έχουμε
Ένας άλλος τρόπος για την επίλυση ότι,

467
00:23:15,360 --> 00:23:17,810
όταν μιλάμε για διπλά συνδεδεμένες λίστες.

468
00:23:17,810 --> 00:23:20,720
>> Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.

469
00:23:20,720 --> 00:23:22,298