Mảng và danh sách

Chia sẻ: Hai Hoang | Ngày: | Loại File: PDF | Số trang:38

0
145
lượt xem
29
download

Mảng và danh sách

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

Giới thiệu kiểu dữ liệu "kiểu mảng" trong C

Chủ đề:
Lưu

Nội dung Text: Mảng và danh sách

  1. Bài 10: Mảng và danh sách 10.1. Mảng 10.1.1. Mảng một chiều, mảng nhiều chiều Kh¸i niÖm Mảng là một tập hợp các phần tử cố định có cùng một kiểu, gọi là kiểu phần tử. Kiểu phần tử có thể là có các kiểu bất kỳ: ký tự, số, chuỗi ký tự…; cũng có khi ta sử dụng kiểu mảng để làm kiểu phần tử cho một mảng (trong trường hợp này ta gọi là mảng của mảng hay mảng nhiều chiều). Ta có thể chia mảng làm 2 loại: mảng 1 chiều và mảng nhiều chiều. Mảng là kiểu dữ liệu được sử dụng rất thường xuyên. Chẳng hạn người ta cần quản lý một danh sách họ và tên của khoảng 100 sinh viên trong một lớp. Nhận thấy rằng mỗi họ và tên để lưu trữ ta cần 1 biến kiểu chuỗi, như vậy 100 họ và tên thì cần khai báo 100 biến kiểu chuỗi. Nếu khai báo như thế này thì đoạn khai báo cũng như các thao tác trên các họ tên sẽ rất dài dòng và rắc rối. Vì thế, kiểu dữ liệu mảng giúp ích ta trong trường hợp này; chỉ cần khai báo 1 biến, biến này có thể coi như là tương đương với 100 biến chuỗi ký tự; đó là 1 mảng mà các phần tử của nó là chuỗi ký tự CÊu tróc l-u tr÷ cña m¶ng. CÊu tróc d÷ liÖu ®¬n gi¶n nhÊt dïng ®Þa chØ tÝnh ®-îc ®Ó thùc hiÖn l-u tr÷ vµ t×m kiÕm phÇn tö, lµ m¶ng mét chiÒu hay vÐc t¬. Th«ng th-êng th× mét sè tõ m¸y sÏ ®-îc dµnh ra ®Ó l-u tr÷ c¸c phÇn tö cña m¶ng. C¸ch l-u tr÷ nµy ®-îc gäi lµ c¸ch l-u tr÷ kÕ tiÕp (sequential storage allocation). Tr-êng hîp mét m¶ng mét chiÒu hay vÐc t¬ cã n phÇn tö cña nã cã thÓ l-u tr÷ ®-îc trong mét tõ m¸y th× cÇn ph¶i dµnh cho nã n tõ m¸y kÕ tiÕp nhau. Do kÝch th-íc cña vÐc t¬ ®· ®-îc x¸c ®Þnh nªn kh«ng gian nhí dµnh ra còng ®-îc Ên ®Þnh tr-íc. VÐc t¬ A cã n phÇn tö, nÕu mçi phÇn tö ai (0 ≤ i ≤ n) chiÕm c tõ m¸y th× nã sÏ ®-îc l-u tr÷ trong cn tõ m¸y kÕ tiÕp nh- h×nh vÏ: a0 A1 . . ai . . an . . cn tõ m¸y kÕ tiÕp nhau L0 §Þa chØ cña ai ®-îc tÝnh bëi c«ng thøc: Loc(ai) = L0 + c * i trong ®ã : L0 ®-îc gäi lµ ®Þa chØ gèc - ®ã lµ ®Þa chØ tõ m¸y ®Çu tiªn trong miÒn nhí kÕ tiÕp dµnh ®Ó l-u tr÷ vÐc t¬ (gäi lµ vÐc t¬ l-u tr÷).
  2. f(i) = c * i gäi lµ hµm ®Þa chØ (address function) §èi víi m¶ng nhiÒu chiÒu viÖc l-u tr÷ còng t-¬ng tù nh- vËy nghÜa lµ vÉn sö dông mét vÐc t¬ l-u tr÷ kÕ tiÕp nh- trªn. a01 a11 . . aij . . anm . . Gi¶ sö mçi phÇn tö trong ma trËn n hµng m cét (m¶ng nhiÒu chiÒu) chiÕm mét tõ m¸y th× ®Þa chØ cña aij sÏ ®-îc tÝnh bëi c«ng thøc tæng qu¸t nh- sau: Loc(aij) = L0 + j * n + i { theo thø tù -u tiªn cét (column major order } Còng víi ma trËn n hµng, m cét c¸ch l-u tr÷ theo thø tù -u tiªn hµng (row major order) th× c«ng thøc tÝnh ®Þa chØ sÏ lµ: Loc(aij) = L0 + i * m + j + Tr-êng hîp cËn d-íi cña chØ sè kh«ng ph¶i lµ 1, nghÜa lµ øng víi aij th× b1 ≤ i ≤ u1, b2 ≤ j ≤ u2 th× ta sÏ cã c«ng thøc tÝnh ®Þa chØ nh- sau: Loc(aij) = L0 + (i - b1) * (u2 - b2 + 1) + (j - b2) v× mçi hµng cã (u2 - b2 + 1) phÇn tö. VÝ dô : XÐt m¶ng ba chiÒu B cã c¸c phÇn tö bijk víi 1 ≤ i ≤ 2; 1 ≤ j ≤ 3; 1 ≤ k ≤ 4; ®-îc l-u tr÷ theo thø tù -u tiªn hµng th× c¸c phÇn tö cña nã sÏ ®-îc s¾p ®Æt kÕ tiÕp nh- sau: b111, b112, b113, b114, b121, b122, b123, b124, b131, b132, b133, b134, b211, b212, b213, b214, b221, b222, b223, b224, b231, b232, b233, b234. C«ng thøc tÝnh ®Þa chØ sÏ lµ : Loc(aijk) = L0 + (i - 1) *12 + (j - 1) * 4 + (k - 1) VD Loc(b223) = L0 + 22. XÐt tr-êng hîp tæng qu¸t víi m¶ng A n chiÒu mµ c¸c phÇn tö lµ : A[s1, s2, . . ., sn] trong ®ã bi ≤ si ≤ ui ( i = 1, 2, . . ., n), øng víi thø tù -u tiªn hµng ta cã: n Loc(A[s1, s2, . . ., sn]) = L0 + ∑ pi(si - bi) i=1 n víi pi = Π (uk - bk +1) k =i + 1 ®Æc biÖt pn = 1. Chó ý :
  3. 1> Khi m¶ng ®-îc l-u tr÷ kÕ tiÕp th× viÖc truy nhËp vµo phÇn tö cña m¶ng ®-îc thùc hiÖn trùc tiÕp dùa vµo ®Þa chØ tÝnh ®-îc nªn tèc ®é nhanh vµ ®ång ®Òu ®èi víi mäi phÇn tö. 2> MÆc dÇu cã rÊt nhiÒu øng dông ë ®ã m¶ng cã thÓ ®-îc sö dông ®Ó thÓ hiÖn mèi quan hÖ vÒ cÊu tróc gi÷a c¸c phÇn tö d÷ liÖu, nh-ng kh«ng ph¶i kh«ng cã nh÷ng tr-êng hîp mµ m¶ng còng lé râ nh÷ng nh-îc ®iÓm cña nã. VÝ dô : XÐt bµi to¸n tÝnh ®a thøc cña x,y ch¼ng h¹n céng hai ®a thøc 2 sau: (3x - xy + y2 + 2y - x) + (x2 + 4xy - y2 +2x) = (4x2 + 3xy + 2y + x) Ta biÕt khi thùc hiÖn céng 2 ®a thøc ta ph¶i ph©n biÖt ®-îc tõng sè h¹ng, ph©n biÖt ®-îc c¸c biÕn, hÖ sè vµ sè mò. §Ó biÓu diÔn ®-îc mét ®a thøc víi 2 biÕn x,y ta cã thÓ dïng ma trËn: hÖ sè cña sè h¹ng xiyj sÏ ®-îc l-u tr÷ ë phÇn tö cã hµng i cét j cña ma trËn. NÕu ta h¹n chÕ kÝch th-íc cña ma trËn lµ n × n th× sè mò cao nhÊt cña x,y chØ xö lý ®-îc víi ®a 2 thøc bËc n-1 th«i. VD : Víi x2 + 4xy - y +2x th× ta sÏ sö dông ma trËn 5 × 5 biÓu diÔn nã sÏ cã d¹ng: 0 0 0 -1 0 1 0 2 4 0 2 0 0 1 0 3 0 0 0 0 4 0 0 0 0 0 1 2 3 4 10.1.2. Cấu trúc lưu trữ mảng trên một số ngôn ngữ lập trình I. GIỚI THIỆU KIỂU DỮ LIỆU “KIỂU MẢNG” TRONG C . Hay như để lưu trữ các từ khóa của ngôn ngữ lập trình C, ta cũng dùng đến một mảng để lưu trữ chúng. Ví dụ 1: Viết chương trình cho phép nhập 2 ma trận a, b có m dòng n cột, thực hiện phép toán cộng hai ma trận a,b và in ma trận kết quả lên màn hình. Trong ví dụ này, ta sẽ sử dụng hàm để làm ngắn gọn hơn chương trình của ta. Ta sẽ viết các hàm: nhập 1 ma trận từ bàn phím, hiển thị ma trận lên màn hình, cộng 2 ma trận.
  4. #include #include void Nhap(int a[][10],int M,int N) { int i,j; for(i=0;i
  5. printf("Ma tran tong C:\n"); InMaTran(c,M,N); getch(); return 0; } Mảng trong C# Array là một cấu trúc dữ liệu cấu tạo bởi một số biến được gọi là những phần tử mảng. Tất cả các phần tử này đều thuộc một kiểu dữ liệu. Bạn có thể truy xuất phần tử thông qua chỉ số (index). Chỉ số bắt đầu bằng zero. Có nhiều loại mảng (array): mảng một chiều, mảng nhiều chiều. Cú pháp : type[ ] array-name; thí dụ: int[] myIntegers; // mảng kiểu số nguyên string[] myString ; // mảng kiểu chuổi chữ Bạn khai báo mảng có chiều dài xác định với từ khoá new như sau: // Create a new array of 32 ints int[] myIntegers = new int[32]; integers[0] = 35;// phần tử đầu tiên có giá trị 35 integers[31] = 432;// phần tử 32 có giá trị 432 Bạn cũng có thể khai báo như sau: int[] integers; integers = new int[32]; string[] myArray = {"first element", "second element", "third element"}; Làm việc với mảng (Working with Arrays)
  6. Ta có thể tìm được chiều dài của mảng sau nhờ vào thuộc tính Length thí dụ sau : int arrayLength = integers.Length Nếu các thành phần của mảng là kiểu định nghĩa trước (predefined types), ta có thể sắp xếp tăng dần vào phương thức gọi là static Array.Sort() method: Array.Sort(myArray); Cuối cùng chúng ta có thể đảo ngược mảng đã có nhờ vào the static Reverse() method: Array.Reverse(myArray); string[] artists = {"Leonardo", "Monet", "Van Gogh", "Klee"}; Array.Sort(artists); Array.Reverse(artists); foreach (string name in artists) { Console.WriteLine(name); } Mảng nhiều chiều (Multidimensional Arrays in C#) Cú pháp : type[,] array-name; Thí dụ muốn khai báo một mảng hai chiều gồm hai hàng ba cột với phần tử kiểu nguyên : int[,] myRectArray = new int[2,3]; Bạn có thể khởi gán mảng xem các ví dụ sau về mảng nhiều chiều: int[,] myRectArray = new int[,]{ {1,2},{3,4},{5,6},{7,8}}; // mảng 4 hàng 2 cột string[,] beatleName = { {"Lennon","John"}, {"McCartney","Paul"}, {"Harrison","George"}, {"Starkey","Richard"} };
  7. chúng ta có thể sử dụng : string[,,] my3DArray; double [, ] matrix = new double[10, 10]; for (int i = 0; i < 10; i++) { for (int j=0; j < 10; j++) matrix[i, j] = 4; } Mảng jagged Một loại thứ 2 của mảng nhiều chiều trong C# là Jagged array. Jagged là một mảng mà mỗi phần tử là một mảng với kích thước khác nhau. Những mảng con này phải đuợc khai báo từng mảng con một. Thí dụ sau đây khai báo một mảng jagged hai chiều nghĩa là hai cặp [], gồm 3 hàng mỗi hàng là một mảng một chiều: int[][] a = new int[3][]; a[0] = new int[4]; a[1] = new int[3]; a[2] = new int[1]; Khi dùng mảng jagged ta nên sử dụng phương thức GetLength() để xác định số lượng cột của mảng. Thí dụ sau nói lên điều này: using System; namespace Wrox.ProCSharp.Basics { class MainEntryPoint { static void Main() { // Declare a two-dimension jagged array of authors' names string[][] novelists = new string[3][]; novelists[0] = new string[] { "Fyodor", "Mikhailovich", "Dostoyevsky"}; novelists[1] = new string[] { "James", "Augustine", "Aloysius", "Joyce"};
  8. novelists[2] = new string[] { "Miguel", "de Cervantes", "Saavedra"}; // Loop through each novelist in the array int i; for (i = 0; i < novelists.GetLength(0); i++) { // Loop through each name for the novelist int j; for (j = 0; j < novelists[i].GetLength(0); j++) { // Display current part of name Console.Write(novelists[i][j] + " "); } // Start a new line for the next novelist Console.Write("\n"); } } } } Kết quả chương trình sau khi chạy: csc AuthorNames.cs Microsoft (R) Visual C# .NET Compiler version 7.00.9466 for Microsoft (R) .NET Framework version 1.0.3705 Copyright (C) Microsoft Corporation 2001. All rights reserved. AuthorNames Fyodor Mikhailovich Dostoyevsky James Augustine Aloysius Joyce Miguel de Cervantes Saavedra 10.2. Danh sách 10.2.1. Khái niệm danh sách tuyến tính Danh s¸ch lµ mét tËp hîp cã thø tù nh-ng bao gåm mét sè biÕn ®éng c¸c phÇn tö (x1, x2, . . ., xn) nÕu n = 0 ta cã mét danh s¸ch rçng. Mét danh s¸ch mµ quan hÖ l©n cËn ®-îc hiÓn thÞ gäi lµ danh s¸ch tuyÕn tÝnh (linear list). VD: VÐc t¬ chÝnh lµ mét tr-êng hîp ®Æc biÖt cña danh s¸ch tuyÕn tÝnh xÐt t¹i mét thêi ®iÓm nµo ®Êy.
  9. Danh s¸ch tuyÕn tÝnh lµ mét danh s¸ch hoÆc rçng (kh«ng cã phÇn tö nµo) hoÆc cã d¹ng (a1, a2, . . ., an) víi ai (1 ≤ i ≤ n) lµ c¸c d÷ liÖu nguyªn tö. Trong danh s¸ch tuyÕn tÝnh lu«n tån t¹i mét phÇn tö ®Çu a1, phÇn tö cuèi an. §èi víi mçi phÇn tö ai bÊt kú víi 1 ≤ i ≤ n - 1 th× cã mét phÇn tö ai+1 gäi lµ phÇn tö sau ai, vµ víi 2 ≤ i ≤ n th× cã mét phÇn tö ai - 1 gäi lµ phÇn tö tr-íc ai. ai ®-îc gäi lµ phÇn tö thø i cña danh s¸ch tuyÕn tÝnh, n ®-îc gäi lµ ®é dµi hoÆc kÝch th-íc cña danh s¸ch. Mçi phÇn tö trong danh s¸ch th-êng lµ mét b¶n ghi ( gåm mét hoÆc nhiÒu tr-êng (fields)) ®ã lµ phÇn th«ng tin nhá nhÊt cã thÓ tham kh¶o. VD: Danh s¸ch sinh viªn trong mét líp lµ mét danh s¸ch tuyÕn tÝnh mµ mçi phÇn tö øng víi mét sinh viªn, nã bao gåm c¸c tr-êng: M· SV (STT), Hä vµ tªn, Ngµy sinh, Quª qu¸n, . . . 10.2.2. C¸c phÐp to¸n thao t¸c trªn danh s¸ch: + PhÐp bæ sung mét phÇn tö vµo trong danh s¸ch (Insert) . + PhÐp lo¹i bá mét phÇn tö trong danh s¸ch (Delete). + PhÐp ghÐp nèi 2 hoÆc nhiÒu danh s¸ch. + PhÐp t¸ch mét danh s¸ch thµnh nhiÒu danh s¸ch. + PhÐp sao chÐp mét danh s¸ch. + PhÐp cËp nhËt (update) danh s¸ch. + PhÐp s¾p xÕp c¸c phÇn tö trong danh s¸ch theo thø tù Ên ®Þnh. + PhÐp t×m kiÕm mét phÇn tö trong danh s¸ch theo gi¸ trÞ Ên ®Þnh cña mét tr-êng nµo ®ã. Trong ®ã phÐp bæ sung vµ phÐp lo¹i bá lµ hai phÐp to¸n th-êng xuyªn ®-îc sö dông trong danh s¸ch. TÖp còng lµ mét tr-êng hîp cña danh s¸ch nã cã kÝch th-íc lín vµ th-êng ®-îc l-u tr÷ ë bé nhí ngoµi. Cßn danh s¸ch nãi chung th-êng ®-îc xö lý ë bé nhí trong. Bé nhí trong ®-îc h×nh dung nh- mét d·y c¸c tõ m¸y(words) cã thø tù, mçi tõ m¸y øng víi mét ®Þa chØ. Mçi tõ m¸y chøa tõ 8 ÷ 64 bits, viÖc tham kh¶o ®Õn néi dung cña nã th«ng qua ®Þa chØ. + C¸ch x¸c ®Þnh ®Þa chØ cña mét phÇn tö trong danh s¸ch: Cã 2 c¸ch x¸c ®Þnh ®Þa chØ: C¸ch 1: Dùa vµo ®Æc t¶ cña d÷ liÖu cÇn t×m . §Þa chØ nµy gäi lµ ®Þa chØ tÝnh ®-îc (hay ®Þa chØ trùc tiÕp). VD: X¸c ®Þnh ®Þa chØ cña c¸c phÇn tö trong vÐc t¬, ma trËn th«ng qua c¸c chØ sè.
  10. C¸ch 2: L-u tr÷ c¸c ®Þa chØ cÇn thiÕt ë trong bé nhí, khi cÇn x¸c ®Þnh sÏ lÊy ë ®ã ra. §Þa chØ nµy ®-îc gäi lµ con trá (pointer) hay mèi nèi (link). L-u tr÷ kÕ tiÕp cña danh s¸ch tuyÕn tÝnh. L-u tr÷ kÕ tiÕp lµ ph¬ng ph¸p l-u tr÷ sö dông m¶ng mét chiÒu lµm cÊu tróc l-u tr÷ cña danh s¸ch tuyÕn tÝnh nghÜa lµ cã thÓ dïng mét vÐc t¬ l-u tr÷ Vi víi 1 ≤ i ≤ n ®Ó l-u tr÷ mét danh s¸ch tuyÕn tÝnh (a1, a2, . . ., an) trong ®ã phÇn tö ai ®-îc chøa ë Vi. ¦u ®iÓm : Tèc ®é truy nhËp nhanh, dÔ thao t¸c trong viÖc bæ sung, lo¹i bá vµ t×m kiÕm phÇn tö trong danh s¸ch. Nh-îc ®iÓm: Do sè phÇn tö trong danh s¸ch tuyÕn tÝnh th-êng biÕn ®éng (kÝch th-íc n thay ®æi) dÉn ®Õn hiÖn t-îng l·ng phÝ bé nhí. MÆt kh¸c nÕu dù tr÷ ®ñ råi thÞ viÖc bæ sung hay lo¹i bá mét phÇn tö trong danh s¸ch mµ kh«ng ph¶i lµ phÇn tö cuèi sÏ ®ßi hái ph¶i dån hoÆc d·n danh s¸ch (nghÜa lµ ph¶i dÞch chuyÓn mét sè phÇn tö ®Ó lÊy chç bæ sung hay tiÕn lªn ®Ó lÊp chç phÇn tö bÞ lo¹i bá) sÏ tèn nhiÒu thêi gian. Nhu cầu xây dựng cấu trúc dữ liệu động Với các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiểu thực, kiểu nguyên, kiểu ký tự ... hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng ... lập trình viên có thể giải quyết hầu hết các bài toán đặt ra. Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này có đặc điểm chung là không thay đổi được kích thước, cấu trúc trong quá trình sống, do vậy thường cứng ngắt, gò bó khiến đôi khi khó diễn tả được thực tế vốn sinh động, phong phú. Các kiểu dữ liệu kể trên được gọi là các kiểu dữ liệu tĩnh. Ví dụ : 1. Trong thực tế, một số đối tượng có thể được định nghĩa đệ qui, ví dụ để mô tả đối tượng "con người" cần thể hiện các thông tin tối thiểu như : Họ tên Số CMND Thông tin về cha, mẹ Ðể biễu diễn một đối tượng có nhiều thành phần thông tin như trên có thể sử dụng kiểu bản ghi. Tuy nhiên, cần lưu ý cha, mẹ của một người cũng là
  11. các đối tượng kiểu NGƯỜI, do vậy về nguyên tắc cần phải có định nghĩa như sau: typedef struct NGUOI{ char Hoten[30]; int So_CMND ; NGUOI Cha,Me; }; Nhưng với khai báo trên, các ngôn ngữ lập trình gặp khó khăn trong việc cài đặt không vượt qua được như xác định kích thước của đối tượng kiểu NGUOI. 2. Một số đối tượng dữ liệu trong chu kỳ sống của nó có thể thay đổi về cấu trúc, độ lớn, như danh sách các học viên trong một lớp học có thể tăng thêm, giảm đi ... Khi đó nếu cố tình dùng những cấu trúc dữ liệu tĩnh đã biết như mảng để biểu diễn những đối tượng đó lập trình viên phải sử dụng những thao tác phức tạp, kém tự nhiên khiến chương trình trở nên khó đọc, do đó khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách có hiệu quả. 3. Một lý do nữa làm cho các kiểu dữ liệu tĩnh không thể đáp ứng được nhu cầu của thực tế là tổng kích thước vùng nhớ dành cho tất cả các biến tĩnh có giới hạn. Khi có nhu cầu dùng nhiều bộ nhớ hơn ta phải sử dụng các cấu trúc dữ liệu động. 4. Cuối cùng, do bản chất của các dữ liệu tĩnh, chúng sẽ chiếm vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình. Tuy nhiên, trong thực tế, có thể xảy ra trường hợp một dữ liệu nào đó chỉ tồn tại nhất thời hay không thường xuyên trong quá trình hoạt động của chương trình. Vì vậy việc dùng các CTDL tĩnh sẽ không cho phép sử dụng hiệu quả bộ nhớ. Do vậy, nhằm đáp ứng nhu cầu thể hiện sát thực bản chất của dữ liệu cũng như xây dựng các thao tác hiệu quả trên dữ liệu, cần phải tìm cách tổ chức kết hợp dữ liệu với những hình thức mới linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống. Các hình thức tổ chức dữ liệu như vậy được gọi là cấu trúc dữ liệu động. Bài sau sẽ giới thiệu về các cấu trúc dữ liệu động và tập trung khảo sát cấu trúc đơn giản nhất thuộc loại này là danh sách liên kết.
  12. Bài 15: Thực hành cài đặt danh sách Stack và Queue Bài 1 Hãy viết một chương trình hoàn chỉnh có menu cho người sử dụng để minh họa các thuật toán sau: 1. Khởi tạo Stack 2. Thêm các phần tử vào Stack 3. Lấy các phần tử ra khỏi Stack 4. Thoát Bài 2. Hãy viết một chương trình hoàn chỉnh có menu cho người sử dụng để minh họa các thuật toán sau: 1. Khởi tạo Queue 2. Thêm các phần tử vào Queue 3. Lấy các phần tử ra khỏi Queue 4. Thoát Bài 3. Dùng Stack để viết chương trình chuyển đổi một số từ hệ cơ số 10 sang hệ cơ số nguyên a (0
  13. Bài 16: Danh sách nối kép (Double Linked List) 16.1. Định nghĩa và nguyên tắc tổ chức DS nối kép Một số ứng dụng đòi hỏi chúng ta phải duyệt danh sách theo cả hai chiều một cách hiệu quả. Chẳng hạn cho phần tử X cần biết ngay phần tử trước X và sau X một cách mau chóng. Trong trường hợp này ta phải dùng hai con trỏ, một con trỏ chỉ đến phần tử đứng sau (next), một con trỏ chỉ đến phần tử đứng trước (previous). Với cách tổ chức này ta có một danh sách liên kết kép. Dạng của một danh sách liên kép như sau: Hình 16.1 Hình ảnh một danh sách liên kết kép Các khai báo cần thiết typedef ... ElementType; //kiểu nội dung của các phần tử trong danh sách typedef struct Node{ ElementType Element; //lưu trữ nội dung phần tử //Hai con trỏ trỏ tới phần tử trước và sau Node* Prev; Node* Next; }; typedef Node* Position; typedef Position DoubleList; Để quản lí một danh sách liên kết kép ta có thể dùng một con trỏ trỏ đến một ô bất kỳ trong cấu trúc. Hoàn toàn tương tự như trong danh sách liên kết đơn đã trình bày trong phần trước, con trỏ để quản lí danh sách liên kết kép có thể là một con trỏ có kiểu giống như kiểu phần tử trong danh sách và nó có thể được cấp phát ô nhớ (tương tự như Header trong danh sách liên kết đơn) hoặc không được cấp phát ô nhớ. Ta cũng có thể xem danh sách liên kết kép như là danh sách liên kết đơn, với một bổ sung duy nhất là có con trỏ previous để nối kết các ô theo chiều ngược lại. Theo quan điểm này thì chúng ta có thể cài đặt các phép toán thêm (insert), xoá (delete) một phần tử hoàn toàn tương tự như trong danh sách liên kết đơn và con trỏ Header cũng cần thiết như trong danh sách liên kết đơn, vì nó chính là vị trí của phần tử đầu tiên trong danh sách. Tuy nhiên, nếu tận dụng khả năng duyệt theo cả hai chiều thì ta không cần phải cấp phát bộ nhớ cho Header và vị trí (position) của một phần tử trong danh sách có thể định nghĩa như sau: Vị trí của phần tử ai là con trỏ trỏ tới ô chứa ai, tức là địa chỉ ô nhớ chứa ai. Nói nôm na, vị trí của ai là ô chứa ai. Theo định nghĩa vị trí như vậy các phép toán trên danh sách liên kết kép sẽ được cài đặt hơi khác với danh sách liên đơn. Trong cách cài đặt này, chúng ta không sử dụng ô đầu mục như danh sách liên kết đơn mà sẽ quản lý danh sách một các trực tiếp (header chỉ ngay đến ô đầu tiên trong danh sách).
  14. 16.2. Các phép toán thao tác trên danh sách nối kép Tạo danh sách liên kết kép rỗng Giả sử DL là con trỏ quản lí danh sách liên kết kép thì khi khởi tạo danh sách rỗng ta cho con trỏ này trỏ NULL (không cấp phát ô nhớ cho DL), tức là gán DL=NULL. void MakeNull_List (DoubleList *DL){ (*DL)= NULL; } Kiểm tra danh sách liên kết kép rỗng Rõ ràng, danh sách liên kết kép rỗng khi và chỉ khi chỉ điểm đầu danh sách không trỏ tới một ô xác định nào cả. Do đó ta sẽ kiểm tra DL = NULL. int Empty (DoubleList DL){ return (DL==NULL); } Xóa một phần tử ra khỏi danh sách liên kết kép Để xoá một phần tử tại vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta phải chú ý đến các trường hợp sau: - Danh sách rỗng, tức là DL=NULL: chương trình con dừng. - Trường hợp danh sách khác rỗng, tức là DL!=NULL, ta phải phân biệt hai trường hợp Ô bị xoá không phải là ô được trỏ bởi DL, ta chỉ cần cập nhật lại các con trỏ để nối kết ô trước p với ô sau p, các thao tác cần thiết là (xem hình II.16): Nếu (p->previous!=NULL) thì p->previous->next=p->next; Nếu (p->next!=NULL) thì p->next->previous=p->previous; Xoá ô đang được trỏ bởi DL, tức là p=DL: ngoài việc cập nhật lại các con trỏ để nối kết các ô trước và sau p ta còn phải cập nhật lại DL, ta có thể cho DL trỏ đến phần tử trước nó (DL = p->Previous) hoặc đến phần tử sau nó (DL = p->Next) tuỳ theo phần tử nào có mặt trong danh sách. Đặc biệt, nếu danh sách chỉ có một phần tử tức là p->Next=NULL và p->Previous=NULL thì DL=NULL.
  15. Hình 16.2 Xóa phần tử tại vị trí p void Delete_List (Position p, DoubleList *DL){ if (*DL == NULL) printf(”Danh sach rong”); else{ if (p==*DL) (*DL)=(*DL)->Next; //Xóa phần tử đầu tiên của danh sách nên phải thay đổi DL else p->Previous->Next=p->Next; if (p->Next!=NULL) p->Next->Previous=p->Previous; free(p); } } Thêm phần tử vào danh sách liên kết kép Để thêm một phần tử x vào vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta cũng cần phân biệt mấy trường hợp sau: Danh sách rỗng, tức là DL = NULL: trong trường hợp này ta không quan tâm đến giá trị của p. Để thêm một phần tử, ta chỉ cần cấp phát ô nhớ cho nó, gán giá trị x vào trường Element của ô nhớ này và cho hai con trỏ previous, next trỏ tới NULL còn DL trỏ vào ô nhớ này, các thao tác trên có thể viết như sau: DL=(Node*)malloc(sizeof(Node)); DL->Element = x; DL->Previous=NULL; DL->Next =NULL; Nếu DL!=NULL, sau khi thêm phần tử x vào vị trí p ta có kết quả như hình 16.3
  16. Hình 16.3: Danh sách trước khi thêm phần tử x Hình 16.4: Danh sách sau khi thêm phần tử x vào tại vị trí p (phần tử tại vị trí p cũ trở thành phần tử "sau" của x) Lưu ý: các kí hiệu p, p->Next, p->Previous trong hình 16.4 để chỉ các ô trước khi thêm phần tử x, tức là nó chỉ các ô trong hình 16.3. Trong trường hợp p=DL, ta có thể cập nhật lại DL để DL trỏ tới ô mới thêm vào hoặc để nó trỏ đến ô tại vị trí p cũ như nó đang trỏ cũng chỉ là sự lựa chọn trong chi tiết cài đặt. void Insert_List (ElementType X,Position p, DoubleList *DL){ if (*DL == NULL){ (*DL)=(Node*)malloc(sizeof(Node)); (*DL)->Element = X; (*DL)->Previous =NULL; (*DL)->Next =NULL; } else{ Position temp; temp=(Node*)malloc(sizeof(Node)); temp->Element=X;
  17. temp->Next=p; temp->Previous=p->Previous; if (p->Previous!=NULL) p->Previous->Next=temp; p->Previous=temp; } }
  18. Bài 17: Thực hành cài đặt DANH SÁCH LIÊN KẾT KÉP Viết chương trình lưu trữ một danh sách các số nguyên, sắp xếp danh sách theo thứ tự (tăng hoặc giảm), trộn 2 danh sách có thứ tự để được một danh sách mới có thứ tự. Yêu cầu chi tiết: 1. Viết các khai báo cần thiết để cài đặt một danh sách các số nguyên. 2. Viết thủ tục khởi tạo một danh sách rỗng. 3. Viết hàm kiểm tra danh sách rỗng. 4. Viết thủ tục nhập một danh sách. 5. Viết thủ tục hiển thị danh sách ra màn hình. 6. Viết thủ tục sắp xếp danh sách theo thứ tự (tăng hoặc giảm). 7. Xen một phần tử mới x vào danh sách sau cho danh sách mới vẫn bảo đảm thứ tự. 8. Xóa một phần tử x ra khỏi danh sách sao cho danh sách mới vẫn bảo đảm thứ tự. 9. viết thủ tục trộn 2 danh sách đã có thứ tự thành một danh sách mới sao cho danh sách mới vẫn bảo đảm thứ tự. Viết chương trình nhập vào một danh sách các số nguyên và thực hiện các yêu cầu sau: • Hiển thị danh sách vừa nhập. • Sắp xếp danh sách theo thứ tự. Hiển thị danh sách sau khi sắp xếp. • Xen một phần tử mới vào danh sách. Hiển thị danh sách mới sau khi xen. • Xóa một phần tử khỏi danh sách. Hiển thị danh sách mới sau khi xóa. • Nhập 2 danh sách, sắp xếp 2 danh sách theo thứ tự, sau đó trộn 2 danh sách này để được một danh sách mới cũng có thứ tự. Hiển thị danh sách mới ra màn hình để kiểm tra.
  19. Bài 18: Kiểu dữ liệu trừu tượng tập hợp và hàm băm 18.1. Tập hợp 18.1.1. Khái niệm Tập hợp là một khái niệm cơ bản trong toán học. Tập hợp được dùng để mô hình hoá hay biểu diễn một nhóm bất kỳ các đối tượng trong thế giới thực cho nên nó đóng vai trò rất quan trọng trong mô hình hoá cũng như trong thiết kế các giải thuật. Khái niệm tập hợp cũng như trong toán học, đó là sự tập hợp các thành viên (members) hoặc phần tử (elements). Tất cả các phần tử của tập hợp là khác nhau. Tập hợp có thể có thứ tự hoặc không có thứ tự, tức là, có thể có quan hệ thứ tự xác định trên các phần tử của tập hợp hoặc không. Tuy nhiên, trong chương này, chúng ta giả sử rằng các phần tử của tập hợp có thứ tự tuyến tính, tức là, trên tập hợp S có quan hệ < và = thoả mản hai tính chất: Với mọi a,b ≍ S thì a
  20. • Thủ tục ASSIGN(A,B) gán A cho B ( tức là B:=A ) • Hàm MIN(A) cho phần tử bé nhất trong tập A • Hàm EQUAL(A,B) cho kết quả TRUE nếu A=B ngược lại cho kết quả FALSE 1. Cài đặt tập hợp bằng vector Bit Hiệu quả của một cách cài đặt tập hợp cụ thể phụ thuộc vào các phép toán và kích thước tập hợp. Hiệu quả này cũng sẽ phụ thuộc vào tần suất sử dụng các phép toán trên tập hợp. Chẳng hạn nếu chúng ta thường xuyên sử dụng phép thêm vào và loại bỏ các phần tử trong tập hợp thì chúng ta sẽ tìm cách cài đặt hiệu quả cho các phép toán này. Còn nếu phép tìm kiếm một phần tử xảy ra thường xuyên thì ta có thể phải tìm cách cài đặt phù hợp để có hiệu quả tốt nhất. Ở đây ta xét một trường hợp đơn giản là khi toàn thể tập hợp của chúng ta là tập hợp con của một tập hợp các số nguyên nằm trong phạm vi nhỏ từ 1.. n chẳng hạn thì chúng ta có thể dùng một mảng kiểu Boolean có n phần tử để cài đặt tập hợp (ta gọi là vectơ bít), bằng cách cho phần tử thứ i của mảng này giá trị TRUE nếu i thuộc tập hợp hoặc cho mảng lưu kiểu 0-1. Nếu nội dung phần tử trong mảng tại vị trí i là 1 nghĩa là i tồn tại trong tập hợp và ngược lại, nội dung là 0 nghĩa là phần tử i đó không tồn tại trong tập hợp. Ví dụ: Giả sử các phần tử của tập hợp được lấy trong các số nguyên từ 1 đến 10 thì mỗi tập hợp được biểu diễn bởi một mảng một chiều có 10 phần tử với các giá trị phần tử thuộc kiểu logic. Chẳng hạn tập hợp A={1,3,5,8} được biểu diễn trong mảng có 10 phần tử như sau: Cách biểu diễn này chỉ thích hợp trong điều kiện là mọi thành viên của tất cả các tập hợp đang xét phải có giá trị nguyên hoặc có thể đặt tương ứng duy nhất với số nguyên nằm trong một phạm vi nhỏ. Có thể dễ dàng nhận thấy khai báo cài đặt như sau const maxlength = 100; // giá trị phần tử lớn nhất trong tập hợp số nguyên không âm typedef int SET [maxlength]; Tạo một tập hợp rỗng Để tạo một tập hợp rỗng ta cần đặt tất cả các nội dung trong tập hợp từ vị trí 0 đến vị trí maxlength đều bằng 0. Câu lệnh được viết như sau : void makenull(SET a)
Đồng bộ tài khoản