C语言数据结构

发表于 | 分类于

数据结构课上的实验作业。收录了线性表、栈和图。

线性表的顺序存储

实验要求：
基本实验内容（顺序表）：
建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；
1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：
. 创建一个新的顺序表，实现动态空间分配的初始化；
. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；
. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；
. 利用最少的空间实现顺序表元素的逆转；
. 实现顺序表的各个元素的输出；
. 彻底销毁顺序线性表，回收所分配的空间；
. 对顺序线性表的所有元素删除，置为空表；
. 返回其数据元素个数；
. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；
. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；
. 判断顺序表中是否有元素存在，对判断结果进行返回；
. 编写主程序，实现对各不同的算法调用。

pubuse.h
后续所有算法几乎都要使用的常量定义（#define）和系统函数原型定义(#include)声明组合成一个文件，存储为一个头文件（取名为pubuse.h）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<process.h>

//#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define MAXSIZE 100
#define OK 1
#define ERROR 0
//#define OVERFLOW -2

seqlistdef.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef int Status;//Status是函数的类型，其值是函数结果状态码
//顺序表存储元素类型

typedef struct{
	char name[50];
	char style[50];
	float price;
}Restaurant;

typedef Restaurant ElemType;

typedef struct{
	ElemType *elem;
	int length;
}SqList;

seqlistAlgo.h

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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
void input(ElemType *e)
{
	//ElemType *e;
	printf("输入菜名\n");
	scanf("%s",e->name);
	printf("输入菜系\n");
	scanf("%s",e->style);
	printf("输入价格\n");
	if(scanf("%f",&e->price) != 1)
	{
		printf("\n输入有误，请重新输入！\n");
		fflush(stdin);
		input(e);
	}
}
void output(Restaurant e)
{
		printf("菜名: %-10s, 菜系: %-20s,  价格: %-10.2lf\n\n", e.name, e.style, e.price);
		putchar('\n');
}

Status InitList(SqList &L)
{
	//L.elem = new ElemType[MAXSIZE];
	L.elem=(Restaurant *)malloc(sizeof(ElemType)*MAXSIZE);
	if(!L.elem){
		printf("初始化失败。\n");
		exit(OVERFLOW);
	}
	L.length = 0;
	printf("\n初始化成功！\n");
	return OK;
}


int LocateElem(SqList &L,Restaurant e)
{
	int i;
	if(L.length == 0)
	{
		printf("\n线性表为空，暂无可以查询的数据！\n");
		return ERROR;
	}

	for(i=0;i<L.length;i++)
		if(!strcmp(L.elem[i].name,e.name))
			return i+1;
	return 0;
}

Status LocatePlace(SqList &L)
{
	int id;
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}
	
	else if(L.length == 0)
	{
		printf("\n线性表为空，暂无可以查询的数据！\n");
		return ERROR;
	}
	else
	{
		printf("请输入要查询的位置：");
		//scanf("%d",&id);

		if(scanf("%d",&id) == 0)
		{	
			printf("\n请输入数字！\n");
			return ERROR;
		}
		else if((id<1) || (id>L.length+1))
		{	
			printf("\n位置不合法！\n");
			return ERROR;
		}
		else
		{
			printf("菜名: %-10s, 菜系: %-20s,  价格: %-10.2lf\n\n", L.elem[id-1].name, L.elem[id-1].style, L.elem[id-1].price);
		}	
		return OK;
	}

}

Status LocateName(SqList &L)
{
	Restaurant e;

	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}

	if(L.length == 0)
	{
		printf("\n线性表为空，暂无可以查询的数据！\n");
		return ERROR;
	}
	else
	{
		printf("请输入需要查询的菜肴名称\n");
		scanf("%s",e.name);

		int temp=LocateElem(L,e);
		if(temp!=0)
			printf("菜名: %-10s, 菜系: %-20s,  价格: %-10.2lf\n\n", L.elem[temp-1].name, L.elem[temp-1].style, L.elem[temp-1].price);
		else
			printf("查询失败！没有此信息\n\n");
	}
	return OK;
}

Status ListInsert(SqList &L,int i,Restaurant e)
{
	int j;

	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}

	if((i<1) || (i>L.length+1))
	{	
		printf("\n位置不合法！\n");
		return ERROR;
	}

	if(L.length==MAXSIZE)
	{
		printf("\n存储空间已满。\n");
		return ERROR;
	}
	
	for(j=L.length-1;j>=i-1;j--)
		L.elem[j+1] = L.elem[j];
	L.elem[i-1] = e;
	++L.length;
	return OK;
}

