LocateNode（h，x）运算的算法 求指点
设有一个双链表,每个结点中除有piror,data,next三个域外，还有一个访问频度域freq,在链表被起用之前，其值均初始化为零.每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域的值加1,并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法.
下面是我写的代码，求大神指正，不胜感激。
#include <stdio.h>算法 c
#include <stdlib.h>
//#define char ElemType; //这样定义报错
typedef char ElemType;
#define N 5
typedef struct DNode
{
ElemType data;
struct DNode *prior;
struct DNode *next;
int freq; // 访问频域
} DLinkList;
/* 创建双链表--尾插法 dgh*/
void CreatDLinkList(DLinkList *&h, int N, ElemType a[]) //DLinkList *h 要改为 *&h
{
DLinkList *s, *p;
int i;
p = (DLinkList*)malloc(sizeof(DLinkList));
p->data = 0;
p->prior = NULL;
p->next = NULL;
h->next = p;
p->prior = h; // 这两句连接头结点和第一个结点
for(i = 0; i < N; i++)
{
s = (DLinkList*)malloc(sizeof(DLinkList));
s->data = a[i];
s->freq = 0; //这里 s->freq 等于多少?
p->next = s;
s->prior = p; //连接结点p和结点s
p = s;
}
p->next = NULL;
}
/* 输出双链表 */
void DispDLinkList(DLinkList *h)
{
DLinkList *p = h->next;
//while(p->next!=NULL)
while(p != NULL) //这里是写p->next!=NULL还是p!=NULL?
{
printf("%c%d", p->data, p->freq);
p = p->next;
}
printf("\n");
}
/* 元素为x的结点中freq域的值加1，并调整表中结点的次序 */
int LocateNode(DLinkList *h, ElemType x)
{
DLinkList *p = h->next, *q;
while(p != NULL && p->data != x)
p = p->next; /*找data域值为x的结点 *p */
if(p == NULL)
return 0;
else
{
p->freq++;
q = p->prior; //dgh 这里p和q不是指向同一个结点吗? *q是 *p的前驱结点
while(q != h && q->freq < p->freq)
{
p->prior = q->prior;
//p->prior->next = p;
q->prior->next = p;
q->next = p->next;
if(q->next != NULL)
// q->next->prior = q;
p->next->prior = q;
//p->prior = q;
//q->next = p;
p->next = q;
q->prior = p;
q = p->next; // q重新指向p的后继结点
}
return 1;
}
}
int main()
{
DLinkList *p;
int a[N];
int i;
int n;
p=(DLinkList*)malloc(sizeof(DLinkList));
printf("输入元素值:");
for(i = 0; i < N; i++)
{
scanf("%c",&a[i]);
}
CreatDLinkList(p,N,a[i]);
LocateNode(p,scanf("%c",&n));
DispDLinkList(p);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType; //使用char的话，就将主程序中的数组改成char，而>且在输入时，要做一下处理，针对回车之类的字符
#define N 5
typedef struct DNode
{
ElemType data;
struct DNode *prior;
struct DNode *next;
int freq; // 访问频域
} DLinkList;
/* 创建双链表--尾插法 dgh*/
void CreatDLinkList(DLinkList *&h,ElemType *a) //DLinkList *h 要改为 *&h
{
DLinkList *s=NULL, *p=NULL;
int i;
//在主程序中已经创建了头节点，不需要再malloc了
//
for(i = 0; i < N; i++)
{
s = (DLinkList*)malloc(sizeof(DLinkList));
s->data = a[i];
s->freq = 0; //这里 s->freq 等于多少?
if(i==0)
{
h->next = s;
s->prior = h;
}
else
{
p->next = s;
s->prior = p;
}
p = s;
}
p->next = NULL;
}
/* 输出双链表 */
void DispDLinkList(DLinkList *h)
{
DLinkList *p = h->next;
while(p != NULL)
{
printf("%d,%d ", p->data, p->freq);
p = p->next;
}
printf("\n");
}
/* 元素为x的结点中freq域的值加1，并调整表中结点的次序 */
int LocateNode(DLinkList *h, ElemType x)
{
DLinkList *p = h->next, *q;
while(p != NULL && p->data != x)
p = p->next;
if(p == NULL)
return 0;
else
{
p->freq++;
q = p->prior;
while(q != h && q->freq < p->freq)
{
p->prior = q->prior;
q->prior->next = p;
q->next = p->next;
if(q->next != NULL)
p->next->prior = q;
p->next = q;
q->prior = p;
//q = p->next; // q重新指向p的后继结点
q = p->prior; //应该向前走，而不是向后
}
return 1;
}
}
int main()
{
DLinkList *p;
int a[N];
int i;
int n;
p=(DLinkList*)malloc(sizeof(DLinkList));
p->next = NULL;
p->prior = NULL;
printf("输入元素值:");
for(i = 0; i < N; i++)
{
scanf("%d",&a[i]);
}
CreatDLinkList(p,a); //N是常量，不需要再传入了
DispDLinkList(p);
printf("please inter a number:");
scanf("%d",&n);
LocateNode(p,n); //不能直接写在这里，接受的是scanf的个数，而不是>实际的数据
DispDLinkList(p);
return 0;
}
