溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
C語言雙向鏈表應用
前言：
平時使用音樂播放器時，播放列表中的歌曲可以很方便地進行增添，刪除，去重等操作。但其本質都可以抽象成一個雙向鏈表。為了更方便用戶的使用，我認為還可以增加一個將最常播放的音樂放在播放列表的頭部的功能，那么如何實現呢？
請看代碼：
#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;
/*這一步很關鍵*/
(*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)
return TRUE;
else
return FALSE;
}
/*尾插法創建鏈表*/
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不是直接的前驅后繼關系
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("未經過排序的鏈表為\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);
}
要實現這一功能，最重要的函數是locateorder()，其實現思路是:如果某個元素的使用頻率不為0，則定義一個向鏈表頭移動的游標，尋找一個比該元素使用頻率高的元素，將該元素插到找到的元素之后即可。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
