棧的c語(yǔ)言實(shí)現(xiàn)基本操作

寫(xiě)了一個(gè)鏈?zhǔn)綏?，你看?/p>

專注于為中小企業(yè)提供網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)新和免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了1000多家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

# include stdio.h

# include malloc.h

# include stdlib.h

typedef struct Node

{

int data;

struct Node *pNext;

}NODE, *PNODE;

typedef struct Stack

{

PNODE pTop;

PNODE pBottom;//pBottem是指向棧底下一個(gè)沒(méi)有實(shí)際意義的元素

}STACK, *PSTACK;

void init( PSTACK );

void push( PSTACK, int );

void traverse( PSTACK );

int pop( PSTACK, int * );

int empty( PSTACK pS );

int main( void )

{

STACK S;//STACK等價(jià)于struct Stack

int val;

init( S );//目的是造出一個(gè)空棧

push( S, 1 );//壓棧

push( S, 2 );

push( S, 3 );

push( S, 4 );

push( S, 5 );

push( S, 6 );

push( S, 7 );

traverse( S );//遍歷輸出

// clear( S ); //清空數(shù)據(jù)

// traverse( S );//遍歷輸出

if( pop( S, val ) )

{

printf( "出棧成功,出棧的元素是%d\n", val );

}

else

{

printf( "出棧失敗" );

}

traverse( S );//遍歷輸出出棧之后的元素

return 0;

}

void init( PSTACK pS )

{

pS-pTop = ( PNODE )malloc( sizeof( NODE ) );

if( NULL == pS-pTop )

{

printf( "動(dòng)態(tài)內(nèi)存分配失敗!\n" );

exit( -1 );

}

else

{

pS-pBottom = pS-pTop;

pS-pTop-pNext = NULL;//或是pS-pBottom = NULL;

}

}

void push( PSTACK pS, int val )

{

PNODE pNew = ( PNODE )malloc( sizeof( NODE ) );

pNew-data = val;

pNew-pNext = pS-pTop;//pS-Top不能改為pS-pBottom

pS-pTop = pNew;

}

void traverse( PSTACK pS )

{

PNODE p = pS-pTop;

while( p != pS-pBottom )

{

printf( "%d ", p-data );

p = p-pNext;

}

printf( "\n" );

}

int empty( PSTACK pS )

{

if( pS-pTop == pS-pBottom )

return 1;

else

return 0;

}

//把pS所指向的棧出棧一次,并把出棧的元素存入pVal形參所指向的變量中,如果出棧失敗,則返回false,否則true

int pop( PSTACK pS, int *pVal)

{

if( empty( pS ) )//pS本身存放的就是S的地址

{

return 0;

}

else

{

PNODE r = pS-pTop;

*pVal = r-data;

pS-pTop = r-pNext;

free( r );

r = NULL; //為什么要把r賦給NULL呢??

return 1;

}

}

//clear清空

void clear( PSTACK pS )

{

if( empty( pS ) )

{

return ;

}

else

{

PNODE p = pS-pTop;

PNODE q = p-pNext;

while( p != pS-pBottom )

{

q = p-pNext;

free( p );

p = q;

}

pS-pTop = pS-pBottom;

}

}

求計(jì)算機(jī)C語(yǔ)言中“?！钡幕靖拍睿Ｍ鱾€(gè)方面都有，全一點(diǎn)。最好和教科書(shū)介紹的一樣詳細(xì)

