首页 栈和队列的基本操作及其应用数据结构实验报告书

栈和队列的基本操作及其应用数据结构实验报告书

栈和队列的基本操作及其应用数据结构实验报告书栈和队列的基本操作及其应用数据结构实验报告书数据结构实验报告计科111 *** 201100814*** 《数据结构》实验内容:栈和队列的基本操作及其应用 201100814*** 计科111 *** 第 1 页数据结构实验报告计科111 *** 201100814*** 前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重...

栈和队列的基本操作及其应用数据结构实验报告书数据结构实验报告计科111 *** 201100814*** 《数据结构》实验内容 :栈和队列的基本操作及其应用 201100814*** 计科111 *** 第 1 页数据结构实验报告计科111 *** 201100814*** 前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课;同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。数据结构课程内容丰富、学习量大，实践性强;隐含在各部分内容中的方法和技术多;算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。第 2 页数据结构实验报告计科111 *** 201100814*** 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容本次实验提供2个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况任选一个～本人由于初学，对数据结构的操作知识欠缺，所以选了2个实验题目中的第1个题目如下: 题目一:回文判断(*) [问题描述] 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。 [基本要求] (1)数据从键盘读入; (2)输出要判断的字符串; (3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出 “Yes”，否则输出“No”。 [测试数据] 由学生任意指定。三、算法设计 1、程序所需头文件已经预处理宏定义如下 #include #include #define OVERFLOW -1 第 3 页数据结构实验报告计科111 *** 201100814*** #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType; typedef int Status; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; typedef char QElemType; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QNodePtr; typedef struct{ QNodePtr front; QNodePtr rear; }LinkQueue; 2、程序中所需的操作栈的POP和PUSH函数 Status Push(SqStack &S,SElemType e) { //插入e为新的栈顶元素 if(S.top-S.base>=S.stacksize) {//栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(SElemType)); if(!S.base)exit (OVERFLOW);//存储空间分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//Push函数 Status Pop(SqStack &S ,SElemType &e) { //若栈不空，删除栈顶元素，并用e返回其值 if(S.top==S.base) return ERROR; 第 4 页数据结构实验报告计科111 *** 201100814*** e=*--S.top; return OK; }//Pop函数 3、程序中所需的操作队列的函数 Status EnQueue(LinkQueue &Q,QElemType e) { QNodePtr p; p=(QNodePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } Status DeQueue(LinkQueue &Q,QElemType &e) { QNodePtr p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return OK; } 4、另外，还有创建栈和创建一个空的链式栈 Status CreatStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//创建栈 Status CreatQueue(LinkQueue &Q) { 第 5 页数据结构实验报告计科111 *** 201100814*** Q.front=Q.rear=(QNodePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; return OK; }//建立一个空的链式栈 5、再就是最重要的判断部分 int Test() //判别输入的字符串是否回文序列,是则返回1,否则返回0 { SqStack S;LinkQueue Q; CreatStack(S);CreatQueue(Q); char c; SElemType a,b; while((c=getchar())!='@') { Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 } while(S.top!=S.base) { Pop(S,a);DeQueue(Q,b); if(a!=b) return ERROR; } return OK; } 判断输入的字符串是否回文序列,是则返回1,否则返回0 四、调试与测试我们开始测试数据:12321，如图: 输出结果是YES，说明程序判断出12321是回文然后我们测试12345，如图第 6 页数据结构实验报告计科111 *** 201100814*** 输出结果是NO，所以程序判断12345不是回文五、总结通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对栈和队列的操作问题。因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。六、源代码 #include #include #define OVERFLOW -1 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType; typedef int Status; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; typedef char QElemType; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QNodePtr; typedef struct{ 第 7 页数据结构实验报告计科111 *** 201100814*** QNodePtr front; QNodePtr rear; }LinkQueue; Status CreatStack(SqStack &S){ //创建栈 S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status Push(SqStack &S,SElemType e){ //插入e为新的栈顶元素 if(S.top-S.base>=S.stacksize){//栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEle mType)); if(!S.base)exit (OVERFLOW);//存储空间分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//Push Status Pop(SqStack &S ,SElemType &e){ //若栈不空，删除栈顶元素，并用e返回其值 if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//Pop Status CreatQueue(LinkQueue &Q){ //建立一个空的链式栈 Q.front=Q.rear=(QNodePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; return OK; } 第 8 页数据结构实验报告计科111 *** 201100814*** Status EnQueue(LinkQueue &Q,QElemType e) { QNodePtr p; p=(QNodePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } Status DeQueue(LinkQueue &Q,QElemType &e) { QNodePtr p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return OK; } int Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 { SqStack S;LinkQueue Q; CreatStack(S);CreatQueue(Q); char c; SElemType a,b; while((c=getchar())!='@') { Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 } while(S.top!=S.base) { Pop(S,a);DeQueue(Q,b); if(a!=b) return ERROR; } return OK; } Status main(){ printf("请输入要判断的字符串\n并请以@作为结束符\n"); if(Test()==1) printf("YES\n"); 第 9 页数据结构实验报告计科111 *** 201100814*** else printf("NO\n"); return OK; } 第 10 页

                    本文档为【栈和队列的基本操作及其应用数据结构实验报告书】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

栈和队列的基本操作及其应用数据结构实验报告书

你可能还喜欢