[工学]太原理工大学《程序设计》课程设计

1、程序设计课程设计姓 名：郭雨晴学 号：班 级：软件1003班指导教师：呼克佑、李誌成 绩：2012年6月设计题目一1 文本文件单词的检索与计数1.1【问题描述】设计C或C+程序，统计在这样的英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为单词(不包括数字)，单词之间用空格或标点符号分隔。 1.2【设计需求及分析】要统计英文文本文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。线性表的顺序存储结构如下：#define LIST_INIT_SI

2、ZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct char word21 /存储单词，不超过20个字符 int count; /单词出现的次数 ElemType;typedef struct ElemType *elem; /存储空间基址 int length; /当前长度int listsize; /当前分配的存储容量 Sqlist;1.3【设计功能的实现】（用C或C+语言描述）#include #include #include #define LIST_INIT_SIZE 100#defin

3、e LISTINCREMENT 10typedef structchar word21;int count; ElemType;typedef structElemType *elem;int length;int listsize; SqList;int InitList(SqList *p)p-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(p-elem=NULL) return 0;p-length=0;p-listsize=LIST_INIT_SIZE;return 1;int LocateElem(SqList *p

4、,char *word)int low,high,mid;low=0;high=p-length-1;while(lowelemmid.word)=0) /表中进行二分查找p-elemmid.count+;return 0;else if(strcmp(word,p-elemmid.word)length=p-listsize)base=(ElemType*)realloc(p-elem,(p-listsize+LISTINCREMENT)*sizeof(ElemType);if(base=NULL) return 0;p-listsize=p-listsize+LISTINCREMENT;

5、/扩充表长p-elem=base;for(j=p-length;j=i;j-)p-elemj=p-elemj-1;strcpy(p-elemi-1.word,word);p-elemi-1.count=1;p-length+;return 1;void PrintList(SqList *p,int num)FILE *fw;int i;int no=num;fw=fopen(F:单词计数.txt,w);fprintf(fw,文章共有%d个单词n以下按字典顺序排序显示出现次数n*n,no);fprintf(fw,单词 出现次数n,no);for(i=0;ilength;i+)fprintf(f

6、w,%-24s %-5dn,p-elemi.word,p-elemi.count);fprintf(fw,*n);fclose(fw);/主函数void main()SqList L;char word21,ch,filename30,filename150;int num=0,i,j=0,mark=0;FILE *fp;InitList(&L);printf(请将文件放入F盘，并输入文件名:n);scanf(%s,&filename);sprintf(filename1,F:%s.txt,filename);getchar();if(fp=fopen(filename1,r)=NULL)pr

7、intf(打开文件失败，请确认文件名与文件路径！n);getchar();exit(0);ch=fgetc(fp);while(ch!=EOF)if(ch=A&ch=a&ch=A&ch20)printf(文章中部分单词太长不予统计);num+;wordj=0;mark=0;j=0;i=LocateElem(&L,word);if(i0)InsertList(&L,i,word);ch=fgetc(fp);fclose(fp);printf(统计结束！单词计数.txt文件已经在F盘生成。);PrintList(&L,num);getchar();1.3.1 实现顺序表的基本操作顺序表的初始化：I

8、nitList(SqList &L)顺序表上查找指定的单词：LocateElem(SqList &L,char *s) 若找到，单词的出现次数增1，返回0，否则返回该单词的插入位置。在顺序表上插入新的单词：InsertList(SqList &L,int i，char *s) 要求按字典顺序有序。新单词的出现次数为1.输出顺序表上存储的单词统计信息：PrintList(SqList &L) 输出文件中每个单词出现的次数以及文件中总的单词数(可输出到文件中)。1.3.2 统计单词数统计过程如下：（1）输入要统计单词的文本文件名，打开相应的文件；（2）初始化顺序表；（3）从文本文件中读取字符，直到

9、文件结束。具体描述如下：While (读文件没有结束) 过滤单词前的非字母字符； 读取一个单词，已字符串形式存储在一个字符数组中； 在线性表中查找该单词，若找到，单词的出现次数加1，否则返回其插入位置； 上一步中，若没找到，则进行插入操作； 处理下一个单词。（4） 关闭文件，输出统计结果。1.4【实例测试及运行结果】1.4.1 运行实例一 文章：TUT 运行结果： 程序显示： 1.4.1 运行实例二文章：Beautiful运行结果： 程序显示： 设计题目二2停车场管理2.1【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依

10、次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2.2【设计需求及分析】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时

11、刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。2.3【设计功能的实现】（用C或C+语言描述）#include#include #include#include#define MAX 10#define price 0.05 typedef struct time int hour;int min;time; typedef struct carnode char num10; time reach; time leav

12、e; carnode; typedef struct carstack carnode *stackMAX+1; int top; carstack; typedef struct qnode carnode *data; struct qnode *next; qnode; typedef struct node qnode *head; qnode *rear; linkqueue; void initstack(carstack *s) int i; s-top=0; for(i=0;istacks-top=NULL; int initqueue(linkqueue *Q) Q-head

13、=(qnode *)malloc(sizeof(qnode); if(Q-head!=NULL) Q-head-next=NULL; Q-rear=Q-head; return 1; else return -1; /车辆到达 int arrival(carstack *enter,linkqueue *w) carnode *p; qnode *t; p=(carnode *)malloc(sizeof(carnode); printf(n请您输入车牌号：); scanf(%s,&p-num); if(enter-toptop+; printf(n该车停在的位置：%d号,enter-top)

14、; printf(n请您输入车到达的时间：); scanf(%d:%d,&(p-reach.hour),&(p-reach.min); enter-stackenter-top=p; return 1; else /没有空车位 printf(对不起，停车场已满请您停在便道上！); t=(qnode *)malloc(sizeof(qnode); t-data=p; t-next=NULL; w-rear-next=t; w-rear=t; return 1; void print(carnode *p,int room)/汽车离站时缴费显示 printf(n车辆离开的时间：); scanf(%

15、d:%d,&p-leave.hour,&p-leave.min); printf(n离开车辆的车牌号为:%s,p-num); printf(n其到达时间为：%02d:%02d,p-reach.hour,p-reach.min); printf(n其离开时间为：%02d:%02d,p-leave.hour,p-leave.min); printf(n应缴费用为：%.2f元,(p-leave.hour-p-reach.hour)*60+(p-leave.min-p-reach.min)*price); free(p); /车辆离开 void leave(carstack *enter,carsta

16、ck *temp,linkqueue *w) int room; carnode *p,*t; qnode *q; if(enter-top0)/有车 while(1) printf(n请您输入车在停车场上的位置:); scanf(%d,&(room); if(room=1&roomtop) break; while(enter-toproom)/位置不在栈顶的汽车出栈 temp-top+; temp-stacktemp-top=enter-stackenter-top; enter-stackenter-top=NULL; enter-top-; p=enter-stackenter-top

17、; enter-stackenter-top=NULL; enter-top-; while(temp-top=1)/当暂时存储汽车的栈结构中有汽车时 enter-top+; enter-stackenter-top=temp-stacktemp-top; temp-stacktemp-top=NULL; temp-top-; print(p,room); /判断便道上是否有车及停车场上是否已满 if(w-head!=w-rear)&enter-tophead-next; t=q-data; enter-top+; printf(n请便道上的%s号车进入第%d位置。,t-num,enter-t

18、op); printf(n请输入现在的时间：); scanf(%d:%d,&(t-reach.hour),&(t-reach.min); w-head-next=q-next; if(q=w-rear) w-rear=w-head; enter-stackenter-top=t; free(q); else printf(n便道里没有车！); else printf(n现在停车场里没有车了！); /显示停车场的信息 void list1(carstack *s) int i; if(s-top0) printf(n停车场：); printf(n停车位置t到达时间t车牌号n); for(i=1;

19、itop;i+) printf( %dt,i); printf( %02d:%02d ,s-stacki-reach.hour,s-stacki-reach.min); printf(t%s,s-stacki-num); else printf(n对不起，暂无停车场里的信息！); /显示便道上的 void list2(linkqueue *w) qnode *p; p=w-head-next; if(w-head!=w-rear) printf(n等待车辆的号码为：); printf(n*); while(p!=NULL) puts(p-data-num); p=p-next; printf(

20、n*); else printf(n便道里没有车！); void list(carstack s,linkqueue w) int flag,tag; flag=1; while(flag) printf(n请选择：); printf(ntt1、停车场信息ntt2、便道信息ntt3、返回主菜单n); while(1) scanf(%d,&flag); if(flag=1|flaghead-next=q-next; if(q=w-rear) w-rear=w-head; enter-stackenter-top=t; free(q); 设计题目三3交通咨询系统设计（最短路径问题）3.1【问题描述

21、】在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度

22、优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。3.2【设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。3.2.1建立图的存

23、储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMV

24、Num; /邻接矩阵，假定为int型MGraph;3.2.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有向边，则costij的权为无穷大（这里取值为3276

25、7）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为disti=costv1i,i=1,2,n。从S之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点

26、到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0； /S集初始时只有源点，源点到源点的距离为0；While (S集中顶点数n)开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离；3.2.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(vw)”,找出v到w的最短路径。要解决这

27、个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的

28、；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。3.3【设计功能的实现】（用C或C+语言描述）3.3.1 建立有向图的存储

29、结构void CreatGraph(Graph *m) int i, j;int head, tail, weight;char ch;printf(输入地点个数和路线条数：n); scanf(%d%d,&(m-vexnum), &(m-arcnum);if(m-vexnumarcnumarcs = (ArcCell *)malloc(sizeof(ArcCell *)*(m-vexnum); for(i=0; ivexnum; i+)m-arcsi = (ArcCell *)malloc(sizeof(ArcCell)*(m-vexnum);for(j=0; jvexnum; j+)(m-a

30、rcsij).adj = 0; (m-arcsii).adj = 1;(m-arcsii).weight = 0;printf(输入带权有向图的弧（按弧头、弧尾、权值的顺序,顶点序号由零开始）n); for(i=0; iarcnum; i+)scanf(%d%d%d,&head, &tail, &weight);if(head0 | tail0 | weight arcsheadtail).weight = weight;(m-arcsheadtail).adj = 1;void PrintGraph(Graph *m)int v = m-vexnum;int i,j;for(i=0; iv;

31、 i+)for(j=0; jarcsij.adj)printf(%-5d,(m-arcs)ij.weight);else printf( );printf(n);BiTree BiTreePathGrow(BiTree cold, int *travel, int v,int w) int u = travelvw; if(u=-1)return cold;cold = (BiTree)malloc(sizeof(Node);cold-data = u;cold-lchild = NULL;cold-rchild = NULL;if(traveluw=0)BiTreePathGrow(cold

32、-rchild,travel,u,w);if(travelvu=0)BiTreePathGrow(cold-lchild,travel,v,u);return cold;void InOrderTraversalBiTree(BiTree cold, void (*fun)(int) if(!cold)return;InOrderTraversalBiTree(cold-lchild,fun);fun(cold-data);InOrderTraversalBiTree(cold-rchild,fun);void PrintData(int travel)printf(%-5d,travel);

33、3.3.2 迪杰斯特拉算法void ShortestPathbyDIJ(Graph *m, int v0) int V = m-vexnum;int v,w,i,j;int min;int *remote; char *final; int *travel; int *pain; final = (char *)malloc(sizeof(char)*V);travel = (int *)malloc(sizeof(int *)*V); pain = (int *)malloc(sizeof(int)*(V-2);remote = (int *)malloc(sizeof(int)*V);fo

34、r(v=0; varcsv0v.adj)remotev = m-arcsv0v.weight;else remotev = INFINITY;travelv = (int *)malloc(sizeof(int)*(V-2); remotev0 = 0;finalv0 = 1; for(i=0; iV; i+) /i为计数器，循环 vexnum-1 次min = INFINITY;for(w=0; wvexnum; w+)if(finalw=0 & remotewmin)v = w;min = remotew;/计算后的路径finalv = 1; for(w=0; warcsvw).adj)i

35、f( (min + (m-arcsvw).weight) arcsvw.weight);/更新路径for(j=0; jpainv; j+)travelwj = travelvj;painw = painv+1;travelwj = v;/*=输出最短路径start=*/for(i=0; iV; i+)if(i != v0)printf(从%d点出发到%d点,v0,i);if(remotei INFINITY)printf(的最短路径（总权值为%d）为：n%d-,remotei,v0);if(paini)printf(-,m-arcsv0traveli0.weight);for(v=1; v p

36、aini ; v+) printf(%d-,traveliv-1,(m-arcs traveliv-1 traveliv ).weight);v-;printf(%d-,traveliv, (m-arcs traveliv i).weight); printf(%dn,i);elseprintf(-%dn,m-arcsv0i.weight,i);elseprintf( 此路不通()n);printf(n); /*=输出最短路径end=*/ 3.3.3 费洛伊德算法void ShortestPathbyFLOYD(Graph *night,int meet,int bye)BiTree BiTr

37、eePathGrow(BiTree, int *travel, int v,int w); /由路径创建二叉树void InOrderTraversalBiTree(BiTree cold, void (*fun)(int); /中序遍历二叉树void PrintData(int);int u, v, w;int pain = night-vexnum;int *travel; int *remote; int forget;BiTree cold;travel = (int *)malloc(sizeof(int *)*pain);remote = (int *)malloc(sizeof(

38、int *)*pain);/初始化for(v=0; vpain; v+)travelv = (int *)malloc(sizeof(int)*pain);remotev = (int *)malloc(sizeof(int)*pain);for(w=0; warcsvw.adj)remotevw = night-arcsvw.weight;else remotevw = INFINITY;for(v=0; vpain; v+)for(w=0; wpain; w+)if(v!=w)for(u=0; upain; u+)if(v!=u & w!=u)if(forget=remotevu+remo

39、teuw) remotevw) travelvw = u;remotevw = forget; /输出最短路径（通过二叉树）printf(从%d点到%d点,meet,bye);if(remotemeetbye INFINITY)printf(的最短路径的权值为%d：n,remotemeetbye);cold = NULL;cold = BiTreePathGrow(cold,travel,meet,bye);printf(路过的点为：n);if(!cold)printf(无（不路过任何点）：n);elseInOrderTraversalBiTree(cold,PrintData); printf(nn);elseprintf(