2022.2.28 variable length sequence table

3

The structure is designed as ：

among ,typedef Set the basic data type int Etc. can be defined as ELEM_TYPE.

This is wrong , yes typedef

1.    .h Code in file , among #pragma  once To prevent header file duplication

#pragma once

typedef int ELEM_TYPE;
#define INIT_SIZE 10

// Structure design of indefinite length sequence table ：
typedef struct Dsqlist
{
	ELEM_TYPE *elem;// The pointer , For reception malloc Return value 
	int length;// Number of current valid values （ How many cells are currently occupied ）
	int list_size;// The current total number of spaces ( How many grids are there currently )
}Dsqlist, *PDsqlist;


// Variable length sequence table can be implemented by the operation function ：
// Additions and deletions 
// initialization 
void Init_Dsqlist(struct Dsqlist * p);//void Init_sqlist(PDsqlist p);

// Insert by position 
bool Insert_pos(PDsqlist p, int pos, int val);

// Delete... By location 
bool Del_pos(PDsqlist p, int pos);

// Delete... By value 
bool Del_val(PDsqlist p, int val);

// Get its effective length 
int Get_length(PDsqlist p);

// Capacity expansion      With 2 Double expansion   
void Inc(PDsqlist p);     

// Get the subscript of the value （ If the data is duplicated , Then return to val First occurrence ）
int Search(PDsqlist p, int val);

// Sentenced to empty 
bool IsEmpty(PDsqlist p);

// Full sentence 
bool IsFull(PDsqlist p);

// Empty 
void Clear(PDsqlist p);

// The destruction 
void Destroy(PDsqlist p);

// Print 
void Show(PDsqlist p);

2.   .cpp In file

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "Dsqlist.h"

// Variable length sequence table can be implemented by the operation function ：
// Additions and deletions 
// initialization 
void Init_Dsqlist(struct Dsqlist * p)//void Init_sqlist(PDsqlist p);
{
	assert(p != NULL);
	if(p == NULL)
		return;

	p->elem = (ELEM_TYPE*)malloc(INIT_SIZE * sizeof(ELEM_TYPE));
	assert(p->elem != NULL);
	if(p->elem == NULL)
		return;

	p->length = 0;
	p->list_size = INIT_SIZE;
}



// Insert by position 
bool Insert_pos(PDsqlist p, int pos, int val)
{
	//assert    p
	//assert    pos 
	// Full sentence     Capacity expansion    
	if(IsFull(p))
	{
		Inc(p); 
	}
	// here , sure p Not for NULL,  also pos Legal location ,  And let me insert... In my free space 
	
	//4. First move the data , Leave the position to be inserted empty , Then set the value val Just put it in 
	//（ Insert , Move data , Move from back to front ）

	for(int i=p->length-1; i>=pos; i--)//i Start with a subscript pointing to the last element , The last moved data subscript is pos
	{
		p->elem[i+1] = p->elem[i];
	}
	// here ,for Loop execution ends    It indicates the completion of moving data     Now you just need to insert the value val Assign in 
	p->elem[pos] = val;
	// Don't forget   There is also a number of valid values at the end of the insert operation length++
	p->length++;

	return true;
}

// Delete... By location 
bool Del_pos(PDsqlist p, int pos)
{
	//1. Sentenced to empty   p!=NULL     Determine whether the fixed length sequence table exists 
	assert(p!=NULL);
	if(p == NULL)
		return false;

	//2. Determine where to delete   Is it legal 
	assert(pos >=0 && pos<p->length);//   When deleting pos==p->length illegal 
	if(pos<0 || pos>=p->length)
		return false;

	//3. Empty operation 
	if(IsEmpty(p))
		return false;


	//4. The valid value after the position to be deleted , Move forward one at a time , Just overwrite the deleted position 
	//（ Delete , Overwrite data forward , Move the element closest to the position to be deleted first ）

	for(int i=pos+1; i<=p->length-1; i++)
	{
		p->elem[i-1] = p->elem[i];
	}
	// here ,for Loop execution ends    It indicates that the forward data coverage is completed     Now all you have to do is p->length--
	p->length--;

	return true;


}

