数据结构课程设计地图着色问题

第一篇：数据结构课程设计地图着色问题

课程设计报告

课程设计题目：地图着色问题

专业：xxxxxxxxx 班级：xxxxxxxxx 姓名：xxxxxxxxx

一：需求分析：

1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；

2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系； 3)演示程序以用户和计算机的对话方式进行；

4)最后对结果做出简单分析。

二：概要设计

一：设计思路

把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。

二：数据结构设计

因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。

其中：

typedef struct ArcNode { int x;

（表示与当前顶点所表示省份相邻的省份的位置信息）

struct ArcNode *next;

（指向下一个弧结点）}ArcNode;

（表示省份之间相邻关系的弧结点）typedef struct { char *name;（顶点所表示的省份的名称）

int color;

（省份的颜色，用数字表示不同的颜色）

ArcNode *firstnext;（指向第一个弧）}shengfen[35];

三：详细设计

该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。

1.初始化模块

声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。

2.着色模块

为各个省份着色。for(i=1;i<=34;i++){

sheng[i].color=0;} for(i=1;i<=34;i++){

j=1;

p=sheng[i].firstnext;

while(p!=NULL)

{

while(p!=NULL&&j!=sheng[p->x].color)

{

p=p->next;

}

if(p!=NULL)

j++;

}

sheng[i].color=j;} 3.输出模块

输出各个省份的颜色信息。

for(i=1;i<=34;i++){

printf(“%s:”,sheng[i].name);

printf(“%dn”,sheng[i].color);}

printf(“/n0表示白色,1表示蓝色,2表示红色,3表示绿色,4表示黄色”);return 0;

四：调试分析

因为我们的程序已知是中国地图，为中国地图染色，所以程序没有输入，只有输出信息。从输出的信息来看，我们最多使用了4种颜色。关于程序测试时存在的问题，我们程序在写完之后，出现了没有错误但是无法输出信息的问题，从网上查找发现是对警告没处理好的原因，随后我们参考了网上的解决方案把问题解决了。关于程序的改进，我们的程序使用的是有向图，但省份之间的相邻关系用无向图就可以表示，这是程序可以改进的地方。其次，我们的程序输出结果描述省份颜色的是数字，也可以改进后使之输出具体的颜色。

五：源程序清单

#include #include typedef struct ArcNode{ int x;struct ArcNode *next;}ArcNode;typedef struct{ char *name;int color;ArcNode *firstnext;}shengfen[35];int main(){ shengfen sheng;int i,j;ArcNode *p,*hu1,*hu2,*hu3,*hu4,*hu5,*hu6,*hu7,*hu8,*hu9,*hu10,*hu11,*hu12,*hu13,*hu14,*hu15,*hu16,*hu17,*hu18;ArcNode *hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu31,*hu32,*hu33,*hu34,*hu35;ArcNode *hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu48,*hu49,*hu50,*hu51,*hu52;ArcNode *hu53,*hu54,*hu55,*hu56,*hu57,*hu58,*hu59,*hu60,*hu61,*hu62,*hu63,*hu64,*hu65,*hu66;ArcNode *hu67,*hu68,*hu69,*hu70,*hu71,*hu72,*hu73,*hu74,*hu75,*hu76,*hu77,*hu78,*hu79,*hu80,*hu81,*hu82,*hu83,*hu84;ArcNode *hu85,*hu86,*hu87,*hu88,*hu89,*hu90,*hu91,*hu92,*hu93,*hu94,*hu95,*hu96,*hu97,*hu98,*hu99,*hu100;ArcNode *hu101,*hu102,*hu103,*hu104,*hu105,*hu106,*hu107,*hu108,*hu109,*hu110,*hu111,*hu112,*hu113,*hu114,*hu115,*hu116,*hu117;ArcNode *hu118,*hu119,*hu120,*hu121,*hu122,*hu123,*hu124,*hu125,*hu126,*hu127,*hu128,*hu129;ArcNode *hu130,*hu131,*hu132,*hu133,*hu134,*hu135,*hu136,*hu137,*hu138,*hu139,*hu1

40,*hu141,*hu142;hu1=(ArcNode *)malloc(sizeof(ArcNode));hu2=(ArcNode *)malloc(sizeof(ArcNode));hu3=(ArcNode *)malloc(sizeof(ArcNode));hu4=(ArcNode *)malloc(sizeof(ArcNode));hu5=(ArcNode *)malloc(sizeof(ArcNode));hu6=(ArcNode *)malloc(sizeof(ArcNode));hu7=(ArcNode *)malloc(sizeof(ArcNode));hu8=(ArcNode *)malloc(sizeof(ArcNode));hu9=(ArcNode *)malloc(sizeof(ArcNode));hu10=(ArcNode *)malloc(sizeof(ArcNode));hu11=(ArcNode *)malloc(sizeof(ArcNode));hu12=(ArcNode *)malloc(sizeof(ArcNode));hu13=(ArcNode *)malloc(sizeof(ArcNode));hu14=(ArcNode *)malloc(sizeof(ArcNode));hu15=(ArcNode *)malloc(sizeof(ArcNode));hu16=(ArcNode *)malloc(sizeof(ArcNode));hu17=(ArcNode *)malloc(sizeof(ArcNode));hu18=(ArcNode *)malloc(sizeof(ArcNode));hu19=(ArcNode *)malloc(sizeof(ArcNode));hu20=(ArcNode *)malloc(sizeof(ArcNode));hu21=(ArcNode *)malloc(sizeof(ArcNode));hu22=(ArcNode *)malloc(sizeof(ArcNode));hu23=(ArcNode *)malloc(sizeof(ArcNode));hu24=(ArcNode *)malloc(sizeof(ArcNode));hu25=(ArcNode *)malloc(sizeof(ArcNode));hu26=(ArcNode *)malloc(sizeof(ArcNode));hu27=(ArcNode *)malloc(sizeof(ArcNode));hu28=(ArcNode *)malloc(sizeof(ArcNode));hu29=(ArcNode *)malloc(sizeof(ArcNode));hu30=(ArcNode *)malloc(sizeof(ArcNode));hu31=(ArcNode *)malloc(sizeof(ArcNode));hu32=(ArcNode *)malloc(sizeof(ArcNode));hu33=(ArcNode *)malloc(sizeof(ArcNode));hu34=(ArcNode *)malloc(sizeof(ArcNode));hu35=(ArcNode *)malloc(sizeof(ArcNode));hu36=(ArcNode *)malloc(sizeof(ArcNode));hu37=(ArcNode *)malloc(sizeof(ArcNode));hu38=(ArcNode *)malloc(sizeof(ArcNode));hu39=(ArcNode *)malloc(sizeof(ArcNode));hu40=(ArcNode *)malloc(sizeof(ArcNode));hu41=(ArcNode *)malloc(sizeof(ArcNode));hu42=(ArcNode *)malloc(sizeof(ArcNode));hu43=(ArcNode *)malloc(sizeof(ArcNode));

hu44=(ArcNode *)malloc(sizeof(ArcNode));hu45=(ArcNode *)malloc(sizeof(ArcNode));hu46=(ArcNode *)malloc(sizeof(ArcNode));hu47=(ArcNode *)malloc(sizeof(ArcNode));hu48=(ArcNode *)malloc(sizeof(ArcNode));hu49=(ArcNode *)malloc(sizeof(ArcNode));hu50=(ArcNode *)malloc(sizeof(ArcNode));hu51=(ArcNode *)malloc(sizeof(ArcNode));hu52=(ArcNode *)malloc(sizeof(ArcNode));hu53=(ArcNode *)malloc(sizeof(ArcNode));hu54=(ArcNode *)malloc(sizeof(ArcNode));hu55=(ArcNode *)malloc(sizeof(ArcNode));hu56=(ArcNode *)malloc(sizeof(ArcNode));hu57=(ArcNode *)malloc(sizeof(ArcNode));hu58=(ArcNode *)malloc(sizeof(ArcNode));hu59=(ArcNode *)malloc(sizeof(ArcNode));hu60=(ArcNode *)malloc(sizeof(ArcNode));hu61=(ArcNode *)malloc(sizeof(ArcNode));hu62=(ArcNode *)malloc(sizeof(ArcNode));hu63=(ArcNode *)malloc(sizeof(ArcNode));hu64=(ArcNode *)malloc(sizeof(ArcNode));hu65=(ArcNode *)malloc(sizeof(ArcNode));hu66=(ArcNode *)malloc(sizeof(ArcNode));hu67=(ArcNode *)malloc(sizeof(ArcNode));hu68=(ArcNode *)malloc(sizeof(ArcNode));hu69=(ArcNode *)malloc(sizeof(ArcNode));hu70=(ArcNode *)malloc(sizeof(ArcNode));hu71=(ArcNode *)malloc(sizeof(ArcNode));hu72=(ArcNode *)malloc(sizeof(ArcNode));hu73=(ArcNode *)malloc(sizeof(ArcNode));hu74=(ArcNode *)malloc(sizeof(ArcNode));hu75=(ArcNode *)malloc(sizeof(ArcNode));hu76=(ArcNode *)malloc(sizeof(ArcNode));hu77=(ArcNode *)malloc(sizeof(ArcNode));hu78=(ArcNode *)malloc(sizeof(ArcNode));hu79=(ArcNode *)malloc(sizeof(ArcNode));hu80=(ArcNode *)malloc(sizeof(ArcNode));hu81=(ArcNode *)malloc(sizeof(ArcNode));hu82=(ArcNode *)malloc(sizeof(ArcNode));hu83=(ArcNode *)malloc(sizeof(ArcNode));hu84=(ArcNode *)malloc(sizeof(ArcNode));hu85=(ArcNode *)malloc(sizeof(ArcNode));hu86=(ArcNode *)malloc(sizeof(ArcNode));hu87=(ArcNode *)malloc(sizeof(ArcNode));

