算法：C语言实现》习题4.8—— 给定两个序列，判断第二个序列是否可以由第一个序列出栈得到

159 阅读 0 评论 105 点赞

我是靠谱客的博主洁净火，这篇文章主要介绍算法：C语言实现》习题4.8—— 给定两个序列，判断第二个序列是否可以由第一个序列出栈得到，现在分享给大家，希望可以做个参考。

《算法：C语言实现》习题4.8

这里，为了简化问题，假设序列的每个元素都不一样。

复制代码

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
#define N 10
#include <stdio.h>
int judge(char *s, char *d)
{
	char com[N] = {0};
	int end = 0;
	while(1)
	{
		if(*d == '') //成功
			return 0;
		if(*s == NULL && com[end-1] != *d)//入栈序列为空并且栈顶元素不等于待比较元素，则失败，返回-1
			return -1;
		if(*d == *s)
		{
			s = s + 1;
			d = d + 1;
		}
		else if(end > 0 && *d == com[end - 1])
		{
			d = d + 1;
			com[end] = 0;
			end --;
		}
		else if(*d != *s)
		{
			if( end == 0 || (end > 0 && *d != com[end - 1]) )
			{
				com[end] = *s;
				end ++;
				s = s + 1;
			}
		}
	}	
	return 0;
}


int main(int argc, char **argv)
{
	char source[N] = {0}, des[N] = {0};
	int i = 0;
	printf("请输入第一个字符串：n");
	scanf("%s",source);
	while(i ++ < 10)
	{
		printf("请输入待比较字符串：n");
		scanf("%s",des);
		int tag = judge(source,des);
		if(tag == 0)
			printf("Existn");
		else
			printf("Not exitstn");
	}
			
	return 0;
}