Chapter 4: Cấu trúc dữ liệu động

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

(cid:67)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:52)

u (Variant) BiBiếến dn dữữ liliệệu (Variant)

(cid:67)(cid:67)ấấ(cid:117)(cid:32)(cid:116)(cid:114)(cid:117)(cid:32)(cid:116)(cid:114)(cid:250)(cid:250)(cid:99)(cid:32)(cid:100)(cid:99)(cid:32)(cid:100)ữữ (cid:108)(cid:105)(cid:108)(cid:105)ệệ(cid:117)(cid:32)(cid:273)(cid:117)(cid:32)(cid:273)ộộ(cid:110)(cid:103)(cid:110)(cid:103) (cid:67)ấ(cid:117)(cid:32)(cid:116)(cid:114)(cid:250)(cid:99)(cid:32)(cid:100)ữ (cid:108)(cid:105)ệ(cid:117)(cid:32)(cid:273)ộ(cid:110)(cid:103)

i dung NNộội dung Nội dung (cid:61607) Khai báo tường minh và được cấp phát vùng nhớ ngay khi khai báo, vùng nhớ được cấp cho biến tĩnh sẽ không thể thu hồi được nếu biến còn trong phạm vi hoạt động

1 Biến và biến động Ví dụ: int X; (cid:61664) X (2 bytes)

(cid:61607) Chúng có thể chiếm dụng bộ nhớ. (cid:61607) Một số thao tác tiến hành thiếu tự nhiên trên các đối tượng tĩnh:

float Y; (cid:61664) Y (4 bytes) 2 Danh sách liên kết (cid:61607) Nhược điểm 3 Ngăn xếp - Stack

Chèn và xóa trong mảng.

3/11/2010

www.lhu.edu.vn

4 Hàng đợi - Queue

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

(cid:61607) Ví dụ:

ng (Dynamic Variant) BiBiếến đn độộng (Dynamic Variant)

(cid:61607) Tính chất của biến động:

(cid:61607) Thuộc một kiểu dữ liệu nào đó, không được khai báo tường minh (cid:61664) không có tên (cid:61607) Được cấp phát vùng nhớ và truy xuất thông qua một biến con trỏ

(cid:61607) Có thể thay đổi kích thước hoặc thu hồi (hủy bỏ) vùng nhớ được cấp phát khi chương trình đang hoạt động (cid:61607) Việc tạo ra biến động (cấp phát vùng nhớ cho nó ) và xóa bỏ nó được thực hiện bởi các thủ tục đã có sẵn

int X=10, P; // khai báo 2 biến tĩnh X, P (con trỏ) P=&X; // Cho P trỏ đến X printf(“\nĐịa chỉ của biến X là %x”,P); printf(“\nX=%d”,P); // hoặc printf(“X=%d”,X); in giá trị của X P=(int)malloc(sizeof(int)); // tạo biến động cho P trỏ đến P=X; //gán giá trị cho biến động bằng giá trị của X printf(“\nĐịa chỉ của biến động là %x”,P); printf(“\nGiá trị của Biến động=%d”,*P); free(P); //hủy (thu hồi vùng nhớ) biến động do P trỏ đến

3/11/2010

www.lhu.edu.vn

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

TTạạo mo mộột bi t biếến đn độộngng TTạạo mo mộột bi t biếến đn độộngng

(cid:61607) Dùng hàm có sẵn trong thư viện hay

(cid:61607) Dùng toán tử new (trong C++)

= new [(Số_phần_tử)]; Công dụng như hàm malloc nhưng tự động thực hiện hàm sizeof(tênkiểu).

(cid:61607) Ví dụ:

(cid:61607) void *malloc ( size ); Cấp phát vùng nhớ có kích thước size bytes và trả về địa chỉ của vùng nhớ đó. (cid:61607) void *calloc ( n, size ); Cấp phát vùng nhớ cho n phần tử, mỗi phần tử có kích thước size bytes và trả về địa chỉ của vùng nhớ đó.

