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

《数据结构演示系统1与3介绍.docx》由会员分享，可在线阅读，更多相关《数据结构演示系统1与3介绍.docx（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构课程设计报告数据结构（c语言版）课程设计题 目 数据结构演示系统1 和3 学生姓名 学 号 指导教师 学 院 信息科学与工程学院 专业班级 计算机类 完成时间 七月 czlzdj目录第一章 项目概述31.1 问题的要求分析与描述.31.2 问题的要求和限制3第二章 概要设计 4第三章 详细设计.83.1系统程序的组成框图. 83.2 程序的流程图.113.3 算法的源程序15第四章 调试分析244.1 调试方法.244.2 算法时间复杂度25第五章 测试结果265.1 正确的输入与输出.265.2 错误的输入与输出32第六章 课程设计总结6.1 个人的体会和感想.41附录A：演示系统1

2、源代码有详细注释.43附录B：演示系统2源代码.60参考文献.82第一章 项目概述 1.1 问题的描述与分析 本次课程设计，我完成了两个题目，数据结构演示系统1、数据结构演示系统2。数据结构演示系统1主要有两种数据的存储结构要实现，顺序和链式,每种存储结构都要实现至少四种算法插入、删除、查询、合并。对于串还要实现模式匹配，使用KMP的快速算法，减小时间复杂度。1、顺序表的插入、删除和合并等基本操作。2、利用插入运算建立链表；实现链表的查找、删除、计数、输出等功能以及有序链表的合并。3、串的模式匹配（包括求next和nextval的值）。数据结构演示系统2 涉及了数据结构常用的三种存储结构，顺序

3、、链式、散列，算法主要是查找和排序。1、实现静态查找（包括顺序查找、折半查找和插入查找）和动态查找（包括二叉排序树和二叉平衡树）。2、根据输入的数据实现下列内部排序：直接插入排序、折半插入排序、表插入排序和希尔排序；快速排序；简单选择排序和堆排序；归并排序；链式基数排序。1.2 问题的要求和限制 1.2.1 我做的界面以用户为主，还兼容了容错能力。首先就是菜单的选择均有容错能力。整形数字的范围是-32768-32767，要求用户输入显示在用户界面上的整形数字（1、2、3、4、），当用户输入不正确的选项时，会自动提示输入错误，并返回原菜单要求用户从新输入。其次，每一个子菜单同样有相同的容错能力，

4、对于某些子系统，用户必须先建立线性表才能进行操作，若不先建立线性表，程序同样会回到主菜单，并提示用户建立线性表。 1.2.2 由于用户能输入任意个数字进行演示，并且长度由用户规定。系统规定用户输入的长度应该在1100以内。长度小于1就没有意义了，但也不能太大，输入长度太大，用户会没有时间去输入线性表的元素。在输入数字时，理论上是表的长度不能小于1。如果小于1，则会提示输入错误，菜单自动返回。此外，在进行某些操作，如插入删除时，用户能在任意位置插入且能在任意位置删除，不过位置必须在线性表的范围之内。若超过线性表的现有长度，那么同样会报错。 1.2.3 在用户界面（DOS界面），用户每执行完一次操

5、作，都会有相应的提示。若用户建立了线性表，则会显示建立成功。若用户进行查找，都会提示查找成功与否。输出地形式是以用户存入线性表的数字为准，一般都是整形。输入其它形式的数字，会自动转化为整形。在串的模式匹配中，模式串和主串的长度输入是整形，规定用户必须输入1100的数字，否则会提示错误，要求从新输入。而串的值是字符型。必须输入字符，才能得到正确的结果。 1.2.4 数据结构演示系统1主要有四个模块，一个主模块，三个子模块。主模块调用三个函数，SqListfun(),LinkListfun(),Index_SS(),分别指向三个不同功能的子模块。SqListfun()实现上述顺序线性表的算法，Li

