当前位置：网站首页>C - linear table

C - linear table

2022-07-07 23:43:00 【Min, Hello, Xun】

List of articles

Basic concept of linear table

Basic concepts

  • A linear table is a finite sequence of zero or more data elements .
  • characteristic ：
    Insert picture description here

Mathematical definition

  • Definition
    Insert picture description here
  • nature
    Insert picture description here

Sequential storage of linear tables

Concept of sequential storage

Insert picture description here

Design and implementation of linear table sequential storage

  • Case study ： The dynamic array
    Insert picture description here

Example ：

  1. Create header file ——DynamicArray.h
#pragma once// Prevent header files from repeatedly containing 
//#ifndef DYNAMIC_ARRAY_H
//#define DYNAMIC_ARRAY_H


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// Statement 
// Put some interfaces in the header file 

// Dynamically growing memory , Put the data on the heap 

// Dynamic array structure definition 
typedef struct DYNAMICARRAY
{
    
	int* pAdder;// The address where the data is stored 
	int size;// Number of current elements 
	int capacity;// Capacity , How many elements can the container currently hold 
}Dynamic_Array;

// Write about DYNAMICARRAY Function of structure operation 
// initialization 
Dynamic_Array* Init_Array();
// Insert 
void Push_Array(Dynamic_Array* arr, int value);
// Delete... According to location 
void RemoveByPos_Arrray(Dynamic_Array* arr, int pos);
// Delete... Based on value 
void RemoveByValue_Array(Dynamic_Array* arr, int value);
// lookup 
 int Find_Array(Dynamic_Array* arr, int value);
 // Print 
 void Printf_Array(Dynamic_Array* arr);
// Free up memory for dynamic arrays 
void FreeSpace_Array(Dynamic_Array* arr);
// Empty array 
void Clear_Array(Dynamic_Array* arr);
// Get dynamic array capacity 
int Capacity_Array(Dynamic_Array* arr);
// Get the current number of elements of the dynamic array 
int Size_Array(Dynamic_Array* arr);
// Get a location element based on the location 
int At_Array(Dynamic_Array* arr, int pos);

//#endif
  1. establish DynamicArray.c Source file , Write each function 
#include"DynamicArray.h"

// initialization 
Dynamic_Array* Init_Array()
{
    
	Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array));
	myArray->size = 0;
	myArray->capacity = 20;
	myArray->pAdder = (int*)malloc(sizeof(int)*myArray->capacity);
	return myArray;
}


// Insert 
void Push_Array(Dynamic_Array* arr, int value)
{
    
	if (arr == NULL)
	{
    
		return ;
	}
	// Judge whether there is enough space 
	if (arr->size == arr->capacity)
	{
    
		// First step , Open up a larger space  , The new space is just space 2 times 
		int* newpAdder= (int*)malloc(sizeof(int)*arr->capacity * 2);
		// The second part copies data 
		memcpy(newpAdder, arr->pAdder, arr->capacity * sizeof(int));
		// Free up space 
		free(arr->pAdder);
		// Update capacity 
		arr->capacity = arr->capacity * 2;
		arr->pAdder = newpAdder;
		
	}
	//  Insert new elements 
		arr->pAdder[arr->size] = value;
		arr->size++;
}


// Delete... According to location 
void RemoveByPos_Arrray(Dynamic_Array* arr, int pos)
{
    

	if (arr == NULL)
	{
    
		return ;
	}
	// Determine if the location is valid 
	if (pos < 0 || pos >= arr->size)
	{
    
		return;
	}
	// Remove elements 
	for (int i = pos; i < arr->size - 1; i++)
	{
    
		arr->pAdder[i] = arr->pAdder[i + 1];
	}
	arr->size--;
}


// Delete... Based on value value（ When it first appeared ）
void RemoveByValue_Array(Dynamic_Array* arr, int value)
{
    
	if (arr == NULL)
	{
    
		return ;
	}
	// Find the location of the value 
	int pos= Find_Array(arr,value);
	
	// Delete... According to location , Call the location deletion function 
	RemoveByPos_Arrray(arr, pos);
}


