Linear table
brief introduction
Linear table(List):A finite sequence of zero or more data elements
Sequential storage structure
/*Sequential storage*/
constexpr auto MAXSIZE = 20;
constexpr auto OK = true;
constexpr auto ERROR = false;
ElemType GetElem(SqList L, int i, ElemType* e);//Read element
ElemType ListInsert(SqList* L, int i, ElemType e);//Insert element
ElemType ListDelete(SqList* L, int i, ElemType* e);//Delete element
//Define sequential storage structure
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int length;
}SqList;
//Read element
ElemType GetElem(SqList L,int i,ElemType *e) {
if (L.length == 0 || i<1 || i>L.length)/*1.L The length of cannot be 0, 2 I < 1 the read element is not in the linear table, 3 i> The element read by L.Length is not in the linear table*/
return ERROR;
*e = L.data[i - 1];
return OK;
}
Insertion and deletion of sequential structure
//Insert element
/*
* Initial condition: table already exists, 1 < = I < = listlength (L)
* Operation result: insert a new data element e before the ith position in L, and add 1 to the length of L
*/
ElemType ListInsert(SqList *L,int i,ElemType e) {
int k;
if (L->length == MAXSIZE) //Table full
return ERROR;
if (i<1 || i>L->length + 1) //i out of range
return ERROR;
if (i <= L->length) //The insertion position is not at the end of the table
{
for (k = L->length; k >= i - 1; k--)
L->data[k + 1] = L->data[k];
}
L->data[i - 1] = e;
L->length++;
return OK;
}
//Delete element
/*
* Initial condition: table already exists, 1 < = I < = listlength (L)
* Operation result: insert a new data element e before the ith position in L, and the length of L is reduced by 1
*/
ElemType ListDelete(SqList* L, int i, ElemType *e) {
int k;
if (L->length == 0) //Table empty
return ERROR;
if (i<1 || i>L->length) //i out of range
return ERROR;
*e = L->data[i-1];
if (i < L->length) //The insertion position is not at the end of the table
{
for (k = i; k < L->length; k++)
L->data[k - 1] = L->data[k];
}
L->length--;
return OK;
}
/*
code Points needing attention
* Delete element judge element is out of range
* if (i<1 || i>L->length) //i Out of range
return ERROR;
* Adding an element determines that the element is out of range
* if (i<1 || i>L->length + 1) //i Out of range
return ERROR;
*/
advantage
-
There is no need to add additional storage space to represent the logical relationship between the elements in the table
-
Quickly access elements anywhere in the table
shortcoming
- The insert delete operation requires a large number of elements to be moved
- When the linear table length changes greatly, it is difficult to determine the storage space capacity
- "Fragmentation" of storage space
Chain storage structure of linear list
Head pointer
- The pointer of the linked list to the first node. If the linked list has a head node, it refers to the pointer to the head node
- The head pointer has the function of identification, so it is often preceded by the name of the linked list
- Whether the linked list is empty or not, the header pointer is not empty. The header pointer is a required element of the linked list
Head node
- For the unification and convenience of operation, before the node of the first element is placed, its data field is generally meaningless (the length of the linked list can also be stored)
- When there is a header node, insert the node and delete the first node before the first element node, and its operation is consistent with other operations
- The header node is not necessarily a required element
typedef struct Node {
ElemType data;
struct Node* next;
} Node;
typedef struct Node* LinkList; //Define LinkList
ElemType GetElem(LinkList L, int i, ElemType* e);//Reading of linked list
ElemType ListInset(LinkList* L, int i, ElemType e);//Insertion of single linked list
ElemType ListInset(LinkList* L, int i, ElemType* e);//Deletion of single linked list
Reading of single linked list
/*
* Initial condition: table already exists, 1 < = I < = listlength (L)
* Operation result: use e to return the value of the ith element in L
*/
ElemType GetElem(LinkList L,int i,ElemType *e) {
int j = 1; //timer
LinkList p;
p = L->next; //p points to the first element of the L linked list
while (p && j<i)
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR;
*e = p->data;
return OK;
}
Insertion and deletion of single linked list
/*
* s->next = p->next;
* p->next = s;
* The code sequence of the above two sentences must not be disordered. If P - > next = s and then s - > next = P - > next, there will be a problem. S - > next = s, then the a(i+1) element has no superior
* Initial condition: table already exists, 1 < = I < = listlength (L)
* Operation result: insert a new data element E before the ith node position in L, and the length of L plus 1
*/
ElemType ListInset(LinkList *L,int i,ElemType e) {//Note that the LinkList type itself is a pointer, and L is a double pointer here
int j = 1;//timer
LinkList p, s;
p = *L;
while (p&&j<i)
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR;
s = (LinkList)malloc(sizeof(Node)); //Apply for the memory of the corresponding size of the node variable, and return the untyped address, (LinkList) is to be forcibly converted to linklist type
s->data = e;
s->next = p->next; //Connect s to p and assign the successor of p to the successor of S
p->next = s->next; //Connect s to p and assign s to the successor of p
return OK;
}
/*
* q = p->next;
* p->next = q->next;
* There are the same problems as above. You can't reverse the order when using
* Initial condition: table already exists, 1 < = I < = listlength (L)
* Operation result: delete the ith element in L and return its value with e. the length of L is reduced by 1
*/
ElemType ListInset(LinkList* L, int i, ElemType *e) {//Note that the LinkList type itself is a pointer, and L is a double pointer here
int j = 1;//timer
LinkList p, q;
p = *L;
while (p->next && j < i) //Here is p - > next instead of P, and P is used inside the loop. Note that this step q = P - > next;
{
p = p->next;
++j;
}
if (!p->next || j > i)
return ERROR;
q = p->next;
p->next = q->next;
*e = q->data; //Assign the data in the q node to e
free(q); //Let the system reclaim this node to free up memory
/*
* The free memory here is as follows:
* free What is released is the memory unit allocated by malloc pointed to by the q pointer. The q pointer itself will not be released,
* So you can then re point the q pointer to the new memory address,
* free Just tell the system that I don't want this one, but it exists before memory is allocated to others
*/
return OK;
}
The free memory here is as follows:
- free releases the memory unit allocated by malloc pointed to by the q pointer. The q pointer itself will not be released,
- So you can then re point the q pointer to the new memory address,
- free just tells the system that I don't want this one, but it exists before memory is allocated to others
About p and p - > next
- While (p&&j < I) increased
- While (P - > next & & J < I) delete
- For addition, p cannot be blank, for deletion, p - > next cannot be blank,
- Because P = P - > next, when increasing, the next value can be an empty tail,
- However, the reduction cannot be p = P - > next, that is, if P is empty at this time, there is no significance of deletion
Whole table creation of single linked table
Algorithm idea
- Declare pointer p and counter i
- Initialize an empty linked list L
- Let the pointer of the head node of L point to null, that is, the established single linked list of the head node
- Cycle:
-
Generate a new node and assign it to p
-
Randomly generated data assigned to p and p - > Data
-
Insert p between the head node and the previous new node
-
Head insertion
//The values of n elements are randomly generated, and the single chain linear table of the leading node is established
//Head insertion
void CreateListHead(LinkList *L,int n) {
LinkList p;
int i;
srand(time(0)); //Initialize random number seed
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; //Establish a single linked list of leading nodes
for ( i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node)); //Generate new node
p->data = rand() % 100+1; //Random number from 0 to 100
p->next = (*L)->next;
(*L)->next = p; //Insert new header
}
}
Tail interpolation
//Tail interpolation
void CreateListTail(LinkList *L,int n) {
LinkList p, r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L; //*r is the node pointing to the tail
for (i = 0; i < n; i++)
{
p = (Node *)malloc(sizeof(Node)); //Generate new node
p->data = rand() % 100 + 1; //Random number from 0 to 100
r->next = p; //Point the pointer of the end node at the end of the table to the new node
r = p; //Define the current new node as the footer terminal node
}
r->next = NULL;
}
Whole table deletion of single linked list
/*
* Free memory one by one
*/
ElemType ClearList(LinkList *L) {
LinkList p,q;
p = (*L)->next; //p points to the first node
while (p) //It's not at the end of the watch
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL; //The header node pointer field is null
return OK;
}
Advantages and disadvantages of single linked list structure and sequential storage structure
Storage allocation method
- Sequential storage - sequential storage units store data elements of a linear table in turn
- Linked list storage - a set of arbitrary storage units to store the data elements of a linear list
Time performance
- lookup
- Sequence O(1)
- Single linked list O(n)
- Insert delete
- Order -- average moving half of the elements in the table, O(n)
- Linked list - the time after finding the pointer at the insertion and deletion position is only O(1)
Spatial performance
- Order - pre allocated storage space is unstable
- Linked list - no allocation is required, and the number of elements is not limited
Static linked list
Static linked list storage structure of linear list
typedef struct {
ElemType data;
int cur; /*A Cursor, when 0, indicates no pointing*/
}Component,StaticLinkList[MAXSIZE];
Chain the components in the one-dimensional array space into a spare linked list, space [0] Cur is the header pointer and "0" is the null pointer
ElemType InitList(StaticLinkList space) {
int i;
for (i = 0;i < MAXSIZE;i++)
space[i].cur = i + 1;
space[MAXSIZE - 1].cur = 0; /*At present, the static linked list is empty, and the cur of the last element is 0*/
return OK;
}
Insert operation
/*If the spare space linked list is not empty, the allocated node subscript is returned; otherwise, 0 is returned*/
int Malloc_SLL(StaticLinkList space) {
int i = space[0].cur; /*The cur stored value of the first element of the current array is the first spare free subscript to be returned*/
if (space[0].cur)
space[0].cur = space[i].cur;/*Since one component is to be used, the next component is used as a backup*/
return i;
}
Insert a new data element e before the ith element in L
ElemType ListInsert(StaticLinkList L,int i,ElemType e) {
int j, k, l;
k = MAXSIZE - 1;
if (i<1 || i>ListLength(L) + 1)
return ERROR;
j = Malloc_SLL(L);
if (j)
{
L[j].data = e;
for (l = 0; l <= i - 1; l++)
k = L[k].cur;
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}
Delete the ith data element e in L
ElemType ListDelete(StaticLinkList L,int i) {
int j, k;
if (i<1||i>ListLength(L))
return ERROR;
k = MAXSIZE-1;
for (j = 0; j <= i - 1; j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[i].cur;
Free_SSL(L,j);
return OK;
}
Reclaim the idle node with subscript k to the standby linked list
void Free_SSL(StaticLinkList space,int k) {
space[k].cur = space[0].cur;
space[0].cur = k;
}
Initial condition: static linked list L already exists. Operation result: returns the number of data elements in L
int ListLength(StaticLinkList L) {
int j = 0;
int i = L[MAXSIZE-1].cur;
while (i) {
i = L[i].cur;
j++;
}
return j;
}
The static linked list will not be repeated
Circular linked list
p = rearA->next; /*Save the header node of table A,*/ rearA->next = rearB->next->next; /*Assign the first node to table B to Reala - > next*/ q = rearB->next; /**/ rearB->next = p; /*Assign the header node of the original A table to realb - > next*/ free(q); /*Release q*/
Bidirectional linked list
Bidirectional linked list storage structure of linear list
typedef struct DulNode {
ElemType data;
struct DulNode* prior;
struct DulNode* next;
}DulNode,*DuLinkList;
Principle basis
p->next->prior = p = p->prior->next
Insert operation
//Insert operation s->prior = p; //Assign p to the precursor of s s->next = p->next; //Assign p - > next to the successor of s p->next->prior = s; //Assign s to the precursor of P - > next p->next = s; //Assign s to the successor of p
Delete operation
Delete operation p->prior->next = p->next; //Assign p - > next to the successor of P - > prior p->next->prior = p->prior; //Assign p - > prior to the precursor of P - > free(p); //Release node