《《物联网软件基础课程设计》指导书 .pdf》由会员分享，可在线阅读，更多相关《《物联网软件基础课程设计》指导书 .pdf（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、0 物联网软件基础课程设计指导书计算机科学与技术学院计工系2016年 6 月 12 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 38 页 -1 前 言软件基础课程设计是物联网专业的重要实践性课程。目的在于培养学生分析问题和解决问题的能力，为学生提供了一个既动手又动脑，独立实践的机会。将课本上的数据结构、离散数学和 C 语言的理论知识和实际应用问题进行有机结合，提高学生程序设计、程序调试及项目开发能力。为后续课程：操作系统、软件工程，编译原理等课程的学习奠定必要的实践基础。本课程设计是利用数据结构、离散数学、C/C+语言理论和实验课中学到的编程知识和编程技巧，通过布置具有一定
2、难度、一定编程量的课程设计题目，利用 C/C+语言作为开发工具，使学生通过课程设计掌握高级编程语言的知识和编程技术，掌握程序设计的思想和方法，初步具备利用计算机求解实际问题的能力。通过程序设计课程设计课程的学习，能够帮助学生加深理解数据结构、离散数学、C 语言基本概念，达到培养学生良好程序设计的习惯和运用C 语言编写程序解决实际问题的能力。使学生学会把书本知识用于解决实际问题，起到深化理解和灵活掌握教学内容的目的。同时使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。通过该课程设计，学生应该掌握C 或 C+语言程序设计的方法、数据结构和离散数学理论知识，熟悉C 或
3、 C+程序的开发环境及C 或 C+程序的调试过程，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力；学生应该具有如下基本技能：培养学生查阅参考资料、手册的自学能力，通过独立思考深入钻研问题，学会自己分析、解决问题。通过对所选题目方案分析比较，确立方案，编制程序与调试程序。能熟练调试程序，在教师的指导下，完成课题任务。根据个人的设计调试过程，按课程设计报告的要求撰写设计报告。选用教材及主要参考书：1.教材1 呼克佑.C 语言程序设计(计算机专业).中国宇航出版社，2002 2 严蔚敏.数据结构(C 语言版)清华大学出版社，2007 3 宋春花、吕进来等.C+面向对象程序设计.2.
4、主要参考书1 谭浩强.程序设计题解与上机指导(三版).清华大学出版社，2005 2 邱仲潘.C 语言参考手册.机械工业出版社，2004 3 郑莉.C+语言程序设计.清华大学出版社，2010 4 方世昌.离散数学.西安电子科技大学出版社，2003 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 38 页 -2 目 录前 言.1 一.课程设计报告要求.4 二.课程设计报告示例 迷宫问题 .5【问题描述】.5【需求分析】.5【概要设计】.5【详细设计】.7【功能的实现】（用 C 或 C+语言描述）.11【实例测试及运行结果】.11【实现提示】.错误！未定义书签。【用户手册】.错误！未定
5、义书签。【选作内容】.错误！未定义书签。三设计题目 .14 1保龄球计分.14 1.1 问题描述 .14 1.2 基本要求 .14 1.3 测试数据 .15 2.文本文件单词的检索与计数.15 2.1 问题描述.15 2.2 设计需求及分析.15 2.2.1 串模式匹配算法的设计要求.15 2.2.2 文本文件单词的检索与计数的设计要求.15 2.3 设计功能的实现（用C 或 C+语言描述）.16 2.3.1 朴素模式匹配算法 .16 2.3.2 给定位置的串匹配算法 .16 2.3.3 建立文本文件 .17 2.3.4 给定单词的计数 .17 2.3.5 检索单词出现在文本文件中的行号、次数
6、及其位置.18 2.3.6 运行主控程序 .18 2.4【实例测试及运行结果】.18 2.4.1 运行实例一 .18 2.4.2 运行实例二 .18 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 38 页 -3 2.5【实现提示】.18 3.停车场管理 .19 3.1 问题描述.19 3.2 设计需求及分析.19 3.3 设计功能的实现（用C 或 C+语言描述）.19 3.4 实例测试及运行结果.19 3.5 实现提示.19 4.交通咨询系统设计（最短路径问题）.20 4.1 问题描述.20 4.2 设计需求及分析.20 4.2.1 建立图的存储结构 .20 4.2.2 单源最
7、短路径 .21 4.2.3 任意一对顶点间最短路径.21 4.3 设计功能的实现（用 C 或 C+语言描述）.22 4.3.1 建立有向图的存储结构 .22 4.3.2 迪杰斯特拉算法 .22 4.3.3 费洛伊德算法 .22 4.3.4 运行主控程序 .22 4.4 实例测试及运行结果 .22 4.4.1 运行实例一 .22 4.4.2 运行实例二 .23 5校园导游咨询 .24 5.1 问题描述.24 5.2 基本要求.24 5.3 测试数据.24 5.4 实现提示.24 6.学生管理系统 .25 6.1 问题描述.25 6.2 设计需求及分析.25 6.3 设计功能的实现（C+语言描述）
8、.25 6.4 实例测试及运行结果.36 6.5 实现提示.37 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 38 页 -4 一、课程设计报告要求课程设计要求选做任意四个题目即可。课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出题目，内容包括以下五项：1【问题描述】简要描述问题，然后说明程序设计的任务，程序要做什么。明确规定以下内容：（1）输入的形式和输入值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2【问题分析与设计】分析问题，简述解决的思想或方法，说明本程序中用到
9、的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。实现设计中定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也写出伪码算法（伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。3【功能实现】（用 C 或 C+描述）/说明：用C 或 C+实现代码设计。4【实例测试及运行结果】列出测试结果，包括输入和输出。测试数据应该完整、严格。测试分析内容包括：（1）测试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析；（2）算法的时空分析和改进设想；（3）经验和体会。5【心得体会】谈谈在设计和调试过程中的收获
10、。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 38 页 -5 二课程设计报告示例 迷宫问题(参考)专业：_ 班级：_ 姓名：_ 学号：_ 完成日期：_【问题描述】编制一个求解迷宫通路的程序。以一个m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标,d 表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1）
11、，（1，2，2），（2，2，2），（3，2，3），（3，1，2）【问题分析与设计】一、问题分析（1）以二维数组MAZEM+2N+2表示迷宫，其中：MAZE0J 和 MAZEM+1J（0JN+1）及 MAZEI0和 MAZEIN+1（0I M+1）为添加的一圈障碍。数组中以元素值为0表示通路，1 表示障碍。限定迷宫的大小M，N 10。（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数M 和列数 N；从第 2 行至第 M+1 行（每行N 个数）为迷宫值，同一行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式
12、将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“”表示“死胡同”，即曾经经过但不能到达出口的位置，其余用空格符表示。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。（6）程序执行的命令为：1）创建迷宫；2）求解迷宫；3）输出迷宫的解。二、概要设计1设定栈的抽象数据类型定义为：ADT stack 数据对象：D=ai|aicharset,i=1,2,n,n 0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个
13、空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 38 页 -6 ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(&S)初始条件：栈S已存在。操作结果：返回栈S 的长度。StackEmpty(&S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S 不空，则以e 返回栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S 的栈顶插入新的栈顶元素e。
14、Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S 的栈顶元素，并以e 返回其值。StackTraverse(S,visit()初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit().ADT stack 2设定迷宫的抽象数据类型为：ADT maze 数据对象：D=ai,j|ai,j,?、,#?、,?、,*?，0i m+1,0j n+1,m,n10数据关系：R=ROW，COL ROW=|ai-1,j，ai,jD,i=1,，m+1,j=0,，n+1 COL=|ai,j-1,ai,j D,i=0,，m+1,j=1,，n+1 基本操作：InitMaze(&M,a
15、,row,col)初始条件：二维数组arow+2col+2 已存在，其中自第1 行至第 row+1 行、每行中自第1 列至第 col+1 列的元素已有值，并且以值0 表示通路，以值1 表示障碍。操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符,#?表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M 已被赋值。操作结果：若迷宫M 中存在一条通路，则按如下规定改变迷宫M 的状态：以字符“*”表示路径上的位置，字符“”表示“死胡同”；否则迷宫的状态不变。PrintMaze(M)初始条件：迷宫M 已存在。操作结果：以字符形式输出迷宫。ADT maze;3.本程序包含
16、三个模块1）主程序模块名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 38 页 -7 void main()初始化do 接受命令；处理命令；while(命令！=“退出”)；2）栈模块-实现栈抽象数据类型3）迷宫模块-实现迷宫抽象数据类型各模块之间的调用关系如下：主程序模块迷宫模块栈模块4求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do 若当前位置可通，则 将当前位置插入栈顶；/纳入路径若该位置是出口位置，则结束；/求得路径存放在栈中否则切换当前位置的东邻方块为新的当前位置；否则 若栈不空且栈位置尚有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位
17、置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/后退一步，从路径中删去该通道块，若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；while(栈不空)；栈空说明没有路径存在 三、详细设计1坐标位置类型typedef struct int r,c;/迷宫中行、列的范围PosType;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 38 页 -8 2迷宫类型typedef struct int m,n;char arrRANGERANGE;/各位置取值,?,#?,?或,*?MazeType;void InitMaze(MazeType&maz
18、e,int a,int row,int col)/按照用户输入的row 行和 col 列的二维数组（元素值为0 或 1）/设置迷宫的初值，包括加上边缘一圈的值bool MazePath(MazeType&maze,PosType start,PosType end)/求解迷宫maze中，从入口start 到出口 end 的一条路径/若存在，则返回TRUE；否则返回FALSE void PrintMaze(MazeType maze)/将迷宫以字符型方阵的形式输出到标准输出文件上3栈类型typedef struct int step;/当前位置在路径上的“序号”PosType seat;/当前的
19、坐标位置directiveType di;/往下一坐标位置的方向ElemType;/栈的元素类型typedef struct NodeType ElemType data;NodeType*next;NodeType,*LinkType;/结点类型，指针类型typedef struct LinkType top;int size;Stack;/栈类型栈的基本操作设置如下：void InitStack(Stack&S)/初始化，设S为空栈（S.top=NULL）void DestroyStack(stack&S)/销毁栈 S，并释放所占空间void ClearStack(Stack&S)/将 S
20、清为空栈int stackLength(Stack S)/返回栈 S 的长度 S.size Status StackEmpty(Stack S)/若 S为空栈（S.top=NULL）,则返回 TRUE;否则返回FALSE Status GetTop(Stack s,ElemType e)/若栈 S 不空,则以 e 带回栈顶元素并返回TRUE,否则返回FALSE;Status Push(Stack&S,ElemType e)/若分配空间成功,则在 S的栈顶插入新的栈顶元素e,并返回 TRUE,/否则栈不变,并返回 FALSE Status Pop(Stack&S,ElemType&e)名师资料总
21、结-精品资料欢迎下载-名师精心整理-第 9 页，共 38 页 -9/若栈不空,则删除 S 的栈顶元素并以e 带回其值，且返回TRUE/否则返回FALSE void StackTraverse(Stack s,Status(*visit)(ElemType e)/从栈底到栈顶依次对S中的每个结点调用函数visit 其中部分操作的算法：Status Push(Stack&S,ElemType e)/若分配空间成功，则在S 的栈顶插入新的栈顶元素e，并返回TRUE；/否则栈不变，并返回FALSE if(MakeNode(p,e)p-next=s.top;s.top=p;s.size+;return
22、TRUE;else return FALSE;Status Pop(Stack&S,ElemType&e)/若栈不空，则删除S 的栈顶元素并以e带回其值，且返回TRUE，/否则返回 FALSE，且 e 无意义if(StackEmpty(S)return FALSE;else p=S.top;S.top=S.top-next;e=p-date;S.size-;return TRUE;4.求迷宫路径的伪码算法：Status MazePath(MazeType maze,PosType start,PosType end)/若迷宫中存在从入口start 到出口 end 的通道,则求得一条存入在栈中/
23、（从栈底到栈顶为从入口到出口的路径），并返回TRUE；否则返回FALSE InitStack(S);curpos=start;/设定“当前位置”为“入口位置”curstep=1;found=FALSE;/探索第一步do if(Pass(maze,curpos)/当前位置可以通过，即是未曾走到过的通道块留下足迹FootPrint(maze,curpos);e=(curstep,curpos,1);Push(S,e);/加入路径if(Same(curpos,end)found=TRUE;/到达终点（出口）else curpos=NextPos(curpos,1);/下一位置是当前位置的东邻curs
24、tep+;/探索下一步/else/if else/当前位置不能通过if(!StackEmpty(S)名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 38 页 -10 Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(maze,e,seat);Pop(S,e);curstep-;/留下不能通过的标记，并退回一步/while if(e.di4)e.di+;Push(S.e);/换下一个方向探索curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上的相邻块/if/if while(!StackEmpty(S)&!f
25、ound);return found;/MazePath 5主函数和其他函数的伪码算法void main()/主程序Initialization();/初始化do ReadCommand(cmd);/读入一个操作命令符Interpret(cmd);/解释执行操作命令符while(cmd!=,q?&cmd!=,Q?);/main void Initialization()/系统初始化clrscr();/清屏在屏幕上方显示操作命令清单：CreatMazec MazePathm PrintMaze p Quitq;在屏幕下方显示操作命令提示框：/Initialization void ReadCom
26、mand(char&cmd)/读入操作命令符显示键入操作命令符的提示信息；do cmd=getche()while(cmd,c?,C?，,m?,M?,p?,P?,q?,Q?)；/ReadCommand void Interpret(char cmd)/解释执行操作命令switch(cmd)case,c?,?C?:提示用户输入“迷宫数据的文件名filename”；从文件读入数据分别存储在rnum，cnum 和二维数组a2中；InitMaze(ma,a2,rnum,cnum);/创建迷宫输出迷宫建立完毕的信息break;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 38 页 -1
27、1 case,m?,M?:提 示 用 户 输 入 迷 宫 的 入 口from和 出 口term的 坐 标 位 置；if(MazePath(ma,from,term)/存在路径提示用户察看迷宫；else 输出该迷宫没有从给定的入口到出口的路径的信息；break；case,p?,P?:PrintMaze(ma):/将标记路径信息的迷宫输出到终端/switch/InterPret 6函数的调用关系图反映了演示程序的层次结构：主程序Initialization ReadCommand InterPret InitMaze MazePath PrintMaze InitStack Push Pop St
28、ackEmpty StackTraverse FootPrint MarkPrint Pass NextPos Same【功能实现】（用 C 或 C+语言描述）说明：此内容由学生自己设计完成。附录：源程序文件名清单：base.H/公用的常量和类型stkpas.H/栈类型maze.H/迷宫类型testmaze.C/主程序【实例测试及运行结果】迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 38 页 -12 提示：当入口位置为（1，1），出口位置为（9，8）时，输出数据应为：*#*#*#*#*#*#*#*#*#*#
29、*测试结果示例：三组测试数据和输出结果分别如下：1输入文件名为：m1.dat，其中迷宫数据为：3 2 0 0 0 0 0 0 入口位置：1 1 出口位置：3 2 求解路径后输出的迷宫：*2输入文件名：m2.dat，其中迷宫数据为：3 4 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 名师资料总结-精品资料欢迎
30、下载-名师精心整理-第 13 页，共 38 页 -13 入口位置：1 1 出口位置：3 4 求解路径后输出的迷宫：*#*3输入文件名：m3.dat，其中迷宫数据同题目中的测试数据。入口位置：1 1 出口位置：9 8 求解路径后输出的迷宫正确，并和需求分析中所列相同。4输入文件名：m4.dat，其中迷宫数据为：4 9 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 入口位置：1 1 出口位置：4 9 输出信息为：此迷宫从入口到出口没有路径。【心得体会】1本次作业比较简单，只有一个核心算法，即求迷宫的路
31、径，所以总的调试比较顺利，只在调试 MazePath 算法时，遇到两个问题：其一是，起初输出的迷宫中没有加上,?的记号，后发现是因为在MarkPrint 函数中的迷宫参数丢失“变参”的原因；其二是，由于回退时没有将curpos 随之减一，致使栈中路径上的序号有错。2栈的元素中的step域没有太多用处，可以省略。3StackTraverse 在调试过程中很有用，它可以插入在MazePath 算法中多处，以察看解迷宫过程中走的路径是否正确，但对最后的执行版本没有用。4本题中三个主要算法：InitMaze,MazePath 和 PrintMaze 的时间复杂度均为0（m*n），本题的空间复杂度亦为0
32、（m*n）（栈所占最大空间）5经验体会：借助DEBUG 调试器和数据观察窗口，可以加快找到程序中疵点。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 38 页 -14 三设计题目（6 选 4）1保龄球计分1.1 问题描述打保龄球是用一个滚球去撞击10 个站立的瓶，将瓶击倒。一局分10 轮，每轮可滚球1 次或2 次，以击到的瓶数为依据计分。一局得分为10 轮得分之和，而每轮的得分不仅与本轮的滚球情况有关，还可能与后一轮或后两轮的滚球情况有关，即：某轮某次滚球击倒的瓶数不仅要计入本轮得分，还可能会计入前一轮或两轮得分。计分规则如下：若某一轮的第一次滚球就击倒全部10 个瓶，则本轮不
33、再滚球（若是第十轮还需加2次滚球），该轮得分为本次击倒瓶数10 与以后 2 次滚球所击倒瓶数之和；若某一轮的第一次滚球未击倒全部10 个瓶，则对剩下未倒的瓶再滚球一次，如果这 2 次滚球击倒全部10 个瓶，则本轮不再滚球（若是第十轮还需加1 次滚球），该轮得分为这2 次击倒瓶数 10 与以后 1 次滚球所击倒瓶数之和；若某一轮2 次滚球未击倒全部10 个瓶，则本轮不在滚球，该轮得分为这2 次滚球所击倒瓶数之和。1.2 基本要求模拟 1 人打保龄球的过程，用一个二维数组：int x114；存储每轮每次击倒的瓶数和得分以及累计得分。即：i 行中的4 个元素xi0、xi1、xi2、xi3分别记录第i
34、轮的第 1 次滚球击倒的瓶数、第2 次滚球击倒的瓶数、本轮得分和累计得分；输入每轮每次滚球击倒的瓶数，若第1次滚球击倒的瓶数为10，则该轮只输入1 次数据；输出每轮每次击倒的瓶数和得分以及累计得分；例如：一二三四五六七八九十8 10 7 9 9 10 10 8 9 10 8 2 0 2 1 1 0 0 1 1 0 2 20 19 9 19 20 28 19 9 20 20 20 39 48 67 87 115 134 143 163 183 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 38 页 -15 1.3 测试数据如上所示。【注】鼓励采用屏幕绘图模拟打球过程；思考：模拟
35、N人打保龄球的过程。2.文本文件单词的检索与计数2.1 问题描述串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串变量与其他变量（如整型、实型等）一样，可以进行各种运算。然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实现串的处理，就必须熟悉串的存储结构及其基本运算。本课程设计的目的就是熟悉串类型的实现方法和文本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理技术。本课程设计分两步：首先，设计出串定位算法（即模式匹配算法）及其实现；然后，再利用串定位算法设计文本文件的检索及单词的计数等
36、操作。2.2 设计需求及分析2.2.1 串模式匹配算法的设计要求在 串 的基 本 操作 中，在主 串 中查 找 模式 串的 模式 匹 配算 法 即求 子串 位 置的 函数Index(S,T)，是文本处理中最常用、最重要的操作之一。所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从主串的任一给定位置检索匹配字符串，所以，首先要给出两个
37、算法：1标准的朴素模式匹配算法2给定位置的匹配算法2.2.2 文本文件单词的检索与计数的设计要求要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，
38、共 38 页 -16 1建立文本文件2给定单词的计数3检索单词出现在文本文件中的行号、次数及其位置4主控菜单程序的结构2.3 设计功能的实现（用C 或 C+语言描述）/说明：要求由学生来完成代码的编写。2.3.1 朴素模式匹配算法该算法的基本思想是：设有三个指针 i,j,k，用 i 指示主串S 每次开始比较的位置；指针 j,k分别指示主串S 和模式串T 中当前正在等待比较的字符位置；一开始从主串S 的第一个字符（i=0;j=1）和模式T 的第一个字符（k=0）比较，若相等，则继续逐个比较后续字符（j+,k+）。否则从主串的下一个字符（i+）起再重新和模式串（j=0）的字符开始比较。依此类推，直
39、到模式T 中的所有字符都比较完，而且一直相等，则称匹配成功，并返回位置i；否则返回-1，表示匹配失败。顺序串的模式匹配算法如下：int index(SString S,SString T)/求子串 T 在主串 S中首次出现的位置int i,j,k,m,n;m=T.length;/模式串长度赋m n=S.length;/目标串长度赋n for(i=0;i=n-m;i+)j=0;k=i;/目标串起始位置i 送入 k while(j=m&s.chk=t.chj)k+;j+;/继续下一个字符的比较if(j=m)/若相等，则说明找到匹配的子串，返回匹配位置i，/否则从下一个位置重新开始比较return
40、i;/endfor return-1;/endIndex 2.3.2 给定位置的串匹配算法该算法要求从串S1（为顺序存储结构）中第k 个字符起，求出首次与字符串S2 相同的子串的起始位置。该算法与上面介绍的模式匹配算法类似，只不过上述算法的要求是从主串的第一个字符开始，该算法是上述算法的另一种思路：从第 k 个元素开始扫描S1，当其元素值与S2 的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到 S2 结束为止。若都相同，则返回当前位置值；否则继续上述过程，直至S1 扫描完为止，其实现算法如下：Int PartPosition(SString S1,SString S2,int k
41、)名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 38 页 -17 int i,j;i=k-1;/扫描 s1 的下标，因为c 中数组下标是从0 开始，串中序号相差1 j=0;/扫描 s2的开始下标while(is1.length&j=s2.length)return i-s2.length;/表示 s1中存在 s2，返回其起始位置else return-1;/表示 s1 中不存在s2，返回-1 /函数结束说明：以上两个算法可统一为一个算法，即在子串定位算法Index(S,T)的参数中增加一个起始位置参数即可。2.3.3 建立文本文件建立文件的实现思路是：（1）定义一个串变量；（
42、2）定义文本文件；（3）输入文件名，打开该文件；（4）循环读入文本行，写入文本文件，其过程如下：While(不是文件输入结束)读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；（5）关闭文件。2.3.4 给定单词的计数该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个文件扫描结束；然后输出单词出现的次数。其实现过程如下：（1）输入要检索的文本文件名，打开相应的文件；（2）输入要检索统计的单词；（3）循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。具体描述如下：While(不是文件结束)读入一行并到串中
43、；求出串长度；名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 38 页 -18 模式匹配函数计数；（4）关闭文件，输出统计结果。2.3.5 检索单词出现在文本文件中的行号、次数及其位置这个设计要求与上一个类似，但要相对复杂一些。其实现过程描述如下：（1）输入要检索的文本文件名，打开相应的文件；（2）输入要检索统计的单词；（3）行计数器置初值0；（4）while(不是文件结束)读入一行到指定串中；求出串长度；行单词计数器置0；调用模式匹配函数匹配单词定位、该行匹配单词计数；行号计数器加1；If(行单词计数器!=0)输出行号、该行有匹配单词的个数以及相应的位置；2.3.6 运行主控
44、程序主控菜单程序的结构要求内容如下：（1）头文件包含；（2）菜单选项包括：1建立文件2单词计数3单词定位4退出程序（3）选择 1 4 执行相应的操作，其他字符为非法。2.4【实例测试及运行结果】2.4.1 运行实例一（说明：由学生自己来给出）2.4.2运行实例二（说明：由学生自己来给出）2.5【实现提示】（说明：由学生自己来补充）名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 38 页 -19 3.停车场管理3.1 问题描述设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一
45、辆车停放在停车场的最北端）,若停车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。3.2 设计需求及分析以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：
46、若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。3.3 设计功能的实现（用C 或 C+语言描述）/说明：此内容由学生自己设计完成。3.4 实例测试及运行结果设 n=2，输入数据为：（,A?,1,5）,（,A?,2,10）,（,D?,1,15）,（,A?,3,20）,（,A?,4,25）,（,A?5,30）,（,D?,2,35）,（,D?,4,40）,（,E?,0,0）。其中：,A?表示到达（arrival）；,D?表示离去（departure）；,E?表示输入结束
47、（end）。3.5 实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。/说明：要求由学生来补充。名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 38 页 -20 4.交通咨询系统设计（最短路径问题）4.1 问题描述在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计
48、算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A 城到 B 城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A 到顶点 B 的所含边数目最少的路径。我们只需要从顶点A 出发对图作广度优先搜索，一旦遇到顶点B 就终止。由此所得广度优先生成树上，从根顶点 A 到顶点 B 的路径就是中转次数最少的路径。路径上 A 与 B 之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设
49、计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。4.2 设计需求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。4.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n 阶方阵：设 G=（V，E）是一个图，结点集为nvvvV,21。G 的邻接矩阵,E,0E,)(,)(jijiji
50、jinnjiijnnijvvvvvvvvwaaA）或当（，或）或当（，当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n 个元素的一维数组来存储顶点信息，其中下标为i 的元素存储顶点i 的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50/最大顶点数typedef struct VertexType vexsMVNum;/顶点数组，类型假定为char 型Adjmatrix arcsMVNumMVNum;/邻接矩阵，假定为int 型名师资料总结-精品资料欢