Giáo án Cấu trúc dữ liệu và giải thuật - Nguyễn Ngọc Duyên

86 trang ngocly 200

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo án Cấu trúc dữ liệu và giải thuật - Nguyễn Ngọc Duyên", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_an_cau_truc_du_lieu_va_giai_thuat_nguyen_ngoc_duyen.pdf

Nội dung text: Giáo án Cấu trúc dữ liệu và giải thuật - Nguyễn Ngọc Duyên

Bộ Lao Động Thương Binh và Xã Hội Trường Cao Đẳng Sư Phạm Kỹ Thuật Vĩnh Long Khoa Sư Phạm  GVHD: Nguyễn Minh Trung SVTH : Nguyễn Ngọc Duyên Lớp : Tin học 2009 06 - 2012
ĐƠN VỊ QUẢN LÝ TRỰC TIẾP CƠ SỞ DẠY NGHỀ SỔ GIÁO ÁN LÝ THUYẾT Môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Lớp : Tin Học 2009 Khoá : K34 Họ và tên giáo viên : Nguyễn Ngọc Duyên Năm học: 2012
LỜI NÓI ĐẦU  Ngày nay, cùng với sự phát triển của xã hội nền khoa học công nghệ ngày càng có những bước phát triển vượt bậc, vì vậy khối lượng kiến thức mà nhân loại cần phải tìm hiểu ngày một khổng lồ. Những thành tựu vĩ đại mà ngày hôm nay chúng ta có được là tất cả thời gian, chất xám, những công trình nghiên cứu, thí nghiệm của các nhà khoa học, đó là nguồn gốc của những kiến thức. Song, để gìn giữ truyền thụ những kiến thức quí báo này cho thế hệ sau chúng ta không thể không kể công đến những người đã dẫn dắt chúng ta đi từ những cái đơn giản đến cái phức tạp, giúp người học nắm bắt được kiến thức. Đó là người Thầy. Vị trí vai trò của người thầy rất là quan trọng . Là người hướng dẫn và truyền đạt cho thế hệ đi sau, là người định hướng cho lớp trẻ trong tương lai . Thì đối với chúng em bước đầu làm quen với công việc một người thầy là biên soạn giáo án lý thuyết và thực hành, nó nằm trong nội dung môn học PHƯƠNG PHÁP GIẢNG DẠY CHUYÊN NGHÀNH là rất quan trọng. Nó quyết định chất lượng giảng dạy của chúng em sau này.Vì là lần đầu tiên đến với công việc này nên chúng em còn gặp rất nhiều khó khăn vướn mắc.Chúng em rất mong được sự hướng dẫn đóng góp ý kiến của các thầy cô để bản thân em và những bạn khác sẽ rút được nhiều kinh nghiệm, giúp chúng em hoàn thành tốt môn học này cũng như là hành trang bổ ích cho công việc giảng dạy của chúng em sau này. Vĩnh Long, ngày 22 tháng 6 năm 2012 Nguyễn Ngọc Duyên
KẾT LUẬN  Qua thời gian học tập nghiên cứu môn học PHƯƠNG PHÁP DẠY HỌC CHUYÊN NGÀNH với sự hướng dẫn của Thầy Nguyễn Minh Trung chúng em đã bước đầu hiểu được cách truyền đạt kiến thức cho học sinh giúp học sinh lĩnh hội một cách tốt nhất và đặc biệt là hiểu được những khó khăn của một người giáo viên trong việc chuẩn bị bài giảng trước khi lên lớp mà cụ thể là biên soạn giáo án. Đây là lần đầu tiên chúng em làm quen với công việc của một người thầy nên gặp không ít khó khăn từ việc soạn mục tiêu, nội dung bài học đến việc biên soạn giáo án nhưng cũng nhờ sự hướng dẫn tận tình của thầy Nguyễn Minh Trung đã giúp chúng em tháo gỡ những vướng mắc, vượt qua khó khăn hoàn thành tốt yêu cầu của thầy cũng như yêu cầu của môn học. Qua đó trang bị cho chúng em những kiến thức, những kinh nghiệm quí báo, đó là nền tảng để chúng em hoàn thành tốt công việc giảng dạy của mình cũng như nối tiếp truyền thống học tập lâu đời của dân tộc ta. Cuối cùng em chân thành cảm ơn thầy Nguyễn Minh Trung cùng các thầy cô đã tận tình hỗ trợ về mặt kiến thức và tạo điều kiện tốt nhất để chúng em hoàn thành tốt nhiệm vụ được giao. Em xin chúc tất cả thầy cô luôn dồi dào sức khỏe để tiếp tục sự nghiệp trồng người vĩ đại và hoàn thành tốt những nhiệm vụ được giao. Vĩnh Long, ngày 22 tháng 6 năm 2012 Nguyễn Ngọc Duyên
NHẬN XÉT CỦA GIÁO VIÊN   
BỘ LAO ĐỘNG-THƯƠNG BINH CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM VÀ XÃ HỘI Độc lập - Tự do - Hạnh phúc CHƯƠNG TRÌNH KHUNG TRÌNH ĐỘ TRUNG CẤP NGHỀ (Ban hành kèm theo Quyết định số 42/2008./QĐ- BLĐTBXH Ngày 16 tháng 4 năm 2008 của Bộ trưởng Bộ lao động - Thương binh và Xã hội)  Xác định vị trí bài giảng trong chương trình đào tạo nghề: Tên nghề: Quản trị cơ sở dữ liệu Mã nghề: Trình độ đào tạo: Trung cấp nghề Đối tượng tuyển sinh:- Tốt nghiệp Trung học phổ thông hoặc tương đương; -Tốt nghiệp Trung học cơ sở và tương đương, có bổ sung văn hoá Trung học phổ thông theo Quyết định Bộ Giáo dục- Đào tạo ban hành. Số lượng môn học, mô-đun đào tạo: 28 Bằng cấp sau khi tốt nghiệp: Bằng tốt nghiệp Trung cấp nghề. 1. MỤC TIÊU ĐÀO TẠO 1.1. Kiến thức, kỹ năng nghề nghiệp * Kiến thức - Nắm vững các kiến thức cơ bản về cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu. - Có đủ kiến thức về khoa học kỹ thuật làm nền tảng cho việc nắm bắt đầy đủ quy trình quản trị, khai thác các hệ thống dữ liệu vừa và nhỏ. - Có khả năng chuẩn đoán và đưa ra giải pháp xử lý các sự cố, tình huống trong hệ thống cơ sở dữ liệu. - Nắm vững các biện pháp an toàn nghề nghiệp. * Kỹ năng - Khai thác, quản trị các hệ thống CSDL ứng dụng vừa và nhỏ. - Cài đặt thành thạo các hệ thống CSDL và hệ quản trị CSDL. - Quản lý, bảo trì và nâng cấp các hệ thống cơ sở dữ liệu vừa và nhỏ. - Phát triển ứng dụng nhỏ để khai thác và quản trị các hệ thống cơ sở dữ liệu. - Tham gia đảm bảo an toàn và bảo mật cho hệ thống cơ sở dữ liệu - Thực hiện các giải pháp có sẵn để khắc phục sự cố trong hệ thống CSDL - Tự nâng cao năng lực chuyên môn và có khả năng làm việc theo nhóm. - Có tính độc lập, chịu trách nhiệm cá nhân trong đơn vị công tác kỹ thuật của mình. 1.2. Chính trị, đạo đức, Thể chất và quốc phòng * Chính trị, đạo đức - Có nhận thức đúng về đường lối xây dựng và phát triển đất nước, hiến pháp và pháp luật, ý thức được trách nhiệm của bản thân về lao động, tác phong, luôn vươn lên và tự hoàn thiện. - Luôn chấp hành các nội qui, qui chế của nhà trường. - Có trách nhiệm, thái độ học tập chuyên cần và cầu tiến. - Có trách nhiệm, thái độ ứng xử, giải quyết vấn đề nghiệp vụ hợp lý.
* Thể chất và quốc phòng - Có sức khoẻ, lòng yêu nghề, có ý thức đầy đủ về bản thân, với cộng đồng và xã hội. - Có nhận thức đúng về đường lối xây dựng phát triển đất nước, chấp hành hiến pháp và pháp luật, ý thức được trách nhiệm của bản thân về lao động quốc phòng. - Có khả năng tuyên truyền, giải thích về trách nhiệm của công dân đối với nền quốc phòng của đất nước. 2. THỜI GIAN CỦA KHOÁ HỌC VÀ THỜI GIAN THỰC HỌC TỐI THIỂU 2.1. Thời gian của khoá học và thời gian thực học tối thiểu: - Thời gian đào tạo: 2 năm - Thời gian học tập : 90 tuần - Thời gian thực học tối thiểu : 2550h. - Thời gian ôn, kiểm tra hết môn và thi : 210h; Trong đó thi tốt nghiệp: 60h 2.2. Phân bổ thời gian thực học tối thiểu: - Thời gian học các môn học chung bắt buộc:180 h - Thời gian học các môn học, mô đun đào tạo nghề: 2370 h + Thời gian học bắt buộc: 2015h; Thời gian học tự chọn: 535 h. + Thời gian học lý thuyết: 805 h; Thời gian học thực hành: 1565 h 3. DANH MỤC CÁC MÔN HỌC, MÔ-ĐUN ĐÀO TẠO BẮT BUỘC, THỜI GIAN VÀ PHÂN BỔ THỜI GIAN; ĐỀ CƯƠNG CHI TIẾT CHƯƠNG TRÌNH MÔN HỌC, MÔ- ĐUN ĐÀO TẠO NGHỀ BẮT BUỘC. 3.1. Danh mục các môn học, mô đun đào tạo nghề bắt buộc Thời gian Thời gian của môn học, Mã đào tạo mô-đun (giờ) MH, Tên môn học, mô-đun Trong đó Năm Học Tổng MĐ Giờ Gìơ học kỳ số LT TH I Các môn học chung 180 121 59 MH 01 Chính trị 1 1 30 24 6 MH 02 Giáo dục thể chất 1 1 30 0 30 MH 03 Pháp luật 1 1 15 11 4 Giáo dục quốc phòng – An MH 04 1 1 45 30 15 ninh MH 05 Ngoại ngữ 1 1 60 56 4 Các môn học, mô-đun đào 1835 625 1210 II tạo nghề bắt buộc Các môn học, mô đun kỹ II.1 360 160 200 thuật cơ sở MĐ 06 Tin học đại cương 1 1 75 30 45 MĐ 07 Tin học văn phòng 1 1 120 40 80 MĐ 08 Internet 1 1 45 15 30 MH 09 Toán ứng dụng 1 1 60 45 15
MH 10 Anh văn chuyên ngành 1 2 60 30 30 Các môn học, mô đun II.2 1475 465 1010 chuyên môn nghề MĐ 11 Lập trình căn bản 1 1 90 30 60 MH 12 Kiến trúc máy tính 1 2 90 45 45 MH 13 Cơ sở dữ liệu 1 2 60 40 20 MH 14 Mạng máy tính 1 2 90 40 50 Cấu trúc dữ liệu và giải MH 15 1 2 60 40 20 thuật MĐ 16 Hệ quản trị CSDL 1 2 90 30 60 MĐ 17 Nguyên lý hệ điều hành 1 2 60 40 20 MĐ 18 Hệ thống thông tin quản lý 2 1 60 20 40 Phân tích và thiết kế hệ MH 19 2 1 75 40 35 thống thông tin MĐ 20 Quản trị mạng 2 1 120 40 80 MĐ 21 An toàn bảo mật dữ liệu 2 1 60 20 40 MĐ 22 Quản trị hệ thống CSDL 2 2 260 80 180 MH 23 Thực tập tốt nghiệp 2 2 360 360 Tổng cộng: 2015 746 1269 3.2. Đề cương chi tiết chương trình môn học, mô đun đào tạo nghề bắt buộc (Nội dung chi tiết kèm theo tại phụ lục 1A và 2A) 4. HƯỚNG DẪN SỬ DỤNG CTKTĐTCN ĐỂ XÁC ĐỊNH CHƯƠNG TRÌNH DẠY NGHỀ ĐÀO TẠO TRÌNH ĐỘ TRUNG CẤP NGHỀ 4.1. Hướng dẫn xác định thời gian cho các môn học, mô-đun đào tạo nghề tự chọn. Ngoài các môn học/mô-đun đào tạo bắt buộc nêu trong mục 3.1 và 3.2, các cơ sở dạy nghề có thể tự xây dựng các môn học/mô-đun đào tạo tự chọn hoặc lựa chọn trong số các môn học/mô-đun đào tạo tự chọn được đề nghị trong chương trình khung. Thời gian dành cho các môn học/mô-đun đào tạo tự chọn được thiết kế sao cho tổng thời gian của các môn học/mô-đun đào tạo tự chọn cộng với tổng thời gian của các môn học/mô-đun đào tạo bắt buộc bằng hoặc lớn hơn thời gian thực học tối thiểu đã quy định nhưng không được quá thời gian thực học đã quy định trong kế hoạch đào tạo của toàn khoá học. 4.2. Hướng dẫn xác định danh mục các môn học, mô đun đào tạo nghề tự chọn; thời gian, phân bổ thời gian và đề cương chi tiết chương trình của từng môn học, mô đun đào tạo nghề tự chọn.
4.2.1. Danh mục môn học, mô đun đào tạo nghề tự chọn và phân bổ thời gian Thời gian Thời gian của môn học, mô Mã Tên môn học, mô đun đào tạo đun (giờ) MH, (Kiến thức, kỹ năng tự Năm Học Tổng Trong đó MĐ chọn) học kỳ số Giờ LT Gìơ TH An toàn vệ sinh công MH 24 1 1 30 20 10 nghiệp MĐ 25 Lắp ráp và cài đặt máy tính 1 2 90 20 70 MĐ 26 Công nghệ đa phương tiện 2 1 120 45 75 MĐ 27 Quản trị thiết bị lưu trữ 2 1 75 30 45 MĐ 28 Lập trình cơ sở dữ liệu 2 2 220 65 155 Tổng cộng: 535 180 355 4.2.2. Đề cương chi tiết chương trình môn học, mô đun đào tạo nghề tự chọn (Nội dung chi tiết kèm theo tại phụ lục 3A và 4A) 4.3 Hướng dẫn xác định chương trình chi tiết của các môn học, mô đun đào tạo nghề bắt buộc trong chương trình dạy nghề của trường Chương trình chi tiết của các môn học / mô đun đã có trong chương trình khung chỉ quy định chi tiết đến các bài học. Các Cơ sở đào tạo nghề có thể tự xây dựng chương trình chi tiết hơn đến nội dung của từng bài để thuận lợi cho giáo viên khi lên lớp giảng dạy. 4.4 Hướng dẫn xây dựng chương trình chi tiết của các môn học, mô-đun đào tạo nghề tự chọn - Thời gian, Nội dung của các môn học, mô-đun đào tạo nghề tự chọn do trường tự xây dựng sẽ được xác định căn cứ vào mục tiêu đào tạo và yêu cầu đặc thù của ngành, nghề hoặc vùng miền. - Thời gian, Nội dung của các môn học, mô-đun đào tạo nghề tự chọn do trường lựa chọn theo kiến nghị trong chương trình khung sẽ xác định theo quy định đã có trong chương trình khung. Trên cơ sở các quy định này, trường tự xây dựng, thẩm định và ban hành chương trình chi tiết của các môn học tự chọn cho trường mình. 4.5. Hướng dẫn kiểm tra sau khi kết thúc môn học, mô-đun đào tạo nghề và hướng dẫn thi tốt nghiệp. 4.5.1. Kiểm tra kết thúc môn học, mô đun đào tạo nghề: - Hình thức kiểm tra hết môn : Viết ,vấn đáp , trắc nghiệm ,bài tập thực hành - Thời gian kiểm tra + Lý thuyết không quá 120 phút + Thực hành không quá 8 giờ * Về kiến thức Được đánh giá bằng các bài kiểm tra viết, các buổi thuyết trình, chất lượng sản phẩm và ý nghĩa của quá trình sản xuất. Đánh giá cụ thể theo các môđun theo trình tự các mức độ sau: - Tổng hợp đầy đủ, chính xác các kiến thức đã học. - Phân tích chặt chẽ và logic các kiến thức đã học.
- Ứng dụng các kiến thức đã học vào cài đặt, khai thác, quản lý, nâng cấp, bảo trì, bảo mật các hệ thống Cơ sở dữ liệu và tham gia phân tích thiết kế hệ thống thông tin doanh nghiệp, có ý tưởng hay đưa ra để giải quyết vấn đề có hiệu quả nhất. - Trình bày đầy đủ Nội dung các kiến thức cơ sở có liên quan. * Về kỹ năng Kết quả thực hành sẽ được đánh giá theo trình tự từ đơn giản đến phức tạp qua quan sát, chấm điểm theo công việc và sản phẩm: - Độc lập công tác đạt kết quả tốt, chủ động, có khả năng hướng dẫn kèm cặp các đồng nghiệp có bậc thấp. - Thực hiện được các công việc trong phạm vi sử dụng các trang thiết bị sẵn có. - Thiết kế và hoàn thiện quy trình công nghệ, tổ chức thực hiện một cách hoàn chỉnh. - Tổ chức và điều hành sản xuất hợp lý, thu xếp, bố trí lập kế hoạch kiểm tra các biện pháp an toàn và cải thiện điều kiện nơi làm việc. * Về thái độ Được đánh giá qua bảng kiểm và nhận xét: - Cẩn thận, nghiêm túc trong công việc. - Trung thực trong kiểm tra, có trách nhiệm và có ý thức giữ gìn bảo quản tài sản, máy móc, dụng cụ, tiết kiệm vật tư, phấn đấu đạt năng suất và chất lượng cao nhất, đảm bảo an toàn trong quá trình sản xuất. - Có ý thức bảo vệ môi trường, bình đẳng trong giao tiếp. - Quan tâm đến đồng đội và xã hội. - Khả năng làm việc theo nhóm. 4.5.2. Thi tốt nghiệp Học sinh sinh viên phải tham gia học tập đầy đủ các môn học/ Mô-đun đào tạo có trong chương trình và thi tốt nghiệp cuối khóa đạt sẽ được cấp bằng tốt nghiệp Trung cấp nghề. Số TT Môn thi Hình thức thi Thời gian thi 1 Chính trị Viết hoặc vấn đáp Không quá 120 phút 2 Kiến thức, kỹ năng nghề -Lý thuyết nghề Viết hoặc vấn đáp Không quá 180 phút + Cơ sở dữ liệu + Hệ quản trị CSDL + PTTK hệ thống - Thực hành nghề Bài thi thực hành Không quá 24 giờ + Cài đặt HQTCSDL + Thiết lập CSDL theo mẫu + Khai thác cơ sở dữ liệu theo yêu cầu - Lý thuyết từ 3 – 4 câu hỏi tổng hợp các môn học/ Mô-đun chuyên ngành đã nêu - Thực hành hoàn thành 1 sản phẩm hoặc 1 công đoạn sản phẩm trong thời gian từ 8 giờ đến 24 giờ Đối với học viên khá, giỏi có thể làm Đề tài tốt nghiệp theo các đề tài
4.6. Hướng dẫn xác định thời gian và nội dung các hoạt động giáo dục ngoại khóa (được bố trí ngoài thời gian đào tạo) nhằm đạt được mục tiêu giáo dục toàn diện. - Để học sinh có nhận thức đầy đủ về nghề nghiệp đang theo học, trường có thể bố trí tham quan một số cơ sở doanh nghiệp đang sản xuất kinh doanh phù hợp với nghề đào tạo (chủ yếu các doanh nghiệp có việc lưu trữ trên hệ thống cơ sở dữ liệu hoặc các trung tâm lưu trữ dữ liệu, các công ty phần mềm. - Thời gian được bố trí ngoài thời gian đào tạo chính khoá. 4.7. Các chú ý khác - Khi sử dụng chương trình để giảng dạy cho đối tượng tuyển sinh tốt nghiệp THCS thì cộng thêm chương trình văn hóa THPT theo quy định của Bộ giáo dục và Đào tạo trong chương trình khung giáo dục TCCN. - Khi các trường thiết kế hoặc lựa chọn xong các môn học/mô-đun tự chọn có thể sắp xếp lại mã môn học/mô-đun trong chương đào tạo của trường mình để dễ theo dõi quản lý. - Có thể lựa chọn các Mô đun / Môn học đào tạo nghề có trong chương trình khung để xây dựng các chương trình dạy nghề trình độ sơ cấp nghề tùy theo nhu cầu của người học, tạo điều kiện thuận lợi cho người học dễ dàng học liên thông lên trình độ cao hơn./. KT. BỘ TRƯỞNG THỨ TRƯỞNG Đàm Hữu Đắc
CHƯƠNG TRÌNH MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã số môn học : MH 15 Thời gian môn học : 60h (Lý thuyết: 40h; Thực hành: 20h) I. VỊ TRÍ, TÍNH CHẤT CỦA MÔN HỌC: - Vị trí : Môn học được bố trí vào học kỳ 2 năm thứ 1, sau khi học viên đã hoàn thành các mô-dun/môn học chung và cơ sở. - Tính chất : Là môn học chuyên môn nghề bắt buộc, kiến thức môn học này là nền tảng hình thành tư duy giải thuật và lập trình có cấu trúc ở những môn học mô đun tiếp theo. II. MỤC TIÊU MÔN HỌC Sau khi học xong môn học này HSSV có khả năng : * Về mặt kiến thức - Hiểu được Nội dung của: dữ liệu, giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. - Phân tích và xác định được dữ liệu, giải thuật, sự kết hợp của dữ liệu và giải thuật trong một chương trình máy tính. - Áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tương thích để giải quyết bài toán đơn giản. - Áp dụng được các phương pháp sắp xếp, tìm kiếm đơn giản, các cấu trúc dữ liệu động (danh sách liên kết), cấu trúc cây và cây nhị phân vào giải quyết các bài toán. * Về mặt kỹ năng - Thực hành (cài đặt và biên dịch) các bài toán sử dụng các cấu trúc và giải thuật đã học. * Về mặt thái độ - Nghiêm túc trong học tập và thực hiện tốt các yêu cầu được giao. - Luôn động não suy nghĩ. thường xuyên luyện tập tư duy trong việc học - Rèn luyện tính cẩn thận, khoa học trong công việc học tập, nghiên cứu. III. NỘI DUNG MÔN HỌC 1 Nội dung tổng quát và phân phối thời gian: Thời gian Số Kiểm tra* Tên chương mục Tổng Lý Thực hành TT (LT hoặc số thuyết Bài tập TH) Tổng quan về Cấu trúc dữ liệu và 5 5 giải thuật I - Tổng quan về Cấu trúc dữ liệu và giải thuật - Các kiểu dữ liệu II Đệ quy và giải thuật đệ quy 10 5 5 - Khái niệm về đệ qui - Giải thuật đệ quy
Cấu trúc dữ liệu động 22 15 7 * - Cấu trúc dữ liệu động III - Danh sách liên kết - Ngăn xếp và hàng đợi (Stack và Queue) IV Các phương pháp sắp xếp cơ bản 15 10 5 * - Định nghĩa bài toán sắp xếp - Các phương pháp sắp xếp V Tìm kiếm 8 5 3 * - Tìm kiếm tuyến tính - Tìm kiếm nhị phân Cộng : 60 40 20 *Ghi chú: Thời gian kiểm tra lý thuyết được tính vào giờ lý thuyết, kiểm tra thực hành được tính vào giờ thực hành. Chương 3: Cấu trúc dữ liệu động Mục tiêu : - Xác định được sự cần thiết khi xây dựng cấu trúc dữ liệu động. - Ghi nhớ (tính chất, chức năng, cách khai báo) kiểu dữ liệu con trỏ. - Định nghĩa được danh sách liên kết. - Khai thác được các loại danh sách liên kết: liên kết đơn; kép; nối vòng (về cách tổ chức và các thao tác xử lý cơ bản trên danh sách liên kết). - Thực hành (lập trình và biên dịch) được với các bài toán sử dụng danh sách liên kết. - Khảo sát một vài dạng danh sách thông dụng khác: Stack và Queue (định nghĩa, cách biểu diễn dạng mảng và danh sách). - Thực hành (lập trình và biên dịch) được với các bài toán sử dụng Stack và Queue. Nội dung Thời gian : 22 h (LT: 15 h ; TH: 7h) 1. Cấu trúc dữ liệu động Thời gian : 4h 1.1. Nhu cầu xây dựng cấu trúc dữ liệu động 1.2. Kiểu dữ liệu con trỏ (biến không động, con trỏ, biến động) 2. Danh sách liên kết Thời gian : 12h 2.1. Định nghĩa 2.2. Các hình thức tổ chức 2.3. Danh sách liên kết đơn (cách tổ chức, các thao tác cơ bản: chèn; tìm; hủy; duyệt danh sách) 2.4. Danh sách liên kết kép (cách tổ chức, các thao tác cơ bản: chèn; tìm; hủy; duyệt danh sách) 2.5. Danh sách liên kết nối vòng (cách tổ chức, các thao tác cơ bản: chèn; tìm; hủy;
duyệt danh sách) 3. Ngăn xếp và hàng đợi (Stack và Queue) Thời gian : 6h 3.1. Stack (Định nghĩa, cách biểu diễn: dùng mảng; dùng danh sách). 3.2. Queue (Định nghĩa, cách biểu diễn: dùng mảng; dùng danh sách) Chương 5: Tìm kiếm Mục tiêu : - Khảo sát giải thuật tìm kiếm tuyến tính, nhị phân cài đặt và đánh giá được độ phức tạp của giải thuật. - Thực hành (lập trình và biên dịch) được với các bài toán sử dụng giải thuật tìm kiếm tuyến tính, nhị phân Nội dung: Thời gian: 8 h (LT: 5h ; TH: 3h) 1.Tìm kiếm tuyến tính Thời gian : 4h 1.1. Giải thuật 1.2. Cài đặt 1.3. Đánh giá giải thuật 2. Tìm kiếm nhị phân Thời gian : 4h 2.1. Giải thuật 2.2. Cài đặt 2.3. Đánh giá giải thuật Lập kế hoạch bài dạy : STT TÊN CHƯƠNG THỜI GIAN THỜI GIAN THỰC HIỆN BÀI DẠY 4x4h(4 giáo án lý thuyết :Chương III Cấu trúc (15hLT)+Chương V (1hLT)) 1 dữ liệu động 22h(15hLT+7hTH) 2x4h (2 giáo án thực hành :Chương III (7hTH) +Chương V(1hTH)). 1x4h(1 giáo án lý thuyết : Chương V (4hLT)) Tìm kiếm 2 8h(5hLT+3hTH) 1x4h (1 giáo án thực hành : Chương V (2hTH)
GIÁO ÁN SỐ: 1 Thời gian thực hiện: 4h Tên chương: Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Thực hiện ngày tháng năm TÊN BÀI: Bài 1: Cấu trúc dữ liệu động MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: *Phân biệt được cấu trúc dữ liệu động và cấu trúc dữ liệu tĩnh *Mô tả được cấu trúc và cách sử dụng của biến con trỏ *Vận dụng, khai báo được biến con trỏ vào bài tập ĐỒ DÙNG VÀ PHƯƠNG TIỆN DẠY HỌC Giáo án, bài giảng chi tiết, giáo trình cấu trúc dữ liệu và giải thuật, bảng, phấn, bảng biểu I. ỔN ĐỊNH LỚP HỌC: Thời gian: 1’ + Điểm danh + Nhắc nhở II. THỰC HIỆN BÀI HỌC TT NỘI DUNG HOẠT ĐỘNG DẠY HỌC THỜI HOẠT ĐỘNG CỦA HOẠT ĐỘNG GIAN GIÁO VIÊN CỦA HỌC SINH 1 Dẫn nhập -GV gọi tên HS trả 5‘ Trả bài cũ và dẫn nhập vào bài. bài mới. -GV nêu câu hỏi. -HS lắng nghe câu hỏi của GV. -GV lắng nghe câu -HS trả lời câu hỏi. trả lời của HS. -HS lắng nghe -GV nhận xét câu trả nhận xét của GV. lời và đánh giá điểm. -GV dẫn nhập vào -HS lắng nghe và phần bài mới. định hình những nội dung sắp học. 2 Giảng bài mới Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Bài 1: Cấu trúc dữ liệu
động GV giới thiệu sơ HS lắng nghe, suy 17’ I.Nhu cầu xây dựng cấu lược về các kiểu cấu nghĩ , trả lời câu trúc dữ liệu động trúc đã học, đặt câu hỏi và viết một số ý hỏi và giải thích vì quan trọng mà GV sao có cấu trúc dữ nhấn mạnh. liệu động. II.Cấu trúc dữ liệu động GV đọc và ghi khái HS lắng nghe và 5’ II.1.Cấu trúc dữ liệu tĩnh niệm cấu trúc dữ liệu ghi khái niệm vào tĩnh lên bảng. tập. GV đặt câu hỏi và HS trả lời câu hỏi. 6’ gọi học sinh trả lời GV nhận xét, bổ HS lắng nghe và 11’ sung câu trả lời của ghi vào tập. HS và đọc hoàn chỉnh câu trả lời để học ghi vào tập. GV cho thời gian HS HS xem tài liệu và 5’ xem tài liệu tư duy suy nghĩ. lại bài. II.2 Cấu trúc dữ liệu động GV nhắc lại phần HS lắng nghe, suy 10’ giới thiệu sơ lược- nghĩ và trả lời câu chuyển ý , đặt câu hỏi. hỏi,cho ví dụ. GV tổ chức thảo HS thảo luận và 5’ luận nhóm. đưa ra ý kiến. a.Biến không động GV lắng nghe câu HS lắng nghe- ghi 7’ trả lời, nhận xét và bài vào tập. bổ sung câu trả lời. b.Biến động GV đặt câu hỏi và HS lắng nghe và trả 8’ gọi HS trả lời. lời câu hỏi. GV lắng nghe câu HS lắng nghe- ghi 5’ trả lời, nhận xét và bài vào tập. bổ sung câu trả lời. Lưu ý: GV đưa ra một số HS chú ý lắng 5’ lưu ý để HS hiểu bài. nghe.
GV cho thời gian HS HS viết bài. viết bài vào tập. III.Biến con trỏ III.1 Giới thiệu GV giới thiệu sơ HS chú ý lắng 10’ lược và dẫn nhập nghe. vào phần mới. III.2 Định nghĩa kiểu GV đặt câu hỏi và HS lắng nghe và trả 5’ con trỏ gọi HS trả lời. lời câu hỏi. GV lắng nghe câu HS lắng nghe- ghi 3’ trả lời, nhận xét và bài vào tập. bổ sung câu trả lời. GV cho ví dụ minh HS quan sát. 4’ họa. III.3 Khai báo biến con GV viết khai báo lên HS chú ý và tự làm 5’ trỏ bảng và cho ví dụ ví dụ. minh họa. GV giải thích ví dụ HS chú ý lắng 3’ trên. nghe. GV cho thời gian HS HS ghi khai báo 5’ ghi bài vào tập. vào tập. III.4 Mẫu chung để định GV dán bảng biểu HS xem tài liệu, 5’ nghĩa kiểu và khai báo lên bảng, gọi HS quan sát bảng biểu. các biến con trỏ quan sát. GV cho ví dụ và gọi Một HS lên bảng 7’ HS lên bảng làm. làm, các HS còn lại làm vào tập. GV nhận xét, giải HS lắng nghe và 3’ thíchvà bổ sung sửa bài vào tập. thêm vào ví dụ. III.5 Cấp phát vùng nhớ GV giới thiệu, đưa HS quan sát,lắng 4’ cho biến ra một ví dụ minh nghe và ghi ví dụ họa, vẽ hình lên vào tập. bảng, giải thích ví dụ
trên. Lưu ý: GV lưu ý một số vấn HS lắng nghe và 3’ đề và cho ví dụ minh quan sát. họa. III.6 Giải phóng vùng GV đưa ra một ví dụ HS lắng nghe và 4’ nhớ của biến minh họa, giải thích ghi ví dụ vào tập. ví dụ trên. 3 Củng cố kiến thức và kết thúc bài -Nhấn mạnh trọng tâm bài Giáo viên đặt ra câu HS lắng nghe, trả 5’ học ở phần I, II.2, III.2, III.3, hỏi để học sinh nắm lời câu hỏi. III.4, III.5 vững tri thức, mở rộng và vận dụng tri thức đã lĩnh hội. -Nhận xét tình hình học của GV nhận xét tinh HS lắng nghe. 4’ lớp thần, thái độ học tập của lớp. -Nêu kế hoạch của tiết tới GV giới thiệu sơ HS ghi chép những 5’ lược về nội dung tiết nội dung liên quan sau. đến tiết tiếp sau. 4 Hướng dẫn tự học Bài tập về nhà: 15’ 1.Ứng dụng biến con trỏ? 2.Con trỏ và mảng có mối quan hệ như thế nào? Nguồn tài liệu tham khảo Tên sách:Cấu trúc dữ liệu Tên tác giả: Nguyễn Trung Trực Tên NXB: Trường ĐH Bách Khoa Hồ Chí Minh Năm XB: 1993 TRƯỞNG KHOA TRƯỞNG TỔ MÔN Ngày tháng năm GIÁO VIÊN Nguyễn Ngọc Duyên
Giáo án số: 1(Giáo án chi tiết) Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Bài 1: CẤU TRÚC DỮ LIỆU ĐỘNG 1.Dẫn nhâp: *Đặt ra câu hỏi để kiểm tra kiến thức cũ. Câu hỏi: 1.Đệ quy là gì? Điều kiện để đệ quy? Ứng dụng ? 2.Nêu các kiểu cấu trúc dữ liệu động mà bạn đã tìm hiểu trước ở nhà? Trả lời: 1. -Đệ quy là đưa ra một định nghĩa và sử dụng lại chính định nghĩa đang được chứng minh. -Điều kiện: Tồn tại bước đệ quy. Có điều kiện dừng. -Ứng dụng: Sử dụng trong việc sắp xếp hoặc để gọi lại những hàm thủ tục có trong nó. VD: trong giải thuật quicksort, tháp hà nội, 2. Các kiểu cấu trúc dữ liệu động là biến con trỏ và danh sách liên kết, +Dẫn nhập vào bài mới: I.Nhu cầu xây dựng cấu trúc dữ liệu động: Tất cả các biến thuộc các kiểu dữ liệu vô hướng chuẩn hay các biến thuộc các kiểu dữ liệu có cấu trúc mà ta đã học và sử dụng được gọi là biến tĩnh. Sở dĩ gọi là biến tĩnh bởi vì khi gặp khai báo các biến này, máy sẽ dành sẵng số ô nhớ cần thiết cho biến đó mặc dù biến đó có dùng đến hay chưa. Câu hỏi: Các loại biến tĩnh đã học gồm có các loại nào? Trả lời: Biến kiểu số thực, số nguyên, kiểu kí tự, Giải thích: Vậy biến tĩnh có kích thước, kiểu dữ liệu và địa chỉ không đổi, các biến này sẽ tồn tại trong suốt quá trình chương trình được thực thi → Gây lãng phí vùng nhớ. Để khắc phục nhược điểm này các ngôn ngữ lập trình cấp cao như Pascal, C, cho phép sử dụng một loại biến khác biến tĩnh được gọi là biến động, biến động là một dạng của của cấu trúc dữ liệu động. II.Cấu trúc dữ liệu động: II.1 Cấu trúc dữ liệu tĩnh: Khái niệm: Một số đối tượng dữ liệu không thay thay đổi được kích thước, cấu trúc, trong suốt quá trình tồn tại. Các đối tượng dữ liệu thuộc những kiểu dữ liệu gọi là kiểu dữ liệu tĩnh. Câu hỏi: Nêu một số kiểu dữ liệu tĩnh? 1
Trả lời: Một số kiểu dữ liệu tĩnh : các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiểu thực, kiểu nguyên, kiểu ký tự hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng (cho học sinh thời gian chép bài vào tập) II.2 Cấu trúc dữ liệu động: Chuyển ý: Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này thường cứng ngắt, gò bó → khó diễn tả được thực tế vốn sinh động, phong phú. VD thực tế: Mô tả, quản lý một đối tượng ‘ con người ‘ cần thể hiện các thông tin tối thiểu như: Họ tên Số CMND Cha mẹ Việc biểu diễn một đối tượng có nhiều thành phần thông tin như trên có thể sử dụng kiểu bảng ghi. Tuy nhiên, cần lưu ý cha, mẹ của một người cũng là các đối tượng kiểu NGUOI, do vậy về nguyên tắc cần phải có định nghĩa như sau: TYPE NGUOI=record Hoten: char[30] ; So_CMND: integer ; Cha_Me NGUOI ; End; Nhưng với khai báo trên, các ngôn ngữ lập trình gặp khó khăn trong việc cài đặt không vượt qua được như xác định kích thước của đối tượng kiểu NGUOI? Một số đối tượng dữ liệu trong chu kỳ tồn tại của nó có thể thay đổi về cấu trúc, độ lớn như danh sách các học viên trong một lớp học có thể tăng thêm hoặc giảm đi Nếu dùng những cấu trúc dữ liệu tĩnh đã biết như mảng để biểu diễn → Những thao tác phức tạp, kém tự nhiên → chương trình khó đọc, khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách có hiệu quả. Dữ liệu tĩnh sẽ chiếm vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình → sử dụng bộ nhớ kém hiệu quả. Hướng giải quyết: Cần xây dựng cấu trúc dữ liệu đáp ứng được các yêu cầu: Linh động hơn. Có thể thay đổi kích thước trong suốt thời gian tồn tại. → Cấu trúc dữ liệu động. CHIA LỚP THÀNH NHÓM THẢO LUẬN: Câu hỏi: 1.Nội dung của biến không động ? 2. Nội dung của biến động? Trả lời: 1.Biến không động (biến tĩnh, biến nửa tĩnh) là những biến thỏa:
Được khai báo tường minh, Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này, Được cấp phát vùng nhớ trong vùng dữ liệu (Data segment) hoặc là Stack (đối với biến nửa tĩnh - các biến cục bộ). Kích thước không thay đổi trong suốt quá trình sống. Do được khai báo tường minh, các biến không động có một định danh đã được kết nối với địa chỉ vùng nhớ lưu trữ biến và được truy xuất trực tiếp thông qua định danh đó. Ví dụ : a: integer b[10]: float // a, b là các biến không động 2.Biến động: Trong nhiều trường hợp, tại thời điểm biên dịch không thể xác định trước kích thước chính xác của một số đối tượng dữ liệu do sự tồn tại và tăng trưởng của chúng phụ thuộc vào ngữ cảnh của việc thực hiện chương trình. Các đối tượng dữ liệu có đặc điểm kể trên nên được khai báo như biến động. Biến động là những biến thỏa: o Biến không được khai báo tường minh. o Có thể được cấp phát hoặc giải phóng bộ nhớ khi người sử dụng yêu cầu. o Các biến này không theo qui tắc phạm vi (tĩnh). o Vùng nhớ của biến được cấp phát trong Heap. o Kích thước có thể thay đổi trong quá trình tồn tại. LƯU Ý: biến động không có tên gọi tường minh, làm sao thao tác ? → cách khắc phục là sử dụng 1 biến gọi là biến con trỏ. III.Biến con trỏ: Dẫn nhập: Biến con trỏ là gì? Tại sao lại sử dụng biến con trỏ ? Để biết về vấn đề này chúng ta tiếp tục tìm hiểu phần biến con trỏ. III.1 Giới thiệu: Biến tĩnh có kích thước, kiểu dữ liệu và địa chỉ không đổi, các biến này sẽ tồn tại trong suốt quá trình chương trình được thực thi → Gây lãng phí vùng nhớ.
Để khắc phục nhược điểm này các ngôn ngữ lập trình cấp cao như Pascal, C, cho phép sử dụng một loại biến khác biến tĩnh được gọi là biến động, biến động là một dạng của của cấu trúc dữ liệu động. Biến động không đươc sinh ra lúc bắt đầu chương trình mà được sinh ra trong quá trình thực thi chương trình và khi không còn sử dụng nữa ta có thể xóa biến đó khỏi bộ nhớ (thu hồi vùng nhớ) mà không cần phải đợi đến kết thúc chương trình. Nói cách khác mặc dù gặp kai báo biến nhưng máy không cấp phát ô nhớ cho biến mà chỉ cấp pát khi nào máy cần tới và sau khi dùng xong máy có thể xóa ngay vì thế tiết kiệm được vùng nhớ. Như vậy biến động là biến có thể thay đổi được địa chỉ và vùng nhớ được cấp phát trong quá trình thực thi chương trình.Tuy nhiên, nó có nhược điểm là không truy cập đến chúng được vì địa chỉ không cố định. Để khắc phục nhược điểm trên ta sử dụng một loại biến đặc biệt, biến này chứa địa chỉ của biến động được gọi là biến con trỏ. III.2 Định nghĩa kiểu con trỏ: Câu hỏi: 1.Biến con trỏ thường dùng để làm gì? 2.Cách định nghĩa như thế nào? Trả lời: 1. Biến con trỏ là biến chuyên dùng để chứa địa chỉ của các biến động, giúp ta truy cập đến biến động. 2. Cách định nghĩa biến con trỏ: TYPE = ; Ví dụ: TYPE byteptr = ^ byte ; contro = ^ lylich ; {con trỏ dữ liệu kiểu mẫu tin} lylich = record hoten , quequan : string ; tuoi : integer ; link : contro ; end ; III.3 Khai báo biến con trỏ: Cách 1: Var : pointer ; VD: Var P : pointer ; P là con trỏ tổng quát không ám chỉ đến một kiểu dữ liệu cụ thể nào nên nó có thể chứa địa chỉ của biến có bất kỳ kiểu gì. Cách 2: Var : ; VD: Var Q : ^ integer ;
Q là một con trỏ chứa địa chỉ của biến có kiểu integer. Hay nói cách khác con trỏ Q trỏ đến dữ liệu kiểu integer. III.4 Mẫu chung để định nghĩa kiểu và khai báo các biến con trỏ Bảng biểu: Cách 1: TYPE lylich = record hoten , quequan : string ; tuoi : integer ; link : contro ; end ; contro = ^ lylich ; Var p , q , first, last : contro ; Cách 2: TYPE contro = ^ lylich ; lylich = record hoten , quequan : string ; tuoi : integer ; link : contro ; end ; Var p , q , first, last : contro ; Ví dụ: Hãy định nghĩa kiểu và khai báo biến con trỏ với tên tự đặt có kiểu dữ liệu là kiểu mẫu tin gồm họ tên sinh viên, lớp, giới tính, niên học, điểm. Bài làm: TYPE sinhvien = record hotensv ,lop, gioitinh : string ; nienhoc : integer ; diem: real; link : contro ; end ; contro = ^ sinhvien ; Var a , b , first, last : contro ; III.5 Cấp phát vùng nhớ cho biến Biến con trỏ bản thân là biến tĩnh nên cũng được cấp phát vùng nhớ 4 bytes. Việc cấp phát này diễn ra khi chương trình dịch đọc đến dòng khai báo biến trong khi đó các biến động kiểu lylich chưa được cấp phát vùng nhớ vì chưa được tác động đến. Để cấp phát vùng nhớ cho một biến động ta dùng thủ tục : NEW ( tên biến ). Ví dụ: New ( p )
Trong đó: p^ : mẫu tin p^.hoten , p^.quequan, p^.tuoi : các trường của mẫu tin p^.link : con trỏ p^.link^ : mẫu tin Lưu ý: Con trỏ NIL: là con trỏ đặc biệt, nó không trỏ đến biến động nào cả. Khi ta gán first := nil nghĩa là con trỏ first không hoặc chưa được sử dụng, có giá trị mặc định là 268. Ta có thể gán 2 biến con trỏ hoặc so sánh = hay trên hai biến con trỏ. Ví dụ: P := nil; q := p ; If q = p then Else ; III.6 Giải phóng vùng nhớ của biến Ta sử dụng thủ tục DISPOSE (tên biến) để giải phóng vùng nhớ cho biến động. Ví dụ: dispose ( p ) ; Tóm tắt và lưu ý về cách dùng con trỏ: Việc dùng con trỏ trong chương trình bao gồm các bước sau:  Bước 1: khai báo con trỏ  Bước 2: cấp vùng nhớ cho biến động. Khi đó giá trị biến con trỏ là địa chỉ vùng nhớ vừa cấp phát. (NEW)  Bước 3: điền nội dung vào vùng nhớ đã được cấp và làm việc với nó như với các kiểu dữ liệu khác.  Bước 4: giải phóng vùng nhớ để sử dụng vào việc khác. ( DISPOSE) Bài tập về nhà: 1.Ứng dụng biến con trỏ? 2.Con trỏ và mảng có mối quan hệ như thế nào?
GIÁO ÁN SỐ: 2 Thời gian thực hiện: 4h Tên chương: Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Thực hiện ngày tháng năm TÊN BÀI: Bài 2: Danh sách liên kết MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: * Trình bày được danh sách liên kết đơn trong môn Cấu trúc dữ liệu và giải thuật. * Trình bày được cách tổ chức danh sách liên kết *Trình bày được thao tác cơ bản : khai báo, khởi tạo, chèn, tìm kiếm, hủy, duyệt danh sách. ĐỒ DÙNG VÀ PHƯƠNG TIỆN DẠY HỌC Giáo án, bài giảng chi tiết, giáo trình cấu trúc dữ liệu và giải thuật, bảng, phấn, bảng biểu I. ỔN ĐỊNH LỚP HỌC: Thời gian: 1’ + Điểm danh + Nhắc nhở II. THỰC HIỆN BÀI HỌC TT NỘI DUNG HOẠT ĐỘNG DẠY HỌC THỜI HOẠT ĐỘNG CỦA HOẠT ĐỘNG GIAN GIÁO VIÊN CỦA HỌC SINH 1 Dẫn nhập -GV gọi tên HS trả 5‘ Trả bài cũ và dẫn nhập vào bài. bài mới. -GV nêu câu hỏi. -HS lắng nghe câu hỏi của GV. -GV lắng nghe câu -HS trả lời câu hỏi. trả lời của HS. -GV nhận xét câu trả -HS lắng nghe lời và đánh giá điểm. nhận xét của GV. -GV dẫn nhập vào -HS lắng nghe và phần bài mới dựa định hình những trên bài cũ. nội dung sắp học. 2 Giảng bài mới Bài 2: Danh sách liên kết GV giới thiệu sơ HS lắng nghe, trả 5’ I.Định nghĩa danh sách liên lược bài mới, đặt câu lời câu hỏi. kết hỏi-gọi HS trả lời. GV nhận xét và bổ HS lắng nghe và 4’ sung hoàn chỉnh câu lĩnh hội.
trả lời. 1.Khái niệm GV đọc khái niệm HS lắng nghe, lĩnh 5’ và đưa ra ví dụ minh hội, ghi bài vào tập. họa. 2.Khai báo GV viết khai báo lên HS lĩnh hội, ghi bài 10’ bảng và cho ví dụ vào tập. minh họa. GV viết khởi tạo lên 3.Khởi tạo bảng và cho ví dụ HS lắng nghe, lĩnh 5’ minh họa. hội, ghi bài vào tập. II.Các hình thức tổ chức GV đọc cho HS ghi HS lắng nghe, ghi 10’ danh sách liên kết các hình thức tổ bài vào tập. chức của danh sách liên kết. GV đặt vấn đề và trả HS lắng nghe. lời để HS hiểu bài hơn. III.Danh sách liên kết đơn: 1.Cách tổ chức GV dẫn nhập và cho HS lắng nghe và 8’ HS xem tài liệu. xem tài liệu. GV gọi 1 HS phát HS phát biểu ý kiến biểu ý kiến về cách xây dựng bài. tổ chức sau khi xem tài liệu. GV viết nội dung lên HS viết nội dung 5’ bảng. vào tập. 2.Các thao tác cơ bản GV dẫn nhập và cho HS lắng nghe và 3’ HS xem tài liệu. xem tài liệu. 2.1 Chèn 1 phần tử vào danh sách liên kết đơn a)Chèn vào đầu GV vẽ 1 danh sách HS quan sát. 4’ danh sách liên kết đơn lên bảng và cho ví dụ minh họa. GV viết giải thuật HS quan sát và viết 8’ lên bảng. vào tập.
b)Chèn vào cuối GV cho HS xem tài HS xem tài liệu. 2’ danh sách liệu GV gọi 1 HS cho ví HS làm ví dụ và 5’ dụ và làm ví dụ vừa quan sát. cho. GV nhận xét. HS lắng nghe và 3’ xem tài liệu viết giải thuật vào tập. 2.2 Tìm 1 phần tử trong GV đặt câu hỏi. HS lắng nghe. 2’ danh sách liên kết đơn GV cho HS xem tài HS xem tài liệu và 10’ liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Trả về kết quả có Gọi HS lên bảng viết HS lên bảng viết. 5’ hay không giải thuật. HS quan sát. b)Trả về danh sách Gọi HS lên bảng viết HS lên bảng viết. 5’ có bắt đầu là phần tử giải thuật. HS quan sát. cần tìm 2.3 Xóa 1 phần tử GV đặt câu hỏi. HS lắng nghe. 10’ trong danh sách liên kết đơn GV cho HS xem tài HS xem tài liệu và 13’ liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Xóa phần tử đầu Gọi HS lên bảng viết HS lên bảng viết. 5’ tiên giải thuật. HS quan sát. b)Xóa phần tử cuối Gọi HS lên bảng viết HS lên bảng viết. 7’ cùng giải thuật. HS quan sát. 2.4 Xuất danh sách liên GV đặt câu hỏi. HS lắng nghe. 3’ kết đơn GV cho HS xem tài HS xem tài liệu và 10’ liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Xuất xuôi có đệ Gọi HS lên bảng viết HS lên bảng viết. 4’ qui giải thuật. HS quan sát. b)Xuất xuôi không Gọi HS lên bảng viết HS lên bảng viết. 3’ có đệ qui giải thuật. HS quan sát.
3 Củng cố kiến thức và kết thúc bài -Nhấn mạnh trọng tâm bài Giáo viên đặt ra câu HS lắng nghe, trả 5’ học ở phần I (Khái niệm, hỏi để học sinh nắm lời câu hỏi. khai báo), phần III (Các thao vững tri thức, mở tác cơ bản) rộng và vận dụng tri thức đã lĩnh hội. -Nhận xét tình hình học của GV nhận xét tinh HS lắng nghe. 2’ lớp thần, thái độ học tập -Nêu kế hoạch của tiết tới của lớp. 5’ -Hướng dẫn học sinh xem GV giới thiệu sơ HS ghi chép những 5’ bài trước ở nhà lược về nội dung tiết nội dung liên quan sau. đến tiết tiếp sau. 4 Hướng dẫn tự học Bài tập về nhà: 3’ 1.Ngoài các thao tác cơ bản vừa giới thiệu trong danh sách liên kết đơn, bạn hãy tìm thêm một số thao tác khác như: In, ghép, trộn, tách các phần tử trong danh sách, cho ví dụ minh họa. 2.Danh sách liên kết kép là gì? Danh sách liên kết nối vòng là gì? Cách tổ chức như thế nào? Nguồn tài liệu tham khảo Tên sách:Cấu trúc dữ liệu Tên tác giả: Nguyễn Trung Trực Tên NXB: Trường ĐH Bách Khoa Hồ Chí Minh Năm XB: 1993 TRƯỞNG KHOA TRƯỞNG TỔ MÔN Ngày tháng năm GIÁO VIÊN Nguyễn Ngọc Duyên
Giáo án số: 2(Giáo án chi tiết) Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Bài 2: Danh sách liên kết 1.Dẫn nhâp: *Đặt ra câu hỏi để kiểm tra kiến thức cũ. Câu hỏi: 1.Tóm tắt và lưu ý về cách dùng con trỏ? 2.Con trỏ và mảng có mối quan hệ như thế nào? Trả lời: 1. Việc dùng con trỏ trong chương trình bao gồm các bước sau:  Bước 1: khai báo con trỏ  Bước 2: cấp vùng nhớ cho biến động. Khi đó giá trị biến con trỏ là địa chỉ vùng nhớ vừa cấp phát. (NEW)  Bước 3: điền nội dung vào vùng nhớ đã được cấp và làm việc với nó như với các kiểu dữ liệu khác.  Bước 4: giải phóng vùng nhớ để sử dụng vào việc khác. ( DISPOSE) 2. Con trỏ và mảng có mối quan hệ chặt chẽ và mảng 2 chiều có thể biến thành mảng một chiều nhờ biến con trỏ. 2.Bài giảng mới: I.Định nghĩa danh sách liên kết: Một danh sách (list) là một tập hợp gồm một số hữu hạn phần tử cùng kiểu, có thứ tự. Có 2 cách cài đặt danh sách liên kết là: Cài đặt theo kiểu kế tiếp: ta có danh sách kề hay danh sách đặc. Cài đặt theo kiểu liên kết: ta có danh sách liên kết. 1.Khái niệm: Danh sách liên kết là danh sách mà các phần tử ðýợc nối kết với nhau nhờ vào vùng liên kết của chúng. Nó thích hợp với các phép thêm vào, loại bỏ, ghép các danh sách, Ví dụ:
2.Khai báo: Type ref = ^ itemp ; Itemp = record Info : integer ; Link : ref ; End ; Ví dụ: Khai báo một danh sách học sinh gồn có hoten, phai Type HocSinh = record hoten: string[40] ; phai: boolean ; end; Type ref = ^ itemp; Itemp = record Info = HocSinh ; link=ref ; end ; 3.Khởi tạo: Procedure Khoitao(var p:ref); Begin P:=nil; End; Ví dụ: Khởi tạo một danh sách liên kết biến tùy ý. Procedure Khoitao(var q:ref); Begin P:=nil; End; II.Các hình thức tổ chức danh sách liên kết Tổ chức của một danh sách liên kết là các phần tử của nó có thể chứa ở những vùng nhớ không kế cận nhau trong bộ nhớ và chúng ðýợc nối với nhau nhờ vào vùng liên kết: vùng liên kết của phần tử thứ 1 chứa ðịa chỉ của phần tử thứ 2, vùng liên kết của phần tử thứ 2 chứa ðịa chỉ của phần tử thứ 3 và cứ thế cho ðến phần tử cuối cùng và vùng liên kết của phần tử cuối cùng là NIL. Đặt vấn đề: Danh sách liên kết có cần nhiều dung lượng bộ nhớ không và giới hạn số lượng phần tử là bao nhiêu? →Danh sách liên kết không ðòi hỏi vùng nhớ lớn và không giới hạn số lýợng phần tử. III.Danh sách liên kết đơn: Dẫn nhập: có bao nhiêu loại danh sách liên kết, vậy các loại danh sách liên kết đó có tên gì? Cách tổ chức và các thao tác cơ bản của nó là gì? Để trả lời các câu hỏi này ta bước vào phần kế tiếp. 1.Cách tổ chức danh sách liên kết đơn: Mỗi phần tử liên kết với phần tử ðứng liền sau trong danh sách Mỗi phần tử trong danh sách liên kết ðõn là một cấutrúc có hai thành phần Thành phần dữ liệu : Lýu trữ thông tin về bảnthân phần tử
Thành phần liên kết : Lýu ðịa chỉ phần tử ðứngsau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách. 2.Các thao tác cơ bản: 2.1 Chèn 1 phần tử vào danh sách liên kết đơn a)Chèn vào đầu danh sách Procedure themdau ( var p : ref ; x : integer ) ; Var q : ref ; Begin New ( q ) ; q^. Info := x ; q^. Link := p ; p := q ; end ; b)Chèn vào cuối danh sách Procedure themcuoi ( var p : ref ; x : integer ) ; Var q , t : ref ; Begin New ( q ) ; q^. Info := x ; q^. Link := nil ; if p = nil then p := q else begin t := p ; while t^. Link nil do t := t^. Link ; t^. Link := q ; end ; end ; 2.2 Tìm 1 phần tử trong danh sách liên kết đơn a.Trả về kết quả có hay không: Function Tim1(p:ref; x:integer) :Boolean; Begin
While (p x) do P:=p^.link; If p=nil then Tim1:=false Else Tim1:=True; End; b.Trả về danh sách bắt ðầu là x: function tim2(p:ref; x:integer): ref; begin While (p x) do P:=p^.link; Tim2:=p ; End ; 2.3 Xóa 1 phần tử trong danh sách liên kết đơn a)Xóa phần tử đầu tiên Procedure Xoadau ( var p : ref ) ; Var tam : ref ; Begin If p nil then Begin tam := p ; p := p^. Link ; dispose ( tam ) ; end ; end ; b)Xóa phần tử cuối cùng Procedure Xoacuoi ( var p : ref ) ; Var t , r : ref ; Begin If p nil then If p^. link = nil then xoadau ( p ) Else Begin r := p ; t := p^. Link ; while t^. Link nil do
begin r := t ; t := t^. Link; end ; r^. Link := nil ; dispose ( t ) ; end ; end ; 2.4 Xuất danh sách liên kết đơn a)Xuất xuôi có đệ qui Procedure xuatdq ( p : ref ) ; begin if p nil then begin write ( p^. Info : 4 ) ; xuatdq (p^. Link ) ; end ; end ; b)Xuất xuôi không có đệ qui Procedure xuat ( p : ref ) ; begin if p nil then begin write ( p^. Info : 4 ) ; p := p^. Link ; end ; end ; Bài tập về nhà: 1.Ngoài các thao tác cơ bản vừa giới thiệu trong danh sách liên kết đơn, bạn hãy tìm thêm một số thao tác khác như: In, ghép, trộn, tách các phần tử trong danh sách, cho ví dụ minh họa. 2.Danh sách liên kết kép là gì? Danh sách liên kết nối vòng là gì? Cách tổ chức như thế nào?
GIÁO ÁN SỐ: 3 Thời gian thực hiện: 4h Tên chương: Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Thực hiện ngày tháng năm TÊN BÀI: Bài 2: Danh sách liên kết MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: * Trình bày được danh sách liên kết kép, nối vòng trong môn Cấu trúc dữ liệu và giải thuật. * Trình bày được cách tổ chức danh sách liên kết kép và danh sách liên kết nối vòng. *Trình bày được thao tác cơ bản : chèn, tìm kiếm, hủy, duyệt danh sách. ĐỒ DÙNG VÀ PHƯƠNG TIỆN DẠY HỌC Giáo án, bài giảng chi tiết, giáo trình cấu trúc dữ liệu và giải thuật, bảng, phấn, bảng biểu I. ỔN ĐỊNH LỚP HỌC: Thời gian: 1’ + Điểm danh + Nhắc nhở II. THỰC HIỆN BÀI HỌC TT NỘI DUNG HOẠT ĐỘNG DẠY HỌC THỜI HOẠT ĐỘNG CỦA HOẠT ĐỘNG GIAN GIÁO VIÊN CỦA HỌC SINH 1 Dẫn nhập -GV gọi tên HS trả 5‘ Trả bài cũ và dẫn nhập vào bài. bài mới. -GV nêu câu hỏi. -HS lắng nghe câu hỏi của GV. -GV lắng nghe câu -HS trả lời câu hỏi. trả lời của HS. -HS lắng nghe -GV nhận xét câu trả nhận xét của GV. lời và đánh giá điểm. -GV dẫn nhập vào -HS lắng nghe và phần bài mới dựa định hình những trên bài cũ. nội dung sắp học. 2 Giảng bài mới Bài 2: Danh sách liên kết GV giới thiệu sơ HS lắng nghe và trả 4’
(tiếp theo) lược bài mới, đặt câu lời câu hỏi. hỏi-gọi HS trả lời. GV nhận xét và bổ HS lắng nghe và 2’ sung hoàn chỉnh câu phản hồi( nếu có). trả lời. IV.Danh sách liên kết kép: 1.Cách tổ chức GV đọc cho HS ghi HS lắng nghe, ghi 3’ các hình thức tổ bài vào tập. chức của danh sách liên kết. GV đặt vấn đề và trả HS lắng nghe. 2’ lời để HS hiểu bài hơn. Cho HS xem tài liệu. HS lắng nghe và 3’ xem tài liệu. GV gọi 1 HS phát HS phát biểu ý kiến 5’ biểu ý kiến về cách xây dựng bài. tổ chức sau khi xem tài liệu. 2.Các thao tác cơ bản GV dẫn nhập và cho HS lắng nghe và 5’ HS xem tài liệu. xem tài liệu. 2.1 Chèn 1 phần tử vào GV vẽ 1 danh sách HS quan sát. 5’ danh sách liên kết kép liên kết kép lên bảng và cho ví dụ minh họa. a)Chèn vào đầu danh GV viết giải thuật HS quan sát và viết 5’ sách lên bảng. vào tập. b)Chèn vào cuối danh GV cho HS xem tài HS xem tài liệu. 3’ sách liệu GV gọi 1 HS cho ví HS làm ví dụ và 5’ dụ và làm ví dụ vừa quan sát. cho. GV nhận xét. HS lắng nghe và 2’ xem tài liệu viết
giải thuật vào tập. 2.2 Tìm 1 phần tử trong GV đặt câu hỏi. HS lắng nghe. 3’ danh sách liên kết kép GV cho HS xem tài HS xem tài liệu và 10’ liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Trả về kết quả có hay Gọi HS lên bảng viết HS lên bảng viết. 5’ không giải thuật. HS quan sát. b)Trả về danh sách có Gọi HS lên bảng viết HS lên bảng viết. 6’ bắt đầu là phần tử cần giải thuật. HS quan sát. tìm 2.3 Xóa 1 phần tử GV đặt câu hỏi. HS lắng nghe. 3’ trong danh sách liên kết kép GV cho HS xem tài HS xem tài liệu và 8’ liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Xóa phần tử đầu tiên Gọi HS lên bảng viết HS lên bảng viết. 4’ giải thuật. HS quan sát. b)Xóa phần tử cuối cùng Gọi HS lên bảng viết HS lên bảng viết. 4’ giải thuật. HS quan sát. 2.4 Xuất danh sách liên GV đặt câu hỏi. HS lắng nghe. 3’ kết kép GV cho HS xem tài HS xem tài liệu và 7’ liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Xuất xuôi có đệ Gọi HS lên bảng viết HS lên bảng viết. 5’ qui giải thuật. HS quan sát. b)Xuất xuôi không Gọi HS lên bảng viết HS lên bảng viết. 5’ có đệ qui giải thuật. HS quan sát. lưu ý GV đưa ra một số HS lắng nghe, suy 2’ lưu ý về danh sách nghĩ. liên kết đơn và danh
sách liên kết kép V.Danh sách liên kết nối GV đặt câu hỏi HS trả lời câu hỏi. 2’ vòng: 1.Cách tổ chức GV đọc cho HS ghi HS lắng nghe, ghi 8’ các hình thức tổ bài vào tập. chức của danh sách liên kết. GV đặt vấn đề và trả HS lắng nghe. 5’ lời để HS hiểu bài hơn. GV dẫn nhập và cho HS lắng nghe và 5’ HS xem tài liệu. xem tài liệu. GV gọi 1 HS phát HS phát biểu ý kiến 5’ biểu ý kiến về cách xây dựng bài. tổ chức sau khi xem tài liệu. GV dẫn nhập và cho HS lắng nghe và 2’ HS xem tài liệu. xem tài liệu. 2.Các thao tác cơ bản GV vẽ 1 danh sách HS quan sát. 3’ liên kết nối vòng lên bảng và cho ví dụ minh họa. 2.1 Chèn 1 phần tử vào GV viết giải thuật HS quan sát và viết 4’ danh sách liên kết nối lên bảng. vào tập. vòng GV cho HS xem tài HS xem tài liệu. 1’ liệu Chú ý: GV đưa ra một số HS lắng nghe. 30’’ lưu ý. GV đặt câu hỏi. HS lắng nghe. 30’’ 2.2 Tìm 1 phần tử trong GV cho HS xem tài HS xem tài liệu và 8’ danh sách liên kết nối liệu và tổ chức thảo tiến hành thảo luận vòng luận nhóm. nhóm. 2.3 Xóa 1 phần tử trong danh sách liên Gọi HS lên bảng viết HS lên bảng viết. 4’ kết nối vòng giải thuật. HS quan sát.
2.4 Xuất danh danh Gọi HS lên bảng viết HS lên bảng viết. 4’ sách liên kết nối vòng giải thuật. HS quan sát. Lưu ý: GV nhấn mạnh một HS lắng nghe. 1’ số vấn đề sai mà HS hay mắc lỗi. 3 Củng cố kiến thức và kết thúc bài -Nhấn mạnh trọng tâm bài Giáo viên đặt ra câu HS lắng nghe, trả 5’ học ở phần IV(Các thao tác hỏi để học sinh nắm lời câu hỏi. cơ bản) và phần V(các thao vững tri thức, mở tác cơ bản) rộng và vận dụng tri thức đã lĩnh hội. -Nhận xét tình hình học của GV nhận xét tinh HS lắng nghe. 2’ lớp thần, thái độ học tập của lớp. -Nêu kế hoạch của tiết tới GV giới thiệu sơ HS ghi chép những 3’ -Hướng dẫn học sinh xem lược về nội dung tiết nội dung liên quan bài trước ở nhà sau. đến tiết tiếp sau. 4 Hướng dẫn tự học Bài tập về nhà: 2’ Ngoài các thao tác cơ bản vừa giới thiệu trong danh sách liên kết kép,danh sách liên kết nối vòng bạn hãy tìm thêm một số thao tác khác như: In, ghép, trộn, tách các phần tử trong danh sách, cho ví dụ minh họa. Nguồn tài liệu tham khảo Tên sách:Cấu trúc dữ liệu Tên tác giả: Nguyễn Trung Trực Tên NXB: Trường ĐH Bách Khoa Hồ Chí Minh Năm XB: 1993 TRƯỞNG KHOA TRƯỞNG TỔ MÔN Ngày tháng năm GIÁO VIÊN Nguyễn Ngọc Duyên
Giáo án số: 3(Giáo án chi tiết) Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Bài 2: Danh sách liên kết (tiếp theo) 1.Dẫn nhâp: *Đặt ra câu hỏi để kiểm tra kiến thức cũ. Câu hỏi: Danh sách liên kết kép là gì? Danh sách liên kết nối vòng là gì? Cách tổ chức như thế nào? Trả lời: Danh sách liên kết kép là danh sách mà mỗi phần tử trong danh sách có kết quả nối với một phần tử đứng trước và một phần tử đứng sau nó. Danh sách liên kết nối vòng là danh sách sách liên kết mà trường link của Node cuối chứa địa chỉ Node đầu tiên. Cách tổ chức: *Danh sách liên kết kép: Ta phải dùng 2 con trỏ, một con trỏ chỉ ðến phần tử ðứng sau (next), một con trỏ chỉ ðến phần tử ðứng trýớc (previous). *Danh sách liên kết nối vòng: Danh sách liên kết nối vòng là danh sách sách liên kết mà trường link của Node cuối chứa địa chỉ Node đầu tiên. 2.Giảng bài mới Dẫn nhập: Danh danh liên kết có 3 loại: danh sách liên kết ðõn, danh sách liên kết kép và danh sách liên kết nối vòng. Ở tiết trýớc chúng ta ðã tìm hiểu về cách tổ chức và các thao tác cõ bản trên danh sách liên kết ðõn, hôm nay, chúng ta hãy tiếp tục hai danh sách liên kết còn lại là danh sách liên kết kép và danh sách liên kết nối vòng. IV.Danh sách liên kết kép: 1.Cách tổ chức Ta phải dùng 2 con trỏ, một con trỏ chỉ ðến phần tử ðứng sau (next), một con trỏ chỉ ðến phần tử ðứng trýớc (previous). Đặt vấn đề: Tại sao người ta lại tổ chức danh sách liên kết kép? Trả lời: Một số ứng dụng ðòi hỏi chúng ta phải duyệt danh sách theo cả hai chiều một cách hiệu quả. Chẳng hạn cho phần tử X cần biết ngay phần tử trýớc X và sau X một cách mau chóng.Trong trýờng hợp này ta phải dùng 2 con trỏ, một con trỏ chỉ ðến phần tử ðứng sau (next), một con trỏ chỉ ðến phần tử ðứng trýớc (previous). 2.Các thao tác cõ bản: 2.1 Chèn 1 phần tử vào danh sách liên kết kép a)Chèn vào đầu danh sách
Procedure themdau ( var p : ref ; x : integer ) ; Var q : ref ; Begin New ( q ) ; q^. Info := x ; if p = nil then begin p : = q ; p^. Link := nil; end; else begin q^. Link := p^. link; q^. Link :=p; p := q; end; end ; b)Chèn vào cuối danh sách Procedure themdau ( var p : ref ; x : integer ) ; Var q , t : ref ; Begin New ( q ) ; q^. Info := x ; q^. Link := nil ;
if p = nil then p := q else begin t := p ; while t^. Link nil do t^. Link := q; t := q ; end ; end ; 2.4 Tìm 1 phần tử trong danh sách liên kết kép a.Trả về kết quả có hay không: Function Tim1(p:ref; x:integer) :Boolean; Begin While (p x) do P:=p^.link; If p=nil then Tim1:=false Else Tim1:=True; End; b.Trả về danh sách bắt ðầu là x: function tim2(p:ref; x:integer): ref; var t: ref; begin t := p ; While (p x) do P:=p^.link; Tim2:=p ; End ; 2.5 Xóa 1 phần tử trong danh sách liên kết đơn a)Xóa phần tử đầu tiên Procedure Xoadau ( var p : ref ) ; Var tam : ref ; Begin If p nil then Begin tam := p ; p := p^. Link ;
dispose ( tam ) ; end ; end ; b)Xóa phần tử cuối cùng Procedure Xoacuoi ( var p : ref ) ; Var t , r : ref ; Begin If p nil then If p^. link = nil then xoadau ( p ) Else Begin r := p ; t := p^. Link ; while t^. Link nil do begin r := t ; t := t^. Link; end ; r^. Link := nil ; dispose ( t ) ; end ; end ; 2.4 Xuất danh sách liên kết đơn a)Xuất xuôi có đệ qui Procedure xuatdq ( p : ref ) ; begin if p nil then begin write ( p^. Info : 4 ) ; xuatdq (p^. Link ) ; end ; end ; b)Xuất xuôi không có đệ qui Procedure xuat ( p : ref ) ; begin if p nil then begin write ( p^. Info : 4 ) ; p := p^. Link ; end ; end ; Lưu ý:
Danh sách liên kết kép về mặt cơ bản có tính chất như danh sách liên kết đơn. Tuy nhiên nó có một số tính chất khác danh sách liên kết đơn như sau: Danh sách liên kết kép có mối liên kết hai chiều nên từ một phần tử bất kì có thể truy xuất một phần tử bất kì khác. Trong khi trên danh sách liên kết đơn ta chỉ có thể truy xuất đến các phần tử đứng sau một phần tử cho trước. Điều này dẫn đến việc ta có thể dễ dàng hủy phần tử cuối danh sách liên kết kép, con trên danh sách liên kết đơn thao tác này tổn chi phí O(n). Bù lại, danh sách liên kết kép tốn chi phí gấp đôi so với danh sách liên kết đơn cho việc lưu trữ các mối liên kết. Điều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp. Như vậy, cần cân nhắc lựa chọn CTDL hợp lý khi cài đặt cho một ứng dụng cụ thể. V.Danh sách liên kết nối vòng: 1.Cách tổ chức Danh sách liên kết nối vòng là danh sách sách liên kết mà trường link của Node cuối chứa địa chỉ Node đầu tiên. 2.Các thao tác cơ bản 2.1 Chèn 1 phần tử vào danh sách liên kết nối vòng Chú ý: Danh sách rỗng : p = null Danh sách có 1 node: p^. Link := p Procedure themdau ( var p : ref ; x : integer ) ; Var q : ref ; Begin New ( q ) ; q^. Info := x ; q^. Link := p ; p := q ; end ; b)Chèn vào cuối danh sách Procedure themcuoi ( var p : ref ; x : integer ) ; Var q , t : ref ; Begin New ( q ) ;
q^. Info := x ; q^. Link := nil ; if p = nil then p := q else begin t := p ; while t^. Link nil do t := t^. Link ; t^. Link := q ; end ; end ; 2.6 Tìm 1 phần tử trong danh sách liên kết đơn a.Trả về kết quả có hay không: Function Tim1(p:ref; x:integer) :Boolean; Begin While (p x) do P:=p^.link; If p=nil then Tim1:=false Else Tim1:=True; End; b.Trả về danh sách bắt ðầu là x: function tim2(p:ref; x:integer): ref; begin While (p x) do P:=p^.link; Tim2:=p ; End ; 2.7 Xóa 1 phần tử trong danh sách liên kết đơn a)Xóa phần tử đầu tiên Procedure Xoadau ( var p : ref ) ; Var tam : ref ; Begin If p nil then Begin tam := p ; p := p^. Link ; dispose ( tam ) ; end ; end ; b)Xóa phần tử cuối cùng Procedure Xoacuoi ( var p : ref ) ; Var t , r : ref ;
Begin If p nil then If p^. link = nil then xoadau ( p ) Else Begin r := p ; t := p^. Link ; while t^. Link nil do begin r := t ; t := t^. Link; end ; r^. Link := nil ; dispose ( t ) ; end ; end ; 2.4 Xuất danh sách liên kết đơn a)Xuất xuôi có đệ qui Procedure xuatdq ( p : ref ) ; begin if p nil then begin write ( p^. Info : 4 ) ; xuatdq (p^. Link ) ; end ; end ; b)Xuất xuôi không có đệ qui Procedure xuat ( p : ref ) ; begin if p nil then begin write ( p^. Info : 4 ) ; p := p^. Link ; end ; end ; Bài tập về nhà: Ngoài các thao tác cơ bản vừa giới thiệu trong danh sách liên kết kép,danh sách liên kết nối vòng bạn hãy tìm thêm một số thao tác khác như: In, ghép, trộn, tách các phần tử trong danh sách, cho ví dụ minh họa.
GIÁO ÁN SỐ: 4 Thời gian thực hiện: 4h Tên chương: Chương III: CẤU TRÚC DỮ LIỆU ĐỘNG Chương V : TÌM KIẾM Thực hiện ngày tháng năm TÊN BÀI: Bài 3: Ngăn xếp và hàng đợi (Stack và Queue)- Chương III Bài 1: Tìm kiếm tuyến tính – Chương V MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: -Trình bày được cấu trúc Stack và cấu trúc Queue -Nhận biết được cấu trúc Stack và cấu trúc Queue -Mô tả được bài toán tìm kiếm trong tin học ĐỒ DÙNG VÀ PHƯƠNG TIỆN DẠY HỌC Giáo án, bài giảng chi tiết, giáo trình cấu trúc dữ liệu và giải thuật, bảng, phấn, bảng biểu I. ỔN ĐỊNH LỚP HỌC: Thời gian: 1’ + Điểm danh + Nhắc nhở II. THỰC HIỆN BÀI HỌC TT NỘI DUNG HOẠT ĐỘNG DẠY HỌC THỜI HOẠT ĐỘNG CỦA HOẠT ĐỘNG GIAN GIÁO VIÊN CỦA HỌC SINH 1 Dẫn nhập -GV gọi tên HS trả 5‘ Trả bài cũ và dẫn nhập vào bài. bài mới. -GV nêu câu hỏi. -HS lắng nghe câu hỏi của GV. -GV lắng nghe câu -HS trả lời câu hỏi. trả lời của HS. -HS lắng nghe -GV nhận xét câu trả nhận xét của GV. lời và đánh giá điểm. -GV dẫn nhập vào -HS lắng nghe và phần bài mới dựa định hình những trên bài cũ. nội dung sắp học. 2 Giảng bài mới Bài 3: Ngăn xếp và hàng đợi (Stack và Queue)
I.Ngăn xếp (Stack) GV giới thiệu sơ HS lắng nghe và trả 4’ lược bài mới, đặt câu lời câu hỏi. hỏi-gọi HS trả lời. GV nhận xét và bổ HS lắng nghe và 2’ sung hoàn chỉnh câu phản hồi( nếu có). trả lời. 1.Định nghĩa GV cho HS xem tài 1 HS đọc, các HS 3’ liệu, gọi 1 bạn đọc còn lại lắng nghe định nghĩa. và xem tài liệu. GV dán hình vẽ về HS quan sát và suy 5’ cấu trúc Stack và nghĩ. Queue cho HS quan sát và so sánh. Gọi 1 HS phát biểu ý HS phát biểu ý 3’ kiến về sự khác nhau kiến. của hai hình. GV nhận xét ý kiến HS lắng nghe và 2’ của HS và bổ sung. thắc mắc ( nếu có). 2.Cách biểu diễn a.Dùng mảng GV vẽ hình cấu trúc HS quan sát và suy 3’ Stack sử dụng mảng nghĩ. để HS quan sát. Gọi 1 HS miêu tả HS phát biểu ý 3’ quá trình hoạt động kiến. của cấu trúc. GV nhận xét-bổ HS lắng nghe và 4’ sung ý kiến và dẫn thắc mắc( nếu có). nhập vào phần mới. GV cho ví dụ minh HS quan sát và suy 2’ họa. nghĩ. GV giải thích ví dụ HS lắng nghe và 6’ trên và cho HS viết viết ví dụ vào tập. ví dụ vào tập.
b.Dùng danh sách GV vẽ hình cấu trúc HS quan sát và suy 4’ Stack sử dụng danh nghĩ. sách liên kết để HS quan sát. Gọi 1 HS miêu tả HS phát biểu ý 5’ quá trình hoạt động kiến. của cấu trúc. GV nhận xét-bổ HS lắng nghe và 8’ sung ý kiến và dẫn thắc mắc( nếu có). nhập vào phần mới. GV cho ví dụ minh HS quan sát và suy 3’ họa. nghĩ. GV giải thích ví dụ HS lắng nghe và 7’ trên và cho HS viết viết ví dụ vào tập. ví dụ vào tập. II. Hàng đợi(Queue) GV liên hệ thực tế HS lắng nghe và 5’ đưa ra một số ví dụ suy nghĩ tư duy. để dẫn nhập vào phần mới. GV gọi một vài HS HS đưa ra một số 4’ cho thêm ví dụ khác ví dụ. ngoài các ví dụ trên. GV nhận xét và HS lắng nghe và 3’ đánh giá. thắc mắc( nếu có). 1.Định nghĩa GV cho HS xem tài 1 HS đọc, các HS 5’ liệu, gọi 1 bạn đọc còn lại lắng nghe định nghĩa. và xem tài liệu. GV dán hình vẽ về HS quan sát và suy 4’ cấu trúc Stack và nghĩ. Queue cho HS quan sát và so sánh. Gọi 1 HS phát biểu ý HS phát biểu ý 4’ kiến về sự khác nhau kiến. của hai hình.
GV nhận xét ý kiến HS lắng nghe và 3’ của HS và bổ sung. thắc mắc ( nếu có). 2.Cách biểu diễn a.Dùng mảng GV vẽ hình cấu trúc HS quan sát và suy 5’ Queue sử dụng nghĩ. mảng để HS quan sát. Gọi 1 HS miêu tả HS phát biểu ý 3’ quá trình hoạt động kiến. của cấu trúc. GV nhận xét-bổ HS lắng nghe và 3’ sung ý kiến và dẫn thắc mắc( nếu có). nhập vào phần mới. GV cho ví dụ minh HS quan sát và suy 3’ họa. nghĩ. GV giải thích ví dụ HS lắng nghe và 3’ trên và cho HS viết viết ví dụ vào tập. ví dụ vào tập. b.Dùng danh sách GV vẽ hình cấu trúc HS quan sát và suy 4’ Queue sử dụng danh nghĩ. sách liên kết để HS quan sát. Gọi 1 HS miêu tả HS phát biểu ý 4’ quá trình hoạt động kiến. của cấu trúc. GV nhận xét-bổ HS lắng nghe và 4’ sung ý kiến và dẫn thắc mắc( nếu có). nhập vào phần mới. GV cho ví dụ minh HS quan sát và suy 3’ họa. nghĩ. GV giải thích ví dụ HS lắng nghe và 4’ trên và cho HS viết viết ví dụ vào tập. ví dụ vào tập. Chương V TÌM KIẾM
Bài 1: Tìm kiếm tuyến tính I.Khái niệm tìm kiếm: GV giới thiệu sơ HS lắng nghe và 4’ lược về bài mới và quan sát. cho ví dụ minh họa. Gọi 1 HS nhận xét HS nhận xét ví dụ. 2’ về ví dụ. GV nhận xét và cho HS lắng nghe và 2’ HS xem tài liệu. xem tài liệu. GV đọc khái niệm, HS lắng nghe và 4’ cho HS viết khái viết khái niệm vào niệm vào tập. tập. GV cho 1 ví dụ nhỏ HS quan sát và 4’ và gọi 1 HS đứng phát biểu ý kiến. lên phát biểu ý kiến. GV nhận xét ý kiến HS lắng nghe và 2’ của HS và bổ sung. thắc mắc(nếu có). II.Mô tả bài toán tìm kiếm GV đặt câu hỏi và HS quan sát, suy 3’ trong tin học gọi một vài HS phát nghĩ và phát biểu ý biểu ý kiến . kiến. GV nhận xét -đánh HS lắng nghe và 2’ giá và giải đáp thắc thắc mắc(nếu có). mắc. GV gọi HS cho ví dụ HS cho ví dụ, lắng 1’ về bài toán tìm kiếm nghe. trong tin học mà HS biết. GV nhận xét và HS lắng nghe, thắc 2’ đánh giá. mắc( nếu có). 3 Củng cố kiến thức và kết thúc bài -Nhấn mạnh trọng tâm bài Giáo viên đặt ra câu HS lắng nghe, trả 5’ học ở phần I-Ngăn xếp(Cách hỏi để học sinh nắm lời câu hỏi. biểu diễn), phần II-Hàng vững tri thức, mở
đợi(Cách biểu diễn) và phần rộng và vận dụng tri I-Khái niệm tìm kiếm thức đã lĩnh hội. -Nhận xét tình hình học của GV nhận xét tinh HS lắng nghe. 2’ lớp thần, thái độ học tập của lớp. -Nêu kế hoạch của tiết tới GV giới thiệu sơ HS ghi chép những 4’ -Hướng dẫn học sinh xem lược về nội dung tiết nội dung liên quan bài trước ở nhà sau. đến tiết tiếp sau. 4 Hướng dẫn tự học Bài tập về nhà: 8’ 1.Nêu vài ví dụ thực tế mà ở đó có cơ chế hoạt động “ vào sau ra trước”. 2.Theo bạn đối với stack và queue thì có những cách cài đặt nào? So sánh đặc điểm của các cách đó. Nguồn tài liệu tham khảo Tên sách:Cấu trúc dữ liệu Tên tác giả: Nguyễn Trung Trực Tên NXB: Trường ĐH Bách Khoa Hồ Chí Minh Năm XB: 1993 TRƯỞNG KHOA TRƯỞNG TỔ MÔN Ngày tháng năm GIÁO VIÊN Nguyễn Ngọc Duyên
Giáo án số: 4(Giáo án chi tiết) Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Bài 2: Ngăn xếp và Hàng đợi ( Stack và Queue ) 1.Dẫn nhâp: *Đặt ra câu hỏi để kiểm tra kiến thức cũ. Câu hỏi: 1.Điểm cần lưu ý giữa danh sách liên kết đơn và danh sách liên kết kép là gì? 2.Ngăn xếp và Hàng đợi là gì? Nêu ví dụ minh họa? Trả lời: 1.Danh sách liên kết kép về mặt cơ bản có tính chất như danh sách liên kết đơn. Tuy nhiên nó có một số tính chất khác danh sách liên kết đơn như sau: Danh sách liên kết kép có mối liên kết hai chiều nên từ một phần tử bất kì có thể truy xuất một phần tử bất kì khác. Trong khi trên danh sách liên kết đơn ta chỉ có thể truy xuất đến các phần tử đứng sau một phần tử cho trước. Điều này dẫn đến việc ta có thể dễ dàng hủy phần tử cuối danh sách liên kết kép, con trên danh sách liên kết đơn thao tác này tổn chi phí O(n). Bù lại, danh sách liên kết kép tốn chi phí gấp đôi so với danh sách liên kết đơn cho việc lưu trữ các mối liên kết. Điều này khiến việc cập nhật cũng nặng nề hơn trong một số trường hợp. Như vậy, cần cân nhắc lựa chọn CTDL hợp lý khi cài đặt cho một ứng dụng cụ thể. 2.Ngăn xếp ( Stack) là một danh sách mà ta giới hạn việc thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu của danh sách, đầu này gọi là đỉnh (TOP) của ngăn xếp. Ví dụ: một chồng đĩa, thêm vào ta để đĩa mới lên trên đỉnh, lấy đĩa ra ta cũng phải lấy từ trên ra. Hàng đợi (Queue) là một danh sách đặc biệt mà phép thêm và bớt được thực hiện ở hai đầu khác nhau. Thêm ở cuối danh sách (REAR), còn bớt thì ở phía đầu danh sách (FRONT). Ví dụ: Sắp hàng mua vé xe, ai vào trước mua trước ra trước ,ai vào sau mua sau ra sau. 2.Giảng bài mới: I.Ngăn xếp (Stack):
Câu hỏi: qua phần kiểm tra bài cũ, và hình 1 trên bảng bạn nào có thể cho tôi một định nghĩa hoàn chỉnh về ngăn xếp (stack) ? Cách biểu diễn? Trả lời:  Định nghĩa:Ngăn xếp ( Stack) là một danh sách mà ta giới hạn việc thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu của danh sách, đầu này gọi là đỉnh (TOP) của ngăn xếp. Như vậy, ngăn xếp là một cấu trúc có tính chất “ vào sau – ra trước” hay LIFO ( last in – first out).  Cách biểu diễn: Stack có thể được biểu diễn như một danh sách đặc hoặc một danh sách liên kết. Vì phép thêm vào hoặc loại bỏ chỉ thực hiện ở một đầu nên chỉ cần một biến sp gọi là chỉ điểm đầu của stack. a) Cách biểu diễn kiểu mảng: Quá trình hoạt động: *Vào:phần tử a vào trước đứng ở vị trí số 1, phần tử 2 tiếp tục vào đứng ở vị trí số 2, cứ thế đến phần tử d đứng ở vị trí thứ 4. *Ra: phần tử d vào sau nhưng là phần tử phía trên (top_pointer) ra trước, tiếp đến phần tử c, phần tử b và phần tử cuối cùng phần tử a. Ví dụ: b)cách biểu diễn kiểu danh sách:
Tương tự cách biểu diễn kiểu mảng ví dụ: II. Hàng đợi (Queue) : Câu hỏi: Qua hình 2 trên bảng bạn nào có thể cho tôi một định nghĩa hoàn chỉnh về hàng đợi (queue) ? Cách biểu diễn? Ví dụ thực tiễn? Trả lời:  Định nghĩa:Hàng đợi (Queue) là một danh sách đặc biệt mà phép thêm và bớt được thực hiện ở hai đầu khác nhau. Thêm ở cuối danh sách (REAR), c̣n bớt th́ ở phía đầu danh sách (FRONT).Vì vậy, hàng đợi còn được gọi là cấu trúc FIFO ( first in – first out) hay “vào trước ra sau”.  Cách biểu diễn: có thể được biểu diễn như một danh sách đặc hoặc một danh sách liên kết. Trong đó có 2 biến: biến đầu Front chỉ ra vị trí thực hiện phép loại bỏ (Dequeue) và biến cuối Rear chỉ ra vị trí thực hiện phép thêm vào (Enqueue). Ví dụ: Xếp hàng mua vé, ai vào trước mua trước ra trước, vào sau mua sau ra sau.
a) Cách biểu diễn bằng mảng: *Cách hoạt động: khách đến trước mua vé trước, khách đến sau mua sau.
Ví dụ: b)Cách biểu diễn bằng danh sách: Ví dụ:
Chương V TÌM KIẾM Bài 1: Tìm kiếm tuyến tính I.Khái niệm tìm kiếm: Tìm kiếm là thao tác cơ bản, thường xuyên và quan trọng trong tin học. Ví dụ như tìm kiếm nhân viên trong danh sách nhân viên, tìm kiếm một sinh viên trong danh sách lớp học Các hệ thống thông tin thường lưu trữ khối lượng dữ liệu lớn, nên thuật toán tìm kiếm tốt sẽ có nhiều lợi ích. Tuy nhiên, thao tác tìm kiếm còn phụ thuộc rất nhiều đến dữ liệu được tổ chức như thế nào; nếu dữ liệu được tổ chức tốt thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn. Giả sử sách được sắp theo chủ đề, thể loại thì dễ tìm kiếm hơn là không được sắp. Hoặc danh sách tên người được sắp theo thứ tự alphabet cũng dễ cho việc tìm kiếm Ví dụ: Đối tượng sinh viên có các kiểu dữ liệu {MaSV, Hoten, Diachi, }. Khi đó tìm kiếm trên danh sách sinh viên thì khóa thường chọn là MaSV hoặc Hoten. II.Mô tả bài toán tìm kiếm trong tin học Câu hỏi: mô hình tìm kiếm trong tin học như thế nào? Trả lời:Tìm kiếm là quá trình xác định một đối tượng nào đó trong một tập các đối tượng. Kết quả trả về là đối tượng tìm được hoặc một chỉ số (nếu có) xác định vị trí của đối tượng trong tập đó. Việc tìm kiếm dựa vào một trường nào đó của đối tượng, trường này là khóa (key) của việc tìm kiếm. Ví dụ: Đối tượng sinh viên có các kiểu dữ liệu {MaSV, Hoten, Diachi, }. Khi đó tìm kiếm trên danh sách sinh viên thì khóa thường chọn là MaSV hoặc Hoten. Thông thường người ta phân làm hai loại tìm kiếm : tìm kiếm tuyến tính hay con gọi là tuần tự cho tập dữ liệu bất kỳ; tìm kiếm nhị phân cho tập dữ liệu đã được sắp xếp. Bài toán tìm kiếm được mô tả như sau:
Tập dữ liệu được lưu trữ là dãy A1, A2, , An. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính, có khai báo: a[n] : integer; Khóa cần tìm là x có kiểu số nguyên : x: integer . Bài tập về nhà: 1.Nêu vài ví dụ thực tế mà ở đó có cơ chế hoạt động “ vào sau ra trước”. 2.Theo bạn đối với stack và queue thì có những cách cài đặt nào? So sánh đặc điểm của các cách đó.
GIÁO ÁN SỐ: 5 Thời gian thực hiện: 4h Tên chương: Chương V : TÌM KIẾM Thực hiện ngày tháng năm TÊN BÀI: Bài 1: Tìm kiếm tuyến tính Bài 2: Tìm kiếm nhị phân MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: -Khảo sát giải thuật tìm kiếm tuyến tính, nhị phân cài đặt và đánh giá được độ phức tạp của giải thuật. -Thực hành (lập trình và biên dịch) được với các bài toán sử dụng giải thuật tìm kiếm tuyến tính, nhị phân ĐỒ DÙNG VÀ PHƯƠNG TIỆN DẠY HỌC Giáo án, bài giảng chi tiết, giáo trình cấu trúc dữ liệu và giải thuật, bảng, phấn, bảng biểu I. ỔN ĐỊNH LỚP HỌC: Thời gian: 1’ + Điểm danh + Nhắc nhở II. THỰC HIỆN BÀI HỌC TT NỘI DUNG HOẠT ĐỘNG DẠY HỌC THỜI HOẠT ĐỘNG CỦA HOẠT ĐỘNG GIAN GIÁO VIÊN CỦA HỌC SINH 1 Dẫn nhập -GV gọi tên HS trả 5‘ Trả bài cũ và dẫn nhập vào bài. bài mới. -GV nêu câu hỏi. -HS lắng nghe câu hỏi của GV. -GV lắng nghe câu -HS trả lời câu hỏi. trả lời của HS. -HS lắng nghe -GV nhận xét câu trả nhận xét của GV. lời và đánh giá điểm. -GV dẫn nhập vào -HS lắng nghe và phần bài mới tiếp định hình những theo dựa trên bài cũ. nội dung sắp học.
2 Giảng bài mới Bài 1: Tìm kiếm tuyến tính (tiếp theo) I.Giải thuật GV đặt vấn đề. HS lắng nghe và 3’ suy nghĩ. GV cho 1 ví dụ minh HS quan sát. 3’ họa. GV đặt câu hỏi để HS lắng nghe và trả 4’ HS hiểu ví dụ và lời câu hỏi. hiểu tìm kiếm tuyến tính là gì. GV nhận xét và HS lắng nghe và 2’ đánh giá. thắc mắc( nếu có). GV viết giải thuật HS quan sát, suy 5’ lên bảng và gọi HS nghĩ và đứng lên đứng lên giải thích giải thích. giải thuật. GV nhận xét và HS lắng nghe và 2’ đánh giá. thắc mắc(nếu có). GV gọi HS liên hệ HS cho ví dụ. 2’ thực tế cho 1 số ví dụ. GV nhận xét và HS lắng nghe và 2’ đánh giá. thắc mắc(nếu có). II.Cài đặt GV đặt câu hỏi về HS lắng nghe- trả 4’ cách cài đặt của giải lời câu hỏi. thuật tìm kiếm tuyến tính và gọi HS trả lời. GV cho thời gian HS HS suy nghĩ và lên 5’ suy và gọi HS lên bảng viết giải thuật, bảng viết chương các HS còn lại viết trình cài đặt giải vào tập. thuật tìm kiếm tuyến
tính. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). GV đặt câu hỏi ưu HS suy nghĩ và trả 5’ nhược điểm về cách lời câu hỏi. cài đặt giải thuật vừa viết. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). GV gọi HS nêu thêm HS suy nghĩ và nêu 5’ cách khác về cài đặt thêm ví dụ. giải thuật tìm kiếm tuyến tính. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). III.Đánh giá giải thuật GV gọi HS đánh giá HS suy nghĩ và nêu 2’ giải thuật. lên đánh giá về giải thuật. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). GV cho thời gian để HS viết bài vào tập. 4’ HS viết bài vào tập. GV đặt câu hỏi để HS suy nghĩ và trả 6’ củng cố kiến thức về lời câu hỏi. giải thuật tìm kiếm và gọi HS trả lời. GV nhận xét, đánh HS lắng nghe và 4’ giá và bổ sung. thắc mắc(nếu có).
Bài 2: Tìm kiếm nhị phân GV đặt câu hỏi. HS lắng nghe và trả 3’ I.Giải thuật lời. GV cho 1 ví dụ minh HS quan sát. 3’ họa. GV đặt câu hỏi để HS lắng nghe và trả 4’ HS hiểu ví dụ và lời câu hỏi. hiểu tìm kiếm nhị phân là gì. GV nhận xét và HS lắng nghe và 3’ đánh giá. thắc mắc( nếu có). GV viết giải thuật HS quan sát, suy 6’ lên bảng và gọi HS nghĩ và đứng lên đứng lên giải thích giải thích. giải thuật. GV nhận xét và HS lắng nghe và 3’ đánh giá. thắc mắc(nếu có). GV gọi cho 1 số ví HS cho ví dụ. 4’ dụ. GV nhận xét và HS lắng nghe và 3’ đánh giá. thắc mắc(nếu có). II.Cài đặt GV đặt câu hỏi về HS lắng nghe- trả 9’ cách cài đặt của giải lời câu hỏi. thuật tìm kiếm nhị phân và gọi HS trả lời. GV cho thời gian HS HS suy nghĩ và lên 5’ suy và gọi HS lên bảng viết giải thuật, bảng viết chương các HS còn lại viết trình cài đặt giải vào tập. thuật tìm kiếm nhị phân.
GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). GV đặt câu hỏi về HS suy nghĩ và trả 5’ ưu nhược điểm về lời câu hỏi. cách cài đặt giải thuật vừa viết. GV nhận xét, đánh HS lắng nghe và 4’ giá và bổ sung. thắc mắc(nếu có). GV gọi HS nêu thêm HS suy nghĩ và nêu 2’ cách khác về cài đặt thêm ví dụ. giải thuật tìm kiếm nhị phân. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). III.Đánh giá giải thuật GV gọi HS đánh giá HS suy nghĩ và nêu 3’ giải thuật. lên đánh giá về giải thuật. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). GV cho thời gian để HS viết bài vào tập. 4’ HS viết bài vào tập. GV đặt câu hỏi để HS suy nghĩ và trả 5’ củng cố kiến thức về lời câu hỏi. giải thuật tìm kiếm và gọi HS trả lời. GV nhận xét, đánh HS lắng nghe và 3’ giá và bổ sung. thắc mắc(nếu có). GV gọi HS cho 1 số HS suy nghĩ cho ví 6’ ví dụ về cây tìm dụ. kiếm nhị phân.
3 Củng cố kiến thức và kết thúc bài -Nhấn mạnh trọng tâm bài Giáo viên đặt ra câu HS lắng nghe, trả 6’ học phần giải thuật, cài đặt, hỏi để học sinh nắm lời câu hỏi. đánh giá giải thuật của tìm vững tri thức, mở kiếm tuyến tính và tiềm kiếm rộng và vận dụng tri nhị phân thức đã lĩnh hội. -Nhận xét tình hình học của GV nhận xét tinh HS lắng nghe. 3’ lớp thần, thái độ học tập của lớp. -Nêu kế hoạch của tiết tới GV giới thiệu sơ HS ghi chép những 5’ -Hướng dẫn học sinh xem lược về nội dung tiết nội dung liên quan bài trước ở nhà sau. đến tiết tiếp sau. 4 Hướng dẫn tự học Bài tập về nhà: 6’ 1.Trình bày tư tưởng của các thuật toán tìm kiếm: Tuyến tính, Nhị Phân? Các thuật toán này có thể được vận dụng trong trường hợp nào? Cho ví dụ minh họa? 2.Cài đặt lại thuật toán tìm tuyến tính bằng các cách: *Sử dụng vòng lặp For *Sử dụng vòng lặp DO WHILE Có nhận xét gì ở mỗi trường hợp? Nguồn tài liệu tham khảo Tên sách:Cấu trúc dữ liệu Tên tác giả: Nguyễn Trung Trực Tên NXB: Trường ĐH Bách Khoa Hồ Chí Minh Năm XB: 1993 TRƯỞNG KHOA TRƯỞNG TỔ MÔN Ngày tháng năm GIÁO VIÊN Nguyễn Ngọc Duyên
Giáo án số: 5(Giáo án chi tiết) Chương V TÌM KIẾM Bài 1: Tìm kiếm tuyến tính 1.Dẫn nhâp: *Đặt ra câu hỏi để kiểm tra kiến thức cũ. Câu hỏi: 1.Giải thuật tìm kiếm tuyến tính là gì? 2.Gải thuật tìm kiếm nhị phân là gì? Trả lời: 1.Thuật toán tìm tuyến tính còn được gọi là Thuật toán tìm kiếm tuần tự (Sequential Search). Tư tưởng: lần lượt so sánh các phần tử của mảng M với giá trị X bắt đầu từ phần tử đâu tiên cho đến khi tìm đến được phần tử có giá trị X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết thúc. 2.Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường hợp số phần tử của dãy không lớn lắm. Tuy nhiên, khi số phần tử của dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khác hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật toán tìm tuần tự thì quả thật tốn rất nhiều thời gian. Trong thực tế, thông thường các phần tử của dãy đã có một thứ tự, do vậy thuật toán tìm kiếm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm kiếm trên dãy đã có thứ tự.Trong thuật toán này chúng ta giả sử các phần tử trong dãy đã có thứ tự tăng ( không giảm dần), tức là các phần tử đừng trước luôn có giá trị nhỏ hơn hoặc bằng (không lớn hơn) phần tử đứng sau nó. Khi đó nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy (M[Mid]) thì X chỉ có thể tìm thấy ở nữa đầu của dãy và ngược lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể tìm thấy ở nửa sau của dãy. 2.Giảng bài mới: I.Giải thuật: Đặt vấn đề: Giả sử chúng ta có một mảng M gồm N phần tử. Vấn đề đặt ra là có hay không phần tử có giá trị bằng X trong mảng M? Nếu có thì phần tử có giá trị bằng X là phần tử thứ mấy trong mảng M? Ví dụ 1: tìm X trong mảng M *Phần tử có nội dung là X *So sánh từng phần tử trong mảng M: M[1] X; M[2] = X;
*Kết luận có phần tử X trong mảng M . Câu hỏi: Tìm kiếm tuyến tính là gì? Trả lời: Thuật toán tìm tuyến tính còn được gọi là Thuật toán tìm kiếm tuần tự (Sequential Search). Tư tưởng: lần lượt so sánh các phần tử của mảng M với giá trị X bắt đầu từ phần tử đâu tiên cho đến khi tìm đến được phần tử có giá trị X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết thúc. Ví dụ thực tế: tìm một sinh viên tên Hoa trong lớp TH2009 có mã số thứ tự bao nhiêu? →so sánh từng sinh viên từ đầu danh sánh, nếu không phải tên Hoa lớp TH2009 thì bỏ qua cho đến khi tìm gặp tên sinh viên này và trả về số thứ tự của sinh viên, ngược lại không tìm thấy sinh viên Hoa khi đã duyệt hết danh sách lớp, kết luận không tồn tại sinh viên này. Câu hỏi: tìm kiếm tuyến tính cài đặt như thế nào? Trả lời: (dựa vào ví dụ 1) Function timX ( M: mang ;N, X : integer) : boolean ; Var vt: integer ; Begin vt := 0 ; While ( M [ vt ] X and vt < N ) do vt := vt + 1 ; if ( vt < N) then write (“ X có vị trí là :” , vt ) else write (“X không tồn tại trong mảng” ); end; câu hỏi: có hình vẽ như sau hãy tìm X có nội dùng là 6. trả lời:
III.Đánh giá giải thuật: Câu hỏi: Nhận xét về ví dụ trên Trả lời: số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n Bài 2 : Tìm kiếm nhị phân I.Giải thuật: Câu hỏi: Tìm kiếm nhị phân là gì? Ý tưởng như thế nào? Trả lời: Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường hợp số phần tử của dãy không lớn lắm. Tuy nhiên, khi số phần tử của dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khác hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật toán tìm tuần tự thì quả thật tốn rất nhiều thời gian. Trong thực tế, thông thường các phần tử của dãy đã có một thứ tự, do vậy thuật toán tìm kiếm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm kiếm trên dãy đã có thứ tự.Trong thuật toán này chúng ta giả sử các phần tử trong dãy đã có thứ tự tăng ( không giảm dần), tức là các phần tử đừng trước luôn có giá trị nhỏ hơn hoặc bằng (không lớn hơn) phần tử đứng sau nó. Khi đó nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy (M[Mid]) thì X chỉ có thể tìm thấy ở nữa đầu của dãy và ngược lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể tìm thấy ở nửa sau của dãy. Ý tưởng thuật giải: So sánh khóa cần tìm với phần tử giữa dãy hiện hành. Nếu nó nhỏ hơn thì tìm bên trái dãy hiện hành. Ngược lại tìm bên phải dãy hiện hành. Lặp lại động tác này. Dãy hiện hành là dãy ta đang tìm, chỉ số đầu tiên của phần tử đầu tiên trong dãy là left, và chỉ số của phần tử cuối cùng trong dãy hiện hành là right. Ví dụ : Cho dãy số A gồm N số nguyên tãng dần khác nhau A1, A2, , An và số nguyên K, nếu có Ai = K ( 1 <= K <= N ) thì thông báo chỉ số i. *Xác định bài toán: Input: dãy A là dãy tăng gồm N số nguyên đôi một khác nhau A1, A2, , An và một số nguyên K; Output : Chỉ số i mà Ai = K hoặc thông báo không có số hạng nào của dãy A có giá trị bằng K.
Ý tưởng: Sử dụng tính chất dãy A là dãy tãng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng ðýợc chọn. Ðể làm ðiều ðó, ta chọn số hạng aGiua ở "giữa dãy" ðể so sánh với k; Khi ðó, chỉ xảy ra một trong ba trýờng hợp sau:  Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.  Nếu aGiua > k thì do dãy A là dãy ðã ðýợc sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2, , aGiua–1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trýớc ðó).  Nếu aGiua k thì ðặt Cuoi = Giua – 1 rồi chuyển ðến býớc 7; B6: Dau ← Giua + 1; B7: Nếu Dau > Cuoi thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc; B8: Quay lại B3. Câu hỏi: Ở býớc 7 có thể thay Dau>Cuoi bằng Dau=Cuoi ðýợc không? Giải thích? Trả lời: Không thể được. Hãy quan sát hình vẽ
Nếu [ðầu] = [cuối] thì vẫn còn một số hạng nữa phải so sánh với khoá k *Sơ đồ khối: III. Đánh giá giải thuật: Tìm kiếm nhị phân (hay chia ðể trị) giúp giảm bớt thao tác so sánh so với giải thuạt tìm kiếm tuyến tính. Bài tập về nhà: 1.Trình bày tư tưởng của các thuật toán tìm kiếm: Tuyến tính, Nhị Phân? Các thuật toán này có thể được vận dụng trong trường hợp nào? Cho ví dụ minh họa? 2.Cài đặt lại thuật toán tìm tuyến tính bằng các cách: *Sử dụng vòng lặp For *Sử dụng vòng lặp DO WHILE Có nhận xét gì ở mỗi trường hợp?
ĐƠN VỊ QUẢN LÝ TRỰC TIẾP CƠ SỞ DẠY NGHỀ SỔ GIÁO ÁN THỰC HÀNH Môn học : CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Lớp : Tin học 2009 Họ và tên giáo viên : Nguyễn Ngọc Duyên Năm học: 2012
GIÁO ÁN SỐ: 1 Thời gian thực hiện: 4h Bài học trước: Đệ quy và giải thuật đệ quy Thực hiện từ ngày đến ngày Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Tên bài: Viết chương trình cho danh sách liên kết MỤC TIÊU CỦA BÀI: -Trình bày được các thành phần của danh sách liên kết -Viết được các chương trình về các thao tác trên danh sách liên kết: thêm phần tử, xóa phần tử, duyệt danh sách liên kết. -Áp dụng cấu trúc dữ liệu danh sách liên kết vào việc giải quyết một số bài toán đơn giản. ĐỒ DÙNG VÀ TRANG THIẾT BỊ DẠY HỌC Máy tính, bảng, viết. HÌNH THỨC TỔ CHỨC DẠY HỌC -Phần lý thuyết :tập trung cả 1 ca -Biểu diễn thao tác mẫu: chia nhóm -Hướng dẫn kết thúc: tập trung cả ca -Hướng dẫn thường xuyên: chia nhóm . I. ỔN ĐỊNH LỚP HỌC: Thời gian:5’ Điểm danh , kiểm tra bài cũ II. THỰC HIỆN BÀI HỌC HOẠT ĐỘNG DẠY HỌC THỜI TT NỘI DUNG HOẠT ĐỘNG CỦA HOẠT ĐỘNG CỦA GIAN GIÁO VIÊN HỌC SINH 1 Dẫn nhập Chúng ta đã học Danh GV nhắc lại bài cũ HS lắng nghe và lĩnh 3‘ sách liên kết vậy Danh hội. sách liên kết có cần nhiều dung lượng bộ nhớ không GV đặt câu hỏi HS trả lời câu hỏi 5‘ và giới hạn số lượng phần tử là bao nhiêu? có bao nhiêu loại danh sách liên kết, vậy các loại danh sách liên kết đó có tên gì? Cách tổ chức và các thao tác cơ bản của nó là gì? Để trả lời các câu hỏi này ta bước vào phần kế tiếp.
2 Hướng dẫn ban đầu 90’ I.Định nghĩa danh sách GV giới thiệu sơ HS lắng nghe, trả lời liên kết lược bài mới, đặt câu câu hỏi. hỏi-gọi HS trả lời. GV nhận xét và bổ HS lắng nghe và lĩnh sung hoàn chỉnh câu hội. trả lời. 1.Khái niệm GV đọc khái niệm và HS lắng nghe, lĩnh đưa ra ví dụ minh hội, ghi bài vào tập. họa. 2.Khai báo GV viết khai báo lên HS lĩnh hội, ghi bài bảng và cho ví dụ vào tập. minh họa. 3.Khởi tạo GV viết khởi tạo lên HS lắng nghe, lĩnh bảng và cho ví dụ hội, ghi bài vào tập. minh họa. II.Các hình thức tổ chức GV đọc cho HS ghi HS lắng nghe, ghi danh sách liên kết các hình thức tổ chức bài vào tập. của danh sách liên kết. GV đặt vấn đề và trả HS lắng nghe. lời để HS hiểu bài hơn. III.Danh sách liên kết GV dẫn nhập và cho HS lắng nghe và xem đơn: HS xem tài liệu. tài liệu. 1.Cách tổ chức GV gọi 1 HS phát HS phát biểu ý kiến biểu ý kiến về cách xây dựng bài. tổ chức sau khi xem tài liệu. GV viết nội dung lên HS viết nội dung vào bảng. tập. 2.Các thao tác cơ GV dẫn nhập và cho bản HS xem tài liệu. HS lắng nghe và xem tài liệu. 2.1 Chèn 1 phần tử GV vẽ 1 danh sách HS quan sát. vào danh sách liên liên kết đơn lên bảng kết đơn và cho ví dụ minh a)Chèn vào đầu họa. danh sách GV viết giải thuật HS quan sát và viết lên bảng. vào tập.
b)Chèn vào cuối GV cho HS xem tài HS xem tài liệu. danh sách liệu GV gọi 1 HS cho ví HS làm ví dụ và dụ và làm ví dụ vừa quan sát. cho. GV nhận xét. HS lắng nghe và xem tài liệu viết giải thuật vào tập. 2.2 Tìm 1 phần tử GV đặt câu hỏi. HS lắng nghe. trong danh sách liên kết đơn GV cho HS xem tài HS xem tài liệu và liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Trả về kết quả Gọi HS lên bảng viết HS lên bảng viết. có hay không giải thuật. HS quan sát. b)Trả về danh Gọi HS lên bảng viết HS lên bảng viết. sách có bắt đầu là giải thuật. HS quan sát. phần tử cần tìm 2.3 Xóa 1 phần tử GV đặt câu hỏi. HS lắng nghe. trong danh sách liên kết đơn GV cho HS xem tài HS xem tài liệu và liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Xóa phần tử Gọi HS lên bảng viết HS lên bảng viết. đầu tiên giải thuật. HS quan sát. b)Xóa phần tử Gọi HS lên bảng viết HS lên bảng viết. cuối cùng giải thuật. HS quan sát. 2.4 Xuất danh sách GV đặt câu hỏi. HS lắng nghe. liên kết đơn GV cho HS xem tài HS xem tài liệu và liệu và tổ chức thảo tiến hành thảo luận luận nhóm. nhóm. a)Xuất xuôi có đệ Gọi HS lên bảng viết HS lên bảng viết. qui giải thuật. HS quan sát. b)Xuất xuôi Gọi HS lên bảng viết HS lên bảng viết. không có đệ qui giải thuật. HS quan sát
3 Hướng dẫn thường 120’ xuyên 1.Viết chương trình thêm -quan sát,nhắc nhở -thực hành một phần tử 2.Viết chương trình xóa -quan sát,nhắc nhở -thực hành một phần tử 3.Viết chương trình tìm 1 phần tử -quan sát,nhắc nhở -thực hành 4.Viết chương trình duyệt -quan sát,nhắc nhở -thực hành danh sách 4 Huớng dẫn kết thúc 14’ -Nhận xét kết quả rèn -Thuyết trình ,nhắc - Lắng nghe , ghi luyện của học sinh. nhở học sinh. chép rút kinh -lưu ý các sai sót và nghiệm cách khắc phục. 5 Hướng dẫn tự rèn luyện Bài tập về nhà: 10’ Xây dựng các CTC sau trên danh sách liên kết , nội dung các phần tử kiểu số nguyên: 1.thêm một phần tử vào trước Y xuất hiện ở lần thứ K. 2. Xóa tất cả các phần tử X có trong danh sách. 3.Tách một danh sách thành hai danh sách tương ứng với các vị trí chẳn lẻ. IV. RÚT KINH NGHIỆM TỔ CHỨC THỰC HIỆN: Ngày tháng năm TRƯỞNG KHOA/ TRƯỞNG TỔ MÔN GIÁO VIÊN Nguyễn Ngọc Duyên
GIÁO ÁN SỐ: 2 Thời gian thực hiện: 4h Bài học trước: Viết chương trình cho danh sách liên kết Thực hiện từ ngày đến ngày Chương III CẤU TRÚC DỮ LIỆU ĐỘNG Tên bài: Viết chương trình cho ngăn xếp (stack) và hàng đợi (queue) Viết chương trình cài đặt tìm kiếm tuyến tính MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: -Trình bày được cấu trúc Stack và cấu trúc Queue -Nhận biết được cấu trúc Stack và cấu trúc Queue -Viết được các chương trình của stack và queue -Viết được chương trình cài đặt tìm kiếm tuyến tính ĐỒ DÙNG VÀ TRANG THIẾT BỊ DẠY HỌC Máy tính, bảng, viết. HÌNH THỨC TỔ CHỨC DẠY HỌC -Phần lý thuyết :tập trung cả 1 ca -Biểu diễn thao tác mẫu: chia nhóm -Hướng dẫn kết thúc: tập trung cả ca -Hướng dẫn thường xuyên: chia nhóm . I. ỔN ĐỊNH LỚP HỌC: Thời gian:5’ Điểm danh , kiểm tra bài cũ II. THỰC HIỆN BÀI HỌC HOẠT ĐỘNG DẠY HỌC THỜI TT NỘI DUNG HOẠT ĐỘNG CỦA HOẠT ĐỘNG CỦA GIAN GIÁO VIÊN HỌC SINH 1 Dẫn nhập Ví dụ 1:Một chồng đĩa, GV nhắc lại bài cũ HS lắng nghe và lĩnh 3‘ thêm vào ta để đĩa mới hội. lên trên đỉnh, lấy đĩa ra ta cũng phải lấy từ trên ra. GV đặt câu hỏi HS trả lời câu hỏi 5‘ Ví dụ 2:Sắp hàng mua vé xe, ai vào trước mua trước ra trước ,ai vào sau mua sau ra sau. Hai ví dụ nêu trên ta liên tưởng đến cấu trúc gì?
2 Hướng dẫn ban đầu 90’ Bài 3: Ngăn xếp và hàng GV giới thiệu sơ HS lắng nghe và trả đợi (Stack và Queue) lược bài mới, đặt câu lời câu hỏi. I.Ngăn xếp (Stack) hỏi-gọi HS trả lời. GV nhận xét và bổ HS lắng nghe và sung hoàn chỉnh câu phản hồi( nếu có). trả lời. 1.Định nghĩa GV cho HS xem tài 1 HS đọc, các HS liệu, gọi 1 bạn đọc còn lại lắng nghe và định nghĩa. xem tài liệu. GV dán hình vẽ về HS quan sát và suy cấu trúc Stack và nghĩ. Queue cho HS quan sát và so sánh. Gọi 1 HS phát biểu ý HS phát biểu ý kiến. kiến về sự khác nhau của hai hình. HS lắng nghe và thắc GV nhận xét ý kiến mắc ( nếu có). của HS và bổ sung. HS quan sát và suy 2.Cách biểu diễn GV vẽ hình cấu trúc nghĩ. a.Dùng mảng Stack sử dụng mảng để HS quan sát. HS phát biểu ý kiến. Gọi 1 HS miêu tả quá trình hoạt động của cấu trúc. HS lắng nghe và thắc mắc( nếu có). GV nhận xét-bổ sung ý kiến và dẫn nhập HS quan sát và suy vào phần mới. nghĩ. GV cho ví dụ minh họa. HS lắng nghe và viết ví dụ vào tập. GV giải thích ví dụ trên và cho HS viết ví dụ vào tập. HS quan sát và suy
nghĩ. b.Dùng danh sách GV vẽ hình cấu trúc Stack sử dụng danh sách liên kết để HS quan sát. HS phát biểu ý kiến. Gọi 1 HS miêu tả quá trình hoạt động HS lắng nghe và thắc của cấu trúc. mắc( nếu có). GV nhận xét-bổ sung HS quan sát và suy ý kiến và dẫn nhập nghĩ. vào phần mới. GV cho ví dụ minh HS lắng nghe và viết họa. ví dụ vào tập. GV giải thích ví dụ trên và cho HS viết HS lắng nghe và suy ví dụ vào tập. nghĩ tư duy. II. Hàng đợi(Queue) GV liên hệ thực tế đưa ra một số ví dụ để dẫn nhập vào HS đưa ra một số ví phần mới. dụ. GV gọi một vài HS cho thêm ví dụ khác HS lắng nghe và thắc ngoài các ví dụ trên. mắc( nếu có). GV nhận xét và đánh 1 HS đọc, các HS giá. còn lại lắng nghe và xem tài liệu. 1.Định nghĩa GV cho HS xem tài liệu, gọi 1 bạn đọc HS quan sát và suy định nghĩa. nghĩ. GV dán hình vẽ về cấu trúc Stack và Queue cho HS quan HS phát biểu ý kiến. sát và so sánh. Gọi 1 HS phát biểu ý HS lắng nghe và thắc kiến về sự khác nhau mắc ( nếu có).
của hai hình. GV nhận xét ý kiến HS quan sát và suy của HS và bổ sung. nghĩ. 2.Cách biểu diễn a.Dùng mảng GV vẽ hình cấu trúc Queue sử dụng mảng HS phát biểu ý kiến. để HS quan sát. Gọi 1 HS miêu tả HS lắng nghe và thắc quá trình hoạt động mắc( nếu có). của cấu trúc. GV nhận xét-bổ sung HS quan sát và suy ý kiến và dẫn nhập nghĩ. vào phần mới. GV cho ví dụ minh HS lắng nghe và viết họa. ví dụ vào tập. GV giải thích ví dụ trên và cho HS viết ví dụ vào tập. b.Dùng danh sách GV vẽ hình cấu trúc HS quan sát và suy Queue sử dụng danh nghĩ. sách liên kết để HS quan sát. Gọi 1 HS miêu tả HS phát biểu ý kiến. quá trình hoạt động của cấu trúc. GV nhận xét-bổ sung HS lắng nghe và thắc ý kiến và dẫn nhập mắc( nếu có). vào phần mới. GV cho ví dụ minh HS quan sát và suy họa. nghĩ. GV giải thích ví dụ HS lắng nghe và viết trên và cho HS viết ví dụ vào tập. ví dụ vào tập.
Chương V HS lắng nghe và suy Bài 1: Tìm kiếm tuyến GV đặt vấn đề. nghĩ. tính (tiếp theo) I.Giải thuật HS quan sát. GV cho 1 ví dụ minh họa. HS lắng nghe và trả GV đặt câu hỏi để lời câu hỏi. HS hiểu ví dụ và hiểu tìm kiếm tuyến tính là gì. HS lắng nghe và thắc GV nhận xét và đánh mắc( nếu có). giá. HS quan sát, suy GV viết giải thuật nghĩ và đứng lên giải lên bảng và gọi HS thích. đứng lên giải thích giải thuật. HS lắng nghe và thắc GV nhận xét và đánh mắc(nếu có). giá. HS cho ví dụ. GV gọi HS liên hệ thực tế cho 1 số ví dụ. HS lắng nghe và thắc GV nhận xét và đánh mắc(nếu có). giá. HS lắng nghe- trả lời II.Cài đặt GV đặt câu hỏi về câu hỏi. cách cài đặt của giải thuật tìm kiếm tuyến tính và gọi HS trả lời. HS suy nghĩ và lên GV cho thời gian HS bảng viết giải thuật, suy và gọi HS lên các HS còn lại viết bảng viết chương vào tập. trình cài đặt giải thuật tìm kiếm tuyến tính. HS lắng nghe và thắc
GV nhận xét, đánh mắc(nếu có). giá và bổ sung. HS suy nghĩ và trả GV đặt câu hỏi ưu lời câu hỏi. nhược điểm về cách cài đặt giải thuật vừa viết. HS lắng nghe và thắc GV nhận xét, đánh mắc(nếu có). giá và bổ sung. HS suy nghĩ và nêu GV gọi HS nêu thêm thêm ví dụ. cách khác về cài đặt giải thuật tìm kiếm tuyến tính. HS lắng nghe và thắc GV nhận xét, đánh mắc(nếu có). giá và bổ sung. HS suy nghĩ và nêu III.Đánh giá giải thuật GV gọi HS đánh giá lên đánh giá về giải giải thuật. thuật. HS lắng nghe và thắc GV nhận xét, đánh mắc(nếu có). giá và bổ sung. HS viết bài vào tập. GV cho thời gian để HS viết bài vào tập. HS suy nghĩ và trả GV đặt câu hỏi để lời câu hỏi. củng cố kiến thức về giải thuật tìm kiếm và gọi HS trả lời. HS lắng nghe và thắc GV nhận xét, đánh mắc(nếu có). giá và bổ sung.
3 Hướng dẫn thường 120’ xuyên 1.Viết chương trình thêm -quan sát,nhắc nhở -thực hành một phần tử trong Queue 2.Viết chương trình xóa -quan sát,nhắc nhở -thực hành một phần tử trong Queue 3.Viết chương trình áp dụng stack loại bỏ đệ qui -quan sát,nhắc nhở -thực hành trong bài toán xuất ngược một danh sách liên kết 4.Viết chương trình xóa -quan sát,nhắc nhở -thực hành một phần tử trong stack 5.Viết chương trình cài -quan sát,nhắc nhở -thực hành đặt tìm kiếm tuyến tính 4 Huớng dẫn kết thúc 14’ -Nhận xét kết quả rèn -Thuyết trình ,nhắc - Lắng nghe , ghi luyện của học sinh. nhở học sinh. chép rút kinh -lưu ý các sai sót và nghiệm cách khắc phục. 5 Hướng dẫn tự rèn luyện Bài tập về nhà: 10’ Cài đặt lại thuật toán tìm tuyến tính bằng các cách: *Sử dụng vòng lặp For *Sử dụng vòng lặp DO WHILE Có nhận xét gì ở mỗi trường hợp? IV. RÚT KINH NGHIỆM TỔ CHỨC THỰC HIỆN: Ngày tháng năm TRƯỞNG KHOA/ TRƯỞNG TỔ MÔN GIÁO VIÊN Nguyễn Ngọc Duyên
GIÁO ÁN SỐ: 3 Thời gian thực hiện: 2h Bài học trước: Viết chương trình cho ngăn xếp (stack) và hàng đợi (queue) Viết chương trình cài đặt tìm kiếm tuyến tính Thực hiện từ ngày đến ngày Chương V TÌM KIẾM Tên bài: Viết chương trình cài đặt tìm kiếm nhị phân MỤC TIÊU CỦA BÀI: Sau khi học xong bài này người học có khả năng: -Viết được chương trình cài đặt tìm kiếm nhị phân -Viết được chương trình duyệt cây nhị phân ĐỒ DÙNG VÀ TRANG THIẾT BỊ DẠY HỌC Máy tính, bảng, viết. HÌNH THỨC TỔ CHỨC DẠY HỌC -Phần lý thuyết :tập trung cả 1 ca -Biểu diễn thao tác mẫu: chia nhóm -Hướng dẫn kết thúc: tập trung cả ca -Hướng dẫn thường xuyên: chia nhóm . I. ỔN ĐỊNH LỚP HỌC: Thời gian:5’ Điểm danh , kiểm tra bài cũ II. THỰC HIỆN BÀI HỌC HOẠT ĐỘNG DẠY HỌC THỜI TT NỘI DUNG HOẠT ĐỘNG CỦA HOẠT ĐỘNG CỦA GIAN GIÁO VIÊN HỌC SINH 1 Dẫn nhập Thuật toán tìm tuyến tính GV nhắc lại bài cũ HS lắng nghe và lĩnh 5‘ tỏ ra đơn giản và thuận hội. tiện trong trường hợp số phần tử của dăy không GV đặt câu hỏi HS trả lời câu hỏi 6‘ lớn lắm. Tuy nhiên, khi số phần tử của dăy khá lớn, chẳng hạn chúng ta t́m kiếm tên một khác hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật toán
tìm tuần tự thì quả thật tốn rất nhiều thời gian. Trong thực tế, thông thường các phần tử của dãy đã có một thứ tự, do vậy thuật toán tìm kiếm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm kiếm trên dãy đã có thứ tự.Trong thuật toán này chúng ta giả sử các phần tử trong dãy đã có thứ tự tăng ( không giảm dần), tức là các phần tử đừng trước luôn có giá trị nhỏ hơn hoặc bằng (không lớn hơn) phần tử đứng sau nó. Khi đó nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy (M[Mid]) thì X chỉ có thể tìm thấy ở nữa đầu của dãy và ngược lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể tìm thấy ở nửa sau của dãy. 2 Hướng dẫn ban đầu 35’ Bài 2: Tìm kiếm nhị GV đặt câu hỏi. HS lắng nghe và trả phân lời. I.Giải thuật GV cho 1 ví dụ minh HS quan sát. họa. GV đặt câu hỏi để HS lắng nghe và trả HS hiểu ví dụ và lời câu hỏi. hiểu tìm kiếm nhị phân là gì. GV nhận xét và đánh HS lắng nghe và thắc giá. mắc( nếu có).
GV viết giải thuật HS quan sát, suy lên bảng và gọi HS nghĩ và đứng lên giải đứng lên giải thích thích. giải thuật. GV nhận xét và đánh HS lắng nghe và thắc giá. mắc(nếu có). GV gọi cho 1 số ví HS cho ví dụ. dụ. GV nhận xét và đánh HS lắng nghe và thắc giá. mắc(nếu có). II.Cài đặt GV đặt câu hỏi về HS lắng nghe- trả lời cách cài đặt của giải câu hỏi. thuật tìm kiếm nhị phân và gọi HS trả lời. GV cho thời gian HS HS suy nghĩ và lên suy và gọi HS lên bảng viết giải thuật, bảng viết chương các HS còn lại viết trình cài đặt giải vào tập. thuật tìm kiếm nhị phân. GV nhận xét, đánh HS lắng nghe và thắc giá và bổ sung. mắc(nếu có). GV đặt câu hỏi về ưu HS suy nghĩ và trả nhược điểm về cách lời câu hỏi. cài đặt giải thuật vừa viết. GV nhận xét, đánh HS lắng nghe và thắc giá và bổ sung. mắc(nếu có). GV gọi HS nêu thêm HS suy nghĩ và nêu cách khác về cài đặt thêm ví dụ. giải thuật tìm kiếm nhị phân. GV nhận xét, đánh HS lắng nghe và thắc giá và bổ sung. mắc(nếu có). III.Đánh giá giải thuật GV gọi HS đánh giá HS suy nghĩ và nêu giải thuật. lên đánh giá về giải thuật. GV nhận xét, đánh HS lắng nghe và thắc giá và bổ sung. mắc(nếu có).
GV cho thời gian để HS viết bài vào tập. HS viết bài vào tập. GV đặt câu hỏi để HS suy nghĩ và trả củng cố kiến thức về lời câu hỏi. giải thuật tìm kiếm và gọi HS trả lời. GV nhận xét, đánh HS lắng nghe và thắc giá và bổ sung. mắc(nếu có). GV gọi HS cho 1 số HS suy nghĩ cho ví ví dụ về cây tìm dụ. kiếm nhị phân. 3 Hướng dẫn thường 45’ xuyên 1.Viết chương trình cài -quan sát,nhắc nhở -thực hành đặt tìm kiếm nhị phân 2.Viết chương trình duyệt -quan sát,nhắc nhở -thực hành cây nhị phân 4 Huớng dẫn kết thúc 14’ -Nhận xét kết quả rèn -Thuyết trình ,nhắc - Lắng nghe , ghi luyện của học sinh. nhở học sinh. chép rút kinh -lưu ý các sai sót và nghiệm cách khắc phục. 5 Hướng dẫn tự rèn luyện Bài tập về nhà: 10’ 1. In chiều cao cây nhị phân 2. Tính tích các nút ở mức cao nhất 3. Đếm các nút trong cây bằng giải thuật không đệ quy IV. RÚT KINH NGHIỆM TỔ CHỨC THỰC HIỆN: Ngày tháng năm TRƯỞNG KHOA/ TRƯỞNG TỔ MÔN GIÁO VIÊN Nguyễn Ngọc Duyên
MỤC LỤC GIÁO ÁN LÝ THUYẾT *Giáo án 1 Chương III CẤU TRÚC DỮ LIỆU ĐỘNG BÀI 1: Cấu trúc dữ liệu động I.Nhu cầu xây dựng cấu trúc dữ liệu động II.Kiểu dữ liệu con trỏ (Biến không động, biến động, biến con trỏ) *Giáo án 2 Chương III CẤU TRÚC DỮ LIỆU ĐỘNG BÀI 2: Danh sách liên kết I. Danh sách liên kết đơn *Giáo án 3: Chương III CẤU TRÚC DỮ LIỆU ĐỘNG BÀI 2: Danh sách liên kết II. Danh sách liên kết kép III.Danh sách liên kết nối vòng *Giáo án 4: Chương III CẤU TRÚC DỮ LIỆU ĐỘNG BÀI 3 : Ngăn xếp ( stack) và Hàng đợi (Queue) I.Ngăn xếp (Stack) II.Hàng đợi (Queue) Chương V TÌM KIẾM I.Khái niệm tìm kiếm II.Mô tả bài toán tìm kiếm trong tin học *Giáo án 5: Chương V TÌM KIẾM I.Tìm kiếm tuyến tính II.Tìm kiếm nhị phân GIÁO ÁN THỰC HÀNH