厦门理工数据结构课程设计报告2.doc

数据结构与算法课程设计报告（2012 2013学年 第 1 学期）专 业： 网络工程 班 级： 11网络工程 姓名学号： 1107022144 指导教师： 林仙丽 成 绩： 计算机科学与技术系2013年 01月11日目 录一 课程设计目的与要求 11设计目的1 2设计任务及要求 1二 .方案实现与调试 11 停车场管理系统11.1算法描述及实验步骤21.2调试过程及实验结果32字符串操作 42.1算法描述及实验步骤52.2调试过程及实验结果63找祖先83.1算法描述及实验步骤93.2调试过程及实验结果104二叉树运算284.1算法描述及实验步骤94.2调试过程及实验结果1三课程设计分析与总结10四 源程序清单111.停车场管理系统112字符串操作 193.找祖先224.二叉树运算225五设计日志31六指导教师评语32一. 课程设计的目的与要求（含设计指标）1、设计目的（1）培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。（2）培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。（3）培养学生初步的软件设计及软件测试的能力。2、设计任务及要求基本要求：学生必须仔细阅读数据结构课程设计指导书，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准； 二. 方案实现与调试2.1 题目：某停车场可以停放n辆汽车，该停车场只有一个大门， 每辆汽车离开停车场都要求之前的汽车必须先退出停车场为它让道，而后让道的汽车再次驶入停车场，停车场示意图如下：要求设计停车管理系统，实现车辆的进入、离开并根据停车时间计费。2.1.1算法描述及实验步骤 停车场管理系统停车场信息退出系统车辆停车车辆离开车库停车便道停车便道信息停车场信息返回主菜单停车位置应缴纳费用停车时刻离开时刻停车位置到达时刻车牌号等待中的车牌号停车时刻停车位置车牌号2.1.2调试过程及实验结果2.2题目：字符串的操作： 任务：字符串采用数组存储，建立两个字符串String1和String2.输出两个字符串。 将字符串String2的头n个字符添加到String1的尾部，输出结果。 查找String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。2.2.1算法描述及实验步骤 void InitString(Sstring *S,int max,char *string);初始化字符串S，将string的字符复制到S中；int Insert(Sstring *S, int pos, Sstring T)：在主串S的pos位置插入子串T;int SubString(Sstring *T,Sstring S, int pos, int len) 取主串S从pos位置开始的长度为len的字串，取成功返回1，失败返回0；void Destroy(Sstring *S)：撤销串S的所占的空间；void Index(Sstring S,Sstring T,int pos)：查找S从pos位置开始的子串T2.2.2调试过程及实验结果2.3题目：2.3.1算法描述及实验步骤通过追踪两个节点的路径，来找出他们的祖先，还可以通过判断从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点 开始输入要查找的两个不同结点a,b其中一个大于根结点，另一个小于根结点？ 否一个结点a是另一个结点b的后代？a,b其中一个大于s，一个小于s？ 是 否 根结点为a,b的最近共同祖先 是 是b的父亲结点为a，b的最近共同祖先s为a,b的最近共同祖先 输出a,b的最近共同祖先 结束2.3.2调试过程及实验结果2.4题目：二叉树的运算2 任务 ：请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。2.4.1算法描述及实验步骤void insert_data(int x) 创建树;void leaflink(test *root) 叶子节点连接;2.4.2调试过程及实验结果三课程设计分析与总结 课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础通过这次课程设计，对于数据结构有了更深的了解。书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。在这次设计过程中，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。四. 源程序清单停车场：#include stdio.h #include stdlib.h #include string.h #include conio.h#define N 100 /*定义一个全局变量用来存储停车场的最大容量*/ typedef struct time int hour; int min; Time; /*用于计算停车时间以便计算停车费用*/typedef struct node char carnum10; Time reach; Time go; Car; /*车辆信息结点*/ typedef struct NODE Car *stack150; int top; SqStack; /*定义一个栈作为停车站*/typedef struct car Car *data; struct car *next; QNode; /*定义一个车结构*/ typedef struct Node QNode *front; QNode *rear; LinkQueue; /*等待通道*/ void InitStack(SqStack *s) /*初始化栈*/ int i; s-top=0; for(i=0;istacks-top=NULL; int InitQueue(LinkQueue *Q) /*初始化便道*/ Q-front=(QNode *)malloc(sizeof(QNode); if(Q-front!=NULL) Q-front-next=NULL; Q-rear=Q-front; return(1); else return(-1); int arrive(SqStack *In,LinkQueue *W) /*车辆到达*/ Car *p; QNode *t; p=(Car *)malloc(sizeof(Car); flushall(); printf(ntt停车场还有%d个停车位,N-In-top);printf(ntt请输入车牌号码:); gets(p-carnum); if(In-toptop+;printf(ntt停车的位置:%d号停车位。,In-top); printf(ntt请输入车到达的时间(格式“*:*”):); scanf(%d:%d,&(p-reach.hour),&(p-reach.min); In-stackIn-top=p;printf(tt请按任意键返回);getch(); return(1); else /*停车场已满，车进便道*/ printf(ntt停车位已满，该车须在便道等待！); t=(QNode *)malloc(sizeof(QNode); t-data=p; t-next=NULL; W-rear-next=t; W-rear=t; printf(tt请按任意键返回); getch();return(1); void Print(Car *p,int room) /*输出停车站车的信息*/ int A1,A2,B1,B2; printf(ntt请输入车离开的时间(格式“*:*”):); scanf(%d:%d,&(p-go.hour),&(p-go.min); printf(ntt车牌号码:); puts(p-carnum); printf(ntt车到达的时间是: %d:%d,p-reach.hour,p-reach.min); printf(tt车离开的时间是: %d:%d,p-go.hour,p-go.min); A1=p-reach.hour; A2=p-reach.min; B1=p-go.hour; B2=p-go.min; printf(ntt费用为: %d元,(B1-A1)*60+(B2-A2); free(p); void go(SqStack *In,SqStack *Out,LinkQueue *W) /*车辆离开*/ int locate; Car *p,*t; QNode *q; /*判断车场内是否有车*/ if(In-top0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf(ntt请输入车在停车场的位置：,In-top); scanf(%d,&locate); if(locate=1&locatetop) break; while(In-toplocate) /*车辆离开*/ Out-top+; Out-stackOut-top=In-stackIn-top; In-stackIn-top=NULL; In-top-; p=In-stackIn-top; In-stackIn-top=NULL; In-top-; while(Out-top=1) In-top+; In-stackIn-top=Out-stackOut-top; Out-stackOut-top=NULL; Out-top-; Print(p,locate); /*判断通道上是否有车及车站是否已满*/ if(W-front!=W-rear)&In-topfront-next; t=q-data; In-top+; printf(ntt便道的%s号车进入车场第%d号停车位。,t-carnum,In-top); printf(ntt请输入现在的时间(格式“*:*”):); scanf(%d:%d,&(t-reach.hour),&(t-reach.min); W-front-next=q-next;if(q=W-rear) W-rear=W-front; In-stackIn-top=t; free(q); else printf(ntt停车场里没有车n); /*没车*/printf(tt请按任意键返回);getch();void info1(SqStack *S) /*列表输出车场信息*/ int i; if(S-top0) /*判断停车场内是否有车*/ printf(n-查看车场:); printf(n位置 到达时间 车牌号n); for(i=1;itop;i+) printf(%d,i); printf(t%d:%dt,S-stacki-reach.hour,S-stacki-reach.min); puts(S-stacki-carnum); else printf(ntt停车场里没有车); void info2(LinkQueue *W) /*显示便道信息*/ QNode *p; p=W-front-next; if(W-front!=W-rear) /*判断通道上是否有车*/ printf(n便道中车辆的号码为:n); while(p!=NULL) puts(p-data-carnum); p=p-next; else printf(n便道里没有车n);printf(请按任意键返回);getch(); void info(SqStack S,LinkQueue W) info1(&S); /*显示停车场信息*/ info2(&W); /*显示停便道信息*/ void main() SqStack In,Out; LinkQueue Wait; int a; InitStack(&In);InitStack(&Out); InitQueue(&Wait);while(1) printf(n*欢迎使用停车场管理系统*n);printf(ntt该停车场的容量为150:);printf(ntt次停车场的停车费用为1.00元/分钟。n);printf(n 1-车辆停车); printf(n 2-车辆离开); printf(n 3-停车场信息); printf(n4-退出系统n);printf(ntt请选择相应操作);while(1) scanf(%d,&a);switch(a) case 1:arrive(&In,&Wait);break; case 2:go(&In,&Out,&Wait);break; case 3:info(In,Wait);break; case 4:printf(tt谢谢使用！欢迎下次光临！);exit(0); default:printf(ntt按键无效，请重新按键选择！);printf(n*欢迎使用停车场管理系统*n);printf(ntt该停车场的容量为150:);printf(ntt次停车场的停车费用为1.00元/分钟。n);printf(n 1-车辆停车); printf(n 2-车辆离开); printf(n 3-停车场信息); printf(n 4-退出系统n);printf(ntt请选择相应操作); 字符串操作:#include#include#includetypedef struct char *ch;int Maxsize;int length;Sstring;void InitString(Sstring *S,int max,char *string)int i;S-ch = (char *)malloc(max*sizeof(char);S-Maxsize=max;S-length = strlen(string); for(i = 0; i length; i+)S-chi = stringi;int Insert(Sstring *S, int pos, Sstring T) int i;if(pos ch所指数组空间，原数组元素存放在新数组的前面 if(S-length + T.length S-Maxsize) realloc(S-ch, (S-length+T.length)*sizeof(char);S-Maxsize=S-length+T.length; for(i = S-length-1; i = pos; i-) S-chi+T.length = S-chi; /依次后移T.length个位置 for(i = 0; i chpos+i = T.chi; /插入字串 S-length = S-length + T.length; /改变S的数据元素个数 return 1;/取主串S从pos位置开始的长度为len的字串，取成功返回1，失败返回0 int SubString(Sstring *T,Sstring S, int pos, int len) int i;if(pos 0 | len S.length) printf(参数pos和len出错！);return 0;if(lenT-Maxsize)T-ch=(char*)malloc(len*sizeof(char);T-Maxsize=len; for(i = 0; i chi = S.chpos+i; T-length = len; return 1; void Destroy(Sstring *S)free(S-ch);S-Maxsize = 0;S-length = 0; void Index(Sstring S,Sstring T,int pos)int i=pos,j=0,v;int m;while(iS.length&jT.length)if(S.chi=T.chj)i+;j+;else i=i-j+1;j=0;if(j=T.length)v=i-T.length;printf(串String3在String1中的%d位置,v);else printf(串String3在String1中不存在！n);printf(请输入插入位置m:n);scanf(%d,&m);Insert(&S,m,T);for(i=0;iS.length;i+)printf(%c,S.chi);printf(n);void main()Sstring S1,S2,S3,S4;int i;int j;int n;int max1=25,max2=10,max3=20,max4=5;InitString(&S1,max1,structAreBox);InitString(&S2,max2,VertexType);InitString(&S3,max3,Data);InitString(&S4,max4,);printf(* * * * * * * * * * * * * * * * * * * * * * * * *n);printf(*1.输入字符串string1*n);printf(*2.输入字符串string2*n);printf(*3.输入字符串string3*n);printf(*4.串String2的头n个字符添加到String1的尾部，输出结果*n);printf(*5.查找sring3在string1的位置*n);printf(* * * * * * * * * * * * * * * * * * * * * * * * *n);/输入第一个字符串printf(n请输入串S1：);for(i=0;iS1.length;i+)printf(%c,S1.chi);printf(n);/输入第二个字符串printf(n请输入串S2：);for(i=0;iS2.length;i+)printf(%c,S2.chi);printf(n);/输入第三个字符串printf(n请输入串S3：);for(i=0;iS3.length;i+)printf(%c,S3.chi);printf(n);/将字符串2的头n个字符添加到S1尾部if(nS2.length)printf(请输入n的值：n);scanf(%d,&n);SubString(&S4,S2,0,n);Insert( &S1,S1.length,S4);else printf(输入不正确);/查找String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。for(i=0;iS1.length;i+) printf(%c,S1.chi); printf(n); Index(S1,S3,0);printf(n);Destroy(&S4);找祖先： #include #include#include#define max 100typedef struct node int data; /元素数据struct node * lchild; /指向左孩子struct node * rchild; /指向右孩子 BTNode;BTNode *root;int amax,cmax,leaf1,leaf2,len1,len2;void insert_data(int x) /*生成二叉排序树*/ BTNode *p,*q,*s;s=(BTNode*)malloc(sizeof(BTNode);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; p=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x)/printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void itemPath(BTNode * b, int path,int leaf,int* len,int pathlen) /求出根节点到指定结点的路径int i;if(b != NULL) if(b-data = leaf) printf( %d到根节点的路径为: %d ,b-data,b-data);a0 = leaf1;for(i=pathlen-1; i=0; i-) printf(%d ,pathi);apathlen-i = pathi;printf(n);*len = pathlen; else pathpathlen = b-data; /将数据放入路径中pathlen+; /路径增长一itemPath(b-lchild,path,leaf,len,pathlen);itemPath(b-rchild,path,leaf,len,pathlen);pathlen-; /恢复原态void findParent() int parent,flag=0;for(int i=1; i=len1; i+) for(int j=1; j=len2; j+) if(ai = aj) parent = ai;printf( %d是%d和%d的最近祖先！n,parent,leaf1,leaf2);flag = 1;break;if(flag)break;int main()int i,x,l1,l2;printf(=找祖先=n);int path1100,path2100;i=1; root=NULL; /*千万别忘了赋初值给root!*/doprintf(请输入第%d个数:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) /printf(nNow output data value:n); else insert_data(x); /*调用插入数据元素的函数*/ while(x!=-9999); printf(请输入两个要找的节点: );scanf(%d%d,&leaf1,&leaf2);l1 = l