数据结构与算法分析——C语言描述(第3章 表、栈和队列②)
2022/9/11 1:24:36
本文主要是介绍数据结构与算法分析——C语言描述(第3章 表、栈和队列②),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 3.3 栈(Stack)ADT
- 3.3.1 栈模型
- 3.3.2 栈的实现
- 栈的链表实现
- 栈的数组实现
- 3.3.3 应用
3.3 栈(Stack)ADT
3.3.1 栈模型
栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈的顶(top)。对栈的基本操作又Push(进栈)和Pop(出栈),前者相当于插入,后者相当于删除最后插入的元素。
栈模型中只有栈顶元素是可访问的/可见的。
栈又叫做LIFO(Last In First Out)。
3.3.2 栈的实现
下面给出两种流行的实现方法:使用指针/使用数组
栈的链表实现
栈ADT链表实现的类型声明:
#ifndef _Stack_h struct Node; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty( Stack S ); Stack CreateStack( void ); void DisposeStack( Stack S ); void MakeEmpty( Stack S ); void Push( ElementType X, Stack S ); ElementType Top( Stack S ); void Pop( Stack S ); #endif /* _Stack_h */ /* Place in implementation file */ /* Stack implementation is a linked list with a header */ struct Node { ElementType Element; PtrToNode Next; }
具体函数实现:
/* Return true if S is empty */ int IsEmpty( Stack S ) { return S->Next == NULL; } /* Create an empty stack */ Stack CreateStack( void ) { Stack S; S = malloc( sizeof( struct Node ) ); if( S == NULL ) FatalError( "Out of space!!!" ); S->Next == NULL; MakeEmpty( S ); return S; } /* Dispose S */ void DisposeStack( Stack S ) { MakeEmpty( S ); free( S ); } /* Make S empty*/ void MakeEmpty( Stack S ) { if( S == NULL ) Error( "Must use CreateStack first" ); else while( !IsEmpty( S ) ) Pop( S ); } /* Push */ void Push( ElementType X, Stack S ) { PtrToNode TmpCell; TmpCell = malloc( sizeof( struct Node ) ); if( TmpCell == NULL) FatalError( "Out of space!!!" ); else { TmpCell->Element = X; TmpCell->Next = S->Next; S->Next = TmpCell; } } /* Return the top element */ ElementType Top( Stack S ) { if( !IsEmpty( S ) ) return S->Next->Element; Error( "Empty stack"); return 0; } /* Pop */ void Pop( Stack S ) { PtrToNode FirstCell; if( IsEmpty( S ) ) Error( "Empty stack" ); else { FirstCell = S->Next; S->Next = S->Next->Next; free( FirstCell ); } }
缺点:对malloc和free的调用的开销是昂贵的。
经常性的使用第二个栈,当一个单元从第一个栈弹出时,被推入第二个栈中,此后当第一个栈需要新的单元时,它首先去检查第二个栈。
栈的数组实现
潜在危害:需要提前声明一个数组的大小
优点:实现简单,所有ADT操作以非常快的常数时间运行。(在带有自增和自减寻址功能的寄存器上操作,整数的Push和Pop都可以写成一条机器指令)
注意:(在错误处理极其重要的场合)应该随时编写错误检测的代码防止越界。(这将导致效率大大降低,所以一般通过声明一个栈大到不至于使得操作溢出,来省去错误检测)
栈ADT数组实现的类型声明:
#ifndef _Stack_h struct StackRecord; typedef struct StackRecord *Stack; int IsEmpty( Stack S ); int IsFull( Stack S ); Stack CreateStack( int MaxElements ); void DisposeStack( Stack S ); void MakeEmpty( Stack S ); void Push( ElementType X, Stack S ); ElementType Top( Stack S ); void Pop( Stack S ); ElementType TopAndPop( Stack S ); #endif /* _Stack_h */ /* Place in implementation file */ /* Stack implementation is a dynamically allocated array */ #define EmptyTOS ( -1 ) #define MinStackSize ( 5 ) struct StackRecord { int Capacity; int TopOfStack; ElementType *Array; }
具体函数实现:
/* Return true if S is empty */ int IsEmpty( Stack S ) { return S->TopOfStack == EmptyTOS; } /* Return true if S is full */ int IsFull( Stack S ) { return S->TopOfStack == S->Capacity - 1; } /* Create an empty stack */ Stack CreateStack( int MaxElements ) { Stack S; if( MaxElements < MinStackSize ) Error( "Stack size is too small" ); S = malloc( sizeof( struct StackRecord ) ); if( S == NULL ) FatalError( "Out of space!!!" ); S->Array == malloc( sizeof( ElementType ) * MaxElements ); if( S->Array == NULL) FatalError( "Out of space!!!" ); S->Capacity = MaxElements; MakeEmpty( S ); return S; } /* Dispose S */ void DisposeStack( Stack S ) { if( S!= NULL ) { free( S->Array ); free( S ); } } /* Make S empty */ void MakeEmpty( Stack S ) { S->TopOfStack = EmptyTOS; } /* Push */ void Push( ElementType X, Stack S) { if( IsFull( S ) ) Error( "Full stack" ); else S->Array[ ++S->TopOfStack ] = X; } /* Return the top element */ ElementType Top( Stack S ) { if( !IsEmpty( S ) ) return S->Array[ S->TopOfStack ]; Error( "Empty stack "); return 0; } /* Pop */ void Pop( Stack S ) { if( IsEmpty( S ) ) Error( "Empty stack" ); else S->TopOfStack--; } /* Return the top element and Pop */ ElementType TopAndPop( Stack S ) { if( !IsEmpty( S ) ) return S->Array[ S->TopOfStack-- ]; Error( "Empty stack "); return 0; }
3.3.3 应用
- 平衡符号
- 后缀(postfix)/逆波兰(reverse Polish)表达式
- 中缀(infix)到后缀的转换
- 函数调用
尾递归(tail recursion),是使用递归极端不当的例子,尽量避免使用。
这篇关于数据结构与算法分析——C语言描述(第3章 表、栈和队列②)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享