Status ListInsert_client(SqList &L)
{
	int id;
	Restaurant r;

	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}

	printf("请输入插入位置：");
	//scanf("%d",&id);

	if(scanf("%d",&id) == 0)
	{	
		printf("\n请输入数字！\n");
		return ERROR;
	}
	else if((id<1) || (id>L.length+1))
	{	
		printf("\n位置不合法！\n");
		return ERROR;
	}
	else
	{
		printf("请输入所要插入菜肴的信息:\n");

		printf("请输入菜名：\n");
		scanf("%s",r.name);
		printf("请输入菜系：\n");
		scanf("%s",r.style);
		printf("请输入价格：\n");
		scanf("%f",&r.price);
	}

	if(ListInsert(L,id,r))
	{
		printf("插入成功!\n\n");
		return OK;}
	else
	{
		printf("插入失败!\n\n");
		return ERROR;}

}

Status ListDelete(SqList &L,int i)
{
	int j;
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}

	printf("\n删除元素的位置：");
	//scanf("%d",&i);
	
	if(scanf("%d",&i) == 0)
	{	
		printf("\n请输入数字！\n");
		return ERROR;
	}
	else if((i<1) || (i>L.length+1))
	{	
		printf("\n位置不合法！\n");
		return ERROR;
	}
	else
	{
		if((i<1) || (i>L.length))
			return ERROR;
		for(j=i;j<=L.length-1;j++)
			L.elem[j-1] = L.elem[j];
		--L.length;
		printf("\n删除成功！\n");
	}

	return OK;
}

Status ModifyList(SqList &L)
{
	int flag=0;
	Restaurant e1;
	Restaurant e2;
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}	
	if(L.length == 0)
	{
		printf("\n线性表为空，暂无可以修改的数据！\n");
		return ERROR;
	}
	else
	{
		printf("\n请输入要修改的菜肴名称：");
		scanf("%s",e1.name);

		int temp=LocateElem(L,e1);
		if(temp!=0)
		{
			flag=1;
			printf("\n将元素%s的价格更改为：",e1.name);
			scanf("%f",&e2.price);
			L.elem[temp-1].price = e2.price;
			printf("\n修改成功");
			//break;
			return OK;
		}
		else{
			if(flag == 0)
				printf("\n未找到该元素\n");
			return ERROR;
		}
	}
}

Status ReverseList(SqList &L)
{
	int i;
	Restaurant temp;
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}	

	for(i=0;i<L.length/2;i++)
	{
		temp = L.elem[i];
		L.elem[i] = L.elem[L.length-i-1];
		L.elem[L.length-i-1] = temp;
	}
	
	return OK;
}

Status CreateList(SqList &L)
{
	int i,count;
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}
	printf("\n请输入菜肴数量：(<100)");
	//scanf("%d",&count);
	if((scanf("%d",&count)) == 0)
	{	
		printf("\n请输入数字！\n");
		return ERROR;
	}
	else{
		if(count>100)
		{	
			printf("\n数量过多！\n");
			return ERROR;
		}
		else{
			for(i=0;i<count;i++)
			{  
				printf("\n将输入%d道菜肴的信息",count);
				printf("\n第%d道菜肴:\n",i+1);
				input(&L.elem[i]);
			}
			L.length=count;	
			putchar('\n');
		}
	}
		return OK;
}


int ListLength(SqList L)
{
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}
	printf("菜肴的个数为：%d\n",L.length);
	return L.length;
}

Status ClearList(SqList &L)
{
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}    
	L.length = 0;
    return OK;
}

int IsEmpty(SqList L)
{
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return 0;
	} 
	
	else if(L.length == 0)
	{
		printf("\n线性表为空。\n");
		return 1;
	}
	else
	{
		printf("\n线性表非空。\n");
		return 0;
	}

}

Status DestroyList(SqList &L)
{
	if(L.length<0)
	{
		printf("\n未进行初始化，请先进行初始化。\n");
		return ERROR;
	}
	if (L.elem)
   {      
	   free(L.elem);
	   exit(0);
   }
    return OK;
}

seqlistUse.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include "pubuse.h"
#include "seqlistDef.h"
#include "seqlistAlgo.h"

void Menu()
{
	printf("\n*******************************菜\t单*************************\n");
	printf("*\t\t\t1.初始化\t\t2.建表\t\t\t\t\t*\n");
	printf("*\t\t\t3.插入数据\t\t4.删除数据\t\t\t\t*\n");
	printf("*\t\t\t5.查看数据\t\t6.修改数据\t\t\t\t*\n");
	printf("*\t\t\t7.逆转顺序表\t\t8.清空顺序表\t\t\t\t*\n");
	printf("*\t\t\t9.销毁数据表（销毁之后程序结束）\t10.根据元素查找序号\t\t\t*\n");
	printf("*\t\t\t11.查看是否为空表\t12.查看表长\t\t\t\t*\n");
	printf("*\t\t\t13.根据序号查找元素\t14.退出\t\t\t\t\t*\n");	
}

void main()
{
	int i=0,n,flag;
	char a;

	
	//Restaurant e;
	//Restaurant e1;
	//Restaurant e2;
	SqList L;
start:
	do
	{
		Menu();
		printf("\n请输入操作序号：\n");
		fflush(stdin);
		scanf("%d",&n);

		if(n>0 && n<=14)
		{
			flag = 1;
			break;
		}
		else
		{
			flag = 0;
			system("cls");
			printf("\n输入有误，请重新选择。\n");
		}
	}
	while(flag == 0);
	while(flag == 1)
	{
		switch(n)
		{
		case 1:InitList(L);break;
		case 2:CreateList(L);break;
		case 3:ListInsert_client(L);break;
		case 4:ListDelete(L,i);break;
		case 5:
			if(L.length<0)
			{
				printf("\n未初始化，请先进行初始化！\n");
			}	
			for(i=0;i<L.length;i++)
		    {
				output(L.elem[i]);
			}
			break;
	
		case 6:ModifyList(L);break;
		case 7:ReverseList(L);break;
		case 8:ClearList(L);break;
		case 9:DestroyList(L);break;
		case 10:LocateName(L);break;
		case 11:IsEmpty(L);break;
		case 12:ListLength(L);break;
		case 13:LocatePlace(L);break;
		case 14:exit(0);//break;
		default:system("cls");goto start;		
		}
		printf("\nY继续菜单操作，N退出程序(y or n)：");
		fflush(stdin);
		a = getchar();
		if(a == 'y' || a == 'Y')
		{
			flag = 1;
			system("cls");
			Menu();
			printf("\n请选择操作序号：");
			fflush(stdin);
			scanf("%d",&n);
		}
		else
		{
			//free(L);
			exit(0);
		}
	}
}

最终界面：


然后初始化、建表等操作如图。我们做成的是菜单模式，有输入是否为数字的判断、数字范围判断等。

线性表的链式存储

实验要求：
建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。
其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。
1． 问题描述：
利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作：
. 初始化一个带表头结点的空链表；
. 创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。又分为逆位序(插在表头)输入n 个元素的值和正位序(插在表尾)输入n 个元素的值；
. 插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入）， 且保持结点的数据按原来的递增次序排列，形成有序链表。
. 删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部删除（值删除）；
. 输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点；
. 编写主程序，实现对各不同的算法调用。
其它的操作算法描述略。
pubuse.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<process.h>
#include <ctype.h>

#include <iostream>
#include <cstdio>
#define OK 1
#define ERROR 0;

linklistDef.h

1
2
3
4
5
6
7
8
9
10
11
12
typedef int Status;
//typedef int ElemType;        //    定义数据类型,可根据需要进行其他类型定义
typedef struct{
	char name[50];
	char style[50];
	float price;
}Restaurant;
                                //    链表节点的定义
typedef struct LNode {
    Restaurant  data;        //    数据域，存放数据
    struct LNode* next;        //    指向下一个链表节点
}LNode, *LinkList;

linklistAlgo.h

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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
//void PrintList(LinkList &L);
void input(Restaurant *e)
{
	printf("\t输入菜名:");
	scanf("%s",&e->name);
	printf("\n\t输入菜系:");
	scanf("%s",&e->style);
	printf("\n\t输入价格:");
	scanf("%f",&e->price);
	//i = scanf("%f",&e->price);
//	return i;
}

//初始化
Status InitList(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
	printf("\n初始化成功！\n");
	return OK;
}

//前插法创建单链表
Status CreateList_H(LinkList &L)
{
	int i,count,j;
	printf("\n请输入菜肴数量(<100):");
	j = scanf("%d",&count);
	if(j == 0)
	{
		printf("\n请输入数字!\n");
	    return ERROR;
	}
	else
	{
		if(count>100)
		{	
			printf("\n数量过多！\n");
			return ERROR;
		}
		else
		{
			printf("\n将输入%d道菜肴的信息",count);
			for(i=0;i<count;i++)
			{  
				LNode *p;
	            p = new LNode;

				printf("\n第%d道菜肴:\n",i+1);
				input(&p->data);
				p->next = L->next;
		        L->next = p;
			}
		printf("\n创建成功！\n");
		}
	}
		return OK;
}

//后插法创建单链表
Status CreateList_R(LinkList &L)
{
	int i,count,j;
	printf("\n请输入菜肴数量(<100):");
	j = scanf("%d",&count);
	LinkList r;
	LNode *p;
	r = L;
	if(j == 0)
	{
		printf("\n请输入数字!\n");
	    return ERROR;
	}
	else
	{
	    if(count>100)
		{	
	    	printf("\n数量过多！\n");
	    	return ERROR;
		}
    	else
		{
	    	printf("\n将输入%d道菜肴的信息:\n",count);
	    	for(i = 0;i < count;i++)
			{
		    	p = new LNode;
		    	printf("\n\t第%d道菜肴:\n\n",i+1);
		    	//scanf("%d",&p->data);
		    	input(&p->data);
		    	p->next = NULL;
			    r->next = p;
		        r = p;
			}
	    	printf("\n创建成功！\n");
	    	return OK;
		}
	}
}

