快捷導(dǎo)航

C語(yǔ)言雙向鏈表實(shí)現(xiàn)根據(jù)使用頻率安排元素位置的功能實(shí)例代碼

更新時(shí)間：2017年03月20日 08:51:27 投稿：lqh

這篇文章主要介紹了C語(yǔ)言雙向鏈表實(shí)現(xiàn)根據(jù)使用頻率安排元素位置的功能實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下

C語(yǔ)言雙向鏈表應(yīng)用

前言：

平時(shí)使用音樂(lè)播放器時(shí)，播放列表中的歌曲可以很方便地進(jìn)行增添，刪除，去重等操作。但其本質(zhì)都可以抽象成一個(gè)雙向鏈表。為了更方便用戶的使用，我認(rèn)為還可以增加一個(gè)將最常播放的音樂(lè)放在播放列表的頭部的功能，那么如何實(shí)現(xiàn)呢？

請(qǐng)看代碼：

#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);
}

/*雙向鏈表初始化*/
status initdlinklist(dlinklist * head,dlinklist * tail){
  (*head)=(dlinklist)malloc(sizeof(node));
  (*tail)=(dlinklist)malloc(sizeof(node));
  if(!(*head)||!(*tail))
    return ERROR;
  /*這一步很關(guān)鍵*/ 
  (*head)->prior=NULL;
  (*tail)->next=NULL;
  (*head)->freq=0;
  (*tail)->freq=0; 
  /*鏈表為空時(shí)讓頭指向尾*/
  (*head)->next=(*tail);
  (*tail)->prior=(*head);
}

/*判定是否為空*/
status emptylinklist(dlinklist head,dlinklist tail){
  if(head->next==tail)
    return TRUE;
  else
    return FALSE;
} 

/*尾插法創(chuàng)建鏈表*/ 
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;
  }
}

/*正序打印鏈表*/ 
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;
  return OK;
}

/*按使用頻次排序*/ 
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");
    return ERROR;
  }
  else{
    pmove->freq++;
    qmove=pmove->prior;
    while(qmove!=head&&qmove->freq<pmove->freq)//向前尋找比pmove->freq大的qmove->freq
       qmove=qmove->prior;
    if(qmove->next!=pmove){//如果找到的qmove和pmove不是直接的前驅(qū)后繼關(guān)系
      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之后
    }
  }
}

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("未經(jīng)過(guò)排序的鏈表為\n");
  traverselist(head,tail);
  printf("在按使用頻率排序后的鏈表為:\n"); 
  locateorder(head,tail,5);
  for(int i=0;i<3;i++){
    locateorder(head,tail,6);
  }
  traverselist(head,tail);
  printf("各元素使用頻率為\n");
  traverselist2(head,tail);
}

要實(shí)現(xiàn)這一功能，最重要的函數(shù)是locateorder()，其實(shí)現(xiàn)思路是:如果某個(gè)元素的使用頻率不為0，則定義一個(gè)向鏈表頭移動(dòng)的游標(biāo)，尋找一個(gè)比該元素使用頻率高的元素，將該元素插到找到的元素之后即可。

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章: