TOPIC 16.4.2
Analysis of the Circularly-linked List Program
1 // BATORDER.CPP
2 // Example of a circularly-linked list.
3
4 // include files
5 #include <iostream.h>
6 #include <iomanip.h>
7 #include <string.h>
8
9 // global structure, variables, and constants
10 const NAME_LENGTH = 20;
11
12 struct batter_node // node for linked list
13 {
14 char batter_name[NAME_LENGTH];
15 batter_node *next; // link to next node
16 };
17
18 batter_node *first;
19 batter_node *current_batter; // pointer to current batter
20
21 // function prototypes
22 int get_batter_name(char name[NAME_LENGTH]);
23 void add_node(char name[NAME_LENGTH]);
24 void do_rotation();
25 void delete_list();
26
27 // beginning of main function
28 int main()
29 {
30 char name[NAME_LENGTH];
31
32 if(get_batter_name(name)) // prompt user for data for the node
33 {
34 first = new batter_node; // initialize list head
35 strcpy(first->batter_name, name);
36 first->next = first; // initialize next node pointer to first
37 current_batter = first;
38
39 while(get_batter_name(name))
40 {
41 add_node(name);
42 }
43 do_rotation(); // display the counties and populations
44 delete_list(); // free the memory used by the linked list
45 }
46 return 0;
47 }
48
49 // Function that gets data from user.
50 int get_batter_name(char name[NAME_LENGTH])
51 {
52 int keep_data = 1;
53
54 cout << "\nEnter batter name (Press Enter alone to stop): ";
55 cin.get(name,NAME_LENGTH);
56 cin.ignore(80,'\n');
57 if(name[0] == 0)
58 {
59 keep_data = 0;
60 }
61 return(keep_data);
62 }
63
64 // Function that adds a node to the end of the linked list.
65 void add_node(char name[NAME_LENGTH])
66 {
67 batter_node *new_rec_ptr; // Declare temporary pointer for the new node.
68
69 new_rec_ptr = new batter_node; // Allocate memory for a new node and
70 // initialize pointer to point to it.
71
72 strcpy(new_rec_ptr->batter_name, name);
73 new_rec_ptr->next = first; // Set next node pointer of new node to first
74
75 current_batter->next = new_rec_ptr; // Place new node in list
76 current_batter = new_rec_ptr;
77 }
78
79 // Function that displays entire linked list.
80 void do_rotation()
81 {
82 char user_input[3];
83
84 current_batter = first; // Move current_batter to first
85 do
86 {
87 cout << "\nThe next batter is "
88 << current_batter->batter_name << ".\n";
89 cout << "\nPress Enter for next batter or Q and Enter to quit: ";
90 cin.get(user_input,3);
91 cin.ignore(80,'\n');
92 current_batter = current_batter->next;
93 } while((user_input[0] != 'Q') && (user_input[0] != 'q'));
94 }
95
96 // Function that frees the memory used by the linked list.
97 void delete_list()
98 {
99 batter_node *temp_ptr; // pointer used for temporary storage
100
101 current_batter = first; // Move current_ptr to head of the list.
102
103 do // Traverse list until the end is reached.
104 {
105 temp_ptr = current_batter->next; // Set temporary pointer to point
106 // to the remainder of the list.
107 delete current_batter; // Delete current
108 current_batter = temp_ptr;
109 } while(temp_ptr != first);
110 }
In lines 32 - 37, the main program starts by prompting the user for the name of the first batter. If a name is supplied, the link list is created containing one node, first, which is linked to itself. In lines 38 - 42, the user is then continually prompted for a batters name until q or Q is typed. If a name is entered the addnode function is called, which inserts the batter into the batting circle. It accomplishes the task, in lines 65 - 77, by first creating a temporary pointer, and assigning it to the newly created batter_node. The batters name is transferred into the node in line 72. The new batter is then inserted into the linked list. In lines 73 - 76, the new node's next pointer is set to first, then the current node's next is then set to the new node to complete the link. The current pointer is then advanced to the new node, so that another batter can be inserted.
After all of the batters have been inserted, the function do_rotation is called to transverse the linked list and display all of the batters. This is done by starting at the first node, and printing out that batters name. The program then prompts the user to continue. If the user continues, the node pointer is advanced to its next node in line 92, and that batters name is printed out. This will continue around the circularly linked list until the user types q or Q.
Once the names have been printed out, it is time to deallocate memory using the function delete_list. The linked list is transversed very similarly to do_rotation, except this time instead of printing the names out, each node is deleted until the first node is reached again.