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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<iostream>
#include<stdlib.h>
using namespace std;
const int defaultSize = 10;
class SeqList {
protected:
int *data;
int maxSize;
int last;
void reSize(int newSize);
public:
SeqList(int sz = defaultSize);
SeqList(SeqList &l);
~SeqList();
int Size() const;
int Length() const;
int Search(int &x) const;
bool getData(int i,int &x) const;
void setData(int i,int &x);
bool Insert(int i,int &x);
bool Remove(int i,int &x);
bool isEmpty();
bool isFull();
void output();
};
bool SeqList::isFull()//判断线性表是否满
{
if(last+1==maxSize)
return true;
else
return false;
}
bool SeqList::isEmpty()//判断线性表是否空
{
if(last == -1)
{
return true;
}else
{
return false;
}
}
void SeqList::reSize(int newSize)//重新开辟空间
{
data = new int[newSize];
}
SeqList::SeqList(int sz)//构造线性表
{
if (sz>0) {
maxSize = sz;
last = -1;
data = new int[maxSize];
if (data == NULL)
exit(1);
}
}
SeqList::~SeqList()//删除线性表
{
delete []data;
}
int SeqList::Length() const//获取线性表的长度
{
return last+1;
}
bool SeqList::getData(int i,int &x) const//获取线性表的第i个元素
{
if(i-1>-1&&i-1<=last)
{
x = data[i-1];
return true;
}else
{
return false;
}
}
void SeqList::setData(int i,int &x)//更改线性表的第i个元素为x
{
if(i-1>0&&i-1<=last)
{
data[i-1] = x;
}
}
bool SeqList::Insert(int i,int &x)//在线性表的第i个位置插入x
{
if (last == maxSize-1)
return false;
if (i<0||i>last+1)
return false;
int j;
for (j=last;j>=i;j--)
data[j+1] = data[j];
data[i] = x;
last++;
return true;
}
bool SeqList::Remove(int i,int &x)//删除线性表第i个元素
{
i = i-1;
if(i>-1&&i<=last)
{
x = data[i];
int j;
for (j=i;j<=last-1;j++)
data[j] = data[j+1];
last--;
return true;
}else return false;
}
void SeqList::output()//输出线性表
{
int i;
for (i=0;i<=last;i++)
cout << data[i] << " ";
cout << endl;
}
int SeqList::Size() const//获得线性表的最大容量
{
return maxSize;
}
int SeqList::Search(int &x) const//获取数据x的下标
{
for(int i=0;i<=last;i++)
{
if(data[i]==x)
{
return i+1;
}
}
return 0;
}
int main()
{
SeqList l(8);
int n,i,x;
cin >> n;
for (i=0;i<n;i++) {
cin >> x;
if (l.isFull())
break;
l.Insert(i,x);
}
cout << l.Size() << " " << l.Length() << endl;
l.output();
l.Remove(3,n);
l.setData(2,n);
l.getData(1,n);
cout << n << endl;
l.output();
return 0;
}
/*
6
3 2 8 9 5 1
*/

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node *next;
}node,*pnode;
int emptylist(pnode H)
{
if(H->next == NULL)
return 1;
else
return 0;
}
int getLength(node *H)//获取链表长度并返回
{
pnode p;
int i = 0;
p = H->next;
if(p!=NULL)
{
while(p!=NULL)
{
i++;
p = p->next;
}
return i;
}else
return 0;
}
void getdata(node *H,int k,int &x)//获取链表第k个数据;并赋给x
{
pnode p;
int i;
p = H ->next;
if(p!=NULL)
{
for(i=0;i<k;i++)
{
x = p->data;
p = p->next;
}
}
}
int searchdata(node *H,int &k,int x)//获取与x相等的第一个元素的下标并赋给k
{
pnode p;
int i=0;
p = H ->next;
if(p!=NULL)
{
while(p)
{
i++;
if(p->data == x)
{
return i;
}
p = p->next;
}
}
return 0;
}
void deletedata(node *H,int k,int &x)//删除链表第k个数据，并赋给x(要注意存在无法删除的情况)
{
pnode p,q;
int i;
p = H;
i = 0;
while(p->next&&i<k-1)
{
p = p->next;
i++;
}
if(p->next&&i<=k-1)
{
q = p->next;
p->next = q->next;
x = q->data;
free(q);
}
}
void insertdata(node *H,int k,int x)//在链表的第k个位置上插入x
{
pnode p,q,l;
p = H->next;
q = H;
l = (node*)malloc(sizeof(node));
l->data = x;
for(int i=0;i<k-1;i++)
{
q = p;
p = p->next;
}
q->next = l;
l->next = p;
}
void output(pnode H)//输出链表
{
pnode p;
p = H->next;
while(p!=NULL)
{
printf("%d",p->data);
p = p->next;
}
cout<<endl;
}
void destroyList(pnode H)//销毁链表
{
pnode p,q;
p = H->next;
while(p)
{
q = p;
p = p->next;
free(q);
}
}
void deletall(pnode H)//清空链表（就加了个H->next = NULL）
{
pnode p,q;
p = H->next;
while(p)
{
q = p;
p = p->next;
free(q);
}
H->next = NULL;
}
pnode combine(pnode H1,pnode H2)//链表合并(有重复元素)
{
pnode p,q,l,H3;
l = H3 = H1;
p = H1->next;
q = H2->next;
while(p&&q)
{
if(p->data<=q->data)
{
l->next = p;
l = p;
p = p->next;
}else
{
l->next = q;
l = q;
q = q->next;
}
}
if(p==NULL&&q!=NULL)
{
l->next = q;
}else
{
l->next =p;
}
return H3;
}
pnode combine2(pnode H1,pnode H2)//链表合并(无重复元素)
{
pnode p,q,l,H3;
l = H3 = H1;
p = H1->next;
q = H2->next;
while(p&&q)
{
if(p->data<q->data)
{
l->next = p;
l = p;
p = p->next;
}else if(p->data>q->data)
{
l->next = q;
l = q;
q = q->next;
}else
{
q = q->next;
}
}
if(p==NULL&&q!=NULL)
{
l->next = q;
}else
{
l->next =p;
}
return H3;
}
int main()
{
pnode H1,H2;
H1 = (pnode)malloc(sizeof(node));
H1->next = NULL;
H2 = (pnode)malloc(sizeof(node));
H2->next = NULL;
int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
insertdata(H1,i,x);
}
for(int i=1;i<=n;i++)
{
cin>>x;
insertdata(H2,i,2*x);
}
//output(H);
/*
insertdata(H,2,2);
output(H);
deletedata(H,4,x);
cout<<x<<endl;
output(H);
cout<<getLength(H)<<endl;
getdata(H,4,x);
cout<<x<<endl;
deletall(H);
printf("%dn",emptylist(H));
*/
//searchdata(H,n,5);
//cout<<n<<endl;
//deletedata(H,4,x);
//output(H);
output(H1);
output(H2);
//H1 = combine(H1,H2);
H1 = combine2(H1,H2);
output(H1);
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/