棧，是硬件。主要作用表現(xiàn)為一種數(shù)據(jù)結(jié)構(gòu)，是只能在某一端插入和刪除的特殊線性表。它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)）。 棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為先進(jìn)后出表。 ?？梢杂脕?lái)在函數(shù)調(diào)用的時(shí)候存儲(chǔ)斷點(diǎn)，做遞歸時(shí)要用到棧！ 以上定義是在經(jīng)典計(jì)算機(jī)科學(xué)中的解釋。 在計(jì)算機(jī)系統(tǒng)中，棧則是一個(gè)具有以上屬性的動(dòng)態(tài)內(nèi)存區(qū)域。程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出。在i386機(jī)器中，棧頂由稱為esp的寄存器進(jìn)行定位。壓棧的操作使得棧頂?shù)牡刂窚p小，彈出的操作使得棧頂?shù)牡刂吩龃蟆?棧在程序的運(yùn)行中有著舉足輕重的作用。最重要的是棧保存了一個(gè)函數(shù)調(diào)用時(shí)所需要的維護(hù)信息，這常常稱之為堆棧幀或者活動(dòng)記錄。堆棧幀一般包含如下幾方面的信息： 1. 函數(shù)的返回地址和參數(shù) 2. 臨時(shí)變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其他臨時(shí)變量。

二、基本算法

1、進(jìn)棧（PUSH）算法 ①若TOP≥n時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）； ②置TOP=TOP+1（棧指針加1，指向進(jìn)棧地址）； ③S(TOP)=X，結(jié)束（X為新進(jìn)棧的元素）； 2、退棧（POP）算法 ①若TOP≤0，則給出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)； ②X=S(TOP)，（退棧后的元素賦給X）： ③TOP=TOP-1，結(jié)束（棧指針減1，指向棧頂）。

三、棧的實(shí)現(xiàn)

棧分順序棧和鏈?zhǔn)綏?，下面程序介紹了順序棧的實(shí)現(xiàn)。

#includestdio.h #includemalloc.h #define DataType int #define MAXSIZE 1024 typedef struct { DataType data[MAXSIZE]; int top; }SeqStack; SeqStack *Init_SeqStack()//棧初始化 { SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); if(!s) { printf("空間不足\n"); return NULL; } else { s-top=-1; return s; } } int Empty_SeqStack(SeqStack *s)//判?？?{ if(s-top==-1) return 1; else return 0; } int Push_SeqStack(SeqStack *s,DataType x)//入棧 { if(s-top==MAXSIZE-1) return 0;//棧滿不能入棧 else { s-top++; s-data[s-top]=x; return 1; } } int Pop_SeqStack(SeqStack *s,DataType *x)//出棧 { if(Empty_SeqStack(s)) return 0;//棧空不能出棧 else { *x=s-data[s-top]; s-top--; return 1; }//棧頂元素存入*x，返回 } DataType Top_SeqStack(SeqStack *s)//取棧頂元素 { if(Empty_SeqStack(s)) return 0;//?？?else return s-data[s-top]; } int Print_SeqStack(SeqStack *s) { int i; printf("當(dāng)前棧中的元素:\n");　 for(i=s-top;i=0;i--) printf("%3d",s-data[i]); printf("\n"); return 0; } int main() { SeqStack *L; int n,num,m; int i; L=Init_SeqStack(); printf("初始化完成\n"); printf("?？眨?d\n",Empty_SeqStack(L)); printf("請(qǐng)輸入入棧元素個(gè)數(shù):\n"); scanf("%d",n); printf("請(qǐng)輸入要入棧的%d個(gè)元素：\n",n); for(i=0;in;i++) { scanf("%d",num); Push_SeqStack(L,num); } Print_SeqStack(L); printf("棧頂元素:%d\n",Top_SeqStack(L)); printf("請(qǐng)輸入要出棧的元素個(gè)數(shù)（不能超過(guò)%d個(gè)）:\n",n); scanf("%d",n); printf("依次出棧的%d個(gè)元素:\n",n); for(i=0;in;i++) { Pop_SeqStack(L,m); printf("%3d",m); } printf("\n"); Print_SeqStack(L); printf("棧頂元素:%d\n",Top_SeqStack(L)); return 0; }

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)（用c語(yǔ)言寫(xiě)） 棧的基本操作

//順序棧

#includestdio.h

#includestdlib.h

#includemalloc.h

#define STACK_INIT_SIZE 100;

