【資料結構不挂科】最全資料結構資料——線性表
文章目錄
- 【資料結構不挂科】最全資料結構資料——線性表
-
- 前言
- 棧
-
-
- 1.棧的定義
- 2.棧的順序結構
- 3.順序棧上實作的基本運算
- 4.鍊棧上實作的基本運算
-
前言
好久不見,本期是資料結構不挂科系列的第二期——棧和隊列。
棧
1.棧的定義
棧是限定僅在表尾進行插入或删除操作的線性表。是以,對棧來說,表尾端有其特殊含義,稱為棧頂,相應的,表頭端稱為棧底。棧的特點是後進先出,即最後被壓入棧的元素會第一個被彈出。
- 棧(Stack)是限制在表的一端進行插入和删除運算的線性表
- 插入、删除的一端稱為棧頂(Top),另一端為棧底(Bottom), 當表中沒有元素時稱為空棧。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiNx8FesU2cfdGLwczX0xiRGZkRGZ0Xy9GbvNGLwIzXlpXazxCRtIWNZNkY1UnVzIVQClGVF5UMR9Fd4VGdsATNfd3bkFGazxSUhxGatJGbwhFT1Y0Mk9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLhRmMlFTZmlzMkRTZmZTY5cDZmRzNjZGZxATOzcjN0M2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
棧又稱為後進先出(Last In First Out)的線性表,簡稱LIFO結構
2.棧的順序結構
#define STACK_INIT_SIZE 100; //初始配置設定量
#define STACKINCREMENT 10; //配置設定增量
typedef struct {
ElemType *base; //棧底指針base
ElemType *top; //棧頂指針top
int stacksize; //已配置設定存儲空間,以元素為機關
} SqStack;
SqStack S; //定義棧S
說明:
1)base稱為棧底指針,始終指向棧底;當base = NULL時,表明棧結構不存在。
2)top稱為棧頂指針,棧空時:top=base;棧非空時:指向棧頂元素的下一個位置;插入一個棧頂元素,指針top增1;删除一個棧頂元素,指針top減1。
3) stacksize :目前棧可使用的記憶體容量,(以sizeof(ElemType)為機關)。
3.順序棧上實作的基本運算
- 初始化
Status InitStack( SqStack &S )
{
S.base =new SElemType[MAXSIZE];
if( !S.base ) return OVERFLOW;
S.top = S.base;
S.stackSize = MAXSIZE;
return OK;
}
- 判斷順序棧是否為空
bool StackEmpty( SqStack S )
{
if(S.top == S.base) return true;
else return false;
}
- 求順序棧的長度
int StackLength( SqStack S )
{
return S.top – S.base;
}
- 清空順序棧
Status ClearStack( SqStack S )
{
if( S.base ) S.top = S.base;
return OK;
}
- 銷毀順序棧
Status DestroyStack( SqStack &S )
{
if( S.base )
{
delete S.base ;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}
- 順序棧進棧
Status Push( SqStack &S, SElemType e)
{
if( S.top - S.base== S.stacksize ) // 棧滿
return ERROR;
*S.top++=e;
return OK;
}
/*
(1)判斷是否棧滿,若滿則出錯
(2)元素e壓入棧頂
(3)棧頂指針加1
*/
- 順序棧出棧
Status Pop( SqStack &S, SElemType &e)
{
if( S.top == S.base ) // 棧空
return ERROR;
e= *--S.top;
return OK;
}
/*(1)判斷是否棧空,若空則出錯
(2)擷取棧頂元素e
(3)棧頂指針減1
*/
- 取順序棧棧頂元素
Status GetTop( SqStack S, SElemType &e)
{
if( S.top == S.base ) return ERROR; // 棧空
e = *( S.top – 1 );
return OK;
}
/*判斷是否空棧,若空則傳回錯誤
否則通過棧頂指針擷取棧頂元素
*/
- 棧的鍊式結構
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;
LinkStack S;
4.鍊棧上實作的基本運算
- 鍊棧的初始化
void InitStack(LinkStack &S )
{
S=NULL;
}
- 判斷鍊棧是否為空
Status StackEmpty(LinkStack S)
{
if (S==NULL) return TRUE;
else return FALSE;
}
- 鍊棧進棧
Status Push(LinkStack &S , SElemType e)
{
p=new StackNode; //生成新結點p
if (!p) exit(OVERFLOW);
p->data=e;
p->next=S; S=p;
return OK;
}
- 鍊棧出棧
Status Pop (LinkStack &S,SElemType &e)
{if (S==NULL) return ERROR;
e = S-> data; p = S; S = S-> next;
delete p; return OK; }
- 取鍊棧棧頂元素
SElemType GetTop(LinkStack S)
{
if (S==NULL)
exit(1);
else
return S–>data;
}