数据结构演示系统1与3介绍

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 int E

10、lemTType;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,i=22

11、,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=22,

13、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个位置之之前插入元素素e。S

14、tatus 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 i,El

15、eemTypee &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, int n

16、extvval)初始条件：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 &e),

17、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 a1,

18、 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), Mergge

19、Listt_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：退出系统； 1：顺序表的运算；2：链表的运算； 3：串的模式匹配其它选项，输入错误返回主菜单。0：退出系统，安全退出。3：串的模式匹配又有四个选项。2：链表的运算又有八个选项。1其它选项，输入错误返回主菜单。0：退出系统，安全退出。3：串的模式匹配又有四个选项。2：链表的运算又有八个选项。1：SqListfun() 顺序表的运算又有七个选项。SqListffun()对对各个函数的的调用错误输入，系统自动返回菜单 顺序表的运算0：返回上一层； 1：顺序表的建立；2：顺序表的插入；错误输入，系统自动返回菜单 顺序表的运算0：返回上一层； 1：顺序表的建立；2：顺序表的

21、插入； 3：顺序表的删除；4：顺序表的查找 ；5：顺序表的无序合并；6：顺序表的有序合并；0。：返回上一层，就是放回到主函数。Main()6用户重新建立两升序的顺序表，合并它们，且合并后有序。5：用户要再建立一个线性表B，系统吧表B合并到表A中。4：用户输入要查找的元素位置，终端显示元素。3：用户输入要删除的位置删除元素2：用户输入要插入的位置和数字，把数字插入到之前建立的线性表中0。：返回上一层，就是放回到主函数。Main()6用户重新建立两升序的顺序表，合并它们，且合并后有序。5：用户要再建立一个线性表B，系统吧表B合并到表A中。4：用户输入要查找的元素位置，终端显示元素。3：用户输入要删

22、除的位置删除元素2：用户输入要插入的位置和数字，把数字插入到之前建立的线性表中1： 用户输入人一个数字，建立一个顺序表。错误的输入，会提示用户并自动返回。 链表的运算1:错误的输入，会提示用户并自动返回。 链表的运算1: 链表的建立;2: 链表的插入;3: 链表的查找;4: 链表的删除;5: 链表的计数:6: 链表的输出;7: 有序链表的合并;0:返回上一层;LinkLisstfun()7用户重新建立两升序的顺序表，合并它们，且合并后有序0.返回到主菜单。0。：返回上一层，就是放回到主函数。Main()6.系统把链表中的数字全部输出到界面上。5把链表中元素的个数以整数的形式输出。2：用户输入要

23、插入的位置和数字，把数字插入到之前建立的链表中17用户重新建立两升序的顺序表，合并它们，且合并后有序0.返回到主菜单。0。：返回上一层，就是放回到主函数。Main()6.系统把链表中的数字全部输出到界面上。5把链表中元素的个数以整数的形式输出。2：用户输入要插入的位置和数字，把数字插入到之前建立的链表中1： 用户输入人一连串数字，建立一个线性链表。4：用户输入要查找的元素位置，终端显示元素。3：用户输入要删除的位置3：按数字的位置来查询。1.按数字的值来查询。3：按数字的位置来查询。1.按数字的值来查询。错误的输入，会提示用户并自动返回。模式匹配0：返回；1:求next的值;2: 求nextv

24、al的值;错误的输入，会提示用户并自动返回。模式匹配0：返回；1:求next的值;2: 求nextval的值;3:进行模式匹配;0.返回主界面。直接回到主菜单。3.在已经求出nextal的情况下，进行模式匹配。显示每一次匹配失败的位置。1.用户输入字串，几面输出next 的值。2.选择这一项，界面直接显示nextval的值。0.返回主界面。直接回到主菜单。3.在已经求出nextal的情况下，进行模式匹配。显示每一次匹配失败的位置。1.用户输入字串，几面输出next 的值。2.选择这一项，界面直接显示nextval的值。3.2 程序序的流程图我设计的程序，主主函数的流程程图如下：开始开始 输入

