C language to achieve a single linked list of operations of one

  • 2020-04-02 00:48:53
  • OfStack

Recently, I have reviewed some important parts of the data structure, and now I have recorded my achievements, which are mainly adapted from the examples and exercises in yan weimin's data structure (C language version). First of all, is the realization of a variety of single linked list, which contains some commonly tested knowledge points. For example, the inverse of a single linked list, the merge of a single linked list, the algorithm to find the middle node of a single linked list and so on.
The following is the definition of the structure of a single linked list:

typedef struct LNode
{
 ElemType data;
 struct LNode *next;
}LinkList;


Below is the basic operation of single linked list: among them, there are some macros, without giving some definitions of them, which can be viewed through yan weimin's data structure (C language version).


Status InitList (struct LNode **L)
{
  (*L) = (struct LNode *)malloc(sizeof(struct LNode)); //Generating head node
  if(!*L)
   exit(OVERFLOW);
  (*L)->next = NULL;
  return OK;
}

Status DestroyList(struct LNode *L)
{
  struct LNode *q;
  while(L)
  {
    q = L->next;
    free(L);
    L = q;
  }
  return OK;
}

Status ClearList(struct LNode *L)
{
  LinkList *p,*q;
  p = L->next;
  while(p)
  {
    q = p->next;
    free(p);
    p = q;
  }
  L->next = NULL;
  return OK;
}

Status ListEmpty(LinkList *L)
{
  if(L->next)
  {
    return FALSE;
  }
  else
  {
    return TRUE;

  }
}

int ListLength(struct LNode *L)
{
  int i=0;
  LinkList *p = L->next;
  while(p)
  {
    i++;
    p = p->next;
  }
  return i;
}

Status GetElem(struct LNode *L,int i,ElemType *e)
{
  int j=1;
  LinkList *p = L->next;
  while(p && j<i)
  {
    p = p->next;
    j++;
  }
  if(!p || j>i)
    return ERROR;
  *e = p->data;
  return OK;
}

int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
  int i =0;
  LinkList *p = L->next;
  while(p)
  {
    i++;
    if(compare(p->data,e))
      return i;
    p=p->next;
  }
  return 0;
}



Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
  LinkList *q,*p=L->next;
  while(p->next)
  {
    q = p->next;//Q points to the successor of p
    if(q->data == cur_e)
    {
      *pre_e = p->data;
      return OK;
    }
    p = q;
  }
  return INFEASIBLE;

}

Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
  LinkList *p;
  p = L->next;
  while(p->next)
  {
    if(p->data == cur_e)
    {
     * next_e = p->next->data;
      return OK;
    }
    p = p->next;
  }
  return INFEASIBLE;
}

Status ListInsert(struct LNode *L,int i,ElemType e)
{
  int j =0;
  struct LNode *p=L,*s=NULL;
  while(p && j<i-1)
  {
    p=p->next;
    j++;
  }
  if(!p || j>i-1)
    return ERROR;
  s = (struct LNode *)malloc(sizeof(struct LNode));
  if(!s)
    printf("malloc error~n");
  // p->next = s;
  s->data = e;
  // p->next = s;
   s->next = p->next;
   p->next = s;
   //s->next = NULL;
  // p = s;
  return OK;
}

Status ListDelete(LinkList *L,int i,ElemType *e)
{

  LinkList *p=L,*q;

   int j=0;
  while(p->next && j< i-1)
  {
    p = p->next;
    j++;
  }
  if(!p->next || j>i-1)
    return ERROR;
  q = p->next;
  p->next = q->next;
  *e = q->data;
  free(q);
  return OK;
  }

Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
  LinkList *p = L->next;
  while(p)
  {
    vi(p->data);
    p = p->next;
  }
  printf("n");
  return OK;
}


Related articles: