顺序表链表KMP算法-数据结构报告

1、目录需求分析-P3概要设计-P4详细设计-P9调试分析-P11测试结果-P11课程设计总结-P15参考文献-P16附录-P16一：需求分析：顺序表的插入、删除、合并等操作：涉及顺序表的创建、插入、删除、查找、合并、显示等。采用数组作为顺序表的结构，定义一个MAXSIZE作为数组的最大长度。从键盘接收用户输入的基本数据类型（这里以char为例，也可以是int等其他类型）为例演示方便，系统自带一个已经含有元素的顺序表。然后接收用户输入指令进行相应的操作。插入演示时，要求用户输入插入的字符串和要插入的位置；删除演示时要求用户输入要删除的长度和起始位置；合并操作演示时，要求用户输入一个字符串用来建立新

2、的顺序表，然后两个顺序表合并并输出新的顺序表。链表的查找、删除、计数、输出等功能以及有序链表的合并：涉及链表的创建、删除、查找、合并、显示等。需要动态分配内存，用指针连接各节点。先自定义一个ListNode节点用户存储数据和指针。为了演示方便，系统依然自带了一个创建好并且含有若干元素的链表，用户可以在此基础上进行操作。查找操作时，要求用户输入查找的字符，然后输出查找结果；插入操作时，要求用户输入要插入的字符以及要插入的位置；删除演示时要求用户输入要删除的长度和起始位置；合并操作演示时，要求用户输入一个字符串用来建立新的链表，然后两个顺序表合并并输出新的顺序表。串的模式匹配：为了演示方便，系统依

3、然自带了一个创建好并且含有若干元素的主串，然后接受用户输入的模式串。求出该模式串的next和nextval，再由此验证模式串在主串中的匹配情况。二：概要设计：本程序中用到的所有抽象数据类型的定义如下。1、顺序表ADT SqList数据对象：D=ai|aiElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList_Sq(&L)操作结果：构造一个空的顺序表。Create_Sq(&L)初始条件：空顺序表L已经构造。操作结果：在L中存放数据元素，创建顺序表L。ListInsert_Sq&L,I,e)初始条件：顺序表L存在，并且1=i=ListLeng

4、th(L)+1。操作结果：在L中的第i个位置之前插入新的数据元素e，L的表长加1。Show_Sq(L)初始条件：存在非空顺序表L。操作结果：输出显示顺序表L。MergeList_Sq(La, Lb, &Lc)初始条件：存在顺序表La,Lb，Lc。操作结果：把LaLb合并为Lc。DeSameElem_Sq(&L)初始条件：存在非空顺序表L。操作结果：剔除L中的相同元素。Sort_Sq(&L)初始条件：存在非空顺序表L。操作结果：/对顺序表L按非递减顺序排序。ListDelete_Sq(&L, i)初始条件：存在顺序表L非空，1=i=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：Ini

5、tList_L(& L)操作结果：构造一个空的链表CreateList_f(void)初始条件：存在空的链表L。操作结果：头插入法实现链表的创建,并且返回头结点给L。CreateList_r(void)初始条件：存在空的链表L。操作结果：尾插入法实现链表的创建,并且返回头结点给L。LocateElem_L(L, &e)初始条件：存在空的链表L。操作结果：查询L第一个与e相等的数据元素，若存在，则返回它的位序，否则返回 0。NumberElem_L(L)初始条件：存在链表L。操作结果：计算并返回L数据元素的个数。Show_L(L)初始条件：存在非空链表L。操作结果：输出显示链表L。ListDel

6、ete_L(&L, i)初始条件：存在链表L非空，1=i=ListLength(L)。操作结果：在顺序链表L中删除第i个元素，返回其值。DeSameElem_L(&L)初始条件：存在非空顺序表L。操作结果：剔除L中的相同元素。MergeList_L(La, Lb, &Lc)初始条件：存在链表La,Lb，Lc。操作结果：把La，Lb合并为Lc。SortList_L(&L)初始条件：存在非空链表L。操作结果：将L按非递减顺序排序。ListInsert(&L,i,e)初始条件：链表L存在非空，并且1=i=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitStr(&S)操作结果：构造一

7、个空串CreateStr(&S,ch)初始条件：ch是字符串常量。串S已经构造。操作结果：生成一个其值等于ch 的串S。ShowStr(S)初始条件：存在非空串S。操作结果：输出显示串S。Index_KMP(S, T, pos, nextval)初始条件：串S和T存在，T是非空串，1=pos=SteLength(L),nextval是next修正值。操作结果：若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；若不则函数值为0。get_next(S, next)初始条件：串S存在且非空。操作结果：求串S的next值。get_nextval(S, nextval

8、)初始条件：串T存在且非非空。操作结果：求串S的nextval值。ADT HString三：详细设计#define MAXSIZE 100 typedef struct nodechar data;/数据域struct node *next;/指针域ListNode;/ListNode数据结构的定义void PrintMenu();/打印菜单 void Demo1();/演示一 void Demo1Menu();/演示一的目录int myinsert(char* s,char* t,int pos);/插入int mydelete(char* s,int len,int pos);/删除int

