1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[השמעת מוסיקה]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID מלאן: זה CS50.

5
00:00:14,010 --> 00:00:18,090
וזה הוא גם ההתחלה ו
end-- כמו literally-- כמעט הסוף

6
00:00:18,090 --> 00:00:18,825
שבוע שישה.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> חשבתי שאני רוצה לחלוק
קצת עובדה כיף.

9
00:00:22,640 --> 00:00:25,370
שלפתי את זה מ
נתונים של הסמסטר האחרון שנקבעו.

10
00:00:25,370 --> 00:00:29,710
אולי אתה זוכר שאנחנו מבקשים מכם בכל
צורת סט p אם ראה באינטרנט

11
00:00:29,710 --> 00:00:31,580
או אם אתה כבר השתתף באופן אישי.

12
00:00:31,580 --> 00:00:33,020
והנה הנתונים.

13
00:00:33,020 --> 00:00:34,710
אז היום היה צפוי מאוד.

14
00:00:34,710 --> 00:00:37,126
אבל רצינו לבלות קצת
זמן איתך בכל זאת.

15
00:00:37,126 --> 00:00:40,599
האם מישהו רוצה לנחש למה זה
גרף הוא כל כך jaggy, עד למטה, למעלה למטה,

16
00:00:40,599 --> 00:00:41,265
כך באופן עקבי?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
מה לעשות כל אחד מהפסגות
ושקתות מייצגות?

19
00:00:45,130 --> 00:00:46,005
>> קהל: [לא ברור]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID מלאן: אכן.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
ועוד בצורה משעשעת, חס וחלילה,
אנו מחזיקים הרצאה אחת ביום שישי

24
00:00:55,480 --> 00:00:58,960
בתחילת הסמסטר,
זה מה שאנו רואים במקרה.

25
00:00:58,960 --> 00:01:03,430
אז היום, אנחנו אוכלים בקצת
נוסף על מבני נתונים.

26
00:01:03,430 --> 00:01:06,660
ולתת לך יותר ממוצק
מודל המנטלי לבעיות בחמש,

27
00:01:06,660 --> 00:01:07,450
שנמצא עכשיו החוצה.

28
00:01:07,450 --> 00:01:10,817
שגיאות כתיב, שבו, אנחנו
למסור לך קובץ טקסט כ -100,000

29
00:01:10,817 --> 00:01:12,650
בתוספת מילות באנגלית, ו
אתה הולך לי

30
00:01:12,650 --> 00:01:17,770
כדי להבין איך לטעון אותם בחוכמה
לזיכרון, לזכרון RAM, באמצעות כמה נתונים

31
00:01:17,770 --> 00:01:19,330
מבנה על פי בחירתך.

32
00:01:19,330 --> 00:01:22,470
>> עכשיו מבנה נתונים כזה יכול
להיות, אבל כנראה לא צריך להיות,

33
00:01:22,470 --> 00:01:25,630
הרשימה למדי פשטנית קשורה,
שהצגנו בפעם האחרונה.

34
00:01:25,630 --> 00:01:29,220
והייתה לו רשימה מקושרת לפחות
יתרון אחד על פני מערך.

35
00:01:29,220 --> 00:01:32,096
מה יתרון אחד
רשימה מקושרת ניתן לטעון?

36
00:01:32,096 --> 00:01:32,950
>> קהל: הכנסה.

37
00:01:32,950 --> 00:01:33,908
>> DAVID מלאן: הכנסה.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
מה אתה מתכוון?

40
00:01:35,196 --> 00:01:37,872
>> קהל: בכל מקום לאורך
הרשימה [לא ברור].

41
00:01:37,872 --> 00:01:38,770
>> DAVID מלאן: טוב.

42
00:01:38,770 --> 00:01:42,090
אז אתה יכול להכניס אלמנט בכל מקום
אתה רוצה באמצע הרשימה

43
00:01:42,090 --> 00:01:45,490
מבלי לערבב כל דבר,
שהגענו למסקנה, במיון שלנו

44
00:01:45,490 --> 00:01:47,630
דיונים, לא
בהכרח דבר טוב,

45
00:01:47,630 --> 00:01:51,200
כי זה לוקח זמן לעבור למעשה
כל בני האדם אלה שמאלה או ימינה.

46
00:01:51,200 --> 00:01:55,540
וכך, עם רשימה מקושרת, אתה יכול
רק להקצות עם malloc, צומת חדשה,

47
00:01:55,540 --> 00:01:58,385
ולאחר מכן לעדכן כמה
pointers-- שני, שלושה ניתוחים max--

48
00:01:58,385 --> 00:02:01,480
ואנחנו מסוגלים חריץ מישהו
בכל מקום לרשימה.

49
00:02:01,480 --> 00:02:03,550
>> מה עוד היה יתרון
על רשימה מקושרת?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
כן?

52
00:02:05,659 --> 00:02:06,534
>> קהל: [לא ברור]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID מלאן: מושלם.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
מושלם.

57
00:02:11,090 --> 00:02:12,070
זה ממש דינמי.

58
00:02:12,070 --> 00:02:15,100
וזה שאתה לא מבצע,
מראש, לכמה גודל קבוע

59
00:02:15,100 --> 00:02:18,750
נתח של זיכרון, כמו שהיית לי
לעם מערך, ההפוך מהם

60
00:02:18,750 --> 00:02:22,455
הוא שאתה יכול להקצות צמתים רק ב
ביקוש ובכך רק באמצעות חלל כמה שיותר

61
00:02:22,455 --> 00:02:23,330
כפי שאתה באמת צריך.

62
00:02:23,330 --> 00:02:26,830
בניגוד למערך, אתה עלול
להקצות מעט מדי בטעות.

63
00:02:26,830 --> 00:02:28,871
ואז זה רק הולך
להיות כאב בצוואר

64
00:02:28,871 --> 00:02:32,440
להקצאה מחדש של מערך גדול חדש, להעתיק
כל מה שמעל, לשחרר את המערך הישן,

65
00:02:32,440 --> 00:02:33,990
ולאחר מכן להעביר על העסק שלך.

66
00:02:33,990 --> 00:02:37,479
או גרוע מכך, ייתכן שתקצה דרך
יותר זיכרון ממה שאתה באמת צריך,

67
00:02:37,479 --> 00:02:40,520
ואז אתה הולך להיות מאוד
דלילות אוכלוסין מערך, אם אפשר לומר כך.

68
00:02:40,520 --> 00:02:44,350
>> אז רשימה מקושרת נותנת לך אלה
יתרונות של הדינמיות וגמישות

69
00:02:44,350 --> 00:02:46,080
עם הוספות ומחיקות.

70
00:02:46,080 --> 00:02:48,000
אבל אין ספק שחייב להיות מחיר ששלם.

71
00:02:48,000 --> 00:02:50,000
למעשה, אחד הנושאים
חקר על חידון אפס

72
00:02:50,000 --> 00:02:52,430
היה כמה הפשרות
שראינו עד כה.

73
00:02:52,430 --> 00:02:56,161
אז מה מחיר ששולם או
חסרון של רשימה מקושרת?

74
00:02:56,161 --> 00:02:56,660
כן.

75
00:02:56,660 --> 00:02:57,560
>> קהל: לא גישה אקראית.

76
00:02:57,560 --> 00:02:58,809
>> DAVID מלאן: אין גישה אקראית.

77
00:02:58,809 --> 00:02:59,540
אבל למי אכפת?

78
00:02:59,540 --> 00:03:01,546
הגישה אקראית לא נשמעה משכנעת.

79
00:03:01,546 --> 00:03:02,421
>> קהל: [לא ברור]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID מלאן: בדיוק.

82
00:03:05,740 --> 00:03:07,580
אם אתה רוצה יש לי
algorithm-- מסוים

83
00:03:07,580 --> 00:03:10,170
ותן לי למעשה מציע
חיפוש בינארי בפרט, ש

84
00:03:10,170 --> 00:03:12,600
הוא אחד מאלה שהשתמשנו די bit--
אם אין לך גישה אקראית,

85
00:03:12,600 --> 00:03:15,516
אתה לא יכול לעשות את זה חשבון פשוט
למצוא כמו אלמנט האמצע

86
00:03:15,516 --> 00:03:16,530
ולקפוץ ישר לעניין.

87
00:03:16,530 --> 00:03:20,239
אתה במקום להתחיל בשעה הראשונה
אלמנט ואופן ליניארי חיפוש משמאל

88
00:03:20,239 --> 00:03:22,780
לימין אם אתה רוצה למצוא
באמצע או כל גורם אחר.

89
00:03:22,780 --> 00:03:24,410
>> קהל: זה כנראה לוקח יותר זיכרון.

90
00:03:24,410 --> 00:03:25,040
>> DAVID מלאן: לוקח יותר זיכרון.

91
00:03:25,040 --> 00:03:27,464
איפה שנוסף
העלות מגיעה בזיכרון?

92
00:03:27,464 --> 00:03:28,339
>> קהל: [לא ברור]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID מלאן: בדיוק.

95
00:03:33,440 --> 00:03:35,679
במקרה זה כאן, היה לנו
רשימה מקושרת למספרים שלמים,

96
00:03:35,679 --> 00:03:37,470
ובכל זאת, אנחנו מכפילים
כמות הזיכרון

97
00:03:37,470 --> 00:03:39,680
אנחנו צריכים גם על ידי אחסון מצביעים אלה.

98
00:03:39,680 --> 00:03:42,090
עכשיו פחות מזה עניין גדול כ
structs שלך לקבל גדול

99
00:03:42,090 --> 00:03:45,320
ואתה אחסון לא מספר אך
אולי סטודנט או חפץ אחר.

100
00:03:45,320 --> 00:03:46,880
אבל הנקודה בהחלט נשארה.

101
00:03:46,880 --> 00:03:49,421
וכך מספר הפעולות
ברשימות מקושרות נקראו

102
00:03:49,421 --> 00:03:50,570
היו O הגדול של יניארי n--.

103
00:03:50,570 --> 00:03:54,730
דברים כמו הכנסה או חיפוש
או מחיקה במקרה אלמנט

104
00:03:54,730 --> 00:03:57,720
היה במקרה בסופו של
הרשימה אם זה מיון או לא.

105
00:03:57,720 --> 00:04:01,167
>> לפעמים אתה עלול לקבל מזל וב
גבולות כל כך נמוכים על פעולות אלה

106
00:04:01,167 --> 00:04:04,250
גם יכול להיות זמן קבוע אם אתה
תמיד מסתכל האלמנט הראשון,

107
00:04:04,250 --> 00:04:05,070
למשל.

108
00:04:05,070 --> 00:04:09,360
אבל סופו של דבר, שהבטחנו
כדי להשיג את הגביע הקדוש

109
00:04:09,360 --> 00:04:12,630
מבני נתונים, או
חלק מהם הקירוב,

110
00:04:12,630 --> 00:04:14,290
בדרך של זמן קבוע.

111
00:04:14,290 --> 00:04:17,579
האם אנחנו יכולים למצוא אלמנטים או להוסיף רכיבים
או להסיר אלמנטים מרשימה?

112
00:04:17,579 --> 00:04:19,059
שנראה די בקרוב.

113
00:04:19,059 --> 00:04:21,100
ומתברר שאחד
של המנגנונים אנחנו

114
00:04:21,100 --> 00:04:23,464
הולך להתחיל להשתמש היום,
שימוש שנתי בעמ להגדיר חמש,

115
00:04:23,464 --> 00:04:24,630
הוא למעשה די מוכר.

116
00:04:24,630 --> 00:04:27,430
לדוגמא, אם מדובר בחבורה
ספרי בחינה, כל אחד מהם

117
00:04:27,430 --> 00:04:29,660
יש של התלמיד ראשון
שם ושם משפחה עליו,

118
00:04:29,660 --> 00:04:31,820
ואני מרים אותם מ
בסוף הבחינה,

119
00:04:31,820 --> 00:04:33,746
והם כולם די
הרבה בסדר אקראי,

120
00:04:33,746 --> 00:04:36,370
ואנחנו רוצים ללכת על מיון
בחינות אלה, כך שמדורגות פעם אחת

121
00:04:36,370 --> 00:04:38,661
זה פשוט הרבה יותר קל ו
מהר יותר למסור אותם בחזרה החוצה

