数据结构实训

1、高职学院计算机专业类课 程 设 计 报 告（2012 -2013学年第1学期）课程设计类型：数据结构题目：栈+串+队列+线性表+后缀表达式求值学号：姓名：专业：计算机应用技术 指导教师：课程设计日期：2012.高职学院 制目 录1. 问题分析11.1 问题描述11.2 要求分析22. 总体设计32.1 功能分析33. 详细设计43.1 程序结构图43.2 程序流程图44. 功能测试74.1 本系统的主界面74.2 栈子系统界面74.3 串子系统界面104.4 队列子系统界面154.5 线性表子系统界面194.6 后缀表达式求值子系统界面234.7退出系统245. 课程设计小结25参 考 文 献

2、25附录：源代码清单261. 问题分析1.1 问题描述1. 栈子系统（1） 设计一个字符型的链栈。（2） 编写进栈、出栈、显示栈中全部元素的程序。（3） 编写一个把十进制整数转换成二进制数的应用程序。（4） 编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序。（5） 设计一个选择式菜单，以菜单方式选择上述操作。2. 串子系统（1） 由用户通过键盘输入建立一个字符串。（2） 编写插入、删除、查找、比较、取子字符串、连接字符串、显示、模式匹配等程序。（3） 设计如下所示的选择式菜单，以菜单方式选择上述操作。3. 队列子系统（1） 掌握队列的特点及其描述方法。（2） 用链式结构实现一个队列。

3、（3） 掌握队列的各种基本操作。（4） 掌握队列的简单应用程序。4. 线性表子系统（1） 用结构体描述一个字符型的单项列表。（2） 创建线性表；在线性表中插入元素、删除元素；显示线性表中所有元素等基本操作。（3） 用if语句设计 一个选择式菜单。5. 后缀表达式求助子系统（1） 后缀表达式求值子系统。（2） 用键盘输入一个整数后缀表达式（操作数的范围是09，运算符只含+、*、/、，而且中间不可以有空格），使用循环程序从左向右读入表达式。（3） 如果读入的是操作数，直接进入操作数栈。（4） 如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。（5）

4、检验程序运行结果。1.2 要求分析1. 栈子系统：使用栈的基本算法。2. 串子系统：使用串的基本算法。3. 队列子系统：使用队列的基本算法。4. 线性表子系统：使用线性表的基本算法。5. 后缀表达式求值子系统：利用栈进行计算2. 总体设计2.1 功能分析1. 栈子系统栈的基本操作2. 串子系统串的基本操作3. 队列子系统队列的基本操作4. 线性表子系统线性表的基本操作5. 后缀表达式求值子系统对后缀表达式进行求值3. 详细设计3.1 程序结构图主菜单退出后缀表达式求值子系统线性表子系统栈子系统队列子系统串子系统3.2 程序流程图开始键盘输入栈函数队列函数线性表函数后缀表达式求值函数串函数选择退

5、出结束主函数流程图函数入口进栈数值转换逆波兰式出栈显示退出栈函数流程图函数入口连接字串插入字串显示字串删除字串取出字串退出比较字串大小输入字串查找字串串子函数流程图函数入口进队出队读队头元素显示退出双队列队列子系统函数流程图函数入口建表插入删除求表长查找退出显示线性表子系统函数流程图函数入口键盘输入求值继续还是退出？Y结束N后缀表达式求值函数流程图4. 功能测试4.1 本系统的主界面4.2 栈子系统界面1. 输入选项1,进入“栈子系统” 2. 输入选项1，选择“进栈”功能3. 输入选项2，选择“出栈”功能4. 输入选项3，选择“显示”功能5. 输入选项4，选择“数值转换”功能6. 输入选项5，

6、选择“逆波兰式”功能7. 输入选项0，选择“退出”功能4.3 串子系统界面1. 输入1，进入“串子系统”2. 输入1，选择“输入字串”功能3. 输入2，选择“连接字串”功能4. 输入3，选择“取出字串”功能5. 输入4，选择“删除字串”功能6. 输入5，选择“插入字串”功能7. 输入6，选择“查找字串”功能8. 输入7，选择“比较串大小”功能9. 输入8，选择“显示字串”功能10. 输入0，选择“退出”功能4.4 队列子系统界面1. 输入1，进入“队列子系统”2. 输入1，选择“进队”功能3. 输入2，选择“出队”功能4. 输入3，选择“读队头元素”功能5. 输入4，选择“显示”功能6. 输入

