数据结构课程设计:栈和队列及其应用文章编辑.doc
《数据结构课程设计:栈和队列及其应用文章编辑.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计:栈和队列及其应用文章编辑.doc(21页珍藏版)》请在沃文网上搜索。
1、目录第一章 课程设计目的1第二章 课程设计内容22.1 栈和队列及其应用22.2 程序流程图32.3 文章编辑52.4 程序流程图6第三章 测试数据73.1 栈和队列及其应用73.2 文档编辑93.3程序清单10第四章 课设心得19第五章 参考文献20 20第一章 课程设计目的课程设计是一门锻炼学生动手操作能力的课程,在了解并掌握数据结构与算法的设计方法的过程中,培养初步的独立分析和设计能力;初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;提高综合运用所学的理论知识和方法独立分析和解决问题的能力;训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的
2、科学的工作方法和作风。为自己以后从事软件开发事业打下基础。课设使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构,存储结构和操作实现算法,以及他们在程序中的使用方法。掌握使用各种计算机资料和有关的参考资料,提高程序设计的基本能力。第二章 课程设计内容课程设计题目一: 2.1 栈和队列及其应用题目简介:目的在于使读者深入了解栈和队列的特性,以便在实际问题背景下灵活运用他们;同时还将巩固对这两种结构的构造方法的掌握,接触较复杂问题的递归算法设计。(最少选择4个)(1):栈列操作的验证(建栈、入栈、出栈、销毁栈) (2):判断表达式中括弧是否正确配对 (3):判断字符串是否回文 (4):
3、字符串的基本操作(5个基本函数实现)设计思路: 栈的特点是先进后出,而队列的特点是先进先出,这个程序主要是利用到栈和队列的这两个特点,根据需要编写各个功能函数代码,因为本程序中涉及到的功能较多,而且每个大的功能块还包含了小功能,所以我使用了function1,function2,function3,function4这四个功能块,分别调用所编写的功能函数来实现所需要的四个大操作,然后再function块中编写功能菜单代码,调用function1,Function2,function3,function4,实现各个菜单。然后在main函数中编写一个询问用户是否继续该程序的功能代码,这样大体上就完
4、成了这个程序的设置。 字符串的基本操作,我写的是创建字符串,串的联接,求串的长度,返回串第pos个位置长为len的字串,清空串,在做这一块时我们可以先把他的各个基本操作的函数写出来,然后在function4中调用它,这样就可以实现了。2.2程序流程图开始1 入栈2 出栈3 销毁栈4 退出栈的基本操作构建一个栈括号匹配回文判断调用相应的功能模块1 串的连接2 比较大小3 求串长4 返回字串5 清空串6 退出创建一个字符串字符串的基本操作主函数模块分析1 InitStack( ) 构建空栈 Push( ) 入栈 Pop( ) 出栈 DestroyStack( ) 销毁栈2. InitQueue(
5、) 构建空队列3. function1( ) 回文判断。 栈的特点是先进后出,队列的特点是先进先出,因此输入一串字符,并将其分别入栈和入队,然后再让其同时出队和出栈,如果每个出队的字符和出栈的字符相同,则该字符串是回文。4. Bracket ( ) 括号匹配。 检验括号匹配的方法可用“期待的急迫程度”这个概念来描述,遇到左括号则进栈,遇到右括号则先检验栈是否为空,若空,则表明右括号多余,否则和栈顶元素比较,如匹配则左括号出栈,否则不匹配,退出,并询问是否继续,5. CreateString( ) 创建字符串 InitString( ) 置空字符串 Concat( ) 将两个字符串联接成新串 S
6、trLength( ) 求串长度 StrCompare( ) 比较串大小 ClearString( ) 清空字符串。主要是串S的指针置空,并且使其长度置0来达到清空的目的。SubString( ) 返回串中第pos个字符长度为len的字串。6. function( ) 该模块主要显示功能菜单,利用switch语句实现各个功能的选择,在相应的菜单中,调用相应的功能模块。7. main( ) 主函数中存放循环语句,提醒用户是否继续改程序。课程设计题目二:2.3文章编辑题目简介:功能:输入一页文字,程序可以统计出文字、数字、空格的个数。静态存储一页文章,每行最多不超过80个字符,共N行;要求(1)分
7、别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章中出现的次数,并输出该次数;(3)删除某一子串,并将后面的字符前移。存储结构使用线性表,分别用几个子函数实现相应的功能;输入数据的形式和范围:可以输入大写、小写的英文字母、任何数字及标点符号。输出形式:(1)分行输出用户输入的各行字符;(2)分4行输出全部字母数、数字个数、空格个数、文章总字数(3)输出删除某一字符串后的文章。设计思路: 在文档编辑这个课设中,我使用的是单链表的存储结构。统计字母,空格,文章的总字数相删除某一字串等这些基本操作时用到了串的查找和删除。首先创建一个单链表,每个结点设置一个数据域和指针域,统计
8、字母的的字数时用到按顺序查找,设置一个标志,查到一个要求的字符,标志就加1,指针指向下一个位置,如此循环,一直查到表尾,此时的标志的值就个数。删除某一字串也是先应用到字符串的查找,查找成功后删除该字串,然后设置一个for循环将删除后的字串输出来。想好算法思想后,接下来就是编写程序了,先将各个功能函数编写出来,然后再main函数中编写菜单代码共用户选择,调用相应的功能函数名,实现所需要的操作。 2.4程序流程图开始模块分析1. InitList( ) 输入一篇文章,存在该线性表中。2. Strnum() 统计某一字符串在文章中出现的次数3. *DelString() 删除某一字串4. print
9、1() 分行输出用户输入的字符 5. print2() 统计英文字母和空格数以及整篇文章的总字数6. main() 主函数中存放功能菜单,在相应的模块下调用功能模块函数。主函数查寻某子串调用相应的功能块输出这段文字统计字母、数字、空格、某一字符串的个数以及文章总字数删除该子串输入一段文字输出删除该串后的文字个数统计第三章 测试数据3.1 栈和队列及其应用 回文判断首先显示功能菜单,用户根据自己的喜好选择相应的选项。 判断括号是否匹配栈的基本操作菜单 出栈操作进栈操作 退出栈的操作销毁栈 联接两字符串字符串操作菜单 比较两字符串大小求两字符串长度返回字符串第pos个字符起长度为len的字串清空字
10、符串退出字符串的基本操作 3.2 文档编辑输入文章,并显示功能菜单 统计字母。数字。空格个数以及总的字数统计某一字串在文章中出现的次数删除某一字串 分行输出用户输入的字符3.3程序清单栈和队列:#include#include#include#include #include#include#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef char SEl
11、emType;typedef char QElemType;/*栈的基本算法描述*/Typedef structSElemType*base;SElemType*top;int stacksize; SqStack;Status InitStack(SqStack *S) /*初始化一个栈*/ S-base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(S-base=NULL) printf(out of space); exit(OVERFLOW); S-top=S-base; S-stacksize=STACK_INIT_
12、SIZE; return OK;void Push(SqStack *S,SElemType e) /*进栈操作*/if(S-top-S-base=S-stacksize) S-base=(SElemType*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType); if(S-base=NULL) printf(out of space); exit(OVERFLOW); S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT; *S-top+=e;char GetTop(S
13、qStack *S,SElemType e)/若栈不为空,则用e返回S的栈顶元素,并返回ok;否则返回ERRORif (S-top=S-base) return ERROR;e=*-S-top;return e; Status Pop(SqStack *S,SElemType * e)/*这里应该用指针出栈操作*/ if(S-base=S-top) return ERROR; *e=*-S-top; return *e;int EmptyStack(SqStack S) /*判断栈是否为空*/if(S.base=S.top) printf(此栈为空);else printf(此栈不为空); r
14、eturn OK;Status DestroyStack(SqStack *S) /*销毁一个栈*/free(S-base); S-base=S-top=0; return OK; /*队列基本算法描述*/typedef struct QNodeQElemType data; struct QNode *next; QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;/构造一个空队列Status InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc
15、(sizeof(QNode);if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK; /-回文判断-typedef struct stack char bata; struct stack *next; Stack;int function1() Stack *top = new Stack; if(!top) exit(1); top = NULL; /初始化栈 LinkQueue *x = new LinkQueue; if(!x) exit(1); x-front = x-rear=NULL; / /初始化队列 cout请输入
16、要检测的字符串,可以包含空格,以结束sri; stack *s1 = new stack; if(!s1) exit(1); if(i=0) s1-next = NULL; /输入栈第一个数据 s1-bata=sri; top = s1; s1-bata = sri; s1-next = top; top = s1; QNode *x1 = new QNode; if(!x1) exit(1); if(i=0) /输入队列第一个数据x1-data = sri; x-front = x1; x-rear = x1; x-front-next = NULL; x1-data = sri; x-re
17、ar-next = x1; x-rear = x1; while(sri!=); cout检测结果front=NULL) cout未输入!next; /将字符删除 while(top!=NULL&x-front!=NULL) if(top-bata!=x-front-data) cout此字符串不是回文!endl; return 0; else cout此字符串是回文。endl; return 0; /-括号匹配-Status Bracket(SqStack &S,char *str) int i=0,flag1=0,flag2;SElemType e; while(stri!=0) swit
18、ch(stri) case (:Push(&S,();break; /(进栈 case :Push(&S,);break; /进栈 case ):Pop(&S,&e); if(e!=() flag1=1; break; /出栈,判断是否为(case :Pop(&S,&e); if(e!=) flag1=1;break; /出栈,判断是否为default: break;if(flag1) break; /出现不匹配,立即结束循环 i+; flag2=EmptyStack(S); /flag2判断堆栈是否为空 if(!flag1 & flag2) printf(括号匹配!n); else prin
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 队列 及其 应用 文章 编辑