9、 mycombine(char* t1,char*t2,char* s);/合并int mycut(char* s,char* temp,int len,int pos);/顺序表切割void Demo2();/演示二 void Demo2Menu(); /演示二的菜单ListNode* CreateList();/只创建一个空链表，返回表头 void Insert(ListNode* head,char data,int pos);/插入一个元素void Append(ListNode* head,char data); /尾部追加一个元素 int Search(ListNode* head

10、,char data);/某个元素是否在链表中,返回所在位置index void DeleteByValue(ListNode* head,char data);/依据元素值删除元素 void DeleteByPos(ListNode* head,int pos);/依据元素索引删除元素 int ListLen(ListNode* head);/求链表长度 void DisplayList(ListNode* head);/打印链表 void ListCombine(ListNode *heada,ListNode *headb);/合并链表,返回合并后的链表的表头 void Demo3();

11、/演示三 int index_KMP(char *s,char *t,int pos,int *next); /模式匹配算法void get_next(char *t,int * next); /获取nextj数组的函数声明 void get_nextval(char *t,int *nextal) ;/获取nextvalj数组的函数声明int main()return 0;四：调试分析调试过程中对菜单处理很难，要做到程序健壮，就要对用户的错误输入进行处理，但是控制台应用程序要做到这一点很困难，一开始我是用char来接受用户输入的菜单指令，调试发现系统会见回车键和空格键当成字符输入。后来决定用

12、int来接受，当然这里也会有不太好的地方。所以还是应该使用图形应用程序比较好。五：测试结果程序启动后主界面顺序表演示界面顺序表插入演示顺序表删除演示链表查找演示链表插入演示链表合并演示串的模式匹配演示六：课程设计总结本次课程设计持续两周。通过这次的课程设计，让我无论是知识上还是能力上，都有所进步。一向惯于独立思考的自己学会了积极的同同学、朋友交流，取长补短，共同进步。提升了实践能力，编程能力。编写程序是件细心活,稍不留神就会出错,这就必须要求我们对待事情要认真!在编写程序的过程中,错误不断出现,不同的类型(如少写了一个符号,写错了字母,用错了函数等等)层出不穷,这考验我们待事细心,耐心,能不能

13、坚持到底,不能半途而废。通过这次的课程设计，我对数据结构课程的认识进一步加深。决定在暑假的时候把数据结构演示系统二，数据结构演示系统三完成。让自己对编程能力，算法分析设计能力有更大的进步。数据结构演示系统一，还有一些可以改进的地方，如，退出系统时，提示用户是否保存数据，增加文件读写功能，以及操作界面美化。七：参考文献1严蔚敏，吴伟民编著，数据结构（C语言版），北京；清华大学出版社，20052 严蔚敏，陈文博编著，数据结构及应用算法教程，北京；清华大学出版社，20063谭浩强.C语言程序设计（第二版）.北京:清华大学出版社,2007.10八：附录（带注释的源程序）#include #includ

14、e #include #define MAXSIZE 100 typedef struct nodechar data;struct node *next;ListNode;void PrintMenu();/打印菜单 void Demo1();/演示一 void Demo1Menu();int myinsert(char* s,char* t,int pos);int mydelete(char* s,int len,int pos);int mycombine(char* t1,char*t2,char* s);int mycut(char* s,char* temp,int len,in

15、t pos);/顺序表切割void Demo2();/演示二 void Demo2Menu(); ListNode* CreateList();/只创建一个空链表，返回表头 void Insert(ListNode* head,char data,int pos);/插入一个元素void Append(ListNode* head,char data); /尾部追加一个元素 int Search(ListNode* head,char data);/某个元素是否在链表中,返回所在位置index void DeleteByValue(ListNode* head,char data);/依据元素

16、值删除元素 void DeleteByPos(ListNode* head,int pos);/依据元素索引删除元素 int ListLen(ListNode* head);/求链表长度 void DisplayList(ListNode* head);/打印链表 void ListCombine(ListNode *heada,ListNode *headb);/合并链表,返回合并后的链表的表头 void Demo3();/演示三 int index_KMP(char *s,char *t,int pos,int *next); void get_next(char *t,int * nex

17、t); /获取nextj数组的函数声明 void get_nextval(char *t,int *nextal) ;/获取nextvalj数组的函数声明 int main()int select;while(1)PrintMenu(); scanf(%d,&select); switch(select) case 1:Demo1();break;case 2:Demo2();break;case 3:Demo3();break;case 4:exit(0);break;default:printf(输入有误，请重新输入！);break; system(pause); /每次循环后停一下，输出

