请各位高手帮忙看一下
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
float coef;
int expn;
}ElemType;
typedef struct Node
{
ElemType elem;
Node *next;
}Node;
typedef struct
{
Node *head;
int length;
}List;
int InitList(List &L)
{
L.head=(Node*)malloc(sizeof(Node));
L.head->next=NULL;
L.length=0;
return 1;
}
int InsertList(List &L,ElemType e)
{
Node *node=(Node*)malloc(sizeof(Node));
node->elem=e;
node->next=NULL;
node->next=L.head->next;
L.head->next=node;
L.length++;
return 1;
}
int InsertNode(List &L,ElemType e)
{
List p;
p.head=L.head;
while(p.head->next!=NULL)
p.head=p.head->next;
Node *node=(Node*)malloc(sizeof(Node));
node->elem=e;
p.head->next=node;
node->next=NULL;
return 1;
}
int PrintList(List &L)
{
Node *s=(Node*)malloc(sizeof(Node));
s->next=NULL;
s=L.head->next;
while(s!=NULL)
{
printf("%f,%d\n",s->elem.coef,s->elem.expn);
s=s->next;
}
free(s);
return 1;
}
int UnionList(List &La,List &Lb)
{
List s;
s.head=La.head;
while(La.head->next!=NULL)
La.head=La.head->next;
La.head->next=Lb.head->next;
Lb.head->next=NULL;
La.head=s.head;
free(Lb.head);
return 1;
}
int DeleteNode(List &La,List &Lb)
{
Node *pa=(Node*)malloc(sizeof(Node));
Node *pb=(Node*)malloc(sizeof(Node));
pa->next=NULL;
pb->next=NULL;
pa=La.head->next;
pb=Lb.head->next;
while(pa&&pb)
{
if(pa->elem.expn==pb->elem.expn)
pa->elem.coef+=pb->elem.coef;
pa=pa->next;
pb=pb->next;
}
free(pa);
free(pb);
return 1;
}
void main()
{
List La;
List Lb;
InitList(La);
InitList(Lb);
ElemType elem[5]={{5,5},{4,4},{3,3},{2,2},{1,1}};
ElemType elem1[3]={{5,5},{2,2},{1,1}};
for(int i=0;i<5;i++)
InsertList(La,elem[i]);
for(i=0;i<3;i++)
InsertList(Lb,elem1[i]);
PrintList(La);
printf("\n");
PrintList(Lb);
printf("\n");
DeleteNode(La,Lb);
PrintList(La);
}
调用函数DeleteNode()改变线性链表La中指数与线性链表Lb中指数相等的系数的值,但是调用该函数后,却不能把La中各项的值都正确打印出来,请各位各帮忙看一下
[解决办法]
- C/C++ code
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
float coef;
int expn;
}ElemType;
typedef struct Node
{
ElemType elem;
Node *next;
}Node;
typedef struct
{
Node *head;
int length;
}List;
int InitList(List &L)
{
L.head=(Node*)malloc(sizeof(Node));
L.head->next=NULL;
L.length=0;
return 1;
}
int InsertList(List &L,ElemType e)
{
Node *node=(Node*)malloc(sizeof(Node));
node->elem=e;
node->next=NULL;
node->next=L.head->next;
L.head->next=node;
L.length++;
return 1;
}
int InsertNode(List &L,ElemType e)
{
List p;
p.head=L.head;
while(p.head->next!=NULL)
p.head=p.head->next;
Node *node=(Node*)malloc(sizeof(Node));
node->elem=e;
p.head->next=node;
node->next=NULL;
return 1;
}
int PrintList(List &L)
{
//Node *s=(Node*)malloc(sizeof(Node));//分配空间多余
//s->next=NULL; //赋值多余
Node *s = NULL;
s=L.head->next;
while(s!=NULL)
{
printf("%f,%d\n",s->elem.coef,s->elem.expn);
s=s->next;
}
//free(s); //释放空间多余 且错误(因为上面的malloc和这里的free不对应,s已经改变)
return 1;
}
int UnionList(List &La,List &Lb)
{
List s;
s.head=La.head;
while(La.head->next!=NULL)
La.head=La.head->next;
La.head->next=Lb.head->next;
Lb.head->next=NULL;
La.head=s.head;
free(Lb.head);
return 1;
}
//这个函数想做什么?
//我的理解:你想把lb中 expn 在la中存在的node找到,并把coef加到la中对应的node中区
int DeleteNode(List &La,List &Lb)
{
//跟PrintList一样,pa、pb是不需要分配空间的
//Node *pa=(Node*)malloc(sizeof(Node));
//Node *pb=(Node*)malloc(sizeof(Node));
//pa->next=NULL;
//pb->next=NULL;
Node *pa = NULL;
Node *pb = NULL;
pa=La.head->next;
pb=Lb.head->next;
/* 这个算法有问题,la和lb中,expn值相同的得node,不一定在同一个位置(不一定都是第n个node去匹配)
while(pa&&pb)
{
if(pa->elem.expn==pb->elem.expn)
pa->elem.coef+=pb->elem.coef;
pa=pa->next;
pb=pb->next;
}
*/
//如果la和lb中的node都无序,查找expn相同的node时间复杂度将是 O(n*n)
//考虑到你的测试数据,这里我假设la和lb中,都是按expn降序排列的。
while (NULL != pa && NULL != pb)
{
if(pa->elem.expn == pb->elem.expn)
{
pa->elem.coef += pb->elem.coef;
pa = pa->next;
pb = pb->next;
}
else if (pa->elem.expn > pb->elem.expn)
{
pa = pa->next;
}
else // pa->elem.expn 小于 pb->elem.expn
{
pb = pb->next;
}
}
//free(pa);
//free(pb);
return 1;
}
void main()
{
List La;
List Lb;
InitList(La);
InitList(Lb);
ElemType elem[5]={{5,5},{4,4},{3,3},{2,2},{1,1}};
ElemType elem1[3]={{5,5},{2,2},{1,1}};
int i;
for(i=0;i <5;i++)
InsertList(La,elem[i]);
for(i=0;i <3;i++)
InsertList(Lb,elem1[i]);
PrintList(La);
printf("\n");
PrintList(Lb);
printf("\n");
DeleteNode(La,Lb);
PrintList(La);
}