beibao1.cpp

数据结构典型问题

#include<iostream>
using namespace std;
//----- 栈的顺序存储表示 -----

  typedef struct {
    int  *base;   //存储空间基地址
    int  *top;     //栈顶指针
    int  stacksize;            //栈容量
  } SqStack;

  int InitStack(SqStack &S);
  int Push(SqStack &S, int e);
  int Pop(SqStack &S, int &e);
  int knapsack(int w[], int T, int n);
  int StackEmpty(SqStack S);
  void Print(SqStack &S,int w[]);

 void main(){
   int T;
   int w[6];
   int i,n=0;
   SqStack S;
   printf("T=");
   scanf("%d",&T);
   printf("Input six objects:");
   for(i=0;i<6;i++){
     scanf("%d",&w[i]);
     n++;  
   } 
   knapsack (w,T,n);
 }


 int knapsack (int w[], int T, int n)
 {    
     SqStack S;
     InitStack(S);
     int k=0;
     do{
            while (T>0 && k<n) 
           {
              if (T-w[k]>=0)  
			  { 
				  Push(S,k); 
				  T=T-w[k]; 
			  }
              k++;          
           }
           if(T==0)  { 
			 Print(S,w); 
			 return 1; 
		   }
		   if(StackEmpty(S)) {
			   printf("There is nothing in the bag\n");
		   }
		   
           else  if (!StackEmpty(S)){
			   Pop(S,k);
			   T=T+w[k]; 
			   k++; 
		   }
	 }while (!StackEmpty(S) || k<n);
     return 0;
 }

  int InitStack (SqStack &S)
{// 构造一个空栈S          
   S.base=(int *)malloc(100*sizeof(int));
  if (!S.base) exit (-2); 
   S.top = S.base;
   S.stacksize = 100;
   return 1;
}

 int Push (SqStack &S, int e) 
{  
   if (S.top - S.base >= S.stacksize) 
   {//栈满，追加存储空间
      S.base=(int*)realloc(S.base,(S.stacksize+10)*sizeof(int));
      if (!S.base) exit (-2);   //存储分配失败
      S.top=S.base+S.stacksize;
      S.stacksize+=100;    
   }
   *S.top++ = e; 
    return 1;
}

int Pop (SqStack &S, int &e) 
{
     // 若栈不空，则删除S的栈顶元素，
     // 用e返回其值，并返回1；
     // 否则返回0
    if (S.top==S.base)  return 0;
    e = *--S.top;
    return 1;
}

int StackEmpty(SqStack S)
{//判断栈是否为空
 //	是则返回1，否则返回0
	if(S.top==S.base)  
		return 1;
	else return 0;
}

void Print(SqStack &S,int w[])
{//输出符合条件的栈的内容所对应的数组的内容
   
   S.top--;
   while(S.top>=S.base){
	printf("w[%d]=%d\n",*S.top,w[*S.top]);
    S.top--;}
}