数据结构课程设计 猴子选大王 joseph环 飞机订票 文章编辑

课程设计课程名称数据结构题目名称数据结构课程设计专业班级计算机系班学生姓名田龙学号指导教师张艳二一一年十二月二十二日目录引言3一、课程设计目的与要求41课程设计的目的42课程设计的基本要求4二、猴子选大王51提出问题52概要设计53调试分析6二、JOSEPH环71提出问题72概要设计721算法设计722存储结构设计73调试分析8三、文章编辑91提出问题92概要设计93调试分析11四、飞机订票系统121提出问题122概要设计1221算法设计1221存储结构设计133调试分析14附录一猴子选大王源程序17附录二JOSEPH环源程序19附录三文章编辑源程序22附录四飞机订票系统源程序27引言课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。数据结构是一门实践性强的课程，其中对算法设计和程序编写的掌握尤其重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范，能够为今后从事计算机开发与应用打下基础。需要学生具有丰富科学知识、独立解决实际问题、有创造能力，这也是该课程设计的最终目的。通过本课程设计，使自己更加系统地理解和掌握数据结构的基本概念；能自如地根据实际要求，设计相应的数据结构，并运用C语言实现所设计的算法，编写较大型的程序，分析和解决实际应用问题，进一步加深、巩固所学专业课程的基本理论知识，理论联系实际，进一步培养自己综合分析问题和解决问题的能力。掌握C语言独立的编写、调试应用程序和进行其它相关设计的技能。此项目主要是考察我们对结构体、数组、文件等具体操作，以及对C语言语法的掌握，所以做成此项目要求比较高的设计要求，对整体有很熟悉的概括，同时调试过程也是很重要的，对程序界面的要求也比较高，要设计的合理同时也要美观一点，能够人性化的描述清楚你的各个功能，一目了然，对其他用户使用本程序简单易懂，这才能成本程序或本系统是成功的。这个设计能够练习我们的理解和运用结构化程序设计的思想和方法，掌握开发一个小型实用系统的基本方法，学会调试一个比较长的程序的基本方法，同时掌握书写程序设计开发文档的能力。一、课程设计目的与要求1课程设计的目的课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。数据结构是一门实践性强的课程，其中对算法设计和程序编写的掌握尤其重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范，能够为今后从事计算机开发与应用打下基础。需要学生具有丰富科学知识、独立解决实际问题、有创造能力，这也是该课程设计的最终目的。2课程设计的基本要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、设计的题目要求达到一定工作量，并具有一定的深度和难度。6、编写出课程设计说明书，说明书不少于15页（不包括代码）。二、猴子选大王1提出问题任务一堆猴子都有编号，编号是1，2，3M,这群猴子（M个）按照1M的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求输入数据输入M,NM,N为整数，NNEXTNULL；（非空表）（空表）单循环链表3调试分析二、JOSEPH环1提出问题任务编号是1，2，,N的N个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值M,从第一个人开始顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据M的初值为20，N7,7个人的密码依次为3，1，7，2，4，7，4，首先M6,则正确的输出是什么要求输入数据建立输入处理输入数据，输入M的初值，N，输入每个人的密码，建立单循环链表。输出形式建立一个输出函数，将正确的输出序列。2概要设计21算法设计利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“N个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个FOR语句实现。22存储结构设计密码和序号的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的。要让这M个人顺序围坐一圈，那就得用循环链表，只须将单循环链表的尾指针的NEXT域指向头指针。3调试分析三、文章编辑1提出问题任务输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；（4）输入数据的形式和范围可以输入大写、小写的英文字母、任何数字及标点符号。输出形式（1）分行输出用户输入的各行字符；（2）分4行输出“全部字母数“、“数字个数“、“空格个数“、“文章总字数“（3）输出删除某一字符串后的文章。2概要设计（1）定义结构体STRUCTLINE，文本行采用顺序存储，行与行之间采用链式存储。（2）主要函数INTFINDSTRINGLINELENSTRLENSILENSTRLENP即前I项恰好不含要删除的字符串，将前I项复制到TMP中JISTRLENSTR即要删除的字符串在I1和J之间，将J之后的字符串复制到TMP中将TMP赋给串S，返回S开始主函数输入文字统计个数查找某一子串输出文字统计字母、数字、空格、某一字符串的个数以及文章总字数删除这一子串输出删除后的文章具体操作3调试分析四、飞机订票系统1提出问题任务通过此系统可以实现如下功能录入可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；订票（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票可退票，退票后修改相关数据文件；客户资料有姓名，订票数量及航班情况，订单要有编号。修改航班信息当航班信息改变可以修改航班数据文件要求根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。2概要设计21算法设计每个模块的算法设计说明如下（1）录入模块查找单链表的链尾，在链尾插入一个“航班信息”的新结点。可以进行新增航班信息、删除航班信息等操作。（2）查询模块提供查方式顺着单链表查找，查找出所有航班的信息和订票信息。（3）订票模块查找乘客要订的航班号，判断此航班是否有空位，有则输入乘客有关信息，订票成功，否则失败。（4）退票模块输入要退票的乘客姓名，查找乘客资料的链表中是否有这位乘客，有则删去此结点，并在空位加上1，无则退票失败。21存储结构设计航班的信息为了便于查找和修改，航班的情况存储结构采用单链表，每个元素表示一个航班的情况，包括航班号、飞机编号、目的地、时间、总座位和空座六个数据项单链表如下每个结点包括数据域和指针域数据域指针域C语言描述如下TYPEDEFSTRUCTAIRLINE/飞机编号结构体/CHARAIR_NUM8/航班号/CHARPLANE_NUM8/飞机编号/CHAREND_PLACE20/目的地/CHARTIME_PLANE16/时间/INTTOTAL/总座位/INTLEFT/空座/STRUCTAIRLINENEXT/指向下个结点/AIRLINE旅客的资料为了便于插入、删除和修改，其采用单链表存储结构，每个数据元素包括姓名、航班号和座位号四个数据项旅客姓名航班号座位号每个结点包括数据域和指针域数据域指针域C语言描述如下TYPEDEFSTRUCTCUSTOMER/乘客编号结构体/CHARNAME8CHARAIR_NUM8INTSEAT_NUMSTRUCTCUSTOMERNEXTCUSTOMER航班号飞机编号目的地时间总座位空座HD1D2D33调试分析附录一猴子选大王源程序源程序INCLUDE“STDIOH“INCLUDE“PROCESSH“INCLUDE“MALLOCH“DEFINETURE1DEFINEFALSE0DEFINEOK1DEFINEERROR0DEFINEINFEASIBLE1DEFINEOVERFLOW2DEFINELIST_INIT_SIZE100DEFINELISTINCREMENT10TYPEDEFINTSTATUSTYPEDEFINTELEMTYPETYPEDEFSTRUCTLNODEELEMTYPEDATASTRUCTLNODENEXTLNODE,LINKLIST/创建循环链表VOIDCREATELIST_LLINKLISTSTRUCTLNODEP,QLLINKLISTMALLOCSIZEOFLNODELNEXTNULLLDATA1QLFORI2IDATAIQNEXTPPNEXTLQQNEXT/链表删除操作STATUSLISTDELETE_LLINKLISTLNODEP,QPLJ1WHILEJNEXTJQPNEXTPNEXTQNEXTEQDATAFREEQLPNEXTRETURNOKVOIDMAINPRINTF“NN“PRINTF“班级N“PRINTF“姓名田龙N“PRINTF“学号N“PRINTF“NN“PRINTF“N“PRINTF“猴子选大王N“PRINTF“N“PRINTF“NN“LINKLISTLINTM,N,IELEMTYPEEPRINTF“N请输入猴子的个数“SCANF“D“,CREATELIST_LL,MPRINTF“所有猴子的编号为N“FORI0IDATALLNEXTPRINTF“N“PRINTF“N请输入猴子要数的数“SCANF“D“,PRINTF“N猴子依次离开的序号N“FORI1IDATA附录二JOSEPH环源程序源程序INCLUDE“STDIOH“INCLUDE“PROCESSH“INCLUDE“MALLOCH“DEFINETRUE1DEFINEFALSE0DEFINEOK1DEFINEERROR0DEFINEINFEASIBLE1DEFINEOVERFLOW2TYPEDEFINTSTATUSINCLUDE“DEFINEHEADERH“TYPEDEFSTRUCTINTNAMEINTSNOELEMTYPETYPEDEFSTRUCTLNODEELEMTYPEDATASTRUCTLNODENEXTLNODE,LINKLIST/逆位序输入N个人的密码，建立带表头结点的单链表LVOIDCREATELIST_LLINKLISTLINKLISTPLLINKLISTMALLOCSIZEOFLNODELNEXTNULLFORINI0IPLINKLISTMALLOCSIZEOFLNODEPDATANAMEISCANF“D“,PNEXTLNEXTLNEXTP/查找元素值STATUSGETELEM_LLINKLISTL,INTI,ELEMTYPEINTJPLNEXTJ1WHILEPJIFP|JIRETURNERROREPDATARETURNOK/在带头结点的单链表L中第I个位置之前插入元素ESTATUSLISTINSERT_LLINKLISTINTJ0PLWHILEPJ/寻找第I1个结点IFP|JI1RETURNERRORSLINKLISTMALLOCSIZEOFLNODESDATAESNEXTPNEXTPNEXTSRETURNOK/在带头结点的单链表L中删除第I个元素，并用E返回其值STATUSLISTDELETE_LLINKLISTINTJ0PLWHILEPNEXTJIFPNEXT|JI1RETURNERRORQPNEXTPNEXTQNEXTEQDATAFREEQRETURNOKVOIDOUTPUTLINKLIST/从第一个人开始顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值IFCUNMN0CUNNLISTDELETE_LL,CUN,EKNCUNMESNOPRINTF“4DD|“,ENAME,ESNO/从上一个报M的人在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。FORIN1I0IIFCUN1MI0CUN1IIFCUN1INCLUDEINCLUDE/文本每行以字符串形式存储，行与行之间以链表存储/TYPEDEFSTRUCTLINECHARDATASTRUCTLINENEXTLINE/创建一链表，同时向里面输入文本数据/VOIDCREATELINELINEPNEWLINE/首先为链表建立一个附加表头结点/HEADP/将P付给表头指针/CHARTMP100WHILE1GETSTMP/输入字符串/IFSTRLENTMP80PRINTF“每行最多输入80字符“BREAKIFTMP05BREAK/如果发现输入E，则退出输入/PPNEXTNEWLINEPDATANEWCHARSTRLENTMP1/为结点分配空间/STRCPYPDATA,TMPIFTMPSTRLENTMP15/除去最后一个控制符E/PDATASTRLENTMP10BREAKPNEXTNULL/最后的一个指针为空/HEADHEADNEXT/统计字母数/INTCOUNTLETTERLINEINTCOUNT0DOINTLENSTRLENPDATA/计算当前DATA里的数据元素的个数/FORINTI0IDATAIA/遍历链表/RETURNCOUNT/返回文章的字母总数/统计数字数/INTCOUNTNUMBERLINEINTCOUNT0DOINTLENSTRLENPDATA/计算当前DATA里的数据元素的个数/FORINTI0IDATAI48/遍历链表/RETURNCOUNT/统计空格数/INTCOUNTSPACELINEINTCOUNT0DOINTLENSTRLENPDATA/计算当前DATA里的数据元素的个数/FORINTI0IDATAI32COUNT/计算空格数，空格ASCII码为32/WHILEPPNEXTNULL/遍历链表/RETURNCOUNT/统计文章的总字数/INTCOUNTALLLINE/保存链表的首地址/INTCOUNT0DO/计算总字符数/COUNTSTRLENPDATAWHILEPPNEXTNULL/遍历链表/RETURNCOUNT/统计STR在文章中出现的次数/INTFINDSTRINGLINEINTCOUNT0INTH0INTLEN10/保存当前行的总字符数/INTLEN2STRLENSTR/待统计字符串的长度/INTI,J,KDOLEN1STRLENPDATA/当前行的字符数/FORI0IDATAISTR0K0FORJ0JDATAIJSTRJKIFKLEN2COUNTIIK1WHILEPPNEXTNULL/遍历链表/RETURNCOUNT/删除指定的字符串/VOIDDELSTRINGWORDCHARS,CHARSTR/S为输入的字符串，STR为将要删除的字符/CHARPSTRSTRS,STR/从字符串S中寻找STR第一次出现的位置/CHARTMP80INTLENSTRLENSINTILENSTRLENPINTJISTRLENSTRINTCOUNT0FORINTM0MDATA,STRNULLDELSTRINGWORDPDATA,STRWHILEPPNEXTNULL/遍历链表/向屏幕输出文章/VOIDOUTPUTLINEDOPRINTF“SN“,PDATAWHILEPPNEXTNULL/遍历链表/VOIDMAINLINEHEADPRINTF“NN“PRINTF“班级N“PRINTF“姓名田龙N“PRINTF“学号“PRINTF“NN“PRINTF“N“PRINTF“文章编辑N“PRINTF“N“CREATEHEADPRINTF“输入的文章为N“OUTPUTHEADPRINTF“N“PRINTF“全部字母数DN“,COUNTLETTERHEADPRINTF“数字个数DN“,COUNTNUMBERHEADPRINTF“空格个数DN“,COUNTSPACEHEADPRINTF“文章总字数DN“,COUNTALLHEADCHARSTR120,STR220PRINTF“N“PRINTF“请输入要统计的字符串“SCANF“S“,STR1PRINTF“S出现的次数为DN“,STR1,FINDSTRINGHEAD,STR1PRINTF“N“PRINTF“请输入要删除的某一字符串“SCANF“S“,STR2DELSTRINGHEAD,STR2PRINTF“删除S后的文章为N“,STR2OUTPUTHEAD附录四飞机订票系统源程序源程序INCLUDEINCLUDEINCLUDEDEFINEOK1DEFINEERROR0TYPEDEFSTRUCTAIRLINE/飞机编号结构体/CHARAIR_NUM8CHARPLANE_NUM8CHAREND_PLACE20CHARTIME_PLANE16INTTOTALINTLEFTSTRUCTAIRLINENEXTAIRLINETYPEDEFSTRUCTCUSTOMER/乘客编号结构体/CHARNAME8CHARAIR_NUM8INTSEAT_NUMSTRUCTCUSTOMERNEXTCUSTOMERAIRLINESTART_AIRAIRLINEAAAIRLINEMALLOCSIZEOFAIRLINEIFANULLANEXTNULLRETURNACUSTOMERSTART_CUSCUSTOMERCCCUSTOMERMALLOCSIZEOFCUSTOMERIFCNULLCNEXTNULLRETURNCAIRLINEMODEFY_AIRLINEAIRLINEL,CHARAIR_NUMAIRLINEPPLNEXTFORPNULLPPNEXTIFSTRCMPAIR_NUM,PAIR_NUM0PLEFTRETURNLPRINTF“对不起，没有该航班“RETURN0/增加飞机信息INTINSERT_AIRAIRLINEP,CHARAIR_NUM,CHARPLANE_NUM,CHAREND_PLACE,CHARTIME_PLANE,INTTOTAL,INTLEFTAIRLINEQQAIRLINEMALLOCSIZEOFAIRLINESTRCPYQAIR_NUM,AIR_NUMSTRCPYQPLANE_NUM,PLANE_NUMSTRCPYQEND_PLACE,END_PLACESTRCPYQTIME_PLANE,TIME_PLANEQTOTALTOTALQLEFTLEFTQNEXTNULLPNEXTQPPNEXT/PRINTF“添加航线成功“RETURNOK/添加航线AIRLINEADD_AIRAIRLINEP,CHARAIR_NUM,CHARPLANE_NUM,CHAREND_PLACE,CHARTIME_PLANE,INTTOTAL,INTLEFTAIRLINEQ,PTPTPQAIRLINEMALLOCSIZEOFAIRLINESTRCPYQAIR_NUM,AIR_NUMSTRCPYQPLANE_NUM,PLANE_NUMSTRCPYQEND_PLACE,END_PLACESTRCPYQTIME_PLANE,TIME_PLANEQTOTALTOTALQLEFTLEFTFORPPNEXTNULLPPNEXTQNEXTPNEXTPNEXTQRETURNPT/增加客户INTINSERT_CUSCUSTOMERP,CHARNAME,CHARAIR_NUM,INTSEAT_NUMCUSTOMERQQCUSTOMERMALLOCSIZEOFCUSTOMERSTRCPYQNAME,NAMESTRCPYQAIR_NUM,AIR_NUMQSEAT_NUMSEAT_NUMQNEXTNULLPNEXTQPPNEXTRETURNOKPRINTF“添加客户成功“/订票INTBOOKAIRLINEA,CHARAIR_NUM,CUSTOMERC,CHARNAMEAIRLINEPCUSTOMERQCNEXTFORQQNEXTNULLQQNEXTPANEXTFORPNULLPPNEXTIFSTRCMPAIR_NUM,PAIR_NUM0IFPLEFT0PRINTF“您的座位号是D“,PTOTALPLEFT1INSERT_CUSPLEFTRETURNOKELSEIFPLEFT0PRINTF“对不起，座位已满“RETURN0PRINTF“对不起，没有该航班“RETURN1/退票INTDEL_CUSCUSTOMERC,AIRLINEL,CHARNAMECUSTOMERP,PRCHARAIR_NUM8PRCPPRNEXTWHILEPNULLIFSTRCMPPNAME,NAME0STRCPYAIR_NUM,PAIR_NUMLMODEFY_AIRLINEL,AIR_NUMPRNEXTPNEXTPPRNEXTPRINTF“S退票成功“,NAMERETURNOKPRPRNEXTPPRNEXTPRINTF“对不起，没有该顾客“RETURNERROR/删除航线INTDEL_AIRLINEAIRLINEL,CUSTOMERM,CHARAIR_NAIRLINEPT,PTRCUSTOMERP,PRPTRLPRMPPRNEXTPTPTRNEXTWHILEPTNULLIFSTRCMPPTAIR_NUM,AIR_N0PTRNEXTPTNEXTWHILEPNULLIFSTRCMPPAIR_NUM,PTAIR_NUM0PRNEXTPNEXTPRINTF“乘坐该航班的顾客S已删除N“,PNAMEPPRNEXTPRPRNEXTPRINTF“删除该航班成功“RETURNOKPTRPTRNEXTPTPTRNEXTPRINTF“对不起，没有该航班“RETURNERROR/查询航线INTSEARCH_AIRAIRLINEHEADAIRLINEPHEADNEXTPRINTF“N“PRINTF“航班号飞机编号目的地时间总座位空座N“FORPNULLPPNEXTPRINTF“5ST8ST7ST5STDTDN“,PAIR_NUM,PPLANE_NUM,PEND_PLACE,PTIME_PLANE,PTOTAL,PLEFTPRINTF“N“RET