02_ Linear table_ Sequence table

2 The linear table

The linear table ：（ The order sheet , Single chain list , Static list , Stack , queue , strand ）
Have a unique head , Have a unique tail ; Any other node has a direct predecessor and a direct successor

The order sheet ： Logical adjacency and physical adjacency （ It's like a one-dimensional array ） But it is different from array
The difference between sequence table and array ：

Arrays only support 2 Operations ： Put data into the array , Get data from the array , One dimensional array is a special order table

The sequence table supports multiple operations ： Insert , Delete …



problem ： Inserting data into the sequence table requires moving the data after its position , But how to judge whether there is data after its location

Common solutions ： C Language can only judge whether there is a value in a variable , Cannot judge whether it is a valid value ;
(1) ’ \0’ Is a sign of the end of a string , So it can only be used to judge the string
(2) arr[i] ! = 0 ; If you use this method , be ’ 0 ' Indicates an invalid value , Valid values cannot be stored in the array ‘ 0 ’
The right solution ： At this time, you need to add a mark manually ： Define a calculator , Number of valid data recorded

2.1 The order sheet ： Suitable for inquiry

2.1.1 Fixed length sequence table

// The order sheet , Fixed length ： It's simple , But it's not practical 
typedef struct SQList// Give a data type a new alias SQList
{
    
	int elem[10];// Storing data , The fixed length is 10
	int length;// Number of valid data ; At this time, the physical location must be continuous when inserting data , No matter how many data are inserted ,length Always a number , So the complexity of space is O(1);
               // If the data is inserted discontinuously , Then each inserted data must be marked . At this time, the space complexity is O（n）;
}SQList,
*PSQList;// Structure pointer ：
// Equivalent to  typedef struct SQList* PSQList; The structure pointer is named PSQList


// initialization 
void InitSqList(PSQList ps)//PSQList==SQList *
{
    
	assert(ps != nullptr);// Assertions are only in Debug Valid in mode ：Debug It's a programmer development version , There's debugging information 
	if (ps == nullptr)    // stay Release Still valid in mode ：Release It's the release version , Code optimized , The compiler automatically deletes all debugging information 
	{
    
		return;
	}
	ps->length = 0;// The number of valid data is 0, Therefore, there is no need to add 10 Elements are initialized to 0;
}

// Determine whether the inserted array is full 
static bool IsFul(PSQList ps)
{
    
	return ps->length == 10;
}

// stay ps In sequence pos Position marker inserts data val
// The inserted data must be continuous on the left 
void Insert(PSQList ps, int pos, int val)
{
    
	assert(ps != nullptr);// Assertions are only in Debug Valid in mode ：Debug It's a programmer development version , There's debugging information 
	if (ps == nullptr)    // stay Release Still valid in mode ：Release It's the release version , Code optimized , The compiler automatically deletes all debugging information 
	{
    
		return ;
	}
	if (pos<0 || pos>ps->length|| IsFul(ps))
	{
    
		return ;
	}
	// Move the following data 
	for (int i = ps->length - 1;i >= pos;i--)
	{
    
		ps->elem[i + 1] = ps->elem[i];
	}
	// Insert new data 
	ps->elem[pos] = val;
	// The number of valid data +1;
	ps->length += 1;

}

// Output sequence table 
void Show(PSQList ps)
{
    
	for (int i = 0;i < ps->length;++i)
	{
    
		printf("%d", ps->elem[i]);
		printf(" ");
	}
	printf("\n");
}

// Sentenced to empty 
bool IsEmpty(PSQList ps)
{
    
	return ps->length == 0;
	/*if (ps->length == 0) { return true; }*/
}

// stay ps Find the first key, Found return subscript , No return found -1
int Search(PSQList ps, int key)
{
    
	for (int i = 0;i < ps->length;i++)
	{
    
		if (key == ps->elem[i])
		{
    
			return i;
		}
		return -1;
	}
}


// stay ps Find the first key, Found return subscript , No return found -1
int Search(PSQList ps, int key)
{
    
	/*for (int i = 0;i < ps->length;i++) { if (key == ps->elem[i]) { return i; } return -1; }*/

	/*int pos = -1; int i = 0; while (i < ps->length && key != ps->elem[i]) { i++; } if (i < ps->length) { pos = i; } return pos;*/

	int pos = ps->length - 1;
	while (pos>=0 && key != ps->elem[pos])
	{
    
		--pos;
	}
	return pos;
}


// Delete pos The value of the location 
bool DelPos(PSQList ps, int pos)
{
    
	// Judge pos Whether the location is legal 
	if (pos < 0 || pos >= ps -> length)
	{
    
		return false;
	}
	// Move the following data forward 
	//for (int i = pos;i < ps->length;i++)
	for (int i = pos;i < ps->length-1;i++)
	{
    
		ps->elem[i] = ps->elem[i + 1];// meet i+1 Cross border needs to be considered 
	}
	ps->length--;
	return true;
}

// Delete the first val value 
bool DelVal(PSQList ps, int val)
{
    
	int i = Search(ps, val);
	if (i < 0)
	{
    
		return false;
	}
	return DelPos(ps, i);
}

// return key The leading subscript of , Returns if none exists -1;
int GetPrio(PSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i <= 0)// Notice that the head has no precursor 
	{
    
		return-1;
	}
	return i - 1;
}

// return key The following subscript of , Returns if none exists -1;
int GetNext(PSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i< 0 || i==ps->length - 1)// Note that the tail has no successor 
	{
    
		return-1;
	}
	return i + 1;
}

// Empty data 
void Clear(PSQList ps)
{
    
	ps->length = 0;
}

// Destroy the entire memory ( Dynamic memory )
void Destory(PSQList ps)
{
    
	Clear(ps);// This example does not open up dynamic memory 
}

