Sequential representation and implementation of sequencelist -- linear structure

Recently, I was preparing for the postgraduate entrance examination data structure , I have learned it once in my sophomore year , Once again, I can't go on just reading , The more you look, the less you look , I always feel that I need to learn the code thoroughly to understand it better , Hey , This may be the awareness of the preparatory programmers .

If there is something wrong written and needs to be discussed , Welcome to comment and discuss ~

The sequential representation and implementation of linear table

Refer to YanWeiMin version 《 data structure 》 Section II of Chapter II ---- The sequential representation and implementation of linear table

The data structure is divided into 3 Kinds of structure ： Sequential structure 、 Tree structure 、 Figure structure （ If you add the set, it is 4 Kind of structure ）
Today we are going to talk about... In the order structure The linear table The order of ( The logical order is consistent with the physical order ) Representation and Implementation , It is mainly realized by array , Then there will be chain representation and implementation , Both have advantages and disadvantages .

Introduction of header file and variable definition

Mainly introduce C Language header file and definition constant identifier , The linear table is defined List( Include the basic element types of the table Student, The length of the watch length, Maximum capacity of the table listsize).

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

//-----  Dynamic allocation sequential storage structure of linear table  ----- 
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

// Define data elements for linear table operations Student Student type ,  Data elements  
typedef struct{
    
	int id;			// Definition student Student's serial number id,  Data item 1 
	int age;		// Definition student The age of the students age,  Data item 2 
}Student;

// Define a linear table  
typedef struct{
    
	Student *student;		// The main information stored in the table is students Student Type information  
	int length;				//length Represents the length of the linear table  
	int listsize;			//listsize Represents the maximum capacity range of the linear table  
}List;

All functions ( Statement )

For the definition of all basic operations of a linear table

// Declare the basic operation of linear table storage  
int initList(List &list);											// Initialize linear table  
int destoryStudentList(List &list);									// Destroy the linear table  
int insertStudentList(List &list, int i, Student student);			// Insert a data element at the specified position for the linear table  
Student deleteStudentList(List &list, int i, Student &student);		// Delete a data element at the specified location , And return the element  
int mergeOrderList(List &list_a, List &list_b, List &list_c);		// Merge two ordered linear tables  
int locateStudent(List &list, Student student);						// Locate the position in the linear table according to the data element  
int getListLength(List &list);										// Gets the length of the linear table  
int isEmptyList(List &list);										// Judge whether it is an empty table  
void printStudentList(List &list);									// Print linear table 

Initialization of linear table

The initialization of linear tables is easy to understand , Mainly through molloc The dynamic function is Student Type opens up memory space ( That is, the capacity is 100 Of Student Array ), initialization List The length of the watch is 0, The range of storage capacity is LIST_INIT_SIZE=100 individual .

// data structure   Algorithm 2.3 Realization --->  Initialize linear table operation  
int initList(List &list)
{
    
	// Construct an empty linear table  
	list.student = (Student *)malloc(LIST_INIT_SIZE*sizeof(Student));
	if(!list.student) return OVERFLOW;				// If allocation fails , Return data overflow information  
	list.length = 0;								// The length of the empty table is initialized to 0 
	list.listsize = LIST_INIT_SIZE;					// The initial storage capacity is the default capacity  
	return OK;
}

Linear table insertion and addition ( important )

The insertion and addition algorithm of linear tables is the focus of this section , Require a given sequence table List, Insertion position i( Sequence table with 1,2,3,4… Indicate location ), Insert the data elements to be inserted student Insert into the sequence table .

Put aside other judgment conditions , The difficulty is how to insert in the specified position of the sequence table ？

We can imagine that , Suppose we start with the last element of a linear table , Move backward in sequence ( That is, the previous one will overwrite the latter one ), Move all the way to the position to be inserted , This is the first time i Position and number i+1 The elements of the two positions are the same , Let's just put student Assign a value to i Elements of position , The insertion operation can be completed .

The operation is as shown in the figure ( The corresponding algorithm is as follows )
After insertion , Increase the length of the linear table , Then return the operation result .

Code implementation ：

// data structure   Algorithm 2.4 Realization  ---->  Student linear table insertion operation 
int insertStudentList(List &list, int i, Student student)
{
    
	if(i < 1 || i > list.length+1)	return ERROR;		// If the insertion position is illegal , Go straight back to  
	if(list.length >= list.listsize)
	{
    
		// call realloc() function   Yes list.student The size of the capacity is dynamically developed again  
		list.student = (Student *)realloc(list.student, (list.listsize + LISTINCREMENT)*sizeof(Student));
		if(!list.student) return OVERFLOW;				// If the development fails , Return failure information  
		list.listsize += LISTINCREMENT;					// Maximum capacity update of linear table  
	}
	
	Student *q = &list.student[i-1];			// preservation  q Is the insertion position of the linear table  
	 
	for(Student *p = &list.student[list.length-1]; p >= q; p--)			// Core code , The elements to be inserted are moved back layer by layer  
	*(p+1) = *p;								// Move back layer by layer , The preceding data element overrides the following data element  
	
	list.student[i-1] = student;				// Insert the data to be inserted into the specified position  
	list.length++;								// The number of student lists has increased  
	
	return OK;
}

Delete operation of linear table ( important )

The deletion algorithm of linear table is also a key point of this section , Require a given sequence table List, Delete location i( Sequence table with 1,2,3,4… Indicate location ), And delete the element with student return .

The difficulty is how to delete elements at the specified position in the sequence table ？

In fact, this algorithm is similar to the previous one , We can imagine that , Suppose we start from the linear table i Elements start , Move forward in sequence ( That is, the latter one will cover the former one ), It covers until the length-1 Elements , The overwrite is complete , Delete completed , This will result in the following figure , Directly subtract... From the length of the linear table 1 that will do , The deletion is considered successful .

Algorithm is as follows :

// data structure   Algorithm  2.5 Realization  ---->  Delete student linear table  , With parameters student Save output information  
Student deleteStudentList(List &list, int i, Student &student)
{
    
	if(i < 1 || i > list.length) return student;		// If the deletion position is illegal ,  Delete failed , Return the original information  
	
	student = list.student[i-1];			// Save and backup the elements to be deleted  
	for(Student *p = &list.student[i-1]; p < &list.student[list.length-1]; p++)		// Core code , Start from the specified position and cover from the back to the front  
	*p = *(p+1);							// Cover layer by layer from back to front  
	
	list.length--;							// Length reduction 1 
	
	return student;							// Returns the deleted saved element  
}

Merge operation of two ordered linear tables

Merging two ordered linear tables requires merging two linear tables , The merged linear table is still ordered , for example ：

L1: 1 2 3 5 6
L2: 1 1 2 3 5
L3: 1 1 1 2 2 3 3 5 5 6

Algorithm implementation ：

// data structure   Algorithm 2.7 Realization  ---->  Combine two ordered linear tables into a new ordered table , It is also required to be orderly  
int mergeOrderList(List &list_a, List &list_b, List &list_c)
{
    
	// Definition pa Is a linear table 1 The first element of , pa_last Is the last element of the linear table , pb Empathy  
	Student *pa = &list_a.student[0], *pa_last = &list_a.student[list_a.length-1]; 
	Student *pb = &list_b.student[0], *pb_last = &list_b.student[list_b.length-1];
	
	// take pa and pb The length and capacity of add up to pc Length and capacity  
	list_c.length = list_a.length + list_b.length;
	list_c.listsize = list_a.listsize + list_b.listsize;
	
	// by pc Open up memory space for storing two linear tables arranged in order  
	list_c.student = (Student *)malloc((list_c.listsize)*sizeof(Student));
	
	//pc Is a pointing linear table 3 The first element of the student element s 
	Student *pc = &list_c.student[0];
	
	// Core code  
	while(pa<=pa_last && pb<=pb_last)		// If the linear table 1 And linear tables 2 Not finished traversing  
	{
    
		// If the linear table 1 Is less than ( Ascending order ) The linear table 2 The elements of , Then put pa The elements in pc Insert , pa、pc Points to the next element cell of its linear table  
		if(pa->id <= pb->id) *pc++ = *pa++; 
		else *pc++ = *pb++;							// Otherwise pb The elements in pc Insert ,  Similarly, change the direction  
	}
	
	while(pa <= pa_last) *pc++ = *pa++;			// if pa Incomplete insertion , Then put pa The left and right elements of are appended to pc 
	while(pb <= pb_last) *pc++ = *pb++;			//pb also ,  but pa、pb At most one is incomplete  
	
	return OK;			// Return status information  
}

Find the location of a data element in a linear table

Find the qualified elements in the linear table through the violence loop , Return to its position

// data structure   Algorithm 2.6 Realization  ----> Student linear table lookup operation , Retrieves the position of an element in a linear table based on the specified element  
int locateStudent(List &list, Student student)
{
    
	int i = 1;
	for(int i = 1; i <= list.length; i++)			// Find through circular violence  
	{
    
		if(student.id==list.student[i-1].id && student.age==list.student[i-1].age)
		return i;								// Successfully found the return sequence number  
	}
	return FALSE;								// Unable to find the return failure information  
}

Other important methods

Output list method PrintStudentList()、 Destroy student list method destoryStudentList()、 Get list length getListLength()、 Determine the empty list function isEmptyList()

// Output all student information  
void printStudentList(List &list)
{
    
	printf(" The student information table is as follows :\n");
	for(int i = 0; i <= list.length-1; i++)
	printf("id = %d, age = %d.\n", list.student[i].id, list.student[i].age);
	printf(" Student capacity :\t%d.\n share  %d  Line information .\n", list.student, list.length);
}

// Destroy student list  
int destoryStudentList(List &list)
{
    
	free(list.student);
	list.student = NULL;
	list.length = 0;
	list.listsize = 0;
	return OK;
}

// Get list length  
int getListLength(List &list)
{
    
	return list.length;
}

// Determine the non empty list function  
int isEmptyList(List &list)
{
    
	if(list.length == 0) return TRUE;
	else return FALSE;
}

summary , It is convenient to store and represent random access elements in a linear table , Operations such as inserting and deleting elements need to move data elements constantly , More troublesome .

Next time, learn to update the chained storage and representation of linear tables , I wish you all the best ~