数据结构课程设计-停车场管理

第一篇：数据结构课程设计-停车场管理

课 程 设 计 报 告

课程名称

数据 结构

题

目

停车场管理

学生姓名 班级/学号 191103

一、需求分析

设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供

汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端），若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

【测试数据】

设n=2，输入数据为：（’A’,1,5），（’A’,2,10），（’D’,1,15），（’A’,3,20），（’A’,4,25），（’A’,5,30），（’D’,2,35），（’D’,4,40），（’E’,0,0）。其中：’A’表示到达；’D’表示离去；’E’表示输入结束。概要设计

以栈模拟停车场，以队列模拟车场外的便道。栈以顺序结构实现。队列以链表结构实现。每一组输入数据包括：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。

输出信息：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。

二、详细设计

三、程序设计

1.数据结构设计 /*栈，模拟停车场*/ typedef struct Car1 {

//车

int number;//汽车车号

int ar_time;//汽车到达时间 }CarNode;

typedef struct {

//停车场

CarNode *base;//停车场的堆栈底

CarNode *top;//停车场的堆栈顶

int stacksize;}Park;

/*队列，模拟便道*/ typedef struct Car2 {

//车

int number;//汽车车号

int ar_time;//汽车到达时间

struct Car2 *next;}*CarPtr;

typedef struct {

//便道

CarPtr front;//便道的队列的对头

CarPtr rear;//便道的队列的队尾

int length;}Shortcut;2.程序设计

主函数中包括3个子函数，A(arrive)，D（depart），E（end）

（1）输入车辆数据：A为到达，D为离去，E为结束程序。

（2）接着输入车辆的牌照信息

（3）若为到达的车辆，输入进场信息，若为离去的车辆，输入离场信息。（4）若车辆到达，可得到车辆的停放位置信息，若车辆离去，可得到车辆的停放时间（在便道上的停放时间除外），以及应该交纳的费用。

（5）本程序不断循环要求输入车辆信息，直到输入的车辆数据为E时，程序结束。

四、调试分析

a、一开始在调试程序时遇到了内存错误，经过DEBUG，找到了引起内存错误的原因：即在建立队头指针与队尾指针时没有对指针进行初始化(没有为指针动态分配空间)。问题得到解决。

b、本程序中：车辆到达,离去时的时间复杂度均为：O(n)。本程序空间复杂度为：O(n)

五、使用说明和测试结果

1.使用说明：用户按照屏幕所显示的提示来选择需要进行操作

2、测试结果：

测试结果满足题目要求，程序无错误。

六、心得体会

通过此实验，加深了我对数据结构这门课的理解，真正运用了知识。将理论与现实完美的联系在了一起。增强了动手能力，对今后的工作学习都有很大的帮助。单调的看书本没有太大的作用，只有去编程才能理解究竟学习的作用。同时，编程过程中遇到过各种各样的问题，与同学讨论，与老师交流。锻炼了我的协做能力与克服困难的能力。编程也极大的提高了我的学习积极性。

七、附录

#include #include #include #define SIZE 2//停车场位置数,共5个车位 typedef int Status;

/*栈，模拟停车场*/ typedef struct Car1 {

//车

int number;//汽车车号

int ar_time;//汽车到达时间 }CarNode;

typedef struct {

//停车场

CarNode *base;//停车场的堆栈底

CarNode *top;//停车场的堆栈顶

int stacksize;

}Park;

/*队列，模拟便道*/ typedef struct Car2 {

//车

int number;//汽车车号

int ar_time;//汽车到达时间

struct Car2 *next;}*CarPtr;

typedef struct {

//便道

CarPtr front;//便道的队列的对头

CarPtr rear;//便道的队列的队尾

int length;}Shortcut;/*初始化停车场*/ Status InitStack(Park &P){

P.base=(CarNode*)malloc(SIZE*sizeof(Car1));

if(!P.base)exit(-2);

P.top=P.base;

P.stacksize=0;

return 1;}

Status Push(Park &P,CarNode e){//车进入停车场

*P.top++=e;

++P.stacksize;

return 1;}

Status Pop(Park &P,CarNode &e){//车离开停车场

if(P.top==P.base)

printf(“停车场为空”);

else

{

e=*--P.top;

--P.stacksize;

}

return 1;} /*初始化便道*/ Status InitQueue(Shortcut &S){

S.front=S.rear=(CarPtr)malloc(sizeof(Car2));

if(!S.front||!S.rear)exit(-2);

S.front->next=NULL;

S.length=0;

return 1;}

Status EnQueue(Shortcut &S,int number,int ar_time){//车进入便道

CarPtr p;

p=(CarPtr)malloc(sizeof(Car2));

if(!p)exit(-2);

p->number=number;

p->ar_time=ar_time;

p->next=NULL;

S.rear->next=p;

S.rear=p;

++S.length;

return 1;}

Status DeQueue(Shortcut &S,CarPtr &w){//车离开便道

if(S.length == 0)

printf(“通道为空”);

else

{

w = S.front->next;

S.front->next=S.front->next->next;

--S.length;

}

return 1;}

Status Arrival(Park &P,Shortcut &S){//对进站车辆的处理

int number,ar_time;

printf(“请输入车牌号:”);

scanf(“%d”,&number);

printf(“进场的时刻:”);

scanf(“%d”,&ar_time);

if(P.stacksize

{

CarNode c;

c.number=number;

c.ar_time=ar_time;

Push(P,c);

printf(“请将车停在第%d号车道。n”,P.stacksize);

}

else

{

EnQueue(S,number,ar_time);

printf(“停车场已满，请暂时停在便道的第%d个位置。n”,S.length);

}

return 1;}

Status Leave(Park &P,Park &P1,Shortcut &S){//对离站车辆的处理

int number,le_time,flag=1,money,ar_time;

printf(“请输入车牌号:”);

scanf(“%d”,&number);

printf(“出场的时刻:”);

scanf(“%d”,&le_time);

CarNode e,m;

CarPtr w;

while(P.stacksize)

{

Pop(P,e);

if(e.number==number)

{

flag=0;

money=(le_time-e.ar_time)*2;

ar_time=e.ar_time;

break;

}

Push(P1,e);

}

while(P1.stacksize)

{

Pop(P1,e);

Push(P,e);

}

// 车从停车场中出

if(flag == 0)

{

if(S.length!=0)

{

DeQueue(S,w);

m.ar_time=le_time;

m.number=w->number;

Push(P,m);

free(w);

printf(“车牌号为%d的车已由便道进入停车场n”,m.number);

}

printf(“停车费为%d, 占用车位数为%dn”,money,P.stacksize);

}

else

{

printf(“停车场不存在牌号为%d的车n”, number);

}

return 1;} /*主函数*/ int main(){

int m=1;

char flag;//选项

Park P,Q;

Shortcut S;InitStack(P);InitStack(Q);InitQueue(S);

while(m)

{

printf(“n

停车场管理程序

n”);

printf(“A 汽车进车场

D 汽车出车场

E 退出程序n”);

printf(“请选择(A,D,E): ”);

scanf(“%c”,&flag);

switch(flag)

{

case 'A':

case 'a':

Arrival(P,S);break;//车进入停车场

case 'D':

case 'd':

Leave(P,Q,S);break;//车离开停车场

case 'E':

case 'e':

m=0;

break;

default:

printf(“Input error!n”);

break;

}

while(flag!= 'n')

scanf(“%c”,&flag);

} }

第二篇：数据结构课程设计报告_15_停车场管理

停车场管理系统

——数据结构课程设计程序设计书

小组成员：

彭路

20131344031 崔琦

20131344028 徐佳

20131344027 范福龙 20121344024 班级 ： 13软件工程1班 时间：2014.12.22

目录

一、程序设计目标

二、问题描述

三、需求分析

四、概要设计

五、详细设计

六、源程序清单

七、软件说明书

八、测试报告

九、课程设计总结

一、程序设计目标

本管理程序由c/c++语言完成，实现了对停车场收费问题的处理。本程序保证了程序的健壮性和操作性，在阅读过使用说明书之后可以轻松使用。本管理系统假设车辆在停车场时一直有人在驾驶，或者说停车场的每块停车位均可智能移动。并假设车辆进出场耗时不计，且时间均为整数类型。最后自动或者人工完成收费。

二、问题描述

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

三、需求分析

根据问题描述，可把本停车场抽象成一个栈存储类型s1，需要输入最大停车容量n。每当输入’A’时即为有车辆申请进入停车场操作，此时需要判断停车场是否有空位，如果有空位，那么这辆车可以进入停车场，即为执行一次压栈操作（push），并记录进入停车场的时间t1，并输出位置p1；如果停车场没有空位，那么这辆车在门外便道等候，并输出位置p2。根据问题描述，可以把此门外便道抽象成一个队列存储类型q，而每有一辆车进入门外便道，即相当于进行一次插入队列操作（push）。每当输入’D’时即为有车辆申请离开停车场操作，此时需要判断该车辆在停车场的位置。如果该车位于停车场最外侧即相当于栈顶，那么该车可以直接批准离开并根据输入的离开时间t2计算出停车时间t2-t1，根据该车本次停车时间完成收费后即可成功驶出停车场，即相当于成功弹出栈顶元素（pop）；如果该车没有位于停车场最外侧，事实上，这也是大多数的情况，那么需要将该车外侧的车依次（即为挡路的车）移动进一个临时停车场，根据问题描述，可以将该临时停车场抽象成另一个栈存储类型s2，那么此次移动操作相当于将栈中某元素以上的元素依次压入另一个栈（push）。当申请离开的车驶出停车场后，在临时停车场的车辆依次进入停车场，此操作相当于将栈s2内元素依次弹出栈（pop）并压入栈s1（push）。此时判断门外便道上有无等待进入停车场的车辆，如果有的话，门外便道上第一辆车可以进入停车场，并记录进入时间t1，此次操作相当于取出队列q的队首元素并将其压入栈s1中。而输入’E’时，即退出系统。至此，所有分析结束。

四、概要设计

根据需求分析，解决此问题需要构建一个Cars类型的结构体，构建一个CarNode类型的节点结构体以构建SQueue类型的队列结构体，并需要构建一个SQstack类型的栈结构体。接下来，分别定义队列和栈的各项基本操作函数。最后，完成菜单函数以实现各项操作。

五、详细设计

本程序定义了三个头文件，manager_cars.h、manager_stack.h、manager_queue.h。分别实现了Cars类型的结构体、SQueue类型的队列结构体、SQstack类型的栈结构体以及队列的相关操作函数和栈的相关操作函数。具体如下：

1、manager_cars.h

sq->lastCar=car;sq->firstCar->nextCar=NULL;sq->length=0;} //进入队列操作

void enterSQueue(SQueue *sq,int num,int t){ CarNode *car=(CarNode *)malloc(sizeof(CarNode));car->headCar.condition='D';car->headCar.number=num;car->headCar.time=t;car->headCar.position=2;

car->nextCar=NULL;sq->lastCar->nextCar=car;sq->lastCar=car;sq->length++;} //出队列操作

void exceedSQueue(SQueue *sq){ if(sq->firstCar==sq->lastCar)

return;CarNode *car=(CarNode *)malloc(sizeof(CarNode));car=sq->firstCar->nextCar;sq->firstCar->nextCar=car->nextCar;sq->length--;if(sq->lastCar==car)

sq->lastCar=sq->firstCar;free(car);

}

//检测队列存在

int SQueueEmpty(SQueue sq){ if(sq.firstCar==sq.lastCar)

return 1;else

return 0;} //获取队首元素

void getSQueue(SQueue sq,Cars *e){ if(sq.firstCar==sq.lastCar)

return;*e=sq.firstCar->nextCar->headCar;S.base;}

extern int GetTop(SQstack S,Cars *e)//若栈不为空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR { if(S.top == S.base)return 0;

*e = *(S.top-1);

return 1;

}

extern int Push(SQstack*S,Cars e)//插入元素e为新的栈顶元素

{ if(S->top

cout<<“请正确输入Y或N:”<

scanf(“%c”,&flag);

getchar();} while(flag=='Y'){

flag='C';

Cars car;

SQstack park;//定义栈并初始化

InitStack(&park);

SQueue street;//定义队列并初始化

setSQueue(&street);

cout<<“请输入本停车场最多可提供的车位数:”;

scanf(“%d”,&maxNum);

getchar();

cout<<“请输入每小时停车费：”;

cin>>Pprice;

cout<

cout<<“请输入到达(A)/离开(D)信息，车牌号，时间（格式为A 1 5）:”;

cin>>car.condition>>car.number>>car.time;

//scanf(“%c %d %d”,&car.condition,&car.number,&car.time);

//getchar();

while(car.condition!='E'&&car.number!=0&&car.time!=0)

{

switch(car.condition)

{

case 'A':

{

enterPark(car,park,street);

break;

}

case 'D':

{

int lasttime;

lasttime=outOfPark(car,park,street,car.number,car.time);

cout<

cout<<“此车在停车场停留了”<break;

}

default :cout<<“请输入正确的格式！”<

}

cin>>car.condition>>car.number>>car.time;

//scanf(“%c %d %d”,&car.condition,&car.number,&car.time);

Cars headCar;struct CarNode *nextCar;}CarNode;

typedef struct { CarNode *firstCar;CarNode *lastCar;

int length;}SQueue;//建队列链表

void setSQueue(SQueue *sq){ CarNode *car=(CarNode *)malloc(sizeof(CarNode));sq->firstCar=car;sq->lastCar=car;sq->firstCar->nextCar=NULL;sq->length=0;} //进入队列操作

void enterSQueue(SQueue *sq,int num,int t){ CarNode *car=(CarNode *)malloc(sizeof(CarNode));car->headCar.condition='D';car->headCar.number=num;car->headCar.time=t;car->headCar.position=2;

car->nextCar=NULL;sq->lastCar->nextCar=car;sq->lastCar=car;sq->length++;} //出队列操作

void exceedSQueue(SQueue *sq){ if(sq->firstCar==sq->lastCar)

return;CarNode *car=(CarNode *)malloc(sizeof(CarNode));car=sq->firstCar->nextCar;sq->firstCar->nextCar=car->nextCar;sq->length--;if(sq->lastCar==car)

sq->lastCar=sq->firstCar;free(car);

}

//检测队列存在

int SQueueEmpty(SQueue sq){ if(sq.firstCar==sq.lastCar)

return 1;else

return 0;} //队首元素

void getSQueue(SQueue sq,Cars *e){ if(sq.firstCar==sq.lastCar)

return;*e=sq.firstCar->nextCar->headCar;}

//队列长度

int SQueueLength(SQueue sq){ int len=0;if(sq.firstCar!=sq.lastCar)len=sq.length;return len;}

#endif

manager_stack.h #include #include #include“manager_cars.h”

#ifndef manager_stack_h #define manager_stack_h

#define STACK_INIT_SIZE 100 //栈的存储空间初始分配量 #define STACKINCREMENT 10 //栈的存储空间分配增量

typedef struct SQstack

//栈的结构体

{ Cars * base;Cars * top;int stacksize;S.base;}

extern int GetTop(SQstack S,Cars *e)//若栈不为空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR { if(S.top == S.base)return 0;

*e = *(S.top-1);

return 1;

}

extern int Push(SQstack*S,Cars e)//插入元素e为新的栈顶元素

{ if(S->top-S->base >= S->stacksize)

{

S->base =(Cars *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(Cars));

if(!S->base)return 0;

S->top = S->base + S->stacksize;

S->stacksize += STACKINCREMENT;

}

*S->top++ = e;

return 1;

}

extern int Pop(SQstack *S,Cars *e)//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR { if(S->top == S->base)return 0;

*e = *--S->top;

return 1;

}

#endif

七、软件说明书

1、打开系统，输入Y进入管理系统。

2、接下来按提示输入停车场的可供使用的车位数。

3、按提示输入该停车场每小时收费标准。

4、按提示输入到达后者离开信息，例如A 1 5，D 1 10。

5、输入E 0 0并输入N，退出系统。

八、测试报告

1、如图，当打开系统时出现此界面，输入Y为进入系统，输入N为退出系统。

2、如图，如果输入错误会提示出错，并重新输入。

3、如图，输入Y后，按提示依次输入停车场可提供的最大车位数和每小时的停车费。

4、如图，输入A 1 5后，提示进入停车场的信息。

5、如图，输入A 2 10，A 3 15后，依次显示提示信息。

6、如图，输入D 1 20后，分别显示便道进入停车场的3号车和1号车的收费情况。

7、如图，输入E 0 0，再按提示输入N，即可退出系统。

九、课程设计总结

通过团队对该问题分析，互相补充了观点，增强了对该题目正确认识。队员们进行了缜密的需求分析，并分工完成各文件和函数的编写。队员们纷纷表示，这绝对是一个以前不能想象到的任务。通过对该系统的编写、实现，着实增强了队员们的团队意识以及对数据结构的进一步的理解。当程序成功运行后，队员们都非常兴奋，虽然本系统仍有瑕疵，但是可以说这是队员们的心血。

0

第三篇：2012数据结构课程设计

数 据 结 构

课程设计报告

题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间：

一、课程设计题目分析

本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。

二、设计思路

本程序采用C语言来完成课程设计。

1、首先，利用顺序存储结构来构造两个存储多项式A(x)和 B(x)的结构。

2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。

3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。

4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。

三、设计算法分析

1、相关函数说明：

(1)定义数据结构类型为线性表的链式存储结构类型变量

typedef struct Polynomial{}

(2)其他功能函数

插入函数void Insert(Polyn p,Polyn h)

比较函数int compare(Polyn a,Polyn b)

建立一元多项式函数Polyn Create(Polyn head,int m)

求解并建立多项式a+b，Polyn Add(Polyn pa,Polyn pb)

求解并建立多项式a-b，Polyn Subtract(Polyn pa,Polyn pb)2

求解并建立多项式a*b，Polyn Multiply(Polyn pa,Polyn pb)

求解并建立多项式a/b，void Device(Polyn pa,Polyn pb)

输出函数输出多项式，void Print(Polyn P)

销毁多项式函数释放内存，void Destroy(Polyn p)

主函数，void main（）

2、主程序的流程基函数调用说明(1)typedef struct Polynomial {

float coef;

int expn;

struct Polynomial *next;} *Polyn,Polynomial;

在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。

(2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下：

Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式

p=head=(Polyn)malloc(sizeof(struct Polynomial));为输入的多项式申请足够的存储空间

p=(Polyn)malloc(sizeof(struct Polynomial));建立新结点以接收数据

Insert(p,head);调用Insert函数插入结点

这就建立一元多项式的关键步骤

(3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void Insert(Polyn p,Polyn h)进行插入操作。(4)加、减、乘、除、的算法实现：

在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。

(5)另一个子函数是输出函数 PrintPolyn（）；

输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。

四、程序新点

通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“Color E0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。

五、设计中遇到的问题及解决办法

首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4

代码编写。

其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。

最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。

六、测试（程序截图）

1.数据输入及主菜单

2.加法和减法模块

3.乘法和除法模块

七、总结

通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。

八、指导老师评语及成绩

附录：（课程设计代码）

#include #include #include typedef struct Polynomial {

float coef;6

int expn;

struct Polynomial *next;} *Polyn,Polynomial;

//Polyn为结点指针类型 void Insert(Polyn p,Polyn h){

if(p->coef==0)free(p);

//系数为0的话释放结点

else

{

Polyn q1,q2;

q1=h;q2=h->next;

while(q2&&p->expnexpn)//查找插入位置

{

q1=q2;q2=q2->next;}

if(q2&&p->expn==q2->expn)//将指数相同相合并 {

q2->coef+=p->coef;

free(p);

if(!q2->coef)//系数为0的话释放结点

{ q1->next=q2->next;free(q2);}

}

else { p->next=q2;q1->next=p;

}//指数为新时将结点插入

} 7

} //建立一个头指针为head、项数为m的一元多项式 Polyn Create(Polyn head,int m){

