Linear tables — > sequential storage — > arrays

A [1] a[2] ==> array int A [10] = {… }

Typedef struct {ElemType *data; //ElemType specifies the value of the field type. }Sqlist;Copy the code
Int InitList(Sqlist *L){L->data = malloc(sizeof(ElemType) * MAXSIZE);if(! L->data)exit(0); L->length = 0; // The length of the empty table is 0return 1;
}
Copy the code
// Insert the sequence table ==> Insert e at position I in the sequence table. You start at 1, not 0. Int 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]; } } L->data[i-1] = e; // put the new element e in the ith position ++L->length; / / length + 1;return 1;
}
Copy the code
Int temp = L->data[i-1]; Int temp = L->data[i-1];Copy the code
Int ListDelete(Sqlist *L,int I){// The list is emptyif(L->length == 0) return0; // The I value is invalidif((i<1) || (i>L->length+1)) return 0;
    
    for(int j = i; j < L->length; J++) {/ / deleted element to the element after the move forward = = "covered the ith element L - > data [1] = L - > data [j]; } // Table length -1; L->length --;return 1;
}
Copy the code
The sequential linear table L already exists. */ int ClearList(Sqlist *L) {L->length=0;return 1;
}
Copy the code
Int LocateElem(Sqlist L,ElemType e) {if (L.length==0) return 0;

    int i;
    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

Two, single linked list – > linear list chain storage, in memory is not continuous

For non-empty linear tables and linear structure features:

  • There is a unique data element called “first”
  • There is a unique data element called “the last”
  • There is a unique data element called “first”

One to one, there’s a head and tail, there’s a precursor and a successor.

Single-linked list nodes

Typedef struct Node{ElemType data; Struct Node *next; // with subsequent pointer fields}Node; typedef struct Node * LinkList; //Copy the code

Single linked list logical state — linked lists with headers (header data field NULL)

Int InitList(LinkList *L) {//*L == Node **L *L = (LinkList)malloc(sizeof(Node)); // Generate a header and point to it with Lif(*L == NULL) return0; // Storage space allocation failed (*L)->next = NULL; // Empty the pointer field of the headerreturn 1;
}
Copy the code

Single linked list insertion — logic

Insert(LinkList *L,int I,ElemType e){int j = 1; LinkList p,s; p = *L;while(p &&j < I) {p = p->next; ++j; } // The ith element does not existif(! p || j>i)return0; s = (LinkList)malloc(sizeof(Node)); // create new node s s->data = e; S ->next = p->next; P ->next = s; // Assign s to the successor of preturn 1;
}
Copy the code

Single-linked lists delete elements – logic

Int ListDelete(LinkList *L,int I,ElemType *e){int j = 1; LinkList p,q; p = *L;while(p &&j < I) {p = p->next; j += 1; }if(! (p->next) || (j>i-1))return0; Q = p->next; q = p->next; P ->next = q->next; *e = q->data; // Assign q to p *e = q->data; // give e free(q); // Let the system reclaim this node, free memory;return 1;
}
Copy the code

** Single-linked list values **

Int GetElem(LinkList L,int I,ElemType *e){int j = 1; LinkList p; //p is not empty, and j is not equal to I, then the loop continueswhile(p && j<=i) { p = p->next; //p points to the next node ++j; }if(! p || j < i)return0; // if p is null or j> I, return 0 *e = p->data; //e = data of the node indicated by preturn 1;
}
Copy the code

Single – linked list before insertion method – logic

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

Single linked list after insertion method

L void CreateListTail(LinkList *L, int n){LinkList p,r; *L = (LinkList)malloc(sizeof(Node)); //r = *L;for(int i=0; i<n; i++) { p = (Node *)malloc(sizeof(Node)); P ->data = I; r->next = p; // add a pointer to a new node r = p; } // Next = null r->next = null; }Copy the code

Contrast linked list structures with sequential storage structures

Storage allocation mode:

  • Sequential storage structures store the data elements of a sex table in a sequence of contiguous storage cells.
  • Single linked list uses chain storage structure, with a set of arbitrary storage cells to store the data elements of a linear list.

Time performance:

  • Find – store O(1) sequentially, single linked list O(n).
  • Insert and delete — the storage structure takes an average of half a table long to move elements, O(n); After a single linked list looks for a pointer at a location, insert and delete to O(1).

Space performance:

  • Sequential storage structure requires pre-allocation of storage space, too large, waste space, too small, easy overflow.
  • Single-linked lists do not require pre-allocation of storage space, as long as there can be allocated, the number of elements is not limited.