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

《数据结构与算法》课程设计报告（2012—2013学年第1学期）专业：网络工程班级：11网络工程姓名学号：1107022144指导教师：林仙丽成绩：计算机科学与技术系2013年01月11日目录一．课程设计目的与要求………………………………………11．设计目的…………………………………………………………12．设计任务及要求…………………………………………………1二.方案实现与调试…………………………………………11．停车场管理系统…………………………………………………11.1算法描述及实验步骤……………………………………………21.2调试过程及实验结果……………………………………………32．字符串操作……………………………………………………42.1算法描述及实验步骤……………………………………………52.2调试过程及实验结果……………………………………………63．找祖先…………………………………………………………83.1算法描述及实验步骤……………………………………………93.2调试过程及实验结果……………………………………………104．二叉树运算2……………………………………………………84.1算法描述及实验步骤……………………………………………94.2调试过程及实验结果……………………………………………1三．课程设计分析与总结………………………………………10四．源程序清单…………………………………………………111.停车场管理系统……………………………………………………112．字符串操作………………………………………………………193.找祖先……………………………………………………………224.二叉树运算2……………………………………………………25五．设计日志………………………………………………………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算法描述及实验步骤voidInitString(Sstring*S,intmax,char*string);初始化字符串S，将string的字符复制到S中；intInsert(Sstring*S,intpos,SstringT)：在主串S的pos位置插入子串T;intSubString(Sstring*T,SstringS,intpos,intlen)取主串S从pos位置开始的长度为len的字串，取成功返回1，失败返回0；voidDestroy(Sstring*S)：撤销串S的所占的空间；voidIndex(SstringS,SstringT,intpos)：查找S从pos位置开始的子串T2.2.2调试过程及实验结果2.3题目：2.3.1算法描述及实验步骤通过追踪两个节点的路径，来找出他们的祖先，还可以通过判断从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点否是否是是2.3.2调试过程及实验结果输入要查找的两个不同结点a,b其中一个大于s，一个小于s？s为a,b的最近共同祖先一个结点a是另一个结点b的后代？b的父亲结点为a，b的最近共同祖先输出a,b的最近共同祖先结束a,b其中一个大于根结点，另一个小于根结点？根结点为a,b的最近共同祖先开始2.4题目：二叉树的运算2任务：请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild域存放指针。2.4.1算法描述及实验步骤voidinsert_data(intx)创建树;voidleaflink(test*root)叶子节点连接;2.4.2调试过程及实验结果三．课程设计分析与总结课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础．通过这次课程设计，对于数据结构有了更深的了解。书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。在这次设计过程中，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。四.源程序清单停车场：#includestdio.h#includestdlib.h#includestring.h#includeconio.h#defineN100/*定义一个全局变量用来存储停车场的最大容量*/typedefstructtime{inthour;intmin;}Time;/*用于计算停车时间以便计算停车费用*/typedefstructnode{charcarnum[10];Timereach;Timego;}Car;/*车辆信息结点*/typedefstructNODE{Car*stack[150];inttop;}SqStack;/*定义一个栈作为停车站*/typedefstructcar{Car*data;structcar*next;}QNode;/*定义一个车结构*/typedefstructNode{QNode*front;QNode*rear;}LinkQueue;/*等待通道*/voidInitStack(SqStack*s)/*初始化栈*/{inti;s-top=0;for(i=0;i=N;i++)s-stack[s-top]=NULL;}intInitQueue(LinkQueue*Q)/*初始化便道*/{Q-front=(QNode*)malloc(sizeof(QNode));if(Q-front!=NULL){Q-front-next=NULL;Q-rear=Q-front;return(1);}elsereturn(-1);}intarrive(SqStack*In,LinkQueue*W)/*车辆到达*/{Car*p;QNode*t;p=(Car*)malloc(sizeof(Car));flushall();printf(\n\t\t停车场还有%d个停车位,N-In-top);printf(\n\t\t请输入车牌号码:);gets(p-carnum);if(In-topN)/*停车场未满，车进车场*/{In-top++;printf(\n\t\t停车的位置:%d号停车位。,In-top);printf(\n\t\t请输入车到达的时间(格式“**:**”):);scanf(%d:%d,&(p-reach.hour),&(p-reach.min));In-stack[In-top]=p;printf(\t\t请按任意键返回);getch();return(1);}else/*停车场已满，车进便道*/{printf(\n\t\t停车位已满，该车须在便道等待！);t=(QNode*)malloc(sizeof(QNode));t-data=p;t-next=NULL;W-rear-next=t;W-rear=t;printf(\t\t请按任意键返回);getch();return(1);}}voidPrint(Car*p,introom)/*输出停车站车的信息*/{intA1,A2,B1,B2;printf(\n\t\t请输入车离开的时间(格式“**:**”):);scanf(%d:%d,&(p-go.hour),&(p-go.min));printf(\n\t\t车牌号码:);puts(p-carnum);printf(\n\t\t车到达的时间是:%d:%d,p-reach.hour,p-reach.min);printf(\t\t车离开的时间是:%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(\n\t\t费用为:%d元,(((B1-A1)*60+(B2-A2))));free(p);}voidgo(SqStack*In,SqStack*Out,LinkQueue*W)/*车辆离开*/{intlocate;Car*p,*t;QNode*q;/*判断车场内是否有车*/if(In-top0)/*有车*/{while(1)/*输入离开车辆的信息*/{printf(\n\t\t请输入车在停车场的位置：,In-top);scanf(%d,&locate);if(locate=1&&locate=In-top)break;}while(In-toplocate)/*车辆离开*/{Out-top++;Out-stack[Out-top]=In-stack[In-top];In-stack[In-top]=NULL;In-top--;}p=In-stack[In-top];In-stack[In-top]=NULL;In-top--;while(Out-top=1){In-top++;In-stack[In-top]=Out-stack[Out-top];Out-stack[Out-top]=NULL;Out-top--;}Print(p,