int i;

Polyn p;

p=head=(Polyn)malloc(sizeof(struct Polynomial));

head->next=NULL;

for(i=0;i

{

p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据

printf(“请输入第%d项的系数与指数:”,i+1);

scanf(“%f %d”,&p->coef,&p->expn);

Insert(p,head);

//调用Insert函数插入结点

}

return head;} //销毁多项式p void Destroy(Polyn p){

Polyn q1,q2;

q1=p->next;8

q2=q1->next;

while(q1->next)

{

free(q1);

q1=q2;//指针后移

q2=q2->next;

} } //输出多项式p int Print(Polyn P){

Polyn q=P->next;

int flag=1;//项数计数器

if(!q)//若多项式为空，输出0

{

putchar('0');

printf(“n”);

return;

}

while(q)

{

if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9

if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况

{

printf(“%g”,q->coef);

if(q->expn==1)putchar('X');

else if(q->expn)printf(“X^%d”,q->expn);

}

else

{

if(q->coef==1){

if(!q->expn)putchar('1');

else if(q->expn==1)putchar('X');

else printf(“X^%d”,q->expn);}

if(q->coef==-1){

if(!q->expn)printf(“-1”);

else if(q->expn==1)printf(“-X”);

else printf(“-X^%d”,q->expn);}

}

q=q->next;

flag++;

}

