栈和队列.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流栈和队列.精品文档.第三章 栈和队列1何为栈和队列？简述两者的区别和联系。栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。队列：队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头(front)。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。因此，队列也被称为“先进先出”表。区别和联系：从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。 栈只允许在表的一端进行插入或删除操作， 队列只允许在表的一端进行插入操作、而在另一端进行删除操作。 因而，栈和队列也可以被称作为操作受限的线性表。 2若依次读入数据元素序列a,b,c,d进栈，进栈过程中允许出栈,试写出各种可能的出栈元素序列。可能的出栈序列：a,b,c,d b,c,d,a b,a,c,d a,b,d,c a,d,c,b a,c,b,d a,c,d,b b,d,c,a b,a,d,c c,d,b,a c,b,d,a c,b,a,d d,c,b,a 等3试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。Status Model()  /识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列  /序列1和序列2中不包含字符&，序列1是序列2的逆序列  InitStack(s);  c=getchar();  while (c!='&') Push(s,c); c=getchar();  c=getchar();  while (c!=''&&!StackEmpty(s)     Pop(s,x);    if (c=x) c=getchar();    else return FALSE;  if (c='' && StackEmpty(s) return TRUE;  else return FALSE;4试写一个判别表达式中开、闭括号是否配对出现的算法。Status Bracket_Test(char *str)/判别表达式中小括号是否匹配  count=0;  for(p=str;*p;p+)      if(*p='(') count+;    else if(*p=')') count-;    if (count<0) return ERROR;    if(count) return ERROR; /注意括号不匹配的两种情况  return OK;/Bracket_Test 5假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。void NiBoLan(char *str,char *new)/把中缀表达式str转换成逆波兰式new  p=str;q=new; /为方便起见,设str的两端都加上了优先级最低的特殊符号  InitStack(s); /s为运算符栈  while(*p)      if(*p是字母) *q+=*p; /直接输出    else          c=gettop(s);      if(*p优先级比c高) push(s,*p);      else              while(gettop(s)优先级不比*p低)                  pop(s,c);*(q+)=c;        /while        push(s,*p); /运算符在栈内遵循越往栈顶优先级越高的原则      /else    /else    p+;  /while/NiBoLan6假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列Q  Q=(CiLNode*)malloc(sizeof(CiLNode);  Q->next=Q;/InitCiQueue void EnCiQueue(CiQueue &Q,int x)/把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素  p=(CiLNode*)malloc(sizeof(CiLNode);  p->data=x;  p->next=Q->next; /直接把p加在Q的后面  Q->next=p;  Q=p;  /修改尾指针 Status DeCiQueue(CiQueue &Q,int x)/从循环链表表示的队列Q头部删除元素x  if(Q=Q->next) return INFEASIBLE; /队列已空  p=Q->next->next;  x=p->data;  Q->next->next=p->next;  free(p);  return OK;/DeCiQueue 7试写出函数Fibonacci数列：F1=0 (n=1)F2=1， (n=2)Fn=Fn-1+Fn-2 (n>2)的递归算法和非递归算法。/  Fibonacci序列第n项的值/  递归算法unsigned int Fib1(unsigned int n)    if (n = 1 | n = 2)        return 1;    else        return Fib(n - 1) + Fib(n - 2);/  Fibonacci序列第n项的值/  非递归算法unsigned int Fib2(unsigned int n)    unsigned int nRet, nP, nPp;    nRet = nP = nPp = 1;    if (n = 1) | (n = 2)        return nRet;    for (unsigned int i = 3; i <= n; i+)            nRet = nP + nPp;        nPp = nP;        nP = nRet;        return nRet;8假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。Status EnCyQueue(CyQueue &Q,int x)/带length域的循环队列入队算法  if(Q.length=MAXSIZE) return OVERFLOW;  Q.rear=(Q.rear+1)%MAXSIZE;  Q.baseQ.rear=x;  Q.length+;  return OK;/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/带length域的循环队列出队算法  if(Q.length=0) return INFEASIBLE;  head=(Q.rear-Q.length+1)%MAXSIZE; /详见书后注释  x=Q.basehead;  Q.length-;/DeCyQueue 9.假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0  InitStack(S);InitQueue(Q);  while(c=getchar()!='')      Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构    while(!StackEmpty(S)      Pop(S,a);DeQueue(Q,b);    if(a!=b) return ERROR;    return OK;/Palindrome_Test