데이터 구조 시험 - 창고 의 실현 및 응용

창고 의 실현 은 가장 기본 적 인 데이터 구조 라 고 할 수 있다.구체 적 인 실현 은 다음 과 같다.
SQSTACK. H 의 내용:

#ifndef __SQSTACK_H__
#define __SQSTACK_H__

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define INITSTACKSIZE 100
#define ADDSTACKSIZE  10

typedef char ElemType;		//        

typedef struct SQSTACK{
	ElemType *top;
	ElemType *base;
	int	size,length;
}SqStack,*SSqStack;

int  InitStack(SSqStack*);
void DestroyStack(SSqStack);
void DisplyStack(SSqStack);
int PushStack(SSqStack,ElemType);
int PopStack(SSqStack);
int EmptyStack(SSqStack);
int LengthStack(SSqStack);
ElemType TopStack(SSqStack);
int print(ElemType);

#endif

SQSTACK. C 의 내용:

#include "SqStack.h"

int InitStack(SSqStack* sstack)
{
	(*sstack)=(SSqStack)malloc(sizeof(SqStack));
	(*sstack)->base=(ElemType*)malloc(INITSTACKSIZE*sizeof(ElemType));
	(*sstack)->top=(*sstack)->base;
	(*sstack)->length=0;
	(*sstack)->size=INITSTACKSIZE;
	return (*sstack)->base!=NULL;
}
void DestroyStack(SSqStack sstack)
{
	free(sstack->base);
	free(sstack);
}
void DisplyStack(SSqStack sstack)
{
	int i=~sstack->length+1;
	while(++i)
	{
		print(*(sstack->base-i));
		printf("->");
	}
	print(*(sstack->base-i));
}
int PushStack(SSqStack sstack,ElemType elem)
{
	ElemType* _temp_sstack;
	if(sstack->length>=sstack->size)
	{
		_temp_sstack=(ElemType*)realloc(sstack->base,
			         (sstack->size+ADDSTACKSIZE)*sizeof(SqStack));
	    if(_temp_sstack==NULL) return -1;
		sstack->base=_temp_sstack;
		sstack->size+=ADDSTACKSIZE;
	}
	*sstack->top=elem;
	sstack->top++;
	sstack->length++;
	return 0;
}
ElemType TopStack(SSqStack sstack)
{
	return *(sstack->top-1);
}
int PopStack(SSqStack sstack)
{
	if(sstack->length==0) return -1;
	sstack->length--;
	sstack->top--;
	return 0;
}
int EmptyStack(SSqStack sstack)
{
	return sstack->length==0;
}
int LengthStack(SSqStack sstack)
{
	return sstack->length;
}
int print(ElemType elem)
{
	switch(sizeof(elem))
	{
		case 1: printf("%c",elem);  break;
		case 4: printf("%d",elem);  break;
		case 8: printf("%lf",elem); break;
		default: return -1;
	}
	return 0;
}

main 함수 테스트 내용:

#include "SqStack.h"

