Download miễn phí Đồ án Xây dựng chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật



MỤC LỤC
MỞ ĐẦU 1
CHƯƠNG 1 : KHẢO SÁT HIỆN TRẠNG CÔNG TÁC ĐÀO TẠO HIỆN NAY. 4
1.1. Công tác giảng dạy chung hiện nay. 4
1.2. Thực tế công tác giảng dạy tại Học viện. 5
1.3. Xu thế của thời đại. 6
CHƯƠNG 2 : TÌM HIỂU CHUNG VỀ MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT. 9
2.1. Giới hiệu môn học. 9
2.2. Kiểu dữ liệu và cấu trúc dữ liệu. 12
2.3. Danh sách liên kết. 15
2.4. Ngăn Xếp. 20
2.5. Hàng đợi. 23
2.6. Các giải thuật đệ quy. 24
2.7. Các thuật toán sắp xếp. 26
2.8. Bảng băm. 30
2.9. Các cấu trúc cây. 34
2.10. Cây nhị phân. 37
2.11. Các thuật toán tìm kiếm. 40
2.12. Cây tìm kiếm nhị phân. 42
CHƯƠNG 3 :GIỚI THIỆU HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ORACLE. 46
3.1. Hệ quản trị cơ sở dữ liệu quan hệ. 46
3.2. Cấu trúc của Oracle. 47
3.3. Bảo mật cơ sở dữ liệu. 49
3.3.1. Cơ chế bảo mật : 49
3.3.2. Tính bảo mật cơ sở dữ liệu: 49
3.3.3. Các cơ chế bảo mật 49
3.4. Quản trị cơ sở dữ liệu. 50
3.4.1. Tập tin tham số INIT.ORA 50
3.4.2. Oracle SID. 51
3.4.3. Tập tin control. 51
3.5. Quản trị không gian đĩa. 51
3.6. Quản trị người dùng. 52
3.7. Sao lưu phục hồi. 53
CHƯƠNG 4 : PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG. 55
4.1. Đặt vấn đề. 55
4.2. Mô tả chương trình. 56
4.2.1. Mô tả nội dung của chương trình. 56
4.2.2. Yêu cầu đối với hệ thống. 56
4.3. Phân tích và thiết kế hệ thống. 57
4.3.1. Phân tích hệ thống. 57
4.3.2. Sơ đồ dòng dữ liệu. 58
4.3.3. Phân tích dữ liệu. 59
4.3.4. Thiết kế menu chương trình. 61
CHƯƠNG 5 : TỔ CHỨC XÂY DỰNG CHƯƠNG TRÌNH. 62
5.1. Yêu cầu về giao diện. 62
5.2. Thiết kế giao diện. 62
KẾT LUẬN 67
TÀI LIỆU THAM KHẢO 68
 
 


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-03-26-do_an_xay_dung_chuong_trinh_ho_tro_giang_day_mon_h.ev3zE8gA8z.swf /tai-lieu/de-tai-ung-dung-tren-liketly-4990/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

