Chain List Implementation (C Language)

Catalog

What is a list of chains:

Chain lists are an example of a chain storage structure where adjacent nodes are chained together. Corresponding to a chain storage structure is a sequential storage structure, which is known as an array. A distinct feature of sequential storage structure is the need to allocate a certain amount of space in memory ahead of time. Whether there is enough space is unknown before the data is fully imported. The end result may be a waste of underutilized allocated memory space or an overflow of data due to insufficient allocated memory space. That's what we don't want to see, so chained storage emerges.

When a new node appears (the part of this node is divided into data fields and pointer fields, data fields are used to store all kinds of actual data, and pointer fields are used to store the address of the previous or next node), we only need to include this new node in the data chain. The specific method is to have each node have the address of the previous or next node, which is the chain at the beginning.

You can see that the implementation of the chain table depends on the establishment of nodes, which in turn depends on the application of the structure.

Nodes and Structures:

As mentioned earlier, each node in a chain table consists of a data field and a pointer field, which means that the corresponding structure contains variables of certain data types and pointer variables of the same type as the structure.

Take a small example:

struct stu
{
int iScore;
char cName[10];
struct stu* pNext;
};

In this structure, there is an integer variable, a string of characters, and a pointer variable of the same type as the structure.

Then we continue to define two variables stu1 and stu2 in the main() function to assign values to them:

int main()
{
	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName,"log");
	stu1.pNext = NULL;
	printf("%d %s", stu1.iScore, stu1.cName);
    
    struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;
	printf("%d %s", stu2.iScore, stu2.cName);
	
    return 0;
}

* Let's run it and get the results:

Nodes and Chains:

How do I link these two variables? We can have the pointer field of the stu1 node store the beginning of the stu2 node

Address, that is, add statement

stu1.pNext = &stu2;

The entire program becomes:

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName,"log");
	stu1.pNext = NULL;
	printf("%d %s\n", stu1.iScore, stu1.cName);
	
	struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;
	
	stu1.pNext = &stu2;
	printf("%d %s", stu1.pNext->iScore, stu1.pNext->cName);
	return 0;
}

The original purpose of this program is to print out the values stored in the data fields of the two nodes stu1 and stu2. On the basis of these operations, a chain between the two nodes has been established. Can we directly define a secondary variable of type struct stu and access the node stu2 through it and the primary node stu1?

For example:

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu_temp;

	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName, "log");
	stu1.pNext = NULL;

	struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;

	stu1.pNext = &stu2;
	stu_temp.pNext = &stu1;
	while (stu_temp.pNext != NULL)
	{
		printf("%d %s\n", stu_temp.pNext->iScore, stu_temp.pNext->cName);
		stu_temp.pNext = stu_temp.pNext->pNext;
	}
	return 0;
}

In this code, we define a temporary variable stu_temp and add stu1 address to stu_temp's pointer field, through a while loop, allows us to print out the data of all non-empty nodes in this chain in sequence.

In addition, we call stu1 the primary node, of course, the queue head node or something else. And stu_temp is called a header node. It is important to note that the data domain of the header node is a spatial domain, and its pointer domain stores the address of the header node.

The logical relationship of the diagram is:

Where the header node stu_temp has an empty data field, indicated by the Greek letter.

Head Node and Head Pointer:

The concept corresponding to a header node is a header pointer, which is optional or not. If a header node is set, the value of the header pointer is the address of the header node. If no header node is set, the value of the header pointer is the address of the queue header node.

Logical relationships are as follows:

In general, a header pointer serves as an identifier and can be used to indicate the name of a linked list. The reason for this is that when writing a program, it is easy to distinguish between two or more linked lists when reading in, modifying, or joining two linked lists with the same type of elements. Moreover, the head pointer is a necessary element of the chain table, and it is not empty whether or not the chain table is empty.

Head nodes are for convenience, and their data fields are generally meaningless before the queue head nodes. When it comes to the convenience of the first node, it is mainly reflected in the presence of the first node, which is helpful if we want to insert a new node before the queue head node or delete the queue head node to make its next node a new queue head node.

The code above changes to:

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu_temp;
	struct stu* pHead=NULL;

	struct stu stu1;
	stu1.iScore = 89;
	strcpy(stu1.cName, "log");
	stu1.pNext = NULL;

	struct stu stu2;
	stu2.iScore = 99;
	strcpy(stu2.cName, "rog");
	stu2.pNext = NULL;

	stu1.pNext = &stu2;
	stu_temp.pNext = &stu1;
	stu_temp.iScore = -1;
	pHead = &stu_temp;
	while (pHead != NULL)
	{
		if (pHead->iScore == -1)
		{
			pHead = pHead->pNext;
			continue;
		}
		printf("%d %s\n", pHead->iScore, pHead->cName);
		pHead = pHead->pNext;
	}
	return 0;
}

pHead is our defined header pointer. After initial values are assigned to the stu1 and stu2 nodes, we store the address of stu2 in the pointer field of stu1 and the address of stu1 in stu_temp's pointer field, and stu_ The value of iScore in temp's data domain is set to -1 to indicate that it is a header node.