// lookup 
int Find_Array(Dynamic_Array* arr, int value)
{
    
	if (arr == NULL)
	{
    
		return -1;
	}
	int pos = -1;
	for (int i = 0; i < arr->size; i++)
	{
    
		if (arr->pAdder[i] == value)
		{
    
			pos = i;
			break;
		}
	}
	return pos;
}


// Print 
void Printf_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return;
	}
	for (int i = 0; i < arr->size; i++)
	{
    
		printf("%d ", arr->pAdder[i]);
	}
	printf("\n");
}


// Free up memory for dynamic arrays 
void FreeSpace_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return;
	}
	if (arr->pAdder != NULL)
	{
    
		free(arr->pAdder);
		
	}
	free(arr);
}


// Empty array 
void Clear_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return ;
	}
	arr->size = 0;
}


// Get dynamic array capacity 
int Capacity_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return -1;
	}
	return arr->capacity;
}


// Get the current number of elements of the dynamic array 
int Size_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return -1;
	}
	return arr->size;
}


// Get a location element based on the location 
int At_Array(Dynamic_Array* arr, int pos)
{
    
	return arr->pAdder[pos];
}
  1. establish 01 The dynamic array .c Source file , To test 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include"DynamicArray.h"

void test01()
{
    
	// Initializing dynamic arrays 
	Dynamic_Array* myArray=Init_Array();

	printf(" Array capacity ：%d\n", Capacity_Array(myArray));
	printf(" Array size ：%d\n", Size_Array(myArray));
	
	// Insert elements 
	for (int i = 0; i <30; i++)
	{
    
		Push_Array(myArray, i);
	}
	Printf_Array(myArray);
	printf(" Array capacity ：%d\n", Capacity_Array(myArray));
	printf(" Array size ：%d\n", Size_Array(myArray));

	RemoveByPos_Arrray(myArray, 2);
	RemoveByValue_Array(myArray, 8);
	// Print 
	Printf_Array(myArray);
	// Look for the element 5 The location of 
	int pos = Find_Array(myArray, 5);
	printf(" Elements 5 The location of the for ：%d\n", pos);

	// Release 
	FreeSpace_Array(myArray);
}
int main()
{
    
	test01();
	system("pause");
	return 0;
}

result ：

 Array capacity ：20
 Array size ：0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 Array capacity ：40
 Array size ：30
0 1 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 Elements 5 The location of the for ：4

Chain storage of linear table

Basic concepts

Insert picture description here

Design and implementation of single linked list

  • The data field and pointer field of one-way linked list are put together , When inserting a new node , We need to open up new space to create new nodes .
    The process of inserting elements at specified positions
    Insert picture description here
  • Example ： Single item list
  1. Create a header file first ,LinkList.h The header file 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// List nodes 
typedef struct LINKNODE
{
    
	void* data;// A typeless pointer can point to the address of any type of data 
	struct LINKNODE* next;
}LinkNode;

// List structure 
typedef struct LINKLIST
{
    
	LinkNode* head;// Head node , It belongs to structure nesting  
	int size;// Number of current elements 
	// The linked list does not need to set the capacity in advance 
}LinkList;

// Print function pointer 
typedef void(*PRINTLINKNODE)(void*);//typedef Define function pointers 
// Initialize linked list 
LinkList* Init_LinkList();
// Insert... At specified location 
void Insert_LinkList(LinkList* list, int pos, void* data);
// Delete the value at the specified location 
void RemoveByPos_LinkList(LinkList* list,int pos);
// Get the length of the list 
int Size_LinkList(LinkList* list);
// lookup 
int Find_LinkList(LinkList* list, void* data);
// Return to the first node 
void* Front_LinkList(LinkList* list);
// Print linked list node 
void Print_LinkList(LinkList* list, PRINTLINKNODE print);//???
// Free up linked list memory 
void FreeSpace_LinkList(LinkList* list);
  1. Build a LinkList.c The source file , Write each function 
#include"LinkList.h"


// Initialize linked list 
LinkList* Init_LinkList()// Maintenance structure , Operate the structure 
{
    
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->head = 0;
	// Make room for the head node , The header node does not save data information 
	list->head = (LinkNode*)malloc(sizeof(LinkNode));
	// Head node initialization , The next node of the head node is the first node of the linked list 
	list->head->data = NULL;
	list->head->next = NULL;
	return list;
}