printf(“n”);} int compare(Polyn a,Polyn b){

if(a&&b)

{

if(!b||a->expn>b->expn)return 1;

else if(!a||a->expnexpn)return-1;

else return 0;

}

else if(!a&&b)return-1;//a多项式已空，但b多项式非空

else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 Polyn Add(Polyn pa,Polyn pb){

Polyn qa=pa->next;

Polyn qb=pb->next;

Polyn headc,hc,qc;

hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 11

hc->next=NULL;

headc=hc;

while(qa||qb){

qc=(Polyn)malloc(sizeof(struct Polynomial));

switch(compare(qa,qb))

{

case 1:

qc->coef=qa->coef;

qc->expn=qa->expn;

qa=qa->next;

break;

case 0:

qc->coef=qa->coef+qb->coef;

qc->expn=qa->expn;

qa=qa->next;

qb=qb->next;

break;

case-1:

qc->coef=qb->coef;

qc->expn=qb->expn;

qb=qb->next;

break;12

}

if(qc->coef!=0)

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

else free(qc);//当相加系数为0时，释放该结点

}

return headc;} //求解并建立多项式a-b，返回其头指针 Polyn Subtract(Polyn pa,Polyn pb){

Polyn h=pb;

Polyn p=pb->next;

Polyn pd;

while(p)//将pb的系数取反

{ p->coef*=-1;p=p->next;}

pd=Add(pa,h);

for(p=h->next;p;p=p->next)

//恢复pb的系数

p->coef*=-1;13

return pd;} //求解并建立多项式a*b，返回其头指针 Polyn Multiply(Polyn pa,Polyn pb){

