Reconstruction and preheating of linked list information management system (2) how to write the basic logic using linear discontinuous structure?

Continue to use the linear discontinuous storage structure for the preheating of reconstruction

Readers , Please move on to the previous post before reading this blog , If you only take one of these two articles , It is like boarding a boat without asking for water , Worship temples without visiting monks , I'm afraid it's hard to understand the taste , In contrast to the two articles , In a narrow sense, we can see the different processing methods of the two storage structures under the similar functions , In a broad sense, it can lead to thinking about finding generics that have nothing to do with the storage structure , To taste the similarities and differences between the two storage structures . To savor , I couldn't help saying ：“ What a mystery ”

Use linear non continuous storage structure to write a simple information management program
requirement ： Realize limited reusability from the perspective of Xiaobai
function ： Dynamically create linked lists and input data , Traverse the output , Judge whether the list is empty , Find the length of the list , insert data , Delete data , Sort by data

Code display ：

Preparatory work
Here is the beginning i The class or structure of the linked list node must be declared before the function

typedef struct Node
{
    
	int data;  
	struct Node* pNext; 
}node, *pnode;

Dynamically create linked lists
Here we need to clarify a few questions , The first is the particularity of the structure of using linked lists , I need to know the chain header pointer when processing data , To facilitate our operation ; Finally, notice that the variable we want to declare to store the header pointer is NULL To avoid the existence of wild pointers ; There is also the need to enhance the robustness of the code

pnode creat_list(void)
{
    
	int len;
	int i;
	int val;

	printf(" Please enter the number of generated linked list nodes  len = ");
	cin >> len;
	
	pnode phead = (pnode)malloc(sizeof(node));
	if (NULL == phead)
	{
    
		printf(" Distribution failed, you fucking ");
		exit(-1);
	}
	pnode ptail = phead;
	ptail->pNext = NULL;

	for (i = 0; i < len; ++i)
	{
    
		printf(" Please enter the first %d Values of nodes ：", i+1 );
		cin >> val;
		pnode pnew = (pnode)malloc(sizeof(node));
		if (NULL == pnew)
		{
    
			printf(" Allocation failed ");
			exit(-1);
		}
		pnew->data = val;
		ptail->pNext = pnew;
		pnew->pNext = NULL;
		ptail = pnew;
	}
	return phead;
}

Traverse the entire list
It's like an array , Not much bb

