Chương 3: Danh sách liên kết

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...
Nội dung trích xuất từ tài liệu:
Chương 3: Danh sách liên kết Chương 3: DANH SÁCH LIÊN K T 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ách1 Khoa CNTT Trư ng TC TÂY NAM Á © 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 ñ ng2 Khoa CNTT Trư ng TC TÂY NAM Á © 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 CNTT Trư ng TC TÂY NAM Á © 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 bytes4 Khoa CNTT Trư ng TC TÂY NAM Á © 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 *p5 Khoa CNTT Trư ng TC TÂY NAM Á © 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 CNTT Trư ng TC TÂY NAM Á © 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 CNTT Trư ng TC TÂY NAM Á © 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 i9 Khoa CNTT Trư ng TC TÂY NAM Á © Dương Thành Ph t-www.thayphet.net Ví d : 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);10 Khoa CNTT Trư ng TC TÂY NAM Á © 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ách11 Khoa CNTT Trư ng TC TÂ ...