CS计算机代考程序代写 Java Structures in C

Structures in C

Linked Lists

CSE 2421

Required Reading: Pointers On C, Chapter 12, Sections 12.1 through 12.2.2

Previously, we saw how to declare a struct with a pointer to a struct of the same type. This kind of struct variable can be used as a node in a linked list. The node typically has two members:
– One member, called data, is a C struct which is used to store data of interest.
– The other member, called next, is a pointer to a struct Node. For example:
struct Data {
char first_name[15];
char last_name[15];
int idNumber;
};
typedef struct Node{
struct Data student;
struct Node *next;
}Node;
The linked list will be constructed by creating a number of these nodes dynamically, one at a time, and linking them to each other with the next pointer.
Linked List Nodes

The structure of a linked list is more complicated than an array, and more work is required to construct and maintain a linked list.
Nonetheless, depending on the application, linked structures often have advantages.
Some say Linear linked structures (linked lists) are not so commonly used in real applications (I disagree), but they are simpler to construct and manipulate than binary (search) trees, so we will only work with a linear, singly-linked list here.
Binary search trees have significant advantages compared with (sorted) arrays in many cases, such as faster insertion and deletion times, but comparable search performance.

Why Use Linked Lists?

Using the nodes that we have introduced before, what else do we need to construct a linked list?
Only one thing: an additional structure Node pointer, list_head, to point to the first node in the list:
Node *list_head = NULL; /*Set list head pointer to NULL initially
to show list is empty */
We only want the Node * rather than a whole Node here to keep space efficiently.
NOTE: This is different from Java where you just use an empty node
To construct the list, we will make the list_head pointer point to the first node, the next member of the first node point to the second node, . . . . the next member of the n – 1st node point to the nth (last) node, and the next member of the nth (last) node point to no node (make it a NULL pointer).
Making the next member of the last node point to NULL will allow us to detect where the end of the list is (and avoid segmentation faults!). This is analogous to ending a character string with a NULL character.

How do we construct a linked list?

Before we look at the details of insertion into the list, we need to consider the list_head pointer more carefully.
Various functions will have to know the address in the list_head pointer in order to do things with the list (insert nodes, delete nodes, process data in the nodes, print data in the nodes, etc.).
If we make the list_head pointer a file scope (“global”) variable, we do not have to pass it as a parameter to these functions.
This, however, is currently an unacceptable way to write software and should only be done in very limited cases (this is not one of them)! Debugging and maintenance are MUCH more difficult with global variables.
You are not allowed to use file scope variables in software you write for this course.
Therefore, in general, the functions in your linked list program will have to be passed the list_head pointer, which is declared in main, as a parameter, if they need to access data in the list or modify the list in any way.
The challenge for each of you is to determine whether the list_head pointer should be passed by value or by reference to each function that requires it. 

Notes on list_head pointer

We need to think about whether the function may need to modify (change) the list_head pointer or if it only needs to read it.
If it needs to potentially modify it, we cannot pass the head pointer by value. Why?
Which functions might need to modify the head pointer? Keep this question in mind as we look at the following slides.
Notes on list_head pointer

/* Here are the necessary declarations for a Node of the type declared above, and for a head pointer */
struct Data {
char first_name[15];
char last_name[15];
int id_number;
};
typedef struct Node {
struct Data student;
struct Node *next;
}Node;

/*Initialize list_head to NULL since list is empty at first. */

Node *list_head = NULL;

Note: no structures of type Node have yet been declared or dynamically allocated, only space for a head pointer has been allocated.
Constructing the Linked List – Creating a Node

/*With the declarations above, to create a new Node, we can use the following */

Node *newNodePtr;
newNodePtr = malloc (sizeof (Node));
if (newNodePtr == NULL) {
. . . . /*The storage was NOT allocated, so print an error message and exit */
}
else {
. . . . /* The storage was allocated, and we can use the Node */
. . . . /* Call a function to get the data for the node and store it in the node */
getDataForNode(newNodePtr); /* why can we just pass the Node address?
why we don’t need to pass &newNodePtr ? */
}
/* then we can put this new Node into the linked list */
insertNode(&list_head, newNodePtr);

Note: When we read the data from input which is to be stored in the node, we can read it directly into the node (how?), rather than storing it in another variable, and then assigning that variable to the node.
Constructing the Linked List – Creating a Node

If we want to insert a node into the list, what do we need to do?
We will assume that the nodes in the list will be ordered in ascending order based on some member in the data member of the node (assume it’s an integer).
First, we have to create the new node (as shown above), and initialize the members of the data member of the Node
Then, we have to call the insert function, and pass it the current list (how?), and the new node (how?).
In the insert function, declare a pointer to traverse (go through) the list:
Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points to, so that you start looking at the beginning of the list.
How might we do these things??
How to Insert Nodes into a Sorted List

If we want to insert a node into the list, what do we need to do?
We will assume that the nodes in the list will be ordered in ascending order based on some member in the data member of the node (assume it’s an integer).
First, we have to create the new node (as shown above), and initialize the members of the data member of the Node
Then, we have to call the insert function, and pass it the current list (how?), and the new node (how?). insert(&list_head, newNodePtr);
Prototype for insert function would be
insert(Node **list_head_ptr, Node *newNodePtr);
In the insert function, declare a pointer to traverse (go through) the list:
Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points to, so that you start looking at the beginning of the list.
traversePtr = *list_head_ptr;
How to Insert Nodes into a Sorted List

When we traverse the list to determine where to insert, there are three possible cases or situations:

