用栈将线性表逆置实验

用栈将线性表逆置实验

ID:14161867

大小:76.00 KB

页数:7页

时间:2018-07-26

用栈将线性表逆置实验_第1页
用栈将线性表逆置实验_第2页
用栈将线性表逆置实验_第3页
用栈将线性表逆置实验_第4页
用栈将线性表逆置实验_第5页
资源描述:

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

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

2、利用一个栈将单链表(a1,a2,…,an)(其中n>=0)逆置为(an,an-1,…,a1)。调试运行实例:⑴含多个结点的顺序表(2,4,6,8,10);⑵含一个结点的顺序表(5);⑶空表()。三、栈的特性1、栈(Stack)是限定在表尾进行插入和删除操作的线性表。其表尾称为栈顶(top),表头称为栈底(bottom)。栈的特点是后进先出(LastInFirstOut)。出栈入栈栈顶an┇a3a2栈底a17图2.1栈的示意图2、栈的基本操作和线性表类似,栈也有两种存储结构,即顺序栈和链栈。⑴顺序栈可以定义为#definemaxsize10

3、0/*栈的最大元素数为100*/typedefstruct/*定义顺序栈*/{datatyped[maxsize];inttop;}seqstack;seqstack*s;/*定义顺序栈的指针*/顺序栈的基本操作如下:①栈的初始化(建立一个空栈)voidInitStack(seqstack*s)/*构造一个空栈s*/{s->top=-1;}②入栈操作seqstack*push(seqstack*s,datatypex)/*入栈*/{if(s->top==maxsize-1){printf(“栈已满,不能入栈!”);returnNULL

4、;}else{s->top++;/*栈顶指针上移*/s->d[s->top]=x;/*将x存入栈中*/returns;}}③出栈函数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;/

5、*栈为空时返回1(真)*/elsereturn0;/*栈非空时返回0(假)*/}⑵链栈可以定义为#defineNULL0typedefstructnode/*定义链栈结点类型*/{datatypedata;structnode*next;}linkstack;linkstack*top;/*定义栈顶指针*/链栈的基本操作如下:①栈的初始化(建立一个空栈)voidinit_linkstack(linkstack*top){top=NULL;}②入栈操作linkstack*push_linkstack(linkstack*top,dataty

6、pex){linkstack*p;p=(linkstack*)malloc(sizeof(linkstack));/*开辟新结点*/p->data=x;p->next=top;top=p;returntop;}③出栈函数datatypepop_linkstack(linkstack*top)/*出栈*/{datatypey;linkstack*p;if(top==NULL){printf(“栈为空,无法出栈!”);return0;}else{p=top;y=top->data;/*栈顶元素出栈,存入y中*/top=top->next;

7、/*栈顶指针下移*/free(p);/*释放存储空间*/7returny;}}④判栈空函数intempty_linkstack(linkstack*top){if(top==NULL)return1;/*栈为空时返回1(真)*/elsereturn0;/*栈非空时返回0(假)*/}一、解题思路方法1(将链表结点中的数据入栈,用顺序栈实现)1、建立一个带头结点的单链表head;2、输出该单链表;3、建立一个空栈s;4、依次将单链表的数据入栈;5、依次将单链表的数据出栈,并逐个将出栈的数据存入单链表的数据域(自前向后);6、再输出单链表。程序

8、如下(采用顺序栈实现):7typedefintdatatype;#include#defineNULL0#definemaxsize100/*设栈的最大元素数为100*/ty

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。