【資料結構——堆疊篇】
目錄
- 【資料結構——堆疊篇】
- 一、堆疊的順序存盤——順序堆疊
- 1、順序堆疊的表示和實作
- 2、順序堆疊的定義
- 2、順序堆疊初始化
- 3、順序堆疊入堆疊
- 4、順序堆疊出堆疊
- 5、取順序堆疊堆疊頂元素
- 6、輸出堆疊內容
- 二、堆疊的鏈式存盤——鏈堆疊
- 1、鏈堆疊的存盤結構
- 2、堆疊鏈的初始化
- 3、鏈堆疊的入堆疊
- 4、鏈堆疊的出堆疊
- 5、取鏈堆疊堆疊頂元素
- 6、輸出鏈堆疊的內容
一、堆疊的順序存盤——順序堆疊
1、順序堆疊的表示和實作
因為堆疊底位置是固定不變的，所以可以將堆疊底位置設定在陣列的兩端的任何一個端點；堆疊頂位置是隨著進堆疊和退堆疊操作而變化的，故需要一個變數top來指示當前堆疊頂的位置，通常稱top為堆疊頂指標，
2、順序堆疊的定義
#define MAXSIZE 100
typedef struct
{
SElemType* base;//堆疊底指標
SElemType* top;//堆疊頂指標
int stacksize;//可使用的最大容量
}SqStack;
SqStack S;//定義順序堆疊
S.stacksize = s;//堆疊的大小
S.base == S.top;//空堆疊
S.top - S.base == stacksize;//滿堆疊
2、順序堆疊初始化
演算法思想：
1、分配空間并檢查空間是否分配成功，否則回傳錯誤
2、堆疊頂指標top初始化為堆疊底指標base
3、stacksize = 堆疊的最大容量
Status IniStack(SqStack& S)
{
S.base = new SElemType[MAXSIZE];//分配空間
if (!S.base) exit(OVERFLOW);//分配失敗，回傳錯誤
S.top = S.base;//堆疊頂指標初始化為堆疊底指標
S.stacksize = MAXSIZE;//初始化堆疊的最大容量
return OK;
}
3、順序堆疊入堆疊
演算法思想
1、判斷是否堆疊滿，若滿則出錯
2、新元素e壓入堆疊頂
3、堆疊頂指標+1
Status Push(SqStack& S, SElemType e)
{
if (S.top - S.base == S.stacksize)
return ERROR;//堆疊滿
*S.top = e;//新元素e壓入堆疊頂
S.top++;//堆疊頂指標+1
return OK;
}
4、順序堆疊出堆疊
演算法思想
1、判斷是否堆疊空，若空則出錯
2、堆疊頂指標-1
3、獲取堆疊頂元素e
Status Pop(SqStack& S, SElemType& e)
{
if (S.top == S.base)
return ERROR;//堆疊空報錯
--S.top;//堆疊頂指標-1
e = *S.top;//獲取堆疊頂元素e
return OK;
}
5、取順序堆疊堆疊頂元素
SElemType GetTop(SqStack S)
{
if (S.top != S.base)//堆疊非空
return *(S.top - 1);//回傳堆疊頂元素的值
//堆疊頂指標不變
}
6、輸出堆疊內容
void OutPut_SqS(SqStack S)
{
SElemType* p;
if (S.top == S.base)
printf("空堆疊！\n");
else
for (p = S.top - 1;p >= S.base;p--)
printf("%d\n", *p);
}
二、堆疊的鏈式存盤——鏈堆疊
1、鏈式存盤方式表示的堆疊稱鏈堆疊
2、運算受限的單鏈表
3、鏈表的頭指標就是堆疊頂
4、不需要頭結點
5、插入與洗掉僅在堆疊頂執行
1、鏈堆疊的存盤結構
typedef struct StackNode
{
SElemType data;
struct StackNode* next;
}StackNode,*LinkStack;
LinkStack S;
2、堆疊鏈的初始化
演算法思想：
1、不需要頭結點
2、鏈堆疊的頭指標就是堆疊頂
3、堆疊鏈無堆疊滿問題，空間可擴充
4、空堆疊相當于頭指標指向NULL
Status IniStack(LinkStack& S)
{//構造一個空堆疊，堆疊頂指標置空
S = NULL;
return OK;
}
3、鏈堆疊的入堆疊
演算法思想：
1、為入堆疊元素e分配空間，用指標p指向
2、將新結點指標域置為e
3、將新結點插入堆疊頂
4、修改堆疊頂指標為p
Status Push(LinkStack& S, SElemType e)
{
p = new StackNode;//生成新結點
p->data = e;//將新結點資料域置為e
p->next = S;//將新結點插入堆疊頂
S = p;//修改堆疊頂指標為p
return OK;
}
4、鏈堆疊的出堆疊
演算法思想：
1、判斷是否是空堆疊，若是空堆疊，回傳錯誤
2、將堆疊頂元素賦值給e
3、臨時保存堆疊頂元素的空間，以備釋放
4、修改堆疊頂指標，指向新的堆疊頂元素
5、釋放原堆疊頂元素的空間
Status Pop(LinkStack& S, SElemType& e)
{
if (S == NULL)
return ERROR;//堆疊空
e = S->data;//將堆疊頂元素存盤到e中
p = S;//用p臨時保存堆疊頂元素的空間，以備釋放
S = S->next;//修改堆疊頂指標
delete p;//釋放原堆疊頂元素的空間
return OK;
}
5、取鏈堆疊堆疊頂元素
SElemType GetTop(LinkStack S)
{
if (S != NULL)
return S->data;
}
6、輸出鏈堆疊的內容
void OutPut(LinkStack S)
{
p = S;
if (!p)
printf("空堆疊！");
else
while (p)
{
printf("%d", p->data);
p = p->next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/171733.html
標籤：其他