Question

帮改一下栈数据结构题！谢谢！

请麻烦帮以下程序改一下错误！
帮写一下C语言连接存储栈的数据结构！谢谢！麻烦您运行成功后在发布！

Answer 1

楼上的#include<iostream.h>是C＋＋吧？

这是我修改严蔚敏书后把栈模块化的，你用dev-cpp（可以去天空软件站下载）编译一下可以：
//预定义常量和类型，本头文件应该首先包括到主函数中

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef int SqStackElemType;//栈元素类型定义
#define SqStackformat "%d "

//栈的顺序存储定义
//SqStackElemType为顺序栈元素类型，由用户在主函数本文件前定义以及输出格式

#define STACK_INIT_SIZE 100 /* 存储空间初始分配量 */
#define STACKINCREMENT 10 /* 存储空间分配增量 */
typedef struct SqStack
{
SqStackElemType *base; /* base指向表的首元素即栈底元素，在栈构造之前和销毁之后，base的值为NULL */
SqStackElemType *top; /* top指向表的末元素（即栈顶元素）的下一个位置，栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */

//顺序栈的基本操作,函数原型说明如下
//Status InitStack(SqStack *S)构造一个空栈S
//Status DestroyStack(SqStack *S)销毁栈S
//Status ClearStack(SqStack *S)把S置为空栈
//Status StackEmpty(SqStack S)若S为空栈则返回TRUE，否则返回FALSE
//int StackLength(SqStack S)返回S的元素个数即栈的长度
//Status GetTop(SqStack S,SqStackElemType *e)若栈不空则用e返回S的栈顶元素指针并返回OK；否则返回ERROR
//Status Push(SqStack *S,SqStackElemType e)插入元素e为新的栈顶元素
//Status Pop(SqStack *S,SqStackElemType *e)若栈不空则删除S的栈顶元素，用e返回其指针并返回OK；否则返回ERROR
//Status StackTraverse(SqStack S,Status(*Visit)(SqStackElemType))
//从栈底到栈顶依次对每个元素调用函数Visit(),一旦Visit()失败，则操作失败

Status InitStack(SqStack *S)
{ //构造一个空栈S,注意栈空和栈被销毁的区别：栈空，栈有存储空间；栈销毁，栈无存储空间
(*S).base=(SqStackElemType *)malloc(STACK_INIT_SIZE*sizeof(SqStackElemType));//分配存储空间，base指向基址
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;//空栈，先令top=base
(*S).stacksize=STACK_INIT_SIZE;//已分配的存储空间（注意和栈的元素个数区分）
return OK;
}

Status DestroyStack(SqStack *S)
{ /* 销毁栈S，S不再存在 */
free((*S).base);//base存储的是栈底元素的地址，把它释放即栈没有任何存储空间
(*S).base=NULL;/* 在栈构造之前和销毁之后，base的值为NULL */
(*S).top=NULL;
(*S).stacksize=0;//当前为栈分配的存储空间为0
return OK;
}

Status ClearStack(SqStack *S)
{ //把S置为空栈,即栈顶与栈底相同
(*S).top=(*S).base;
return OK;
}

Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)//栈底与栈顶相同为空栈判断条件
return TRUE;
else
return FALSE;
}

int StackLength(SqStack S)
{ /* 函数返回S的元素个数，即栈的长度 */
return S.top-S.base;//指针运算
}

