狠狠撸

1
Danh Sách Liên K?t
Nguy?n Thanh Hiên
Danh Sách Liên K?t (Linked List)
? G?m nhi?u ph?n t? (g?i m?i ph?n t? là
m?t node)
? Các ph?n t? n?i k?t v?i nhau th?ng qua
vùng liên k?t
? Các ph?n t? ???c try xu?t tu?n t? và bao
g?m: vùng d? li?u và các vùng liên k?t
Ai
A node in a
linked list
A header node
A tail node

2
Các lo?i danh sách liên k?t
? DSLK ??n
? DSLK kép
? DSLK vòng
A2 A3 ANA1
A1
A2 A3 AN
A1
A2 A3 AN
Các Tác V?
? Kh?i t?o (init)
? Ki?m tra DSLK r?ng (IsEmpty)
? Xác ??nh kích th??c (Size)
? Chèn (Insert)
? Xóa (Remove)
? Tìm ki?m (Retrieve)
? Thay th? (Replace)
? Duy?t (Traverse)

3
DSLK ??n- C?u trúc d? li?u
? typedef struct node{
T info; // T là ki?u ?? ??nh ngh?a tr??c
struct node* link; // con tr? ch? ??n c?u trúc node
}NODE;
? T là ki?u d? li?u c? b?n ho?c ki?u d? li?u
t? ??nh ngh?a
? typedef struct node
{
int info;
struct node* link;
}NODE;
CTDL cho m?t
ph?n t? c?a DS
các s? nguyên

4
? typedef struct SinhVien
{
char Ten[30];
int MaSV;
}SV;
? typedef struct svNode
{
SV info;
struct svNode* link;
}SVNODE;
CTDL cho m?t
ph?n t? c?a DS
các sinh viên
? typedef struct phanso
{
int tu;
int mau;
}PS;
? typedef struct psNode
{
PS info;
struct psNode* link;
}PSNODE;
CTDL cho m?t
ph?n t? c?a DS
các ph?n s?

5
? typedef struct
{
NODE* pHead;
NODE* pTail;
} LIST;
pHead
pTail
A1
A2 A3 AN
DSLK ??n- Các Tác V?
? Kh?i t?o DS
void init (LIST &list){
list.pHead=NULL;
list.pTail=NULL;
}

6
? T?o m?t Node m?i cho DS
NODE* getNode(T x){
NODE* p;
p=new NODE;
if (p==NULL)
return NULL;
p-> info = x;
p-> link=NULL;
return p;
}
x
? Chèn m?t ph?n t? vào DS
– Chèn vào ??u (insertHead)
– Chèn vào cu?i (insertTail)
– Chèn sau ph?n t? q (insertMid)

7
? Chèn vào ??u (insertHead)
A1
A2 A3 AN
pTail
pHead
x
newNode
(1)(2)
? Chèn vào ??u (insertHead)
void insertHead(LIST &ds, NODE* newNode)
{
if (ds.pHead==NULL) //ds r?ng
{
ds.pHead = newNode; ds.pTail = ds.pHead;
}
else
{
newNode ->link = ds.pHead;
ds.pHead = newNode;
}
}

8
? Chèn vào cu?i (insertTail)
pHead
pTail
A1
A2 A3 AN
x
(1)
(2)
? Chèn vào cu?i (insertTail)
void insertTail(LIST &ds, NODE *newNode)
{
if (ds.pHead==NULL)
{
ds.pHead = newNode; ds.pTail = ds.pHead;
}
else
{
ds.pTail->link = newNode;
ds.pTail = newNode;
}
}

9
? Chèn sau ph?n t? q (insertMid)
pHead
pTail
A1
A2 A3 AN
x
(1)(2)
q
? Chèn sau ph?n t? q (insertMid)
void insertMid(LIST &ds,NODE *q, NODE* newNode)
{
if ( q!=NULL)
{
newNode ->link = q-> link;
q-> link = newNode;
if(q == ds.pTail)
ds.pTail = newNode;
}
else //chèn vào ??u danh sách
insertHead(ds, newNode);
}

10
? Tìm m?t ph?n t? trong DS
NODE * Retrieve(LIST ds, Data k)
{
NODE *p;
p = ds.pHead;
while((p!= NULL)&&(p->info != x))
p = p->link;
return p;
}
? Duy?t DS
void * Traverse(LIST ds)
{
NODE *p;
p = ds.pHead;
while(p!= NULL){
process(p);
p = p->link;
}
}

11
? Xoá m?t ph?n t?
– Xoá ph?n t? ??u
– Xoá ph?n ft? sau ph?n t? q
– Xoá ph?n t? có khoá k
? Xoá ph?n t? ??u
A1
A2 A3 AN
pTail
pHead

12
? Xoá ph?n t? ??u
Data RemoveHead(LIST &ds)
{
NODE *p;
Data x = NULLDATA;
if ( ds.pHead != NULL)
{
p = ds.pHead; x = p->info;
ds.pHead = ds.pHead->link;
delete p;
if(ds.pHead == NULL) ds.pTail = NULL;
}
return x;
}
? Xoá ph?n ft? sau ph?n t? q
A1
A2 A3 AN
pTail
pHead
q p