hu88=(ArcNode *)malloc(sizeof(ArcNode));hu89=(ArcNode *)malloc(sizeof(ArcNode));hu90=(ArcNode *)malloc(sizeof(ArcNode));hu91=(ArcNode *)malloc(sizeof(ArcNode));hu92=(ArcNode *)malloc(sizeof(ArcNode));hu93=(ArcNode *)malloc(sizeof(ArcNode));hu94=(ArcNode *)malloc(sizeof(ArcNode));hu95=(ArcNode *)malloc(sizeof(ArcNode));hu96=(ArcNode *)malloc(sizeof(ArcNode));hu97=(ArcNode *)malloc(sizeof(ArcNode));hu98=(ArcNode *)malloc(sizeof(ArcNode));hu99=(ArcNode *)malloc(sizeof(ArcNode));hu100=(ArcNode *)malloc(sizeof(ArcNode));hu101=(ArcNode *)malloc(sizeof(ArcNode));hu102=(ArcNode *)malloc(sizeof(ArcNode));hu103=(ArcNode *)malloc(sizeof(ArcNode));hu104=(ArcNode *)malloc(sizeof(ArcNode));hu105=(ArcNode *)malloc(sizeof(ArcNode));hu106=(ArcNode *)malloc(sizeof(ArcNode));hu107=(ArcNode *)malloc(sizeof(ArcNode));hu108=(ArcNode *)malloc(sizeof(ArcNode));hu109=(ArcNode *)malloc(sizeof(ArcNode));hu110=(ArcNode *)malloc(sizeof(ArcNode));hu111=(ArcNode *)malloc(sizeof(ArcNode));hu112=(ArcNode *)malloc(sizeof(ArcNode));hu113=(ArcNode *)malloc(sizeof(ArcNode));hu114=(ArcNode *)malloc(sizeof(ArcNode));hu115=(ArcNode *)malloc(sizeof(ArcNode));hu116=(ArcNode *)malloc(sizeof(ArcNode));hu117=(ArcNode *)malloc(sizeof(ArcNode));hu118=(ArcNode *)malloc(sizeof(ArcNode));hu119=(ArcNode *)malloc(sizeof(ArcNode));hu120=(ArcNode *)malloc(sizeof(ArcNode));hu121=(ArcNode *)malloc(sizeof(ArcNode));hu122=(ArcNode *)malloc(sizeof(ArcNode));hu123=(ArcNode *)malloc(sizeof(ArcNode));hu124=(ArcNode *)malloc(sizeof(ArcNode));hu125=(ArcNode *)malloc(sizeof(ArcNode));hu126=(ArcNode *)malloc(sizeof(ArcNode));hu127=(ArcNode *)malloc(sizeof(ArcNode));hu128=(ArcNode *)malloc(sizeof(ArcNode));hu129=(ArcNode *)malloc(sizeof(ArcNode));hu130=(ArcNode *)malloc(sizeof(ArcNode));hu131=(ArcNode *)malloc(sizeof(ArcNode));

hu132=(ArcNode *)malloc(sizeof(ArcNode));hu133=(ArcNode *)malloc(sizeof(ArcNode));hu134=(ArcNode *)malloc(sizeof(ArcNode));hu135=(ArcNode *)malloc(sizeof(ArcNode));hu136=(ArcNode *)malloc(sizeof(ArcNode));hu137=(ArcNode *)malloc(sizeof(ArcNode));hu138=(ArcNode *)malloc(sizeof(ArcNode));hu139=(ArcNode *)malloc(sizeof(ArcNode));hu140=(ArcNode *)malloc(sizeof(ArcNode));hu141=(ArcNode *)malloc(sizeof(ArcNode));hu142=(ArcNode *)malloc(sizeof(ArcNode));sheng[1].name=“heilongjiang”;hu1->x=2;hu2->x=4;sheng[1].firstnext=hu1;hu1->next=hu2;hu2->next=NULL;sheng[2].name=“jilin”;hu3->x=4;hu4->x=3;hu141->x=1;sheng[2].firstnext=hu3;hu3->next=hu4;hu4->next=hu141;hu141->next=NULL;sheng[3].name=“liaoning”;hu5->x=4;hu6->x=10;hu142->x=2;sheng[3].firstnext=hu5;hu5->next=hu6;hu6->next=hu142;hu142->next=NULL;sheng[4].name=“neimenggu”;hu7->x=1;hu8->x=2;hu9->x=3;hu10->x=10;hu11->x=9;hu12->x=8;hu13->x=7;hu14->x=6;hu15->x=5;sheng[4].firstnext=hu7;

hu7->next=hu8;hu8->next=hu9;hu9->next=hu10;hu10->next=hu11;hu11->next=hu12;hu12->next=hu13;hu13->next=hu14;hu14->next=hu15;hu15->next=NULL;sheng[5].name=“xinjiang”;hu16->x=6;hu17->x=13;hu18->x=16;sheng[5].firstnext=hu16;hu16->next=hu17;hu17->next=hu18;hu18->next=NULL;sheng[6].name=“gansu”;hu19->x=4;hu20->x=7;hu21->x=8;hu22->x=17;hu23->x=13;hu24->x=5;sheng[6].firstnext=hu19;hu19->next=hu20;hu20->next=hu21;hu21->next=hu22;hu22->next=hu23;hu23->next=hu24;hu24->next=NULL;sheng[7].name=“ningxia”;hu25->x=4;hu26->x=8;hu27->x=6;sheng[7].firstnext=hu25;hu25->next=hu26;hu26->next=hu27;hu27->next=NULL;sheng[8].name=“shanxi1”;hu28->x=4;hu29->x=9;hu30->x=14;hu31->x=19;

hu32->x=18;hu33->x=17;hu34->x=6;hu35->x=7;sheng[8].firstnext=hu28;hu28->next=hu29;hu29->next=hu30;hu30->next=hu31;hu31->next=hu32;hu32->next=hu33;hu33->next=hu34;hu34->next=hu35;hu35->next=NULL;sheng[9].name=“shanxi2”;hu36->x=4;hu37->x=10;hu38->x=14;hu39->x=8;sheng[9].firstnext=hu36;hu36->next=hu37;hu37->next=hu38;hu38->next=hu39;hu39->next=NULL;sheng[10].name=“hebei”;hu40->x=4;hu41->x=3;hu42->x=11;hu43->x=12;hu44->x=15;hu45->x=14;hu46->x=9;sheng[10].firstnext=hu40;hu40->next=hu41;hu41->next=hu42;hu42->next=hu43;hu43->next=hu44;hu44->next=hu45;hu45->next=hu46;hu46->next=NULL;sheng[11].name=“beijing”;hu47->x=10;sheng[11].firstnext=hu47;hu47->next=NULL;sheng[12].name=“tianjin”;

hu48->x=10;sheng[12].firstnext=hu48;hu48->next=NULL;sheng[13].name=“qinghai”;hu49->x=5;hu50->x=6;hu51->x=17;hu52->x=16;sheng[13].firstnext=hu49;hu49->next=hu50;hu50->next=hu51;hu51->next=hu52;hu52->next=NULL;sheng[14].name=“henan”;hu53->x=9;hu54->x=10;hu55->x=15;hu56->x=21;hu57->x=20;hu58->x=19;hu59->x=8;sheng[14].firstnext=hu53;hu53->next=hu54;hu54->next=hu55;hu55->next=hu56;hu56->next=hu57;hu57->next=hu58;hu58->next=hu59;hu59->next=NULL;sheng[15].name=“shandong”;hu60->x=10;hu61->x=14;hu62->x=21;sheng[15].firstnext=hu60;hu60->next=hu61;hu61->next=hu62;hu62->next=NULL;sheng[16].name=“xizang”;hu63->x=5;hu64->x=13;hu65->x=17;hu66->x=23;sheng[16].firstnext=hu63;hu63->next=hu64;

hu64->next=hu65;hu65->next=hu66;hu66->next=NULL;sheng[17].name=“sichuan”;hu67->x=13;hu68->x=6;hu69->x=8;hu70->x=18;hu71->x=24;hu72->x=23;hu73->x=16;sheng[17].firstnext=hu67;hu67->next=hu68;hu68->next=hu69;hu69->next=hu70;hu70->next=hu71;hu71->next=hu72;hu72->next=hu73;hu73->next=NULL;sheng[18].name=“chongqing”;hu74->x=17;hu75->x=8;hu76->x=19;hu77->x=25;hu78->x=24;sheng[18].firstnext=hu74;hu74->next=hu75;hu75->next=hu76;hu76->next=hu77;hu77->next=hu78;hu78->next=NULL;sheng[19].name=“hubei”;hu79->x=8;hu80->x=14;hu81->x=20;hu82->x=26;hu83->x=25;hu84->x=18;sheng[19].firstnext=hu79;hu79->next=hu80;hu80->next=hu81;hu81->next=hu82;hu82->next=hu83;hu83->next=hu84;

hu84->next=NULL;sheng[20].name=“anhui”;hu85->x=14;hu86->x=21;hu87->x=27;hu88->x=26;hu89->x=19;sheng[20].firstnext=hu85;hu85->next=hu86;hu86->next=hu87;hu87->next=hu88;hu88->next=hu89;hu89->next=NULL;sheng[21].name=“jiangsu”;hu90->x=15;hu91->x=14;hu92->x=20;hu93->x=27;hu94->x=22;sheng[21].firstnext=hu90;hu90->next=hu91;hu91->next=hu92;hu92->next=hu93;hu93->next=hu94;hu94->next=NULL;sheng[22].name=“shanghai”;hu95->x=21;hu96->x=27;sheng[22].firstnext=hu95;hu95->next=hu96;hu96->next=NULL;sheng[23].name=“yunnan”;hu97->x=16;hu98->x=17;hu99->x=24;hu100->x=29;sheng[23].firstnext=hu97;hu97->next=hu98;hu98->next=hu99;hu99->next=hu100;hu100->next=NULL;sheng[24].name=“guizhou”;hu101->x=17;hu102->x=24;

