Table of contents
1. Linear table and its logical structure
2. Abstract data type description of linear table
Second, the sequential storage structure of the linear table
2. The realization of the basic operation of the sequence table
(2) Initialize the linear table InitList(&L)
(3) Destroy the linear table DestroyList(&L)
(4) Determine whether the linear table is an empty table ListEmpty(L)
(5) Find the length of the linear table ListLength(L)
(6) Output linear table DispList(L)
(7) Find the value of a data element in the linear table GetElem(L,i,e)
(8) Find LocateElem(L,e) by element value
(9) Insert data element ListInsert(&L,i,e)
(10) Delete the data element ListDelete(&L,i,e)
1. Linear table and its logical structure
1. Definition of Linear Table
(1) Definition
A linear list refers to a finite sequence of data elements with the same characteristics
(2) indicates
The linear table is represented by two-tuples as
,in:
D={
|
,
,For Elem Type } //Elem Type is a custom type identifier
R={r}
r={<
>|
} //and
adjacent (ordered)
(3) Characteristics
- Finiteness: the number of elements in a linear table is finite
- Consistency: All elements in a linear table have the same properties. From a realistic point of view, all elements have the same data type
- Sequentiality: The relative positions of all elements in a linear table are linear, that is, there are unique start and end elements, and in addition, each element has only unique predecessor and successor elements. The position of the elements in the linear table depends only on their ordinal numbers, so there can be two elements with the same value in a linear table.
(4) Note
- In the linear table, each data element is uniquely determined by its logical sequence number.
(represents the logical sequence number) elements are
, then the general representation of the linear table is
,in
Also known as the header element,
Also known as the footer element. - Elements in a linear table exhibit a linear relationship.
2. Abstract data type description of linear table
ADT List
{ data object:
D={|,,For Elem Type} //Elem Type is a custom type identifier Data relationship:
R={<>|,
,
} //andadjacent (ordered)
Basic operations:
InitList(&L): Initialize the linear list and construct an empty linear list L
DestroyList(&L): Destroy the linear table and release the memory space occupied by the linear table L
ListEmpty(L): Determine whether the linear table is an empty table, if L is an empty table, return true, otherwise return false
ListLength(L): Find the length of the linear list and return the number of elements in L
DispList(L): Output the linear table, when the linear table L is not empty, sequentially display the value range of each node in L
GetElem(L,i,&e): Find the value of a data element in the linear table, and use e to return the first element in L() element value
LocateElem(L,e): Search by element value, return the serial number of the first element in L whose value range is equal to e, if such an element does not exist, the return value is 0
ListInsert(&L,i,e): Insert data elements, in the Lth
A new element e is inserted at the position, and the length of L is increased by 1
ListDelete(&L,i,&e): delete data elements, delete the first
elements and return their value with e, minus 1 from the length of L
}
3. Examples
Suppose there are two sets A and B, respectively represented by two linear tables LA and LB, that is, the data elements in the linear table are the elements in the set. Design an algorithm to find a new set using the basic operations of linear tables
, that is, put the union of the two sets in the linear table LC.
void unionList(List LA,List LB,List &LC)
{
int lena,i;
ElemType e;
InitList(LC) //Initialize LC
for(i=1;i<=ListLength(LA),i++) //Copy all elements in LA into LC
{
GetElem(LA,i,e); //Take the ith element in LA and assign it to e
ListInsert(LC,i,e); //Insert element e into LC
}
lena=ListLength(LA); //Find the length of the linear table LA
for(i=1;i<=ListLength(LB);i++) //Loop through each element in LB
{
GetElem(LB,i,e); //Take the i-th element in LB and assign it to e
if(!LocateElem(LA,e)) //Determine if e is in LA
ListInsert(LC,++lena,e) //If e is not in LA, insert it into LC
}
}Second, the sequential storage structure of the linear table
1. Sequence table
(1) Definition
The sequential storage structure of the linear table is to store all the elements in the linear table sequentially in a continuous storage space starting from the specified storage location in the computer memory according to their logical order. Since two logically adjacent elements in the linear table are also adjacent in their storage locations in the corresponding sequential table, this mapping becomes a direct mapping. The sequential storage structure of the linear table is simply referred to as the sequential table.
[Note]
- Assuming that the element type of the linear table is ElemType, the size of the storage space (that is, the number of bytes) occupied by each element is sizeof(ElemType), and the size of the storage space occupied by the entire linear table is n*sizeof(ElemType), where n Indicates the length of the linear table.
- In the C/C++ language, the array type is used to implement the sequence table, that is, the array stores the elements of the linear table and their logical relationships. The basic type of the array is the type of the elements in the linear table, and the size of the array (ie the upper bound of the array - the next + 1) It must be greater than or equal to the length of the linear table, otherwise the array cannot store all the elements of the corresponding linear table.
- The array size MaxSize is generally defined as an integer variable. If you estimate that a linear table will not exceed 50 elements, you can define MaxSize as 50:
#define MaxSize 50
- When declaring the sequential storage type of the linear table, a data array is defined to store all elements in the linear table, and an integer variable length is also defined to store the actual length of the linear table, and the structure type SqList is used to represent the following:
typedef struct
{
ElemType data[MaxSize]; //store the elements in the linear table
int length; //Store the length of the linear table
}SqList; //Sequence table type2. The realization of the basic operation of the sequence table
For simplicity, assuming ElemType is of type int, use the following custom type statement:
typedef int ElemType;
[Note] Both the sequence table pointer L and the sequence table Q can provide a sequence table, but the former provides the sequence table indirectly through the pointer L, and its definition method is SqList *L, and the latter directly provides the sequence table, and its definition method is SqList Q. The former refers to the length field as L->length, and the latter refers to the length field as Q.length. The reason why the sequence table pointer is used is mainly to facilitate the design of the sequence table release algorithm, and to save the space allocated by the formal parameter when the sequence table pointer is passed between functions.
(1) Create a sequence table
The overall creation sequence table is introduced here, that is, the sequence table L is created by the array elements a[0..n-1]. The method is to put each element in the array a into the sequence list in turn, and assign n to the length field of the sequence list. The algorithm is as follows:
void CreatList(SqList *&L,ElemType a[],int n) //Build a sequential list from n elements in a
{
int i=0,k=0; //k represents the number of elements in L, and the initial value is 0
L=(SqList *)malloc(sizeof(SqList)); //Allocate space for storing linear tables
while(i>n) //i scan array a
{
L->data[i]=a[i]; //Store element a[i] in L
k++;j++;
}
L->length=k; //Set the length of L to k
}(2) Initialize the linear table InitList(&L)
Constructing an empty linear table actually only needs to allocate the storage space of the linear table and set the length field to 0. (The time complexity of this algorithm is O(1))
void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList)) //Allocate space for storing linear tables
L->length=0; //Set the length of the empty linear table to 0
}(3) Destroy the linear table DestroyList(&L)
The function of this operation is to release the memory space occupied by the linear table L. (O(1))
void DestroyList(SqList *&L)
{
free(L); //Free the sequential tablespace pointed to by L
}(4) Determine whether the linear table is an empty table ListEmpty(L)
This operation returns a boolean value indicating whether L is an empty list. Returns true if L is an empty list, otherwise returns false. (O(1))
bool ListEmpty(SqList *L)
{
return(L->length==0);
}(5) Find the length of the linear table ListLength(L)
int ListLength(SqList *L)
{
return(L->length);
}(6) Output linear table DispList(L)
This operation displays the value of each element in L in turn. (O(n))
void DispList(SqList *L)
{
for(int i=0;i<L->length;i++)
print("%d",L->data[i]);
printf("\n");
}(7) Find the value of a data element in the linear table GetElem(L,i,e)
bool GetElem(SqList *L,ElemType &e)
{
if(i<1||i>L->length)
return false;
e=L->data[i-1];
return true;
}(8) Find LocateElem(L,e) by element value
int LocateElem(SqList *L,ElemType e)
{
int i=0;
while(i<L->length&&L->data[i]!=e)
i++;
if(i>=L->length) //return 0 if not found
return 0;
else
return i+1; //return its logical sequence number
}(9) Insert data element ListInsert(&L,i,e)
bool ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if(i<1||i>L->length+1) //i>=1&&i<=n+1 meets the condition
return false;
i--;
for(j=L->length;j>i;i--)
L->data[j]=L->data[j-1];
L-<data[i]=e;
L->length++;
return true;
}(10) Delete the data element ListDelete(&L,i,e)
bool ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if(i<1||i>L->length)
return false;
i--;
for(j=i;i<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return true;
}3. Examples
- Assuming that a linear table is represented by a sequential table, an algorithm is designed to delete all elements whose value is equal to x. The time complexity of the algorithm is required to be O(n) and the space complexity is O(1).
//Algorithm one
void delnode1(SqList *&L,ElemType x)
{
int k=0,i;
for(i=0;i<L->length;i++)
if(L->data[i]!=x)
{
L->data[k]=L->data[i];
k++;
}
L->length=k;
}
//Algorithm 2
void delnode2(SqList *&L,ElemType x)
{
int k=0,i=0;
while(i<L->length)
{
if(L->data[i]!=x)
k++;
else
L->data[i-k]=L->data[i];
i++;
}
L->length-=k
}- There is a sequence table L, assuming that the element type ElemType is an integer, design an algorithm as efficient as possible, take the first element as the dividing line (reference), move all elements less than or equal to it to the front of the reference, and move all elements Elements larger than it are moved to the back of the datum.
//Algorithm one
int partition1(SqList *&L)
{
int i=0,j=L->length-1;
ElemType pivot=L->data[0];
while(i<j)
{
while(i<j&&L->data[j]>pivot)
j--;
while(i<j&&L->data[i]<=pivot)
i++;
if(i<j)
swap(L->data[i],L->data[j]);
}
swap(L->data[0],L->data[i]);
}
//Algorithm 2
void partition2(SqList *&L)
{
int i=0,j=L->length-1;
ElemType pivot=L->data[0];
while(i<j)
{
while(j>i&&L->data[j]>pivot)
j--;
L->data[i]=L->data[j];
while(i<j&&L->data[j]<=pivot)
i++;
L->data[j]=L=data[i];
}
L->data[i]=pivot;
}- There is an order table L, assuming that the element type ElemType is integer, design an algorithm that is as efficient as possible to move all odd numbers to the front of even numbers.
//Algorithm one
void move1(SqList *&L)
{
int i=0,j=L->length-1;
while(i<j)
{
while(i<j&&L->data[j]%2==0) //Scan from right to left for an odd element
j--;
while(i<j&&L->data[i]%2==1) //Scan from left to right to find an even element
i++;
if(i<j)
swap(L->data[i],L->data[j]);
}
}
//Algorithm 2
void move2(SqList *&L)
{
int i=-1,j;
for(j=0;j<=L->length-1;j++)
{
if(L->data[j]%2==1) //When j points to an odd number
{
i++; //Increment the number of odd intervals by 1
if(i!=j) //If i is not j, swap L->data[i] and L->data[j]
swap(L->data[i],L->data[j]);
}
}
}