(Implementations of Linear List) (Implementations of Linear List)
• Dùng m ng (Array-based)
〓C t gi các ph n t c adanh sách vào các ô liênti p c a m ng
• Danh sách liên k t (Linked list / Pointer-based)
〓Các ph n t c a danh sách có th c t gi các ch tu ý trong b nh .
〓M i ph n t có contr (ho cmóc n i- link) đ n ph n t ti p theo
• a ch không tr c ti p (Indirect addressing)
〓Cácph n t c adanh sách có th c t gi các ch tu ý trongb nh
〓T o b ng trong đó ph n t th i c a b ngcho bi t n i l u tr ph n t th ic a danh sách
• Mô ph ng con tr (Simulated pointer)
〓T ng t nh bi u di n liên k t nh ng các s nguyên đ c thay b i contr c a C++
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
3.3. Danh sách 3.3. Danh sách
3.3.1. Danh sách tuy n tính
3.3.2. Cài đ t danh sách tuy n tính Bi u di n d i d ng m ng
Danh sách móc n i Danh sách n i đôi 3.3.3. Các ví d ng d ng
3.3.4. Phân tích s d ng linked list
3.3.5. M t s bi n th c a danh sách móc n i
Chap03-46
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
3.3.2.1. Bi u di n d i d ng m ng 3.3.2.1. Bi u di n d i d ng m ng
(Array
(Array--based based Representation of Linear Representation of Linear List)List)
• Ta c t gi các ph n t c a danh sách tuy n tính vào các ô (liên ti p) c a m ng (array).
• Danh sách s làc utrúcg m hai thànhph n.
〓Thànhph n 1 : làm ng các ph n t
〓Thành ph n 2 : last - cho bi t v trí c a ph n t cu i cùng trong danh sách
• V trí có ki u nguyên (integer) và ch y trong kho ng t 0 đ n maxlength-1 . Hàm END(L)tr l igiá tr last+1.
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Bi u di n d i d ng m ng Bi u di n d i d ng m ng -- CC
(Array
(Array--based based Representation of Linear Representation of Linear List)List)
# define maxlength 1000
typedef int elementtype; /* elements are integers */
typedef struct list_tag {
elementtype elements [maxlength];
int last;
} list_type;
Hàm End(L)
int end (list_type *lp) {
return (lp->last +1) }
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Cài đ t Insert Cài đ t Insert
Insert (x, p,L): Chèn x vào v trí p trong danh sách
void insert (elementtype x , int p , list_type * lp) { int v; // running position
if (lp -> last >= maxlength - 1) { printf("\n%s ","list is full");
return;
}
if ((p < 0) || (p > lp -> last + 1))
{ printf("\n%s ","position does not exist");
return;
} else {
for (int q = lp -> last; q <= p; q--)
lp -> elements [q+1] = lp -> elements [q];
lp -> last = lp -> last +1 ; lp -> elements[p] = x;
} }
Chap03-49
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Cài đ t DELETE Cài đ t DELETE
Delete (p, L): lo i ph n t v trí p trong danh sách L
void deleteL(int p , list_type * lp) {
int q; /* running position */
if ((p > lp-> last) || (p < 0))
{ printf("\n%s ","position does not exist");
return;
}
else /* shift elements */ { lp -> last --;
for (int q = p; q <= lp ->last; q++)
lp -> elements [q] = lp -> elements [q+1];
} }
Chap03-50
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Cài đ t LOCATE Cài đ t LOCATE
Locate (x, L): tr l i v trí c a x trong danh sách L
int locate (elementtype x , list_type * lp) {
int q;
for (q = 0; q <= lp ->last; q++) if (lp -> elements [q] == x)
return (q);
return (lp -> last + 1); /* if not found */
}
Chap03-51
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
3.3. Danh sách 3.3. Danh sách
3.3.1. Danh sách tuy n tính
3.3.2. Cài đ t danh sách tuy n tính Bi u di n d i d ng m ng
Danh sách móc n i
Danh sách n i đôi 3.3.3. Các ví d ng d ng
3.3.4. Phân tích s d ng linked list
3.3.5. M t s bi n th c a danh sách móc n i
Chap03-52
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Phân tích cách bi u di n d i d ng m ng Phân tích cách bi u di n d i d ng m ng
(Array
(Array--based based Representation of Linear Representation of Linear List)List)
• Có th nh n th y m t s u - khuy t đi m sau đây c a cách t ch c l u tr này:
〓Cách bi u di nnày r t ti ncho vi ctruy xu t đ ncác ph n t c adanh sách.
〓Do danh sách là bi n đ ng, s ph n t trong danh sách là không bi t tr c. Nên ta th ng ph i khai báo kích th c t i đa cho m ng đ d phòng (maxlength). i u này d n đ n lãng phíb nh .
〓Các thao tác chèn m t ph n t vào danh sách và xoá b m t ph n t kh i danh sách đ c th c hi n ch m (v i th i gian tuy ntínhđ i v i kích th c danh sách)
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
L u tr móc n i đ i v i danh sách tuy n tính L u tr móc n i đ i v i danh sách tuy n tính
((Linked List)Linked List)
• L u tr k ti p có nh ng nh c đi m c b n đã đ c phân tích trên: đó là vi c b sung và lo i tr ph n t là r t t n kémth i gian, ngoài ra ph i k đ n vi c s d ng m t không gian liên t c trong b nh . Vi c t ch c con tr (ho c móc n i) đ t ch c danh sách tuy n tính - mà ta g i là danh sách móc n i là gi i pháp kh c ph c nh c đi m này, tuy nhiên cái giá mà taph i tr là b nh dành cho con tr .
• Ta s xét các cách t ch c danh sách móc n i sau đây:
〓Danh sách n i đ n(Singly linked list)
〓Danh sách n ivòng (Circulary linked list)
〓Danh sách n i đôi (Doubly Linked List)
Chap03-54
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Khi nào dùng danh sách móc n i Khi nào dùng danh sách móc n i
• Khi không bi t kích th c c a d li u - hãy dùng con tr và b nh đ ng (Unknown data size – use pointers & dynamic storage).
• Khi không bi t ki u d li u - hãy dùng con tr void (Unknown data type – use void pointers).
• Khi không bi t s l ng d li u - hãy dùng danh sách móc n i (Unknown number of data – linked structure).
Chap03-55
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
(Singly linked list) (Singly linked list)
• Trong cách bi u di n này, danh sách bao g m các ô (các nút - node), m i ô ch a m t ph n t c a danh sách và con tr đ n ô ti ptheo c adanh sách.
• N u danh sách là a1, a2, . . . , an, thì ô l u tr ai có con tr (m i n i) đ n ô l u tr ai+1 v i i = 1, 2 , . . . , n-1. Ô l u tr an có con tr r ng,mà ta s ký hi ulànil.Nh v y m i ô có c utrúc:
• Có m t ô đ c bi t g i là ô header đ tr ra ô ch a ph n t đ u tiên trong danh sách (a1); Ô header khôngl u tr ph n t nào c . Trong tr ng h p danh sách r ng, con tr c a header là nil, và không có ô nào khác.
• Các ô cóth n m v trí b t k trong b nh
Chap03-56
Element Link/Pointer
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
(Singly linked list) (Singly linked list)
• Danh sách móc n i đ c t ch c nh trong hình v sau:
• M i n i ch ra đ a ch b nh c a nút ti p theo trong danh sách
Chap03-57
header
3000 10 5000 8 2000 50 NULL 3000 5000 2000
a ch b nh
a1 a2 . . . an nil
header
list
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
(Singly linked list) (Singly linked list)
• Mô t danh sách n i đ n trong PASCAL:
Type
DataType = ... {ki u c a d li u}
PointerType = ^Node;
Node = record
Inf: DataType; {l u tr ph n t } Next: PointerType; {tr đ n nút k ti p} end;
LIST = PointerType; { ki u LIST đ mô t danh sách }
• Khai báo trên đ nh ngh a ki u PointerType tr t i Node, trong đó Node là ki u b n ghi mô t m t nút g m hai tr ng:
〓Inf -l u d li u có ki u là DataType đã đ c đ nh ngh a, có th g m nhi u thành ph n
〓Next thu c ki u PointerType, l u đ a ch c a nút k ti p.
• C n có bi n First thu c ki u PointerType l u đ a ch c a nút đ u tiên trong danh sách:
Var First: PointerType;
Chap03-58
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
((Singly linked list)Singly linked list)
• Mô t danh sách n i đ n trong C:
typedef <Ki u d li u ph n t > ElementType;
struct NodeType{
ElementType Inf;
NodeType *Next; };
typedef struct NodeType LIST;
• Khai báo trên đ nh ngh a ki u NodeType, trong đó NodeType là ki u b n ghi mô t m t nút g m hai tr ng:
〓Inf -l u d li u có ki u là ElementType (đã đ c đ nh ngh a, có th g m nhi u thành ph n)
〓Next thu c ki u NodeType, l u đ a ch c a nút k ti p.
• C n có bi n con tr First l u đ a ch c a nút đ u tiên trong danh sách:
NodeType *First;
Chap03-59
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm END(L) Hàm END(L)
functionEND ( L: LIST ): PointerType;
{ END tr l i con tr đ n ô cu i cùng c a L} varq: PointerType;
begin q := L;
whileq^.next<> nil do q := q^.next;
return(q) end;
• Chú ý:
〓Hàm này làm vi c không hi u qu vì nó ph i duy t qua toàn b danh sách.
〓N u nh th ng xuyên ph i dùng đ n hàm này ng i ta th ng t o thêm m t con tr đ tr đ n v trí cu i cùng c a danh sách.
Chap03-60
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm INSERT(x,p) Hàm INSERT(x,p)
• Gi s c n chèn m t ph n t có n i dung d li u là x (có ki u ElementType) vào danh sách. V trí c n chèn đ c xác đ nh là sau nút đ c tr b i con tr Pred. Thao tác đ c ti n hành theo cácb c:
〓(1) Xin c p phát m t nút m i cho con tr TempNode đ l u x,
〓N inút này vào danh sách t i v trí c nchèn:
(2)TempNode->Next b ngPred->Next (3)ghi nh n l iPred->Next b ngTempNode.
Chap03-61
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm INSERT(x,p) Hàm INSERT(x,p)
• S đ c a thao tác c n làm v i danh sách đ c minh ho nh sau:
Chú ý:
〓Vi cchèn m tnút không nh h ng đ n m iliênk t c acác nút đ ngsau v trí chèn, do đó không ph i th c hi n d n ph n t nh trong cài đ t m ng.
Chap03-62 (1) TempPtr
(3) (2)
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm INSERT(x,p): Cài đ t trên C Hàm INSERT(x,p): Cài đ t trên C
NodeType *Insert_Middle(NodeType *Pred, ElementType X) { Chèn m t nút m i v i thông tin X vào sau nút đ c tr b i Pred }
{ NodeType *TempNode;
TempNode = (NodeType *) malloc(sizeof(NodeType)); //(1) TempNode->Inf=X; //(1) TempNode->Next=Pred->Next; //(2) Pred->Next=TempNode; //(3) return TempNode;
}
Chap03-63
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm INSERT(x,p) Hàm INSERT(x,p)
64
0x2000 TempPtr
0x3050 0x3080
Pred 0x3080
First
New(TempPtr); { xin c p phát nút m i } TempPtr^.Inf := x; { ghi nh n d li u }
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm INSERT(x,p) Hàm INSERT(x,p)
65
0x2000 TempPtr
0x3050 0x3080
Pred 0x3080
First
TempPtr^.Next := Pred^.Next;
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm INSERT(x,p) Hàm INSERT(x,p)
66
0x2000 TempPtr
0x3050 0x3080
Pred 0x3080
First
Pred^.Next := TempPtr;
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm DELETE(p) Hàm DELETE(p)
• Gi s c n lo i b nút đ ng sau nút đang đ c tr b i Pred. Vi c xoá ch ti n hành khi danh sách là khác r ng (C n ph i ki m tra đi u ki n này tr c khi th c hi n thao tác xoá).
• S d ng con tr TempPtr đ ghi nh n nút c n xóa, thao tác xoáđ c ti n hành theo các b c sau:
(1) GánTempPtrb ng Pred->Next.
(2) t l i Pred->Nextb ng TempPtr->Next.
(3) Thuh i vùng nh đ c tr b iTempPtr.
Chap03-67
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm DELETE(p) Hàm DELETE(p)
• S đ c a thao tác c n làm v i danh sách đ c minh ho trong hình d i đây:
Chap03-68 (1) TempPtr
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Danh sách móc n i đ n Danh sách móc n i đ n
Hàm DELETE(p): Cài đ t trên C Hàm DELETE(p): Cài đ t trên C
ElementType Delete(NodeType *Pred)
{ Xoá nút sau nút đ c tr b i Pred và tr l i giá tr nút b xoá } { ElementType X; NodeType *TempNode;
TempNode=Pred->Next; //(1) Pred->Next=Pred->Next->Next; //(2) X=TempNode->Inf;
free(TempNode); //(3) return X;
}
Chap03-69 Pred
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Cài đ t m t s thao tác th ng dùng khác Cài đ t m t s thao tác th ng dùng khác
• Chèn m t nút vào đ u danh sách
• Chèn m t nút vào cu i danh sách
• Xoá nút đ u danh sách
• Xoá nút cu i danh sách
• Ki m tra danh sách r ng
• Hu danh sách
Chap03-70
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Chèn vào đ u danh sách Chèn vào đ u danh sách
Procedure ChenVaoDau(Var First : LIST; X : DataType);
{ Chèn m t nút vào đ u danh sách đ c tr b i First} Var TempPtr : PointerType;
Begin
New(TempPtr);
TempPtr^.Inf := X;
TempPtr^.Next := First;
First := TempPtr;
End;
Chap03-71 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Chèn vào cu i danh sách Chèn vào cu i danh sách
Procedure ChenVaoCuoi(Var First : LIST; X : DataType);
{ Chèn m t nút vào cu idanh sáchđ c tr b i First. Gi s danh sách khác r ng} Var TempPtr, prev, cur : PointerType;
Begin
New(TempPtr); TempPtr^.Inf := X; (* T o nút m i ch a X *) prev := nil; {kh i t o con tr prevvà cur.}
cur := First;
while(cur <> nil) do{L n đ n nút cu i danh sách}
begin
prev :=cur; cur := prev^.next;
end;
TempPtr^.next := cur; {n i nút m i vào cu i danh sách } prev^.next := TempPtr;
End;
Chap03-72 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Xoá ph n t đ u danh sách Xoá ph n t đ u danh sách
Procedure XoaDau(Var First : LIST; Var X : DataType);
{ Xoá nút đ u danh sách đ c tr b i First} Var TempPtr : PointerType;
Begin
TempPtr := First;
First := First^.Next;
X := TempPtr^.Inf; { C t n i dung c a nút ra X } Dispose(TempPtr);
End;
Chap03-73 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Xoá ph n t cu i danh sách Xoá ph n t cu i danh sách
procedure DeleteLast (First: LIST; X: DataType);
(* Xoá nút cu i c a danh sách. Gi s danh sách khác r ng *) var cur, prev: PointerType;
begin
cur := First; {kh i t o con tr prevvà cur.}
prev := nil;
while(cur^.next <> nil) do {l p đ n khi cur ch đ n nút cu i danh sách}
begin prev :=cur; cur := prev^.next; end;
X:= cur^.Inf; { tr l i X nút cu i }
prev^.next := nil; { đ t set the LINK portion of the node pointed by prev}
dispose(cur); { thu h i vùng nh c p cho nút cu i } end;
Chap03-74 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Tìm ki m Tìm ki m
{Tìm ki m trên danh sách móc n i đ c tr b i First. N u giá tr e có trong danh sách thì curs ch ra nút và khi đó prevs ch ra nút đi tr c. }
procedureSearch (First: LIST; varcur, prev: PointerType; e: DataType);
begin
cur := First; {initialization}
prev := nil;
while( cur^.Inf <> e) and (cur^.next <> nil) do begin prev := cur;
cur := cur^.next end;
end;
Chap03-75
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
IsEmpty và PrintLIST IsEmpty và PrintLIST
{ Hàm ki m tra danh sách r ng }
Function IsEmpty(First : LIST) : Boolean;
Begin
IsEmpty := First = Nil End;
{ a ra toàn b thông tin các nút } Procedure PrintLIST(First : LIST);
Var TempPtr : U;
Begin
TempPtr := First;
While TempPtr <> Nil Do Begin
< Print(TempPtr^.Inf )> { a ra n i dung c a nút } TempPtr := TempPtr^.Next
End;
End;
Chap03-76
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Cài đ t trên C Cài đ t trên C
Chap03-77
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Chèn vào đ u danh sách Chèn vào đ u danh sách
//Chèn m t nút vào đ u danh sách đ c tr b i First
NodeType *Insert_ToHead(NodeType *First, ElementType X) { NodeType *TempNode;
TempNode = (NodeType *) malloc(sizeof(NodeType));
TempNode->Inf=X; TempNode->Next=First;
First=TempNode;
return First;
}
Chap03-78 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Chèn vào cu i danh sách Chèn vào cu i danh sách
//Chèn m t nút vào cu idanh sáchđ c tr b i head. Gi s danh sách khác r ng NodeType *Insert_ToLast(NodeType *head, ElementType X) { NodeType *NewNode; NodeType *TempNode;
NewNode = (NodeType *) malloc(sizeof(NodeType));
NewNode->Inf=X; TempNode=head;
while (TempNode->next != NULL) // go to the end of a list
TempNode= TempNode->next;
TempNode->next = NewNode;
return head;
}
Chú ý: N u thao tác này ph i th c hi n th ng xuyên thì nên đ a vào con tr Last tr đ n nút cu i cùng c a danh sách
Chap03-79 head
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Xoá ph n t đ u danh sách Xoá ph n t đ u danh sách
//Xoá nút đ u danh sách đ c tr b i First
NodeType *Delete_Head(NodeType *First) { NodeType *TempNode;
TempNode=First->Next;
free(First);
return TempNode;
}
Chap03-80 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Xoá ph n t cu i danh sách Xoá ph n t cu i danh sách
// Xoá nút cu i c a danh sách. Gi s danh sách khác r ng NodeType *Delete_Last(NodeType *First)
{ NodeType *TempNode1, *TempNode2;
TempNode1= First; TempNode2= First;
while (TempNode1->next != NULL) // Go to the end of a list
{ TempNode2 = TempNode1;
TempNode1= TempNode1->next; } TempNode2->next = NULL;
free(TempNode1);
return First;
}
Chú ý: N u thao tác này ph i th c hi n th ng xuyên thì nên đ a vào con tr Last tr đ n nút cu i cùng c a danh sách
Chap03-81 First
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Tìm ki m Tìm ki m
• Tìm ki m trên danh sách móc n i đ c tr b i head, tr l i con tr đ n nút ch a giá tr e.
NodeType *Search(NodeType *head, ElementType e) {
while (head->inf != e) head=head->next);
return head;
}
Chap03-82
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
IsEmpty và PrintLIST IsEmpty và PrintLIST
• Hàm ki m tra danh sách r ng int IsEmpty(NodeType *head){
return !head;
}
• Hu danh sách
NodeType *MakeNull(NodeType *head){
while (!IsEmpty(head)) head=Delete_Head(head);
return head;
}
• a ra toàn b thông tin các nút void Print(NodeType *head)
{ NodeType *TempNode;
TempNode=head; int count = 0;
while (TempNode) {
printf("%6d", TempNode->Inf); count++;
TempNode=TempNode->Next;
if (count % 12 == 0) printf("\n");
}
printf("\n");
} Chap03-83
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1. Ch ng trình minh ho trên C Ví d 1. Ch ng trình minh ho trên C
• Xây d ng ch ng trình th c hi n công vi c sau đây:
〓T o ng u nhiên m t danh sách v i các ph n t là các s nguyên. Sau đó:
〓T danh sách t o đ c xây d ng hai danh sách: m t danh sách ch a t t c các s d ng còn danh sách kia ch a t t c các s âmc adanh sách banđ u.
• Ch ng trình d i đây s xây d ng m t s phép toán c b n đ i v i danh sách móc n i đ th c hi n các công vi c đ t ra.
Chap03-84
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1. Ch ng trình trên C Ví d 1. Ch ng trình trên C
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef long ElementType;
struct PointerType{
ElementType Inf;
PointerType *Next; };
PointerType *Insert_ToHead(PointerType *First, ElementType X)
{ PointerType *TempNode;
TempNode = (PointerType *) malloc(sizeof(PointerType));
TempNode->Inf=X; TempNode->Next=First;
First=TempNode;
return First;
}
Chap03-85
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1.
Ví d 1.
PointerType *Insert_Middle(PointerType *Pred, ElementType X) { PointerType *TempNode;
TempNode = (PointerType *) malloc(sizeof(PointerType));
TempNode->Inf=X;
TempNode->Next=Pred->Next;
Pred->Next=TempNode;
return TempNode;
}
Chap03-86
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1.
Ví d 1.
PointerType *Delete_Head(PointerType *First) { PointerType *TempNode;
TempNode=First->Next;
free(First);
return TempNode;
}
ElementType Delete(PointerType *Pred) { ElementType X;
PointerType *TempNode;
TempNode=Pred->Next;
Pred->Next=Pred->Next->Next;
X=TempNode->Inf; free(TempNode);
return X;
}
Chap03-87
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1.
Ví d 1.
void Print(PointerType *First) { PointerType *TempNode;
TempNode=First; int count = 0;
while (TempNode) {
printf("%6d", TempNode->Inf); count++;
TempNode=TempNode->Next;
if (count % 12 == 0) printf("\n");
} printf("\n");
}
int IsEmpty(PointerType *First) { return !First;
}
PointerType *MakeNull(PointerType *First) {
while (!IsEmpty(First)) First=Delete_Head(First);
return First;
}
Chap03-88
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1.
Ví d 1.
int main() {
PointerType *S1, *S2, *S3, *V1, *V2, *V3;
ElementType a; int i, n;
clrscr(); randomize(); S1=NULL;
// Tao phan tu dau tien a=-100+random(201);
S1=Insert_ToHead(S1, a);
printf("Nhap vao so luong phan tu n = ");
scanf("%i", &n); printf("\n");
// Tao ngau nhien danh sach va dua ra man hinh V1=S1;
for (i=2; i<=n; i++) { a=-100+random(201);
V1=Insert_Middle(V1, a);
}
printf("====> Danh sach ban dau: \n"); Print(S1);
printf("\n");
Chap03-89
CTDL & TT –NGUY N C NGH A –B môn KHMT – HBK Hà n i
Ví d 1.
Ví d 1.
V1 = S1; S2 = NULL; S3 = NULL;
while (V1) {
if (V1->Inf > 0)
if (!S2) { S2=Insert_ToHead(S2, V1->Inf); V2 = S2; } else { Insert_Middle(V2, V1->Inf); V2 = V2->Next; } if (V1->Inf < 0)
if (!S3) { S3=Insert_ToHead(S3, V1->Inf); V3 = S3;}
else { Insert_Middle(V3, V1->Inf); V3 = V3->Next;}
V1= V1->Next;
}
printf("====> Danh sach so duong: \n"); Print(S2);
printf("\n");
printf("====> Danh sach so am: \n"); Print(S3);
printf("\n");
S1=MakeNull(S1); S2=MakeNull(S2); S3=MakeNull(S3);
getchar(); getchar();
}
Chap03-90