数据结构课程结构设计 29页

'数据结构课程结构设计一.课程设计的目的与要求（含设计指标）1、设计目的（1）培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。（2）培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。（3）培养学生初步的软件设计及软件测试的能力。2、设计任务及要求基本要求：学生必须仔细阅读《数据结构》课程设计指导书，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准；二.方案实现与调试2.1题目：某停车场可以停放n辆汽车，该停车场只有一个大门，每辆汽车离开停车场都要求之前的汽车必须先退出停车场为它让道，而后让道的汽车再次驶入停车场，停车场示意图如下：要求设计停车管理系统，实现车辆的进入、离开并根据停车时间计费。2.1.1算法描述及实验步骤29 停车场管理系统停车场信息退出系统车辆停车车辆离开车库停车便道停车便道信息停车场信息返回主菜单停车位置应缴纳费用停车时刻离开时刻停车位置到达时刻车牌号等待中的车牌号停车时刻停车位置车牌号2.1.2调试过程及实验结果29 29 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的所占的空间；29 voidIndex(SstringS,SstringT,intpos)：查找S从pos位置开始的子串T2.2.2调试过程及实验结果29 2.3题目：2.3.1算法描述及实验步骤通过追踪两个节点的路径，来找出他们的祖先，还可以通过判断从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点29 开始输入要查找的两个不同结点a,b其中一个大于根结点，另一个小于根结点？否一个结点a是另一个结点b的后代？a,b其中一个大于s，一个小于s？是否根结点为a,b的最近共同祖先是是b的父亲结点为a，b的最近共同祖先s为a,b的最近共同祖先输出a,b的最近共同祖先结束2.3.2调试过程及实验结果29 2.4题目：二叉树的运算2任务：请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild域存放指针。2.4.1算法描述及实验步骤voidinsert_data(intx)创建树;voidleaflink(test*root)叶子节点连接;2.4.2调试过程及实验结果29 三．课程设计分析与总结课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础．通过这次课程设计，对于数据结构有了更深的了解。书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。在这次设计过程中，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。四.源程序清单停车场：#include"stdio.h"#include"stdlib.h"#include"string.h"#include"conio.h"#defineN100/*定义一个全局变量用来存储停车场的最大容量*/typedefstructtime{29 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;/*等待通道*/29 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("ntt停车场还有%d个停车位",N-In->top);printf("ntt请输入车牌号码:");gets(p->carnum);29 if(In->toptop++;printf("ntt停车的位置:%d号停车位。",In->top);printf("ntt请输入车到达的时间(格式“**:**”):");scanf("%d:%d",&(p->reach.hour),&(p->reach.min));In->stack[In->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);}}voidPrint(Car*p,introom)/*输出停车站车的信息*/{intA1,A2,B1,B2;printf("ntt请输入车离开的时间(格式“**:**”):");scanf("%d:%d",&(p->go.hour),&(p->go.min));29 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);}voidgo(SqStack*In,SqStack*Out,LinkQueue*W)/*车辆离开*/{intlocate;Car*p,*t;QNode*q;/*判断车场内是否有车*/if(In->top>0)/*有车*/{while(1)/*输入离开车辆的信息*/{printf("ntt请输入车在停车场的位置：",In->top);scanf("%d",&locate);if(locate>=1&&locate<=In->top)break;}while(In->top>locate)/*车辆离开*/{29 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,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->stack[In->top]=t;free(q);29 }}elseprintf("ntt停车场里没有车n");/*没车*/printf("tt请按任意键返回");getch();}voidinfo1(SqStack*S)/*列表输出车场信息*/{inti;if(S->top>0)/*判断停车场内是否有车*/{printf("n->>>>>>>查看车场:");printf("n位置到达时间车牌号n");for(i=1;i<=S->top;i++){printf("%d",i);printf("t%d:%dt",S->stack[i]->reach.hour,S->stack[i]->reach.min);puts(S->stack[i]->carnum);}}elseprintf("ntt停车场里没有车");}voidinfo2(LinkQueue*W)/*显示便道信息*/{QNode*p;p=W->front->next;if(W->front!=W->rear)/*判断通道上是否有车*/{29 printf("n便道中车辆的号码为:n");while(p!=NULL){puts(p->data->carnum);p=p->next;}}elseprintf("n便道里没有车n");printf("请按任意键返回");getch();}voidinfo(SqStackS,LinkQueueW){info1(&S);/*显示停车场信息*/info2(&W);/*显示停便道信息*/}voidmain(){SqStackIn,Out;LinkQueueWait;inta;InitStack(&In);InitStack(&Out);InitQueue(&Wait);while(1){29 printf("n********************欢迎使用停车场管理系统******************n");printf("ntt该停车场的容量为150:");printf("ntt次停车场的停车费用为1.00元/分钟。n");printf("n1--------车辆停车");printf("n2--------车辆离开");printf("n3--------停车场信息");printf(n4--------退出系统n");printf("ntt请选择相应操作");while(1){scanf("%d",&a);switch(a){case1:arrive(&In,&Wait);break;case2:go(&In,&Out,&Wait);break;case3:info(In,Wait);break;case4:{printf("tt谢谢使用！欢迎下次光临！");exit(0);}default:printf("ntt按键无效，请重新按键选择！");}printf("n********************欢迎使用停车场管理系统******************n");printf("ntt该停车场的容量为150:");printf("ntt次停车场的停车费用为1.00元/分钟。n");printf("n1--------车辆停车");printf("n2--------车辆离开");printf("n3--------停车场信息");printf("n4--------退出系统n");printf("ntt请选择相应操作");}}29 }字符串操作:#include#include#includetypedefstruct{char*ch;intMaxsize;intlength;}Sstring;voidInitString(Sstring*S,intmax,char*string){inti;S->ch=(char*)malloc(max*sizeof(char));S->Maxsize=max;S->length=strlen(string);for(i=0;ilength;i++)S->ch[i]=string[i];}intInsert(Sstring*S,intpos,SstringT){inti;if(pos<0){printf("参数pos出错！");return0;}else{//重新申请S->ch所指数组空间，原数组元素存放在新数组的前面if(S->length+T.length>S->Maxsize)realloc(S->ch,(S->length+T.length)*sizeof(char));29 S->Maxsize=S->length+T.length;for(i=S->length-1;i>=pos;i--)S->ch[i+T.length]=S->ch[i];//依次后移T.length个位置for(i=0;ich[pos+i]=T.ch[i];//插入字串S->length=S->length+T.length;//改变S的数据元素个数return1;}}//取主串S从pos位置开始的长度为len的字串，取成功返回1，失败返回0intSubString(Sstring*T,SstringS,intpos,intlen){inti;if(pos<0||len<0||pos+len>S.length){printf("参数pos和len出错！");return0;}if(len>T->Maxsize){T->ch=(char*)malloc(len*sizeof(char));T->Maxsize=len;}for(i=0;ich[i]=S.ch[pos+i];T->length=len;return1;}voidDestroy(Sstring*S)29 {free(S->ch);S->Maxsize=0;S->length=0;}voidIndex(SstringS,SstringT,intpos){inti=pos,j=0,v;intm;while(i#include#include#definemax10029 typedefstructnode{intdata;//元素数据structnode*lchild;//指向左孩子structnode*rchild;//指向右孩子}BTNode;BTNode*root;inta[max],c[max],leaf1,leaf2,len1,len2;voidinsert_data(intx)/*生成二叉排序树*/{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("dataalreadyexist!n");return;}elseif(xdata)p=p->lchild;elsep=p->rchild;}if(xdata)q->lchild=s;elseq->rchild=s;}voiditemPath(BTNode*b,intpath[],intleaf,int*len,intpathlen){//求出根节点到指定结点的路径inti;29 if(b!=NULL){if(b->data==leaf){printf("%d到根节点的路径为:%d",b->data,b->data);a[0]=leaf1;for(i=pathlen-1;i>=0;i--){printf("%d",path[i]);a[pathlen-i]=path[i];}printf("n");*len=pathlen;}else{path[pathlen]=b->data;//将数据放入路径中pathlen++;//路径增长一itemPath(b->lchild,path,leaf,len,pathlen);itemPath(b->rchild,path,leaf,len,pathlen);pathlen--;//恢复原态}}}voidfindParent(){intparent,flag=0;for(inti=1;i<=len1;i++){for(intj=1;j<=len2;j++){if(a[i]==a[j]){parent=a[i];printf("%d是%d和%d的最近祖先！n",parent,leaf1,leaf2);flag=1;break;}}if(flag)break;}}intmain(){inti,x,l1,l2;printf("===========找祖先===========n");intpath1[100],path2[100];i=1;root=NULL;/*千万别忘了赋初值给root!*/do{29 printf("请输入第%d个数:",i);i++;scanf("%d",&x);/*从键盘采集数据，以-9999表示输入结束*/if(x==-9999){//printf("nNowoutputdatavalue:n");}elseinsert_data(x);/*调用插入数据元素的函数*/}while(x!=-9999);printf("请输入两个要找的节点:");scanf("%d%d",&leaf1,&leaf2);l1=leaf1;l2=leaf2;itemPath(root,path1,l1,&len1,0);itemPath(root,path2,l2,&len2,0);findParent();return0;}二叉树运算二:#include#includetypedefstructlnode{intdata;structlnode*lchild,*rchild;}test;test*root,*k,*n;voidinsert_data(intx){test*p,*q,*s;s=(test*)malloc(sizeof(test));s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)29 {root=s;return;}p=root;while(p){q=p;if(p->data==x){printf("dataalreadyexist!n");return;}elseif(xdata)p=p->lchild;elsep=p->rchild;}if(xdata)q->lchild=s;elseq->rchild=s;}voidleaflink(test*root){if(!root)return;if(root->lchild==NULL&&root->rchild==NULL){if(k==NULL)k=n=root;else{n->rchild=root;n=n->rchild;}}if(root->lchild)leaflink(root->lchild);29 if(root->rchild)leaflink(root->rchild);return;}voidmain(){intx;root=NULL;printf("pleaseinputthedataendby-9999:n");scanf("%d",&x);while(x!=-9999){insert_data(x);scanf("%d",&x);}leaflink(root);while(k){printf("%d",k->data);k=k->rchild;}}29 设计日志2013.1.7熟悉了解题目要求，上网查阅资料关于一些函数的用法。2013.1.8字符串操作开始编写代码，先开始对界面进行设计，然后针对要实现的功能进行编写，主要对于字符串操作函数不了解，遇到了点问题；最后还是没解决。。。。2013．1.9开始写二叉树运算2；2013.1.10答辩，整理文档，上交报告。29 （注：指导教师评语和成绩所在表格另起一页）指导教师评语课程设计成绩指导教师签字年月日29'