实验三栈

实验三 线性表的应用—栈操作

[ 实验日期 ] 2012 年 10 月 12 日

学号：10131504 专业年级：石工10-15 姓名：于秀玲

一、目的和要求

1．熟悉并掌握栈的逻辑结构定义、特点。 2．熟悉并掌握栈的顺序与链式两种存储方式。

3．熟悉并掌握栈的基本操作：栈的建立，访问栈顶元素，进栈、出栈等。

注意：标明实现的是顺序栈还是链栈。 二、实验内容

（详细说明栈操作的各个函数头的说明） 顺序栈

该程序共有9个函数，8个子函数和1个主函数。可以实现本程序建立了长度为100的学生信息顺序栈，通过输入不同的操作选项1、2、3，可以实现元素的多次入栈、出栈、访问栈顶元素、判断栈空。下面对各个函数进行说明：

1、 struct student定义结构体，该结构体包含 name、sex、age、score四项，数据类型b即为

该结构体类型，可以用b定义新的变量，作为结点的一项。

2、 typedef struct node用结构体定义结点类型SeqStack，结点包含学生信息和栈顶、栈底3

项。可以用SeqStack定义新的结点。

3、void makempty(SeqStack *S) 建立一个空顺序栈S来存储学生信息，并对栈进行初始化。 4、int empty(SeqStack *S) 判断栈S是否为空，通过对栈顶指针的数值是否为-1，来进行判断的，并返回判别标志：1栈空，0栈不为空。

5、void insertyuansu() 输入要入栈的元素b，通过printf提示用户输入学生信息，由scanf完成信息的输入。

6、int push(SeqStack *S) 学生信息b入栈。先判断是否栈满，若栈满返回0，否则b入栈，调用insertyuansu() 输入要入栈的元素b，然后对s赋值，栈顶指针后移。

7、int pop(SeqStack *S) 顺序栈S栈顶元素出栈，先判断栈是否为空，若栈空返回0作为识别标志，否则栈顶指针后移，栈顶元素出栈。

8、int gettop(SeqStack *S,struct student *m) 读取顺序栈S栈顶元素，并将栈顶元素赋给m。 9、void print(struct student *m) 输出顺序栈S栈顶元素m。

10、void menu()菜单函数，指导用户选择想要进行的操作，输入1-4不同的数字，会进行对应的不同的操作。

11、void main()是主函数实现对子函数的调用。通过输入的不同数字，调用相应的函数。 链栈

该程序共有5个函数，4个子函数、1个主函数，可以实现对链栈的创建，入栈、出栈、判

断栈是否为空等操作。下面对各个函数进行说明：

1、typedef struct Node 用结构体定义结点，该结点有数据域data和指针域Node *next组成。StackNode为结点类型，可以用来定义变量。

2、StackNode *Creat()是创建头节点函数。定义头结点，申请空间，初始化，并返回指向头结点的指针。

3、void Push(StackNode *s)利用头插法创建链表，可以连续插入多个数据，以-1作为判别标志，运用while循环，定义头结点，申请空间，对结点赋值。

4、void Empty(StackNode *s)判断是否栈空，通过头结点s的指针域是否为空来判断栈是否为空。

5、int Pop(StackNode *s)是出栈函数，若栈空会提示不可再出栈，否则输出栈顶元素,指针移动将出队元素移出队，并释放空间。

6、void main()是主函数实现对子函数的调用。

三、实验环境

1．硬件：PC机。 2．软件：DOS 、Windows9.x 、Window2000或以上版本，TurboC 2.0 及以上版本或VC6.0。

四、源程序

顺序栈

#include #define Max 100 struct student {

char name[10]; char sex[10]; int age; int score; }b;

typedef struct node {

struct student information[M]; int top,bot; }SeqStack; SeqStack S;

void makempty(SeqStack *S) {

(*S).bot=0; (*S).top=-1; }

int empty(SeqStack *S) {

if(S->top==-1) return 1; else return 0; }

void insertyuansu() {

printf(\"请输入姓名,性别,年龄,分数\\n\"); scanf(\"%s\ scanf(\"%s\ scanf(\"%d\ scanf(\"%d\}

int push(SeqStack *S) {

if((*S).top==(M-1)) return 0; else {

insertyuansu(); (*S).top++;

(*S).information[(*S).top]=b; return 1; } }

int pop(SeqStack *S) {

if(empty(S)) return 0; else {

(*S).top--; return 1; } }

int gettop(SeqStack *S,struct student *m) {

if(empty(S)) return 0; else {

*m=S->information[(*S).top]; return 1; } }

void print(struct student *m) {

printf(\"栈顶元素信息为 \\n\"); printf(\" 学生姓名 \"); puts((*m).name);

printf(\" 学生性别 \"); puts((*m).sex);

printf(\" 学生年龄 \"); printf(\"%d\\n\ printf(\" 学生得分 \");

printf(\"%d\\n\ printf(\"\\n\"); }

void menu() {

printf(\" 选择选项对应相应操作\\n\");

printf(\" 入栈 ************ 1\\n\"); printf(\" 出栈 ************ 2\\n\"); printf(\" 访问栈顶元素 ************ 3\\n\"); printf(\" 结束操作 ************ 4\\n\"); }

void main() {

int xuanze;

struct student m; makempty(&S); menu(); while(1) {

printf(\"\\n输入操作选项\\n\"); printf(\"操作选项为\"); scanf(\"%d\ if(xuanze==1) {

if(push(&S)) printf(\"入栈成功\\n\"); else printf(\"栈满溢出，入栈失败\\n\"); }

if(xuanze==2) {

if(pop(&S)) printf(\"出栈成功\\n\"); else printf(\"栈空，出栈失败\\n\"); }

if(xuanze==3) {

if(gettop(&S,&m)) {

printf(\"访问栈顶元素成功\\n\"); print(&m); }

else printf(\"栈空，访问栈顶元素失败\\n\"); }

if(xuanze==4) break; } } 链栈

#include #include typedef struct Node { int data; struct Node *next; }StackNode;

StackNode *Creat()//创建头节点 { StackNode *top; top=(StackNode *)malloc(sizeof(StackNode)); top->next=NULL; return top; }

void Push(StackNode *s)//创建，头插法 { StackNode *p; int x; printf(\"输入数据，以-1结束: \"); scanf(\"%d\ while(x!=-1) { p=(StackNode *)malloc(sizeof(StackNode)); p->data=x; p->next=s->next; s->next=p;

printf(\"输入下一个数据: \"); scanf(\"%d\ } }

void Empty(StackNode *s)//判断是否栈空 { if(s->next==NULL) printf(\"该栈为空！\"); else printf(\"该栈不为空\"); }

int Pop(StackNode *s)//出栈 { int *y; StackNode *p; if(s->next==NULL) { printf(\"该栈为空，不可出栈！\"); return 0; } else { *y=s->next->data;//传回栈顶结点的数据 printf(\"%d\ p=s->next; s->next=p->next;

free(p);

return 1; } }

void main() { StackNode *top; top=Creat(); Push(top); Pop(top); }