6、nkListfun()实现上述连是线性表的算法，最后一个Index_SS()实现上述串的模式匹配算法。每一个模块的调用以及返回都是通过用户选择菜单来实现的。这些模块能够演示顺序表建立、插入、删除、查找、无序合并和有序合并，链表的建立、插入、删除、查找有序合并，用KMP算法实现串的模式匹配，给用户看每一次匹配失败的地方，和字串的 next和nextval值。 正确输入以及出入结果：正确的菜单选择是界面上面的数字，正确的大小范围是1到100的长度建立，正确的插入范围是线性表的长度范围，正确的字符串长度也是1到100，正确的模式匹配应输入字符。有了正确的输入，系统会按要求，显示正常的结果，如表中的元

7、素是什么，表插入成功后表的元素也会增加，删除成功会显示删除的是哪个元素哪个位置。 错误的输入会导致错误的输出，输入不在菜单范围内的数字系统会自动提示，接着返回原菜单。输入超过线性表长度范围的位置，系统不会进行插入或者删除，并自动返回原菜单。在有序合并的共能当中，没有按递增序列输入数字，合并后的链表也不会是有序的。第二章 概要设计2.1 数据类型定义数据机构演示系统1定义了五种存储结构，typedef int Status;是定义函数的返回值类型，也可以定义数据的类型，在数据有变动时而算法不变时，只需要改变其中的“int”就可以。SqList是顺序表的数据类型，其中包含三个成员，一个是ElemT

8、ype的指针变量，第二个是表中元素的个数，第三个是表的当前容量。第三个是上面提到的ElemType，主要表示各种元素的数据类型。第四个是typedef struct LNode *LinkList,这个是链表的元素类型，每次用链表都用这个来定义新结点。最后是typedef unsigned char SStringMAXSTRLEN +1;这个是字符串数组，在模式匹配中用到。ElemTypetypedef int ElemType;typedef struct ElemType *elem; int length; int listsize; SqList;typedef unsigned c

9、har SStringMAXSTRLEN +1;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList; 顺序表的各种抽象数据类型的定义如下 ADT list_Sq数据对象：D=ai|aiElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,i=2,n基本操作： Status InitList_Sq(SqList &L) 操作结果：构造一个空的线性顺序表L。 Status GetElem(SqList L,ElemType i,ElemType &e) 初始条件：线性表L已存在，1=i=L

