数据结构课程设计：栈和队列及其应用文章编辑.doc

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

19、tf(括号不匹配!n); return OK; void function2() char temp,flag=y; while(flag=y) char str255; SqStack S; printf(请输入字符串:); scanf(%s,str); scanf(%c,&temp); /接受输入的回车键 InitStack(&S); Bracket(S,str); printf(你想再试一次吗(按y继续): ); scanf(%c,&flag) ; printf(n); printf(程序结束.n);/-栈的基本操作-void function3() int x=1; SqStack s

20、q; InitStack(&sq); SElemType e; int flag=1;couttt-栈的基本操作-n;couttt-1.入栈-n;couttt-2.出栈-n;couttt-3.销毁栈-n;couttt-0.退出-n;while(flag) coutx;switch(x) case 1: int i; char a100; couta; for(i=0;ai!=0;i+)Push(&sq,ai); break;cout请输入选择x;case 2: for(i=0;ai!=0;i+)Pop(&sq,&e);cout出栈的元素为:eendl; break;cout请输入选择x;cas

21、e 3: DestroyStack(&sq);cout栈已被销毁成功endl; break;cout请输入选择x;case 0: flag=0; break; /-字符串的基本操作-typedef structchar *ch; int length; HString;Status CreateString(HString &S) /创建一个字符串int k; S.ch=(char *)malloc(STACK_INIT_SIZE * sizeof(char);if(!S.ch) exit(OVERFLOW);coutk; S.length=k;cout请输入该字符串的值:; for(int

22、i=0;iS.chi; return OK; int InitString(HString &S)/将S.ch置成空指针，S的长度设为0 S.ch=NULL; S.length=0; return 1; Status Concat(HString &T,HString S1,HString S2) /用T返回值由S1和S2联接而成的新串 if (T.ch) free(T.ch); /释放原有的空间 if (!(T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char) exit(OVERFLOW); int i; for (i=0;iS1.len

23、gth;+i) T.chi=S1.chi; T.length=S1.length+S2.length; for (i=0;iS2.length;+i) T.chi+S1.length=S2.chi; return OK; int StrLength(HString S) return S.length; /求串的长度int StrCompare(HString S,HString T) /比较字符串S和T for(int i=0;iS.length & iT.length;i+)if(S.chi!=T.chi) return S.chi-T.chi; return S.length-T.len

24、gth;Status ClearString(HString &S) /清空串if(S.ch) free(S.ch); S.ch=NULL; S.length=0; return OK;Status SubString(HString &Sub,HString S,int pos,int len) / /用Sub返回串S的第pos个字符起长度为len的字串if(posS.length|lenS.length-pos+1) return ERROR;if(Sub.ch) free(Sub.ch); if(!len) Sub.ch=NULL; Sub.length=0;elseSub.ch=(ch

25、ar *)malloc(len * sizeof(char); int j=0;for(inti=0;ilen;i+)Sub.chi=S.chj;j+;Sub.length=len;returnOK;int DispStr(HString S) if (S.length=0) return ERROR; int i;for (i=0;iS.length;i+) coutS.chi; return OK;/DispStrvoid function4()HString S1,S2,Sub1,Sub2,T;InitString (S1); InitString (S2); InitString (S

26、ub1); InitString (Sub2); InitString (T); int flag=1; int x;couttt-1,将S1字符串和S2联接成新串-endl;couttt-2,比较S1字符串和S2字符串长度的大小-endl;couttt-3,求S1字符串和S2字符串的长度-endl;couttt-4,返回串S起第pos个字符起长度为len的字串endl;couttt-5,清空字符串-endl;couttt-0,退出-endl;CreateString(S1); CreateString(S2); cout字符串创建成功endl;while(flag) coutx;switch

27、(x) case 1: Concat(T,S1,S2); DispStr(T); break; cout请输入选择0) cout字符串S1大于S2!endl; if(StrCompare(S1,S2)=0) cout两字符串相同!endl;if(StrCompare(S1,S2)0) cout字符S1小于S2!endl; break; cout请输入选择endl;case 3: cout字符串S1的长度为; coutStrLength(S1)endl; cout字符串S2的长度为; coutStrLength(S2)endl; break; cout请输入选择endl;case 4: int

28、pos1,pos2,len1,len2; cout返回串S1起第pos1个字符起长度为len1的字串endl; cout请输入pos1的值pos1 cout请输入len1的值len1; SubString(Sub1,S1,pos1,len1); DispStr(Sub1); coutendl; cout返回串S2起第pos2个字符起长度为len2的字串endl; cout请输入pos2的值pos2; cout请输入len2的值len2; SubString(Sub2,S2,pos2,len2); DispStr(Sub2); coutendl; break; cout请输入选择endl;cas

29、e 5: cout该选择将清空字符串endl; ClearString(S1); ClearString(S2);cout字符串S1,S2已被清空endl; break;cout请输入选择endl; case 0: flag=0; break; void function() int k; coutntt*;coutntt*欢迎使用本系统*; coutntt*;coutntt*基本功能*;coutntt*栈和队列的应用*endl; coutntt 1.回文判断endl; coutntt 2.括号匹配endl; coutntt 3.栈列的基本操作endl; coutntt 4.字符串的基本操作e

30、ndl; coutntt*;coutk;while(!(k=1|k=2|k=3|k=4) coutk; switch(k) case 1: function1();break; case 2: function2();break; case 3: function3();break; case 4: function4();break; void main()char ch;do function();coutch; while(!(ch=n|ch=N|ch=y|ch=Y) coutch; while(ch=y|ch=Y); coutnnt;文档编辑：#include #include #in

31、clude struct node char c; node *next; ;void InitList(node *L) /输入以#结束的文章 cout输入一页文字(以结束): c = getchar() != ) L-next = new node; L = L-next; L-next = NULL; void Strnum(node *L) /统计某一字符串在文章中出现次数 int n = 0; char s80, *q; node *p; couts; while(L-next) for (p = L, q = s; *q != 0 & p-next; p = p-next, q+)

32、 if (p-c != *q) break; if (*q = 0) n+; L = L-next; cout字符串 s 出现 n 次n; node *DelString(node *L) /删除某一子串 node *H = L; char t80, *q; node *p; coutt; if (H-c = *t) for (p = H-next, q = t+1; *q != 0 & p-next; p = p-next, q+) if (p-c != *q) break; if (*q = 0) H = p; while(L-next) for (p = L-next, q = t; *

33、q != 0 & p-next; p = p-next, q+) if (p-c != *q) break; if (*q = 0) L-next = p; else L = L-next; return p; void print1(node *L) /分行输出用户输入的各行字符 while(L-next) coutc; L = L-next; coutnext; L = L-next, n+) if(isalpha(L-c) p1+; else if(isdigit(L-c) p2+; else if(L-c = ) p3+; else if(L-c = n) n-; coutn全部字母数

34、: p1; coutn数字个数: p2; coutn空格个数: p3; coutn文章总字数: nendl; void main() node *L = new node; int p1, p2, p3, n, c; InitList(L); do coutntt-文档编辑-endl; couttt1:统计英文字母和空格数以及整篇文章总字数n; couttt2:统计某一字符串在文章中出现次数n; couttt3:删除某一子串n; couttt4:分行输出用户输入的各行字符n; coutc; switch(c) case 1:print2(L, p1, p2, p3, n);break; cas

35、e 2:Strnum(L);break; case 3:DelString(L); case 4:print1(L); while(c!=0); 第四章 课设心得一直以来我都是打心底里不喜欢做课程设计这门功课，因为太苦太累了，一个微小的差错都得花上好长好长的时间去调试，还有写报告也太辛苦了，但是不得不承认课程设计是最能提高我们综合能力的一种方式，平时我们学习的都是些理论的知识，可是一碰到实际的操作，还是会觉得有点措手不及，这是提高我们动手能力的一门课程，所以做课设应该是一种虽苦犹乐的过程吧。因为平时不是十分认真的听课，所以在做课设的时候就得花大量的时间去查资料，为了让自己的设计更加完善更符合课

36、设标准，一次次的更改自己的设计方案。这次我做的栈和队列的应用以及文档编辑，在做课设之前一定要想好算法思想，构思好各个功能模块的布局等然后开始编写，因为这些程序都是由微小的代码组成的，所以经常会出现一些错误，令我最纠结的是参数传递部分，编译的过程中经常会出现诸如“cannot convert parameter 1 from SqStack to SqStack *”这种错误，一开始不明白是什么意思，后来才知道功能调用的模块函数类型要声明的部分一致，而且传递的数据个数也要一致。还有更令我纠结的一个问题是出现在串的基本操作中，我先把串的基本操作代码写完然后开始编写主函数，需要执行的功能就在相应的地方写一个调用函数，写完后发现编译没错误，可是一部分就是没法运行，一运行就出现什么“0x000004”内存不能被“read”啊什么错误的，检查过来检查过去就是不知道错在哪里了，后来请教了同学才知道要将串先初始化，置成空串，也就相当于给他一个空间，这样他才能接受赋值给他的字符串，改后就没错了，感觉如释重负。在这次的课设中我学到的还是很多的，巩固了自己在课堂上所学习得东西，同时学会了解决很多自己以前没碰到的问题，提高了自己实践能力。不管怎样，作为一名工科学生做此类的课程设计还是相当具有意义的。也非常感谢学校给我们提供了