数据结构第3章和滴4章参考答案

数据结构第三章和第四章滴参考答案,有需要的额同学可以下载下来看看哦!

3.2 写出一个算法判定所给的操作序列是否合法。若合法，返回1，否则返回0

（假设被判定的操作序列已存入一维数组中）

Panduan(char *t)

{

InitStack(S);

while(*t)

{switch(*t)

{case ‘I’: Push(S,*t); break;

case ‘O’:if(!StackEmpty (S)) { Pop(S,e); break;} else return 0; } t++; }

if(!EmptyStack(T)) return 1;

return 0;

}

3.3 假设表达式中允许包含三种括号，圆括号，方括号和大括号，编写一个算法判断表达式中的括号是不是匹配

//入栈的操作

void push_stack(STACK *stack, char e)

{

stack->top++;

stack->ex[stack->top] = e;

}

//出栈的操作

bool pop_stack(STACK *stack, char *ch)

{

if(-1 == stack->top)

return false;

else

{

*ch = stack->ex[stack->top];

stack->top--;

}

return true;

}

//判断是不是匹配

//注意：此处有很多同学在判断右括号时，没有考虑栈顶元素，并要弹出栈顶元素 bool is_match(char *exp)

{

int i = 0;

char ch;

STACK *stack;

stack = init_stack();

数据结构第三章和第四章滴参考答案,有需要的额同学可以下载下来看看哦!

while(exp[i] != '\0') { if('('==exp[i] || '['==exp[i] || '{'==exp[i]) { push_stack(stack, exp[i]); } //如果是左括号直接进栈 else if(')'==exp[i] || ']'==exp[i] || '}'==exp[i]) { //，如果是右括号，考虑下面三种可能的匹配情况， switch(exp[i]) { case ')': if(pop_stack(stack, &ch)) { if(ch != '(') return false; } else return false; break; case ']': if(pop_stack(stack, &ch)) { if(ch != '[') return false; } else return false; break; case '}': if(pop_stack(stack, &ch)) { if(ch != '{') return false; } else return false; break; default:break; } } i++;

数据结构第三章和第四章滴参考答案,有需要的额同学可以下载下来看看哦!

}

if(stack->top==-1)

return true;

else

return false;

}

3.5编写一个算法，将一个环形队列（容量为n，元素下标从1到n）的元素倒置

解此题的思路是 将队列中的数据先转到栈中，然后再把栈中的数据转到另一个队列中，实现倒置。//注意：不是简单的首尾元素交换！因为交换意味着有元素要进队，而进队的操作与简单的交换操作是不同的！有很多同学是采取的交换方式

void traverse(QUEUE *queue1, QUEUE *queue2, STACK *stack)

{

queue1->front = (queue1->front)%10+1;

//将队列中的数出队放到栈中

while(queue1->front != queue1->rear)

{

stack->top++;

stack->c[stack->top] = queue1->ch[queue1->front];

queue1->front = (queue1->front)%10+1;

}

stack->top++;

stack->c[stack->top] = queue1->ch[queue1->front];

free(queue1);

//将元素出栈，放到队列中

queue2->rear = (queue2->rear)%10+1;

while(stack->top != -1)

{

queue2->ch[queue2->rear] = stack->c[stack->top];

stack->top--;

queue2->rear = (queue2->rear)%10+1;

}

}

4.1 采用顺序结构存储串，编写一个实现串通配符匹配的算法，pattern_index()其中的通配符只有“?”它可以和任意一字符匹配成功，例如pattern_index("?re", "there are")返回的结果是2

//字符串匹配

int pattern_index(STRING *t, STRING *s)

{

数据结构第三章和第四章滴参考答案,有需要的额同学可以下载下来看看哦!

int i = 0, j = 0; int n = 0; while(i<s->length) { if(s->string[i] == t->string[j] || t->string[j]==’?’) { i++; j++; } else {

i = i-j+1; //拉回到上一次匹配不成功的位置的下一处 j = 0; //模式串回到起始位置

} //注意：很多同学没有做这个动作！

//计算符合要求字串的个数

if(j>=t->length) //表明已经匹配成功

{

n++;

j = 0;

}

}

return n;

}