#define STACKINCREMENT 10;

typedef struct

{

int *base;

int *top;

int stacksize;

}SqStack;

typedef int ElemType;

int InitStack(SqStack S) //為棧S分配存儲(chǔ)空間，并置S為空棧

{

int size = STACK_INIT_SIZE;

S.base=(int *)malloc(size*sizeof(ElemType));

if(!S.base)

return 0;

S.top=S.base; //置棧S為空棧

S.stacksize=STACK_INIT_SIZE;

return 1;

}

int GetTop(SqStack S,int e) //若棧不空，則用e返回S的棧頂元素

{

if(S.top==S.base) return 0;

e=*(S.top-1);

return 1;

}

int Push(SqStack S, int e) /*進(jìn)棧函數(shù),將e插入棧S中,并使之成為棧頂元素*/

{ if(S.top-S.base=S.stacksize) /*棧滿，追加存儲(chǔ)空間*/

{

int stackinvrement = STACKINCREMENT;

S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType));

if(!S.base)

return 0; /*存儲(chǔ)分配失敗*/

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return 1;

}

int Pop(SqStack S,int e)/*出棧函數(shù),若棧S不空,則刪除S的棧頂元素,用e返回其值*/

{ if(S.top==S.base) return 0;

e=*--S.top;

return 1;

}

void OutputStack(SqStack S)

{int *q;

q=S.top-1;

for(int i=0;iS.top-S.base;i++)

{

printf("%3d ",*q);q--;}

}

void main()

{

int a,b,c ;

char m;

SqStack s;

InitStack(s);

printf("請(qǐng)輸入要進(jìn)棧的元素個(gè)數(shù)是:");

scanf("%d",a);

printf("\n請(qǐng)輸入要進(jìn)棧的%d個(gè)元素:",a);

for(b=0;ba;b++) {

scanf("%d",c);

Push(s,c); }

do { printf("\n");

printf("*********** 1.輸出棧的元素**********\n");

printf("*********** 2.取棧頂元素************\n");

printf("*********** 3.刪除棧頂元素**********\n");

printf("*********** 4.退出程序**********\n");

printf("\n請(qǐng)選擇一個(gè)字符:");

getchar();

scanf("%c",m);

switch(m) {

case '1': printf("\n輸出的棧為:");

OutputStack(s);

break;

case '2': GetTop(s,c);

printf("\n棧頂元素為:%d",c);

printf("\n輸出的棧為:");

OutputStack(s);

break;

case '3': Pop(s,c);

printf("\n刪除的棧頂元素:%d",c);

printf("\n輸出的棧為:");

OutputStack(s);

printf("\n");

break;

case '4':break;

default: printf("輸入的數(shù)字有錯(cuò)，請(qǐng)重新選擇!\n"); break;

}

}while(m!='4');

}

//鏈棧

#includestdio.h

#includestdlib.h

typedef struct SNode

{

int data;

struct SNode *next;

}SNode,*LinkStack;

LinkStack top;

LinkStack PushStack(LinkStack top,int x) //入棧

{

LinkStack s;

s=(LinkStack)malloc(sizeof(SNode));

s-data=x;

s-next=top;

top=s;

return top;

}

LinkStack PopStack(LinkStack top) //退棧

{

LinkStack p;

if(top!=NULL)

{

p=top;

top=top-next;

free(p);

printf("退棧已完成\n");

return top;

}

else printf("棧是空的，無(wú)法退棧！\n"); return 0;

}

int GetStackTop(LinkStack top) //取棧頂元素

{

return top-data;

}

bool IsEmpty()//bool取值false和true，是0和1的區(qū)別,bool只有一個(gè)字節(jié),BOOL為int型,bool為布爾型

{

return top==NULL ? true:false;

}

void Print()

{

SNode *p;

p=top;

if(IsEmpty())

{

printf("The stack is empty!\n");

return;

}

while(p)

{

printf("%d ", p-data);

p=p-next;

}

printf("\n");

}

void main()

{

int x,a,b;

char m;

do { printf("\n");

printf("###############鏈棧的基本操作##################\n");

printf("××××××××1.置空棧××××××××××\n");

printf("××××××××2.進(jìn)?！痢痢痢痢痢痢痢痢痢痢羂n");

printf("××××××××3.退?！痢痢痢痢痢痢痢痢痢痢羂n");

printf("××××××××4.取棧頂元素××××××××\n");

printf("××××××××5.退出程序×××××××××\n");

printf("##############################################\n");

printf("\n請(qǐng)選擇一個(gè)字符:");

scanf("%c",m);

switch(m){

case '1':

top=NULL;

printf("\n棧已置空!");

break;

case '2':

printf("\n請(qǐng)輸入要進(jìn)棧的元素個(gè)數(shù)是:");

scanf("%d",a);

printf("\n請(qǐng)輸入要進(jìn)棧的%d個(gè)元素:",a);

for(b=0;ba;b++) {

scanf("%d",x);

top=PushStack(top,x); }

printf("進(jìn)棧已完成！\n");

printf("\n輸出棧為:");

Print();

break;

case '3':

printf("\n操作之前的輸出棧為:");

Print();

top=PopStack(top);

printf("\n操作過(guò)后的輸出棧為:");

Print();

break;

case '4':

printf("\n輸出棧為:");

Print();

if(top!=NULL)

printf("\n棧頂元素是：%d\n",GetStackTop(top));

else

printf("\n棧是空的，沒(méi)有元素！");

break;

case '5':break;

default:

printf("\n輸入的字符不對(duì)，請(qǐng)重新輸入!");

break;

}

getchar();

}while(m!='5');

}

C語(yǔ)言函數(shù)調(diào)用棧

程序的執(zhí)行過(guò)程可看作連續(xù)的函數(shù)調(diào)用。當(dāng)一個(gè)函數(shù)執(zhí)行完畢時(shí)，程序要回到調(diào)用指令的下一條指令(緊接call指令)處繼續(xù)執(zhí)行。函數(shù)調(diào)用過(guò)程通常使用堆棧實(shí)現(xiàn)，每個(gè)用戶態(tài)進(jìn)程對(duì)應(yīng)一個(gè)調(diào)用棧結(jié)構(gòu)(call stack)。編譯器使用堆棧傳遞函數(shù)參數(shù)、保存返回地址、臨時(shí)保存寄存器原有值(即函數(shù)調(diào)用的上下文)以備恢復(fù)以及存儲(chǔ)本地局部變量。

不同處理器和編譯器的堆棧布局、函數(shù)調(diào)用方法都可能不同，但堆棧的基本概念是一樣的。

寄存器是處理器加工數(shù)據(jù)或運(yùn)行程序的重要載體，用于存放程序執(zhí)行中用到的數(shù)據(jù)和指令。因此函數(shù)調(diào)用棧的實(shí)現(xiàn)與處理器寄存器組密切相關(guān)。

AX(AH、AL)：累加器。有些指令約定以AX(或AL)為源或目的寄存器。輸入/輸出指令必須通過(guò)AX或AL實(shí)現(xiàn)，例如：端口地址為43H的內(nèi)容讀入CPU的指令為INAL，43H或INAX，43H。目的操作數(shù)只能是AL/AX，而不能是其他的寄存器。 [5]

BX(BH、BL)： 基址寄存器 。BX可用作間接尋址的地址寄存器和 基地址寄存器 ，BH、BL可用作8位通用數(shù)據(jù)寄存器。 [5]

CX(CH、CL)：計(jì)數(shù)寄存器。CX在循環(huán)和串操作中充當(dāng)計(jì)數(shù)器，指令執(zhí)行后CX內(nèi)容自動(dòng)修改，因此稱為計(jì)數(shù)寄存器。 [5]

