Cấu Trúc Dữ Liệu và Giải Thuật - chương 3

Chia sẻ: Chung Tran Minh Tanh Tanh | Ngày: | Loại File: PDF | Số trang:80

Thêm vào BST

Báo xấu

111
lượt xem 28
download

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

Cấu trúc dữ liệu động: Biến không động dùng để lưu trữ đối tượng dữ liệu được sử dụng không có nhu cầu thay đôiu cà kích thước, số lượng..

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu Trúc Dữ Liệu và Giải Thuật - chương 3

Chương 3: C U TRÚC D LI U ð NG 3.1. Ki u d li u con tr 3.2. Danh sách liên k t (link list) 3.3. Danh sách liên k t ñơn 3.4. S p x p danh sách 3.5. Các c u trúc ñ c bi t c a danh sách liên k t ñơn 3.5.1. Stack 3.5.2. Hàng ñ i (Queue) 3.6. Bài t p 1 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.1. Ki u D Li u Con Tr 3.1.1. Bi n không ñ ng 3.1.2. Ki u con tr 3.1.3. Bi n ñ ng 2 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.1.1. Bi n không ñ ng Dùng ñ lưu tr nh ng ñ i tư ng d li u ñư c s d ng không có nhu c u thay ñ i và kích thư c, s lư ng . . . • ðư c khai báo tư ng minh • T n t i trong ph m vi khái báo • Kích thư c không thay ñ i trong su t quá trình s ng Ví d : int a; char b[10]; 3 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.1.2. Ki u con tr Ki u con tr là ki u cơ s dùng lưu ñ a ch c a m t ñ i tư ng d li u khác. Bi n thu c ki u con tr là bi n mà giá tr c a nó là ñ a ch m t vùng nh c a m t bi n ho c là giá tr Null. Tùy vào lo i con tr g n (near pointer) hay con tr xa (far pointer) mà ki u d li u con tr có các kích thư c khác nhau: + Con tr g n: 2 bytes + Con tr xa: 4 bytes 4 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
Cú pháp ñ nh nghĩa m t ki u con tr typedef *; Ví d : typedef int *intpointer; inpointer p; Hay int *p; Các thao tác: - Khi 1 bi n con tr p lưu ñ a ch c a ñ i tư ng x, ta nói “p tr x” - Gán ñ a ch c a bi n cho con tr p: p=& -Truy xu t n i dung c a ñ i tư ng do p tr ñ n *p 5 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
c. Ví d : void main() { int a,b,*pa,*pb; a=2; b=3; cout
3.1.3. Bi n ñ ng Trong 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 ñ i tư ng d li u(do chúng ph thu c vào ng c nh). Các ñ i tư ng d li u này ñư c khai báo như bi n ñ ng. Bi n ñ ng là nh ng bi n th a: Không ñư c khai báo tư ng minh. ðư c c p phát/gi i phóng b nh khi yêu c u. Các bi n này không theo qui t c ph m vi. Vùng nh c a bi n ñư c c p phát trong Heap. Kích thư c thay ñ i trong quá trình s ng. 7 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
Các thao tác trên bi n ñ ng: T o bi n ñ ng và cho con tr p tr ñ n: Các hàm c p phát b nh : void* malloc(size); // tr v con tr ch ñ n m t vùng // nh size byte v a ñư c c p phát. void* calloc(n,size);// tr v con tr ch ñ n m t vùng // nh v a ñư c c p phát g m n //ph n t ,m i ph n t có kích //thư c size byte new // hàm c p phát b nh trong C++ 8 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
H y m t bi n ñ ng do p ch ñ n: Hàm free(p): Hu vùng nh c p phát b i hàm malloc do p tr t i Hàm delete p: hu vùng nh c p phát b i hàm new do p tr t i 9 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
Ví d : //Trong C int* p1, p2; //C p phát vùng nh cho 1 bi n ñ ng ki u int p1 = (int*)malloc(sizeof(int)); //ð t giá tr 5 cho bi n ñ ng p1 p1* = 5; //C p phát bi n ñ ng ki u m ng 10 p.t ki u int p2 = (int*)calloc(10, sizeof(int)); //ð t giá tr 0 cho ph n t th 4 c a m ng p2 (p2+3)* = 0; free(p1); free(p2); //Trong C++ int* p; p=new int; delete p; 10 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.2. Danh Sách Liên K t 3.2.1. Ð nh nghĩa 3.2.2. Các hình th c t ch c danh sách 11 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.2.1. Ð nh nghĩa Ki u danh sách Tx g m các ph n t thu c ki u T ñư c ñ nh nghĩa là: Tx = trong ñó: Vx = {t p h p có th t các ph n t ki u T ñư c móc n i v i nhau theo trình t tuy n tính}; Ox = {T o danh sách; Tìm 1 ph n t trong danh sách; Chèn m t ph n t vào danh sách; Hu m t ph n t kh i danh sách ; Li t kê danh sách, S p x p danh sách ...} 12 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
Ví du: H sơ các h c sinh c a m t trư ng ñư c t ch c thành danh sách g m nhi u h sơ c a t ng h c sinh; s lư ng h c sinh trong trư ng có th thay ñ i do v y c n có các thao tác thêm, h y m t h sơ; ñ ph c v công tác giáo v c n th c hi n các thao tác tìm h sơ c a m t h c sinh, in danh sách h sơ ... 13 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.2.2. Các hình th c t ch c danh sách M i liên h gi a các ph n t ñư c th hi n ng m: M i ph n t trong danh sách ñư c ñ c trưng b ng ch s . C p ph n t xi, xi+1 ñư c xác ñ nh là k c n V i hình th c t ch c này, các ph n t c a danh sách ph i lưu tr liên ti p trong b nh , công th c xác ñ nh ñ a ch ph n t th I là. Cách bi u di n này cho phép truy xu t ng u nhiên, ñơn gi n và nhanh chóng ñ n m t ph n t b t kỳ trong danh sách, nhưng l i h n ch v m t s d ng b nh b lãng phí. 14 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
M i liên h gi a các ph n t th hi n tư ng minh: M i ph n t ngoài các thông tin còn ch a m t liên k t (ñ a ch ) ñ n ph n t k trong danh sách nên còn ñư c g i là danh sách móc n i. V i hình th c này các ph n t trong danh sách không c n ph i lưu tr k c n trong b nh nên kh c ph c ñư c các khuy t ñi m c a hình th c t ch c m ng, nhưng vi c truy xu t ñ n m t ph n t ñòi h i ph i th c hi n truy xu t qua m t s ph n t khác. 15 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
Có các ki u t ch c liên k t gi a các ph n t . Danh sách liên k t ñơn Danh sách liên k t kép Danh sách liên k t vòng 16 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.3. Danh Sách Liên K t ðơn 3.3.1. T ch c danh sách ñơn theo cách c p phát liên k t 3.3.2. Các thao tác cơ b n trên danh sách ñơn 17 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
3.3.1. T ch c danh sách ñơn theo cách c p phát liên k t M i ph n t là m t c u trúc ch a 2 thông tin : - Thành ph n d li u: Lưu tr các thông tin v b n thân ph n t . - Thành ph n m i liên k t: lưu tr ñ a ch c a ph n t k ti p trong danh sách, ho c lưu tr giá tr NULL n u là ph n t cu i danh s ách. Ta có ñ nh nghĩa t ng quát struct tNode { DataType key; tNode* pNext; }; 18 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
Ví d : Ð nh nghĩa danh sách ñơn lưu tr h sơ SV struct tSinhVien { char Ten[30]; int MaSV; }; typedef struct tSinhVien Sinhvien; struct SinhvienNode { Sinhvien Info; SinhvienNode* pNext; }; typedef struct SinvienNode SVNode; 19 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net
N u bi t ñư c ñ a ch c a ph n t ñ u tiên trong danh sách ñơn thì có th d a vào thông tin pNext c a nó ñ truy xu t ñ n ph n t th 2, th 3... ð qu n lý m t xâu ñơn ch c n bi t ñ a ch ph n t ñ u xâu. Con tr Head dùng ñ lưu tr ñ a ch ph n t ñ u xâu Khai báo: NODE *pHead; Ð ti n l i, có th s d ng thêm m t con tr pTail gi ñ a ch ph n t cu i xâu. Khai báo: NODE *pTail; 20 Khoa KTCN Trư ng ðH KTKT B.Dương © Dương Thành Ph t-www.thayphet.net