A, definitions,

The data elements are different, but the elements in the same linear table must have the same characteristics, that is, belong to the same data object, and there is this order even relationship between adjacent data elements. Such finite sequences of (n>=0) elements with the same data properties are called linear lists.

The number of elements in a linear table, n, is defined as the length of the linear table, and is called empty if n = 0.

For non-empty linear tables and linear structures, the characteristics are as follows:

  • There exists a unique data element called “first”
  • There exists a unique data element called “the last”
  • Every data element in the structure except the first has a precursor
  • Every data element in the structure has a successor except the last one
Store category Sequential storage structure Single linked list storage structure
Storage allocation mode A sequence of contiguous storage cells is used to store the data elements of a linear table The chain storage structure is used to store the elements of a linear list in a group of arbitrary storage units
Time performance Find O(1), Insert, and delete O(n) Find O(n), Insert, and delete O(1)
Space performance The storage space needs to be pre-allocated. If the storage space is large, it will be wasted. If the storage space is small, it will overflow easily There is no need to allocate storage space, as long as there is an unlimited number of elements can be allocated
  • If the linear table needs to be searched frequently and insertion and deletion operations are seldom performed, the sequential storage structure is recommended. If frequent insertions and deletions are required, the single-linked list structure is recommended.
  • When the number of elements in a linear table varies greatly or the size of the elements is unknown, it is best to use a single-linked list structure, so that the size of the storage space does not need to be considered. The sequential storage structure is much more efficient if the approximate length of a linear table is known beforehand

Two, sequential storage implementation

Using an array implementation, a set of contiguous addresses of storage units, the size of the array can be specified in two ways, one is static allocation, the other is dynamic expansion.

Note: Linear tables start at 1, while arrays start at 0.

  • Advantages: Random access feature, search O(1) time, high storage density; Elements that are logically adjacent are physically adjacent;
  • Disadvantages: Insertion and deletion need to move a large number of elements.

  • 1<= index <=(7+1); 2 <= index <=(7+1);
  • Deletion: Node deletion can only be found between the blue squares, i.e. 1 <= index <= 7

2.1 Sequence Table Initialization

Let’s define some states

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0/* ElemType specifies the type of the field. The value is assumed to be int */ typedef int. / / typedefs int Status; / / typedefs int Status; / / typedefs int Status; // / typedef struct {ElemType *data; int length; }Sqlist;Copy the code

In the initialization

Status InitList(Sqlist *L){// Allocate an array space of MAXSIZE to the order table L->data = malloc(sizeof(ElemType) * MAXSIZE); // Storage allocation failed to exitif(! L->data)exit(ERROR); L->length = 0;return OK;
}
Copy the code

2.2 Insertion of sequence tables

ListLength(1) ≤ I ≤ListLength(L)+1; Insert a new element e before the ith position in L, add 1 */ Status ListInsert(Sqlist *L,int I,ElemType e){// The value of I is invalidif((i<1) || (i>L->length+1)) returnERROR; // The storage space is fullif(L->length == MAXSIZE) returnERROR; // Insert data not at the end of the tableif(i <= L->length){
        for(int j = L->length-1; j>=i-1; J -) {/ / after insert location and the location of the mobile one L - > data [j + 1) = L - > data [j]; } // Put the new element e in the ith position L->data[i-1] = e; / / length + 1; ++L->length;return OK;
    
}
Copy the code

2.3 Deleting the sequence table

/* ListDelete(Sqlist *L,int I){// List (Sqlist *L,int I)if(L->length == 0) returnERROR; // The I value is invalidif((i<1) || (i>L->length)) return ERROR;
    
    for(int j = i; j < L->length; J++) {/ / deleted element to the element after the move forward L - > data [1] = L - > data [j]; } // Table length -1; L->length --;return OK;
    
}
Copy the code

2.4 Value of the sequence table

Status GetElem(Sqlist L,int I, ElemType *e){// Checks whether the I value is reasonable. If not, an ERROR message is displayedif(i<1 || i > L.length) returnERROR; *e = l.data [i-1]; *e = l.data [i-1];return OK;
}
Copy the code

2.5 Clearing the order table

/* Initial condition: sequential linear table L already exists. */ Status ClearList(Sqlist *L) {L->length=0;return OK;
}