Status GetTop(SqStack S,SqStackElemType *e)
{ /* 若栈不空，则用*e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top==S.base) return ERROR;
*e=*(S.top-1);
return OK;
}

Status Push(SqStack *S,SqStackElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SqStackElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SqStackElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
//这两步很关键!先使top指向原栈顶元素下一位（因为要为e找到插入位置），然后才可以使stacksize改变
}
*((*S).top)++=e;//先把e赋给*top再使top自加，如此top依然指向新栈顶元素的下一位
return OK;
}

Status Pop(SqStack *S,SqStackElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;//因为要删除栈顶元素所以top自减,然后再把*top即栈顶元素赋给*e
return OK;
}

Status StackTraverse(SqStack S,Status(*Visit)(SqStackElemType))
{ //从栈底到栈顶依次对栈中每个元素调用函数Visit()。一旦Visit()失败，则操作失败
while(S.top>S.base)
Visit(*S.base++);
printf("\n");
return OK;
}

main()
{int i;
SqStack S;
SqStackElemType e[50],ee;
for(i=0;i<50;++i)e[i]=i+1;
InitStack(&S);
for(i=0;i<50;++i)Push(&S,e[i]);
GetTop(S,&ee);
printf(SqStackformat,ee);
getch();
}

自己要用栈模块中的什么操作就看函数原型说明吧，然后在mian函数里加上就行了。

Answer 2

程序呢？

Answer 3

栈
#include<iostream.h>
#include<malloc.h>
#include<conio.h>

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status ;
typedef int ElemType;

struct STACK
{
ElemType *base;
ElemType *top;
int stacksize;
};

typedef struct STACK SqStack;
//typedef struct STACK *pSqstack;
//函数声明
Status InitStack(SqStack &S);
void DestroyStack(SqStack &S);
void ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,ElemType &e);
Status Push(SqStack &S,ElemType e);
Status Pop(SqStack &S,ElemType &e);
//初始化
Status InitStack(SqStack &S)
{
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
//销毁栈
void DestroyStack(SqStack &S)
{
free(S.base);
}
//清空栈
void ClearStack(SqStack &S)
{
S.top=S.base;
}
//判栈空
Status StackEmpty(SqStack S)
{
if(S.top==S.base) return TRUE;
else
return FALSE;
}
//求栈中元素个数
int StackLength(SqStack S)
{
int i;
ElemType *p;
i=0;
p=S.top;
while(p!=S.base)
{p--;
i++;
}
return i;
}
//获取栈顶元素值
Status GetTop(SqStack S,ElemType &e)
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
//入栈
Status Push(SqStack &S,ElemType e)
{

if(S.top - S.base>=S.stacksize)
{

S.base=(ElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize += STACKINCREMENT;
}
*(S.top++)=e;
return OK;
}
//出栈
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
//逆序打印栈中元素
void PrintElem(SqStack S)
{
ElemType e;
if(S.top==S.base) cout<<"该栈为空栈.";
else

while(S.top!=S.base)
{
Pop(S,e);cout<<e<<ends;
}
cout<<endl;
}
//进制转换函数
void conversion()
{
SqStack S;
ElemType e;
char b[17]="0123456789ABCDEF";
int n,r;
InitStack(S);
cout<<"Input a number to convert to :\n";
cin>>n;
cout<<"请输入要转换的进制：";
cin>>r;

if(n<0)
{
cout<<"\nThe number must be over 0.";
return;
}
if(!n) Push(S,0);

while(n){
Push(S,n%r);
n=n/r;
}
cout<<"the result is: ";
while(!StackEmpty(S)){
Pop(S,e);
cout<<b[e];
}
cout<<endl;
}

void main()
{
ElemType e;
SqStack Sa;

cout<<"\n\n-------------------SqStack Demo is running...----------------\n\n";
cout<<"First is Push function.\n";

InitStack(Sa);
cout<<" Now Stack is Empty.\n";
cout<<"请输入第一个要入栈的元素值：";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has one element.\n";
PrintElem(Sa);
cout<<"请输入第二个要入栈的元素值：";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has another element.\n";
PrintElem(Sa);
int n;
cout<<"请输入还要入栈的元素个数:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\n请输入第"<<i+2<<"个元素：";
cin>>e;
Push(Sa,e);
}
cout<<"\n Now Pop Stack,the top elem put into variable e.\n";
Pop(Sa,e);
cout<<e<<endl;
cout<<" Let's see the left of Stack's elem:\n";
PrintElem(Sa);
cout<<"现在栈中元素个数为："<<StackLength(Sa);
cout<<endl;
getch();
cout<<"进制转换演示：\n";
conversion();
}
------------------------------

-------------------------------
队列
#include <iostream.h>
#include <malloc.h>

typedef int QElemType;
typedef int Status;

#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0

#define MaxQsize 100 /*最大队列长度*/

typedef struct {
QElemType *base; /*初始化的动态分配存储空间*/
int front; /*头指针，若队列不空，指向队列头元素*/
int rear; /*尾指针，若队列不空，指向队列尾元素的下一个位置*/
}SqQueue;

Status InitQueue(SqQueue &Q){
/*构造一个空队列Q*/
Q.base=(QElemType *)malloc(MaxQsize*sizeof(QElemType));
if(!Q.base) return ERROR;/*存储分配失败*/
Q.front=Q.rear=0;
return OK;
}

Status QueueEmpty(SqQueue Q){
/*若队列Q为空队列，则返回TRUE，否则返回FALSE*/
if(Q.front==Q.rear) return TRUE;
else return FALSE;
}

int QueueLength(SqQueue Q){
/*返回Q的元素个数，即为队列的长度*/
return(Q.rear-Q.front+MaxQsize)% MaxQsize;
}

Status GetHead(SqQueue Q,QElemType &e){
/*若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERROR*/
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}

Status EnQueue(SqQueue &Q,QElemType e){
/*插入元素e为Q的新的队尾元素*/
if((Q.rear+1)%MaxQsize==Q.front) return ERROR;/*队列满*/
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MaxQsize;
return OK;
}

Status DeQueue(SqQueue &Q,QElemType &e){
/*若队列不空，则删除Q的队头元素，用e返回其值，并返回OK,否则返回ERROR*/
if(Q.rear==Q.front) return ERROR;/*队列空*/
e=Q.base[Q.front];
Q.front=(Q.front+1)%MaxQsize;
return OK;
}

void main(){
SqQueue Q;
int select;
QElemType e;
if (InitQueue(Q)==ERROR)
cout<<"分配失败，即将退出程序！\n";
else/*否则显示队列操作的菜单，并选择相应的基本操作*/
do {
cout<<"1：判断队列是否为空\n";
cout<<"2：测试队列的长度\n" ;
cout<<"3：取队头元素值\n";
cout<<"4：向队列中插入一新元素\n";
cout<<"5：删除队列中一元素\n";
cout<<"0：结束\n";
cout<<"\n请输入您的选择：";
cin>>select;
cout<<endl;
switch (select) {
case 1:
if (QueueEmpty(Q)==TRUE) cout<<"队列为空\n";
else cout<<"队列不为空\n";break;
case 2:
cout<<"队列长度为："<<QueueLength(Q)<<endl;break;
case 3:
if(GetHead(Q,e)==ERROR) cout<<"队列为空\n";
else cout<<"队首元素为："<<e<<endl;break;
case 4:
cout<<"请输入要插入的元素值：";
cin>>e;
if(EnQueue(Q,e)==ERROR) cout<<"\n队列满\n";
else cout<<"\n元素成功插入\n";break;
case 5:
if(DeQueue(Q,e)==ERROR) cout<<"队列空,无数据可删\n";
else cout<<"删除元素为："<<e;break;
case 0:
cout<<"操作结束\n";break;
default:
cout<<"输入选择出错！\n";
}/*switch*/
cout<<endl<<endl;
}while (select);
}/*main_end*/