数据结构课程设计报告—纸牌游戏

课题设计2:扑克牌游戏

1、问题描述

编号为1-52张牌,正面向上,从第2张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后,从第3张开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;然后…从第4张开始,以4为基数,是4的倍数的牌翻一次, 直到最后一张牌;...再依次5的倍数的牌翻一次,6的,7的 直到 以52为基数的 翻过,输出:这时正面向上的牌有哪些?

存储结构:

源程序:#include <stdio.h>

void main()

{   

int i,j,a[52];

     for(i=2;i<=52;i++)

       for(j=i-1;j<52;j+=i)

           a[j]=!a[j];

  printf("正面向上的牌有:");

  for(i=0;i<52;i++)    

   if(a[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
{
   数据对象:D={ai | ai∈CharSet,i= 1,2,…,n,n≥0}
   数据关系:R1={&lt; ai-1 ,ai &gt; | ai ∈D, I=2,…,n}

三.源程序:#include<stdio.h>

#include<stdlib.h>

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;i<=n;i++)

 {

  p=(Node *)malloc(sizeof(Node));

  if(!p) exit(1);

  printf("the key_%d is:",i);

  scanf("%d",&p->key);

  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;i<=n;i++)

 {

  for(int j=1;j<x;j++)

   p=p->next;

  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<iostream.h>

#include"string.h"

#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;

class 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<<"货架已满"<<endl;

else

{

top++;

stack[top].num=x;

stack[top].date.Day=day;

stack[top].date.Month=month;

stack[top].date.Year=year;

}

}

void pop()

{

if(top==0)

cout<<"货架已空"<<endl;

else

top--;

}

elemtype gettop()

{

if(top==0)

cout<<"货架已空"<<endl;

else

return top;}

bool empty()

{

return top==0;

}

};

void main()

{

seqstack c[k+1]; //存放k种商品的数组,用c[0]来做中介货架

int Txq[k+1]; //第i种取货用的时间

int Txs[k+1]; //第i种上货用的时间

int Nx[k+1]; //第i种每天的销售数量

int N=0; //每天销售总量

int Tx[k+1]; //第i种每天上货的总时间

int T=0; //每天上货用的总时间

char yn='Y';

for(int i=1;i<=k;i++)

{

cout<<" ******************************"<<endl;

cout<<" 商品货架管理系统"<<endl;

cout<<" ******************************"<<endl;

Node store[20];

char year,month;

int count; //货架上第i种商品的数目

int x,d,m,y; //x为第i种商品的序号

cout<<"请输入货架上第"<<i<<"种货物的详细信息:"<<endl;

cout<<"(序号,生产日期(年、月、日如2006.2.13),现在货架上的存货数目,上货用时和取货用时)"<<endl;

cin>>x>>y>>year>>m>>month>>d>>count>>Txs[i]>>Txq[i];

Nx[i]=maxsize-count;

cout<<"货架上还需上"<<i<<"货物"<<Nx[i]<<"件"<<endl;

Tx[k]=Txs[i]*(maxsize+count)+2*Txq[i]*count;

cout<<"该货架满货需要用时"<<Tx[k]<<endl;

cout<<"是否要上货?(Y/N)"<<endl;

cin>>yn;

if(yn=='Y'||yn=='y')

{

int numbers,nian,yue,ri;

cout<<"请输入要上货物的数目及生产日期(年、月、日)"<<endl; //上的是同一日期生产的货物

cin>>numbers>>nian>>yue>>ri;

if(numbers>maxsize-count)

{

cout<<"要上的货物数目超出了货架的最大容量,请重新输入"<<endl;

cin>>numbers>>nian>>yue>>ri;

}

for(int j=1;j<=numbers;j++)

{

}

}

N+=Nx[i];

T+=Tx[i];

}

cout<<"每天销售总量为:"<<N<<endl;

cout<<"每天上货用的总时间为:"<<T<<endl;

}

3、测试结果:

 


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

1、需求分析:

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

2、源程序:#include <stdio.h>

#include <string.h>

#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

{

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<radix_n;j++)

{

f[j]=e[j]=0;

}

for(p=sl[0].next;p;p=sl[p].next)

{

j=sl[p].keys[i]%48;

if(!f[j])

f[j]=p;

else

sl[e[j]].next=p;

e[j]=p;

}

}

void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)

{

int j,t;

for(j=0;!f[j];j++);

sl[0].next=f[j];

t=e[j];

while(j<radix_n-1)

{

for(j=j+1;j<radix_n-1&&!f[j];j++);

if(f[j])

{

sl[t].next=f[j];

t=e[j];

}

}

sl[t].next=0;

}

void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)

{

int j,p;

for(j=0;j<radix_c;j++)

{

f[j]=e[j]=0;

}

for(p=sl[0].next;p;p=sl[p].next)

{

j=sl[p].keys[i]%65;

if(!f[j])

f[j]=p;

else

sl[e[j]].next=p;

e[j]=p;

}

}

void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)

{

int j,t;

for(j=0;!f[j];j++);

sl[0].next=f[j];

t=e[j];

while(j<radix_c-1)

{

for(j=j+1;j<radix_c-1&&!f[j];j++);

if(f[j])

{

sl[t].next=f[j];

t=e[j];

}

}

sl[t].next=0;

}

void radixsort(sllist &l)//链式

{

int i;

arrtype_n fn,en;

arrtype_c fc,ec;

for(i=0;i<l.length;i++)

l.sl[i].next=i+1;

l.sl[l.length].next=0;

for(i=l.keynum-1;i>=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<l.length;i++)

{

while(p<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<=high)

{

mid=(low+high)/2;

if(strcmp(key,l.sl[mid].keys)==0)

return mid;

else if(strcmp(key,l.sl[mid].keys)<0)

high=mid-1;

else

low=mid+1;

}

return 0;

}

void seqsearch(sllist l,keytype key[],int i)

{

int j,k,m=0;

printf("*************************************************************\n");

printf("* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *\n");

for(j=1;j<=l.length;j++)

{

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<=5)

{

printf("\n ********************\n");

printf(" * 航班信息查询系统 *\n");

printf(" ********************\n");

printf(" * 1.航 班 号 *\n");

printf(" * 2.起 点 站 *\n");

printf(" * 3.终 点 站 *\n");

printf(" * 4.起飞时间 *\n");

printf(" * 5.到达时间 *\n");

printf(" * 0.退出系统 *\n");

printf(" ********************\n");

printf(" 请选择(0-5):");

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("\n\n\n 再 见\n\n\n");

}

}

}

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

相关推荐