The C language bidirectional linked list implements the functional instance code to arrange the location of elements according to the frequency of use

  • 2020-05-17 06:00:23
  • OfStack

C language bidirectional linked list application

Preface:

Usually when using the music player, the songs in the playlist can be easily added, deleted, reworked and so on. But its essence can be abstracted into a bidirectional linked list. In order to make it easier for users to use, I think we can also add a function to put the most frequently played music in the head of the playlist, so how to achieve it?

Look at the code:


#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
  elemtype data;
  int freq;
  struct node * next;
  struct node * prior;
}node;
typedef struct node* dlinklist;

status visit(elemtype c){
  printf("%d ",c);
}

/* Bidirectional list initialization */
status initdlinklist(dlinklist * head,dlinklist * tail){
  (*head)=(dlinklist)malloc(sizeof(node));
  (*tail)=(dlinklist)malloc(sizeof(node));
  if(!(*head)||!(*tail))
    return ERROR;
  /* this 1 Step is crucial */ 
  (*head)->prior=NULL;
  (*tail)->next=NULL;
  (*head)->freq=0;
  (*tail)->freq=0; 
  /* When the list is empty, point the head to the tail */
  (*head)->next=(*tail);
  (*tail)->prior=(*head);
}

/* Determines whether it is empty */
status emptylinklist(dlinklist head,dlinklist tail){
  if(head->next==tail)
    return TRUE;
  else
    return FALSE;
} 

/* The tail method creates a linked list */ 
status createdlinklist(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=head,qmove=tail,pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  if(!pinsert)
    return ERROR;
  else{
    pinsert->data=data;
    pinsert->prior=pmove;
    pinsert->next=pmove->next;
    pmove->next->prior=pinsert;
    pmove->next=pinsert;
  }
}

/* Print a linked list in positive order */ 
status traverselist(dlinklist head,dlinklist tail){
  dlinklist pmove=head->next;
  while(pmove!=tail){
    visit(pmove->data);
    pmove=pmove->next;
  }
  printf("\n");
}

status traverselist2(dlinklist head,dlinklist tail){
  dlinklist pmove=head->next;
  while(pmove!=tail){
    visit(pmove->freq);
    pmove=pmove->next;
  }
  printf("\n");
}

/* Insert an element at the head of the chain */
status inserthead(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  pinsert->data=data;
  pinsert->next=NULL;
  pinsert->prior=NULL;
  tail->prior->next=pinsert;
  pinsert->prior=tail->prior;
  pinsert->next=tail;
  tail->prior=pinsert;
  return OK;
}

/* Sort by frequency of use */ 
status locateorder(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=head->next,qmove;
  while(pmove!=tail&&pmove->data!=data)
    pmove=pmove->next;
  if(pmove==tail){
    printf(" Not found \n");
    return ERROR;
  }
  else{
    pmove->freq++;
    qmove=pmove->prior;
    while(qmove!=head&&qmove->freq<pmove->freq)// Look ahead than pmove->freq big qmove->freq
       qmove=qmove->prior;
    if(qmove->next!=pmove){// If found qmove and pmove It's not a direct precursor to the next 
      pmove->next->prior=pmove->prior;
      pmove->prior->next=pmove->next;// will pmove Remove the 
      pmove->prior=qmove;
      pmove->next=qmove->next;
      qmove->next->prior=pmove;
      qmove->next=pmove;// Into the qmove after 
    }
  }
}

int main(void){
  dlinklist head,tail,pmove=head;
  int i=0;
  initdlinklist(&head,&tail);
  for(i=0;i<10;i++)
    inserthead(head,tail,i);
  printf(" The unsorted list is \n");
  traverselist(head,tail);
  printf(" The list sorted by frequency of use is :\n"); 
  locateorder(head,tail,5);
  for(int i=0;i<3;i++){
    locateorder(head,tail,6);
  }
  traverselist(head,tail);
  printf(" The use frequency of each element is \n");
  traverselist2(head,tail);
}

The most important function to implement this 1 is locateorder(). The idea is that if the frequency of an element is not zero, define a cursor that moves to the head of the chain, look for an element that is more frequently used than that element, and insert it into the element you find.

Thank you for reading, I hope to help you, thank you for your support of this site!


Related articles: