数据结构与算法课程设计.doc

摘要数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构。因此，仅掌握几种计算机语言是难以应付众多复杂的课题，想要有效地使用计算机，还必须学习数据结构的有关知识。在计算机发展初期，人们使用计算机主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型,实型或布尔型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无需重视数据结构。随着计算机应用领域的扩大和软，硬件的发展，“非数值性问题”越来越显得重要。据统计，当今处理非数值性问题占用了90%以上的机器时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决此类问题的关键已不再是分析数学和计算方法，而是能设计出合适的数据结构，才能有效地解决问题。著名的瑞士计算机科学家沃思教授曾提出：算法+数据结构=程序。这里的数据结构是指数据的逻辑结构和储存结构，而算法则是对数据运算的描述。由此可见，程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构关键字：数据结构、算法分析、树、图、存储结构、线性表目录一、 运动会分数统计51、 需求分析52、 概要设计53、 详细设计104、 调试分析16二、 一元多项式计算171、 需求分析172、 概要设计173、 详细设计184、 调试分析23三、 订票系统281、 需求分析282、 概要设计283、 详细设计334、 调试分析39四、 迷宫求解401、需求分析402、概要设计403、详细设计414、调试分析47五、 文章编辑481、 需求分析482、 概要设计483、 详细设计514、 调试分析55六、 joseph环571、需求分析572、概要设计573、详细设计574、调试分析59七、 猴子选大王601、 需求分析602、 概要设计603、 详细设计654、 调试分析69八、 建立二叉树，后序、先序遍历701、 需求分析702、 概要设计703、 详细设计704、 调试分析72九、 哈夫曼树的建立731、 需求分析732、 概要设计733、 详细设计744、 调试分析78十、 纸牌游戏791、 需求分析792、 概要设计793、 详细设计804、 调试分析80十一、 图的建立及输出811、 需求分析812、 概要设计813、 详细设计824、 调试分析84课程总结85课程设计过程中的课程设计进展情况86参考文献87一、 运动会分数统计1、需求分析：任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20） (1)、可以输入各个项目的前三名或前五名的成绩；（2)、能统计各学校总分；(3)、可以按学校编号、学校总分、男女团体总分排序输出；(4)、可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整型界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明.2、概要设计 本程序中学校的存储结构为链表，prev school1 next头结点prev school（最后） next其中school类为：class school:public athlete /*学校*/ public: int count; /*学校获奖数*/ int serial; /*学校编号*/ int menscore; /*男选手总分*/ int womenscore; /*女选手总分*/ int totalscore; /*总分*/ athlete athmaxsize; /*获奖运动员信息数组，包括分数，名次，项目*/ school *prev;/前指针 school *next; /后指针;其中部分主要的函数：添加操作add(school* &head)查询操作checkfunc(school *head,int &n)文件保存save(school *head)总分快速排序tquicksort(vector& v, int first, int last)总分基数排序 tbasesort(vector& v, int d) 关键算法 添加项目号for ( i = 1 ; i serial =要添加的编号) (first-athfirst-count).item =要添加的项目号;(first-athfirst-count).range =i（名次） first指向的学校的项目加一;更新总分break;first = first-next;开始输入项目编号temp是数字ny0temp18ny输出“项目不存在”学校遍历结束temp存在ynnext schoolntemp是奇数 ny取5名取3名输入获奖的学校编号se1senext;输出向量中的内容1. 所有学校总分统计表2. 学校成绩查询3. 项目情况查询4. 返回主菜单1. 按学校编号统计2. 按学校名次统计3. 按男团总分统计4. 按女团总分统计5. 返回查询菜单6. 返回主菜单/按学校编号顺序输出所有参赛学校运动会成绩void serialsort(vector& v)for(int i=0;iv.size();i+)cout*vi;3、详细设计#include #include #include #include #define null 0 #define maxsize 30 typedef struct athletestruct /*运动员*/ char name20; int score; /*分数*/ int range; /*/ int item; /*项目*/ ath; typedef struct schoolstruct /*学校*/ int count; /*编号*/ int serial; /*/ int menscore; /*男选手分数*/ int womenscore; /*女选手分数*/ int totalscore; /*总分*/ ath athletemaxsize; /*/ struct schoolstruct *next; sch; int nsc,msp,wsp; int ntsp; int i,j; int overgame; int serial,range; int n; sch *head,*pfirst,*psecond; int *phead=null,*pafirst=null,*pasecond=null; create() pfirst = (struct schoolstruct *)malloc(sizeof(struct schoolstruct); pfirst-next = head-next ; head-next = pfirst ; pfirst-count = 1; pfirst-menscore = 0; pfirst-womenscore = 0; pfirst-totalscore = 0; input () char answer; head = (sch *)malloc(sizeof(sch); /*/ head-next = null; pfirst = head; answer = y; while ( answer = y ) is_game_domain:printf(nget top 5 when oddnget top 3 when even); printf(n输入运动项目序号 (x=%d):,ntsp); scanf(%d,pafirst); overgame = *pafirst; if ( pafirst != phead ) for ( pasecond = phead ; pasecond ntsp ) printf(n项目不存在); printf(n请重新输入); goto is_game_domain; switch ( overgame%2 ) case 0: n = 3;break; case 1: n = 5;break; for ( i = 1 ; i = n ; i+ ) is_serial_domain: printf(n输入序号 of the no.%d (0x nsc ) printf(n超过学校数目,请重新输入); goto is_serial_domain; if ( head-next = null ) create(); psecond = head-next ; while ( psecond != null ) if ( psecond-serial = serial ) pfirst = psecond; pfirst-count = pfirst-count + 1; goto store_data; else psecond = psecond-next; create(); store_data: pfirst-athletepfirst-count.item = overgame; pfirst-athletepfirst-count.range = i; pfirst-serial = serial; (input name:) : ); scanf(%s,); printf(n继续输入运动项目(y&n)？); answer = getch(); printf(n); calculate() /*/ pfirst = head-next; while ( pfirst-next != null ) for (i=1;icount;i+) if ( pfirst-athletei.item % 2 = 0 ) switch (pfirst-athletei.range) case 1:pfirst-athletei.score = 5;break; case 2:pfirst-athletei.score = 3;break; case 3:pfirst-athletei.score = 2;break; else switch (pfirst-athletei.range) case 1:pfirst-athletei.score = 7;break; case 2:pfirst-athletei.score = 5;break; case 3:pfirst-athletei.score = 3;break; case 4:pfirst-athletei.score = 2;break; case 5:pfirst-athletei.score = 1;break; if ( pfirst-athletei.item menscore = pfirst-menscore + pfirst-athletei.score; else pfirst-womenscore = pfirst-womenscore + pfirst-athletei.score; pfirst-totalscore = pfirst-menscore + pfirst-womenscore; pfirst = pfirst-next; output() pfirst = head-next; psecond = head-next; while ( pfirst-next != null ) /clrscr(); printf(n第%d号学校的结果成绩:,pfirst-serial); printf(nn项目的数目t学校的名字t分数); for (i=1;i=ntsp;i+) for (j=1;jcount;j+) if ( pfirst-athletej.item = i ) printf(n %dtttttt%sn %d,i,,pfirst-athletej.score);break; printf(nnntttttt按任意建 进入下一页); getch(); pfirst = pfirst-next; /clrscr(); printf(n运动会结果:nn学校编号t男运动员成绩t女运动员成绩t总分); pfirst = head-next; while ( pfirst-next != null ) printf(n %dtt %dtt %dtt %d,pfirst-serial,pfirst-menscore,pfirst-womenscore,pfirst-totalscore); pfirst = pfirst-next; printf(nnnttttttt按任意建结束); getch(); /create()void save() file *fp; if(fp = fopen(school.dat,wb)=null) printf(cant open school.datn); fclose(fp); return; fwrite(pfirst,sizeof(sch),10,fp); fclose(fp); printf(文件已经成功保存n); main() system(cls); printf(nttt 运动会分数统计n); printf(输入学校数目 (x= 5):); scanf(%d,&nsc); printf(输入男选手的项目(x=20):); scanf(%d,&msp); printf(输入女选手项目(=20):); scanf(%d,&wsp); ntsp = msp + wsp; phead = calloc(ntsp,sizeof(int); pafirst = phead; pasecond = phead; input(); calculate(); output(); save(); 4、调试分析时间复杂度分析：o()二、 一元多项式计算1、需求分析能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法.课程设计的目的 （1）掌握算法的编写方法。 （2）掌握类c语言的算法转换成c程序并上机调试的基本方法。 （3）设计一个c语言程序，该程序具有能够按照指数降序排列建立并输出多项式， 完成两个多项式的相加、相减，并将结果输入的功能。2、概要设计 问题描述 用c语言编写一段程序，该程序的功能相当于一个一元多项式计算器。它能够实现按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减的运算和将其结果输入的功能。 数据结构设计 此程序的数据结构是选择用带表头结点的单链表存储多项式。虽然一元多项式可以用顺序和链式两种存储结构表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费了巨大的存储空间，所以应该选择用链式存储结构来存储一元多项式。单链表的结构体可以用来存储多项式的系数，指数，下一个指针3个元属，这样便于实现任意多项式的加法，减法运算。功能模块图思路设计 （1）一元多项式的建立 输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。 （2）显示一元多项式 如果系数是大于0的话就输出+系数x指数的形式；如果系数是小于0的话就输出系数x指数的形式；如果指数为0的话，直接输出系数；如果系数是1的话就直接输出+x；如果系数是-1的话就直接输出-x。 （3）一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二多项式用新节点产生。 （4）一元多项式减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。 p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。抽象数据类型的定义typedef struct lnode float coef; int expn; lnode* next;term, *link;typedef struct link head,tail; int len;polynomial,* lpoly;3、详细设计#include #include #include typedef struct polynode int coef; /多项式的系数 int exp; /指数 struct polynode *next; node; node *create() /用尾插法建立一元多项式的链表 node *h,*r,*s; int c,e; h=(node*)malloc(sizeof(node); r=h; printf(coef:); scanf(%d,&c); printf(exp: ); scanf(%d,&e); while(c!=0) /输入系数为0时，多项式的输入结束 s=(node*)malloc(sizeof(node); s-coef=c; s-exp=e; r-next=s; r=s; printf(coef:); scanf(%d,&c); printf(exp: ); scanf(%d,&e); r-next=null; return(h); void print(node *p) /输出函数，打印出一元多项式 while(p-next!=null) p=p-next; printf( %d*x%d,p-coef,p-exp); void polyadd(node *ha, node *hb)/一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式ha中，并将多项式hb删除 node *p,*q,*pre,*temp; int sum; p=ha-next; q=hb-next; pre=ha; while(p!=null&q!=null) if(p-expexp) pre-next=p; pre=pre-next; p=p-next; else if(p-exp=q-exp) sum=p-coef+q-coef; if(sum!=0) p-coef=sum; pre-next=p;pre=pre-next;p=p-next; temp=q;q=q-next;free(temp); else /如果系数和为零，则删除结点p与q，并将指针指向下一个结点 temp=p-next;free(p);p=temp; temp=q-next;free(q);q=temp; else pre-next=q; pre=pre-next; q=q-next; if(p!=null) /将多项式a中剩余的结点加入到和多项式中 pre-next=p; else pre-next=q; void minus(node *ha,node *hb) node *p,*q,*n,*m; int sum1; p=ha-next; q=hb-next; n=hb; while(p!=null&q!=null) if(p-expexp) n-next=p; n=n-next; p=p-next; else if(p-exp=q-exp) sum1=p-coef-q-coef; if(sum1!=0) p-coef=sum1; n-next=p;n=n-next;p=p-next; m=q;q=q-next;free(m); else /如果系数和为零，则删除结点p与q，并将指针指向下一个结点 m=p-next;free(p);p=m; m=q-next;free(q);q=m; else n-next=q; n=n-next; q=q-next; if(p!=null) /将多项式a中剩余的结点加入到和多项式中 n-next=p; else n-next=q; void main() node *ha,*hb; printf(请输入多项式ha的系数与指数:n); ha=create(); print(ha); printf(n); printf(请输入多项式hb的系数与指数:n); hb=create(); print(hb); printf(n); printf(多项式的和是:n);polyadd(ha,hb); print(ha); printf(n);printf(请输入多项式ha的系数与指数:n); ha=create(); print(ha); printf(n); printf(请输入多项式hb的系数与指数:n); hb=create(); print(hb); printf(n); printf(多项式的差是:n);minus(ha,hb); print(hb); printf(n); 4、调试分析 这次课程设计是通过用我们所学过的带有头结点的单链表的数据结构为基础建立一元多式。再进一步设计一个一元多项式简单计算器。该计算器能够按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减，并将结果输出。 通过这次课程设计，我了解c语言这门课的重要性，我们一定要学好c语言。c语言功能强,使用灵活, 可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件,而且c语言语法限制不严格,程序设计自由度大。所以我们要学会正确的使用c语言编程. 而数据结构学的怎么样直接影响到我们对其它专业课的学习和今后业务的成长。我觉得我们对于数据结构的学习不 仅包括理论部分的学习，还要让我们勤动手，多实践。通过了这次课程设计使我得到了充分的锻炼，并使自己得到了较大的提高。在编程过程中善于发现程序中的错误，并且能很快地排除这些错误，使程序能正确运行。经验丰富的人，当编译时出现“出错信息”时，能很快地判断出错误所在，并改正之。而缺乏经验的人即使在明确的出错提示下也往往找不出错误而求救于别人。调试程序的经验固然可以借鉴他人的现成经验，但更重要的是通过自己的直接实践来累积，而且有些经验是只能“会意”难以“言传”。因此，在实验时千万不要在程序通过后就认为万事大吉、完成任务了，而应当在已通过的程序基础上作一些改动(例如修改一些参数、增加程序一些功能、改变输入数据的方法等)，再进行编译、连接和运行。(1)调试过程中遇到的问题及其解决方法a.问题:库函数 malloc 调用错误 解决方法:函数 malloc 的声明 void * malloc (unsigned size ) 可以强制类型转换,前面为指针类型,后面为所分配的内存空间的大小 用于申请一段新的地址,参数 size 为需要内存空间的长度 b.问题:函数的指针类型的形式参数重复定义 解决方法:在函数定义的形式参数列表中, 指针类型的形式参数定义注意事项: 采用值传递,内存空间已经自动分配完毕; 采用引用传递,内存空间需要自动分配;c.问题:在 for 循环语句中,循环变量使用控制错误 解决方法: 在 for 循环语句中,应该意识到循环变量的执行次数总是比循环体的执行次数多一次，即最后一次的循环体执行完毕之后,循环变量又执行了一次,但是循环体却没有再执行了；d.问题: c+ 中编译出错信息: cannot open debug/*.exe for writing 解决方法: 第一次编译运行后，没有关掉那个程序，所以更改后再次编译就提示不能写入;那么打开任务管理器看看那个进程在不在，可能关了窗口，但程序还没有结束;记得编译前关闭程序，或者到任务管理器的看看进程是否存在，有的话结束掉；e.问题: av(access violation) 错误解决方法: 访问不再有效的内存,大多数的情况下,出现这个错误要么是因为你试图访问一块已经被释放的内存,要么是想使用一个还未创建对象的指针。f.问题: c+ 中编译出错信息: left operand must be l-value 解决方法: l-value应该是个left-value，也就是左值，只有变量和看作指针的内存空间可以被看作是左值 (2)经验与体会a.在线性链表中进行遍历操作的两种常用控制手段:a. 利用该线性链表的长度 l.lengthb. 利用该线性链表的尾指针 nullb.在书写程序时,应该注意 return 语句在程序中的位置,因为在顺序结构中一旦使用到了 return 语句,return 语句后面的所有程序代码都无法再执行.c.在对线性链表的操作中, 如果是加工型操作,则需要在形参列表中用引用传递的方式返回该线性链表 l; 如果是引用型操作,则不需要在形参列表中用引用传递的方式返回该线性链表 l;d.在程序调试过程中,如果发现许多地方犯了同一类错误,则应该一次性将这一类错误全部调试好,这样可以提高程序调试的效率e.返回链表类型的数据元素应该是链表结点,而不是该链表结点中的数据域 data三、 订票系统1、需求分析任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；（a）需求分析：在该部分中叙述，每个模块的功能要求订票系统功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）。这个要采取存储的方法来完成，所以在此用所学的存储结构来进行存储。2、概要设计查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；这个也是要用到所学的存储结构来完成，但这还要用到结构体数组与查找的方法来进行配用，并将它们联系与处理好。订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；这也是先要用到存储结构与栈等，进而用到查找的方法来进行选择，联系好它们。退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件这是用到存储文件、存储结构、进栈出栈、查找及删除等。在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。a.抽象类型定义如下 struct flaight char flanum10; /* 航班号 */ char ftime10; /* 起飞时间 */ char ltime10; /* 降落时间?*/ char fcity30; /* 起飞城市 */ char lcity30; /* 降落城市 */ int fprice; /* 票价 */ char priof10; /* 折扣 */ int seat; /* 座位数 */ struct flaight *next;struct custom /* 客户资料 */ char cname30; /* 客户姓名 */ char id30; /* 证件号 */ int ticketn; /* 订票数量 */ char flan10; /* 航班号 */ char listn60; /* 订单编号 */ struct custom *next;struct flaight *head1=null;struct custom *head2=null;b本程序包含三个模块（1）主程序模块：void main()do接受命令；处理命令；while(命令！=退出)；（2）信息输入模块完成基本信息的输入（3）实现功能模块实