一个指针有关问题，求大神看看！

2013-10-21

一个指针问题，求大神看看！！我要建立一个双链表，其中节点包括三个数据域data,prior和next,另外还有一个访问

一个指针问题，求大神看看！！
我要建立一个双链表，其中节点包括三个数据域data,prior和next,另外还有一个访问频度域freq,当节点被访问，freq的值就自加一，并将该节点移动到靠近头节点的位置。但是在LocateNode（）函数节点交换那一块，我卡了，求大神解释。
#include<iostream>
using namespace std;
typedef struct LinkNode
{
int data;
struct LinkNode *prior,*next;
int frep;
}DLinkNode;

//初始化双链表
void InitLinkNode(DLinkNode *L)
{
L->prior=NULL;
L->next=NULL;
L->frep=0;
}

//创建链表
void CreateDList(DLinkNode *&L,int a[],int n)
{
DLinkNode *s;
int i;
L=(DLinkNode *)malloc(sizeof(DLinkNode));
L->prior=NULL;
L->next=NULL;
for(i=0;i<n;i++)
{
s=(DLinkNode *)malloc(sizeof(DLinkNode));
s->data=a[i];
s->next=L->next;
if(L->next!=NULL)
L->next->prior=s;
L->next=s;
s->prior=L;
}
}
//输出链表
void dispList(DLinkNode *L)
{
DLinkNode *p = L->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
//销毁链表
void DestroyDList(DLinkNode *L)
{
DLinkNode *pre=L,*p=pre->next;
while(p!=NULL)
{
free(pre);
pre=p;
p=pre->next;
}
free(pre);
L=NULL;
}
//访问双链表，将其中节点中的数值等于X的移到靠近表头的地方，
void LocateNode(DLinkNode *L,int x)
{
DLinkNode *s1=L,*p,*r,*s2;
while(s1->next!=NULL)
{
if(s1->next->data=x)
{
s1->frep++;
break;
}
s1=s1->next;
}
s1=L;
int max=s1->frep;
while(s1->next!=NULL)
{
if(s1->next->frep>max)
{
max=s1->next->frep;
p=s1->next;
}
s1=s1->next;
}
//记住原节点的位置
r=p;
s2=p;
p->next->prior=r->prior;
p->prior->next=r->next;

s2->next=L->next;
L->next=p;
s2->prior=L;

}

int main()
{
DLinkNode DL;
DLinkNode *L=&DL;
int a[10];

cout<<"please input ten numbers:";
for(int i=0;i<10;i++)
cin>>a[i];

//初始化链表
InitLinkNode(L);

//创建链表
CreateDList(L,a,10);

//输出链表
dispList(L);

//访问表中的数据
LocateNode(L,2);

//输出链表
dispList(L);

//销毁链表
DestroyDList(L);
return 0;
}

[解决办法]
单步调试，或者参考stl的list源代码
[解决办法]

引用:

我要建立一个双链表，其中节点包括三个数据域data,prior和next,另外还有一个访问频度域freq,当节点被访问，freq的值就自加一，并将该节点移动到靠近头节点的位置。但是在LocateNode（）函数节点交换那一块，我卡了，求大神解释。
#include<iostream>
using namespace std;
typedef struct LinkNode
{
int data;
struct LinkNode *prior,*next;
int frep;
}DLinkNode;

//初始化双链表
void InitLinkNode(DLinkNode *L)
{
L->prior=NULL;
L->next=NULL;
L->frep=0;
}

//创建链表
void CreateDList(DLinkNode *&L,int a[],int n)
{
DLinkNode *s;
int i;
L=(DLinkNode *)malloc(sizeof(DLinkNode));
L->prior=NULL;
L->next=NULL;
for(i=0;i<n;i++)
{
s=(DLinkNode *)malloc(sizeof(DLinkNode));
s->data=a[i];
s->next=L->next;
if(L->next!=NULL)
L->next->prior=s;
L->next=s;
s->prior=L;
}
}
//输出链表
void dispList(DLinkNode *L)
{
DLinkNode *p = L->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
//销毁链表
void DestroyDList(DLinkNode *L)
{
DLinkNode *pre=L,*p=pre->next;
while(p!=NULL)
{
free(pre);
pre=p;
p=pre->next;
}
free(pre);
L=NULL;
}
//访问双链表，将其中节点中的数值等于X的移到靠近表头的地方，
void LocateNode(DLinkNode *L,int x)
{
DLinkNode *s1=L,*p,*r,*s2;
while(s1->next!=NULL)
{
if(s1->next->data=x) //不该有的错误
{
s1->frep++;
break;
}
s1=s1->next;
}
s1=L;
int max=s1->frep;
while(s1->next!=NULL)
{
if(s1->next->frep>max)
{
max=s1->next->frep;
p=s1->next;
}
s1=s1->next;
}
//记住原节点的位置
r=p;
s2=p;
p->next->prior=r->prior;
p->prior->next=r->next;

s2->next=L->next;
L->next=p;
s2->prior=L;

}

int main()
{
DLinkNode DL;
DLinkNode *L=&DL;
int a[10];

cout<<"please input ten numbers:";
for(int i=0;i<10;i++)
cin>>a[i];

//初始化链表

InitLinkNode(L);

//创建链表
CreateDList(L,a,10);

//输出链表
dispList(L);

//访问表中的数据
LocateNode(L,2);

//输出链表
dispList(L);

//销毁链表
DestroyDList(L);
return 0;
}

实现被访问的结点向头结点靠近：要考虑3种情况：
举例：
1. 结点顺序为  L为头结点， L1，L2，L3依次

思想如下：
1.假如访问的结点为：L1 不需要移动
2.假如结点为L2，移动如下
L2->prior->next = L2->next;
L3->prior = L2->prior;
L->next->prior = L2;
L2->next = L->next;
L->next = L2;
3。结点为L3，移动如下：
L3->prior->next = L3->next;
L3->next = L->next;
L1->prior = L3;
L3->prior = L;
L->next = L3;

LZ使用的插入方法为投插法，以上的算法应该能弄懂。
调试是最好的老师， F9（打断点）->F10（单步调试）->F11（进入函数调试）
希望帮到LZ

[解决办法]
if(s1->next->data=x)    //不该有的错误     ******************* 注意下LZ
[解决办法]
1）不知道你的prior 指针可以干啥。
2）难道不会出现,找不到节点数据为x的情况吗，为何不处理这种情况.
3）辛辛苦苦找到的节点，又丢掉了
4）头结点，不储存数据，他的frep（freq）毫无意义。
5)查找最大值作什么，只要找到一个位置，可以插入新发现节点就可以了。
   需要查找，相邻节点中，前一个频率比数据为x的节点大（或者相等）
   后一个不比他大就行了。
6）频率是用来排序的，频率大的在前。不然直接插入，最前头好了。
7）双链表插入节点，至少要修改4个指针

//    插入 prior，next 两个节点中间。 
      p->next =prior; //1)
     p->prior =next  //2) 
     prior->next = p;//3)
     next ->prior= p;//4)
    
//     p插入q后面 
      p->next = q->next;  //1) 
      p->prior = q;       //2)
     if(q->next) q->next->prior = p; //3)
     q->next = p;        //4)
//     p插入q前面面 
       p->next = q;          //1) 
      p->prior = q->prior;  //2)
    if(q->prior）q->prior->next = p;   //3)
      q->prior = p;         //4)
//为了程序更健壮，要检查，是否空指针

在双链表中插入节点示意图

7.1）插入前，插入位置的，前后两个节点  prior，next
          prior          next

[解决办法]

[解决办法]

            V               V
         +--------+    +--------+
.....<---
[解决办法]
  prior
[解决办法]
<---
[解决办法]
  prior
[解决办法]
<--- .....
.....--->
[解决办法]
  next
[解决办法]
--->
[解决办法]
  next
[解决办法]
---> .....
         +--------+    +--------+
7.2）要插入的节点
      p

[解决办法]

      V
    +--------+
<---
[解决办法]
  prior
[解决办法]
<---
--->
[解决办法]
  next
[解决办法]
--->
    +--------+

7.3）插入后的链表,三个节点prior，p， next

          prior           p            next

[解决办法]

[解决办法]

[解决办法]

           V              V             V
         +--------+    +--------+    +--------+
.....<---
[解决办法]
  prior
[解决办法]
<---
[解决办法]
  prior
[解决办法]
<---
[解决办法]
prior
[解决办法]
<---......
.....--->
[解决办法]
  next
[解决办法]
--->
[解决办法]
  next
[解决办法]
--->
[解决办法]
next
[解决办法]
--->......
         +--------+    +--------+    +--------+


void LocateNode(DLinkNode *L,int x)
{
DLinkNode *s1=L,*p,*r,*s2;
while(s1->next!=NULL)
{
if(s1->next->data=x)
{
s1->frep++;
break;
}
s1=s1->next;
}//2）找不到咋办？？？？
s1=L;//3）辛辛苦苦找到的，值为x的节点s1丢失了，现在s1 变成头节点了。
int max=s1->frep;//4）头结点，不储存数据，他的frep（freq）毫无意义。

while(s1->next!=NULL)//5）查找最大值作什么，只要找到一个位置，可以插入就可以了。
{
if(s1->next->frep>max)
{
max=s1->next->frep;
p=s1->next;
}
s1=s1->next;
}
//记住原节点的位置
r=p;
s2=p;
p->next->prior=r->prior;
p->prior->next=r->next;
//6）既然,记录频率，为何直接插到最前头。频率干啥的？？？？频率是用来排序的！！！
//7）双链表插入节点，至少要修改4个指针
s2->next=L->next;
L->next=p;
s2->prior=L;

}

热点排行

C++

一个指针有关问题，求大神看看！