13
? Xoá ph?n t? sau ph?n t? q
void RemoveAfter (LIST &ds, NODE *q)
{ NODE *p;
if ( q != NULL)
{
p = q ->link ;
if ( p != NULL)
{
if(p == ds.pTail) ds.pTail = q;
q->link = p->link;
delete p;
}
}
else
RemoveHead(ds);
}
? Xoá ph?n t? có khoá k
int RemoveNode(LIST &ds, Data k)
{
NODE *p = ds.pHead;
NODE *q = NULL;
while( p != NULL)
{
if(p->info == k) break;
q = p; p = p->link;
}
if(p == NULL) return 0;
//Kh?ng tìm th?y k
if(q != NULL)
{
if(p == ds.pTail)
ds.pTail = q;
q->link = p->link;
delete p;
}
else //p là ph?n t? ??u ds
{
ds.pHead = p->link;
if(ds.pHead == NULL)
ds.pTail = NULL;
}
return 1;
}

14
DSLK ??n- H?y danh sách
void ReamoveList(LIST &ds)
{ NODE *p;
while (ds.pHead!= NULL)
{
p = ds.pHead;
ds.pHead = p->link;
delete p;
}
ds.pTail = NULL;
}
DSLK Kép- C?u trúc d? li?u
typedef struct DNode
{
T info;
struct DNode* pPre;
struct DNode* pNext;
}DNODE;

15
DSLK Kép- C?u trúc d? li?u
DNODE* GetNode(T x)
{
DNODE *p;
p = new DNODE;
if ( p==NULL) return NULL
p ->Info = x;
p->pPrev = NULL;
p->pNext = NULL;
return p;
}
DSLK Kép- Insert
? Chèn ??u
? Chèn cu?i
? Chèn sau ph?n t? q
? Chèn tr??c ph?n t? q

16
DSLK Kép- Insert
DSLK Kép- Insert
void Insert(DLIST &ds, DNODE* q, DNODE* newNode)
{ DNODE* p = q->pNext;
if ( q!=NULL) {
newNode->pNext = p; //(1)
newNode->pPrev = q; //(2)
q->pNext = newNode; //(3)
if(p != NULL)
p->pPrev = newNode; //(4)
if(q == ds.pTail)
ds.pTail = newNode;
}
else //chèn vào ??u danh sách
InsertHead(ds, newNode);
}

17
DSLK Kép- Remove
? Xóa ??u
? Xóa cu?i
? Xóa sau ph?n t? q
? Xóa tr??c ph?n t? q
? Xóa có khóa k
DSLK Kép- Remove sau q
void Remove(DLIST &ds, DNODE *q)
{ DNODE *p;
if ( q != NULL)
{
p = q ->pNext ;
if ( p != NULL)
{
q->pNext = p->pNext;
if(p == ds.pTail) ds.pTail = q;
else p->pNext->pPrev = q;
delete p;
}
}
else
RemoveHead(ds);
}

18
STACK
56
31
29
179
52
21 Bottom_of_stack
(this is where the
stack started)
top
Empty/unfilled
portion of stack
Direction
in which
stack grows
?Danh sách h?n ch?
?Các ph?n t? ???c
thêm vào và l?y ra ?
??nh stack
? Hi?n th?c dùng dslk
ho?c array
Stack – Tác v?
? Init()
? Push()
? Pop()
? IsEmpty()
? IsFull()
typedef struct {
T *theArray;
int top;
int size;
}STACK;
void init (STACK &s, int size) {
s.size = size;
s.theArray = new T[size];
s.top = -1;
}

19
Stack- Push()
void push(STACK &s, T x){
if (!isFull(s)){
s.top++;
s.theArray[s.top]=x;
}
}
bool isFull(STACK s) {
if(s.top < s.size-1) return false;
else return true;
}
Stack- Pop(), Top()
T pop(STACK &s){
if (!isEmpty(s))
return s.theArray[s.top--];
}
T top(STACK s){
return s.theArray[s.top];
}
bool isEmpty(STACK s) {
if(s.top == -1) return true;
else return false;
}

20
Stack-Ví d?
56
31
29
179
52
21
top
56
31
29
179
21
pop()
56
31
29
179
2
21
push(2)
56
31
29
179
2
21
Return 2
top
top
Return 52
top()
Queue
? Danh sách h?n ch?
? Chèn vào m?t ??u, l?y ra ? ??u kia
? Hi?n th?c dùng dslk ho?c array
? Linear and Circular Queues
front back empty portion
of the queue
12 31 79 5 63

21
Queue-Tác v?
? EnQueue()
Input: element to be enqueued
Algorithm:
increment back by 1
add element to the empty location pointed to by back
Return: void
? DeQueue()
Input: void
Algorithm:
return the element pointed to by front
increment front by 1
Return: the element dequeued
Queue – Ví d?
front back
12 31 79 5 63
front back
12 31 79 5 63 17
front back
31 79 5 63 17
front back
5231 79 5 63 17
front back
5279 5 63 17
enqueue(17)
dequeue
enqueue(52)
dequque