// Insert... At specified location 
void Insert_LinkList(LinkList* list, int pos, void* data)
{
    
	if (list ==NULL ||data==NULL)
	{
    
		return;
	}
	// about pos Friendly handling of cross-border 
	if (pos<0 || pos>list->size)
	{
    
		pos = list->size;
	}
	// Create a new node 
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	newnode->data = data;
	newnode->next = NULL;
	// Find nodes , Auxiliary pointer variable 
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
    
		pCurrent = pCurrent->next;
	}
	// Insert the new node into the linked list 
	newnode->next = pCurrent->next;
	pCurrent->next = newnode;

	list->size++;
}


// Delete the value at the specified location 
void RemoveByPos_LinkList(LinkList* list, int pos)
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
    
		return;
	}
	// Find the previous node of the node to be deleted 
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
    
		pCurrent = pCurrent->next;
	}
	// Cache deleted nodes 
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;
	// Release the memory of deleting nodes 
	free(pDel);
	list->size--;
}


// Get the length of the list 
int Size_LinkList(LinkList* list)
{
    
	return list->size;
}


// lookup 
int Find_LinkList(LinkList* list, void* data)
{
    
	if (list == NULL)
	{
    
		return -1;
	}
	if (data == NULL)
	{
    
		return -1;
	}
	LinkNode* pCurrent = list->head->next;
	int i=0;
	while (list != NULL)
	{
    
		if (pCurrent->data == data)
		{
    
			break;
		}
		i++;
		pCurrent = pCurrent->next;
	}	
	return i;
}


// Return the element of the first node 
void* Front_LinkList(LinkList* list)
{
    
	return list->head->next->data;
}


// Print the elements of the linked list node 
void Print_LinkList(LinkList* list, PRINTLINKNODE print)//???
{
    
	if (list == NULL)
	{
    
		return;
	}
	// Auxiliary pointer variable 
	LinkNode* pCurrent = list->head->next;
	while (pCurrent != NULL)
	{
    
		print(pCurrent->data);// Call function 
		pCurrent = pCurrent->next;
	}
}


// Free up linked list memory 
void FreeSpace_LinkList(LinkList* list)
{
    
	if (list == NULL)
		return;
	// Auxiliary pointer variable , Release node memory first 
	LinkNode* pCurrent = list->head;
	while (pCurrent!=NULL)
	{
    
		// Cache the next node , Otherwise, each traversal will release one , It will be difficult to find the next node 
		LinkNode* pNext = pCurrent->next;
		free(pCurrent);
		pCurrent = pNext;
	}
	// Release list 
	list->size = 0;
	free(list);
}
  1. establish 02 Single item list .c Source file , To test 
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include"LinkList.h"

// Custom data types 
typedef struct PERSON
{
    
	char name[21];
	int age;
	int score;
}person;

// Print function 
void myPrint(void* data)
{
    
	person* p = (person*)data;
	printf(" name ：%s  Age ：%d  achievement ：%d\n", p->name, p->age, p->score);
}
int main()
{
    
	// Create a list of 
	LinkList* list = Init_LinkList();
	// Create data types 
	person p1 = {
     " Zhang San ",18,98 };
	person p2 = {
     " Li Si ",16,89 };
	person p3 = {
     " Wang Wu ",15,99 };
	person p4 = {
     " Liu Liu ",19,86 };
	person p5 = {
     " Chen Qi ",23,87 };
	// Data insertion linked list 
	printf("------------- Insert --------------\n");
	Insert_LinkList(list, 0, &p1);
	Insert_LinkList(list, 0, &p2);
	Insert_LinkList(list, 0, &p3);
	Insert_LinkList(list, 0, &p4);
	Insert_LinkList(list, 0, &p5);
	// Print 
	Print_LinkList(list, myPrint);

	// lookup 
	printf("------------- lookup ---------------\n");
	int pos=Find_LinkList(list, &p2);// When calling a function with a return value , To set the return value 
	printf(" The element position searched is ：%d\n",pos );
	
	// Delete 
	printf("-------------- Delete location 3 The elements of ---------------\n");
	RemoveByPos_LinkList(list, 3);
	Print_LinkList(list,myPrint);
	
	// Return to the first node 
	printf("----------------- Return the first node element --------------\n");
	person* ret = Front_LinkList(list);
	printf(" full name ：%s  Age ：%d  achievement ： %d\n", ret->name, ret->age, ret->score);
	// Release list 
	FreeSpace_LinkList(list);


	return 0;
}

