汉扬编程 编程大纲 (c语言编程判断是否为闰年)判断圆括号是否配对用C语言如何实现

(c语言编程判断是否为闰年)判断圆括号是否配对用C语言如何实现

  status check()

{

inttStack(s);//构造空栈

push(s,\’#\’);//表示括号串开始

ch=getchar();//读取括号串中的一个字符

bool=1;//当bool为1是,则检验正确,为0是,则检验出错

whjile(ch!=\’&& bool)

{

if(ch==\'(\’)

push(s,ch);//如果遇左括号,则左括号进栈

if(ch==\’)\’)

if(gettop(s,e)==\’#\’)//取栈顶元素与\”#\”比较

bool=0;//无左括号配对,令bool为0

else pop(s,e);//有左括号配对,则消解左括号

ch =getchar();

}

if(gettop(s,e)!=\’#\’)//取栈顶元素与#比较

bool=0;//左括号多于右括号,令bool为0

if(bool)//为1打印正确

printf(\”right\”);

else

printf(\”error\”);//为0打印错误

}

自己去调试一下。
  

   栈的定义

栈(Stack)又称堆栈,它是一种运算受限的线性表,其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶,栈顶的第一个元素被称为栈顶元素,相对地,把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈,它是把该元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称为出栈或退栈,它是把栈顶元素删除掉,使其下面的相邻元素成为新的栈顶元素。
  

在日常生活中,有许多类似栈的例子,如刷洗盘子时,依次把每个洗净的盘子放到洗好的盘子上,相当于进栈;取用盘子时,从一摞盘子上一个接一个地向下拿,相当于出栈。又如向枪支弹夹里装子弹时,子弹被一个接一个地压入,则为进栈;射击时子弹总是从顶部一个接一个地被射出,此为子弹出栈。
  

由于栈的插入和删除运算仅在栈顶一端进行,后进栈的元素必定先出栈,所以又把栈称为后进先出表(Last In First Out, 简称LIFO)。

例如,假定一个栈S为(a,b,c),其中字符c的一端为栈顶,字符c为栈顶元素。
  若向S压入一个元素d,则S变为(a,b,c,d),此时字符d为栈顶元素;若接着从栈S中依次删除两个元素,则首先删除的是元素d,接着删除的使元素c,栈S变为(a,b),栈顶元素为b。

2。 栈的存储结构

栈既然是一种线性表,所以线性表的顺序存储和链接存储结构同样适用于栈。
  

(1) 栈的顺序存储结构

栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现,利用数组来顺序存储栈中的所有元素,利用整型变量来存储栈顶元素的下标位置。假定栈数组用 stack[StackMaxSize]表示,指示栈顶位置的整型变量用top表示,则元素类型为ElemType的栈的顺序存储类型可定义为:

ElemType stack[StackMaxSize];

int top;

其中,StackMaxSize为一个整型全局常量,需事先通过const语句定义,由它确定顺序栈(即顺序存储的栈)的最大深度,又称为长度,即栈最多能够存储的元素个数;由于top用来指示栈顶元素的位置,所以把它称为栈顶指针。
  

栈的顺序存储结构同样可以定义在一个记录类型中,假定该记录类型用Stack表示,则定义为:

struct Stack {

ElemType stack[StackMaxSize];

int top;

};

在顺序存储的栈中,top的值为-1表示栈空,每次向栈中压入一个元素时,首先使top增1,用以指示新的栈顶位置,然后再把元素赋值到这个位置上,每次从栈中弹出一个元素时,首先取出栈顶元素,然后使top减1,指示前一个元素成为新的栈顶元素。
  由此可知,对顺序栈的插入和删除运算相当于是在顺序表(即顺序存储的线性表)的表尾进行的,其时间复杂度为O(1)。

设一个栈S为(a,b,c,d,e),对应的顺序存储结构如图4-1(a)所示。若向S中插入一个元素f,则对应如图4-1(b)所示。
  若接着执行两次出栈操作后,则栈S对应如图4-1(c)所示。若依次使栈S中的所有元素出栈,则s变为空,如图4-1(d)所示。在图4-1中栈是垂直画出的,并且使下标编号向上递增,这样可以形象地表示出栈顶在上,栈底在下。

图4-1 栈的顺序存储结构及操作过程

在一个顺序栈中,若top已经指向了StackMaxSize-1的位置,则表示栈满,若top的值已经等于-1,则表示栈空。
  向一个满栈插入元素和从一个空栈删除元素都是不允许的,应该停止程序运行或进行特别处理。

(2) 栈的链接存储结构

栈的链接存储结构与线性表的链接存储结构相同,是通过由结点构成的单链表实现的,此时表头指针被称为栈顶指针,由栈顶指针指向的表头结点被称为栈顶结点,整个单链表被称为链栈,即链接存储的栈。
  当向一个链栈插入元素时,是把该元素插入到栈顶,即使该元素结点的指针域指向原来的栈顶结点,而栈顶指针则修改为指向该元素结点,使该结点成为新的栈顶结点。当从一个链栈中删除元素时,是把栈顶元素结点删除掉,即取出栈顶元素后,使栈顶指针指向原栈顶结点的后继结点。
  由此可知,对链栈的插入和删除操作是在单链表的表头进行的,其时间复杂度为O(1)。

设一个栈为(a,b,c),当采用链接存储时,对应的存储结构示意图如图4-2(a)所示,其中HS表示栈顶指针,其值为存储元素c结点的地址。当向这个栈插入一个元素d后,对应如图4-2(b)所示。
  当从这个栈依次删除两个元素后,对应如图4-2(c)所示。当链栈中的所有元素全部出栈后,栈顶指针HS 的值为空,即常量NULL所表示的数值0。

图4-2 栈的链接存储结构及操作过程

3。 栈的抽象数据类型

栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈,它可以采用任一种存储结构实现;操作部分包括元素进栈、出栈、读取栈顶元素、检查栈是否为空等。
  下面给出栈的抽象数据类型的具体定义。

ADT STACK is

Data:

采用顺序或链接方式存储的栈,假定其存储类型用StackType

标识符表示。
  

Operation:

void InitStack(StackType& S);

// 初始化栈S,即把它置为空

void ClearStack(StackType& S);

// 清除栈S中的所有元素,使之成为一个空栈

int StackEmpty(StackType& S);

// 判断S是否为空,若是则返回1,否则返回0

ElemType Peek(StackType& S)

// 返回S的栈顶元素,但不移动栈顶指针

void Push(StackType& S, const ElemType& item)

// 元素item进栈,即插入到栈顶

ElemType Pop(StackType& S)

// 删除栈顶元素并返回之

int StackFull(Stack& S)

// 若栈已满则返回1,否则返回0,此函数为顺

// 序存储的栈所特有

end STACK

对于判断栈是否为空和返回栈顶元素的两种操作,由于它们不改变栈的状态,所以可在参数类型说明前使用常量定义符const。
  

假定栈a的元素类型为int,下面给出调用上述栈操作的一些例子。

(1) InitStack(a); // 把栈a置空

(2) Push(a,35); // 元素35进栈

(3) int x=48; Push(a,x); // 48进栈

(4) Push(a,x/2); // x除以2的值24进栈

(5) x=Pop(a); // 栈顶元素24退栈并赋给x

(6) x=Peek(a); // 读取栈顶元素48并赋给x

(7) Pop(a); // 栈顶元素48退栈

(8) StackEmpty(a); // 因栈非空,应返回0

(9) coutnext;

delete cp;

cp=np;

}

HS=NULL; // 置链栈为空

}

(3) 检查链栈是否为空

int StackEmpty(LNode* HS)

// HS为值参或引用形参均可

{

return HS==NULL;

}

(4) 读取栈顶元素

ElemType Peek(LNode* HS) // HS为值参或引用形参均可

{

if(HS==NULL) {

cerrdata;

}

(5) 向链栈中插入一个元素

void Push(LNode*& HS, const ElemType& item)

{

// 为插入元素获取动态结点

LNode* newptr= new LNode;

if(newptr==NULL) {

cerrdata=item;

// 向栈顶插入新结点

newptr->next=HS;

HS=newptr;

}

(6) 从链栈中删除一个元素

ElemType Pop(LNode*& HS)

{

if(HS==NULL) {

cerrnext; // 使栈顶指针指向其后继结点

ElemType temp=p->data; // 暂存原栈顶元素

delete p; // 回收原栈顶结点

return temp; // 返回原栈顶元素

}

5。
   栈的简单应用举例

例1。 从键盘上输入一批整数,然后按照相反的次序打印出来。

根据题意可知,后输入的整数将先被打印出来,这正好符合栈的后进先出的特点。所以此题很容易用栈来解决。参考程序如下:

#include

#include

const int StackMaxSize=30;

typedef int ElemType; // 定义元素类型为整型

struct Stack {

ElemType stack[StackMaxSize];

int top;

};

#include\”stack。
  h\”

// 假定对顺序栈操作的算法已经存于\”stack。
  h\”头文件中

void main()

{

Stack a;

InitStack(a);

int x;

cin>>x;

while(x!=-1) {

// 假定用-1作为终止键盘输入的标志,输入的整数个数

// 不能超过StackMaxSize所规定的值

Push(a,x);

cin>>x;

}

while(!StackEmpty(a)) // 栈不为空时依次退栈打印出来

cout>ch) // 顺序扫描文件中的每一个字符

{

if(ch==39) { // 单引号内的字符不参与配对比较

while(ifstr>>ch)

if(ch==39) // 39为单引号的ASCII值

break;

if(!ifstr)

return 0;

}

else if(ch==34) { // 双引号内的字符不参与配对比较

while(ifstr>>ch)

if(ch==34) // 34为双引号的ASCII值

break;

if(!ifstr)

return 0;

}

switch (ch)

{

case \'{\’:

case \'[\’:

case \'(\’:

Push(a,ch); // 出现以上三种左括号则进栈

break;

case \’}\’:

if(Peek(a)==\'{\’)

Pop(a); // 栈顶的左花括号出栈

else

return 0;

break;

case \’]\’:

if(Peek(a)==\'[\’)

Pop(a); // 栈顶的左中括号出栈

else

return 0;

break;

case \’)\’:

if(Peek(a)==\'(\’)

Pop(a); // 栈顶的左圆括号出栈

else

return 0;

}

}

if(StackEmpty(a))

return 1;

else

return 0;

}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/7085.html

程序员专属推荐:8 个超级好用的的代码编辑器!附下载地址链接

(韩语初学者基础知识)「高分收藏」初学者必看的C语言基础知识体系

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部