2.1.2 Indefinite length sequence table

The type changes as follows ：

Bubble sort of sequence table

Code optimization ： If the data itself is orderly , Exit the loop directly

// The order sheet , Length is not fixed （ When the capacity is full, it can grow automatically ）
typedef struct DSQList// Give a data type a new alias SQList
{
    
	int* elem;// Address of dynamic memory , Because with malloc, So return is an address , Want to save an integer value , Array stores integer values , So return an integer pointer 
	// The book defines ElemType*elem; The goal is to solve generics （int,char...)
	//C Language solves generics with ： A function pointer ;C++ Solve generics with ： Templates 
	int length;// Number of valid data ;
	int listsize;// Total capacity 
}DSQList,
* DPSQList;// Structure pointer ：
// Equivalent to  typedef struct DSQList* DPSQList; The structure pointer is named DPSQList

// initialization , Dynamically create initial capacity 
void InitDSqList(DPSQList ps)
{
    
	assert(ps != nullptr);
	if(ps==nullptr)
	{
    
		return;
	}
	ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));// contrast STL The initialization of the container in is 0
	ps->length = 0;// The number of valid data 
	ps->listsize = INIT_SIZE;// Total capacity 
}

// Determine whether the inserted array is full 
static bool IsFul(DPSQList ps)// Internal use does not provide external services, so it is a static function 
{
    
	return ps->length == INIT_SIZE;
}

// Capacity growth function , The capacity becomes the original 2 times （STL It may be 2 Times or 1.5 times ）
//1.5 Times better . Because when the space in front is released , When you reapply for space later, you can use the space released in front 
// 10 15 23 35 53 ...  When the first 2 Capacity expansion application 23 You can use the space released in front 10+15=25 Space （ If the space is continuous ）

//10 20 40 ...  If you expand 2 times , The space released in front cannot be reused 
static bool Inc(DPSQList ps)
{
    
	ps->elem = (int*)realloc(ps->elem, ps->listsize * 2 * sizeof(int));
	assert(ps->elem != NULL);
	ps->listsize *= 2;
	//ps->length; unchanged 
	return true;
}
// stay ps In sequence pos Position marker inserts data val
bool Insert(DPSQList ps, int pos, int val)
{
    
	if (pos<0 || pos> ps->length)
	{
    
		return false;
	}
	if (IsFul(ps))
	{
    
		Inc(ps);
	}
	// Move the following data 
	for (int i = ps->length - 1;i >=pos;i--)
	{
    
		ps->elem[i + 1] = ps->elem[i];
	}
	// Insert new valid data 
	ps->elem[pos] = val;
	// The number of valid data +1
	ps->length++;
	return true;
}

// Sentenced to empty 
bool IsEmpty(DPSQList ps)
{
    
	return ps->length == 0;
}

// stay ps Find the first key, Found return subscript , No return found -1
int Search(DPSQList ps, int key)
{
    
	for (int i = 0;i < ps->length;i++)
	{
    
		if (key == ps->elem[i])
		{
    
			return i;
		}
		
	}
	return -1;
}

// Delete pos The value of the location 
bool DelPos(DPSQList ps, int pos)
{
    
	// Judge pos Whether the location is legal 
	if (pos < 0 || pos >= ps->length)
	{
    
		return false;
	}
	// Move the following data forward 
	//for (int i = pos;i < ps->length;i++)
	for (int i = pos;i < ps->length - 1;i++)
	{
    
		ps->elem[i] = ps->elem[i + 1];// meet i+1 Cross border needs to be considered 
	}
	ps->length--;
	return true;
}

// Delete the first val value 
bool DelVal(DPSQList ps, int val)
{
    
	int i = Search(ps, val);
	if (i < 0)
	{
    
		return false;
	}
	return DelPos(ps, i);
}

// Delete all val value 
bool Del_All_Val(PDSQList ps, int val)
{
    
	int i, j = 0;
	while (j < ps->length)
	{
    
		if (ps->elem[j] != val)
		{
    
			ps->elem[i] = ps->elem[j];
			++i;
		}
		++j;
	}
	ps->length = i;
}

// return key The leading subscript of , Returns if none exists -1;
int GetPrio(DPSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i <= 0)// Notice that the head has no precursor 
	{
    
		return-1;
	}
	return i - 1;
}

// return key The following subscript of , Returns if none exists -1;
int GetNext(DPSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i < 0 || i == ps->length - 1)// Note that the tail has no successor 
	{
    
		return-1;
	}
	return i + 1;
}

// Output sequence table 
void Show(DPSQList ps)
{
    
	for (int i = 0;i < ps->length;++i)
	{
    
		printf("%d", ps->elem[i]);
		printf(" ");
	}
	printf("\n");
}

// Empty data 
void Clear(DPSQList ps)
{
    
	ps->length = 0;
}

// Destroy the entire memory 
void Destory(DPSQList ps)
{
    
	free(ps->elem);
	ps->elem = NULL;//ps->elem==(*ps).elem
	ps->length = 0;
	ps->listsize = 0;
	ps = NULL;// Invalid code 
}

ps = NULL; Why is it invalid code
Because the ps empty , Just changed ps Point to , No dereference （* ps）, So the pointer elem The sequence table pointed to is not destroyed

The characteristics of the sequence table ：
1. The time complexity of inserting data is O（n); If it is tail interpolation, the time complexity is O（1）

	for (int i = ps->length - 1;i >=pos;i--)
	{
    
		ps->elem[i + 1] = ps->elem[i];
	}

2. The time complexity of deleting data is O（n); If it is tail deletion, the time complexity is O（1）
3. Access data through subscripts , The time complexity is O（1）
4. Simple