C语言双向链表实现根据使用频率安排元素位置的功能实例代码

#include

#include

#include

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedefintstatus;

typedefintelemtype;

typedefstructnode{

  elemtype data;

  intfreq;

  structnode * next;

  structnode * prior;

}node;

typedefstructnode* dlinklist;

status visit(elemtype c){

  printf("%d ",c);

}

/*双向链表初始化*/

status initdlinklist(dlinklist * head,dlinklist * tail){

  (*head)=(dlinklist)malloc(sizeof(node));

  (*tail)=(dlinklist)malloc(sizeof(node));

  if(!(*head)||!(*tail))

    returnERROR;

  /*这一步很关键*/

  (*head)->prior=NULL;

  (*tail)->next=NULL;

  (*head)->freq=0;

  (*tail)->freq=0;

  /*链表为空时让头指向尾*/

  (*head)->next=(*tail);

  (*tail)->prior=(*head);

}

/*判定是否为空*/

status emptylinklist(dlinklist head,dlinklist tail){

  if(head->next==tail)

    returnTRUE;

  else

    returnFALSE;

}

/*尾插法创建链表*/

status createdlinklist(dlinklist head,dlinklist tail,elemtype data){

  dlinklist pmove=head,qmove=tail,pinsert;

  pinsert=(dlinklist)malloc(sizeof(node));

  if(!pinsert)

    returnERROR;

  else{

    pinsert->data=data;

    pinsert->prior=pmove;

    pinsert->next=pmove->next;

    pmove->next->prior=pinsert;

    pmove->next=pinsert;

  }

}

/*正序打印链表*/

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");

}

/*在链表头插入元素*/

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;

  returnOK;

}

/*按使用频次排序*/

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("未找到n");

    returnERROR;

  }

  else{

    pmove->freq++;

    qmove=pmove->prior;

    while(qmove!=head&&qmove->freqfreq)//向前寻找比pmove->freq大的qmove->freq

       qmove=qmove->prior;

    if(qmove->next!=pmove){//如果找到的qmove和pmove不是直接的前驱后继关系

      pmove->next->prior=pmove->prior;

      pmove->prior->next=pmove->next;//将pmove取下

      pmove->prior=qmove;

      pmove->next=qmove->next;

      qmove->next->prior=pmove;

      qmove->next=pmove;//插到qmove之后

    }

  }

}

intmain(void){

  dlinklist head,tail,pmove=head;

  inti=0;

  initdlinklist(&head,&tail);

  for(i=0;i<10;i++)

    inserthead(head,tail,i);

  printf("未经过排序的链表为n");

  traverselist(head,tail);

  printf("在按使用频率排序后的链表为:n");

  locateorder(head,tail,5);

  for(inti=0;i<3;i++){

    locateorder(head,tail,6);

  }

  traverselist(head,tail);

  printf("各元素使用频率为n");

  traverselist2(head,tail);

}