result ：

------------- Insert --------------
 name ： Chen Qi   Age ：23  achievement ：87
 name ： Liu Liu   Age ：19  achievement ：86
 name ： Wang Wu   Age ：15  achievement ：99
 name ： Li Si   Age ：16  achievement ：89
 name ： Zhang San   Age ：18  achievement ：98
------------- lookup ---------------
 The element position searched is ：3
-------------- Delete location 3 The elements of ---------------
 name ： Chen Qi   Age ：23  achievement ：87
 name ： Liu Liu   Age ：19  achievement ：86
 name ： Wang Wu   Age ：15  achievement ：99
 name ： Zhang San   Age ：18  achievement ：98
----------------- Return the first node element --------------
 full name ： Chen Qi   Age ：23  achievement ： 87

Design and implementation of enterprise linked list

  • The data field and pointer field of the enterprise linked list are separated , And less code .
    Example ： Enterprise linked list
  1. Build a LinkList.h The header file 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// Summary of the list 
typedef struct LINKNODE
{
    
	struct LINKNODE* next;
}LinkNode;

// Link list node 
typedef struct LINKLIST
{
    
	LinkNode head;
	int size;
}LinkList;


// Define print function pointer 
typedef void(*PRIENTFNODE)(LinkNode*);
// Compare function pointers 
typedef int(*COMPARENODE)(LinkNode*, LinkNode*);

// initialization 
LinkList* Init_LinkList();
// Insert 
void Insert_LinkList(LinkList* list, int pos, LinkNode* data);// The inserted data is LinkNode* Type of 
// Delete 
void Remove_LinkList(LinkList* list, int pos);
// lookup 
int Find_LinkList(LinkList* list, LinkNode* data,COMPARENODE compare);
// Return the size of the list 
int Size_LinkList(LinkList* list);
// Print 
void Printf_LinkList(LinkList* list, PRIENTFNODE printf);
// Free up linked list memory 
void Free_LinkList(LinkList* list);
  1. Build a LinkList.c The source file 
#include"LinkList.h"



// initialization 
LinkList* Init_LinkList()
{
    
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->head.next = NULL;
	list->size = 0;
	return list;
}


// Insert 
void Insert_LinkList(LinkList* list, int pos, LinkNode* data)// The inserted data is LinkNode* Type of 
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (data == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>list->size)
	{
    
		pos = list->size;
	}
	// Insert new node 
	LinkNode* pcurrent = &(list->head);// Because in LinkList.h In the definition of LinkList when ,head It's not a pointer type , So it should be converted to address type 
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	// Insert new node 
	data->next = pcurrent->next;
	pcurrent->next = data;
	list->size++;
}


// Delete 
void Remove_LinkList(LinkList* list, int pos)
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>list->size)
	{
    
		return;
	}
	// Auxiliary nodes 
	LinkNode* pcurrent = &(list->head);
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	// Delete node 
	pcurrent->next = pcurrent->next->next;
	list->size--;

}


// lookup 
int Find_LinkList(LinkList* list, LinkNode* data, COMPARENODE compare)
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (data == NULL)
	{
    
		return;
	}
	LinkNode* pcurrent = list->head.next;
	int index = 0;
	while (pcurrent != NULL)
	{
    
		if (compare(pcurrent, data) == 0)
		{
    
			break;
		}
		pcurrent = pcurrent->next;
		index++;
	}
	return index;
}


// Return the size of the list 
int Size_LinkList(LinkList* list)
{
    
	return 0;
}


// Print 
void Printf_LinkList(LinkList* list, PRIENTFNODE printf)
{
    
	if (list == NULL)
	{
    
		return;
	}
	// Auxiliary pointer 
	LinkNode* pcurrent = list->head.next;
	while (pcurrent != NULL)
	{
    
		printf(pcurrent);
		pcurrent = pcurrent->next;
	}
}


// Free up linked list memory 
void Free_LinkList(LinkList* list)
{
    
	if (list == NULL)
	{
    
		return;
		free(list);
	}
}
  1. Build a 03 Enterprise linked list .c The source file , To test 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkList.h"

typedef struct PERSON
{
    
	LinkNode node;
	char name[21];
	int age;
}person;
void myprintf(LinkNode* data)
{
    
	person* p = (person*)data;
	printf(" full name ：%s  Age ：%d\n", p->name, p->age);
}
int main()
{
    
	// Create a linked list 
	LinkList* list = Init_LinkList();
	// Create data 
	/*person p1 = { " Zhang San ",18 }; person p2 = { " Li Si ",19 }; person p3 = { " Wang Wu ",17 };*/   // You can't write it like that , because person There is also a definition node

	person p1, p2, p3;
	strcpy(p1.name, " Zhang San ");
	strcpy(p2.name, " Li Si ");
	strcpy(p3.name, " Wang Wu ");
	p1.age = 18;
	p2.age = 17;
	p3.age = 19;
	// Insert the node into the linked list 
	Insert_LinkList(list, 0, (LinkNode*)&p1);
	Insert_LinkList(list, 0, (LinkNode*)&p2);
	Insert_LinkList(list, 0, (LinkNode*)&p3);
	
	
	// Print 
	Printf_LinkList(list, myprintf);

	// Delete node 
	Remove_LinkList(list, 1);
	printf(" Delete 1 The linked list element after the node of the position is ：\n");
	Printf_LinkList(list, myprintf);
	// Free up linked list memory 
	Free_LinkList(list);
}

result ：

 full name ： Wang Wu   Age ：19
 full name ： Li Si   Age ：17
 full name ： Zhang San   Age ：18
 Delete 1 The linked list element after the node of the position is ：
 full name ： Wang Wu   Age ：19
 full name ： Zhang San   Age ：18

Design and implementation of circular linked list

Insert picture description here
Example ：

  1. Build a CircleLinkList.h The header file 
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define CIRCLELINKLIST_TRUE 1 // Macro definition 
#define CIRCLELINKLIST_FALSE 0

typedef struct CIRCLELINKNODE
{
    
	struct CIRCLELINKNODE* next;
	
}CircleLinkNode;
typedef struct CIRCLELINKLIST
{
    
	CircleLinkNode head;
	int size;
}CirecleLinkList;

typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);// Compare callback 

typedef void(*PRINTFNODE)(CircleLinkNode*);// Print callback 

// Write... For the operation of the linked list structure API function 

// Initialization function 
CirecleLinkList* Init_CircluLinkList();
// Insert the function 
void Insert_CircluLinkList(CirecleLinkList* clist, int pos, CircleLinkNode*data);
// Get the first element 
CircleLinkNode* Front_CircleLinkList(CirecleLinkList* clist);
// Delete elements according to location 
void RemovByPos_CircleLinkList(CirecleLinkList* clist, int pos);
// Delete elements... Based on values 
void RemoveByValue_CircleLinkList(CirecleLinkList* clist, CircleLinkNode*data,COMPARENODE compare);
// Get the length of the list 
int Size_CircleLinkList(CirecleLinkList* clist);
// Determine whether it is null 
int IsEmpty_CircleLinkList(CirecleLinkList* clist);
// lookup 
int Find_CiecleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
// Print node 
void Printf_CircleLinkList(CirecleLinkList* clist, PRINTFNODE print);
// Free memory 
void FreeSpace_CircleLinkList(CirecleLinkList* clist);
  1. Build a CircleLinkList.c Source file 
#include "CircleLinkList.h"

// Initialization function 
CirecleLinkList* Init_CircluLinkList()
{
    
	CirecleLinkList* clist = (CirecleLinkList*)malloc(sizeof(CirecleLinkList));
	clist->size = 0;
	clist->head.next = &(clist->head);
	return clist;
}


