[음악 연주] 데이비드 J. 마란 : 좋습니다. 이 CS50이다. 이 주 오 계속, 그리고 우리 좋은 소식과 나쁜 소식이있다. 그래서 좋은 소식은 CS50입니다 이 금요일 시작합니다. 당신이 우리와 함께하고 싶은 경우, 여기에 일반적인 URL로 향한다. 더 나은 뉴스, 어떤 강의가 없습니다 이는 13 일 월요일오고. 약간 덜 더 나은 뉴스, 퀴즈 제로는 다음주 수요일입니다. 추가 사항이 될 수 있습니다 여기에이 URL에서 발견했다. 그리고 다음 몇 일 동안 우리는 빈칸을 채우는거야 객실에 관해서 우리가 예약 한 것이다. 더 좋은 소식이있을 것이 오 물론 전체를 검토 할 수 세션은 오는 저녁에 월요일. 과정의에 계속 지켜봐 주시기 바랍니다 위치 및 자세한 내용은 웹 사이트. 그것은을하더라도 섹션 휴일, 또한뿐만 아니라 만날 것입니다. 최고의 소식은 다음주 금요일 강의. 그래서이 전통 우리는 강의 계획서에 따라 보유하고 있습니다. 그냥 ... 그것은 훌륭 할 것입니다. 당신은 같은 일을 볼 수 있습니다 일정 시간의 데이터 구조 및 해시 테이블과 나무와 시도. 그리고 우리는 생일 문제에 대해 이야기 할 것입니다. 물건의 전체 무리 다음주 금요일이 기다리고있다. 확인을 클릭합니다. 어쨌든. 그래서 우리는 봤는데 리콜 무엇이이 그림에 초점을 맞추고 우리의 컴퓨터의 메모리 내부. 그래서 메모리 또는 RAM 어디 프로그램입니다 당신이 그들을 실행하는 동안 존재한다. 당신을 두 번 클릭하면 아이콘은 어떤 프로그램을 실행하려면 또는을 두 번 클릭 일부 파일을 열려면 아이콘, 그것은 하드에서 장전 드라이브 또는 솔리드 스테이트 드라이브 RAM, 랜덤 액세스 메모리로 전원이 꺼질 때까지 그것은 삶 노트북 뚜껑이 닫히고 또는 당신은 프로그램을 종료합니다. 이제 메모리의 하는 당신은 아마이 1기가바이트 요즘,이 기가 바이트, 또는 더 많은, 일반적으로 뻗어있다 주어진 프로그램에 대한 직사각형의 이런 종류의 개념 모델 우리는 맨 아래에있는 스택을 가지고있다 상단에서 다른 물건을 무리. 매우 상단에있는 것은 우리는이 사진을 본 적이 전에 그러나 결코에 대한 이야기 소위 텍스트 세그먼트이다. 텍스트 세그먼트는 단지 멋진 방법입니다 0과 말의 실제 컴파일 된 프로그램을 구성한다. 그래서 때를 두 번 클릭 Mac 또는 PC에 마이크로 소프트 워드, 이 점을 실행할 때 나에 마리오를 슬래시 터미널 창에서 Linux 컴퓨터, 구성하는 0과 1 Word 또는 마리오 일시적으로 저장된다 소위에서 컴퓨터의 RAM에 특정 프로그램에 대한 텍스트 세그먼트. 그가는 아래 초기화 초기화되지 않은 데이터입니다. 이 전역 변수 같은 물건입니다, 우리가 많이 사용되지으니, 하지만 경우에 우리는했습니다 전역 변수를했다 또는 정적 문자열을 정의한 하드 "안녕하세요"와 같은 단어를 부호화 사용자로부터 도입되지 않은 그 프로그램에 하드 코딩되어 있습니다. 이제, 아래로 아래에 우리 소위 스택을 가지고있다. 그리고 스택은, 지금까지, 우리는 봤는데 목적의 종류에 사용? 스택은 무엇을 사용하고있어? 그래? 청중 : 기능. 데이비드 J. 마란 : 함수의? 기능에 대한 어떤 의미에서? 청중 : 당신이 함수를 호출 할 때, 인수는 스택에 복사됩니다. 데이비드 J. 마란 : 그렇지. 당신은 함수를 호출 할 때, 그것을 인수는 스택에 복사됩니다. 그래서 어떤 X의 나 Y 나 나 B의 당신은 함수로 전달하고 있는지 일시적으로 배치됩니다 소위 스택, 단지 아넨 버그의 같은 식당 트레이, 또한 일 지역 변수 등을들 수있다. 만약 당신의 foo는 함수 또는 스왑 함수는 지역 변수를 가지고, 온도와 같은, 두 스택에 끝낸다. 이제, 우리는에 대해 말을 너무 많이하지 않습니다 그들,하지만 이러한 환경 변수 하단에 우리는 얼마 전에 때 보았다 나는 키보드 일일에서 작업을했으며 나는 일을 액세스 시작 변수는 argv 100 argv에 1000 등, 단지 elements-- 잊지 숫자들하지만 나에 액세스 할 예정되지 않았다. 우리는 몇 가지를보기 시작 화면에 펑키 기호입니다. 사람들은 소위이었다 환경 변수 글로벌 설정과 같은 내 프로그램이나 컴퓨터,하지 않는 최근 관련이없는 우리가 논의 버그, Shellshock, 그되었습니다 대부분의 컴퓨터를 괴롭 히고. 이제 마지막으로 오늘의 초점 우리는 궁극적으로 힙에있을 것이다. 이 메모리의 또 다른 덩어리이다. 그리고 기본적으로 모든 메모리는 동일한 재료이다. 그것은 동일한 하드웨어이다. 우리는 일종의 그저 다른 클러스터 치료 의 다른 목적 바이트. 힙은 또한 위치가 될 것입니다 당신이 요청 변수와 메모리 운영 체제에서 일시적으로 저장됩니다. 그러나 문제 가지있다 여기, 그림에서 알 수 있듯이. 우리는 종류의 두가 에 대한 선박 충돌합니다. 당신은 점점 더 사용으로 인해 오늘날 우리가 볼 수있는 스택과 같이 이후, 당신은 점점 더 많은을 사용할 때 힙, 반드시 나쁜 일이 일어날 수 있습니다. 그리고 실제로, 우리는 그것을 유도 할 수있다 고의 또는 실수로. 마지막 클리프 행어 그래서 시간은이 프로그램이었다, 모든 기능을 제공하지 않았다 증명하는 것 이외의 목적을 방법을 나쁜 사람이 실제로 취할 수있는 다른 사람의 프로그램 버그의 장점 심지어 프로그램 또는 인수 전체 컴퓨터 시스템 또는 서버. 그러니 그냥 눈에 잠시 당신을 맨 아래에있는 그 주를 주목 명령 줄에서 소요 argv에 따라 인수. 그리고 그것은 함수 f에 대한 호출을 가지고 기본적으로 이름없는 함수가 호출 f를하고 argv를 전달 정보 [1]. 그래서에서의 어떤 단어를 사용자 유형 이 프로그램의 이름 뒤에 프롬프트 그리고 다음이 임의 함수 닫 위, f는 문자열에 소요 AKA 숯불 * 우리가 논의하기 시작했습니다로서, 그리고 그것은 단지 "바 '이래. 그러나 우리는 무엇을 호출 할 수 있습니다. 그리고, 그것은 내부에 선언 F, 문자의 배열 12 같은 문자 c--했다. 자, 이야기가 나는 말하고 있었다 조금 전에 여기서 메모리에 C, 또는 그 12 아르 끝날 것 문자? 그냥 명확합니다. 그래? 청중 : 스택에. 데이비드 J. 마란 : 스택에. 그래서 C는 지역 변수입니다. 우리는 12 문자 또는 12 바이트를 요구하고 있습니다. 사람들은 결국 예정 소위 스택에. 이제 마지막이 다른 기능입니다 즉, 실제로 꽤 유용 그러나 우리는 정말 사용하지 않는 것 그것은 우리 자신, strncopy. 그것은, 문자열 복사를 의미하지만, 문자, n 개의 문자를 명. 따라서 n 개의 문자가 될 것입니다 C로 표시 줄에서 복사. 그리고 얼마나 많은? 바의 길이입니다. 따라서 환언하면, 그 한 줄, strncopy, 복사 할 것입니다 효과적으로 C에 바. 자, 그냥 가지 예상 이 이야기의 도덕적, 무슨 일이 잠재적으로 문제가있다? 우리는 길이를 확인하고 있지만 바의와 strncopy로 전달 무엇이 당신 직감은 말하고있다 아직이 프로그램에 대해 깨진? 그래? 청중 : 포함되지 않습니다 널 문자를위한 공간. 데이비드 J. 마란 : 포함되지 않습니다 널 문자를위한 공간. 에서 잠재적으로 달리 과거의 관행에도 못 할 이 플러스 일에 관해서는 너무 많은 그 널 문자를 수용. 그러나 그것보다 더 악화. 또 우리는 무엇을 실패하고? 그래? 청중 : [들리지] 데이비드 J. 마란 : 완벽 한. 우리는 하드 꽤 임의로 12 코딩했습니다. 즉, 너무 많이하지 않습니다 문제가 있지만, 실제로 우리는 경우에도 검사를하지 않을 것을 막대의 길이는, 12 이하 이 경우이 될 것 메모리에 넣어 안전 우리가 할당 한 전화 다. 실제로, 바 같은 경우 길이 20 자, 이 기능은 복사하는 것으로 나타납니다 따라서 C로 표시 줄에서 20 자 적어도 8 바이트를 사용 그것은하지 않을 것을. 즉, 여기에 의미합니다. 짧은 깨진 프로그램 그래서. 큰 문제 같은 것은 아닙니다. 어쩌면 당신은 세그먼트 오류를​​ 얻을. 우리는 모든 프로그램에서 버그를 했어. 우리 모두는 버그가있을 수 있습니다 지금 프로그램. 그러나 의미는 무엇입니까? 음, 여기의 확대 버전을하다 내 컴퓨터의 메모리의 사진입니다. 이것은 내 스택의 바닥이다. 그리고 실제로, 맨 아래에 무엇입니다 라는 부모 루틴 스택, 멋진 방법 의 메인 말하는 것. 기능이라고 누구든지 그 그래서 우리가 이야기하고있는 바. 그래서이 스택의 바닥이다. 반환 주소는 새로운 무언가이다. 그것은 항상 거기에 있었어요 항상 그 사진에 있었다. 우리는 관심을 호출되지 단지 않았다. 알고 보니 때문에 C의 작동 방식은 일 함수가 서로 호출 할 때, 뿐만 아니라에 대한 인수 작업을 수행 함수가 스택으로 푸시 얻을, 뿐만 아니라 함수의 지역 할 변수는 스택으로 푸시 얻을, 뭔가 반환 주소라고 또한 스택에 배치됩니다. 특히, 주요 통화 foo는 경우, 기본의 메모리에 자신의 주소, 황소 뭔가, 효과적으로 스택에 넣어 도착 그래서 F는 그것을 실행 완료되면 텍스트로 다시 이동 위치를 알고 실행을 계속하기 위해 세그먼트. 우리가 개념적으로 여기 경우에 따라서, 메인에서, 다음 f를 호출된다. f를 알고 있지 어떻게 사람 다시 손을 제어? 음,이 작은 여기에 빨간색의 이동 경로, 반환 주소라고, 그것은 단지 수표, 그 반환 주소는 무엇인가? 아, 내가 다시 여기 메인에 점프 할 수 있습니다. 그리고 조금이다 지나친 단순화의, 0과 1 때문에 주요 기술적으로 아르 여기에 기술 부문에서 최대. 하지만 그 생각이다. F 단지 무엇을 알고있다 위치로 제어가 궁극적으로 거슬러 올라갑니다. 그러나 방법은 컴퓨터 긴 물건을 배치했다 지역 변수와 같은과 인수는 다음과 같이합니다. 이 그림의 상단에 따라서 파란색 그래서 모든 F에 대한 스택 프레임입니다 메모리의 F 구체적으로 사용하고 있습니다. 그래서 그에 따라, 알 바는이 사진에 있습니다. 바 인수했다. 그리고 우리는 주장 인수에 그 기능은 스택으로 푸시 얻는다. C는 물론, 이 그림에서. 그리고 그냥 표기를 위해, 왼쪽 상단 모서리에 알 브래킷 0 ℃ 무엇을 것하고 다음 약간 오른쪽 아래 C 브래킷 (11)이다. 그래서 다른 말로하면, 당신은 상상할 수 바이트의 격자가 있음 가있다 첫째있는 왼쪽 상단, 하단에있는의 이들 12 바이트의 마지막이다. 하지만 지금은 빨리하려고합니다. 어떻게 우리가 전달하는 경우 발생하는 약입니다 C보다 더 긴 문자열 표시 줄에? 그리고 우리는 경우 확인하지 않을 그것은 참 이상 12 이상입니다. 이 그림의 어떤 부분에 것입니다 바이트 0, 1, 2, 3으로 겹쳐 얻을 도트 도트 도트, 11 다음 나쁜, 12, 19을 통해 13? 어떻게 여기에 일어날 당신은 주문에서 추론하는 경우 그 C 브래킷 공은 상단에 및 C 브래킷 (11)은 아래의 일종 오른쪽? 그래? 청중 : 글쎄, 무슨 char *로 줄을 덮어 씁니다. 데이비드 J. 마란 : 네, 그것은처럼 보이는 당신은 문자 * 줄을 덮어 쓸 것입니다. 그리고 더 나쁜, 당신은 정말로 긴에 보내는 경우 문자열, 당신도 무엇을 덮어 쓸 수 있습니다? 반환 주소. 어느 다시, 단지처럼 프로그램 위치를 알려줄 이동 경로 때 F로 돌아갑니다 호출되고 수행된다. 그래서 나쁜 사람은 일반적으로 무엇을 그들이 프로그램에 걸쳐 올 경우입니다 그들은인지 궁금 것을 이러한 방법으로 악용, 버그 그 또는 그녀는 걸릴 수 있습니다 그 버그의 장점, 일반적으로 그들은 얻을하지 않습니다 이 권한 처음. 그들은 단지 예를 들어, 전송 시작 프로그램에 임의의 문자열, 키보드의 여부, 나 솔직히 그들은 아마 작은 프로그램을 작성 단지 자동으로 문자열 생성 에 의해 프로그램을 두드리는 시작 다른 입력의 제비에 전송 다른 길이에서. 즉시 당신의 프로그램이 충돌로, 그 놀라운 일입니다. 그가 의미하기 때문에 또는 그녀는 발견했다 무슨 일이 참으로 아마 버그입니다. 그리고 그들은 더 영리 얻을 수 있습니다 그리고 시작은 더 좁게 초점 이 버그를 악용하는 방법에 대한. 특히, 그가 또는 그녀는 수도 할 안녕하세요, 최상의 경우에 보낼 것이다. 특별한 건 없구요. 그것은 충분히 짧다 문자열입니다. 그러나 그 또는 그녀가 보내는 경우, 우리는 그것을로 일반화 것 공격은 제로 있도록 code-- 그 사람은 일을 RM-RF처럼 모든 것을 제거하는 하드 드라이브 나 스팸 메일을 보낼 어떻게 든 컴퓨터를 공격? 이들 각각의 경우에 따라서 문자는 나타냅니다 개념적으로, 공격, 공격, 공격, 공격, 나쁜 코드 다른 사람이 쓴, 그러나 그 사람이 똑똑 경우 뿐만 아니라 모든 포함 그러한 RM-RFS의 아니라 자신의 지난 몇 바이트가 상당 수있을 주소 그의 혹은 그녀의 자신의 공격 코드 그 또는 그녀는 그냥 통과하는 것이 프롬프트를 제공함으로써, 효과적으로 컴퓨터를 속일 수 있습니다 F의 실행이 완료되면 몰래에, 오, 나 점프하기위한 시간이다 다시 빨간색 반환 주소. 그러나 그 또는 그녀가 어떻게 든이 있기 때문에 그 리턴 어드레스를 중복 자신의 번호, 그들은 충분히 똑똑 있음을 구성한하기 번호는 같이 참조합니다 슈퍼 상단에 표시 이 왼쪽 코너, 컴퓨터의의 실제 주소 자신의 공격 코드의 일부 메모리, 나쁜 사람은 컴퓨터를 속일 수 있습니다 자신의 코드를 실행에. 그리고 그 코드는 다시, 무엇이든 될 수있다. 그것은 일반적이라고 단지입니다 쉘 코드, 그렇지 않은 것을 말하는 방법 RM-RF만큼 간단 일반적으로 뭔가. 그것은 실제로 배쉬 같은 뭔가 또는 실제 프로그램 그를 준다 혹은 그녀의 프로그램 제어 실행하기 그들이 원하는 것을 아무것도. 그래서 짧은,이 모든 단순한 사실에서 유래 관련이 버그는 확인하지 않는 것이 배열의 경계. 그리고 그 길 때문에 컴퓨터 작업은 그들이 에서 스택을 사용 효과적으로, 개념적 최대에 바닥하지만 요소 당신은 상단을 아래로 성장 스택에 푸시 이 믿을 수 없을만큼 문제가있다. 자,이 문제를 해결하는 방법이 있습니다. 그리고 솔직히, 언어가있다 있는이 문제를 해결합니다. 자바는, 예를 들어, 면역 이 특정 문제에. 그들이 당신에게 포인터를 제공하지 않습니다 때문입니다. 그들은 당신에게 제공하지 않습니다 직접 메모리 주소. 우리가이 전원 그래서 메모리에 아무것도 만지지 우리는 인정 하듯이, 큰 위험, 제공 할 수 있습니다. 그래서 눈을 밖으로 유지. 솔직히 경우 개월 또는 년은 언제 올 당신은 어떤 착취에 대해 읽어 프로그램 또는 서버, 당신은 무언가의 힌트를 참조하는 경우 버퍼 오버 플로우 공격과 같은, 또는 스택 오버 플로우는 또 다른 유형입니다 공격, 정신에는 변함이, 웹 사이트의 영감으로 많은 당신이 그것을 알고 있다면, 이름, 모든 단지에 대해서 이야기 일부 문자의 크기를 넘쳐 배열 또는 더 일반적으로 어떤 배열입니다. 여기에 다음 질문,,? 집에서 시도하지 마십시오. 좋아. 그래서 malloc에​​ 지금까지 우리의 새로운을하고있다 우리가 메모리를 할당 할 수 있다는 점에서 친구 우리는 필요에 모르는 우리는 우리가하지 않아도 원하는 사전 에 하드 코드에 대한 우리의 12 같은 프로그램 번호. 사용자는 우리에게 얼마나 알려줍니다되면 그 또는 그녀가 원하는 입력 데이터, 우리는 그 많은 메모리를 malloc을 할 수 있습니다. 그래서 malloc에​​ 그것은에 밝혀 우리가 사용하고 정도, 명시 전회 다음 너희들은 그것을 사용하고있다 에 대한 무의식적 getString에 대한 몇 주, malloc에​​의 모든 메모리 소위 힙에서 비롯됩니다. 그리고 이것은 예를 들어, 왜있는 getString입니다 동적으로 메모리를 할당 할 수 있습니다 넌 모르고 사전에 입력 한 것, 이 메모리에 다시 포인터를 손으로, 그 기억은 당신이 계속 여전히, 도 수익을 getString에 후. 때문에 리콜 후 모든 스택은 끊임없이 위로 추락 상하. 그리고 즉시이 간다 아래로, 즉 메모리를 의미한다 사용이 기능해야 다른 사람이 사용할 수 없습니다. 지금은 쓰레기 값을합니다. 그러나 힙이 여기에있다. 그리고 malloc에​​가 있다는 것입니다에 대한 좋은거야 malloc에​​ 여기에 메모리를 할당 할 때, 이를 위해, 영향을받지 것 스택에 의해 대부분. 그래서 어떤 기능에 액세스 할 수 있습니다 다음 malloc 된 메모리, 심지어 getstring를 같은 기능에 의해, 후에도이 반환됩니다. 이제, malloc에​​의 반대는 무료입니다. 그리고 실제로, 규칙 당신에게 채택 시작해야 모든, 모든, 당신이 malloc을을 사용하는 시간이다 당신은 자신이 결국, 무​​료 사용해야합니다 같은 포인터. 우리는 기록 된 모든이 시간 버그, 여러 가지 이유로 버그 코드. 그러나 중 하나가되었습니다 CS50 라이브러리를 사용하는 자체는 의도적입니다 버그, 그것은 메모리 누수. 당신이 getstring를 호출 한 모든 시간 지난 몇 주 동안 우리가 운영을 요구하고 시스템, 리눅스, 메모리. 그리고 당신은 한 번 다시 준 적이있다. 그리고이에없는 좋은 일을 연습 할 수 있습니다. 그리고 Valgrind의, 하나의 Pset에 4에 도입 된 도구, 당신을 돕는에 대한 모든입니다 지금과 같은 버그를 찾을 수 있습니다. 그러나 다행히도 Pset에 4 당신은 필요가 없습니다 CS50 라이브러리 나있는 getString를 사용합니다. 그래서 메모리와 관련된 버그가 있습니다 궁극적으로 자신이 될 것. 그래서 malloc에​​는 이상입니다 이 목적을 위해 편리합니다. 우리는 실제로 지금 해결할 수 근본적으로 다른 문제 근본적으로 많은 문제를 해결 효율적 주 제로의 약속에 따라. 지금까지이 섹시한입니다 데이터 구조는 우리가 했어. 그리고 자료 구조로 그냥 의미 개념화 메모리 방법 단지 말을 뛰어 넘는 방법으로, 이것은이 문자이며, int이며. 우리는 함께 클러스터 것들을 시작할 수 있습니다. 그래서 배열이처럼 보였다. 그리고 약의 주요 것이었다 배열은 당신을 준다이다 백투백의 덩어리 메모리에, 각각의 같은 유형이 될 것입니다, 중간, 중간, 중간, 중간, 또는 문자, 문자, 문자, 문자. 그러나 몇 가지 단점이있다. 이것은 예를 들면, 크기 육의 배열. 당신이 육으로이 배열을 채우기 가정 숫자와 다음, 어떤 이유로, 사용자가주고 싶어 당신 칠분의 일 수입니다. 어디를 배치해야합니까? 당신이 가지고있는 경우 솔루션 기능 스택에 배열을 만들어, 예를 들면, 단지 주 함께 우리가 도입이 표기법 내 번호와 대괄호? 글쎄, 당신은 여섯있어 이 상자의 숫자. 당신의 본능은 어떤 것입니까? 어디 넣어할까요? 청중 : [들리지] 데이비드 J. 마란 : 죄송합니다? 관객 : 마지막에 넣습니다. 데이비드 J. 마란 : 결국에 넣습니다. 그러니 그냥 오른쪽에있는 이상, 이 상자의 외부. 어느 쪽이 좋은,하지만 것 당신이 할 수 없어 밝혀졌습니다. 당신이 물어 보지 한 경우 때문에 이 메모리 청크, 그것은이 그 우연의 일치가 될 수있다 다른 변수에 의해 사용되는 모두. 우리가 마련 할 때 그래서 주 다시 생각 나 Zamyla 및 다빈와 게이브의 이름 아웃 메모리. 그들은 문자 그대로 있었다 다시 다시 다시합니다. 그래서 우리는 반드시 할 수 없습니다 그 무엇의 신뢰 여기 내가 사용하는 것이 가능합니다. 그래서 당신은 다른 무엇을 할 수 있는가? 글쎄, 당신을 한 번 실현 크기 일곱의 배열이 필요 당신은 단지를 만들 수 있습니다 크기 일곱의 배열은 사용 루프 또는 while 루프에 대한, 새로운 배열에 복사, 다음 어떻게 든 그냥 없애 이 배열하거나 사용을 중지. 그러나 특히 효율적인 아니다. 즉, 배열은 두지 마세요 동적으로 크기를 조정합니다. 그래서 한편으로는 얻을 놀라운 랜덤 액세스. 그것을 할 수 있기 때문에 우리는 일을 분열과 정복 등 우리가했습니다 모두 이진 검색, 여기에 화면에 대한 이야기​​. 하지만 당신은 구석에 자신을 칠합니다. 즉시 히트로 배열의 끝, 당신은 아주 할 필요가 비용이 많이 드는 작업 또는 코드의 전체 무리 쓰기 지금 문제를 해결한다. 그래서 그 대신 경우 우리는 한 무슨 뭔가 목록을 호출, 또는 특히 목록을 연결? 어떤 경우 대신 갖는 사각형, 다시 다시 다시 우리는 조금두고 사각형을 그들 사이 재량권의 비트? 비록 내가이 그려진 것 사진이나이 사진을 적응 텍스트 중 하나에서 다시 여기에있을 수 있습니다 다시 현실에서 매우 질서 백업하려면 그 사각형의 한 여기까지 메모리에있을 수 있습니다. 그 중 하나는 여기에있을 수 있습니다. 그 중 하나는 여기에있을 수 여기서, 등 위에. 그러나 우리가 그린 그림을 경우 이 경우, 화살표 어떻게 든 이들을 연결하는 것이 함께 사각형? 사실, 우리는 기술을 봤어요 화살표의 화신. 우리가 최근에 사용한 일이 후드 아래, 화살표의 대표? 포인터, 오른쪽? 그래, 내가 대신 단지 숫자를 저장 같은 9, 17, 22, 26, 34, 우리는 무엇을하지 저장 경우 숫자 만 아니라 포인터 이러한 각 번호 옆에? 그래서 많은 당신이 스레드 것처럼 직물의 전체 무리를 통해 바늘, 어떻게 든 동점 일 함께 유사 할 수 포인터 등으로 우리 여기에 화살표로 성육신, 가지 짜 이러한 개별 사각형 효과적으로 포인터를 이용하여 각 번호 옆에 그 것으로, 일부 다음 수를 포인트 차례로, 약간의 다음 수를 포인트? 따라서 환언하면, 무엇이 우리가 실제로 원하는 경우 이런 식으로 뭔가를 구현하는 방법? 그런데 불행하게도,이 사각형, 9 적어도 하나, 17, 22에서, 등이 더 이상 없다 하나의 숫자와 함께 좋은 사각형입니다. 바닥, 사각형 9 이하, 예를 들면, 무엇을 나타내는 지는해야 포인터, 32 비트 수. 지금, 나는 아직 모든 데이터 유형을 인식하지 않아요 C에서 그에게뿐만 아니라 int를 제공합니다 하지만 포인터 모두. 우리가 원하는 경우에 따라서 솔루션 무엇 이에 우리 자신의 대답을 발명? 그래? 청중 : [들리지] 데이비드 J. 마란 : 무엇입니까? 청중 : 새로운 구조입니다. 데이비드 J. 마란 : 그래, 왜 그렇게 우리는 새로운 구조를 생성하지 않습니다, 또는 C, 구조체? 우리는 경우 잠시 전에 구조체를 본 적이 우리는 학생 구조 처리 곳 과 같이 이름과 집을 가지고있는 사람. Pset에에서 3 브레이크 아웃 당신은 전체를 사용 structs-- GRect 및 GOvals의 무리 스탠포드에 만든 함께 클러스터 정보를 제공합니다. 그래서 우리는이 같은 생각을하는 경우 키워드 "형식 정의"와 "구조체" 다음 일부 학생 별 물건, 그리고 다음에이 진화 : 형식 정의 구조체 node-- 노드는 그냥 아주 일반적인 컴퓨터 과학 데이터 구조에 뭔가에 대한 용어 데이터 구조에서의 컨테이너. 내가 주장하는 노드는해야 할 것입니다 완전히 간단한 정수 n을, 다음 더 비밀스럽게 조금, 이 두 번째 줄, 구조체 노드 * 다음. 그러나 덜 기술적 인 측면에서, 그 두 번째 라인은 무엇인가 중괄호 안의 코드? 그래? 청중 : [들리지] 데이비드 J. 마란 : 다른 노드의 포인터. 그래서 일반적으로 인정 하듯이, 조금 애매한 구문. 하지만 당신은 문자 그대로 읽으면, 다음의 변수의 이름이다. 데이터 유형은 무엇입니까? 그것은,이 때 약간의 자세한이다 하지만 * 형 구조체 노드의입니다. 우리가 뭔가의 별을 본 적이 때마다, 그 는 해당 데이터 유형에 대한 포인터입니다 의미합니다. 그래서 다음에 분명히있다 구조체 노드의 포인터. 이제 구조체 노드는 무엇인가? 글쎄, 당신은 사람들을 볼주의 오른쪽 상단의 같은 단어입니다. 그리고 실제로, 당신은 또한 단어를 참조 여기 아래 왼쪽 하단에 "노드". 그리고이 사실은 단지 편리합니다. 우리가 학생의 정의에있는 것을 알 수 있습니다 한 번만 단어 "학생"이있다. 그리고 그 학생이 있기 때문이다 목적은 자기 참조하지 않았다. 학생의 내부에 아무것도 없어 즉 다른 학생을 가리 키도록해야합니다, persay. 그 종류의 것 현실 세계에서 이상. 그러나의 노드와 링크 목록, 우리는 노드를 원하는가 비슷한 개체에 참조 할 수 있습니다. 그리고 여기에 변화가없는 알 그냥 뭐 중괄호 내부입니다. 그러나 우리는 "노드"라는 단어를 추가 상단뿐만 아니라 아래에 추가 대신에 "학생." 그리고 이것은 단지 기술적 인 세부 사항입니다 그래서 다시, 데이터 구조 , 자기 참조가 될 수 있도록 노드는 같은 또 다른 노드를 가리킬 수 있습니다. 따라서이 궁극적으로 무엇인가 우리에게 의미하는 것? 음, 한,이 물건의 내부 우리 노드의 내용이다. 여기까지이 일이, 오른쪽 상단은 너무하다 즉, 다시, 우리는 우리 자신을 참조 할 수 있습니다. 그리고 가장 바깥쪽에있는 물건, 노드는 새로운 용어가 있더라도 아마도 여전히있어 학생 및 내용과 동일 SPL에서 후드 아래에 있었다. 그래서 우리가 지금 시작하기를 원한다면 이 연결리스트를 구현, 우리가 어떻게 번역 할 수 있습니다 이 같은 코드가? 음, 그냥 보자 그 프로그램의 예 실제로 링크 된 목록을 사용합니다. 오늘의 유통 코드 중 목록 제로라는 프로그램입니다. 나는 이것을 실행하는 경우 그리고 난 슈퍼를 생성 간단한 GUI, 그래픽 사용자 인터페이스 그러나 그것은 정말로 단지는 printf입니다. 그리고 지금은 자신에게 몇 가지 메뉴를 준 options-- 삭제, 삽입, 검색, 트래버스. 그리고 종료합니다. 이들은 그냥 일반적인 작업 아르 링크리스트로 알려진 데이터 구조. 지금에가는 삭제 목록에서 번호를 삭제합니다. 삽입 추가 할 것 목록에 번호입니다. 검색 보일 것입니다 목록 번호. 그리고 옆으로는 멋진 방법입니다 말하는, 목록을 도보 그것을 밖으로 인쇄하지만, 그게 다예요. 어떤 방법으로 그것을 변경하지 마십시오. 그럼이 시도 할 수 있습니다. 이제 가서 2를 입력 할 수 있습니다. 그리고 나는 갈거야 수를 삽입 구를 말한다. 입력합니다. 그리고 지금 내 프로그램은입니다 말을 프로그램 목록은 이제 구이다. 자, 가서 경우 다시 삽입 않습니다 보자 나 가서 축소와 17을 입력하세요. 지금 내 목록은, 17 구이다. 내가 다시 삽입 할 경우의 하나를 건너 뛸 수 있습니다. 대신 22, 그림에 따라 우리는했습니다 여기에서 찾고, 내가 앞으로 이동하자 그리고 다음 26를 삽입합니다. 그래서 26를 입력 할거야. 내가 예상대로 목록입니다. 하지만 지금은 그냥이 코드 있는지 확인합니다 유연한 될 것입니다, 지금 나를 보자 유형 22,하는 이상 개념적으로, 우리는이 있다면 이 사실 인 정렬되어 유지 지금 골은 될 것, 17과 26의 사이에 가야한다. 그래서 입력하고 Enter 키를 누르십시오. 사실, 그 작동합니다. 그래서 지금 내가 삽입하자 마지막으로, 그림, 34 당. 좋아. 그래서 지금 나를 그렇게 규정 할 수 삭제하고 이송 및 검색 수행 사실, 작동합니다. 내가 검색을 실행할 경우 사실,하자 입력 한 숫자 (22)를 검색합니다. 그것은 22을 발견했다. 그래서 어떤이는 프로그램 목록 제로는 않습니다. 그러나 실제로 무엇을 것입니다 에 그이 구현? 음, 첫째 나는, 그리고 참으로 수 나는 파일이 list0.h라고해야합니까. 그리고이이 곳에서 라인 타입 정의, 구조체 노드, 나는 내 중괄호가 N 중간, 및 다음 정의 무엇 struct--? 구조체 노드 옆에. 그래서 우리는 스타가 필요합니다. 이제 기술적으로 우리는 들어가 여기를 그리는 습관. 당신은 교과서를 볼 수 있으며 온라인 참조가 그것을 할. 그것은 기능적으로 동일합니다. 사실, 이것은 좀 더 전형적이다. 그러나 나는 것과 일치 할 것이다 우리는 지난 시간을했고,이 작업을 수행. 그리고 마지막으로, 난 할거야. 헤더 파일 그래서 어딘가 list0.h에서 오늘이 구조체 정의입니다, 아마 다른 물건. 한편 list0c에있다 몇 가지가 될 것. 그러나 우리는거야 그냥 시작이 완료되지. List0.h 내가 원하는 파일입니다 내 C 파일에 포함합니다. 그리고 어떤 점에서 난 주, 지능 무효화 것. 그리고 나는 갈거야 해야 할 몇 가지가 여기에 있습니다. 나는 또한이거야 프로토 타입, 무효, 검색, 정수 등 N, 인생에서 누구의 목적은 요소를 검색합니다. 그리고 여기있는 난의 주장 오늘날의 코드, 무효, 검색, 중간, N, 세미콜론 없지만 열린 중괄호. 지금은 어떻게 든 검색 할 이 목록에있는 요소. 그러나 우리는 충분하지 않습니다 아직 화면에 정보를 표시합니다. 나는 실제로이 목록 자체를 표현. 그래서 하나의 방법 우리는 구현할 수 프로그램에서 연결리스트 내가 가지 일을 할됩니다 등이 여기에 목록을 연결 선언합니다. 단순하게하기 위해, 내가 만들거야 이 경우에도 일반적으로 우리의 생각, 글로벌 이 너무 많이하지 않아야합니다. 그러나이 예제를 단순화됩니다. 그래서 선언 할 여기 링크 된 목록입니다. 이제, 내가 어떻게 할 수 있는가? 여기에 링크 된 목록의 그림입니다. 그리고 정말 안돼 방법 순간 알 나는 표현에 대해 갈거야 하나 너무 많은 것들 메모리 변수입니다. 그러나 다시 순간을 생각합니다. 우리가 가진 것 모두이 시간 문자열, 다음, 그것은 우리를 의 배열로 밝혀 자, 다음 그것은 우리를 단지 포인터로 밝혀 첫 번째 문자로 문자의 배열에 즉, 널 (null) 종료합니다. 그 로직에 의해,이 너무 의견을 시드의 사진 종류, 우리가 실제로 무엇을 쓸 필요가 우리의 코드가 링크 된 목록을 나타내는? 얼마나이 정보를 우리가 필요로 할 C 코드에서 캡처, 당신은 말할 것? 그래? 청중 : 우리는 노드에 대한 포인터가 필요합니다. 데이비드 J. 마란 : 노드에 대한 포인터. 특히, 어떤 노드는을 것 본능에 대한 포인터를 유지하는? 청중 : 첫 번째 노드입니다. 데이비드 J. 마란 : 네, 아마 첫째. 그리고, 제 알 노드는 다른 형태이다. 이 구조체의 절반 크기이다, 때문에 실제로 포인터 만입니다. 그래서 당신은 실제로 할 수있는 선언이다 연결리스트는 * 유형 노드의 수입니다. 그리고 그냥 먼저 부르 자 하고 null로 초기화합니다. 그래서 널, 다시오고있다 여기 사진에. 뿐만 아니라 널 (null) 특수 등으로 사용된다 getstring를 같은 것들에 대한 반환 값 과의 malloc은 널 (null)는 제로 포인터, 포인터의 부족 만약에 당신. 그냥 아무것도 아직 여기 없음을 의미합니다. 지금 첫번째에, 난 할 수 이 아무것도했다. 나는 "목록"이라고 불렀다 수 있었다 또는 다른 것들의 수. 그러나 나는 그래서 "첫번째"라고 전화를 해요 이 사진과 함께이 라인 업. 그러니 그냥 문자열처럼 표현 될 수있다 그 첫 번째 바이트의 주소, 그래서 연결리스트가 있습니다. 그리고 우리는 다른 데이터를 볼 수 있습니다 구조가 표현 될 하나의 포인터, 32 비트 화살표 가리키는 구조에서 첫 번째 노드. 하지만 지금의 문제를 예상 할 수 있습니다. 나는 단지 기억하고있어 경우 내 프로그램 주소 제 노드, 제 데이터 구조에 직사각형 있었다 더 나은에 대한 경우가 될 것 내 목록의 나머지 부분의 구현? 무슨 중요한 세부 사항은 무엇입니까 이 실제로 작동하는지 확인하는 방법? 그리고에 의해 나는 "실제로 작동" 많은 캐릭터처럼 말은, 우리는 첫 번째 문자에서 가자 두 번째로 다빈의 이름으로, 셋째로,에 넷째, 맨 마지막에, 우리가 마지막에있을 때 우리는 어떻게 알고 이처럼 보이는 링크 목록? 때 널 (null)입니다. 그리고는 이런 종류의 표현했습니다 전기 기술자의 힘처럼, 작은 접지와 기호 종류의. 그러나 그것은 단지이 경우에는 널 (null)을 의미합니다. 당신은 어떤 수를 그릴 수 있습니다 방법이지만이 저자 여기이 기호를 사용하여 일어났다. 우리가 모인 말라구 함께 이들 노드 모두 경우에만 기억 첫번째는, 너무 길면 우리는에 특수 기호를 넣어 목록의 맨 마지막 노드, 그 때문에 우리는, 널 (null)을 사용합니다 우리가 사용할 수 무엇을 우리가, 이 목록이 완료됩니다. 그리고 심지어 경우에만 당신에게에 대한 포인터를 제공 첫 번째 요소, 당신, 프로그래머, 확실히의 나머지 부분을 액세스 할 수있다. 그러나의 당신의 마음을합시다 조금 방황, 그들은 이미하지 않으면 아주 무엇 wandered-- 의 실행 시간이 될 것 이 목록에서 아무것도 발견? 그것은 젠장, 그것은 N의 큰 O이야, 이는 공평하게, 나쁘지 않습니다. 그러나 선형이다. 우리는 어떤 기능을 포기 더 이동하여 배열의 동적으로이 사진을 향해 함께 짠 또는 노드를 연결? 우리는 랜덤 액세스를 포기했습니다. 배열 때문에 좋은 수학적으로 모든 뒷면에 다시 다시 다시입니다. 심지어이 사진하지만 예쁜 외모, 심지어 이들 노드처럼 보이지만 멋지게 실제로, 이격 그들은 어느 곳이 될 수 있습니다. OX1, Ox50, Ox123, Ox99,이 노드는 곳이 될 수 있습니다. malloc에​​ 메모리를 할당 않기 때문에 힙하지만, 어느 곳에서나 힙. 당신은 반드시 그건 모르겠어요 돌아가는 것은 다시 다시합니다. 그리고 현실의 너무이 사진 확실히이 꽤 될 수 없습니다. 그래서 조금 걸릴 거예요 이 기능을 구현하기 위해 작동한다. 그래서 지금 검색을 구현​​ 할 수 있습니다. 그리고 우리는의 종류를 볼 수 있습니다 이렇게 영리한 방법. 내가 검색 기능입니다 경우에 따라서 및 나는 변수, 정수 n을 부여하고있어 을 찾기 위해, 나는 알 필요가 내부보고를위한 새로운 구문 야 구조 , n은 찾아 지적했다. 그래서이 작업을 수행 할 수 있습니다. 그래서 첫째 나는 갈거야 앞서와 * 노드를 선언합니다. 그리고 내가 전화하려고 해요 단지 규칙에 따라 포인터. 그리고 첫번째로 초기화하는거야. 그리고 지금은이 작업을 수행 할 수 있습니다 여러 가지 방법. 하지만 일반적인 접근 방식을거야. 포인터와 동일하지는 않지만 null의 경우, 그 유효 구문입니다. 그리고는 그냥 그렇게, 다음을 수행 의​​미 오랫동안 아무것도 가리키는 아니에요있다. 내가 뭘하고 싶어? 포인터 도트 N 경우에, 저 돌아 오게 그에게 equals-- 무엇을 동일? 어떤 값을 내가 찾고 있어요? 전달 된 실제 명. 그래서 여기에 또 다른 기능입니다 C 많은 언어. 심지어 구조라는 노드하지만 n 값, 완전히 합법적있다 또한 로컬 인수를 가지고 또는 변수는 N했다. 심지어 우리와 함께 있기 때문에 인간의 눈은 구별 할 수있다 이 n은 아마도입니다 이 N 다릅니다. 구문이 다르기 때문입니다. 당신은 도트 및 포인터를 가지고있어, 이 한 반면 같은 것은이 없습니다. 그래서 이것은 정상입니다. 즉, 같은 일을 전화를 확인합니다. 나는 당신이 찾을 경우, 난 뭔가를 할 것 같은 우리가 N을 발견했다고 발표. 그리고 우리는 같은 것을 떠날거야 의견이나 의사 코드입니다. 그렇지, 그리고 여기에 흥미로운 부분은, 어떤 나는 현재 노드 경우 어떻게할까요 내가 걱정하는 N을 포함되지 않는 이유는 무엇입니까? 방법은 다음을 달성합니까? 만약에 내 손가락 순간 PTR이며 야 무엇을 가리키는 첫째는, 가리키고 나는 내 손가락을 이동 어떻게 코드의 다음 노드로? 글쎄, 우리가있어 이동 경로 무슨 이 경우에 따라가는거야? 청중 : [들리지]. 데이비드 J. 마란 : 네, 다음. 내가 다시 가면 그래서 내 여기 코드, 참, 난 , 포인터를 가서 말을하려고하는 그것은 그냥 임시 variable--입니다 이상한 이름, PTR하지만, 그냥 temp--처럼 나는 포인터를 설정하는거야 어떤 포인터는 ... 동일 다시이 될 것입니다 다음 순간은 점에 대한 약간의 버그. 즉, 내가 걸릴거야 내 이 노드를 가리키는 손가락 여기 당신이 알고 말할거야 무엇을, 다음 필드를 살펴 에 손가락을 이동 무엇이든 그것을 가리키는 것. 그리고 이것은을 것입니다 반복, 반복을 반복합니다. 그러나 때 내 손가락을 수행 전혀 아무것도하지? 곧 어떤 코드 차기의 라인으로? 청중 : [들리지] 데이비드 J. 마란 : 만약 포인트 동안 포인터는 null로 동일하지 않습니다. 어느 순간 내 손가락의에서 널 (null)을 가리키는 될 것 나는 실현거야 그리스트의 마지막입니다. 자,이 조금이다 단순 흰색 거짓말입니다. 그것은 밝혀 그 경우에도 우리 바로이 점 표기법을 배웠다 구조에 대한 포인터는 구조체가 아닙니다. PTR은 무엇입니까? 그냥 더 nitpicky합니다. 이 노드에 대한 포인터이다. 이 노드 자체 아니다. 여기에는 스타가 없었 경우, 포인터 absolutely--는 노드입니다. 이 주 일처럼 변수의 선언 심지어 단어 "노드가"새로운 생각. 그러나 우리는 소개 마자 스타, 이제 노드에 대한 포인터이다. 그리고 불행하게도 당신은 사용할 수 없습니다 포인터의 점 표기법. 사용자는 화살표를 사용할 필요 표기되는, 눈에 띄게, 처음은 조각이다 구문의 직관적 보인다. 이것은 말 그대로 화살처럼 보인다. 그리고 그건 좋은 일이야. 그리고 여기에 아래로 그대로 화살표 모양. 그래서 그게 그렇게하지 ​​la-- 생각 내가 이곳에 오버 커밋 있다고 생각 I 그 마지막으로 새로운 조각 생각 구문의 우리는 볼 것입니다. 그리고 다행히도, 그것은 참이다 좀 더 직관적. 지금, 당신의 사람들을 위해 사람 옛날 방식을 선호 할 수 있습니다, 당신은 여전히​​ 점 표기법을 사용할 수 있습니다. 그러나 월요일의 당 대화, 우리는 첫번째 그로 이동, 거기에 갈 필요가 해결 한 다음 필드에 액세스 할 수 있습니다. 따라서이 또한 정확합니다. 그리고 솔직히, 이것이 많은 학자 연하는 좀. 당신은 말 그대로 말을하는지, 역 참조 포인터가 이동합니다. 그런 다음 .N 잡아 필드는 N했다. 하지만 솔직히, 아무도 원하지 않는다 입력하거나이를 읽을 수 있습니다. 그리고 세계는 발명 화살표 표기법하는 , 동일, 동일합니다 그냥 문법 설탕입니다. 이런 말 그래서 멋진 방법 좋아 보이는, 또는 간단 보인다. 그래서 지금은 하나의 다른 일을 할거야. 나는 일단 "휴식"을 말하는거야 그렇게 나는 그것을 찾고 보관하지 않습니다 발견. 하지만이 요점이다 검색 기능. 그러나에, 많은 쉽게 끝 코드를 걸을 수 없습니다. 이것은 참으로 공식적인 구현 오늘의 유통 코드 검색. 그 삽입이 아니라고 감히 을 통해 걸을 특히 재미 시각적으로도에도 삭제 하루의 끝에서하지만 그들은 상당히 졸이다 간단한 휴리스틱. 그래서이 작업을 수행 할 수 있습니다. 여기에 유머 날거야, 내가했다 스트레스 공의 무리를 가져온다. 나는 숫자의 무리를 가져왔다. 그리고 우리는 몇 자원 봉사자를 얻을 수 9, 17, 20, 22, 29, 34을 나타내는? 그래서 기본적으로 모든 사람 누가 오늘 여기입니다. 즉, 하나, 둘, 셋이었다 넷, 다섯, 여섯 사람입니다. 난 안 볼 봐야 ... 해왔 어 다시 한 그들의 손을 발생시킵니다. OK, 하나, 둘, 셋, 넷, five-- 날 육을 balance--로드 할 수 있습니다. 좋아, 여섯 최대 어서. 우리는 다른 사람이 필요합니다. 우리는 여분의 스트레스 공을 가져왔다. 그리고 당신이 할 수있는 경우에 대한 잠시, 선 자신 최대 단지 여기이 그림처럼. 좋아. 당신의 이름은 무엇입니까, 보자? 청중 : 앤드류. 데이비드 J. 마란 : 앤드류, 당신은 9 번입니다. 만나서 반가워요. 여기 당신은 간다. 청중 : 젠. 데이비드 J. 마란 : 젠. 데이비드. 번호 17. 네? 청중 : 나는 줄리아 해요. 데이비드 J. 마란 : 줄리아, 데이비드. 번호 20. 청중 : 기독교. 데이비드 J. 마란 : 기독교, 데이비드. 번호 22. 그리고? 청중 : JP. 데이비드 J. 마란 : JP. 번호 29. 그래서 어 오 가서 받 얻을. 어 오. 대기. 20. 사람이 마커를 가지고 있습니까? 청중 : 나는 샤피 있어요. 데이비드 J. 마란 : 당신은 샤피있어? 확인을 클릭합니다. 그리고 사람이 종이 조각이 있나요? 강의 내용을 저장합니다. 어서. 청중 : 우리는 그것을 가지고있다. 데이비드 J. 마란 : 우리는있어? 좋아요, 감사합니다. 여기에 우리가 간다. 이것은 여러분이 되었습니까? 당신은 일 저장. 그래서 29. 좋아. 나는 29 철자하지만, 확인을 클릭합니다. 어서. 좋아, 내가 당신에게 줄 것이다 펜 다시 잠시. 그래서 우리는 여기이 사람들이 있습니다. 의 다른 하나를 보자. 게이브, 당신은 연주하고 싶어 여기에 첫 번째 요소? 우리는 지적 할 필요가있을 것이다 이 좋은 사람들에서. 그래서 9, 17, 20, 22, 정렬 29 일 후 34. 우리는 사람을 잃게 했습니까? 나는 34을해야합니까. 여기서 원하는 한일 확인, 34이 될 수 있습니다? OK, 34, 최대 어서. 좋아,이 될 것입니다 절정 볼만한 가치가있는 곳입니다. 당신의 이름은 무엇입니까? 청중 : 피터. 데이비드 J. 마란 : 피터, 최대 어서. 좋아, 그래서 여기에 노드의 전체 무리. 너희들은 각각 나타냅니다 이 사각형의 하나. 그리고 게이브, 약간 이상한 아웃 인간, 첫째 나타냅니다. 그래서 그의 포인터는 조금 작다 다른 사람보다 화면. 그리고이 경우, 각 좌측 손을 아래로 가리 키도록 어느 것입니다 이에 따라서, 널 (null) 대표 단지 포인터의 부재 아니면 가리키는 될 것 당신 옆에 노드. 그래서 지금 당신이 장식하는 경우 사진과 같이 자신 여기 가서 지점 게이브와, 서로 에서 특정 가리키는 9 번 목록을 나타냅니다. 확인을 번호 34, 왼손 그냥 바닥을 가리키는해야합니다. OK, 그래서 이것은 링크 된 목록입니다. 따라서이 문제의 시나리오입니다. 그리고 실제로이 대표 문제의 클래스 당신은 코드를 해결하기 위해 시도 할 수있다. 당신은 궁극적으로 삽입 할 목록에 새 요소입니다. 이 경우, 우리는에 갈거야 숫자 55를 삽입하려고합니다. 그러나이있을거야 다른 경우 고려해야 할. 그리고 실제로,이 일을 될 것입니다 큰 그림은 여기 테이크 아웃,이다 다른 경우는 무엇인가. 조건 경우 또는 다른 무엇인가 프로그램이있을 수 있습니다 가지? 음, 수 당신은에 노력하고 우리는 55로 지금 알고 삽입,, 하지만 당신은 알고하지 않은 경우 사전에, 나는 daresay 적어도 세에 빠진다 가능한 상황. 어디에서 새로운 요소가 될 수 있을까요? 청중 : 그리고 끝이나 중간. 데이비드 J. 마란 : 마지막에,에 중간 또는 시작 부분에. 그래서 나는 적어도 거기에 주장 세 가지 문제는 우리가 해결해야합니다. 의 아마 무엇을 선택하자 틀림없이 간단한 하나, 여기서 새로운 요소를 시작 부분에 속한다. 그래서 나는 꽤 코드를하려고 해요 같은 난 그냥 쓴, 검색 할 수 있습니다. 그리고, PTR을 가지고 갈거야하는 난 내 손가락으로 여기에 표현됩니다 평소와 같이. 그리고, 어떤 값을 기억 우리는에 PTR 초기화 했습니까? 그래서 우리는 처음에 null로 초기화. 그러나 우리는 일단 무슨 짓을 한거야 우리의 검색 기능 내부에 있었다? 우리는 첫째로는 동일하게 설정 이 일을 의미하지 않는. 나는 첫번째에 해당 PTR을 설정하면, 무엇을 내 손은 정말 가리키는해야 하는가? 오른쪽. 게이브 내가려고하는 경우에 따라서 여기에 같은 값이어야합니다, 우리는 9 번에 두 지점이 필요합니다. 그래서 이것은 우리의 이야기의 시작이었다. 그리고 지금은 그냥 간단합니다 비록 구문은 새로운 기능입니다. 개념적으로이 단지 선형 검색합니다. 9와 동일한 55인가? 또는 오히려,의 9 이하 가정 해 봅시다. 나는에 노력하고있어 때문에 55을 넣어 위치를 알아낼. 9 미만, 17 미만, 이하 20 이상, 이하 22 일 이하 29 일 미만 (34), 아니. 그래서 지금 우리는 경우에있어 적어도 셋 중 하나. 나는 여기에 55을 삽입 할 경우, 어떤 코드 필요 라인은 모두 실행하는 방법? 어떻게이 그림을 수행 인간은 변경해야합니까? 나는 내 왼쪽 손으로 무엇을해야합니까? 이것은, 처음은 null이어야합니다 I가리스트의 끝에라서. 그리고 무슨 일이 일어날해야 여기에 피터와 함께, 그것은했다? 그는 분명히 나를 가리거야. 그래서 나는 적어도 두 개의 선이있다 주장 오늘부터 샘플 코드의 코드 즉,이를 구현하는 것 꼬리 (55)를 추가의 시나리오. 그리고 나는 누군가 홉을 가질 수 최대 단지 55에 해당합니까? 좋아, 당신은 새로운 55입니다. 그래서 지금 무엇을 다음 경우 시나리오는 따라 온다 우리는에 삽입 할 시작 또는리스트의 헤드? 그리고 당신의 이름, 숫자 55은 무엇입니까? 청중 : 잭. 데이비드 J. 마란 : 잭? OK, 만나서 반갑습니다. 탑승을 환영합니다. 그래서 지금 우리는에 갈거야 말하자면, 숫자 5를 삽입합니다. 다음의 두 번째 경우이다 세 우리는 전에 함께했다. 그래서 5 초에 속하는 경우, 이제 우리가을 알 방법을 볼 수 있습니다. 내 PTR를 초기화 다시 숫자 9에 대한 포인터입니다. 그리고 5 미만 9입니다, 오, 깨달았다. 그래서 우리에게이 사진을 수정합니다. 누구의 손, 게이브 나 다윗의 에 올 수 9의 이름은 무엇입니까? 청중 : 젠. 데이비드 J. 마란 : 젠의 hands-- 우리의 손의 어떤 변경해야합니까? 좋아, 그럼 게이브는 지금 무엇을 가리키는? 나 한테. 나는 새 노드입니다. 그래서 이동의 단지 종류거야 여기에 시각적으로 볼 수 있습니다. 그리고 그 사이에 무슨 일이 난 그 지점합니까? 아직도 어디를 가리키는거야. 그래서 그것입니다. 코드 수정 그래서 정말 한 줄 이러한 특정 문제가 보인다. 좋아, 잘 했어. 그리고 누군가가 5에 대한 자리 표시 할 수 있습니까? 올라 와요. 우리는 당신이 다음 번에 ​​얻을 것이다. 좋아요, 아니예요 및 옆으로, 이름과 난 지금의 명시 적 언급을하지 않을 겁니다 지금 PRED 포인터, 이전 포인터 새로운 포인터, 그건 단지 이름이 부여되고 포인터에 대한 샘플 코드 또는 가지 주위를 가리키는 것 내 손에. 당신의 이름은 무엇입니까? 청중 : 크리스틴. 데이비드 J. 마란 : 크리스틴. 탑승을 환영합니다. 좋아, 그래서 지금 생각해 봅시다 약간 더 성가신 시나리오 나는 삽입 할있다 이 후 26 뭔가. 20? 무엇? 다음은 우리가 펜을 가지고 좋은 일을 알수가. 좋아, 20. 누군가의 또 다른 조각을 얻을 수있는 경우 종이 그냥 모든 권리를 case--에서 준비. 아, 흥미 롭군요. 그럼이은 예입니다 강의 버그. OK 그래서 자네 이름이 뭐였더라? 청중 : 줄리아. 데이비드 J. 마란 : 줄리아, 당신은 팝업 수 출력 및 척 당신은 결코이 있었다? OK, 이것은 결코 일어나지 않았다. 감사합니다. 그래서 우리는 삽입한다고 가정 이 연결리스트에 줄리아. 그녀는 20 번이다. 그리고 물론 그녀는이다 에 속하는 것 begin-- 아직 아무것도 가리하지 않습니다. 그래서 당신의 손은 가지가 될 수 아래 null 또는 일부 쓰레기 값입니다. 의 빠른 이야기를 보자. 나는 5 번이 시간을 가리키는거야. 그럼 난 9 확인. 그럼 17은 확인합니다. 그럼 22은 확인합니다. 그리고, 우, 줄리아 실현 22 전에 갈 필요가있다. 어떤 일이 일어날 필요가 있겠습니까? 누구의 손을 변경해야합니까? 줄리아, 광산,에 올 이름이 뭐였더라? 청중 : 기독교. 데이비드 J. 마란 : 기독교 나? 청중 : 앤디. 데이비드 J. 마란 : 앤디. 기독교 나 앤디? 앤디 가리 필요가 있겠습니까? 줄리아. 좋아. 그래서 앤디, 당신은 줄리아 가리 하시겠습니까? 그러나 분을 기다립니다. 지금까지의 이야기에서, 나는 일의 종류 해요 의미에서 충전에 그 포인터입니다 것입니다 목록을 이동. 우리는 앤디의 이름을 가지고 있지만, 수 앤디라는 어떤 변수가 없습니다. 우리가 유일한 변수입니다 첫째, 게이브으로 표시 누가. 그래서이 이유 때문에 실제로 지금까지 우리는 이것을 필요하지했습니다. 하지만 지금은 화면에이 PRED 포인터를 다시 언급. 그래서 좀 더 명시 적으로 할 수 있습니다. 이 포인터 인 경우, 내가 더 잘했다 좀 더 지능 얻을 내 반복에 대한 정보가 포함되어 있습니다. 내 여기를 통과 괜찮다면 다시 여기를 가리키는 여기를 가리키는. 그러나 나를 PRED 포인터를하자, 이전 포인터, 그건 가지 가리키는 요소 난 그냥 있었다. 그래서 내가 여기에 갈 때, 지금 내 왼쪽 손으로 업데이트됩니다. 여기에 내 왼손 업데이트를 갈 때. 지금은에 대한 포인터뿐만 아니라이 줄리아 후가는 요소 난 여전히 포인터가 앤디, 전에 요소입니다. 그래서 당신은 본질적으로 접근 할 수 빵 부스러기, 만약에 당신, 필요한 포인터의 모든. 내가 가리키는있어 경우에 따라서 앤디와 나는 또한 가리키는거야 그의 손 기독교에서 지금은 다른 곳에서 지적해야 하는가? 앤디 그래서 지금 줄리아에 가리킬 수 있습니다. 줄리아는 이제 기독교에서 가리킬 수 있습니다. 그녀는 복사 할 수 있기 때문에 내 오른쪽의 포인터. 그리고 효과적으로 당신을두고 다시 여기이 장소에. 그래서 짧은, 심지어이 비록 영원히 종류의 우리를 복용 실제로 업데이트하려면 목록을 연결 실현 작업이 상대적으로 간단하다. 그것은, 둘, 하나의 세입니다 궁극적으로 코드 라인. 하지만 그 감싸 아마도 코드 라인 논리의 약간은 효율적이다 질문, 우리가 요청? 우리가 처음이고, 중간 또는 최종? 이제 확실히 다른있다 우리가 구현하는 작업. 그리고 여기이 그림은 묘사 우리가 단지 인간과 않았다. 무엇 제거에 대한? 내가하고 싶은 경우에, 예를 들어, 번호를 제거 34 또는 55, I는, 코드의 종류가 동일 할 수도 하지만 난 하나 또는 두 개의 단계를 필요 해요. 새로운 무엇 때문에? 나는 마지막에 사람을 제거하는 경우, 수와 같은 55 다음 34, 무엇도 나는 할 수로 변경할 수있다? 나는 evict--되지해야 이름이 뭐였더라? 청중 : 잭. 데이비드 J. 마란 : 잭. 나는 evict-- 무료 잭뿐만 아니라에있다 그래서 말 그대로 최소한 무료 잭에게 전화를 걸거나 이 포인터도하지만 지금은 무슨 일이 피터와 함께 변경해야? 그의 손은 더 아래로 가리키는 시작합니다. 최대한 빨리 내 무료 전화로 인해 잭, 베드로는 여전히 잭을 가리키는 경우 나는 때문에 통과 유지 목록 및 액세스이 포인터, 그 때 우리의 오랜 친구 분할이다 실제로 킥 있습니다 잘못. 우리가 준 때문에 잭 메모리 백업합니다. 당신은 거기에 머물 수 가벼운 부상을 입 그냥 잠시. 우리는 몇 가지를 가지고 있기 때문에 최종 작업은 고려. 리스트의 헤드를 제거 beginning--이 하나의 나 조금 짜증나. 우리가 알고 있기 때문에 게이브 가지 특별한 프로그램입니다. 때문에 실제로 그는 자신의 포인터를 가지고있다. 그는 단지에서 지적하지 않을 것 여기에 거의 모든 사람들이 다른 때문이다. 그래서리스트의 헤드 인 경우 누구의 손을 지금 변경해야 제거? 당신의 이름이 뭐죠? 청중 : 크리스틴. 데이비드 J. 마란 : 나는 끔찍 해요 이름에서, 분명히. 그래서 크리스틴과 게이브, 누구의 손을 변경해야 우리는 크리스틴을 제거하려고 할 때, 그림에서 숫자 5,? OK, 그래서 게이브을 할 수 있습니다. 게이브 가리키는 것, 아마도, 9 번에서. 하지만 다음에 무슨 일이 일어날 것인가? 청중 : 크리스틴해야 [INAUDIBLE] null이. 데이비드 J. 마란 : OK, 우리는 아마해야 make-- 어디 선가 "널 (null)"들었다. 청중 : 널 (null)와 그녀의 자유. 데이비드 J. 마란 그럼 NULL은 무엇? 청중 : 널 (null)와 그녀의 자유. 데이비드 J. 마란 : 널 (null)와 그녀의 자유. 그래서 이것은 매우 간단합니다. 그리고 그것은 당신이 지금 일종의 걸 완벽 의 소속, 거기 서. 당신은 했소 리스트에서 분리. 당신은 효과적으로 봤는데 목록에서 고아. 그래서 우리는 더 나은 지금 무료로 전화했다 크리스틴은 그 메모리를 다시 얻었다. 그렇지 않으면 때마다 우리 리스트에서 노드를 삭제 우리는 목록을 만들 수 있습니다 짧은, 그러나 실제로 감소하지 메모리의 크기입니다. 그래서 우리는 계속 추가 할 경우 추가 목록에 물건을 추가, 내 컴퓨터가 느려질 수 있습니다 과 느린 속도가 느린, 내가 부족 해요 때문에 메모리, 사실은 아니에요 경우에도 크리스틴의 바이트를 사용하여 메모리의 이상. 그래서 결국 다른있다 course-- 제거 시나리오 중간 제거에 끝으로 우리는 보았다. 그러나 더 흥미를 도전은 지금 가는 정확히 고려 될 실행 시간은 무엇인지. 그래서뿐만 아니라 유지할 수 있습니다 종이 조각, 게이브, 경우, 당신이주는 상관 없어 모두 스트레스 공입니다. 우리의 연결리스트에 정말 감사합니다 여기에 자원 봉사자, 당신이 할 수 있다면. [박수] 데이비드 J. 마란 : 좋습니다. 분석의 그래서 몇 다음 질문, 내가 할 수있는 경우. 우리는 전에이 표기법을 본 적이 큰 O와 오메가, 상한 과에 하한 어떤 알고리즘의 실행 시간. 그래서 그냥 생각 해보자 몇 가지 질문. 하나, 우리는 그것을했다 전에 실행은 무엇인가 검색 시간 큰 O의 관점에서 목록? 어떻게 실행에 상한이다 연결리스트를 검색하는 시간 여기에 우리의 자원 봉사자들에 의해 구현 된? 그것은 N의 큰 O, 선형입니다. 최악의 경우로 인해 요소, 55 등, 우리는 여기서 할 수 있습니다에보고 될 수 있습니다 잭, 마지막에 모든 방법이었다. 그리고 불행하게도, 배열과는 달리 우리는이 시간을 멋진 얻을 수 없습니다. 우리는 모든 인간의 되었더라도 작은 요소, 5 정렬 더 큰 요소까지 모든 방법, 55, 즉 일반적으로 좋은 일입니다. 그러나 가정을 무엇을 더 이상 우리가 수행 할 수 없습니다? 청중 : [들리지] 데이비드 J. 마란은 : 다시 말해? 청중 : 임의 액세스 할 수 있습니다. 데이비드 J. 마란 : 임의 액세스 할 수 있습니다. 그리고 차례로 그없이 우리가 할 수있는 것을 의미 더 이상 약한 제로, 직관을 사용 바이너리를 사용하고 명백한 검색 및 분할 및 정복. 비록 때문에 우리 인간은 분명 수 앤디 나 기독교라고 볼 수 대략 목록의 중간에, 우리는 같은 알고 목록을 걷어 컴퓨터 처음부터. 그래서 우리는 랜덤 액세스를 포기했습니다. N의 그래서 큰 O는 이제 상단입니다 우리의 검색 시간에 바인딩됩니다. 무엇을 우리의 검색 오메가에 대한? 하한 검색에 무엇입니까 이 목록의 일부 번호? 청중 : [들리지] 데이비드 J. 마란은 : 다시 말해? 관객 : 한. 데이비드 J. 마란 : 한. 그래서 일정 시간. 최상의 경우 크리스틴이다 실제로 목록의 시작 부분에. 그리고 우리는을 찾고 숫자 5는, 그래서 우리는 그녀를 발견했다. 그래서 더 큰 문제. 하지만 그녀는에있을거야 이 경우,리스트의 시작. 뭔가에 대해 무엇을 삭제 하시겠습니까? 당신은 요소를 삭제하기 위해 무엇을해야할까요? 무슨 상한과 하한입니다 링크에서 뭔가 삭제에 목록? 청중 : [들리지] 데이비드 J. 마란은 : 다시 말해? 대상 : 명. 데이비드 J. 마란 : n은 바운드 실제로 위. 최악의 경우에 우리는 시도로 인해 우리가했던 것처럼, 잭을 삭제합니다. 그는 마지막에있는 모든 방법입니다. 우리를 영원히 간다, 또는 N 단계는 그를 찾을 수 있습니다. 그래서 상한을합니다. 즉, 확인, 선형입니다. 그리고 최상의 경우는 시간을 실행 또는 최상의 경우에서 하한 일정 시간이 될 것이다. 어쩌면 우리가 삭제하려고하기 때문에 크리스틴, 그리고 우리는 단지 운 그녀는 처음입니다. 지금 분을 기다립니다. 게이브, 시작 부분도 있었다 우리는 또한 게이브을 업데이트했다. 그래서 단 하나의 단계 만이 아니었다. 그래서 그것은 참 일정 시간, 최상의 경우에, 가장 작은 요소를 제거하려면? 그것은이있을지라도 그것은이다 코드 셋, 또는 100 라인 그것의 동일한 수 있다면 하지 어떤 루프 라인, 및 크기와 무관 목록의, 절대적으로. 요소에서 삭제 리스트의 처음 우리는 처리 할 경우에도 게이브는 아직 일정 시간이다. 그래서이 보인다 뒤로 거대한 단계를 포함한다. 그리고 시간의 낭비 다 , 만약 주 하나 주에서 제로 우리는뿐만 아니라했다 의사 코드 그러나 실제 코드 로그가 뭔가를 구현하는 베이스 N, 또는 로그, 오히려, N의,베이스 (2), 그 주행 시간적. 그래서 도대체 우리가 시작하려는 이유 연결리스트 같은 것을 사용하고 계십니까? 그래. 청중 : 그래서 당신은 추가 할 수 있습니다 배열에 요소. 데이비드 J. 마란 : 그래서 당신이 할 수있는 배열에 요소를 추가 할 수 있습니다. 그리고이 너무 주제이다. 그리고 우리는 계속 볼 것 이,이 트레이드 오프, 많은 같은 우리가 본 적이 병합 정렬과 트레이드 오프. 우리는 정말로 속도를 높일 수 오히려 검색하거나 정렬 우리가 조금 더 많은 공간을 할애 경우 메모리의 추가적인 청크를 가지고 또는 병합 정렬을위한 배열입니다. 그러나 우리는 더 많은 지출을 공간,하지만 우리는 시간을 절약 할 수 있습니다. 이 경우, 우리는 야 시간을 포기하지만 우리는있어 유연성을 얻고, 동성 만약에 당신, 이는 틀림없이 긍정적 인 기능입니다. 우리는 또한 공간을 지출하고 있습니다. 어떤 의미에서 연결되어 있습니다 더 비싼 목록 배열보다 공간의 측면에서? 어디 여분의 공간에서오고있다? 그래? 청중 : [들리지] 포인터. 데이비드 J. 마란 : 그래, 우리 또한 포인터를 가지고있다. 그래서이 minorly 짜증나 그 더 이상 어디로 없습니다 난 그냥 int를 저장 int를 나타냅니다. 나는 INT 및 저장 해요 또한 32 비트 포인터. 그래서 말 그대로 두 배로 해요 공간의 양을 포함했다. 그래서 트레이드 오프,이지만 그 INT의 경우입니다. , 당신은 정수를 저장하지 않을 것을 가정 하지만, 이들 각각의 사각형을 가정 또는 이들 각각은 인간 나타내는 하였다 단어, 영어 단어 그 5 자, 열 수 있습니다 자, 어쩌면 더. 그럼 그냥 32 더 많은 비트를 추가 큰 문제가 덜 될 수 있습니다. 어떤 학생의 각 경우 데모에서 했다 문자 그대로 학생 구조체가 아마 이름과 주택과가 전화 번호와 트위터 처리 등을들 수있다. 그래서 모든 필드의 우리는 시작 다른 일에 대해 얘기, 와 같은 큰 문제의 훨씬 더 우리의 노드는 더 흥미로워 큰, 어, 추가를 지출 포인터는 함께 연결합니다. 그러나 실제로는 트레이드 오프입니다. 그리고 실제로, 코드는 더 복잡한,대로거야 를 통해 감추고에 의해 참조 특정 예. 그러나이 있다면 여기에 몇 가지 성배. 우리는 조치를 취할하지 않으면 어떻게 거꾸로하지만 거대한 단계 앞으로 및 데이터를 구현 구조하는을 통해 우리 잭 또는 같은 요소를 찾을 수 있습니다 크리스틴 또는 다른 요소 사실 일정한 시간이 배열? 검색은 일정하다. 삭제는 일정하다. 삽입은 일정하다. 이러한 모든 작업은 일정하다. 즉, 우리의 성배 것입니다. 그리고 어디 우리 다음 시간을 선택할 것입니다. 다음을 참조하십시오.