3/11/2010

www.lhu.edu.vn

(cid:61607) void * realloc (void *ptr, size_t nbyte): Thay đổi kích thước vùng nhớ đã cấp phát trước đó cho biến con trỏ ptr là n byte, đồng thời chép dữ liệu vào vùng nhớ mới. int *p1, *p2, *p3; // khai báo 3 biến con trỏ p1 = (int *) malloc( sizeof(int) ); //tạo biến động p1 = (int*) realloc (p1, 4); //thay đổi kích thước biến p2 = (int*) calloc(10, 2);//tạo 10 biến động p2 = new int;

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

HHủủy my mộột bi t biếến đn độộngng Truy xuấất bi Truy xu t biếến đn độộngng

(cid:61607) Dùng hàm

free(Tên_con_trỏ); (cid:61607) Dùng toán tử delete (trong C++) delete Tên_con_trỏ ;

(cid:61607) Tên_con_trỏ ~ Địa chỉ của biến động (cid:61607) *Tên_con_trỏ ~ Giá trị của biến động (cid:61607) Ví dụ

Lưu ý: không thể dùng hàm free để hủy một biến được cấp phát bằng toán tử new (cid:61607) Ví dụ:

int *p1, *p2; // khai báo 2 biến con trỏ p1 = (int *) malloc( sizeof(int) ); //tạo biến động kiểu int p2 = new float; // tạo biến động kiểu float free(p1); //hủy biến động do p1 trỏ tới delete p2; //hủy biến động do p2 trỏ tới

3/11/2010

www.lhu.edu.vn

int *P; P=(int*) malloc(sizeof(int));// tạo biến động *P=100; //gán giá trị cho biến động print(“\nĐịa chỉ của biến động là %x”,P); print(“\nGiá trị của biến động là %d”,*P);

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

HHììnhnh ảảnh mnh mộột danh s t danh sáách liên k ch liên kếếtt Danh sáách liên k Danh s ch liên kếếtt

(cid:61607) Danh sách liên kết là 1 tập hợp các phần tử cùng kiểu, giữa 2 phần tử trong danh sách có một mối liên kết

(cid:61607) Cho trước kiểu dữ liệu T, Kiểu xâu liên kết

(cid:61607) Cấu trúc một node trong danh sách gồm

(cid:61607) Thành phần DATA: chứa dữ liệu kiểu T nào đó (cid:61607) Thành phần NEXT: là một con trỏ tới node kế tiếp

Tx = < Vx, Ox> trong đó: (cid:61607) Vx = { Tập hợp có thứ tự gồm các biến động kiểu T } (cid:61607) Ox = {Tạo danh sách; Liệt kê các phần tử trong danh

3/11/2010

www.lhu.edu.vn

sách; Thêm; Hủy; Tìm; Sắp xếp } DATA NEXT

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

Danh sáách liên k Danh s ch liên kếết đơn t đơn (xâu(xâu đơn ) (Simple List) đơn) (Simple List) VVíí ddụụ

typedef struct Node {

(cid:61607) Khai báo xâu liên kết lưu trữ các hệ số của một đa thức Khai báo kiểu 1 nút trong xâu liên kết đơn:

KiểuT Data; struct Node *Next;

typedef struct Node NodeType; struct Node {

KiểuT Data; NodeType *Next;

} NodeType;

} ;

typedef struct float Heso; { int Bac;

} Hangtu; typedef struct Node { NodeType *Head; Khai báo con trỏ đầu xâu: Hangtu Data; NodeType *Next ; /* Con trỏ liên kết */ Có thể khai báo kiểu con trỏ đến kiểu nút :

3/11/2010

www.lhu.edu.vn

typedef NodeType *NodePtr; NodePtr Head; } NodeType; typedef NodeType *NodePtr; NodePtr Head; /* Con trỏ đầu xâu */

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c trên xâu đơn c thao táác trên xâu đơn CCáác thao t c trên xâu đơn c thao táác trên xâu đơn