The list is empty (list_head is a NULL pointer).
– To insert, make list_head point to the inserted node. That is, list_head = address of node we wish to insert.
*list_head_ptr = newNodePtr;
– Make the next pointer of the inserted node point to NULL (it may have been initialized to NULL during data entry, but if not, this needs to be done here).
newNodePtr->next = NULL;
How to Insert Nodes into a Sorted List

list_head_ptr list_head

newNodePtr NULL

Inserting a Node
NULL

*list_head_ptr = newNodePtr;
list_head_ptr list_head

newNodePtr NULL

Inserting a Node

2) The list already has one or more nodes and the new node needs to be inserted as the first node in the list.
– How?
IN THIS ORDER
A. The current address in list_head must be copied to the *next member in the newNodePtr structure
newNodePtr->next = *list_head_ptr;

B. The value of list_head must be changed to the address of newNodePtr.

*list_head_ptr = newNodePtr;
How to Insert Nodes into a Sorted List (cont.)

newNodePtr->next = *list_head_ptr;
list_head_ptr list_head

newNodePtr
NULL

At this point, both list_head and newNodePtr->next point to the same place

Inserting a Node:Step 1

*list_head_ptr = newNodePtr;
list_head_ptr list_head

newNodePtr
NULL

Now list_head points to newNodePtr;and
newNodePtr->next points to all following Nodes

Inserting a Node:Step 2

3. Non-exception case. i.e. The new Node belongs somewhere between two existing Nodes.
– we traverse the list to search for where to insert the node. To do so,
we must maintain a pointer to the node before the node where we are
(see below):
Node *priorNode;
– use the traversePtr previously declared to point to the Node we are
currently looking at
– So, traverse the list, node by node, to find out the correct place to insert the node based on our sort key;
advance traversePtr and priorNode through the list.
– When traversing, we need to check that the traverse pointer is not NULL before trying to access members of the node to which it points. If it is NULL, we have reached the end of the list, and should insert the new node there (as described below).
– When the correct place is found, change these pointers (in this order!):
a. The next pointer of the node to be inserted:
newNodePtr->next = traversePtr;
b. The next pointer of the node after which the new node is being inserted (this is priorNode->next): priorNode->next = newNodePtr;

How to Insert Nodes into a Sorted List (cont.)

priorNode traversePtr

newNodePtr

Inserting a Node

next
next
next

newNodePtr->next = traversePtr;
priorNode traversePtr

newNodePtr

At this point both priorNode and newNodePtr point to traversePtr

Inserting a Node: Step 1

next
next
next

priorNode->next = newNodePtr;
priorNode traversePtr

newNodePtr

At this point newNodePtr is inserted in the linked list

Inserting a Node: Step 2

next
next
next

If we want to delete a node from the list, what do we need to do?
Declare a pointer to traverse the list:
Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points to.
traversePtr = *list_head_ptr;

How to Delete Nodes from the List

When we traverse the list to find the node to be deleted, there are 3 possible situations:

1. The list is empty: ERROR – There are no nodes, so there is nothing to be deleted! Print an error message informing the user that they have tried to delete a non-existent node.

How to Delete Nodes from the List cont.

2. Node to delete is at the front of the linked list
– Check to see if the node to be deleted is the first node. If so, in order to delete it, do these things, in this order:
Make the list_head pointer point to the same thing as
traversePtr->next, then free(traversePtr);

*list_head_ptr = traversePtr->next;
free(traversePtr);
How to Delete Nodes from the List

list_head_ptr list_head

traversePtr

Deleting a Node

*list_head_ptr = traversePtr->next;
list_head_ptr list_head

traversePtr

Deleting a Node: Step 1

free(traversePtr);
list_head_ptr list_head

Deleting a Node: Step 2

3. Non-exception case. i.e. The Node to delete is somewhere between two existing Nodes or at the end. Both cases can be handled this way.
– traverse the list to search for the node to be deleted, we must maintain a pointer to the node before the node where we are:
struct Node *priorNode;
– advance traversePtr and priorNode to go through the list.
– When traversing, we need to check that the traverse pointer is not NULL before trying to access members of the node to which it points.
– If it is NULL, the node is not in the list. Print an error message to the user.
– If the node is found, do these actions in this order:
a. Change the next pointer of prior node (the node before the node which is being deleted): priorNode->next = traversePtr->next;
b. Call free() with the pointer to the node being deleted (what pointer is this?).
How to Delete Nodes from the List

priorNode traversePtr->next

traversePtr

Deleting a Node

Node to delete

next
next
next

priorNode->next = traversePtr->next;
priorNode traversePtr->next

traversePtr

At this point, both priorNode->next and traversePtr->next point to the same thing, but we’re getting ready to free traversePtr.
Deleting a Node: Step 1

Node to delete

next
next
next

Free(traversePtr);
priorNode traversePtr->next

Deleting a Node: Step 2

next
next

Besides insertion and deletion, there are some other kinds of operations we can identify on linked lists:
List traversal for some purpose:
– Find an element in the list, and print out the related data.
– Print all the items in the list.
– Do computations on the data in the list, such as totaling all the items, counting the number of items in the list, computing averages, finding minimum and maximum values, etc.
In general, traversing the list for these purposes is less complicated than it is for insertion and deletion, because we do not have to keep track of the prior node; we can declare a traversePtr and make it point to the beginning of the list and then go through the entire list.
Do you think you would need to pass the list_head by reference or by value to these type functions?
We do, however, still have to ensure that we do not try to access nodes beyond the end of the list (you should now be able to figure out how to do this)!

Related Posts