The linear table

The introduction

New physical examination, in order to management and unified data, school specially stipulated in line way, namely according to the student number line, who is who in the back, before this is all good, so who is who, is very convenient, the classmates like was linked to a line (student id), the organizational data (students) we can called linear table structure

define

Linear list: A finite sequence of zero or more data elements (having the same properties and belonging to the same element)

If we write the linear table as (a0, a1,ai -1 ai,ai +1… , an – 1 , an )

  • Note: I is an arbitrary number, only for relative position, the subscript is its position in the linear table)

  • Before and after: Because of the sequential relationship between the elements before and after, each element except the first and last elements contains a precursor and a successor, which is simply understood as the previous element and the next element

  • Empty table: If the number of elements in a linear table is the length of the linear table, then n = 0, the linear table is empty

  • First node and last node: a0 is called the first node and an is called the last node

Abstract data type

  • Data type: A collection of values of the same nature and the collective name for the operations defined on this collection

  • Abstract data type: REFERS to a mathematical model and the set of operations defined on that model

We can give an example of data types

  • For example, we often use integer floating-point data. These are the general names of data, and all data conforming to their properties can be defined by their corresponding data types. For example, 520 is an integer data, so it can be assigned to a variable of int typeint love = 520;

General data types such as these are usually encapsulated in the internal definition of the programming language and provided directly to the user for the user to call for operations, whereas abstract data types are usually defined by the user themselves based on existing data types

Abstract data types and data types in high-level programming languages are actually a concept, but their meaning is much broader and more abstract than ordinary data types

Why abstract? Because it is a data type corresponding to our users to solve practical problems and describe the entities in real life and display life. I can define the structure of its storage, and I can define some operations that it can or needs to perform, such as adding or deleting employee information in the employee table. These two parts make up the abstract data type “employee.

The general process is:

  • A: The average user would write A custom data type as the base type

  • B: Some of these abstract operations can be defined as member functions of that type and then implemented

  • C: If the external interface is in the public domain, these operations can be invoked through objects

  • Of course, when we use abstract datatypes, we pay more attention to the API description of the data itself than to the representation of the data, which is something that developers implementing the abstract datatypes should consider

There are two types of linear lists, sequential and chained, and we’ll start with the first

Sequential storage structure

What is a sequential storage structure?

Sequential storage structure: a sequence of storage cells with contiguous addresses to store the data elements of a linear table

How do you understand this storage?

For example, in a vegetable garden, there is an open field, we find a small piece of land to plant vegetables, because the land is not smooth and loose, we need to cultivate the land, and the seeds are planted in a certain order, this is the initialization of the table

Garden can be understood as memory space, the space can be understood as a memory space that can be used by our way through the kinds of vegetable seeds, will be a certain amount of memory space occupied, of course, you are placed in the space of data elements must be of the same type That is to say, all is the vegetable seeds, some seeds are sometimes moth is broken, we need to remove some of the seeds, After the purchase and then choose a place to plant in the vacant place, this is to add and delete the number of elements

Address calculation mode

From the definition, we know that the data stored in this way is continuous and of the same type, so each data element occupies the same amount of storage space. Assuming that each data element occupies L storage units, we can derive the following formula


  • I is the index of the element in question
  • That’s the unit length times the number

Abstract data types for linear tables

#ifndef _LIST_H_
#define _LIST_H_
#include<iostream>
using namespace std;

class outOfRange{};
class badSize{};
template<class T>
class List {
public:
    // Clear the linear table
	virtual void clear(a)=0;
    // the table returns true for empty and false for non-empty
	virtual bool empty(a)const=0;
    // Find the length of the linear table
	virtual int size(a)const=0;
    // Insert value at position I [0..n] in a linear table
	virtual void insert(int i,const T &value)=0;
    // In a linear table, drop the element at position I [0..n-1]
	virtual void remove(int i)=0;
    // In a linear table, find the first occurrence of the element with value
	virtual int search(const T&value)const=0;
    // In a linear table, find the element with bit order I and return its value
	virtual T visit(int i)const=0;
    // iterate over the linear table
	virtual void traverse(a)const=0;
    // invert the linear table
	virtual void inverse(a)=0;					
	virtual ~List(){};
};