7、5，选择“双队列”功能7. 输入0，选择“退出”功能4.5 线性表子系统界面1. 输入1，进入“线性表系统”2. 输入1，选择“建表”功能3. 输入2，选择“插入”功能4. 输入3，选择“删除”功能5. 输入4，选择“显示”功能6. 输入5，选择“查找”功能7. 输入6，选择“求表长”功能8. 输入0，选择“退出”功能4.6 后缀表达式求值子系统界面1. 输入5，进入“后缀表达式求值子系统”2. 选择界面4.7退出系统1. 输入选项0，选择“退出”功能，此功能下可以退出并关闭本程序5. 课程设计小结在这次课程设计之前总觉得自己学的还可以。但通过这次的课程设计让自己知道了自己有许多不懂的地方和还

8、需要学习的知识点。当然在这次课程中也遇到许多的困难尤其是在编完程序后调试遇到的困难令我难忘。通过这次课程设计也让我认识到了自己实践自己编程、自己调试的重要性。通过自己动手实践不仅可以增强自己自己的动手实践能力也可以加深自己对数据结构算法的理解。对我们学好数据结构这门课程具有很大的意义。除此之外我和认识到了和同学之间的合作的重要性。通过讨论不仅可以融洽同学之间的关系也可以更好的得出结论在调试中遇到的困难通过同学间的讨论也可以得到更好的改进方法。总之，这次的课程设计让我受益匪浅也可以增加我对数据结构这门课程设计的兴趣。让对以后数据结构的学习充满了信心。参 考 文 献（1） 李龙澍C+程序设计实训

9、清华大学出版社，2003年（2） 伍俊良VISUAL C+课程设计与系统开发案例，清华大学出版社2003年（3） 乌尼尔 Visual C+经典例程分析中国电力出版社，2000年（4） 张曜VISUAL C+程序开发案例解析清华大学出版社，1999年（5） 宋晓宇、王永会VISUAL C+高级编程技术与实例 中国水利水电出版社，2003年附录：源代码清单/开始.cpp#include串.h#include栈.h#include队列.h#include线性表.h#include后缀.hvoid main()int choice;char ch;ch=y;while(ch=y|ch=Y)print

10、f(nnn);printf(ntt 数据结构主系统 );printf(ntt 主菜单 );printf(ntt*);printf(ntt* 1- 栈 *);printf(ntt* 2- 串 *);printf(ntt* 3-队 列 *);printf(ntt* 4-线 性 表 *);printf(ntt* 5-自 主实 验 *);printf(ntt* 0-退 出 *);printf(ntt*);printf(ntt 请选择菜单号(0-5):);scanf(%d,&choice);getchar();switch(choice)case 1:Stack();break;case 2:Strin

11、g();break;case 3:Queue();break;case 4:LineList();break;case 5:Postfix();break;case 0:ch=n;break;default:printf(菜单选择错误!请重输);system(cls);/栈.cpp#include#include#define STACKMAX 100typedef struct stacknodeint data;struct stacknode *next;StackNode;typedef struct StackNode *top;LinkStack;void Push(LinkSta