122
00:04:38,661 --> 00:04:40,030
לתלמידים לפי סדר אלפביתי.

123
00:04:40,030 --> 00:04:42,770
מה היית האינסטינקטים שלך יהיו
לערימת בחינות כמו זה?

124
00:04:42,770 --> 00:04:45,019
>> ובכן, אם אתה אוהב אותי, אתה
אולי תראה שזה מ ',

125
00:04:45,019 --> 00:04:48,505
אז אני הולך לשים סוג של זה ל,
אם זה השולחן שלי או הרצפה שלי שבו

126
00:04:48,505 --> 00:04:50,650
אני מתפשט דברים
out-- או המערך שלי אמת--

127
00:04:50,650 --> 00:04:52,210
אני יכול לשים את כל הגב שביש.

128
00:04:52,210 --> 00:04:52,710
אה.

129
00:04:52,710 --> 00:04:55,020
הנה א 'אז אני יכול
לשים כלכאן.

130
00:04:55,020 --> 00:04:55,520
אה.

131
00:04:55,520 --> 00:04:57,980
הנה א 'עוד אני הולך
לשים את זה כאן.

132
00:04:57,980 --> 00:05:02,490
הנה ז הנה מ 'נוסף וכך
אני יכול להתחיל להרוויח ערימות כמו זה.

133
00:05:02,490 --> 00:05:06,620
ואז אולי הייתי הולך במאוחר
ומאוד קטנוני-ly מיין של

134
00:05:06,620 --> 00:05:07,710
הערימות בודדות.

135
00:05:07,710 --> 00:05:11,300
אבל הנקודה היא שאני תיראה
בכניסה שאני בידיים

136
00:05:11,300 --> 00:05:14,016
והייתי עושה כמה מחושב
החלטה המבוססת על קלט ש.

137
00:05:14,016 --> 00:05:15,640
אם הוא מתחיל ב, לשים אותו שם.

138
00:05:15,640 --> 00:05:18,980
אם הוא מתחיל בZ, לשים אותו על
יש, וכל מה שבין.

139
00:05:18,980 --> 00:05:22,730
>> אז זה טכניקה זה
ידוע בדרך כלל כhashing-- H--S-H--

140
00:05:22,730 --> 00:05:26,550
אשר בדרך כלל פירושו לקחת כ
קלט ובאמצעות קלט שכדי לחשב

141
00:05:26,550 --> 00:05:30,940
ערך, בדרך כלל מספר, וש
מספר הוא המדד לאחסון

142
00:05:30,940 --> 00:05:32,260
מיכל, כמו מערך.

143
00:05:32,260 --> 00:05:35,490
אז במילים אחרות, אולי יש לי
פונקצית חשיש, כפי שאני עושה בראש שלי,

144
00:05:35,490 --> 00:05:37,940
שאם אני רואה מישהו זה
שם שמתחיל ב,

145
00:05:37,940 --> 00:05:40,190
אני הולך המפה ש
אפס בראש שלי.

146
00:05:40,190 --> 00:05:44,160
ואם אני רואה מישהו עם Z, אני
הולך מפה שעד 25 בראש שלי

147
00:05:44,160 --> 00:05:46,220
ואז לשים את זה ב
רוב הערימה האחרונה.

148
00:05:46,220 --> 00:05:50,990
>> עכשיו, אם אתה חושב על לא המוח שלי
אבל תכנית C, מה מספרים יכולים

149
00:05:50,990 --> 00:05:53,170
אתה מסתמך על מנת להשיג את אותה תוצאה?

150
00:05:53,170 --> 00:05:55,594
במילים אחרות, אם אתה
היה לי אופי ASCII,

151
00:05:55,594 --> 00:05:57,510
איך אתה לקבוע
מה דלי ללשים אותו ב?

152
00:05:57,510 --> 00:05:59,801
אתה בטח לא רוצה
הכניס אותו לתוך דלי 65, ש

153
00:05:59,801 --> 00:06:01,840
יהיה כמו שם יהיה
ללא סיבה טובה.

154
00:06:01,840 --> 00:06:04,320
איפה אתה רוצה לשים את
במונחים של ערך ASCII שלו?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
איפה אתה רוצה לעשות לASCII שלו
הערך לבוא עם דלי חכמה יותר

157
00:06:08,920 --> 00:06:09,480
לשים את זה ב?

158
00:06:09,480 --> 00:06:10,206
>> קהל: א 'מינוס

159
00:06:10,206 --> 00:06:10,956
>> DAVID מלאן: כן.

160
00:06:10,956 --> 00:06:13,190
אז מינוס או מינוס
במיוחד 65 אם זה

161
00:06:13,190 --> 00:06:18,240
א הון או 98 אם
זה קטנה.

162
00:06:18,240 --> 00:06:21,300
וכדי שיאפשר לנו, מאוד
פשוט ומאוד אריתמטית,

163
00:06:21,300 --> 00:06:23,260
מכניס משהו לדלי כמו ש.

164
00:06:23,260 --> 00:06:26,010
אז מתברר שאנחנו עושים בפועל
זה גם אפילו עם החידונים.

165
00:06:26,010 --> 00:06:29,051
>> אז אתם אולי זוכרים אותך הקפתם
שמו של בחור הוראה על העטיפה.

166
00:06:29,051 --> 00:06:32,270
והשמות של TF היו מאורגנים
בטורים אלה בסדר אלפביתי,

167
00:06:32,270 --> 00:06:34,400
גם, תאמינו או לא,
כאשר כל 80 בתוספת שלנו

168
00:06:34,400 --> 00:06:37,800
התכנסתי בלילה לכיתה,
השלב האחרון בתהליך הדירוג שלנו

169
00:06:37,800 --> 00:06:41,830
הוא חשיש החידונים לגדולים
שטח של רצפה ב[ לא ברור]

170
00:06:41,830 --> 00:06:45,110
ולהניח החידונים של כולם החוצה
לפי הסדר בדיוק של TF שלהם

171
00:06:45,110 --> 00:06:47,700
שמות על העטיפה, כי
אז זה הרבה יותר קל לנו

172
00:06:47,700 --> 00:06:51,290
לחפש דרך שליניארי באמצעות
לחפש או איזה סוג של התחכמות

173
00:06:51,290 --> 00:06:54,050
לTF למצוא או
החידונים של תלמידיה.

174
00:06:54,050 --> 00:06:56,060
>> אז הרעיון הזה של hashing
שתראה הוא

175
00:06:56,060 --> 00:07:00,520
די חזק הוא די בעצם
דבר שבשגרה ומאוד אינטואיטיבי,

176
00:07:00,520 --> 00:07:03,000
בדומה לחלק אולי ו
כיבוש היה בשבוע אפס.

177
00:07:03,000 --> 00:07:05,250
קדימה מהר אני להאקאתון
לפני כמה שנים.

178
00:07:05,250 --> 00:07:08,040
זה היה Zamyla וכמה
תלמידי ברכת צוות אחרים

179
00:07:08,040 --> 00:07:09,030
כפי שהם באו.

180
00:07:09,030 --> 00:07:12,680
והיו לנו חבורה של קיפול כל
שולחנות שם עם תגים שם.

181
00:07:12,680 --> 00:07:15,380
והיינו לנו התגים שם מאורגנים
עם כמו כשם

182
00:07:15,380 --> 00:07:16,690
וZS שם.

183
00:07:16,690 --> 00:07:20,350
ואז אחד מTFS מאוד בחוכמה
כתב זאת בהוראות

184
00:07:20,350 --> 00:07:21,030
ליום.

185
00:07:21,030 --> 00:07:24,480
ובשבוע השני של הסמסטר זה 12
הכול הגיוני וכולם מושלמים

186
00:07:24,480 --> 00:07:25,310
לא ידע מה לעשות.

187
00:07:25,310 --> 00:07:27,900
אבל בכל עת שיש לך
בתור באותה הדרך,

188
00:07:27,900 --> 00:07:30,272
אתה מיישם את
אותו רעיון של חשיש.

189
00:07:30,272 --> 00:07:31,730
אז בואו למסד את זה קצת.

190
00:07:31,730 --> 00:07:32,890
כאן הוא מערך.

191
00:07:32,890 --> 00:07:36,820
זה נמשך להיות קצת
רחב רק לתאר, מבחינה ויזואלית,

192
00:07:36,820 --> 00:07:38,920
שאנו עלולים לשים מחרוזות
במשהו כזה.

193
00:07:38,920 --> 00:07:41,970
ומערך זה הוא
ברור בגודל 26 סך הכל.

194
00:07:41,970 --> 00:07:43,935
והדבר נקרא
שולחן באופן שרירותי.

195
00:07:43,935 --> 00:07:48,930
אבל זה רק ביצוע של אמן
ממה שטבלת חשיש עלולה להיות.

196
00:07:48,930 --> 00:07:52,799
>> אז טבלת חשיש עכשיו הוא הולכת
להיות מבנה נתונים ברמה גבוה יותר.

197
00:07:52,799 --> 00:07:54,840
בסופו של היום
אנחנו עומדים לראות שאתה

198
00:07:54,840 --> 00:07:58,700
יכול ליישם טבלת חשיש, ש
הרבה כמו קו זמן השק-אין

199
00:07:58,700 --> 00:08:02,059
בהאקאתון הרבה כמו זה
שולחן המשמש למיון ספרי בחינה.

200
00:08:02,059 --> 00:08:03,850
אבל שולחן חשיש
סוג של רמה גבוהה זו

201
00:08:03,850 --> 00:08:08,250
רעיון שיכול להשתמש במערך
מתחת למכסת המנוע כדי ליישם אותה,

202
00:08:08,250 --> 00:08:11,890
או שזה יכול להשתמש ברשימת אורך, או אפילו
אולי כמה מבני נתונים אחרים.

203
00:08:11,890 --> 00:08:15,590
ועכשיו זה הלקיחה theme--
כמה ממרכיבי יסוד אלה

204
00:08:15,590 --> 00:08:18,310
כמו מערך והבניין הזה
לחסום עכשיו של רשימה באורך

205
00:08:18,310 --> 00:08:21,740
ולראות מה עוד אנחנו יכולים לבנות
על גבי אלה, כמו מרכיבים

206
00:08:21,740 --> 00:08:26,550
למתכון, מה שהופך יותר ויותר
תוצאות סופיות מעניינות ושימושיות.

207
00:08:26,550 --> 00:08:28,680
>> אז עם שולחן החשיש
אולי ליישם אותו

208
00:08:28,680 --> 00:08:32,540
בזיכרון ציורי כמו זה, אבל
איך ייתכן שזה באמת להיות מקודד עד?

209
00:08:32,540 --> 00:08:33,789
ובכן, אולי כפשוט זה.

210
00:08:33,789 --> 00:08:38,270
אם יכולת בכל כמוסות, היא פשוט
כמה constant-- למשל 26,

211
00:08:38,270 --> 00:08:42,030
26 מכתבים של alphabet--
אני יכול לקרוא לי השולחן משתנה,

212
00:08:42,030 --> 00:08:45,630
ואני יכול לטעון שאני הולך
לשים כוכבי char שם, או מחרוזת.

213
00:08:45,630 --> 00:08:49,880
אז זה פשוט כמו זה אם אתה
רוצה ליישם טבלת חשיש.

214
00:08:49,880 --> 00:08:51,490
ובכל זאת, זה באמת רק מערך.

215
00:08:51,490 --> 00:08:53,198
אבל שוב, חשיש
שולחן הוא עכשיו מה יהיה לנו

216
00:08:53,198 --> 00:08:57,470
קורא סוג נתונים מופשט שרק
סוג של שכבות רעיוניות על גבי

217
00:08:57,470 --> 00:09:00,780
של משהו ארצי יותר
עכשיו כמו מערך.

218
00:09:00,780 --> 00:09:02,960
>> עכשיו, איך אנו עושים
על פתרון בעיות?

219
00:09:02,960 --> 00:09:06,980
ובכן, קודם לכן לא היה לי את הלוקסוס
שיש שטח שולחן מספיק כאן

220
00:09:06,980 --> 00:09:09,460
כדי שאוכל לשים את
חידונים בכל מקום שאני רוצה.

221
00:09:09,460 --> 00:09:10,620
אז כפי שאפשר ללכת כאן.

