数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一个位置r为队尾元素的位置 假定队列元素的个数小于n,计算队列中元素个数的公式?
解答:对于非循环队列来说,尾指针和头指针的差值便是队列的长度,而对于循环队列,差值可能是负值 所以需要将差值加上MAXSIZE(本题是n),然后与MAXSIZE(本题是N)求余,即是(r-f+n)%n
(1)将编号为0和1的两个栈存放于一个数组空间V[m]中,栈底分别处于数组的两端 当第0号栈的栈顶指针top[0]等于-1时该栈为空;当第一号栈的栈顶指针top[1]等于m时,该栈为空。两个栈均从两端向中间增长 试编写双栈初始化,判断栈空,栈满,进栈,出栈等等算法的函数 双栈数据结构的定义如下所示
`////-----栈的数据结构定义-----
typedef struct
{
int top[2],bot[2]; ///栈顶和栈底指针
SElemtype *v; //栈数组
int m; //栈最大可容纳元素个数
}DblStack;`
`///-----双栈的初始化-----
int init()
{ S.top[0]=-1; ///第0号栈为空
S.top[1]=m; ///第一号栈为空
return 1; ///初始化成功
} `
`////------判断栈空-------
int Empty()
{ return(S.top[0]==-1&&S.top[1]==m); }`
`////-----入栈操作-----
int push(Stack &s,int i,int x)////i为栈号,i=0表示左栈,i=1表示右栈,x是入栈元素 ,入栈成功返回1,失败返回0;
{ if(i<0||i>1)
{ count<<"栈号输入不对"<<endl;
exit(0);
}
if(S.top[1]-S.top[0]==1)
{count<<"栈已经满"<<endl; return(0); }
switch(i)
{ case 0: S.v[++S.top[0]]=x; return(1); ///第零号栈入栈操作
break;
case 1:S.V[--S.top[1]]=x; } ///第一号栈入栈操作
} `
`////------出栈操作----------
ElemType pop (Stack &s,int i) ///退栈,i代表栈号 i=0表示左栈
{ if(i<0||i>1)
{ count<<"栈号输入不对"<<endl;
exit(0); }
Switch(i)
{case 0: if(S.top[0]==-1) ////判断栈是否为空能否出栈
{count<<"栈空"<<endl;return(-1); }
else
return(S.V[S.top[0]--]);
case 1: if(S.top[1]==m)
{count<<"栈空"<<endl;return(-1); }
else
return (S.V[S.top[1]++]); }
}`
回文是指正读反读均相同的字符序列,如“abba"和"abdba"均是回文 但是"good"不是回文试写一个算法判断给定的字符序列是否为回文(提示:将一半字符入栈)
`////-----回文判断------
#define StackSize 100 //假定预分配的栈空间最多为100个元素
typedef char DataType; //假定栈元素的数据类型为字符
typedef Struct
{DataType data[StackSize];
int top;
}SeqStack; ///栈数据结构的定义
int IsHuiwen (char *t)
{ //判断t字符向量是否为回文,若是返回1,不是返回0
SeqStack S;
int i,length;
char temp; ///temp存储暂时变量
initStack(&S);
length=strlength(t); ///求向量长度
for(i=0;i<length/2;i++)
push(&S,t[i]); ///将一半的字符入栈
while(!EmptyStack(&S))
{ ///每弹出一个字符与相应字符比较
temp=Pop(&S);
if(temp!=S[i])
return 0; ///不等则返回0;
else
i++;}
return 1; ///比较完毕若相等则返回1
}`
假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设头指针)以此编写相应的置空队列,判断队列是否为空 入队和出队等算法。
`////------预定义链队的结构------
typedef struct queuenode
{ Datatype data;
struct queuenode *next;
} QueueNode; //结点类型的定义
typedef struct
{ queueNode *rear; ///只设一个指向队尾元素的指针
}Linkqueue;`
`///-----置空队--------
void initQueue(LinkQueue *Q)
{ ///置空队就是让头结点成为队尾元素
QueueNode *s;
Q.rear=Q.rear->next; //将队尾指针指向头结点
while(Q.rear!=Q.rear->next) ///当队列非空将队中元素逐个出队
{ S=Q.rear->next; ///S指向队尾元素
Q.rear->next=S->next; //修改尾结点的指针域
delete S; } //回收结点空间
}`
`///----判队空-------
int EmptyQueue (LinkQueue &Q)
{ //判断队空 当头结点的next指针 指向自己时为空队
return Q.rear->next->next==Q.rear->next; }`
`///----入队操作-----
void EnQueue (LinkQueue &Q , Datatype x)
{ //入队,也就是尾结点处插入元素
QueueNode *p=new QueueNode; //申请新结点
p->data=x;
p->next=Q.rear->next; ///初始化新结点并链入
Q.rear->next=p;
Q.rear=p; //将尾指针移至新结点
}`
`////-------出队操作--------
Datatype DeQueue (LinkQueue *Q)
{ //出队,把头结点之后的元素摘下
Datatype t;
QueueNode *p; //定义下头结点
if(EmptyQueue(Q))
Error("Queue underflow");
p=Q.rear->next->next;//p指向将要摘下的结点
x=p->data; //保存结点中的数据
if(p==Q.rear)
{ //当队列中只有一个结点时,P结点出队后,要将队尾指针指向头结点
Q.rear=Q.rear->next;
Q.rear->next=p->next; }
else
Q.rear->next->next=p-next; //摘下结点p
delete p; //释放被删除结点
return x; }`
已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归算法
-
求链表的最大整数
-
求链表的结点个数
-
求所有整数的平均值
`///------求链表中的最大整数-------- int GetMax(Linklist p) { if(!p->next) return p->data; else { int max=GetMax(p->next); return p->data>=max? p->data:max; } } ` `///-----求链表的结点个数------- int Getlength(Linklist p) { if(!p->next) return 1; else { return Getlength(p->next) +1; } }` `///-----求所有整数的平均值------- double GetAverage(Linklist p,int n) { if(!p->next) return p->data; else { double ave=GetAverage(p-next,n-1); return (ave *(n-1)+p->data)/n; } }`