数据结构顺序表和有理数结构类型括号匹配双向栈
顺序表
Status ListInsert_Va(SqList &V,int i, ElemType x){
//在顺序表Va
if(i<1||i>V.length+1) return ERROR; //插入位置不合法
if(V.length>=V.listsize){ //表满,增加存储容量
ElemType*newbase=(ElemType *)
realloc(V.elem,(V.listsize+LISTINCREMENT)*sizeof(ElemType))
if(!newbase)exit(OVERFLOW);
V.elem=newbase; V.listsize+=LISTINCREMENT;
}
while(i>=0&&x<=V.elem[i-1])
i--;
for(p=&(V.elem[V.length-1]);p>=&(V.elem[i-1]);--p) //插入位置后的元素右移
*(p+1)=*p;
V.elem[i]=x;
++V.length;
return OK;
}//ListInsert_Va
有理数
#include
#include
#include
//函数结果状态代码
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;
//--采用动态分配的“顺序”存储结构--
typedef int ElemType;
typedef ElemType * Rational;
Status InitRational(Rational &Q,ElemType v1, ElemType v2){
//构造有理数Q,分子分母分别为v1,v2,若v2=0则Q赋空,返回Error
if(v2==0){Q=NULL;return ERROR;} /*return后括号可有可无*/
Q=(ElemType *)malloc(2*sizeof(ElemType)); //莫忘malloc.h
if(!Q)exit(OVERFLOW);//分配存储空间失败, 结束进程,exit与stdlib.h
Q[0]=v1;Q[1]=v2; /*之前的else可省略,若不省略最好加花括号*/
return(OK);
}
Status GetNumerator( Rational Q, ElemType &e)
//用e返回有理数Q的分子
{
if(Q==NULL) return ERROR;
else{
e=Q[0];return OK;
}
}
int gcd(int m,int n){ //求整数m与n的最大公约数,其中n不为0
int r;
if(m<0)m=-m; if(n<0)n=-n; //取绝对值
r=m%n; //辗转相除法:除数变被除数,余数变除数,商为0停
while(r!=0){m=n; n=r; r=m%n;}
return n;
}
Status RationalAdd (Rational Q1, Rational Q2,Rational &Q){
//用Q返回有理数Q1和Q2的和
int temp;
if(Q1!=NULL&&Q2!=NULL){
Q=(ElemType *)malloc(2*sizeof(ElemType));
if(!Q)exit(OVERFLOW);
Q[1]=Q1[1]*Q2[1]; Q[0]=Q1[0]*Q2[1]+Q2[0]*Q1[1];
temp=gcd(Q[0],Q[1]);
Q[0]=Q[0]/temp;Q[1]=Q[1]/temp;
return OK;
}
else return (ERROR);
}
Status RationalPrint(Rational Q){
//以分数形式输出有理数Q
if(Q==NULL)return ERROR;
printf(" %d/%d ",Q[0],Q[1]);
return OK;
}
void main(){
Rational Q1,Q2,Q;
InitRational(Q1,2,3);
InitRational(Q2,3,4);
RationalAdd(Q1,Q2,Q);
RationalPrint(Q);
}
括号匹配
#include
#include
#include
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType;//栈元素类型
typedef SElemType Status; typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈容量
}SqStack;
Status InitStack(SqStack &S){//构造空栈S
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW); //存储分配失败
S.top=S.base; //空栈
S.stacksize=STACK_INIT_SIZE;
return(OK);
}//InitStack
Status Push(SqStack &S, SElemType e){
//插入e为栈顶元素
if(S.top-S.base==S.stacksize){//栈满则应重新分配空间
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=(S.base+S.stacksize);//使得S.top重新指向栈顶,因realloc
S.stacksize+=STACKINCREMENT;
}
*S.top++=e; //top指向待插入位置
return(OK);
}//Push
Status Pop(SqStack &S,SElemType &e){
//若栈不空则栈顶元素出栈并用e带回其值
if(S.top==S.base)return ERROR;
e=*(--S.top); //栈顶元素为*(S.top-1)
return OK;
}
Status StackEmpty(SqStack S) {
if(S.top==S.base)return TRUE;else return FALSE;
}
Status match(char *str)
{
char ch;
SqStack S;
int hasErr=0;
InitStack(S);
while((ch=getchar())!='\n'&&hasErr==0){
switch(ch){
case '(':
Push(S,ch); break;
case '[':
Push(S,ch); break;
case '{':
Push(S,ch); break;
case ']':
if(StackEmpty(S))
{
hasErr=1;break;
}
else
{
Pop(S,ch);
if(ch!='['){hasErr=1;break;}
}
case ')':
if(StackEmpty(S))
{
hasErr=1;break;
}
else
{
Pop(S,ch);
if(ch!='('){hasErr=1;break;}
}
case '}':
if(StackEmpty(S))
{
hasErr=1;break;
}
else
{
Pop(S,ch);
if(ch!='{'){hasErr=1;break;}
}
}
}
if(hasErr==0&&StackEmpty(S)){
printf("匹配正确");
return TRUE;
}
else{
printf("匹配不正确");
return FALSE;
}
//return OK;
}
int main()
{
// SqStack S;
char *str;
scanf("%s",&str);
match(str);
}
双向站
#include #include #include #define OK 1
#define ERROR -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int SElemType;//栈元素类型
typedef SElemType Status; typedef struct{
SElemType *base[2]; //栈底指针
SElemType *top[2]; //栈顶指针
int stacksize; //栈容量
}BDStack;
Statwus InitStack(BDStack &tws,int m){//构造空栈twS
tws.base[0]=(SElemType*)malloc(m*sizeof(SElemType));
if(!tws.base[0])exit(OVERFLOW); //存储分配失败
tws.base[1]=tws.base[0]+m; //空栈
tws.top[0]=tws.base[0];
tws.top[1]=tws.base[1];
//S.stacksize=STACK_INIT_SIZE;
return(OK);
}//InitStack
Status Push(BDStack &tws,int i, SElemType e){
//插入e为栈顶元素
if(tws.top[0]+tws.top[1]==m)exit(OVERFLOW);
if(i==0){
//S.stacksize+=STACKINCREMENT;
*tes.top[0]++=e; //top指向待插入位置
return(OK);
}
if(i==1){
tws.top[1]++=e;
return OK;}
}//Push
Status Pop(SqStack &tws,int i,SElemType &e){
//若栈不空则栈顶元素出栈并用e带回其值
if(i==0){
if(tws.top[0]==tws.base[0])return ERROR;
e=*(++tws.top[0]); //栈顶元素为*(S.top-1)
return OK;
else
return ERROR;
}
if(i==1){
if(tws.top[1]=tws.base[1])return ERROR;
e=*(--tws.top[0]);
return OK;
else
return ERROR; }
return OK; }
本文档为【数据结构顺序表和有理数结构类型括号匹配双向栈】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。