222
00:09:10,620 --> 00:09:12,100
ZS יכול ללכת כאן.

223
00:09:12,100 --> 00:09:13,230
הגב 'יכול ללכת לכאן.

224
00:09:13,230 --> 00:09:14,740
ואז היה לי כמה שטח נוסף.

225
00:09:14,740 --> 00:09:18,740
אבל זה קצת נכון לרמות
עכשיו בגלל השולחן הזה, אם אני באמת

226
00:09:18,740 --> 00:09:22,720
חשב על זה כעל מערך, הוא פשוט
הולך להיות קצת בגודל קבוע.

227
00:09:22,720 --> 00:09:25,380
>> אז מבחינה טכנית, אם אני מושך
עד החידון של תלמיד אחר

228
00:09:25,380 --> 00:09:28,490
ותראה, אה, אדם זה של
שם מתחילה עם יותר מדי,

229
00:09:28,490 --> 00:09:30,980
אני די רוצה לשים את זה שם.

230
00:09:30,980 --> 00:09:34,740
אבל ברגע שאני שם אותו שם, אם
טבלה זו אכן מייצגת מערך,

231
00:09:34,740 --> 00:09:37,840
אני הולך להיות דריסה או מחץ
מי החידון של תלמיד זה.

232
00:09:37,840 --> 00:09:38,340
נכון?

233
00:09:38,340 --> 00:09:41,972
אם זה מערך, יכול רק דבר אחד
ללכת בכל אחד מהתאים או המרכיבים האלה.

234
00:09:41,972 --> 00:09:43,680
ואז אני סוג של יש לי
לבחור ולבחור.

235
00:09:43,680 --> 00:09:45,735
>> עכשיו קודם לכן סוג של
רימיתי ועשה לי את זה או

236
00:09:45,735 --> 00:09:47,526
פשוט סוג של נערם
שלהם מעל אחד את השני.

237
00:09:47,526 --> 00:09:49,170
אבל זה לא הולך לטוס בקוד.

238
00:09:49,170 --> 00:09:52,260
אז איפה אני יכול לשים את
תלמיד שני ששמו

239
00:09:52,260 --> 00:09:54,964
הוא אם כל מה שהיה לי היא זו
שטח שולחן זמין?

240
00:09:54,964 --> 00:09:57,880
ואני השתמשתי בשלושה חריצים ו
נראה כאילו יש רק כמה אחרים.

241
00:09:57,880 --> 00:09:58,959
מה אתה יכול לעשות?

242
00:09:58,959 --> 00:09:59,834
קהל: [לא ברור]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID מלאן: כן.

245
00:10:01,315 --> 00:10:02,370
אולי בואו פשוט לשמור את זה פשוט.

246
00:10:02,370 --> 00:10:02,660
נכון?

247
00:10:02,660 --> 00:10:04,243
זה לא מתאים שבו אני רוצה לשים את זה.

248
00:10:04,243 --> 00:10:07,450
אז אני הולך לשים את זה
מבחינה טכנית שבו היה ב 'ללכת.

249
00:10:07,450 --> 00:10:09,932
עכשיו, כמובן, אני מתחיל
לצייר את עצמי לפינה.

250
00:10:09,932 --> 00:10:11,890
אם אני מגיע לסטודנט
שמו הוא למעשה B,

251
00:10:11,890 --> 00:10:14,840
עכשיו ב 'הולך להיות זז מעט
קדימה, שכעלול לקרות, כן,

252
00:10:14,840 --> 00:10:17,530
אם זה B, עכשיו הוא צריך ללכת כאן.

253
00:10:17,530 --> 00:10:20,180
>> ואז זה מהר מאוד
יכול להיות בעייתי,

254
00:10:20,180 --> 00:10:23,850
אבל זה טכניקה שלמעשה
המכונה ליניארי חיטוט,

255
00:10:23,850 --> 00:10:26,650
שבו אתה רק רואה
מערך להיות לאורך הקו.

256
00:10:26,650 --> 00:10:29,680
ואתה פשוט סוג של הבדיקה או
לבדוק כל רכיב זמין

257
00:10:29,680 --> 00:10:31,360
מחפש מקום פנוי.

258
00:10:31,360 --> 00:10:34,010
וברגע שאתה מוצא
אחד, אתה מפיל אותו לשם.

259
00:10:34,010 --> 00:10:38,390
>> עכשיו, המחיר שמשלם החברה
לפתרון זה הוא מה?

260
00:10:38,390 --> 00:10:41,300
יש לנו מערך בגודל קבוע,
וכאשר אני מכניס שמות

261
00:10:41,300 --> 00:10:44,059
לתוך זה, לפחות בהתחלה, מה ש
זמן הריצה של הכנסה

262
00:10:44,059 --> 00:10:46,350
לשים את התלמידים "
חידונים בדליים נכון?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
O הגדול של מה?

265
00:10:50,002 --> 00:10:51,147
>> קהל: n.

266
00:10:51,147 --> 00:10:52,480
DAVID מלאן: שמעתי O הגדול של n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
לא נכון.

269
00:10:54,300 --> 00:10:56,490
אבל אנחנו להפריד
מדוע ברגע.

270
00:10:56,490 --> 00:10:57,702
מה עוד יכול להיות?

271
00:10:57,702 --> 00:10:58,755
>> קהל: [לא ברור]

272
00:10:58,755 --> 00:11:00,380
DAVID מלאן: ותן לי לעשות את זה מבחינה ויזואלית.

273
00:11:00,380 --> 00:11:04,720
אז נניח שזה האות S

274
00:11:04,720 --> 00:11:05,604
>> קהל: זה אחד.

275
00:11:05,604 --> 00:11:06,520
DAVID מלאן: זה אחד.

276
00:11:06,520 --> 00:11:06,710
נכון?

277
00:11:06,710 --> 00:11:08,950
זה הוא מערך, ש
משמעות הדבר היא שיש לנו גישה אקראית.

278
00:11:08,950 --> 00:11:11,790
ואם אנו חושבים על זה
כאפס וזה 25,

279
00:11:11,790 --> 00:11:13,800
ואנו מבינים כי,
הו, הנה S הקלט שלי,

280
00:11:13,800 --> 00:11:16,350
אני בהחלט יכול להמיר
S, תווי ASCII,

281
00:11:16,350 --> 00:11:18,540
למספר מתאים
בין אפס 25

282
00:11:18,540 --> 00:11:20,910
ולאחר מכן באופן מיידי
לשים אותו למקום שלו.

283
00:11:20,910 --> 00:11:26,120
>> אבל כמובן, ברגע שאני מגיע ל
אדם שני ששם הוא A או B או C

284
00:11:26,120 --> 00:11:29,300
סופו של דבר, אם אני כבר בשימוש
ליניארי חיטוט כפתרון שלי,

285
00:11:29,300 --> 00:11:31,360
זמן הריצה של
הכנסה במקרה הגרוע ביותר

286
00:11:31,360 --> 00:11:33,120
הוא בעצם הולך לרדת ברמה למה?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
ואני לא שמעתי את זה כאן
בצורה נכונה בשלב מוקדם.

289
00:11:36,045 --> 00:11:36,920
קהל: [לא ברור]

290
00:11:36,920 --> 00:11:41,620
DAVID מלאן: אז זה n אכן פעם אחת
יש לך סט נתונים גדול מספיק.

291
00:11:41,620 --> 00:11:44,410
אז, מצד האחד, אם
המערך שלך הוא גדול מספיק

292
00:11:44,410 --> 00:11:48,287
הנתונים שלך, והוא דליל מספיק, לך
מקבל זמן קבוע זה יפה.

293
00:11:48,287 --> 00:11:50,620
אבל ברגע שאתה מתחיל
מקבל יותר ויותר אלמנטים,

294
00:11:50,620 --> 00:11:53,200
ורק מבחינה סטטיסטית אתה מקבל
יותר אנשים עם המכתב

295
00:11:53,200 --> 00:11:56,030
שמם כאו המכתב
B, הוא עלול

296
00:11:56,030 --> 00:11:57,900
לרדת ברמה למשהו יותר ליניארי.

297
00:11:57,900 --> 00:11:59,640
אז לא ממש מושלם.

298
00:11:59,640 --> 00:12:00,690
אז אנחנו יכולים לעשות טובים יותר?

299
00:12:00,690 --> 00:12:03,210
>> ובכן, מה היה שלנו
פתרון לפני כשאנחנו

300
00:12:03,210 --> 00:12:06,820
רוצה יותר דינמי מאשר
משהו כמו מערך מותר?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
קהל: [לא ברור]

303
00:12:08,960 --> 00:12:10,030
DAVID מלאן: מה עשיתי להציג?

304
00:12:10,030 --> 00:12:10,530
כן.

305
00:12:10,530 --> 00:12:11,430
אז רשימה מקושרת.

306
00:12:11,430 --> 00:12:14,430
ובכן, בואו נראה מה קשור
רשימה עשויה לעשות עבורנו במקום.

307
00:12:14,430 --> 00:12:17,630
ובכן, הרשה לי להציע לנו ש
לצייר את התמונה באופן הבא.

308
00:12:17,630 --> 00:12:19,620
עכשיו זה שונה
תמונה מדוגמה

309
00:12:19,620 --> 00:12:24,750
מטקסט שונה, למעשה, ש
הוא למעשה משתמש במערך של גודל 31.

310
00:12:24,750 --> 00:12:28,220
ומחבר זה פשוט
החליט חשיש מחרוזות

311
00:12:28,220 --> 00:12:32,430
אינו מבוסס על השמות של האדם,
אבל על סמך תאריכי הלידה שלהם.

312
00:12:32,430 --> 00:12:35,680
ללא קשר לחודש, שהם חשבו
אם אתה נולד ביום הראשון של חודש

313
00:12:35,680 --> 00:12:39,580
או ה -31 של חודש, המחבר
יהיה חשיש המבוסס על הערך ש,

314
00:12:39,580 --> 00:12:44,154
כדי להפיץ את השמות מתוך קצת
יותר מסתם 26 נקודות עשויות לאפשר.

315
00:12:44,154 --> 00:12:47,320
ואולי זה קצת יותר מדי
מאשר ללכת עם אותיות אלף-בית,

316
00:12:47,320 --> 00:12:50,236
כי כמובן יש כנראה
יותר אנשים בעולם עם שמות

317
00:12:50,236 --> 00:12:54,020
התחלה כי עם יותר מבהחלט
כמה מכתבים אחרים של האלפבית.

318
00:12:54,020 --> 00:12:56,380
אז אולי זה קצת
אחיד יותר, בהנחה

319
00:12:56,380 --> 00:12:58,640
התפלגות אחידה
של תינוקות על פני חודש.

320
00:12:58,640 --> 00:12:59,990
>> אבל, כמובן, זה עדיין לא מושלם.

321
00:12:59,990 --> 00:13:00,370
נכון?

322
00:13:00,370 --> 00:13:01,370
אנו עורכים התנגשויות.

323
00:13:01,370 --> 00:13:04,680
אנשים רבים בזה
מבנה נתונים עדיין

324
00:13:04,680 --> 00:13:08,432
נתקל באותה התאריך הלידה של לפחות
אתה ללא קשר לחודש.

325
00:13:08,432 --> 00:13:09,640
אבל מה עשה המחבר?

326
00:13:09,640 --> 00:13:13,427
ובכן, זה נראה כאילו יש לנו מערך
בצד השמאל נמשך בצורה אנכית,

327
00:13:13,427 --> 00:13:15,010
אבל זה רק ביצוע של אמן.

328
00:13:15,010 --> 00:13:18,009
זה לא משנה מה כיוון שאתה
לצייר מערך, זה עדיין מערך.

329
00:13:18,009 --> 00:13:20,225
מה זה מערך של ככל הנראה?

330
00:13:20,225 --> 00:13:21,500
>> קהל: רשימה מקושרת.

331
00:13:21,500 --> 00:13:21,650
>> DAVID מלאן: כן.

332
00:13:21,650 --> 00:13:23,490
זה נראה כמו שזה
מערך של רשימה מקושרת.

333
00:13:23,490 --> 00:13:26,490
אז שוב, לנקודה מסוג זה
של שימוש במבני נתונים אלה עכשיו

334
00:13:26,490 --> 00:13:28,550
כמרכיבים ליותר
פתרונות מעניינים,

