c語言怎麼實現通用棧的簡單介紹

本文目錄一覽：

• 1、C語言函數調用棧
• 2、棧的基本操作的實現(c語言)，高手速來！！
• 3、棧的c語言實現基本操作
• 4、C語言，棧的實現~

C語言函數調用棧

程序的執行過程可看作連續的函數調用。當一個函數執行完畢時，程序要回到調用指令的下一條指令(緊接call指令)處繼續執行。函數調用過程通常使用堆棧實現，每個用戶態進程對應一個調用棧結構(call stack)。編譯器使用堆棧傳遞函數參數、保存返回地址、臨時保存寄存器原有值(即函數調用的上下文)以備恢復以及存儲本地局部變量。

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

寄存器是處理器加工數據或運行程序的重要載體，用於存放程序執行中用到的數據和指令。因此函數調用棧的實現與處理器寄存器組密切相關。

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

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

CX(CH、CL)：計數寄存器。CX在循環和串操作中充當計數器，指令執行後CX內容自動修改，因此稱為計數寄存器。 [5]

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

2.指針和 變址寄存器

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

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

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

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

函數調用棧的典型內存布局如下圖所示：

圖中給出主調函數(caller)和被調函數(callee)的棧幀布局，”m(%ebp)”表示以EBP為基地址、偏移量為m位元組的內存空間(中的內容)。該圖基於兩個假設：第一，函數返回值不是結構體或聯合體，否則第一個參數將位於”12(%ebp)” 處；第二，每個參數都是4位元組大小(棧的粒度為4位元組)。在本文後續章節將就參數的傳遞和大小問題做進一步的探討。 此外，函數可以沒有參數和局部變量，故圖中「Argument(參數)」和「Local Variable(局部變量)」不是函數棧幀結構的必需部分。

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

EBP指針在當前函數運行過程中(未調用其他函數時)保持不變。在函數調用前，ESP指針指向棧頂地址，也是棧底地址。在函數完成現場保護之類的初始化工作後，ESP會始終指向當前函數棧幀的棧頂，此時，若

棧的基本操作的實現(c語言)，高手速來！！

/*程序錯誤太多*/ #include”stdio.h”

#include”stdlib.h”

#include”time.h”

#include”malloc.h”

#define

STACK_INIT_SIZE

10

//棧容量 typedef

struct

SqStack

{

int

top;

//棧頂當前指針

int

*base;

//棧空間數組

}SqStack; void

InitStack(SqStack

S);

//構造空棧S

int

Push(SqStack

S,int

e);

//入棧（棧地址，入棧數據）

返回0對，-1錯

int

Pop(SqStack

S);

//出棧

（棧地址）返回棧頂數據

int

StackLength(SqStack

S);

//返回站的元素個數，即求棧長

void

Print_S(SqStack

S);

//顯示棧內數據 int

main()

{

SqStack

S;

int

i=0;

int

a,e;

InitStack(S);

srand((unsigned)time(NULL));

//srand((unsigned)time(NULL))以time函數值(當前時間)作為種子

printf(“隨機填充5個元素為:

“);

while(

i5)

{

a

=

rand()%100;

printf(“%d

“,

a);

Push(S,a);

i++;

}

Print_S(S);

printf(“請輸入要插入棧頂的元素:”);

scanf(“%d”,e);

Push(S,e);

Print_S(S);

printf(“再彈出的棧頂元素為:%d

\n”,Pop(S));

printf(“棧的長度為:%d

\n”,StackLength(S));

Print_S(S);

return

0;

} void

InitStack(SqStack

S)

//構造空棧S

{

S.base

=

(int

*)malloc(STACK_INIT_SIZE

*

sizeof(int));

//分配組數空間，長度STACK_INIT_SIZE

if

(S.base==NULL)

{

printf(“內存分配失敗!\n”);

return;

}

S.top=-1;

} int

Push(SqStack

S,int

e)

{

if(S.top=STACK_INIT_SIZE)

{

printf(“棧空間已滿，入棧失敗!\n”);

return

-1;

}

else

{

S.base[++S.top]=e;

return

0;

}

} int

Pop(SqStack

S)

//返回棧頂數據

{

if

(S.top=0)

//棧內有數據

{

return

S.base[S.top–];

}

else

{

printf(“空棧，無數據彈出!\n”);

return

-1;

}

} int

StackLength(SqStack

S)

{

return

S.top+1;

} void

Print_S(SqStack

S)

{

printf(“\n出棧顯示：”);

if(S.top

==

-1)

printf(“棧內無數據!\n”);

else

{

while(S.top=0

)

printf(“%d

“,Pop(S));

putchar(‘\n’);

}

}

棧的c語言實現基本操作

寫了一個鏈式棧，你看看

# 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是指向棧底下一個沒有實際意義的元素

}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等價於struct Stack

int val;

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

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 ); //清空數據

// 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( “動態內存分配失敗!\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;

}

}

C語言，棧的實現~

#includestdio.h

#includemalloc.h

//enum bool {false,true};

typedef struct Node{

int a;

int Number; //在棧中的序號，棧底為0

struct Node *next;

}Node,*LpNode;

typedef struct SqStack{

Node *top;

Node *prev;

Node *base;

int length;

}*LpSqStack;

//將e的能容複製到S中並將e摧毀

bool Node_evaluation(LpNode S,LpNode e,bool M)

{

//賦值操作

//S-Number = e-Number;

if(M == true) free(e);

return true;

}

bool InitStack(LpSqStack S)

{

S-length = 0;

S-base = (LpNode)malloc(sizeof(Node));

if(!S-base) return false;

S-top = S-base;

S-prev = S-base;

S-base-Number = 0;

return true;

}

bool StackEmpty(LpSqStack S)

{

if(S-top != S-base) return false;

return true;

}

bool GetTop(LpSqStack S,LpNode e)

{

if(S-top == S-base) return false;

e = S-top;

return true;

}

bool Push(LpSqStack S,LpNode e)

{

if(!Node_evaluation(S-top,e,true)) return false;

S-top-Number = S-prev-Number + 1;

S-prev = S-top;

S-top = (LpNode)malloc(sizeof(Node));

S-prev-next = S-top;

S-top-next = NULL;

return true;

}

bool Pop(LpSqStack S,LpNode e)

{

if(S-top == S-base) return false;

if(!Node_evaluation(e,S-top,true)) return false;

S-top = S-prev;

S-top-next = NULL;

return true;

}

bool Vistit(LpSqStack S,LpNode e,int i)

{

LpNode p;

p = S-base;

for(int j = 0; j = i; j++)

{

if(p-next == NULL) return false;

p = p-next;

}

if(!Node_evaluation(p,e,false)) return false;

return true;

}

int main()

{

SqStack a;

InitStack(a);

LpNode b=new Node;

LpNode c=new Node;

LpNode d=new Node;

//free(b);這free了你下面又賦值。。。

b-a=1;

Push(a,c);

GetTop(a,c);

printf(“%d”,c-a);

return 0;

}

棧里的內存是不能free的，你要free你就自己在堆里分配。