(cid:61607) Khởi tạo 1 xâu mới rỗng: Head = Tail =NULL; (cid:61607) Kiểm tra xâu rỗng: if (Head == NULL)... (cid:61607)

Tạo Nút chứa giá trị kiểu T: Thuật toán: Trả về địa chỉ biến động chứa giá trị X b1: Tạo biến động kiểu T và lưu địa chỉ vào biến con trỏ P b2: Nếu không tạo được thì báo lỗi và kết thúc ngược lại chuyển sang b3

(cid:61607) Khởi tạo xâu rỗng (cid:61607) Kiểm tra xâu rỗng (cid:61607) Tạo nút mới (cid:61607) Chèn nút vào xâu (cid:61607) Tạo xâu (cid:61607) Hủy nút trên xâu (cid:61607) Tìm kiếm giá trị (cid:61607) Duyệt xâu (cid:61607) Sắp xếp dữ liệu

3/11/2010

www.lhu.edu.vn

b3: Lưu giá trị X vào phần dữ liệu của nút b4: Gán phần Liên kết của Nút giá trị NULL b5: return P;

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn c trên xâu đơn _ T_ Tạạo no núút cht chứứa ga giá trị iá trị XX CCáác thao t c thao táác trên xâu đơn o xâu c trên xâu đơn _ C_ Chèhèn nn núút vt vàào xâu

(cid:61607) Cài đặt

(cid:61607) Chèn nút mới vào đầu xâu:

void InsertFirst(NodePtr P, NodePtr &Head, NodePtr &Tail) { P->Next = Head;

NodePtr CreateNode( KiểuT x) { NodePtr P;

if (Head == NULL) Tail = P; Head = P;

}

3/11/2010

www.lhu.edu.vn

P = (NodePtr) malloc(sizeof(NodeType)); if (p == NULL) {printf(“Khong du bo nho”); exit(1);} P->Data = x; P->Next = NULL; return P; }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn o xâu c trên xâu đơn _ C_ Chèhèn nn núút vt vàào xâu CCáác thao t c thao táác trên xâu đơn o xâu c trên xâu đơn _ C_ Chèhèn nn núút vt vàào xâu

(cid:61607) Chèn nút mới vào sau nút trỏ bởi Q:

(cid:61607) Chèn nút mới vào cuối xâu:

void InsertLast(NodePtr P, NodePtr &Head, NodePtr &Tail) {

Head = P; Tail = Head;

}

