【数据结构周周练】003顺序栈与链栈

淩亂°似流年 2021-06-11 15:12 446阅读 0赞

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

**目录**

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

1、题目

2、普通方法实现

3、顺序表实现

4、链表实现

5、顺序栈实现

6、链栈实现

--------------------

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

## 1、题目 ##

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

A: IIIIOOOO

B: IOIOIOIO

C: IIOOOIOI

D: IIIOOIOO

## 2、普通方法实现 ##

### 代码 ###

#include<iostream>
    
    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;
    }

### 执行结果 ###

![70][]

## 3、顺序表实现 ##

### 代码 ###

#define MAXLISTSIZE 20
    #define LISTINCREMENT 5
    
    #include <iostream>
    #include<malloc.h>
    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;
    }

### 执行结果 ###

![70 1][]

## 4、链表实现 ##

### 代码 ###

#include <iostream>
    #include<malloc.h>
    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;
    }

### 执行结果 ###

![70 2][]

## 5、顺序栈实现 ##

### 代码 ###

#define MAXSTACKSIZE 20
    #define STACKCREMENT 5
    #include<iostream>
    #include<malloc.h>
    
    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数组合法。"<<endl;
    	else
    		cout << "A数组不合法。" << endl;
    
    	if (JudgeStack(SB, B, e))
    		cout << "B数组合法。" << endl;
    	else
    		cout << "B数组不合法。" << endl;
    
    	if (JudgeStack(SC, C, e))
    		cout << "C数组合法。" << endl;
    	else
    		cout << "C数组不合法。" << endl;
    
    	if (JudgeStack(SD, D, e))
    		cout << "D数组合法。" << endl;
    	else
    		cout << "D数组不合法。" << endl;
    
    }

### 执行结果 ###

![70 3][]

## 6、链栈实现 ##

### 代码 ###

#include<iostream>
    #include<malloc.h>
    
    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;
    }

### 执行结果 ###

![70 4][]

[70]: /images/20210516/5caac8e96c384cab91649f086d4f046a.png
[70 1]: /images/20210516/20d095bbb9de4e70b044c3c6e67d9215.png
[70 2]: /images/20210516/fa238d6e1a234a5688753b643ff4c55e.png
[70 3]: /images/20210516/0657350f6b6846caa055df8f9ec3ed42.png
[70 4]: /images/20210516/de70f62fc5a04ac5923d277cda3cdbe1.png