《数据结构演示系统1与3介绍44545.docx》由会员分享，可在线阅读，更多相关《数据结构演示系统1与3介绍44545.docx（145页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告数据结构（c语言版）课程设计题 目 数数据结构演示示系统1 和3 学生姓名 学 号 指导教师 学 院 信信息科学与工工程学院 专业班级 计算机机类 完成时间 七月 czlzdj目录第一章 项目目概述31.1 问题题的要求分析析与描述.331.2 问题题的要求和限限制3第二章 概要设设计 4第三章 详细细设计.83.1系统程序序的组成框图图. 83.2 程序的的流程图.113.3 算法的的源程序15第四章 调试试分析244.1 调试方方法.244.2 算法时时间复杂度225第五章 测试试结果265.1 正确的的输入与输出出.265.2 错误的的输入与输出出332第六章 课程程
2、设计总结6.1 个人的的体会和感想想.41附录A：演示系系统1源代码码有详细注释释.43附录B：演示系系统2源代码码.600参考文献.822第一章 项目概述 1.1 问题的描述述与分析 本次课程程设计，我完完成了两个题题目，数据结结构演示系统统1、数据结结构演示系统统2。数据结构演示系系统1主要有有两种数据的的存储结构要要实现，顺序序和链式,每每种存储结构构都要实现至至少四种算法法插入、删除除、查询、合合并。对于串串还要实现模模式匹配，使使用KMP的的快速算法，减减小时间复杂杂度。1、顺顺序表的插入入、删除和合合并等基本操操作。2、利利用插入运算算建立链表；实现链表的的查找、删除除、计数、输输
3、出等功能以以及有序链表表的合并。33、串的模式式匹配（包括括求nextt和nexttval的值值）。数据结构演示系系统2 涉及及了数据结构构常用的三种种存储结构，顺顺序、链式、散散列，算法主主要是查找和和排序。1、实实现静态查找找（包括顺序序查找、折半半查找和插入入查找）和动动态查找（包包括二叉排序序树和二叉平平衡树）。22、根据输入入的数据实现现下列内部排排序：直接接插入排序、折折半插入排序序、表插入排排序和希尔排排序；快速速排序；简简单选择排序序和堆排序；归并排序序；链式基基数排序。1.2 问题的的要求和限制制 1.2.1 我做的界面面以用户为主主，还兼容了了容错能力。首首先就是菜单单的选
4、择均有有容错能力。整整形数字的范范围是-322768-327677，要求用户户输入显示在在用户界面上上的整形数字字（1、2、33、4、），当用户户输入不正确确的选项时，会会自动提示输输入错误，并并返回原菜单单要求用户从从新输入。其其次，每一个个子菜单同样样有相同的容容错能力，对对于某些子系系统，用户必必须先建立线线性表才能进进行操作，若若不先建立线线性表，程序序同样会回到到主菜单，并并提示用户建建立线性表。 1.22.2 由于于用户能输入入任意个数字字进行演示，并并且长度由用用户规定。系系统规定用户户输入的长度度应该在1100以内内。长度小于于1就没有意意义了，但也也不能太大，输输入长度太大大
5、，用户会没没有时间去输输入线性表的的元素。在输输入数字时，理理论上是表的的长度不能小小于1。如果果小于1，则则会提示输入入错误，菜单单自动返回。此此外，在进行行某些操作，如如插入删除时时，用户能在在任意位置插插入且能在任任意位置删除除，不过位置置必须在线性性表的范围之之内。若超过过线性表的现现有长度，那那么同样会报报错。 1.2.3 在在用户界面（DDOS界面），用用户每执行完完一次操作，都都会有相应的的提示。若用用户建立了线线性表，则会会显示建立成成功。若用户户进行查找，都都会提示查找找成功与否。输输出地形式是是以用户存入入线性表的数数字为准，一一般都是整形形。输入其它它形式的数字字，会自动
6、转转化为整形。在在串的模式匹匹配中，模式式串和主串的的长度输入是是整形，规定定用户必须输输入1100的数数字，否则会会提示错误，要要求从新输入入。而串的值值是字符型。必必须输入字符符，才能得到到正确的结果果。 1.2.4 数数据结构演示示系统1主要要有四个模块块，一个主模模块，三个子子模块。主模模块调用三个个函数，SqqListffun(),LinkLListfuun(),IIndex_SS(),分别指向三三个不同功能能的子模块。SSqListtfun()实现上述顺顺序线性表的的算法，LiinkLisstfun()实现上述述连是线性表表的算法，最最后一个Inndex_SSS()实现现上述串的模
7、模式匹配算法法。每一个模模块的调用以以及返回都是是通过用户选选择菜单来实实现的。这些些模块能够演演示顺序表建建立、插入、删删除、查找、无无序合并和有有序合并，链链表的建立、插插入、删除、查查找有序合并并，用KMPP算法实现串串的模式匹配配，给用户看看每一次匹配配失败的地方方，和字串的的 nextt和nexttval值。 正确输输入以及出入入结果：正确确的菜单选择择是界面上面面的数字，正正确的大小范范围是1到1100的长度度建立，正确确的插入范围围是线性表的的长度范围，正正确的字符串串长度也是11到100，正正确的模式匹匹配应输入字字符。有了正正确的输入，系系统会按要求求，显示正常常的结果，如如
8、表中的元素素是什么，表表插入成功后后表的元素也也会增加，删删除成功会显显示删除的是是哪个元素哪哪个位置。 错误的的输入会导致致错误的输出出，输入不在在菜单范围内内的数字系统统会自动提示示，接着返回回原菜单。输输入超过线性性表长度范围围的位置，系系统不会进行行插入或者删删除，并自动动返回原菜单单。在有序合合并的共能当当中，没有按按递增序列输输入数字，合合并后的链表表也不会是有有序的。第二章 概要要设计2.1 数据类类型定义数据机构演示系系统1定义了了五种存储结结构，typpedef int SStatuss;是定义函函数的返回值值类型，也可可以定义数据据的类型，在在数据有变动动时而算法不不变时，
9、只需需要改变其中中的“int”就可以。SSqListt是顺序表的的数据类型，其其中包含三个个成员，一个个是ElemmType的的指针变量，第第二个是表中中元素的个数数，第三个是是表的当前容容量。第三个个是上面提到到的ElemmType，主主要表示各种种元素的数据据类型。第四四个是typpedef strucct LNoode *LinkkList,这个是链表表的元素类型型，每次用链链表都用这个个来定义新结结点。最后是是typeddef unnsigneed chaar SSttringMAXSTTRLEN +1;这这个是字符串串数组，在模模式匹配中用用到。ElemTyppetypedeff i
10、nt ElemTType;typedeff struuct ElemTType *elem; int llengthh; int llistsiize; SqLiist;typedeff unsiigned char SStriingMAAXSTRLLEN +11;typedeff struuct LNNode ElemTType ddata; strruct LLNode *nextt;LNode,*LinkkList; 顺序表的的各种抽象数数据类型的定定义如下 ADT llist_SSq数据对象：D=ai|aaiElemSSet,i=1,2,n,n=0数据关系：R11=|ai-1,aiD,
11、i=22,n基本操作： Stattus InnitLisst_Sq(SqLisst &L) 操作作结果：构造造一个空的线线性顺序表LL。 Stattus GeetElemm(SqLiist L,ElemTType ii,ElemmType &e) 初始条件：线性表L已已存在，1=i=LListleength(L)。操作结果：把线线性表L中的的第i个元素素传递给e。 Stattus LiistInssert_SSq(SqLList &L,intt i,EllemTyppe e) 初初始条件：线线性表L已存存在，1=i=Liistlenngth(LL)+1。 操操作结果：在在顺序表L中中第i个位置
12、置之前插入新新的元素e，LL的长度加11。 Stattus LiistDellete_SSq(SqLList &L,intt i,EllemTyppe &e) 初初始条件：线线性顺序表LL已存在且非非空，i的合合法值为1=i=LL.lenggth。 操作结果果：在顺序线线性表L中删删除第i个元元素，并用ee返回其值，LL的长度减11。 Stattus LoocateEElem_SSq(SqLList LL,ElemmType e,Staatus (*comppare)(ElemTType, ElemTType) 初初始条件：线线性表L已存存在，1=i=0数据关系：R11=|ai-1,aiD,i
13、=22,n基本操作：void CrreateLList_LL(LinkkList &L,innt n)操作结果：顺位位序输入n个个元素的值，建建立带头结点点的单链表LL。void prrint_LL(LinkkList head)操作结果：在界界面上打印hhead结点点。 初始条件：单链线性表表L存在。 操作结果：返回单链线线性表的长度度。Status ListIInsertt_L(LiinkLisst &L,int ii,ElemmType e) 初始条件：单链线性表表L存在且不不为空，1=i=LListleength(L)+1。操作结果：在带带头结点的单单链表L中第第i个位置之之前插入元素
14、素e。Status ListDDeletee_L(LiinkLisst &L, int i, EllemTyppe &e) 初始条件件：单链线性性表L存在，ii的合法值为为1=i=L.leength。 在带头结结点的单链线线性表L中，删删除第i个元元素，并由ee返回其值。int LoccateEllem_L(LinkLList LL,ElemmType e)初始条件：单链链线性表L已已存在且非空空。 操作结果果：在单链表表L中从头开开始找第1个个值域与e相相等的节点，若若存在这样的的节点，则返返回位置，并并打印该结点点的值。Status GetEllem_L(LinkLList LL,int
15、i,EleemTypee &e) 初始始条件： LL为带头结点点的单链表的的头指针，11=i=0数据关系：R11=|ai-1,aiD,i=22,n基本操作：void geet_nexxt(SSttring T,intt nextt)操作结果：求模模式串T的nnext函数数值并存入数数组nextt.。 voiid gett_nexttval(SSStrinng T,iint neextvall) 初始条件：T非空。操作结果：求模模式串T的nnext函数数修正值并存存入数组neextvall。 intt Indeex_KMPP(SStrring SS,SStrring TT,int &pos, i
16、nt nextvval)初始条件：T非非空，1=pos=StrLeength(S)。操作结果：利用用模式串T的的next函函数求T在主主串中第poos个字符之之后的位置的KMPP算法。2.2 各个函函数的调用关关系各个函数的调用用关系：maain()调调用SqLiistfunn()，LinkLListfuun()，Indexx_SS();。SqListffun()调调用InittList_Sq(&LL), LiistInssert_SSq(SqLList &L,intt i,EllemTyppe e), ListtDelette_Sq(SqLisst &L,int ii,ElemmType &
17、e), prinnt_Sq(SqLisst L), GetEElem(SSqListt L,EllemTyppe i,EElemTyype &ee)，unionnSq(SqqList &La,SSqListt Lb)和和MergeeList(SqLisst La,SqLisst Lb,SqLisst &Lcc)。其中，unioonSq(SSqListt &La,SqLisst Lb)调用LocaateEleem_Sq(SqLisst L,EElemTyype e,Statuus (*ccomparre)(EllemTyppe, EllemTyppe)，和和compaare(EllemTyppe
18、 a1, ElemmType a2)。 LinkLiistfunn()调用CreaateLisst_L(LLinkLiist &LL,int n)，ListIInsertt_L(LiinkLisst &L,int ii,ElemmType e)，ListDDeletee_L(LiinkLisst &L, int i, EllemTyppe &e)，int LisstLenggth_L(LinkLList LL)，LocatteElemm_L(LiinkLisst L,EElemTyype e), GetEElem_LL(LinkkList L,intt i,EllemTyppe &e), Me
19、rggeListt_L(LiinkLisst &Laa,LinkkList &Lb,LLinkLiist &LLc)和printt_L(LiinkLisst heaad)。而Index_SS()调调用了gett_nextt(SStrring TT,int next)，get_nnextvaal(SSttring T,intt nexttval)，Indexx_KMP(SStriing S,SStriing T,int &pos, int nnextvaal)。 第三章 详细细设计3.1系统程序序的组成框图图主函数对各个函函数的调用关关系图。 欢迎界面0：退出系统； 1：顺序表的运算；2：链表的
20、运算； 3：串的模式匹配 其它选项，输入错误返回主菜单。0：退出系统，安全退出。3：串的模式匹配又有四个选项。2：链表的运算又有八个选项。1：SqListfun() 顺序表的运算又有七个选项。SqListffun()对对各个函数的的调用错误输入，系统自动返回菜单 顺序表的运算0：返回上一层； 1：顺序表的建立；2：顺序表的插入； 3：顺序表的删除；4：顺序表的查找 ；5：顺序表的无序合并；6：顺序表的有序合并； 0。：返回上一层，就是放回到主函数。Main()6用户重新建立两升序的顺序表，合并它们，且合并后有序。5：用户要再建立一个线性表B，系统吧表B合并到表A中。4：用户输入要查找的元素位置
21、，终端显示元素。3：用户输入要删除的位置删除元素2：用户输入要插入的位置和数字，把数字插入到之前建立的线性表中1： 用户输入人一个数字，建立一个顺序表。错误的输入，会提示用户并自动返回。 链表的运算1: 链表的建立;2: 链表的插入;3: 链表的查找;4: 链表的删除;5: 链表的计数:6: 链表的输出;7: 有序链表的合并;0:返回上一层;LinkLisstfun()7用户重新建立两升序的顺序表，合并它们，且合并后有序0.返回到主菜单。0。：返回上一层，就是放回到主函数。Main()6.系统把链表中的数字全部输出到界面上。5把链表中元素的个数以整数的形式输出。2：用户输入要插入的位置和数字，
22、把数字插入到之前建立的链表中1： 用户输入人一连串数字，建立一个线性链表。4：用户输入要查找的元素位置，终端显示元素。3：用户输入要删除的位置3：按数字的位置来查询。1.按数字的值来查询。错误的输入，会提示用户并自动返回。模式匹配0：返回；1:求next的值;2: 求nextval的值;3:进行模式匹配;Index_SSS() 0.返回主界面。直接回到主菜单。3.在已经求出nextal的情况下，进行模式匹配。显示每一次匹配失败的位置。1.用户输入字串，几面输出next 的值。2.选择这一项，界面直接显示nextval的值。3.2 程序序的流程图我设计的程序，主主函数的流程程图如下：开始 输入
23、假choice=0choice=0 假choice=1 真 假choice=2真 顺序表的运算 真 假choice=3 链表的运算 真真 真 choice=0串的模式匹配串的模式匹配 choice=0 真 choice=0 假 真真 真 结束顺序表的运算 输入 假choice=0 choice=1 假 choice=3 choice=2 真 假 假假choice=2真 顺序表的建立 真 真 假顺序表的插入choice=4 顺序表的查找 真 假Choice=64Choice=54顺序表的删除 真 真真 顺序表的有序合并顺序表的无序合并 返回主菜单链表的运算 输入 假choice=0 choice
24、=1 假 choice=3 假choice=2 真 假 假假choice=2真 单链表的建立 真 真 假单链表的插入choice=4 单链表的查找 真 假Choice=74Choice=64单链表的删除 真 真真 单链表的有序合并链表的输出 返回主菜单串的模式匹配 输入 假choice=0 choice=1 假 假假choice=3 choice=2 真 假 choice=2真 求next的值 真 真 求字串nextval 串的模式匹配 返回主菜单3.3 算法实实现的原程序序typedeff unsiigned char SStriingMAAXSTRLLEN +11;/*字字符串的数据据类型
25、*/typedeff int Statuus;typedeff int ElemTType;typedeff struuct ElemTType *elem; int llengthh; int llistsiize; SqLiist;/*顺序表的数数据类型*/typedeff struuct LNNode ElemTType ddata; strruct LLNode *nextt;LNode,*LinkkList;/*单链表表的数据类型型*/每一个抽象数据据结构对应的的算法如下void prrint_SSq(SqLList LL)/打印顺序序表的全部元元素。int i;int aMaxSi
26、ize;for(i=0;iLL.lenggth;i+)/从第00个元素开始始，一直到LL.lenggth输出LL的值ai=LL.elemmi;printff(%4dd,aii);printff(n);/prinnt_Sq void printt_Sq(SSqListt L)/打印顺序序表的全部元元素。int i;int aMaxSiize;for(i=0;iLL.lenggth;i+)/从第00个元素开始始，一直到LL.lenggth输出LL的值ai=LL.elemmi;printff(%4dd,aii);printff(n);/prinnt_Sq void MeergeLiist(SqqLi
27、st La,SqqList Lb,SqqList &Lc)/已知线性性表La和LLb中的数据据元素按值非非递减排列/归并Laa和Lb得到到新的线性表表Lc,Lcc的数据元素素也按值非递递减排列。 intt ai,bbj,i,jj,k,Laa_len,Lb_leen; IniitListt_Sq(LLc);i=j=1;k=0;La_lenn=La.llengthh;Lb_lenn=Lb.llengthh;while(i=LLa_lenn)&(jj=Lb_len)/当其其中任意一个个表没有选择择完的时候GetEleem(La,i,ai); /调用用GetEllem()函函数，获取LLa的值，并并赋给aiGetEleem(Lb,j,bj);if(ai=bj) /把其其中小的插入入到Lc中 LisstInseert_Sqq(Lc,+k,aii);/*调调用ListtInserrt_