// Insert the function 
void Insert_CircluLinkList(CirecleLinkList* clist, int pos, CircleLinkNode*data)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	if (data == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>clist->size)
	{
    
		pos = clist->size;
	}
	// Find the node according to the location 
	// Auxiliary pointer variable 
	CircleLinkNode* pcurrent = &(clist->head);
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	// New data into the linked list 
	data->next = pcurrent->next;
	pcurrent->next = data;
	clist->size++;
}


// Get the first element 
CircleLinkNode* Front_CircleLinkList(CirecleLinkList* clist)
{
    
	
	return clist->head.next;
}


// Delete elements according to location 
void RemovByPos_CircleLinkList(CirecleLinkList* clist, int pos)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>clist->size)
	{
    
		return;
	}
	CircleLinkNode* pcurrent = &(clist->head);
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	// Cache the next node of the current node , That is, the node to be deleted 
	CircleLinkNode* pnext = pcurrent->next;
	pcurrent->next = pnext->next;
	clist->size--;
}


// Delete elements... Based on values 
void RemoveByValue_CircleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	if (data == NULL)
	{
    
		return;
	}
	// This is a circular list 
	CircleLinkNode* pprev = &(clist->head);
	CircleLinkNode* pcurrent = pprev->next;
	for (int i = 0; i < clist->size; i++)
	{
    
		if (compare(pcurrent,data) == CIRCLELINKLIST_TRUE)
		{
    
			pprev->next = pcurrent->next;
			break;
		}
		pprev=pcurrent;
		pcurrent = pprev->next;
	}
	clist->size--;

}


// Get the length of the list 
int Size_CircleLinkList(CirecleLinkList* clist)
{
    
	return clist->size;
}


// Determine whether it is null 
int IsEmpty_CircleLinkList(CirecleLinkList* clist)
{
    
	if (clist->size == 0)
	{
    
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}


// lookup 
int Find_CiecleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{
    
	if (clist == NULL)
	{
    
		return -1;
	}
	if (data == NULL)
	{
    
		return -1;
	}
	CircleLinkNode* pcurrent = clist->head.next;
	int flag = -1;
	for (int i = 0; i < clist->size;i++)
	{
    
		if (compare(pcurrent, data) == CIRCLELINKLIST_TRUE)
		{
    
			flag = i;
			break;
		}
		pcurrent = pcurrent->next;
	}
	return flag;
}


// Print node 
void Printf_CircleLinkList(CirecleLinkList* clist, PRINTFNODE print)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	// Auxiliary pointer variable 
	CircleLinkNode* pcurrent = clist->head.next;
	for (int i = 0; i < clist->size; i++)// If you print it twice, you have to multiply it 2, We still need to judge , Is it the head node （ Because it's a circular list ）
	{
    
		if (pcurrent == &(clist->head))
		{
    
			pcurrent = pcurrent->next;// Judge if it is a header node   Then point to the next node , Because the header node does not store data 
			printf("-----------------------\n");
		}
		print(pcurrent);
		pcurrent = pcurrent->next;
	}
}


// Free memory 
void FreeSpace_CircleLinkList(CirecleLinkList* clist)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	free(clist);
}
  1. Build a 01 Circular linked list .c The source file , Perform functional tests 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"CircleLinkList.h"



typedef struct PERSON
{
    
	CircleLinkNode node;
	char name[21];
	int age;
	int score;
}person;

void myprintf(CircleLinkNode* data)// Preparation of callback function 
{
    
	person* p = data;
	printf(" full name ：%s  Age ：%d  achievement ：%d\n", p->name, p->age, p->score);
}