12、ck &s,int x)StackNode *p=new StackNode;p-data=x;p-next=s.top;s.top=p;int Pop(LinkStack &s,int &x) StackNode *p;if(s.top!=NULL)p=s.top;x=p-data;s.top=p-next;delete p;return 1;else return 0;void ShowStack(LinkStack s)system(cls);StackNode *p=s.top;if(p=NULL)printf(ntt栈为空.);elseprintf(ntt栈元素为:);while(p

13、!=NULL)printf(%6d,p-data);p=p-next;printf(n);void Conversion(int n)LinkStack s;int x;s.top=NULL;dox=n%2;n=n/2;Push(s,x);while(n);printf(ntt转换后的二进制数值为:);while(Pop(s,x)printf(%d,x);printf(n);void Suffix()system(cls);char strSTACKMAX;char stackSTACKMAX;char expSTACKMAX;char ch;int sum,i,j,t,top=0;print

14、f(ntt输入算术表达式(运算符只能包含+,-,*,/),以#结束:ntt);fflush(stdin);i=0;do i+;scanf(%c,&stri);while(stri!=#&i!=STACKMAX);sum=i;t=1;i=1;ch=stri;i+;while(ch!=#) switch(ch)case (:top+;stacktop=ch;break;case ):while(stacktop!=()expt+=stacktop-;expt+=,;top-;break;case +:case -:while(top!=0 & stacktop!=()expt+=stacktop-

15、;expt+=,;stack+top=ch;break;case *:case /:while(stacktop=*|stacktop=/) expt+=stacktop-; expt+=,;stack+top=ch;break;case :break;default:while(ch=0&ch=z) expt+=ch;ch=stri+;i-;expt+=,;ch=stri+;while(top!=0)expt+=stacktop-;if(top!=0)expt+=,;printf(ntt输入的中缀表达式:);for(j=1;jsum;j+)printf(%c,strj);printf(nnt

16、t后缀表达式:);for(j=1;jt;j+)printf(%c,expj);printf(n);void Stack()system(cls);LinkStack s;int i=1,j=1,val,n;char choice;s.top=NULL;while(1) printf(nnn);printf(ntt 栈子系统 );printf(ntt*);printf(ntt* 1-进 栈 *);printf(ntt* 2-出 栈 *);printf(ntt* 3-显 示 *);printf(ntt* 4-数制转换 *);printf(ntt* 5-逆波兰式 *);printf(ntt* 0-退

17、 出 *);printf(ntt*);printf(ntt 请选择菜单号(0-5):);fflush(stdin);choice=getchar();switch (choice)case 1:while(1)printf(ntt键入一个整数(0表示结束)并按回车:);scanf(%d,&val);if(val!=0)Push(s,val);elsesystem(cls);break;break;case 2:if(Pop(s,val)system(cls);printf(ntt出栈元素为:%6dn,val);elsesystem(cls);printf(ntt栈为空，没有元素可以出栈!n);

18、break;case 3:ShowStack(s);break;case 4:system(cls);printf(ntt请输入一个十进制正整数:);scanf(%d,&n);Conversion(n);break;case 5:Suffix();break;case 0:exit(0);break;default:printf(ntt输入菜单错误，请重新输入!n);/串.cpp#include#include#define STRINGMAX 100typedef structchar vecSTRINGMAX;int len;str;void ConcatStr(str *r1,str *

19、r2) int i;printf(nttr1=%s r2=%sn,r1-vec,r2-vec);if(r1-len+r2-lenSTRINGMAX)printf(ntt两个串太长,溢出!n);elsefor(i=0;ilen;i+)r1-vecr1-len+i=r2-veci;r1-vecr1-len+i=0;r1-len=r1-len+r2-len;void SubStr(str *r,int i,int j)int k;str a;str *r1=&a;if(i+j-1r-len)printf(ntt子串超界!n);return;elsefor(k=0;kveck=r-veci+k-1;r

20、1-len =j;r1-vecr1-len=0;printf(ntt取出字符为:);puts(r1-vec);void DelStr(str *r,int i,int j)int k;if(i+j-1r-len)printf(ntt所要删除的子串超界!n);elsefor(k=i+j;klen;k+,i+)r-veci=r-veck;r-len=r-len-j;r-vecr-len=0;str *InsStr(str *r,str *r1,int i)int k;if(i=r-len|r-len+r1-lenSTRINGMAX)printf(ntt不能插入！n);elsefor(k=r-len

21、-1;k=i;k-)r-vecr1-len+k=r-veck; for(k=0;klen;k+)r-veci+k=r1-veck;r-len=r-len+r1-len;r-vecr-len=0;return r;int IndexStr(str *r,str *r1)int i,j,k;for(i=0;r-veci;i+)for(j=i,k=0;r-vecj=r1-veck;j+,k+)if(!r1-veck+1)return i;return -1;int LenStr(str *r)int i=0;while(r-veci!=0)i+;return i;str *CreateStr(str

22、 *r)gets(r-vec);r-len=LenStr(r);return r;int EqualStr(str *r1,str *r2)for(int i=0;r1-veci&r2-veci&r1-veci=r2-veci;i+);return r1-veci-r2-veci;void String()system(cls);str a,b,c,d;str *r=&a,*r1;r-vec0=0;char choice,p;int i,j,ch=1;while(ch!=0)printf(nnn);printf(ntt 串子系统 );printf(ntt*);printf(ntt* 1-输入字

23、串 *);printf(ntt* 2-连接字串 *);printf(ntt* 3-取出字串 *);printf(ntt* 4-删除字串 *); printf(ntt* 5-插入字串 *); printf(ntt* 6-查找字串 *); printf(ntt* 7-比较串大小 *); printf(ntt* 8-显示字串 *); printf(ntt* 0-退 出 *); printf(ntt*); printf(ntt 请选择菜单号(0-8):); scanf(%c,&choice); getchar();if(choice=1)system(cls);printf(ntt请输入一个字符串:)

24、; gets(r-vec); r-len=LenStr(r); else if(choice=2)system(cls);printf(ntt请输入所要连接的串:); r1=CreateStr(&b); ConcatStr(r,r1); printf(ntt连接以后的新串值为:n); puts(r-vec); else if(choice=3)system(cls);printf(ntt请输入从第几个字符开始:); scanf(%d,&i);getchar(); printf(ntt请输入取出的连续字符数:); scanf(%d,&j); getchar(); SubStr(r,i,j); e

25、lse if(choice=4)system(cls);printf(ntt请输入从第几个字符开始:); scanf(%d,&i);getchar(); printf(ntt请输入删除的连续字符数:); scanf(%d,&j); getchar(); DelStr(r,i-1,j); else if(choice=5)system(cls);printf(ntt请输入在第几个字符前插入:);scanf(%d,&i);getchar();printf(ntt请输入所要插入的字符串:);r1=CreateStr(&b);InsStr(r,r1,i-1);else if(choice=6)syst

26、em(cls);printf(ntt请输入所要查找的字符串:);r1=CreateStr(&b);i=IndexStr(r,r1);if(i!=1)printf(ntt第一次出现的位置是第%d个.n,i+1);elseprintf(ntt该子串不在其中!);else if(choice=7)system(cls);printf(ntt请输入第一个串:);gets(c.vec);printf(ntt请输入第二个串:);gets(d.vec);int k=EqualStr(&c,&d);if(k0)printf(ntt第一个串大!n);else if(kvec0=0)printf(空!n);els

27、eputs(r-vec);else if(choice=0)exit(0);else printf(nttt请注意!输入有误!n);if(choice=!X&choice!=X)printf(ntt按【Enter】键继续,按任意键返回主菜单.);p=getchar();if(p!=xA)getchar();break;/队列.cpp#includetypedef struct queuenodeint data;struct queuenode *next;QueueNode;typedef structQueueNode *front,*rear;LinkQueue;void InQueue

28、(LinkQueue *q)system(cls);int x;QueueNode *p=new QueueNode;printf(ntt请键入一个整数:);scanf(%d,&x);getchar();p-data=x;p-next=NULL;if(q-front=NULL)q-front=p;else q-rear-next=p;q-rear=p;if(p)printf(ntt%d进队成功!,x);int OutQueue(LinkQueue *q,int *v)QueueNode *p;if(q-front=NULL)return 0;elsep=q-front;*v=p-data;q-

29、front=p-next;if(q-front=NULL)q-rear=NULL;delete p;return 1;void ShowQueue(LinkQueue *q)system(cls);QueueNode *p=q-front;if(p=NULL)printf(ntt队列为空!n);else printf(ntt队列中的元素为:);while(p!=NULL)printf(%6d,p-data);p=p-next;printf(n);void ReadFront(LinkQueue *q)system(cls);if(q=NULL|q-front=NULL)printf(ntt队列

30、为空!没有队顶元素!n);elseprintf(ntt队首元素是:%4d n,q-front-data);#define QUEUEMAX 20int queueQUEUEMAX;int front=-1;int rear=-1;void InQueue(int val)rear=(rear+)%QUEUEMAX;if(front=rear)printf(ntt队列已满!);elsequeuerear=val;int OutQueue_rear()int t;if(front=rear)return -1;t=queuerear-;if(rear0&front!=-1)rear=QUEUEMA

31、X-1;return t;int OutQueue_front()int t;if(front=rear)return -1;t=queue+front;if(front=QUEUEMAX)front=0;return t;void DQ()system(cls);int choice;int out5;int in5=5,4,3,2,1;int t,pos=0,i;for(i=0;i5;i+)InQueue(ini);printf(ntt初始数据顺序是:);for(i=0;i5;i+)printf(%d,ini);printf(ntt 1-从头出队 2-从尾出队nn);while(front

32、!=rear)printf(tt请输入选择(1或2):);scanf(%d,&choice);switch(choice)case 1:t=OutQueue_front();outpos+=t;break;case 2:t=OutQueue_rear();outpos+=t;break;printf(ntt数据输出的顺序是:);for(i=0;ifront=q-rear=NULL;while(i)printf(nnn);printf(ntt 队列子系统 );printf(ntt*);printf(ntt* 1-进 队 *);printf(ntt* 2-出 队 *);printf(ntt* 3-

33、读队头元素 *);printf(ntt* 4-显 示 *);printf(ntt* 5-双 队 列 *);printf(ntt* 0-退 出 *);printf(ntt*);printf(ntt 请选择菜单号(0-5):);scanf(%c,&choice);getchar();switch(choice)case 1:InQueue(q);break;case 2:system(cls);if(OutQueue(q,&val)=0)printf(ntt队列为空!n);elseprintf(ntt出队元素为:%d,val);break;case 3:ReadFront(q);break;cas

34、e 4:ShowQueue(q);break;case 5:DQ();break;case 0:exit(0);break;default:;if(choice=1|choice=2|choice=3|choice=4|choice=5)printf(ntt按【Enter】键继续,按任意键返回主菜单,n);w=getchar();if(w!=xA)i=0;system(cls);/线性表.cpp#include#includetypedef struct linknodechar data;struct linknode *next;linnode;linnode *head;int n;vo

35、id createlist()system(cls);n=0;linnode *p,*s;char x;int z=1;head=new linnode;p=head;printf(ntt请逐个输入结点,以“x”为结束标记!n);printf(n);while(z)printf(tt输入一个字符数据,并按回车键!);scanf(%c,&x);getchar();if(x!=x)s=new linnode;n+;s-data=x;p-next=s;s-next=NULL;p=s;else z=0;void inslist(int i,char x)linnode *s,*p;p=head;int

36、 j=0;while(p!=NULL&jnext;if(p!=NULL)s=new linnode;s-data=x;s-next=p-next;p-next=s;n+;else printf(ntt线性表为空或插入位置超出!n);void dellist(char x)linnode *p,*q;if(head=NULL)printf(ntt线性表已经为空!);return;if(head-next=NULL)printf(ntt线性表已经为空!);return;q=head;p=head-next;while(p!=NULL&p-data!=x)q=p;p=p-next;if(p!=NUL

37、L)q-next=p-next;delete p;n-;printf(ntt结点%c已经被删除!,x);else printf(ntt抱歉!没有找到您要删除的结点.);void showlist()system(cls);linnode *p=head;printf(ntt显示线性表的所有元素:);if(head-next=NULL|p=NULL)printf(ntt链表为空!);elseprintf(ntt);while(p-next!=NULL)printf(%5c,p-next-data);p=p-next;void searchlist(char x)linnode *p;int i=1;if(head=NULL)printf(ntt链表下隘!);return;if(head-next=NULL)printf(ntt线性表为空,没有任何结点!);return;p=head-next;while(p!=NULL&p-data!=x)p=p-next;i+;if(p!=NULL)printf(ntt在表的第%d位上找到值为%c的结点!,i,x);elseprintf(ntt抱歉,未找到值为%c的结点!,x);void LineList()system(cls