ấ ử ụ

ớ ế

ữ ệ ớ ấ

ố

ợ

ộ ớ ố ể ớ đ  ho t

ỉ

ế Phương  hư ng  gi

ộ ấ ấ ộ

CHƯƠNG VIII DANH SÁCH MÓC N IỐ ả ể ử Ta  thương  s   d ng  m ng  c u  trúc  đ   x   lý  ậ đúng  ộ v i  nhóm  d   li u.  Đây  là  m t  cách  ti p  c n  ầ ố t trế ư c chính xác s  các c u trúc c n có.  khi ta bi ẽ Tuy  nhiên,  khi  con  s   này  không  rõ  ràng,  mãng  s   ấ ả đư c  c p  phát  ở tr   nên  khá  t n  kém  vì  chúng  ph i  đư c ợ đăng ký  ủ ộ ố ạ đ ng. B  nh  này  đ  b  nh   ả ụ ứ ẽ và  s   không  dành  cho  nh ng  tác  v   khác  ngay  c   ầ ử ả ỏ ộ  m ng.  khi ta ch  dùng m t sô nh  các ph n t ề ấ đ   này  là  ả ớ i  quy t  cho  v n  ớ ớ cho phép c p phát b  nh  cho m t c u trúc m i khi  ầ c n thi

ế t.

ệ đi u  này  thông  qua  cáhc

malloc() và calloc()

ự ộ ộ C  cho  phép  ta  th c  hi n  ằ ấ c p phát b  nh ề ớ đ ng b ng:

ợ

ấ ấ

ế ấ ộ ể ố ế ấ ả ậ đ  n i k t t ầ ớ ạ t c  các c u trúc l

ầ ử ể ế ố đ   k t  n i  các  ph n  t

ế ạ ấ Nhưng  các  c u  trúc  n u  ẽ ế đư c  c p  pháp  xong  s   ẽ đư c ợ ằ ả không có đ m báo nào r ng các c u trúc s   ề ế ặ đó  đi u  c n  đ t  liên  ti p  nhau  trong  b   nh .  Do  ỹ thi i  t là k  thu t  ớ v i nhau. Phương  cách  thông  d ng ụ đó l i là dùng danh sách liên k t (Linked list)

I. Danh sách liên k t ế đơn: ị 1. Đ nh nghĩa

ấ

Cú pháp: ể struct   {

ầ ử ể ủ

ấ

ế ầ ử  ; ể struct  *

ụ ị ế đ  ể

ứ pointer tr  ỏ đ n ph n c u trúc ti p theo trong  Danh sách> } ộ Ví d : Đ nh nghĩa m t danh sách liên k t  ố ch a các s  nguyên.

struct  Point { int info;

struct Point *Next;

};

ế ấ 2. Các phép toán trên danh sách liên k tế ỏ ớ ớ a. C p phát bô nh  cho bi n con tr  m i

Cú pháp:

Point_New = (struct Point_Name *) malloc

