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 เราได้ครอบคลุมมากของพื้นฐานของซี เรารู้มากเกี่ยวกับตัวแปรอาร์เรย์ที่ 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 ก็อาจจะ เป็น 1000 ก็อาจจะ 34 00:01:51,940 --> 00:01:55,930 เป็น x ที่ x คือตัวเลขที่ผู้ใช้ ให้เราที่พร้อมท์หรือคำสั่ง 35 00:01:55,930 --> 00:01:56,630 สาย 36 00:01:56,630 --> 00:01:59,905 >> แต่เราเท่านั้นที่ได้รับการยิงหนึ่งที่มันเรา ไม่ได้รับการพูดแล้วโอ้ที่จริงผม 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 ดีถ้าคุณจำได้จากวิดีโอของเรา การกำหนดประเภทที่กำหนดเองที่มีความละเอียดชนิด 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 ช่วยให้ผมแล้วบอกว่าผมต้องการ ตัวชี้ไป sllist struct อื่น 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 และวิธีที่เราอาจเห็นภาพพวกเขา การพูดคุยในรหัส pseudocode เฉพาะ 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 ดังนั้นตอนนี้เรากำลังจะก้าวซี เริ่มต้นเขตข้อมูลค่าโหนด 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 และฉันจะเป็นตัวแทนโมฆะ ชี้เป็นเพียงแค่กล่องสีแดง 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-- บูลพบและ แล้วเราต้องการที่จะผ่านในสองข้อโต้แย้ง 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 เราก็ไม่สามารถพูดว่าฉันต้องการ ไปที่องค์ประกอบ 0, 238 00:12:18,150 --> 00:12:21,410 หรือองค์ประกอบที่ 6 ของอาเรย์ของฉัน ซึ่งผมสามารถทำในอาร์เรย์ 239 00:12:21,410 --> 00:12:25,080 ฉันไม่สามารถพูดฉันต้องการที่จะไป องค์ประกอบ 0 หรือองค์ประกอบที่ 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 เพื่อให้ใส่จำนวนใด วาลคือเข้าไปในโหนด 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 จะกลายเป็นของ n o การดำเนินงานจะกลับ 297 00:15:04,140 --> 00:15:06,720 การสนทนาของเราของ ความซับซ้อนของคอมพิวเตอร์ 298 00:15:06,720 --> 00:15:10,140 มันจะกลายเป็น o n ของการดำเนินการที่ เป็นรายการมีขนาดใหญ่และขนาดใหญ่ 299 00:15:10,140 --> 00:15:13,310 และขนาดใหญ่ก็จะกลายเป็นมากขึ้นและ ยากมากที่จะตรึงบางสิ่งบางอย่าง 300 00:15:13,310 --> 00:15:14,661 ในตอนท้าย 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 orphaning ส่วนที่เหลือของรายการ 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 >> ถ้าเราได้มาถึงตัวชี้โมฆะเรา ต้องการที่จะหยุดมิฉะนั้นเพียงแค่ลบ 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-- และฉันยังดึง ขึ้นเฟรมสแต็คของเราภาพประกอบ 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 ดังนั้นนี่คือรหัส pseudocode ของเรา 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 ไม่ได้เป็นตัวชี้โมฆะ 10 มีตัวชี้โมฆะ 405 00:20:17,930 --> 00:20:20,200 แต่ 10 ไม่ได้เป็นตัวเอง ตัวชี้ null ตอนนี้ 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 มันเป็นตัวชี้โมฆะ แต่รายการ เป็นอักษรชุดนี้มันเป็นค่าโมฆะ 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 และเพื่อให้กรอบการทำงานที่ถูกทำลาย และเรารับที่แสงสีฟ้าหนึ่ง 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 ถ้าเรา messed ขึ้นห่วงโซ่ถ้า เราไม่ได้เชื่อมต่อตัวชี้ 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 การเรียงลำดับของขั้นตอนออกหนึ่งที่อยู่เบื้องหลัง อื่น ๆ ที่เราไปหรือได้รับไปยังจุด 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 >> ฉันลอยด์ดั๊กนี้เป็น CS50 469 00:23:20,720 --> 00:23:22,298