int mycompare(CircleLinkNode* data1, CircleLinkNode* data2)
{
    
	person* p1 = data1;
	person* p2 = data2;
	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age&&p1->score == p2->score)
	{
    
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}
int main()
{
    
	// Create a circular list 
	CirecleLinkList* clist = Init_CircluLinkList();

	person p1, p2, p3,p4,p5;
	strcpy(p1.name, " Zhang San ");
	strcpy(p2.name, " Li Si ");
	strcpy(p3.name, " Wang Wu ");
	strcpy(p4.name, " Liu Liu ");
	strcpy(p5.name, " Chen Qi ");
	p1.age = 20;
	p2.age = 18;
	p3.age = 21;
	p4.age = 19;
	p5.age = 22;
	p1.score = 98;
	p2.score = 97;
	p3.score =99;
	p4.score = 87;
	p5.score = 90;

	// Insert , Data into linked list 
	Insert_CircluLinkList(clist,100, (CircleLinkNode*)&p1);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p2);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p3);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p4);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p5);

	// Print 
	Printf_CircleLinkList(clist, myprintf);


	// Delete... Based on value 
	/*person pdel; strcpy(pdel.name, " Wang Wu "); pdel.age = 21; pdel.score = 99; RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&pdel, mycompare);*/ //==

	RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&p3, mycompare); //==
	printf(" The deleted linked list is ：\n");
	Printf_CircleLinkList(clist, myprintf);
	// Free memory 
	FreeSpace_CircleLinkList(clist);

	return 0;
}

result ：

 full name ： Zhang San   Age ：20  achievement ：98
 full name ： Li Si   Age ：18  achievement ：97
 full name ： Wang Wu   Age ：21  achievement ：99
 full name ： Liu Liu   Age ：19  achievement ：87
 full name ： Chen Qi   Age ：22  achievement ：90
 The deleted linked list is ：
 full name ： Zhang San   Age ：20  achievement ：98
 full name ： Li Si   Age ：18  achievement ：97
 full name ： Liu Liu   Age ：19  achievement ：87
 full name ： Chen Qi   Age ：22  achievement ：90

Joseph's question —— Typical application of circular linked list

Insert picture description here
Insert picture description here
Example ：

  1. Build a CircleLinkList.h The header file
    Above ： The circular list shows
  2. Build a CircleLinkList.c The source file
    Above ： The circular list shows
  3. Build a 02 Joseph's question .c The source file , Write the main function 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "CircleLinkList.h"
#define M 8
#define N 3


typedef struct MYNUM
{
    
	CircleLinkNode node;
	int value;
}mynum;

void myprintf(CircleLinkNode* data)
{
    
	mynum* num = (mynum*)data;
	printf("%d ", num->value);
}
void mycompare(CircleLinkNode*data1, CircleLinkNode* data2)
{
    
	mynum* num1 = data1;
	mynum* num2 = data2;
	if (num1->value == num2->value)
	{
    
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}

int main()
{
    
	CirecleLinkList* clist = Init_CircluLinkList();
	// Linked list insert data 
	mynum num[M];
	for (int i = 0; i < M; i++)
	{
    
		num[i].value= i + 1;
		Insert_CircluLinkList(clist, i,(CircleLinkNode*)&num[i]);
	}

	// Print 
	Printf_CircleLinkList(clist, myprintf);
	printf("\n");

	int index = 1;
	// Auxiliary pointer 
	CircleLinkNode* pcurrent = clist->head.next;
	while (Size_CircleLinkList(clist) > 1)
	{
    
		if (index == N)
		{
    
			mynum* tempnum = (mynum*)pcurrent;
			printf("%d ", tempnum->value);
			// Cache the next node of the node to be deleted 
			CircleLinkNode* pnext = pcurrent->next;
			// Delete... Based on value 
			RemoveByValue_CircleLinkList(clist, pcurrent, mycompare);
			pcurrent = pnext;
			if (pcurrent == &(clist->head))
			{
    
				pcurrent = pcurrent->next;
			}
			index = 1;
		}
		pcurrent = pcurrent->next;
		if (pcurrent == &(clist->head))
		{
    
			pcurrent = pcurrent->next;
		}

		index++;
	}
	if (Size_CircleLinkList(clist) == 1)
	{
    
		mynum* tempnum=(mynum*)Front_CircleLinkList(clist);
		printf("%d ", tempnum->value);
	}
	else
	{
    
		printf(" error ！！！");
	}
	// Release 
	FreeSpace_CircleLinkList(clist);

}

result ：

1 2 3 4 5 6 7 8
3 6 1 5 2 8 4 7
原网站

版权声明
本文为[Min, Hello, Xun]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/188/202207072126039285.html

边栏推荐

猜你喜欢

随机推荐