栈与队列Word文档格式.docx
《栈与队列Word文档格式.docx》由会员分享，可在线阅读，更多相关《栈与队列Word文档格式.docx（21页珍藏版）》请在冰点文库上搜索。
int*top;
intstacksize;
}SqStack;
intCreateStack（SqStack&
S）/*建立顺序栈*/
intx;
S.base=（int*）malloc（MaxSize*sizeof（int））;
if（!
S.base）
exit（0）;
S.top=S.base;
S.stacksize=MaxSize;
printf（"
请输入顺序栈\n"
）;
请输入栈底元素\n"
scanf（"
%d"
&
x）;
请输入其余栈元素\n"
while（x!
=-1）
{
*S.top=x;
scanf（"
S.top++;
}
S.top--;
returnOK;
}
voidPrintStack（SqStackS）/*打印顺序栈*/
int*p;
p=S.top;
if（S.base==S.top）
printf（"
该站为空栈\n"
else
由栈顶至栈底输出该顺序栈为:
\n"
while（S.base!
=p）
{
printf（"
%5d\n"
*p）;
*p--;
}
%5d"
voidInsertStack（SqStack&
S）/*插入元素*/
inti,*p,x,a,b,n;
p=S.base;
n=S.top-S.base+1;
n++;
在堆栈中插入一个元素\n"
请输入需插入的元素距栈底的距离\n"
i）;
请输入需插入的元素\n"
if（i==n）
elseif（i<
n）
i--;
while（i）
p++;
i--;
a=*p;
*p=x;
p++;
while（p!
=S.top）
b=*p;
*p=a;
a=b;
*p=a;
else
Error!
该插入位置无效\n"
voidDeleteStack（SqStack&
S）/*删除元素*/
inti,*p,*q;
在堆栈中删除一个元素\n"
请输入需删除的元素距栈底的距离\n"
i--;
while（i）
S.top++;
q=p+1;
while（p!
*p=*q;
q++;
S.top=S.top-2;
voidmain（）
SqStacks;
CreateStack（s）;
/*建立顺序栈*/
PrintStack（s）;
InsertStack（s）;
/*插入元素*/
DeleteStack（s）;
/*删除元素*/
二）链队列题目：
初始化队列+入队列+出队列+销毁队列
（1）初始化一个链队列；
（2）在初始化好的链队列中放入数，入队列，完成后要求显示；
（3）从队列中出队列，要求显示出来的元素和之后的队列；
（4）销毁创建的队列，释放内存；
#defineOK1;
#defineERROR0;
#defineEND0;
typedefstructQNode
intdata;
structQNode*next;
}QNode,*QueuePtr;
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
intInitQuene（LinkQueue&
Q）
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
Q.front）exit（0）;
Q.front->
next=NULL;
intEnQueue（LinkQueue&
Q,inte）
if（e!
QueuePtrp;
p=（QNode*）malloc（sizeof（QNode））;
if（!
p）exit（0）;
p->
data=e;
if（Q.rear==NULL）
Q.front=Q.rear=p;
Q.rear->
next=p;
Q.rear=p;
returnOK;
elsereturnEND;
voidPrintQueue（LinkQueueQ）
QueuePtrp;
p=Q.front->
next;
while（p）
p->
data）;
p=p->
intDeQueue（LinkQueue&
Q,int&
e）
if（Q.front==Q.rear）
returnERROR;
e=p->
data;
next=p->
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
intDestroyQueue（LinkQueue&
while（Q.front）
Q.rear=Q.front->
free（Q.front）;
Q.front=Q.rear;
inte,flag=1;
LinkQueueq;
建立链队列:
InitQuene（q）;
请输入链队列元素:
while（flag）
e）;
flag=EnQueue（q,e）;
链队列为:
PrintQueue（q）;
从队列中出队列\n"
DeQueue（q,e）;
出来的元素为:
%d\n"
e）;
之后的队列为:
flag=DestroyQueue（q）;
if（flag==1）
释放链队列成功\n"
三）应用题
（1）编制程序，将输入的十进制数据M转换为八进制数据M8，将其调试通过。
在此基础上修改程序，实现十进制数据M向任意进制（2-9进制）的转换。
intInitStack（SqStack&
intPushStack（SqStack&
S,inte）
*S.top++=e;
intPopStack（SqStack&
S,int&
if（S.top==S.base）
e=*--S.top;
intEmptyStack（SqStack&
S）
voidconversion（SqStack&
S,intN,inti）
InitStack（S）;
inte;
while（N）
PushStack（S,N%i）;
N=N/i;
转换后的数为：
while（!
EmptyStack（S））
PopStack（S,e）;
intN;
inti;
请输入需转换的十进制数\n"
N）;
请输入需转向的进制数\n"
conversion（s,N,i）;
（2）编制程序，从键盘接收一个字符串（长度最长设为100），检测其中的括号（），[]，{}匹配情况，若有成对括号则在屏幕输出括号对及其所包含的字符内容。
char*base;
char*top;
S.base=（char*）malloc（MaxSize*sizeof（char））;
S,chare）
char*p;
while（S.top!
%c"
*p++;
voidMatchStack（SqStackS）
char*p,*q;
q=S.top;
=q）
if（*p=='
（'
）
SqStackM;
InitStack（M）;
PushStack（M,*p）;
while（*p!
='
）'
||p!
{
PushStack（M,*p）;
p++;
printf（"
}
if（p!
配对成功，字符串为：
PrintStack（M）;
chare;
intn=0;
InitStack（s）;
请输入一个长度小于100的字符串\n"
while（e!
\n'
PushStack（s,e）;
n++;
输入的字符串为\n"
MatchStack（s）;
（3）假设以Ｉ和Ｏ分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由Ｉ和Ｏ组成的序列，称可以操作的序列为合法序列，否则为非法序列。
编写一个算法，判断所给的序列S1：
ＩＯＯＩＩＯＩＯＯ ，S２：
ＩＯＯＩＯＩＩＯ及S３：
ＩＩＩＯＩＯＩＯ，S４：
ＩＩＩＯＯＩＯＯ是否合法。
#include<
typedefstructLNode
structLNode*next;
}LNode,*LinkList;
typedefstructLinkQueue
LNode*front;
LNode*rear;
intQueueInit（LinkQueue&
q）
q.front=（LinkList）malloc（sizeof（LNode））;
q.rear=q.front;
q.front）
q.front->
intQueueIn（LinkQueue&
q,inte）
LNode*p;
p=（LinkList）malloc（sizeof（LNode））;
p）
p->
q.rear->
q.rear=p;
intQueueOut（LinkQueue&
q,int&
if（q.front==q.rear）
p=q.front->
if（q.rear==p）
q.rear=q.front;
free（p）;
voidmain（）
LinkQueueq1,q2;
inti,j,n;
inte,e1,e2,e3;
请输入需要的杨辉三角长度:
n）;
QueueInit（q1）;
QueueInit（q2）;
for（i=1;
i<
=n;
i++）
for（j=0;
j<
=n-i;
j++）
"
e3=0;
while（q1.front!
=q1.rear）
QueueOut（q1,e1）;
e2=e3+e1;
%d"
e2）;
QueueIn（q2,e2）;
e3=e1;
if（q1.front==q1.rear）{
e2=1;
QueueIn（q2,e2）;
while（q2.front!
=q2.rear）{
QueueOut（q2,e）;
QueueIn（q1,e）;
1
11
121
1331
……
（4）二项式（a+b）n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。
升级会员 