18、提示信息，等待用户 system(pause);return 0;/打印菜单 void PrintMenu()system(cls);printf(tttt主菜单nn); printf(ttt1.顺序表的插入、删除、合并操作nn); printf(ttt2.链表的查找、删除、计数、输出以及合并nn); printf(ttt3.串的模式匹配、next、nextvalnn); printf(ttt4.退出nn); printf(tt请选择一项:); /演示一 void Demo1()char DemoStringMAXSIZE=abcdefgVERYCSU;/演示用原字符串 char OtherD

19、emoSMAXSIZE;char S2GetherMAXSIZE;int select;/选择的菜单项 char InsertString20;/插入的字符串 int len;/要删除的字符串长度 int pos;/在原字符串中的位置 while(1)system(cls);Demo1Menu(); scanf(%d,&select); switch(select) case 1:system(cls);printf(这是演示用字符串:%snn,DemoString);printf(请输入要插入的字符串，20字节以内:);scanf(%s,InsertString);printf(nn要将字符

20、串插入原字符串哪个位置？请输入正确的索引值:);scanf(%d,&pos);myinsert(DemoString,InsertString,pos);printf(nn插入操作后的字符串:%snn,DemoString); break;case 2:system(cls);printf(这是演示用字符串:%snn,DemoString);printf(要删除的字符串原字符串哪个位置？请输入正确的索引值:);scanf(%d,&pos);printf(nn请输入要删除的字符串长度:);scanf(%d,&len);mydelete(DemoString,len,pos);printf(nn插

21、入操作后的字符串:%snn,DemoString);break;case 3:system(cls);printf(这是演示用字符串:%snn,DemoString);printf(请输入一个字符串，用于演示合并:);scanf(%s,OtherDemoS);mycombine(DemoString,OtherDemoS,S2Gether);printf(你输入的是:%s,S2Gether);break;case 4:return;break;/回到上一级菜单，return就可以了 default:printf(输入有误，请重新输入！);break; system(pause); void D

