Hàng đợi và ngăn xếp

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:9

0
245
lượt xem
58
download

Hàng đợi và ngăn xếp

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo về hàng đợi và ngăn xếp - môn Khoa học máy tính

Chủ đề:
Lưu

Nội dung Text: Hàng đợi và ngăn xếp

  1. Hàng ñ i và Ngăn x p (Queue and Stack) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com
  2. Hàng ñ i (Queue) Hàng ñ i là gì? Là m t danh sách nhưng các phép toán ch ñư c th c hi n hai ñ nh c a danh sách. M t ñ nh g i là ñ u hàng, ñ nh còn l i g i là cu i hàng. Ví d : • X p hàng mua vé tàu xe, giao d ch v i ngân hàng Tính ch t: Vào trư c ra trư c (First in First Out: FIFO)
  3. Hàng ñ i Tr u tư ng hóa c u trúc hàng ñ i 1. Mô t d li u A = (a0, a1, …, an) trong ñó: – ao: Ph n t ñ u c a hàng ñ i A – an: Ph n t cu i c a hàng ñ i A Ví d : A = (‘Vinh’, ‘Tu n’,. ‘Ánh’) trong ñó: ‘Vinh’: ð u hàng ñ i ‘Ánh’: Cu i hàng ñ i
  4. Các phép toán trên hàng ñ i • empty (A): Ki m tra hàng ñ i có r ng hay không • length (A): Cho bi t s ph n t c a hàng ñ i • EnQueue (A, x): Thêm ph n t x cu i hàng ñ i. A = (a0, a1,…, an) → A = (a0,a1,…,an , x) Ví d : A = (1,3,5) EnQueue (A, 4) → A = (1, 3, 5, 4) • DeQueue (A): Lo i ph n t ñ u hàng ñ i A = (a0, a1,…, an-1, an) → A = (a1,…,an) Ví d : A = (1,3,5) DeQueue (A) → A = (3, 5) • GetHead (A): L y ph n t ñ u hàng ñ i A = (a0, a1,…, an-1, an) → getHead (A) → a0 Ví d : A = (1,3,5) getHead (A) → 1
  5. Bài t p 1. Vi t chương trình cài ñ t c u trúc hàng ñ i b ng m ng và danh sách liên k t 2. Tính ñ ph c t p cho cài ñ t câu 1 3. ð c và cài ñ t hàng ñ i b ng màng tròn
  6. Ngăn x p (stack) Ngăn x p là gì? Là m t danh sách nhưng các phép toán ch ñư c th c hi n m t ñ nh c a danh sách. Ví d : – L y hàng hóa trong kho – Tìm các c p d u ngo c tương ng Tính ch t: Vào trư c ra sau (First In Last Out: FILO)
  7. Ngăn x p Tr u tư ng hóa c u trúc ngăn x p 1. Mô t d li u A = (a0, a1, …, an) trong ñó an là ph n t ñ nh c a ngăn x p A Ví d : A = (1, 2, 3, 3, 4, 5) → 5: Ph n t ñ nh ngăn x p A = (‘Vinh’, ‘Tu n’,. ‘Ánh’) → Ánh: Ph n t ñ nh ngăn x p 2. Mô t các phép toán trên c u trúc ngăn x p • empty (A): Ki m tra ngăn x p có r ng hay không • length (A): Cho bi t s ph n t c a ngăn x p
  8. Ngăn x p (stack) • push (A, x): Thêm ph n t x ñ nh ngăn x p. A = (a0, a1,…, an) → A = (a0,a1,…,an , x) Ví d : A = (1,3,5) push (A, 4) → A = (1, 3, 5, 4) • Pop (A): Lo i ph n t ñ nh ngăn x p A = (a0, a1,…, an-1, an) → A = (a0,a1,…,an-1) Ví d : A = (1,3,5) pop (A) → A = (1, 3) • GetTop (A): L y ph n t ñ nh ngăn x p A = (a0, a1,…, an-1, an) → getTop (A) → an Ví d : A = (1,3,5) getTop (A) → 5
  9. Bài t p 1. Vi t chương trình cài ñ t c u trúc ngăn x p b ng m ng và danh sách liên k t 2. Vi t chương trình tìm t t c các c p d u ngo c tương ng trong m t chương trình C++ 3. V i m i phép toán, tính ñ ph c t p

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản