本文共 6404 字，大约阅读时间需要 21 分钟。

这次只有一道题，采用了五种算法来实现，一个是普通方法，不采用任何结构，一个是用顺序表，一个是用链表，一个是用顺序栈，一个是用链栈。但是结构定义和算法实现方法不唯一，如果大家有其他的算法实现，在下面评论哦！

目录

习题一：判断序列是否合法

1、题目

I表示入栈操作，O表示出栈操作，栈的初始状态与终态均为空，由I，O组成序列，可以进行栈的操作的序列称为合法序列，否则称为不合法序列。

A: IIIIOOOO

B: IOIOIOIO

C: IIOOOIOI

D: IIIOOIOO

2、普通方法实现

代码

#include
   
    char A[] = { 'I','I','I','I','O','O','O','O' };char B[] = { 'I','O','I','O','I','O','I','O' };char C[] = { 'I','I','O','O','O','I','O','I' };char D[] = { 'I','I','I','O','O','I','O','O' };int Legal(char * Arr) {	int k = 0;	int i = 0;	while (i < 8 && k >= 0) {		if (Arr[i] == 'I')			k++;		else			k--;		i++;	}	if(k<0)	{		return 0;	}	return 1;}void main() {	if (Legal(A))		std::cout << "A 序列合法" << std::endl;	else		std::cout << "A 序列不合法" << std::endl;	if (Legal(B))		std::cout << "B 序列合法" << std::endl;	else		std::cout << "B 序列不合法" << std::endl;	if (Legal(C))		std::cout << "C 序列合法" << std::endl;	else		std::cout << "C 序列不合法" << std::endl;	if (Legal(D))		std::cout << "D 序列合法" << std::endl;	else		std::cout << "D 序列不合法" << std::endl;}
   

执行结果

3、顺序表实现

代码

#define MAXLISTSIZE 20#define LISTINCREMENT 5#include 
   
    #include
    
     using namespace std;char A[] = { 'I','I','I','I','O','O','O','O' };char B[] = { 'I','O','I','O','I','O','I','O' };char C[] = { 'I','I','O','O','O','I','O','I' };char D[] = { 'I','I','I','O','O','I','O','O' };typedef struct {	char *elem;	int length;	int listsize;}SqList;int InitSqList(SqList & S) {	S.elem = (char *)malloc(MAXLISTSIZE * sizeof(SqList));	if (!S.elem)	{		cout << "空间分配失败" << endl;		return OVERFLOW;	}	S.length = 0;	S.listsize = MAXLISTSIZE;	return 1;}int JudgeSqList(SqList S, char *A) {	int j = 0;	int k = 0;	for (int i = 0; i < 8; i++)	{				if (A[i] == 'I') {			S.elem[j] = A[i];			j++;		}		else if (A[i] == 'O' && S.elem[k] == 'I')		{			S.elem[k] = A[i];			k++;		}		else		{			return 0;		}	}	return 1;}void main() {	SqList LA, LB, LC, LD;	InitSqList(LA);	InitSqList(LB);	InitSqList(LC);	InitSqList(LD);	if (JudgeSqList(LA, A))		cout << "A 序列合法" << endl;	else		cout << "A 序列不合法" << endl;	if (JudgeSqList(LB, B))		cout << "B 序列合法" << endl;	else		cout << "B 序列不合法" << endl;	if (JudgeSqList(LC, C))		cout << "C 序列合法" << endl;	else		cout << "C 序列不合法" << endl;	if (JudgeSqList(LD, D))		cout << "D 序列合法" << endl;	else		cout << "D 序列不合法" << endl;}
    
   

执行结果

4、链表实现

代码

#include 
   
    #include
    
     using namespace std;char A[] = { 'I','I','I','I','O','O','O','O' };char B[] = { 'I','O','I','O','I','O','I','O' };char C[] = { 'I','I','O','O','O','I','O','I' };char D[] = { 'I','I','I','O','O','I','O','O' };typedef struct LNode {	char elem;	LNode * next;}LNode,*LinkList;int InitList(LinkList &L) {	L = (LinkList)malloc(sizeof(LNode));	if (!L)	{		cout << "空间分配失败" << endl;		return OVERFLOW;	}	L->next = NULL;}int JudgeList(LinkList &L,char *A) {	LinkList p = L;	LinkList q = (LinkList)malloc(sizeof(LNode));	q->elem = 'I';	q->next = NULL;	p->next = q;	p = q;	q = p->next;		for (int i = 0; i < 8;i++)	{		if (!L->next)			return 0;		else if (A[i] == 'I')		{			q = (LinkList)malloc(sizeof(LNode));			if (!q)			{				cout << "空间分配失败" << endl;				return OVERFLOW;			}			q->elem = 'I';			q->next = NULL;			p->next = q;			p = q;		}		else 		{			LinkList l = L->next;			L->next = l->next;			free(l);		}			}	return 1;}void main() {	LinkList LA, LB, LC, LD;	InitList(LA);	InitList(LB);	InitList(LC);	InitList(LD);	if (JudgeList(LA,A))		cout << "A 序列合法" << endl;	else 		cout << "A 序列不合法" << endl;	if (JudgeList(LB, B))		cout << "B 序列合法" << endl;	else		cout << "B 序列不合法" << endl;	if (JudgeList(LC, C))		cout << "C 序列合法" << endl;	else		cout << "C 序列不合法" << endl;	if (JudgeList(LD, D))		cout << "D 序列合法" << endl;	else		cout << "D 序列不合法" << endl;}
    
   

