3.1 Definition of linear table

The linear table (List)： A finite sequence of zero or more data elements .
characteristic ：
1. It’s a sequence , There’s an order between the elements , If there are multiple elements , Then the first element has no precursor , The last element has no successors .
2. The elements of a linear table are finite .
3. Same data type .

ADT The linear table (List)

The data object set of linear table is {a1,a2,…,an}, The type of each element is DataType. among , Except for the first element a1 Outside , Every element a1 There is and only one direct precursor element , Except for the last element an Outside , Each element has and has only one immediate successor element . The relationship between data elements is one-to-one . Pictured ：

Number of linear elements n (n≥0) It’s defined as the length of a linear table , When n=0 when , Known as the empty table .

3.2 Abstract data types and basic operations of linear tables

Abstract data types ：

In a more complex linear table , A data element can be composed of several data items .
Pictured ：

Basic operation

 Operation
InitList (*L) : Initialization operation , Create an empty linear table L.
ListEmpty (L) ： If the linear table is empty , return true, Otherwise return to false.
ClearList(*L) ： Clear the linear table .
GetElem(L,i,*e) ： Put the linear table L No i Location element values are returned to e.
LocateElem(L,e) ： In the linear table L Find and given values in e Equal elements , If the search is successful , Returns the sequence number of the element in the table, indicating success ; otherwise , return 0 It means failure .
ListInsert ( *L,i,e) ： In the linear table L No i Place to insert new elements e.
ListDelete ( *L,i,*e) ： Delete linear table L pass the civil examinations i Location elements , And use e Return its value .
ListLength (L) ： Return to linear table L Number of elements of .

3.3 Sequential storage structure for linear tables

Definition ：

Sequential storage structure for linear tables , It refers to storing the data elements of the linear table in sequence with a continuous storage unit of address .
The linear table (a1,a2,…,an) Schematic diagram of sequential storage ：

Sequential storage mode

Is to find a place in memory , By occupying space , Take up some memory space , Then the data elements of the same data type are stored in this open space in turn . Since each data element of the linear table has the same type , So it can be used C Language ( Other languages are the same ) One dimensional array to realize the sequential storage structure , That is, the first The data elements are stored in the array with the subscript 0 In the , Next, the adjacent elements of the linear table are stored in the adjacent positions in the array .

Address calculation method

Array subscript is from 0 At the beginning , The first i Elements are stored in i-1 The location of . The corresponding relationship is shown in the figure ：

Suppose the occupation is c Storage unit , Then the second in the linear table i+1 Storage location of data elements and i The storage locations of data elements satisfy the following relationship (LOC Represents the function to get the storage location ).

So for the i Data element ai The storage location of can be determined by a1 It is calculated that :

3.4 Insertion and deletion of sequential storage structure

Advantages and disadvantages of sequential storage structure

advantage

● There is no need to add extra storage space to represent the logical relationship between elements in the table
● You can quickly access elements anywhere in the table

shortcoming

● Insert and delete operations need to move a large number of elements
● When the length of linear meter changes greatly , It’s hard to determine the capacity of the storage space
● Creating storage space “ debris ”

3.5 Advantages and disadvantages of single linked list structure and sequential storage structure

Storage allocation

● Sequential storage structure uses a continuous storage unit to store the data elements of linear table in turn
● Single linked list adopts chain storage structure , Use a set of arbitrary storage units to store the elements of a linear table

Time performance

lookup
● Sequential storage structure 0(1)
● Single chain list 0(n)
Insert and delete
● The sequential storage structure needs to move an average of half the elements of the table , Time is 0(n)
● After the single linked list shows the pointer at a certain position on the line , The insertion and deletion time is only 0(1)

Space performance

● Sequential storage structure needs to allocate storage space in advance , It’s big , waste , Small points are prone to overflow
● Single linked lists don’t need to allocate storage space , As long as there is, it can be allocated , The number of elements is also unlimited

3.6 Static list 3.7 Double linked list 3.8 Circular linked list summary ：