//输出线性表
void PrintList(LinkList &L)
{
	LinkList p;
	p = L->next;
	if(p == NULL)
		printf("\n不存在数据\n");
	else
	{
		printf("\n\t\t菜名\t\t菜系\t\t价格\n");
		while(p != NULL)
		{
			printf("\t\t%-16s%-16s%-16.2lf\n", p->data.name, p->data.style, p->data.price);
			p = p->next;
		}
		printf("\n");
	}
}
//根据位置插入节点
Status ListInsert(LinkList &L)
{
	int id,j;
	Restaurant r;
	printf("\n请输入插入位置：");
	j = scanf("%d",&id);
	LNode *p;
	p = new LNode;
	p = L;
	int i = 0;
	if(j == 0)
	{
	    printf("\n请输入数字！\n");
		return ERROR;
	}
	else
	{
	    while(p && (i < id-1))
	    {
		    p = p->next;
		    i++;
	    }
	    if(!p || i > id-1)
	    {
		    printf("\n位置不合法！\n");
		    return ERROR;
	    }
	    printf("\n请输入所要插入菜肴的信息:\n\n");

	    printf("\t请输入菜名：");
	    scanf("%s",&r.name);
	    printf("\n\t请输入菜系：");
	    scanf("%s",&r.style);
	    printf("\n\t请输入价格：");
	    scanf("%f",&r.price);
	    LNode *s;
	    s = new LNode;
	    s->data = r;
	    s->next = p->next;
	    p->next = s;
	    printf("\n插入成功！\n");
	    return OK;
	}
}

//根据位置删除节点
Status ListDelete_locate(LinkList &L)
{
	int id,j;
	printf("\n请输入删除菜肴位置:");
	j = scanf("%d",&id);
	LNode *p;
	p = new LNode;
	p = L;
	int i=0;
	if(j == 0)
	{
	    printf("\n请输入数字！\n");
		return ERROR;
	}
	else
	{
		while((p->next) && (i < id-1))
	    {
	    	p = p->next;
		    ++i;
    	}
	    if(!(p->next) || (i > id-1))
	    {
	    	printf("\n位置不合法!\n");
		    return ERROR;
	    }
	    
    	LNode *q;
	    q = p->next;
    	p->next = q->next;
    	delete q;
    	printf("\n删除成功！\n");
	    return OK;
	}
}

//根据结点值删除
Status ListDelete_value(LinkList &L)
{
	Restaurant r;
	printf("\n请输入要删除的菜肴信息：\n\n");
	printf("\t请输入菜名：");
	scanf("%s",&r.name);
	printf("\t请输入菜系：");
	scanf("%s",&r.style);
	LNode *p = L;
	LNode *q = p;
	while(p && strcmp(p->data.name,r.name) || strcmp(p->data.style,r.style))
	{
		  q = p;
		  p = p->next;
	}
	if(p == NULL)
		printf("\n并没有该道菜！\n");
	else
	{
		q->next = p->next;
		delete p;
		printf("\n删除成功!\n");
	}
	return OK;
}

//查找元素
LNode *LocateElem(LinkList L)
{
	Restaurant r;
	printf("\n请输入需要查询的菜肴名称:");
	scanf("%s",r.name);
	int i = 0;
	bool b = true;
	LinkList p = L->next;
	while(p && strcmp(p->data.name,r.name))
	{
		p = p->next;
		i++;
	}
	if(p == NULL)
		printf("\n该菜肴不存在！\n");
	else 
	{
		printf("\t\t菜名\t\t菜系\t\t价格\n");
		printf("\t\t%-16s%-16s%-16.2lf\n", p->data.name, p->data.style, p->data.price);
	}
	return p;
}

//修改数据
LNode *ModifyList(LinkList &L)
{
	Restaurant r1,r2;
	LinkList temp;
	printf("\n请输入要修改的菜肴名称：");
	scanf("%s",r1.name);
	temp = L->next;
	while(temp && strcmp(temp->data.name,r1.name))
	{
		temp = temp->next;
	}
	if(temp == NULL)
	    printf("\n该菜肴不存在！\n");
	else 
	{
		printf("\n将元素%s的价格更改为：",r1.name);
		scanf("%f",&r2.price);
	    temp->data.price = r2.price;
	    printf("\n修改成功!\n");
	}
	return temp;
}

//清空链表

Status ClearList(LinkList L)
{
	LinkList p,q;
	p = L->next;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next=NULL;
	printf("\n清空成功!\n");
	return OK;
}

//销毁链表
Status DestoryList(LinkList &L)
{
	LinkList p;
	while(L)
	{
		p = L;
		L = L->next;
		delete p;
	}
	printf("\n销毁成功！\n");
	return OK;
}

//查看表长
int Length(LinkList L)
{
	int len = 0;
	LinkList p;
	p = L->next;
	while(p)
	{
		len++;
		p = p->next;
	}
	if(L->next)
	{
	    printf("\n菜肴的个数为：%d\n",len);	
	    return len;
	}
	else
	{
	    printf("\n菜肴的个数为：%d\n",0);
		return 0;
	}
}

