数据结构课程设计论文_我的数据结构课程设计

数据结构课程设计论文由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“我的数据结构课程设计”。

09数据结构课程设计论文

课题：

一、迷宫求解

二、扑克牌游戏

三、joseph环

四、商品货架管理

五、航空客运订票系统

………………………………………………………………………………

班级：07信息与计算科学 学生：XXX 学号：

指导老师：XXX

目录

课程设计封…………………………………………………………………1 目录……………………………………………………………………2 迷宫求解………………………………………………………………3—9

（一）需求分析……………………………………………………………3

（二）源程序……………………………………………………………4—5

（三）测试后的结果……………………………………………………6—7

（四）结果分析……………………………………………………………8 扑克牌游戏……………………………………………………………9—10

（一）需求分析……………………………………………………………9

（二）源程序……………………………………………………………9

（三）测试后的结果………………………………………………………9

（四）结果分析…………………………………………………………10 joseph环……………………………………………………………10—16

（一）需求分析……………………………………………………………11

（二）源程序…………………………………………………………12—14

（三）测试后的结果…………………………………………………15—16

（四）结果分析……………………………………………………………16 商品货架管理………………………………………………………16—17

（一）需求分析……………………………………………………………16

（二）源程序……………………………………………………………16

（三）测试后的结果……………………………………………………16

（四）结果分析…………………………………………………………17 航空客运订票系统…………………………………………………18—24

（一）需求分析……………………………………………………………18

（二）源程序……………………………………………………19—20

（三）测试后的结果…………………………………………………20—22

（四）结果分析…………………………………………………………24 课程设计心得体会…………………………………………………24—25

课题设计1：迷宫求解

一.需求分析：

本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。

首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。

二、概要设计： 1.抽象数据类型定义：

ADT Find{ 数据对象：D={ai?ai ∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={?ai-1, ai∈D } 基本操作：

find(&S)初始条件：已初始化栈S，且栈为空

操作结果：从栈Ｓ中找出相对应的数据关系，并输出结果 }ADT Find 2.主程序的流程以及各程序模块之间的调用关系：(1).定义变量i、j、w、z为整形变量(2).输入迷宫二维数组maze(0:m,0:n)(3).调用子程序find()(4).结束程序

三、相应的源程序如下： #include #include typedef enum { ERROR, OK } Status;typedef struct

{ int row, line;

}PosType;

typedef struct

{

int di, ord;

PosType seat;

}SElemType;

typedef struct { SElemType * base;SElemType * top;int

stacksize;}SqStack;Status InitStack(SqStack &S);

Status Push(SqStack &S,SElemType &a);

Status Pop(SqStack &S,SElemType &a);

Status StackEmpty(SqStack S);

Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end);void Initmaze(int maze[12][12],int size);

void printmaze(int maze[12][12],int size);

Status Pa(int maze[12][12],PosType CurPos);

void Markfoot(int maze[12][12], PosType CurPos);

PosType NextPos(PosType CurPos, int Dir);

void printpath(int maze[12][12],SqStack S,int size);void main(void){

SqStack S;int size,maze[12][12];for(int n=0;n

printf(“创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):n”);

scanf(“%d”,&size);if(size10){printf(“输入错误!”);return;}

Initmaze(maze,size);

printmaze(maze,size);

PosType start,end;

printf(“输入入口行坐标和列坐标:”);scanf(“%d”,&start.row);scanf(“%d”,&start.line);

printf(“输入出口行坐标和列坐标:”);scanf(“%d”,&end.row);scanf(“%d”,&end.line);

if(MazePath(maze,S,start,end))

printpath(maze,S,size);

else printf(“找不到通路!nn”);} } Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end)