Polyn hf,pf;

Polyn qa=pa->next;

Polyn qb=pb->next;

hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点

hf->next=NULL;

for(;qa;qa=qa->next)

{

for(qb=pb->next;qb;qb=qb->next)

{

pf=(Polyn)malloc(sizeof(struct Polynomial));

pf->coef=qa->coef*qb->coef;

pf->expn=qa->expn+qb->expn;

Insert(pf,hf);//调用Insert函数以合并指数相同的项

}

}

return hf;}

//求解并建立多项式a/b，返回其头指针 void Device(Polyn pa,Polyn pb){

Polyn hf,pf,temp1,temp2;

Polyn qa=pa->next;

Polyn qb=pb->next;

hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商

hf->next=NULL;

pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数

pf->next=NULL;

temp1=(Polyn)malloc(sizeof(struct Polynomial));

temp1->next=NULL;

temp2=(Polyn)malloc(sizeof(struct Polynomial));

temp2->next=NULL;

temp1=Add(temp1,pa);

while(qa!=NULL&&qa->expn>=qb->expn)

{

temp2->next=(Polyn)malloc(sizeof(struct Polynomial));

temp2->next->coef=(qa->coef)/(qb->coef);

temp2->next->expn=(qa->expn)-(qb->expn);

Insert(temp2->next,hf);

pa=Subtract(pa,Multiply(pb,temp2));15

qa=pa->next;

temp2->next=NULL;

}