//判断是否为空
bool IsEmpty(LinkList L)
{
	if(L->next)
	{
		printf("\n该表不为空!\n");
		return false;
	}
	else
	{
		printf("\n该表为空!\n");
		return true;
	}
}
//是否继续进行
int Continue(char a)
{
	if(a == 'y' || a == 'Y')
		{
			return 1;
		}
		else if (a == 'n' || a == 'N')
		{
			return 2;
		}
		else
		{
			return 3;
		}
}

linklistUse.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
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
#include "pubuse.h"
#include "linklistDef.h"
#include "linklistAlgo.h"
void Menu()
{
	printf("\n\t\t**************************************菜\t单*******************************\n");
	printf("\t\t*\t\t\t1.初始化\t\t2.建表\t\t\t\t*\n");
	printf("\t\t*\t\t\t3.插入菜肴\t\t4.删除菜肴\t\t\t*\n");
	printf("\t\t*\t\t\t5.查看菜肴\t\t6.查找菜肴\t\t\t*\n");
	printf("\t\t*\t\t\t7.修改菜肴\t\t8.清空链表\t\t\t*\n");
	printf("\t\t*\t\t\t9.查看是否为空\t\t10.查看菜肴个数\t\t\t*\n");
	printf("\t\t*\t\t\t11.销毁链表\t\t12.退出\t\t\t\t*\n");
}

void main()
{
	system("color F9");
	
	int n,flag,c = 0,ct;
	bool d = false;
	char a,b;
	LinkList L;
start:
	do
	{
		Menu();
		printf("\n请输入操作序号：");
		fflush(stdin);
		scanf("%d",&n);

		if(n>0 && n<13)
		{
			flag = 1;
			break;
		}
		else
		{
			flag = 0;
			system("cls");
			printf("\n输入有误，请重新选择。\n");
		}
	}
	while(flag == 0);
	while(flag == 1)
	{
		switch(n)
		{
		case 1:
			c = InitList(L);
			break;
		case 2:
			{
				if(c==1)
				{
					printf("\n\t选择正序(z)插入还是逆序(n)插入？(z or n):");
					fflush(stdin);
		            b = getchar();
					if(b == 'z' || b == 'Z')
					{
						CreateList_R(L);
						d = true;
						break;
					}
					else if(b == 'n' || b == 'N')
					{
						CreateList_H(L);
						d = true;
						break;
					}
					else
					{
						printf("\n输入错误！\n");
						break;
					}
				}
				else 
				{
					printf("\n请先初始化!\n");
					break;
				}
			}
		case 3:
			{
				if(d)
					ListInsert(L);
				else
					printf("\n请先建表!\n");
				break;
			}
		case 4:
			{
				if(d)
				{
					printf("\n\t选择按位置(w)删除还是按值(z)删除？(w or z):");
					fflush(stdin);
		            b = getchar();	
					if(b == 'w' || b == 'W')
					{
						ListDelete_locate(L);
						break;
					}
					else if(b == 'z' || b == 'Z')
					{
						ListDelete_value(L);
						break;
					}
					else
						printf("\n输入错误！\n");
				}
				else
					printf("\n请先建表!\n");
				break;
			}
		case 5:
			{
				if(d)
				    PrintList(L);
		    	else 
					printf("\n并无数据，请先建表!\n");
				break;
			}
		case 6:
			{
				if(d)
					LocateElem(L);
				else
					printf("\n并无数据，请先建表!\n");
				break;
			}
		case 7:
			{
				if(d)
					ModifyList(L);
                else 
					printf("\n并无数据，请先建表!\n");
				break;
			}
		case 8:
			{
				ClearList(L);
				d = false;
				break;
			}
		case 9:
			if(c!=1)
				printf("\n请先初始化。\n");
			else
			    IsEmpty(L);
			break;
		case 10:
			if(c!=1)
			    printf("\n请先初始化。\n");
			else
			    Length(L);
			break;
		case 11:
			if(c!=1)
			    printf("\n请先初始化。\n");
			else
				DestoryList(L);
				d = false;
			break;
		case 12:exit(0);
		default:
			system("cls");
			printf("\n输入错误，请重新选择。\n");
			goto start;		
		}
		printf("\nY继续菜单操作，N退出程序(y or n)：");
		fflush(stdin);
		a = getchar();
		ct=Continue(a);
		while(ct==3)//输入不合法
		{
			printf("\n输入错误，请重新选择Y继续菜单操作，N退出程序(y or n)：");
				fflush(stdin);
				a = getchar();
				ct=Continue(a);
		}
		if(ct==1)//输入合法y
		{
			int y;
			//flag = 1;
			system("cls");
			Menu();
			printf("\n请选择操作序号：");
			fflush(stdin);
			y=scanf("%d",&n);
			if(y==0)
			{
				system("cls");
				printf("\n输入有误，请重新选择。\n");
				goto start;
			}
		}
		else//输入合法n
		{
			exit(0);
		}
	}
}

栈的操作

问题描述：

