厦门理工数据结构课程方案报告

1、数据结构与算法 课程设计报告<2018 2018学年 第1学期）专业：网络项目班 级：11网络项目姓名学号：1107022144指导教师:林仙丽成 绩：计算机科学与技术系2018 年 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三. 课

2、程设计分析与总结 10四. 源程序清单 111. 停车场管理系统112. 字符串操作193. 找祖先 224. 二叉树运算2 25五. 设计日志 31六. 指导教师评语 32一.课程设计的目的与要求 <含设计指标）1、设计目的<1）培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法 设计问题。<2）培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调 试能力。<3）培养学生初步的软件设计及软件测试的能力。2、设计任务及要求基本要求：学生必须仔细阅读数据结构课程设计指导书，认真主动完成课程设计的要求。有 问题及时主动通过各种方式与教师

3、联系沟通。学生要发挥自主学习的能力，充分利用 时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时 的向教师汇报。课程设计按照教案要求需要一周时间完成，一周中每天<按每周5天）至少要上 3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过 程分析及说明、实验结果情况说明、结论。每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准方案实现与调试2.1题目:某停车场可以停放 n辆汽车，该停车场只有一个大

4、门，每辆汽车离开停车场都要求之前的汽车必须先退出停车场为它让道，而后让道的汽车再次驶入停车场，停车场示意图如 下：汽车曲要求设计停车管理系统，实现车辆的进入、离开并根据停车时间计费。算法描述及实验步骤停车场管理系统车rF.rrt牌号辆-停 -车 车库停车到 达 时 刻车停2停.2车位置j_-2-3 -4停 车 位 置车辆离开停 车 时 刻调试过程及实验结果停车 场信 息退出系统离 开 时 刻* W11P 史 耳OW乎辆停车应 缴 纳 费 用 rF.rrt牌号便 道 信 息停 车 位 置停 车 时 刻等待 中的 车牌 号返 回 主 菜 单请选择相应操作1囂瞬刖：12：00请按任sfci.?1咬任

5、竜摆返回自3 车开信统 停®® 车车停退 一 一 _ _一雜莓黑篱 01 盹元/分钟o算料xx觸xx料xx觸xx料xx觸xx WJLHJ史 弔焊工刘官土里zn3k其料鬓其其涎其涎M其其涎其涎托其托其一 _ _ _ 一-一 一 12 3 4请选择相应操作丄僵年场还滾丄彗个停车位曙焉入车廉号码痕1J丰的位囂沌号停车位。请输入李氧达馬时间龙格式卄：12：03雜麴霹輛“元仆自IIJJ 卉开佶统 停® SS 车案退12 3 4请选择相应操作2韻娜熬5请按任蠶蠶評郴悬12 = 30车牌号码酿请输入车离开的时间（格式'J* "> = 12：30请输入车衽

6、停车场的位置：10715用 为费 量立白3 车开隹统 停系 车WK退请选择相应操作3->>»»>查看车场：位置到达时间车牌号112：302便道里没直车请按任意無返回鼻貝鼻氈貝賈買賈氈耳良/貝賈氈耳良）* KpR 卩"fy 牛土勿系二兀員貝XU JtXWWlt貝鼻 w:车场的餐量为1与肌 车场的荐车费用为麵元”分钟。自LU车开住统u次光临1 Press ani/ kev to continue2.2题目:字符串的操作：任务：字符串采用数组存储，建立两个字符串String1和String2.输出两个字符串。将字符串String2的头n个字符添加到St

