用栈将线性表逆置实验

《用栈将线性表逆置实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计题实验2栈一、实验的目的要求1、了解栈的特性，以及它在实际问题中的应用。2、掌握栈的实现方法以及它的基本操作，学会运用栈来解决问题。二、实验的主要内容1、已知head是带头结点的单链表（a1,a2,…,an）（其中n>=0）,有关说明如下：typedefintdatatype;#include#defineNULL0typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head;请设计一个算法，利用一个栈将上述单链表实现逆置，即利用一个栈将单链表（a1,a2,…,an）

2、（其中n>=0）逆置为（an,an-1,…，a1）。调试运行实例：⑴含多个结点的顺序表（2，4，6，8，10）；⑵含一个结点的顺序表（5）；⑶空表（）。三、栈的特性1、栈（Stack）是限定在表尾进行插入和删除操作的线性表。其表尾称为栈顶(top)，表头称为栈底(bottom)。栈的特点是后进先出（LastInFirstOut）。出栈入栈栈顶an┇a3a2栈底a17图2.1栈的示意图2、栈的基本操作和线性表类似，栈也有两种存储结构，即顺序栈和链栈。⑴顺序栈可以定义为#definemaxsize100/*栈的最大元素数为100*/typedefstruct/*定义顺序栈*/{dat

3、atyped[maxsize];inttop;}seqstack;seqstack*s;/*定义顺序栈的指针*/顺序栈的基本操作如下：①栈的初始化（建立一个空栈）voidInitStack(seqstack*s)/*构造一个空栈s*/{s->top=-1;}②入栈操作seqstack*push(seqstack*s,datatypex)/*入栈*/{if(s->top==maxsize-1){printf(“栈已满，不能入栈！”)；returnNULL;}else{s->top++;/*栈顶指针上移*/s->d[s->top]=x;/*将x存入栈中*/returns;}}③出

4、栈函数datatypepop(seqstack*s)/*出栈*/{datatypey;if(s->top==-1){printf(“栈为空，无法出栈！”)；return0;}else{y=s->d[s->top];/*栈顶元素出栈，存入y中*/s->top--;/*栈顶指针下移*/returny;}7}④判栈空函数intStackEmpty(seqstack*s){if(s->top==-1)return1;/*栈为空时返回1（真）*/elsereturn0;/*栈非空时返回0（假）*/}⑵链栈可以定义为#defineNULL0typedefstructnode/*定义链栈结

5、点类型*/{datatypedata;structnode*next;}linkstack;linkstack*top;/*定义栈顶指针*/链栈的基本操作如下：①栈的初始化（建立一个空栈）voidinit_linkstack(linkstack*top){top=NULL;}②入栈操作linkstack*push_linkstack(linkstack*top,datatypex){linkstack*p;p=(linkstack*)malloc(sizeof(linkstack));/*开辟新结点*/p->data=x;p->next=top;top=p;returntop;}

6、③出栈函数datatypepop_linkstack(linkstack*top)/*出栈*/{datatypey;linkstack*p;if(top==NULL){printf(“栈为空，无法出栈！”)；return0;}else{p=top;y=top->data;/*栈顶元素出栈，存入y中*/top=top->next;/*栈顶指针下移*/free(p);/*释放存储空间*/7returny;}}④判栈空函数intempty_linkstack(linkstack*top){if(top==NULL)return1;/*栈为空时返回1（真）*/elsereturn0;

7、/*栈非空时返回0（假）*/}一、解题思路方法1（将链表结点中的数据入栈，用顺序栈实现）1、建立一个带头结点的单链表head；2、输出该单链表；3、建立一个空栈s；4、依次将单链表的数据入栈；5、依次将单链表的数据出栈，并逐个将出栈的数据存入单链表的数据域（自前向后）;6、再输出单链表。程序如下(采用顺序栈实现)：7typedefintdatatype;#include#defineNULL0#definemaxsize100/*设栈的最大元素数为100*/ty