Vui lòng download xuống để xem tài liệu đầy đủ.

Cấu trúc dữ liệu và giải thuật_ Bài tập lớn

Chia sẻ: | Ngày: | Loại File: doc | 7 trang

1
1.070
lượt xem
307
download

*ADT (Abstract Data Types) – kiểu dữ liệu trừu tượng bao gồm: Tập các giá trị (đối tượng) Tập các phép toán có thể thực hiện với tất cả các giá trị này Cách biểu diễn dữ liệu được sử dụng chung cho tất cả các giá trị này *Stack (ngăn xếp): là một kiểu dữ liệu trừu tượng, một dạng đặc biệt của danh sách tuyến tính (dãy gồm 0 hoặc nhiều hơn các phần tử cùng kiểu cho trước) trong đó các đối tượng được nạp vào (push) và lấy ra (pop) chỉ từ một đầu gọi là đỉnh (top) của danh sách....

Lưu

Cấu trúc dữ liệu và giải thuật_ Bài tập lớn
Nội dung Text

  1. Cấu trúc dữ liệu và giải thuật ADT Stack Bài tập lớn CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đề tài: ADT Stacks [Ngăn xếp] -o0o- Mai Xuân Cường - Nguyễn Trung Dũng A - Hoàng Mạnh Hùng Nguyễn Thị Thu Nga - Vũ Thị Quỳnh Trang - Ngô Anh Tuấn - Nguyễn Tuấn *** I. Định nghĩa: *ADT (Abstract Data Types) – kiểu dữ liệu trừu tượng bao gồm: ­ Tập các giá trị (đối tượng) ­ Tập các phép toán có thể thực hiện với tất cả các giá trị này ­ Cách biểu diễn dữ liệu được sử dụng chung cho tất cả các giá trị này *Stack (ngăn xếp): là một kiểu dữ liệu trừu tượng, một dạng đặc biệt của danh sách tuyến tính  (dãy gồm 0 hoặc nhiều hơn các phần tử cùng kiểu cho trước) trong đó các đối tượng được nạp  vào (push) và lấy ra (pop) chỉ từ một đầu gọi là đỉnh (top) của danh sách.  nguyên tắc: vào sau ra trước (LIFO – last in first out) ­  Đối tượng cất giữ:  các phần tử ­ số (nguyên, thực), ký tự, xâu  (string), mảng (array), bản ghi (record), file... ­ Các phép toán cơ bản:  + push  đẩy phần tử vào ngăn xếp + pop  lấy phần tử ra khỏi ngăn xếp + isEmpty  kiểm tra ngăn xếp rỗng + size  trả về số phần tử của ngăn xếp + top  trả về giá trị của phần tử nằm ở đầu danh sách mà không lấy nó ra khỏi ngăn xếp II. Cài đặt: 1­ Các cấu trúc dữ liệu để biểu diễn và cài đặt các phép toán: a) Mảng: + nạp các phần tử theo thứ tự từ trái sang phải + có biến lưu trữ chỉ số của phần tử ở đầu ngăn xếp Stack 3 5 2 …… 6 7 0 1 2 …. n maxn + trong đó: maxn _ số phần tử tối đa xin cấp phát của ngăn xếp n _ biến dùng để lưu trữ chỉ số phần tử ở đầu ngăn xếp + một hạn chế của việc sử dụng mảng là phải khai báo kích thước tối đa để dự phòng nên gây  lãng phí bộ nhớ hoặc phải thông báo tràn bộ nhớ (Full Stack) khi thực hiện thao tác push b) Danh sách móc nối (con trỏ): 1
  2. Cấu trúc dữ liệu và giải thuật ADT Stack + mỗi nút bao gồm 2 thành phần cơ bản:  elements  để lưu trữ nội dung dữ liệu của phần tử,  *next là con trỏ đến nút tiếp theo trong ngăn xếp + thao tác bố sung và loại bỏ luôn làm việc ở nút đầu tiên thông qua việc sử dụng một con trỏ  *top trỏ đến nút đầu tiên trong ngăn xếp + việc sử dụng danh sách móc nối (hay con trỏ) có một ưu điểm là không phải khai báo số phần  tử tối đa của ngăn xếp để dự phòng từ đó có thể tiết kiệm được bộ nhớ không cần thiết. 7 54 ……. 93 5 NULL *top elements *next 2­ Chương trình minh họa:  file: StackPtr.cpp, STACKARR.cpp III. Ứng dụng: 1­ Phát biểu bài toán: *Tính giá trị biểu thức số học: Biểu thức số học xuất hiện rất nhiều trong cuộc sống và việc tính toán giá trị của các biểu thức  đó là điều tất yếu, quan trọng. Ví dụ:  ­ Khi sử dụng máy tính (calculator), người dùng sẽ nhập các biểu thức số học cần tính thông  qua các phím số và phép toán có sẵn. Nhiệm vụ của máy sẽ tính toán và hiển thị kết quả chính  xác ra màn hình. ­ Khi sử dụng các bảng tính điện tử (như Excel, …) để lập các bảng tính lương, thống kê việc thu  chi của doanh nghiệp…, người dùng sẽ nhập các biểu thức số học vào các ô tính. Khi đó, chương  trình sẽ có nhiệm vụ phân tích và tính toán rồi đưa ra kết quả tại ô đó. ­ Hay trong các ngôn ngữ lập trình (như C, PASCAL…), ta đã khá quen thuộc với các lệnh gán X=<biểu thức số học> //X là biến Khi thực hiện chương trình, gặp các lệnh gán, máy tính cần phải xác định giá trị của các biểu  thức số học đó và gán kết quả cho biến X.  Vì vậy, việc xây dựng một chương trình tính toán giá trị của các biểu thức số học là cần thiết. Biểu thức số học là một dãy các toán hạng (hằng (số), biến hoặc hàm) nối với nhau bởi các  phép toán số học (như cộng, trừ, nhân, chia, lũy thừa, căn thức,...). Trong các biểu thức có thể  chứa các dấu ngoặc tròn để xác định thứ tự ưu tiên. Khi đó các phép toán trong ngoặc sẽ được  thực hiện trước các phép toán ở ngoài. Các phép toán số học được phân ra làm 2 loại: ­ Các phép toán hai ngôi (+, ­, *, /, ^,…): mỗi phép toán được đặt giữa các toán hạng. Ví dụ:  2+3, 56*12, 3^8,… ­ Các phép toán một ngôi (căn, logarit, các hàm lượng giác: sin, cos, tg,…): mỗi phép toán đi  ngay trước toán hạng. Ví dụ: sin4, ln7,… Hơn nữa, khi tính các biểu thức số học, ta cần phải tuân theo những quy tắc sau: ­ Thứ tự ưu tiên: ^  *, /  +, ­ ­ Quy tắc kết hợp: cho biết khi có 2 phép toán có cùng thứ tự ưu tiên thì sẽ thực hiện phép toán  nào trước. + ^: thực hiện từ phải qua trái. + + ­ * /: thực hiện từ trái qua phải. 2
  3. Cấu trúc dữ liệu và giải thuật ADT Stack + dấu () được ưu tiên hơn cả thứ tự ưu tiên và quy tắc kết hợp. 2­ Mô tả thuật toán giải và đánh giá độ phức tạp của thuật toán: a) Mô tả thuật toán giải: Bài toán tính toán giá trị của biểu thức số học được xây dựng một cách dễ dàng bằng thuật toán  Ba Lan trên cơ sở ứng dụng của kiểu dữ liệu trừu tượng ngăn xếp (stack). *Ký pháp nghịch đảo Ba Lan: Ký pháp nghịch đảo Ba Lan được phát minh vào khoảng giữa thập kỷ 1950 bởi Charles Hamblin  ­ một triết học gia và khoa học gia máy tính người Úc ­ dựa theo công trình về ký pháp Ba Lan  của nhà Toán học người Ba Lan Jan Łukasiewicz. Hamblin trình bày nghiên cứu của mình tại một  hội nghị khoa học vào tháng 6 năm 1957 và chính thức công bố vào năm 1962. Từ cái tên hậu tố cũng có thể đoán ra phần nào là theo cách biểu diễn này, các toán tử sẽ được  đặt sau các toán hạng. Cụ thể là biểu thức trung tố: 4+5 sẽ được biểu diễn lại thành 4 5 +.  Ý tưởng là đọc biểu thức từ trái sang phải, nếu gặp một toán hạng (con số hoặc biến) thì push  toán hạng này vào ngăn xếp; nếu gặp toán tử, lấy hai toán hạng ra khỏi ngăn xếp (stack), tính kết  quả, đẩy kết quả trở lại ngăn xếp. Khi quá trình kết thúc thì con số cuối cùng còn lại trong ngăn  xếp chính là giá trị của biểu thức đó.  Ví dụ:  biểu thức trung tố :  5 + ((1 + 2) * 4) + 3 được biểu diễn lại dưới dạng hậu tố là (ta sẽ bàn về thuật toán chuyển đổi từ trung tố sang hậu  tố sau):  5 1 2 + 4 * + 3 + Quá trình tính toán sẽ diễn ra theo như bảng dưới đây:  Ký tự Thao tác Trạng thái stack 5 Push 5 5 1 Push 1 5, 1 2 Push 2 5, 1, 2 + Tính 1 + 2  5, 3 Push 3 4 Push 4 5, 3, 4 * Tính 3 * 4 5, 12 Push 12 + Tính 12 + 5  17 Push 17 3 Push 3 17, 3 + Tính 17 + 3 20 Push 20 Chuyển đổi từ trung tố sang hậu tố: 3
  4. Cấu trúc dữ liệu và giải thuật ADT Stack Thuật toán chuyển đổi này được phát minh bởi vị giáo sư người Đức nổi tiếng Edsger Dijkstra  (cũng là tác giả của thuật toán tìm đường đi ngắn nhất được đặt theo tên ông và semaphore, một  kỹ thuật để đồng bộ các tiến trình trong lập trình đa nhiệm). Thuật toán này cũng dựa theo cơ chế  ngăn xếp. Ý tưởng chung của thuật toán cũng là duyệt biểu thức từ trái sang phải: ­ Nếu gặp một toán hạng (con số hoặc biến) thì ghi nó vào chuỗi kết quả (chuỗi kết quả là biểu  thức trung tố). ­ Nếu gặp dấu mở ngoặc, đưa nó vào stack. ­ Nếu gặp một toán tử (gọi là o1 ), thực hiện hai bước sau: + Chừng nào còn có một toán tử o2 ở đỉnh ngăn xếp VÀ độ ưu tiên của o1 nhỏ hơn hay bằng độ  ưu tiên của o2 thì lấy o2 ra khỏi ngăn xếp và ghi vào kết quả. + Push o1 vào ngăn xếp ­ Nếu gặp dấu đóng ngoặc thì cứ lấy các toán tử trong ngăn xếp ra và ghi vào kết quả cho đến  khi lấy được dấu mở ngoặc ra khỏi ngăn xếp. ­ Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toán hạng (nếu có) từ ngăn xếp ra và ghi  vào chuỗi kết quả. Để dễ hiểu, bạn hãy quan sát quá trình thực thi của thuật toán qua một ví dụ cụ thể sau: Biểu thức cần chuyển đổi: 3+4*2/(1­5) Ký tự Thao tác Stack Chuỗi hậu tố 3 Ghi 3 vào k.quả   3 + Push + +   4 Ghi 4 vào k.quả   3 4 * Push * + *    2 Ghi 2 vào kquả   3 4 2 / Lấy * ra khỏi stack, ghi vào  +  / 3 4 2 * k.quả, push / ( Push (  + / ( 3 4 2 * 1 Ghi 1 vào k.quả + / (  3 4 2 * 1 ­ Push ­ + / ( ­  3 4 2 * 1 5 Ghi 5 vào k.quả  + / ( ­  3 4 2 * 1 5 ) Pop cho đến khi lấy được (, ghi  + /  3 4 2 * 1 5 ­ các toán tử pop được ra k.quả  2 Ghi 2 ra k.quả  + /  3 4 2 * 1 5 – 2   Pop tất cả các toán tử ra khỏi    3 4 2 * 1 5 – 2  / + ngăn xếp và ghi vào kết quả b) Đánh giá độ phức tạp của thuật toán: Giả sử xâu biểu thức dạng trung tố đầu vào có độ dài là n Gọi thời gian tính của thuật toán là O(f(n)),  ­ thời gian tính của hàm convert (char *input, char *output) chuyển đổi xâu biểu thức đầu vào  từ dạng trung tố sang hậu tố là O(g(n)),  ­ thời gian tính của hàm tinhtoan (char *bieuthuc) tính toán giá trị của biểu thức dạng hậu tố là  O(h(n)). 4
  5. Cấu trúc dữ liệu và giải thuật ADT Stack Ta  có:  thời gian  cài đặt  và  thực hiện  các  phép  toán  cơ  bản trên stack  như  Push(),   Pop(),   Is_Empty(), … là hằng số  O(1). Vậy ta có thời gian tính của thuật toán là: O(f(n)) = max {O(g(n)), O(h(n))}   * Đánh giá độ phức tạp của hàm convert(char *input, char *output)     tính O(g(n))      ­ Chuyển xâu biểu thức đầu vào sang chữ thường strlwr(input) thời gian tính là O(n); ­ Duyệt toàn bộ xâu: while(input[i]!=’\0’)  { while(input[i]==””) // loại bỏ dấu “ ”; { // câu lệnh hoặc khối câu lệnh với thời gian O(1); i++; } if(((input[i]>='0')&&(input[i]<='9'))||(input[i]=='.'))  { while(((input[i]>='0')&&(input[i]<='9'))||(input[i]=='.')) { // câu lệnh hoặc khối câu lệnh với thời gian O(1); } … } elseif(…) { … } … }  + Vòng lặp này thực hiện cho đến khi gặp phần tử NULL của biểu thức (kết thúc biểu thức), nếu  là ký tự rỗng (dấu cách) thì bỏ qua (tăng chỉ số phần tử của xâu thêm một đơn vị) rồi tiếp tục cho  đến khi hết các ký tự cách liền nhau, gặp chữ số hoặc dấu chấm thì đưa vào output cho đến khi  hết các ký tự này liền nhau… Vì vậy, thuật toán chỉ duyệt qua xâu biểu thức đúng một lần  thời  gian tính là O(n)  thời gian tính của hàm convert(char *input, char *output) là: O(g(n)) = max{O(n),O(n)} = O(n)   * Đánh giá độ phức tạp của hàm tinhtoan(char *bieuthuc)     tính O(h(n))      Trình tự thực hiện của hàm này cũng tương tự như hàm convert. Tuy nhiên độ dài của xâu đầu  vào có sự thay đổi do hàm convert đã bỏ qua các dấu cách và đơn giản hóa các toán tử (như sin   s, cos  c, ...) Giả sử độ dài của xâu biểu thức đầu vào là m (m<n) ­ thời gian tính toán các phép tính cơ bản là hằng số 5
  6. Cấu trúc dữ liệu và giải thuật ADT Stack ­ các phép toán cơ bản trên stack là hằng số ­ thời gian thực hiện gán các giá trị vào các biến tạm thời cũng là hằng số ­ xâu biểu thức đầu vào được duyệt qua đúng một lần Từ đó, ta có thể dễ dàng suy ra tương tự như trên, thời gian tính của hàm  tinhtoan (char   *bieuthuc) là: O(h(n)) = O(m)  Vậy thời gian tính của toàn bộ thuật toán tính giá trị biểu thức dạng hậu tố là: O(f(n)) = max {O(n),O(m)} = O(n) 3­ Mô tả cài đặt chương trình: Đầu vào: Biểu thức số học dạng trung tố. Đầu ra: Biểu thức số học dạng hậu tố và giá trị kết quả của biểu thức đó. *Cài đặt chương trình: Sử dụng các phép toán cơ bản xây dựng được trên kiểu dữ liệu trừu tượng ngăn xếp, tiến hành  việc chuyển đổi biểu thức số học trung tố do người dùng nhập từ bàn phím sang biểu thức số học  dạng hậu tố, tính toán giá trị của biểu thức đó và hiển thị kết quả ra màn hình. Chương trình gồm: ­ Hàm  main(): thực hiện việc nhập biểu thức vào xâu  input, gọi các hàm chuyển đổi và tính  toán đưa kết quả ra màn hình, tạo giao diện người dùng (có thể lặp lại việc tính toán với biểu thức  khác). ­ Hàm convert(char *input,char *output): thực hiện việc phân tích xâu biểu thức vào (input),  chuyển đổi thành xâu biểu thức ra (output) là biểu thức số học ban đầu dưới dạng hậu tố. + duyệt lần lượt các phần tử của xâu input. + bỏ qua khi gặp dấu cách. + nếu là chữ số hoặc dấu chấm (số thực) thì đưa vào xâu output. + gặp dấu mở ngoặc ‘(‘ thì đẩy vào stack. + gặp dấu cộng ‘+’ hoặc trừ ‘­‘ mà khi đó đỉnh ngăn xếp là dấu ‘(‘thì đẩy vào, còn không phải là  dấu mở ‘(‘ thì lấy phần tử đỉnh ra khỏi ngăn xếp trước, đưa vào xâu output rồi mới đẩy vào stack. + gặp dấu nhân ‘*’ hoặc chia ‘/’: đẩy vào nếu đỉnh không phải là ‘(‘, ‘+’ hoặc ‘­‘, lấy phần tử đỉnh  ra trước đưa vào output rồi mới đẩy vào stack nếu ngược lại. + tương tự khi gặp các toán tử lũy thừa ‘^’, căn thức ‘v’, logarit ‘l’, và các hàm lượng giác (sin ­  ‘s’, cos – ‘c’, tan – ‘t’): đẩy vào ngay nếu đỉnh không phải là các toán tử ở trên, lấy phần tử đỉnh  ra trước đưa vào output rồi mới đẩy vào stack nếu ngược lại. + gặp dấu đóng ngoặc ‘)’ thì đẩy các phần tử trong ngăn xếp ra cho đến khi gặp dấu mở ngoặc  ‘(‘, đưa vào xâu output. + cuối cùng ta thu được xâu output là biếu thức dạng hậu tố ­ Hàm tinhtoan(char *bieuthuc): thực hiện việc phân tích biểu thức dưới dạng hậu tố, tính toán  giá trị biểu thức theo thuật toán Ba Lan, trả lại giá trị là kết quả của biểu thức ban đầu. + duyệt xâu chứa biểu thức dạng hậu tố. + duyệt từng phần tử của xâu. + nếu gặp dấu cách thì bỏ qua, nếu phần tử = NULL thì kết thúc. + gặp chữ số hoặc dấu chấm lưu ra một xâu tạm thời để thực hiện việc chuyển đổi sang kiểu số  thực đẩy vào stack. + khi gặp các toán tử hai ngôi như +, ­, *, /, ^: đẩy lần lượt 2 phần tử ở đỉnh ngăn xếp ra, lưu vào  2 biến tạm thời rồi tiến hành thực hiện phép tính. 6
  7. Cấu trúc dữ liệu và giải thuật ADT Stack + khi gặp toán tử một ngôi như sin, cos, tan, ln, e^: thực hiện việc đẩy phần tử đỉnh ra lưu vào  biến tạm thời rồi tính. + lặp lại quá trình cho đến khi duyệt hết xâu (khi ngăn xếp còn duy nhất một phần tử).  ­ Ngoài ra, chương trình còn có một thư viện lưu trữ cấu trúc của ngăn xếp và các phép toán cơ  bản trên ngăn xếp (file Pstack.h). 4­ Hướng dẫn sử dụng: * Các phép toán mà chương trình có thể thực hiện được: Phép toán Biểu diễn Ví dụ Cộng x + y 2+3 Trừ x – y 8­1 Nhân x * y 5*7 Chia x / y 9/2 Lũy thừa x ^ y 5^6 Lũy thừa cơ số e ex e4 Căn bậc 2 vx v25 Logarit tự nhiên lnx hoặc lx l20 sin sinx hoặc sx s4 cos cosx hoặc cx c45 tan tanx hoặc tx t32 * Một số chú ý: ­ Số thực. Ví dụ: 5.67 ­ Số âm. Ví dụ: ­6 ­ Các góc trong các hàm lượng giác được tính theo đơn vị radian. ­ Có thể sử dụng các dấu đóng mở ngoặc. Ví dụ: (2+3)*5­7.4/(2.56­5.32) ­ Các cách nhập biểu thức sau là không hợp lệ  sin­5  hợp lệ: sin(­5)  e­2  hợp lệ: e(­2)  2/­1  hợp lệ: 2/(­1) <dấu trừ không được viết liền sau các toán tử để phân biệt số âm và toán tử ‘­‘>  vv7  hợp lệ: v(v7)  lnsin2  hợp lệ: ln(sin2)  <Các toán tử một ngôi không được viết liền nhau> 7

Có Thể Bạn Muốn Download

Đồng bộ tài khoản