C++建立邻接表,程序出错,下面是代码

发布网友 发布时间：2022-05-13 09:51

我来回答

共3个回答

热心网友 时间：2023-10-05 11:19

/**
 *
 * 处理流程是：先根据图的顶点数创建一个空的邻接表，然后
将图的信息输入邻接表（由CeateList函数完成）
 *
**/
#include <iostream>
using namespace std;
class Node
{
public:
char data;
Node *next;
int info;
public:
Node(){next=NULL;}
};

class AdjList
{
private:
Node *node;
int vernum;
public:
void Initialize(int);
void CreatList();
void display();
};
void AdjList::Initialize(int n)
{
int i;
vernum=n;
node=new Node[n];
for(i=0;i<n;i++)
{
node[i].info=i;
node[i].data='A'+i;
}
}

//@ 创建邻接表
void AdjList::CreatList()//char a,char b
{
int i,j;
int num;//@ 与某个顶点相邻接的顶点的数量
Node *p_node_new;//@ 新创建的节点
Node *p_node_second;//@ 链表中的第二个节点
char c;//@ 输入的顶点
for(i=0;i<vernum;i++)
{
printf("请输入与第%d个顶点[%c]相邻的顶点数：",i,node[i].data);
cin>>num;
printf("请输入与[%c]相邻的顶点，用大写字母进行输入：",node[i].data);

//@ 输入顶点，并加入node[i]链。
for(j=0;j<num;j++)
{
cin>>c;
p_node_new=new Node;
p_node_new->data=c;
p_node_new->info=c-'A';

//@ 将新节点插入到链表开头
p_node_second=node[i].next;
node[i].next=p_node_new;
p_node_new->next=p_node_second;
}
}
/*
Node *t=new Node();
int i,j;
for(i=0;i<vernum;i++)
{

for(j=0;j<vernum;j++)
{
if(node[i].data==a && node[j].data==b)
{
t=&node[i];

while(t->next!=NULL)
{
t=t->next;
}
t->next=&node[j];
return;
}
}
}
*/
}
void AdjList::display()
{
int i;
for(i=0;i<vernum;i++)
{
//Node *T=new Node();
Node *T; //@ 这里是遍历现存的链表，不需要new
cout<<node[i].info<<" "<<node[i].data<<"-";
T=node[i].next;
while(T!=NULL)
{
cout<<T->info<<"-";
T=T->next;
}
cout<<"^"<<endl;
//delete T;
}
}
int main()
{
AdjList a;
int i,j,t,num,arc;
char c1,c2;

cout<<"请输入图的顶点数: ";
cin>>t; //@ 顶点数
a.Initialize(t);//@ 创建空表
cout<<"创建的邻接表为：\n";
a.display();
a.CreatList();//@ 将图的信息存入表中

cout<<endl;
cout<<"输入的端邻接表为："<<endl;
a.display();

return 0;
}

热心网友 时间：2023-10-05 11:20

这个地方，相当于是删除了i到j之间的Node，但是有两个问题
1：删去的Node内存没有释放

2：删除之后，从j到vernum之间的Node的info值需要修改一下

追问编译是通过的，是逻辑错误，下面是测试数据
输入1
5 7
A B
A D
A E
B D
C B
C E
E D
输出
0 A-1-3-4-^
1 B-3-^
2 C-1-4-^
3 D-^
4 E-3-^

我知道在哪出错了，在输入完A B A D A E后建立了一个链表A->B->D->E
输入B D后，本意是要建立B->D，但前面的指向保留了下来，实际建立的是B->D->E->D

知道怎样修改吗

追答你这个CreateList(a,b) 是找到a，b对应的节点，然后把a节点开始的最后一个链表元素和b连起来
所以 "在输入完A B A D A E后建立了一个链表A->B->D->E" 在这个之后

再输入B D 就是把D放在 B链表结尾 就是 A->B->D->E->D(后面形成循环链），

不知道你想要的结果是什么。

热心网友 时间：2023-10-05 11:20

#include <iostream>
using namespace std;

#define MAX_SIZE 20

class Node // 图的顶点类
{
public:
char data;
Node *next;
int info;
public:
Node(){next=NULL;}
};

class AdjList // 邻接表类
{
private:
Node *node; //Node node[MAX_SIZE];
int vernum;
public:
void Initialize(int);
void CreatList(char ,char);
void display();
};
void AdjList::Initialize(int n)
{
int i;
vernum=n;
node=new Node[n];
for(i=0;i<n;i++)
{
node[i].info=i;
node[i].data='A'+i;
node[i].next = NULL;
}
}
void AdjList::CreatList(char a,char b)
{
int i,j;
for(i=0;i<vernum;i++)
{
for(j=0;j<vernum;j++)
{
if(node[i].data==a && node[j].data==b)
{
if(!node[i].next) // 如果下一个结点为空
{
Node * p = new Node(); // 建立一个伪结点
p->data = NULL;
p->info = j;
p->next = NULL;
node[i].next = p;
}
else
{
Node * p = new Node();
p = node[i].next;
while(p->next) // 知道p的下一个结点为空
{
p = p->next;
}

Node * q = new Node();
q->data = NULL;
q->info = j;
q->next = NULL;
p->next = q;
}
return;
}
}
}
}
void AdjList::display()
{
int i;
for(i=0;i<vernum;i++)
{
Node *T=new Node();
cout<<node[i].info<<" "<<node[i].data<<"-";
T=node[i].next;
while(T!=NULL)
{
cout<<T->info<<"-";
T=T->next;
}
cout<<"^"<<endl;
delete T;
}
}
int main()
{
AdjList a;
int i,t,num,arc;
char c1,c2;
cout<<"输入图的个数：";
cin>>t;
while(t--)
{
cout<<endl<<"输入顶点数和弧数：";
cin>>num>>arc;
a.Initialize(num);
cout<<"输入"<<arc<<"条弧的起点和终点："<<endl;
for(i=0;i<arc;i++)
{
cin>>c1>>c2;
a.CreatList(c1,c2);
}
cout<<"图的邻接表为："<<endl;
a.display();
}
return 0;
}