首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

请帮忙看一下

2012-03-11 
请各位高手帮忙看一下#include stdio.h#include stdlib.htypedef struct{float coefint expn}ElemTy

请各位高手帮忙看一下
#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);
}

热点排行