void traverse_list(pnode phead)
{
    
	pnode p = phead->pNext;
	while(NULL!=p)
	{
    
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("\n");
	return;
}

Judge whether the list is empty ：
This function is produced to increase the robustness of the code , So write it according to the structural characteristics of the linked list , Not much bb

bool is_Empty(pnode phead)// Sentenced to empty 
{
    
	if (NULL==phead->pNext )
		return true;
	else
		return false;
}

Find the length of the list
A linked list is one after another and the last pointer field is empty , So you understand ：

int lenght_list(pnode phead) // Calculate the length 
{
    
	pnode p = phead->pNext;
	int len=0;
	while (NULL != p)
	{
    
		++len;
		p = p->pNext;
	}
	return len;
}

Sort the data
The idea of generics is embodied here , It is different from array comparison , But the inner logic is the same

void sort_list(pnode phead)//  Sort 
{
    
	int i, j, t,len;
	len = lenght_list(phead);
	pnode p, q;
	len = lenght_list(phead);
	for (i=0,p=phead->pNext; i < len - 1;++i, p=p->pNext)
	{
    
		for (j=i+1,q=p->pNext; j < len; ++j,q = q->pNext)
		{
    
			if (p->data> q->data)  // Similar to... In an array a[i]>a[j]
			{
    
				t = p->data; 
				p->data = q->data;
				q->data = t;
			}
		}
	}
	return;
}

insert data
Compare it with an array , Here is an algorithm borrowed from Grandma Yan , I have to write more and practice more

// stay phead Point to pos Insert a new node in front of a node , The value of this node is val, also pos The value of is from the beginning 
bool insert_list(pnode phead, int pos, int val)
{
    
	int i = 0;
	pnode p = phead;
	while (NULL != p && i<pos-1)
						
	{
    
		p = p->pNext;
		++i;
	}
	if (i > pos - 1 || NULL == p)// i>pos-1 It's to judge pos Negative or not 
		return false;
	pnode pnew = (pnode)malloc(sizeof(node));
	if (NULL == pnew)
	{
    
		printf(" There was no surplus food in the landlord's house \n");
		exit(-1);
	}
	pnew->data = val;
	pnode q = p->pNext;
	p->pNext = pnew;
	pnew->pNext = q;
	return true;
}

Delete data
This is very simple , Note that you want to release the deleted node

bool delete_list(pnode phead, int pos, int * pval)
{
    
	int i = 0;
	pnode p = phead;
	while (NULL != p->pNext && i < pos - 1)
	{
    
		p = p->pNext;
		++i;
	}
	if (i > pos - 1 || NULL == p->pNext)
		return false;
	pnode q = p->pNext;
	*pval = q->data;
	// Delete p The node behind the node 
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
}

Source code ：

#include<stdio.h>
#include<malloc.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct Node
{
    
	int data;  
	struct Node* pNext; 
}node, *pnode;
// Function declaration 
pnode creat_list(void);// Dynamically create linked lists 
void traverse_list(pnode phead); // Traverse the entire list 
bool is_Empty(pnode phead);// Determine whether it is null 
// Judge whether it is full 
int lenght_list(pnode phead);// Find the length of the list 
bool insert_list(pnode phead, int pos, int val);
				
bool delete_list(pnode phead, int pos, int * pval);
void sort_list(pnode phead);
int main(void)
{
    
	pnode phead = NULL; 
	phead = creat_list();//creat_list() function ： Create an acyclic single chain table , And pay the address of the head node of the linked list to phead（ Actually, it's the return header, but the address ）
	traverse_list(phead);

	if(is_Empty(phead))
		printf(" Linked list is empty. \n");
	else
		printf(" The linked list is not empty \n");
	int len = lenght_list(phead);
	printf(" The length of this linked list is %d\n", len);

	sort_list(phead);
	traverse_list(phead);

	insert_list(phead, 2, 22);
	traverse_list(phead);

	int val;
	if (delete_list(phead, 3, &val))
		printf(" Delete successful , The deleted element is ：%d\n",val);
	else
		printf(" Delete failed , The element you deleted does not exist \n");
	traverse_list(phead);

	return 0;
}
pnode creat_list(void)
{
    
	int len;//  The number of valid nodes used to store 
	int i;
	int val;// It is used to temporarily store the value of the node entered by the user 

	printf(" Please enter the number of generated linked list nodes  len = ");
	cin >> len;
	
	pnode phead = (pnode)malloc(sizeof(node));
	if (NULL == phead)
	{
    
		printf(" Distribution failed, you fucking ");
		exit(-1);
	}
	pnode ptail = phead;
	ptail->pNext = NULL;

	for (i = 0; i < len; ++i)
	{
    
		printf(" Please enter the first %d Values of nodes ：", i+1 );
		cin >> val;
		pnode pnew = (pnode)malloc(sizeof(node));
		if (NULL == pnew)
		{
    
			printf(" Distribution failed, you fucking ");
			exit(-1);
		}
		pnew->data = val;
		ptail->pNext = pnew;
		pnew->pNext = NULL;
		ptail = pnew;
	}
	return phead;
}
void traverse_list(pnode phead)
{
    
	pnode p = phead->pNext;
	while(NULL!=p)
	{
    
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("\n");
	return;
}
bool is_Empty(pnode phead)
{
    
	if (NULL==phead->pNext )
		return true;
	else
		return false;
}
int lenght_list(pnode phead) // Calculate the length 
{
    
	pnode p = phead->pNext;
	int len=0;
	while (NULL != p)
	{
    
		++len;
		p = p->pNext;
	}
	return len;
}
void sort_list(pnode phead)//  Sort 
{
    
	int i, j, t,len;
	len = lenght_list(phead);
	pnode p, q;
	len = lenght_list(phead);
	for (i=0,p=phead->pNext; i < len - 1;++i, p=p->pNext)
	{
    
		for (j=i+1,q=p->pNext; j < len; ++j,q = q->pNext)
		{
    
			if (p->data> q->data)  // Similar to... In an array a[i]>a[j]
			{
    
				t = p->data; 
				p->data = q->data;
				q->data = t;
			}
		}
	}
	return;
}
// stay phead Point to pos Insert a new node in front of a node , The value of this node is val, also pos The value of is from the beginning 
bool insert_list(pnode phead, int pos, int val)
{
    
	int i = 0;
	pnode p = phead;
	while (NULL != p && i<pos-1)
						
	{
    
		p = p->pNext;
		++i;
	}
	if (i > pos - 1 || NULL == p)/
		return false;
	pnode pnew = (pnode)malloc(sizeof(node));
	if (NULL == pnew)
	{
    
		printf(" There was no surplus food in the landlord's house \n");
		exit(-1);
	}
	pnew->data = val;
	pnode q = p->pNext;
	p->pNext = pnew;
	pnew->pNext = q;
	return true;
}
bool delete_list(pnode phead, int pos, int * pval)
{
    
	int i = 0;
	pnode p = phead;
	while (NULL != p->pNext && i < pos - 1)
	{
    
		p = p->pNext;
		++i;
	}
	if (i > pos - 1 || NULL == p->pNext)
		return false;
	pnode q = p->pNext;
	*pval = q->data;
	// Delete p The node behind the node 
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
}