335
00:13:28,550 --> 00:13:30,862
אתה יכול בהחלט לקחת
בסיסי, כמו מערך,

336
00:13:30,862 --> 00:13:33,320
ולאחר מכן לקחת משהו יותר
מעניין כמו רשימה מקושרת

337
00:13:33,320 --> 00:13:36,660
ואפילו לשלב אותם לתוך אפילו
מבנה נתונים מעניין יותר.

338
00:13:36,660 --> 00:13:39,630
ואכן, זה היה יותר מדי
ייקרא טבלת חשיש,

339
00:13:39,630 --> 00:13:42,610
לפי המערך הוא
באמת שולחן החשיש,

340
00:13:42,610 --> 00:13:45,600
אבל יש שטבלת החשיש
שרשרות, אם אפשר לומר כך,

341
00:13:45,600 --> 00:13:50,220
שיכול לגדול או להתכווץ המבוסס על
מספר האלמנטים ברצונך להוסיף.

342
00:13:50,220 --> 00:13:52,990
>> עכשיו, בהתאם, מה
זמן הריצה עכשיו?

343
00:13:52,990 --> 00:13:58,030
אם אני רוצה להכניס מישהו
יום ההולדת שלו הוא יום 31 באוקטובר,

344
00:13:58,030 --> 00:13:59,040
שבו הוא או היא הולכת?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
בְּסֵדֶר.

347
00:14:01,030 --> 00:14:02,819
בתחתית מאוד שבו כתוב 31.

348
00:14:02,819 --> 00:14:03,610
וזה מושלם.

349
00:14:03,610 --> 00:14:05,060
זה היה זמן קבוע.

350
00:14:05,060 --> 00:14:08,760
אבל מה אם אנחנו מוצאים מישהו אחר
יום ההולדת שלו הוא, בואו נראה,

351
00:14:08,760 --> 00:14:10,950
אוקטובר, נובמבר, דצמבר 31?

352
00:14:10,950 --> 00:14:12,790
איפה הוא או היא הולכת?

353
00:14:12,790 --> 00:14:13,290
אותו דבר.

354
00:14:13,290 --> 00:14:13,970
שני שלבים אף.

355
00:14:13,970 --> 00:14:15,303
זה קבוע אם כי לא?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
בְּסֵדֶר.

358
00:14:16,860 --> 00:14:17,840
ברגע זה.

359
00:14:17,840 --> 00:14:20,570
אבל במקרה הכללי,
יותר אנשים נוסיף,

360
00:14:20,570 --> 00:14:23,790
הסתברותי, אנחנו הולכים
כדי לקבל יותר ויותר התנגשויות.

361
00:14:23,790 --> 00:14:26,820
>> עכשיו זה קצת
טוב יותר, כי מבחינה טכנית

362
00:14:26,820 --> 00:14:34,580
עכשיו הרשתות שלי יכולות להיות ב
במקרה הגרוע ביותר כמה זמן?

363
00:14:34,580 --> 00:14:38,890
אם אני מכניס n אנשים לזה יותר
מבנה נתונים מתוחכם, n אנשים,

364
00:14:38,890 --> 00:14:41,080
במקרה הגרוע ביותר זה הולך להיות n.

365
00:14:41,080 --> 00:14:41,815
למה?

366
00:14:41,815 --> 00:14:43,332
>> קהל: כי אם כולם
יש את אותו יום ההולדת,

367
00:14:43,332 --> 00:14:44,545
הם הולכים להיות בשורה אחת.

368
00:14:44,545 --> 00:14:45,420
DAVID מלאן: מושלם.

369
00:14:45,420 --> 00:14:47,480
זה עלול להיות קצת מאולץ,
אבל באמת במקרה הגרוע ביותר,

370
00:14:47,480 --> 00:14:50,117
אם לכולם יש את אותו יום הולדת,
בהתחשב בתשומות שיש לך,

371
00:14:50,117 --> 00:14:51,950
אתה הולך לי
שרשרת ארוכה בצורה מסיבית.

372
00:14:51,950 --> 00:14:54,241
וכך, אפשר לקרוא לזה
חשיש שולחן, אבל באמת זה

373
00:14:54,241 --> 00:14:56,810
רק רשימה מקושרת מסיבית עם
המון שטח מבוזבז.

374
00:14:56,810 --> 00:15:00,460
אבל באופן כללי, אם תניח ש
לפחות ימי הולדת הם uniform--

375
00:15:00,460 --> 00:15:01,750
וזה כנראה לא.

376
00:15:01,750 --> 00:15:02,587
אני ממציא את זה.

377
00:15:02,587 --> 00:15:04,420
אבל אם נניח, ל
לצורך דיון

378
00:15:04,420 --> 00:15:07,717
שהם, אז בתאוריה, אם
זה הייצוג האנכי

379
00:15:07,717 --> 00:15:11,050
של המערך, גם אז אני מקווה שאתה
הולך לקבל רשתות המהווים, אתה יודע,

380
00:15:11,050 --> 00:15:15,880
בערך באותו האורך שבו כל אחד מ
אלה מייצגים יום בחודש.

381
00:15:15,880 --> 00:15:19,930
>> עכשיו, אם יש 31 ימים בחודש,
זה אומר שזמן הריצה שלי באמת

382
00:15:19,930 --> 00:15:25,230
הוא O הגדול של n מעל 31, ש
מרגיש טוב יותר מאשר ליניארי.

383
00:15:25,230 --> 00:15:27,950
אבל מה שהיה אחד משלנו
התחייבויות שבועות

384
00:15:27,950 --> 00:15:31,145
לפני כל פעם שהוא בא לביטוי
זמן הריצה של אלגוריתם?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
רק מסתכל רק על טווח סדר הגבוה.

387
00:15:35,190 --> 00:15:35,690
נכון?

388
00:15:35,690 --> 00:15:37,400
ביום 31 בהוא בהחלט מועיל.

389
00:15:37,400 --> 00:15:39,610
אבל זה עדיין O הגדול של n.

390
00:15:39,610 --> 00:15:41,730
אבל אחד הנושאים
בעיה להגדיר חמש

391
00:15:41,730 --> 00:15:43,950
הולך להיות ל
להכיר בכך שבהחלט,

392
00:15:43,950 --> 00:15:47,320
אסימפטוטית, באופן תיאורטי
מבנה נתונים זה

393
00:15:47,320 --> 00:15:50,470
אינו טוב יותר מאשר רק
רשימה אחת מסיבית קשורה.

394
00:15:50,470 --> 00:15:53,550
ואכן, במקרה הגרוע ביותר, זה
טבלת חשיש עלולה להידרדר של.

395
00:15:53,550 --> 00:15:57,620
>> אבל בעולם האמיתי, איתנו בני אדם
כי מחשבי מקינטוש או מחשבים או מה ש

396
00:15:57,620 --> 00:16:01,240
ופועלים עולם אמיתי
תוכנה על נתונים בעולם אמיתיים,

397
00:16:01,240 --> 00:16:03,260
שאלגוריתם אתה הולך מעדיף?

398
00:16:03,260 --> 00:16:09,180
אחד שלוקח צעדי סוף או
אחד שלוקח מחולק n על ידי ביום 31 בצעדים

399
00:16:09,180 --> 00:16:12,900
למצוא פיסת מידע או
כדי לחפש מידע מסוים?

400
00:16:12,900 --> 00:16:16,580
אני מתכוון, בהחלט עושה ביום 31 ב
הבדל בעולם האמיתי.

401
00:16:16,580 --> 00:16:18,540
זה 31 פעמים מהר יותר.

402
00:16:18,540 --> 00:16:20,880
ואנו, בני אדם הם בהחלט
הולך מעריך את זה.

403
00:16:20,880 --> 00:16:23,004
>> אז מבין את הדיכוטומיה
יש בין למעשה

404
00:16:23,004 --> 00:16:25,920
מדבר על דברים באופן תיאורטי
ואסימפטוטית אשר בהחלט

405
00:16:25,920 --> 00:16:28,760
יש לו ערך כפי שראינו,
אבל בעולם האמיתי,

406
00:16:28,760 --> 00:16:32,930
אם אכפת לך רק עושה
שמח אדם לתשומות כלליות,

407
00:16:32,930 --> 00:16:36,010
ייתכן מאוד רוצה לקבל
העובדה ש, כן, זה הוא ליניארי,

408
00:16:36,010 --> 00:16:38,360
אבל זה 31 פעמים מהר יותר
מ ליניארי יכול להיות.

409
00:16:38,360 --> 00:16:41,610
וזה יותר טוב, אנחנו לא רק צריכים
לעשות משהו שרירותי כמו תאריך לידה,

410
00:16:41,610 --> 00:16:44,030
אנחנו יכולים להשקיע קצת
יותר זמן ופקחות

411
00:16:44,030 --> 00:16:47,140
ולחשוב על מה שאנחנו יכולים לעשות,
שמו של אדם נתון, ואולי

412
00:16:47,140 --> 00:16:50,130
תאריך הלידה שלהם לשלב אותם
מרכיבים להבין משהו

413
00:16:50,130 --> 00:16:52,720
כי הוא באמת יותר
אחיד ופחות jaggy,

414
00:16:52,720 --> 00:16:56,250
כביכול מאשר תמונה זו
מציע כיום זה יכול להיות.

415
00:16:56,250 --> 00:16:57,750
איך אנחנו יכולים ליישם את זה בקוד?

416
00:16:57,750 --> 00:17:00,280
ובכן, הרשה לי להציע לנו ש
רק לשאול כמה תחביר יש לנו

417
00:17:00,280 --> 00:17:01,799
משמש כמה פעמים עד כה.

418
00:17:01,799 --> 00:17:03,590
ואני הולך להגדיר
צומת, שבו שוב

419
00:17:03,590 --> 00:17:06,812
הוא מונח כללי לרק חלק
מיכל לכמה מבנה נתונים.

420
00:17:06,812 --> 00:17:09,020
אני הולך להציע ש
מחרוזת הולכת לשם.

421
00:17:09,020 --> 00:17:11,369
אבל אנחנו הולכים להתחיל לקחת
אלה גלגלי עזר מחברה.

422
00:17:11,369 --> 00:17:13,230
>> לא עוד ספריית CS50
באמת, אם אתה לא רוצה

423
00:17:13,230 --> 00:17:15,230
כדי להשתמש בו לסופי שלך
פרויקט, וזה בסדר,

424
00:17:15,230 --> 00:17:18,569
אבל עכשיו אנחנו הולכים למשוך בחזרה
וילון ואומרים שזה רק כוכב char.

425
00:17:18,569 --> 00:17:22,069
אז המילה שם הולך להיות
שמו של האדם בשאלה.

426
00:17:22,069 --> 00:17:25,079
ועכשיו יש לי קישור
כאן לקשר הבא

427
00:17:25,079 --> 00:17:28,170
כך שאלו מייצגים
כל אחד מצומת

428
00:17:28,170 --> 00:17:30,950
בשרשרת, שעלול להיות,
של רשימה מקושרת.

429
00:17:30,950 --> 00:17:34,090
>> ועכשיו, איך לעשות אני מצהיר
השולחן עצמו החשיש?

430
00:17:34,090 --> 00:17:36,660
איך אני מצהיר בכל המבנה הזה?

431
00:17:36,660 --> 00:17:40,960
ובכן, באמת, הרבה כמו פעם מצביע
רק האלמנט הראשון של רשימה

432
00:17:40,960 --> 00:17:44,510
לפני, באופן דומה אני יכול רק לומר
אני רק צריך חבורה של מצביעים

433
00:17:44,510 --> 00:17:46,270
ליישם טבלת חשיש כל זה.

434
00:17:46,270 --> 00:17:49,484
אני הולך יש לי מערך
שולחן קרא לטבלת חשיש.

435
00:17:49,484 --> 00:17:50,900
זה הולך להיות של קיבולת גודל.

436
00:17:50,900 --> 00:17:52,525
זה כמה אלמנטים יכול להתאים אותו.

437
00:17:52,525 --> 00:17:56,180
וכל אחד מאותם יסודות בזה
מערך הוא הולך להיות כוכב צומת.

438
00:17:56,180 --> 00:17:56,810
למה?

439
00:17:56,810 --> 00:18:00,160
ובכן, לכל התמונה הזאת, מה שאני
יישום שולחן החשיש כ