执行结果

5、顺序栈实现

代码

#define MAXSTACKSIZE 20#define STACKCREMENT 5#include
   
    #include
    
     using namespace std;typedef struct {	int *base;	int *top;	int stacksize;}SqStack;int InitSqStack(SqStack &S) {	S.base = (int*)malloc(MAXSTACKSIZE * sizeof(int));	if (!S.base)	{		exit(OVERFLOW);	}	S.top = S.base;	S.stacksize = MAXSTACKSIZE;	return 1;}int Push(SqStack &S, int e) {	if (S.top - S.base == S.stacksize) {		S.base = (int *)realloc(S.base, (S.stacksize + STACKCREMENT) * sizeof(SqStack));		if (!S.base)		{			cout << "空间分配失败" << endl;			exit(OVERFLOW);		}		S.stacksize += STACKCREMENT;	}	*S.top++ = e;	return 1;}int Pop(SqStack &S, int &e) {	if (S.top == S.base)		return 0;	e = *--S.top;	return 1;}int IsEmpty(SqStack S) {	if (S.top==S.base)	{		return 1;	}	return 0;}int JudgeStack(SqStack &S, char *Arr,int e) {	for (int i = 0; i < 8; i++)	{		if (Arr[i] == 'I')			Push(S, e);		else if (Arr[i] == 'O' && !IsEmpty(S))			Pop(S, e);		else			return 0;	}	return 1;}void main() {	char A[] = { 'I','I','I','I','O','O','O','O' };	char B[] = { 'I','O','I','O','I','O','I','O' };	char C[] = { 'I','I','O','O','O','I','O','I' };	char D[] = { 'I','I','I','O','O','I','O','O' };	SqStack SA, SB, SC, SD;	int e = 1;	InitSqStack(SA);	InitSqStack(SB);	InitSqStack(SC);	InitSqStack(SD);		if(JudgeStack(SA, A, e))		cout<<"A数组合法。"<
    
   

执行结果

6、链栈实现

代码

#include
   
    #include
    
     using namespace std;char A[] = { 'I','I','I','I','O','O','O','O' };char B[] = { 'I','O','I','O','I','O','I','O' };char C[] = { 'I','I','O','O','O','I','O','I' };char D[] = { 'I','I','I','O','O','I','O','O' };typedef struct LNode {	int data;	struct LNode *next;}LNode,*LinkStack;int InitStack(LinkStack &LS) {	LS = (LinkStack)malloc(sizeof(LNode));	if (!LS)	{		cout << "空间分配失败" << endl;		return OVERFLOW;	}	LS->next = NULL;	return 1;}int Push(LinkStack &LS, int e) {	//LinkStack sp = LS;	LinkStack sp = (LinkStack)malloc(sizeof(LNode));	sp->data = e;	sp->next = LS;	LS = sp;	return 1;}int Pop(LinkStack &LS, int &e) {	LinkStack sp;	if (LS->next)	{		sp = LS;		LS = LS->next;		free(sp);		return 1;	}	return 0;}int JudgeStack(LinkStack &LS, char*Arr, int &e) {	for (int i = 0; i < 8; i++)	{		if (Arr[i] == 'I')			Push(LS, e);		else if (Arr[i] == 'O' && LS->next)			Pop(LS, e);		else			return 0;	}	return 1;}void main() {	LinkStack LA, LB, LC, LD;	InitStack(LA);	InitStack(LB);	InitStack(LC);	InitStack(LD);	int e = 1;	if (JudgeStack(LA, A, e))		cout << "A数组合法。" << endl;	else		cout << "A数组不合法。" << endl;	if (JudgeStack(LB, B, e))		cout << "B数组合法。" << endl;	else		cout << "B数组不合法。" << endl;	if (JudgeStack(LC, C, e))		cout << "C数组合法。" << endl;	else		cout << "C数组不合法。" << endl;	if (JudgeStack(LD, D, e))		cout << "D数组合法。" << endl;	else		cout << "D数组不合法。" << endl;}
    
   

执行结果