10、istlength(L)。操作结果：把线性表L中的第i个元素传递给e。 Status ListInsert_Sq(SqList &L,int i,ElemType e) 初始条件：线性表L已存在，1=i=Listlength(L)+1。 操作结果：在顺序表L中第i个位置之前插入新的元素e，L的长度加1。 Status ListDelete_Sq(SqList &L,int i,ElemType &e) 初始条件：线性顺序表L已存在且非空，i的合法值为1=i=L.length。 操作结果：在顺序线性表L中删除第i个元素，并用e返回其值，L的长度减1。 Status LocateElem_Sq(S

11、qList L,ElemType e,Status (*compare)(ElemType, ElemType) 初始条件：线性表L已存在，1=i=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：void CreateList_L(LinkList &L,int n)操作结果：顺位序输入n个元素的值，建立带头结点的单链表L。void print_L(LinkList head)操作结果：在界面上打印head结点。 初始条件：单链线性表L存在。 操作结果：返回单链线性表的长度。Status ListInsert_L(LinkList &L,int i,ElemType e) 初始条件：

12、单链线性表L存在且不为空，1=i=Listlength(L)+1。操作结果：在带头结点的单链表L中第i个位置之前插入元素e。Status ListDelete_L(LinkList &L, int i, ElemType &e) 初始条件：单链线性表L存在，i的合法值为1=i=L.length。 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值。int LocateElem_L(LinkList L,ElemType e)初始条件：单链线性表L已存在且非空。 操作结果：在单链表L中从头开始找第1个值域与e相等的节点，若存在这样的节点，则返回位置，并打印该结点的值。Status Get

13、Elem_L(LinkList L,int i,ElemType &e) 初始条件： L为带头结点的单链表的头指针，1=i=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：void get_next(SString T,int next)操作结果：求模式串T的next函数值并存入数组next.。 void get_nextval(SString T,int nextval) 初始条件：T非空。操作结果：求模式串T的next函数修正值并存入数组nextval。 int Index_KMP(SString S,SString T,int &pos, int nextval)初始条件：T非

14、空，1=pos=StrLength(S)。操作结果：利用模式串T的next函数求T在主串中第pos个字符之后的位置的KMP算法。2.2 各个函数的调用关系各个函数的调用关系：main()调用SqListfun()，LinkListfun()，Index_SS();。SqListfun()调用InitList_Sq(&L), ListInsert_Sq(SqList &L,int i,ElemType e), ListDelete_Sq(SqList &L,int i,ElemType &e), print_Sq(SqList L), GetElem(SqList L,ElemType i,El

15、emType &e)，unionSq(SqList &La,SqList Lb)和MergeList(SqList La,SqList Lb,SqList &Lc)。其中，unionSq(SqList &La,SqList Lb)调用LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType, ElemType)，和compare(ElemType a1, ElemType a2)。 LinkListfun()调用CreateList_L(LinkList &L,int n)，ListInsert_L(LinkList &L,int

16、 i,ElemType e)，ListDelete_L(LinkList &L, int i, ElemType &e)，int ListLength_L(LinkList L)，LocateElem_L(LinkList L,ElemType e), GetElem_L(LinkList L,int i,ElemType &e), MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)和print_L(LinkList head)。而Index_SS()调用了get_next(SString T,int next)，get_nextval(SS

17、tring T,int nextval)，Index_KMP(SString S,SString T,int &pos, int nextval)。 第三章 详细设计3.1系统程序的组成框图主函数对各个函数的调用关系图。 欢迎界面0：退出系统； 1：顺序表的运算；2：链表的运算； 3：串的模式匹配 其它选项，输入错误返回主菜单。0：退出系统，安全退出。3：串的模式匹配又有四个选项。2：链表的运算又有八个选项。1：SqListfun() 顺序表的运算又有七个选项。SqListfun()对各个函数的调用错误输入，系统自动返回菜单 顺序表的运算0：返回上一层； 1：顺序表的建立；2：顺序表的插入；

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

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

20、回主界面。直接回到主菜单。3.在已经求出nextal的情况下，进行模式匹配。显示每一次匹配失败的位置。1.用户输入字串，几面输出next 的值。2.选择这一项，界面直接显示nextval的值。3.2 程序的流程图我设计的程序，主函数的流程图如下：开始 输入 假choice=0choice=0 假choice=1 真 假choice=2真 顺序表的运算 真 假choice=3 链表的运算 真 真 choice=0串的模式匹配串的模式匹配 choice=0 真 choice=0 假 真 真 结束顺序表的运算 输入 假choice=0 choice=1 假 choice=3 choice=2 真 假

21、 假choice=2真 顺序表的建立 真 真 假顺序表的插入choice=4 顺序表的查找 真 假Choice=64Choice=54顺序表的删除 真 真 顺序表的有序合并顺序表的无序合并 返回主菜单链表的运算 输入 假choice=0 choice=1 假 choice=3 假choice=2 真 假 假choice=2真 单链表的建立 真 真 假单链表的插入choice=4 单链表的查找 真 假Choice=74Choice=64单链表的删除 真 真 单链表的有序合并链表的输出 返回主菜单串的模式匹配 输入 假choice=0 choice=1 假 假choice=3 choice=2 真

22、 假 choice=2真 求next的值 真 真 求字串nextval 串的模式匹配 返回主菜单3.3 算法实现的原程序typedef unsigned char SStringMAXSTRLEN +1;/*字符串的数据类型*/typedef int Status;typedef int ElemType;typedef struct ElemType *elem; int length; int listsize; SqList;/*顺序表的数据类型*/typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList

