定義棧的存儲結構
❶ 棧結構通常採用的兩種儲存結構是和
順序存儲和鏈接存儲，通稱順序隊列和鏈隊列，
是計算機科學中一種特殊的串列形式的抽象數據類型，其特殊之處在於只能允許在鏈表或數組的一端（稱為堆棧頂端指針，英語：top）。
進行加入數據（英語：push）和輸出數據（英語：pop）的運算。另外堆棧也可以用一維數組或鏈表的形式來完成。堆棧的另外一個相對的操作方式稱為隊列。
由於堆棧數據結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。
堆棧數據結構使用兩種基本操作：推入（壓棧，push）和彈出（彈棧，pop）：
推入：將數據放入堆棧的頂端（數組形式或串列形式），堆棧頂端top指針加一。
彈出：將頂端數據數據輸出（回傳），堆棧頂端數據減一。
(1)定義棧的存儲結構擴展閱讀：
堆棧是一個特定的存儲區或寄存器，它的一端是固定的，另一端是浮動的。對這個存儲區存入的數據，是一種特殊的數據結構。所有的數據存入或取出，只能在浮動的一端(稱棧頂)進行，嚴格按照「後進先出」的原則存取，位於其中間的元素。
必須在其棧上部(後進棧者)諸元素逐個移出後才能取出。在內存儲器 (隨機存儲器) 中開辟一個區域作為堆棧，叫軟體堆棧; 用寄存器構成的堆棧，叫硬體堆棧。堆棧處理器就是一種硬體堆棧相對寄存器文件處理器來講。
它具有很多優點系統復雜度低；精簡的指令集；晶元面積小；定址方式簡單；代碼體積小；快速的中斷響應，子程序調用能力。這些優點使得堆棧處理器在工業控制領域和航空航天領域有著不可替代的地位。
❷ 棧的順序存儲結構
這是結果，需要的話給我個郵箱
/*
在vc++6.0中的輸出結果：
------------------------
初始化棧.....
創建一個包含5個不大於100的正整數值的棧（5個值由計算機隨機產生）...
棧中的元素從棧底到棧頂為：41 67 34 0 69
請輸入要插在棧頂的元素e = 100
棧中的元素從棧底到棧頂為：41 67 34 0 69 100
彈出的棧頂元素 e = 100
棧中的元素從棧底到棧頂為：41 67 34 0 69
棧中元素個數是5
輸出從棧頂到棧底的所有元素：69 0 34 67 41
Press any key to continue
------------------------------
*/
❸ 一道數據結構題目（高手進）
sdfauybgoaiusvg6 56 98twgbuihi
❹ C語言版的數據結構中，棧存儲結構是什麼
棧（stack）在計算機科學中是限定僅在表尾進行插入或刪除操作的線性表。 棧是一種數據結構 ，是只能在某一端插入和刪除的特殊線性表 。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。
❺ 棧的順序存儲是什麼
由於棧是運算受限的線性表，因此線性表的存儲結構對棧也適用，而線性表有順序存儲和鏈式存儲兩種，所以棧也有順序存儲和鏈式存儲兩種。
1.棧的順序存儲棧的順序存儲是利用一組地址連續的存儲單元依次存放從棧底到棧頂的數據元素，並附設指針top指示棧頂。
2.棧的順序存儲類型定義1）用內存動態分配方式定義棧的順序存儲（1）棧的順序存儲表示。
順序棧本質上是順序表的簡化，由於棧底位置是固定不變的，所以可以將棧底位置設置在存儲空間的基地址上，棧頂位置是隨著進棧和退棧操作而變化的，故用top來指示當前棧頂元素的下一個位置，通常稱top為棧頂指針。
❻ 分別就棧的順序存儲結構和鏈式存儲結構實現棧的各種基本操作。
順序存儲結構
#include<iostream>
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *&s);//初始化棧
void ClearStack(sqStack *&s);//摧毀棧
int StackLength(sqStack *s);//返回棧的長度
bool StackEmpty(sqStack *s);//判斷棧是否為空
int Push(sqStack *&s,ElemType e);//進棧
int Pop(sqStack *&s,ElemType &e);//出棧
int GetTop(sqStack *s,ElemType &e);//取棧頂元素
void DispStack(sqStack *s);//顯示棧中元素值
int main()
{
return 0;
}
void InitStack(sqStack *&s)//初始化棧
{
s=new sqStack;
s->top=-1;
}
void ClearStack(sqStack *&s)//摧毀棧
{
delete s;
}
int StackLength(sqStack *s)//返回棧的長度
{
return (s->top+1);
}
bool StackEmpty(sqStack *s)//判斷棧是否為空
{
return (s->top==-1);
}
int Push(sqStack *&s,ElemType e)//進棧
{
if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
int Pop(sqStack *&s,ElemType &e)//出棧
{
if(s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;
}
int GetTop(sqStack *s,ElemType &e)//取棧頂元素
{
if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}
void DispStack(sqStack *s)//顯示棧中元素值
{
for(int i=s->top;i>=0;i--)
cout<<s->data[i]<<" ";
cout<<endl;
}
鏈式存儲結構
typedef char ElemType;
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *&s);//初始化棧
void ClearStack(LiStack *&s);//摧毀棧
int StackLength(LiStack *s);//返回棧的長度
bool StackEmpty(LiStack *s);//判斷棧是否為空
void Push(LiStack *&s,ElemType e);//進棧
int Pop(LiStack *&s,ElemType &e);//出棧
int GetTop(LiStack *s,ElemType &e);//取棧頂元素
void DispStack(LiStack *s);//顯示棧中元素值
int main()
{
return 0;
}
void InitStack(LiStack *&s)//初始化棧
{
s=new LiStack;
s->next=NULL;
}
void ClearStack(LiStack *&s)//摧毀棧
{
for(LiStack *p=s->next;p;p=p->next)
{
delete s;
s=p;
p=p->next;
}
delete s;
}
int StackLength(LiStack *s)//返回棧的長度
{
int i=0;
for(LiStack *p=s->next;p;p=p->next)
i++;
return i;
}
bool StackEmpty(LiStack *s)//判斷棧是否為空
{
return (s->next==NULL);
}
void Push(LiStack *&s,ElemType e)//進棧
{
LiStack *p=new LiStack;
p->data=e;
p->next=s->next;
s->next=p;
}
int Pop(LiStack *&s,ElemType &e)//出棧
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
delete p;
return 1;
}
int GetTop(LiStack *s,ElemType &e)//取棧頂元素
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}
void DispStack(LiStack *s)//顯示棧中元素值
{
LiStack *p=s->next;
for(;p;p=p->next)
cout<<p->data<<" ";
cout<<endl;
}
❼ 定義棧的順序存儲結構表達式求值
include
#include
#include //判斷是否為字元的函數的頭文件
#define maxsize 100
typedef int elemtype;
typedef struct sqstack sqstack;//由於sqstack不是一個類型 而struct sqstack才是
char ch[7]=;//把符號轉換成一個字元數組
int f1[7]=;//棧內元素優先順序
int f2[7]=;//棧外的元素優先順序
struct sqstack
{
elemtype stack[maxsize];
int top;
};
void Initstack(sqstack *s)
{
s->top=0;
}
void Push(sqstack *s,elemtype x)
{
if(s->top==maxsize-1)
printf("Overflow\n");
else
{
s->top++;
s->stack[s->top]=x;
}
}
void Pop(sqstack *s,elemtype *x)
{
if(s->top==0)
printf("underflow\n");
else
{
*x=s->stack[s->top];
s->top--;
}
}
elemtype Gettop(sqstack s)
{
if(s.top==0)
{
printf("underflow\n");
return 0;
}
else
return s.stack[s.top];
}
elemtype f(char c)
{
switch(c)
{
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
case '(':
return 4;
case ')':
return 5;
default:
return 6;
}
}
char precede(char c1,char c2)
{
int i1=f(c1);
int i2=f(c2);//把字元變成數字
if(f1[i1]>f2[i2])//通過原來設定找到優先順序
return '>';
else if(f1[i1]<f2[i2])
return '<';
else
return '=';
}
int Operate(elemtype a,elemtype theta,elemtype b)
{
int sum;
switch(theta)
{
case 0:
sum=a+b;
break;
case 1:
sum=a-b;
break;
case 2:
sum=a*b;
break;
default:
sum=a/b;
}
return sum;
}
EvaluateExpression()
{
char c;
int i=0,sum=0;
int k=1,j=1;//設置了開關變數
elemtype x,theta,a,b;
sqstack OPTR,OPND;
Initstack(&OPTR);
Push(&OPTR,f('#'));//0壓入棧
Initstack(&OPND);
c=getchar();
if(c==ch[2]||c==ch[3]||c==ch[5]||c==ch[6])//先對＋和-的情況忽略和左括弧的情況
{
printf("錯誤1 \n");
k=0;
return 0;
}
if(c==ch[0])
c=getchar();//如果是＋，把它覆蓋
if(c==ch[1])
{
j=0;
c=getchar();//也把－號覆蓋
}
while(c!='#'||ch[Gettop(OPTR)]!='#')
{
if(isdigit(c))
{
sum=0;
while(isdigit(c))
{
if(!j)
{
sum=sum*10-(c-'0');//實現了數字串前面有負號（之前是：sum=-(sum*10)-(c-'0')結果是－12＋13＝21）
}
else
sum=sum*10+(c-'0');
c=getchar();
}
Push(&OPND,sum);//如果還是數字先不壓棧，把數字串轉化成十進制數字再壓棧
j=1;
}
else
if(k)
{
switch(precede(ch[Gettop(OPTR)],c))
{
case'<': Push(&OPTR,f(c));//把它們整型化
c=getchar();
if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c=='\n')//要除去下個是『（』的情況 也把以運算符歸到這里來
{
printf("出錯2\n");
k=0;
return 0;//加了開關變數和返回0的值使程序更以操作
}
break;
case'=': Pop(&OPTR,&x);
c=getchar();
if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c=='\n')//把ch[6]的情況也忽略了但此時並沒有注意到右括弧後面右運算符的情況
{
printf("出錯2\n");
k=0;
return 0;
}
break;
case'>': Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);//注意這里是誰先出棧
Push(&OPND,Operate(a,theta,b));
break;
}
}
}//在這里判斷是否以運算符結束是不對的
return(Gettop(OPND));
}
main()
{
int result;
printf("輸入你的算術表達式：\n");
result=EvaluateExpression();
printf("結果是 :%d\n",result);
return 0;
}
:
本計算器利用堆棧來實現。
1、定義後綴式計算器的堆棧結構
因為需要存儲的單元不多，這里使用順序棧，即用一維數組來模擬堆棧：
#define MAX 100
int stack[MAX];
int top=0;
因此程序中定義了長度為MAX的一維數組，這里MAX用宏定義為常數100，我們可以修改宏定義而重新定義堆棧的大小。
整型數據top為棧頂指示，由於程序開始時堆棧中並無任何數據元素，因此top被初始化為0。
2、存儲後綴式計算器的運算數
我們定義了堆棧stack[MAX]後，就可以利用入棧操作存儲先後輸入的兩個運算數。
下面看一下是如何實現的：
int push(int i) /*存儲運算數，入棧操作*/
{
if(top<MAX)
{
stack[++top]=i; /*堆棧仍有空間，棧頂指示上移一個位置*/
return 0;
}
else /*堆棧已滿，給出錯誤信息，返回出錯指示*/
{
printf("The stack is full");
return ERR;
}
}
我們在調用函數push時，如果它的返回值為0，說明入棧操作成功；否則，若返回值為ERR(在程序中說明為-1)，說明入棧操作失敗。
3、從堆棧中取出運算數
當程序中讀完了四則運算符後，我們就可以從堆棧中取出已經存入的兩個運算數，構成表達式，計算出結果。取出運算數的函數採用的正是出棧演算法。在本例中，實現該演算法的函數 為pop():
int pop(); /*取出運算數，出棧操作*/
{
int var; /*定義待返回的棧頂元素*/
if(top!=NULL) /*堆棧中仍有數據元素*/
{
var=stack[top--]; /*堆棧指示下移一個位置*/
return var;
}
else /*堆棧為空，給出錯誤信息，並返回出錯返回值*/
printf("The stack is cmpty!\n");
return ERR;
}
同樣，如果堆棧不為空，pop()函數返回堆棧頂端的數據元素，否則，給出棧空提示，並返回錯誤返回值ERR。
4、設計完整的後綴式計算器
有了堆棧存儲運算數，後綴式計算器的設計就很簡單了。程序首先提示用戶輸入第一個運算數，調用push()函數存入堆棧中；而後提示用戶輸入第二個運算數，同樣調用push()函數存入堆棧中。接下來，程序提示用戶輸入+,-,*,/四種運算符的一種，程序通過switch_case結構判斷輸入運算符的種類，轉而執行不同的處理代碼。以除法為例，說明程序的執行流程：
case '/':
b=pop();
a=pop();
c=a/b;
printf("\n\nThe result is %d\n",c);
printf("\n");
break;
程序判斷用戶輸入的是除號後，就執行上述代碼。首先接連兩次調用pop()函數從堆棧中讀出先前輸入的運算數，存入整型數a和b中；然後執行除法運算，結果存入單元c中。這時需要考慮究竟誰是被除數，誰是除數。由於開始我們先將被除數入棧，根據堆棧「先進後出」的原則，被除數應該是第二次調用pop()函數得到的返回值。而除數則是第一次調用pop()函數得到的返回值。
最後程序列印出運算結果，並示提示用戶是否繼續運行程序：
printf("\t Continue?(y/n):");
l=getche();
if(l=='n')
exit(0);
如果用戶回答是"n"，那麼結束程序，否則繼續循環。
完整的程序代碼如下：
#include
#include
#include
#define ERR -1
#define MAX 100 /*定義堆棧的大小*/
int stack[MAX]; /*用一維數組定義堆棧*/
int top=0; /*定義堆棧指示*/
int push(int i) /*存儲運算數,入棧操作*/
{
if(top<MAX)
{
stack[++top]=i; /*堆棧仍有空間，棧頂指示上移一個位置*/
return 0;
}
else
{
printf("The stack is full");
return ERR;
}
}
int pop() /*取出運算數，出棧操作*/
{
int var; /*定義待返回的棧頂元素*/
if(top!=NULL) /*堆棧中仍有元素*/
{
var=stack[top--]; /*堆棧指示下移一個位置*/
return var; /*返回棧頂元素*/
}
else
printf("The stack is empty!\n");
return ERR;
}
void main()
{
int m,n;
char l;
int a,b,c;
int k;
do{
printf("\tAriothmatic Operate simulator\n"); /*給出提示信息*/
printf("\n\tPlease input first number:"); /*輸入第一個運算數*/
scanf("%d",&m);
push(m); /*第一個運算數入棧*/
printf("\n\tPlease input second number:"); /*輸入第二個運算數*/
scanf("%d",&n);
push(n); /*第二個運算數入棧*/
printf("\n\tChoose operator(+/-/*//):");
l=getche(); /*輸入運算符*/
switch(l) /*判斷運算符，轉而執行相應代碼*/
{
case '+':
b=pop();
a=pop();
c=a+b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
case '-':
b=pop();
a=pop();
c=a-b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
case '*':
b=pop();
a=pop();
c=a*b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
case '/':
b=pop();
a=pop();
c=a/b;
printf("\n\n\tThe result is %d\n",c);
printf("\n");
break;
}
printf("\tContinue?(y/n):"); /*提示用戶是否結束程序*/
l=getche();
if(l=='n')
exit(0);
}while(1);
}
:
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define STACK_INIT_SIZE 100 //初始分配量
#define STACKINCREMENT 10 //存儲空間的分配增量
typedef char ElemType;
typedef ElemType OperandType; //操作數
typedef char OperatorType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{
//構造一個空棧S
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S){
ElemType e;
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return e;
}
Status Push (SqStack &S,ElemType e)
{
//插入元素e為新的棧頂元素
if (S.top - S.base >= S.stacksize){
S.base = (ElemType *) realloc ( S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop (SqStack &S,ElemType &e){
//若棧不空，則刪除S的棧頂元素，用e返回其值，並返回OK；否則返回ERROR
if(S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}
char In(char c,char OP[])
{
if(c>=35 && c<=47)
return 1;
else return 0;
}
char OP[8]=;
int m[7][7]={1,1,2,2,2,1,1,
1,1,2,2,2,1,1,
1,1,1,1,2,1,1,
1,1,1,1,2,1,1,
2,2,2,2,2,0,-1,
1,1,1,1,-1,1,1,
2,2,2,2,2,-1,0};//1 > 2 < 0 = -1 不存在
char Precede(char i,char j)
{
int a,b; char *p;
for(p=OP,a=0;*p!='\0';p++,a++)
if(*p==i) break;
for(p=OP,b=0;*p!='\0';p++,b++)
if(*p==j) break;
if(m[a][b]==1) return '>';
else if(m[a][b]==2) return '<';
else if(m[a][b]==0) return '=';
else return 'O';
}
char Operate(char a,char theta,char b)
{
if(a>47) a=atoi(&a);
if(b>47) b=atoi(&b);
switch(theta)
{
case '+': return a+b;
break;
case '-': return a-b;
break;
case '*': return a*b;
break;
case '/': return a/b;
break;
}
}
OperandType EvaluateExpression()
{
SqStack OPTR,OPND;
OperandType a,b,c; OperatorType theta;
InitStack(OPTR); Push(OPTR,'#');
InitStack(OPND); c=getchar();
while (c!='#' || GetTop(OPTR)!='#')
{
if (!In(c,OP))
else
switch(Precede(GetTop(OPTR),c))
{
case '<' :
Push(OPTR,c); c = getchar();
break;
case '=' :
Pop(OPTR,c); c = getchar();
break;
case '>' :
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
}
return GetTop(OPND);
}
void main()
{
printf("(以#為結束符)\n");
printf("請輸入：\n");
int a;
a=(int)EvaluateExpression();
printf("%d",a);
getch();
}
:
ls都正確
:
C++ In Action這本書裡面有表達式求值的詳細項目分析.
:
數據結構的書裡面都有的,仔細看一下
:
studyall123的只能對0到9的數字運算才有效,對於10以上的數字就不行!不知道有沒有更好的方法!
:
現在的人，連google一下都懶啊
:
實際上是按照逆波蘭式的順序讓輸入的表達式入棧，再根據運算符優先順序來計算。
:
lenrning!