{

PosType curpos;int curstep;SElemType e;InitStack(S);curpos = start;

curstep = 1;

do {

if(Pa(maze,curpos))

{

Markfoot(maze,curpos);

e.di =1;

e.ord = curstep;

e.seat= curpos;

Push(S,e);

if(curpos.row==end.row && curpos.line==end.line)

return OK;

curpos = NextPos(curpos, 1);

curstep++;

}

else

{

if(!StackEmpty(S))

{

Pop(S,e);

while(e.di==4 &&!StackEmpty(S))

{

Markfoot(maze,e.seat);

Pop(S,e);

}

if(e.di

{

e.di++;

Push(S, e);

curpos = NextPos(e.seat, e.di);

}

}

}

} while(!StackEmpty(S));return ERROR;}

void Initmaze(int maze[12][12],int size){

char select;

printf(“选择创建方式 A:自动生成 B:手动创建n”);

label:scanf(“%c”,&select);if(select=='a'||select=='A')

{

for(int i=0;i

for(i=1;i

{

maze[i][0]=1;

for(int j=1;j

maze[i][j]=rand()%2;

maze[i][size+1]=1;

}

for(i=0;i

}

else if(select=='b'||select=='B')

{

printf(“按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):n”,size,size);

for(int i=0;i

for(i=1;i

{

maze[i][0]=1;

for(int j=1;j

scanf(“%d”,&maze[i][j]);

maze[i][size+1]=1;

}

for(i=0;i

}

else if(select=='n')goto label;

else printf(“输入错误!”);} void printmaze(int maze[12][12],int size){ printf(“nn”);printf(“显示所建的迷宫(#表示外面的墙):n”);

for(int i=0;i

printf(“%c ”,'#');

for(int j=1;j

{

printf(“%d ”,maze[i][j]);

}

printf(“%c”,'#');

printf(“n”);

}

for(i=0;i

void printpath(int maze[12][12],SqStack S,int size){

printf(“nn通路路径为:n”);SElemType * p=S.base;while(p!=S.top){

maze[p->seat.row][p->seat.line]=2;

p++;}

for(int i=0;i

printf(“%c ”,'#');

for(int j=1;j

{

if(maze[i][j]==2)printf(“%c ”,'0');

else

printf(“ ”);

}

printf(“%c”,'#');

printf(“n”);}

for(i=0;i

Status Pa(int maze[12][12],PosType CurPos){ if(maze[CurPos.row][CurPos.line]==0)

return OK;

else return ERROR;

} void Markfoot(int maze[12][12],PosType CurPos){ maze[CurPos.row][CurPos.line]=1;} PosType NextPos(PosType CurPos, int Dir){ PosType ReturnPos;switch(Dir)

{

case 1:

ReturnPos.row=CurPos.row;

ReturnPos.line=CurPos.line+1;

break;

case 2:

ReturnPos.row=CurPos.row+1;

ReturnPos.line=CurPos.line;

break;

case 3:

ReturnPos.row=CurPos.row;

ReturnPos.line=CurPos.line-1;

break;

case 4:

ReturnPos.row=CurPos.row-1;

ReturnPos.line=CurPos.line;

break;} return ReturnPos;} Status InitStack(SqStack &S){ S.base=(SElemType *)malloc(100*sizeof(SElemType));if(!S.base)return ERROR;S.top=S.base;S.stacksize=100;return OK;} Status Push(SqStack &S,SElemType &a){

*S.top++=a;return OK;} Status Pop(SqStack &S,SElemType &a){ if(S.top==S.base)return ERROR;a=*--S.top;return OK;} Status StackEmpty(SqStack S){ if(S.top==S.base)return OK;return ERROR;}

以下为测试数据：

输入一个矩阵，例如：1 0 0 1 1

0 0 1 1 10 0 0 1

0 1 0 1 1

1 0 0 0

输入入口行坐标和列坐标：1 2 输入出口行坐标和列坐标：5 5 通路路径为：

课题设计2：扑克牌游戏

1、问题描述

编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到

最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 存储结构：

源程序：#include void main(){

int i,j,a[52];for(i=2;i

a[j]=!a[j];printf(“正面向上的牌有:”);for(i=0;i

printf(“%4d”,i+1);}

测试结果：正面向上的牌有：1 4 9 16 25 36 49 算法的时间复杂度：T（n）=O（n2）

课题设计3：joseph环

一.需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1.输入的形式和输入值的范围

本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2.输出的形式

从屏幕显示出列顺序。3.程序功能

提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。

二、概要设计

以单向循环链表实现该结构。1.抽象数据类型的定义为： ADT LNode { 10

数据对象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0}

数据关系：R1={ | ai ∈D，I=2，…，n} 三．源程序：#include #include typedef struct Node { int key;//每个人持有的密码 int num;//这个人的编号

struct Node *next;//指向下一个节点 }Node,*Link;void InitList(Link &L)//创建一个空的链表 { L=(Node *)malloc(sizeof(Node));if(!L)exit(1);L->key=0;L->num=0;L->next=L;} void Creater(int n,Link &L)//初始化链表 { Link p,q;q=L;for(int i=1;ikey);p->num=i;L->next=p;L=p;} L->next=q->next;free(q);} void main(){ Link L,p,q;int n,x;L=NULL;InitList(L);//构造出一个只有头结点的空链表

printf(“please input the totle number of people:”);scanf(“%d”,&n);//总共的人数n printf(“the start key is:”);

scanf(“%d”,&x);//初始密码为x Creater(n,L);//建立好一个约瑟夫环 p=L;for(int i=1;inext;q=p->next;x=q->key;printf(“%d ”,q->num);p->next=q->next;free(q);} }

四、测试数据：

m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4 输出：6 7 4 1 5 3 2 课题设计4：商品货架管理

1、需求分析：设计一个算法，每一次上货后始终保持生产日期越近的商品越靠近栈底。求货架上剩余货物M、每天销售件数N、员工每天上货工作时间T，三者之间有何关系及T的最小值。

2、源程序：#include #include“string.h” 12

#include“stdio.h” const int maxsize=100;const int k=10;#define elemtype char typedef struct { int Month;int Day;int Year;}DATE;typedef struct { int num;DATE date;} Node;cla seqstack { public: Node stack[maxsize];int top;void inistack(){ top=0;}

void push(int x,int day,int month,int year){ if(top==maxsize)cout

} } void pop(){ if(top==0)cout

int Tx[k+1];//第i种每天上货的总时间 int T=0;//每天上货用的总时间 char yn='Y';for(int i=1;i

char year,month;int count;//货架上第i种商品的数目 int x,d,m,y;//x为第i种商品的序号

cout>x>>y>>year>>m>>month>>d>>count>>Txs[i]>>Txq[i];Nx[i]=maxsize-count;cout>yn;if(yn=='Y'||yn=='y'){ int numbers,nian,yue,ri;cout

cin>>numbers>>nian>>yue>>ri;if(numbers>maxsize-count){ cout>numbers>>nian>>yue>>ri;} for(int j=1;j

3、测试结果：

五、课程设计5：航空客运订票系统

1、需求分析：

对于本设计，可采用基数排序法对于一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快递查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用的较少。

2、源程序：#include #include #define maxspace 100 #define keylen 7 #define radix_n 10 #define radix_c 26 typedef char keytype;typedef struct { char start[6];char end[6];char sche[10];char time1[5];char time2[5];char model[4];int price;}infotype;typedef struct 16

{ keytype keys[keylen];infotype others;int next;}slnode;typedef struct { slnode sl[maxspace];int keynum;int length;}sllist;typedef int arrtype_n[radix_n];typedef int arrtype_c[radix_c];void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e){ int j,p;for(j=0;j

while(j=2;i--){ distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);} for(i=1;i>=0;i--){ distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);} } void arrange(sllist &l)//重新整理 { int p,q,i;slnode temp;p=l.sl[0].next;for(i=1;i

p=l.sl[p].next;q=l.sl[p].next;if(p!=i){ temp=l.sl[p];l.sl[p]=l.sl[i];l.sl[i]=temp;l.sl[i].next=p;} p=q;} } int binsearch(sllist l,keytype key[]){ int low,high,mid;low=1;high=l.length;while(low

switch(i){ case 2:k=strcmp(key,l.sl[j].others.start);break;case 3:k=strcmp(key,l.sl[j].others.end);break;case 4:k=strcmp(key,l.sl[j].others.time1);break;case 5:k=strcmp(key,l.sl[j].others.time2);break;} if(k==0){ m=1;printf(“*

%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n”,l.sl[j].keys,l.sl[j].others.start,l.sl[j].others.end,l.sl[j].others.sche,l.sl[j].others.time1,l.sl[j].others.time2,l.sl[j].others.model,l.sl[j].others.price);} } if(m==0)printf(“* 无此航班信息，可能是输入错误！*n”);printf(“*************************************************************n”);} void searchcon(sllist l){ keytype key[keylen];int i=1,k;while(i>=1&&i

scanf(“%d”,&i);printf(“n”);switch(i){ case 1:printf(“输入要查询的航班号(字母要大写):”);scanf(“%s”,key);k=binsearch(l,key);printf(“*************************************************************n”);if(k==0)printf(“* 无此航班信息，可能是输入错误！*n”);else { printf(“* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n”);printf(“*

%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n”,l.sl[k].keys,l.sl[k].others.start,l.sl[k].others.end,l.sl[k].others.sche,l.sl[k].others.time1,l.sl[k].others.time2,l.sl[k].others.model,l.sl[k].others.price);} printf(“*************************************************************n”);break;case 2:printf(“输入要查询的航班起点站名:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 3:printf(“输入要查询的航班终点站名:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 4:printf(“输入要查询的航班起飞时间:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 5:printf(“输入要查询的航班到达时间:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 0:printf(“nnn 再 见nnn”);22

} } } void inputdata(sllist &l){ int i=++l.length;char yn='y';while(yn=='y'||yn=='Y'){ printf(“航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价n”);scanf(“%s%s%s%s%s%s%s%d”,l.sl[i].keys,l.sl[i].others.start,l.sl[i].others.end,l.sl[i].others.sche,l.sl[i].others.time1,l.sl[i].others.time2,l.sl[i].others.model,&l.sl[i].others.price);++i;getchar();radixsort(l);arrange(l);printf(“继续输入吗?y/n:”);scanf(“%c”,&yn);} l.length=i-1;} void main(){ sllist l;l.keynum=6;l.length=0;inputdata(l);searchcon(l);}

3、测试结果：

航班信息：航班号 起点站 终点站 航班期

起飞时间 到达时间 机型 票价

输入：CA1544 合肥

北京

1.2.4.5

1055

1240

733

960 提示：继续输入吗？y/n：y 显示：航班号 起点站 终点站 航班期

起飞时间 到达时间 机型 票价 MU5341 上海 广州 每日 1420 1615 M90 1280 提示：继续输入吗？y/n：y ……

提示：继续输入吗？y/n:n

最后，课程设计心得体会：

通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到一个问题，想办法去解决时，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写的过程中不可避免的遇到问题，这些问题有的只是一个符号错了，一个括号少了，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。当然，在学习中不要害怕提问，但是这个问题最好是你找不到答案的时候再去提。要经过自己的思考后在去提问，那样才会有效果。

通过一些课程设计，也让自己对于数据结构有了更深层次的理解，虽然有很多的东西并不是自己编，而是在网上找的，但是在调试的那个过程中也是收获很多。本次课程设计，使我对《数据结构》这门课程有了更深入的理解。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。指针其实是C语言的灵魂，许多的数据结构在我们学到这里之前都可以说是精通了。所以我们的任务就是，让数据结构在指针中运行。当然，刚刚开始接触到这些新的东西，是一件非常痛苦的事情，所以我们一定要用非常形象的思维去看待指针，不能太固化。所以，新的东西，比如结构体在指针中的表现方法，数组及 24

多维数组在结构体中的运用，都一点一点的加了进来，同时丰满了我们对原来C的数据机构，数据表示的理解。

《数据结构》就是编程的思维，编程的灵魂，算法的精髓所在，没有了数据结构，程序就好像一个空核，是低效率的。学习数据结构的目的就是提高自己的思想，数据结构的高低是确定于你写的程序的运行效率，想不想到奇异的方法解决问题，程序的壮健性，并不是你记得多少算法。就好像我现在排序算法已经忘记了很多，平衡二叉树的建立跟删除，图论完全忘记。难道这样我就是初学者？？肯定不是，自要有思想在，有些算法用到的时候看看书就可以了。在课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。

课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，单片机已经成为当今计算机应用中空前活跃的领域，在生活中可以说得是无处不在。

通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。

刚开始做这个程序的时候，感到完全无从下手，觉得让我完成这次程序设计根本就是不可能的，于是开始查阅一些资料，如：苏仕华的《数据结构课程设计》之后便开始着手对于一些程序调试以及去看明白。

整个程序和以往所编的程序最大的区别就是要求从文件读入信息，文件是C语言中极其重要的部分，通过课程设计，加深了对文件知识的掌握。我的程序原先是只能从固定的一个文件读入图的信息，经过修改，它可以通过输入文件名来选择要读入的文件，使程序更加灵活，功能更加完善。

通过课程设计还提高了一点改错能力，对于一些常见问题加深了印象。如果我们把编程当作一种乐趣的话，用兴趣去引领学习的话，你会发现学习编码的速度会更快，因为在这个过程中你会有强烈的欲望去看懂它，你会把编码分到最细，这样的成功，对于我们今后的编程学习将会有很大的信心。