❶ 棧的存儲結構
棧同順序表和鏈表一樣，棧也是用來存儲邏輯關系為 "一對一" 數據的線性存儲結構。
棧的具體實現
棧是一種 "特殊" 的線性存儲結構，因此棧的具體實現有以下兩種方式：
順序棧：採用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構；
鏈棧：採用鏈式存儲結構實現棧結構；
棧存儲結構與之前所學的線性存儲結構有所差異，這緣於棧對數據 "存" 和 "取" 的過程有特殊的要求：
棧只能從表的一端存取數據，另一端是封閉的；
在棧中，無論是存數據還是取數據，都必須遵循"先進後出"的原則，即最先進棧的元素最後出棧。
通常，棧的開口端被稱為棧頂；相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素。
❷ 棧、隊列的操作
先解答第一題：
#include<iostream>
using namespace std;
int N=100;
#define INCREASESIZE 10
#define OK 1
#define FAIL 0
#define NUM 5
typedef struct
{
char taskname[10]; //任務名
int taskno; //任務號
}DataType;
typedef struct
{
DataType *s;
DataType *base,*top;
}ST;
class Stack
{
public:
int push(DataType e)
{
if(st.top-st.base==N)
{
st.s=new DataType[N+INCREASESIZE];
N+=10;
}
*st.top=e;
st.top++;
return OK;
}
int pop(DataType& e)
{
if(st.base==st.top)
return FAIL;
e=*(--st.top);
return OK;
}
int destroy()
{
delete [] st.s;
return OK;
}
int initial()
{
st.s=new DataType[N];
st.base =st.top=st.s;
return OK;
}
private:
ST st;
};
int main()
{
Stack SS;
DataType v[NUM]={{"ab",1},{"bc",2},{"cd"鎮兆,3},{"de",4},{"ef",5}},e;
int i;
SS.initial();
for(i=0;i<NUM;i++)
SS.push(v[i]);
cout<<"\nPlease print the stack:\n";
for(i=0;i<枝吵NUM;i++)
{
SS.pop(e);
cout<<猛旅侍e.taskname<<" "<<e.taskno<< endl;
}
SS.destroy();
return OK;
}
第二題，吃完飯，再解。。。
#include<iostream>
using namespace std;
#define N 5
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef struct
{
int *p;
int front,rear;
}QUE;
class Queue
{
public:
int enQueue(int e)
{
if((Qu.rear+1)%MAXSIZE==Qu.front)
return ERROR;
Qu.p[Qu.rear]=e;
Qu.rear=(Qu.rear+1)%MAXSIZE;
return OK;
}
int deQueue(int& e)
{
if(Qu.front==Qu.rear)
return ERROR;
e=Qu.p[Qu.front];
Qu.front=(Qu.front+1)%MAXSIZE;
return OK;
}
int destroyQ()
{
delete [] Qu.p;
return OK;
}
int initial()
{
Qu.p=new int[MAXSIZE];
Qu.front=Qu.rear=0;
return OK;
}
private:
QUE Qu;
};
typedef struct node
{
int value;
struct node *next;
}node,*PN;
typedef struct
{
PN front;
PN rear;
}LQ;
class LinkQueue
{
public:
int enQueue(int e)
{
pn=new node;
pn->value =e;
pn->next=NULL;
lq.rear->next=pn;
lq.rear=pn;
return OK;
}
int deQueue(int& e)
{
if(lq.front==lq.rear)
return ERROR;
pn=lq.front ->next ;
e=pn->value ;
lq.front =lq.front ->next ;
if(lq.front ==lq.rear )
lq.rear =lq.front ;
return OK;
}
int destroyQ()
{
while(lq.front)
{
lq.rear=lq.front->next;
free(lq.front);
lq.front=lq.rear;
}
return OK;
}
int initial()
{
lq.front =lq.rear=new node;
lq.front->next=NULL;
return OK;
}
private:
LQ lq;
PN pn;
};
int main()
{
Queue Q;
int a[N]={1,2,3,4,5},i,e;
Q.initial();
for(i=0;i<N;i++)
Q.enQueue(a[i]);
cout<<"\nPlease print the Queue:\n";
for(i=0;i<N;i++)
{
Q.deQueue(e);
cout<<e<<" "<<endl;
}
Q.destroyQ();
LinkQueue lk;
lk.initial();
for(i=0;i<N;i++)
lk.enQueue (a[i]);
cout<<"\nPlease print the LinkQueue:\n";
for(i=0;i<N;i++)
{
lk.deQueue(e);
cout<<e<<" "<<endl;
}
lk.destroyQ();
return 0;
}
希望kutpbpb的回答能對你有所幫助！
❸ c語言 棧的操作
#include
#include
#define Max 100
typedef char T;
typedef struct MyStack
{
T aa[Max];
unsigned int p;
} stack;
//創建空棧
stack* createEmptyStack()
{
stack* st = (stack *)malloc(sizeof(stack));
int i=0;
for(i=0;i<Max;i++)
st->aa[i]=0;
st->p=0;
return st;
};
//棧判空
int isEmpty(const stack* st)
{
if(st->p==0) return 1;
else return 0;
};
//求棧的大小
unsigned int size(const stack* st)
{
return st->p;
};
//push操作
void push(stack* st,const T a)
{
st->p=st->p+1;
if(st->p==Max)
{
printf("棧滿\n");
st->p--;
return;
}
st->aa[st->p]=a;
};
//pop操作
T pop(stack* st)
{
if(isEmpty(st))
{
printf("棧空");
return NULL;
}
char t=st->aa[st->p];
st->p=st->p-1;
printf("%c ",t);
return t;
};
//棧銷毀
void destroy(stack* st)
{
free(st);
};
int main()
{
stack* st = createEmptyStack();
if(isEmpty(st)) printf("MyStack is empty\n");
else printf("MyStack is not empty\n");
push(st,'a');
push(st,'b');
push(st,'c');
push(st,'d');
push(st,'e');
printf("%d\n",size(st));
while(!isEmpty(st)) pop(st);
destroy(st);
system("pause");
return 0;
}
❹ 數據結構編程求救
試驗一:
#include<iostream>
#include<string>
using namespace std;
struct List
{
int num;
List *next;
};
List *head=NULL;
List* CreateList()
{
List *pL;
List *pEnd;
pL=new List;
head=pL;
pEnd=pL;
cout<<"請輸入節點的數目,以 0 結束"<<endl;
cin>>pL->num;
while(pL->num!=0)
{
pEnd->next=pL;
pEnd=pL;
pL=new List;
cin>>pL->num;
}
delete pL;
pEnd->next=NULL;
return head;
}
void ShowList(List *head)
{
cout<<endl;
cout<<"鏈表節點如下:"<<endl;
while(head)
{
cout<<head->num<<endl;
head=head->next;
}
}
void InsertList(List *head,int num)
{
List *list =new List;
List *l;
while(head)
{
l=head;
head=head->next;
}
list->num=num;
list->next=NULL;
l->next=list;
}
void DeleteList(List *head, int num)
{
List *l;
if(head->num==num)
{
l=head;
head=head->next;
::head=head;
delete l;
return ;
}
List *l1=head;
while(head)
{
if(head->next==NULL){
cout<<"找不到不要刪除的數字."<<endl;
return ;
}
if(head->next->num==num)
{
l=head->next;
head->next=l->next;
delete l;
::head=l1;
cout<<"操作成功"<<endl;
return ;
}
head=head->next;
}
cout<<"找不到不要刪除的數字."<<endl;
}
int GetListNum(List *head)
{
int num=0;
while(head)
{
num++;
head=head->next;
}
return num;
}
int main()
{
string str;
begin:
cout<<"1->增加鏈表 2->顯示鏈表 3->插入節點 4->刪除節點 5->節點數目"<<endl;
cin>>str;
if(str[0]=='1')
{
CreateList();
}
else if(str[0]=='2')
{
if(head==NULL)
{
cout<<"你的鏈表現在是空的,請增加鏈表"<<endl;
getchar();
getchar();
system("cls");
goto begin;
}
ShowList(head);
}
else if(str[0]=='3')
{
if(head==NULL)
{
cout<<"你的鏈表現在是空的,請增加鏈表"<<endl;
getchar();
getchar();
system("cls");
goto begin;
}
int num;
cout<<"請輸入要插入的數字:"<<endl;
cin>>num;
InsertList(head,num);
}
else if(str[0]=='4')
{
if(head==NULL)
{
cout<<"你的鏈表現在是空的,請增加鏈表"<<endl;
getchar();
getchar();
system("cls");
goto begin;
}
int num;
cout<<"請輸入要刪除的數字:"<<endl;
cin>>num;
DeleteList(head,num);
}
else if(str[0]=='5')
{
cout<<"節點數是:"<<GetListNum(head)<<endl;
}
else
{
cout<<"輸入錯誤,請重新輸入.";
}
if(str[0]!='Q' && str[0]!='q'){
cout<<endl<<endl;
getchar();
getchar();
system("cls");
goto begin;
}
}
試驗二:
#include<iostream>
#include<string>
using namespace std;
struct Stack {
char c;
Stack *pNext;
};
void InitStack(Stack *&s)
{
s=NULL;
}
char Peek(Stack *s)
{
if(s==NULL) {
cout<<"棧是空的."<<endl;
return -1;
}
return s->c;
}
void Push(Stack *&s,Stack *newS)
{
newS->pNext=s;
s=newS;
}
char Pop(Stack *&s)
{
if(s==NULL)
{
cout<<"棧是空的."<<endl;
return -1;
}
Stack *pNext;
char c;
if(s)
{
pNext=s->pNext;
c=s->c;
delete s;
s=pNext;
return c;
}
}
int main()
{
Stack *s;
Stack *s1;
InitStack(s);
long num;
int m;
int k;
char c;
cout<<"輸入一個數:"<<endl;
cin>>num;
cout<<"輸入要轉換的進制:"<<endl;
cin>>k;
while(num!=0)
{
m=num%k;
c=(int('0')+m);
s1=new Stack;
s1->c=c;
Push(s,s1);
num/=k;
}
while(s)
{
cout<<Pop(s);
}
cout<<endl;
}
❺ 利用棧實現中序線索化二叉樹非遞歸演算法的實驗報告——百度文庫
#include<iostream.h>
typedef char elemtype;
class bitree
{
public:
elemtype data; //結點數據類型
bitree *lchild, *rchild; //定義左、右孩子純鄭為指針型
bitree *creat();
void preorder(bitree *root);
void inorder(bitree *root);
void postorder(bitree *root);
};
//建立二叉樹
bitree *bitree::creat()
{
bitree *q[100];
bitree *s;
bitree *root;
int front=1,rear=0;
char ch;
root=NULL;
cin>>ch;
while(ch!='#')
{
s=NULL;
if(ch!=',')
{
s=new bitree;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
q[rear]=s;
if(rear==1) root=s;
else
{
if((s!=NULL)&&(q[front]!=NULL))
{
if(rear%2==0) q[front]->lchild=s;
else q[front]->rchild=s;
}
if(rear%2==1) front++;
}
cin>>ch;
}
return root;
}
//前序遍歷二叉樹做啟頌
void bitree::preorder(bitree *root)
{
bitree *p,*s[100];
int top=0;
p=root;
while((p!=NULL)||(top>0))
{
while(p!=NULL)
{
cout<<p->data<<" ";
s[++top]=p;
p=p->lchild;
}
p=s[top--];
p=p->rchild;
}
}
//中序遍歷二叉樹
void bitree::inorder(bitree *root)
{bitree *p,*s[100]; //s為一個棧，top為棧頂指針
int top=0;
p=root;
while((p!=NULL)||(top>0))
{
while(p!=NULL)
{
s[++top]=p; //進棧
p=p->lchild;
} //進入左子樹
{p=s[top--]; //退棧
cout<<p->data<<" ";
p=p->rchild; //進入右子樹
}
}
}
//後序遍歷二叉樹
void bitree::postorder(bitree *root)
{
bitree *p,*s1[100]; //s1棧存放樹中結點
int s2[100],top=0,b; //s2棧存放進旁喚棧標志
p=root;
do
{ while(p!=NULL)
{s1[top]=p;s2[top++]=0; //第一次進棧標志為0
p=p->lchild;} //進入左子樹
if(top>0)
{b=s2[--top];
p=s1[top];
if(b==0)
{s1[top]=p;s2[top++]=1; //第二次進棧標志為1
p=p->rchild;} //進入右子樹
else
{cout<<p->data<<" ";
p=NULL;
} }
}while(top>0);}
void main()
{ bitree *root=NULL;
cout<<"請輸入二叉樹的根: ";
root=root->creat();
cout<<"先跟遍歷的順序是:";root->preorder(root);cout<<endl;
cout<<"中跟遍歷的順序是:";root->inorder(root);cout<<endl;
cout<<"後跟遍歷的順序是:";root->postorder(root);cout<<endl;
}
//輸入ab,,c,,,,d#回車鍵
❻ 用棧的順序存儲結構實現棧的各種基本操作
一、順序棧
棧的順序存儲結構簡稱為順序棧，它是運算受限的順序表。因此，可用數組來實現順序棧。
因為棧底位置是固定不變的，所以可以將棧底位置設置在數組的兩端的任何一個端點；
棧頂位置是隨著進棧和退棧操作而變化的.
棧的順序存儲表示 — 順序棧
#include <assert.h>
template <class Type> class Stack {
private:
int top; //棧頂數組指針
Type *elements; //棧數組
int maxSize; //棧最大容量
public:
Stack ( int=10 ); //構造函數
~Stack ( ) {
delete[ ] elements;
}//析構函數
void Push ( const Type & item ); //入棧
Type Pop ( ); //出棧
Type GetTop ( ); //取棧頂元素
void MakeEmpty ( ) { top=-1; } //置空棧
int IsEmpty ( ) const {
return top == -1;
}
int IsFull ( ) const{
return top == maxSize-1;
}
}
void Push ( const Type & item ); //入棧
Type Pop ( ); //出棧
Type GetTop ( ); //取棧頂元素
void MakeEmpty ( ) { top=-1; } //置空棧
int IsEmpty ( ) const {
return top == -1;
}
int IsFull ( ) const {
return top == maxSize-1;
}
}
構造函數
template <class Type> Stack<Type>::
Stack ( int s ) : top (-1), maxSize (s) {
elements = new Type[maxSize];
}
template <class Type> void Stack<Type>::
Push ( const Type & item ) {
assert ( !IsFull ( ) );或//先決條件斷言
if(top != maxSize-1 )
elements[++top] = item; //加入新元素
}
template <class Type> Type Stack<Type>:: Pop ( ) {
assert ( !IsEmpty ( ) ); //先決條件斷言
return elements[top--]; //退出棧頂元素
}
template <class Type> Type stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) ); //先決條件斷言
return elements[top]; //取出棧頂元素
}
❼ 數據結構試驗~~實驗三、棧的操作
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW 2
#define OK 1
typedef int SElemType;
typedef int Status;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status ChuShihua(SqStack &S)
{
int n;
printf("請輸入數據以-1結束\n");
while(scanf("%d",&n),n!=-1)
*S.top++=n;
return OK;
}
Status Push(SqStack &S)
{
int e;
printf("請輸入要壓入的元素：含衫");
scanf("%d",&e);
if(S.top-S.base>=S.stacksize){
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S)
{
printf("談友腔出棧元素為：");
if(S.top!=S.base)
printf("%d\n",*--S.top);
return 0;
}
void tishi()
{
printf("所有操作如下：\n");
printf("（1）採用順序存儲實現棧的初始化操作。\n");
printf("（2）採用順序存儲實現棧的入棧操作。\n");
printf("（3）採用順序存儲告橡實現棧的出棧操作。\n");
printf("（-1）退出\n");
printf("請選擇：");
}
int main()
{ int m;
SqStack s;
InitStack(s);
do{
tishi();
scanf("%d",&m);
switch(m)
{
case 1:
ChuShihua(s);
break;
case 2:
Push(s);
break;
case 3:
Pop(s);
break;
}
}while(m!=-1);
return OK;
}