第一关

本关任务:编写程序实现双向栈。 假定以顺序存储结构实现一个双向栈,即在一个一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。试编写实现着个双向栈的3个函数: 初始化栈inistack、入栈push和出栈pop

双向栈的物理结构示意图如下:

相应地,根据该示意图定义其数据类型:
#define N 100
typedef struct TWSTACK { ElemType elem[N]; int top1,top2; } TWSTACK;

//在下面的begin和end间填写相应代码
void inistack(TWSTACK &S)
//该函数实现初始化S,得到2个空栈。根据双向栈的示意图,理解初始化要求。
{
/***************begin***************/
    for(int i=0;i<N;i++){
        S.elem[i]=0;//每个元素置0
    }
    S.top1=0;
    S.top2=N-1;//初始化指针
/*************** end ***************/
}
int push(TWSTACK &S,int i,ElemType e)
//i取值1或2,分别对应左或右栈,将元素e压入S的对应栈。成功入栈返回1,否则返回0
{
/***************begin***************/
    if(i==1){
        if(S.top1>S.top2) return 0;
        S.elem[S.top1++]=e;
        return 1;
    }
    else{
        if(S.top1>S.top2) return 0;
        S.elem[S.top2--]=e;
        return 1;
    }
    /*************** end ***************/
}

int pop(TWSTACK &S,int i, ElemType &e)
//i取值1或2,分别对应左或右栈,将S对应栈的栈顶元素出栈,赋值给e。成功出栈返回1,否则返回0
{
/***************begin***************/
    if(i==1){
        if(S.top1==0) return 0;
        e=S.elem[--S.top1];
        return 1;
    }
    else{
        if(S.top2==N-1) return 0;
        e=S.elem[++S.top2];
        return 1;
    }

/*************** end ***************/
}
注意根据栈指针的特性规定前缀还是后缀

第二关

本关任务:编写程序实现循环队列。 假定以循环队列定义为:以域变量front和length分别指示循环队列中的队首元素的位置和内含元素的个数。试编写实现循环队列3个函数: 初始化队列iniQueue、入队enQueue和出队deQueue

为了完成本关任务,你需要掌握:1.队列,2.循环队列。 循环队列数据类型: #define MAXLENGTH 100
typedef struct QUEUE { ElemType elem[MAXLENGTH];
int front,length;
} QUEUE;

//在下面的begin和end间填写相应代码
void iniQueue(QUEUE &Q)
//该函数实现初始化Q
{
/***************begin***************/
    for(int i=0;i<MAXLENGTH;i++){
        Q.elem[i]=0;
    }
    Q.front=0;
    Q.length=0;
/*************** end ***************/
}
int enQueue(QUEUE &Q,ElemType e)
//将元素e入队Q。成功入栈返回1,否则返回0
{
/***************begin***************/
    if(Q.length==MAXLENGTH) return 0;
    Q.elem[(Q.front+Q.length)%MAXLENGTH]=e;
    Q.length++;
/*************** end ***************/
}
int deQueue(QUEUE &Q, ElemType &e)
//将Q队首元素出队,赋值给e。成功出队返回1,否则返回0
{
/***************begin***************/
    if(!Q.length) return 0;
    e=Q.elem[Q.front];
    Q.front=(Q.front+1)%MAXLENGTH;
    Q.length--;
/*************** end ***************/
}
注意循环链表的移动规则
判定双向链表为满的规则?

第三关

本关任务:假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’ 是回文,‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为 结束符的字符序列是否是“回文”。

int isPalindrome(char *str)
//判断字符串str是否回文,是则返回1,否则返回0
{
/**********begin**********/
    char x,y;
    TWSTACK S;
    QUEUE Q;
    iniQueue(Q);
    inistack(S);
    while(*str!='@'){
        push(S,1,*str);
        enQueue(Q,*str);
        str++;
    }
    while(S.top1){
        pop(S,1,x);
        deQueue(Q,y);
        if(x!=y) return 0;
    }
    return 1;
/********** end **********/
}

这就是,把字符串分别放进栈和队列里,根据栈和队列的出入特性来判断,队列或者栈空了那就是结束了

最后修改日期:2020年11月2日