pf=Subtract(temp1,Multiply(hf,pb));

pb=temp1;

printf(“商是:”);

Print(hf);

printf(“余数是:”);

Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式A printf(“n”);printf(“请输入B(x)的项数:”);16

scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式B printf(“n”);printf(“**********************************************n”);printf(“*

多项式操作菜单

printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){

printf(”执行操作:“);

scanf(”%d“,&flag);

switch(flag)

{

case 1:

printf(”多项式A(x):“);Print(pa);*n”);

printf(“多项式B(x):”);Print(pb);

break;

case 2:

pc=Add(pa,pb);

printf(“多项式A(x)+B(x):”);Print(pc);

Destroy(pc);break;

case 3:

pd=Subtract(pa,pb);

printf(“多项式A(x)-B(x):”);Print(pd);

Destroy(pd);break;

case 4:

pf=Multiply(pa,pb);

printf(“多项式A(x)*B(x):”);

Print(pf);

Destroy(pf);

break;

case 5:

Device(pa,pb);18

break;

case 6:

exit(0);

break;

} }

Destroy(pa);

Destroy(pb);}

第四篇：数据结构课程设计

数据结构课程设计

1.赫夫曼编码器

设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求：

1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)

2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树；

3)编码：利用建好的哈夫曼树生成哈夫曼编码；