/* Custom exception handling class */ 


class outOfRange :public exception {  // Used to check the validity of the scope
public:
	const char* what(a) const throw(a) {
		return "ERROR! OUT OF RANGE.\n"; }};class badSize :public exception {   // Check the validity of the length
public:
	const char* what(a) const throw(a) {
		return "ERROR! BAD SIZE.\n"; }};#endif
Copy the code

In the abstract data type of the linear table above, some common methods are defined where we can add and remove functions as needed

So with this abstract data type List we can write down the order structure under a linear List and the definition of a chained List

Exception statement description: If new gets an error when calling the allocator to allocate storage (the error message is saved), it will catch an exception of type bad_alloc. The what function, which fetches the basic information of the error, is a string of const char* or string

Sequential table – Definition of a sequential storage structure

#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include "List.h"
#include<iostream>
using namespace std;

//celemType is the element type stored in the sequential table
template <class elemType>
class seqList: public List<elemType> { 
private:
	// Use arrays to store data elements
	elemType *data;
    // The number of elements stored in the current sequence table
    int curLength;
    // The maximum length of the sequence table
    int maxSize;
    // Expand the tablespace when the table is full
    void resize(a);							
public:
	// constructor
    seqList(int initSize = 10);				
 	// Copy the constructor
	seqList(seqList & sl);
    // destructor
    ~seqList()  {delete[] data; }// To clear the table, just change curLength
    void clear(a)  {curLength = 0; }/ / found empty
	bool empty(a)const{return curLength == 0; }// Returns the number of elements currently stored in the sequence table
    int size(a) const  {returncurLength; }// Insert value at position I and increase the table length by 1
    void insert(int i,const elemType &value);
    // Drop the element value at position I. If the drop position is valid, the length of the table is reduced by 1
    void remove(int i);
    // Find the first occurrence of the element with value
    int search(const elemType &value) const ;
    // Accesses the value of the element in bit order I. Bit order 0 represents the first element, similar to an array subscript
    elemType visit(int i) const;			
    // Iterate over the order table
    void traverse(a) const;
    // Reverse the sequence table
	void inverse(a);							
	bool Union(seqList<elemType> &B);
};
Copy the code

The realization of the basic operation of sequence table

(1) Constructor

In the constructor, we need to complete the initialization of the empty order table, that is, create an empty order table

template <class elemType>
seqList<elemType>::seqList(int initSize) { 

	if(initSize <= 0) throw badSize();
	maxSize = initSize;
	data = new elemType[maxSize];
	curLength = 0;
						
} 
Copy the code

Here we are careful to distinguish between initSize and curLenght

  • initSize: Initializes (specifies) the array length
    • Array length is to store the length of the linear table storage space, in general, this value is fixed, but in order to satisfy the need in many cases, we will choose the distribution of the dynamic array, namely define expansion mechanism, although very convenient, and it has brought the loss of efficiency, we will be mentioned in the expansion of the function of this problem
  • CurLenght: indicates the number of data elements in a linear table

(2) Copy constructor

template <class elemType>
seqList<elemType>::seqList(seqList & sl) { 

	maxSize = sl.maxSize;
	curLength = sl.curLength;
	data = new elemType[maxSize];
	for(int i = 0; i < curLength; ++i)
		data[i] = sl.data[i];
	
}
Copy the code

(3) insertion

Here we talk about a very common operation – inserts, with our first example, then arrange a medical school, everyone consciously in accordance with the student id along the ready queue, but a student from the late Z and know the front ranks of the C students, in the past want to befriend, a team, if the students agreed, this means that the original C classmate in front of people into the Z, The person behind student B also changed from C to Z, and all the students behind the inserted position had to move back one position, and the students behind inexplicably moved back one position

Let’s think about how to implement this in code, and what are some special considerations?

  • 1. The legitimacy and validity of the insert element position
    • [0,curLength] Description: curLength: indicates the current valid position
  • 2. Check whether the table is full. If the table is full, you cannot add more tables
    • A: No operation, exit with an error (to avoid setting the initial size of the array to be larger)
    • B: Dynamic expansion to expand the array capacity (used in the following example)
  • 3. Special insertion of head and tail nodes is considered
  • 4. Direction of movement
    • Using a loop, you move from the end of the table, overwriting unmoved elements if you start at the insertion position