1
2
在这里插入代码片

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
#include <iostream>
using namespace std;
int MAXSIZE = 100;
typedef struct
{
int *base;
int *top;
int stacksize;
}Node;
void initstack(Node &S)//顺序栈的初始化
{
S.base = new int[MAXSIZE];
S.top = S.base;
S.stacksize = MAXSIZE;
}
bool stackempty(Node S)//判断栈空
{
if(S.top == S.base)
return true;
else
return false;
}
int stacklength(Node S)//求栈的长度
{
return S.top - S.base;
}
void clearstack(Node &S)//清空栈
{
if(S.base)
S.top = S.base;
}
void destroystack(Node &S)//销毁栈
{
if(S.base)
{
free(S.base);
S.stacksize = 0;
S.base = S.top = NULL;
}
}
void Push(Node &S,int x)//顺序入栈
{
if(S.top - S.base < S.stacksize)
*S.top++ = x;
}
void Pop(Node &S,int &x)//顺序出栈
{
if(S.top!=S.base)
{
x = *--S.top;
}
}
void GetTop(Node S,int &x)//取栈顶元素
{
if(S.base!=S.top)
{
x = *(S.top--);
}
}
int main()
{
Node S;
int x;
initstack(S);
for(int i=0;i<5;i++)
Push(S,i);
for(int i=0;i<5;i++)
{
Pop(S,x);
cout<<x<<' ';
}
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/

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
#include <iostream>
using namespace std;
typedef struct StackNode
{
int data;
struct StackNode *next;
}node,*lnode;
void initstack(lnode &S)//栈的初始化
{
S = NULL;
}
bool stackempty(lnode S)//判断栈空
{
if(S == NULL)
return true;
else
return false;
}
void Push(lnode &S,int x)//顺序入栈
{
lnode p;
p = (lnode)malloc(sizeof(node));
p->data = x;
p->next = S;
S = p;
}
void Pop(lnode &S,int &x)//顺序出栈
{
if(S!=NULL)
{
lnode p;
p = S;
x = S->data;
S = S->next;
free(p);
}
}
void GetTop(lnode S,int &x)//取栈顶元素
{
if(S!=NULL)
{
x = S->data;
}
}
int main()
{
lnode S;
int x;
initstack(S);
for(int i=0;i<5;i++)
Push(S,i);
for(int i=0;i<5;i++)
{
Pop(S,x);
cout<<x<<' ';
}
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/

1
2
在这里插入代码片

1
2
在这里插入代码片

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
#include <iostream>
using namespace std;
#define MAXQSIZE 10
typedef struct
{
int *base;
int front1;
int rear;
}queueq;
void initqueue(queueq &Q)//循环队列初始化
{
Q.base = new int[MAXQSIZE];
Q.front1 = Q.rear = 0;
}
int queuelength(queueq Q)//求循环队列长度
{
return (Q.rear - Q.front1 + MAXQSIZE)%MAXQSIZE;
}
void enqueue(queueq &Q,int x)//循环队列入队
{
if((Q.rear+1)%MAXQSIZE!=Q.front1)
{
Q.base[Q.rear]=x;
Q.rear = (Q.rear+1)%MAXQSIZE;
}
}
void dequeue(queueq &Q,int &x)//循环队列出队
{
if(Q.front1!=Q.rear)
{
x = Q.base[Q.front1];
Q.front1 = (Q.front1+1)%MAXQSIZE;
}
}
bool queueempty(queueq &Q)//判断队空
{
return (Q.front1 == Q.rear);
}
bool queuefull(queueq &Q)//判断队满
{
return ((Q.rear+1)%MAXQSIZE == Q.front1);
}
int main()
{
queueq Q;
initqueue(Q);
for(int i=0;i<9;i++)
{
enqueue(Q,i);
}
cout<<queuefull<<endl;
int x;
for(int i=0;i<9;i++)
{
dequeue(Q,x);
cout<<x<<' ';
}
cout<<endl;
cout<<queueempty(Q);
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/

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
#include <iostream>
using namespace std;
typedef struct Qnode
{
int data;
struct Qnode *next;
}qnode;
typedef struct
{
qnode *front1;
qnode *rear;
}Lqueue;
void initqueue(Lqueue &Q)//链队列初始化
{
Q.front1 = Q.rear = (qnode *)malloc(sizeof(qnode));
Q.front1->next = NULL;
}
void destroyqueue(Lqueue &Q)//销毁链队列
{
while(Q.front1)
{
Q.rear = Q.front1->next;
free(Q.front1);
Q.front1 = Q.rear;
}
}
bool queueempty(Lqueue Q)//判断链队列是否为空
{
return (Q.front1 == Q.rear);
}
void getqueue(Lqueue Q,int &x)//取队头元素
{
if(Q.front1!=Q.rear)
x = Q.front1->next->data;
}
void enqueue(Lqueue &Q,int x)//链队入队
{
qnode *p;
p = (qnode *)malloc(sizeof(qnode));
p->data = x;
p->next = Q.rear->next;
Q.rear->next = p;
Q.rear = p;
}
void dequeue(Lqueue &Q,int &x)//链队出队
{
if(Q.front1!=Q.rear)
{
qnode *p;
p = Q.front1;
Q.front1 = Q.front1->next;
x = Q.front1->data;
free(p);
}
}
int main()
{
Lqueue Q;
initqueue(Q);
for(int i=0;i<5;i++)
{
enqueue(Q,i);
}
int x;
for(int i=0;i<5;i++)
{
dequeue(Q,x);
cout<<x<<' ';
}
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <queue>
using namespace std;
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
int LTag,RTag;
}trenode,*ptrenode;
ptrenode pre;
void createtree(ptrenode &T)//利用先序遍历建立二叉树
{
char ch;
cin>>ch;
if(ch=='#')
{
T = NULL;
}else
{
T = new tree;
T->data
= ch;
createtree(T->lchild);
createtree(T->rchild);
}
}
void inoutput(ptrenode T)//利用中序遍历输出二叉树
{
if(T!=NULL)
{
inoutput(T->lchild);
cout<<T->data;
inoutput(T->rchild);
}
}
void noutput(ptrenode T)//层序输出Big陈
{
ptrenode p;
queue<ptrenode> Q;
if(T)
{
Q.push(T);
while (!Q.empty())
{
p=Q.front();
cout<<p->data;
Q.pop();
if(p->lchild)
Q.push(p->lchild);
if(p->rchild)
Q.push(p->rchild);
}
}
}
void trecopy(ptrenode &T1,ptrenode &T2)//树的复制
{
if(T1 == NULL)
{
T2 = NULL;
return;
}else
{
T2 = new tree;
T2->data
= T1->data;
trecopy(T1->lchild,T2->lchild);
trecopy(T1->rchild,T2->rchild);
}
}
int Countnode(ptrenode T)//计算二叉树结点总数
{
if(T==NULL)
return 0;
else
return Countnode(T->lchild)+Countnode(T->rchild)+1;
}
int Countlead(ptrenode T)//计算二叉树叶子总数
{
if(T == NULL)
return 0;
if(T->lchild == NULL&&T->rchild == NULL)
return 1;
else
return Countlead(T->lchild)+Countlead(T->rchild);
}
int Countdepth(ptrenode T)//求二叉树的深度
{
if(T==NULL)
return 0;
else
return max(Countdepth(T->lchild)+1,Countdepth(T->rchild)+1);
}
int Num1(ptrenode &T){
//统计度为1的节点的个数
if(T == NULL)
return 0;
if(T->lchild == NULL&&T->rchild != NULL)
{
return Num1(T->rchild)+1;
}
else if(T->lchild != NULL&&T->rchild == NULL)
{
return Num1(T->lchild)+1;
}
else
{
return Num1(T->rchild)+Num1(T->lchild);
}
}
void inthreading(ptrenode &T)//线索二叉树的建立（有问题）
{
if(T)
{
inthreading(T->lchild);
if(!T->lchild)
{
T->LTag=1;
T->lchild = pre;
}else
T->LTag=0;
if(!pre->rchild)
{
pre->RTag=1;
pre->rchild = T;
}else
pre->RTag = 0;
pre=T;
inthreading(T->rchild);
}
}
int main()
{
//pre->RTag = 1;
//pre->rchild = NULL;
ptrenode T,Tnew;
createtree(T);
inoutput(T);
cout<<endl;
trecopy(T,Tnew);
inoutput(Tnew);
cout<<endl;
cout<<Countnode(T)<<endl;
cout<<Countlead(T)<<endl;
cout<<Countdepth(T)<<endl;
/*
createtree(T);
inthreading(T);
inoutput(T);
*/
return 0;
}
/*
ABC##DE#G##F###
*/

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
#include <iostream>
#include<cstdio>
using namespace std;
typedef struct BThrNode{
char data;
struct BThrNode *lchild, *rchild;
int ltag, rtag;
}BThrNode, *BThrTree;
BThrTree T,p;
void createBTree(BThrTree &T)//前序遍历建立二叉树
{
char ch;
cin>>ch;
if(ch=='@') T=NULL;
else
{
T=new BThrNode;
T->data=ch;
createBTree(T->lchild);
createBTree(T->rchild);
}
}
BThrTree pre=NULL;//全局变量
void InThread(BThrTree p)//中序遍历线索化二叉树
{
if(p!=NULL)
{
InThread(p->lchild);
if(p->lchild==NULL)
{
p->ltag=1;
p->lchild=pre;
}else
p->ltag=0;
if(p->rchild==NULL)
{
p->rtag=1;
pre->rchild=p;
}
else
pre->rtag=0;
pre=p;
InThread(p->rchild);
}
}
void TraveBTree(BThrTree &T)
{
if(T)
{
TraveBTree(T->lchild);
cout<<T->data;
TraveBTree(T->rchild);
}
}
int main()
{
createBTree(T);
InThread(p);
TraveBTree(T);
return 0;
}

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
#include <iostream>
using namespace std;
typedef struct linjiejuzhen{
char a[100];
int b[100][100];
int dian,bian;
}linjie;
int find1(linjie t,char x)
{
int i;
for(i=0;i<t.dian;i++)
{
if(t.a[i]==x)
return i;
}
return -1;
}
int createju(linjie &t)
{
scanf("%d %d",&t.dian,&t.bian);
int i,j,k;
char m,n;
for(i=0;i<t.dian;i++)
{
scanf(" %c",&t.a[i]);
}
for(i=0;i<t.dian;i++)
{
for(j=0;j<t.dian;j++)
t.b[i][j]=0;
}
for(i=0;i<t.bian;i++)
{
scanf(" %c %c",&m,&n);
j=find1(t,m);
k=find1(t,n);
t.b[k][j]=1;
t.b[j][k]=1;
}
for(i=0;i<t.dian;i++)
{
for(j=0;j<t.dian;j++)
printf("%d ",t.b[i][j]);
printf("n");
}
}
int main()
{
linjie t;
createju(t);
return 0;
}

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<iostream>
#include<cstdio>
#include<queue>
#define MAX_NUM 20
using namespace std;
int w;
int mark[100];
int vis[100];
typedef struct EdgeNode//边的结点
{
int edge;
int weight;
struct EdgeNode *nextedge;
}EdgeNode;
typedef struct Vnode//点的节点
{
int data;
EdgeNode *pp;
}Vnode;
typedef struct//图的定义
{
Vnode VList[MAX_NUM];
int n,e;//点数和边数
}Graph;
void createDirGraph(Graph &G)//有向图的构建
{
int x,y;
EdgeNode *q;
cin>>G.n>>G.e;
for(int i=1;i<=G.n;i++)//输入结点信息并初始化节点
{
cin>>G.VList[i].data;
G.VList[i].pp=NULL;
}
for(int i=1;i<=G.e;i++)//输入边的信息
{
cin>>x>>y;
q = new EdgeNode;
q->edge = y;
q->nextedge = G.VList[x].pp;
G.VList[x].pp = q;
}
}
void createUndirGraph(Graph &G)//无向图的构建
{
int x,y;
EdgeNode *q,*p;
cin>>G.n>>G.e;
for(int i=1;i<=G.n;i++)//输入结点信息并初始化节点
{
cin>>G.VList[i].data;
G.VList[i].pp=NULL;
}
for(int i=1;i<=G.e;i++)//输入边的信息
{
cin>>x>>y;
q = new EdgeNode;
p = new EdgeNode;
q->edge = y;
p->edge = x;
q->nextedge = G.VList[x].pp;
p->nextedge = G.VList[y].pp;
G.VList[x].pp = q;
G.VList[y].pp = p;
}
}
void showGraph(Graph G)
{
for(int i=1;i<=G.n;i++)
{
cout<<G.VList[i].data<<':';
EdgeNode *p = G.VList[i].pp;
while(p)
{
cout<<p->edge<<' ';
p = p->nextedge;
}
cout<<endl;
}
}
void DFS(Graph &G,int v)//深度优先遍历
{
cout<<v<<" ";
mark[v]=1;
EdgeNode *p=G.VList[v].pp;
while(p!=NULL)
{
w=p->edge;
if(!mark[w])
DFS(G, w);
p=p->nextedge;
}
}
void BFS(Graph &G,int v)//广度优先遍历
{
int x;
queue<int>Q;
Q.push(G.VList[v].data);
while(!Q.empty())
{
x = Q.front();
Q.pop();
if(!vis[x])
{
cout<<'v'<<x<<' ';
vis[x] = 1;
}
EdgeNode *p = G.VList[x].pp;
while(p)
{
if(!vis[p->edge])
{
Q.push(p->edge);
}
p=p->nextedge;
}
}
}
void getdu(Graph &G)//求入度，出度，度
{
int a[100][3],cnt;
for(int i=1;i<=G.n;i++)
a[i][1] = 0;
for(int i=1;i<=G.n;i++)
{
cnt = 0;
a[i][0] = G.VList[i].data;
EdgeNode *p = G.VList[i].pp;
while(p)
{
cnt++;
a[p->edge][1]++;
p = p->nextedge;
}
a[i][2] = cnt;
}
for(int i=1;i<=G.n;i++)
{
cout<<a[i][0]<<':'<<a[i][1]<<' '<<a[i][2]<<' '<<a[i][1]+a[i][2]<<endl;
}
}
int main()
{
Graph G;
createUndirGraph(G);
BFS(G,1);
return 0;
}
/*
12 16
1 2 3 4 5 6 7 8 9 10 11 12
1 4
1 2
1 3
1 12
4 5
2 3
3 5
3 7
5 7
3 8
9 12
9 10
10 12
9 11
11 6
6 8
*/