棧的鏈?zhǔn)綄?shí)現(xiàn)

1、#include <conio.h>/getch();#include <windows.h>/system("cls")#include<malloc.h> / malloc()等#include<stdio.h>#include<process.h> / exit()#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; / Status

2、是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int SElemType;/ SElemType是int類型typedef int ElemType;/ ElemType是int類型struct LNodeSElemType data;LNode *next;typedef LNode *LinkStack;/ 操作結(jié)果：構(gòu)造一個(gè)空的線性表LStatus InitStack(LinkStack &L)L=(LinkStack)malloc(sizeof(LNode); / 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) if(!L) / 存儲(chǔ)分配失敗exit(OVERFLOW);L->n

3、ext=NULL; / 指針域?yàn)榭誶eturn OK;/ 初始條件：線性表L已存在/ 操作結(jié)果:依次對(duì)L的每個(gè)數(shù)據(jù)元素進(jìn)行輸出Status STraverse(LinkStack L)/對(duì)棧進(jìn)行遍歷輸出;LinkStack p=L->next;/讓指針指向頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)，頭結(jié)點(diǎn)里無內(nèi)容; printf("tt");while(p)printf("%5d",p->data);p=p->next;printf("n");return OK;/ 線性表L已存在，在L的頭部插入新的數(shù)據(jù)元素e,作為鏈表的第一個(gè)元素 Stat

4、us Push(LinkStack L,SElemType e)/在棧頂插入元素;LinkStack s;s=(LinkStack)malloc(sizeof(LNode); / 生成新結(jié)點(diǎn)s->data=e; / 給結(jié)點(diǎn)賦值s->next=L->next; / 插在棧頂L->next=s;return OK;/ 線性表L已存在，刪除L的棧頂元素，并返回其值SElemType Pop(LinkStack L)/彈出棧頂元素;system("cls");/清屏,包含于頭文件<windows.h>LinkStack p=L->next;

5、/SElemType e;printf("tt-棧頂元素-n");if(p)e=p->data;L->next=p->next;free(p);return e;elsereturn ERROR;/ 返回表頭元素的值SElemType GetTop(LinkStack L)LinkStack p=L->next;SElemType e;if(!p) / 空表return ERROR;else / 非空表e=p->data;return e;/ 從棧底到棧頂依次對(duì)棧中每個(gè)元進(jìn)行訪問。 Status StackTraverse(LinkStack

6、S)SElemType e;LinkStack temp,p=S;InitStack(temp); / 初始化temp棧printf("tt-棧元素瀏覽-n");printf("tt棧的元素依次為: n");while(p->next)e=GetTop(p);Push(temp,e);p=p->next;STraverse(temp);printf("n");printf("tt按任意鍵返回.n");getch();system("cls");return OK;/ 初始條件：線性表

7、L已存在。操作結(jié)果：銷毀線性表L Status DestroyStack(LinkStack &L)LinkStack q;while(L)q=L->next;free(L);/釋放棧;L=q;return OK;/ 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE Status StackEmpty(LinkStack L)if(L->next) / 如果頭結(jié)點(diǎn)有后繼說明棧非空，此時(shí)返回值0;return FALSE;elsereturn TRUE;int StackLength(LinkStack L) / 初始條件：線性表L已存在。操

8、作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)int i=0;LinkStack p=L->next; / p指向第一個(gè)結(jié)點(diǎn)system("cls");printf("tt-棧的長(zhǎng)度-n");while(p) / 沒到表尾i+; /用來標(biāo)記棧的長(zhǎng)度;p=p->next;return i;/返回值即為棧的長(zhǎng)度;Status ClearStack(LinkStack L) / 不改變L / 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表LinkStack p,q;p=L->next; / p指向第一個(gè)結(jié)點(diǎn)while(p) / 沒到表尾,到表位則停止操作;

9、q=p->next;free(p);p=q;L->next=NULL; / 頭結(jié)點(diǎn)指針域?yàn)榭誶eturn OK;void print(SElemType c)/打印printf("%d ",c);void main()int i;int select;/標(biāo)記變量;LinkStack s;SElemType e;InitStack(s);/創(chuàng)建一個(gè)空棧;if(!InitStack(s)printf("棧初始化失敗!");return ; /初始化失敗 提示并退出程序; elseprintf("棧已初始化成功!n");/初始化

10、成功則提示; while(1)printf("ttt棧的操作nn"); printf("ttt 1. 從棧頂插入元素 n ");printf("ttt 2. 彈出棧頂元素 n ");printf("ttt 3. 查詢棧長(zhǎng)度 n ");printf("ttt 4. 查詢棧頂元素 n ");printf("ttt 5. 是否為空棧 n ");printf("ttt 6. 瀏覽棧中的元素 n ");printf("ttt 7. 清空棧 n "

11、);printf("ttt 0. 退出程序 nn");printf("tttn"); printf("ttt您的選擇(0-7): ");scanf("%d",&select);switch(select)case 1:system("cls");printf("ttt-棧插入元素-n");printf("ttt請(qǐng)輸入要插入元素個(gè)數(shù):");scanf("%d",&i);printf("ttt請(qǐng)依次輸入要插入的元素

12、:");while(i-)scanf("%d",&e);Push(s,e);printf("ttt壓棧操作完成!n"); printf("tt按任意鍵返回."); getch();/返回主菜單; system("cls");/清屏; break; case 2: e = Pop(s); if(e) printf("ttt棧頂元素: %d 已彈出！n",e); else printf("ttt棧頂元素不存在！n"); printf("tt按任意鍵返回

13、.n"); getch();/返回主菜單,getch()包含于頭文件<conio.h> system("cls"); break; case 3: printf("ttt此時(shí)棧的長(zhǎng)度為%d n",StackLength(s); printf("tt按任意鍵返回.n"); getch(); system("cls"); break; case 4: system("cls"); printf("tt-棧頂元素-n"); e=GetTop(s); if(e)

14、 printf("ttt棧頂元素是:%d n",e); else printf("ttt棧為空n"); printf("tt按任意鍵返回.n"); getch(); system("cls"); break; case 5: system("cls"); printf("tt-判斷空棧-n"); printf("tt是否空棧？%d(1:空 0:否)n",StackEmpty(s); printf("tt按任意鍵返回.n"); getch

15、(); system("cls"); break; case 6: system("cls"); StackTraverse(s); break; case 7: system("cls"); printf("ttt-棧的清空-n"); ClearStack(s); if(!ClearStack(s) printf("tt棧清空失敗!n"); printf("tt按任意鍵返回.n"); getch(); else printf("tt棧清空成功!n"); printf("tt按任意