template <class elemType>
void seqList<elemType>::insert(int i, const elemType &value) { 
	
	// The valid insert range is 0..curlength.
	if (i < 0 || i > curLength) throw outOfRange(); 
	// Table full, expand array capacity
	if (curLength == maxSize) resize();		    
	for (int j = curLength; j > i; j--)
		// Index elements in the curleng-1.. I range move one step back
		data[j] = data[j - 1];
    // Place the element with value at position I
	data[i] = value;
    // The table length increases
	++curLength;	

}
Copy the code

(4) Delete

Now that you understand the insert operation, strike while the iron is hot. Let’s take a look at the corresponding delete operation. What is the flow of this operation? In the example above, the students who jumped the queue were found by the management staff and had to leave the queue. In this way, the students who were forced to move back together just now all moved forward. Of course, the sequential relationship of deleted positions also changed

Same as insertion, what’s interesting about it?

  • 1. The validity and validity of the deleted element position

    • Delete valid range: [0, curleng-1]
    • i < 0 || i > curLength- 1Implicitly resolves the problem of judging empty tables

  • 2. Direction of movement

    • Using a loop, you move forward from the position of the element after it is deleted
template <class elemType>
void seqList<elemType>::remove(int i) { 
	
	// Valid delete scope
	if(i < 0 || i > curLength- 1) throw outOfRange();  
	for(int j = i; j < curLength - 1; j++)
		data[j] = data[j+1];
	--curLength; 
}
Copy the code

(5) Capacity expansion

SeqList

::seqList(int initSize) {code content}

We also initialize the specified parameter value as the length of the array

maxSize = initSize;

Why don’t we just specify maxSize as an argument in the constructor?

As you can see from the variable name, this is to show that the initial value and the maximum value are not the same data, or to prepare for expansion,

Why expand it?

Arrays hold linear tables, but what if the length of the linear table (the number of data elements) reaches the length of the array? Obviously we don’t have enough space to do things like insert, which is also called a full table, so we define a capacity expansion operation, which is performed when the table is full

Is expansion the best way?

Although arrays look a bit awkward, they are also an effective way to store objects or data. We also recommend this method, but due to its fixed length, it can be limited in many cases. For example, the table is full. One way we set the initial value is more than the actual value, but due to the actual value will often have some fluctuations, lead to take up too much memory space would be caused by the waste, or still table full of problems, in order to solve the actual problem, obviously or expansion more in line with the need, but the price is certain efficiency loss

An array is a simple linear sequence, which makes element access very fast. But the price you pay for this speed is that the size of the array object is fixed and immutable throughout its life

Let’s take a look at the rationale for expansion and you’ll see why!

Expansion ideas:

Since the array space must be contiguous in memory, expanding the array space requires applying for a new, larger array, copying the contents of the original array into the new array, freeing up the original array space, and using the new array as the storage area of the linear table

Therefore, in order to realize the automatic allocation of space, although we still prefer the way of dynamic expansion, such flexibility obviously requires some overhead

template <class elemType>
void seqList<elemType>::resize() { 

	elemType *p = data;
	maxSize *= 2;
	data = new elemType[maxSize];
	for(int i = 0; i < curLength; ++i)
		data[i] = p[i];
	delete[] p; 
 
}
Copy the code

(6) Search elements by value

To find the position of the first occurrence of the elements with value in sequence, you only need to traverse the data of each element in the linear table and compare it with the specified value in turn

  • Same: bit order of return value
    • Note the valid range of the query
  • Not found or error: return -1

template<class elemType>
int seqList<elemType>::search(const elemType & value) const
{

	for(int i = 0; i < curLength; i++)
		if(value == data[i])return i;
	return - 1;

}
Copy the code

(7) Find elements by position (subscript)

This is really easy, just return the result

template<class elemType>
elemType seqList<elemType>::visit(int i) const {

	return data[i];                                                                   
	
}
Copy the code

(8) Traverse the elements

What do I mean by ergodic? If the table is empty, the output information will be displayed. Note that the valid range of traversal is [0, the last element -1].

