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

2024-02-27 07:05:03 46

C语言双向链表应用

前言：

平时使用音乐播放器时，播放列表中的歌曲可以很方便地进行增添，删除，去重等操作。但其本质都可以抽象成一个双向链表。为了更方便用户的使用，我认为还可以增加一个将最常播放的音乐放在播放列表的头部的功能，那么如何实现呢？

请看代码：

#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefintstatus;
typedefintelemtype;
typedefstructnode{
elemtypedata;
intfreq;
structnode*next;
structnode*prior;
}node;
typedefstructnode*dlinklist;

statusvisit(elemtypec){
printf("%d",c);
}

/*双向链表初始化*/
statusinitdlinklist(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);
}

/*判定是否为空*/
statusemptylinklist(dlinklisthead,dlinklisttail){
if(head->next==tail)
returnTRUE;
else
returnFALSE;
}

/*尾插法创建链表*/
statuscreatedlinklist(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpmove=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;
}
}

/*正序打印链表*/
statustraverselist(dlinklisthead,dlinklisttail){
dlinklistpmove=head->next;
while(pmove!=tail){
visit(pmove->data);
pmove=pmove->next;
}
printf("\n");
}

statustraverselist2(dlinklisthead,dlinklisttail){
dlinklistpmove=head->next;
while(pmove!=tail){
visit(pmove->freq);
pmove=pmove->next;
}
printf("\n");
}

/*在链表头插入元素*/
statusinserthead(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpinsert;
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;
}

/*按使用频次排序*/
statuslocateorder(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpmove=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){
dlinklisthead,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);
}

要实现这一功能，最重要的函数是locateorder()，其实现思路是:如果某个元素的使用频率不为0，则定义一个向链表头移动的游标，寻找一个比该元素使用频率高的元素，将该元素插到找到的元素之后即可。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

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

热门推荐

随机推荐