c语言高级应用动态双向链表

欢迎大家来到IT世界,在知识的湖畔探索吧!

题目要求：

设有一个双向循环链表，每个结点中除了有prior，data和next三个域外还有一个访问频度域freq。在该双向链表启用之前，频度域freq的值全部初始化为0，每当对链表进行一次访问时，被访问的结点的频度域freq就自动增加1，同时调整链表中结点之间的次序，使其按照访问频度非递增的次序顺序排列，以便始终保持被访问的结点总是靠近表头结点。编写一个程序实现上述功能。

#include "stdio.h" /*定义双向链表类型*/ typedef struct node{ int data; int freq; struct node *prior; struct node *next; }dbLNode,*dbLinkList; /*创建一个双向链表，返回它的头指针*/ dbLinkList GreatdbLinkList(int n){ dbLinkList p,r,list=NULL; int e; int i; list = (dbLinkList)malloc(sizeof(dbLNode)); /*创建头结点head，头结点中不存放内容*/ list->next = list->prior = NULL; for(i=1;i<=n;i++){ scanf("%d",&e); p = (dbLinkList)malloc(sizeof(dbLNode)); p->data = e; p->freq = 0; p->next = NULL; p->prior = NULL; if(!list->next) { list->next = p; /*第一个结点*/ p->prior = list; } else{ r->next = p; /*双向连接下面的结点*/ p->prior = r; } r = p; } return list; } /*访问双向链表中指定的结点，并调整结点次序*/ visit(dbLinkList *l,int x){ dbLinkList p = *l, q, r, s; p = p->next; /*p指向第一个结点*/ while(p->data != x)p = p->next; /*通过循环找到指定的结点*/ if(p == NULL) { printf("Input error!\n"); return; } /*找不到指定的结点，程序报错*/ p->freq ++; printf("Visiting this node\n"); while((p->prior)!=*l && p->freq > p->prior->freq) { /*实现双向链表结点的交换*/ q = p->prior; r = p->next; s = p->prior->prior; p->prior = q->prior; p->next = q; q->prior = p; q->next = r; if (r!=NULL) { r->prior = q; } s->next = p; } } TransdbLinkList(dbLinkList l) { /*遍历整个双向链表，并打印出每个结点中的数据和访问频度*/ l = l->next; while(l!=NULL){ printf("(data:%d ,freq:%d)--> ",l->data,l->freq); l = l->next; } printf("X\n\n"); } main() { dbLinkList l; int d; printf("Input five integer to creat a doubly link list\n"); l = GreatdbLinkList(5); /*创建一个包含5个元素，6个结点的双向链表*/ TransdbLinkList(l); /*遍历双向链表，打印出每个结点中的数据和访问频度*/ printf("Please input the data that you want to vist\n"); scanf("%d",&d); while(d!=0){ visit(&l,d); TransdbLinkList(l); scanf("%d",&d); } getche(); }

欢迎大家来到IT世界,在知识的湖畔探索吧!

运行结果：

运行结果

欢迎大家来到IT世界,在知识的湖畔探索吧!