Data structure sequence table (c language)

Storage structure of sequence table

(1) When a high-level programming language such as c language is used to describe the problem of data structure, the method to realize the sequential storage structure is to use array.
(2) There are two kinds of arrays: static array and dynamic array. The application and release of static array storage space are automatically completed by the system, and the application and release of dynamic array storage space are completed by users by calling system functions. Whether static array or dynamic array, its function is to apply to the system for a finite space with continuous addresses, but the method of applying for space is different.

Implementation of sequence table operation:

(1) Define structure SeqList

In order to describe the sequence table shown in the above figure in c language, the structure SeqList is defined as follows

typedef struct 
{
	DataType List[MaxSize];
	int size;
}SeqList;

Where DataType is the data type of array elements (i.e. data elements), MaxSize represents the maximum number of array elements, List represents the array members of the sequence table, size represents the number of data elements currently stored in the sequence table, and must meet the requirements of size < = MaxSize

(2) Initialize listinitiate
//Initialize listinitiate
void ListInitiate (SeqList *L)//Initialization sequence table L
{
	L->size=0;//Define the number of initialization data elements
}

*Since the value of the size field of parameter L needs to be changed in the function, parameter L should be designed as an output parameter, that is, parameter L should be designed as the pointer type of SeqList. Otherwise, the modified value of the size field cannot be brought back.

(3) Find the number of current data elements ListLength(L)
int ListLength(SeqList L)//Returns the number of current data elements
{
	return L.size;
}
(4) Insert data element ListInsert(L,i,x)
//Insert data element
int ListInsert(SeqList *L,i,DataType x)//Insert data element x at position i
{
	int j=0;
	if(L->size>=MaxSize)
	{
		printf("The sequence table is full, unable to insert data!\n");
		return 0;

	}
	else if(i<0||i>L->size)
	{
		printf("parameter i wrongful!\n");
		return 0;
	}
	else
	{
		//Move the data back from back to front in order to prepare for input
		for(int j=L->size;j>i;j--)
		{
			L->List[j]=L->List[j-1];

		}
		L->List[i]=x;//Insert element x
		L->size++;//Number of elements plus one
     return 1;
	}
}

Because the size of the current number of data elements in the sequence table is initially 0, and when there is one data element, it is 1 (that is, the size of the number of data elements is 1 larger than the array subscript, that is, the value of parameter i), the insertion position parameter i should be greater than or equal to 0 and less than or equal to size. When the parameter i is not within the above interval, it can be determined that the parameter is wrong. The storage space of the array is limited. If the MaxSize storage space of the array is full, you cannot continue to insert.

(5) Delete data element ListDelete(L,i,x)
int ListDelete(SeqList *L,int i,DataType *x)//Delete the data element at the ith position in the sequence table L and save it in x
{
	int j;
	if(L->size=0)
	{
		printf("The sequence table is empty and no data can be deleted!\n");
		return 0;
	}
	else if(i<0||i>L->size-1)
	{
		printf("parameter i wrongful \n");
		return 0
	}
	else
	{
		*x=L->List[i];
		//Move the data forward in turn from deleting that data element
		for(int j=i+1;j<=L->size;j++)
		{
			L->List[j-1]=L->size[j];
		}
		
		L->size--;//Number of elements minus one
		return 1;
	}
}

If there is no data element in the sequence table, it cannot be deleted. It should be judged as an error in function call. The deletion position parameter i should be greater than or equal to 0 and less than or equal to size-1. When parameter i is not within the above interval, it is a parameter error.

(6) Get data element ListGet(L,i,x)
int ListGet(SeqList L,int i,DataType *x)
	 //Take the ith data element in the sequence table L and store it in x. 1 is returned for success and 0 is returned for failure
 {
	 if(i<0||i>L.size-1)
	 {
		 printf("parameter i wrongful!\n");
		 return 0;
	 }
	 else
	 {
		 *x=L.List[i];
		 return 1;
	 }
 }

The operation of fetching data elements is similar to the operation of deleting data elements, but it is simpler. The operation of fetching data elements only needs to fetch data elements List[i] into parameter x.

Design example:

The programming realizes the following tasks: establish a linear table, input 1, 2, 3, 4... 10 in turn, then delete data element 5, and finally display the data elements in the current linear table in turn. Assuming that the number of data elements in the linear table will not exceed 100 in the worst case, it is required to use the sequential table.

The program design is as follows:

#include <stdio.h>
#define Maxsize 100
typedef int Datatype;
#include "SeqList.h"
void main(void)
{
	int i;
	int x;
	SeqList myList;
	ListInitiate(&myList);//Initialize function call
	for( i=0;i<10;i++)//Insert 10 data elements
		ListInsert(&myList,i,i+1);//Insert function call
	ListDelete(&myList,4,&x);//Delete function call
	//Displays the current data element of the sequential table
	for( i=0;i<ListLength(myList);i++)//Current number of elements function call
	{
		ListGet(myList,i,&x);//Get element function call
		printf("%d\t",x);//Show data elements
	}
}

Operation results:

Keywords: C data structure Back-end

Added by herreram on Sat, 05 Mar 2022 02:04:46 +0200