（1）利用栈的顺序存储结构,设计一组输入数据，能够对顺序栈进行如下操作： 初始化、销毁栈、判空栈、清空栈、求栈长度、入栈、出栈、取栈顶元素、栈遍历等；
. 编写主程序，实现对各不同的算法调用。
实现以下功能：
1、实现十进制数与非十进制进制之间的转换；
2、算术表达式求值；
3、括号匹配检测

实现要求：

对顺序栈的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。
.“初始化栈算法”操作结果：构造一个空栈S；
.“销毁栈算法”操作结果：销毁栈S，S 不再存在；
.“置空栈算法” 操作结果：把S 置为空栈；
.“判是否空栈算法” 操作结果：若栈S 为空栈，则返回TRUE，否则返回FALSE；
.“求栈的长度算法” 操作结果：返回S 的元素个数，即栈的长度；
.“取栈顶元素算法” 操作结果：若栈不空，则用e 返回S 的栈顶元素，并返回OK；否则返回ERROR；
.“入栈算法”操作结果：插入元素e 为新的栈顶元素
.“出栈算法”操作结果：若栈不空，则删除S 的栈顶元素，用e 返回其值，并返回OK；否则返回ERROR
“栈遍历”操作结果：栈已存在且非空，从栈底到栈顶一次对栈里的每个数据元素经行访问并返回OK；否则返回ERROR 。

这里我选的链式栈：)
pubuse.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<process.h>
#include <stdlib.h>

//#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define MAXSIZE 100
#define OK 1
#define ERROR 0
//#define OVERFLOW -2

linklistDef.h

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXSIZE 100
#define STACKINCREAMENT 2
#define SElemType int
typedef int Status;
//typedef char SElemType;


typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;

linkstackAlgo.h

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
Status InitStack(LinkStack &S){
	S=NULL;
	return OK;
}

Status Push(LinkStack &S,SElemType e){
	StackNode *p;
	p = new StackNode;
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}

Status Pop(LinkStack &S,SElemType &e){
	StackNode *p;
	if(S == NULL) return ERROR;
	e = S->data;
	//printf("栈顶元素为：%d\n",e);
	p = S;
	S = S->next;
	delete p;
	return OK;
}

SElemType GetTop(LinkStack S){
	if(S!=NULL)
		return S->data;
}

bool IsEmpty(LinkStack S){
	if(S == NULL)
	{
		//printf("\n链栈为空。\n");
		return true;
	}
	else
	{
		//printf("\n链栈不为空。\n");
		return false;
	}
}

linkstackUse.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
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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
#include"pubuse.h"
#include"SqStackDef.h"
#include"SqStackAlgo.h"

LinkStack S;
SElemType e;

void Menu()
{
	printf("\t\t\t*************************************************************************\n");
	printf("\t\t\t*\t\t\t\t菜\t单\t\t\t\t*\n");	
	printf("\t\t\t*\t\t\t1.十进制转换为八进制\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t2.括号检测匹配\t\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t3.表达式求值\t\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t4.退\t出\t\t\t\t\t*\n");
	printf("\t\t\t*************************************************************************\n");
}

void Transform(int num)
{
	InitStack(S);
	while(num)
	{
		Push(S,num%8);
		num=num/8;
	}
	printf("结果为：");
	while(!IsEmpty(S))
	{
		Pop(S,e);
		printf("%d\n",e);
	}
}

Status Matching()
{
	InitStack(S);
	char ch;
	int flag = 1;
	scanf("%c",&ch);
	while(ch!='#' && flag)
	{
		switch(ch)
		{
		case '[':
			Push(S,ch);
			break;
		case '(':
			Push(S,ch);
			break;
		case ')':
			if(!IsEmpty(S) && GetTop(S)=='(')
				Pop(S,e);
			else
				flag = 0;
			break;
		case ']':
			if(!IsEmpty(S) && GetTop(S)=='[')
				Pop(S,e);
			else
				flag = 0;
			break;
		}
		scanf("%c",&ch);
	}
	if(IsEmpty(S) && flag)
	{
		printf("全部匹配完成。");
		return true;
	}
	else{
		printf("匹配失败。");
		return false;
	}
}


	Status In(char c)
	{
		switch(c){
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':
		case '#':
			return OK;
			break;
		default:
			return ERROR;
			break;		
		}	
	}


	char Precede(char op1,char op2)
	{
		switch(op1)
		{
			case '+':
				switch(op2)
				{
				case '*':
				case '/':
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;
				}
				break;
			
			case '-':
				switch(op2)
				{
				case '*':
				case '/':
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;
				}
				break;

			case '*':
				switch(op2)
				{
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;				
				}
				break;

			case '/':
				switch(op2)
				{
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;				
				}
				break;
				
			case '(':
				switch(op2)
				{
				case ')':
					return '=';
					break;
				default:
					return '<';
					break;
				}
				break;

			case ')':
				switch(op2)
				{
				default:
					return '>';
					break;
				}
				break;

			case '#':
				switch(op2)
				{
				case '#':
					return '=';
					break;
				default:
					return '<';
					break;
				}
				break;
				
			default:
				return '<';
				break;
		}
	
	}



	SElemType Operate(SElemType a,SElemType theta,SElemType b)
	{
		int result;
		switch(theta)
		{
		case '+':
			result = a+b;
			break;
		case '-':
			result = a-b;
			break;
		case '*':
			result = a*b;
			break;
		case '/':
			if(b==0)
			{
				printf("除数为零！");
				exit(0);
			}
			result = a/b;
			break;
		default:
			printf("不是操作符。\n");
			break;
		}
		printf("%d %c %d = %d\n",a,theta,b,result);
		return result;
	}