4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。

代码如下：

#include #include #include #include #define N 200

typedef struct HTNode

//结构体 { int Weight;

char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode;

void Save(int n,HTNode *HT)

//把权值保存到文件 {

FILE * fp;

int i;

if((fp=fopen(“data.txt”,“wb”))==NULL)

{

printf(“cannot open filen”);

return;

}

for(i=0;i

if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1)

printf(“file write errorn”);

fclose(fp);

system(“cls”);

printf(“保存成功！”);

}

void Create_H(int n,int m,HTNode *HT)

//建立赫夫曼树，进行编码 {

int w,k,j;char c;for(k=1;k<=m;k++){

if(k<=n)

{

printf(“n请输入权值和字符(用空格隔开): ”);

scanf(“%d”,&w);

scanf(“ %c”,&c);HT[k].ch=c;

HT[k].Weight=w;

}

else HT[k].Weight=0;

HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;}

int p1,p2,w1,w2;

for(k=n+1;k<=m;k++){

p1=0;p2=0;

w1=32767;w2=32767;

for(j=1;j<=k-1;j++)

{

if(HT[j].Parent==0)

{

if(HT[j].Weight

{

w2=w1;p2=p1;

w1=HT[j].Weight;

p1=j;

}

else if(HT[j].Weight

{

w2=HT[j].Weight;

p2=j;

}

}

} HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight;

HT[p1].Parent=k;HT[p2].Parent=k;

} printf(“输入成功！”);}

void Coding_H(int n,HTNode *HT)

//对结点进行译码 { int k,sp,fp,p;char *cd;HCode HC;

HC=(HCode)malloc((n+1)*sizeof(char *));

cd=(char *)malloc(n*sizeof(char));cd[n-1]='';

printf(“************************n”);printf(“Char Codingn”);

for(k=1;k<=n;k++)

{

sp=n-1;p=k;fp=HT[k].Parent;

for(;fp!=0;p=fp,fp=HT[fp].Parent)

if(HT[fp].Lchild==p)

cd[--sp]='0';

else

cd[--sp]='1';

HC[k]=(char *)malloc((n-sp)*sizeof(char));

strcpy(HC[k],&cd[sp]);

printf(“%c

%sn”,HT[k].ch,HC[k]);

}

printf(“************************n”);free(cd);} void Read(int n,HTNode *HT)