25、输入 假choice=0choice=0 choice=0choice=0 假choice=1 choice=1 真 假choice=2真 choice=2顺序表的运算顺序表的运算 真 假choice=3 choice=3链表的运算 真真 链表的运算 真 choice=0choice=0串的模式匹配串的模式匹配 串的模式匹配串的模式匹配choice=0 choice=0 真 choice=0 choice=0 假 真真 真 结束结束顺序表的运算顺序表的运算 输入 输入 假choice=0 choice=0 choice=1 假choice=1 choice=3 choice=3choice=2

26、 真 假 假假choice=2choice=2真 choice=2顺序表的建立 真顺序表的建立 真 假顺序表的插入choice=4 顺序表的插入choice=4 真 假Choice=64Choice=64Choice=54 真 真真 返回主菜单返回主菜单链表的运算链表的运算 输入 输入 假choice=0 choice=0 choice=1 假choice=1 choice=3 choice=3choice=2 真 假 假假choice=2choice=2真 choice=2单链表的建立 真单链表的建立 真 假单链表的插入choice=4 单链表的插入choice=4 真 假Choice=74

27、CChoice=74Choice=64 真 真真 返回主菜单返回主菜单串的模式匹配串的模式匹配 输入 输入 假choice=0 choice=0 choice=1 假choice=1 假假choice=3 choice=3choice=2 真 假 choice=2choice=2真 choice=2求next的值 真求next的值 真 求字串nextval 求字串nextval 返回主菜单返回主菜单3.3 算法实实现的原程序序typedeff unsiigned char SStriingMAAXSTRLLEN +11;/*字字符串的数据据类型*/typedeff int Statuus;ty

