数据结构实验报告5

数据结构实验报告——实验5

学号： 姓名： 得分：______________

一、实验目的

1、复习栈的逻辑结构、存储结构及基本操作； 2、掌握顺序栈、链栈。

二、实验内容

1、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作： （1）Status InitStack (&S) //构造空栈S； （2）Status Push(&S, e) //元素e入栈S；

（3）Status Pop(&S, &e) //栈S出栈，元素为e。 2、（必做题）请实现：对于一个可能包括括号{}、[]、()的表达式，判定其中括号是否匹配。

三、算法描述

（采用自然语言描述）

1. 构建空栈s，输入元素，将元素依次入栈，遍历打印栈中元素，输出栈顶元素，打印被输出的元素，遍历打印栈中元素。

2.构建空栈，输入表达式，使用函数count判断表达式中括号是否匹配，如果匹配输出匹配正确，不匹配则输出匹配错误。

四、详细设计

1.

开始 构建空栈s 输入元素 将元素依次入栈 遍历打印栈中元素 输出栈顶元素 打印被输出的元素 遍历打印栈中元素 结束 1

2.

开始 构建空栈s 输入表达式 使用函数count判断表达式中括号是否匹配 输出匹配错误 输出匹配正确 结束

五、程序代码

（给出必要注释） 1.

#include #include #define MaxSize 100

typedef struct node* SqStack; typedef char ElemType;

struct node//栈的数据结构 {

int top;

ElemType data[MaxSize]; };

void StatusInitStack(SqStack *L)//构造空栈S {

(*L) = (SqStack*)malloc(sizeof(SqStack)); (*L)->top = -1; }

2

void StatusPush(SqStack L, ElemType e)//元素e入栈S {

if (L->top == MaxSize - 1) {

printf(\栈满\\n\ } else {

L->top++;

L->data[L->top] = e; } }

void StatusPop(SqStack L, ElemType *e)//栈S出栈，元素为e {

if (L->top == -1) {

printf(\栈空\\n\ } else {

*e = L->data[L->top]; L->top--; } }

void Print(SqStack L)//遍历输出 {

int i = 0;

for(i = 0; i <= L->top; i++) {

printf(\ }

printf(\}

int main() {

SqStack s; ElemType e; ElemType* y; y = &e;

StatusInitStack(&s);

printf(\输入入栈数据:\ scanf(\

3

while (e!='\\n') {

StatusPush(s, e); scanf(\ }

printf(\目前栈中元素为:\\n\ Print(s);

StatusPop(s, y);

printf(\出栈元素是:%c\\n\

printf(\栈顶元素出栈后，栈为:\\n\ Print(s); } 2.

#include #include #include

#define STACK_INIT_SIZE 10 #define STACK_GROW_SIZE 5 #define ELEMTYPE char

typedef struct /*建立一个栈的首结点*/ {

ELEMTYPE * base; ELEMTYPE * top; int stacksize; } SpStack;

int InitStack(SpStack *s) /*建立空的栈并返回首地址*/ {

s->base=((ELEMTYPE*)malloc(STACK_INIT_SIZE*sizeof(ELEMTYPE))); if (!s->base) return 0; s->top=s->base;

s->stacksize=STACK_INIT_SIZE; return 1; }

int StackEmpty(SpStack *s) /*判断栈是否为空*/ {

if (s->top==s->base) return 1; else return 0; }

int Push(SpStack *s,ELEMTYPE e) /*往栈顶插入元素即进栈*/

4

{

if (s->top-s->base>=s->stacksize) /*判断是否栈满*/ {

s->base=((ELEMTYPE*)realloc(s->base,(s->stacksize+STACK_GROW_SIZE)*sizeof(ELEMTYPE))); if (!s->base) return 0;

s->stacksize+=STACK_GROW_SIZE; s->top=s->base+s->stacksize; }

*s->top++=e; return 1; }

int Pop(SpStack *s,ELEMTYPE *e) /*让栈顶元素依次输出即出栈*/ {

if (StackEmpty(s)) return 0; *e=*(--s->top); return 1; }

int Count(SpStack *s) {

ELEMTYPE e[STACK_INIT_SIZE*2]; ELEMTYPE e1; int i;

InitStack(s); gets(e);

if ('\\n'==e[strlen(e)-1]) e[strlen(e)-1]=0; for (i=0; e[i]!='\\0'; i++) {

switch (e[i]) {

case '(': case '[': case '{':

Push(s,e[i]); break; case ')': case ']': case '}':

if(StackEmpty(s)) {

printf(\匹配错误\\n\

5

本文来源：https://www.bwwdw.com/article/8b5d.html