char EvaluateExpression()
{
	LinkStack OPND, OPTR;
	InitStack(OPND);
	InitStack(OPTR);
	SElemType a;
	SElemType b;
	SElemType theta;
	char ch;
	int flag=0;
	
	Push(OPTR,'#');
	scanf("%c",&ch);
	while(ch!='#' || GetTop(OPTR)!='#')
	{
		if(!In(ch))
		{
			if(!In(GetTop(OPND)) && flag)
			{
				int tmp=GetTop(OPND);
				Pop(OPND,e);
				Push(OPND,(ch-48)+tmp*10);
				scanf("%c",&ch);
			}
			else
			{
				Push(OPND,(ch-48));
				scanf("%c",&ch);
				flag=1;
			}
		}
		else
		{
			flag=0;
			switch(Precede(GetTop(OPTR),ch))
			{
			case '<':
				Push(OPTR,ch);
				scanf("%c",&ch);
				break;
			case '>':
				Pop(OPTR,theta);
				Pop(OPND,b);
				Pop(OPND,a);

				Push(OPND,Operate(a,theta,b));
				break;
			case '=':
				Pop(OPTR,e);
				scanf("%c",&ch);
				break;
			}
		}
	}
	return GetTop(OPND);
}
void main()
{
	int choice,f;
	//Menu();
start:
	do
	{
		Menu();
		fflush(stdin);
		printf("请输入要操作的序号：");
		fflush(stdin);
		scanf("%d",&choice);

		if(choice>0 && choice<=4)
		{
			f = 1;
			break;
		}
		else
		{
			f = 0;
			system("cls");
			printf("请输入菜单内的序号（1、2、3）。\n");
		}
	}
	while(f==0);
	while(f==1)
	{
		switch(choice)
		{
		case 1:
			int num;
			printf("\n请输入要转化的数字：\n");
			scanf("%d",&num);
			Transform(num);
			break;
		case 2:
			Matching();
			break;
		case 3:
			fflush(stdin);
			EvaluateExpression();
			break;
		case 4:
			exit(0);
		default:
			system("cls");
			goto start;
		}
		fflush(stdin);
		system("pause");
		system("cls");
		Menu();	
		goto start;

	}

}

写的时候遇到了一些问题。比如我的栈设计的是int类型，但是要操作的数据类型有int也有char。所以在表达式求值的时候，最开始出现了将输入的数字ascii值压栈的情况。于是我首先判断输入，操作数就减去48之后再压栈。

这样之后，我又遇到多位数只去最后一个压栈的数的问题，即识别不了多位数。于是我百度网上的方法之后，首先设置一个flag为0，flag值为1即取栈顶元素保存为tmp，再弹出栈顶元素，然后取下面一个值*10再加栈顶元素。

将三个程序合起来的时候，会有判断输入的序号再跳转到不同的情况，这时候就会读入一个回车字符。通过fflush(stdin)解决。

图的操作

. 采用邻接表或邻接矩阵方式存储图，实现图的深度优先遍历和广度优先遍历；
1.问题描述：
利用邻接表存储结构，设计一种图（有向或无向），并能够对其进行如下操作：
. 创建一个可以随机确定结点数和弧（有向或无向）数的图;
. 根据图结点的序号，得到该结点的值；
. 根据图结点的位置的第一个邻接顶点的序号，以及下一个邻接顶点的序号;
. 实现从第v 个顶点出发对图进行深度优先递归遍历;
. 实现对图作深度优先遍历;
. 实现对图进行广度优先非递归遍历;
. 编写主程序，实现对各不同的算法调用。

2．实现要求：（以邻接表存储形式为例）编写图的基本操作函数:：
.“建立图的邻接表算法”：CreateGraph(ALGraph *G)
操作结果：采用邻接表存储结构,构造没有相关信息的图G

.“邻接表表示的图的递归深度优先遍历算法”：DFS (ALGraph G,void(Visit)(char))
初始条件：图G 已经存在；
操作结果：返回图的从任意起点的按深度遍历的结果。

.“邻接表表示的图的广度优先遍历算法”： BFS (ALGraph G,void(Visit)(char))
初始条件：图G 已经存在；
操作结果：返回图的从任意起点的按广度遍历的结果。
分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

pubuse.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
//#include<stdlib>


#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<process.h>

