数据结构 实验四 栈和队列的基本操作的实现

1. 实验目的

熟练掌握栈和队列的抽象数据类型，能在相应的应用问题中正确选用它们，熟练掌握栈和队列的实现方法（顺序和链式），两种存储结构和基本操作的实现算法，注意空和满的判断条件及它们的描述方法，掌握循环队列与其它顺序结构实现上的不同及解决办法，熟悉各种队列的基本操作在循环队列上的实现

1. 实验内容

（1）用栈实现括号匹配的检验

（2）用栈实现形如a+b@b+a#的中心对称的字符序列的检验。

（3）用队列实现形如a+b@b+a#的中心对称的字符序列的检验

选择合适的存储结构（顺序栈或链式栈）表示栈，给出其定义，在上述存储结构上实现栈的基本操作：初始化、置栈空、入栈、出栈、取栈顶元素等。选择合适的存储结构（循环队列）表示队列，解决队空、队满判断条件相同的矛盾，实现基于循环队列的存储结构的基本操作，初始化、队空/满判断，入队、出队、取队头元素、求队列长度等，对所写出的算法进行时间复杂度分析

1. 数据结构定义

    （说明你算法中用到的数据结构、数据类型的定义）

栈：

ADT Stack {

  数据对象：D={ai| ai Î ElemSet, i=1,2,…,n, n³0}

  数据关系：R1={< ai-1, ai >| ai-1，ai ÎD，i=2,…,n}

  基本操作：InitStack（&S）, DestroyStack(&S)

                  ClearStack(&S), StackEmpty(S)

                  StackLength(&S), GetTop(S, &e)

                  Push(&S, e),         Pop(&S, &e)

                  StackTraverse(s, visit())

              } ADT Stack

队列：

ADT Queue {

       数据对象：D={ai | ai Î ElemSet, i=1,2,…,n, n>=0}

       数据关系：R1={< ai-1, ai > | ai-1, ai ÎD， i=1,2,…,n}

       基本操作：InitQueue(&Q) , DestroyQueue(&Q)

                       ClearQueue(&Q) , QueueEmpty(Q)

                       QueueLength(Q), Gethead(Q, &e)

                       EnQueue(&Q, e), DeQueue(&Q, &e)

                       QueueTraverse(Q, Visit())

       }ADT Queue

1. 算法思想及算法设计

    （先文字说明算法的思想，然后给出类C语言算法）

1、

括号问题可以用来解决C语言中的“{”和“}”的匹配问题，可以观察到，如果从左至右扫描一个字符串，那么每个右括号将于最近遇到的那个未匹配的左括号相匹配，在从左至右的扫描工程中把所遇到的左括号存放到堆栈内，每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。

2、

先把@符号前的字符进栈，然后出栈与@后的字符一一比较。