440
00:18:00,160 --> 00:18:04,330
ביעילות בהתחלה היא רק
המערך הזה שאנחנו נמשכים בצורה אנכית,

441
00:18:04,330 --> 00:18:06,820
כל אחד מריבועים ש
מייצג מצביע.

442
00:18:06,820 --> 00:18:09,170
כי שיש להן קווים נטויים
דרכם הם רק null.

443
00:18:09,170 --> 00:18:11,410
ושיש להן
חיצים הולכים ימינה

444
00:18:11,410 --> 00:18:16,140
הם מצביעים בפועל לבלוטות בפועל,
ergo תחילת רשימה מקושרת.

445
00:18:16,140 --> 00:18:19,050
>> אז הנה, אם כן, הוא כיצד אוכל
ליישם טבלת חשיש ש

446
00:18:19,050 --> 00:18:21,580
מיישם שרשור נפרד.

447
00:18:21,580 --> 00:18:22,840
עכשיו אנחנו יכולים לעשות טובים יותר?

448
00:18:22,840 --> 00:18:25,632
בסדר הבטחתי פעם האחרונה ש
אנחנו יכולים להשיג בזמן קבוע.

449
00:18:25,632 --> 00:18:27,381
ואני סוג של נתתי לך
זמן קבוע כאן,

450
00:18:27,381 --> 00:18:29,850
אבל אז אמר לא ממש
זמן קבוע כי זה עדיין

451
00:18:29,850 --> 00:18:31,890
תלוי בסך הכל
מספר האלמנטים

452
00:18:31,890 --> 00:18:34,500
אתה מזין ל
מבנה הנתונים.

453
00:18:34,500 --> 00:18:35,980
אבל נניח שעשינו את זה.

454
00:18:35,980 --> 00:18:39,550
תן לי לחזור למסך כאן.

455
00:18:39,550 --> 00:18:44,520
תן לי גם להקרין את זה כאן, ברור
המסך, ומניח שעשיתי את זה.

456
00:18:44,520 --> 00:18:49,300
נניח שאני רוצה להכניס את שמו
להתפלל למבנה הנתונים שלי.

457
00:18:49,300 --> 00:18:52,100
>> אז אני רוצה להכניס מחרוזת
דייבן אל את מבנה הנתונים.

458
00:18:52,100 --> 00:18:54,370
מה אם אני לא משתמש ב
חשיש שולחן, אבל אני משתמש ב

459
00:18:54,370 --> 00:18:56,980
משהו שהוא יותר עצים כמו
כמו עץ ​​משפחה, שבו

460
00:18:56,980 --> 00:18:59,670
יש לך כמה שורש ב
צמתים ועלים העליונים ולאחר מכן

461
00:18:59,670 --> 00:19:01,440
שתלך כלפי מטה וכלפי חוץ.

462
00:19:01,440 --> 00:19:04,450
נניח שלאחר מכן, אני ש
רוצה להכניס דייבן

463
00:19:04,450 --> 00:19:06,430
למה שכרגע רשימה ריקה.

464
00:19:06,430 --> 00:19:09,780
אני הולך לבצע את הפעולות הבאות: אני
הולך ליצור צומת במשפחה זו

465
00:19:09,780 --> 00:19:15,170
עץ-כמו מבנה נתונים שנראה
קצת כמו זה, כל אחד מהם

466
00:19:15,170 --> 00:19:19,640
מלבנים יש, נניח,
לעת עתה 26 אלמנטים בזה.

467
00:19:19,640 --> 00:19:21,650
וכל אחד מהתאים
במערך זה הולך

468
00:19:21,650 --> 00:19:23,470
לייצג את המכתב של האלפבית.

469
00:19:23,470 --> 00:19:28,190
>> באופן ספציפי, אני הולך לטיפול
זה, אז B, ואז C, אז D,

470
00:19:28,190 --> 00:19:29,310
זה כאן.

471
00:19:29,310 --> 00:19:32,940
אז זה הולך בצורה יעילה
מייצג את המכתב ד

472
00:19:32,940 --> 00:19:36,040
אבל להכניס את כל דייבן
שם אני צריך לעשות קצת יותר.

473
00:19:36,040 --> 00:19:37,840
אז קודם כל אני הולך חשיש, אם אפשר לומר כך.

474
00:19:37,840 --> 00:19:41,049
אני הולך להסתכל על האות הראשונה
בדייבן אשר ללא ספק D,

475
00:19:41,049 --> 00:19:42,840
ואני הולך להקצות
צומת שנראית

476
00:19:42,840 --> 00:19:45,570
כמו זה-- מלבן גדול גדול
מספיק כדי להתאים את כל האלפבית.

477
00:19:45,570 --> 00:19:47,140
>> עכשיו D נעשה.

478
00:19:47,140 --> 00:19:49,720
עכשיו א 'D-A-V-E-N הוא המטרה.

479
00:19:49,720 --> 00:19:51,220
אז עכשיו מה שאני הולך לעשות הוא זה.

480
00:19:51,220 --> 00:19:54,027
ברגע שהתחלתי הודעת D
אין מצביע יש.

481
00:19:54,027 --> 00:19:56,860
זה ערכי זבל ברגע,
או שאני יכול לאתחל אותו לאפס.

482
00:19:56,860 --> 00:19:59,630
אבל תן לי להמשיך עם
הרעיון הזה של בניית עץ.

483
00:19:59,630 --> 00:20:04,260
תן לי להקצות עוד אחד מאלה
צמתים שיש 26 אלמנטים בזה.

484
00:20:04,260 --> 00:20:05,150
>> ואתם יודעים מה?

485
00:20:05,150 --> 00:20:09,130
אם זה רק צומת בזיכרון ש
אני יצרתי עם malloc, באמצעות struct

486
00:20:09,130 --> 00:20:11,240
כפי שאנו תראו בקרוב,
אני הולך לעשות זה--

487
00:20:11,240 --> 00:20:14,450
אני הולך לצייר חץ מ
הדבר שייצג D למטה

488
00:20:14,450 --> 00:20:15,860
לצומת חדשה זה.

489
00:20:15,860 --> 00:20:19,240
ועכשיו, ראשון הבא
מכתב בשמו של דייבן,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- אני הולך קדימה
ולצייר צומת אחר כך,

491
00:20:24,150 --> 00:20:30,150
לפי, אלמנטי V כאן, ש
אנחנו עושים הגרלה אופס instance--.

492
00:20:30,150 --> 00:20:31,020
אנחנו לא נמשוך לשם.

493
00:20:31,020 --> 00:20:31,936
זה הולך כאן.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> ואז אנחנו הולכים ל
לשקול את זה כדי להיות V.

496
00:20:35,712 --> 00:20:44,920
ואז כאן אנחנו הולכים מדד
למטה מ V למה שאנו רואים א

497
00:20:44,920 --> 00:20:50,100
ואז מכאן אנחנו הולכים
ללכת יש לי אחת של בלוטות אלה כאן.

498
00:20:50,100 --> 00:20:52,930
ועכשיו יש לנו לענות על שאלה.

499
00:20:52,930 --> 00:20:57,840
אני צריך איכשהו מצביע על כך ש
אנחנו בסוף המחרוזת בדייבן.

500
00:20:57,840 --> 00:20:59,490
אז אני יכול פשוט להשאיר אותו ריק.

501
00:20:59,490 --> 00:21:02,670
>> אבל מה אם יש לי דייבן
שמו מלא גם, ש

502
00:21:02,670 --> 00:21:04,280
הוא, כפי שאמרנו, דבנפורט?

503
00:21:04,280 --> 00:21:06,970
אז מה אם להתפלל הוא
למעשה מחרוזת,

504
00:21:06,970 --> 00:21:08,960
קידומת של מחרוזת ארוכה יותר?

505
00:21:08,960 --> 00:21:11,450
אנחנו לא יכולים סתם באופן קבוע
אומר שום דבר לא הולך

506
00:21:11,450 --> 00:21:14,410
ללכת לשם, כי אנחנו יכולים
לעולם אל תכניס מילה כמו דבנפורט

507
00:21:14,410 --> 00:21:15,840
למבנה נתונים זה

508
00:21:15,840 --> 00:21:19,560
>> אז מה אנחנו יכולים לעשות במקום הוא
טיפול בכל אחד מהאלמנטים האלה

509
00:21:19,560 --> 00:21:22,170
כאולי יש שני
אלמנטים בתוכם.

510
00:21:22,170 --> 00:21:24,810
אחד הוא מצביע, אכן,
כמו שאני כבר עושה.

511
00:21:24,810 --> 00:21:27,100
אז כל אחד מהתיבות הללו
לא רק תא אחד.

512
00:21:27,100 --> 00:21:29,855
אבל מה אם החלק העליון
one-- התחתון של אחד

513
00:21:29,855 --> 00:21:32,230
הולך להיות null, כי
אין דבנפורט עדיין.

514
00:21:32,230 --> 00:21:34,197
מה אם ראש אחד
איזה ערך מיוחד?

515
00:21:34,197 --> 00:21:36,530
וזה הולך להיות קצת
קשה לצייר אותו בגודל זה.

516
00:21:36,530 --> 00:21:38,130
אבל נניח שזה רק סימן ביקורת.

517
00:21:38,130 --> 00:21:38,920
בדוק.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N הוא מחרוזת
במבנה נתונים זה.

519
00:21:44,230 --> 00:21:48,350
>> בינתיים, אם יש לי יותר מקום
כאן, אני יכול לעשות את P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
ואני יכול לשים את הסימון בצומת
שיש לו את האות T בסוף מאוד.

521
00:21:52,650 --> 00:21:55,460
אז זה בצורה מסיבית
מבנה נתונים למראה מורכב.

522
00:21:55,460 --> 00:21:57,210
וכתב היד שלי
בהחלט לא עוזר.

523
00:21:57,210 --> 00:22:00,043
אבל אם אני רוצה להכניס משהו
אחר, לשקול מה היינו עושה.

524
00:22:00,043 --> 00:22:03,370
אם אנחנו רוצים לשים דוד ב,
היינו לעקוב אחר אותו ההיגיון, D--V,

525
00:22:03,370 --> 00:22:08,802
אבל עכשיו הייתי נקודה בעולם הבא
אלמנט לא מE, אבל מאני לד

526
00:22:08,802 --> 00:22:10,760
אז יש הולך להיות
יותר צמתים בעץ הזה.

527
00:22:10,760 --> 00:22:12,325
אנחנו הולכים להיות שיחת malloc יותר.

528
00:22:12,325 --> 00:22:14,700
אבל אני לא רוצה לעשות
בלגן שלם של תמונה זו.

529
00:22:14,700 --> 00:22:17,710
אז בואו במקום להסתכל אחד
זה כבר נסח מראש

530
00:22:17,710 --> 00:22:21,810
כמו זה עם לא נקודה, נקודה,
נקודות, אבל מערכים רק מקוצרים.

531
00:22:21,810 --> 00:22:23,950
אבל כל אחד מצומת
בעץ את זה כאן

532
00:22:23,950 --> 00:22:26,700
מייצג את אותו thing--
מערך ריי בגודל 26.

533
00:22:26,700 --> 00:22:28,860
>> או אם אנחנו רוצים להיות
באמת נכון עכשיו, מה

534
00:22:28,860 --> 00:22:30,790
אם שמו של מישהו כ
גרש, בוא

535
00:22:30,790 --> 00:22:35,560
תניח כי כל צומת בעצם יש
כמו 27 אינדקסים בזה, לא רק 26.

536
00:22:35,560 --> 00:22:42,020
אז זה עכשיו הולך להיות נתונים
מבנה נקרא T-R-אני-E trie--.

537
00:22:42,020 --> 00:22:46,120
לבלבים, שהוא כביכול
מבחינה היסטורית שם חכם לעץ

538
00:22:46,120 --> 00:22:49,040
זה מותאם במיוחד ל
אחזור, שכמובן,

539
00:22:49,040 --> 00:22:50,870
מאוית עם I-E כך שזה לבלבים.

540
00:22:50,870 --> 00:22:52,710
אבל זה ההיסטוריה של הלבלבים.

541
00:22:52,710 --> 00:22:55,860
>> אז לבלבים הוא נתוני עץ דמוי זה
מבנה דמוי עץ משפחה