(sizeof(struct Point_Name)

Ví d :ụ

typedef struct Point POINT; POINT Head, Last, p; CreatNode() {

p=(POINT *) malloc (POINT) if (Head==(POINT* ) NULL)

Head=Last=p;

else {

Last=Head;

while (Last­>Next!= (POINT*) NULL) Last=Last­>Next; Last­>Next=p; Last=p;

} printf(“\nInput information for Node”); scanf(“%d”, p­>.info); Last­>Next=(POINT *) NULL; return;

}

ỏ ộ b. Xoá m t con tr : Cú pháp:

free(Point_Variable)

ả ỏ ở ợ i phóng vùng nh ớ đư c tr  b i

Gi Point_Variable

ạ

ầ ư c a danh sách

c. Các phép toán thương dùng trong danh sách liên

ề ấ ộ

ớ ớ ỏ ỏ đ n vùng nh  này.

k tế  T o m t ph n t ủ ộ ấ ả Đi u ph i làm là c p pháp b  nh  cho c u trúc  ế ả ề và tr  v  con tr  tr   Ví d :ụ

*CreatNode()

POINT {

*p;

POINT p = (POINT *) malloc (sizeof(POINT)); if  (p==NULL) {

printf(“Malloc falled.\n”); exit(1);

} printf(“Input data for Node info = ”);  scanf(“%d”, p­>info); p­>Next = NULL return p;

}

B  sung ph n t

ỉ ấ

ộ

ầ ư vào danh sách ổ Hàm CreatNode() ch  c p phát b  nh  nh

ầ ử

ớ ưng nó  đi u ề ể

ố  này vào danh sách. Đ  làm  không n i ph n t ộ ầ ọ ữ này, ta c n thêm m t hàm n a, g i là hàm AddNode().  ư sau: ị Đư c ợ đ nh nghĩa nh static POINT *Head; void AddNode(POINT *e) {

POINT *p; if (Head ==NULL) {

Head = e; return;

}

for (p=Head; p­>Next!=NULL; p=p­>Next); p­>Next=e;

} Chú ý: ế ầ

ợ ầ

ị ể

ế ả

ợ ị vào danh sách liên k t, ta ph i  ầ ử ớ ẽ đư c chèn vào v  trí nào.Sau

ẽ ự ệ ỏ ỏ đ n ế đ u  danh  sách,  nên  Bi n  Head  là  con  tr   tr   ương  trình.(Sau  ph n ầ c n ầ đư c  khai  báo  đ u  ch ỏ khai đ nh nghĩa ki u con tr ). Chèn ph n tầ ư vào danh sách ầ ử ể Đ  chèn ph n t ỉ ỏ  m i s   ch  r  ph n t ệ đây là hàm s  th c hi n công vi c trên.

void InsertNode(POINT *p, POINT *q) { if (p=NULL || q=NULL || p==q || q­>Next ==p)

{ printf (“Cannot Insert \n”);    return; }

p­>Next =q­>Next; q­>Next=p; };

Xoá ph n tầ ư vào danh sách

kh i danh sách liên k t

ầ ử ầ

ố ế đơn,  đ  ể  c n xoá  ầ ử  sau ph n t   ớ ộ i ph ng b  nh ầ ử ỏ ớ ầ ử ư c ph n t  tr ầ ử ố ạ ớ i v i ph n t ể ả đ  gi

ầ ử ị b  xoá.

ộ Xoá m t ph n t ả ầ ta c n ph i tìm ph n t ụ đích n i l ằ nh m m c  ầ c n xoá. Ta dùng hàm free()  ở ế chi m b i ph n t ưng là: ể Có th  xây d void DeleteNode(POINT *goner) {

POINT *p; p=Head; if (goner ==Head)

Head = goner­>Next;

else  { while (p!=NULL && p­>Next!=goner)

p=p­>Next;

if (p=NULL)

{

printf(“Cannot find Node \n”); return;

} p­>Next=p­>Next­>Next;

}; free(goner)

};

Tìm ph n tầ ư vào danh sách ạ

ậ

ộ

ổ

ả ự

ờ

ề ể ế

ử ụ ả ử ụ

ấ ổ

Th t khó t o m t hàm FindNode() t ng quát,  ộ ở ế b i vì khi tìm ki m thì ta ph i d a vào m t trong  ụ ữ ệ ủ ấ ư ng d  li u c a c u trúc,  ữ đi u này ph   nh ng tr ộ t  hàm  thu c  vào  c u  trúc  dang  s   d ng.  Đ   vi ỏ ỏ FindNode() t ng quát ta ph is  d ng con tr  tr   ế đ n hàm. ớ ấ

ự

V i c u trúc trên ta xây d ng hàm FindNode()

như sau:

POINT *FindNode(int *n)

{ POINT *p; for (p=Head; p!=NULL; p=p­>Next)

if (p­>Info=n)  return p;

return NULL; };

II. Danh sách đa liên k tế

ị

ấ

ể ủ ầ ử

ầ ấ

ầ ử ấ c u trúc

Đ nh nghĩa: Cú pháp: ể struct   { ầ ử  ; ỏ ấ ể struct  *,; }

ể ứ ế đ  ch a

ụ ị ộ Ví d : Đ nh nghĩa m t danh sách liên k t  ố các s  nguyên. struct  Point {

int info; struct Point *Next,*Previous;

};

III. STACK và QUEUE 1.

ặ ệ ặ ầ t. M c d u ta

ề ể ự

ữ ẫ ấ

ỏ ỉ ầ ử ở

ủ

ể ấ ấ ạ đ nh c a Stack. ưng như v y thì Stack có ki u c u

STACK Là danh sách có móc n i ố đ c bi ệ có th  th c hi m nhi u phép toán trên danh sách  ổ t ng quát, Stack v n có nh ng tính ch t riêng  ệ t: ch  cho phép thêm và xoá b  các ph n t   bi ỉ ộ ị m t v  trí duy nh t, t i  ậ V i ớ đ c trặ ữ ệ trúc d  li u là LIFO (Last In First Out)

ử ụ ả ở ạ a. Kh i t o Stack S  d ng m ng:

int stack[100], p; Stackinit() { p=0; } ử ụ ế S  d ng danh sách liên k t

struct Node  {  int info;     struct Node *Next;

};

typedef struct Node NODE; NODE *Head, *p, *q; StackInit() {

Head = (NODE *) malloc (sizeof *Head);  p=(NODE *) malloc (sizeof *p); Head­>Next=p; Head­>info=0; p­>Next=NULL; return 0;

}

b. Đ y d  li u vào Stack

ẩ ữ ệ ử ụ ả

S  d ng m ng: Push (int x) {

stack[p++]=x;

ử ụ ế } S  d ng danh sách liên k t:

Push(int a) {

q=(NODE *) malloc (sizeof *q); q­>info=a; q­>Next=Head­>Next; Head­>Next=q; return 0;

ỏ

ị c. L y giá tr  ra kh i Stack

} ấ ử ụ

ả

S  d ng m ng: Pop (int x) {

return stack[p­­];

}

ử ụ ế S  d ng danh sách liên k t:

Pop() {

int x; q=Head­>Next; Head­>Next=q­>Next; x=q­>info; free(q); return x;

}

ỗ

ả d. Ki m tra Stack r ng S  d ng m ng:

ể ử ụ int stackempty() {

return !p;

ế S  d ng danh sách liên k t:

} ử ụ int StackEmpty() {

return Head­>Next==p;

}

ằ ự ụ

Ví d : Xây d ng stack b ng danh sách liên kêt: #include "stdio.h" #include "alloc.h" #define ESC 27 struct Node  {    int info;    struct Node *Next;  }; typedef struct Node NODE; NODE *Head, *p, *q;

StackInit() {  Head = (NODE *) malloc (sizeof *Head);  p=(NODE *) malloc (sizeof *p);  Head­>Next=p;  Head­>info=0;  p­>Next=NULL;  return 0; }

Push(int a) {   q=(NODE *) malloc (sizeof *q);   q­>info=a;   q­>Next=Head­>Next;   Head­>Next=q;   return 0; }

Pop() {   int x;   q=Head­>Next;   Head­>Next=q­>Next;   x=q­>info;   free(q);   return x; } int StackEmpty() { return Head­>Next==p; }

void main() {  int b;  char c;  StackInit();  do   {    clrscr();    printf("\nNhap gia tri vao Stack  ");    scanf("%d",&b);    Push(b);

printf("\nAn Enter de tiep tuc/ESC de thoi nhap");

c=getchar();    c=getch();   }  while(c!=ESC);  printf("\nCac gia tri trong Stack\n");  while (!StackEmpty())  printf("%d  ",Pop());  printf("\nAn ESC de ket thuc");  getch(); }

2. Queue

ộ Queue hay còn g i là hàng

ọ t. Các ph n t

ộ

ệ ợ ọ ợ ọ đư c g ilà

ư c.ớ đư c s  d ng trong các tình  ộ ệ ử c

đ i, ợ đây là m t ki u  ể ợ ầ ử đư c thêm vào  ặ danh sách đ c bi ấ ầ ừ ộ đ u, ầ đư c g i là  đ u sau, và l y ra m t   m t  t đ u trầ ầ đ u khác,  ợ ử ụ ấ C u trúc này  ầ ử ầ ử ậ ố hu ng l p trình c n x  lý m t dãy các ph n t   ọ ị ộ ậ ự ố đ nh. Vi c x  lý này g i là  theo m t tr t t FIFO (First Int First Out).