Copy the code

2.6 The judgment order table is empty

/* Initial condition: sequential linear table L already exists. Return TRUE if Lis an empty table; otherwise return FALSE */ Status ListEmpty(Sqlist L) {if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

Copy the code

2.7 Obtaining the Length of the Order Table (Number of elements)

int ListLength(Sqlist L)
{
    return L.length;
}

Copy the code

2.8 Output the List in sequence

Status TraverseList(Sqlist L) {int I;for(i=0; i<L.length; i++)printf("%d\n",L.data[i]);
    printf("\n");
    return OK;
}

Copy the code

2.9 The sequential table finds the element and returns the position

/* Initial condition: sequential linear table L already exists */ * Result: Return the bit order of the first data element in L that satisfies e. */ ElemType e (Sqlist L,ElemType e) {int I;if (L.length==0) return 0;
    
    for(i=0; i<L.length; i++) {if (L.data[i]==e)
            break;
    }
  
    if(i>=L.length) return 0;
    return i+1;
}
Copy the code

2.10 the test

Sqlist L; Sqlist Lb; ElemType e; Status iStatus; IStatus = InitList(&l);printf("After initialization: L length = %d\n", L.length); //1.2 Sequential table data insertionfor(int j=1; j <= 5; j++){ iStatus = ListInsert(&L, 1, j); }printf("Insert data L length: %d\n",L.length); //1.3 Sequence table values GetElem(L, 5, &e);printf("The value of the 5th element of sequence table L is :%d\n",e); ListDelete(&l, 2); ListDelete(&l, 2);printf("Order table deletes element %d with length %d\n",2,L.length); IStatus = ClearList(&l);printf("After clearing, l.length = %d\n",L.length); IStatus =ListEmpty(L);printf("L empty: I =%d(1: yes 0: no)\n",iStatus); / / 1.8 TraverseListfor(int j=1; j <= 5; j++){ iStatus = ListInsert(&L, 1, j); } TraverseList(L);Copy the code

Single linked list storage implementation

A linked list is defined recursively as either null or a reference to another node, node, that contains a reference to the next node or list.

Compared with sequential storage, storage space is allowed to be discontinuous, insertion and deletion do not need to move a large number of elements, just modify the pointer, but to find an element, you can only go through the whole list from scratch.

Header node: the node that stores the first data element in a linear list. It is the beginning node of the list.

Head pointer: A pointer to the first node (or head node or primary node) in a linked list

Header: A header is a node appended before the first node of the linked list. The value field does not contain any information (information can also be stored as required, such as the length of the linked list). The pointer field of the header points to the first element of the linked list.

Single-linked lists are divided into leading nodes and non-leading nodes. Regardless of whether there is a head node, the head pointer points to the first node of the list (with a head node pointing to a head node).

The advantages of the lead node are as follows:

  • 1. The operation on the first node of the linked list is the same as that on other nodes (easy to handle the first node).
  • 2. No matter whether the linked list is empty or not, the head pointer points to the head node, and the empty table is treated the same as the non-empty table.

List element structure

There is no head node, and the head pointer points to the head node

There’s a head node, and the head pointer points to the head node

An empty linked list with a head node

A non-empty linked list with a head node

Note: the trouble of the linked list is the modification of the pointer when inserting and deleting, which ensures continuous chain, generally broken after the first chain.

This is shown in the following code (the following code is for the leading node)

3.1 Initializing a Single-linked List A linear list

Let’s define some states

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* Initial allocation of storage space */typedef int Status; / / typedef int ElemType; / / typedef int ElemType; /* ElemType specifies the type of the ElemType Node. struct Node *next; }Node; typedef struct Node * LinkList;Copy the code

Initialize a single-linked linear list

LinkList *L = (LinkList)malloc(sizeof(Node)); // Failed to allocate storage spaceif(*L == NULL) returnERROR; (*L)->next = NULL;return OK;
}
Copy the code

3.2 Single linked list insertion

/* ListLength = 1≤ I ≤ListLength(L); Insert a new data element e after the ith position in L, and increase the length of L by 1; */ Status ListInsert(LinkList *L,int i,ElemType e){ int j; LinkList p,s; P = *L; p = *L; j = 1; 0>1>2>3>4>5 I = 3while(p && j<i) { p = p->next; ++j; } // The ith element does not existif(! p || j>i)returnERROR; // create a new Node s s = (LinkList)malloc(sizeof(Node)); // select * from s where s->data = e; / /! [](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2020/4/1/171349562f080e26~tplv-t2oaga2asx-image.image) S ->next = p->next; P ->next = s;return OK;
}

Copy the code

3.3 Deleting elements from a Single Linked List

ListLength(1≤ I ≤ListLength(L)); ListDelete(LinkList *L,int I,ElemType *e){int j; LinkList p,q; P = (*L)->next; j = 1; // find the i-1 node where p points towhile(p->next && j<(i-1)) { p = p->next; ++j; } // If I >n or I <1, the delete position is incorrectif(! (p->next) || (j>i-1))returnERROR; //q = p->next; P ->next = q->next; E *e = q->data; // Let the system reclaim this node, free memory; free(q);return OK;
}

Copy the code

3.4 Single-linked List Value

/* ListLength = 1≤ I ≤ListLength(L); */ Status GetElem(LinkList L,int I,ElemType *e){//j: count. // declare node p; LinkList p; // point node P to the first node of list L; p = L->next; / / j calculation = 1; j = 1; //p is not empty, and j is not equal to I, then the loop continueswhile(p &&j < I) {p = p->next; ++j; } // If p is empty or j> I, error is returnedif(! p || j > i)returnERROR; // data *e = p->data;return OK;
}

Copy the code

3.4 Output of single linked list elements

Linktraverse (LinkList p) {LinkList p=L->next; LinkList p=L->next; LinkList p=L->next;while(p)
    {
        printf("%d\n",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

Copy the code

3.5 Clearing single-linked lists

/* Initial condition: sequential linear table L already exists. */ Status ClearList(LinkList *L) {LinkList p,q; p=(*L)->next; /* p is the first node */while*/ {q=p->next; free(p); p=q; } (*L)->next=NULL; /* The header pointer field is null */return OK;
}

Copy the code

3.6 Single-Linked List Front Insertion method (Head insertion method)

Insert a new node into the head of the current list (after the head) in the reverse order. The key is to remember the old head and create a new one before the old head

Void CreateListHead(LinkList *L, int n){LinkList p; void CreateListHead(LinkList *L, int n){LinkList p; *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; // Insert random data before loopfor(int i = 0; i < n; P = (LinkList)malloc(sizeof(Node)); P ->data = I; P ->next = (*L)->next; // insert node P after the header; (*L)->next = p; }}Copy the code

3.7 Single Linked List After Insertion (Tail Insertion)

Add a tail pointer and insert the new node to the end of the list in the same order as the list

Void CreateListTail(LinkList *L, int n){LinkList p,r; void CreateListTail(LinkList *L, int n); *L = (LinkList)malloc(sizeof(Node)); //r = *L;for(int i=0; i<n; P = (Node *)malloc(sizeof(Node)); p->data = i; R ->next = p; // define the current new node as the table end node r = p; } next = null r->next = null; }Copy the code

3.8 the test

Status iStatus; LinkList L1,L; struct Node *L2; ElemType e; IStatus = InitList(&l);printf("L successfully initialized? (0: failed,1: succeeded) %d\n",iStatus); //2.2 Single linked list inserts datafor(int j = 1; j<=10; j++) { iStatus = ListInsert(&L, 1, j); }printf("L after insertion \n"); ListTraverse(L); GetElem(L,5,&e);printf("The value of the 5th element is: %d\n",e); IStatus = ListDelete(&l, 5, &e);printf("Delete 5th element with value :%d\n",e); ListTraverse(L); L iStatus = ClearList(&l); CreateListHead(&L, 20);printf("Collate elements that create L (pre-interpolation):\n"); ListTraverse(L); L iStatus = ClearList(&l); CreateListTail(&L, 20);printf("Collate elements that create L (interpolation):\n");
    ListTraverse(L);
Copy the code