// Delete... By value 
bool Del_val(PDsqlist p, int val)
{
	//assert p
	// Judge val This value    Existence does not exist 
	int index = Search(p, val);
	if(index == -1)
	{
		return false;
	}

	return Del_pos(p, index);
}

// Get its effective length 
int Get_length(PDsqlist p)
{
	//assert
	return p->length;
}

// Capacity expansion      With 2 Double expansion   
void Inc(PDsqlist p)
{
	//assert  p    Does this assertion require ？   Unwanted 
	
	/*ELEM_TYPE* tmp = (ELEM_TYPE*)realloc(p->elem, p->list_size*sizeof(ELEM_TYPE) * 2);
	assert(tmp != NULL);
	if(tmp == NULL)
	{
		printf("realloc error\n");
		return;
	}
	else
	{
		p->elem = tmp;
	}*/

	p->elem = (ELEM_TYPE*)realloc(p->elem, p->list_size*sizeof(ELEM_TYPE) * 2);
	assert(p->elem != NULL);
	if(p->elem == NULL)
	{
		printf("realloc error\n");
		return;
	}
		

	//p->length;// After the expansion   The number of valid values does not change 
	p->list_size *= 2;// After the expansion    The total number of cells needs *2

}

// Get the subscript of the value （ If the data is duplicated , Then return to val First occurrence ）
int Search(PDsqlist p, int val)
{
	//assert
	for(int i=0; i<p->length; i++)
	{
		if(p->elem[i] == val)
		{
			return i;
		}
	}
	return -1;
}



// Sentenced to empty 
bool IsEmpty(PDsqlist p)
{
	//assert
	return p->length == 0;
}
// Full sentence 
bool IsFull(PDsqlist p)
{
	//assert
	return p->length == p->list_size;
}

// Empty 
void Clear(PDsqlist p)
{
	//assert
	p->length = 0;
}

// The destruction    It mainly deals with memory leaks 
void Destroy(PDsqlist p)
{
	//assert
	free(p->elem);
}

// Print 
void Show(PDsqlist p)
{
	//assert
	for(int i=0; i<p->length; i++)
	{
		printf("%d ", p->elem[i]);
	}
	printf("\n");
}

3.    In the main function file

 

#include <stdio.h>
#include "assert.h"
#include <stdlib.h>
#include <vld.h>
#include "Dsqlist.h"
int main()
{
	struct Dsqlist head;
	Init_Dsqlist(&head);
	printf("maxsize: %d\n", head.list_size);
	printf("length = %d\n", Get_length(&head));

	
	for(int i=0; i<10; i++)
	{
		Insert_pos(&head, i, i+1);
	}
	Insert_pos(&head, 0, 100);
	Insert_pos(&head, head.length, 200);
	printf("maxsize: %d\n", head.list_size);
	printf("length = %d\n", Get_length(&head));
	Show(&head);


	Del_pos(&head, 3);
	Show(&head);
	Del_val(&head, 9);
	Show(&head);

	printf("%d\n", Search(&head, 5));
	printf("%d\n", Search(&head, 300));

	Clear(&head);
	printf("length = %d\n", Get_length(&head));
	Show(&head);

	Destroy(&head);

	return 0;
}

Running results ：

 4. Sequence table summary

The characteristics of the sequence table ：（ Fewer insert delete operations , Random access to the values in the array is a common operation ）
(1) The logic is simple , Implement a simple
(2) Insertion operation time complexity O(n), Because you need to move data   But the tail interpolation does not need to move the data （ Tail interpolation time complexity O(1)）
(3) Delete operation time complexity O(n), Because the data needs to be overwritten forward   But the tail deletion does not need to move the data （ Tail deletion time complexity O(1)）
(4) Random access time is complex O(1), Because the sequence table can directly access the element values in the array through subscripts

The order sheet ： Between data and data , Logical adjacency , Physical also adjacent