原创 数据结构第3章习题参考答案(1)

这是第3章的部分答案.所有的基础知识题基本没贴出来,因为相对简单.另外3.24-3.27也比较简单,没有贴出来,3.28以后是关于queue的题目,还没来得及做.

// chapt3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include <ctype.h>

//////////////////////////////////////////////////////
//
//下面实现一个stack及其基本操作
//
/////////////////////////////////////////////////////
#define STACK_INIT_SIZE 1024

typedef struct _sqstack
{
 int *bottom;
 int top;
 int size;
}sqstack,*psqstack;

//初始化stack
bool init_stack(sqstack *s)
{
 if((s->bottom=(int *)malloc(sizeof(int)*STACK_INIT_SIZE))==NULL)
  return false;
 s->top=-1;
 s->size=STACK_INIT_SIZE;
 return true;
}

bool push(psqstack s,int x)
{
 if(s->top>=s->size-1)
  return false;
 s->bottom[++s->top]=x;
 return true;
}

bool pop(sqstack *s,int *x)
{
 if(s->top==-1||s->size<=0)
  return false;
 *x=s->bottom[s->top--];
 return true;
}

bool stack_empty(sqstack *s)
{
 if(s->top==-1)
  return true;
 return false;
}

bool get_stack_top(sqstack *s,int *x)
{
 if(s->top==-1||s->size<=0)
  return false;
 *x=s->bottom[s->top];
 return true;
}

void destroy_stack(psqstack s)
{
 free(s->bottom);
 s->size=0;
 s->top=-1;
}

void clean_stack(psqstack s)
{
 s->top=-1;
}

int stack_length(psqstack s)
{
 return s->top+1;
}

void test(int *sum)
{
 int x;
 scanf("%d",&x);
 if(x==0)
  *sum=0;
 else
 {
  test(sum);
  *sum+=x;
 }
 printf("%d\t",*sum);
}

void test_loop(int *sum)
{
 int x;
 sqstack s;
 if(!init_stack(&s))
 {
  printf("init stack error\n");
  return;
 }

 scanf("%d",&x);
 while(x!=0)
 {
  //*sum+=x;
  push(&s,x);
  scanf("%d",&x);
 }
 printf("%d\t",0);
 *sum=0;
 //push(&s,*sum);
 while(!stack_empty(&s))
 {
  pop(&s,&x);
  *sum+=x;
  printf("%d\t",*sum);
 }
}

//双向stack
typedef struct _twstack{
 int *left;
 int *right;
 int ltop;
 int rtop;
 int size;
}twstack,*ptwstack;
typedef enum{
 LEFT=0,
 RIGHT=1
}Side;

bool init_twstack(ptwstack s)
{
 if((s->left=(int*)malloc(sizeof(int)*STACK_INIT_SIZE))==NULL)
  return false;
 s->right=&(s->left[STACK_INIT_SIZE-1]);
 s->size=STACK_INIT_SIZE;
 s->ltop=-1;
 s->rtop=1;
 return true;
}

bool push_twstack(ptwstack s,int x,Side a)
{
 if(s->ltop+1>=s->size+s->rtop)
  return false;
 switch (a)
 {
 case LEFT:
  s->left[++s->ltop]=x;
  return true;
 case RIGHT:
  s->right[--s->rtop]=x;
  return true;
 default:
  return false;
 }
}

bool pop_twstack(ptwstack s,int *x,Side a)
{
 if(s->size<=0)
  return false;
 switch(a)
 {
 case LEFT:
  if(s->ltop==-1)
   return false;
  *x=s->left[s->ltop--];
  break;
 case RIGHT:
  if(s->rtop==1)
   return false;
  *x=s->right[s->rtop++];
  break;
 default:
  return false;
 }
 return true;
}

//ex 3.17
bool check_express(psqstack s)
{
 char x,y;
 bool status="true";
 bool flag="true";
 scanf("%c",&x);
 while(x!='@')
 {
  if(!flag)
  {
   if(!pop(s,(int*)&y))
    status=false;
   else if(y!=x)
     status=false;
   
   scanf("%c",&x);
  }

  else if(x!='&')
  {
   push(s,(int)x);
   scanf("%c",&x);
   //continue;
  }
  else{
   flag=false;
   scanf("%c",&x);
  }
 }
 return status;
}

//ex3.18
bool check_bracket(sqstack *s)
{
 bool ret="true";
 char x;
 int data;

 scanf("%c",&x);
 while(x!='\n')
 {
  switch (x)
  {
  case '(':
  case '[':
  case '<':
  case '{':
   push(s,(int)x);
   break;
  case ')':
   pop(s,&data);
   if((char)data!='(')
    ret=false;
   break;
  case ']':
   pop(s,&data);
   if((char)data!='[')
    ret=false;
   break;
  case '>':
   pop(s,&data);
   if((char)data!='<')
    ret=false;
   break;
  case '}':
   pop(s,&data);
   if((char)data!='{')
    ret=false;
   break;
  default:
   break;
  }
  scanf("%c",&x);
 }
 if(ret&&stack_empty(s))
  return true;
 return false;
}

//ex 3.21
//helper function
//确定运算符的优先次序
bool operator_is_precede(char a, char b)
{
 if(a=='#')
  return false;

 if(a=='*'||a=='/'||a=='%')
  return true;
 if(a=='+'||a=='-')
 {
  if(b=='*'||b=='/'||b=='%')
   return false;
  else
   return true;
 }
 if(a=='(')
 {
  if(b!='(')
   return false;
  else
   return true;
 }
 if(a==')')
 {
  if(b!=')')
   return false;
  else return true;
 }
 return false;
}

//判断一个字符是否为操作数
bool is_operator(char c)
{
 if(c=='*'||c=='('||c==')'||c=='/'||c=='+'
  ||c=='-'||c=='%')
  return true;
 return false;
}

bool transform_nibolan(char *orig,char *result)
{
 int i,j;
 i=j=0;
 char c;

 sqstack s;
 init_stack(&s);
 //push(&s,(int)'#');

 while(orig!='\0')
 {
  if(!is_operator(orig))
   result[j++]=orig[i++];
  
  else
  {
   if(orig=='(')
    push (&s,(char)orig[i++]);
   else if(orig==')')
   {
    if(pop(&s,(int *)&c))
    {
     while(c!='(')
     {
      result[j++]=c;
      if(!pop(&s,(int *)&c))
       goto error;
     }
     i++;
    }
    else
     goto error;
   }
   else
   {
    while(get_stack_top(&s,(int*)&c)&&operator_is_precede(c,orig))
    {
     pop(&s,(int*)&c);
     result[j++]=c;
    }
   // if(c!='#')
     push(&s,(int)orig[i++]);
   }
  }
 }
 while(!stack_empty(&s))
 {
  pop(&s,(int*)&c);
  result[j++]=c;
 }
 result[j]='\0';
 destroy_stack(&s);
 return true;
error:
 destroy_stack(&s);
 return false;
}