542
00:22:55,860 --> 00:22:57,510
שמתנהג סופו של דבר כמו ש.

543
00:22:57,510 --> 00:23:00,890
וכאן הוא רק דוגמא נוספת ל
כל חבורה של השמות של אנשים אחרים.

544
00:23:00,890 --> 00:23:03,540
אבל השאלה עכשיו
ביד היא מה שיש לי

545
00:23:03,540 --> 00:23:08,070
אנו שנרכשו על ידי החדרת לטעון יותר
מבנה מסובך נתונים, ואחד,

546
00:23:08,070 --> 00:23:09,870
בכנות, שמשתמש בהרבה זיכרון.

547
00:23:09,870 --> 00:23:11,703
>> כי למרות ש,
באותו הרגע, אני רק

548
00:23:11,703 --> 00:23:15,050
באמצעות המצביע של D'ו
וV וEs וNS,

549
00:23:15,050 --> 00:23:16,700
אני מבזבז את לעזאזל של הרבה זיכרון.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
אבל איפה אני מבלה משאב אחד,
אני נוטה לעשות לקבל בחזרה אחר.

552
00:23:22,660 --> 00:23:26,020
אז אם אני מבלה יותר מרחב,
מה כנראה התקווה?

553
00:23:26,020 --> 00:23:27,407
שאני מבלה פחות מה?

554
00:23:27,407 --> 00:23:28,240
קהל: פחות זמן.

555
00:23:28,240 --> 00:23:28,990
DAVID מלאן: זמן.

556
00:23:28,990 --> 00:23:30,320
עכשיו למה שעשוי להיות?

557
00:23:30,320 --> 00:23:33,880
ובכן, מה היא ההכנסה
זמן, במונחים של O הגדול עכשיו,

558
00:23:33,880 --> 00:23:37,660
של שם כמו בדייבן
או דבנפורט או דוד?

559
00:23:37,660 --> 00:23:39,340
ובכן, דייבן היה חמישה שלבים.

560
00:23:39,340 --> 00:23:42,350
דבנפורט יהיה תשעה שלבים,
כך שזה יהיה עוד כמה צעדים.

561
00:23:42,350 --> 00:23:44,250
דוד יהיה חמישה שלבים, כמו גם.

562
00:23:44,250 --> 00:23:47,230
אז אלה הם בטון
מספרים, אבל אין ספק שיש

563
00:23:47,230 --> 00:23:49,550
גבול עליון ל
אורכו של שמו של מישהו.

564
00:23:49,550 --> 00:23:52,240
ואכן, בבעיה
סטים של חמישה מפרט,

565
00:23:52,240 --> 00:23:54,050
אנחנו הולכים להציע
שזה משהו

566
00:23:54,050 --> 00:23:55,470
זה תווים 40-ומשהו.

567
00:23:55,470 --> 00:23:58,180
>> באופן מעשי, אין לאף אחד
שם ארוך לאין שיעור,

568
00:23:58,180 --> 00:24:01,542
כלומר שאורכו של
שם או האורך של מחרוזת שאולי

569
00:24:01,542 --> 00:24:03,750
יש לי מסוים המדינה
מבנה הוא לטעון מה?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
זה קבוע.

572
00:24:06,250 --> 00:24:06,430
נכון?

573
00:24:06,430 --> 00:24:09,310
זה יכול להיות קבוע גדול כמו
40 ומשהו, אבל זה קבוע.

574
00:24:09,310 --> 00:24:13,752
ואין לה תלות בכמה
שמות אחרים הם במבנה נתונים זה.

575
00:24:13,752 --> 00:24:15,460
במילים אחרות, אם אני
רציתי להכניס עכשיו

576
00:24:15,460 --> 00:24:20,540
קולטון או גבריאל או רוב או Zamyla או
אליסון או בלינדה או כל שמות אחרים

577
00:24:20,540 --> 00:24:23,940
מהצוות לנתונים זה
מבנה, הוא זמן הריצה

578
00:24:23,940 --> 00:24:26,750
החדרה של שמות אחרים
הולך להיות בכל השפיע

579
00:24:26,750 --> 00:24:30,220
על ידי כמה גורמים אחרים
במבנה נתונים כבר?

580
00:24:30,220 --> 00:24:31,040
זה לא.

581
00:24:31,040 --> 00:24:31,540
נכון?

582
00:24:31,540 --> 00:24:36,150
מכיוון שאנחנו משתמשים באופן יעיל
טבלת חשיש רב שכבתית זו.

583
00:24:36,150 --> 00:24:38,280
וזמן הריצה של
כל הפעולות הללו

584
00:24:38,280 --> 00:24:41,510
תלויה לא במספר
אלמנטים שנמצאים במבנה נתונים

585
00:24:41,510 --> 00:24:43,090
או שסופו של דבר הולך
להיות במבנה נתונים,

586
00:24:43,090 --> 00:24:44,714
אבל באורך של מה באופן ספציפי?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> להיות המחרוזת
הוכנס, שהופך אותה

589
00:24:49,200 --> 00:24:52,580
זה אסימפטוטית קבועה
O הגדול time-- של אחד.

590
00:24:52,580 --> 00:24:54,720
ולמען אמת, רק ב
העולם האמיתי, זה

591
00:24:54,720 --> 00:24:58,380
משמעות הדבר היא הכנסה שם של דייבן לוקח
כמו חמישה שלבים, או דבנפורט תשע

592
00:24:58,380 --> 00:25:00,100
צעדים, או דוד חמישה צעדים.

593
00:25:00,100 --> 00:25:03,071
זה לא רע בכלל פעמים ריצה קטנות.

594
00:25:03,071 --> 00:25:05,320
ואכן, זה מאוד
דבר טוב, במיוחד כאשר

595
00:25:05,320 --> 00:25:08,126
זה לא תלוי בסך
מספר האלמנטים שביש.

596
00:25:08,126 --> 00:25:10,500
אז איך אנחנו יכולים ליישם את זה
סוג של מבנה בקוד?

597
00:25:10,500 --> 00:25:12,900
זה קצת יותר
מורכב, אבל עדיין זה

598
00:25:12,900 --> 00:25:15,050
רק יישום של
אבני בניין בסיסי.

599
00:25:15,050 --> 00:25:17,830
אני הולך להגדיר מחדש
צומתנו כדלקמן:

600
00:25:17,830 --> 00:25:21,100
bool נקרא word-- וזה
אפשר לקרוא לכל דבר.

601
00:25:21,100 --> 00:25:23,970
אבל בול מייצג
מה ציירתי כסימן ביקורת.

602
00:25:23,970 --> 00:25:24,490
כן.

603
00:25:24,490 --> 00:25:26,720
זה קצה חוט
במבנה נתונים זה.

604
00:25:26,720 --> 00:25:30,702
>> וגם, כמובן, את כוכב הצומת
יש המתייחס לילדים.

605
00:25:30,702 --> 00:25:32,410
ואכן, בדיוק כמו
עץ משפחה, אתה

606
00:25:32,410 --> 00:25:34,370
תשקול את צמתים
המשתלשלים מ

607
00:25:34,370 --> 00:25:36,920
של החלק התחתון של כמה הורים
אלמנט להיות ילדים.

608
00:25:36,920 --> 00:25:40,510
וכדי שהילדים הולכים ל
להיות מערך של 27, 27 אחד

609
00:25:40,510 --> 00:25:41,680
פשוט להיות לגרש.

610
00:25:41,680 --> 00:25:43,390
אנחנו הולכים כדי למיין
של מקרה מיוחד ש.

611
00:25:43,390 --> 00:25:45,400
אז אתה יכול לקבל מסוים
שמות עם גרשיים.

612
00:25:45,400 --> 00:25:47,399
אולי אפילו מקף צריך
להיכנס לשם, אבל אתה

613
00:25:47,399 --> 00:25:50,330
לראות בסט עמ '5 רק טיפול ש
על מכתבים וגרשיים.

614
00:25:50,330 --> 00:25:52,990
>> ואז איך שאתה מייצג
המבנה עצמו נתונים?

615
00:25:52,990 --> 00:25:56,454
איך אתה מייצג את השורש
של לבלבים זה, אם אפשר לומר כך?

616
00:25:56,454 --> 00:25:59,620
ובכן, בדיוק כמו עם רשימה מקושרת, אתה
צריך מצביע לאלמנט הראשון.

617
00:25:59,620 --> 00:26:04,270
עם לבלבים אתה רק צריך אחד
מצביע לשורש של לבלבים זה.

618
00:26:04,270 --> 00:26:07,290
ומשם אתה יכול חשיש
את הדרך למטה עמוק יותר ויותר

619
00:26:07,290 --> 00:26:10,460
לכל צומת אחר במבנה.

620
00:26:10,460 --> 00:26:13,440
אז פשוט עם הפח הזה
אנו מייצגים struct ש.

621
00:26:13,440 --> 00:26:15,877
>> עכשיו Meanwhile-- אה, שאלה.

622
00:26:15,877 --> 00:26:17,220
>> קהל: מה מילה בול?

623
00:26:17,220 --> 00:26:20,490
>> DAVID מלאן: מילה בול היא
רק גלגול C זה

624
00:26:20,490 --> 00:26:22,920
של מה שתארתי
בתיבה זו כאן, כאשר

625
00:26:22,920 --> 00:26:26,000
התחלתי פיצול כל אחד מ
האלמנטים של המערך לשני חלקים.

626
00:26:26,000 --> 00:26:27,600
אחד הוא מצביע לצומת הבאה.

627
00:26:27,600 --> 00:26:30,280
האחרים צריך להיות
משהו כמו תיבת סימון

628
00:26:30,280 --> 00:26:33,770
לומר כן, יש
מילה להתפלל כי מסתיימת כאן,

629
00:26:33,770 --> 00:26:35,610
בגלל שאנחנו לא רוצים,
באותו הרגע, דייב.

630
00:26:35,610 --> 00:26:39,320
>> למרות שדייב הולך להיות
מילה לגיטימית, הוא לא בלבלבים

631
00:26:39,320 --> 00:26:39,830
עדיין.

632
00:26:39,830 --> 00:26:40,950
ו- D הוא לא מילה.

633
00:26:40,950 --> 00:26:42,770
ו- D-הוא לא מילה או שם.

634
00:26:42,770 --> 00:26:45,020
אז את הסימון
מצביע רק פעם אחת אתה

635
00:26:45,020 --> 00:26:48,190
פגע צומת זה
הדרך קודמת של תווים

636
00:26:48,190 --> 00:26:50,700
למעשה מחרוזת שהוספת.

637
00:26:50,700 --> 00:26:53,660
אז זה כל מה bool
יש עושה לנו.

638
00:26:53,660 --> 00:26:55,500
>> שאלות אחרות על ניסיונות?

639
00:26:55,500 --> 00:26:56,215
כן.

640
00:26:56,215 --> 00:26:58,035
>> קהל: מהו החפיפה?

641
00:26:58,035 --> 00:26:59,945
מה אם יש לך דייב ולהתפלל?

642
00:26:59,945 --> 00:27:00,820
DAVID מלאן: מושלם.

643
00:27:00,820 --> 00:27:02,580
מה אם יש לך דייב ולהתפלל?

644
00:27:02,580 --> 00:27:06,240
אז אם אנחנו מכניסים, אומרים כינוי,
לDavid-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
זהו למעשה סופר פשוט.

647
00:27:08,700 --> 00:27:10,325
אז אנחנו הולכים רק לקחת ארבעה שלבים.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. ומה אני צריך לעשות כדי
לעשות ברגע שאני מכה שהצומת הרביעית?

650
00:27:15,847 --> 00:27:16,680
רק הולך לבדוק.

651
00:27:16,680 --> 00:27:18,000
אנחנו כבר טובים ללכת.

652
00:27:18,000 --> 00:27:18,840
עשה.

653
00:27:18,840 --> 00:27:19,750
ארבעה שלבים.

654
00:27:19,750 --> 00:27:21,590
זמן קבוע אסימפטוטית.

655
00:27:21,590 --> 00:27:26,300
ועכשיו אנחנו כבר הצביעו על כך שגם דייב
ואתפלל הן מחרוזות במבנה.

656
00:27:26,300 --> 00:27:27,710
אז לא בעיה.