22
Queue – Ví d?
front back
79 5 63 17
front back
5279 5 63 17 enqueue(23)
dequeue
52 23
back
5 63 17 52 23
front
back
63 17 52 23
front
17 52 23
front back
dequeue
dequeue
enqueue(44):
QUEUE_FULL
Circular Queue

23
Circular Queue
? In enqueue:
back = (back +1) mod ARRAY_SIZE
? In dequeue:
front = (front + 1) mod ARRAY_SIZE
Circular Queue
back front
1171 57 81 122 39
back
front
8
EnQueue -> Queue full: (back+1)%size == front
DeQueue-> Queue empty: back == front

24
Circular Queue
typedef struct {
int size;
int front;
int back;
T* values;
} QUEUE;
Circular Queue
void init(QUEUE &q, int size) {
q.size = size;
q.values = new T[size];
q.front = 0;
q.back = 0;
}

25
Circular Queue
bool isFull(QUEUE q) {
if( (q.back+1) % q.size == q.front) return true;
else return false;
}
bool isEmpty(QUEUE q) {
if(q.back == q.front) return true;
else return false;
}
Circular Queue
void enqueue(QUEUE &q,T x) {
if(!isFull(q)) {
q.back = (q.back+1) % q.size;
q.values[q.back] = x;
}
}
T dequeue(QUEUE &q) {
if(!isEmpty(q)) {
q.front = (q.front+1) % q.size;
return values[q.front];
}
return NULLDATA;
}

26
C?Y
A
B C D E F
G H I J K L
T1 T3
T5leaf
root
T2 T4
edge
? C?y N node s? có N-1 c?nh
subtree
Path: n1->nk là m?t chu?i các nút n1 ->nk sao cho ni là cha ni+1, 1 <= i <=k
depth
C?Y
A
B C D E F
G H I J K L
T1 T3
T5leaf
root
T2 T4
depth
C?y nh? ph?n là c?y
mà m?i nút có t?i
?a hai nút con

27
C?Y NH? PH?N
C?C PH?P DUY?T
? PreOrder
– Duy?t g?c
– Duy?t các c?y con bên trái
– Duy?t c?y con bên ph?i
? InOrder
– Duy?t c?y con bên trái
– Duy?t g?c
? PostOrder
– Duy?t c?y con bên trái
– Duy?t g?c

28
C?Y NH? PH?N- CTDL
typedef struc TNode{
T info;
TNode* left;
TNode* right;
}TNODE;
TNODE *root=NULL;
C?Y NH? PH?N- Duy?t
void PreOrder(TNODE *root){
if (root!=NULL){
process(root);
PreOrder(roo->left);
PreOrder(root->right);
}
}
void InOrder(TNODE *root){
if (root!=NULL){
InOrder (root->left);
process(root);
InOrder (root->right);
}
}
void PostOrder(TNODE *root){
if (root!=NULL){
PostOrder (root->left);
PostOrder (root->right);
process(root);
}
}

29
V? D?
? Cho c?y nh? ph?n, m?i nút có info (kh?ng trùng
nhau) là m?t s? nguyên
– ??m s? nút trên c?y
– Tính t?ng các info trên c?y
– Cho bi?t t? tiên c?a nút có info là x
– Cho bi?t info các nút ? m?c 3
– Cho bi?t t?ng info trên c?y
– Cho bi?t các nút có t?ng info các conlà b?i s? c?a info
c?a cha nó
– Cho bi?t t?ng s? nút lá
– Cho bi?t t?ng s? nút b?c m?t
– Cho bi?t c?y có b? suy bi?n kh?ng
LAN TRUY?N TH?NG TIN
? Tham s?
– Tham bi?n
– Tham tr?
? H?i-?áp
H?i
a
H?i
b
a, b

30
C?Y NH? PH?N T?M KI?M (BST)
BST-Retrieval
TNODE* Retrieval(TNODE* root, T x){
if (root != NULL) {
If (root->info==x) return root;
if (x < root->info)
return Retrieveal (root->left, x);
else
return Retrieveal (root->right, x);
}
return NULL;
}

31
BST-Retrieval
x
BST-Insert
? T?o BSTv?i các info: 5 9 7 3 8 12 6 4 20

33
BST-Insert
BST-Insert
int Insert(TNODE*& root, T x)
{
if (root != NULL) {
if (root->info==x) return 0;
if (x < root ->info)
return Insert(root ->left, x);
else
return Insert(root ->right, x);
}
root = new TNODE;
If (root==NULL) return -1
root ->right = NULL;
root ->left = NULL:
root ->info = x;
return 1;
}

狠狠撸

Baigiang ctdl

Recommended

More Related Content

Viewers also liked (6)

Similar to Baigiang ctdl (20)

More from H? L?i (20)

Baigiang ctdl