linked list. I save those functions into a source file. In addition, I will set up an interface between the module file and the user. In other words, the user can
call one of the functions saved in the module via the interface. The interface is invoked in the main() function that is
saved in another source file. I will put data declarations and function prototypes in a separate header file.
A linked list is a chain of nodes (or elements). Each node consists of data items and a pointer that points to the next
node in the list.
The linked list I'm going to build is a very simple one, in which each element contains only two items: student name
and ID number. Listing 24.1 contains the module program, which is saved in the source file named 24L01.c.
TYPE
Listing 24.1. Putting cohesive functions in the module program.
1: /* 24L01.c: A module file */
2: #include "24L02.h"
3:
4: static NODE *head_ptr = NULL;
5:
6: /**
7: ** main_interface()
8: **/
9: void main_interface(int ch)
10: {
11: switch (ch){
12: case `a':
13: list_node_add();
14: break;
15: case `d':
16: if (!list_node_delete())
17: list_node_print();
18: break;
19: case `p':
20: list_node_print();
21: break;
22: default:
23: break;
24: }
25: }
26: /**
27: ** list_node_create()
28: **/
29: NODE *list_node_create(void)
30: {
31: NODE *ptr;
32:
33: if ((ptr=(NODE *)malloc(sizeof(NODE))) == NULL)
34: ErrorExit("malloc() failed.\n");
35:
36: ptr->next_ptr = NULL; /* set the next pointer to NULL */
37: ptr->id = 0; /* initialization */
38: return ptr;
39: }
40:
41: /**
42: ** list_node_add()
43: **/
44: void list_node_add(void)
45: {
46: NODE *new_ptr, *ptr;
47:
48: new_ptr = list_node_create();
49: printf("Enter the student name and ID: ");
50: scanf("%s%ld", new_ptr->name, &new_ptr->id);
51:
52: if (head_ptr == NULL){
53: head_ptr = new_ptr;
54: } else {
55: /* find the last node in the list */
56: for (ptr=head_ptr;
57: ptr->next_ptr != NULL;
58: ptr=ptr->next_ptr)
59: ; /* doing nothing here */
60: /* link to the last node */
61: ptr->next_ptr = new_ptr;
62: }
63: }
64: /**
65: ** list_node_delete()
66: **/
67: int list_node_delete(void)
68: {
69: NODE *ptr, *ptr_saved;
70: unsigned long id;
71: int deleted = 0;
72: int reval = 0;
73:
74: if (head_ptr == NULL){
75: printf("Sorry, nothing to delete.\n");
76: reval = 1;
77: } else {
78: printf("Enter the student ID: ");
79: scanf("%ld", &id);
80:
81: if (head_ptr->id == id){
82: ptr_saved = head_ptr->next_ptr;
83: free(head_ptr);
84: head_ptr = ptr_saved;
85: if (head_ptr == NULL){
86: printf("All nodes have been deleted.\n");
87: reval = 1;
88: }
89: } else {
90: for (ptr=head_ptr;
91: ptr->next_ptr != NULL;
92: ptr=ptr->next_ptr){
93: if (ptr->next_ptr->id == id){
94: ptr_saved = ptr->next_ptr->next_ptr;
95: free(ptr->next_ptr);
96: ptr->next_ptr = ptr_saved;
97: deleted = 1;
98: break;
99: }
100: }
101: if (!deleted){
102: printf("Can not find the student ID.\n");
103: }
104: }
105: }
106: return reval;
107: }
108: /**
109: ** list_node_print()
110: **/
111: void list_node_print(void)
112: {
113: NODE *ptr;
114:
115: if (head_ptr == NULL){
116: printf("Nothing to display.\n");
117: } else {
118: printf("The content of the linked list:\n");
119: for (ptr = head_ptr;
120: ptr->next_ptr != NULL;
121: ptr = ptr->next_ptr){
122: printf("%s:%d -> ",
123: ptr->name,
124: ptr->id);
125: }
126: printf("%s:%d ->|",
127: ptr->name,
128: ptr->id);
129: printf("\n");
130: }
131: }
132: /**
133: ** list_node_free()
134: **/
135: void list_node_free()
136: {
137: NODE *ptr, *ptr_saved;
138:
139: for (ptr=head_ptr; ptr != NULL; ){
140: ptr_saved = ptr->next_ptr;
141: free(ptr);
142: ptr = ptr_saved;
143: }
144: free(ptr);
145: }
146: /**
147: ** ErrorExit()
148: **/
149: void ErrorExit(char *str)
150: {
151: printf("%s\n", str);
152: exit(ERR_FLAG);
153: }
ANALYSIS
There is no direct output from the module program in Listing 24.1.
The purpose of the program in Listing 24.1 is to provide a module program that contains all cohesive functions for
linked list creation, node addition, and node reduction.
TYPE
Listing 24.2. Putting data declarations and function prototypes into the header file.
1: /* lnk_list.h: the header file */
2: #include
3: #include
4:
5: #ifndef LNK_LIST_H
6: #define LNK_LIST_H
7: #define ERR_FLAG 1
8: #define MAX_LEN 16
9:
10: struct lnk_list_struct
11: {
12: char name[MAX_LEN];
13: unsigned long id;
14: struct lnk_list_struct *next_ptr;
15: };
16:
17: typedef struct lnk_list_struct NODE;
18:
19: NODE *list_node_create(void);
20: void list_node_add(void);
21: int list_node_delete(void);
22: void list_node_print(void);
23: void list_node_free(void);
24: void ErrorExit(char *);
25: void main_interface(int);
26:
27: #endif /* for LNK_LIST_H */
ANALYSIS
There is no direct output from the program in Listing 24.2.
The purpose of the program in Listing 24.2 is to declare a structure with the tag name of lnk_list_struct in lines
10_15, and define a new variable name, of the structure NODE, in line 17.
The prototypes of the functions defined in the module program in Listing 24.1, such as list_node_create(),
list_node_add(), and list_node_delete(), are listed in lines 19_25.
Note that the #ifndef and #endif preprocessor directives are used in lines 5 and 27. The declarations and definitions
located between the two directives are compiled only if the macro name LNK_LIST_H has not been defined. Also,
line 6 defines the macro name if it's not been defined. It's a good idea to put the #ifndef and #endif directives in a
header file so as to avoid cross-inclusions when the header file is included by more than one source file. In this case,
the declarations and definitions in the 24L02.h header file will not be included more than one time.
The module program in Listing 24.3 provides an interface that the user can use to call the functions saved in the
source file (24L01.c).
TYPE
Listing 24.3. Calling functions saved in the module file.
1: /* 24L03.c: The driver file */
2: #include "24L02.h" /* include header file */
3:
4: main(void)
5: {
6: int ch;
7:
8: printf("Enter a for adding, d for deleting,\n");
9: printf("p for displaying, and q for exit:\n");
10: while ((ch=getchar()) != `q'){
11: main_interface(ch); /* process input from the user */
12: }
13:
14: list_node_free();
15: printf("\nBye!\n");
16:
17: return 0;
18: }
OUTPUT
I compile the source files, 24L01.c and 24L03.c, separately with Microsoft Visual C++, and then link
their object files and C library functions together to produce a single executable program called
24L03.exe. I have the following output shown on the screen after I run the executable 24L03.exe, and
enter or delete several student names and their ID numbers (the bold characters or numbers in the output
section are what I entered from the keyboard):
C:\app>24L03
Enter a for adding, d for deleting,
p for displaying, and q for exit:
a
Enter the student name and ID: Peter 1234
a
Enter the student name and ID: Paul 5678
a
Enter the student name and ID: Mary 7777
p
The content of the linked list:
Peter:1234 -> Paul:5678 -> Mary:7777 ->|
d
Enter the student ID: 1234
The content of the linked list:
Paul:5678 -> Mary:7777 ->|
d
Enter the student ID: 5678
The content of the linked list:
Mary:7777 ->|
d
Enter the student ID: 7777
All nodes have been deleted.
q
Bye!
C:\app>
ANALYSIS
The purpose of the program in Listing 24.3 is to provide the user with an interface. The functions, such
as list_node_create(), list_node_add(), and list_node_delete(), can be invoked through the interface. Also,
the main() function is located inside the program of Listing 24.3.
The content of a linked list node can be printed out in the format of
name:id ->
The following is an example:
Peter:1234 -> Paul:5678 -> Mary:7777 ->|
Here the sign | is used to indicate that the pointer of the last node is a null pointer.
No comments:
Post a Comment