// ElemType == char      .H  
int main()
{
	SSqStack sstack;		//        
	InitStack(&sstack);		//    
	
	//       
	printf(EmptyStack(sstack)?"Empty
":"Not Empty
");

	// a,b,c,d,e    
	PushStack(sstack,'a');	
	PushStack(sstack,'b');	
	PushStack(sstack,'c');	
	PushStack(sstack,'d');	
	PushStack(sstack,'e');
	
	//       
	printf(EmptyStack(sstack)?"Empty
":"Not Empty
");

	//       
	printf("Stack length: %d
Top to Base:",LengthStack(sstack));

	//          
	DisplyStack(sstack);
	printf("
");

	//       
	while(!EmptyStack(sstack))
	{
		printf("Out Stack: %c
",TopStack(sstack));
		PopStack(sstack);
	}

	//       
	printf(EmptyStack(sstack)?"Empty
":"Not Empty
");

	//    
	DestroyStack(sstack);
	return 0;
}

이번 시험 은 스 택 의 실현, 10 진 정수 회전 2 진수, 괄호 일치 와 표현 식 계산 등 4 개의 작은 실험 을 포함 하고 있 습 니 다. 다음은 main 함수 의 쓰기 만 붙 이 고 나머지 내용 은  http://download.csdn.net/detail/decting/4724605 위 에서 아래로.
10 진 바 이 너 리:

#include "SqStack.h"

// ElemType == int      .H  
int main()
{
	int n;
	SSqStack sstack;		//        
	InitStack(&sstack);		//    
	
	//       
	printf("            (Enter for confirm):");
	scanf("%d",&n);

	//   
	do{
		PushStack(sstack,n&1);
		n>>=1;
	}while(n>0);

	//   
	printf("     :");
	while(!EmptyStack(sstack))
	{
		printf("%d",TopStack(sstack));
		PopStack(sstack);
	}
	printf("
");
	//    
	DestroyStack(sstack);
	return 0;
}

괄호 일치 (Test. c 파일 을 읽 어야 합 니 다):

#include "SqStack.h"

// ElemType == char      .H  
//            ，            C     。
int main()
{
	int flag=1;
	ElemType temp;
	SSqStack sstack;		//        
	InitStack(&sstack);		//    
	freopen("Test.c","r",stdin);
	
	while(scanf("%c",&temp)!=EOF)
	{
		switch(temp)
		{
			case '(': case '[': case '{':
			    PushStack(sstack,temp); break;
			case ')': 
				temp=TopStack(sstack);
				PopStack(sstack);
				if(temp!='(') flag=0;
				break;
			case ']': 
				temp=TopStack(sstack);
				PopStack(sstack);
				if(temp!='[') flag=0;
				break;
			case '}':
				temp=TopStack(sstack);
				PopStack(sstack);
				if(temp!='{') flag=0; break;
		}
		//printf("%c",temp);
		if(!flag) break;
	}

	printf(flag&&EmptyStack(sstack)?"Matching
":"Not Matching
");

	//    
	DestroyStack(sstack);
	return 0;
}

표현 식 계산:

#include <ctype.h>
#include <math.h>
#include <string.h>
#include "SqStack.h"
#define SRANGE 100
// ElemType == int      .H  
//        ，   
int Priority(char oper)
{
	switch(oper)
	{
		case '+':case '-': return 1;
		case '*':case '/': return 2;
		case '%':		   return 2;
		case '^':		   return 3;
	}
}
int calc(int a,int b,char operc)
{
	switch(operc)
	{
		case '+':  return a+b;
		case '-':  return a-b;
		case '*':  return a*b;
		case '/':  return a/b;
		case '%':  return a%b;
		case '^':  return (int)pow(a,b);
	}
}
int main()
{
	int  stackf,a,b;
	char operc,s[SRANGE],*p;
	SSqStack S_ope,S_num;					//        
	InitStack(&S_ope);						//       
	InitStack(&S_num);						//      

	scanf("%s",p=s,printf("           :
"));

	//    ，             ，      ，     
	while(*p||LengthStack(S_num)!=1)
	{
		if(isdigit(*p))			//    
		{
			int temp_num=0;
			while(isdigit(*p)) temp_num=temp_num*10+(*p++-'0');
			PushStack(S_num,temp_num);
		}
		else if(*p!=0)			//        ，    
		{
			switch(*p)
			{
				case '(': stackf=1; p++; break;		//stackf     
				case ')': p++; if(!stackf) goto _Calc; break;
				default: 
				
				if(!stackf&&!EmptyStack(S_ope)&&Priority(TopStack(S_ope))>=Priority(*p)) 
				{
					operc=TopStack(S_ope);	PopStack(S_ope);
					b=TopStack(S_num);	PopStack(S_num);
					a=TopStack(S_num);	PopStack(S_num);
					PushStack(S_num,calc(a,b,operc));
				}
				stackf=0;	PushStack(S_ope,*p++);
			}
			
		}
		else goto _Calc;
		if(0)
		{
			_Calc:
			{
				operc=TopStack(S_ope);	PopStack(S_ope);
				b=TopStack(S_num);	PopStack(S_num);
				a=TopStack(S_num);	PopStack(S_num);
				PushStack(S_num,calc(a,b,operc));
			}
		}
		// DisplyStack(S_num); printf("
");   //           
	}
	DisplyStack(S_num);			//      
	
	DestroyStack(S_ope);		//           
	DestroyStack(S_num);
	return 0;
}