directory

  • Knowledge framework

  • Exam outline content

  • Definition and basic operations of linear tables

  • Sequential representation of linear tables (sequential storage)

  • Implementation of basic operations on sequential tables

【 Knowledge framework 】

【考 题 content/By 2022 】

  • Definition and basic operations of linear tables

  • Implementation of linear tables

    Sequential storage; Chain storage; Application of linear tables

Definition and basic operation of linear table

1. Definition of linear tables

A linear table is a finite sequence of N data elements of the same data type, where n is the length of the table, and when n=0 a linear table is an empty table. If the linear table is named by L, it is generally expressed as: L= (A1, A2, A3… Ai,… An).

  • Note that the bit order starts at 1 (distinguished from array subscripts starting at 0)
  • In this formula, A1 is the unique “first” data element, also known as the table header element
  • In the formula,an is the only “last” data element, also known as the table tail element
  • In addition to the first element, each element has only one direct precursor
  • Each element has one and only one immediate successor except the last

2,☆ Characteristics of linear tables

  • The number of elements in the table is limited
  • The elements in a table are logically sequential. The elements in a table have a sequence
  • The elements in the table are data elements, and each element is a single element
  • The data types of the elements in the table are the same, which means that each element occupies the same amount of storage space
  • The elements in the table are abstract, that is, the logical relationship between the elements is discussed, regardless of what the elements represent
  • Pay attention to: A linear table is a logical structure that represents one-to-one adjacency between elements. Sequential lists and linked lists are storage structures. They belong to different concepts and should not be confused.

3. Basic operations of linear tables

  • InitList(&L): initializes the table. Construct an empty linear table.
  • Length(L): Find the Length of the table. Returns the length of linear table L, the number of data elements in L.
  • LocateElem(L,e): Lookup operation by value. Find the element with the given keyword value in table L.
  • GetElem(L, I): bitwise search operation. Gets the value of the element in the ith position in table L.
  • ListInsert (&L, I,e) : Insert operation. Inserts the specified element e at position I in table L.
  • ListDelete(&L, I,&e) : Delete operation. Delete the element in the ith position of table L and return the value of the deleted element with e.
  • PrintList(L): Output operation. Outputs all element values of linear table L in sequential order.
  • Empty(L): Nulls operation. Return true if L is an empty table, false otherwise.
  • DestroyList(&L): Destroy operation. Destroys the linear table and frees the memory occupied by the linear table L.

Note:

① The implementation of the basic operation depends on the use of which storage structure, storage structure is different, the implementation of the algorithm is also different,

The “&” is a reference call in C++, and the same effect can be achieved by using Pointers in C.

Second, the sequential representation of linear table and its basic operation

1. Definition of order table

The sequential storage of linear tables is also called sequential tables. It uses a set of storage cells with contiguous addresses to store the data elements in a linear table so that logically adjacent elements are physically adjacent as well.

Note:

(1) In linear tables, all statements about elements are bit order, and the bit order starts from 1. Distinguish the subscripts from arrays starting at 0.

② In the sequence table, the scale variable of the problem is table length L.length.

2. Static allocation of sequential tables

#define ElemType int	ElemType is of type int

#define MaxSize 50	// Define the maximum length of a linear table
typedef struct {
	ElemType data[MaxSize];	// The elements of the sequence table
	int length;	// The current length of the sequence table
}SqList;	// Type definition of sequence table (Sq=sequence)
Copy the code

3. Dynamic allocation of order tables

  • C language dynamic allocation statement

    L.data=(ElemType*)malloc(sizeof(ElemType))

  • C++ language dynamic allocation statement

    L.data=new ElemType[InitSize]

  • Note: dynamic allocation is not chained storage, it is also a sequential storage structure, the physical structure remains the same, is still random access, but the size of the allocation can be dynamically determined at run time.
#define ElemType int	ElemType is of type int

#define InitSize 100	// The initial definition of the table length
typedef struct {
	ElemType *data	// Indicates a dynamically allocated array pointer
	int MaxSize,length;	// The maximum size and current number of arrays
}SeqList;	// Dynamically allocate array order table type definition
Copy the code

4. Implementation of basic operations on the sequence table

  • Create the order table and initialize it

// Static allocation
void InitList(SqList &L){
	for(int i=0; i<MaxSize; i++){ L.data[i]=0;
	}
	L.length=0;
}

int main(a){
	SqList L;
	InitList(L);
	return 0;
}


// Dynamic allocation
void InitList(SeqList &L){
	L.data=(ElemType*)malloc(sizeof(ElemType));
	L.length=0;
	L.MaxSize=InitSize;
}

void InCreaseSize(SeqList &L,int len){
	ElemType* p =L.data;
	L.data=(ElemType*)malloc(sizeof((L.MaxSize+len)*ElemType)));
	for(int i=0; i<L.length; i++){// Copy the original data
		L.data[i]=p[i];
	}
	free(p);	// Free the original space
}

int main(a){
	SeqList L;
	InitList(L);
	InCreaseSize(L,5);
	return 0
}

Copy the code
  • Insert operation: Insert new element E at position I (1<= I <=L.length+1) of sequence table L
bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1) {// Check whether the I value is valid.
		return false;
	}
	if(L.length>=MaxSize){	// The current storage space is full and cannot be inserted
		return false;
	}
	for(intj=L.length; j>=i; j++){// The element moves back in the ith position and beyond.
		L.data[j]=L.data[j- 1];
	}
	L.data[i- 1]=e;
	L.length++;
	return true;
}
Copy the code
  • Delete operation: Delete the element at position I (1<= I <=L.length) in order table L, returned by reference variable e.
bool ListDelete(SqList &L,int i,int &e){
	if(i<1||i>L.length){
		return false;
	}
	e=L.data[i- 1];	// Return the deleted array to variable e
	for(intj=i; j<L.length; j++){ L.data[j- 1]=L.data[j];
	}
	L.length--;	// The real control over the length of the table is length, regardless of whether the last element is deleted, as long as the length is reduced by one.
	return true;

}
Copy the code
  • Lookup by value (sequential lookup) : Searches the sequence table L for the first element whose value is equal to e and returns its bit order.
int LocateElem(SqList L,ElemType e){
	for(int i=0; i<L.length; i++){if(L.data[i]==e){
			return i+1;	// Array subscript value + 1 = bit order value}}return 0;	// If 0 is returned, the search failed
}
Copy the code