//从文件中读出数据 {

int i;FILE * fp;if((fp=fopen(“data.txt”,“rb”))==NULL){

printf(“cannot open filen”);

exit(0);} for(i=0;i

fread(&HT[i].Weight,sizeof(struct HTNode),1,fp);// printf(“%d n”,HT[i].Weight);

} Coding_H(n,HT);

fclose(fp);}

void Print_H(int m,HTNode *HT)

//输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“Num Weight

Par LCh RCh n”);for(k=1;k<=m;k++){

printf(“%d ”,k);

printf(“

%d”,HT[k].Weight);

printf(“

%d”,HT[k].Parent);

printf(“

%d”,HT[k].Lchild);

printf(“

%dn”,HT[k].Rchild);

} printf(“************************n”);}

void Decode(int m,HTNode *HT)

//对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){

if(a[j]=='0')

i=HT[i].Lchild;

else i=HT[i].Rchild;

if(HT[i].Lchild==0)

//HT[i]是叶结点

{

printf(“%c”,HT[i].ch);

i=m;

//回到根结点

}

j++;} printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2')

printf(“ERROR”);}

int main()

//主函数 { int n,m,c;HTNode HT[N];do {

system(“color 2f”);

//运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt 赫夫曼编译码系统 ttt”);

printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”);

printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”);

printf(“nnttt请选择:”);

scanf(“%d”,&c);

switch(c)

{

case 1:system(“cls”);printf(“输入多少结点:”);

scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break;

case 2:system(“cls”);Save(n,HT);break;

case 3:system(“cls”);Print_H(m,HT);break;

case 4:system(“cls”);Coding_H(n,HT);break;

case 5:system(“cls”);Decode(m,HT);break;

case 6:system(“cls”);Read(n,HT);break;

case 7:system(“cls”);exit(0);

}

}while(1);return 0;}

运行界面如下：

2.学生成绩管理（链表实现）要求：

实现如下功能：增加、查找、删除、输出、退出。

代码如下：

#include #include #include typedef struct score

//定义成绩信息结构体 {

char Number[20];char Name[20];char Chinese[20];char English[20];char Math[20];}score;typedef struct node_score

//定义成绩信息链表结点，包括数据域和指针域 {

score data;struct node_score *next;}node_score,*p_node_score;p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s)//输出信息函数 { printf(“ %10s”,s.Number);printf(“ |

%-6s”,s.Name);printf(“

|

%-3s”,s.Chinese);printf(“

|

%-3s”,s.English);

printf(“ |

%-3sn”,s.Math);} void View()//输出函数 {

p_node_score pNodeScore;

pNodeScore=headScore;printf(“

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩n”);while(pNodeScore!= NULL){

PrintScore(pNodeScore->data);//输出学生信息和成绩信息

pNodeScore=pNodeScore->next;} } void Add(){

p_node_score pNodeScore;// 定义一个节点

pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间

printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){ //如果头结点为空

headScore=pNodeScore;

pNodeScore->next=NULL;} else

