This is the 30th day of my participation in the August Text Challenge.More challenges in August

Research algorithm will

3. A singly linked list retrieves an element

Algorithm idea:

  1. Declare a node P to point to the first node in the list and initialize j as a counter, starting at 1
  2. When j< I, we iterate over the list, so that p keeps moving backwards, the counter j+1
  3. When the search succeeds, the node is returned
  4. When p is empty at the end of the list, the ith element does not exist

A singly linked list gets an element code implementation

1≤ I ≤ListLength (L)
Return e to the ith element in the table
int GetElem(LinkList L,int i,ElemType *e){
    int j=1;              /*j = counter */
 LinkList p; /* Declare a node p*/
 p=L->next; /*p points to the first node of list L */
 while(p && j<i) { /* The loop continues */ when p is not empty and the counter is not equal to IP = p - > next;/*p points to the next node */
        ++j;
    }
    if(! p || j > i)return ERROR;
   *e = p->data;
    returnOK; }Copy the code

Code analysis:

The core of the algorithm is traversal linked list, traversal in search of the specified elements, although the algorithm is simple, but if the code problem in the middle of the remember to write fault tolerance mechanism.

4. Single linked list inserts elements

How to insert a node S at any position with data field value e?

The answer:

s->next = p->next; / / the first step

p->next = s; / / the second step

First change the successor node of P, P ->next, to the successor node of S, and then change node S to the successor node of P. P ->next=s; S ->next= P ->next. In this case, the relationship between P and P ->next was first disconnected, and then S -> Next could not find a successor node.

The algorithm idea of the ith data insertion node in a single linked list is as follows:

  1. Declare a node P to point to the first node in the list and initialize j as a counter starting at 1.
  2. When j< I, the linked list is traversed so that the p pointer moves backward, constantly pointing to the next node, at which point j+1. 3. If the list is traversed to the end, the ith element does not exist.
  3. Otherwise, the search succeeds and an empty node s is created.
  4. Assign e to s->data.
  5. Single list insert: s->next = p->next; p->next = s; .
  6. Return success and the algorithm ends.

Single linked list insert element code implementation


1 ≤ I ≤ ListLength (L)
// Insert a new element e at I in the order table
int ListInsert(LinkList *L,int i,ElemType e)
{
int j=1; LinkList p,s; P = * L;while (p && j<i) /* Find the ith node */{ p=p->next; + + j; }if(! p || j>i)return ERROR; /* The ith element does not exist */

s=(LinkList *) malloc (sizeof(Node));/* Generate a new node (C standard function) */s->data=e; S - > next = p - > next;P ->next=s; /* Assigns s to the successor of p */
    return OK;
}
Copy the code