1. Definition and characteristics of linear table
-
Linear table: a finite sequence consisting of n (n > = 0) elements with the same data characteristics
- Length of linear table: number of elements n
- Empty table: when n = 0
-
For non empty linear tables or linear structures, features:
- There is a unique data element called "first"
- There is a unique data element called "last"
- Except for the first, each data element in the structure has only one precursor
- Except for the last one, each data element in the structure has only one successor
2. Sequential representation and implementation of linear table
2.1 sequential storage representation of linear table
-
Sequential List: a set of storage units with continuous addresses are used to store the data elements of the linear table in turn
- A sequential storage structure or sequential image, also known as a linear table
- characteristic:
- Logically adjacent data elements
- The physical order is also adjacent
-
It is assumed that each element of the linear table needs to occupy l storage units, and the storage address of the first unit occupied is taken as the storage starting position of the data element
-
The storage location LOC(ai+1) of the I + 1st data element and the storage location LOC(ai) of the i-th data element satisfy the following relationship
L O C ( a i + 1 ) = L O C ( a i ) + l LOC(a_{i+1}) = LOC(a_i) + l LOC(ai+1)=LOC(ai)+l -
The storage location of the ith element ai of the linear table is
L O C ( a i ) = L O C ( a 1 ) + ( i − 1 ) ∗ l LOC(a_i) = LOC(a_1) + (i-1)*l LOC(ai)=LOC(a1)+(i−1)∗l- LOC(ai) is often referred to as the starting position or base address of a linear table
-
As long as the starting position of the linear table is determined, any data element in the linear table can be stored randomly, so the sequential storage structure of the linear table is a random storage storage structure
-
-
Arrays are usually used to describe sequential storage structures in data structures
-
Because the length of the linear table is variable and the maximum storage space required varies with different problems, the linear table is represented by a dynamically allocated one-dimensional array in C language
#define MAXSIZE 5 // Maximum possible length of linear table typedef struct { ElemType *elem; // Base address of storage space int length; // Current length } SqList; // The structure type of the sequence table is SqList- ElemType is customized for unified description. In practical application, users can define the data types of data elements in the table according to actual needs
- Can be basic data type
- int, float, char, etc
- It can also be a construction data type
- struct structure type
- Can be basic data type
- ElemType is customized for unified description. In practical application, users can define the data types of data elements in the table according to actual needs
-
-
Represents an example of sequential storage of polynomials
P n ( x ) = p 1 x e 1 + p 2 x e 2 + ⋯ + p m x e m P_n(x) = p_1x^{e_1} + p_2x^{e_2} + \cdots + p_mx^{e_m} Pn(x)=p1xe1+p2xe2+⋯+pmxem0 ≤ e 1 < e 2 < ⋯ < e m = n 0 \leq e_1 < e_2 < \cdots < e_m = n 0≤e1<e2<⋯<em=n
- Use a linear table with length m and two data items (coefficient term and index term) for each element
[ ( p 1 , e 1 ) , ( p 2 , e 2 ) , ⋯ , ( p m , e m ) ] [(p_1,e_1),(p_2,e_2),\cdots,(p_m,e_m)] [(p1,e1),(p2,e2),⋯,(pm,em)]
#define MAXSIZE 5 // Maximum possible length of linear table typedef struct { // Definition of polynomial float coef; // coefficient int expn; // index } Polynomial; typedef struct { Polynomial *elem; // Base address of storage space int length; // Number of current terms in polynomial } SqList; // The sequential storage structure type of polynomials is SqList
2.2 implementation of basic operations in sequence table
2.2.1 initialization
-
Construct an empty sequence table
-
Steps:
- Dynamically allocate a predetermined size array space for the sequence table, so that elem points to the base address of this space
- Set the current length of the table to 0
void InitList(SqList* L) {
L->abc = (ABC *) malloc(MAXSIZE * sizeof(ABC));
L->length = 0;
printf("Init Success\n");
}
2.2.2 value
- Obtain the value of the ith data element in the sequence table according to the specified position sequence number i
void GetElem(SqList* L, int i) {
printf("Get Success\n");
printf("first = %d\n", L->abc[i].first);
printf("second = %d\n", L->abc[i].second);
}
2.2.3 search
- Compare from the first element to obtain successful data
void LocateElem(SqList* L, int value) {
printf("Locate Success\n");
int j;
for (int i = 0; i < L->length; i++)
{
j = L->abc[i].second;
if (j == value)
{
printf("index = %d\n", i);
}
}
}
-
When searching, the expected value of the number of data elements that need to be compared with the given value in order to determine the position of elements in the sequence table is called the Average Search Length (ASL) of the search algorithm when the search is successful
-
Suppose pi is the probability of finding the ith element, and Ci is the number of keywords that have been compared with the given value when finding the ith record in the table whose keyword is equal to the given value, then in the linear table with length n, the average search length when the search is successful is
A S L = ∑ i = 1 n p i c i ASL = \sum_{i=1}^{n}{p_ic_i} ASL=i=1∑npici
In general, Ci = i, pi = 1/n, so ASL can be simplified to
A S L = 1 n ∑ i = 1 n i = n + 1 2 ASL = \frac{1}{n} \sum_{i=1}^{n}{i} = \frac{n+1}{2} ASL=n1i=1∑ni=2n+1
Therefore, the average time complexity of the sequential table search by value algorithm is O(n)
2.2.4 insertion
-
Insert a new data element e at the ith position of the table to make the linear table with length n
( a 1 , ⋯ , a i − 1 , a i , ⋯ , a n ) (a_1,\cdots,a_{i-1},a_i,\cdots,a_n) (a1,⋯,ai−1,ai,⋯,an)
Become a linear table with length n+1
( a 1 , ⋯ , a i − 1 , e , a i , ⋯ , a n ) (a_1,\cdots,a_{i-1},e,a_i,\cdots,a_n) (a1,⋯,ai−1,e,ai,⋯,an)-
The logical relationship between data elements ai-1 and ai has changed
-
In the sequence table, because logically adjacent data elements are also adjacent in physical location, unless i = n+1, the elements must be moved to reflect the change of this logical relationship
-
Generally, when inserting an element at position I (1 < = I < = n), it is necessary to start from the last element, i.e. the nth element, and move back one position successively until the ith element (n-i+1 elements in total)
-
-
Steps:
- Determine whether the insertion position i is legal
- Judge whether the storage space of the sequence table is full
- Move the elements from the nth to the ith position backward one position in turn to vacate the ith position
- Put the new element e in position i
- Table length plus 1
void ListInsert(SqList* L, ABC abc, int index) {
if (index < 0 || index > L->length || L->length == MAXSIZE)
{
printf("Insert Error\n");
return 0;
}
int i = L->length - 1;
while ((i - index) != -1)
{
L->abc[i + 1] = L->abc[i];
i--;
}
L->abc[index] = abc;
L->length += 1;
printf("Insert Success\n");
}
- Assuming that pi is the probability of inserting an element before the ith element, and Eins is the expected value (average number) of times to move an element when inserting an element in a linear table with length n, then
E i n s = ∑ i = 1 n + 1 p i ( n − i + 1 ) E_{ins} = \sum_{i=1}^{n+1}{p_i(n-i+1)} Eins=i=1∑n+1pi(n−i+1)
In general, pi = 1/(n+1), so Eins can be simplified to
E i n s = 1 n + 1 ∑ i = 1 n + 1 ( n − i + 1 ) = n 2 E_{ins} = \frac{1}{n+1} \sum_{i=1}^{n+1}{(n-i+1)} = \frac{n}{2} Eins=n+11i=1∑n+1(n−i+1)=2n
Therefore, the average time complexity of the sequential table insertion algorithm is O(n)
2.2.5 deletion
-
Delete the ith element of the table to make the linear table with length n
( a 1 , ⋯ , a i − 1 , a i , a i + 1 ⋯ , a n ) (a_1,\cdots,a_{i-1},a_i,a_{i+1}\cdots,a_n) (a1,⋯,ai−1,ai,ai+1⋯,an)
Become a linear table with length n-1
( a 1 , ⋯ , a i − 1 , a i + 1 , ⋯ , a n ) (a_1,\cdots,a_{i-1},a_{i+1},\cdots,a_n) (a1,⋯,ai−1,ai+1,⋯,an)- The logical relationship between data elements ai-1, ai and ai+1 has changed. In order to reflect this change in the storage structure, it is also necessary to move the elements
- Generally, when deleting the I (1 < = I < = n) th element, move the i+1 to n (n-i elements in total) forward one position in turn
-
Steps:
- Judge whether the deletion location i is legal
- Move the elements in positions i+1 to n forward one position in turn
- Table length minus 1
void ListDelete(SqList* L, int index) {
int i = L->length;
if (index < 0 || index > (L->length - 1))
{
printf("Delete Error\n");
return 0;
}
while ((i - 1 - index) != -1)
{
L->abc[index] = L->abc[index+1];
index++;
}
L->length -= 1;
printf("Delete Success\n");
}
- Assuming that pi is the probability of deleting the ith element and Edel is the expected value (average number) of times to move an element when deleting an element in a linear table with length n, then
E d e l = ∑ i = 1 n p i ( n − i ) E_{del} = \sum_{i=1}^{n}{p_i(n-i)} Edel=i=1∑npi(n−i)
In general, pi = 1/n, so Edel can be simplified to
E d e l = 1 n ∑ i = 1 n ( n − i ) = n − 1 2 E_{del} = \frac{1}{n} \sum_{i=1}^{n}{(n-i)} = \frac{n-1}{2} Edel=n1i=1∑n(n−i)=2n−1
Therefore, the average time complexity of the sequential table insertion algorithm is O(n)
Sequence table summary
- A sequential table can randomly access any element in the table, and its storage location can be expressed by a simple and intuitive formula
- However, this feature also causes the disadvantages of this storage structure:
- A large number of elements need to be moved when inserting or deleting out
- Because the array has the static characteristics of relatively fixed length, when the number of data elements in the table is large and changes greatly, the operation process is relatively complex, which will inevitably lead to a waste of storage space
Test code
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
void InitList(SqList);
void GetElem(SqList);
void LocateElem(SqList);
void ListInsert(SqList, ABC);
void TraverseList(SqList);
void ListDelete(SqList);
typedef struct {
int first;
int second;
} ABC;
typedef struct {
ABC* abc;
int length;
} SqList;
int main() {
SqList L;
ABC a;
ABC b;
ABC c;
InitList(&L);
printf("****************\n");
a.first = 1;
a.second = 0;
c.first = 3;
c.second = 2;
L.abc[0] = a;
L.length += 1;
L.abc[1] = c;
L.length += 1;
TraverseList(&L);
printf("****************\n");
GetElem(&L, 0);
printf("****************\n");
LocateElem(&L, 2);
printf("****************\n");
b.first = 2;
b.second = 1;
ListInsert(&L, b, 1);
TraverseList(&L);
printf("****************\n");
ListDelete(&L, 2);
TraverseList(&L);
printf("****************\n");
}
void InitList(SqList* L) {
L->abc = (ABC *) malloc(MAXSIZE * sizeof(ABC));
L->length = 0;
printf("Init Success\n");
}
void GetElem(SqList* L, int i) {
printf("Get Success\n");
printf("first = %d\n", L->abc[i].first);
printf("second = %d\n", L->abc[i].second);
}
void LocateElem(SqList* L, int value) {
printf("Locate Success\n");
int j;
for (int i = 0; i < L->length; i++)
{
j = L->abc[i].second;
if (j == value)
{
printf("index = %d\n", i);
}
}
}
void ListInsert(SqList* L, ABC abc, int index) {
if (index < 0 || index > L->length || L->length == MAXSIZE)
{
printf("Insert Error\n");
return 0;
}
int i = L->length - 1;
while ((i - index) != -1)
{
L->abc[i + 1] = L->abc[i];
i--;
}
L->abc[index] = abc;
L->length += 1;
printf("Insert Success\n");
}
void ListDelete(SqList* L, int index) {
int i = L->length;
if (index < 0 || index > (L->length - 1))
{
printf("Delete Error\n");
return 0;
}
while ((i - 1 - index) != -1)
{
L->abc[index] = L->abc[index+1];
index++;
}
L->length -= 1;
printf("Delete Success\n");
}
void TraverseList(SqList* L) {
printf("Traverse Success\n");
for (int i = 0; i < L->length; i++)
{
printf("abc[%d] : first = %d, second = %d\n", i, L->abc[i].first, L->abc[i].second);
}
printf("length = %d\n", L->length);
}