目錄
一、鏈棧
1、鏈棧的定義：
2、鏈棧的優(yōu)缺點(diǎn)：
二、鏈棧的基本操作算法（C語(yǔ)言）????
1、宏定義
??2、創(chuàng)建結(jié)構(gòu)體
3、鏈棧的初始化?
?4、鏈棧的進(jìn)棧
5、鏈棧的出棧
6、獲取棧頂元素
7、棧的遍歷輸出
8、鏈棧的判空
?9、求鏈棧的棧長(zhǎng)
10、鏈棧的清空
11、鏈棧的銷毀
三、鏈棧的基本操作完整代碼（C語(yǔ)言）
?四、運(yùn)行結(jié)果
一、鏈棧
1、鏈棧的定義：
鏈棧是一種棧的實(shí)現(xiàn)方式，它使用鏈表結(jié)構(gòu)來(lái)實(shí)現(xiàn)。每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和指針域，其中數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)，指針域用于指向下一個(gè)節(jié)點(diǎn)。鏈棧的棧頂指針指向棧頂元素，棧底指針指向棧底元素。
2、鏈棧的優(yōu)缺點(diǎn)：
鏈棧的優(yōu)點(diǎn)：
- 空間利用率高：鏈?？梢愿鶕?jù)實(shí)際情況動(dòng)態(tài)調(diào)整棧的大小，避免了順序?？赡艹霈F(xiàn)的內(nèi)存溢出等問(wèn)題。
- 時(shí)間復(fù)雜度低：鏈棧的入棧和出棧操作只需要改變棧頂指針的指向，時(shí)間復(fù)雜度為O(1)，不需要像順序棧一樣進(jìn)行數(shù)據(jù)的移動(dòng)，具有比較高的效率。
- 方便進(jìn)行動(dòng)態(tài)擴(kuò)展：鏈?？梢苑奖愕剡M(jìn)行動(dòng)態(tài)擴(kuò)展，當(dāng)需要增加元素時(shí)，可以動(dòng)態(tài)地增加存儲(chǔ)空間；當(dāng)需要減少元素時(shí)，可以釋放未使用的空間。
鏈棧的 缺點(diǎn)：
- 需要額外的指針存儲(chǔ)空間，因此占用的存儲(chǔ)空間較大。
- 插入和刪除操作需要修改指針，操作較為復(fù)雜。
- 無(wú)法充分利用內(nèi)存的連續(xù)性優(yōu)勢(shì)，因?yàn)殒湵砉?jié)點(diǎn)的存儲(chǔ)位置是分散的。
二、鏈棧的基本操作算法（C語(yǔ)言）????
1、宏定義
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int SElemType;
typedef int Status;??2、創(chuàng)建結(jié)構(gòu)體
//創(chuàng)建結(jié)構(gòu)體
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;3、鏈棧的初始化?
//初始化
Status InitStack(LinkStack &S) {
S = NULL;
return OK;
}?4、鏈棧的進(jìn)棧
//進(jìn)棧
Status Push(LinkStack &S, SElemType e) {//在棧頂插入元素e
StackNode *p = new StackNode; //生成新結(jié)點(diǎn)
if (!p) exit(OVERFLOW);
p->data = e;
p->next = S; //將新結(jié)點(diǎn)插入 棧頂
S = p; //修改棧頂指針為p
return OK;
}
5、鏈棧的出棧
//出棧
Status Pop(LinkStack &S, int &e) {//刪除S的棧頂元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //將棧頂元素賦給e
LinkStack p = S; //用p臨時(shí)保存棧頂元素空間，以備釋放
S = S->next; //修改棧頂指針
delete p;
return OK;
}6、獲取棧頂元素
//獲取棧頂元素
Status Top(LinkStack &S, int &e) {//刪除S的棧頂元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //將棧頂元素賦給e
return OK;
}7、棧的遍歷輸出
//棧的遍歷輸出
void StackTraverse(LinkStack S) {
LinkStack p; //使用指針p輔助訪問(wèn)棧里元素
p = S; //p初始從棧頂開(kāi)始
printf("從棧頂依次讀出該棧中的元素值為:");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}8、鏈棧的判空
//判空
Status stackEmpty(LinkStack S) {
if (S == NULL) {如果棧頂?shù)闹羔樣蛑赶蚩眨瑒t?？? return true;
} else {
return false;
}
}?9、求鏈棧的棧長(zhǎng)
//求棧長(zhǎng)
Status stackLength(LinkStack S) {
int len = 0;
while (S != NULL) {
len++;
S = S->next;
}
return len;
}10、鏈棧的清空
//清空
Status ClearStack(LinkStack &S) {
StackNode *p;
while (S != NULL) {
p = S->next;
delete S;
S = p;
}
return OK;
}11、鏈棧的銷毀
//銷毀
Status DestoryStack(LinkStack S) {
StackNode *p;
while (S) {
p = S;
S = S->next;
delete p;
}
S = NULL;
return OK;
}三、鏈棧的基本操作完整代碼（C語(yǔ)言）
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int SElemType;
typedef int Status;
//創(chuàng)建結(jié)構(gòu)體
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;
//初始化
Status InitStack(LinkStack &S) {
S = NULL;
return OK;
}
//進(jìn)棧
Status Push(LinkStack &S, SElemType e) {//在棧頂插入元素e
StackNode *p = new StackNode; //生成新結(jié)點(diǎn)
if (!p) exit(OVERFLOW);
p->data = e;
p->next = S; //將新結(jié)點(diǎn)插入 棧頂
S = p; //修改棧頂指針為p
return OK;
}
//出棧
Status Pop(LinkStack &S, int &e) {//刪除S的棧頂元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //將棧頂元素賦給e
LinkStack p = S; //用p臨時(shí)保存棧頂元素空間，以備釋放
S = S->next; //修改棧頂指針
delete p;
return OK;
}
//獲取棧頂元素
Status Top(LinkStack &S, int &e) {//刪除S的棧頂元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //將棧頂元素賦給e
return OK;
}
//獲取棧頂元素
Status GetTop(LinkStack S) {//返回S的棧頂元素，不修改棧頂指針
if (S != NULL) {
return S->data;
}
}
//棧的遍歷輸出
void StackTraverse(LinkStack S) {
LinkStack p; //使用指針p輔助訪問(wèn)棧里元素
p = S; //p初始從棧頂開(kāi)始
printf("從棧頂依次讀出該棧中的元素值為:");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//判空
Status stackEmpty(LinkStack S) {
if (S == NULL) {如果棧頂?shù)闹羔樣蛑赶蚩?，則?？? return true;
} else {
return false;
}
}
//求棧長(zhǎng)
Status stackLength(LinkStack S) {
int len = 0;
while (S != NULL) {
len++;
S = S->next;
}
return len;
}
//清空
Status ClearStack(LinkStack &S) {
StackNode *p;
while (S != NULL) {
p = S->next;
delete S;
S = p;
}
return OK;
}
//銷毀
Status DestoryStack(LinkStack S) {
StackNode *p;
while (S) {
p = S;
S = S->next;
delete p;
}
S = NULL;
return OK;
}
//功能菜單
int choice() {
printf("==================================\n");
printf(" 鏈棧操作功能菜單 \n");
printf("1、進(jìn)棧 2、出棧 3、獲取棧頂元素 \n");
printf("4、清空 5、銷毀 6、批量進(jìn)棧 \n");
printf("7、判空 8、鏈棧的長(zhǎng)度 \n");
printf("9、打印棧內(nèi)元素 10、退出程序 \n");
printf("==================================\n");
return 0;
}
int main() {
LinkStack linkstack;
//初始化
Status rInitStack = InitStack(linkstack);
if (rInitStack == OK) {
printf("鏈棧初始化成功！\n");
} else {
printf("鏈棧初始化失??！\n");
}
while (1) {
//功能菜單
choice();
int flag;
printf("請(qǐng)輸入所需的功能編號(hào)：\n");
scanf("%d", &flag);
switch (flag) {
case 1: {//進(jìn)棧
Status Pushdata;
printf("請(qǐng)輸入插入元素(請(qǐng)?jiān)谟⑽臓顟B(tài)下輸入例如:1): \n");
scanf("%d", &Pushdata);
Status rPush = Push(linkstack, Pushdata);
if (rPush == OK) {
printf("向鏈棧進(jìn)棧%d成功！\n", Pushdata);
} else {
printf("向鏈棧進(jìn)棧失??！\n");
}
}
break;
case 2: {//出棧
Status popData;
Status rPop = Pop(linkstack, popData);
if (rPop == OK) {
printf("向鏈棧出棧%d成功！\n", popData);
} else {
printf("向鏈棧出棧失??！\n");
}
}
break;
case 3: {//獲取棧頂元素
Status topData;
Status rTop = Top(linkstack, topData);
if (rTop == OK) {
printf("向鏈棧獲取棧頂元素：%d\n", topData);
} else {
printf("向鏈棧獲取棧頂元素失敗！\n");
}
// //獲取棧頂元素
// Status rGetTop = GetTop(linkstack);
// if (rGetTop == OK) {
// printf("向鏈棧獲取棧頂元素：%d\n", topData);
// } else {
// printf("向鏈棧獲取棧頂元素失??！\n");
// }
}
break;
case 4: { //清空
Status rClearStack = ClearStack(linkstack);
if (rClearStack == OK) {
printf("鏈棧清空成功！\n");
} else {
printf("鏈棧清空失??！\n");
}
}
break;
case 5: {//銷毀
Status rDestroyStack = DestoryStack(linkstack);
if (rDestroyStack == OK) {
printf("鏈棧銷毀成功！\n");
} else {
printf("鏈棧銷毀失??！\n");
}
}
break;
case 6: {//批量插入
int on;
printf("請(qǐng)輸入想要插入的元素個(gè)數(shù)：\n");
scanf("%d", &on);
SElemType array[on];
for (int i = 1; i <= on; i++) {
getchar();
printf("向順序棧第%d個(gè)位置插入元素為:", (i));
scanf("%d", &array[i]);
}
for (int i = 1; i <= on; i++) {
Status rPush = Push(linkstack, array[i]);
if (rPush == OK) {
printf("向鏈棧進(jìn)棧%d成功！\n", array[i]);
} else {
printf("向鏈棧進(jìn)棧失?。n");
}
}
}
break;
case 7: {//判空
Status rStackEmpty = stackEmpty(linkstack);
if (rStackEmpty == true) {
printf("鏈棧為空棧！\n\n");
} else
printf("鏈棧不為空！\n\n");
}
break;
case 8: {//鏈棧的長(zhǎng)度
Status length = stackLength(linkstack);
printf("鏈棧的長(zhǎng)度為：%d 。\n\n", length);
}
break;
case 9: { //打印棧內(nèi)元素
StackTraverse(linkstack);
}
break;
case 10: {//退出程序
return 0;
}
break;
default: {
printf("輸入錯(cuò)誤，無(wú)此功能，請(qǐng)檢查輸入:\n\n");
}
}
}
return 1;
}?四、運(yùn)行結(jié)果
?
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-820911.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-820911.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 鏈棧的基本操作 （C語(yǔ)言版）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