#define MAX_VERTEX_NUM 100
#define OK 1
#define ERROR 0

ALGraphDef.h

图的邻接表的创建需要两个数组，一个是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef int GElemType;

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
	GElemType data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}LinkGraph;

ALGraphAlgo.h

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
bool visited[MAX_VERTEX_NUM];

int LocateVex(LinkGraph G,int v)
{
	for(int i=0;i<G.vexnum;i++)
	{
		if(v==G.vertices[i].data)
			return i;
	}
}

int LocateNum(LinkGraph G,int n)
{
	int m;
	if(n<0 || n>=G.vexnum)
	{
		printf("请输入%d个结点内的值",G.vexnum);
		printf("请输入序号：");
		scanf("%d",&m);
		LocateNum(G,m);
	}
	return G.vertices[n].data;
}


void CreateGraph(LinkGraph &G)
{
	ArcNode *p,*q;
	int i,j,k,v1,v2;
	printf("请输入顶点个数和边的数目，空格分隔：\n");
	scanf("%d%d",&G.vexnum,&G.arcnum);
	printf("\n%d---%d\n",G.vexnum,G.arcnum);
	printf("分别输入各个顶点值：\n");
	for(i=0;i<G.vexnum;i++)
	{
		scanf("%d",&G.vertices[i].data);
		G.vertices[i].firstarc=NULL;
	}
 
	printf("分别输入各边的两个顶点，空格分隔：\n");
	for(k=0;k<G.arcnum;k++)
	{
		scanf("%d %d",&v1,&v2);

		i=LocateVex(G,v1);
		j=LocateVex(G,v2);

		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=j;
		p->nextarc=NULL;
		p->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p;

		q=(ArcNode*)malloc(sizeof(ArcNode));
		q->adjvex=i;
		q->nextarc=NULL;
		q->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=q;
	}
	printf("无向图创建成功！\n");
}

//深度优先遍历
void dfs(LinkGraph G,int i)
{
	ArcNode *p;
	printf("访问结点%d：%d\n",i,G.vertices[i].data);

	visited[i]=1;
	p=G.vertices[i].firstarc;
	while(p)
	{
		if(!visited[p->adjvex])
			dfs(G,p->adjvex);
		p=p->nextarc;
	}
}

void DfsTraverse(LinkGraph G)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		visited[i]=0;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
			dfs(G,i);
}

//广度优先遍历
void bfs(LinkGraph G,int i)
{
	int j;
	ArcNode *p;
	int queue[MAX_VERTEX_NUM],head,tail;
	head=-1; 
	tail=-1;
	printf("访问结点%d：%d\n",i,G.vertices[i].data);
	visited[i]=1;
	queue[++tail]=i;
	while(tail>head)
	{
		j=queue[++head];
		p=G.vertices[j].firstarc;
		while(p)
		{
			if(visited[p->adjvex]==0)
			{
				printf("%d ",G.vertices[p->adjvex].data);
				queue[++tail]=p->adjvex;
				visited[p->adjvex]=1;
			}
			p=p->nextarc;
		}	
	}
}

int BfsTraverse(LinkGraph G)
{
	int i,count=0;
	for(i=0;i<G.vexnum;i++)
		visited[i]=0;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
		{
			printf("\n");
			count++;
			bfs(G,i);
		}
		printf("该图共有%d个连通分量。\n",count);
		return count;
}

ALGraphUse.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
#include"pubuse.h"
#include"ALGraphDef.h"
#include"ALGraphAlgo.h"

void Menu()
{
	printf("\t\t\t*************************************************************************\n");
	printf("\t\t\t*\t\t\t\t菜\t单\t\t\t\t*\n");	
	printf("\t\t\t*\t\t\t1.建立无向图\t\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t2.深度优先搜索\t\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t3.广度优先搜索\t\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t3.按序号查找值\t\t\t\t\t*\n");
	printf("\t\t\t*\t\t\t5.退\t出\t\t\t\t\t*\n");
	printf("\t\t\t*************************************************************************\n");
}

int main()
{
	int n,data,choice,f;
	LinkGraph G;

start:
	do
	{
		Menu();
		fflush(stdin);
		printf("请输入要操作的序号：");
		scanf("%d",&choice);

		if(choice>0 && choice<=5)
		{
			f = 1;
			break;
		}
		else
		{
			f = 0;
			system("cls");
			printf("请输入菜单内的序号（1、2、3）。\n");
		}
	}

	while(f==0);
	while(f==1)
	{
		switch(choice)
		{
		case 1:
			CreateGraph(G);
			break;
		case 2:
			DfsTraverse(G);
			break;
		case 3:
			BfsTraverse(G);
			break;
		case 4:
			printf("请输入想要查找的结点序号：");
			scanf("%d",&n);
			data=LocateNum(G,n);
			printf("该结点的值为：%d\n",data);
			break;
		case 5:
			exit(0);
		default:
			system("cls");
			goto start;
		}
		system("pause");
		system("cls");	
		goto start;
	}
	return 0;
}