657
00:27:27,710 --> 00:27:30,200
ושים לב כמה הנוכחות
של דייבן את לא עושה את זה

658
00:27:30,200 --> 00:27:34,750
לקחת כל זמן פחות או יותר
זמן לדייב ולהיפך.

659
00:27:34,750 --> 00:27:36,000
>> אז מה עוד אנחנו יכולים עכשיו לעשות?

660
00:27:36,000 --> 00:27:40,680
אנחנו השתמשנו במטאפורה זו לפני
של מגשים מייצגים משהו.

661
00:27:40,680 --> 00:27:43,380
אבל מתברר ש
ערימה של מגשים היא למעשה

662
00:27:43,380 --> 00:27:47,187
הפגנתי של עוד נתונים מופשטים
type-- מבנה נתונים ברמה גבוה יותר

663
00:27:47,187 --> 00:27:49,770
כי בסוף היום הוא רק
כמו מערך או רשימה מקושרת

664
00:27:49,770 --> 00:27:50,970
או משהו ארצי יותר.

665
00:27:50,970 --> 00:27:53,270
אבל זה יותר מעניין
מושג רעיוני.

666
00:27:53,270 --> 00:27:56,440
ערימה, כמו אלה
מגשים כאן בMather,

667
00:27:56,440 --> 00:27:58,750
בדרך כלל נקראים
רק that-- ערימה.

668
00:27:58,750 --> 00:28:02,540
>> וזה סוג של מבנה נתונים
יש לך שתי operations--

669
00:28:02,540 --> 00:28:05,880
יש לך דחיפה בשם אחד ל
הוספת משהו לערימה,

670
00:28:05,880 --> 00:28:08,320
כמו לשים מגש אחר
לאחור בחלק העליון של הערימה.

671
00:28:08,320 --> 00:28:11,350
ואז צץ, מה שאומר ש
לקחת את המגש העליון.

672
00:28:11,350 --> 00:28:16,210
אבל מה מפתח על ערימה היא ש
יש לו המאפיין המוזר הזה.

673
00:28:16,210 --> 00:28:19,560
כצוות חדר האוכל הם
ארגון מחדש של המגשים לארוחה הבאה,

674
00:28:19,560 --> 00:28:21,380
מה הולך להיות
אמיתי על איך תלמידים

675
00:28:21,380 --> 00:28:22,856
אינטראקציה עם מבנה נתונים זה?

676
00:28:22,856 --> 00:28:24,480
קהל: הם הולכים להתפוצץ אחד.

677
00:28:24,480 --> 00:28:26,550
DAVID מלאן: הם הולכים
להסתלק אחד, אני מקווה שהראש.

678
00:28:26,550 --> 00:28:28,910
אחרת זה פשוט סוג של טיפשים
ללכת כל הדרך עד לתחתית.

679
00:28:28,910 --> 00:28:29,070
נכון?

680
00:28:29,070 --> 00:28:31,620
מבנה נתונים לא ממש מאפשר
לך לתפוס את המגש התחתון לפחות

681
00:28:31,620 --> 00:28:32,520
בקלות.

682
00:28:32,520 --> 00:28:35,040
אז יש את זה סקרן
רכוש לערימה

683
00:28:35,040 --> 00:28:39,730
כי בסעיף האחרון הוא
הולך להיות את זו.

684
00:28:39,730 --> 00:28:43,400
ומדעני מחשב קוראים
זה LIFO-- יימשך נכנס, ראשון יוצא.

685
00:28:43,400 --> 00:28:45,540
וזה דווקא יש לי
יישומים מעניינים.

686
00:28:45,540 --> 00:28:50,090
זה לא בהכרח ברור כמו כמה
אחרים, אבל זה יכול, אכן, להיות שימושי,

687
00:28:50,090 --> 00:28:54,040
ויכול, אכן, להוציאה לפועל
בכמה דרכים שונות.

688
00:28:54,040 --> 00:28:58,550
>> אז אחת, ולמעשה, תן לי
לי לא לצלול לתוך זה.

689
00:28:58,550 --> 00:28:59,860
בואו נעשה את זה במקום.

690
00:28:59,860 --> 00:29:03,700
בואו נסתכל על אחד שכמעט
אותו רעיון, אבל זה קצת יותר הוגן.

691
00:29:03,700 --> 00:29:04,200
נכון?

692
00:29:04,200 --> 00:29:07,560
אם אתה אחד מבני אוהד אלה או
בנות שבאמת אוהבת את המוצרים של אפל

693
00:29:07,560 --> 00:29:10,130
והתעוררת שעה 3:00 לפנות הבוקר
בשורה בחנות כלשהי

694
00:29:10,130 --> 00:29:14,150
כדי לקבל את iPhone החדש ביותר, אתה
אולי עמד בתור כזה.

695
00:29:14,150 --> 00:29:15,800
>> עכשיו תור שמו נקרא מאוד במכוון.

696
00:29:15,800 --> 00:29:18,190
זה קו כי יש
כמה הגינות לזה.

697
00:29:18,190 --> 00:29:18,690
נכון?

698
00:29:18,690 --> 00:29:21,690
זה היה נשאב סוג של אם יש לך
הגעתי לשם ראשון בחנות אפל

699
00:29:21,690 --> 00:29:25,700
אבל אתה ביעילות התחתונה
מגש, שכן עובדי אפל

700
00:29:25,700 --> 00:29:28,189
פופ האדם האחרון ש
למעשה יש בשורה.

701
00:29:28,189 --> 00:29:31,230
אז ערימות ותורים, למרות ש
פונקציונלי הוא סוג של same--

702
00:29:31,230 --> 00:29:33,105
זה פשוט אוסף זה
משאבים זה

703
00:29:33,105 --> 00:29:36,210
הולך לגדול וshrink-- יש
היבט הגינות זה לזה,

704
00:29:36,210 --> 00:29:39,634
לפחות בעולם האמיתי,
שבו פעולותיך לממש

705
00:29:39,634 --> 00:29:40,800
שונים באופן מהותי.

706
00:29:40,800 --> 00:29:43,360
Stack-- תור
rather-- הוא אמר לי

707
00:29:43,360 --> 00:29:45,320
שתי פעולות: תור n ותור ד.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
או שאתה יכול לקרוא להם
כל מספר של דברים.

710
00:29:48,090 --> 00:29:50,770
אבל אתה רק רוצה ללכוד
הרעיון שהאדם הוא הוספה

711
00:29:50,770 --> 00:29:53,230
ואחד סופו של דבר הפחתה.

712
00:29:53,230 --> 00:29:58,840
>> עכשיו מתחת למכסה המנוע, שתי הערימה
ויכול להיות מיושם תור איך?

713
00:29:58,840 --> 00:30:01,390
אנחנו לא נכנסנו לקוד של
זה בגלל שהרמה גבוהה יותר

714
00:30:01,390 --> 00:30:03,387
רעיון הוא סוג של יותר ברור.

715
00:30:03,387 --> 00:30:04,470
אני מתכוון, מה שבני האדם עושים?

716
00:30:04,470 --> 00:30:07,030
אם אני האדם הראשון באפל
אחסן וזה בדלת הקדמית,

717
00:30:07,030 --> 00:30:08,130
אתה יודע, אני הולך לעמוד כאן.

718
00:30:08,130 --> 00:30:09,750
ושל האדם הבא
הולך לעמוד כאן.

719
00:30:09,750 --> 00:30:11,500
ושל האדם הבא
הולך לעמוד כאן.

720
00:30:11,500 --> 00:30:13,792
אז מה מבנה נתונים
משאיל את עצמו לתור?

721
00:30:13,792 --> 00:30:14,542
>> קהל: תור.

722
00:30:14,542 --> 00:30:15,667
DAVID מלאן: טוב, תור.

723
00:30:15,667 --> 00:30:16,390
בטח.

724
00:30:16,390 --> 00:30:16,920
מה עוד?

725
00:30:16,920 --> 00:30:17,600
>> קהל: רשימה מקושרת.

726
00:30:17,600 --> 00:30:18,990
>> DAVID מלאן: מקושר
רשימה שאתה יכול ליישם.

727
00:30:18,990 --> 00:30:22,500
ורשימה מקושרת היא נחמדה, כי אז
זה יכול לגדול באופן שרירותי ארוך בניגוד

728
00:30:22,500 --> 00:30:24,880
שיש מספר קבוע כלשהו
של אנשים בחנות.

729
00:30:24,880 --> 00:30:27,030
אבל אולי מספר קבוע
מקומות הוא לגיטימי.

730
00:30:27,030 --> 00:30:30,350
כי אם יש להם רק כמו 20
מכשירי iPhone ביום הראשון, אולי

731
00:30:30,350 --> 00:30:33,930
הם צריכים מערך של גודל רק
20 לייצג תור ש, ש

732
00:30:33,930 --> 00:30:37,070
הוא רק אומר עכשיו ברגע שאנחנו מתחילים לדבר
בעיות ברמה גבוהות אלה על,

733
00:30:37,070 --> 00:30:38,890
אתה יכול ליישם את זה
בכל מספר הדרכים.

734
00:30:38,890 --> 00:30:42,030
ויש כנראה רק הולך
להיות את מסחר במרחב ובזמן

735
00:30:42,030 --> 00:30:43,950
או רק במורכבות קוד משלך.

736
00:30:43,950 --> 00:30:45,380
>> מה לגבי ערימה?

737
00:30:45,380 --> 00:30:48,190
ובכן, ערימה, שראינו יותר מדי
יכול להיות רק מגשים אלה.

738
00:30:48,190 --> 00:30:50,007
ואתה יכול ליישם את זה מערך.

739
00:30:50,007 --> 00:30:53,090
אבל בשלב מסוים אם אתה משתמש במערך,
מה יקרה למגשים

740
00:30:53,090 --> 00:30:54,173
אתה מנסה לשים למטה?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
בְּסֵדֶר.

743
00:30:55,670 --> 00:30:57,490
אתה הולך רק ל
להיות מסוגל ללכת כל כך גבוה.

744
00:30:57,490 --> 00:31:00,156
ואני חושב בMather הם
למעשה שקוע בפתיחה ש.

745
00:31:00,156 --> 00:31:01,950
אז אכן, זה כמעט
כמו Mather משתמש

746
00:31:01,950 --> 00:31:03,783
מערך של גודל קבוע,
כי רק אתה יכול

747
00:31:03,783 --> 00:31:08,302
להתאים מגשים כל כך הרבה בפתיחה שב
הקיר למטה ברכיים של אנשים.

748
00:31:08,302 --> 00:31:10,010
וכך זה יכול להיות
אמר לי להיות מערך,

749
00:31:10,010 --> 00:31:14,300
אבל אנחנו בהחלט יכולים ליישם את זה
באופן כללי יותר עם רשימה מקושרת.

750
00:31:14,300 --> 00:31:16,390
>> ובכן, מה לגבי מבנה נתונים אחר?

751
00:31:16,390 --> 00:31:18,760
תן לי להרים את אחד אחר חזותי כאן.

752
00:31:18,760 --> 00:31:24,710
משהו כמו מה דעתך על זה כאן?

753
00:31:24,710 --> 00:31:28,920
למה שזה עשוי להיות שימושי יש לא
משהו מפואר כמו לבלבים, ש

754
00:31:28,920 --> 00:31:32,370
ראיתי שיש לנו צמתים רחבים מאוד אלה,
כל אחד מהם הוא במערך?

755
00:31:32,370 --> 00:31:35,740
אבל מה אם אנחנו עושים משהו יותר
פשוט, כמו עץ ​​משפחה בבית הספר ישן,

756
00:31:35,740 --> 00:31:38,110
כל אחד מצומת שכאן
רק אחסון מספר.

757
00:31:38,110 --> 00:31:42,180
במקום בשם או צאצא
רק אחסון מספר כזה.

758
00:31:42,180 --> 00:31:45,250
>> ובכן, בז'רגון אנו משתמשים ב
מבני נתונים הוא שני הניסיונות

759
00:31:45,250 --> 00:31:49,510
ועצים, שבו לבלבים, שוב, הוא
רק אחד צמתים שהם מערכים,

760
00:31:49,510 --> 00:31:51,680
עדיין מה שאפשר
להשתמש מבית הספר יסודי

761
00:31:51,680 --> 00:31:53,860
כאשר עשה משפחה
עלים tree-- והשורש

