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

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,则定义一个向链表头移动的游标,寻找一个比该元素使用频率高的元素,将该元素插到找到的元素之后即可。

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

(0)

相关推荐

  • C语言 数据结构双向链表简单实例

    双向链表的基本操作 1.利用尾插法建立一个双向链表. 2.遍历双向链表. 3.实现双向链表中删除一个指定元素. 4.在非递减有序双向链表中实现插入元素e仍有序算法. 5.判断双向链表中元素是否对称若对称返回1否则返回0. 6.设元素为正整型,实现算法把所有奇数排列在偶数之前. 7.在主函数中设计一个简单的菜单调试上述算法. 实例代码: //排序的时候因为没有说明奇数和偶数需不需要各自再排序,我就没有排序,只是将奇数放在偶数后面. //创建链表的时候,因为这个实验没有要求输出链表的长度,所以我就输

  • C语言实现数据结构和双向链表操作

    数据结构  双向链表的实现 双向链表中的每一个结点都含有两个指针域,一个指针域存放其后继结点的存储地址,另一个指针域则存放其前驱结点的存储地址. 双向链表结点的类型描述: //双向链表的类型描述 typedef int ElemType; typedef struct node{ ElemType data; struct node *prior,*next; }DuLNode,*DuLinkList; 其中,prior域存放的是其前驱结点的存储地址,next域存放的是其后继结点的存储地址. 双

  • C语言中双向链表和双向循环链表详解

    双向链表和双向循环链表 和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作 新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =

  • java 实现双向链表实例详解

    java 实现双向链表实例详解 双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力.话不多说,上代码:     首先是链表的节点类: /** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainN

  • C语言之双向链表详解及实例代码

    1,双向链表简介. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 2,例子要求: 完成双向链表的插入.删除以及查找,将学生管理系统使用的数组,以双向链表的方式实现,能够支持无限制的学生人数的增删改查以及保存. 3,代码实现. #include <stdio.h> #include <string.h> #include <

  • C语言数据结构 双向链表的建立与基本操作

    C语言数据结构 双向链表的建立与基本操作 双向链表比单链表有更好的灵活性,其大部分操作与线性表相同.下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题. 1.双向链表的建立 双向链表在初始化时,要给首尾两个节点分配内存空间.成功分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是十分关键的一步,因为这是之后用来判断空表的条件.同时,当链表为空时,要将首节点的next指向尾节点,尾节点的prior指向首节点. 2.双向链表的插入操作 由于定义双向链表时指针域中

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

    C语言双向链表应用 前言: 平时使用音乐播放器时,播放列表中的歌曲可以很方便地进行增添,删除,去重等操作.但其本质都可以抽象成一个双向链表.为了更方便用户的使用,我认为还可以增加一个将最常播放的音乐放在播放列表的头部的功能,那么如何实现呢? 请看代码: #include<stdio.h> #include<stdlib.h> #include<time.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALS

  • jquery操作select元素和option的实例代码

    废话不多说了,直接给大家贴代码,具体代码如下所示: <html> <head> <title></title> <!--添加jquery--> <script src="../Script/jQuery/jquery-1.6.2.min.js" type="text/javascript"></script> <script type="text/javascript

  • JavaScript操作select元素和option的实例代码

    废话不多说了,直接给大家贴代码,具体代码如下所示: <!DOCTYPE html PUBLIC "-//WC//DTD XHTML . Transitional//EN" "http://www.w.org/TR/xhtml/DTD/xhtml-transitional.dtd"> <html xmlns="http://www.w.org//xhtml"> <head> <title></t

  • C语言中实现“17进制”转“10进制”实例代码

    C语言中实现"17进制"转"10进制"实例代码 17进制转成10进制,输入是数字跟大写字母.例如输入G.11.FF,分别输出16.18.270 #include <iostream> #include <string> using namespace std; int main() { string s; int len,factor=17,num; bool sign;//用来标志输入字符串是否非法 while(cin>>s)

  • C语言输入三角形边长判断其类型并输出面积实例代码

    本文主要研究的是输入三角形边长判断其类型并输出面积,用C语言实现,具体如下. 思路:首先判断所给的三条边是否能够组成三角形,若可以组成三角形,则判断该三角形是什么类型,并求三角形的面积. 相关知识: 三角形是由同一平面内不在同一直线上的三条线段'首尾'顺次连接所组成的封闭图形.常见的三角形按边分有普通三角形(三条边都不相等),等腰三角(腰与底不等的等腰三角形.腰与底相等的等腰三角形即等边三角形) 不等边三角形:不等边三角形,数学定义,指的是三条边都不相等的三角形叫不等边三角形. 等腰三角形:等腰

  • C语言统计一篇英文短文中单词的个数实例代码

    具体代码如下所述: #include<stdio.h> #define N 1000 void main(){ char en[N][81]; int i,j,num=0,n,state; //num 用来统计单词的个数 //state 用来记录程序当前是否处于一个单词之中,初值为0,表示不在单词中,值为1,表示正处于在一个单词中 printf("Please input the number of lines for English passage:"); scanf(&

  • Java语言实现简单的酒店前台管理小功能(实例代码)

    笔者是一名刚上路的小萌新,有什么问题希望大家可以指正! 以下为题目: 为某个酒店编写程序:酒店管理系统,模拟订房.退房.打印所有房间状态等功能. 1.该系统的用户是:酒店前台. 2.酒店使用一个二维数组来模拟."Room[][] rooms;" 3.酒店中的每一个房间应该是一个java对象:Room 4.每一个房间Room应该有:房间编号.房间类型.房间是否空闲. 5.系统应该对外提供的功能: 可以预定房间:用户输入房间编号,订房. 可以退房:用户输入房间编号,退房. 可以查看所有房间

  • php判断数组元素不为空格实例代码

    1.使用foreach ($arr as $value){}语句遍历数组. 2.使用if($value!=" ")语句判断数组元素是否为空格. 3.如果数组元素全部不为空,则输出数组元素不为空格. 实例 <?php header("Content-type:text/html;charset=utf-8"); $arr = array(10,"php中文网",20," ","php教程"); $i=0

  • Draggable Elements 元素拖拽功能实现代码

    当然我们可以研究js库的源码, 也可以自己去发明轮子试试看, 其过程还是挺有趣的...下面我就来实现下页面元素的拖拽功能 现在就开始着手实现, 让我们从最顶层的方法讲起, 它用于初始化一个drag object, 方法的声明如下 function DragObject(cfg) 这里的cfg我们用一个对象来传入, 有点像Extjs里配置属性 复制代码 代码如下: var dragObj = new DragObject({ el: 'exampleB', attachEl: 'exampleBH

  • jquery 设置元素相对于另一个元素的top值(实例代码)

    <div id="span1">sfdsfsddfsdf</div><span id="span2" style="position:relative"> <input id="input" type="text"></input>        <input id="button" type="button&q

随机推荐