【数据结构周周练】003顺序栈与链栈 淩亂°似流年 2021-06-11 15:12 391阅读 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
还没有评论,来说两句吧...