hu103->x=29;hu104->x=23;hu105->x=18;sheng[24].firstnext=hu101;hu101->next=hu102;hu102->next=hu103;hu103->next=hu104;hu104->next=hu105;hu105->next=NULL;sheng[25].name=“hunan”;hu106->x=18;hu107->x=19;hu108->x=26;hu109->x=30;hu110->x=29;hu111->x=24;sheng[25].firstnext=hu106;hu106->next=hu107;hu107->next=hu108;hu108->next=hu109;hu109->next=hu110;hu110->next=hu111;hu111->next=NULL;sheng[26].name=“jiangxi”;hu112->x=25;hu113->x=19;hu114->x=20;hu115->x=27;hu116->x=28;hu117->x=30;sheng[26].firstnext=hu112;hu112->next=hu113;hu113->next=hu114;hu114->next=hu115;hu115->next=hu116;hu116->next=hu117;hu117->next=NULL;sheng[27].name=“zhejiang”;hu118->x=22;hu119->x=21;hu120->x=20;hu121->x=26;hu122->x=28;sheng[27].firstnext=hu118;

hu118->next=hu119;hu119->next=hu120;hu120->next=hu121;hu121->next=hu122;hu122->next=NULL;sheng[28].name=“fujian”;hu123->x=27;hu124->x=26;hu125->x=30;sheng[28].firstnext=hu123;hu123->next=hu124;hu124->next=hu125;hu125->next=NULL;sheng[29].name=“guangxi”;hu126->x=23;hu127->x=24;hu128->x=25;hu129->x=30;sheng[29].firstnext=hu126;hu126->next=hu127;hu127->next=hu128;hu128->next=hu129;hu129->next=NULL;sheng[30].name=“guangdong”;hu130->x=29;hu131->x=25;hu132->x=26;hu133->x=28;hu134->x=31;hu135->x=32;hu136->x=34;sheng[30].firstnext=hu130;hu130->next=hu131;hu131->next=hu132;hu132->next=hu133;hu133->next=hu134;hu134->next=hu135;hu135->next=hu136;hu136->next=NULL;sheng[31].name=“aomen”;hu137->x=30;sheng[31].firstnext=hu137;hu137->next=NULL;sheng[32].name=“xianggang”;

hu138->x=30;sheng[32].firstnext=hu138;hu138->next=NULL;sheng[33].name=“taiwan”;hu139->x=28;sheng[33].firstnext=hu139;hu139->next=NULL;sheng[34].name=“hainan”;hu140->x=30;sheng[34].firstnext=hu140;hu140->next=NULL;for(i=1;i<=34;i++){

sheng[i].color=0;} for(i=1;i<=34;i++){

j=1;

p=sheng[i].firstnext;

while(p!=NULL)

{

while(p!=NULL&&j!=sheng[p->x].color)

{

p=p->next;

}

if(p!=NULL)

j++;

}

sheng[i].color=j;} for(i=1;i<=34;i++){

printf(“%s:”,sheng[i].name);

printf(“%dn”,sheng[i].color);}

printf(“/n0表示白色,1表示蓝色,2表示红色,3表示绿色,4表示黄色”);return 0;}

第二篇：数据结构课程设计舞伴问题

分类号编号

华北水利水电大学

North China Institute of Water Conservancy and Hydroelectric Power

课程设计

题目舞伴问题

院系信息工程学院专业计算机科学与技术

姓名贾宁

指导教师杨彬

第一章需求分析........................................................................................................................2

1.1问题描述......................................................................................................................2 1.2 基本要求.....................................................................................................................2

1.2.1 输入及输出格式..............................................................................................2 1.2.2 程序所完成的功能..........................................................................................2

第二章概要设计........................................................................................................................3

2.1 数据结构.....................................................................................................................3 2.2 程序模块.....................................................................................................................4 2.3 模块调用及算法.........................................................................................................5 第三章详细设计........................................................................................................................7

3.1 操作实现.............................................................................................................7 3.2 算法实现.............................................................................................................8

第四章编码调试......................................................................................................................10

4.1 调试环境...................................................................................................................10 4.2 调试方法...................................................................................................................10 4.3 调试项目及调试结果...............................................................................................10

4.3.1 登陆测试........................................................................................................10 4.3.2 加载学生信息................................................................................................11 4.3.3 学生配对调试................................................................................................12 4.3.4 显示总配对....................................................................................................13 4.3.5 查询配对........................................................................................................13

第五章总结..............................................................................................................................15 参考文献..................................................................................................................................16 附录系统源代码......................................................................................................................17

第一章需求分析

1.1问题描述

一班有m个女生、n个男生(m不等于n), 举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。

1.2 基本要求

1.2.1 输入及输出格式

输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。在读入男女生信息时，可以从文件中直接读取学生的姓名和性别信息。

输出显示时显示每首歌的配对情况，包括对应配对学生的姓名、性别以及编号。可以输出整个舞池配对过程的所有配对情况。将输出显示的内容对应写入到指定的文件中。

1.2.2 程序所完成的功能

从文件或者手动输入班级的学生信息，包括姓名和性别基本信息，根据性别使男女生分别坐在舞池两边的座位上，学生的座位编号顺序生成，且一旦编号确定，将不再发生变化。

每一首歌曲播放时，依次从男女生队列中出来学生进行配对，由于男女生人数不一致，会使某个队列中剩下若干学生配对不成功，配对不成功者等待下首歌时再进行配对。该首歌结束时，配对成功的学生再回到座位上。然后再依次进行配对，未成功者等待下首歌再进行配对。

配对成功时，会显示本首歌的详细配对情况，以及整个过程的配对情况，并且可以将配对情况写入到文件。

根据男女生的姓名或者某首歌曲的名字可以查询到对应的配对情况。

第二章概要设计

2.1 数据结构

学生座位队列： ADT StuQueue{ 数据对象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 数据关系：R={ ai∈D，i=1,2..n} voidInitQueue(StuQueue&Q)操作结果：初始化一个空的循环队列 voidEnQueue(StuQueue&Q,FinalStustu)初始条件：循环队列Q已经存在，并且无信息

操作结果：向Q中循环加入信息 void EnQueue2(StuQueue&Q,FinalStustu)初始条件：循环队列已存在，非首次进循环队列

操作结果：向Q中添加信息

FinalStuDeQueue(StuQueue&Q)初始条件：循环队列已存在

操作结果：使队列头的元素出队列，且返回FinalStu类型值 }ADT StuQueue //学生座位队列音乐队列： ADTMusicList{ 数据对象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 }

数据关系：R={ ai∈D，i=1,2..n} voidInitMusic(MusicList&MList)操作结果：创建循环链表

voidInsertMusic(MusicList&MList,char* name)初始条件：该链表已存在

操作结果：向链表中添加数据 }ADT MusicList；

临时队列： ADTTempQList{ 数据对象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 }

数据关系：R={ ai∈D，i=1,2..n} void InitQList(TempQList&TQL)操作结果：初始化临时队列

voidEnTempQueue(TempQList&TQL,FinalStustu)初始条件：队列TQL已存在操作结果：向TQL中添加信息 FinalStuDeTempQueue(TempQList&TQL)初始条件：队列TQL存在

操作结果：取出队列的对头元素，返回FinalStu类型 }ADT TempQList；

2.2 程序模块

本系统主要包括登陆模块、学生入座、自动配对、显示配对过程以及查询配对信息模块。

登陆：输入正确的用户名以及密码，方可进入系统，连续输入错误三次则禁止进入系统。

学生入座：以不同的方式获取学生信息后，根据学生性别依次进入两个循环队列，并为每个学生唯一编号。

自动配对：每首歌开始时，男女生依次从坐席中出来进行本首歌的配对，配对不成功者等待下首歌继续配对，下首歌时，上首歌未配对成功者本首歌先进行配对。

显示配对过程：在播放歌曲的过程中，显示播放的歌曲信息，以及本首歌的配对信息。

查询配对：根据男女生的姓名查出两人的在哪一首歌进行过配对，根据歌曲名称查询出本首歌的配对信息。

文件操作：将配对情况及学生的座位信息写入文件根据系统模块的划分，本系统的功能模块图如图2-1所示

舞池配对系统登陆学生入座自动配对显示配对过程查询配对结果

图 2-1 功能模块

2.3 模块调用及算法

登陆成功后进入主界面，进入主界面后，需要先运行学生入座模块，方能进行下边的操作。学生入座后会得到相关的基本信息。之后调用配对模块函数，进行学生的配对。学生配对成功后，才能利用显示配对过程进行显示配对的情况，后续的查询配对模块也必须在配对成功的基础上进行。模块间的调用流程如图2-2所示

主函数登陆函数入座模块配对模块显示配对查询结果图 2-2 模块调用在进行配对过程中用到算法，在每首歌配对时，依次从男女生队列中出来一个学生，进入到临时队列，从临时队列中获取配对的情况。在本首歌结束，下首歌开始之前，让临时队列中的男女在分别根据性别入队，依次循环，每次调用配对函数，实现学生的循环配对。

第三章详细设计

3.1 操作实现

本系统包含七个文件。设计分有欢迎界面，登陆系统，入队函数，配对函数，显示函数，查询函数等。登陆界面是整个系统的入口，其主要是让合法人员进入系统，入队函数主要让学生进入男女队列，配对函数主要是根据每首歌曲把男女生进行配对，显示函数主要是显示男女生的配对情况，查询函数主要是根据男女生姓名和歌曲名查找配对情况。

系统首先通过程序调用void main()进入欢迎界面和系统登陆界面，根据用户的帐号和密码登陆成功后进入主菜单。根据用户的选择可分别进入：1.学生就坐；2.每曲配对；3.显示结果；4.查询配对；5.退出。

选择“1.学生就坐”项，会显示学生信息来源，包括“1.按班级获取(推荐)”“2.手动输入...”两项可供选择。其中，1是从文件中获取学生信息，2是用户手动输入学生信息。

选择“2.每曲配对”项，会显示播放歌曲的类型，有“1.流行”“2.复古”两个音乐风格可供选择，当用户选择其中一个风格并确定播放后，会显示出当前播放的歌曲名字和所配对的男女生。

选择“3.显示结果”项，会有“1.学生座位信息”和“2.学生配对信息”两项操作可供选择。当选择1，会把学生就坐后的信息显示出来，选择2，会把每首歌学生的配对情况显示出来。

选择“4.查询配对”项，也有两个操作可供选择，分别是“1.按学生姓名”“按歌曲名”两项。选择1，会根据用户输入的男女生姓名查看他们的配对情况，选择2，会根据用户输入的歌曲名称显示每首歌曲学生的配对情况。

