数据结构课程设计报告.docx
- 文档编号:13704362
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:87
- 大小:455.16KB
数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告.docx(87页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告
一、设计目的
《数据结构》是一门实践性较强的软件基础课程,为了学好这门课程,必须在掌握理论知识的同时,加强上机实践。
本课程设计的目的就是要达到理论与实际应用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能。
二、设计要求
1、通过这次设计,要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。
同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
2、学生必须仔细研读《数据结构》课程设计(实习)要求,以学生自学为主、指导教师指导为辅,认真、独立地完成课程设计的任务,有问题及时主动与指导教师沟通。
3、本次课程设计按照教学要求需要在一周半时间内独立完成,学生要发挥自主学习的能力,充分利用时间,安排好课设的时间计划,并在课设过程中不断检测自己的计划完成情况,及时地向指导教师汇报。
4、编程语言任选。
三、设计题目及内容
文章编辑
一、需求分析
功能:
输入一页文字,程序可以统计出文字、数字、空格的个数。
静态存储一页文章,每行最多不超过80个字符,共N行;
要求:
(1)分别统计出其中英文字母数和空格数及整篇文章总字数;
(2)统计某一字符串在文章中出现的次数,并输出该次数;
(3)删除某一子串,并将后面的字符前移。
存储结构使用线性表,分别用几个子函数实现相应的功能;
输入数据的形式和范围:
可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式:
(1)分行输出用户输入的各行字符;
(2)分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"
(3)输出删除某一字符串后的文章;
二、概要设计
1、定义结构体structline,文本行采用顺序存储,行与行之间采用链式存储
三、主要函数:
intFindString(LINE*&head,char*str)/*统计str在文章中出现的次数*/
求在一行中Str出现的次数的流程图:
①.查找第一个字符,如果有第一个字符即p->data[i]==str[0],设计数器k=0
②.查找这个字符后面的字符与要查找的字符串是否匹配即p->data[i+j]==str[j],如果匹配k++
③.重复第二步,如果k=len2,则查找到,count++;如果没查找到,重新进行第一步
voiddelstringword(char*s,char*str)/*删除字符串*s中的字符串*str*/
实现思想:
①.从字符串s中寻找str第一次出现的位置*p=strstr(s,str);
②.len=strlen(s);i=len-strlen(p)即前i项恰好不含要删除的字符串,将前i项复制到tmp中
③.j=i+strlen(str)即要删除的字符串在i+1和j之间,将j之后的字符串复制到tmp中
④.将tmp赋给串s,返回s
四、调试分析和问题思考:
1.测试数据及结果
2、问题思考:
输入文章时,计算机怎样识别文章是否结束?
输出文章时,怎样处理表示结束的字符?
解决方案:
输入文章时,以Ctrl+E(^E)为结尾,当tmp[0]==5时,发现输入^E,则退出输入。
输出时文章时,如果tmp[strlen(tmp)-1]==5即发现表示结束的字符^E,用p->data[strlen(tmp)-1]='\0'除去最后一个控制符^E。
宿舍管理系统
一、设计任务与目标
任务:
为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求:
(1)采用交互工作方式
(2)可以增加、删除、修改信息
(3)建立数据文件,数据文件按关键字(姓名、学号、房号)进行排序(选择、快速排序、堆排序等任选一种)
(4)查询:
a.按姓名查询;b.按学号查询;c按房号查询
(5)打印任一查询结果(可以连续操作)
要求:
上述查询功能中,学号、房号用折半查找,姓名查找用哈希查找。
二、方案设计与论证
流程图:
输入“学号,姓名,房间号”
是否继续
YN
车场内信息
便道车信息
对room计费
Room前车辆进临时栈
退出
车离开
车到达
进入主菜单
初始化两个栈Enter和Temp及一个队列Wait。
开始
结束
输入“3”返回上一级菜单
输入“5”退出
输入“4”返回上一级菜单
分别进行查询
插入学生信息
输出已录入的学生信息
“信息显示”
“信息录入”
查找功能子菜单
插入功能子菜单
显示“宿舍管理查询系统主菜单”
count=0;h=0;len1=0;
len2=strlen(str);
三、算法说明
主要有主菜单函数,插入功能子菜单函数,查找功能子菜单函数,学生信息录入函数,显示函数,排序函数,插入函数以及查找函数。
在每个区域中会调用不同的函数来实现主要的功能。
比如,在学生显示这个功能里调用显示函数;在插入功能里调用子菜单函数;在显示信息时调用排序函数先对需要输出的信心进行排序,然后再输出;在查找功能里会调用查找函数来进行查找,包括按照性别,学号,姓名,房间号等查询。
四、调试测试与分析
主菜单显示:
信息录入界面:
信息显示界面:
查找学生信息界面:
停车场管理系统
一、需求分析
任务:
设停车场是一个可以停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序,依次有北向南排列(大门在最南端,最先到达的第一车停放在车场的最北端),若车场内已停满n辆车,那么后来的车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
试为停车场编制按上述要求进行管理的模拟程序。
要求:
以栈模拟停车场,以队列模拟车场外的便道。
每一组输入数据包括三个数据项:
汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。
对每一组输入数据进行操作后的输出信息为:
若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停车不收费)。
栈以顺序存储结构实现,队列以链表结构实现。
二概要设计
此停车场管理系统是在一个狭长的通道上的,而且只有一个大门可以供车辆进出,并且要实现停车场内某辆车要离开时,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些辆再依原来的次序进场的功能,就可以设计两个堆栈,其中一个堆栈用来模拟停车场,另一个堆栈用来模拟临时停车场,该临时停车场用来存放当有车辆离开时,原来停车场内为其让路的车辆。
至于当停车场已满时,需要停放车辆的通道可以用一个链队列来实现。
当停车场内开走一辆车时,通道上便有一辆车进入停车场,此时只需要改变通道上车辆结点的连接方式就可以了,使通道上第一辆车进入停车场这个堆栈,并且使通道上原来的第二辆车成为通道上的第一辆车,此时只需将模拟通道的链队列的头结点连到原来的第二辆车上就可以了。
对于此停车场管理系统的实现,就是用两个堆栈来分别模拟停车场以及停车场内车辆为其它车辆让路时退出停车的临时停放地点。
至于通道上车辆的停放则用一个链队列来实现,此时,通道上车辆的离开或者进入停车场只需改变此链队列上的结点而已。
对于要对停车场内的车辆根据其停放时间收取相应的停车费用,可以记录下车辆进入以及离开停车场的时间,再用时间差乘以相应的单价并且打印出最后的费用就可以实现了。
三、主要模块及关系
1.主要模块
首先定义用来模拟停车场的堆栈以及用来模拟通道的链队列为全局变量,然后编写主函数,在此主函数中实现对其它各个模块的调用。
在主函数中首先调用option()函数,出现欢迎用户使用的主界面,然后提示用户进入此停车场管理系统后,再出现一个供用户选择的界面,在用户的选择过程中,程序又分别调用车辆的到达、车辆的离开、停车场内停放车辆的信息以及退出程序这四个函数模块。
其中,在车辆的离开那个模块函数中又调用了打印离开车辆信息的函数,在停车场内停放车辆信息的那个模块函数中,又分别调用了显示停车场上车辆信息的函数以及显示便道上车辆信息的函数。
最后,从调鼐的这四个函数中回到主函数结束整个程序的运行。
在以上各个模块中,出现的调用的函数为:
voidInitStack(SeqStackCar*s);
intInitQueue(LinkQueueCar*Q);
option();
intArrival(SeqStackCar*Enter,LinkQueueCar*W);
voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W);
voidPRINT(CarNode*p);
voidList(SeqStackCarS,LinkQueueCarW);
voidList1(SeqStackCar*S);
voidList2(LinkQueueCar*W);
2.模块间关系
四、调试分析
①欢迎界面
②车辆到达
车辆离开
④车辆信息(车场)
⑤车辆信息(便道)
猴子选大王
一、需求分析:
任务:
一堆猴子都有编号,编号是1,2,3...m,这群猴子(m个)按照1--m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
要求:
(注:
分别顺序存储结构和链式存储实现)
输入数据:
输入m,n。
m,n为整数,n 输出形式: 中文提示按照m个猴子,数n个数的方法,输出为大王的猴子是几号,建立一个函数来实现此功能 二、概要设计 从用户输入的数据中读取猴子的数量和报数的最大数,然后对猴子进行编号,并用链表来存储,让链表中的猴子进行报数,对于报数为n的猴子则从链表中删掉,当链表只剩下最后一个猴子进行报数的时候,则选出大王。 typedefstructLNode//设计一个猴子的结构体,该结构体用monkey表 intmain()//主程序 三、主要函数 1.猴子选大王的链式储存结构 ypedefstructLNode{ intdata; structLNode*next; }LNode,*LinkList; 2.需要用到一个while语句来进行循环,达到在猴子进行报数的过程中删掉报数为n的猴子。 LinkListDeleteList_L1(LinkListL,intn,intk){ inti; intj; LinkListp; LinkListq; p=L; for(i=1;i<=n-1;i++){ for(j=1;j<=k-1;j++) p=p->next; q=p->next; p->next=q->next; free(q); } L=p; returnL; } 3.一些重要语句 LinkListCreateList_L1(LinkListL,intn){ LinkListp; LinkListq; inti; L=(LinkList)malloc(sizeof(LNode)); q=L; for(i=1;i p=(LinkList)malloc(sizeof(LNode)); q->data=i; q->next=p; q=p; } p->data=n; p->next=L; L=p; returnL; } 四、调试分析 1.按顺序结构调试 2.按链式结构调试 平衡二叉树 一、需求分析 具体要求: (1)用二叉链表作存储结构,以回车('\n')为输入结束标志,输入数列L,生成一棵平衡的二叉排序树T,并以直观的方式显示在终端上; (2)对二叉排序树T作中序遍历,输出结果; (3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”,并将x插入该二叉排序树中。 注意: 插入、删除应保证二叉排序树的平衡性。 二、概要设计 平衡二叉树是在构造二叉排序的过程中,每当插入一个新节点时,首先检查是否因插入新节点而破坏了二叉树排序的平衡性。 在中序序列中,根结点的左子树中的所有结点都在根结点的左侧,根结点的右子树中的所有结点都在根结点的右侧,这个特点恰好与二叉排序树具有相同的性质;在读入序列时,前序序列则从左向右读,这恰好与遍历二叉树的顺序相同;后序序列从右向左读,则按照根结点、右子树、左子树的顺序还原。 三、主要函数 1.中遍历的递归 voidPreOrder(BSTree&T,void(*Visit)(ElemTypee)) {//中序遍历二叉排序树 if(T) { PreOrder(T->lchild,Visit); Visit(T->data); PreOrder(T->rchild,Visit); } } 2.主函数的调用 voidmain() { inta,n,t,i; BSTNode*T=NULL; boolm; show(); cin>>a; while(a! =0) { switch(a) { case1: cout<<"请输入结点个数! 同时输入数列"< cin>>i; for(t=0;t { cin>>n; InsertAVL(T,n,m); } ShowTree(T); break; case2: PreOrder(T,Print); break; case3: cout< "; cin>>i; SearchBST(T,i); if(SearchBST(T,i)==NULL) { cout<<"该结点在树中不存在,要插入。 "< cout<<"下面是处理后中序遍历输出的树"< InsertAVL(T,i,m); ShowTree(T); } else { cout<<"该结点已经找到,要删除."< cout<<"下面是处理后中序遍历输出的树"< DeleteAVL(T,i); ShowTree(T); } break; } show(); cin>>a; } } 四、调试分析 类型二,试题八 (一)设计内容简介 对一个字符串中的所有单词,如果单词的首字母不是大写字母,则把单词的首字母变成大写字母。 在字符串中,单词之间通过空白符分隔,空白符包括: 空格('')、制表符('\t')、回车符('\r')、换行符('\n')。 (二)算法设计说明 对于接收到的字符串根据分隔符来判断是否是新单词,如果是,将这个字符替换为大写。 具体可以定义一个标记变量,如果遇到分割符,那么它的下一个不是分隔符的字符必然是一个新单词的首字母,然后根据ASCII码判断是否是大写字母,如果不是将其转换为大写。 (三)测试结果 (四)分析与探讨 此题目考查对字符串的处理,难点在单词的判断上,即如何根据分割符判断新单词。 类型二,试题九 (一)设计内容简介 输入一个英文句子,长度不超过40个字符。 编写程序,输出句子中最长的一个单词。 (二)算法设计说明 本题与第八题类似,只是在发现新单词是统计新单词的字母个数,然后与之前的最大单词数目相比较,如果比较大,则记录此单词的开始下标。 最后输出这个下标单词。 (3)测试结果 (4)分析与探讨 字符串处理,加上了记录字符串下标。 类型二,试题十 (1)设计内容简介 判断一行字符串中的数字出现的个数。 (2)算法设计说明 以一个10个大小的数组来存储0~9共十个数字的出现字数,将它们初始化为0,遇到对应的输入,则将对应的数组加一。 最后输出在各个数组即可, (3)测试结果 (四)分析与探讨 此题目主要是判段数字的个数,使用数组存储。 四、小结体会 通过这两周的课程设计,加深了我对《数据结构》这门课程所学内容的进一步的理解与掌握; 刚开始没有什么头绪,通过各种资料的搜集后发现调用各种函数来实现比较容易,整个过程中出现了很多小问题,各个函数的调用比较混乱。 通过一系列的梳理后慢慢清晰,发现比较的容易。 我们都知道,做什么事都要认真,编程时更是如此,出现的错误要及时找出并改正,遇到问题要去查相关的资料,反复的调试程序,把各个要注意的问题要想到: 同时要形成自己的调试程序的风格,从每个细节出发,不放过每个知识点。 另外,要注意符号的使用。 争取让自己有一个明确的知识体系,以牢固掌握所学内容。 总之,此次课程设计使我对数据结构方面的知识有了更加深入的了解,也使我认识到自己在学习编程方面还有很多的不足。 今后我要多读一些编程方面的书籍,不能只拘泥于课本上的知识,并注重理论与实践的结合,多上机练习编写程序,提高自己的实际动手能力和独立思考的能力,不断充实自己,更好的掌握编程思想。 五、参考资料 《数据结构(C语言版)》严蔚敏、吴伟民等清华大学出版社 《数据结构课程设计》.苏仕华等机械工业出版社 《C++编程思想》BruceEckelChuckAllison刁成嘉译机械工业出版社 六、源代码 1.文章编辑 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 #include #include usingnamespacestd; //行链表结点 typedefstructline { char*data; structline*next; }LINE; voidCreate(LINE*&head) { printf("请输入一页文章,输入Ctrl+E后回车结束,(每行最多输入80字符): \n"); LINE*p=newLINE; head=p; chartmp[100]; while (1) { gets(tmp); if(strlen(tmp)>80) { printf("每行最多输入字符"); break; } if(tmp[0]==5)break;//如果发现输入^E,则退出 p=p->next=newLINE; p->data=newchar[strlen(tmp)+1]; strcpy(p->data,tmp); if(tmp[strlen(tmp)-1]==5)//除去最后一个控制符^E { p->data[strlen(tmp)-1]='\0'; break; } } p->next=NULL; head=head->next; } intCountLetter(LINE*&head)//统计字母数 { LINE*p=head; intcount=0; do { intLen=strlen(p->data); for(inti=0;i if((p->data[i]>='a'&&p->data[i]<='z')||(p->data[i]>='A'&&p->data[i]<='Z')) count++; } while((p=p->next)! =NULL); returncount; } intCountNumber(LINE*&head)//统计数字数 { LINE*p=head; intcount=0; do { intLen=strlen(p->data); for(inti=0;i if(p->data[i]>=48&&p->data[i]<=57)count++; } while((p=p->next)! =NULL); returncount; } intCountSpace(LINE*&head)//统计空格数 { LINE*p=head; intcount=0; do { intLen=strlen(p->data); for(inti=0;i if(p->data[i]==32)count++; } while((p=p->next)! =NULL); returncount; } intCountAll(LINE*&head)//统计文章的总字数 { LINE*p=head; intcount=0; do { count+=strlen(p->data); } while((p=p->next)! =NULL); returncount; } intFindString(LINE*&head,char
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)