Linear table and its logical structure
1. Definition of linear tables
A linear list is a finite sequence of data elements with the same properties.
The number of elements in the sequence is called the length of the linear list, denoted by n (n>=0). When n=0, the linear table is empty, that is, the table does not contain any data elements.
The first element in a linear table is called the header element, and the last element is called the tail element.
A linear list is ordered in position, that is, the ith element is behind the I -1 element and before the I +1 element. The order in this position is a linear relationship, so a linear list is a linear structure.
2. Abstract data type description for linear tables
ADT List{
// The I in the parentheses of the data object is the subscript
D = {a(i)|1=<i<=n, n>=0, a (I) belongs to ElemType}// Data relation
R = {<a(i), a(i+1)>, a(i+1Belongs to D, I =1,..., n- 1}
// Basic operations
InitList(&L) This method initializes L to an empty linear table
DestroyList(&L) // This method will free up the storage space occupied by L
ListEmpty(L) Return true if L is empty, false otherwise
DisPlayList(L) // Outputs the values of each node in the linear table in order
GetElem(L, i, &e) (1=< I <=ListLength(L)); (2 =< I <=ListLength(L))
LocateElem(L, e) // Returns the sequence number of the first data element in L whose value is equal to e
ListInsert(&L, i, e) // Insert e before the ith element of L to increase the length of L by 1
ListDelete(&L, i, &e) // Remove the ith element of L and return its value with e
}
Copy the codeSecond, the sequential storage structure of linear tables
1. Sequence table
The sequential storage structure of a linear table is to store the data elements in a linear table in a logical order into a contiguous storage space at a specified location in the computer memory. In this case, the location of the header element is the first address of the specified storage space, and the i-th element is immediately before the i-th +1 element.
Suppose that the data element in a linear table is ElemType, the storage space occupied by each data element is sizeof(ElemType), and the storage space occupied by the entire linear table is n*sizeof(ElemType), where N is the length of the linear table.
In C/C++, the two adjacent elements of an array are also adjacent in memory, and the storage structure of a sequential table is exactly the same, so in C/C++ we can use arrays to implement a sequential table.
2. Basic algorithm implementation of sequence table
We first define the types of the sequential table and the data elements in the sequential table:
#define INIT_LIST_LEN 50
#define INCREACEMENT_NUM 20
#define ERROR -1
#define OK 1
#define NULL_VALUE -51
typedef char ElemType;
typedef struct {
ElemType *data;
int length;
int max_size;
}LinerList;
Copy the codeElemType is the data element type in the order table, and LinerList is the type of the order table.
In the order table, we define an ElemType array pointer data, which points to the storage space where the ElemType data is stored.
In use, data can be directly regarded as an ElemType array, but different from array, the size of data (equivalent to the length of array) can be dynamically changed.
Length is the current length of the order table, and max_size is the maximum number of elements that the order table can currently store.
When length is greater than max_size, realloc allocates a larger chunk of memory to data (the size is the original size plus INIT_LIST_LEN times sizeof(ElemType)).
Let’s define the basic operation of the order table:
void InitList(LinerList*& L) {
L = (LinerList*)malloc(sizeof(LinerList));
L->data = (ElemType*)malloc(INIT_LIST_LEN * sizeof(ElemType));
L->max_size = INIT_LIST_LEN;
L->length = 0;
}
void DestroyList(LinerList*& L) {
free(L->data);
free(L);
L = NULL;
}
bool ListEmpty(LinerList L) {
// L length is less than 0 when L is not initialized
// L length equals 0 when L is initialized but null
// In both cases L is considered null
if (L->length <= 0) {
return true;
}
else {
return false; }}int ListLength(LinerList L) {
// Return -1 when L is not initialized
if (L->length >= 0) {
return L->length;
}
else{
returnERROR; }}void DisplayList(LinerList L) {
if (L->length < 0) {
printf("This list is not inited.\n");
}
else if(L->length == 0) {printf("This list is empty.\n");
}
else {
for (int i = 1; i <= L->length; i++) {
printf("ElmType %2d: %c\n", i, L->data[i]); }}}void GetElem(LinerList L, int i, ElemType* e) {
if (i <= 0 || i > L.length) {
printf("invalid integer i.\n");
}
else{ *e = L.data[i]; }}int LocateElem(LinerList L, ElemType e) {
// contains error handling
for (int i = 1; i <= L.length; i++) {
if (L.data[i] == e) {
returni; }}return 0;
}
Copy the codeListInsert:
int ListInsert(LinerList* L, int i, ElemType e) {
if (L->length == L->max_size) {
L->data = (ElemType*)realloc(L->data, (L->max_size + INCREACEMENT_NUM) * sizeof(ElemType));
L->max_size += INCREACEMENT_NUM;
}
if (i > L->length + 1 || i <= 0) {
return ERROR;
}
else {
for (int k = L->length; k >= i; k--) {
L->data[k + 1] = L->data[k];
}
L->data[i] = e;
L->length++;
}
return OK;
}
Copy the codeBefore inserting data elements, we check whether the order table has reached its maximum size. If the order table has reached its maximum size, we realloc reallocate a larger memory and increase the maximum size of the order table by INCREACEMENT_NUM (that is, 20).
If the order table has not reached its maximum capacity, we first check the validity of insert position I.
Obviously it’s not valid if I is less than or equal to 0 and I is greater than the order length plus 1.
We insert when we are sure that I is valid.
First we move the ith element and all subsequent elements back one place, then we insert the data element E into the ith position and increase the length of the order table by one.
ListDelete:
int ListDelete(LinerList* L, int i, ElemType* e) {
if (i > L->length || i <= 0) {
return ERROR;
}
else {
*e = L->data[i];
for (int k = i; k < L->length - 1; k++) {
L->data[k] = L->data[k + 1]; } L->data[L->length] = NULL_VALUE; L->length--; }}Copy the codeAs with inserting data elements, we check the validity of I before performing the delete operation, and perform the next delete operation only when the value of I is valid.
Before deleting the target data element, we assign its value to the data element E, and then delete it in the order table with the length of the order table reduced by one.
When deleting a data element, we move all the data elements following the data element forward one place, assign the value of the last data element to a null value, and finally subtract the length of the sequence table by one.
Testing:
int main(a) {
LinerList* L = NULL;
InitList(L);
ElemType t;
ElemType a = 'a';
ElemType b = 'b';
// Check whether the sequence table is empty
if (ListEmpty(*L)) {
printf("true\n");
}
else {
printf("false\n");
}
// Delete the sequence table when it is empty
ListDelete(L, 1, &t);
// Outputs the sequence table when the sequence table is empty
DisplayList(*L);
// The sequence table is empty
printf("the locate is %d\n", LocateElem(*L, b));
// Get the order table length
printf("list length: %d\n", ListLength(*L));
for (int i = 0; i < 100; i++) {
ListInsert(L, 1, a);
}
// Check whether the sequence table is empty
if (ListEmpty(*L)) {
printf("true\n");
}
else {
printf("false\n");
}
// Insert the sequence expression to the maximum length
ListInsert(L, 10, b);
// Delete the sequence when it reaches the maximum length
ListDelete(L, 1, &t);
ListDelete(L, 1, &t);
// Given too large I
ListInsert(L, 100, a);
ListInsert(L, 101, a);
// The sequence table is not empty
printf("the locate is %d\n", LocateElem(*L, b));
// Get the order table length
printf("list length: %d\n", ListLength(*L));
// Outputs the sequence table
DisplayList(*L);
int c;
scanf_s("%d", &c);
}
Copy the code3. Chain storage structure of linear list
1, the linked list
In the chain store, each node not only contain elements of provincial information (this is known as data fields), also contains elements of the logical relationship between information, which contains the subsequent precursor node address information (this is called a pointer domain), so that we can through the precursor node pointer in the domain information to easily find the subsequent node location.
Because each data element in the sequence table has only one precursor node and one successor node at most, when chained storage is used, only one pointer field is generally set in each node to point to the location of the successor node. The linked list thus constituted is called one-way linked list, or singly linked list for short.
Another method is to set up two pointer fields in each node, one for the precursor node and one for the successor node, thus forming a linked list called a double-linked list.
In a singly linked list, each node has only one pointer to its successor node, so when we visit a node, we can only access its successor node, not its predecessor node. In a double-linked list, since each node contains Pointers to both precursor nodes and successor nodes, after visiting a node, we can access both its precursor nodes and its successor nodes in turn.
In chained storage of linear lists, to facilitate the implementation of insert and delete algorithms, each strap has a head node, and the list is uniquely identified by a pointer to the head node.
In a single linked list, each node should contain the data field that stores the element and the pointer field that points to the next node. We use the structure of C language to define the node type of the single linked list:
typedef char ElemType;
typedef struct ListNode {
ElemType data;
ListNode* next;
} LinkList;
Copy the codeFor double-linked lists. The type definition is similar to that of a single linked list, but unlike a single linked list, a double linked list has two pointer fields.
typedef char ElemType;
typedef struct DListNode {
ElemType data;
DListNode* pre;
DListNode* next;
} DLinkList;
Copy the code2, single linked list of basic operations
(1) Head plug method to create a single linked list
A linked list is created by creating a head node and inserting a new node after the head node. Note that the head node only stores the address of the start node of the list, but does not protect the data. That is to say, the first node of the list should be the first node after the head node. The algorithm of the head interpolation method is implemented as follows:
void CreateLinkList(LinkList*& L, ElemType data[], int n) {
L = (LinkList*)malloc(sizeof(LinkList));
L->next = NULL;
for (int i = 0; i < n; i++) {
LinkList* p = (LinkList*)malloc(sizeof(LinkList)); p->data = data[i]; p->next = L->next; L->next = p; }}Copy the codeThink about:
Since the head node does not hold any data, can we define another head node type to represent a linked list?
Such as:
typedef char ElemType;
typedef struct ListNode {
ElemType data;
ListNode* next;
} ListNode;
typedef struct {
int length;
ListNode *first_node
} LinkList;
Copy the codeElemType is the data type to be saved, ListNode is the node type of the linked list, and LinkLIst is the linked list type.
We represent a linked list with a variable of type LInkList, which contains a pointer to the start node of the list and a variable length representing the length of the list.
(2) Tail insertion method to create a single linked list
Although it is easy to create a linked list using header interpolation, the order of the data elements in the list created by header interpolation is the reverse of the order of the elements in the original array. If we want the two to be in the same order, we can create a linked list using tail interpolation.
The tail interpolation method adds data elements to the end of the list, so we need a pointer to the end of the list.
Tail insertion method to create a linked list algorithm is as follows:
void ECreateLinkList(LinkList*& L, ElemType data[], int n) {
L = (LinkList*)malloc(sizeof(LinkList));
L->next = NULL;
LinkList* end = L; // End always points to the end of the list
for (int i = 0; i < n; i++) {
LinkList* p = (LinkList*)malloc(sizeof(LinkList));
p->data = data[i];
end->next = p;
end = p;
}
end->next = NULL;
}
Copy the codeDestroying a linked list requires freeing space for each node:
void DestroyList(LinkList*& L){
LinkList* p = L;
LinkList* q = p->next;
while(q ! =NULL) {
free(p);
p = q;
q = p->next;
}
free(p);
}
Copy the code(3) The basic operation of single linked list
void DestroyList(LinkList*& L){
LinkList* p = L;
LinkList* q = p->next;
while(q ! =NULL) {
free(p);
p = q;
q = p->next;
}
free(p);
}
bool ListEmpty(LinkList* L) {
if (L->next == NULL) {
return true;
}
else {
return false; }}int ListLength(LinkList* L) {
int i = 0;
LinkList* t = L;
while(t->next ! =NULL) {
i++;
t = t->next;
}
return i;
}
void DisplayList(LinkList* L) {
if (L->next == NULL) {
printf("list is empty.\n");
}
else {
while(L->next ! =NULL) {
L = L->next;
printf("node data: %c\n", L->data); }}}void GetElem(LinkList* L, int i, ListNode*& e) {
int count = 0;
while(L->next ! =NULL && count < i) {
L = L->next;
count++;
}
if (count == i) {
e = (ListNode*)malloc(sizeof(ListNode));
e->data = L->data;
e->next = L->next;
}
else {
e = NULL; }}int LocateElem(LinkList* L, ListNode* e) {
int i = 1;
L = L->next;
while(L ! =NULL&& L->data ! = e->data) { L = L->next; i++; }if (L == NULL) {
return 0;
}
else {
returni; }}Copy the codeInsert a node into a list:
int ListInsert(LinkList* L, int i, ListNode* e) {
int count = 0;
while (count < i - 1&& L ! =NULL) {
count++;
L = L->next;
}
if (L == NULL || count == 0) {
return 0;
}
else {
LinkList* t = L->next;
L->next = e;
e->next = t;
return 1; }}Copy the codeWhen inserting a node into the list, we first locate the i-1 node.
If the i-1st node exists, count=i-1 and L is not empty; If the i-1st node does not exist, L is empty. If the input I is an invalid value (such as a negative number), count is 0.
When the i-1 node exists, the next pointer of the i-1 node points directly to the node to be inserted, and the next pointer of the node to be inserted points to the I +1 node (the original i-1 node).
When the i-1 node does not exist, the i-th node has no precursor node, so the node cannot be inserted at the i-th node.
Delete a node from a linked list:
int ListDelete(LinkList* L, int i, ListNode*& e) {
int count = 0;
while (count < i - 1&& L ! =NULL) {
count++;
L = L->next;
}
if(L ! =NULL&& L->next ! =NULL&& count ! =0) {
ListNode *t = L->next;
e = (ListNode*)malloc(sizeof(ListNode));
e->data = t->data;
e->next = t->next;
L->next = t->next;
free(t);
return 1;
}
else {
e = NULL;
return 0; }}Copy the codeLike inserting a node, we need to locate the i-1 node before deleting a node, but unlike inserting a node, we need to check the existence of the i-1 node first, and only delete the i-1 node if it exists.
Why do we want to locate the i-1 node instead of the i-1 node?
This is because singly linked lists can only be accessed in one direction, and the i-th node cannot be accessed at the i-1st node. So if we go to the i-th node, we can’t point the i-1st node to the next node.
3, the basic operation of double linked list
There are two pointer fields in a double-linked list, one pointing to a precursor node and the other to a successor node.
typedef char ElemType;
typedef struct DListNode {
ElemType data;
DListNode* pre;
DListNode* next;
} DLinkList;
Copy the codeLike singly linked lists, there are two ways to create a double-linked list: head and tail.
(1) Head plug method to establish double linked list
void CreateDoubleLinkList(DLinkList *&L, ElemType data[], int n) {
L = (DLinkList*)malloc(sizeof(DLinkList));
L->pre = NULL;
L->next = NULL;
for (int i = 0; i < n; i++) {
DLinkList *t = (DLinkList*)malloc(sizeof(DLinkList));
t->next = L->next;
t->pre = L;
t->data = data[i];
L->next = t;
if(t->next ! =NULL) { t->next->pre = t; }}}Copy the codeIn the double-linked list algorithm, we first allocate storage space for the head node and assign NULL to both pointer fields of the head node.
When inserting a node into a double-linked list, we always insert the node to be inserted between the end node and the start node.
When inserting a node, we first set the next pointer of the node to be inserted to the start node (that is, L->next), and then set the pre pointer of the node to be inserted to the head node. At this point, we have established the relationship between the node to be inserted and the head node and the start node.
However, the relationship is still one-way. We also need to make the next pointer of the head node point to the node to be inserted, so that the bidirectional relationship between the head node and the node to be inserted is established.
We can use the same method to establish a bidirectional connection between the node to be inserted and its successor, but we need to check whether there is a successor node before establishing the connection. The bidirectional connection is established only when there is a successor node.
(2) Tail insertion method to establish double linked list
void ECreateDoubleLinkList(DLinkList *&L, ElemType data[], int n) {
L = (DLinkList*)malloc(sizeof(DLinkList));
L->pre = NULL;
L->next = NULL;
// Always a pointer to the end of the double-linked list
DLinkList *end = L;
for (int i = 0; i < n; i++) {
DLinkList* t = (DLinkList*)malloc(sizeof(DLinkList));
t->pre = end;
t->data = data[i];
end->next = t;
end = t;
}
end->next = NULL;
}
Copy the codeIt was last modified on 13 September 2018.
Reprinted from:
Data Structures Tutorial (2nd Edition)
Li Chunbao et al
Tsinghua University Press
ISBN: 978-7-30-14229-2 and 4