选择“5.退出”项，会出现感谢使用系统界面，并按任意键退出系统。本系统的主流程图如图3-1 所示

开始欢迎和登陆界面主界面1 ？NN2 ？N3 ？N4 ？N5 ？Y结束程序Y学生就坐Y每曲配对Y每曲配对显示Y查询配对情况

图 3-1 主流程

3.2 算法实现

定义学生结构体FinalStu，将学生的信息放到本结构体中，定义两个循环队列Boys和Girls队列，分别存储男女生的座位信息。定义MusicList循环链表，用于存放音乐信息。定义TempQueue队列，用于临时存放从男女生队列中出来的学生信息。创建一个存放每首歌配对情况的数组stuTable[]，用来存放播放该首歌曲时男女生的信息。

每一首歌开始时，男女生依次用Boys和Girls队列中出对，依次进入临时队列TempQueue，从TempQueue中读取男女生的信息，放到stuTable数组中，表示该首歌的 8 配对情况。下首歌开始时，让临时队列中的学生再根据性别依次进入男女循环队列。同时将存放歌曲的MusicList循环链表指针后移，播放下首歌曲，再执行上述操作，便可实现循环配对。

第四章编码调试

4.1 调试环境

硬件环境：Intel 1GHZ处理器（或AMD同类处理器），512M或以上内存容量，10G或以上硬盘容量,可连接互联网的相关设备。

软件环境（软件、操作系统）：Windows XP（或Windows 2003或Windows vista或Windows 7）操作系统，Microsoft Visual Studio 2008。

4.2 调试方法

为了提高测试效率，降低测试成本，本测试方案采用黑盒法设计基本的测试方案，再用白盒法补充一些方案。在黑盒法测试方案中，采用等价划分技术，把所有可能的数据划分成几个等价类。

4.3 调试项目及调试结果

4.3.1 登陆测试

用户根据用户名及密码登陆系统，内置用户为Admin，密码为888888。登陆成功如图4-1所示，登陆失败如图4-2所示

图 4-1 登陆成功

图 4-2 登陆失败

4.3.2 加载学生信息

可以从文件或者手动输入学生信息，从文件中选择时，可以选择不同的文件，其运行结果如图4-2 及图4-3 所示

图 4-3 选择信息来源

图 4-4 显示获取信息 4.3.3 学生配对调试

在进行配对之前，需要先将音乐信息加载到系统中，其加载过程如图4-5所示

图 4-5 加载音乐

学生就位及音乐加载成功后，开始播放音乐，并进行配对，其音乐播放情况及每首歌曲的配对情况如图4-

6、图4-7及图4-8所示

图 4-6 配对开始

图 4-7 播放下一首

图 4-8 循环配对

4.3.4 显示总配对

在整个过程结束后，停止播放音乐，可以显示整个过程的配对情况，其结果如图4-9所示

图 4-9 显示配对结果

4.3.5 查询配对

可以根据男女生的姓名查询两人的配对情况，当输入两个学生姓名时，显示在整个过程中的配对情况，其结果如图 4-10所示

图4-10 姓名查询配对

根据每一首歌曲情况查询在本首歌曲中的配对情况，其结果如图4-11 所示

图 4-11 按歌名查找

第五章总结

这次的课程设计懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的，在构思总体架构时，需要先将需求分析搞清楚，需要在找到了需要解决的问题后，再想办法解决该问题。而不是在设计过程中边想边解决，需要先将所有可能的问题都考虑到，再依次解决。在整个系统设计完成后，如果再遇到新的问题，可以对系统进行适当的更新。

调试时经常会遇到这样那样的错误，有的时候是因为一些最基本的错误，如标点的中英错误，括号的匹配问题，数据的输入错误等。当然，也有很多地方是因为用错了解决方法。在设计的过程中，最能体现出的缺点就是基础不扎实，本可以避免的错误却一再出现。

在实现舞池配对问题过程中，需要使学生循环配对，此程序设计的是当一个光盘的音乐播放结束时，整个配对过程随之结束，而没有让学生再次进去坐席，导致不再从新将学生入座，就无法实现配对。设计的是在每首歌开始之前学生进入队列，可以改为当某个学生坐席为空时，随即让学生再次进入队列，可以解决不能重复换歌曲的问题。

刚开始的时候我直接在开发环境下一边看题一边写代码，瞪了半天什么也没写出来，于是我便先开始在纸上画画写写，将事件的整个过程画下来，然后考虑怎么才能运用代码来实现，一边思考一边写一些粗略的代码，最后从上到下执行代码看看是不是符合题目要求。有没有什么漏洞。等这些完成以后，再在开发环境下将代码完善、编译和调试。虽然说代码还有许多要改进的地方，有的功能还不够完善，可毕竟是自己亲自写出来的，对于程序的条理有了一个清晰的了解，对编程也有了更加深刻的认识。

参考文献

[1] 谭浩强.C程序设计(第三版)[M].北京：清华大学出版社，2005.[2] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，1997.[3] 陆丽娜.软件工程.北京：经济科学出版社，2005.[4] 姚诗斌.数据库系统基础.计算机工程与应用,1981年第8期

附录系统源代码

#include #include #include #include #include #define MAXQSIZE 20 //循环队列最大存储量 #define STU_SIZE 5 //学生人数 #define SIZE 100

int idCount=1000;//全局变量控制学生id自增 int length;//记录每首歌配对的数量 int index=0;//记录最终配对表的下标 usingnamespace std;//舞池就坐后的学生信息结构体 struct Admin { char name[15];char passWord[15];Admin *next;};Admin *admin;struct FinalStu { char name[15];char sex[3];int id;};FinalStu stu[STU_SIZE];FinalStu stuSeat[STU_SIZE];//用来存放入座后的学生信息

FinalStu stuTable[STU_SIZE][2];//用来存放没收歌曲的配对情况 //舞池座位 struct StuQueue { FinalStu *base;int front;int rear;};StuQueue Boys;//男生队列 StuQueue Girls;//女生队列 //初始化学生坐席

void InitQueue(StuQueue &Q){ Q.base=(FinalStu*)malloc(MAXQSIZE*sizeof(FinalStu));if(Q.base==NULL)

return;Q.front=Q.rear=0;

} //学生就坐,首次入队，需要获取学生的id void EnQueue(StuQueue &Q,FinalStu stu){ int i=100;if((Q.rear+1)%MAXQSIZE==Q.front)

return;strcpy(Q.base[Q.rear].name,stu.name);strcpy(Q.base[Q.rear].sex,stu.sex);Q.base[Q.rear].id=idCount++;Q.rear=(Q.rear+1)%MAXQSIZE;} //非首次入队，不需获取学生的id void EnQueue2(StuQueue &Q,FinalStu stu){ strcpy(Q.base[Q.rear].name,stu.name);strcpy(Q.base[Q.rear].sex,stu.sex);Q.base[Q.rear].id=stu.id;Q.rear=(Q.rear+1)%MAXQSIZE;} //从坐席上出来

FinalStu DeQueue(StuQueue &Q){ FinalStu stu;if(Q.rear!=Q.front){

stu=Q.base[Q.front];} Q.front=(Q.front+1)%MAXQSIZE;return stu;} //存放音乐信息 struct Music { char M_Name[15];Music *next;};//存放音乐链,循环链表 struct MusicList { Music *head;

Music *tail;};MusicList ML;Music *M_p;//初始化指针

void InitMusic(MusicList & MList){ MList.head=MList.tail=(Music *)malloc(sizeof(Music));MList.head->next=NULL;} //向音乐链表中添加音乐

void InsertMusic(MusicList &MList,char* name){ Music *p=(Music*)malloc(sizeof(Music));MList.tail->next=p;strcpy(p->M_Name,name);MList.tail=p;MList.tail->next=MList.head;} //临时队列，用于存放从男女生队列中配对成成功的学生信息 struct TempQueue { FinalStu stu;TempQueue * next;};

struct TempQList { TempQueue *front;TempQueue *rear;};TempQList TempQL;//临时队列，用于存放每次出来的男女生信息 void

InitQList(TempQList &TQL){ TQL.front=TQL.rear=(TempQueue *)malloc(sizeof(TempQueue));TQL.front->next=NULL;}

void EnTempQueue(TempQList & TQL,FinalStu stu){ TempQueue *p=(TempQueue *)malloc(sizeof(TempQueue));p->stu=stu;p->next=NULL;TQL.rear->next=p;TQL.rear=p;}

FinalStu DeTempQueue(TempQList &TQL){ FinalStu stu;TempQueue *p;p=TQL.front->next;if(p==TQL.rear){

stu=p->stu;

TQL.rear=TQL.front;} else {

stu=p->stu;

TQL.front->next=p->next;} free(p);return stu;} //==========配对信息存放=================== struct MatchList { char musicName[20];FinalStu stu[2];};MatchList matchTable[SIZE];//从键盘读入学生信息 void GetInfKey(){ for(int i=0;i

cout<<“输入第”<

scanf(“%s”,stu[i].name);

cout<<“输入第”<

scanf(“%s”,stu[i].sex);} } //学生入座

void StudentSit(){ for(int i=0;i

if(strcmp(stu[i].sex,“男”)==0)

EnQueue(Boys,stu[i]);

else

EnQueue(Girls,stu[i]);} } //获取就坐后的男女生性别、姓名、编号,stuSeat[] 存放就坐后的学生信息，包括学生编号

void GetStuSeat(){ int i=0;

int j=0;i=Boys.front;j=Girls.front;

while(i!=Boys.rear){

stuSeat[i]=Boys.base[i];

i++;} while(j!=Girls.rear){

stuSeat[i]=Girls.base[j];

j++;

i++;} } //将就座的学生信息写入文件 int

InFileStuSeat(){ FILE *fp_Seat;int res=0;if((fp_Seat=fopen(“Seat.txt”,“wt”))==NULL){

cout<<“读取学生座位信息失败！！”;

return-1;} fprintf(fp_Seat,“姓名t性别t序号n”);for(int i=0;i

fprintf(fp_Seat,“%st%st%d”,stuSeat[i].name,stuSeat[i].sex,stuSeat[i].id);

fprintf(fp_Seat,“n”);

res++;} fclose(fp_Seat);return res;}

