数据结构课程设计 毕业设计

数据结构课程设计姓名杨本芊学号119074059专业计算机科学与技术112指导老师秦峰大数相乘1问题描述输入第一个数为13286754398172586，输入第二个数为2397567453241147则程序运行后输出132867543981725862397567453241147的正确答案。2设计思路将两个大数存放在单链表中，利用乘法原理将第一个大数和第二个大数每一位进行相乘并存放在单链表中。然后按照错位相加，将结果放进单链表。打印链表。3数据结构设计大数相乘利用了单链表的存储，所以具体的数据结构定义如下TYPEDEFSTRUCTNODECHARDATASTRUCTNODENEXTLNODE,LINKLIST4功能函数设计1创建存储大数的单链表函数CREAT_LINKLISTCHARS此函数的形参是字符串，从键盘中读取字符串。通过该函数将大数存入单链表中。2错位相加函数CUO_WEI_XIANG_JIALINKLISTP,LINKLISTQ此函数用来将两个单链表中的值进行错位相加并存储在单链表中，返回。3大数相乘函数DA_SHU_XIANG_CHENGCHARS1,CHARS2此函数用来第一个大数和第二个大数每一位进行相乘后的结果分别的用单链表存储起来，并调用错位相加函数CUO_WEI_XIANG_JIALINKLISTP,LINKLISTQ将最后的结果输出。注意此函数需要S1比S2的长度大。4转置函数RESERVELINKLISTH此函数将单链表中的所有元素转置过来并输出。5主函数MAIN用来实现两大数相乘后的结果。注意判断S1和S2的长度5程序代码INCLUDEINCLUDEINCLUDEDEFINEMAX500TYPEDEFSTRUCTNODECHARDATASTRUCTNODENEXTLNODE,LINKLIST/销毁链表/VOIDDESTROY_LINKLISTLINKLISTHLINKLISTP,QPHWHILEPQPPPNEXTFREEQHNULL/链表的长度/INTLENGTH_LINKLISTLINKLISTHLINKLISTPHNEXTINTCOUNT0WHILEPCOUNTPPNEXTRETURNCOUNT/按序号查找元素/LINKLISTLOCATE_LINKLIST_POSLINKLISTH,INTILINKLISTPINTJPHJ0WHILEPJIFJI|PPRINTF“参数I错或单链表不存在“RETURNNULLRETURNP/删除指定序号的元素（结点）/INTDEL_LINKLISTLINKLISTH,INTILINKLISTP,QIFHNULL|HNEXTNULLPRINTF“链表不存在或空表不能删除“RETURN0PLOCATE_LINKLIST_POSH,I1IFPNULL|PNEXTNULLPRINTF“参数I错“RETURN0QPNEXTPNEXTQNEXTFREEQRETURN1LINKLISTCREAT_LINKLISTCHARSLINKLISTP,Q,PREINTIPLINKLISTMALLOCSIZEOFLNODEPNEXTNULL/带头结点的单链表/PREPFORISTRLENS1I0IQLINKLISTMALLOCSIZEOFLNODEQNEXTNULLQDATASIPRENEXTQPREQRETURNP/错位想加/LINKLISTCUO_WEI_XIANG_JIALINKLISTP,LINKLISTQINTA,B,C,D,E,F,GLINKLISTR,S,PRE,T,HRPNEXTSQNEXTALENGTH_LINKLISTPBLENGTH_LINKLISTQCDEFG0IFAB1WHILESNULLRRNEXTCRDATA48DSDATA48ECDGFE10GE/10RDATAF48SSNEXTIFG0TLINKLISTMALLOCSIZEOFLNODETNEXTNULLTDATAGRNEXTTRETURNPELSEPRERRRNEXTWHILERNULLCRDATA48DSDATA48ECDGFE10GE/10RDATAF48SSNEXTPRERRRNEXTHSNEXTWHILEG0|HNULLDSDATA48EDGFE10GE/10SDATAF48PRENEXTSPRESSSNEXTHSIFG0TLINKLISTMALLOCSIZEOFLNODETNEXTNULLTDATAGSDATAPRENEXTTPRETPRENEXTNULLRETURNPVOIDPRINT_LINKLISTLINKLISTHLINKLISTPPHNEXTWHILEPPRINTF“C“,PDATAPPNEXTPRINTF“N“/规定S2的长度比S1不大/LINKLISTDA_SHU_XIANG_CHENGCHARS1,CHARS2LINKLISTH1,Q1,PRE1,H2,Q2,PRE2INTI,J,A,EINTF,GINTB,C,DASTRLENS2ESTRLENS1LINKLISTRALINKLISTSA,PAH1CREAT_LINKLISTS1H2CREAT_LINKLISTS2PRE2H2FORI0INEXTNULLPIRIPRE1H1Q1PRE1NEXTQ2PRE2NEXTWHILEQ1NULLSILINKLISTMALLOCSIZEOFLNODESINEXTNULLFQ1DATA48GQ2DATA48BFGDCB10DB/10SIDATAC48PINEXTSIPISIQ1Q1NEXTIFD0SILINKLISTMALLOCSIZEOFLNODESIDATAD48PINEXTSIPISIPINEXTNULL/用来处理第二个数和第一个数最高位相乘后还存在进位的情况/PRE2Q2DESTROY_LINKLISTDESTROY_LINKLISTFORIA2I0IRICUO_WEI_XIANG_JIARI,RI1RETURNR0LINKLISTRESERVELINKLISTHLINKLISTP,Q,H,RHLINKLISTMALLOCSIZEOFLNODEHNEXTNULLPHNEXTRLINKLISTMALLOCSIZEOFLNODERNEXTNULLRDATAPDATAHNEXTRQHNEXTPPNEXTWHILEPRLINKLISTMALLOCSIZEOFLNODERNEXTNULLRDATAPDATARNEXTQHNEXTRQRPPNEXTRETURNHINTMAINCHARS1MAX,S2MAXLINKLISTP,Q,HPRINTF“请输入第一个数N“SCANF“S“,S1GETCHARPRINTF“请输入第二个数N“SCANF“S“,S2IFSTRLENS1STRLENS2PDA_SHU_XIANG_CHENGS1,S2PRINTF“两数之积为N“HRESERVEPPRINT_LINKLISTHELSEPDA_SHU_XIANG_CHENGS2,S1PRINTF“两数之积为N“HRESERVEPPRINT_LINKLISTHRETURN06运行与测试运行结果7设计心得设计过程中遇到了遇到了许多错误，比如没有给变量分配内存问题，还有回车字符的问题，因为都是老师上课时提到过的问题，所以解决起来也挺方便的。设计为了能够减少空间复杂度可以将长度较小的数作为第二个乘数。设计过程中遇到错误进行调试。跟着电脑一步一步来，看问题出在哪，并给予纠正二迷宫问题1问题描述心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。2设计思路该程序的设计思路用到了回溯法，从入口出发按某一方向向前探索，若能走通且未走过，即某处可以到达，则到达新的点，否则探视下一个方向；若所有的方向均没有通路，则沿原路返回前一个点，换一个方向继续探测。直到找到一条通路，或无路可走又返回到入口处。求解过程中，为了确保在到达某一点不能向前继续行走时能正确返回前一个点以便继续从下一个方向向前探测，则需要用一个栈保存所能够到达的每一个点的下标及从该点前进的方向。3数据结构设计1表示迷宫的数据结构设迷宫有M行N列，利用MAZEM2N2来表示一个迷宫，MAZEIJ0或1表示通路或不通。迷宫的四周值全是1，这样就可以确保迷宫中每个点独有四个方向。入口坐标（1,1），出口坐标（6,8）迷宫定义如下DEFINEM6DEFINEN8INTMAZEM2N22试探方向迷宫上的一个点从它的正东方向开始沿顺时针方向进行的四个方向的增量放在一个结构数组中MOVE4,该数组有两个域,X为横坐标增量，Y为纵坐标增量。MOVE定义如下TYPEDEFSTRUCTINTX,YITEMITEMMOVE43栈的设计到达某点后无路可走时还需要返回到前一个点，并从前一个点的下一个方向开始继续寻找。所以压入栈中的元素应该是一个由行，列，方向组成，栈设计如下TYPEDEFSTRUCTINTX,Y,DDATATYPETYPEDEFSTRUCTDATATYPEDATAMAXSIZEINTTOPSEQSTACK,PSEQSTACK4对于所有已经访问过的节点的值赋值为1，以避免发生死循环。4功能函数设计1走迷宫函数MAZEPATHINTMAZEN2,ITEMMOVE,INTX0,INTY0,INTP,INTQ此函数用来计算怎样从入口到出口的路线。当返回值是0时表示走不通，返回为1时可以走通，并且打印出路线。X0，Y0表示的是入口的横纵坐标。P,Q分别表示出口的横纵坐标而且走过的路会被用另一种数字所代替，知道走过的路线。2主函数MAIN用来创建迷宫，确定入口和出口。实现走迷宫函数5程序代码INCLUDEINCLUDEDEFINEMAXSIZE100INCLUDEDEFINEM6DEFINEN8TYPEDEFSTRUCTINTX,YITEMTYPEDEFSTRUCTINTX,Y,DDATATYPETYPEDEFSTRUCTDATATYPEDATAMAXSIZEINTTOPSEQSTACK,PSEQSTACKPSEQSTACKINIT_SEQSTACKPSEQSTACKSSPSEQSTACKMALLOCSIZEOFSEQSTACKIFSSTOP1RETURNSINTEMPTY_SEQSTACKPSEQSTACKSIFSTOP1RETURN1ELSERETURN0INTPUSH_SEQSTACKPSEQSTACKS,DATATYPEXIFSTOPMAXSIZE1RETURN0ELSESTOPSDATASTOPXRETURN1INTPOP_SEQSTACKPSEQSTACKS,DATATYPEXIFEMPTY_SEQSTACKSRETURN0ELSEXSDATASTOPSTOPRETURN1INTGETTOP_SEQSTACKPSEQSTACKS,DATATYPEXIFEMPTY_SEQSTACKSRETURN0ELSEXSDATASTOPRETURN1VOIDDESTORY_SEQSTACKPSEQSTACKSIFSFREESSNULLRETURNINTMAZEPATHINTMAZEN2,ITEMMOVE,INTX0,INTY0,INTP,INTQPSEQSTACKSDATATYPETEMPINTX,Y,D,I,JTEMPXX0TEMPYY0TEMPD1SINIT_SEQSTACKIFSPRINTF“栈初始化失败“RETURN0PUSH_SEQSTACKS,TEMPWHILEEMPTY_SEQSTACKSPOP_SEQSTACKS,XTEMPXYTEMPYDTEMPD1WHILED4IXMOVEDXJYMOVEDYIFMAZEIJ0TEMPXXTEMPYYTEMPDDPUSH_SEQSTACKS,TEMPXIYJMAZEXY1IFXPWHILEEMPTY_SEQSTACKSPOP_SEQSTACKS,PRINTF“D,D“,TEMPX,TEMPYMAZETEMPXTEMPY8DESTORY_SEQSTACKRETURN1ELSED0ELSEDDESTORY_SEQSTACKRETURN0INTMAININTMAZE810ITEMMOVE4INTX0,Y0,I,J,X,X1,Y1MOVE0X0MOVE0Y1/正东/MOVE1X1MOVE1Y0/正南/MOVE2X0MOVE2Y1/正西/MOVE3X1MOVE3Y0/正北/PRINTF“请输入迷宫的布局N“FORJ0J9JMAZE0J1MAZE7J1FORI0I7IMAZEI01MAZEI91SRANDUNSIGNEDTIMENULLFORI1I6IFORJ1J8JMAZEIJRAND2/SCANF“D“,PRINTF“迷宫如下图分布N“FORI0I7IFORJ0J9JPRINTF“D“,MAZEIJPRINTF“N“PRINTF“请输入入口的横坐标N“SCANF“D“,PRINTF“请输入入口的纵坐标N“SCANF“D“,PRINTF“请输入