23、;/*单链表的数据类型*/每一个抽象数据结构对应的算法如下void print_Sq(SqList L)/打印顺序表的全部元素。int i;int aMaxSize;for(i=0;iL.length;i+)/从第0个元素开始，一直到L.length输出L的值ai=L.elemi;printf(%4d,ai);printf(n);/print_Sq void print_Sq(SqList L)/打印顺序表的全部元素。int i;int aMaxSize;for(i=0;iL.length;i+)/从第0个元素开始，一直到L.length输出L的值ai=L.elemi;printf(%4d,a

24、i);printf(n);/print_Sq void MergeList(SqList La,SqList Lb,SqList &Lc)/已知线性表La和Lb中的数据元素按值非递减排列/归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列。 int ai,bj,i,j,k,La_len,Lb_len; InitList_Sq(Lc);i=j=1;k=0;La_len=La.length;Lb_len=Lb.length;while(i=La_len)&(j=Lb_len)/当其中任意一个表没有选择完的时候GetElem(La,i,ai); /调用GetElem()函数，获取La的

25、值，并赋给aiGetElem(Lb,j,bj);if(ai=bj) /把其中小的插入到Lc中 ListInsert_Sq(Lc,+k,ai);/*调用ListInsert_Sq把小的值插入到中*/ +i; /*i的值加1，指向下一个元素*/else ListInsert_Sq(Lc,+k,bj); +j;/else/whilewhile(i=La_len)/*把La中剩余的元素赋给Lc*/GetElem(La,i+,ai); ListInsert_Sq(Lc,+k,ai);while(j=Lb_len) /*把Lb中剩余的元素赋给Lc*/GetElem(Lb,j+,bj); ListInser

26、t_Sq(Lc,+k,bj);/while/MergeListStatus GetElem(SqList L,ElemType i,ElemType &e)/把线性表L中的第i个元素传递给e if(iL.length) /i的范围有误，要重新输入printf(范围错误!n);return 0; e=L.elemi-1; /吧线性表的第i个元素取出来。 return 1; /GetElemvoid unionSq(SqList &La,SqList Lb)/将所有在线性表Lb中但不在La中的数据元素插入到La中ElemType La_len,Lb_len,i;ElemType e;La_len=

27、La.length; Lb_len=Lb.length;for(i=1;i=Lb_len;i+)GetElem(Lb,i,e); /调用GetElem()函数，获取Lb中的第i个值，并赋给e if(!LocateElem_Sq(La,e, compare)/*调用LocateElem_Sq函数，如果在La中找不到与e相等的函数， 就把e插入到La中，否则不进行插入*/ListInsert_Sq(La,+La_len,e);/unionSqStatus LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType, ElemType)

28、/在顺序线性表中查找第一个与e值满足compare关系的位序/若找到则返回其在L中的位序，否者返回0 ElemType i=1; ElemType *p=L.elem; /*把L的首元素的地址给p*/ while(i=L.length&!(*compare)(*p+,e) /*找到与e相等的元素，并且i在合法的值以内*/ +i; if(i=L.length)/*i的值比元素个数少，是正常的查找*/ return i; else return 0; /查找不成功，返回0./LocateElem_SqStatus ListDelete_Sq(SqList &L,int i,ElemType &e)

29、/在顺序线性表L中删除第i个元素，并用e返回其值/i的合法值为1=i=L.length。ElemType *p,*q; if(iL.length) return ERROR;/*输入i的位置不合法，函数退出，返回0*/ p=&(L.elemi-1); /把线性表的第i个值的地址给p e=*p; /把的p所指元素值赋给e q=L.elem+L.length-1; /*q指向最后一个元素*/ for(+p;p=q;+p) *(p-1)=*p; /*从i开始，把所有的元素都向前移动*/ -L.length; /*顺序表的长度减少1*/ return OK; /ListDelete_Sq Status compare(E