template<class elemType>
void seqList<elemType>::traverse()const {

	if (empty())
		cout << "is empty" << endl;	
	else {
		cout << "output element:\n";
		// Access all elements in the sequence table in turn
		for (int i = 0; i < curLength; i++)	
			cout << data[i] << "";
		cout << endl; }}Copy the code

(9) Inverse operation

Inverse operation as the name implies, is to invert the data of linear table, that is the first element and tail transpositions element, and then the second element and the penultimate element exchange, then to the middle to continue to exchange for the unit, ending symmetric exchange, also called need to pay attention to the number that is the cycle is only half the length of the linear table

template<class elemType>
void seqList<elemType>::inverse() {
	
	elemType tem;
	for(int i = 0; i < curLength/2; i++) {
		// Switch the specific way, you can set a middle value
		tem = data[i];
		// Two symmetric data
		data[i] = data[curLength - i - 1];
		data[curLength - i - 1] = tem; }}Copy the code

(10) Merge order table

Now, given two linear tables, table A and table B, where the elements are stored in positive order, how can two tables be merged and placed in table A, but the elements in the table are still stored in positive order

Algorithm idea: We set three hands respectively, represent A, B, C, C represents A new table, we have three pointer to three tables at the end of the table A and table B, the tail element of comparison, and then A big move into A new table, then will be big elements of the pointer of the linear table and new table pointer, forward A, so continue to compare elements A and B table size, Repeat until one table is empty, and move the remaining elements of the remaining table into the new table A

template<class elemType>
bool seqList<elemType>::Union(seqList<elemType> &B) {	

	int m, n, k, i, j;	
    // The current object is linear table A
    //m and n are the lengths of linear tables A and B respectively
	m = this->curLength;						  
	n = B.curLength;
    //k is the working pointer (subscript) of the resulting linear table in the new table A
	k = n + m - 1;	
    // I and j are working Pointers to linear tables A and B, respectively.
	i = m - 1, j = n - 1;
    // Check whether the space of table A is large enough. If not, expand the space
	if (m + n > this->maxSize)					  
		resize();
    // Merge sequential tables until a table is empty
	while (i >= 0 && j >= 0)					  
		if (data[i] >= B.data[j])
			data[k--] = data[i--];
		// Default current object, this pointer can be omitted
		else data[k--] = B.data[j--];			  
	// Copy the remaining elements from table B into table A
	while (j >= 0)								  
		data[k--] = B.data[j--];
	// Change the length of table A
	curLength = m + n;							  
	return true;
	 
}
Copy the code

Advantages and disadvantages of sequential tables

Advantages:

  1. Logical and physical order, order table can be directly and quickly access elements by subscript
  2. There is no need to add additional storage space to represent logical relationships between elements in the table

Disadvantages:

  1. Linear table length needs to be defined initially, and it is often difficult to determine the storage capacity, so expansion mechanism can only be used at the cost of reducing efficiency

  2. Insert and delete operations require a large number of elements to be moved and are inefficient

Time complexity proof

Read:

Do you remember this formula?


We can use this formula to calculate the address of any place in the linear table at any time, and the time used by the computer is the same, a constant, which means that the time complexity is O(1).

Insert and delete:

Let’s take the example of insertion

  • First, the best case is that the element is inserted at the end, so that whatever it does doesn’t affect any of the other elements, so its time is O(1).

  • So the worst-case scenario is that the element inserts exactly in the first place, which means that everything that follows has to move one place, so it’s order n time.

  • In the average case, since the probability of insertion is the same in every position, and the further you insert, the more you move, the average case is equal to a certain number of times of the middle value, which is (n-1) / 2, and the average time is still order n.

Conclusion:

When reading data, its time complexity is O(1), when inserting and deleting data, its time complexity is O(n), so the sequential table in linear table is more suitable to deal with some stable elements, query read more problems

The end:

If there are any deficiencies or mistakes in the article, please leave a comment and share your thoughts. Thank you for your support!

If it helps you, follow me! If you prefer the way of reading articles on wechat, you can follow my official account

We don’t know each other here, but we are working hard for our dreams

A adhere to push original development of technical articles of the public number: ideal more than two days