void PrintStuSeat(){ cout<<“ttt姓名t性别t序号”<

cout<<“ttt”<

cout<next=NULL;Admin *q=admin;FILE *fp_Admin;if((fp_Admin=fopen(“admin.txt”,“rt”))==NULL){

cout<<“打开文件失败！！”;

return;} while(!feof(fp_Admin)){

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

p->next=NULL;

fscanf(fp_Admin,“%s%s”,p->name,p->passWord);

q->next=p;

q=p;} fclose(fp_Admin);} //从文件获取学生信息 void ReadStuFile(int res){ FILE *fp;if(res==1){

if((fp=fopen(“student1.txt”,“rt”))==NULL)

{

cout<<“打开文件失败！！”<

return;

} } elseif(res==2){

if((fp=fopen(“student2.txt”,“rt”))==NULL)

{

cout<<“打开文件失败！！”<

return;

} } int i=0;while(!feof(fp))

{

fscanf(fp,“%s%s”,stu[i].name,stu[i].sex);

i++;

if(i>=STU_SIZE)

break;

} fclose(fp);} //加载音乐信息

int

LoadMusic(int cd){ char music[5][20];//存放从文件中获取的音乐名称

int res=0;FILE *fp_music;if(cd==1){

if((fp_music=fopen(“music1.txt”,“rt”))==NULL)

{

cout<<“打开音乐文件失败！！”<

return-1;

} } elseif(cd==2){

if((fp_music=fopen(“music2.txt”,“rt”))==NULL)

{

cout<<“打开音乐文件失败！！”<

return-1;

} } for(int j=0;j<5;j++){

if(fread(music[j],20*sizeof(char),1,fp_music)==1)

res++;

} fclose(fp_music);InitMusic(ML);for(int i=0;i<5;i++){

InsertMusic(ML,music[i]);} return res;} int InFileMatchTable(){ FILE *fp_MTable;if((fp_MTable=fopen(“matchtable.txt”,“wt”))==NULL){

cout<<“打开文件失败~~~~”<

return-1;} fprintf(fp_MTable,“歌曲名称t姓名t性别t序号t姓名t性别t序号n”);for(int i=0;i

fprintf(fp_MTable,“%stt%st%st%dt”,matchTable[i].musicName,matchTable[i].stu[0].name,matchTable[i].stu[0].sex,matchTable[i].stu[0].id);

fprintf(fp_MTable,“%st%st%dn”,matchTable[i].stu[1].name,matchTable[i].stu[1].sex,matchTable[i].stu[1].id);}

fclose(fp_MTable);return 1;} void StudentSitAgain(){ FinalStu stu;while(TempQL.front!=TempQL.rear){

stu=DeTempQueue(TempQL);

if(strcmp(stu.sex,“男”)==0)

EnQueue2(Boys,stu);

else

EnQueue2(Girls,stu);} } //播放歌曲

void PlayMusic(){ cout<<“tt正在播放:t”<M_Name;} //下一首

void NextMusic(){ M_p=M_p->next;if(M_p==ML.head){

M_p=ML.head->next;} } //学生配对 void Match(){ //FinalStu student[STU_SIZE];intstatic i=0;int j=0;length=0;while(Boys.front!=Boys.rear&&Girls.front!=Girls.rear){

EnTempQueue(TempQL,DeQueue(Boys));//从男生队列中出来进入临时队列

EnTempQueue(TempQL,DeQueue(Girls));//从女生队列中出来进入临时队列

length++;//记录每首歌的配对数

} //从临时队列中将信息赋值给表

TempQueue *tem=TempQL.front->next;while(tem){

strcpy(matchTable[index].musicName,M_p->M_Name);

strcpy(matchTable[index].stu[0].name,tem->stu.name);

strcpy(matchTable[index].stu[0].sex,tem->stu.sex);

matchTable[index].stu[0].id=tem->stu.id;

//----每曲歌的配对情况

strcpy(stuTable[j][0].name,tem->stu.name);

strcpy(stuTable[j][0].sex,tem->stu.sex);

stuTable[j][0].id=tem->stu.id;

tem=tem->next;

//------整个播放过程的配对表

strcpy(matchTable[index].stu[1].name,tem->stu.name);

strcpy(matchTable[index].stu[1].sex,tem->stu.sex);

matchTable[index].stu[1].id=tem->stu.id;

//----每首歌配对表

strcpy(stuTable[j][1].name,tem->stu.name);

strcpy(stuTable[j][1].sex,tem->stu.sex);

stuTable[j][1].id=tem->stu.id;

tem=tem->next;

index++;

j++;}

} //显示每首歌配对情况 void PrintEachMatch(){ cout<

//length为每首歌的配对长度

{

cout<

1、学生就坐”;cout<<“t”<<“

2、每曲配对”<

3、显示结果”;cout<<“t”<<“

4、查询配对”<

5、退出”;

} //配对显示

void PrintMatchTable(){ cout<<“歌曲名称t姓名t性别t序号t姓名t性别t序号”<

cout<

cout<>res;switch(res){ case 1:

//从文件读取数据

int res;

cout<<“请选择班级：”<

cout<<“1.三年一班t2.三年二班”<

cin>>res;

if(res==1)

{

ReadStuFile(1);

}

elseif(res==2)

{

ReadStuFile(2);

}

break;case 2:

cout<<“开始输入....”<

GetInfKey();

//键盘键入数据

break;default:

cout<<“输入有误，再见”<

break;} } void MusicMenu(){ cout<<“请选择要放入的光盘类型：”<>res;if(res==1)

i=LoadMusic(1);else

i=LoadMusic(2);if(i){

M_p=ML.head->next;//p指向第一首歌

cout<<“歌曲光盘已就位,是否现在播放(Y/N)”<

cin>>ch;

InitQList(TempQL);//初始化临时队列

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

{

system(“cls”);

PlayMusic();

Match();

PrintEachMatch();

}

cout<<“按n进行下一首歌曲、、n”;

cout<<“按q停止播放音乐、、”<

cin>>ch;

while(ch=='n'||ch=='N')

{

system(“cls”);

Next();

cout<<“按n进行下一首歌曲、、n”;

cout<<“按q停止播放音乐、、”<

cin>>ch;

}

if(ch=='q'||ch=='Q')

return;}

} void Welcome(){ cout<<“tttt欢迎进入进入舞池~~~~”<

Admin *p=admin->next;

cout<<“ttt请输入您的用户名：”;

cin>>userName;

cout<<“ttt请输入您的密码：”;

cin>>key;

while(p)

{

if(strcmp(p->name,userName)==0)

break;

p=p->next;

}

if(!p)

{

system(“cls”);

cout<<“ttt输入的用户名不存在~~~~~”<

continue;

}

if(p)

{

if(strcmp(p->passWord,key)==0)

{

system(“cls”);

cout<<“tttt欢迎回来.”;

Sleep(500);

system(“cls”);

cout<<“tttt欢迎回来..”;

Sleep(500);

system(“cls”);

cout<<“tttt欢迎回来...”;

Sleep(500);

//system(“cls”);

break;

}

else

{

system(“cls”);

cout<<“ttt输入的密码错误、、、”<

continue;

}

} } if(i>=3){

cout<<“ttt您今天的机会已经用完，再见”;

exit(0);} } void ShowMessage(){ system(“cls”);int res;cout<<“ttt选择要操作的信息:”<>res;if(res==1){

cout<<“ttt座位信息如下:”<

PrintStuSeat();

char ch;

cout<<“是否将该信息写入文件(Y/N):”;

cin>>ch;

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

{

if(InFileMatchTable())

{

cout<<“数据已写入文件...”<

}

} } elseif(res==2){

PrintMatchTable();

char ch;

cout<<“是否将该信息写入文件(Y/N):”;

cin>>ch;

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

{

if(InFileMatchTable())

cout<<“数据已写入文件...”<

}

Sleep(3000);}

} void Quit(){

system(“CLS”);

printf(“nnnnnnnnttt

^o^”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次使^”);

Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次使用”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次使用^o^”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次使用^o^nntttt

-----”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次使用^o^nntttt

-----GoodBye!”);Sleep(200);system(“CLS”);

printf(“nnnnnnnnttt

^o^欢迎下次使用^o^nntttt

-----GoodBye!n”);} void CheckByName()

//根据姓名查询配对情况 { char boyName[15];char girlName[15];cout<<“请输入男生姓名:”;cin>>boyName;cout<<“请输入女生姓名:”;cin>>girlName;int count=0;for(int i=0;i

if(strcmp(matchTable[i].stu[0].name,boyName)==0&& strcmp(matchTable[i].stu[1].name,girlName)==0)