DX(DH、DL)：數(shù)據(jù)寄存器。除用作通用寄存器外，在 I/O指令 中可用作端口 地址寄存器 ，乘除指令中用作輔助累加器。 [5]

2.指針和 變址寄存器

BP( Base Pointer Register)：基址指針寄存器。 [5]

SP( Stack Pointer Register)： 堆棧指針寄存器 。 [5]

SI( Source Index Register)：源變址寄存器。 [5]

DI( Destination Index Register)：目的變址寄存器。 [5]

函數(shù)調(diào)用棧的典型內(nèi)存布局如下圖所示：

圖中給出主調(diào)函數(shù)(caller)和被調(diào)函數(shù)(callee)的棧幀布局，"m(%ebp)"表示以EBP為基地址、偏移量為m字節(jié)的內(nèi)存空間(中的內(nèi)容)。該圖基于兩個(gè)假設(shè)：第一，函數(shù)返回值不是結(jié)構(gòu)體或聯(lián)合體，否則第一個(gè)參數(shù)將位于"12(%ebp)" 處；第二，每個(gè)參數(shù)都是4字節(jié)大小(棧的粒度為4字節(jié))。在本文后續(xù)章節(jié)將就參數(shù)的傳遞和大小問(wèn)題做進(jìn)一步的探討。 此外，函數(shù)可以沒(méi)有參數(shù)和局部變量，故圖中“Argument(參數(shù))”和“Local Variable(局部變量)”不是函數(shù)棧幀結(jié)構(gòu)的必需部分。

其中，主調(diào)函數(shù)將參數(shù)按照調(diào)用約定依次入棧(圖中為從右到左)，然后將指令指針EIP入棧以保存主調(diào)函數(shù)的返回地址(下一條待執(zhí)行指令的地址)。進(jìn)入被調(diào)函數(shù)時(shí)，被調(diào)函數(shù)將主調(diào)函數(shù)的幀基指針EBP入棧，并將主調(diào)函數(shù)的棧頂指針ESP值賦給被調(diào)函數(shù)的EBP(作為被調(diào)函數(shù)的棧底)，接著改變ESP值來(lái)為函數(shù)局部變量預(yù)留空間。此時(shí)被調(diào)函數(shù)幀基指針指向被調(diào)函數(shù)的棧底。以該地址為基準(zhǔn)，向上(棧底方向)可獲取主調(diào)函數(shù)的返回地址、參數(shù)值，向下(棧頂方向)能獲取被調(diào)函數(shù)的局部變量值，而該地址處又存放著上一層主調(diào)函數(shù)的幀基指針值。本級(jí)調(diào)用結(jié)束后，將EBP指針值賦給ESP，使ESP再次指向被調(diào)函數(shù)棧底以釋放局部變量；再將已壓棧的主調(diào)函數(shù)幀基指針彈出到EBP，并彈出返回地址到EIP。ESP繼續(xù)上移越過(guò)參數(shù)，最終回到函數(shù)調(diào)用前的狀態(tài)，即恢復(fù)原來(lái)主調(diào)函數(shù)的棧幀。如此遞歸便形成函數(shù)調(diào)用棧。

EBP指針在當(dāng)前函數(shù)運(yùn)行過(guò)程中(未調(diào)用其他函數(shù)時(shí))保持不變。在函數(shù)調(diào)用前，ESP指針指向棧頂?shù)刂?，也是棧底地址。在函?shù)完成現(xiàn)場(chǎng)保護(hù)之類的初始化工作后，ESP會(huì)始終指向當(dāng)前函數(shù)棧幀的棧頂，此時(shí)，若

本文名稱：c語(yǔ)言中棧的基本函數(shù),C語(yǔ)言函數(shù)調(diào)用棧
鏈接地址：http://chinadenli.net/article22/dsshgjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、標(biāo)簽優(yōu)化、App設(shè)計(jì)、網(wǎng)站營(yíng)銷、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)