连接存储的栈
Ⅰ 麻烦高手帮写一个C语言连接存储一个是栈一个是队列
栈
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status ;
typedef int ElemType;
struct STACK
{
ElemType *base;
ElemType *top;
int stacksize;
};
typedef struct STACK SqStack;
//typedef struct STACK *pSqstack;
//函数声明
Status InitStack(SqStack &S);
void DestroyStack(SqStack &S);
void ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,ElemType &e);
Status Push(SqStack &S,ElemType e);
Status Pop(SqStack &S,ElemType &e);
//初始化
Status InitStack(SqStack &S)
{
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
//销毁栈
void DestroyStack(SqStack &S)
{
free(S.base);
}
//清空栈
void ClearStack(SqStack &S)
{
S.top=S.base;
}
//判栈空
Status StackEmpty(SqStack S)
{
if(S.top==S.base) return TRUE;
else
return FALSE;
}
//求栈中元素个数
int StackLength(SqStack S)
{
int i;
ElemType *p;
i=0;
p=S.top;
while(p!=S.base)
{p--;
i++;
}
return i;
}
//获取栈顶元素值
Status GetTop(SqStack S,ElemType &e)
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
//入栈
Status Push(SqStack &S,ElemType e)
{
if(S.top - S.base>=S.stacksize)
{
S.base=(ElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize += STACKINCREMENT;
}
*(S.top++)=e;
return OK;
}
//出栈
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
//逆序打印栈中元素
void PrintElem(SqStack S)
{
ElemType e;
if(S.top==S.base) cout<<"该栈为空栈.";
else
while(S.top!=S.base)
{
Pop(S,e);cout<<e<<ends;
}
cout<<endl;
}
//进制转换函数
void conversion()
{
SqStack S;
ElemType e;
char b[17]="0123456789ABCDEF";
int n,r;
InitStack(S);
cout<<"Input a number to convert to :\n";
cin>>n;
cout<<"请输入要转换的进制：";
cin>>r;
if(n<0)
{
cout<<"\nThe number must be over 0.";
return;
}
if(!n) Push(S,0);
while(n){
Push(S,n%r);
n=n/r;
}
cout<<"the result is: ";
while(!StackEmpty(S)){
Pop(S,e);
cout<<b[e];
}
cout<<endl;
}
void main()
{
ElemType e;
SqStack Sa;
cout<<"\n\n-------------------SqStack Demo is running...----------------\n\n";
cout<<"First is Push function.\n";
InitStack(Sa);
cout<<" Now Stack is Empty.\n";
cout<<"请输入第一个要入栈的元素值：";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has one element.\n";
PrintElem(Sa);
cout<<"请输入第二个要入栈的元素值：";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has another element.\n";
PrintElem(Sa);
int n;
cout<<"请输入还要入栈的元素个数:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\n请输入第"<<i+2<<"个元素：";
cin>>e;
Push(Sa,e);
}
cout<<"\n Now Pop Stack,the top elem put into variable e.\n";
Pop(Sa,e);
cout<<e<<endl;
cout<<" Let's see the left of Stack's elem:\n";
PrintElem(Sa);
cout<<"现在栈中元素个数为："<<StackLength(Sa);
cout<<endl;
getch();
cout<<"进制转换演示：\n";
conversion();
}
队列
#include <iostream.h>
#include <malloc.h>
typedef int QElemType;
typedef int Status;
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define MaxQsize 100 /*最大队列长度*/
typedef struct {
QElemType *base; /*初始化的动态分配存储空间*/
int front; /*头指针，若队列不空，指向队列头元素*/
int rear; /*尾指针，若队列不空，指向队列尾元素的下一个位置*/
}SqQueue;
Status InitQueue(SqQueue &Q){
/*构造一个空队列Q*/
Q.base=(QElemType *)malloc(MaxQsize*sizeof(QElemType));
if(!Q.base) return ERROR;/*存储分配失败*/
Q.front=Q.rear=0;
return OK;
}
Status QueueEmpty(SqQueue Q){
/*若队列Q为空队列，则返回TRUE，否则返回FALSE*/
if(Q.front==Q.rear) return TRUE;
else return FALSE;
}
int QueueLength(SqQueue Q){
/*返回Q的元素个数，即为队列的长度*/
return(Q.rear-Q.front+MaxQsize)% MaxQsize;
}
Status GetHead(SqQueue Q,QElemType &e){
/*若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERROR*/
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e){
/*插入元素e为Q的新的队尾元素*/
if((Q.rear+1)%MaxQsize==Q.front) return ERROR;/*队列满*/
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MaxQsize;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e){
/*若队列不空，则删除Q的队头元素，用e返回其值，并返回OK,否则返回ERROR*/
if(Q.rear==Q.front) return ERROR;/*队列空*/
e=Q.base[Q.front];
Q.front=(Q.front+1)%MaxQsize;
return OK;
}
void main(){
SqQueue Q;
int select;
QElemType e;
if (InitQueue(Q)==ERROR)
cout<<"分配失败，即将退出程序！\n";
else/*否则显示队列操作的菜单，并选择相应的基本操作*/
do {
cout<<"1：判断队列是否为空\n";
cout<<"2：测试队列的长度\n" ;
cout<<"3：取队头元素值\n";
cout<<"4：向队列中插入一新元素\n";
cout<<"5：删除队列中一元素\n";
cout<<"0：结束\n";
cout<<"\n请输入您的选择：";
cin>>select;
cout<<endl;
switch (select) {
case 1:
if (QueueEmpty(Q)==TRUE) cout<<"队列为空\n";
else cout<<"队列不为空\n";break;
case 2:
cout<<"队列长度为："<<QueueLength(Q)<<endl;break;
case 3:
if(GetHead(Q,e)==ERROR) cout<<"队列为空\n";
else cout<<"队首元素为："<<e<<endl;break;
case 4:
cout<<"请输入要插入的元素值：";
cin>>e;
if(EnQueue(Q,e)==ERROR) cout<<"\n队列满\n";
else cout<<"\n元素成功插入\n";break;
case 5:
if(DeQueue(Q,e)==ERROR) cout<<"队列空,无数据可删\n";
else cout<<"删除元素为："<<e;break;
case 0:
cout<<"操作结束\n";break;
default:
cout<<"输入选择出错！\n";
}/*switch*/
cout<<endl<<endl;
}while (select);
}/*main_end*/
Ⅱ 栈的链式存储
#include<stdio.h>
#include<stdlib.h>
#define
elemtype
int
#define
MAXSIZE
100
typedef
struct
stack{
elemtype
elem;
struct
stack
*next;
}STACK;
//链式存储的栈结构，及其相应算法
void
InitStack(STACK
*top)
{//初始化空栈
top->next=NULL;
}
void
DestroyStack(STACK
*top)
{//销毁栈，将栈所占内存空间释放
STACK
*p;
p=top->next;
while(p!=NULL){
top->next=p->next;
free(p);
p=top->next;
}
}
int
EmptyStack(STACK
*top)
{//判断是否栈空，为空则返回1，否则返回0
if(top->next==NULL){
return
1;
}
else{
return
0;
}
}
int
push(STACK
*top,
elemtype
x)
{//元素x进栈操作，成功返回1，否则返回0
STACK
*p;
p=(STACK
*)malloc(sizeof(STACK));
p->elem=x;
p->next=top->next;
top->next=p;
return
1;
}
elemtype
pop(STACK
*top)
{//出栈操作，返回出栈元素
if(EmptyStack(top)){
printf("栈为空");
return
0;
}
else{
elemtype
x;
STACK
*p;
p=top->next;
x=p->elem;
top->next=p->next;
free(p);
p=top->next;
return
x;
}
}
void
Print(STACK
*top)
{//依次输出栈顶到栈底的所有元素
STACK
*h;
h=top->next;
while(h!=NULL){
printf("%4d",h->elem);
h=h->next;
}
}
int
main(void)
{
STACK
*top=NULL;
top=(STACK
*)malloc(sizeof(STACK));
InitStack(top);
push(top,1);
push(top,2);
push(top,4);
Print(top);
push(top,5);
Print(top);
pop(top);
Print(top);
DestroyStack(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;
}
Ⅳ 什么叫存栈
关栈是海关的一种保税制度，通常是指经海关准予注册用以存储保税货物的仓版库或场所。在清季，保税关权栈是由商人自立栈房（码头仓栈）改设的。关栈与商栈同是存储货物之所，其不同之处在于：关栈所存为未经通关的保税待纳货物，而商栈所存则为业经通关的已税货物。关栈保税，本是中国所无，亦不载于不平等条约。其请设和开办经历了长期抗争与骤然让与的矛盾过程，斗争焦点是外国栈房准作关栈抑或中国自办关栈。
Ⅳ 链栈和顺序栈两种存储结构有什么不同
存储结构不同：来
链栈动自态分配内存存储数据，不浪费内存，存储的数据不连续。
顺序栈使用固定大小数组保存数据，数据量小时浪费内存，过多时出问题，存储数据连续。
它们的具体区别如下：
顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用光而引起的溢出问题。在系统将内存分配给数组后，则这些内存对于其他任务就不可用。而对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间开始，另外当某个项不使用时也可将内存返还给系统。
Ⅵ C语言链式存储栈的建栈、入栈、出栈、打印
你在main里调用InitStack初始化栈，后面就可以Push Pop进出了
Ⅶ 栈的链式存储结构--出栈操作
#include
#include
#define
elemtype
int
#define
maxsize
100
typedef
struct
stack{
elemtype
elem;
struct
stack
*next;
}stack;
//链式存储的栈结构，及其相应算法
void
initstack(stack
*top)
{//初始化空栈
top->next=null;
}
void
destroystack(stack
*top)
{//销毁栈，将栈所占内存空间释放
stack
*p;
p=top->next;
while(p!=null){
top->next=p->next;
free(p);
p=top->next;
}
}
int
emptystack(stack
*top)
{//判断是否栈空，为空则返回1，否则返回0
if(top->next==null){
return
1;
}
else{
return
0;
}
}
int
push(stack
*top,
elemtype
x)
{//元素x进栈操作，成功返回1，否则返回0
stack
*p;
p=(stack
*)malloc(sizeof(stack));
p->elem=x;
p->next=top->next;
top->next=p;
return
1;
}
elemtype
pop(stack
*top)
{//出栈操作，返回出栈元素
if(emptystack(top)){
printf("栈为空");
return
0;
}
else{
elemtype
x;
stack
*p;
p=top->next;
x=p->elem;
top->next=p->next;
free(p);
p=top->next;
return
x;
}
}
void
print(stack
*top)
{//依次输出栈顶到栈底的所有元素
stack
*h;
h=top->next;
while(h!=null){
printf("%4d",h->elem);
h=h->next;
}
}
int
main(void)
{
stack
*top=null;
top=(stack
*)malloc(sizeof(stack));
initstack(top);
push(top,1);
push(top,2);
push(top,4);
print(top);
push(top,5);
print(top);
pop(top);
print(top);
destroystack(top);
}
Ⅷ 栈的链式存储结构是什么
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存专储结构。人们将用链式属存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入、删除操作只能在一端进行，而对于单链表来说，在首端插入、删除结点要比在尾端进行相对容易一些，所以将单链表的首端作为栈的顶端，即将单链表的头指针作为栈顶指针。链栈如图1所示。
图1链栈的存储示意
Ⅸ 栈的两种存储表示方法
栈的存储结构
顺序栈
和线性表类似，堆栈也有两种基本的存储结构：版顺序存储结构和链权式存储结构。
顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。
由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选择线性表的一端作为栈顶即可。
根据数组操作的特性，选择数组下标大的一端，即线性表顺序存储的表尾来作为栈顶，此时入栈、出栈等操作可以在Ο(1)时间完成。
由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的指示栈顶元素在数组中的位置。
通常 top 可以用栈顶元素所在数组下标来表示，top= -1 时表示空栈。
链栈
链栈即采用链表作为存储结构实现的栈。
当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。
由于堆栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可以。
使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；
使用不带头结点的单链表时，结点的插入和删除都在链表的首结点上进行。
Ⅹ 栈的顺序存储和链表存储的差异
顺序存储： 线性表的顺序表：指的是用一组地址连续的存储单元，依次存储线性表的数据元素。
线性表的顺序存储结构具备如下两个基本特征： 1、线性表中的所有元素所占的存储空间是连续的（即要求内存中可用存储单元的地址必须是连续的）。 2、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 即：线性表逻辑上相邻、物理也相邻（逻辑与物理统一：相邻数据元素的存放地址也相邻），则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。 优点： 1、
无须为表示结点间的逻辑关系而增加额外的存储空间。
2、
可以方便的随机存取表中的任一结点。
3、
存储密度大（＝1），存储空间利用率高。 缺点： 1、
插入和删除运算不方便，需移动大量元素。 2、
由于要求占用连续的存储空间，存储分配只能按最大存储空间预先进行，致使存储空间不能得到充分利用。
3、
表的容量难以扩充。 链表存储： 线性表的链式存储：指用一组任意的存储单元存储线性表中的数据元素。
线性表的链式存储结构具备的基本特征： 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点： 1、
插入、删除操作很方便，可通过修改结点的指针实现，无须移动元素。
2、
方便扩充存储空间。
缺点： 1、
不能随机存取元素。
2、
存储密度小（<1），存储空间利用率低。 总结： 1、
顺序表适宜于做查找这样的静态操作；
链表宜于做插入、删除这样的动态操作。 2、若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。