-
Notifications
You must be signed in to change notification settings - Fork 0
/
Adjacency List.cpp
79 lines (72 loc) · 1.61 KB
/
Adjacency List.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//graph node definition()
#include <bits/stdc++.h>
using namespace std;
struct node
{
int pos;
struct node *next;
};
void linkedListDefine(const int n,const int m,const vector<vector<int> > &v)
{
struct node *first[n+1],*p;
for (int i=1;i<=n;i++)
{
first[i]=NULL;
}
for (int i=1;i<=m;i++)
{
p=(struct node *)malloc(sizeof(struct node));
p->pos=i;
p->next=first[v[i][0]];
first[v[i][0]]=p;
}
for (int i=1;i<=n;i++)
{
cout<<i<<":";
if (first[i]==NULL)
{
cout<<"null"<<endl;
continue;
}
for (p=first[i];p!=NULL;p=p->next)
{
cout<<v[p->pos][1]<<" ";
}
cout<<endl;
}
}
void arrayDefine(int n,int m,vector<vector<int> > &v)
{
vector<int> first(n+1,-1);
vector<int> next(m+1,-1);
for (int i=1;i<=m;i++)
{
next[i]=first[v[i][0]];
first[v[i][0]]=i;
}
for (int i=1;i<=n;i++)
{
cout<<i<<":";
if (first[i]==-1)
{
cout<<"null"<<endl;
continue;
}
for (int pos=first[i];pos!=-1;pos=next[pos])
{
cout<<v[pos][1]<<" ";
}
cout<<endl;
}
}
int main(void)
{
vector<vector<int> > v={{0,0,0},{1,4,9},{4,3,8},{1,2,5},{2,4,6},{1,3,7}}; //{0,0,0}占位元素
int n=4,m=5;
//链表表示
linkedListDefine(n,m,v);
cout<<endl;
//数组表示
arrayDefine(n,m,v);
return 0;
}