用顺序结构表示栈并实现栈的各种基本操作

1、栈的顺序表示和实现 2.2基础实验 2.2.1实验目的 (1) 掌握栈的顺序表示和实现 (2) 掌握栈的链式表示和实现 (3) 掌握队列的顺序表示和实现 (4) 掌握队列的链式表示和实现 2.2.2实验内容 实验一：栈的顺序表示和实现 【实验内容与要求】 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能: (1) 初始化顺序栈 (2 )插入元素 (3) 删除栈顶元素 (4) 取栈顶元素 (5) 遍历顺序栈 (6) 置空顺序栈 【知识要点】 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p-top= =M

2、AXNUM-1 ，栈满时，不能入 栈；否则岀现空间溢岀，引起错误，这种现象称为上溢。 岀栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转 移的条件。 注意： (1) 顺序栈中元素用向量存放 (2) 栈底位置是固定不变的，可设置在向量两端的任意一个端点 (3) 栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top (通常称top为栈顶指针)来指示当 前栈顶位置 【实现提示】 /*定义顺序栈的存储结构*/ typedef struct ElemType stackMAXNUM; int top; SqStack; /*初始化顺序栈函数*/ void ln

3、itStack(SqStack *p) q=(SqStack*)malloc(sizeof(SqStack)/* 申请空间 */) /*入栈函数*/ void Push(SqStack *p,ElemType x) if(p-toptop=p-top+1;/* 栈顶 +1*/ p-stackp-top=x; /* 数据入栈 */ /*岀栈函数*/ ElemType Pop(SqStack *p) x=p-stackp-top; /* 将栈顶元素赋给 x*/ p-top=p-top-1; /* 栈顶-1*/ /*获取栈顶元素函数*/ ElemType GetTop(SqStack *p) x=p

4、-stackp-top; /*遍历顺序栈函数*/ void OutStack(SqStack *p) for(i=p_top;i=O;i_) printf(第 %d 个数据元素是：%6dn,i,p-stacki); /*置空顺序栈函数*/ void setEmpty(SqStack *p) p-top= -1; 【参考程序】 #include #include #define MAXNUM 20 #define ElemType int /*定义顺序栈的存储结构*/ typedef struct ElemType stackMAXNUM; int top; SqStack; /*初始化顺序栈*

5、/ void InitStack(SqStack *p) if(!p) printf(Eorror); p-top=-1; /*入栈*/ void Push(SqStack *p,ElemType x) if(p-toptop=p_top+1; p-stackp-top=x; else printf(Overflow!n); /*出栈*/ ElemType Pop(SqStack *p) ElemType x; if(p-top!=0) x=p-stackp-top; printf(以前的栈顶数据元素 %d已经被删除！n,p-stackp-top); p-top=p-top-1; return

6、(x); else printf(Underflow!n); return(O); /*获取栈顶元素*/ ElemType GetTop(SqStack *p) ElemType x; if(p-top!=0) x=p-stackp-top; return(x); else printf(Underflow!n); return(0); /*遍历顺序栈*/ void OutStack(SqStack *p) int i; printf(n); if(p-toptop;i=0;i_) printf(第%d 个数据元素是：%6dn,i,p-stacki); /*置空顺序栈*/ void setEm

7、pty(SqStack *p) p-top= -1; /*主函数*/ main() SqStack *q; int y,cord;ElemType a; do printf(n); printf(”第一次使用必须初始化！n); printf(n); printf(n 主菜单 n printf(n 1 初始化顺序栈 n); printf(n 2 插入一个元素 n); printf(n 3 删除栈顶元素 n); printf(n 4 取栈顶元素 n); printf(n 5 置空顺序栈 n); printf(n 6 结束程序运行 n); printf(nn); printf(请输入您的选择(1,2

8、, 3, 4, 5,6); scanf(%d, printf(n); switch(cord) case 1: q=(SqStack*)malloc(sizeof(SqStack); InitStack(q); OutStack(q); break; case 2: printf(请输入要插入的数据元素：a=); scanf(%d, Push(q,a); OutStack(q); break; case 3: Pop(q); OutStack(q); break; case 4: y=GetTop(q); printf(n 栈顶元素为：%dn,y); OutStack(q); break; c

9、ase 5: setEmpty(q); printf(n顺序栈被置空！n); OutStack(q); break; case 6: exit(0); while (cordtop=NULL; /*链栈置空函数*/ void setEmpty(LinkStack * s) s-top=NULL; /*入栈函数*/ void pushLstack(LinkStack * s, Elemtype x) p=(StackNode *)malloc(sizeof(StackNode); / 建立一个节点。 p_data=x; p-next=s-top;/ 指向栈顶。 s-top=p;插入 /*岀栈函数

10、*/ Elemtype popLstack(LinkStack * s) x=p_data; s-top=p-next;/当前的栈顶指向原栈的next free(p);/ 释放 /*取栈顶元素函数*/ Elemtype StackTop(LinkStack *s) return s-top-data; /*遍历链栈函数*/ void Disp(LinkStack * s) while (p!=NULL) printf(%dn,p-data); p=p-next; 【参考程序】 #include stdio.h #include malloc.h #include stdlib.h typede

11、f int Elemtype; typedef struct stacknode Elemtype data; stacknode * next; StackNode; typedef struct stacknode * top; / 栈顶指针 LinkStack; /*初始化链栈*/ void lnitStack(LinkStack * s) s-top=NULL; printf(n已经初始化链栈！n); /*链栈置空*/ void setEmpty(LinkStack * s) s-top=NULL; printf(n 链栈被置空！ n); /*入栈*/ void pushLstack(

12、LinkStack * s, Elemtype x) StackNode * p; p=(StackNode *)malloc(sizeof(StackNode); / 建立一个节点。 p_data=x; p-next=s-top; /由于是在栈顶pushLstack,所以要指向栈顶。 s-top=p;插入 /*出栈*/ Elemtype popLstack(LinkStack * s) Elemtype x; StackNode * p; p=s-top;/指向栈顶 if (s-top =0) printf(n栈空，不能出栈！ n); exit(-1); x=p-data; s-top=p-

13、next;/当前的栈顶指向原栈的next free(p);/ 释放 return x; /*取栈顶元素*/ Elemtype StackTop(LinkStack *s) if (s-top =0) printf(n 链栈空 n); exit(-1); return s-top-data; /*遍历链栈*/ void Disp(LinkStack * s) printf(n链栈中的数据为：n); printf(=n); StackNode * p; p=s-top; while (p!=NULL) printf(%dn,p-data); p=p_next; printf(=n); void m

14、ain() printf(=链栈操作=nn); int i,m,n,a; LinkStack * s; s=(LinkStack *)malloc(sizeof(LinkStack); int cord; do printf(n); printf(第一次使用必须初始化！n); printf(n); printf(n 主菜单 n printf(n 1 初始化链栈 n); printf(n 2 入栈 n); printf(n 3 出栈 n); printf(n 4 取栈顶元素 n); printf(n 5 置空链栈 n); printf(n 6 结束程序运行 n); printf(nn); pri

15、ntf(请输入您的选择(1,2, 3, 4, 5,6); scanf(%d, printf(n); switch(cord) case 1: InitStack(s); Disp(s); break; case 2: n=); printf(”输入将要压入链栈的数据的个数: scanf(%d, printf(依次将%d个数据压入链栈：n,n); for(i=1;i=n;i+) scanf(%d, pushLstack(s,a); Disp(s); break; case 3: printf(n出栈操作开始!n); printf(输入将要出栈的数据个数：m=); scanf(%d, for(i=

16、1;i=m;i+) printf(n 第 %d 次出栈的数据是：%d,i,popLstack(s); Disp(s); break; case 4: printf(nn 链栈的栈顶元素为：dn,StackTop(s); printf(n); break; case 5: setEmpty(s); Disp(s); break; case 6: exit(0); while (cordfront=_1; q-rear=-1; /*入队函数*/ int append(sqqueue *q, Elemtype x) q-rea r+; q_queueq_rear=x; /*出队函数*/ Elemty

17、pe Delete(sqqueue *q) x=q_queue+q_front; /*判断队列是否为空函数*/ int Empty(sqqueue *q) if (q-front=q-rear) return TRUE; /*取队头元素函数*/ int gethead(sqqueue *q) return(q-queueq-front+1); /*遍历队列函数*/ void display(sqqueue *q) while(srear) s=s+1; printf(%dqueues); /*建立顺序队列函数*/ void Setsqqueue(sqqueue *q) for (i=0;in;

18、i+) /*利用循环快速输入数据*/ scanf(%d, append(q,m); /*利用入队函数快速输入数据*/ 【参考程序】 #include #include #define MAXNUM 100 #define Elemtype int #define TRUE 1 #define FALSE 0 typedef struct Elemtype queueMAXNUM; int front; int rear; sqqueue; /*队列初始化*/ int initQueue(sqqueue *q) if(!q) return FALSE; q-front=-1; q-rear=-1

19、; return TRUE; /*入队*/ int append(sqqueue *q, Elemtype x) if(q-rear=MAXNUM-1) return FALSE; q-rea 叶+; q_queueq_rear=x; return TRUE; /*出队*/ Elemtype Delete(sqqueue *q) Elemtype x; if (q-front=q-rear) return 0; x=q_queue+q_front; return x; /*判断队列是否为空*/ int Empty(sqqueue *q) if (q-front=q-rear) return T

20、RUE; return FALSE; /*取队头元素*/ int gethead(sqqueue *q) if (q-front=q-rear) return 0; return(q-queueq-front+1); /*遍历队列*/ void display(sqqueue *q) int s; s=q-front; if (q-front=q-rear) printf(队列空!n); else printf(n顺序队列依次为：”)； while(srear) s=s+1; printf(%dqueues); printf(n); printf(顺序队列的队尾元素所在位置 ：rear=%dn,q-rear); printf(顺序队列的队头元素所在位置 :front=%dn,q-front); /*建立顺序队列*/ void Setsqqueue(sqqueue *q) int n,i,m; printf(n请输入将要入顺序队列的长度:); scanf(%d, printf(n请依次输入入顺序队列的元素值:n); for (i=0;in;i+) scanf(%d, append(q,m); main() sqqueue *head; int x,y,z,select; head=(sqqueu