Hướng dẫn và cài đặt bằng C/C++

Ở nội dung trước, tôi đã hướng dẫn bạn cách cài đặt mục lục link đơn và các tri thức về mục lục link. Nội dung này, mình sẽ hướng dẫn bạn cài đặt mục lục link đôi nhé. Danh mục link đôi có sự link 2 chiều giữa 2 phần tử liền kề nhau trong lúc mục lục link đơn chỉ có link một chiều.

1. Lý thuyết về Danh mục link đôi

Một Node của mục lục link đôi sẽ có dạng như sau:

1

2

3

4

5

6

 

    ———————————————

    |              |             |              |

    |     PREV     |     DATA    |    NEXT      |

    |              |             |              |

    ———————————————

 

Và hình dưới đây so sanh sự khác nhau giữ dslk đôi và dslk đơn:

2. Cài đặt mục lục link đôi

2.1. Khai báo & khởi tạo

Khác một tí với dslk đơn, ngoài con trỏ next, tất cả chúng ta sẽ có thêm con trỏ prev để link với Node trước nó. Tất cả chúng ta vẫn sẽ để data có kiểu int để dễ dàng và dễ hiểu nhé.

Ngay sau khai báo, tất cả chúng ta sẽ khởi tạo Node trước hết của mục lục link đôi.

1

2

3

4

5

6

7

8

 

struct

Node

  

{

    

int

data

;

    

struct

Node*

next

;

    

struct

Node*

prev

;

}

;

 

struct

Node*

head

;

// Khởi tạo Node head global của dslk đôi.

 

2.2. Tạo mới 1 Node

Thay vì chỉ cho next = NULL và gán giá trị cho Node mới, tất cả chúng ta cũng cần phải cho con trỏ prev = NULL.

1

2

3

4

5

6

7

8

9

 

struct

Node*

GetNewNode

(

int

x

)

{

    

struct

Node*

newNode

        

=

(

struct

Node*

)

malloc

(

sizeof

(

struct

Node

)

)

;

    

newNode

>

data

=

x

;

    

newNode

>

prev

=

NULL

;

    

newNode

>

next

=

NULL

;

    

return

newNode

;

}

 

2.3. Thêm Node

Thêm vào đầu

  • Nếu head = NULL, ta sẽ cho cả head và tail = newNode.
  • Nếu head != NULL, ta sẽ update lại head mới là newNode. Ta cần tạo link giữa head lúc này với newNode trước khi cho newNode làm head mới.

1

2

3

4

5

6

7

8

9

10

11

12

 

void

InsertAtHead

(

int

x

)

{

    

struct

Node*

newNode

=

GetNewNode

(

x

)

;

    

if

(

head

==

NULL

)

{

        

head

=

newNode

;

        

tail

=

newNode

;

        

return

;

    

}

    

head

>

prev

=

newNode

;

    

newNode

>

next

=

head

;

    

head

=

newNode

;

}

 

Về căn bản, sáng tạo thêm Node vào đầu/ cuối vẫn giống với thêm vào đầu trong mục lục link đơn.

Thêm vào cuối

  • Nếu head = NULL, newNode sẽ là head và tail luôn
  • Nếu head != NULL, update lại tail mới là newNode. Ta cần tạo link thằng tail lúc này với newNode trước khi để newNode làm tail mới.

1

2

3

4

5

6

7

8

9

10

11

12

 

void

InsertAtTail

(

int

x

)

{

    

struct

Node*

newNode

=

GetNewNode

(

x

)

;

    

if

(

head

==

NULL

)

{

        

head

=

newNode

;

        

tail

=

newNode

;

        

return

;

    

}

    

tail

>

next

=

newNode

;

    

newNode

>

prev

=

tail

;

    

tail

=

newNode

;

}

 

2.4. Xóa Node

Xóa ở đầu

  • Nếu head = NULL, chẳng có gì để xóa
  • Nếu head != NULL, cho head mới bằng phần tử kế đến và sửa prev của nó = NULL(ngắt link với thằng head cũ).

1

2

3

4

5

6

7

8

 

void

DeleteAtHead

(

)

{

    

if

(

head

==

NULL

)

{

        

return

;

    

}

    

head

=

head

>

next

;

    

head

>

prev

=

NULL

;

}

 

Xóa ở cuối

  • Nếu head = NULL, chẳng có gì để xóa
  • Nếu head != NULL, cho tail mới bằng phần tử trước nó và sửa next của nó = NULL(ngắt link với thằng tail cũ).

1

2

3

4

5

6

7

8

 

void

DeleteAtTail

(

)

{

    

if

(

head

==

NULL

)

{

        

return

;

    

}

    

tail

=

tail

>

prev

;

    

tail

>

next

=

NULL

;

}

 

2.5. Duyệt mục lục link

Duyệt từ đầu tới cuối

Ta sẽ duyệt khởi đầu từ Node head cho tới trước khi gặp Node NULL bằng cách sử dụng con trỏ next.

1

2

3

4

5

6

7

8

9

10

 

void

Print

(

)

{

    

struct

Node*

temp

=

head

;

    

printf

(

“nForward: “

)

;

    

while

(

temp

!

=

NULL

)

{

        

printf

(

“%d “

,

temp

>

data

)

;

        

temp

=

temp

>

next

;

    

}

    

printf

(

“n”

)

;

}

 

