設有一個雙向回圈鏈表，每個節點中除有prior,data和next三個域外，還增設了一個訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當對鏈表進行一次LOCATE(L,x)的操作后，被訪問的結點（即元素值等于x的結點）中的頻度域freq的值便增1，同時調整鏈表中結點之間的次序，使其訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結點總是靠近表頭結點。是撰寫符合上述要求的LOCATE操作的演算法。
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
typedef int Elemtype;
typedef struct DuLNode {
Elemtype data;
DuLNode* prior;
DuLNode* next;
int freq;
}DuLNode,*LinkList;
DuLNode* LinkListInit()
{
DuLNode* L;
L = (DuLNode*)malloc(sizeof(DuLNode));
if (L == NULL)
return NULL;
L->prior = NULL;
L->next = NULL;
L->freq = 0;
return L;
}
int LinkListInsert(DuLNode* L,int i, Elemtype e)
{
DuLNode* p, * s;
s = (DuLNode*)malloc(sizeof(DuLNode));
s->data = e;
s->prior = NULL; s->next = NULL;
if (i == 1)
{
s->next = L;
L->prior = s;
L = s;
}
else
{
p = L;
for (int j = 1; j < i - 1; j++)
{
p = p->next;
}
if (p->next == NULL)
{
p->next = s; s->prior = p;
}
else
{
p->next->prior = s;
s->next = p->next;
p->next = s;
s->prior = p;
}
}
return 1;
}
void PrintList(DuLNode* L)
{
DuLNode* p = L->next;
while (p != NULL)
{
printf("%3d", p->data);
p = p->next;
}
printf("\n");
}
void PrintList_s(DuLNode* L)
{
DuLNode* p = L->next;
while (p != NULL)
{
printf("%3d", p->data);
p = p->next;
}
printf("\n");
while (p != NULL)
{
printf("freq:%d", p->freq);
p = p->next;
}
printf("\n");
}
DuLNode *LinkListLocate(DuLNode* L, Elemtype e)
{
DuLNode* p, * q;
p = L; q = p->next;
while (q != L && q->data != e)
q = q->next;
if (q != L)
{
q->freq++;
p = q->next;
p->prior = q->prior; q->prior->next = p;
p = L->next;
while (p != L && p->freq > q->freq)
p = p->next;
q->next = p; p->prior->next = q;
q->prior = p->prior; p->prior = q;
return q;
}
else
return 0;
}
int main()
{
DuLNode* head;
int x, loc;
int i = 1;
head = LinkListInit();
if (head == NULL)
{
printf("初始化鏈表失敗！\n");
return 0;
}
do {
printf("請輸入第%d個元素的值（結束輸入請輸入0）:",i++);
scanf_s("%d", &x);
LinkListInsert(head,i,x);
} while (x != 0);
PrintList(head);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/98850.html
標籤：C語言
下一篇：c語言多回圈問題！