Question

数据结构定义一个栈并实现入栈和出栈操作的程序，是什么？

Answer 1

如下：

#include "stdio.h"
struct stackNode{
  int data;
  struct stackNode *nextPtr;
};
typedef struct stackNode LISTSTACK;
typedef LISTSTACK *STACKNODEPTR;
void push(STACKNODEPTR *,int);
int pop(STACKNODEPTR *);
int isEmpty(STACKNODEPTR);
void printStack(STACKNODEPTR);
void instruct();
int main()
{
     int item;
     int choice;
     STACKNODEPTR sPtr=NULL;
     instruct();
     printf("choose your choice\n");
     scanf("%d",&choice);
     while(choice!=3)
     {
          switch(choice)
          {
               case 1:
               printf("please input an integer!\n");
               scanf("%d",&item);
               //printf("%d\n",item);
               push(&sPtr,item);
               printStack(sPtr);
               break;
               case 2:
               if(!isEmpty(sPtr))
               {
                    printf("deleting element of top stack\n");
                    pop(&sPtr);
                    printStack(sPtr);
               }
               else{
                    printf("no element in the stack\n");
               }
               break;
               default:
                    printf("invalid input,check your input!\n");
                    break;
          }
          printf("pleace choose your choice ");
          instruct();
          scanf("%d",&choice);
     }
}
void instruct()
{
     printf("Following the instruction below:\n"
            "1:insert new elment into the stack\n"
            "2:delete the top element of the stack\n"
            "3:to end of run\n");
}
int isEmpty(STACKNODEPTR sPtr)
{
     return sPtr==NULL;
}
void printStack(STACKNODEPTR sPtr)
{
     if(sPtr==NULL)
     {
          printf("The stack is empty!\n");
     }
     else{
          printf("The elements of the stack:\n");
          while(sPtr!=NULL)
          {
               printf("%d-->",sPtr->data);
               sPtr=sPtr->nextPtr;
          }
          printf("NULL\n\n");
     }
}
void push(STACKNODEPTR *topPtr,int value)
{
     STACKNODEPTR newPtr;
     newPtr=malloc(sizeof(STACKNODEPTR));
     if(newPtr!=NULL)
     {
          newPtr->data=value;
          newPtr->nextPtr=*topPtr;
          *topPtr=newPtr;
     }
     else
     {
          printf("%d is not inserted into stack.No memory is availiable\n");
     }
}
int pop(STACKNODEPTR *topPtr)
{
     STACKNODEPTR newPtr;
     int topValue;
     newPtr=*topPtr;
     *topPtr=(*topPtr)->nextPtr;
     free(newPtr);
     topValue=(*topPtr)->data;
     printf("deleting--- %d\n",topValue);
     return topValue;
}

数据结构：

是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

常用数据结构：

数组 (Array)、栈 (Stack)、队列 (Queue)、链表 (Linked List)、树 (Tree)、图 (Graph)、堆 (Heap)、散列表 (Hash)

Answer 2

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR 0
#define OK 1;
typedef int SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

//           初始化
int InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
{
printf("!\n");
exit(ERROR);
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
printf("栈初始化完毕!\n");
return OK;
}
//       入栈（插入元素）
int Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)malloc(S.stacksize+STACKINCREMENT*sizeof(SElemType));
if(!S.base)
{
printf("存储分配失败！\n");
exit(ERROR);
}
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREMENT;
}
*S.top=e;
S.top++;
//	printf("入栈成功！\n");
return OK;
}
//       出栈（删除栈顶元素）
int Pop(SqStack &S,SElemType &e)
{
if(S.base==S.top)
{
printf("栈空！\n");
return ERROR;
}
S.top--;
e=*S.top;
printf("出栈成功！\n");
return OK;
}
//    栈顶元素
int GetTop(SqStack S,SElemType &e)
{
if(S.base==S.top)
{
printf("栈空！\n");
return ERROR;
}
e=*(S.top-1);
return OK;
}
//     判断空栈
int Empty_SqStack(SqStack S)
{
if(S.top==S.base)
printf("栈空！\n");
else
printf("栈非空！\n");
return OK;
}
//    置空
int ClearStack(SqStack &S)
{
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
printf("置空！\n");
return OK;
}
int main()
{
SqStack Ss;
SElemType e;
InitStack(Ss);
Empty_SqStack(Ss);
printf("Input S_elem:(0结束)\n");
scanf("%d",&e);
while(e!=0)
{
Push(Ss,e);
printf("Input S_elem:(0结束)\n");
scanf("%d",&e);
}
Empty_SqStack(Ss);
//	ClearStack(Ss);
//	Empty_SqStack(Ss);
while(Ss.base!=Ss.top)
{
GetTop(Ss,e);
printf("e=%d\n",e);
Pop(Ss,e);
}
Empty_SqStack(Ss);
return 0;
}