762
00:31:53,860 --> 00:31:57,250
של העץ וילדים של
הורה ואחיו.

763
00:31:57,250 --> 00:32:03,670
ואולי ליישם עץ,
למשל, כפשוט כמו זה.

764
00:32:03,670 --> 00:32:07,420
עץ, אם זה כצומת, אחד מ
חוגים אלה, שיש לו מספר,

765
00:32:07,420 --> 00:32:09,947
זה לא הולך להיות
אחד מצביע, אלא שתיים.

766
00:32:09,947 --> 00:32:11,780
וברגע שאתה מוסיף
מצביע שני, אתה

767
00:32:11,780 --> 00:32:13,905
ממש יכול עכשיו לעשות סוג
נתונים דו-ממדיים

768
00:32:13,905 --> 00:32:14,780
מבנים בזיכרון.

769
00:32:14,780 --> 00:32:16,660
בדומה דו-ממדי
מערך, שאתה יכול

770
00:32:16,660 --> 00:32:18,904
יש סוג של דו-ממדי
רשימות אבל אלה מקושרים

771
00:32:18,904 --> 00:32:20,820
שבצע דפוס
שבה אין מחזורים.

772
00:32:20,820 --> 00:32:24,487
זה באמת עץ עם אחד
דרך לכאן, ואז סב

773
00:32:24,487 --> 00:32:27,320
חלק מהורים וילדים ו
נכדים ונינים.

774
00:32:27,320 --> 00:32:28,370
וכן הלאה.

775
00:32:28,370 --> 00:32:32,390
>> אבל מה באמת מסודר גם בעניין זה,
רק כדי להקניט אותך עם קצת קוד,

776
00:32:32,390 --> 00:32:35,370
רקורסיה זוכר מ
לא מזמן, לפיה

777
00:32:35,370 --> 00:32:38,220
אתה כותב פונקציה שקוראת לעצמו.

778
00:32:38,220 --> 00:32:41,140
זוהי הזדמנות יפה
ליישם משהו

779
00:32:41,140 --> 00:32:42,920
כמו רקורסיה, כי רואים את זה.

780
00:32:42,920 --> 00:32:43,860
>> זה עץ.

781
00:32:43,860 --> 00:32:48,040
ואני כבר קצת אנאלי עם איך
אני שם את המספרים השלמים לרחוב.

782
00:32:48,040 --> 00:32:51,020
עד כדי כך שיש לו מיוחד
name-- עץ חיפוש בינארי.

783
00:32:51,020 --> 00:32:53,460
עכשיו אנחנו כבר שמענו על ינארי
לחפש, אבל אתה יכול

784
00:32:53,460 --> 00:32:55,180
לעבוד לאחור משמו של הדבר הזה?

785
00:32:55,180 --> 00:32:59,280
מהו הדפוס של איך אני
הכניס את המספרים השלמים לעץ הזה?

786
00:32:59,280 --> 00:33:00,696
זה לא שרירותי.

787
00:33:00,696 --> 00:33:01,570
יש איזה דפוס.

788
00:33:01,570 --> 00:33:02,090
כן.

789
00:33:02,090 --> 00:33:03,370
>> קהל: קטן יותר בצד השמאל.

790
00:33:03,370 --> 00:33:03,690
>> DAVID מלאן: כן.

791
00:33:03,690 --> 00:33:05,062
קטן יותר הם בצד השמאל.

792
00:33:05,062 --> 00:33:06,270
גדול יותר נמצאים בצד הימני.

793
00:33:06,270 --> 00:33:12,940
כך שמשפט נכון הוא
ההורה הוא גדול יותר מהילד שלה השמאלי,

794
00:33:12,940 --> 00:33:14,850
אבל פחות מהילד שלה תקין.

795
00:33:14,850 --> 00:33:17,750
וזה לבדו אפילו
הגדרה מילולית רקורסיבית

796
00:33:17,750 --> 00:33:20,500
כי אתה יכול ליישם את זה
אותו היגיון לכל צומת

797
00:33:20,500 --> 00:33:23,080
וזה רק תחתית
את, מקרה בסיס אם אתה

798
00:33:23,080 --> 00:33:25,740
יהיה, כאשר אתה מכה אחד
העלים, אם אפשר לומר כך,

799
00:33:25,740 --> 00:33:28,580
שבו יש לו חופשה ללא ילדים נוספים.

800
00:33:28,580 --> 00:33:30,614
>> עכשיו איך אתה יכול למצוא את המספר 44?

801
00:33:30,614 --> 00:33:32,280
אתה היה מתחיל בשורש ואומר, HM.

802
00:33:32,280 --> 00:33:35,690
55 הוא לא 44 אז אני רוצה ללכת
תקין או שאני רוצה ללכת שמאלה?

803
00:33:35,690 --> 00:33:37,190
ובכן, ברור שאתה רוצה ללכת שמאלה.

804
00:33:37,190 --> 00:33:40,060
ואז זה בדיוק כמו הטלפון
דוגמא ספר בחיפוש בינארי

805
00:33:40,060 --> 00:33:41,099
באופן כללי יותר.

806
00:33:41,099 --> 00:33:43,390
אבל אנחנו מיישמים את זה
עכשיו קצת יותר דינמי

807
00:33:43,390 --> 00:33:45,339
מ מערך עשוי לאפשר.

808
00:33:45,339 --> 00:33:48,130
ולמעשה, אם אתה רוצה להיראות
בקוד, שבמבט הראשון בטוח.

809
00:33:48,130 --> 00:33:49,671
זה נראה כמו חבורה של קווים שלמה.

810
00:33:49,671 --> 00:33:51,220
אבל זה פשוט יפה.

811
00:33:51,220 --> 00:33:54,490
אם אתה רוצה ליישם פונקציה
חיפוש בשם מטרתו בחיים

812
00:33:54,490 --> 00:33:57,290
הוא לחפש ערך
כמו n, מספר שלם,

813
00:33:57,290 --> 00:34:01,756
ואתה עבר בpointer-- אחד
מצביע לצומת של השורשים,

814
00:34:01,756 --> 00:34:04,380
ולא, של עץ שממנו
אתה יכול לגשת לכל דבר אחר,

815
00:34:04,380 --> 00:34:08,850
שים לב איך בצורה ישירה
אתה יכול ליישם את ההיגיון.

816
00:34:08,850 --> 00:34:10,880
אם העץ הוא null,
כמובן שזה לא שם.

817
00:34:10,880 --> 00:34:11,880
בואו פשוט נחזיר שקר.

818
00:34:11,880 --> 00:34:12,000
נכון?

819
00:34:12,000 --> 00:34:14,040
אם תמסור לי שום דבר,
אין שם כלום.

820
00:34:14,040 --> 00:34:17,900
>> אחר, אם n הוא פחות מ
חץ עץ n-- עכשיו חץ n,

821
00:34:17,900 --> 00:34:20,670
זוכר שהצגנו סופר
בקצרה היום האחר,

822
00:34:20,670 --> 00:34:25,100
וזה רק אומר שדה-התייחסות
מצביע ומסתכלים על השדה שנקרא n.

823
00:34:25,100 --> 00:34:27,690
אז זה אומר ללכת לשם ו
מסתכל על השדה שנקרא n.

824
00:34:27,690 --> 00:34:33,810
אז אם n, הערך שנותן לכם, הוא פחות
מהערך במספר השלם עצים,

825
00:34:33,810 --> 00:34:35,449
איפה אתה רוצה ללכת?

826
00:34:35,449 --> 00:34:36,389
משמאל.

827
00:34:36,389 --> 00:34:37,780
>> אז שים לב לרקורסיה.

828
00:34:37,780 --> 00:34:39,860
אני returning-- לא נכון.

829
00:34:39,860 --> 00:34:40,989
לא מזויף.

830
00:34:40,989 --> 00:34:45,670
אני מחזיר מה התשובה
הוא משיחה לעצמי, שעבר

831
00:34:45,670 --> 00:34:50,100
n שוב, ומיותר,
אבל מה ששונה במקצת עכשיו?

832
00:34:50,100 --> 00:34:51,989
איך אני עושה את הבעיה קטנה יותר?

833
00:34:51,989 --> 00:34:54,920
אני מעביר כבשני
ויכוח, לא השורש של העץ,

834
00:34:54,920 --> 00:34:59,616
אבל הילד השמאלי במקרה זה.

835
00:34:59,616 --> 00:35:00,990
אז אני מעביר בילד השמאלי.

836
00:35:00,990 --> 00:35:04,720
>> בינתיים, אם n הוא גדול יותר מ
הצומת אני כרגע מסתכל על,

837
00:35:04,720 --> 00:35:06,690
אני מחפש בצד ימין.

838
00:35:06,690 --> 00:35:10,880
אחר, אם העץ הוא לא ריק, ו
אם האלמנט לא לשמאל

839
00:35:10,880 --> 00:35:13,240
וזה לא תקין,
מה הוא להפליא המקרה?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
למעשה אנחנו כבר מצאנו את הצומת ב
שאלה, וכך אנחנו חוזרים אמיתיים.

842
00:35:18,440 --> 00:35:21,490
>> אז יש לנו רק גירדתי את פני השטח
עכשיו כמה ממבני נתונים אלה.

843
00:35:21,490 --> 00:35:24,370
בבעיה להגדיר חמש תמצאו
לחקור אלה עוד יותר:

844
00:35:24,370 --> 00:35:27,250
ותינתן לך את העיצוב שלך
בחירה של איך ללכת על זה.

845
00:35:27,250 --> 00:35:30,250
מה שהייתי רוצה לסיים ב
רק טיזר שני 30

846
00:35:30,250 --> 00:35:32,080
ממה שמצפה בשבוע הבא ומעבר.

847
00:35:32,080 --> 00:35:35,390
>> כפי שbegin-- לשמחתך אולי
think-- המעבר שלנו לאט

848
00:35:35,390 --> 00:35:38,680
מהעולם של C ותחתון
פרטי יישום ברמה,

849
00:35:38,680 --> 00:35:42,090
לעולם שבו אנחנו יכולים לקחת ל
מובן מאליו כי למישהו אחר יש סוף סוף

850
00:35:42,090 --> 00:35:44,010
יושם נתונים אלה
מבנים עבורנו,

851
00:35:44,010 --> 00:35:47,570
ונתחיל להבין
עולם האמיתי פירושו של יישום

852
00:35:47,570 --> 00:35:50,560
תוכנות מבוססות רשת ו
אתרים בדרך כלל יותר

853
00:35:50,560 --> 00:35:52,910
וגם מאוד ביטחון
השלכות שיש לנו רק

854
00:35:52,910 --> 00:35:54,850
התחיל לגרד את פני השטח של.

855
00:35:54,850 --> 00:35:57,320
הנה מה שמחכה לנו
בימים הבאים.

856
00:35:57,320 --> 00:36:00,480
>> [וידאו השמעה]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -הוא בא עם מסר,
עם פרוטוקול כולו.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
הוא הגיע לעולם של אכזריות
חומות אש, נתבים אדישים,

861
00:36:30,894 --> 00:36:33,368
וסכנות הרבה יותר גרועה ממוות.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
הוא מהיר.

864
00:36:36,236 --> 00:36:37,980
הוא חזק.

865
00:36:37,980 --> 00:36:42,830
הוא TCP / IP, ויש לו את הכתובת שלך.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"לוחמים נטו."

868
00:36:48,074 --> 00:36:49,660
[END הפעלת וידאו]

869
00:36:49,660 --> 00:36:50,910
DAVID מלאן: בשבוע הבא יגיע.

870
00:36:50,910 --> 00:36:51,880
נראים אותך אז.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[וידאו השמעה]

873
00:36:56,060 --> 00:36:59,240
-ואז עכשיו, "מחשבות עמוקות"
על ידי לדייבן פארנהאם.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David תמיד מתחיל
הרצאות עם, "בסדר."

876
00:37:05,820 --> 00:37:08,750
למה לא, "הנה הפתרון
לקבוצת הבעיה "של השבוע

877
00:37:08,750 --> 00:37:12,180
או "אנחנו נותנים את כולכם?"

878
00:37:12,180 --> 00:37:13,380
[צוחק]

879
00:37:13,380 --> 00:37:15,530
[END הפעלת וידאו]