《数据结构》课程设计-数据结构演示系统.doc

数据结构课程设计 -数据结构演示系统课程设计报告学 院专 业 班 级 学 号 姓 名 完成日期 目 录一， -需求分析-二， -概要设计-三， -详细设计-四， -调试分析-五， -测试结果-六， -设计总结-七， -参考文献-八， -附录程序-一， 课程设计题目 数据结构演示系统1（1）、顺序表的插入、删除和合并等基本操作（2）、利用插入运算建立链表；实现链表的查找、删除、计数、输出等功能以及有序链表的合并。（3）、串的模式匹配（包括求next和nextval的值）。 2程序模块的功能要求（1） 输入的形式和输入值的范围（2） 顺序表和链表的输入形式是整形，输入值的范围是0-9999。 串的输入形式是字符型（3） 输出的形式 顺序表和链表的输出形式是整形； 串的输出形式是字符型。（4） 程序所能达到的功能；实现顺序表的创建、插入、删除和合并实现链表的创建、查找、删除、插入、输出。实现串的模式匹配（包括求next和nextval的值）（5） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果顺序表的输入：0|11|22|33|44|55|66|77|88|99| 链表输入： 2 3 4 5 6 7 8 9 二， 概 要 设 计1， 定 义定义顺序表的结构体typedef int elemtype;typedef struct/定义顺序表结构体elemtype datamaxsize;int length;sqlist;定义链表的结点结构typedef struct node /*定义单链表结点结构类型*/ int data; /*结点的数据域*/ struct node *next; /*结点的指针域*/linklist;定义字符串的数组结构int indexbf(char s,char t,int pos)int i,j,m,n; i=pos-1;j=0; m=strlen(s); n=strlen(t); 2，主流程图主菜单界面选择：顺序表；链表；串；离开顺序表操作链表操作创建删除合并查找删除输出串操作求next求nextval结束插入创建创建主串创建子串插入3，各模块之间的层次关系(1) 第一层为主界面函数，第二层为顺序表界面函数、链表界面函数、模式匹配界面函数第三层为顺序表子函数、链表子函数、模式匹配子函数（2）主界面函数调用的函数有sqlistfuc()、linklistfuc()、indexfuc（）顺序表界面调用的函数有creatsq（）、listinsert()、listdelete()、mergelist()链表界面调用的函数有creat（）、insert()、delete()、search()、mergelink()、模式匹配界面调用的函数有creatstring()、kmp(),getnext(),getnextval三，详细设计（见附录）四、调试分析1、调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析（1）一开始在在调试程序时遇到了内存错误，最终通过网上查资料找到了出错的原因：在建立对头指针和队尾指针时没有对指针进行初始化，即没有为指针动态分配空间。（2指针变量没有初始化。定义一个指针变量，c编译系统即为它开辟了一个存储空间，如果不进行初始化，则存放的是一个随机地址，它指向的位置就不确定，这在c中是很危险的，如果让一个随机的指针去指向一个随机的地址的话，可能会指向系统的工作区域，破坏数据，从而破坏某种设置，结果可能会使系统运行失常、死机甚至瘫痪。（3）警告错误太多。忽略这些警告错误并不影响程序的执行，但有时会影响到程序的执行结果，所以一定要对“warning”错误引起足够重视，编程时尽量按照警告信息消除可能影响程序结果的隐患。 编译时当警告错误数目大于某一规定值时(缺省为100)便退出编译器, 这时应改变集成开发环境菜单options/compiler/errors中的有关警告错误检查开关为off。（4）循环语句中, 循环控制变量在每次循环未进行改变, 使循环成为死循环；或和在循环语句中，不能正确的给循环变量初始化，造成循环次数不合乎要求，得不到正确的结果。2、算法的时间复杂性（1）顺序表查找的时间复杂度为：o(1)、插入的时间复杂度为：o(n)、删除的时间复杂度为：o(n)、合并的时间复杂度为：o(n)（2）有序链表插入、查找、删除、合并的时间复杂度分别为为：o(n)、o(1)、o(1)、o(n)（3）kmp模式匹配的时间复杂度为：o(n*m)三， 测试结果运行环境：c-free 4 1， 编译进入主界面2， 输入数字1进入顺序表界面 输入1进行顺序表的创建 输入10个元素，建立一个顺序表按y继续运行进入顺序表的主界面，按2输出刚建立顺序表 按y继续运行进入顺序表的主界面，按3在顺序表中查找按y继续运行进入顺序表的主界面，按4在顺序表插入一个元素按y继续运行进入顺序表的主界面，按5在顺序表删除一个元素按y继续运行进入顺序表的主界面，按6进行顺序表的合并按y继续运行进入顺序表的主界面，按0返回主菜单3， 输入数字2进入链表的界面 输入1进行单链表的建立 输入2查找单链表，查找节点位置4输入3插入节点，节点位置为4，插入的元素为100输入4删除节点，节点位置为4输入5输出单链表输入6返回主菜单4， 输入3进入字符串模式匹配界面输入1进行bf匹配，匹配的起始位置为4，主串为aaabaaaabaa输入2进行kmp匹配，起始位置为3输入3查看next 输入4查看nextval 输入5显示字符串输入6退出字符串界面，进入主菜单5， 按数字4退出系统。六、课程设计总结在开始的时候，很多人都会在编程语言上下苦功，本身并没有错，但是有些人就会产生程序设计的问题就是对编程语言的使用问题的观念，导致他们在进一步学习程序设计的过程中忽略了各种编程思想的吸收和运用，例如有些人很清楚指针的工作原理，却不懂得怎样去利用指针构造并操作完美的链表，他们设计出来的链表也许在删除节点的时候没有释放内存，或许在插入节点的时候因赋值顺序错误导致链表“断裂”，信息丢失，等等。随着要解决的问题复杂度越来越大，没有经过良好程序设计思想组织起来的代码会出现各种各样的逻辑错误，这种漏洞百出的程序在运行时有时甚至会导致系统崩溃。 所以在对编程语言有了初步了解之后，应该开始重视编程思想的培养，语言很重要，但究竟只是工具，思想才是精髓。当初我得到数据结构一书后，就通过阅读书中的各种数据结构及相应算法的代码来吸收书中的思想。我认为学习数据结构最能培养一个人对解决程序设计问题的敏感性，其建模思想对解决各种棘手问题有很大帮助，看书的时候要学会思考，例如循环队列的尾节点为何一定要是空的。当你懂得程序设计问题是类似于数学建模的思想问题后，你才算是真正入门了。这时，面对程序设计，才不会无所适从。再进一步提高自己，就要靠做题来验证各种算法思想，前期做题的时候要参考别人的代码，学会从执行效率上分辨出代码的优劣，其次再讨论其实现难度。之后就是形成自己的风格，有自己的一套解题方式和相应的算法，例如在快排和堆排的具体使用上，能有自己的一套运用方式。根据具体问题采取自己所熟悉的相应算法来解决，这样的话或许程序的运行效率不是最高效的，但解决问题的速度会比较快，而且这种根据自己风格设计的程序出错率通常会比较低。七、参考文献数据结构（c语言版）-清华大学出版社-严蔚敏+吴伟民编c语言程序设计（第二版）-中国铁道出版社-李丽娟+马淑萍编八、附录程序#include#include#include#include#include#include#include#include#define maxsize 100#define len sizeof(linklist)typedef struct node /*定义单链表结点结构类型*/ int data; /*结点的数据域*/ struct node *next; /*结点的指针域*/linklist; linklist *linkcreat() /*建立单链表函数*/int x;linklist *head,*p,*rear; /*head,rear分别为头指针和尾指针*/printf(t你选择的是尾插法建立链表功能：n);head=(struct node*)malloc(len);head-data=-999; /*头指针数据域初始为-999*/rear=head; /*尾指针的初始值为头结点head*/ printf(t请输入一组正整数以0结束输入：nt);scanf(%d,&x);while(x!=0) /*输入数据以0为结束标志*/ p=(struct node*)malloc(len); /*生成一个新结点*/ p-data=x; /*给新结点数据域赋值*/ rear-next=p; /*新结点插入到表尾*rear之后*/ rear=p; /*将尾指针rear指向新的尾结点之后*/ scanf(%d,&x);rear-next=null; /*将单链表最后一个结点rear指针域置空*/printf(t建立链表成功！n);return(head);void linksearch(linklist *head) /*查找单链表结点函数*/int x;int i=0;linklist *p;printf(t你选择的是查找功能：n);printf(t请输入要查找节点的值：);scanf(%d,&x);p=head; /*从头结点开始扫面*/while(p-next!=null)&(p-data!=x) /*循环判断查找数据*/ p=p-next; /*扫描下移*/ i+; /*数据位置后移*/if(p-data=x) /*如果查找成功输出数据所在位置*/printf(t查找成功！n); printf(t输出查找的数据所在位置为:%dn,i);else printf(t查找结点不存在！n);linklist *linkinsert(linklist *head) /*单链表结点插入函数*/int x,i,j=1;linklist *s,*q;printf(t你选择的是尾插法插入功能：n);printf(t请输入要插入的位置：);scanf(%d,&i);printf(t请输入要插入的数据：);scanf(%d,&x);s=(struct node*)malloc(len); /*建立插入数据的结点*/s-data=x; /*给新结点数据域赋值*/for(q=head;(q!=null)&(jnext; /*指针后移指向下一个结点*/if(q!=null) printf(t插入成功！n); s-next=q-next; /*新结点s后继指向原q结点的后继*/ q-next=s; /*q结点的后继指向新结点s*/else printf(t插入失败！n);return(head);linklist *linkdelete(linklist *head) /*删除单链表结点函数*/linklist *p,*q;int i,j=1; /*j为结点计数变量初始为1*/printf(t输入要删除的位置：); /*输入删除的位置*/ scanf(%d,&i);p=head; while(p-next!=null)&(jnext; j+;if(p-next!=null) /*若该结点存在删除该结点*/q=p-next; /*p的后继地址赋给q*/ printf(t删除成功！n); printf(t删除的数据为：); printf(%dn,q-data); /*输出删除结点数据*/ p-next=q-next; /*原始p结点后继指向q删除结点的后继*/ free(q); /*释放删除结点空间q*/else printf(t删除失败！);return(head);void linkprint(linklist *head) /*输出单链表函数*/ linklist *p; p=head; if(p=null) /*如果表为空输出失败信息*/printf(t输出失败！n); printf(t输出链表为：); while(p-next!=null) /*从表头开始循环输出*/ p=p-next; /*指针后移指向下一个结点*/printf(%3d,p-data); printf(n);int select() /*菜单显示函数*/ int k; printf( *2.链表操作*n); printf(t 1. 建 立 单 链 表n); printf(t 2. 查 找 单 链 表n); printf(t 3. 插 入 结 点n); printf(t 4. 删 除 结 点n); printf(t 5. 输 出 单 链 表n); printf(t 6. 退 出n); do printf(t请输入选择的功能：); scanf(%d,&k); /*输入选择的功能*/ printf( -n);while(k6); return(k);typedef int elemtype;typedef struct/定义顺序表结构体elemtype datamaxsize;int length;sqlist;void initlist(sqlist &l)l.length=0;void creatsqlist(sqlist &l,int n)int i,k=0,j=0,x=1;int flag =0;/设置 整数判别的标志位for(i=0;i-1;j-)l.datai+=(strj-0)*x;x*=10;x=1;if( l.datai 9999 | int(l.datai) != l.datai | l.datai0;j-)strj=0;k=0;l.length=n;getchar();/*void bubblesort(sqlist *l)/冒泡排序int i,j;elemtype t;sqlist *p=l;for (j = 0 ; j length-1 ; j+)for (i = 0 ; i length-j-1 ; i+)if (p-datai p-datai+1)t=p-datai;p-datai=p-datai+1;p-datai+1=t; */int output(sqlist l) /输出表int i;printf(顺序表为：n);for(i=0;il.length;i+)if(i%5=0) /按每行5个输出printf(|nn);printf(|);printf(%6d ,l.datai);printf(|);if(l.length = 0)return 0;else return 1;int getelem(sqlist l,int i)if( i=l.length )return -9999;else return l.datai;int locateelem(sqlist l,elemtype x)int k=0;while(kl.length & l.datak!=x)k+;if(kl.length) return k;else return -1;int insert(sqlist &l,elemtype x,int i)int k;if( i l.length | l.length = maxsize)return 0;elsefor(k = l.length;k = i;k-)l.datak=l.datak-1;l.datai=x;l.length=l.length+1;return 1;int delete(sqlist &l,int i)int k;if(i = l.length)return 0;elsefor(k=i;kl.length;k+)l.datak=l.datak+1;l.length-;return 1;void mergelist(sqlist la,sqlist lb,sqlist &lc)int i=0,j=0,k=0;while( i la.length )/将la先存在lc 在将lb接着lc存lc.datak+=la.datai+;while( j lb.length )lc.datak+=lb.dataj+;lc.length=k;/*while(ila.length & jlb.length)if(la.datai lb.dataj)lc.datak+=lb.dataj+;else lc.datak+=lb.dataj+;i+;while(i la.length)lc.datak+=la.datai+;while(j lb.length)lc.datak+=la.dataj+;lc.length=k;*/void title(void)int i;for(i=0;i10;i+)printf( );for(i=0;i32;i+)printf(*);printf(n);int indexbf(char s,char t,int pos)int i,j,m,n; i=pos-1;j=0; m=strlen(s); n=strlen(t); while(im & j=n) return i-n+1; else return -1;void getnext(char t,int next)/ 求模式串t的next函数值并存入数组nextint j=0,k=-1;int n=strlen(t);nextj=-1;while(jn) if(k=-1|tj=tk) j+;k+;nextj=k; else k=nextk; void getnextval(char t,int nextval) int k=-1,j=0; int n=strlen(t); nextvalj=-1; while(jn) if(k=-1|tj=tk) j+;k+;if(tj!=tk) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk;int indexkmp(char s,char t,int next,int pos)/ 利用模式串t的next函数求t在主串s中第pos个字符之后的位置的kmp算法。 / 其中,t非空,1posstrlength(s)int i,j,n;i=pos-1;j=0;int m=strlen(s);/sm=0;n=strlen(t);/tn=0;while(im & j=n) return i-n+1;/ 匹配成功return -1;/串模式匹配的测试main() system(color 1b); int m; char continue=y; sub: printf(*数据结构演示系统*n); printf(*-请选择操作-*n); printf(*-1.顺序表操作-*n); printf(*-2.链表操作-*n); printf(*-3.字符串模式匹配-*n); printf(*-4.按任意其他数字退出系统-*n); printf(请选择数字进行操作：); scanf(%d,&m);printf(n);switch(m) case 1: int i;printf(*1.顺序表的操作*n);for(i=0;i10;i+) printf( );printf(*);printf(1.建立一个顺序表);for(i=0;i10;i+) printf( );printf(*);printf(n);for(i=0;i10;i+) printf( );printf(*);printf(2.输出一个顺序表);for(i=0;i10;i+) printf( );printf(*);printf(n);for(i=0;i10;i+) printf( );printf(*);printf(3.在顺序表中查找);for(i=0;i10;i+) printf( );printf(*);printf(n);for(i=0;i10;i+) printf( );printf(*);printf(4.向顺序表中插入一个元素);for(i=0;i2;i+) printf( );printf(*);printf(n);for(i=0;i10;i+) printf( );printf(*);printf(5.删除顺序表中的一个元素);for(i=0;i2;i+) printf( );printf(*);printf(n);for(i=0;i10;i+) printf( );printf(*);printf(6.将两个顺序表合并);for(i=0;i8;i+) printf( );printf(*);printf(n);for(i=0;i10;i+) printf( );printf(*);printf(0.退出);for(i=0;i8;i+) printf( );printf(*);printf(n);title(); int t,n=0,m,k=1,x,z,j;int flag=1,key;sqlist l,la,lc;initlist(l);while(flag)/y/n的标志位printf(请选择 0-6： n);title();printf(请输入：);m=getche();printf(n);if(m = 0x0036)/键盘上0-6的按键ascii码m=0x0037;switch(m)case 0x0030:goto sub;case 0x0031:printf(输入元素值，构建顺序表：n);printf(请输入顺序表元素的个数(范围为0100)：);scanf(%d,&n);creatsqlist(l,n);output(l);break;case 0x0032:t=output(l);if(t = 0)printf(请先建立一个顺序表!);break;printf(n);break;case 0x0033:t=output(l);if(t = 0)printf(请先建立一个顺序表!);break;printf(na:查找元素值：);printf(nb:查找序列号：n);printf(a or b ?);z=getch();/对 查找进行分类了 选a还是bif(z=a)printf(na:请输入要查找的元素值(从0号开始计数)：);scanf(%d,&x);k=locateelem(l,x);if(k = -1)printf(该元素在顺序表中不存在！n);else printf(n所查找的元素：%d的序列是：%d,x,k);else if(z=b) printf(nb:请输入要查找的序列号(从0号开始计数)：);scanf(%d,&x);k=getelem(l,x);if(k = -9999)printf(该序列没有值！);elseprintf(n第%d个元素是：%d,x,k);break;case 0x0034:t=output(l);if(t = 0)printf(请先建立一个顺序表!);break;printf(n输入要插入元素的位置及其值:);printf(n输入要插入元素的位置:);scanf(%d,&i);printf(n输入要插入元素的值:);scanf(%d,&x);k=insert(l,x,i);if(k = 0)printf(输入正确的位置！);output(l);break;case 0x0035:t=output(l);if(t = 0)printf(请先建立一个顺序表!);break;printf(n输入要删除的元素位置：);scanf(%d,&j);k=delete(l,j);if(k = 0)printf(输入正确的位置！);output(l);break;case 0x0036:t=output(l);if(t = 0)printf(请先建立一个顺序表!n);break;initlist(la);printf(n请输入第二个顺序表元素的个数：);m=getche();printf(n);m=m-0;creatsqlist(la,m);output(la);mergelist(l,la,lc);printf(n输出合并后的顺序表中的元素：n);output(lc);break;default:break; printf(n继续运行吗？y/n:n);xyz:key=getche();if(key = 0x0079)flag=1;else if(key = 0x006e)flag=0;elsegoto sub;case 2:int k;linklist *head;sub1: printf( *2.链表操作*n); printf(t 1. 建 立 单 链 表n); printf(t 2. 查 找 单 链 表n); printf(t 3. 插 入 结 点n); printf(t 4. 删 除 结 点n); printf(t 5. 输 出 单 链 表n); printf(t 6. 退 出n); printf(t请输入选择的功能：); scanf(%d,&k); /*输入选择的功能*/ printf( -n); /*单链表主函数*/ /*输入选择功能*/switch(k)case 1:head=linkcreat();linkprint(head);goto sub1; /*建立单链表函数*/case 2:linksearch(head);goto sub1; /*建立单链表函数*/case 3:head=linkinsert(head);linkprint(head);goto sub1; /*单链表结点插入函 数*/ case 4:head