Multi-node chain table:

In the previous section, we see that when fewer nodes are connected, it is possible to define the nodes and then connect them. However, when the number of nodes we want to connect is not in a specific range, the amount of work we need to do is uncertain. You might say that we can allocate a fixed amount of memory to store this data, which goes back to the sequential storage structure we mentioned at the beginning of this article and violates the goal of building a chain storage structure.

Then we can define only one variable representing the node, assign new values to the node, and then incorporate the node into the existing chain. According to the previous thought, the link between existing n nodes is established, while the new idea is to establish a new node and then incorporate it into the chain composed of the first n nodes.

This means that we need to reuse the same variable to open up new nodes, that is, to keep opening up space in a way that does not define new variables. That's a bit frustrating. Let's take the code above as an example. We've developed two nodes, stu1 and stu2, by defining these two variables. If we're going to define a series of nodes, stu3 and stu4...... stu n, we'll have n statements defining variables, which are repetitive and verbose. The purpose of defining variables is to open up memory space for these n nodes. If there is another way that we can open up memory space for each node in a less verbose way, it must be something else.

* We can use <stdlib. The functions malloc() or calloc() in h> open up a certain amount of memory space, of which malloc() functions are commonly used.

The full name of malloc is memory allocation, which is called in Chinese Dynamic memory allocation To apply for a contiguous block area of specified size to void * Type returns the allocated memory area address when it is unknown Memory When it comes to specific locations, you want to bind the real Memory space Dynamic memory allocation is required and the allocated size is the size required by the program. Normally it is paired with the free function. The free function releases a dynamically allocated address, indicating that the dynamically allocated memory is no longer used and returns previously dynamically requested memory to the system. ———— Baidu

The prototype of the malloc() function is:

void *malloc(unsigned int size);

The return value is a pointer of the specified type.

For example, use the malloc() function to allocate an integer memory space:

int *pInt;

pInt=(int*)malloc(sizeof(int));

Notice that malloc() is preceded by a pointer type to which the return value is converted, and the number of bytes in parentheses is the data type.

The calloc() function adds a parameter n to the malloc() function, which is prototyped as:

void *calloc(unsigned n,unsigned size);

This means to allocate contiguous memory space of n block size byte size, somewhat like an array.

Using the malloc() function, we can change the above code to:

#include<stdio.h>
#include<string.h>
struct stu
{
	int iScore;
	char cName[10];
	struct stu* pNext;
};
int main()
{
	struct stu stu_temp;
	struct stu* pHead=NULL;

	struct stu* stu_new=(struct stu*)malloc(sizeof(struct stu));
	struct stu* stu_end=NULL;

	stu_temp.pNext = stu_new;
	//Connect a queue head node to a head node
	stu_temp.iScore = -1;
	pHead = &stu_temp;

	while (scanf("%d", &stu_new->iScore)&&stu_new->iScore != -1)
	//Input-1, cycle stops
	{
		scanf("%s", stu_new->cName);
		stu_end = stu_new;
		stu_new= (struct stu*)malloc(sizeof(struct stu));
		stu_end->pNext = stu_new;
	}

	stu_end->pNext = NULL;
	free(stu_new);

	printf("Print results:\n");
	while (pHead != NULL)
	{
		if (pHead->iScore == -1)
		{
			pHead = pHead->pNext;
			continue;
		}
		printf("%d %s\n", pHead->iScore, pHead->cName);
		pHead = pHead->pNext;
	}
	return 0;
}

Let's print the output first:

Note: stu_in the code above New, stu_end is a pointer to a particular node. For convenience, the name of a particular node is the name of the pointer to that particular node, such as the pointer stu_that will point to a particular node. New as the name of that particular node.

The following statements are the most important:

while (scanf("%d", &stu_new->iScore)&&stu_new->iScore != -1)
	//Input-1, cycle stops
	{
		scanf("%s", stu_new->cName);
		stu_end = stu_new;
		stu_new= (struct stu*)malloc(sizeof(struct stu));
		stu_end->pNext = stu_new;
	}

	stu_end->pNext = NULL;
	free(stu_new);

This statement is used to open up a new node stu_new, and after setting the data field for the new node, stu_end serves as another name for the node, then continues to open up a new memory space using the following statement:

stu_new= (struct stu*)malloc(sizeof(struct stu));

After successful development, use stu_ Newto name this new space, that is, the name of this new node is stu_new. Take another look at the termination conditions for this loop:

while (scanf("%d", &stu_new->iScore)&&stu_new->iScore != -1)

Place the following assignment in this termination condition to easily pass stu_after New->iScore equals -1 to decide whether to terminate, so only if we are stu_ New->iScore assigns a value other than -1 to open a new node and incorporate it into the old chain:

scanf("%d", &stu_new->iScore)

When jumping out of the loop, the iScore of the data field of this new node is -1. We do not need this new node, nor do we need to include it in the old chain. The last node of an existing old chain is stu_end, we set its pointer field to NULL, which means stu_ The end is no longer connected to the new node, and the space we will open for the new node is returned to the system with the following statement: