Implementation of sequence table: static and dynamic

The linear table （ Logical structure ）：

The most common and simplest data structure . Form like ：A1、A2、A3….An This contains a finite sequence of data ,

The basic operation of linear table

• initialization

• The destruction

• Insert Delete

• According to the value lookup Search by bit

Other operating

• Factory director
• Output operation
• Empty operation

Implementation of sequence table （ Physical structure ）

Linear table realized by sequential storage

1. Static implementation

#include<stdio.h>
#define MaxSize 10
typedef struct 
{
    
    int data[MaxSize];
    int lenght;
}SqList;

// Initialization of sequence table 
void InitList(SqList &L){
    
    for (int i = 0; i < MaxSize; i++)
    {
    
        L.data[i]=0;// Clean up dirty data 
    }
    L.lenght=0;
}

int main()
{
    
    SqList L;
    InitList(L);
	
	// Print the entire sequence table 
    for (int i = 0; i < MaxSize; i++)
    {
    
        printf("data[%d]=%d\n",i,L.data[i]);
    }
	
	// Normal access ,
    for (int i = 0; i < L.lenght; i++)
    {
    
        printf("data[%d]=%d\n",i,L.data[i]);
    }

    return 0;
}

Print the results

data[0]=0
data[1]=0
data[2]=0
data[3]=0
data[4]=0
data[5]=0
data[6]=0
data[7]=0
data[8]=0
data[9]=0

1. Dynamic implementation

principle ： Dynamic memory allocation

• When the sequence table is full , Apply for a larger space , And copy the original data to the new area , And release the original area

C

• malloc
• free function

L.data=（ElemType *）malloc（sizeof（ElemType）*InitSize)

C++

• new
• delete

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10
typedef struct 
{
    
	int *data;
    int MaxSize;
    int lenght;
}SeqList;

// Initialization of sequence table 
void InitList(SeqList &L){
    
	// Apply for a piece of continuous storage 
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.lenght=0;
	L.MaxSize=InitSize;
}

void IncreaseiSize(SeqList &L,int len){
    
	int *p=L.data;
	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int)); // Open up a new space 
	for(int i=0;i<L.lenght;i++){
    // Copy the data to the New Area , Time is expensive 
		L.data[i]=p[i];
	}
	L.MaxSize=L.MaxSize+len;
	free(p);
}

int main(){
    
    SeqList L;
    InitList(L);
	IncreaseiSize(L,1);
	// Print the entire sequence table 
    for (int i =0; i< L.MaxSize; i++)
    {
    
        printf("data[%d]=%d\n",i,L.data[i]);
    }
	
	// Normal access , It will not be implemented here 
    for (int i = 0; i < L.lenght; i++)
    {
    
        printf("data[%d]=%d\n",i,L.data[i]);
    }
    return 0;
}

Running results

data[0]=0
data[1]=0
data[2]=0
data[3]=0
data[4]=0
data[5]=0
data[6]=0
data[7]=0
data[8]=0
data[9]=0
data[10]=0 // because IncreaseiSize(L,1); Added one

The characteristics of the sequence table ：

• Random access , Can be in O(n） Find the second one in time i Elements
• High storage density , Each node only stores data elements
• Inconvenient to expand capacity （ Even if the dynamic allocation of time to achieve , The time replication of the extended length is relatively high ）
• It is inconvenient to insert or delete , A lot of data needs to be moved

Basic operation of sequence table

• Insert and delete
• According to the value lookup
• Search by bit

#include<stdio.h>
#define MaxSize 10
typedef struct 
{
    
    int data[MaxSize];
    int length;
}SqList;

// Initialization of sequence table 
void InitList(SqList &L){
    
    for (int i = 0; i < MaxSize; i++)
    {
    
        L.data[i]=0;// Clean up dirty data 
    }
    L.length=0;
}

// stay L The order of place of i Insert elements e
bool ListInsert(SqList &L,int i,int e){
    
	if(i<1||i>L.length+1)
		return false;
	if(L.length>=MaxSize)
		return false;
	for(int j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1]; // The first n The subscript of an element is n-1
	L.data[i-1]=e;
	L.length++;
	return true;
}

// stay L The order of place of i Insert elements e
bool ListDelete(SqList &L,int i,int &e){
    
	if(i<1||i>L.length+1)
		return false;
	e=L.data[i-1];
	
	for(int j=i;j<=L.length;j++) // Will be the first i All forward after functions 
		L.data[j-1]=L.data[j]; //
	L.length--;
	return true;
}

int GetElem(SqList &L,int i){
    
	return L.data[i-1];
	}

int LocateElem(SqList &L,int e)
{
    
	for(int i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
	return -1; // If you don't find it, return to -1
}

int main()
{
    
    SqList L;
    InitList(L);
	ListInsert(L,1,3);// Insert only at the beginning , Because it doesn't use 
	ListInsert(L,2,4);// Insert only at the beginning , Because it doesn't use 
	
	printf(" It has been found that the value is 3 Of , The order is =%d\n",LocateElem(L,4));
	LocateElem(L,4);
	
	int e=-1;
	if(ListDelete(L,1,e))
		printf(" Section... Has been deleted 1 Elements , The value is =%d\n",e);
	else
		printf(" Illegal bit order \n");
	
	printf(" We have found No 1 Elements , The value is =%d\n",GetElem(L,1));
	printf(" It has been found that the value is 3 Of , The order is =%d\n",LocateElem(L,4));
	GetElem(L,1);
	
	
	
	// Print the entire sequence table 
    for (int i = 0; i < MaxSize; i++)
    {
    
      printf("data[%d]=%d\n",i,L.data[i]);
    }
	

    return 0;
}

Output results

It has been found that the value is 3 Of , The order is =2
Section... Has been deleted 1 Elements , The value is =3
We have found No 1 Elements , The value is =4
It has been found that the value is 3 Of , The order is =1
data[0]=4
data[1]=0
data[2]=0
data[3]=0
data[4]=0
data[5]=0
data[6]=0
data[7]=0
data[8]=0
data[9]=0

Average time complexity =O(n)