void InsertAfter(NodePtr P, NodePtr Q, NodePtr &Tail) { If (Q != NULL) {

NodePtr Last ; If (Head == NULL) { else {

Tail->Next = P; Tail = P;

}

3/11/2010

www.lhu.edu.vn

P->Next = Q->Next; Q->Next = P; if (Q==Tail) Tail = P; } }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

void InsertListOrder(NodePtr G,NodePtr &Head,NodePtr &Tail) {

(cid:61607) Chèn nút vào xâu theo thứ tự tăng của node (cid:61607) Thuật toán:

NodePtr P, Q; P = Head; while (P != NULL) {

Bước 1: Tìm vị trí cần chèn (Ghi nhận nút đứng

if (P->Data >= G->Data) break; Q = P; P = Q->Next;

trước vị trí cần chèn)

/*InsertFirst(G, Head, Tail)*/

Bước 2: Nếu vị trí cần chèn ở đầu xâu thì chèn

} if (P == Head) { G->Next = Head;

Head = G;

vào đầu danh sách

/*InsertAfter(G,Q, Tail);*/

Bước 3: Ngược lại thì chèn vào sau nút tìm được

} else { G->Next = Q->Next;

Q->Next = G;

}

3/11/2010

www.lhu.edu.vn

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn o xâu c trên xâu đơn _ T_ Tạạo xâu CCáác thao t c thao táác trên xâu đơn trong xâu c trên xâu đơn _ T_ Tììm phm phầần tn tửử trong xâu

(cid:61607)

Tạo một Danh sách liên kết: void CreateList (NodePtr &Head, NodePtr &Tail) { Head = NULL; do {

(cid:61607) Thuật toán: Áp dụng thuật toán tìm kiếm tuyến tính. Sử dụng 1 con trỏ phụ P để lần lượt trỏ đến các phần tử trong xâu. b1: Cho P trỏ phần tử đầu xâu: P = Head; b2: Trong khi chưa hết danh sách (P != NULL)

Nhập gía trị mới X Nếu (không nhập X) thì break; Tạo Nút chứa X Chèn Nút vào xâu

Nếu P->Data == X thì báo tìm thấy và kết thúc ngược lại thì chuyển sang phần tử kế tiếp (P = P->Next)

} while (1);

b3: Báo không tìm thấy

3/11/2010

www.lhu.edu.vn

}

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn trong xâu c trên xâu đơn _ T_ Tììm phm phầần tn tửử trong xâu CCáác thao t c thao táác trên xâu đơn t trong xâu c trên xâu đơn _ H_ Hủủy ny núút trong xâu

(cid:61607) Hủy nút đầu xâu

NodePtr Search(KiểuT X, NodePtr Head) { NodePtr P; P = Head; while (P != NULL)

void DeleteFirst(NodePtr &Head, NodePtr &Tail) { NodePtr P ;

if (P->Data == X) return P; else P = P->Next ; return NULL;// Không tìm thấy

if (Head != NULL) P = Head; Head = P->Next; { if (Head == NULL) Tail = NULL; free(P);

}

3/11/2010

www.lhu.edu.vn

} }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn t trong xâu c trên xâu đơn _ H_ Hủủy ny núút trong xâu CCáác thao t c thao táác trên xâu đơn y xâu c trên xâu đơn _ H_ Hủủy xâu

(cid:61607) Hủy nút sau nút trỏ bởi Q (cid:61607) Thuật toán : Bước 1: Trong khi (Danh sách chưa hết) thực hiện B11:

void DeleteAfter( NodePtr Q, NodePtr &Tail) { NodePtr P;

if ( Q != NULL) {

P = Q->Next; if (P != NULL) {

if (P == Tail) Tail = Q;

Q->Next = P->Next; free(P); //delete P;

p = Head; Head:=Head->pNext; // p trỏ tới phần tử kế B12: Hủy p;

}

3/11/2010

www.lhu.edu.vn

Bước 2: Tail = NULL; //Bảo đảm tính nhất quán khi xâu rỗng

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn trong xâu c trên xâu đơn _ T_ Tììm phm phầần tn tửử trong xâu CCáác thao t c thao táác trên xâu đơn t xâu c trên xâu đơn _ D_ Duyuyệệt xâu

void RemoveList(NodePtr &Head, NodePtr &Tail) { NodePtr p;

while (Head!= NULL) {

p = Head; Head = p->Next; delete p;

void TraverseList(NodePtr Head) { NodePtr P, Q; P = Head; while (P != NULL) Q = P; { P = Q->Next; Xu_Ly_Nut(Q);

} Tail = NULL;

}

3/11/2010

www.lhu.edu.vn

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên xâu đơn p xâu c trên xâu đơn __ SSắắp xp xếếp xâu CCáác thao t c thao táác trên xâu đơn p xâu c trên xâu đơn __ SSắắp xp xếếp xâu

(cid:61607) Ý tưởng: Tạo xâu mới có thứ tự từ xâu cũ

(đồng thời hủy xâu cũ)

(cid:61607) Thuật toán:

3/11/2010

www.lhu.edu.vn

Void SapXep(NodePtr &Head, NodePtr & Tail) { NodePtr H,T, P; H = T = NULL; while (Head != NULL) { (cid:61607) B1: Khởi tạo xâu mới Result rỗng; (cid:61607) B2: Tách phần tử đầu xâu cũ ra khỏi danh sách (cid:61607) B3: Chèn phần tử đó vào xâu Result theo đúng thứ P = Head; Head = P->Next; P->Next = NULL; InsertListOrder(P,H,T); tự sắp xếp. (cid:61607) B5: Lặp lại bước 2 trong khi xâu cũ chưa rỗng. } Head = H; Tail = T; }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

p _ Stack Ngăn xếếp _ Stack Ngăn x CCáác thao t c thao táác trên Stack ( ng xâu đơn)) c trên Stack (dùdùng xâu đơn

(cid:61607) Ngăn xếp thường được sử dụng để lưu trữ dữ liệu tạm thời trong quá trình chờ xử lý theo nguyên tắc: vào sau ra trước (Last In First Out - LIFO) (cid:61607) Khai báo Cấu trúc dữ liệu (dùng xâu đơn)

(cid:61607) Tạo Stack Rỗng: Stack = NULL; (cid:61607) Kiểm tra Ngăn xếp Rỗng: if (Stack == NULL).. (cid:61607) Thêm 1 phần tử X vào đầu Stack: void Push(DataType X , StackPtr &Stack ) {

typedef <Định nghĩa kiểu T>; typedef struct Node {

T Data; struct Node *Next; //Con trỏ tới nút kế

} NodeType; typedef NodeType *StackPtr;

StackPtr Stack;

3/11/2010

www.lhu.edu.vn

NodePtr P; P = CreateNode(x); P->Next = Stack; /*InsertFirst(P, Stack);*/ Stack = P; (cid:61607) Khai báo con trỏ đầu Stack }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên Stack ( ng xâu đơn)) c trên Stack (dùdùng xâu đơn p _ Stack Ngăn xếếp _ Stack Ngăn x

(cid:61607) Lấy phần tử ở đỉnh Stack

(cid:61607) Khai báo Cấu trúc dữ liệu (dùng mảng)

/*Kích thước Stack*/ (cid:61607) #define MaxSize 100 (cid:61607) typedef <Định nghiã kiểu T > KieuT Pop(StackPtr &Stack) { DataType x;

(cid:61607) Khai báo kiểu mảng:

if (Stack!=NULL) { (cid:61607) typedef KiểuT StackArray[MaxSize];

(cid:61607) Khai báo một Stack: (cid:61607) StackArray Stack;

3/11/2010

www.lhu.edu.vn

int top; //chỉ mục phần tử đầu Stack x = (Stack)->Data; /*Xoa nut dau*/ P = Stack; Stack = P->Next; free(P); return x; } }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên Stack ( c trên Stack (dùdùng mng mảảng)ng) CCáác thao t c thao táác trên Stack ( c trên Stack (dùdùng mng mảảng)ng)

(cid:61607) Lấy phần tử ở đỉnh Stack

top = -1 if (top == -1)... if(top == MaxSize-1)...

KieuT Pop(StackArray Stack, int &top) {

(cid:61607) Khởi tạo 1 Stack rỗng: (cid:61607) Kiểm tra ngăn xếp rỗng: (cid:61607) Kiểm tra ngăn xếp đầy: (cid:61607)

Thêm 1 phần tử có nội dung x vào đầu Stack: void Push(KieuT x, StackArray Stack, int &top) {

KieuT Item; if (top != -1) {

Item = Stack[top]; top--; return Item;

top++; Stack[top]= x;

}

if (top < MaxSize-1) { }

}

3/11/2010

www.lhu.edu.vn

}

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

a Stack ỨỨng dng dụụng cng củủa Stack i _ Queue HàHàng đng đợợi _ Queue

(cid:61607) Chuyển đổi các hệ thống số

(cid:61607) Thập phân (cid:61664) nhị phân (cid:61607) Nhị phân (cid:61664) thập phân (cid:61607) ....

(cid:61607) Xử lý biểu thức hậu tố

(cid:61607) Loại danh sách này có hành vi giống như việc xếp hàng chờ mua vé, với qui tắc Đến trước - Mua trước. (First in First Out - FIFO) Ví dụ: Bộ đệm bàn phím, tổ chức công việc chờ in trong Print Manager của Windows (cid:61607) Hàng đợi là một kiểu danh sách đặc biệt có

(cid:61607) Chuyển đổi biểu thức ngoặc toàn phần sang biểu (cid:61607) Các thao tác chèn thêm dữ liệu đều thực hiện ở cuối danh sách ... (cid:61607) Các thao tác lấy dữ liệu được thực hiện ở đầu danh

(cid:61607)

3/11/2010

www.lhu.edu.vn

sách. thức tiền tố, trung tố, hậu tố (cid:61607) Ước lượng giá trị các biểu thức (cid:61607) ...

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

i _ Queue HàHàng đng đợợi _ Queue CCáác thao t c thao táác trên Queue ( ng xâu đơn)) c trên Queue (dùdùng xâu đơn

(cid:61607) Khai báo Cấu trúc dữ liệu (dùng xâu đơn)

<Định nghĩa kiểu T>; (cid:61607) Khởi tạo hàng đợi rỗng: Head = NULL; Tail = NULL; (cid:61607) Kiểm tra hàng đợi rỗng: if (Head == NULL)... (cid:61607) Chèn dữ liệu X vào cuối hàng đợi:

void Push( KieuT x, QueuePtr &Head, QueuePtr &Tail ) { QueuePtr P; typedef typedef struct Node T Data; { struct Node *Next; //Con trỏ tới nút kế

} } NodeType; typedef NodeType *QueuePtr; P = CreateNode(x); if (Head == NULL){ Head = P; Tail = Head; else { Tail->Next = P; Tail = P; }

(cid:61607) Khai báo con trỏ

3/11/2010

www.lhu.edu.vn

} QueuePtr Head, Tail;

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CCáác thao t c thao táác trên Queue ( ng xâu đơn)) c trên Queue (dùdùng xâu đơn CàCài đi đặặt Queue d t Queue dùùng mng mảảngng

Head

Tail

(cid:61607) (cid:61607) Sử dụng kỹ thuật xác định chỉ số vòng tròn để định vị trí đầu và cuối hàng đợi.

Lấy dữ liệu từ đầu hàng đợi KieuT Pop( QueuePtr &Head, QueuePtr &Tail) { QueuePtr P; KieuT x; if (Head != NULL) { A C E B /* DeleteFirst(Head);*/ D (cid:61607) Head là vị trí phần tử đầu hàng đợi. Tail là vị trí phần tử

Vị trí đầu mới = (Head + 1) mod Maxsize Vị trí cuối mới = (Tail + 1) mod Maxsize

x = Head->Data; P = Head; Head = P->Next; free(P); If (Head == NULL) Tail = NULL;

3/11/2010

www.lhu.edu.vn

} return x; cuối hàng đợi (cid:61607) Hàng đợi rỗng: Head = Tail (cid:61607) (cid:61607) (cid:61607) Hàng đợi đầy: Vị trí cuối mới = Head }

Chương 4 C4 Cấấu tru trúúc dc dữữ liliệệu đu độộngng Chương

CàCài đi đặặt Queue d t Queue dùùng mng mảảngng CCáác thao t c thao táác trên Queue ( c trên Queue (dùdùng mng mảảng)ng)

(cid:61607) Khởi Tạo Queue rỗng:

(cid:61607) Khai báo kích thước Queue

void CreateQ(QueueType &queue) { (cid:61607) #define MaxSize 100 (cid:61607) queue.Head = 0; queue.Tail = 0; } typedef /* khai báo kiểu T*/ (cid:61607) Khai báo cấu trúc Queue

(cid:61607) Kiểm tra hàng đợi rỗng: Head == Tail

3/11/2010

www.lhu.edu.vn

typedef struct { int EmptyQ(QueueType queue ) { int Head, Tail; KiểuT Node[MaxSize] ; return (queue.Head == queue.Tail ? 1 : 0)); } } QueueType; QueueType Queue ;