Duyệt từ cuối về đầu

Lần này, ta sẽ duyệt khởi đầu từ Node tailcho tới trước khi gặp Node NULL bằng cách sử dụng con trỏ prev.

1

2

3

4

5

6

7

8

9

10

11

12

 

void

ReversePrint

(

)

{

    

struct

Node*

temp

=

tail

;

    

if

(

temp

==

NULL

)

return

;

// empty menu, exit

    

// Traversing backward using prev pointer

    

printf

(

“nReverse: “

)

;

    

while

(

temp

!

=

NULL

)

{

        

printf

(

“%d “

,

temp

>

data

)

;

        

temp

=

temp

>

prev

;

    

}

    

printf

(

“n”

)

;

}

 

3. Full code mục lục link đôi

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

 

/* Doubly Linked Menu implementation */

#includevàlt;stdio.hvàgt;

#includevàlt;stdlib.hvàgt;

 

struct

Node

  

{

    

int

data

;

    

struct

Node

*

next

;

    

struct

Node

*

prev

;

}

;

 

struct

Node

*

head

,

*

tail

;

// Khởi tạo Node head global của dslk đôi.

 

//Creates a new Node and returns pointer to it.

struct

Node

*

GetNewNode

(

int

x

)

{

    

struct

Node

*

newNode

        

=

(

struct

Node

*

)

malloc

(

sizeof

(

struct

Node

)

)

;

    

newNode

>

data

=

x

;

    

newNode

>

prev

=

NULL

;

    

newNode

>

next

=

NULL

;

    

return

newNode

;

}

 

//Inserts a Node at head of doubly linked menu

void

InsertAtHead

(

int

x

)

{

    

struct

Node

*

newNode

=

GetNewNode

(

x

)

;

    

if

(

head

==

NULL

)

{

        

head

=

newNode

;

        

tail

=

newNode

;

        

return

;

    

}

    

head

>

prev

=

newNode

;

    

newNode

>

next

=

head

;

    

head

=

newNode

;

}

 

//Inserts a Node at tail of Doubly linked menu

void

InsertAtTail

(

int

x

)

{

    

struct

Node

*

newNode

=

GetNewNode

(

x

)

;

    

if

(

head

==

NULL

)

{

        

head

=

newNode

;

        

tail

=

newNode

;

        

return

;

    

}

    

tail

>

next

=

newNode

;

    

newNode

>

prev

=

tail

;

    

tail

=

newNode

;

}

 

 

void

DeleteAtHead

(

)

{

    

if

(

head

==

NULL

)

{

        

return

;

    

}

    

head

=

head

>

next

;

    

head

>

prev

=

NULL

;

}

 

//Inserts a Node at tail of Doubly linked menu

void

DeleteAtTail

(

)

{

    

if

(

head

==

NULL

)

{

        

return

;

    

}

    

tail

=

tail

>

prev

;

    

tail

>

next

=

NULL

;

}

 

//Prints all the elements in linked menu in forward traversal order

void

Print

(

)

{

    

struct

Node

*

temp

=

head

;

    

printf

(

“nForward: “

)

;

    

while

(

temp

!

=

NULL

)

{

        

printf

(

“%d “

,

temp

>

data

)

;

        

temp

=

temp

>

next

;

    

}

    

printf

(

“n”

)

;

}

 

//Prints all elements in linked menu in reverse traversal order.

void

ReversePrint

(

)

{

    

struct

Node

*

temp

=

tail

;

    

if

(

temp

==

NULL

)

return

;

// empty menu, exit

    

// Traversing backward using prev pointer

    

printf

(

“nReverse: “

)

;

    

while

(

temp

!

=

NULL

)

{

        

printf

(

“%d “

,

temp

>

data

)

;

        

temp

=

temp

>

prev

;

    

}

    

printf

(

“n”

)

;

}

 

int

main

(

)

{

 

    

/*Driver code to check the implementation*/

    

head

=

NULL

;

// empty menu. set head as NULL.

 

    

// Calling an Insert and printing menu both in forward as well as reverse direction.

    

InsertAtTail

(

2

)

;

    

Print

(

)

;

ReversePrint

(

)

;

    

InsertAtTail

(

4

)

;

    

Print

(

)

;

ReversePrint

(

)

;

    

InsertAtHead

(

6

)

;

    

Print

(

)

;

ReversePrint

(

)

;

    

InsertAtTail

(

8

)

;

    

Print

(

)

;

ReversePrint

(

)

;

    

DeleteAtHead

(

)

;

    

Print

(

)

;

ReversePrint

(

)

;

    

DeleteAtTail

(

)

;

    

Print

(

)

;

ReversePrint

(

)

;

}

 

Kết quả chạy:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

 

Forward: 2

 

Reverse: 2

 

Forward: 2 4

 

Reverse: 4 2

 

Forward: 6 2 4

 

Reverse: 4 2 6

 

Forward: 6 2 4 8

 

Reverse: 8 4 2 6

 

Forward: 2 4 8

 

Reverse: 8 4 2

 

Forward: 2 4

 

Reverse: 4 2

 

Process returned 0 (0x0)   execution time : 0.040 s

Press any key to continue.

 

Xem Thêm  Tìm kiếm link Fshare nhanh chóng, chính xác - edumall review

Viết một bình luận