{ //如果头结点不为空

pNodeScore->next=headScore;

headScore=pNodeScore;//将头结点新结点

} } void Input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i

Add();printf(“输入成功！”);} int Delete(){ p_node_score pNodeScore,p1;//p1为pNodeScore的前驱

p1=headScore;if(p1==NULL){

printf(“成绩表中没有数据！请先添加数据！n”);

return 0;} char DeleteNumber[20];

printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0)

{ //如果要删除的结点在第一个

headScore=p1->next;

pNodeScore=p1;

printf(“学号为%s的学生信息已经删除！n”,DeleteNumber);

return 0;} else

{

pNodeScore=p1->next;

while(pNodeScore!=NULL)

{

if(strcmp(pNodeScore->data.Number,DeleteNumber)==0)

{

p1->next=pNodeScore->next;

printf(“学号为%s的学生信息已经删除！n”,DeleteNumber);

return 0;

}

else

{ //否则，结点向下一个，p1仍为pNodeScore的前驱

p1=pNodeScore;

pNodeScore=pNodeScore->next;

}

} } printf(“没有此学号的学生！”);} int Change(){

p_node_score pNodeScore;

pNodeScore=headScore;if(pNodeScore==NULL){

printf(“成绩表中没有数据！请先添加数据！n”);

return 0;} char EditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){

if(strcmp(pNodeScore->data.Number,EditNumber)==0)

{ //用strcmp比较两字符串是否相等，相等则返回0

printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息

printf(“

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩n”);

PrintScore(pNodeScore->data);

printf(“语文新成绩:”);

scanf(“%s”,pNodeScore->data.Chinese);

printf(“英语新成绩:”);

scanf(“%s”,pNodeScore->data.English);

printf(“高数新成绩:”);

scanf(“%s”,pNodeScore->data.Math);

printf(“成绩已经修改！”);

return 0;

}

pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点

} printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生

} int Find(){

p_node_score pNodeScore;

pNodeScore=headScore;if(pNodeScore==NULL){

printf(“成绩表中没有数据！请先添加数据！n”);

return 0;} char FindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){

if(strcmp(pNodeScore->data.Number,FindNumber)==0)

{

printf(“你要查找的学生成绩信息如下：n”);

printf(“

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩n”);

PrintScore(pNodeScore->data);

return 0;

}

pNodeScore=pNodeScore->next;} printf(“没有此学号的学生！n”);} int main()

//主函数 { int choice=0;headScore=NULL;int c;do {

system(“color 2f”);

//运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt 学生成绩管理系统 ttt”);

printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”);

printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”);

printf(“nnttt请选择:”);

scanf(“%d”,&c);

switch(c)

{

case 1:system(“cls”);Input();break;

case 2:system(“cls”);View();break;

case 3:system(“cls”);Add();break;

case 4:system(“cls”);Change();break;

case 5:system(“cls”);Delete();break;

case 6:system(“cls”);Find();break;

case 7:system(“cls”);exit(0);

}

}while(1);return 0;}

运行界面如下：

第五篇：《数据结构》课程设计文档格式（定稿）

课程设计报告的内容

设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写,打印并装订,排版及图,表要清楚,工整.装订顺序如下:封面、目录、正文.正文包括以下7个内容:

1.需求分析

陈述说明程序设计的任务,强调的是程序要做什么，需要什么结果、所能达到的功能.2.概要设计

说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.3.详细设计

实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图、N S 图进行描述,画出函数和过程的调用关系图.4.调试分析

内容包括:

a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想;

c.经验和体会等.5.测试结果

列出你的测试结果,包括输入和输出.这里的测试数据应该完整和严格,最好多于需求分析中所列.6.参考文献

列出参考的相关资料和书籍.封面格式如下：

数据结构课程设计报告

班级：_____ _____ _____ _________

姓名：____________________

指导教师：___________________

成绩：__________________________

信息工程学院

年月日

目录

1.需求分析 ………………………………………………

22．概要设计………………………………………………2

3.详细设计 ………………………………………………2

4.调试分析 ………………………………………………2

5.测试结果… ……………………………………………2 参考文献 …………………………………………………6

附录……………………………………………………

一、需求分析

二、概要设计

三、详细设计

四、调试分析

五、测试结果

六、参考文献

七、附录

附录为程序代码！4