7、ring1的尾部，输出结果。查找String3 在串String1 中的位置，若 String3 在String1 中不存在，则插入算法描述及实验步骤void InitString(Sstring *S,int max,char *string>符复制到S中；int Insert(Sstring *S, int pos, Sstring T>int SubString(Sstring *T,Sstring S, int pos, int len>。初始化字符串 S,将string 的字:在主串S的pos位置插入子串 To取主串S从pos位置开始的String3 在String

8、1 中的m位置上。输出结果。void Index(Sstring S,Sstring T,int pos>:查找S从pos位置开始的子串T长度为len的字串，取成功返回1,失败返回0;void Destroy(Sstring *S>:撤销串S的所占的空间;*1幵2町*4stringl* 吕 st r ing2* 串 strinrin输出结果释« « «调试过程及实验结果请输入串SEI： tructApeBox请输入串 E2： UertexT ype 请输入串阳；Box蒂鎰入n的值：2structfireBoxUe串String3在Strinl中的9位置

9、曲 *C:VC123Debue123- exe输出结杲派K- -W W的尾部* w »幵 g”« i wwtrtrtr头5S#s s幵吕呂吕即刖» 幵壬士t“才養认入入st找"*董:structAr&Box；(JertexType:弓彳入串韵：Data jf入n的值：struLctHFeBoxUe$Striny3在航沁吨中不存在I m输入插入位置和：C:VC123Debug123,eef stringl* 咅弱 £tring2* /f qstring3*|*4串ggrdnsrZ曲头口亍字简添in?ljstringl的尾部*输岀结果 -查

10、找srin 33jXxtringl的位置来晴输入串El：st rue t Ai*e Bo x输入串 (JertexType2.3题目算法描述及实验步骤通过追踪两个节点的路径，来找出他们的祖先，还可以通过判断从根结点开始，判断 以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在 它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的 右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树 中，一个出现在右子树中，那当前的结点就是最低的共同父结点开始b的父亲结点为a, b的最近共同祖先1,输出a,b的最近共同祖先,Fs为a

11、,b的最近共同祖先结束调试过程及实验结果2321510 20 2515 10 205 fl223122J8 1-12345&78?个聶点< -11朴貳节m 入入入入入入入入入入入入酣列是 也也亚业也亚也也也赴刘羽至5 0节聊和请请请点"C:VCt ast4Oebugyyy. eze"5 52 203 0 02 3!0 t2 : -9 UMVUMV3J-999点0! 950 0 0275 52 一 + 卩各各 |!1页 且223122381 : 找数数数数数数数数数唆缚幕讨< T*个*个个个个时"僅龍33 =123456789 丄丄丿-4-1-兩

12、 -JSSJ1JSM®28 -_一IAIA1AIAIAIAIAIA1AIAIAIA®_ 一一 S0302S2.4题目二叉树的运算2任务：请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个 单链表。二叉树用二叉链存储，链接时用叶子结点的rchild域存放指针。算法描述及实验步骤void in sert_data(i nt x>仓 U建树。void leafli nk(test *root>叶子节点连接。调试过程及实验结果gplease Input the data end by 9999 ：2025302126鼬212636Press any ker to

13、 c三.课程设计分析与总结课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前 一个必不少的过程.”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名 言的真正含义.我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳 健地在社会大潮中奔跑打下坚实的基础.通过这次课程设计，对于数据结构有了更深的了解。书本上的知识与老师的讲解都比较容 易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适 合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序 中再加以必要的连接以完成程序的编写。针对这一情况，我会严

14、格要求自己，熟练掌握算 法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问 题的能力。在这次设计过程中，体会了学以致用、突出自己劳动成果的喜悦心情，从中发 现自己平时学习的不足和薄弱环节，从而加以弥补。四 . 源程序清单停车场：#include "stdio.h"#include "stdlib.h"#include "string.h"#include "conio.h"#define N 100 /* 定义一个全局变量用来存储停车场的最大容量 */typedef struct tim

15、eint hour 。int min 。Time 。 /* 用于计算停车时间以便计算停车费用 */typedef struct nodechar carnum10 。Time reach 。Time go 。Car 。 /* 车辆信息结点 */typedef struct NODECar *stack150 。int top 。SqStack 。 /* 定义一个栈作为停车站 */ typedef struct carCar *data 。struct car *next 。QNode。 /* 定义一个车结构 */typedef struct NodeQNode *front 。QNode *r

16、ear 。LinkQueue 。 /* 等待通道 */void InitStack(SqStack *s> /* 初始化栈 */int i 。s->top=0 。for(i=0 。i<=N。i+>s->stacks->top=NULL 。int InitQueue(LinkQueue *Q> /* 初始化便道 */Q->front=(QNode *>malloc(sizeof(QNode>> 。if(Q->front!=NULL>Q->front->next=NULL 。Q->rear=Q->

17、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-ln->top>。printf("ntt 请输入车牌号码 :"> 。 gets(p->carnum> 。if(ln->top<N> /* 停车场未满

18、，车进车场 */ln->top+ 。printf("ntt停车的位置 :%d 号停车位。 ",ln->top>printf("ntt请输入车到达的时间 (格式“ *:* ”scanf("%d:%d",&(p->reach.hour>,&(p->reach.min>> ln->stackln->top=p 。printf("tt 请按任意键返回 "> 。getch(> 。return(1> 。else /* 停车场已满，车进便道 */

19、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> 。int A1,A2,B1,B2 。printf("ntt 请输入车离开的时间 ( 格式“ *:* ”>:"> 。scanf(&qu

20、ot;%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->rea

21、ch.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->top>0> /*有车 */while(1> /* 输入离开车辆的信息 */printf(

22、"ntt 请输入车在停车场的位置： ",In->top> scanf("%d",&locate> 。if(locate>=1&&locate<=In->top>breakwhile(In->top>locate> /* 车辆离开 */Out->top+ 。Out->stackOut->top=In->stackIn->top 。 In->stackIn->top=NULL 。In->top- 。p=In->stackI

23、n->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->top<N> /* 便道的车辆进

24、入停车场 */ q=W->front->next 。 t=q->data 。In->top+ 。printf("ntt便道的$号车进入车场第d号停车位。”,t->carnum,In->top> 。printf("ntt 请输入现在的时间 (格式“ *:* ”>:"> 。 scanf("%d:%d",&(t->reach.hour>,&(t->reach.min>>。W->front->next=q->next if(q=W-&g

25、t;rear> W->rear=W->frontIn->stackIn->top=t 。free(q> 。else printf("ntt 停车场里没有车 n"> 。 /* 没车 */printf("tt 请按任意键返回 "> 。getch(> 。void info1(SqStack *S> /*列表输出车场信息 */int i 。if(S->top>0> /* 判断停车场内是否有车 */ printf("n->>>>>>>

26、查看车场 :"> 。printf("n 位置 到达时间 车牌号 n"> 。for(i=1 。 i<=S->top 。 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(Link

27、Queue *W> /*显示便道信息 */QNode *p 。p=W->front->next 。if(W->front!=W->rear> /*判断通道上是否有车 */printf("n 便道中车辆的号码为 while(p!=NULL>puts(p->data->carnum>p=p->next 。else printf("n 便道里没有车 n"> 。printf(" 请按任意键返回 "> 。getch(> 。void info(SqStack S,LinkQ

28、ueue W>info1(&S> 。 /* 显示停车场信息 */info2(&W> 。 /* 显示停便道信息 */void main(>SqStack In,Out 。LinkQueue Wait 。int a 。:n"> 。InitStack(&In> 。InitStack(&Out> 。InitQueue(&Wait> 。 while(1>printf("n*欢迎使用停车场管理系统*printf("ntt 该停车场的容量为 150:"> 。printf

29、("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,&Wa

30、it>。 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

31、 次停车场的停车费用为 1.00 元 / 分钟。 n"> 。 printf("n 1 车辆停车 "> 。printf("n 2 车辆离开 "> 。printf("n 3 停车场信息 "> 。printf("n 4 退出系统 n"> 。printf("ntt请选择相应操作 "> 。字符串操作 :#include<stdio.h>#include<malloc.h>#include<string.h>typedef s

32、truct 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 < S->length 。 i+>S->chi = stringi。int Insert(Sstring *S, int

33、 pos, Sstring T> int i 。if(pos < 0> printf(" 参数 pos 出错！ "> 。 return 0 。 else/ 重新申请 S->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->

34、length-1。 i >= posi->。 / 依次后移 T.length 个位置。 i+>。 / 插入字串。 / 改变 S 的数据元素个数S->chi+T.length = S->chi for(i = 0 。 i < T.lengthS->chpos+i = T.chiS->length = S->length + T.length return 1 。/ 取主串 S 从 pos 位置开始的长度为 len 的字串，取成功返回 1，失败返回 0 int SubString(Sstring *T,Sstring S, int pos, i

35、nt len> int i 。if(pos < 0 | len < 0 | pos+len > S.length> printf(" 参数 pos 和 len 出错！ "> 。 return 0 。if(len>T->Maxsize>T->ch=(char*>malloc(len*sizeof(char>>T->Maxsize=len 。for(i = 0 。 i < len 。 i+>T->chi = S.chpos+i 。T->length = len 。retu

36、rn 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(i<S.length&&j<T.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 在 S

37、tring1 中的 c位置 ”,v>。else printf(" 串 String3 在 String1 中不存在！ n"> 。printf(" 请输入插入位置 m:n"> 。scanf("%d",&m> 。Insert(&S,m,T> 。for(i=0 。 i<S.length 。 i+>printf("%c",S.chi> 。printf("n"> 。void main(>Sstring S1,S2,S3,S4 。

38、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("* * * * * * * * * * * * * * * * * * * *

39、* * * *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">o/ 输入第一个字符

40、串 printf("n 请输入串 S1： ">。for(i=0 。i<S1.length。i+>printf("%c",S1.chi> 。 printf("n"> 。/ 输入第二个字符串 printf("n 请输入串 S2：">。for(i=0 。 i<S2.length 。 i+> printf("%c",S2.chi> 。 printf("n"> 。/ 输入第三个字符串 printf("n 请输入串 S

41、3：">。for(i=0 。 i<S3.length 。 i+> printf("%c",S3.chi> printf("n"> 。/将字符串2的头n个字符添加到 S1尾部if(n<S2.length>printf(" 请输入 n 的值： n"> 。 scanf("%d",&n> 。SubString(&S4,S2,0,n> 。Insert( &S1,S1.length,S4> 。 else printf("

42、; 输入不正确 "> 。/ 查找 String3 在串 String1 中的位置，若 String3 在 String1 中不存在，则插入String3 在String1 中的m位置上。for(i=0 。 i<S1.length 。 i+>printf("%c",S1.chi>。printf("n"> 。Index(S1,S3,0> 。printf("n"> 。Destroy(&S4> 。找祖先：#include <malloc.h>#include<

43、stdio.h>#include<stdlib.h>#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>>

44、; 。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(x<p->data> p=p->lchild 。else p=p->rchild 。 if(x<q->data> q->lchild=s

45、 。elseq->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>

46、; 。 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<=

47、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(”请输入第c个数:",i> 。i+ 。scanf("%d",&x> 。/* 从键盘采集数据，以 -9999 表示输入结束 */if(x=-9999>/printf(