{

count++;

} } if(count==0){

cout<<“未找到配对情况:”;} else {

cout<<“ttt查询的学生的配对情况如下:”<

cout<<“歌曲名称t姓名t性别t编号t姓名t性别t编号”<

for(int j=0;j

{

if(strcmp(matchTable[j].stu[0].name,boyName)==0&& strcmp(matchTable[j].stu[1].name,girlName)==0)

{

cout<

}

} } } void CheckByMusic(){ char MusicName[15];cout<<“请输入歌名:”;cin>>MusicName;int count=0;for(int i=0;i

if(strcmp(matchTable[i].musicName,MusicName)==0)

{

count++;

} } if(count==0){

cout<<“未找到该歌曲~~~~”;

} else {

cout<<“ttt查询的学生的配对情况如下:”<

cout<<“歌曲名称t姓名t性别t编号t姓名t性别t编号”<

for(int j=0;j

{

if(strcmp(matchTable[j].musicName,MusicName)==0)

{

cout<

}

} } } //主界面选项

void MainChoose(){

int ins;LoadAdmin();while(1){

system(“cls”);

MainMenu();

cout<

cin>>ins;

switch(ins)

{

case 1:

system(“cls”);

StudentChose();

InitQueue(Boys);

InitQueue(Girls);

StudentSit();

//学生分别入座

GetStuSeat();//获取学生座位信息

cout<<“ttt男女生已分别就位....”<

cout<<“ttt座位信息如下:”<

PrintStuSeat();

char ch;

cout<<“是否将该信息写入文件(Y/N):”;

cin>>ch;

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

{

if(InFileStuSeat())

cout<<“数据已写入文件...”<

}

Sleep(3000);

break;

case 2:

system(“cls”);

cout<<“tttt请先放入歌曲光盘...”<

MusicMenu();

break;

case 3:

ShowMessage();

break;

case 4:

system(“cls”);

cout<<“ttt请选择查询的方式:”<

cout<<“ttt1.按学生姓名t2.按歌曲名”<

int i;

cin>>i;

switch(i)

{

case 1:

CheckByName();

break;

case 2:

CheckByMusic();

break;

}

//CheckByMusic();

getch();

break;

case 5:

system(“color FC”);

Quit();

exit(0);

break;

} } } void main(){ MainChoose();}

第三篇：数据结构课程设计学生搭配问题

数据结构课程设计

报告

设计题目：

学生搭配问题

专业：计算机科学与技术学生姓名：班级学号：分组成员：指导教师：

学生搭配问题课程设计报告

一、设计时间

二、设计地点

三、设计目的

1.通过这次课程设计进一步熟悉基本概念； 2.熟练掌握C语言编程，了解程序基本的流程；

3.运用所学C语言知识，掌握数据结构方法循环队列应用，算法思路设计； 4.培养查阅资料，独立思考问题的能力。

四、设计小组成员

五、指导老师

六、设计课题

学生搭配问题

七、基本思路及关键问题的解决方法

基本思路：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。

循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。

（1）要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。

（2）将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。

（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。

（4）循环队列的长度分别设为男女生的个数即可。

（5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况

关键问题: 循环队列的应用

解决方法：数据模型（逻辑结构）: 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。

存储结构: 循环链表

核心算法: 循环队列的入队，出队，判队满，判队空。输入数据: 男生人数、女生人数，歌曲数量

输出数据: 每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。

八、算法及流程图

九、调试过程中出现的问题及解决方法

问题：在构造队列时，设队列分配的最大空间为男女生的个数，此时便无法根据Q.front=Q.rear来判别队列空间是“空”还是“满”,因此，在入队操作即插入一个新元素作为新的队尾元素时出现了问题，即最后一位同学无法入队。

解决方法：将队列分配的最大空间至少再增加一个

十、测试及运行结果

测试输入数据：男女生的个数曲子数和要查找的男女生编号

输出结果为：每首曲子男女生搭配的情况程序运行界面：

十一、课程设计心得体会

通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。

我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法

十二、源程序

#include #include #include #include #define MAXSIZE 60 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW-1 typedef int system;typedef struct QNode{ int num;struct QNode *next;}QNode,* QueuePtr;typedef struct{ QueuePtr front;QueuePtr rear;}LinkQueue;void sleep(clock_t wait)//延迟函数 { clock_t goal;goal = wait + clock();while(goal > clock());} void InitQ(LinkQueue &Q)//建立空队列 { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));Q.front=p;Q.rear=p;Q.front->next=NULL;} void EnQueue(LinkQueue &Q,int num){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));p->num=num;p->next=NULL;Q.rear->next=p;Q.rear=p;} void DeQueue(LinkQueue &Q, int &num){ QueuePtr p,q;if(Q.front==Q.rear)

printf(“队列为空”);p=Q.front->next;num=p->num;Q.front->next=p->next;q=p->next;if(Q.rear==q)

Q.rear=Q.front;free(p);} void printF(LinkQueue &F,int i)//打印第i首曲子时女队的情况 { QueuePtr p;int n=1;while(n

printf(“_ ”);

n++;} p=F.front->next;while(F.rear!=p){

printf(“%d ”,p->num);

p=p->next;} printf(“%d n”,p->num);} void printM(LinkQueue &M,int i)//打印第i首曲子时男队的情况 { QueuePtr p;int n=1;while(n

printf(“_ ”);

n++;} p=M.front->next;while(M.rear!=p){

printf(“%d ”,p->num);

p=p->next;} printf(“%d n”,p->num);} void main(){ int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F;//女生队

LinkQueue M;//男生队

printf(“请输入女生数量：”);scanf(“%d”,&m);printf(“请输入男生数量：”);scanf(“%d”,&n);printf(“请输曲子号：”);scanf(“%d”,&k);printf(“请输入要查找的男生编号：”);scanf(“%d”,&a);printf(“请输入要查找的女生编号：”);scanf(“%d”,&b);InitQ(F);InitQ(M);for(i=1;i<=m;i++){

EnQueue(F,i);} for(i=1;i<=n;i++){

EnQueue(M,i);} for(i=1;i<=k;i++){

system(“CLS”);

printf(“第%d首曲子 n”,i);

printF(F,i);

printM(M,i);

p=F.front->next;

q=M.front->next;

printf(“目前跳舞的是第%d号女生和第%d号男生n”,p->num,q->num);

if(p->num==a&&q->num==b)

{

count++;printf(“第%d曲是要查找的男女生跳舞n”,i);

}

sleep(3000);

DeQueue(F,num);EnQueue(F,num);

DeQueue(M,num);

EnQueue(M,num);} printf(“该对男女生共跳舞%d次n”,count);}

十三、参考文献

[1] 数据结构（C语言版）严蔚敏吴伟明编著，清华大学出版社 [2] C语言程序设计（第三版）谭浩强著，清华大学出版社

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

课程设计任务书

信息学院信息管理与信息系统专业 09级1班班孙鹏一、二、课程设计题目：迷宫求解、一元多项式

课程设计主要参考资料：数据结构（C语言版）严蔚敏、吴伟民编著

数据结构题集（C语言版）严蔚敏、吴伟民、米宁编著

数据结构课件

三、设计应解决下列各主要问题：

1.实现迷宫的路径求解，并输出最终路径，标记走过却未选择的路径和最终选择的路径

2.对一元多项式实现加法，减法，乘法，求导的计算，并按指数由大到小排序输出

四、课程设计相关附件（如：图纸、软件等）：

五、命题发出日期：2011-3-15 设计应完成日期： 2010-6-20

设计指导教师（签章）：

系主任（签章）：

指导教师对课程设计的评语

指导教师（签章）：

年月日

山东科技大学学生课程设计

课程设计1 迷宫问题

一、需求分析：

1.2.3.4.以二维数组Maze[][]表示迷宫

用户输入迷宫的数据：构建迷宫，行数m，列数n 迷宫的入口位置和出口位置可由用户随时设定

若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾经途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。

5.本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数做小量修改，便可求得全部路径。

二、概要设计：

抽象数据类型线性表的定义如下： ⒈ 设计栈的抽象数据类型定义：

ADT Stack { 数据对象：D={ai:|ai∈PositionSet,i=1„n,n≥0} 数据关系：R1={|ai-1,ai∈d,i=2,„n} 基本操作：的初始化S GetTop(S,&e)素

Push(&S,e)Pop(&S,e)

返回其值 }ADT Stack；

⒉ 迷宫的抽象数据类型定义： ADT Maze{ 数据对象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0}

数据关系：R={ROW.COL} Row={|ai-1,aij∈D i=1,„,m+2,j=1,„,n+2}

第1页

操作结果

构造一个空栈，完成栈用e返回栈S的栈顶元将新的元素e压入栈顶删除栈顶元素，并用eInitStack(&S)

山东科技大学学生课程设计

Col={|aijaij-1∈D}

基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始条件：已知目前迷宫状态, 传过起始位置，和终止位置操作结果：搜索迷宫，用sqstack s返回搜索所得路径。如不存在，返回2 }ADT MAZE

三、详细设计：

#include #include #include #define OVERFLOW-2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 100 //存储空间初始量 #define STACK_INCREMENT 10//存储空间初始增量

typedef int Status;

typedef struct { int r;int c;}PostType;//坐标位置

迷宫的r行c列 typedef struct { int ord;//通道块在路径上的序号

PostType seat;//通道块的当前坐标位置

int di;//通道块指向下一通道块的方向 }SElemType;//栈元素的类型 typedef struct { SElemType *base;//栈底指针

SElemType *top;//栈顶指针

int stacksize;//栈的最大容量 }Stack;//栈的类型

第2页山东科技大学学生课程设计

Status InitStack(Stack &S)//初始化栈 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)

exit(OVERFLOW);//存储分配失败;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//InitStack

Status StackEmpty(Stack S)//判断栈是否为空,如果为空返回TRUE,否则返回FALSE { if(S.top==S.base)

return TRUE;

return FALSE;}//StackEmpty

Status Push(Stack &S,SElemType e)//插入元素为e的栈顶元素 { if(S.top-S.base>=S.stacksize){

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));

if(!S.base)

exit(OVERFLOW);

S.top=S.base+S.stacksize;

S.stacksize+=STACK_INCREMENT;} *S.top++=e;return OK;}//Push

Status Pop(Stack &S,SElemType &e)//删除栈顶元素存入e { if(S.top==S.base)

return ERROR;e=*--S.top;

第3页山东科技大学学生课程设计

return OK;}//Pop

Status DestroyStack(Stack &S)//销毁栈 { free(S.base);S.top=S.base;return OK;}//DestroyStack

//maze.cpp #define MAXLEN 20//迷宫包括外墙最大行列数目 typedef struct{

int r;

int c;

char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType;

//迷宫类型

Status InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE

int m,n,i,j,k=1;

printf(“输入迷口的行数和列数: ”);

scanf(“%d%d”,&maze.r,&maze.c);//迷宫行和列数

for(i=0;i<=maze.c+1;i++){//迷宫行外墙

maze.adr[0][i]='#';

maze.adr[maze.r+1][i]='#';

}//for

for(i=0;i<=maze.r+1;i++){//迷宫列外墙

maze.adr[i][0]='#';

maze.adr[i][maze.c+1]='#';

}

for(i=1;i<=maze.r;i++)

for(j=1;j<=maze.c;j++)

maze.adr[i][j]=' ';//初始化迷宫

printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k);

scanf(“%d%d”,&m,&n);

k++;

while(m!=0)

{

if(m>maze.r || n>maze.c)//越界

第4页山东科技大学学生课程设计

exit(ERROR);

maze.adr[m][n]='#';//迷宫障碍用'#'标记

printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k);

scanf(“%d%d”,&m,&n);

k++;

}

return OK;}//InitMaze