22、emo1Menu()printf(ttt1.插入演示nn); printf(ttt2.删除演示nn); printf(ttt3.合并演示nn); printf(ttt4.回到上一级菜单nn); printf(tt请选择一项:); int mycut(char* s,char* temp,int len,int pos) if(checkcut(s,temp,len,pos)=0) temp0=0; return 0; int i=0; for(i=0;istrlen(s)|posstrlen(s),not = else return 1;int myinsert(char* s,char* t

23、,int pos) char temp1MAXSIZE; char temp2MAXSIZE; int state=checkInsert(s,t,pos); if(state=0) printf(操作未能成功！n); return 0; if(state=1) mycombine(s,t,s); if(state=2) mycut(s,temp1,pos,0); mycut(s,temp2,strlen(s)-pos,pos); mycombine(temp1,t,temp1); mycombine(temp1,temp2,s); /插入检查int checkInsert(char* s,c

24、har* t,int pos)/无法用char作为返回值类型吗？ int is=strlen(s); int it=strlen(t); if(posMAXSIZE|posMAXSIZE) return 0;/error if(posis) return 1;/append if(posis) return 2;/insert/合并int mycombine(char* t1,char*t2,char* s) if(checkCombine(t1,t2,s)=0) printf(操作未能成功！n); return 0; int m=strlen(t1); int n=strlen(t2); i

25、nt i; for(i=0;im;i+) si=t1i; for(i=0;i=MAXSIZE) return 0; else return 1;int mydelete(char* s,int len,int pos) char temp1MAXSIZE; char temp2MAXSIZE; if(checkDelete(s,len,pos)=0) printf(len或pos参数错误！n); return 0; mycut(s,temp1,pos,0); mycut(s,temp2,strlen(s)-pos-len,pos+len); mycombine(temp1,temp2,s);i

26、nt checkDelete(char* s,int len,int pos) if(len=0|strlen(s)len|posstrlen(s) return 0; else return 1;/演示二,链表的查找、删除、计数、输出以及合并void Demo2()int select;/选择的菜单项 int len;/要删除的字符串长度 int pos;/在原字符串中的位置 char SearchC,delValue,insertValue;int SearchCIndex,delIndex,insertIndex;char demoString=zhongnandaxue; char o

27、therListStrMAXSIZE; int i;ListNode* head=CreateList();ListNode* temphead=head;for(i=0;idata=demoStringi;tempNode-next=NULL;temphead-next=tempNode;temphead=temphead-next;while(1)system(cls);Demo2Menu(); scanf(%d,&select); switch(select) case 1:system(cls);printf(当前演示链表:);DisplayList(head);printf(nn请输

28、入要查找的字符:);scanf(%s,&SearchC);/这样接收一个字符，用%s就可以了 SearchCIndex=Search(head,SearchC);printf(Index=%dn,SearchCIndex); break;case 2:system(cls);printf(当前演示链表:);DisplayList(head);printf(nn请输入要删除的字符索引:);scanf(%d,&delIndex);DeleteByPos(head,delIndex);printf(n指定位置的字符已经删除，现在链表为:); DisplayList(head);printf(nn请输

29、入要删除的字符:);scanf(%s,&delValue);DeleteByValue(head,delValue);printf(n你输入的字符已经删除，现在链表为:);DisplayList(head);printf(n);break;case 3:system(cls);printf(当前演示链表:);DisplayList(head);printf(nn请输入要插入位置索引值:);scanf(%d,&insertIndex);printf(nn请输入要插入字符:);scanf(%s,&insertValue);Insert(head,insertValue,insertIndex);p

30、rintf(n你输入的字符已经插入，现在链表为:);DisplayList(head);printf(n);break;case 4:printf(请输入一个字符串:);scanf(%s,otherListStr);ListNode* otherhead=(ListNode *)malloc(sizeof(ListNode);ListNode* tempOther=otherhead;for(i=0;idata=otherListStri;tempNode-next=NULL;tempOther-next=tempNode;tempOther=tempOther-next; printf(你输

31、入的是:); DisplayList(otherhead);printf(nn); ListCombine(head,otherhead); printf(合并后的链表:); DisplayList(head);printf(nn);break;case 5:printf(当前链表中有%d个元素:,ListLen(head);DisplayList(head);printf(n);break; case 6:return;break;/回到上一级菜单，return就可以了 default:printf(输入有误，请重新输入！);break; system(pause); void Demo2M

32、enu()printf(ttt1.查找演示nn); printf(ttt2.删除演示nn); printf(ttt3.插入演示nn);printf(ttt4.合并演示nn);printf(ttt5.输出计数演示nn);printf(ttt6.回到上一级菜单nn); printf(tt请选择一项:); ListNode* CreateList()ListNode *head=(ListNode *)malloc(sizeof(ListNode);/head必须分配内存，这样才有head-next return head;/*返回头节点的指针*/插入一个元素 void Insert(ListNod

33、e* head,char data,int pos)ListNode* temp=head;int i=0;if(posListLen(head)Append(head,data);return; for(i=0,temp=head;inext,i+);/循环体内部误操作，只为了使temp到达指定pos ListNode* newnode=(ListNode*)malloc(sizeof(ListNode);newnode-data=data;newnode-next=temp-next;temp-next=newnode; /尾部追加一个元素void Append(ListNode* hea

34、d,char data)ListNode* temp=head;for(temp=head;temp-next!=NULL;temp=temp-next);ListNode* newnode=(ListNode*)malloc(sizeof(ListNode);newnode-data=data;newnode-next=NULL;temp-next=newnode; /求链表长度 int ListLen(ListNode* head)int count=0;ListNode* temp=head;for(count=0;temp-next!=NULL;temp=temp-next,count

35、+);/这是很精简的一种方式，C专家编程里面有的技巧 return count; /打印链表 void DisplayList(ListNode* head)ListNode* temp=head;while(temp-next!=NULL)printf(%c ,temp-next-data);temp=temp-next; /查找元素，返回元素第一次出现的位置索引int Search(ListNode* head,char data)ListNode* temp=head;int index=0;for(index=0;temp-next!=NULL&temp-next-data!=data

36、;temp=temp-next,index+);/循环体内不必操作，index已经递增if(index=ListLen(head)return -1;return index; /依据元素值删除元素 void DeleteByValue(ListNode* head,char data) ListNode* temp=head; ListNode* t; for(temp=head;temp-next!=NULL;temp=temp-next) if(temp-next-data=data) t=temp-next; temp-next=temp-next-next; free(t); /依据

37、元素索引删除元素 void DeleteByPos(ListNode* head,int pos)ListNode* temp=head,*t;if(pos=ListLen(head)|pos0)return 0;int i=0;for(i=0,temp=head;inext,i+);t=temp-next;temp-next=temp-next-next;free(t);/合并链表,返回合并后的链表的表头void ListCombine(ListNode *heada,ListNode *headb)ListNode* a=heada;ListNode* b=headb;for(b=headb;b-next!=NULL;b=b-next) for(a=heada;a-next!=NULL;a=a-next) if(a-next-data=b-ne