《数据结构与算法 C语言版》—— 3.5典型例题

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第3.5节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.5典型例题

例1设有两个栈S1、S2采用顺序栈方式，并且共享一个数组A［Maxsize］，为了尽量利用空间，减少溢出的可能，采用栈顶相向、迎面增长的存储方式。设计S1、S2的有关初始化、入栈和出栈的操作算法。解两栈共享数组空间，将两栈栈底设在数组的两端，初始时，top［0］=-1，top［1］=Maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，两栈顶指针都指向栈顶元素。

#define Maxsize 100//栈空间容量 typedef struct { ElemType data［Maxsize］; int Top［2］;//指向栈顶元素 }Dstack;

初始化、入栈和出栈的操作算法如下。(1)初始化操作

void InitStack(Dstack &S){ S.Top［0］=-1;S.Top［1］=Maxsize; }

(2)进栈操作

int Push(Dstack &S,ElemType x,int i){ if(S.Top［0］+1==S.Top［1］)return 0;//栈满 switch(i){ case 0:S.Top［0］++;S.data［S.Top［0］］=x;break; case 1:S.Top［1］--;S.data［S.Top［1］］=x;break; default:return 0; } return 1; }

(3)出栈操作

int Pop(Dstack &S,ElemType &x,int i){ switch(i){ case 0:if(S.Top［0］==-1)return 0; x=S.data［S.Top［0］］;S.Top［0］--;break; case 1:if(S.Top［1］==Maxsize)return 0;x=S.data［S.Top［1］］;S.Top［1］++;break; default:return 0; } return 1; }

例2设从键盘输入一个整数序列:a1，a2，…，an。试编写一个算法实现:用栈结构存储输入的整数，当a≠－1时，进栈；当a=－1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。解算法描述如下：

#define Maxsize 100//栈空间容量 void InOutStack(int S［Maxsize］){ int i,x,n,top=0; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&x); if(x!=-1) if(top==Maxsize-1){printf("栈满\\\\n");exit(OVERFLOW);} else S［++top］=x; else if(top==0){printf("栈空\\\\n");exit(OVERFLOW);} else printf("出栈元素是%d\\\\n",S［top--］); } }

例3设结点结构为(data,next)，试用一个全局指针p和某种链接结构实现一个队列，并给出入队和出队操作的算法，要求它们的时间复杂度都是O(1)(不计new和delete时间)。解本题可采用链表结构来实现。但题目中仅给一个全局指针p，且入队和出队的时间复杂度都是O(1)，因此我们用只设尾指针的循环链表来实现，算法描述如下。(1)入队操作

void EnQueue(LinkQueue &P,ElemType x){ Qnode *s; s=new Qnode; s->data=x; s->next=P->next; P->next=s;P=s; }

(2)出队操作

void DeQueue(LinkQueue &P,ElemType &x){ Qnode *s; if(P->next==P){printf("空队列\\\\n");exit(OVERFLOW);} else{ s=P->next->next; P->next->next=s->next; x=s->data; if(P==s)P=P->next;//只有一个结点的情况 delete s ; } }

例4利用两个栈S1和S2来模拟一个队列。已知栈的三个操作如下：Push(S,x)，元素x入栈；Pop(S,x)，栈顶元素x出栈；StackEmpty(S)，判栈是否为空栈。利用栈的操作来实现该队列的三个操作：EnQueue()，插入元素入队列；DeQueue()，删除一个元素出队列；QueueEmpty()，判队列是否为空队列。解栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈S1和S2来模拟一个队列时，S1作为输入栈，逐个元素入栈，以此模拟队列元素的入队。当需要出队时，将栈S1出栈并逐个压入栈S2中，S1中最先入栈的元素，在S2中处于栈顶。S2出栈，相当于队列的出队，实现了先进先出。显然，只有S2为空且S1也为空时，才算是空队列。算法如下。(1)入队操作

int EnQueue(Stack &s1,ElemType x){//s1是容量为n的栈，栈元素类型为ElemType。入栈成功返回OK， //否则返回ERROR if(s1top==n&&!StackEmpty(s2)){//top是s1的栈顶指针，s1满s2非空，这时s1不能再入栈 printf("栈满\\\\n"); exit(OVERFLOW); } if(s1top==n&&StackEmpty(s2))//若s2空，先将s1出栈，元素压入栈s2 while(!StackEmpty(s2)){Pop(s1,x);Push(s2,x);} Push(s1,x);return(OK);//x入栈，实现了队列元素的入队 }

(2)出队操作void DeQueue(Stack s1,Stack &s2){//s2是输出栈，将s2栈顶元素出栈，实现队头元素的出队

ElemType x; if(!StackEmpty(s2)){//栈s2不空，则直接出栈 Pop(s2,x);printf("出队元素为%d\\\\n",x); } else//处理s2空栈 if(StackEmpty(s1)){//若输入栈也为空，则判定空队列 printf("队列空\\\\n"); exit(OVERFLOW); } else{//先将s1倒入s2，再进行出队操作 while(!StackEmpty(s1)){Pop(s1,x);Push(s2,x);} Pop(s2,x); //s2出栈相当于队列出队 printf("出队元素为%d\\\\n",x); } }

(3)判队列空

int QueueEmpty(){//队列空返回1，否则返回0 if(StackEmpty(s1)&&StackEmpty(s2))return 1; else return 0; } 相关资源：设计-源码