void match(){ InitStack(S);printf("input with #:");c=getchar();while (c!='@'){  push(S,c);c=getchar();}c=getchar();while (c!='#'&&!StackEmpty(S)){   x=Pop(S,x);if (c==x) c=getchar();else { printf("not match\n");      return;     }}if (c==‘#’ && StackEmpty(S))       printf("match");else  printf("not match");}

实验代码

    （即C语言程序）

1、

#include#includetypedef struct{char * base;char * top;int stacksize;}stack;void initstack(stack*s)//栈的初始化函数{s->base = (char*)malloc(sizeof(char));if (!s->base)//检测内存是否分配成功{exit(0);}s->base = s->top;s->stacksize = 10;}void push(stack*s, char x)//入栈函数{if (s->top - s->base >= s->stacksize)//先检测是否发生上溢{s->base = (char*)realloc(s->base, (s->stacksize + 10) * sizeof(char));//若发生，则增加10个内存空间（动态扩容）if (!s->base)//检测内存是否分配成功{exit(0);}s->stacksize = s->stacksize + 10;s->top = s->base + 10;}*s->top = x;s->top++;}int main(){stack * s = (stack*)malloc(sizeof(stack));initstack(s);char c;printf("请输入测试用例（如{[]()}#,#标志输入结束）：");c=getchar();push(s,c);while (c != '#'){c=getchar();if (c == '{'||c == '('||c == '['){push(s, c);}if (c == '}'||c == ')'||c == ']'){if (s->base == s->top){push(s, c);}if (c == '}'){if (*--(s->top) == '{')//这里解释下，*--(s->top)很明显是栈顶元素，但是这个操作已经实现了top--。变相的实现了pop功能。所以实际上是没有删除栈中的元素，只是移动top指针，不断的覆盖元素。{//top--已经实现，这里不需要任何操作}else{push(s, c);}}if (c == ')'){if (*--(s->top) == '('){}else{push(s, c);}}if (c == ']'){if (*--(s->top) == '['){}else{push(s, c);}}}}if (s->base == s->top){printf("括号匹配成功");}else{printf("括号匹配失败");}return 0;}

2、

#include#include#define TRUE 1#define FALSE 0#define ERROR 0#define OK 1#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef char SElemType;typedef struct {SElemType *base;SElemType *top;int stacksize;} SqStack;Status InitStack(SqStack *S) {//构造一个空栈，该栈由指针指示S->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));//栈的连续空间分配if (!S->base)exit(OVERFLOW);//存储分配失败S->top = S->base;//空栈，初始化栈顶指针S->stacksize = STACK_INIT_SIZE;return OK;}Status Push(SqStack *S, SElemType e) {//插入元素e作为新的栈顶if (S->top - S->base >= S->stacksize) {//栈满，追加存储空间S->base = (SElemType*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));if (!S->base)exit(OVERFLOW);S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;}*S->top = e;S->top++;return OK;}Status Pop(SqStack *S) {//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR;if (S->top == S->base){printf("栈空");return ERROR;}return *--S->top;//--S->top; e=*S->top;}SElemType GetTop(SqStack *S) {//若栈不空，则删除S的栈顶元素，并返回OK，否则返回ERRERif (S->top = S->base){// printf("栈空");return ERROR;}return *(S->top - 1);//取栈顶元素}Status StackEmpty(SqStack *S) {if (S->top == S->base){//printf("栈空");return TRUE;}else{// printf("栈非空");return FALSE;}}Status Match(SqStack *S) {char c, x;c = getchar();while (c != '@') {Push(S, c);c = getchar();}c = getchar();while (c != '@' && !StackEmpty(S)) { //c不等于中心对称的标记'@'同时S栈还不能是空的x = Pop(S);if (c == x)c = getchar();else {printf("not match\n");return ERROR;}}if (c == '#'&&StackEmpty(S))//为了解决前半部分确实匹配上了，但是"@"后边的部分超过了前边部分的长度{printf("match!\n");return OK;}else{printf("not match\n");return ERROR;}}int main(){SqStack S;InitStack(&S);printf("请输入字符序列，对称中心是'@'，以'#'结束！\n");Match(&S);system("pause");return 0;}

3、

#include#include#include#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0#define OVERFLOW 0#define MAXQSIZE 100typedef int Status;typedef char QElemType;typedef struct {QElemType *base;int front;//指向队列的第一个元素int rear;//指向队列的最后一个元素的下一个元素} SqQueue;Status InitQueue(SqQueue *Q) {//构造一个空队列QQ->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));//if (!Q->base)exit(OVERFLOW);//存储分配失败Q->front = Q->rear = 0;//初始化头指针，尾指针return OK;}Status EnQueue(SqQueue *Q, QElemType e) {//插入元素e作为Q的新的队尾元素if ((Q->rear + 1) % MAXQSIZE == Q->front)//队列满return ERROR;Q->base[Q->rear] = e;//把这个入队列的数保存在头指针指的那个位置，其实他不是一个真正的指针，只不过是为了方便保存元素Q->rear = (Q->rear + 1) % MAXQSIZE;//尾指针向前移动一位return OK;}Status DeQueue(SqQueue *Q, QElemType *e) {//若队列不空，则删除Q 的队头元素，用e返回其值，并返回OK否则返回ERRORif (Q->front == Q->rear)//队列满return ERROR;*e = Q->base[Q->front];//出队列时，队头元素先出去Q->front = (Q->front + 1) % MAXQSIZE;//头指针向前移动一位return OK;}Status DeQueue_rear(SqQueue *Q, QElemType *e) {//若队列不空，则删除Q 的队尾元素，用e返回其值，并返回OK否则返回ERRORif (Q->front == Q->rear)//队列满return ERROR;Q->rear = (Q->rear - 1) % MAXQSIZE;//队尾指针总是指向最后一个元素的下一个元素的位置，因此在删队尾元素时要先把指针向前移动一位*e = Q->base[Q->rear];//然后取出这个元素return OK;}Status QueueEmpty(SqQueue Q) {if (Q.front == Q.rear)return TRUE;elsereturn FALSE;}int QueueLength(SqQueue Q) {//返回Q中元素的个数，即队列的长度return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;}Status Match(char*a) {char c, b;char*p; //定义字符指针变量pp = a;//把字符串数组的首地址赋给pSqQueue Q;//定义队列QInitQueue(&Q);//初始化队列Qwhile (*p != '@') {//p当前所指的元素值不是对称中心字符 的标记EnQueue(&Q, *p);//让p所指的字符进队列p++;//p指针指向下一个字符}p++;//跳过对称中心标志@，不让他进队列while (*p != '#') { //p当前所指的字符不是队尾结束EnQueue(&Q, *p);//继续进队列p++;// p指针后移}while (QueueLength(Q) != 0){//循环的条件限制为队列不是空的，从队尾队头分别删除字符进行比较if (!DeQueue(&Q, &b))//取出队头元素，同时检查是否能取成功return OVERFLOW;if (!DeQueue_rear(&Q, &c))//取出队尾元素，同时检查是否能取成功return OVERFLOW;//队长不为零，取队头元素和队尾元素比较if (b != c) //如果检测出有一对队头与队尾字符不匹配，就证明这个字符串不是中心对称的{printf("不是中心对称字符序列!\n");return FALSE;}}if (Q.rear == Q.front)//当从队头队尾删除字符的两个指针相遇时，说明他们之前的字符都成功匹配上了printf("是中心对称字符序列！");return OK;}int main() {char a[100];//定义字符数组printf("请输入要检验的字符序列,以#作为结束标志！\n");gets(a);//接收字符串Match(a);//数组名做实参，把数组首元素的地址传递给形参system("pause");return 0;}

1. 算法测试结果

    （说明测试数据，粘贴实验结果图）

实验数据：{（【】）} （{}】）

1. 分析与总结

    （1）算法复杂度分析及优、缺点分析

        （说明你编写算法的复杂度，算法的优点和缺点有哪些）

对输入的一串字符逐个进栈，知道标识符@的出现后，然后再依次出栈与标识符后的字符一一进行比较，其中基本语句就是进栈和出栈比较的过程，其时间复杂度为O（n).

    （2）实验总结

        （说明你怎么解决实验中遇到的问题，有什么收获）

通过这次实验，我能够熟练掌握栈和队列的抽象数据类型，能在相应的应用问题中正确选用它们，熟练掌握栈和队列的实现方法（顺序和链式），两种存储结构和基本操作的实现算法，注意空和满的判断条件及它们的描述方法，掌握循环队列与其它顺序结构实现上的不同及解决办法，熟悉各种队列的基本操作在循环队列上的实现。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！