❶ 栈的存储结构
栈同顺序表和链表一样，栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构。
栈的具体实现
栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：
顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
链栈：采用链式存储结构实现栈结构；
栈存储结构与之前所学的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：
栈只能从表的一端存取数据，另一端是封闭的；
在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。
❷ 栈、队列的操作
先解答第一题：
#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;
}