(2). Lặp lại các bước dưới cho đến khi dấu kết thúc biểu thức được đọc:
(a). Đọc phần tử (token - hằng số, biến số, toán tử số học ) tiếp theo trong biểu thức RPN.
(b). Nếu phần tử này là một toán hạng, đẩy nó vào ngăn xếp. Nếu nó là toán tử, thực hiện các bước sau:
(i). Lấy ra từ đỉnh ngăn xếp hai giá trị ( nếu ngăn xếp không chứa hai phần tử, xảy ra lỗi biểu thức không đúng dạng RPN, và thuật toán kết thúc) .
(ii). Áp dụng toán tử trên vào hai giá trị vừa lấy ra.
(iii). Đẩy giá trị kết quả vào ngăn xếp.
(3). Khi gặp dấu kết thúc biểu thức, giá trị của nó là giá trị ở đỉnh của ngăn xếp (và nó phải là giá trị duy nhất trong ngăn xếp).
Chuyển đổi biểu thức trung tố sang dạng hậu tố.
Để minh hoạ cách dùng ngăn xếp chuyển đổi từ dạng trung tố sang dạng hậu tố, ta xét biểu thức trung tố sau :
7 + 2 * 3
Khi đọc biểu thức này từ trái sang phải, giá trị 7 có thể được thực hiện ngay lập tức. Tiếp theo là toán tử +, nhưng nó phải được lưu trữ vì toán hạng bên phải của nó chưa được hiển thị, vì vậy nó được đẩy vào ngăn xếp các toán tử.
Tiếp theo là toán hạng 2 được đọc và hiển thị. Lúc này nó phải được xác định là toán hạng bên phải của toán tử + hay là toán hạng bên trái của toán tử tiếp theo. Chúng ta xác định điều này bằng cách so sánh toán tử + ở đỉnh của ngăn xếp với toán tử tiếp theo *. Bởi vì * được ưu tiên hơn +, toán hạng 2 là toán hạng bên trái của toán tử *, vì vậy chúng ta đẩy * vào ngăn xếp và tìm toán hạng bên phải của nó.
Toán hạng 3 được đọc và hiển thị, bởi vì lúc này ta đạt đến kết thúc biểu thức, toán hạng bên phải của toán tử * ở đỉnh ngăn xếp được tìm ra, toán tử * có thể lấy ra từ ngăn xếp và hiển thị.
Dấu kết thúc biểu thức cũng chỉ ra rằng toán hạng bên phải của toán tử còn lại + trong ngăn xếp được tìm ra, vì vậy có thể lấy nó ra khỏi ngăn xếp và hiển thị, ta được biểu thức hậu tố.
7 2 3 * +
Mô tả thuật toán thực hiện chuyển đổi từ dạng trung tố sang hậu tố.
(1). Khởi động một ngăn xếp rỗng của các toán tử.
(2). While (không xảy ra lỗi và chưa đạt đến kết thúc của biểu thức trung tô) làm các bước sau:
(a). Đọc Token( hằng số, biến số, toán tử số học, các dấu ngoặc) tiếp theo trong biểu thức trung tố.
(b). Nếu phần tử (Token) là
(i). Một dấu ngoặc trái : đẩy nó vào ngăn xếp.
(ii). Một dấu ngoặc phải : lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi dấu ngoặc trái được đọc.(nếu ngăn xếp là rỗng thì báo lỗi).
(iii). Một toán tử : nếu ngăn xếp là rỗng hay Token được ưu tiên hơn phần tử ở đỉnh ngăn xếp, đẩy Token vào ngăn xếp.
Nếu khác lấy ra và hiển thị phần tử đỉnh của ngăn xếp; lặp lại việc so sánh Token với phần tử ở đỉnh ngăn xếp.
Chú thích : dấu ngoặc trái được xem là có ưu tiên thấp hơn các toán tử.
(iv). Một toán hạng : hiển thị nó.
(3). Khi đạt đến kết thúc của biểu thức trung tố, lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi ngăn xếp rỗng.
Hàng đợi.
Khái niệm về hàng đợi.
Hàng đợi như là một cấu trúc dữ liệu là một kiểu danh sách đặc biệt trong đó các phép toán cơ bản chèn và xoá được giới hạn ở các điểm cuối của danh sách. Các phần tử của hàng đợi được lấy ra từ một điểm cuối, gọi là đầu của hàng đợi, và được thêm vào tại đầu kia của hàng đợi, gọi là đuôi. Vậy hàng đợi là một cấu trúc “vào trước - ra trước” = ( FIST IN - FIST OUT =FIFO).
Các thao tác với hàng đợi.
Các phép toán cơ bản của hàng đợi.
CreateQ : Tạo một hàng đợi rỗng.
EmptyQ : Xác định hàng đợi có rỗng hay không.
AddQ : Thêm phần tử mới vào đuôi hàng đợi.
FullQ : Kiểm tra hàng đầy.
RemoveQ : Tìm và lấy ra phần tử ở đầu hàng đợi.
Các giải thuật đệ quy.
Khái niệm về đệ quy.
Ta nói một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hay nó được định nghĩa dưới dạng của chính nó.
Giải thuật đệ quy và thủ tục đệ quy : Nếu lời giải của một bài toán T được thực hiện bằng lời giải của một bài toán T’, có dạng giống như T, thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy. Ở đây điểm mấu chốt là T’ tuy có dạng giống T, nhưng theo một nghĩa nào đó nó phải nhỏ hơn T.
Các ví dụ về giải thuật đệ quy.
Ví dụ : trong toán học ta gặp các định nghĩa đệ quy như sau :
Số tự nhiên :
(1) 1 là một số tự nhiên.
(2) x là số tự nhiên nếu x -1 là số tự nhiên.
Hàm n giai thừa : N!
(1) 0!=1
(2) Nếu n > 0 thì n!=n(n-1)!.
Bài toán tháp Hà Nội.
Có n đĩa, kích thước nhỏ dần, đĩa có lỗ ở giữa, có thể xếp chồng chúng lên nhau xuyên qua một cọc, to dưới nhỏ trên để cuối cùng có một chồng đĩa dạng như hình tháp, như sau :
Yêu cầu đặt ra là :
Chuyển chồng đĩa từ cọc A sang cọc khác, chẳng hạn sang cọc C, theo những điều kiện sau :
(1). Mỗi lần chỉ được chuyển một đĩa.
(2). Không khi nào có tình huống đĩa to ở trên đĩa nhỏ (dù là tạm thời).
(3). Được phép sử dụng một cọc trung gian, ở đây cọc B để đặt tạm đĩa.
Tính đúng đắn của các giải thuật đệ quy.
Để chứng minh tính đúng đắn của một thuật toán, chúng ta phải chứng minh rằng thuật toán sẽ kết thúc và cho ra kết quả đúng. Ta dùng quy nạp.
Tính đúng đắn của giải thuật FACTORIAL hàm N!.
Ta muốn chứng minh rằng thủ tục hàm FACTORIAL(n) sẽ cho giá trị :
FACTORIAL(0) = 1
FACTORIAL(n) = n*(n - 1)*. . .*2*1 nếu n>0.
Ta thấy trong thủ tục có chỉ thị
If n= 0 then FACTORIAL : =1
Chứng tỏ thủ tục đã đúng với n =0 ( cho giá trị bằng 1).
Giả sử nó đã đúng với n =k, nghĩa là với FACTORIAL(k) thủ tục cho ra giá trị là : FACTORIAL(k) = k * (k -1)*. . . * 2*1
Bây giờ ta sẽ chứng minh nó đúng với n=k+1
Với n =k +1 >0 chỉ thị đứng sau else
FACTORIAL := n *FACTORIAL( n-1)
sẽ được thực hiện. Vậy với n=k+1 thì giá trị sẽ là :
(k+1)*FACTORIAL(k) = (k+1)*k*(k-1)*. . . *2*1
và việc chứng minh hoàn tất.
Các thuật toán sắp xếp.
Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng nào đó, theo một thứ tự ấn định. Chẳng hạn thứ tự tăng dần ( hay giảm dần) đối với một dãy số, thứ tự từ điển với các chữ.v.v . . .
Như vậy bài toán đặt ra ở đây là sắp xếp đối với một bảng gồm n bản ghi R1, R2, R3, . . .Rn.
Sắp xếp chọn (Selection Sort).
Ý tưởng cơ bản của cách sắp xếp này là đi qua nhiều lần danh sách hay một phần của nó, và cứ mỗi lần đi qua có một phần tử được sắp xếp theo đúng vị trí. Thuật toán mô tả như sau với danh sách cài đặt bằng mảng.
/*Thuật toán sắp xếp n phần tử trong mảng X[1], X[2],...,X[n] theo thứ tự tăng dần */.
For i=1 to n-1 làm các bước sau :
/* chọn phần tử nhỏ nhất trong danh sách con X, . . ., X[n] */
- Gán giá trị i cho SmallPos
- Gán giá trị X[SmallPos] cho Smalllest.
- For j = i +1 to n làm các bước sau :
If X[j] < SmallLest then /* Tìm ra phần tử nhỏ hơn*/
+ Gán giá trị j vào SmallPos
+ Gán giá trị X[SmallPos] cho SmallLest
/* Chuyển phần tử nhỏ nhất này vào đầu danh sách con */
- Gán giá trị X vào X[SmallPos]
- Gán giá trị SmallLest vào X
Sắp xếp chèn (Insertion ...

---

Yêu cầu Download