Status Pass(MazeType maze,PostType curpos){ //当前位置可通则返回TURE,否则返回FALSE

if(maze.adr[curpos.r][curpos.c]==' ')//可通

return TRUE;

else

return FALSE;}//Pass

Status FootPrint(MazeType &maze,PostType curpos){ //若走过并且可通返回TRUE,否则返回FALSE //在返回之前销毁栈S

maze.adr[curpos.r][curpos.c]='*';//“*”表示可通

return OK;}//FootPrint

PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐标

PostType cpos;

cpos=curpos;

switch(i){

//1.2.3.4分别表示东,南,西,北方向

case 1 : cpos.c+=1;break;

case 2 : cpos.r+=1;break;

case 3 : cpos.c-=1;break;

case 4 : cpos.r-=1;break;

default: exit(ERROR);

}

return cpos;}//Nextpos

Status MarkPrint(MazeType &maze,PostType curpos){ //曾走过但不是通路标记并返回OK

第5页山东科技大学学生课程设计

maze.adr[curpos.r][curpos.c]='@';//“@”表示曾走过但不通

return OK;}//MarkPrint

void PrintMaze(MazeType &maze)//将最后标记好的迷宫输出 { int i,j;printf(“n输出迷宫的路径:n”);for(i=0;i<=maze.c+1;i++)

printf(“%4d”,i);//输出列数

printf(“n”);for(i=0;i<=maze.r+1;i++){

printf(“%d”,i);//输出行数

for(j=0;j<=maze.c+1;j++)

printf(“%4c”,maze.adr[i][j]);//输出迷宫

printf(“n”);} }//PrintMaze

Status MazePath(MazeType &maze,PostType start,PostType end)//若迷宫从入口start到end的通道则求得一条存放在栈中 { Stack S;//初始化栈

PostType curpos;int curstep;SElemType e;InitStack(S);curpos=start;curstep=1;do {

if(Pass(maze,curpos))//当前位置可通过而未曾走过留下足迹

{

FootPrint(maze,curpos);

e.ord=curstep;e.seat=curpos;e.di=1;

Push(S,e);//加入栈路径中

if(curpos.r==end.r && curpos.c==end.c)//到达出口返回TRUE

{

第6页山东科技大学学生课程设计

if(!DestroyStack(S))

exit(OVERFLOW);

else return TRUE;

}

else

{

curpos=NextPos(curpos,1);//下一位置是当前位置

curstep++;//探索下一步

}

}//if

else//当前位置不能通过

{

if(!StackEmpty(S))

{

Pop(S,e);//提取前一位置

while(e.di==4 &&!StackEmpty(S))//4个方向都不能通过则留下记号@ 提取前一个位置进行判断是否是能通过

{

MarkPrint(maze,e.seat);

Pop(S,e);

}

if(e.di<4)//换下一个方向探索

设定当前位置为该新方向上的邻位

{

e.di++;

Push(S,e);

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

}

}//if

} }while(!StackEmpty(S));if(!DestroyStack(S))

exit(ERROR);else return FALSE;}//MazePath

int main(){ MazeType maze;PostType start,end;char c;

第7页山东科技大学学生课程设计

do {

printf(“**********迷宫求解**********n”);

if(!InitMaze(maze))

{

printf(“n 初始化迷宫失败！!”);

exit(ERROR);

}

{

printf(“n请输入入口的坐标:”);

scanf(“%d%d”,&start.r,&start.c);//输入入口坐标

if(start.r>maze.r || start.c>maze.c)

printf(“n输入错误,请重新输入入口的坐标！n”);

continue;

}

while(start.r>maze.r || start.c>maze.c);

{

printf(“n请输入出口的坐标:”);//输入出口的坐标

scanf(“%d%d”,&end.r,&end.c);

if(end.r>maze.r || end.c>maze.c)

printf(“n输入错误,请重新输入出口坐标！n”);

continue;

}

while(end.r>maze.r || end.c>maze.c);

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

printf(“n不能找到一条路径！!n”);

else PrintMaze(maze);//输出迷宫

printf(“是否要继续?(y/n):”);

scanf(“%s”,&c);} while(c=='y' || c=='Y');}。测试结果：

第8页

四、山东科技大学学生课程设计

课程设计2 一元多项式

一、需求分析：

第9页山东科技大学学生课程设计

1.2.3.首先定义一个结构体，其中定义一元多项式中的两个参数:系数和指数和链表中结点的指针域；

然后一一罗列每个在主程序中用到的函数，并一一实现；最后在主程序中主要完成用户的输入和相关函数的调用。

二、概要设计：

void insert(PLOYList *head,PLOYList *input)

//查找位置插入新链节的函数，且让输入的多项式呈降序排列 PLOYList *creat(char ch)//输入多项式

PLOYList *add(PLOYList *head,PLOYList *pre)//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头

PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减

PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式相乘

PLOYList *der(PLOYList *head)//多项式求导

void print(PLOYList *fun)//输出多项式，fun指要输出的多项式链表的表头 void start()//用户选择界面

三、详细设计：

#include #include typedef struct node

//定义节点类型 { float coef;

//多项式的系数

int expn;

//多项式的指数

struct node * next;//结点指针域 }PLOYList;void insert(PLOYList *head,PLOYList *input)

//查找位置插入新链节的函数，且让输入的多项式呈降序排列 {

PLOYList *pre,*now;

int signal=0;

pre=head;

第10页山东科技大学学生课程设计

if(pre->next==NULL){pre->next=input;} //如果只有一个头结点，则把新结点直接连在后面

else {

now=pre->next;//如果不是只有一个头结点，则设置now指针

while(signal==0)

{

if(input->expn < now->expn)

{

if(now->next==NULL)

{

now->next=input;

signal=1;

}

else

{

pre=now;

now=pre->next;//始终让新输入的数的指数与最后一个结点中的数的指数比较，小于则插在其后面

}

else if(input->expn > now->expn)

{

input->next=now;

pre->next=input;

signal=1;

}//若新结点中指数比最后一个结点即now中的指数大，则插入now之前

else//若指数相等则需合并为一个结点，若相加后指数为0则释放该结点

{

now->coef=now->coef+input->coef;

signal=1;

free(input);

if(now->coef==0)

{

pre->next=now->next;

free(now);

}

}//else } //while

第11页山东科技大学学生课程设计

}//else }//void

PLOYList *creat(char ch)

//输入多项式 {

PLOYList *head,*input;

float x;

int y;

head=(PLOYList *)malloc(sizeof(PLOYList));

//创建链表头

head->next=NULL;

scanf(“%f %d”,&x,&y);//实现用户输入的第一个项，包括其指数和系数

while(x!=0)

{

input=(PLOYList *)malloc(sizeof(PLOYList));//创建新链节

input->coef=x;

input->expn=y;

input->next=NULL;

insert(head,input);//每输入一项就将其排序，是的链表中多项式呈降序排列

scanf(“%f %d”,&x,&y);

} return head;}

PLOYList *add(PLOYList *head,PLOYList *pre)

//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 {

PLOYList *input;

int flag=0;

while(flag==0)

{

if(pre->next==NULL)

flag=1;//若该链表为空，则无需进行加法运算，跳出循环

else

{

pre=pre->next;

input=(PLOYList *)malloc(sizeof(PLOYList));

第12页山东科技大学学生课程设计

input->coef=pre->coef;

input->expn=pre->expn;

input->next=NULL;

insert(head,input);// 把g(x)插入到f(x）中，相当于两者相加，结果保存于f(x)

}

} return head;}

PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减 {

PLOYList *input;

int flag=0;

while(flag==0)

{

if(pre->next==NULL)

flag=1;

else

{

pre=pre->next;

input=(PLOYList *)malloc(sizeof(PLOYList));

input->coef=0-pre->coef;//将第二个多项式里的数变为其相反数，再用和加法一样的方法实现减法

input->expn=pre->expn;

input->next=NULL;

insert(head,input);

}

} return head;}

PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式项乘 { PLOYList *hf,*pf,*qa,*qb;

qa = head-> next;

qb = pre-> next;//定义指针指向表头后一个元素，即链表中第一个元素

hf =(PLOYList *)malloc(sizeof(PLOYList));//新创建一个结点，当做表头

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

第13页山东科技大学学生课程设计

{

for(qb = pre-> next;qb;qb= qb-> next)//用两个循环，实现两个多项式之间每个项相乘，结果用insert函数进行排序与合并

{

pf =(PLOYList *)malloc(sizeof(PLOYList));

pf-> coef = qa-> coef * qb-> coef;//系数相乘

pf-> expn = qa-> expn + qb-> expn;//指数相加

pf-> next = NULL;

insert(hf,pf);

} } return hf;}

PLOYList *der(PLOYList *head)//多项式求导 { PLOYList *p;p = head-> next;while(p){

p-> coef = p-> coef * p-> expn;

p-> expn = p-> expn--;

p = p-> next;} return head;}//将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导

void print(PLOYList *fun)//输出多项式，fun指要输出的多项式链表的表头 {

PLOYList *printing;

int flag=0;

printing=fun->next;

if(fun->next==NULL)//若为空表，则无需输出

{

printf(“0n”);

return;

}

while(flag==0)

{

第14页山东科技大学学生课程设计

if(printing->coef>0&&fun->next!=printing)

printf(“+”);

if(printing->coef==1);

else if(printing->coef==-1)

printf(“-”);

else

printf(“%f”,printing->coef);

if(printing->expn!=0)printf(“x^%d”,printing->expn);

else if((printing->coef==1)||(printing->coef==-1))

printf(“1”);

if(printing->next==NULL)

flag=1;

else

printing=printing->next;

} printf(“n”);}

void start()//用户选择界面 { printf(“

#n”);

printf(“

用户选择界面

n”);

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

printf(“ *

*n”);

printf(“ *

1.两个一元多项式相加

*n”);

printf(“ *

2.两个一元多项式相减

*n”);

printf(“ *

3.两个一元多项式相乘

*n”);

printf(“ *

4.对一个一个一元多项式求导 *n”);

printf(“ *

0.退出系统

*n”);

printf(“ *

*n”);

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

printf(“

n”);