28、pedeff 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 aMaxSiize;for(i=0;iLL.lenggth;i

29、+)/从第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(SqqList La,SqqList Lb,SqqList

30、&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(a

31、i=bj) /把其其中小的插入入到Lc中 LisstInseert_Sqq(Lc,+k,aii);/*调调用ListtInserrt_Sq把把小的值插入入到中*/ +i; /*ii的值加1，指指向下一个元元素*/else ListIInsertt_Sq(LLc,+kk,bj); +j;/elsse/whiilewhile(i=Laa_len)/*把LLa中剩余的的元素赋给LLc*/GetEllem(Laa,i+,ai); ListInnsert_Sq(Lcc,+k,ai);while(j=Lbb_len) /*把LLb中剩余的的元素赋给LLc*/GetEleem(Lb,j+,bbj); Lis

32、tInnsert_Sq(Lcc,+k,bj);/whiile/MerggeListtStatus GetEllem(SqqList L,EleemTypee i,EllemTyppe &e)/把线性表表L中的第ii个元素传递递给e if(iL.llengthh) /i的范围围有误，要重重新输入printtf(范围围错误!nn);returrn 0; ee=L.ellemi-1; /吧线性性表的第i个个元素取出来来。 retturn 11; /GetEllemvoid unnionSqq(SqLiist &LLa,SqLList LLb)/将所有在在线性表Lbb中但不在LLa中的数据据元素插入到

33、到La中ElemTyype Laa_len,Lb_leen,i;ElemTyype e;La_len=La.leength; Lb_len=LLb.lenngth;for(i=11;i=LLb_lenn;i+)GetElemm(Lb,ii,e); /调用GettElem()函数，获获取Lb中的的第i个值，并并赋给e if(!LoccateEllem_Sqq(La,ee, commpare)/*调用用LocatteElemm_Sq函数数，如果在LLa中找不到到与e相等的的函数， 就把把e插入到LLa中，否则则不进行插入入*/ListInssert_SSq(La,+La_len,ee);/unio

34、onSqStatus LocatteElemm_Sq(SSqListt L,EllemTyppe e,SStatuss (*coomparee)(EleemTypee, EleemTypee) /在在顺序线性表表中查找第一一个与e值满满足comppare关系系的位序/若找到则则返回其在LL中的位序，否否者返回0 EleemTypee i=1; EleemTypee *p=LL.elemm; /*把LL的首元素的的地址给p*/ whiile(i=L.leength&!(*ccomparre)(*pp+,e) /*找找到与e相等等的元素，并并且i在合法法的值以内*/ +i; if(i=L.leng

35、tth)/*ii的值比元素素个数少，是是正常的查找找*/ reeturn i; elsse retuurn 0; /查找不成功功，返回0./LocaateEleem_SqStatus ListDDeletee_Sq(SSqListt &L,iint i,ElemTType &e)/在顺序线线性表L中删删除第i个元元素，并用ee返回其值/i的合法法值为1=i=L.lengtth。ElemTyype *pp,*q; if(iiL.lengtth) rreturnn ERROOR;/*输输入i的位置置不合法，函函数退出，返返回0*/ p=&(LL.elemmi-1); /把线性表表的第i个值值的地址

36、给pp e=*p; /把的pp所指元素值值赋给e q=L.eelem+LL.lenggth-1; /*qq指向最后一一个元素*/ for(+p;p=q;+p) *(p-1)=*pp; /*从i开开始，把所有有的元素都向向前移动*/ -L.lengtth; /*顺序表的的长度减少11*/ returrn OK; /LiistDellete_SSq Statuss comppare(EElemTyype a11, EleemTypee a2) /如果aa1和a2相相等，则返回回1，否者返返回0 iif(a1=a2) retturn 11; eelse retturn 00;/listtDelett

37、e_SqStatus ListIInsertt_Sq(SSqListt &L,iint i,ElemTType ee) /在顺序序表L中第ii个位置之前前插入新的元元素e /i的合合法值为1=i=LL.lenggth+1 ElemTyype *nnewbasse,*p,*q;if(iL.lengtth+1) /i值值不合法printff(范围错错误,请重新新输入n);returnn ERROOR;if(L.leength=L.liistsizze)/当前空间已已满，增加分分配 newwbase=(ElemmType *)reaalloc(L.eleem,(L.listssize+LLISTIN

38、NCREMEENT)*ssizeoff(ElemmType);if(!neewbasee) priintf(空间已经满满了，无法获获得新空间n); exiit(OVEERFLOWW); /存储分配失失败 L.ellem=neewbasee; L.liistsizze+=LIISTINCCREMENNT; /容量相应地地增加 q=&(LL.elemmi-1); /q为插入入位置 for(pp=&(L.elemL.lenngth-11);p=q;-p) *(p+11)=*p; /插入入位置及之后后的元素右移移 *q=e; +L.llengthh;/表长长增1 returrn OK;/ListtIn

39、serrt_SqStatus InitLList_SSq(SqLList &L)/构造一个空空的线性表 L.elem=(ElemmType *)mallloc(LLIST_IINIT_SSIZE*ssizeoff(ElemmType); iff(!L.eelem) printff(分配不不了地址);exitt(OVERRFLOW); L.lenngth=00; /初始化没没有元素，顺顺序表的长度度为0 L.lisstsizee=LISTT_INITT_SIZEE; /存存储空间初始始化的空间 returrn OK; /InittList_Sqint Inddex_KMMP(SSttring S

40、,SSttring T,intt &poss, intt nexttval)/利用模式串串T的nexxt函数求TT在主串中第第pos个字字符之后/的位置的的KMP算法法。其中，TT非空，1=pos=StrLLengthh(S) int i=pos; int j=1,k=11; while(i=S0&jjTT0)printff(最后匹匹配成功,在在第%4d个个位置n,i-T0);returnn i-T0; /返回成成功匹配的位位置else printff(最后匹匹配不成功!n);returnn 0;/Indeex_KMPPvoid geet_nexxtval(SStriing T,int nne

41、xtvaal)/求模式串串T的nexxt函数修正正值并存入数数组nexttvalint i=1,j=00;nextvaal1=0;while(iT00)if(j=0|TTi=Tj) /*11的nexttval是00*/+i; /*i和jj各加1*/+j; if(TTi!=Tj) nexxtvali=j; /*字符符串不相等，就就上一次的jj赋给nexxtval*/elsee nexttvalii=nexxtvalj; /*相等的的话就把前一一个nexttval的值值赋给这个*/iff elsee j=neextvallj;/*若不相等等的话，就可可以吧nexxtval赋赋给j*/whiile/

42、get_nextvvalvoid geet_nexxt(SSttring T,intt nextt)/求模式串串T的nexxt函数值并并存入数组 i=1,j;next11=0; /*1的的next是是0*/j=0;while(inext; /*后面的就就指向La*/pb=Lb-next;Lc=pc=LLa;while(ppa&pbb)if(pa-dataadataa) pc-next=pa; /*pa指指向的节点值值小，就把该该连到Lc中中*/ pc=ppa; /*pcc指最新连入入的节点*/ ppa=pa-nextt; /*pa指向下下一个节点*/elseppc-neext

43、=pbb;/*pbb指向的节点点值小，就把把该连到Lcc中*/ ppc=pb; /*pcc指最新连入入的节点*/ pb=ppb-neext;/*pb指向下下一个节点*/pc-neext=paa?pa:ppb; /*指向不为为空的那个结结点*/free(LLb); /*释放LLb的空间*/MerggeListt_void prrint_LL(LinkkList head) LinkkList p=heaad-neext; whille(p!=NULL) /*p不不为空*/ printtf(%55d,p-dataa ); p=p-next; /*p指向下一一个结点*/printff(n);/pri

44、nnt_Lint LisstLenggth_L(LinkLList LL) LinkkList p=L; int i=0; whille(p-next!=NULLL)/*当pp不为空*/ ii+; /*i加1*/ pp=p-nnext; /wwhile retuurn (ii);/ListtLengtth_LStatus ListDDeletee_L(LiinkLisst &L, int i, EllemTyppe &e) /在带带头结点的单单链线性表LL中，删除第第i个元素，并并由e返回其其值 LinkLList qq,p=L; int jj=0; whilee(p-nnext&jneext

45、; /*p指向下下一个节点*/ +j; if(!(p-neext)|ji-11) /*i的值小小于1或者大大于L.leength*/ prinntf(删删除位置不合合理!n); retuurn ERRROR; q=p-next; p-neext=q-nextt; /删除第i个个结点 e=q-data; /把该节点的的值赋给e free(q); /*释放已已删结点的空空间*/ printtf(删除除%d成功！n,ee); returrn OK;/ListtDeletteStatus GetEllem_L(LinkLList LL,int i,EleemTypee &e)/L为带头头结点的单链链表

46、的头指针针 /当当第i个元素素存在时，其其值赋给e并并返回OK，否否者返回ERRRORLNode *p;ElemTyppe j;p=L-neext;j=1;while(pp&jnnext; +j;if(!p|ji) /ii小于1或者者大于表长printff(第%44d个元素不不存在,ii);returnn ERROOR;e=p-daata; /*找到到地i个元素素，并赋给ee*/printf(第%4dd元素为%44d,i,e);return OK;/GetEElem_LLint LoccateEllem_L(LinkLList LL,ElemmType e) /*在单链链表L中从头头开始找第1

47、1个值域与ee相等的节点点， *若存在在这样的节点点，则返回位位置，并打印印该结点的值值 */ LinnkListt p=L-nextt;int i=1;while(p!=NUULL&pp-datta!=e) /*pp没有指向表表尾，并且没没有找到元素素e*/ p=p-nextt;/*p指指向下一个结结点*/ i+;/whiileif(p=NULL) /找到表尾，没没有找到元素素eprinttf(这个个数值%d不不存在,ee);returrn NULLL;elseprinttf(你所所查询的数%d是第%dd个,e,i);returrn (i);/LocaateEleem_LStatus Lis

48、tIInsertt_L(LiinkLisst &L,int ii,ElemmType e)/在带头结结点的单链表表L中第i个个位置之前插插入元素eLinkLisst s,pp=L; int j=00;while(pp&jneext; /p指向向下一个节点点 +j;if(!p|ji-11)printff(第%44d节点不存存在n,i); /p为空，或或者i小于11或者大于表表长加1returnn ERROOR;s=(LinkkList)mallooc(sizzeof(LLNode);/生生成新的结点点s-dataa=e;s-nextt=p-nnext; /插入LL中,使s成成为第i个结结点p-n

49、extt=s;printf(插入成功功！n);return OK;/ListtInserrt_Lvoid CrreateLList_LL(LinkkList &L,innt n)/顺位序输输入n个元素素的值，建立立带头结点的的单链表L LinkkList s,r; int i; L=(LLinkLiist)maalloc(sizeoof(LNoode);/开辟一一个新的空间间 r=L; if(nn1) /长长度要大于等等于1 priintf(长度有问题题n); retturn; for(i=1;iidaata);/*给该节点点赋值*/ r-nextt=s; /*把新的节节点连接到表表尾*/ r

50、=s; /*rr指向表尾*/ r-nnext=NNULL;/尾指针的的next为为空/CreaateLisst_Lint maiin()systemm(collor 1AA);/选择颜色的的函数 int cchoicee; innt lagg=0; whhile(11)/用用whilee和swittch来控制制菜单，三个个子模块和这这个算法相同同 systtem(CCLS);/清屏函函数 putss(n); priintf(ttn); putts(ttttt欢欢迎使用数据据结构演示系系统t);puts(tttt tt); puuts(tttt 顺序序表的运算 tt); puts(ttttt 链

51、表表的运算 tt); puts(ttttt 串的的模式匹配 tt); puts(ttttt 退退出 ttt); puuts(tttt 请输入你的的选择:ttt); puts(ttttt tt); printtf(tttn); printtf(ttttt ); sscanf(%d,&choiice);switchh(intt)choiice) casse 0: returrn 1;case 11: SqLListfuun(); breeak; /顺序表表的运算case 22: LinnkListtfun(); breeak; /链表的的运算 casse 3: Indexx_SS(); break

52、k; /模式匹配defaullt: prrintf(输入的序序号不正确！请重新输入入n);systeem(PAAUSE);breakk;/swiitch /whhile/mainn调试分析4.1 调试中中的问题 在写第一个个系统的过程程中，发现要要实现的功能能很多，这样样写起来，系系统会很庞杂杂。我用传递递参数解决了了这个问题。为为了避免主菜菜但中有过多多的程序。我我把每一个子子模块都写在在一个函数中中，主菜单只只要调用这些些函数就可以以了。这样主主菜单就能够够很简短。其其次，每一个个子菜单的功功能是独立的的，又可以在在子菜单中重重新定义函数数，实现各种种功能。这样样修改起来会会很方便，并并且

53、符合结构构化的程序设设计。最开始遇到的问问题是与传递递参数有关的的问题。当时时我写了很个个子程序的算算法，编译结结果0个错误误，0个警告告。我就以为为程序可以运运行，可以一一旦调用程序序，电脑就报报出内存不能为wrrittenn或者内存不不能为reaad。我找不不到解决的方方法，因为没没有语法的错错误。我把结结构也改为结结构体指针，在在把所有的调调用重新改一一遍，还是不不行。没办法法，这个超出出我的能力范范围之外。我我已经写了那那么多程序了了，想要改变变算法重新写写估计也不可可能了。一方方面，我暂时时放开题目11,就静下心心来写第三个个程序。另外外一方面，我我找到程序设设计很熟练的的人帮我改错

54、错。功夫不负负有心人，他他一下子就看看到我的错误误。要再每一一个需要改变变的形参前加加一个“&“，不让程序序无法运行。这这代表传递参参数。我终于于明白是怎么么回事。马上上修改自己的的程序，果然然全都能运行行并的到正确确的结果。在课程设计过程程中，相互帮帮助非常重要要。最开始我我只会写菜单单，而不知道道怎样去实现现一个个算法法。而我的一一位同学把这这些算法都写写过一遍，却却对程序设计计不怎么熟练练。我们正好好互补，他给给我指明了方方向，如何实实现这些算法法。而我教了了他如何把这这些算法整合合到一起形成成一个系统。此外，有些问题题经过讨论才才得出来。比比如，在写顺顺序表和链表表的操作时，就就遇到一

55、个问问题，用户必必须悬着菜单单1建立顺序序表或者菜单单，才能够进进行后面的操操作。如果用用户没哟建立立线性表就进进行操作，系系统不会报错错，但是程序序会无法执行行。这样，我我就想出了要要写一个先把把程序，只有有当这个菜单单执行后，其其它的菜单才才能够开通。若若用户直接选选择后面的菜菜单，就会提提示用户先建建立。这个功功能是我在设设计系统前没没哟想到的。有有了这个经验验后，在串的的模式匹配的的子模块中，由由于第三个菜菜单中KMPP模式匹配算算法用的是菜菜单二中的nnextvaal，而菜单单二中的neextvall又是从菜单单一中的字串串中的到的。那那么必须先执执行菜单1，在在执行菜单22，最后执

56、行行菜单三，才才能的到正确确的结果。用用上述的方法法，设置两个个LAG很快快就能够实现现这个功能了了。在写代码的过程程中，有时候候会遇到一些些莫名的错误误，比如以前前能够的到的的结果，现在在却得不到了了。有些程序序明明没有错错误，却得不不到正确的结结果。其实这这都是在一些些小的方面出出了问题。比比如i,j看不清清，两个数组组一下子忘记记改变了，该该加1的没有有加。在进行行插入或者删删除操作时，对对i的长度的的限定，是llengthh+1,还是是lengtth，也都需需要详细的推推敲。又是后后需要用某些些变量做标记记，却忘记给给该变量赋初初值，导致出出现-25666的数字。又又是后指针和和地址没

57、有分分辨清楚，打打印出的结果果也会很奇怪怪。后来想要把界面面做的美观，就就想到用一些些特殊的符号号来装饰界面面。我悬着了了有花纹的粗粗边框。可想想要吧这个符符号整合成一一个完整的矩矩形，还是要要细细的琢磨磨。没调试一一下就上机运运行一次。方方框做好了，又又要保证字体体在正中央，还还得重新调试试。在和同学的不断断交流中，我我知道了怎么么利用，清屏屏函数，暂停停函数，还有有颜色配置函函数来把我的的界面变成彩彩色。并且没没执行完一个个工功能都会会暂停，显得得更人性化。要做到很好的设设计程序，还还是要严格推推敲，多编程程，所实践，多多思考。4.2算法的时时间复杂度以下是各个菜单单的时间复杂杂度的列表，

58、以以及如何改进进。主菜main 有几个子菜菜单就有要比比较几次，时时间复杂度为为O(n);同样三个子菜单单的时间复杂杂度也都是OO(n);由由于需要用户户来选择，需需要和每一个个选项比较，无无法提高复杂杂度，可以设设置指针，如如果用户输入入一个选项，就就自动连接到到该选项指定定的命令，时时间复杂度就就可以变为OO(1)了； InitLisst_Sq(&L),OO（1），初初始化，一次次性分配空间间 ListInnsert_Sq(SqqList &L,innt i,EElemTyype e), O（n），在在插入的位置置之后的元素素全部都要向向后移动ListDellete_SSq(SqLList

59、 &L,intt i,EllemTyppe &e), O（n），在在删除的位置置之后的元素素全部都要向向前移动print_SSq(SqLList LL), O（nn），打印nn个数字。GetElemm(SqLiist L,ElemTType ii,ElemmType &e)，OO（1），直直接定位置unionSqq(SqLiist &LLa,SqLList LLb) OO(m*n),表B中的的元素要和表表A中的每一一个元素比较较MergeLiist(SqqList La,SqqList Lb,SqqList &Lc)。OO(m+n),有序合并并，相对应比比较就行。unionSqq(SqLiis

60、t &LLa,SqLList LLb)，O(m+n),有序合并，相相对应比较就就行。 LocateeElem_Sq(SqqList L,EleemTypee e,Sttatus (*commpare)(ElemmType, ElemmType)O（n），把整整个表都找一一遍comparee(ElemmType a1, EElemTyype a22)，O(11),CreateLList_LL(LinkkList &L,innt n),O(n),用户输入nn个数字ListInssert_LL(LinkkList &L,innt i,EElemTyype e)，O（1），只只需要改变节节点指针Lis