[Powered by Google Translate] [Review] [Câu đố 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Đại học Harvard]
>> [Đây là CS50.] [CS50.TV]
>> Hey, tất cả mọi người.
Chào mừng bạn đến với phiên xem xét cho 0 Quiz, đang diễn ra này Wednesday.
Những gì chúng ta sẽ làm tối nay, tôi với 3 TFs khác,
và cùng nhau chúng ta sẽ đi qua một đánh giá về những gì chúng tôi đã thực hiện trong khóa học cho đến nay.
Nó sẽ không được 100% toàn diện, nhưng nó sẽ cho bạn một ý tưởng tốt hơn
của những gì bạn đã có và những gì bạn vẫn cần phải học tập trước khi thứ tư.
Và cảm thấy tự do để nâng cao tay của bạn với những câu hỏi như chúng ta sẽ cùng,
nhưng hãy nhớ rằng chúng ta cũng sẽ có một chút ít thời gian vào cuối
nếu chúng tôi nhận được thông qua với một vài phút để phụ tùng để làm các câu hỏi chung chung,
để giữ cho rằng trong tâm trí, và do đó, chúng ta sẽ bắt đầu từ đầu với Tuần 0.
>> [Quiz 0 Review] [0] [Lexi Ross] Nhưng trước khi chúng ta làm chúng ta hãy nói về
các dịch vụ hậu cần của bài kiểm tra.
>> Logistics] [Câu đố diễn ra vào ngày Thứ Tư 10/10 để thay thế cho bài giảng]
>> [(Xem http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf để biết thêm chi tiết)] Đó là ngày thứ tư tháng 10 10.
>> Đó là thứ Tư này, và nếu bạn đi đến URL này ở đây,
mà cũng có thể truy cập từ CS50.net-có một liên kết đến nó
bạn có thể xem thông tin về nơi để đi dựa trên
tên cuối cùng của bạn hoặc liên kết trường học cũng như
nó nói về chính xác những gì các bài kiểm tra sẽ bao gồm các loại câu hỏi mà bạn sẽ nhận được.
Hãy nhớ rằng bạn cũng sẽ có cơ hội xem xét về bài kiểm tra trong phần,
TFs của bạn sẽ được đi qua một số vấn đề thực hành,
và đó là một cơ hội tốt để xem mà bạn vẫn cần phải học cho bài kiểm tra.
Hãy bắt đầu ngay từ đầu với Bytes Bits n '.
Hãy nhớ một chút chỉ là 0 hoặc 1,
và một byte là một bộ sưu tập 8 của những bit.
Hãy nhìn vào bộ sưu tập này của các bit ngay tại đây.
Chúng tôi sẽ có thể để tìm ra bao nhiêu bit.
Nơi mà chúng tôi đếm có 8 trong số họ, tám 0 hoặc 1 đơn vị.
Và kể từ khi có 8 bit, đó là 1 byte,
và chúng ta hãy chuyển nó sang hệ thập lục phân.
Hệ thập lục phân là căn cứ 16, và nó rất dễ dàng để chuyển đổi
một số trong hệ nhị phân, đó là những gì có nghĩa là, một số trong hệ thập lục phân.
Tất cả những gì chúng tôi làm là chúng ta nhìn vào nhóm 4,
và chúng tôi chuyển đổi chúng sang các chữ số thập lục phân thích hợp.
Chúng tôi bắt đầu với nhóm phải nhất của 4, 0011.
Đó sẽ là một 1 và một trong 2, vì vậy với nhau mà làm cho 3.
Và sau đó chúng ta hãy nhìn vào các khối khác 4.
1101. Đó sẽ là một 1, 4, và một trong 8.
Cùng đó là sẽ là 13, mà làm cho D.
Và chúng tôi sẽ nhớ rằng trong hệ thập lục phân, chúng tôi không chỉ cần đi từ 0 đến 9.
Chúng tôi đi 0 đến F, vì vậy sau 9, 10 tương ứng với A,
11 đến B, vân vân đó F là 15.
Ở đây 13 là một D,
do đó, để chuyển đổi nó sang thập phân tất cả những gì chúng ta làm là chúng tôi thực sự
điều trị từng vị trí như là một sức mạnh của 2.
Đó là một trong 1, 2, không 4s, không 8s, là một trong 16, vân vân,
và đó là một chút khó để tính toán trong đầu của bạn, nhưng nếu chúng ta đi sang slide tiếp theo
chúng ta có thể thấy câu trả lời cho điều đó.
>> Về cơ bản chúng ta sẽ đối diện từ bên phải sang trái,
và chúng tôi đang nhân mỗi chữ số bằng năng lực tương ứng của 2.
Và hãy nhớ, cho hệ thập lục phân, chúng ta biểu thị những con số này với 0x ở đầu
nên chúng tôi không nhầm lẫn nó với một số thập phân.
Tiếp tục trên, đây là một bảng ASCII,
và những gì chúng tôi sử dụng mã ASCII là bản đồ từ các nhân vật giá trị số.
Nhớ trong pset mật mã, chúng tôi đã sử dụng rộng rãi của bảng ASCII
để sử dụng các phương pháp khác nhau về mật mã,
Caesar và mật mã Vigenère, để chuyển đổi các chữ cái khác nhau
trong một chuỗi theo phím được đưa ra bởi người sử dụng.
Hãy xem xét một chút về môn toán ASCII.
Nhìn vào 'P' + 1, ở dạng nhân vật đó sẽ là Q,
và nhớ rằng '5 '≠ 5.
Và cách chính xác chúng tôi sẽ chuyển đổi giữa 2 hình thức?
Nó không thực sự quá khó khăn.
Để nhận được 5 chúng ta trừ đi '0 '
bởi vì có 5 nơi giữa '0 'và '5'.
Để đi theo cách khác chúng ta chỉ cần thêm số 0,
vì vậy nó là loại giống như số học thường xuyên.
Chỉ cần nhớ rằng khi một cái gì đó có dấu ngoặc kép xung quanh nó là một nhân vật
và do đó tương ứng với một giá trị trong bảng mã ASCII.
Di chuyển vào các chủ đề khoa học chung máy tính.
Chúng tôi đã học được những gì một thuật toán và làm thế nào chúng ta sử dụng lập trình
để thực hiện các thuật toán.
Một số ví dụ của các thuật toán là một cái gì đó thực sự đơn giản như
kiểm tra xem một số là số chẵn hoặc lẻ.
Cho rằng nhớ là chúng tôi mod số 2 và kiểm tra nếu kết quả là 0.
Nếu vậy, nó thậm chí còn. Nếu không, thật kỳ lạ.
Và đó là một ví dụ về một thuật toán thực sự cơ bản.
>> Một chút của một tham gia nhiều hơn là tìm kiếm nhị phân,
mà chúng ta sẽ đi qua trong phiên xem xét.
Và lập trình là thuật ngữ chúng tôi sử dụng một thuật toán
và chuyển đổi nó để mã máy tính có thể đọc.
2 ví dụ về lập trình Scratch,
đó là những gì chúng tôi đã làm trong tuần 0.
Mặc dù chúng tôi không thực sự loại ra các mã đó là một cách thực hiện
thuật toán này, được in các số 1-10,
và ở đây chúng tôi làm như vậy trong ngôn ngữ lập trình C.
Đây là những chức năng tương đương, chỉ cần viết bằng ngôn ngữ khác nhau hoặc cú pháp.
Sau đó chúng tôi đã học được về các biểu thức boolean,
và boolean là một giá trị đó là đúng hoặc sai,
và ở đây trong mọi biểu thức boolean
đi vào bên trong các điều kiện, vì vậy nếu (x ≤ 5),
tốt, chúng tôi đã được thiết lập x = 5, do đó, điều kiện được đi để đánh giá đúng sự thật.
Và nếu đó là sự thật, bất cứ điều gì đang ở dưới điều kiện
sẽ được đánh giá bằng máy tính, do đó chuỗi sẽ được in
đầu ra tiêu chuẩn, và tình trạng hạn
đề cập đến bất cứ điều gì là bên trong dấu ngoặc đơn của câu lệnh if.
Nhớ tất cả các nhà khai thác.
Ghi && và | | khi chúng tôi đang cố gắng để kết hợp 2 hoặc nhiều điều kiện,
== Không = để kiểm tra xem 2 điều này là bình đẳng.
Hãy nhớ rằng = là chuyển nhượng trong khi == là một nhà điều hành boolean.
≤, ≥ và sau đó cuối cùng 2 tự giải thích.
Một đánh giá chung của logic boolean ở đây.
Và biểu thức boolean cũng rất quan trọng trong các vòng lặp,
mà chúng ta sẽ đi qua.
Chúng tôi đã học được khoảng 3 loại của các vòng cho đến nay năm CS50,, trong khi, và làm trong khi.
Và điều quan trọng là phải biết rằng trong khi đối với hầu hết các mục đích
chúng tôi thực sự có thể sử dụng bất kỳ loại vòng lặp thường
có một số loại mục đích hoặc các mẫu phổ biến
trong lập trình cụ thể gọi cho một trong những vòng
mà làm cho nó hiệu quả nhất hoặc thanh lịch để mã nó theo cách đó.
Hãy đi qua những gì mỗi của những vòng có xu hướng được sử dụng thường xuyên nhất.
>> Trong một vòng lặp for, chúng ta thường đã biết bao nhiêu lần chúng ta muốn để lặp.
Đó là những gì chúng ta đặt trong tình trạng này.
Đối với, i = 0, i <10, ví dụ.
Chúng ta đã biết rằng chúng tôi muốn làm một cái gì đó 10 lần.
Bây giờ, cho một vòng lặp trong khi, nói chung chúng tôi không nhất thiết phải
biết bao nhiêu lần chúng tôi muốn vòng lặp để chạy.
Nhưng chúng tôi biết một số loại điều kiện mà chúng ta muốn nó
luôn luôn đúng hoặc luôn luôn là sai lầm.
Ví dụ, khi được thiết lập.
Hãy nói rằng đó là một biến boolean.
Trong khi đó là sự thật, chúng tôi muốn code để đánh giá,
do đó, một chút mở rộng hơn, một chút tổng quát hơn so với một vòng lặp for,
nhưng bất kỳ vòng lặp for cũng có thể được chuyển đổi thành một vòng lặp while.
Cuối cùng, làm trong khi vòng lặp, có thể là khó khăn nhất để hiểu ngay,
thường được sử dụng khi chúng ta muốn đánh giá các mã đầu tiên
trước khi lần đầu tiên chúng ta kiểm tra điều kiện.
Một trường hợp sử dụng phổ biến cho một làm trong khi vòng lặp
là khi bạn muốn để có được đầu vào của người dùng, và bạn biết bạn muốn yêu cầu người dùng
cho đầu vào ít nhất một lần, nhưng nếu họ không cung cấp cho bạn nhập tốt ngay
bạn muốn giữ lại yêu cầu họ cho đến khi họ cung cấp cho bạn các đầu vào tốt.
Đó là việc sử dụng phổ biến nhất của một vòng lặp trong khi,
và chúng ta hãy nhìn vào cấu trúc thực tế của các vòng lặp.
Họ thường luôn luôn có xu hướng làm theo các mô hình.
>> Trên vòng lặp cho bên trong, bạn có 3 thành phần:
khởi tạo, kiểu như int i = 0 nơi mà tôi là bộ đếm,
điều kiện, mà chúng tôi muốn nói chạy vòng lặp như lâu như tình trạng này vẫn còn giữ,
như i <10, và cuối cùng, cập nhật, đó là làm thế nào chúng ta tăng
biến đếm tại mỗi điểm trong vòng lặp.
Một điều phổ biến để xem có chỉ là i + +,
có nghĩa là tăng i lên 1 mỗi lần.
Bạn cũng có thể làm một cái gì đó giống như i + = 2,
có nghĩa là thêm 2 đến tôi mỗi khi bạn đi qua vòng lặp.
Và sau đó làm điều này chỉ đề cập đến bất kỳ mã mà thực sự chạy như là một phần của vòng lặp.
Và đối với một vòng lặp trong khi, lần này chúng tôi thực sự có việc khởi tạo bên ngoài vòng lặp,
ví dụ như vậy, chúng ta hãy nói rằng chúng tôi đang cố gắng để làm cùng một loại vòng lặp như tôi vừa mô tả.
Chúng tôi sẽ nói int i = 0 trước khi vòng lặp bắt đầu.
Sau đó, chúng ta có thể nói rằng trong khi tôi <10 làm điều này,
vì vậy cùng một khối mã như trước,
và lần này phần cập nhật của mã này, ví dụ, i + +,
thực sự đi bên trong của vòng lặp.
Và cuối cùng, cho làm trong khi, nó tương tự như vòng lặp while,
nhưng chúng ta phải nhớ rằng mã sẽ đánh giá một lần
trước khi điều kiện được kiểm tra, vì vậy nó làm cho rất nhiều ý nghĩa hơn
nếu bạn nhìn vào nó theo thứ tự trên xuống dưới.
Trong một, làm trong khi vòng lặp mã đánh giá thậm chí trước khi bạn nhìn vào các điều kiện trong khi
trong khi một vòng lặp while, nó kiểm tra đầu tiên.
Báo cáo và các biến.
Khi chúng ta muốn tạo một biến mới, đầu tiên chúng ta muốn khởi tạo nó.
>> Ví dụ, int bar khởi tạo biến thanh,
nhưng nó không cung cấp cho nó một giá trị, do đó, giá trị của thanh là những gì bây giờ?
Chúng tôi không biết.
Nó có thể là một số giá trị mà trước đó đã được lưu trữ trong bộ nhớ có rác,
và chúng tôi không muốn sử dụng biến
cho đến khi chúng tôi thực sự cung cấp cho nó một giá trị,
do đó, chúng ta khai báo nó ở đây.
Sau đó, chúng ta khởi tạo nó là 42 dưới đây.
Bây giờ, tất nhiên, chúng ta biết điều này có thể được thực hiện trên một dòng, int bar = 42.
Nhưng chỉ để được rõ ràng nhiều bước mà đang xảy ra,
khai báo và khởi tạo đang diễn ra một cách riêng biệt ở đây.
Nó xảy ra trên một bước, và một trong những kế tiếp, int baz = bar + 1,
tuyên bố này dưới đây, đó baz tăng, do đó, ở phần cuối của khối mã này
nếu chúng ta để in các giá trị của baz nó sẽ là 44
bởi vì chúng ta khai báo và khởi tạo nó là 1> thanh,
và sau đó chúng tôi tăng nó một lần nữa với + +.
Chúng tôi đã đi qua này một thời gian ngắn khá, nhưng nó rất tốt để có một vị tướng
sự hiểu biết về những gì các chủ đề và các sự kiện.
Chúng tôi chủ yếu đã làm điều này trong Scratch,
vì vậy bạn có thể nghĩ các chủ đề như nhiều chuỗi mã
chạy cùng một lúc.
Trong thực tế, nó có thể không chạy cùng một lúc,
nhưng loại trừu tượng chúng ta có thể nghĩ về nó theo cách đó.
>> Scratch, ví dụ, chúng tôi đã có nhiều sprites.
Nó có thể được thực thi mã khác nhau cùng một lúc.
Một người có thể được đi bộ trong khi người kia đang nói điều gì đó
trong một phần khác nhau của màn hình.
Sự kiện này là một cách khác để tách ra logic
giữa các yếu tố khác nhau của mã của bạn,
và trong Scratch, chúng tôi đã có thể để mô phỏng các sự kiện bằng cách sử dụng Bảng phát hình,
và đó là thực sự khi tôi nhận được, không phải khi tôi nghe,
nhưng về cơ bản đó là một cách để truyền thông tin
từ một sprite khác.
Ví dụ, bạn có thể muốn truyền tải trò chơi trên,
và khi sprite khác nhận được trò chơi trên,
nó phản ứng theo một cách nhất định.
Đây là một mô hình quan trọng để hiểu cho lập trình.
Chỉ cần đi qua Tuần cơ bản 0, những gì chúng tôi đã đi qua cho đến nay,
chúng ta hãy nhìn vào chương trình C đơn giản này.
Các văn bản có thể là một chút nhỏ từ đây, nhưng tôi sẽ đi qua nó thực sự nhanh chóng.
Chúng tôi bao gồm 2 tập tin tiêu đề, đầu cs50.h và stdio.h.
Chúng tôi sau đó xác định một giới hạn được gọi là liên tục là 100.
Sau đó chúng tôi đang thực hiện các chức năng chính của chúng tôi.
Vì chúng ta không sử dụng đối số dòng lệnh ở đây, chúng ta cần đặt khoảng trống
như là đối số cho chính.
Chúng tôi thấy int trên chính. Đó là kiểu trả về, do đó trở về 0 ở phía dưới.
Và chúng tôi đang sử dụng CS50 chức năng thư viện có được int
yêu cầu người dùng cho đầu vào, và chúng tôi lưu trữ nó trong biến x,
do đó, chúng ta khai báo x ở trên, và chúng tôi khởi tạo nó với x = getInt.
>> Chúng tôi sau đó kiểm tra xem nếu người sử dụng đã cho chúng ta đầu vào tốt.
Nếu đó là ≥ LIMIT chúng tôi muốn trả lại một mã lỗi của 1 và in thông báo lỗi.
Và cuối cùng, nếu người sử dụng đã cho chúng ta tốt đầu vào
chúng ta sẽ vuông vắn số và in ra kết quả đó.
Chỉ cần bảo đảm rằng tất cả các nhà hit
bạn sẽ nhìn thấy nhãn của các bộ phận khác nhau của mã ở đây.
Tôi đã đề cập liên tục, tập tin tiêu đề.
Ồ, int x. Hãy chắc chắn để nhớ đó là một biến địa phương.
Tương phản từ một biến toàn cầu, mà chúng ta sẽ nói về
một chút sau đó trong phiên xem xét,
và chúng tôi đang kêu gọi các chức năng thư viện printf,
vì vậy nếu chúng tôi đã không bao gồm các tập tin header stdio.h
chúng tôi sẽ không thể gọi printf.
Và tôi tin rằng mũi tên đó đã cắt được trỏ đến% d,
đó là một chuỗi định dạng trong printf.
Nó nói in ra biến này như một số% d,.
Và đó là nó cho Tuần lễ 0.
Bây giờ Lucas sẽ để tiếp tục.
Hey, guys. Tên tôi là Lucas.
Tôi là một sinh viên năm thứ hai trong nhà tốt nhất trong trường, Mather,
và tôi sẽ nói một chút về Tuần 1 và 2,1.
[Tuần 1 và 2,1!] [Lucas Freitas]
Như Lexi đã nói, khi chúng tôi bắt đầu dịch mã của bạn từ Scratch C
một trong những điều mà chúng tôi nhận thấy rằng bạn không thể chỉ
viết mã của bạn và chạy nó bằng cách sử dụng một lá cờ màu xanh lá cây nữa.
Trên thực tế, bạn phải sử dụng một số bước để làm cho chương trình C của bạn
trở thành một tập tin thực thi.
Về cơ bản những gì bạn làm khi bạn đang viết một chương trình là
bạn dịch ý tưởng của bạn thành một ngôn ngữ mà một trình biên dịch có thể hiểu được,
vì vậy khi bạn đang viết một chương trình trong C
những gì bạn đang làm là thực sự viết một cái gì đó mà trình biên dịch của bạn sẽ hiểu,
và sau đó trình biên dịch sẽ dịch rằng mã
thành một cái gì đó mà máy tính của bạn sẽ hiểu.
>> Và điều, máy tính của bạn thực sự là rất ngu ngốc.
Máy tính của bạn chỉ có thể hiểu 0 và 1,
do đó, thực sự trong các máy tính đầu tiên người ta thường lập trình
sử dụng 0 và 1, nhưng không được nữa, cảm ơn Chúa.
Chúng tôi không có để ghi nhớ các chuỗi 0 và 1
cho một vòng lặp hoặc một vòng lặp while và do đó.
Đó là lý do tại sao chúng tôi có một trình biên dịch.
Một trình biên dịch là nó về cơ bản dịch mã C,
trong trường hợp của chúng tôi, một ngôn ngữ mà máy tính của bạn sẽ hiểu,
đó là mã đối tượng, và trình biên dịch mà chúng tôi đang sử dụng
được gọi là kêu vang, vì vậy đây thực sự là biểu tượng cho kêu vang.
Khi bạn đã có chương trình của bạn, bạn phải làm 2 việc.
Trước tiên, bạn phải biên dịch chương trình của bạn, và sau đó bạn sẽ để chạy chương trình của bạn.
Để biên dịch chương trình của bạn, bạn có rất nhiều lựa chọn để làm như vậy.
Người đầu tiên là làm program.c kêu vang
mà các chương trình là tên của chương trình của bạn.
Trong trường hợp này, bạn có thể thấy chúng tôi chỉ nói rằng "Hey, biên dịch chương trình của tôi."
Bạn tôi không nói rằng: "Tôi muốn tên này cho chương trình của tôi" hoặc bất cứ điều gì.
>> Lựa chọn thứ hai là đưa ra một tên cho chương trình của bạn.
Bạn có thể nói kêu vang-o và sau đó là tên mà bạn muốn
các tập tin thực thi được đặt tên là và sau đó program.c.
Và bạn cũng có thể làm cho chương trình và xem như thế nào trong 2 trường hợp đầu tiên
Tôi đặt c, và trong 1/3, tôi chỉ có các chương trình?
Yeah, bạn thực sự không nên đặt c khi bạn sử dụng.
Nếu không, các trình biên dịch thực sự là sẽ hét vào mặt bạn.
Và cũng có thể, tôi không biết nếu các bạn nhớ,
nhưng rất nhiều lần chúng tôi cũng được sử dụng lcs50,-lm.
Điều đó được gọi là liên kết.
Nó chỉ nói cho trình biên dịch mà bạn sẽ sử dụng các thư viện phải có,
vì vậy nếu bạn muốn sử dụng cs50.h bạn thực sự phải gõ
kêu vang program.c-lcs50.
Nếu bạn không làm điều đó, trình biên dịch sẽ không biết
mà bạn đang sử dụng các chức năng trong cs50.h.
Và khi bạn muốn chạy chương trình của bạn, bạn có 2 lựa chọn.
Nếu bạn đã làm program.c kêu vang, bạn đã không đặt tên cho chương trình của bạn.
Bạn phải chạy nó bằng cách sử dụng / a.out..
A.out là một cái tên tiêu chuẩn mà kêu vang cho chương trình của bạn nếu bạn không cung cấp cho nó một cái tên.
Nếu không, bạn sẽ làm gì / chương trình. Nếu bạn đặt tên cho chương trình của bạn,
và cũng có thể nếu bạn đã làm cho chương trình tên một chương trình đang đi để có được
đã được lập trình cùng tên với tập tin c.
Sau đó, chúng tôi nói chuyện về các loại dữ liệu và dữ liệu.
>> Về cơ bản các loại dữ liệu là điều tương tự như hộp nhỏ mà họ sử dụng
để lưu trữ các giá trị, do đó, các kiểu dữ liệu thực sự giống như Pokemon.
Họ đi vào tất cả các kích cỡ và các loại.
Tôi không biết nếu tương tự có ý nghĩa.
Kích thước dữ liệu thực sự phụ thuộc vào cấu trúc máy tính.
Tất cả các dữ liệu kích thước mà tôi sẽ để hiển thị ở đây
thực sự cho một máy 32-bit, đó là trường hợp thiết bị của chúng tôi,
nhưng nếu bạn thực sự mã hóa máy Mac của bạn hoặc trong một Windows
có thể là bạn đang đi để có một máy tính 64-bit,
do đó, hãy nhớ rằng các kích thước dữ liệu mà tôi sẽ hiển thị ở đây
cho các máy tính 32-bit.
Người đầu tiên mà chúng ta thấy là một int,
đó là khá đơn giản.
Bạn sử dụng int để lưu trữ một số nguyên.
Chúng tôi cũng thấy các nhân vật, các char.
Nếu bạn muốn sử dụng một lá thư hoặc biểu tượng một chút, bạn có thể sẽ sử dụng một char.
Một char có 1 byte, có nghĩa là 8 bit, như Lexi nói.
Về cơ bản chúng ta có một bảng ASCII có 256
kết hợp có thể có của số 0 và số 1,
và sau đó khi bạn gõ một char nó sẽ dịch
nhân vật mà đầu vào cho bạn một số mà bạn có trong bảng mã ASCII, như Lexi.
Chúng tôi cũng có float, mà chúng tôi sử dụng để lưu trữ các số thập phân.
Nếu bạn muốn chọn 3,14, ví dụ, bạn sẽ sử dụng một phao
hoặc một đôi có độ chính xác hơn.
Float A có 4 byte.
Đôi A có 8 byte, do đó, sự khác biệt duy nhất là độ chính xác.
Chúng tôi cũng có một thời gian dài được sử dụng cho các số nguyên,
và bạn có thể nhìn thấy cho một máy tính 32-bit một int và một thời gian dài có cùng kích thước,
vì vậy nó không thực sự làm cho cảm giác sử dụng một thời gian dài trong một máy tính 32-bit.
>> Nhưng nếu bạn đang sử dụng một máy Mac và 64-bit, thực sự là một dài có kích thước 8,
do đó, nó thực sự phụ thuộc vào kiến ​​trúc.
Đối với các máy 32-bit, nó không làm cho cảm giác sử dụng một thời gian dài thực sự.
Và sau đó một lâu dài, mặt khác, có 8 byte,
do đó, nó là rất tốt nếu bạn muốn có một số nguyên lâu hơn.
Và cuối cùng, chúng ta có chuỗi, mà thực sự là một char *,
mà là một con trỏ đến một char.
Nó rất dễ dàng để nghĩ rằng kích thước của chuỗi được sẽ như thế
số lượng ký tự mà bạn đã có,
nhưng thực sự là char *
có kích thước của một con trỏ đến một char, đó là 4 byte.
Kích thước của một char * là 4 byte.
Nó không quan trọng nếu bạn có một từ nhỏ hoặc một lá thư hoặc bất cứ điều gì.
Nó sẽ là 4 byte.
Chúng tôi cũng đã học được một chút về đúc,
vì vậy khi bạn có thể thấy, nếu bạn có, ví dụ, một chương trình nói rằng
int x = 3 và sau đó printf ("% d", x / 2)
làm bạn biết những gì nó sẽ in ra màn hình?
>> Một người nào đó >> [sinh viên] 2.
1. >> 1, yeah.
Khi bạn làm 3/2 nó đang xảy ra để có được 1,5,
nhưng kể từ khi chúng tôi đang sử dụng một số nguyên nó sẽ bỏ qua phần thập phân,
và bạn sẽ có 1.
Nếu bạn không muốn điều đó xảy ra những gì bạn có thể làm, ví dụ,
là khai báo một phao y = x.
Sau đó, x mà sử dụng được 3 sẽ là 3,000 trong y.
Và sau đó bạn có thể in các y / 2.
Thực ra, tôi cần phải có một 2. ở đó.
Nó sẽ làm 3.00/2.00,
và bạn đang đi để có được 1,5.
Và chúng ta có f 0,2 chỉ để yêu cầu 2 đơn vị thập phân trong phần thập phân.
Nếu bạn có 0,3 f nó sẽ thực sự có 1,500.
Nếu đó là 2 nó sẽ là 1,50.
Chúng tôi cũng có trường hợp này ở đây.
Nếu bạn làm float x = 3,14 và sau đó bạn printf x
bạn đang đi để có được 3,14.
Và nếu bạn làm x = int x,
có nghĩa là điều trị x là một int và bạn in x bây giờ
bạn sẽ có 3,00.
Điều đó làm cho tinh thần?
Bởi vì bạn đang đầu tiên điều trị x là một số nguyên, vì vậy bạn đang bỏ qua phần thập phân,
và sau đó bạn đang in x.
Và cuối cùng, bạn cũng có thể làm được điều này,
int x = 65, và sau đó bạn khai báo một char c = x,
và sau đó nếu bạn in c, bạn đang thực sự sẽ nhận được
A, do đó, về cơ bản những gì bạn đang làm gì ở đây
dịch các số nguyên vào nhân vật,
giống như bảng ASCII.
Chúng tôi cũng đã nói về các nhà khai thác toán học.
Hầu hết trong số đó là khá đơn giản, do đó, +, -, *, /,
và chúng tôi cũng nói về mod, đó là phần còn lại của một bộ phận của 2 con số.
Nếu bạn có 10% 3, ví dụ,
nó có nghĩa là phân chia 10 cho 3, và phần còn lại là những gì?
Nó sẽ là 1, do đó, nó thực sự rất hữu ích cho rất nhiều chương trình.
Đối với Vigenère và Caesar tôi khá chắc chắn rằng tất cả các bạn sử dụng mod.
Giới thiệu các nhà khai thác toán học, phải rất cẩn thận khi kết hợp * và /.
>> Ví dụ, nếu bạn làm (3/2) * 2 bạn đang đi để có được?
[Sinh viên] 2.
Yeah, 2, bởi vì 3/2 sẽ là 1,5,
nhưng kể từ khi bạn đang làm hoạt động giữa 2 số nguyên
bạn đang thực sự chỉ cần đi để xem xét 1,
và sau đó 1 * 2 sẽ là 2, do đó, có rất, rất cẩn thận
khi làm số học với số nguyên vì
bạn có thể nhận được rằng 2 = 3, trong trường hợp đó.
Và cũng có thể rất cẩn thận về ưu tiên.
Bạn thường nên sử dụng dấu ngoặc để chắc chắn rằng bạn biết những gì bạn đang làm.
Một số phím tắt hữu ích, tất nhiên, là một trong những i + + hoặc i + = 1
hoặc bằng cách sử dụng + =.
Đó là điều tương tự như làm i = i + 1.
Bạn cũng có thể làm tôi - hoặc i - = 1,
đó là điều tương tự như i = i -1,
một cái gì đó bạn sử dụng rất nhiều trong cho các vòng, ít nhất.
Ngoài ra, *, nếu bạn sử dụng * = và nếu bạn làm, ví dụ,
i * = 2 là điều tương tự như nói i = i * 2,
và điều tương tự để chia.
Nếu bạn làm i / = 2 đó là điều tương tự như i = i / 2.
>> Bây giờ về chức năng.
Các bạn học có chức năng là một chiến lược rất tốt để lưu mã
trong khi bạn đang lập trình, vì vậy nếu bạn muốn thực hiện cùng một nhiệm vụ
trong mã một lần nữa và một lần nữa, có thể là bạn muốn sử dụng một chức năng
chỉ để bạn không phải để sao chép và dán mã hơn và hơn nữa.
Trên thực tế, chính là một chức năng, và khi tôi hiển thị cho bạn các định dạng của một hàm
bạn sẽ thấy rằng đó là khá rõ ràng.
Chúng tôi cũng sử dụng các chức năng từ một số thư viện,
printf, ví dụ, GetIn, mà là từ các thư viện CS50,
và các chức năng khác như toupper.
Tất cả những chức năng được thực sự thực hiện trong các thư viện khác,
và khi bạn đặt các tập tin tether trong phần đầu của chương trình của bạn
bạn nói rằng bạn có thể xin vui lòng cho tôi mã cho những chức năng
vì vậy tôi không có để thực hiện chúng của bản thân mình?
Và bạn cũng có thể viết các chức năng riêng của bạn, vì vậy khi bạn bắt đầu lập trình
bạn nhận ra rằng các thư viện không có tất cả các chức năng mà bạn cần.
Cho pset cuối cùng, ví dụ, chúng tôi đã viết vẽ, tranh giành, và tra cứu,
và nó rất, rất quan trọng để có thể viết các chức năng
bởi vì họ là hữu ích, và chúng tôi sử dụng tất cả thời gian trong lập trình,
và nó tiết kiệm rất nhiều mã.
Các định dạng của một hàm là một trong những điều này.
Chúng tôi có loại trả lại trong đầu. Kiểu trả về là gì?
Nó chỉ là khi chức năng của bạn sẽ quay trở lại.
Nếu bạn có một chức năng, ví dụ, thừa,
có nghĩa là sẽ tính toán một nhân tố của một số nguyên,
có lẽ nó sẽ trả lại một số nguyên.
Sau đó, các kiểu trả về sẽ là int.
Printf thực sự có một khoảng trống kiểu trả về
bởi vì bạn không quay trở lại bất cứ điều gì.
Bạn chỉ cần in ra màn hình
và bỏ chức năng sau đó.
Sau đó, bạn có tên của các chức năng mà bạn có thể chọn.
Bạn sẽ có một chút hợp lý, giống như không chọn một cái tên như xyz
hoặc như x2f.
Cố gắng làm cho một tên có ý nghĩa.
>> Ví dụ, nếu đó là thừa, nói thừa.
Nếu đó là một chức năng có nghĩa là sẽ vẽ một cái gì đó, đặt tên nó vẽ.
Và sau đó chúng tôi có các thông số, còn được gọi là đối số,
mà cũng giống như các nguồn tài nguyên mà chức năng của bạn cần
từ mã của bạn để thực hiện nhiệm vụ của mình.
Nếu bạn muốn tính giai thừa của một số
có thể là bạn cần phải có một số để tính toán một thừa.
Một trong những lý luận mà bạn sẽ phải là số chính nó.
Và sau đó nó sẽ làm điều gì đó và trả về giá trị ở cuối
trừ khi đó là một hàm void.
Hãy xem một ví dụ.
Nếu tôi muốn viết một chức năng mà tổng tất cả các số trong một mảng các số nguyên,
đầu tiên của tất cả, kiểu trả về sẽ là int
vì tôi có một mảng các số nguyên.
Và sau đó tôi sẽ có tên chức năng như sumArray,
và sau đó nó sẽ mất các mảng chính nó, nums int,
và sau đó chiều dài của mảng vì vậy tôi biết tôi có bao nhiêu số tổng hợp.
Sau đó, tôi phải khởi tạo một khoản tiền gọi là biến, ví dụ, để 0,
và mỗi lần tôi thấy một phần tử trong mảng tôi nên thêm nó để tổng hợp, do đó, tôi đã làm một vòng lặp for.
Cũng giống như Lexi nói, bạn làm int i = 0, i <chiều dài và i + +.
Và đối với tất cả các phần tử trong mảng, tôi đã làm tổng + = nums [i],
và sau đó tôi trả lại số tiền, vì vậy nó rất đơn giản, và nó tiết kiệm rất nhiều mã
nếu bạn đang sử dụng chức năng này rất nhiều lần.
Sau đó, chúng tôi đã xem xét ở điều kiện.
Chúng tôi có nếu, khác, và nếu người nào khác.
Hãy xem sự khác biệt giữa những người là những gì.
Hãy nhìn vào 2 mã này. Sự khác biệt giữa chúng là gì?
Người đầu tiên đã về cơ bản các mã muốn cậu nói
nếu một số là +, -, hoặc 0.
Người đầu tiên nói rằng nếu nó> 0 thì đó là tích cực.
Nếu đó là = là 0 sau đó nó là 0, và nếu nó <0 thì đó là tiêu cực.
>> Và một trong những khác được thực hiện nếu, khác nếu, khác.
Sự khác biệt giữa hai là một trong những điều này thực sự sẽ
kiểm tra xem> 0, <0 hoặc = 0 ba lần,
vì vậy nếu bạn có số 2, ví dụ, nó sẽ đến đây và nói
if (x> 0), và nó sẽ nói có, vì vậy tôi in tích cực.
Nhưng mặc dù tôi biết rằng đó là> 0 và nó sẽ không là 0 hoặc <0
Tôi vẫn sẽ làm là 0, là nó <0,
vì vậy tôi thực sự đi bên trong của IFS rằng tôi không phải
bởi vì tôi đã biết rằng nó sẽ không đáp ứng bất cứ điều kiện.
Tôi có thể sử dụng nếu, khác nếu, khác tuyên bố.
Về cơ bản nó nói rằng nếu x = 0 tôi in tích cực.
Nếu không, tôi sẽ cũng thử nghiệm này.
Nếu đó là 2 không tôi sẽ làm điều này.
Về cơ bản nếu tôi có x = 2 bạn sẽ nói
if (x> 0), có, do đó in này.
Bây giờ tôi biết rằng đó là> 0 và nó hài lòng đầu tiên nếu
Tôi thậm chí không để chạy mã này.
Mã chạy nhanh hơn, trên thực tế, nhanh gấp 3 lần nếu bạn sử dụng.
Chúng tôi cũng đã học về và.
Tôi sẽ không đi qua điều này bởi vì Lexi đã nói về họ.
Nó chỉ là && và | nhà điều hành |.
>> Điều duy nhất tôi sẽ nói là hãy cẩn thận khi bạn có 3 điều kiện.
Sử dụng dấu ngoặc đơn bởi vì nó rất khó hiểu khi bạn có một điều kiện
và một số khác hoặc một số khác.
Sử dụng dấu ngoặc đơn chỉ để đảm bảo rằng các điều kiện của bạn có ý nghĩa
bởi vì trong trường hợp đó, ví dụ, bạn có thể tưởng tượng rằng
nó có thể là điều kiện đầu tiên và một hay khác
hoặc 2 điều kiện kết hợp trong một
hoặc 1/3, do đó, chỉ cần cẩn thận.
Và cuối cùng, chúng tôi nói chuyện về các thiết bị chuyển mạch.
Bộ chuyển mạch là rất hữu ích khi bạn có một biến.
Hãy nói rằng bạn có một biến như n
có thể là 0, 1, hoặc 2, và cho mỗi người trong số những trường hợp
bạn sẽ thực hiện một nhiệm vụ.
Bạn có thể nói chuyển biến, và nó cho thấy rằng
Sau đó, giá trị là như value1 tôi sẽ để làm điều này,
và sau đó tôi phá vỡ, có nghĩa là tôi sẽ không nhìn bất cứ lúc nào trong các trường hợp khác
bởi vì chúng tôi đã hài lòng trường hợp đó
và sau đó value2 và như vậy, và tôi cũng có thể có một chuyển đổi mặc định.
Điều đó có nghĩa là nếu nó không đáp ứng bất kỳ trong các trường hợp mà tôi đã có
rằng tôi sẽ làm cái gì khác, nhưng đó là tùy chọn.
Đó là tất cả đối với tôi. Bây giờ chúng ta hãy có Tommy.
Được rồi, điều này là có được Tuần 3-ish.
Đây là một số trong những chủ đề chúng tôi sẽ được bao gồm, mật, phạm vi, mảng, vân vân.
Chỉ cần một lời nhanh chóng trên mật. Chúng tôi sẽ không để búa nhà này.
>> Chúng tôi đã làm điều này trong pset 2, nhưng cho bài kiểm tra chắc chắn rằng bạn biết sự khác biệt
giữa mật mã Caesar và mật mã Vigenère,
làm thế nào cả hai người trong số những người làm việc mật mã và những gì nó giống như mã hóa
và giải mã văn bản bằng cách sử dụng những 2 thuật toán mã hóa.
Hãy nhớ rằng, mật mã Caesar chỉ đơn giản là xoay mỗi nhân vật bằng cách cùng một số tiền,
làm cho chắc chắn rằng bạn mod bằng của số chữ cái trong bảng chữ cái.
Và mật mã Vigenère, mặt khác, xoay mỗi nhân vật
bởi một số lượng khác nhau, do đó, thay vì nói:
mỗi luân chuyển nhân vật bằng 3 Vigenère sẽ luân phiên mỗi nhân vật
bởi một số lượng khác nhau tùy thuộc vào một số từ khóa
trong đó mỗi chữ cái trong từ khóa đại diện cho một số lượng khác nhau
để xoay văn bản rõ ràng.
Hãy nói chuyện đầu tiên về phạm vi biến.
Có 2 loại khác nhau của các biến.
Chúng tôi có các biến địa phương, và những điều này sẽ được xác định
bên ngoài của chính hoặc bên ngoài bất kỳ chức năng hoặc khối,
và chúng sẽ có thể truy cập bất cứ nơi nào trong chương trình của bạn.
Nếu bạn có một chức năng và chức năng đó là một vòng lặp while
các biến toàn cầu lớn có thể truy cập ở khắp mọi nơi.
Một biến địa phương, mặt khác, là scoped để nơi nó được định nghĩa.
>> Nếu bạn có một chức năng ở đây, ví dụ, chúng ta có hàm g,
và bên trong g có một biến ở đây gọi là y,
và điều đó có nghĩa rằng đây là một biến địa phương.
Mặc dù biến này được gọi là y
và biến này được gọi là y 2 chức năng này
không có ý tưởng những gì các biến địa phương của nhau.
Mặt khác, ở đây chúng ta nói int x = 5,
và điều này là ngoài phạm vi chức năng bất kỳ.
Đó là bên ngoài phạm vi chính, vì vậy đây là một biến toàn cầu.
Điều đó có nghĩa là bên trong của 2 chức năng này khi tôi nói x - x + +
Tôi đang truy cập cùng x, theo đó y và y này là các biến khác nhau.
Đó là sự khác biệt giữa một biến toàn cầu và một biến địa phương.
Theo như thiết kế là có liên quan, đôi khi nó có thể là một ý tưởng tốt hơn
để giữ cho các biến địa phương bất cứ khi nào bạn có thể có thể
kể từ khi có một loạt các biến toàn cầu có thể nhận được thực sự khó hiểu.
Nếu bạn có một loạt các chức năng tất cả các sửa đổi điều tương tự
bạn có thể quên điều gì sẽ xảy ra nếu chức năng này vô tình thay đổi này trên toàn cầu,
và điều này chức năng khác không biết về nó,
và nó nhận được khá khó hiểu khi bạn nhận được mã nhiều hơn.
Giữ các biến địa phương bất cứ khi nào bạn có thể có thể
là chỉ cần thiết kế tốt.
Mảng, hãy nhớ rằng, chỉ đơn giản là danh sách các phần tử cùng loại.
Bên trong của CI không có thể có một danh sách giống như 1, 2,0, xin chào.
Chúng tôi không thể làm điều đó.
>> Khi chúng ta khai báo một mảng trong C tất cả các yếu tố phải có cùng loại.
Ở đây tôi có một mảng của 3 số nguyên.
Ở đây tôi có chiều dài của mảng, nhưng nếu tôi chỉ cần khai báo nó trong cú pháp này
nơi mà tôi xác định tất cả các yếu tố kỹ thuật tôi không cần này 3.
Trình biên dịch là đủ thông minh để tìm ra các mảng lớn như thế nào.
Bây giờ khi tôi muốn nhận được hoặc thiết lập giá trị của một mảng
đây là cú pháp để làm điều đó.
Điều này thực sự sẽ thay đổi phần tử thứ hai của mảng bởi vì, hãy nhớ,
số bắt đầu từ 0, không phải tại 1.
Nếu tôi muốn đọc giá trị đó, tôi có thể nói một cái gì đó như int x = array [1].
Hoặc nếu tôi muốn thiết lập giá trị đó, giống như tôi đang làm ở đây,
Tôi có thể nói array [1] = 4.
Đó là thời gian truy cập các phần tử bằng cách chỉ mục của họ
hoặc vị trí của họ hoặc nơi họ đang có trong mảng,
và niêm yết bắt đầu từ 0.
Chúng tôi cũng có thể có mảng của mảng,
và điều này được gọi là một mảng đa chiều.
Khi chúng ta có một mảng đa chiều
điều đó có nghĩa là chúng ta có thể có một cái gì đó giống như các hàng và cột,
và điều này chỉ là một cách hình dung này hay suy nghĩ về nó.
Khi tôi có một mảng đa chiều có nghĩa là tôi sẽ bắt đầu cần
hơn 1 chỉ mục bởi vì nếu tôi có một mạng lưới
nói hàng bạn đang ở trong không cung cấp cho chúng tôi một số.
Đó là thực sự chỉ sẽ cung cấp cho chúng tôi một danh sách các số.
Hãy nói rằng tôi có mảng này ở đây.
Tôi có một mảng lưới, và tôi nói rằng đó là 2 dòng và 3 cột,
và vì vậy đây là một cách hình dung nó.
Khi tôi nói rằng tôi muốn để có được những yếu tố [1] [2]
điều đó có nghĩa là bởi vì đây là hàng đầu tiên và sau đó cột
Tôi sẽ nhảy chèo 1 kể từ khi tôi nói 1.
>> Sau đó, tôi sẽ đến đây để cột 2, và tôi sẽ để có được những giá trị 6.
Có ý nghĩa?
Mảng đa chiều, hãy nhớ rằng, về mặt kỹ thuật chỉ là một mảng của các mảng.
Chúng tôi có thể có mảng của mảng của mảng.
Chúng ta có thể tiếp tục đi, nhưng thực sự là một cách để suy nghĩ về
làm thế nào điều này đang được đặt ra và những gì đang xảy ra là để hình dung nó
trong một mạng lưới như thế này.
Khi chúng tôi vượt qua các mảng chức năng, họ sẽ cư xử
một chút khác biệt so với khi chúng tôi vượt qua các biến thông thường chức năng
giống như đi qua một int hoặc float.
Khi chúng tôi vượt qua trong một loại int hoặc char hoặc bất kỳ của những dữ liệu khác
chúng tôi chỉ cần lấy một cái nhìn nếu chức năng chỉnh sửa
giá trị của biến đó mà thay đổi không phải là đi tuyên truyền
chức năng gọi điện thoại.
Với một mảng, mặt khác, đó sẽ xảy ra.
Nếu tôi vượt qua trong một mảng một số chức năng và chức năng mà thay đổi một số yếu tố,
khi tôi trở lại lên đến chức năng mà nó được gọi là
mảng của tôi bây giờ là có được khác nhau, và từ vựng cho rằng
là mảng được thông qua tham khảo, như chúng ta sẽ thấy sau này.
Điều này có liên quan đến con trỏ làm việc như thế nào, các kiểu dữ liệu cơ bản,
Mặt khác, thông qua giá trị.
>> Chúng ta có thể nghĩ rằng như làm một bản sao của biến số và sau đó đi qua trong bản sao.
Nó không quan trọng những gì chúng tôi làm với biến đó.
Các chức năng gọi điện thoại sẽ không nhận thức được rằng nó đã được thay đổi.
Mảng là chỉ là một chút khác nhau trong đó liên quan.
Ví dụ, như chúng ta vừa thấy, chính là chỉ đơn giản là một chức năng
mà có thể mất trong 2 đối số.
Đối số đầu tiên để các chức năng chính là argc, hoặc số của các đối số,
và đối số thứ hai được gọi là argv,
và những người đang có giá trị thực tế của các đối số.
Hãy nói rằng tôi có một chương trình gọi là this.c,
và tôi nói thực hiện điều này, và tôi sẽ chạy này tại dòng lệnh.
Bây giờ để vượt qua trong một số đối số chương trình của tôi gọi như thế này
Tôi có thể nói một cái gì đó như / là cs 50.
Đây là những gì chúng ta tưởng tượng David để làm mỗi ngày tại thiết bị đầu cuối.
Nhưng bây giờ bên trong chức năng chính của chương trình đó
có những giá trị này, do đó, argc là 4.
Nó có thể là một chút bối rối bởi vì thực sự chúng tôi chỉ đi qua trong cs 50.
Đó là chỉ có 3.
Nhưng hãy nhớ rằng yếu tố đầu tiên của argv hoặc đối số đầu tiên
là tên của các chức năng riêng của mình.
Vì vậy, điều đó có nghĩa là chúng ta đã có 4 điều ở đây,
và các yếu tố đầu tiên là có được /..
Và điều này sẽ được thể hiện như một chuỗi.
Sau đó, các yếu tố còn lại là những gì chúng ta gõ vào sau tên của chương trình.
Vì vậy, cũng giống như một sang một bên, như chúng ta có thể nhìn thấy trong pset 2,
hãy nhớ rằng chuỗi 50 ≠ số nguyên 50.
Vì vậy, chúng ta không thể nói một cái gì đó giống như, 'int x = argv 3.
>> Đó chỉ là sẽ không có ý nghĩa, bởi vì đây là một chuỗi, và điều này là một số nguyên.
Vì vậy, nếu bạn muốn chuyển đổi giữa 2, hãy nhớ rằng, chúng ta sẽ
có chức năng này kỳ diệu được gọi là atoi.
Mà phải mất một chuỗi và trả về số nguyên đại diện bên trong của chuỗi đó.
Vì vậy, đó là một sai lầm dễ dàng để làm cho bài kiểm tra,
chỉ nghĩ rằng điều này sẽ tự động được đúng loại.
Nhưng chỉ biết rằng sẽ luôn luôn được chuỗi
ngay cả nếu chuỗi chỉ chứa một số nguyên hoặc một ký tự hoặc một phao.
Vì vậy, bây giờ chúng ta hãy nói về việc chạy thời gian.
Khi chúng tôi có tất cả các thuật toán làm tất cả những điều điên rồ,
nó trở nên thực sự hữu ích để đặt câu hỏi, "bao lâu để họ đi?"
Chúng tôi đại diện cho rằng với một cái gì đó được gọi là tiệm cận ký hiệu.
Vì vậy, điều này có nghĩa là, chúng ta hãy nói rằng chúng tôi cung cấp cho thuật toán của chúng tôi
một số đầu vào thực sự, thực sự, thực sự lớn.
Chúng tôi muốn đặt câu hỏi, "Làm thế nào là nó sẽ mất?
Nó sẽ mất bao nhiêu bước thuật toán của chúng tôi để chạy
như là một chức năng của các kích thước của đầu vào? "
Vì vậy, cách đầu tiên chúng ta có thể mô tả thời gian chạy là với lớn O.
Và đây là trường hợp xấu nhất thời gian chạy của chúng tôi.
Vì vậy, nếu chúng ta muốn sắp xếp một mảng, và chúng tôi cung cấp cho thuật toán của chúng tôi một mảng
đó là thứ tự giảm dần khi nó phải ở trong thứ tự tăng dần,
đó sẽ là trường hợp xấu nhất.
Đây là phía trên của chúng tôi bị ràng buộc trong chiều dài tối đa thời gian thuật toán của chúng tôi sẽ.
Mặt khác, điều này Ω sẽ mô tả phù hợp nhất là thời gian chạy.
Vì vậy, nếu chúng ta cho một mảng đã được sắp xếp vào một thuật toán sắp xếp,
nó sẽ mất bao lâu để sắp xếp nó?
Và điều này, sau đó, mô tả một thấp hơn bị ràng buộc về thời gian chạy.
Vì vậy, đây chỉ là một số từ mô tả một số lần chạy chung.
Đây là những thứ tự tăng dần.
Thời gian nhanh nhất chạy chúng tôi có được gọi là hằng số.
>> Điều đó có nghĩa là không có vấn đề bao nhiêu yếu tố chúng tôi cung cấp cho thuật toán của chúng tôi,
không có vấn đề lớn như thế nào mảng của chúng tôi, phân loại nó
hoặc làm bất cứ điều gì chúng tôi đang làm mảng sẽ luôn luôn có cùng một lượng thời gian.
Vì vậy, chúng ta có thể đại diện cho rằng chỉ với một 1, mà là một hằng số.
Chúng tôi cũng nhìn vào thời gian chạy logarit.
Vì vậy, một cái gì đó giống như tìm kiếm nhị phân là logarit,
nơi mà chúng tôi cắt giảm các vấn đề trong một nửa thời gian mỗi
và sau đó mọi thứ chỉ có được cao hơn từ đó.
Và nếu bạn đã bao giờ viết một O của bất kỳ thuật toán giai thừa,
bạn có lẽ không nên coi đây là công việc của bạn.
Khi chúng ta so sánh các lần chạy điều quan trọng cần ghi nhớ những điều này.
Vì vậy, nếu tôi có một thuật toán là O (n), và ai đó khác
đã một thuật toán O (2n) đây là những thực sự tiệm tương đương.
Vì vậy, nếu chúng ta tưởng tượng n là một số lượng lớn như eleventy tỷ:
do đó, khi chúng ta đang so sánh eleventy tỷ một cái gì đó giống như eleventy tỷ + 3,
đột nhiên 3 mà không thực sự làm cho một sự khác biệt lớn nữa.
Đó là lý do tại sao chúng ta sẽ bắt đầu xem xét những điều này là tương đương.
Vì vậy, những thứ như các hằng số ở đây, có 2 x này, hoặc thêm một 3,
đây chỉ là hằng số, và những điều này sẽ giảm.
Vì vậy, đó là lý do tại sao tất cả 3 của những lần chạy giống như nói rằng họ là O (n).
Tương tự như vậy, nếu chúng ta có 2 lần chạy khác, chúng ta hãy nói O (n + 2n ² ³), chúng ta có thể thêm
+ N, + 7, và sau đó chúng tôi có một thời gian chạy đó chỉ là O (n ³).
một lần nữa, đây là những điều tương tự bởi vì những - đây là không giống nhau.
Đây là những điều tương tự, xin lỗi. Vì vậy đây là giống nhau bởi vì
³ n này sẽ chi phối ² 2n.
>> Những gì không phải là cùng một điều là nếu chúng ta đã chạy như O (n ³) và O (n ²)
bởi vì đây ³ n là lớn hơn nhiều so ² n này.
Vì vậy, nếu chúng ta có số mũ, đột nhiên này bắt đầu quan trọng,
nhưng khi chúng ta chỉ đối phó với các yếu tố như chúng tôi đang ở đây,
sau đó nó sẽ không quan trọng bởi vì họ chỉ cần đi bỏ.
Hãy có một cái nhìn tại một số các thuật toán chúng tôi đã nhìn thấy cho đến nay
và nói chuyện về thời gian chạy của họ.
Cách đầu tiên tìm kiếm một số trong một danh sách, mà chúng ta đã thấy, là tuyến tính tìm kiếm.
Và thực hiện tìm kiếm tuyến tính là siêu đơn giản.
Chúng tôi chỉ có một danh sách, và chúng ta sẽ xem xét tất cả các yếu tố duy nhất trong danh sách
cho đến khi chúng tôi tìm thấy số lượng chúng tôi đang tìm kiếm.
Vì vậy, đó có nghĩa là trong trường hợp xấu nhất, điều này O (n).
Và trường hợp xấu nhất ở đây có thể là nếu phần tử
yếu tố cuối cùng, sau đó sử dụng tìm kiếm tuyến tính, chúng ta phải nhìn vào từng yếu tố duy nhất
cho đến khi chúng tôi nhận được một trong những cuối cùng để biết rằng nó đã thực sự trong danh sách.
Chúng ta không thể bỏ nửa chừng và nói, "Đó có thể là không có."
Với tìm kiếm tuyến tính, chúng ta phải nhìn vào toàn bộ điều.
Thời gian chạy tốt nhất, mặt khác, là không đổi
bởi vì trong trường hợp tốt nhất các yếu tố mà chúng tôi đang tìm kiếm chỉ là một trong những đầu tiên trong danh sách.
Vì vậy, nó sẽ đưa chúng ta chính xác 1 bước, không có vấn đề lớn như thế nào trong danh sách là
nếu chúng ta đang tìm kiếm các yếu tố đầu tiên mỗi lần.
>> Vì vậy, khi bạn tìm kiếm, hãy nhớ rằng, nó không yêu cầu danh sách của chúng tôi được sắp xếp.
Bởi vì chúng tôi chỉ đơn giản là để xem qua tất cả các yếu tố duy nhất, và nó không thực sự quan trọng
thứ tự các yếu tố.
Một thuật toán tìm kiếm thông minh hơn là một cái gì đó giống như tìm kiếm nhị phân.
Hãy nhớ rằng, việc thực hiện tìm kiếm nhị phân là khi bạn đang đi để
tiếp tục tìm kiếm ở giữa danh sách.
Và bởi vì chúng tôi đang tìm kiếm ở giữa, chúng tôi yêu cầu rằng danh sách được sắp xếp
hoặc người nào khác chúng tôi không biết nơi giữa là, và chúng ta phải nhìn qua
toàn bộ danh sách để tìm thấy nó, và sau đó tại thời điểm đó, chúng tôi chỉ đang lãng phí thời gian.
Vì vậy, nếu chúng ta có một danh sách được sắp xếp và chúng tôi tìm thấy giữa, chúng tôi sẽ so sánh giữa
phần tử, chúng tôi đang tìm kiếm.
Nếu đó là quá cao, sau đó chúng ta có thể quên nửa bên phải
bởi vì chúng tôi biết rằng nếu phần tử của chúng tôi là đã quá cao
và tất cả mọi thứ ở bên phải của yếu tố này thậm chí còn cao hơn,
sau đó chúng ta không cần để tìm ở đó nữa.
Mặt khác, nếu phần tử của chúng tôi là quá thấp,
chúng ta biết tất cả mọi thứ để bên trái của phần tử đó cũng là quá thấp,
do đó, nó không thực sự có ý nghĩa để tìm ở đó, một trong hai.
Bằng cách này, với từng bước và mỗi lần chúng ta nhìn vào điểm giữa của danh sách,
chúng ta sẽ cắt giảm vấn đề của chúng tôi trong một nửa vì đột nhiên chúng ta biết
một bó toàn bộ các số mà không thể được mà chúng ta đang tìm kiếm.
>> Trong giả này sẽ giống như thế này,
và bởi vì chúng tôi đang cắt giảm danh sách trong một nửa thời gian mỗi duy nhất,
trường hợp xấu nhất của chúng tôi thời gian chạy nhảy từ tuyến tính logarit.
Vì vậy, đột nhiên chúng tôi có đăng nhập trong các bước để tìm một phần tử trong một danh sách.
Thời gian chạy tốt nhất, mặc dù, vẫn còn liên tục
bởi vì bây giờ, chúng ta hãy chỉ nói rằng các phần tử chúng tôi đang tìm kiếm
luôn luôn giữa chính xác của danh sách ban đầu.
Vì vậy, chúng ta có thể phát triển danh sách của chúng tôi là lớn như chúng tôi muốn, nhưng nếu các yếu tố chúng tôi đang tìm kiếm là ở giữa,
sau đó nó sẽ đưa chúng ta 1 bước.
Vì vậy, đó là lý do tại sao chúng tôi là O (log n) và Ω (1) hoặc liên tục.
Hãy thực sự chạy tìm kiếm nhị phân trong danh sách này.
Vì vậy, chúng ta hãy nói rằng chúng tôi đang tìm kiếm các yếu tố 164.
Điều đầu tiên chúng ta sẽ làm là tìm điểm giữa của danh sách này.
Nó chỉ như vậy sẽ xảy ra rằng trung điểm sẽ rơi vào giữa 2 con số,
vì vậy hãy chỉ cần tùy tiện, mỗi lần trung điểm nằm giữa 2 con số,
chúng ta hãy chỉ làm tròn.
Chúng ta chỉ cần để đảm bảo rằng chúng tôi làm điều này tất cả các bước của con đường.
Vì vậy, chúng tôi đang đi vòng lên, và chúng ta sẽ nói rằng 161 là giữa của danh sách của chúng tôi.
Vì vậy, 161 trang <164, và tất cả các yếu tố bên trái trong tổng số 161
cũng là <164, vì vậy chúng tôi biết rằng nó sẽ không giúp cho chúng ta cả
để bắt đầu tìm kiếm ở đây bởi vì các yếu tố, chúng tôi đang tìm kiếm không thể có mặt.
Vì vậy, những gì chúng ta có thể làm là chúng tôi chỉ có thể quên đi rằng một nửa trái toàn bộ danh sách,
và bây giờ chỉ xem xét từ bên phải trở đi 161.
>> Vì vậy, một lần nữa, điều này là trung điểm, chúng ta hãy chỉ làm tròn.
Bây giờ 175 là quá lớn.
Vì vậy, chúng ta biết nó không phải đi để giúp chúng tôi tìm kiếm ở đây hoặc ở đây,
vì vậy chúng tôi chỉ có thể ném đi, và cuối cùng chúng tôi sẽ tung ra 164.
Bất kỳ câu hỏi về tìm kiếm nhị phân?
Chúng ta hãy chuyển từ việc tìm kiếm thông qua một danh sách đã được sắp xếp
để thực sự tham gia một danh sách các số theo thứ tự bất kỳ
và làm cho rằng danh sách theo thứ tự tăng dần.
Các thuật toán đầu tiên chúng tôi nhìn được gọi là bong bóng sắp xếp.
Và điều này sẽ được đơn giản của các thuật toán chúng ta đã thấy.
Bong bóng sắp xếp nói rằng khi bất kỳ 2 yếu tố bên trong danh sách ra khỏi vị trí,
có nghĩa là có một số lượng cao hơn bên trái của một số thấp hơn,
sau đó chúng ta sẽ trao đổi chúng, bởi vì điều đó có nghĩa rằng danh sách sẽ được
"Sắp xếp" so với trước.
Và chúng tôi sẽ tiếp tục quá trình này một lần nữa và một lần nữa và một lần nữa
cho đến khi cuối cùng các loại nguyên tố của các bong bóng đến vị trí chính xác của họ và chúng tôi có một danh sách được sắp xếp.
>> Thời gian chạy của điều này là có được O (n ²). Tại sao?
Vâng, bởi vì trong trường hợp xấu nhất, chúng tôi sẽ tận dụng mọi yếu tố, và
chúng ta sẽ so sánh nó với tất cả các yếu tố khác trong danh sách.
Tuy nhiên, trong trường hợp tốt nhất, chúng tôi có một danh sách đã được sắp xếp, bong bóng sắp xếp
sẽ phải đi qua một lần, nói "Không. Tôi đã không thực hiện bất kỳ giao dịch hoán đổi, vì vậy tôi thực hiện."
Vì vậy, chúng tôi có một thời gian phù hợp nhất là chạy Ω (n).
Chạy bong bóng Sắp xếp trên một danh sách.
Hoặc đầu tiên, chúng ta hãy nhìn vào một số giả thực sự nhanh chóng.
Chúng tôi muốn nói rằng chúng tôi muốn theo dõi, trong mỗi lần lặp của vòng lặp,
theo dõi hay không, chúng tôi thay đổi bất kỳ yếu tố.
Vì vậy, lý do là, chúng ta sẽ dừng lại khi chúng tôi đã không trao đổi bất kỳ yếu tố.
Vì vậy, khi bắt đầu vòng lặp của chúng tôi, chúng tôi đã không trao đổi bất cứ điều gì, vì vậy chúng tôi sẽ nói rằng đó là sai.
Bây giờ, chúng ta sẽ phải đi qua danh sách và so sánh các yếu tố i vào phần tử i + 1
và nếu nó là trường hợp đó có một số lớn hơn bên trái của một số lượng nhỏ,
sau đó chúng ta sẽ trao đổi chúng.
>> Và sau đó chúng ta sẽ nhớ rằng chúng ta trao đổi một phần tử.
Điều đó có nghĩa là chúng ta cần phải đi qua danh sách ít nhất là 1 lần nữa
bởi vì điều kiện mà chúng tôi dừng lại khi toàn bộ danh sách đã được sắp xếp,
có nghĩa là chúng tôi đã không thực hiện bất kỳ giao dịch hoán đổi.
Vì vậy, đó là lý do tại sao điều kiện của chúng tôi xuống ở đây là trong khi một số yếu tố đã được trao đổi.
Vì vậy, bây giờ chúng ta hãy nhìn này chạy trên một danh sách.
Tôi có danh sách 5,0,1,6,4.
Bong bóng sắp xếp được sẽ bắt đầu tất cả các con đường ở bên trái, và nó sẽ so sánh
các yếu tố i, 0 đến i + 1, là 1 phần tử.
Nó sẽ nói, 5> 0, nhưng ngay bây giờ 5 là bên trái,
vì vậy tôi cần phải trao đổi 5 và 0.
Khi tôi trao đổi chúng, đột nhiên tôi nhận được danh sách này khác nhau.
Bây giờ 5> 1, do đó, chúng ta sẽ trao đổi chúng.
5 không phải là> 6, vì vậy chúng tôi không cần phải làm bất cứ điều gì ở đây.
Nhưng 6> 4, vì vậy chúng tôi cần phải trao đổi.
Một lần nữa, chúng ta cần phải chạy qua danh sách toàn bộ để cuối cùng khám phá ra
rằng đây là những ra khỏi trật tự, chúng tôi trao đổi chúng,
và vào thời điểm này, chúng tôi cần phải chạy qua danh sách 1 thời gian nữa
để đảm bảo rằng tất cả mọi thứ trong trật tự của nó, và ở việc này bong bóng điểm đã hoàn tất.
Một thuật toán khác nhau dành một số yếu tố và phân loại chúng là lựa chọn loại.
Ý tưởng đằng sau lựa chọn loại là chúng ta sẽ xây dựng một phần sắp xếp danh sách
1 phần tử tại một thời điểm.
>> Và cách chúng tôi sẽ làm điều đó bằng cách xây dựng phân khúc bên trái của danh sách.
Và về cơ bản, mỗi trên mỗi bước, chúng tôi đang đi để có những phần tử nhỏ nhất chúng tôi đã để lại
đã không được sắp xếp được nêu ra, và chúng ta sẽ di chuyển nó vào phân khúc được sắp xếp.
Điều đó có nghĩa là chúng ta cần phải liên tục tìm các phần tử tối thiểu được phân loại
và sau đó đi mà yếu tố tối thiểu và trao đổi nó với bất cứ điều gì
trái hầu hết các yếu tố không được sắp xếp.
Thời gian chạy của việc này là sẽ là O (n ²) bởi vì trong trường hợp xấu nhất
chúng ta cần phải so sánh tất cả các yếu tố duy nhất để mọi phần tử khác.
Bởi vì chúng ta đang nói rằng nếu chúng ta bắt đầu ở nửa bên trái của danh sách, chúng ta cần
đi qua toàn bộ các phân đoạn phải tìm các phần tử nhỏ nhất.
Và sau đó, một lần nữa, chúng ta cần phải đi qua toàn bộ mảng bên phải và
tiếp tục đi qua rằng hơn và hơn và hơn một lần nữa.
Đó sẽ là n ². Chúng ta sẽ cần một bên trong vòng lặp của một vòng lặp for
điều này cho thấy n ².
Trong suy nghĩ trường hợp tốt nhất, chúng ta hãy nói rằng chúng tôi cung cấp cho nó một danh sách đã được sắp xếp;
chúng tôi thực sự không làm tốt hơn so với bất kỳ n ².
Bởi vì lựa chọn loại không có cách nào biết được
các yếu tố tối thiểu chỉ là một trong tôi tình cờ được xem xét.
Nó vẫn cần để đảm bảo rằng điều này thực sự là tối thiểu.
>> Và cách duy nhất để đảm bảo rằng đó là tối thiểu, bằng cách sử dụng thuật toán này,
là để xem xét tất cả các yếu tố duy nhất một lần nữa.
Vì vậy, thực sự, nếu bạn cho nó - nếu bạn cho lựa chọn loại một danh sách đã được sắp xếp,
nó sẽ không làm bất kỳ tốt hơn so với cho nó một danh sách không được sắp xếp.
Bằng cách này, nếu nó xảy ra là trường hợp rằng cái gì là O (một cái gì đó)
và omega của một cái gì đó, chúng tôi chỉ có thể nói ngắn gọn hơn rằng đó là θ của một cái gì đó.
Vì vậy, nếu bạn nhìn thấy mà đi lên bất cứ nơi nào, đó là những gì mà chỉ có nghĩa là.
>> Nếu một cái gì đó là theta của n ², nó là cả hai O lớn (n ²) và Ω (n ²).
Vì vậy, trường hợp tốt nhất và trường hợp xấu nhất, nó không tạo sự khác biệt,
các thuật toán sẽ làm điều tương tự mỗi lần.
Vì vậy, đây là mã giả để sắp xếp lựa chọn có thể trông giống như.
Chúng tôi về cơ bản sẽ nói rằng tôi muốn để lặp lại trên danh sách
từ trái sang phải, và mỗi lần lặp của vòng lặp, tôi sẽ di chuyển
các yếu tố tối thiểu thành phần này được sắp xếp danh sách.
Và một khi tôi di chuyển cái gì đó, tôi không bao giờ cần phải xem xét yếu tố đó một lần nữa.
Bởi vì ngay sau khi tôi trao đổi một yếu tố trong phân khúc bên trái của danh sách, nó được sắp xếp
bởi vì chúng tôi đang làm tất cả mọi thứ trong thứ tự tăng dần bằng cách sử dụng tối thiểu.
Vì vậy, chúng tôi đã nói, không sao, chúng tôi đang ở vị trí i, và chúng tôi cần phải xem xét tất cả các yếu tố
ở bên phải của tôi để tìm ra tối thiểu.
Vì vậy, điều đó có nghĩa là chúng ta muốn nhìn từ i + 1 đến cuối danh sách.
Và bây giờ, nếu các yếu tố mà chúng tôi hiện đang xem xét là ít hơn mức tối thiểu của chúng tôi cho đến nay,
đó, hãy nhớ rằng, chúng tôi đang bắt đầu off tối thiểu chỉ là
yếu tố bất cứ điều gì chúng tôi hiện tại, tôi sẽ giả định rằng mức tối thiểu.
Nếu tôi tìm một phần tử có kích thước nhỏ hơn, sau đó tôi sẽ nói, được rồi,
tốt, tôi đã tìm thấy một tối thiểu mới.
Tôi sẽ nhớ nơi mà tối thiểu là.
>> Vì vậy, bây giờ, một khi tôi đã đi qua đó phân khúc phải được phân loại,
Tôi có thể nói tôi sẽ trao đổi các yếu tố tối thiểu với các yếu tố đó là ở vị trí i.
Đó là sẽ xây dựng danh sách của tôi, phần tôi sắp xếp danh sách từ trái sang phải,
và chúng tôi không bao giờ cần phải nhìn vào một phần tử một lần nữa khi nó đã trong phần đó.
Một khi chúng tôi đã đổi chỗ.
Vì vậy, chúng ta hãy chạy loại lựa chọn trong danh sách này.
Các yếu tố màu xanh ở đây là có được tôi, và các yếu tố màu đỏ là có được các yếu tố tối thiểu.
Vì vậy, tôi bắt đầu tất cả các con đường ở bên trái của danh sách, như vậy ở mức 5.
Bây giờ chúng ta cần phải tìm thấy các yếu tố tối thiểu được phân loại.
Vì vậy, chúng ta nói 0 <5, do đó 0 là tối thiểu mới của tôi.
>> Nhưng tôi không thể dừng lại ở đó, bởi vì mặc dù chúng ta có thể nhận ra rằng 0 là nhỏ nhất,
chúng ta cần phải chạy qua mọi phần tử khác của danh sách để đảm bảo.
Vì vậy, 1 là lớn hơn, 6 là lớn hơn, 4 là lớn hơn.
Điều đó có nghĩa là sau khi xem xét tất cả các yếu tố này, tôi đã xác định 0 là nhỏ nhất.
Vì vậy, tôi sẽ trao đổi 5 và 0.
Khi tôi trao đổi đó, tôi sẽ nhận được một danh sách mới, và tôi biết rằng tôi không bao giờ cần phải nhìn vào mà 0 một lần nữa
bởi vì một khi tôi đã đổi chỗ, tôi đã sắp xếp nó và chúng tôi đang thực hiện.
Bây giờ nó chỉ như vậy sẽ xảy ra rằng các phần tử màu xanh là một lần nữa trong 5,
và chúng ta cần phải nhìn vào số 1, 6 và 4 để xác định rằng 1
là yếu tố tối thiểu nhỏ nhất, do đó, chúng tôi sẽ trao đổi 1 và 5.
Một lần nữa, chúng ta cần phải nhìn vào so sánh 5 đến 6 và 4,
và chúng tôi sẽ trao đổi 4 và 5, và cuối cùng, so sánh
những 2 con số và trao đổi chúng cho đến khi chúng tôi nhận được danh sách của chúng tôi được sắp xếp.
Bất kỳ câu hỏi về lựa chọn loại?
Okay. Hãy di chuyển đến chủ đề cuối cùng ở đây, và đó là đệ quy.
>> Đệ quy, hãy nhớ rằng, điều này thực sự là meta điều mà một chức năng
nhiều lần tự gọi mình.
Vì vậy, tại một số điểm, trong khi fuction của chúng tôi là liên tục gọi chính nó,
cần có một số điểm mà tại đó chúng tôi dừng lại gọi mình.
Bởi vì nếu chúng ta không làm điều đó, sau đó chúng tôi chỉ cần đi để tiếp tục làm điều này mãi mãi,
và chương trình của chúng tôi chỉ là sẽ không chấm dứt.
Chúng tôi gọi đây là điều kiện trường hợp cơ sở.
Và trường hợp cơ sở nói, thay vì gọi một chức năng một lần nữa,
Tôi chỉ cần đi để trả lại một số giá trị.
Vì vậy, khi chúng tôi đã trả lại một giá trị, chúng tôi đã không gọi mình,
và phần còn lại của các cuộc gọi chúng tôi đã thực hiện cho đến nay cũng có thể trở lại.
Sự đối lập với trường hợp cơ sở là trường hợp đệ quy.
Và đây là khi chúng ta muốn thực hiện một cuộc gọi đến các chức năng mà chúng tôi hiện đang nhập.
Và chúng ta có thể, mặc dù không phải luôn luôn, muốn sử dụng đối số khác nhau.
>> Vì vậy, nếu chúng ta có một chức năng được gọi là f, e chỉ cần gọi là mất 1 đối số,
và chúng tôi chỉ cần giữ gọi f (1), f (1), f (1), và nó chỉ như vậy sẽ xảy ra rằng
đối số 1 rơi vào trường hợp đệ quy, chúng tôi vẫn sẽ không bao giờ dừng lại.
Thậm chí nếu chúng ta có một trường hợp cơ sở, chúng ta cần để đảm bảo rằng cuối cùng chúng tôi đang đi để đạt trường hợp đó, cơ sở.
Chúng tôi không chỉ ở trong trường hợp này đệ quy.
Nói chung, khi chúng ta gọi chúng ta, chúng ta có thể sẽ có một cuộc tranh luận khác nhau mỗi lần.
Dưới đây là một hàm đệ quy thực sự đơn giản.
Vì vậy, điều này sẽ tính toán giai thừa của một số.
Up đầu ở đây chúng tôi có trường hợp cơ sở của chúng tôi.
Trong trường hợp n ≤ 1, chúng tôi sẽ không gọi thừa một lần nữa.
Chúng ta sẽ dừng lại, chúng tôi chỉ cần đi để trả lại một số giá trị.
Nếu điều này là không đúng sự thật, sau đó chúng tôi đang đi để đạt trường hợp đệ quy của chúng tôi.
Chú ý ở đây rằng chúng tôi không chỉ cần gọi điện thoại thừa (n), bởi vì đó không sẽ rất hữu ích.
Chúng tôi sẽ gọi thừa của cái gì khác.
>> Và như vậy bạn có thể thấy, cuối cùng, nếu chúng tôi vượt qua một cái gì đó thừa (5),
chúng ta sẽ gọi thừa (4) và như vậy, và cuối cùng chúng tôi đang đi để đạt trường hợp này cơ sở.
Vì vậy, điều này có vẻ tốt. Hãy xem những gì sẽ xảy ra khi chúng ta thực sự chạy.
Đây là đống, và hãy nói rằng chính là sẽ gọi chức năng này với một đối số (4).
Vì vậy, một khi thừa thấy và = 4, thừa sẽ gọi chính nó.
Bây giờ, đột nhiên, chúng tôi có thừa (3).
Vì vậy, các chức năng này sẽ tiếp tục phát triển cho đến khi cuối cùng chúng tôi trường hợp cơ sở của chúng tôi.
Tại thời điểm này, giá trị trả lại này là sự trở lại (nx giá trị trả lại này),
giá trị trả lại này là nx giá trị trả lại này.
Cuối cùng, chúng tôi cần phải nhấn một số số.
Ở phía trên ở đây, chúng ta nói trả lại 1.
Điều đó có nghĩa rằng một khi chúng ta trở lại con số đó, chúng ta có thể bật ra khỏi stack.
Vì vậy, điều này thừa (1) được thực hiện.
Khi 1 trả về, điều này (1) trả thừa, trở về 1.
Giá trị trả lại này, hãy nhớ rằng, là nx giá trị trả lại này.
Đột ngột như vậy, anh chàng này biết rằng tôi muốn trở lại 2.
>> Vì vậy, hãy nhớ, trả lại giá trị này chỉ là nx giá trị trả lại ở đây.
Vì vậy, bây giờ chúng ta có thể nói 3 x 2, và cuối cùng, ở đây chúng ta có thể nói
điều này là chỉ cần đi là 4 x 3 x 2.
Và một lần trở lại này, chúng tôi nhận được xuống để một số nguyên duy nhất bên trong của chính.
Bất kỳ câu hỏi về đệ quy?
Được rồi. Vì vậy, có nhiều thời gian hơn cho các câu hỏi ở cuối,
nhưng bây giờ Joseph sẽ bao gồm các chủ đề còn lại.
>> [Joseph Ong] Tất cả các quyền. Vì vậy, bây giờ mà chúng tôi đã nói chuyện về recursions,
chúng ta hãy nói một chút về những gì hợp nhất sắp xếp là.
Kết hợp các loại về cơ bản là một cách khác để sắp xếp một danh sách các số.
Và nó hoạt động như thế nào, với loại hợp nhất, bạn có một danh sách, và những gì chúng tôi làm là
chúng ta nói, chúng ta hãy phân chia này thành 2 nửa.
Đầu tiên chúng ta sẽ chạy hợp nhất loại một lần nữa vào nửa trái,
sau đó chúng tôi sẽ chạy hợp nhất sắp xếp trên nửa bên phải,
và cung cấp cho chúng tôi ngay bây giờ 2 nửa đều được sắp xếp, và bây giờ chúng ta sẽ kết hợp những nửa với nhau.
Đó là một chút khó khăn để xem mà không cần một ví dụ, vì vậy chúng ta sẽ đi qua các chuyển động và xem những gì sẽ xảy ra.
Vì vậy, bạn bắt đầu với danh sách này, chúng tôi chia nó thành 2 nửa.
Chúng tôi chạy hợp nhất trên nửa bên trái đầu tiên.
Vì vậy, đó là một nửa trái, và bây giờ chúng tôi chạy chúng thông qua danh sách này một lần nữa
mà được thông qua vào merge loại, và sau đó chúng ta nhìn, một lần nữa,
ở phía bên trái của danh sách này và chúng tôi chạy hợp nhất sắp xếp trên nó.
Bây giờ, chúng ta sẽ có được một danh sách của 2 con số,
và bây giờ là một nửa trái dài chỉ có 1 phần tử, và chúng ta không thể
chia một danh sách chỉ có 1 phần tử vào một nửa, vì vậy chúng tôi chỉ nói rằng, một khi chúng tôi có 50,
mà chỉ là 1 phần tử, nó đã được sắp xếp.
>> Khi chúng tôi đang thực hiện với điều đó, chúng ta có thể thấy rằng chúng ta có thể
chuyển sang nửa bên phải của danh sách này,
và 3 cũng được sắp xếp, và vì vậy bây giờ cả hai nửa của danh sách này đều được sắp xếp
chúng ta có thể tham gia những con số này lại với nhau.
Vì vậy, chúng ta nhìn vào 50 và 3, 3 là nhỏ hơn 50, do đó, nó đi trong lần đầu tiên và sau đó 50.
Bây giờ, đó là thực hiện, chúng tôi quay trở lại với danh sách và sắp xếp nó nửa bên phải.
42 là số riêng của nó, do đó, nó đã được sắp xếp.
Vì vậy, bây giờ chúng ta so sánh những 2 và 3 là nhỏ hơn 42, vì vậy mà được đặt trong lần đầu tiên,
tại 42 được đưa vào, và 50 được đặt in
Bây giờ, đó là sắp xếp, chúng tôi đi tất cả các cách trở lại để phía trên, 1337 và 15.
Vâng, bây giờ chúng ta nhìn vào nửa bên trái của danh sách này, 1337 là bởi chính nó để nó được sắp xếp và cùng với 15.
Vì vậy, bây giờ chúng tôi kết hợp 2 số này để sắp xếp mà danh sách ban đầu 15 <, 1337,
do đó, nó đi trong lần đầu tiên, sau đó 1337 đi.
Và bây giờ chúng tôi sắp xếp cả hai nửa của danh sách ban đầu lên hàng đầu.
Và tất cả chúng ta phải làm là kết hợp các.
Chúng tôi nhìn vào 2 số đầu tiên của danh sách này, 3 <15, do đó, nó đi vào mảng sắp xếp đầu tiên.
15 <42, vì vậy nó đi. Bây giờ, 42 <1337, mà đi.
50 <1337, vì vậy nó đi. Nhận thấy rằng chúng tôi chỉ mất 2 con số trong danh sách này.
Vì vậy, chúng tôi không chỉ xen kẽ giữa 2 danh sách.
Chúng tôi chỉ tìm kiếm ở đầu, và chúng tôi đang dùng các yếu tố
đó là nhỏ hơn và sau đó đặt nó vào một mảng của chúng tôi.
Bây giờ chúng tôi đã hợp nhất tất cả các nửa và chúng tôi đang thực hiện.
>> Thắc mắc về hợp nhất loại? Vâng?
[Sinh viên] Nếu đó là chia tách thành các nhóm khác nhau, tại sao không phải là họ chỉ cần chia nó một lần
và bạn có 3 và 2 trong một nhóm? Phần còn lại của câu hỏi khó hiểu]
Lý do - vì vậy câu hỏi là lý do tại sao chúng ta không thể hợp nhất chúng ở những bước đầu tiên sau khi chúng tôi có chúng?
Lý do chúng ta có thể làm được điều này, bắt đầu ở các yếu tố trái nhất của cả hai bên,
và sau đó đi một trong những nhỏ hơn và đặt nó trong, là chúng ta biết rằng những
danh sách cá nhân trong đơn đặt hàng được sắp xếp.
Vì vậy, nếu tôi đang nhìn vào các yếu tố trái nhất của cả hai nửa,
Tôi biết họ sẽ là những yếu tố nhỏ nhất của những danh sách.
Vì vậy, tôi có thể đặt chúng vào những điểm yếu tố nhỏ nhất trong danh sách này lớn.
Mặt khác, nếu tôi nhìn vào 2 danh sách ở cấp độ thứ hai ở đó,
50, 3, 42, 1337 và 15, những người không được sắp xếp.
Vì vậy, nếu tôi nhìn vào 50 và 1337, tôi sẽ đặt 50 vào danh sách của tôi đầu tiên.
Nhưng điều đó không thực sự có ý nghĩa, bởi vì 3 là phần tử nhỏ nhất trong số tất cả những người.
Vì vậy, lý do duy nhất chúng tôi có thể thực hiện bước này kết hợp là bởi vì danh sách của chúng tôi đã được sắp xếp.
Đó là lý do tại sao chúng tôi có để có được tất cả các cách để phía dưới
bởi vì khi chúng ta chỉ có một số duy nhất, bạn biết rằng một số duy nhất
trong và của chính nó đã là một danh sách được sắp xếp.
>> Bất kỳ câu hỏi nào? Không?
Phức tạp? Vâng, bạn có thể thấy rằng tại mỗi bước có số cuối cùng,
và chúng ta có thể phân chia một danh sách trong nhật ký 1/2 n lần,
đó là nơi mà chúng tôi nhận được n x log n phức tạp.
Và bạn sẽ thấy trường hợp tốt nhất cho hợp nhất loại n log n, và nó chỉ như vậy sẽ xảy ra
trường hợp xấu nhất, hoặc Ω ở đó, cũng là n log n.
Cái gì đó để ghi nhớ.
Di chuyển trên, chúng ta hãy đi vào một số tập tin cơ bản siêu I / O.
Nếu bạn nhìn Scramble, bạn sẽ nhận thấy chúng tôi đã có một số loại hệ thống
nơi bạn có thể viết vào một tập tin đăng nhập, nếu bạn đọc thông qua các mã.
Chúng ta hãy xem làm thế nào bạn có thể làm điều đó.
Vâng, chúng tôi có fprintf, mà bạn có thể nghĩ như chỉ printf,
nhưng chỉ cần in vào một tập tin thay vào đó, và do đó f ở đầu.
Loại mã này lên đây, những gì nó là, như bạn có thể nhìn thấy trong Scramble,
nó đi qua in mảng 2-chiều của bạn ra hàng bởi hàng gì các con số.
Trong trường hợp này, printf in ra thiết bị đầu cuối của bạn hoặc những gì chúng ta gọi là đầu ra tiêu chuẩn của phần.
>> Và bây giờ, trong trường hợp này, tất cả chúng ta phải làm là thay thế printf với fprintf,
nói với nó những tập tin mà bạn muốn in, và trong trường hợp này chỉ cần in nó ra đến tập tin đó
thay vì in ấn nó ra để thiết bị đầu cuối của bạn.
Vâng, sau đó đặt ra câu hỏi: Nơi nào chúng ta có được loại này của tập tin, phải không?
Chúng tôi đã thông qua đăng nhập vào fuction fprintf này, nhưng chúng tôi không biết nó đến từ đâu.
Vâng, sớm trong mã, những gì chúng tôi đã có được đoạn mã này ở đây,
về cơ bản nói rằng tập tin mở các cuộc gọi log.txt.
Những gì chúng tôi làm sau đó là chúng ta phải đảm bảo rằng tập tin là thực sự mở thành công.
Vì vậy, nó có thể thất bại vì nhiều lý do, bạn không có đủ không gian trên máy tính của bạn, ví dụ.
Vì vậy, nó luôn luôn quan trọng trước khi bạn làm bất kỳ hoạt động với các tập tin
rằng chúng ta kiểm tra xem tập tin đã được mở thành công.
Vì vậy, những gì là một, đó là một tham số để fopen, tốt, chúng ta có thể mở một tập tin bằng nhiều cách.
Những gì chúng tôi có thể làm là, chúng ta có thể vượt qua nó w, có nghĩa là ghi đè lên các tập tin nếu nó thoát ra,
Chúng tôi có thể vượt qua một một, mà họ thêm vào cuối của tập tin thay vì trọng nó,
hoặc chúng ta có thể xác định r, có nghĩa là, chúng ta hãy mở tập tin như là chỉ đọc.
Vì vậy, nếu chương trình cố gắng để thực hiện bất kỳ thay đổi vào tập tin,
la hét vào họ và không để cho họ làm điều đó.
Cuối cùng, khi chúng tôi đang thực hiện với các tập tin, thực hiện các hoạt động trên nó,
chúng ta cần phải chắc chắn rằng chúng tôi đóng file.
Và như vậy ở phần cuối của chương trình của bạn, bạn sẽ vượt qua chúng một lần nữa
tập tin này mà bạn đã mở, và chỉ cần đóng nó.
Vì vậy, đây là một cái gì đó quan trọng là bạn phải chắc chắn rằng bạn làm.
Vì vậy, nhớ bạn có thể mở một tập tin, sau đó bạn có thể ghi vào tập tin,
làm các hoạt động trong tập tin, nhưng sau đó bạn phải đóng các tập tin ở cuối.
>> Bất kỳ câu hỏi về tập tin cơ bản I / O? Vâng?
[Sinh viên câu hỏi, không thể hiểu]
Ngay ở đây. Câu hỏi là, tập tin này log.txt xuất hiện nơi nào?
Vâng, nếu bạn chỉ cần cho nó log.txt, nó tạo ra nó trong cùng thư mục với tập tin thực thi.
Vì vậy, nếu phổ cập như - >> [Sinh viên câu hỏi, không thể hiểu]
Vâng. Trong cùng một thư mục, hoặc trong cùng một thư mục, như bạn gọi nó.
Bây giờ bộ nhớ, ngăn xếp, và một đống.
Vì vậy, làm thế nào là bộ nhớ đặt ra trong máy tính?
Vâng, bạn có thể tưởng tượng bộ nhớ sắp xếp của khối này ở đây.
Và trong bộ nhớ chúng ta có những gì được gọi là heap bị mắc kẹt ở đó, và ngăn xếp ở dưới đó.
Và heap phát triển đi xuống và ngăn xếp phát triển đi lên.
Vì vậy, như Tommy đã đề cập - oh, tốt, và chúng tôi có 4 phân đoạn khác mà tôi sẽ nhận được để trong một giây -
Như Tommy đã nói trước đó, bạn biết chức năng của mình như thế nào tự gọi mình và gọi nhau?
Họ xây dựng loại này stack frame.
Vâng, nếu cuộc gọi chính foo foo được đặt trên stack.
Foo gọi bar, bar được đặt trên stack, mà được đặt trên stack sau.
Và khi họ trở về, họ từng được đưa ra khỏi stack.
Mỗi người trong số các địa điểm này và bộ nhớ giữ?
Vâng, hàng đầu, đó là phân khúc văn bản có chứa các chương trình riêng của mình.
Vì vậy, các mã máy, đó là có, một khi bạn biên dịch chương trình của bạn.
Tiếp theo, bất kỳ khởi tạo biến toàn cầu.
>> Vì vậy, bạn có các biến toàn cầu trong chương trình của bạn, và bạn nói giống như, một 5 =
được đặt vào phân khúc này, và ngay dưới đó,
bạn có bất kỳ uninitialized dữ liệu toàn cầu, mà chỉ là int một,
nhưng bạn không nói nó bằng bất cứ điều gì.
Nhận ra đây là những biến toàn cầu, vì vậy họ đang ở bên ngoài của chính.
Vì vậy, điều này có nghĩa là bất kỳ biến toàn cầu được công bố nhưng không được khởi tạo.
Vì vậy, những gì trong đống này? Cấp phát bộ nhớ bằng cách sử dụng malloc, chúng tôi sẽ nhận được để trong một ít.
Và cuối cùng, với stack bạn có bất kỳ biến địa phương
và bất kỳ chức năng, bạn có thể gọi trong bất kỳ các thông số của họ.
Điều cuối cùng, bạn không thực sự cần phải biết những gì các biến môi trường làm,
nhưng bất cứ khi nào bạn chạy chương trình, có là một cái gì đó liên quan, như
đây là tên người dùng của người chạy chương trình.
Và đó sẽ là loại ở phía dưới.
Trong điều kiện các địa chỉ bộ nhớ, mà là giá trị thập lục phân,
các giá trị vào đầu hàng đầu tại 0, và họ đi tất cả các con đường xuống phía dưới.
Trong trường hợp này, nếu bạn đang ở trên hệ thống 32-bit,
địa chỉ ở phía dưới là có được 0x, tiếp theo af, bởi vì đó là 32 bit,
đó là 8 byte, và trong trường hợp này 8 byte tương ứng với 8 chữ số thập lục phân.
Vì vậy, xuống đây bạn sẽ có, như, 0xffffff, và ở đó bạn sẽ có 0.
Vì vậy, con trỏ là gì? Một số bạn không có thể đã được bảo hiểm này trong phần trước.
nhưng chúng tôi đã đi qua nó trong bài giảng, do đó, một con trỏ chỉ là một kiểu dữ liệu
mà các cửa hàng, thay vì một số loại giá trị như 50, nó lưu các địa chỉ của một số vị trí trong bộ nhớ.
Giống như là bộ nhớ [khó hiểu].
Vì vậy, trong trường hợp này, những gì chúng tôi đã, chúng tôi có một con trỏ đến một số nguyên hoặc * một int,
và nó chứa địa chỉ này thập lục phân của 0xDEADBEEF.
>> Vì vậy, những gì chúng ta có là, bây giờ, con trỏ điểm tại một số vị trí trong bộ nhớ,
và đó chỉ là một giá trị 50 là bộ nhớ vị trí.
Trên một số hệ thống 32-bit, trên tất cả các hệ thống 32-bit, con trỏ mất bit 32 hoặc 4 byte.
Tuy nhiên, ví dụ, trên một hệ thống 64-bit, con trỏ là 64 bit.
Vì vậy, đó là một cái gì đó bạn sẽ muốn giữ lại trong tâm trí.
Vì vậy, trên một hệ thống đầu cuối-bit, con trỏ dài là bit cuối.
Con trỏ là loại khó tiêu hóa mà không có thêm những điều,
do đó, chúng ta hãy đi qua một ví dụ về cấp phát bộ nhớ động.
Cấp phát bộ nhớ động làm cho bạn, hoặc những gì chúng ta gọi malloc,
nó cho phép bạn phân bổ một số loại dữ liệu bên ngoài của các thiết lập.
Vì vậy, dữ liệu này là loại lâu dài hơn trong suốt thời gian của chương trình.
Bởi vì như bạn biết, nếu bạn khai báo x bên trong của một chức năng, và trả về chức năng,
bạn không còn phải truy cập vào các dữ liệu đã được lưu trữ trong x.
Những gì con trỏ cho chúng tôi làm là họ cho phép chúng tôi lưu trữ bộ nhớ hoặc lưu trữ các giá trị
trong một phân đoạn khác nhau của bộ nhớ, cụ thể là các đống.
Bây giờ khi chúng ta trở lại ra khỏi chức năng, miễn là chúng ta có một con trỏ
vị trí đó trong bộ nhớ, sau đó những gì chúng ta có thể làm là chúng ta chỉ có thể nhìn vào các giá trị đó.
Hãy xem một ví dụ: Đây là bố trí bộ nhớ của chúng tôi một lần nữa.
Và chúng tôi có chức năng này, chính.
Những gì nó làm là được rồi, rất đơn giản, phải int x = 5, đó chỉ là một biến trên stack chính.
>> Mặt khác, bây giờ chúng ta khai báo một con trỏ mà các cuộc gọi giveMeThreeInts chức năng.
Và vì vậy bây giờ chúng ta đi vào chức năng này và chúng tôi tạo ra một khung stack mới cho nó.
Tuy nhiên, trong khung ngăn xếp, chúng ta khai báo int * temp,
mà mallocs 3 số nguyên cho chúng ta.
Vì vậy, kích thước của int sẽ cho chúng ta có bao nhiêu byte int này,
và malloc cho chúng ta nhiều byte của không gian trên heap.
Vì vậy, trong trường hợp này, chúng tôi đã tạo ra không gian đủ cho 3 số nguyên,
và heap là cách lên đó, đó là lý do tại sao tôi đã vẽ nó lên cao hơn.
Một khi chúng ta đã thực hiện xong, chúng tôi trở lại lên đây, bạn chỉ cần 3 ints quay trở lại,
và nó trả về địa chỉ, trong trường hợp này trên bộ nhớ mà.
Và chúng tôi đặt con trỏ = chuyển đổi, và trên đó chúng ta chỉ có một con trỏ.
Nhưng những gì mà trở về chức năng được xếp chồng lên nhau ở đây và biến mất.
Vì vậy, tạm thời biến mất, nhưng chúng tôi vẫn duy trì địa chỉ của nơi
3 số nguyên là bên trong của nguồn điện.
Vì vậy, trong bộ này, con trỏ scoped tại địa phương cho khung xếp chồng lên nhau,
nhưng bộ nhớ mà họ tham khảo trong heap.
>> Điều đó làm cho tinh thần?
[Sinh viên có thể lặp lại điều đó không? >> [Joseph].
Vì vậy, nếu tôi đi trở lại chỉ là một chút, bạn thấy rằng tạm thời phân bổ
một số bộ nhớ trên heap lên đó.
Vì vậy, khi chức năng này, giveMeThreeInts trở về, chồng này ở đây sẽ biến mất.
Và với bất kỳ của các biến, trong trường hợp này, con trỏ đã được phân bổ trong khung xếp chồng lên nhau.
Có nghĩa là sẽ biến mất, nhưng kể từ khi chúng tôi trở về nhiệt độ
và chúng tôi đặt con trỏ = temp, con trỏ sẽ chỉ cùng một bộ nhớ vị trí như temp.
Vì vậy, bây giờ, mặc dù chúng ta mất đi tạm thời, mà con trỏ địa phương,
chúng tôi vẫn giữ lại các địa chỉ bộ nhớ của những gì nó đã chỉ vào bên trong của con trỏ biến.
Câu hỏi? Đó có thể là của một chủ đề khó hiểu nếu bạn không đi qua nó trong phần.
Chúng ta có thể, TF của bạn chắc chắn sẽ đi qua nó và dĩ nhiên chúng tôi có thể trả lời các câu hỏi
ở phần cuối của phiên họp xem xét cho điều này.
Nhưng đây là sắp xếp của một chủ đề phức tạp, và tôi có nhiều ví dụ hơn sẽ hiển thị
sẽ giúp làm rõ những gì con trỏ thực sự đang có.
>> Trong trường hợp này, con trỏ tương đương với mảng,
vì vậy tôi chỉ có thể sử dụng con trỏ như là cùng một điều như là một mảng int.
Vì vậy, tôi lập chỉ mục vào 0, và thay đổi số nguyên đầu tiên là 1,
thay đổi số nguyên thứ hai là 2, và số nguyên thứ 3 đến 3.
Vì vậy, trên con trỏ. Vâng, nhớ lại Binky.
Trong trường hợp này, chúng tôi đã phân bổ một con trỏ, hoặc chúng tôi tuyên bố một con trỏ,
nhưng ban đầu, khi tôi chỉ tuyên bố một con trỏ, nó không chỉ đến bất cứ nơi nào trong bộ nhớ.
Đó là giá trị rác bên trong của nó.
Vì vậy, tôi không có ý tưởng, nơi này con trỏ trỏ đến.
Nó có một địa chỉ mà chỉ là lấp đầy với 0 và 1 nơi mà nó bước đầu đã được tuyên bố.
Tôi không thể làm bất cứ điều gì với điều này cho đến khi tôi gọi malloc vào nó
và sau đó nó mang lại cho tôi một không gian nhỏ trên đống, nơi tôi có thể đặt giá trị bên trong.
Sau đó, một lần nữa, tôi không biết những gì bên trong của bộ nhớ này.
Vì vậy, điều đầu tiên tôi phải làm là kiểm tra xem hệ thống có đủ bộ nhớ
để cho tôi 1 số nguyên ở nơi đầu tiên, đó là lý do tại sao tôi làm điều này kiểm tra.
Nếu con trỏ là null, có nghĩa là nó không có đủ không gian hay một số lỗi khác xảy ra,
vì vậy tôi phải thoát ra khỏi chương trình của tôi.
Nhưng nếu nó đã thành công, bây giờ tôi có thể sử dụng con trỏ
và những gì * con trỏ theo địa chỉ ở đâu
nơi mà giá trị đó, và nó đặt nó bằng 1.
Vì vậy, ở đây, chúng tôi đang kiểm tra nếu là bộ nhớ tồn tại.
>> Một khi bạn biết nó tồn tại, bạn có thể đưa vào nó
những gì giá trị mà bạn muốn đưa vào nó, trong trường hợp này 1.
Khi chúng tôi đang thực hiện với nó, bạn cần phải giải phóng con trỏ
bởi vì chúng tôi cần để có được trở lại hệ thống mà bộ nhớ mà bạn yêu cầu ở nơi đầu tiên.
Bởi vì máy tính không biết khi chúng tôi đang thực hiện với nó.
Trong trường hợp này, chúng tôi đang rõ ràng nói cho nó, không sao, chúng tôi đang thực hiện với bộ nhớ đó.
Nếu một số quy trình khác cần nó, một số chương trình khác cần nó, cảm thấy tự do để đi trước và mang nó.
Những gì chúng tôi cũng có thể làm là chúng ta chỉ có thể có được địa chỉ của các biến địa phương thiết lập.
Vì vậy, int x là bên trong khung xếp chồng lên nhau của chính.
Và khi chúng ta sử dụng ký hiệu này, và nhà điều hành, những gì nó làm là
phải mất x, và x là một số dữ liệu trong bộ nhớ, nhưng nó có một địa chỉ.
Nó nằm ở một nơi nào đó. Vì vậy, bằng cách gọi điện thoại & x, điều này không là nó mang lại cho chúng tôi địa chỉ của x.
Bằng cách này, chúng tôi đang làm điểm con trỏ trong đó x là trong bộ nhớ.
Bây giờ chúng ta chỉ cần làm một cái gì đó như * x, chúng ta sẽ nhận được 5 trở lại.
Ngôi sao này được gọi là dereferencing nó.
Bạn làm theo các địa chỉ và bạn sẽ có được giá trị của nó được lưu giữ tại đó.
>> Bất kỳ câu hỏi nào? Vâng?
[Sinh viên] Nếu bạn không làm điều 3-cánh, nó vẫn biên dịch?
Vâng. Nếu bạn không làm điều 3-con trỏ, nó vẫn sẽ để biên dịch,
nhưng tôi sẽ cho bạn thấy những gì xảy ra trong một giây, và không làm điều đó,
đó là những gì chúng ta gọi là rò rỉ bộ nhớ. Bạn không cho hệ thống
sao bộ nhớ của nó, vì vậy sau một thời gian chương trình sẽ tích lũy
nhớ mà nó sử dụng, và không có gì khác có thể sử dụng nó.
Nếu bạn đã từng nhìn thấy Firefox với 1,5 triệu kilobytes trên máy tính của bạn,
trong công việc quản lý, đó là những gì đang xảy ra.
Bạn có một rò rỉ bộ nhớ trong chương trình rằng họ đang không xử lý.
Vì vậy, làm thế nào để con trỏ số học làm việc?
Vâng, con trỏ số học là sắp xếp các chỉ mục như vào một mảng.
Trong trường hợp này, tôi có một con trỏ, và những gì tôi làm là tôi làm cho điểm con trỏ đến các yếu tố đầu tiên
mảng này của 3 số nguyên mà tôi đã được phân bổ.
Vì vậy, bây giờ những gì tôi làm, sao con trỏ chỉ thay đổi phần tử đầu tiên trong danh sách.
Sao con trỏ +1 điểm trên đây.
Vì vậy, con trỏ là ở đây, con trỏ +1 là ở đây, con trỏ 2 là ở đây.
>> Vì vậy, chỉ cần thêm 1 điều tương tự như di chuyển dọc theo mảng này.
Những gì chúng tôi làm là, khi chúng ta làm con trỏ 1 bạn sẽ có được địa chỉ trên đây,
và để có được giá trị ở đây, bạn đặt một ngôi sao trong toàn bộ biểu thức
để dereference nó.
Vì vậy, trong trường hợp này, tôi đang thiết lập vị trí đầu tiên trong mảng này là 1,
2 vị trí 2, và vị trí thứ ba đến 3.
Sau đó, những gì tôi đang làm ở đây là tôi đang in con trỏ của chúng tôi 1,
mà chỉ mang lại cho tôi 2.
Bây giờ tôi đang incrementing con trỏ, vì vậy con trỏ bằng con trỏ 1,
trong đó di chuyển nó về phía trước.
Và vì vậy bây giờ nếu tôi in ra con trỏ 1, con trỏ +1 là 3,
mà trong trường hợp này in ra 3.
Và để một cái gì đó miễn phí, con trỏ mà tôi cung cấp cho nó
phải được trỏ vào đầu của mảng mà tôi nhận được trở lại từ malloc.
Vì vậy, trong trường hợp này, nếu tôi được gọi 3 ngay tại đây, điều này sẽ không được quyền,
bởi vì nó ở giữa của mảng.
Tôi phải trừ đi để có được vị trí ban đầu
vị trí ban đầu trước khi tôi có thể miễn phí.
Vì vậy, đây là một ví dụ liên quan đến nhiều hơn.
Trong trường hợp này, chúng tôi đang phân bổ 7 ký tự trong một mảng ký tự.
>> Và trong trường hợp này những gì chúng tôi đang làm là chúng ta đang Looping hơn 6 tháng đầu năm của họ,
và chúng tôi đang thiết lập cho họ đến Z.
Vì vậy, cho int i = 0, i> 6, i + +,
Vì vậy, con trỏ + i sẽ chỉ cung cấp cho chúng tôi, trong trường hợp này,
con trỏ, +1 con trỏ, +2 con trỏ, con trỏ 3, và vv và vv trong vòng lặp.
Những gì nó sẽ làm gì là nó được địa chỉ đó, dereferences nó để có được giá trị,
và thay đổi giá trị cho một Z.
Sau đó, vào cuối nhớ những điều này là một chuỗi, phải không?
Tất cả các chuỗi có kết thúc với các ký tự chấm dứt vô giá trị.
Vì vậy, những gì tôi làm là trong con trỏ 6 tôi đặt nhân vật terminator vô giá trị.
Và bây giờ về cơ bản những gì tôi đang làm ở đây đang thực hiện printf cho một chuỗi, phải không?
>> Vì vậy, khi printf bây giờ khi nó đạt đến kết thúc của một chuỗi?
Khi nó chạm vào nhân vật chấm dứt vô giá trị.
Vì vậy, trong trường hợp này, con trỏ điểm ban đầu của tôi để bắt đầu của mảng này.
Tôi in các ký tự đầu tiên. Tôi di chuyển nó trên một.
Tôi in rằng nhân vật. Tôi di chuyển nó trên.
Và tôi tiếp tục làm điều này cho đến khi tôi đạt được kết thúc.
Và bây giờ * kết thúc con trỏ dereference này và chấm dứt được những nhân vật vô giá trị trở lại.
Và do đó, vòng lặp trong khi tôi chỉ chạy khi giá trị đó không phải là các ký tự null chấm dứt.
Vì vậy, bây giờ tôi thoát ra khỏi vòng lặp này.
Và vì vậy nếu tôi trừ đi 6 từ con trỏ này,
Tôi quay trở lại tất cả các cách để bắt đầu.
Hãy nhớ rằng, tôi đang làm điều này vì tôi phải đi đầu để giải phóng nó.
>> Vì vậy, tôi biết đó là rất nhiều. Có bất kỳ câu hỏi nào?
Xin vui lòng, đúng không?
[Sinh viên câu hỏi khó hiểu]
Bạn có thể nói to hơn? Xin lôi.
[Sinh viên] slide cuối cùng ngay trước khi bạn giải phóng con trỏ,
bạn thực sự thay đổi giá trị của con trỏ?
[Joseph] Vì vậy, ngay tại đây. >> [Sinh viên] Oh, okay.
[Joseph] Vì vậy, tôi có một con trỏ trừ trừ, phải,
trong đó di chuyển trở lại một điều, và sau đó tôi giải phóng nó,
bởi vì con trỏ này để được chỉ đầu của mảng.
[Sinh viên] Nhưng điều đó sẽ không cần thiết bạn đã dừng lại sau khi dòng đó.
[Joseph] Vì vậy, nếu tôi đã dừng lại sau khi điều này, điều này sẽ được xem xét một rò rỉ bộ nhớ,
bởi vì tôi đã không chạy miễn phí.
[Sinh viên] [khó hiểu] sau khi ba dòng đầu tiên mà bạn đã có con trỏ 1 [khó hiểu].
[Joseph] Uh-huh. Vì vậy, câu hỏi có những gì?
Xin lôi. Không, không. Đi, đi, xin vui lòng.
[Sinh viên] Vì vậy, bạn không phải thay đổi giá trị của con trỏ.
Bạn sẽ không phải để làm con trỏ trừ trừ.
[Joseph] Vâng, chính xác.
Vì vậy, khi tôi làm con trỏ +1 và con trỏ 2,
Tôi không làm con trỏ bằng con trỏ 1.
Vì vậy, con trỏ chỉ những chuyến du lịch chỉ vào đầu của mảng.
Đó là chỉ khi tôi làm cộng với cộng với nó đặt giá trị trở lại bên trong con trỏ,
rằng nó thực sự di chuyển này cùng.
Được rồi.
Câu hỏi nhiều hơn?
>> Một lần nữa, nếu điều này là loại áp đảo, điều này sẽ được đề cập trong phiên giao dịch.
Yêu cầu giáo viên giảng dạy của bạn về nó, và chúng ta có thể trả lời các câu hỏi ở cuối.
Và thường chúng tôi không muốn làm điều này trừ.
Điều này có yêu cầu tôi theo dõi bao nhiêu tôi đã bù đắp trong mảng.
Vì vậy, nói chung, điều này chỉ là để giải thích cách làm việc của con trỏ số học.
Nhưng những gì chúng ta thường muốn làm là chúng tôi muốn tạo ra một bản sao của con trỏ,
và sau đó chúng tôi sẽ sử dụng bản sao khi chúng tôi đang di chuyển xung quanh trong chuỗi.
Vì vậy, trong trường hợp này, bạn sử dụng các bản sao để in toàn bộ chuỗi,
nhưng chúng tôi không phải làm như con trỏ trừ đi 6 hoặc theo dõi bao nhiêu chúng ta di chuyển này,
chỉ vì chúng tôi biết rằng bản gốc quan điểm của chúng tôi vẫn chỉ đầu của danh sách
và tất cả những gì chúng ta thay đổi là bản sao này.
Vì vậy, nói chung, thay đổi bản sao của con trỏ ban đầu của bạn.
Đừng cố gắng để sắp xếp như đừng thay đổi bản gốc.
Đang cố gắng để thay đổi các bản sao duy nhất của ban đầu của bạn.
Vì vậy, bạn nhận thấy khi chúng tôi vượt qua chuỗi thành printf
bạn không có để đặt một ngôi sao ở phía trước của nó như chúng tôi đã làm với tất cả các dereferences khác, phải không?
Vì vậy, nếu bạn in ra toàn bộ chuỗi% s hy vọng sẽ là một địa chỉ,
và trong trường hợp này là một con trỏ hoặc trong trường hợp này giống như một mảng kí tự.
>> Ký tự, char * s, và mảng là điều tương tự.
Con trỏ là ký tự, và mảng ký tự có cùng một điều.
Và như vậy, tất cả chúng ta phải làm là vượt qua trong con trỏ.
Chúng tôi không có để vượt qua trong như * con trỏ hoặc bất cứ điều gì như thế.
Vì vậy, mảng và con trỏ là điều tương tự.
Khi bạn đang làm một cái gì đó như x [y] trên đây để một mảng,
những gì nó đang làm dưới mui xe là nó nói rằng, được rồi, đó là một mảng ký tự,
do đó, nó là một con trỏ.
Và như vậy x là điều tương tự,
và do đó, những gì nó làm là nó cho biết thêm y x,
đó là điều tương tự như di chuyển về phía trước trong bộ nhớ rằng có rất nhiều.
Và bây giờ x + y cung cấp cho chúng tôi một số loại địa chỉ,
và chúng tôi dereference địa chỉ hoặc theo các mũi tên
vị trí đó trong bộ nhớ và chúng tôi nhận được giá trị của vị trí đó trong bộ nhớ.
Vì vậy, do đó, hai là chính xác những điều tương tự.
Nó chỉ là một đường cú pháp.
Họ làm điều tương tự. Họ săn syntactics khác nhau cho nhau.
>> Vì vậy, những gì có thể đi sai với con trỏ? Giống như, rất nhiều. Okay. Vì vậy, những điều xấu.
Một số những điều xấu bạn có thể làm được không kiểm tra nếu cuộc gọi malloc của bạn trả về null, phải không?
Trong trường hợp này, tôi đang yêu cầu hệ thống để cho tôi con số đó là những gì?
Giống như 2 tỷ lần 4, bởi vì kích thước của một số nguyên là 4 byte.
Tôi đang yêu cầu nó cho như 8 tỷ byte.
Tất nhiên máy tính của tôi không phải là đi để có thể cung cấp cho tôi rằng nhiều bộ nhớ trở lại.
Và chúng tôi đã không kiểm tra nếu điều này là vô giá trị, vì vậy khi chúng ta cố gắng dereference nó ở đó -
theo các mũi tên đến nơi mà nó sẽ - chúng tôi không có mà bộ nhớ.
Đây là những gì chúng ta gọi là dereferencing một con trỏ null.
Và điều này về cơ bản làm bạn segfault.
Đây là một trong những cách bạn có thể segfault.
Những điều xấu khác bạn có thể làm tốt.
Đó là dereferencing một con trỏ null. Okay.
Những thứ khác xấu - tốt, để sửa chữa mà bạn chỉ cần đặt một kiểm tra trong đó
để kiểm tra xem con trỏ là null
và thoát ra khỏi chương trình nếu nó xảy ra malloc trả về một con trỏ null.
Đó là truyện tranh xkcd. Mọi người sẽ hiểu nó ngay bây giờ. Phân loại của.
>> Vì vậy, bộ nhớ. Và tôi đã nói về điều này.
Chúng tôi kêu gọi malloc trong một vòng lặp, nhưng mỗi lần chúng tôi gọi malloc
chúng ta đang mất đi theo dõi các nơi này con trỏ trỏ đến,
bởi vì chúng tôi đang clobbering nó.
Vì vậy, các cuộc gọi ban đầu để malloc mang lại cho tôi bộ nhớ ở đây.
Con trỏ của tôi con trỏ này.
Bây giờ, tôi không giải phóng nó, vì vậy bây giờ tôi gọi malloc một lần nữa.
Bây giờ nó chỉ ở đây. Bây giờ bộ nhớ của tôi là chỉ ở đây.
Chỉ ở đây. Chỉ ở đây.
Nhưng tôi đã mất theo dõi các địa chỉ của tất cả các bộ nhớ hơn ở đây mà tôi được phân bổ.
Và vì vậy bây giờ tôi không có bất kỳ tài liệu tham khảo cho họ nữa.
Vì vậy, tôi không thể giải thoát họ bên ngoài vòng lặp này.
Và như vậy để sửa chữa một cái gì đó như thế này,
nếu bạn quên bộ nhớ miễn phí và bạn sẽ có được bộ nhớ bị rò rỉ này,
Bạn có để giải phóng bộ nhớ bên trong vòng lặp này một khi bạn đang thực hiện với nó.
Vâng, đây là những gì xảy ra. Tôi biết rất nhiều bạn ghét này.
Nhưng bây giờ - yay! Bạn nhận được 44.000 kilobyte.
Vì vậy, bạn giải phóng nó vào cuối của vòng lặp,
và đó sẽ chỉ miễn phí bộ nhớ mỗi lần.
Về cơ bản, chương trình của bạn không có một rò rỉ bộ nhớ nữa.
>> Và bây giờ cái gì khác bạn có thể làm là miễn phí một số bộ nhớ mà bạn đã yêu cầu hai lần.
Trong trường hợp này, bạn malloc một cái gì đó, bạn thay đổi giá trị của nó.
Giải phóng nó một lần bởi vì bạn nói bạn đang thực hiện với nó.
Nhưng sau đó chúng tôi đã giải phóng một lần nữa.
Đây là cái gì đó là khá xấu.
Nó sẽ không ban đầu segfault,
nhưng sau một thời gian điều này là nhấn đúp giải phóng này corrupts cấu trúc heap của bạn,
và bạn sẽ tìm hiểu thêm một chút về điều này nếu bạn chọn để có một lớp học như CS61.
Nhưng về cơ bản sau một thời gian máy tính của bạn sẽ bị lẫn lộn
về vị trí bộ nhớ là nó được lưu trữ ở đâu và ở đâu -
nơi dữ liệu được lưu trữ trong bộ nhớ.
Và do đó giải phóng một con trỏ hai lần là một điều xấu mà bạn không muốn làm.
>> Những thứ khác có thể đi sai là không sử dụng sizeof.
Vì vậy, trong trường hợp này bạn malloc 8 byte,
và đó là điều tương tự như hai số nguyên, phải không?
Vì vậy, đó là hoàn toàn an toàn, nhưng nó?
Vâng, như Lucas nói về kiến ​​trúc khác nhau,
số nguyên là độ dài khác nhau.
Vì vậy, trên các thiết bị mà bạn đang sử dụng, số nguyên là khoảng 4 byte,
nhưng trên một số hệ thống khác, họ có thể là 8 byte hoặc họ có thể là 16 byte.
Vì vậy, nếu tôi chỉ cần sử dụng con số này ở đây,
chương trình này có thể làm việc trên thiết bị,
nhưng nó sẽ không phân bổ đủ bộ nhớ trên một số hệ thống khác.
Trong trường hợp này, đây là những gì được sử dụng cho các nhà điều hành sizeof.
Khi chúng ta gọi sizeof (int), điều này không
nó cho chúng ta kích thước của một số nguyên trên hệ thống mà chương trình đang chạy.
Vì vậy, trong trường hợp này, sizeof (int) sẽ trở lại 4 trên một cái gì đó giống như thiết bị,
và bây giờ điều này sẽ 4 * 2 là 8,
mà chỉ là số lượng không gian cần thiết cho hai số nguyên.
Trên một hệ thống khác nhau, nếu một int là 16 byte hoặc 8 byte,
nó chỉ là để trở về byte đủ để lưu trữ số tiền đó.
>> Và cuối cùng, cấu trúc.
Vì vậy, nếu bạn muốn để lưu trữ một bảng sudoku trong bộ nhớ, làm thế nào chúng ta có thể làm điều này?
Bạn có thể nghĩ như một biến cho điều đầu tiên,
một biến cho điều thứ hai, một biến cho điều thứ ba,
một biến cho điều thứ tư - xấu, đúng không?
Vì vậy, một trong những cải tiến bạn có thể thực hiện trên đầu trang này là để thực hiện một mảng 9 x 9.
Đó là tốt, nhưng những gì nếu bạn muốn kết hợp những thứ khác với Ban sudoku
thích những gì khó khăn của hội đồng quản trị,
hay, ví dụ, điểm số của bạn là gì, hoặc có bao nhiêu thời gian nó đã đưa bạn giải quyết hội đồng quản trị này?
Vâng, những gì bạn có thể làm là bạn có thể tạo ra một cấu trúc.
Những gì tôi đang về cơ bản nói là tôi xác định cấu trúc này ở đây,
và tôi xác định một hội đồng quản trị sudoku trong đó bao gồm một hội đồng là 9 x 9.
>> Và những gì nó đã có con trỏ đến tên của các cấp.
Nó cũng có x và y, đó là những tọa độ của tôi ngay bây giờ.
Nó cũng đã dành thời gian [khó hiểu], và nó có tổng số di chuyển tôi đã đầu vào cho đến nay.
Và như vậy trong trường hợp này, tôi có thể nhóm một bó toàn bộ dữ liệu vào cơ cấu chỉ là một
thay vì nó giống như đang bay xung quanh như các biến khác nhau
mà tôi có thể không thực sự theo dõi.
Và điều này cho phép chúng tôi có chỉ là cú pháp tốt đẹp cho loại tham khảo những điều khác nhau bên trong của cấu trúc này.
Tôi chỉ có thể làm board.board, và tôi nhận được hội đồng quản trị sudoku trở lại.
Board.level, tôi nhận được nó khó khăn như thế nào.
Board.x và board.y cung cấp cho tôi các tọa độ của nơi mà tôi có thể có trong hội đồng quản trị.
Và vì vậy tôi đang truy cập những gì chúng ta gọi là các lĩnh vực trong một cấu trúc.
Này định nghĩa sudokuBoard, mà là một loại mà tôi có.
Và bây giờ chúng tôi đang ở đây. Tôi có một biến được gọi là "hội đồng" của sudokuBoard loại.
Và vì vậy bây giờ tôi có thể truy cập vào tất cả các lĩnh vực tạo nên cấu trúc này ở đây.
>> Bất kỳ câu hỏi về cấu trúc? Vâng?
[Sinh viên] int x, y, bạn tuyên bố cả hai trên cùng một dòng? >> [Joseph] Uh-huh.
[Sinh viên] Vì vậy, có thể bạn chỉ cần làm điều đó với tất cả chúng?
Giống như trong x, y lần dấu phẩy, tổng?
[Joseph] Có, bạn chắc chắn có thể làm điều đó, nhưng lý do tôi đặt x và y trên cùng một dòng -
và câu hỏi là tại sao chúng ta có thể chỉ làm điều này trên cùng một dòng?
Tại sao chúng ta không chỉ cần đặt tất cả các trên cùng một dòng
x và y có liên quan với nhau,
và đây chỉ là phong cách chính xác hơn, trong một cảm giác,
bởi vì nó được nhóm hai điều trên cùng một dòng
mà loại như của liên quan đến cùng một điều.
Và tôi chỉ cần chia những ngoài. Nó chỉ là một điều phong cách.
Nó có chức năng làm cho không có sự khác biệt gì.
Bất kỳ các câu hỏi về cấu trúc?
Bạn có thể xác định một Pokédex với một cấu trúc.
Pokémon có một số và nó có một lá thư, một chủ sở hữu, một loại.
Và sau đó nếu bạn có một mảng của Pokémon, bạn có thể tạo nên một chiếc Pokédex, phải không?
Được rồi, mát mẻ. Vì vậy, câu hỏi về cấu trúc. Đó là những liên quan đến cấu trúc.
>> Cuối cùng, GDB. GDB cho phép bạn làm gì? Nó cho phép bạn gỡ lỗi chương trình của bạn.
Và nếu bạn đã không sử dụng GDB, tôi sẽ đề nghị xem ngắn
và chỉ cần đi qua GDB là gì, làm thế nào bạn làm việc với nó, làm thế nào bạn có thể sử dụng nó,
và thử nghiệm nó trên một chương trình.
Và vì vậy những gì GDB cho phép bạn làm là nó cho phép tạm dừng [khó hiểu] của bạn chương trình
và một dòng thực tế.
Ví dụ, tôi muốn tạm dừng thực hiện tại như dòng 3 của chương trình của tôi,
và khi tôi đang ở dòng 3, tôi có thể in ra tất cả các giá trị được ở đó.
Và do đó, những gì chúng ta gọi như tạm dừng trong một dòng
là chúng tôi gọi đây là đặt một breakpoint tại dòng đó
và sau đó chúng tôi có thể in ra các biến trạng thái của chương trình tại thời điểm đó.
>> Sau đó chúng ta có thể từ đó bước thông qua các chương trình dòng-by-line.
Và sau đó chúng ta có thể nhìn vào tình trạng của chồng lúc đó.
Và vì vậy để sử dụng GDB, những gì chúng tôi làm là chúng ta gọi là kêu vang trên các tập tin C,
nhưng chúng ta phải vượt qua nó ggdb-flag.
Và một khi chúng tôi đang thực hiện với điều đó, chúng tôi chỉ cần chạy gdb trên các tập tin đầu ra kết quả.
Và như vậy bạn nhận được một số đại chúng như văn bản như thế này,
nhưng thực sự tất cả những gì bạn phải làm là nhập vào lệnh ngay từ đầu.
Phá vỡ chính đặt một breakpoint chính.
Danh sách 400 liệt kê các dòng mã xung quanh dòng 400.
Và như vậy trong trường hợp này, bạn có thể chỉ cần nhìn xung quanh và nói, oh,
Tôi muốn thiết lập một breakpoint tại dòng 397, đó là dòng này,
và sau đó chương trình của bạn chạy vào bước đó và nó sẽ phá vỡ.
Nó sẽ tạm dừng ở đó, và bạn có thể in ra, ví dụ, giá trị thấp hoặc cao.
Và do đó, là một loạt các lệnh bạn cần phải biết,
và xem hình tự động này sẽ đi lên trên trang web,
vì vậy nếu bạn chỉ muốn tham khảo những hoặc như đặt chúng trên tờ cheat của bạn, cảm thấy tự do.
>> Cool. Đó là Câu đố Đánh giá 0, và chúng tôi sẽ dính xung quanh nếu bạn có bất kỳ câu hỏi nào.
Được rồi.
>> [Vỗ tay]
>> [CS50.TV]