printf(“ 注释：输入多项式格式（可无序）：系数1 指数1 系数2 指数2 „„，并以0 0 结束：n”);

printf(“

n”);

printf(“ 请选择操作: ”);}

int main(){ PLOYList *f,*g,*pf,*hf,*p;

第15页山东科技大学学生课程设计

int sign=-1;

start();

while(sign!=0)

{

scanf(“%d”,&sign);

switch(sign)

{

case 0:

break;

case 1://多项式相加

{

printf(“ 你选择的操作是多项式相加:n”);

printf(“ 请输入第一个多项式f(x)：”);

f=creat('f');

printf(“ 第一个多项式为：f(x)=”);

print(f);

printf(“ 请输入第二个多项式g(x)：”);

g=creat('g');

printf(“ 第二个多项式为：g(x)=”);

print(g);

printf(“ 结果为：F(x)=f(x)+g(x)=”);

f=add(f,g);

print(f);

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.break;

}

case 2://多项式相减

{

printf(” 你选择的操作是多项式相减:n“);

printf(” 请输入第一个多项式f(x)：“);

f=creat('f');

printf(” 第一个多项式为：f(x)=“);

print(f);

printf(” 请输入第二个多项式g(x)：“);

g=creat('g');

printf(” 第二个多项式为：g(x)=“);

print(g);

printf(” 结果为：F(x)=f(x)-g(x)=“);

f=sub(f,g);

print(f);

”);第16页

山东科技大学学生课程设计

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.”);

break;

}

case 3://多项式相乘

{

printf(“ 你选择的操作是多项式相乘:n”);

printf(“ 请输入第一个多项式f(x)：”);

f=creat('f');

printf(“ 第一个多项式为：f(x)=”);

print(f);

printf(“ 请输入第二个多项式g(x)：”);

g=creat('g');

printf(“ 第二个多项式为：g(x)=”);

print(g);

printf(“ 结果为：F(x)=f(x)* g(x)=”);

pf=mul(f,g);

print(pf);

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.”);

break;

}

case 4://多项式求导

{

printf(“您选择的是对一个一元多项式求导：n”);

printf(“请输入一个一元多项式：”);

f = creat('f');

printf(“这个多项式为：f(x)= ”);

print(f);

printf(“求导结果为：F(x)=f'(x)= ”);

f=der(f);

print(f);

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.”);

break;

}

}//swith

}//while }//void

四、测试结果：

第17页山东科技大学学生课程设计

第18页

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

南京航空航天大学金城学院

《数据结构》课程设计报告

题目：一元多项式的加减乘法运算

班级： 20100232 学号： 2010023220 姓名：祁博成绩：

指导教师：叶延风

完成日期： 2012年 2月18 日

课程设计的主要内容需求分析

1.1课程设计题目

用线性表实现一元多项式的加法减法与乘法。

1.2课程设计的任务及要求

任务：利用所学线性表知识来完成计算器中一元多项式的加法减法与乘法的运算。要求：能自己创建线性表，能自主的进行线性表的有关插入删除操作，并且可以在此基础上实现线性表之间的加减乘除运算。

1.3课程设计思想

首先要定义一个结构体，其中定义一元多项式的两个参数，系数和指数和链表中的指针域，然后一一罗列每个在主程序中得到的函数，并一一实现，最后在主程序中主要完成用户的输入和相关程序的调用。

1.4软件开发的环境

VC++6.0。

 2.程序源代码

#include #include

typedef struct node{//定义节点类型

float coef;int expn;

struct node * next;}Ployn;

void menu()//用户选择界面

{

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

printf(“ 两个一元多项式的相加/相减，相乘:n”);

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

printf(“请选择操作:n”);

printf(“0.退出n”);

printf(“1.两个一元多项式相加n”);

printf(“2.两个一元多项式相乘n”);

printf(“3.两个一元多项式相减n”);

}

void insert(Ployn *head,Ployn *inpt)//查找位置插入新链节程序

{

Ployn *pre,*now;

int signal=0;

pre=head;//pre定义为现在的前一个链节

if(pre->next==NULL){pre->next=inpt;}

else {now=pre->next;while(signal==0){

if(inpt->expn>now->expn)//当新链节小于现在的连接时向后移一个链节

{

if(now->next==NULL)

{

now->next=inpt;

signal=1;

}

else

{

pre=now;

now=pre->next;

}

else if(inpt->expnexpn)//如果发现比现在的链节大了就插入到这个连接的前面

{

inpt->next=now;

pre->next=inpt;

signal=1;

}

else

{

now->coef=now->coef+inpt->coef;

signal=1;

free(inpt);//与当前链节相等指数

if(now->coef==0)

{

pre->next=now->next;

free(now);

}

} } } }

Ployn *creat(char ch)//输入多项式

{

Ployn *head,*inpt;

float x;

int y;

head=(Ployn *)malloc(sizeof(Ployn));//创建链表头

head->next=NULL;

printf(“请输入一元多项式%c:(格式是：系数指数；以0 0 结束！)n”,ch);

scanf(“%f %d”,&x,&y);

while(x!=0)

{

inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节

inpt->coef=x;

inpt->expn=y;

inpt->next=NULL;

insert(head,inpt);//不然就查找位置并且插入新链节

printf(“请输入一元多项式%c的下一项:(以0 0 结束！)n”,ch);

scanf(“%f %d”,&x,&y);

}

return head;}

Ployn *addPloyn(Ployn *head,Ployn *pre)//多项式相加

{

Ployn *inpt;

int flag=0;

while(flag==0)

{

if(pre->next==NULL)

flag=1;//当现在指向空时跳出循环

else

{

pre=pre->next;

inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节

inpt->coef=pre->coef;

inpt->expn=pre->expn;

inpt->next=NULL;

insert(head,inpt);

}//否则把当前“g(x)”的链节插入到“y(x)”中

}

return head;}

Ployn *minusPloyn(Ployn *head,Ployn *pre)//多项式相加

{

Ployn *inpt;

int flag=0;

while(flag==0)

{

if(pre->next==NULL)

flag=1;//当现在指向空时跳出循环

else

{

pre=pre->next;

inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节

inpt->coef=0-pre->coef;

inpt->expn=pre->expn;

inpt->next=NULL;

insert(head,inpt);

}//否则把当前“g(x)”的链节插入到“y(x)”中

}

return head;}

Ployn *byPloyn(Ployn *head1,Ployn *head2)//多项式相乘

{

Ployn *inpt,*res,*pre;

int flag=0;

res=(Ployn *)malloc(sizeof(Ployn));//创建链表头

res->next=NULL;

head1=head1->next;

pre=head2;

while(flag==0)

{

if(pre->next==NULL)

{

pre=head2;//当现在指向空时跳出循环

head1=head1->next;

continue;

}

if(head1==NULL)

{

flag=1;//当现在指向空时跳出循环

continue;

}

pre=pre->next;

inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节

inpt->coef=pre->coef*head1->coef;

inpt->expn=pre->expn+head1->expn;

inpt->next=NULL;

insert(res,inpt);//把当前“g(x)”的链节插入到“y(x)”中

}

return res;}

void print(Ployn *fun)//输出多项式

{

Ployn *printing;

int flag=0;

printing=fun->next;//正在被打印的链节

if(fun->next==NULL)//如果函数为空打印0

{

printf(“0n”);

return;}

while(flag==0)

{

if(printing->coef>0 && fun->next!=printing)

printf(“+”);//为正数且不为第一项时打印“+”号

if(printing->coef==1);//如果为“1”就不用打印系数了

else if(printing->coef==-1)

printf(“-”);//如果为“-1”就打印“-”号就行了

else

printf(“%f”,printing->coef);//其余情况都得打印

if(printing->expn!=0)//如果指数为“0”不打印指数项

{ if(printing->expn==1)printf(“x”);

else printf(“x^%d”,printing->expn);

}

else if((printing->coef==1)||(printing->coef==-1))

printf(“1”);

if(printing->next==NULL)

flag=1;//如果现在的链节没有下一个就结束

else

printing=printing->next;

}

printf(“n”);}

void main(){

Ployn *f,*g;

int sign=-1;//设置标志

menu();

while(sign!=0)

{

scanf(“%d”,&sign);

switch(sign){

case 0: break;//退出

case 1:

{

printf(“你选择的操作是多项式相加:n”);

f=creat('f');//输入多项式f(x)

printf(“f(x)=”);

print(f);

g=creat('g');//输入多项式g(x)

printf(“g(x)=”);

print(g);

printf(“F(x)=f(x)+g(x)=”);

f=addPloyn(f,g);//两个多项式相加

print(f);

sign=-1;//复位标志

menu();//回复用户选择界面

break;

}

case 2:

{

printf(“你选择的操作是多项式相乘:n”);

f=creat('f');//输入多项式f(x)

printf(“f(x)=”);

print(f);

g=creat('g');//输入多项式g(x)

printf(“g(x)=”);

print(g);

printf(“F(x)=f(x)*g(x)=”);

f=byPloyn(f,g);//两个多项式相加

print(f);

sign=-1;//复位标志

menu();//回复用户选择界面

break;

}

case 3:

{

printf(“你选择的操作是多项式相减:n”);

f=creat('f');//输入多项式f(x)

printf(“f(x)=”);

print(f);

g=creat('g');//输入多项式g(x)

printf(“g(x)=”);

print(g);

printf(“F(x)=f(x)-g(x)=”);

f=minusPloyn(f,g);//两个多项式相加

print(f);

sign=-1;//复位标志

menu();//回复用户选择界面

break;

}

default:

{

printf(“输入有误!请重新选择操作!n”);//选择错误,返回选择界面

menu();

break;

}

} }

 3.心得体会

每次做课设都有很大的收获。课设不仅是对课本知识的理论实践，更是对自我的一种挑战。

这次课设过程中，遇到很多的问题，让我有种无从下手的感觉，但是办法总比困难多，于是，在老师、同学的帮助下，以及自己在翻书、上网找资料的情况下，顺利解决问题。于是，我又上课的认识到，团队的重要性。

数据结构课程设计地图着色问题

第一篇：数据结构课程设计地图着色问题

第二篇：数据结构课程设计舞伴问题

第三篇：数据结构课程设计学生搭配问题

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

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

相关范文推荐