数据结构课程设计报告.docx

数据结构课程设计报告数据结构演示系统1班级： 姓名： 学号： 完成日期：7月1. 需求分析设计一个数据结构演示系统，要求：（1） 顺序表的插入、删除和合并等基本操作。（2） 利用插入运算建立链表；实现链表的查找、删除、计数、输出等功能以及有序链表的合并。（3） 串的模式匹配（包括求next和nextval的值）。顺序表和链表演示中输入值必须为int类型。串的演示中输入必须为char类型。系统能够完成对顺序表链表以及串的基本操作。2. 概要设计用到的抽象数据类型的定义有：ADT List数据对象：D=ai|aiElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList_Sq(& L)操作结果：构造一个空的线性表ListInsert(&L,I,e)初始条件：线性表L存在，并且1=i=ListLength(L)+1。操作结果：在L中的第i个位置之前插入新的数据元素e，L的表长加1。Print_Sq(&L)初始条件：线性表L存在。操作结果：输出显示线性表L。Creat_Sq(&La, &Lb)初始条件：存在空的线性表La,Lb,。操作结果：向La，Lb中输入元素。MergeList_Sq(La, Lb, &Lc)初始条件：存在线性表La,Lb，Lc。操作结果：把LaLb合并为Lc。ListDelete_Sq(&L, i, &e)初始条件：存在线性表L非空，1=i=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：StrAssign(&T,S)初始条件：char是字符串常量。操作结果：生成一个其值等于chars的串T。Index_KMP(S, T, pos, nextval)初始条件：串S和T存在，T是非空串，1=pos=SteLength(L),nextval是next修正值。操作结果：若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；若不则函数值为0.get_next(T, next)初始条件：串T存在。操作结果：求串T的next值。get_nextval(T, nextval)初始条件：串T存在。操作结果：求串T的nextval值。ADT String系统分为两个层次，主函数main，以及每个子菜单main1，main2，main3，分别对应顺序表，链表，串的相关操作。3. 详细设计头文件包括：#include#include#include #include#include 顺序表的存储结构：typedef structElemType *elem;int length;int listsize;SqList; 链表的存储结构：typedef struct LNode int data; / 数据域 struct LNode *next; / 指针域LNode,*LinkList; 串的存储结构：typedef unsigned char SStringMAXSTRLEN+1;/串的定义系统的流程图：数据结构演示系统1主函数main顺序表的相关操作main1链表的相关操作main2串的模式匹配Main3建立顺表La和Lb，并合并成Lc建立链表La和Lb。输入主串S和模式串T，并求T的next和nextavl值输入POS值，进行模式匹配进行插入操作进行删除操作合并插入删除查找各个子函数：Print_Sq：运用for语句，按顺序输出顺序表中的每个值。InitList_Sq：动态开辟一个空间来构建一个空的顺序表。ListInsert_Sq：在顺序线性表L的第i个元素之前插入新的元素e，i和之后的值向后移动以为，表长加1.用*(p+1) = *p实现右移。Creat_Sq：构表，其中调用了InitList_Sq，ListInsert_Sq，Print_Sq等函数。MergeList_Sq：已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。对LA和LB中的值进行一一对比，小的先存入Lc中，最后剩下的连接到表尾。ListDelete_Sq：在顺序线性表L中删除第i个元素，并用e返回其值。i之后的元素左移，由*(p-1) = *p实现。CreateList_L：动态分配空间创建链表，并输入值。CreateList_L：遍历链表，并输出链表的值。MergeList_L：合并LA和LB链表为LC。比较La和Lb的值，先把比较小的存入Lc，最后剩下的连接到表尾。ListInsert_L：在第i个元素插入一个元素e。循环语句寻找i的位置，然后开辟一个结点，由s-data=e;s-next=p-next;p-next=s;实现插入。ListDelete_L：由q=p-next;p-next=q-next;e=q-data;free（q）来实现。Listsearch_L：查找，给定数字，设置计数器j，从表头开始比较，若有相等值，返回此时的j值，若j表长，返回0.get_next：求next值函数。get_nextval：求nextval函数。Index_KMP：按KMP算法求解模式匹配问题。4. 调试分析（1）.一开始没有构思好，一味的去写函数，最后把子函数写好后发现很难联系起来，不好调用。所以设计时最好从主函数出发，再根据主函数的需求来编写子函数，这样可以很好的调用函数。（2）.在写程序时，指针的指向是一个很烦恼的问题，不知道什么地方该加1还是加2，转来转去，不知道指向了。这个问题很让人头疼，需要仔细仔细再仔细。（3）.在完成程序之后，已经调试成功，但是依然出现内存不能read的问题如图最后发现是Status InitList_Sq(SqList L)应该改为Status InitList_Sq(SqList &L)这样就可以给予L不同的存储空间了。很细微的一个错误，找了很久才发现。调试结果：主界面：各个子菜单：5. 测试结果（1）.对顺序表的测试La:1 2 3 4 5Lb：6 7（2）.对链表的测试La:4 5 6 7Lb:8 9(3).串的模式匹配S：asdfghjkT:ghj6. 课程设计总结(1)调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析；刚写出代码时，调试显示出100多行错误。这说明我C语言有待加强。程序中我并没有添加特别的结束语句，在每个子函数main1 main2 main3中如果按不是提示的几个键都会返回main，所以利用这点我就设计按5键返回上一个目录，虽然是按1234之外的键都有这个功能。在各种错误中，我印象最深的是输入第二个顺序表时不能内存read的问题。由于我采用插入建表的方法Status InitList_Sq(SqList L)，Status InitList_Sq(SqList L)函数在分配地址时只能给出一个地址，无法为第二个顺序表分配，所以第二次调用的时候就出了就出现了内存不能read的错误。解决办法Status InitList_Sq(SqList L)改为Status InitList_Sq(SqList &L)。(2)算法的时间复杂性和可能的改进设想。算法的效率：Listsearch_L(LinkList L,int n)/查找 在查找过程中每次都要重新从头开始消耗时间多。改进设想：建立哈希函数，通过查找关键字直接查找到需要的数据。在这次课程设计中理解了很多，特别上课时有些地方无法理解的通过实战也有了一定了解，但是这还不够，我还会在暑假中努力学习，要达到100%理解。7. 参考文献数据结构（c语言版）（清华大学出版社）C语言程序审计（第二版）（中国铁道出版社）8. 附录 #include#include#include#define TRUE 1#define FALSE 0#define YES 1#define NO 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define MAXSIZE 100#include#includetypedef int Status;typedef int ElemType ;#define LIST_INIT_SIZE 100#define LISTINCERMENT 10#define MAXSTRLEN 64typedef structElemType *elem;int length;int listsize;SqList;typedef struct LNodeint data; / 数据域struct LNode *next; / 指针域LNode,*LinkList;typedef unsigned char SStringMAXSTRLEN+1;/串的定义 void Print_Sq(SqList &L)int i;for(i=0;iL.length;i+)printf(%d ,L.elemi);printf(n); Status InitList_Sq(SqList &L)/构造空的顺序表LaL.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;Status ListInsert_Sq(SqList &L, int i, ElemType e)/ 在顺序线性表L的第i个元素之前插入新的元素eElemType *p;if (i L.length+1) return ERROR;if (L.length = L.listsize)ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCERMENT)*sizeof (ElemType);if (!newbase) return ERROR;L.elem = newbase;L.listsize += LISTINCERMENT;ElemType *q = &(L.elemi-1);for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p;*q = e;+L.length;return OK;Status Creat_Sq(SqList &La,SqList &Lb)/构表 int i,n1,n2,e,a;system(pause);printf(请输入La元素个数：n);scanf(%d,&n1);if(n1100) return 0;printf(请输入要在该顺序表存放的值n); if(InitList_Sq(La) for(i=1;i100) return 0;printf(请输入要在该顺序表存放的值n); if(InitList_Sq(Lb)for(i=1;i=n2;i+)- 10 -scanf(%d,&a);ListInsert_Sq(Lb,i,a);printf(Lb顺序表输出为:); Print_Sq(Lb); printf(n); system(CLS);printf(La顺序表输出为:); Print_Sq(La); printf(n);printf(Lb顺序表输出为:); Print_Sq(Lb); printf(n); void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa = La.elem; pb = Lb.elem;Lc.listsize = Lc.length = La.length+Lb.length;pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType);if (!Lc.elem)exit(OVERFLOW); / 存储分配失败pa_last = La.elem+La.length-1;pb_last = Lb.elem+Lb.length-1;while (pa = pa_last & pb = pb_last) / 归并if (*pa = *pb) *pc+ = *pa+;else *pc+ = *pb+;while (pa = pa_last) *pc+ = *pa+; / 插入La的剩余元素while (pb = pb_last) *pc+ = *pb+; / 插入Lb的剩余元素Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表L中删除第i个元素，并用e返回其值ElemType *p, *q;if (iL.length) return ERROR;p = &(L.elemi-1);e = *p;q = L.elem+L.length-1;for (+p; pLc.length+1) printf(n输入错误，请重新输入n); scanf(%d%d,&i,&e); ListInsert_Sq(Lc,i,e);/插入结点。 printf(插入后的顺序表为：); Print_Sq(Lc); printf(nnn); goto add; case 3: printf(请选择要删除的位置：); scanf(%d,&i); while(i-1Lc.length-1)printf(n输入错误，请重新输入n); scanf(%d,&i); ListDelete_Sq(Lc,i,e); /删除结点。 printf(删除后的链表为:); Print_Sq(Lc); printf(nnn); goto add;default: break; /创建的带头结点的单链表。void CreateList_L(LinkList &L,int &n)L=(LinkList)malloc(sizeof (LNode);/建立一个空链表L。 if(!L) exit(OVERFLOW); else L-next=NULL; int i=0; LinkList p,q; printf(请输入要在该链表存放的值:n); q=L;for(i=0;idata); p-next=q-next; q-next=p; q=p;int TraverseList_L(LinkList L) /遍历单链表 LinkList p; p=L-next; while(p) printf(-%d,p-data); p=p-next; return OK;LinkList MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)/合并LA和LB链表为LC。 LNode *p,*q,*pc; p=LA-next;/p指向尾结点q=LB-next;LC=pc=LA;/用La的头结点作为Lc的头结点while(p&q)if(p-datadata) pc-next=p;pc=p;p=p-next;elsepc-next=q;pc=q;q=q-next; pc-next=p?p:q; free(LB);return(LA); LinkList ListInsert_L(LinkList &L,int i,int e)/在第i个元素插入一个元素e。LNode *p,*s;int j; printf(请输入要插入的结点位置：);scanf(%d,&i);p=L;j=0;while(p&jnext;+j; /寻找第i-1个结点。if(!p|ji-1)printf(您插入的位置不合法，不合法);return 0; /判断i的值是否合法s=(LinkList)malloc(sizeof(LNode);/开辟一个新结点 if(!s) exit(OVERFLOW);printf(请输入要在该结点存放的数值 :); scanf(%d,&e);s-data=e;s-next=p-next;p-next=s;return(L);LinkList ListDelete_L(LinkList &L,int i,int e)/删除结点 LNode *p,*q;printf(请输入要删除的结点的位置:);scanf(%d,&i);p=L;int j=0;while(p-next & jnext;+j;if(!(p-next)|ji-1)printf(您删除的位置不合法，不合法); return 0;q=p-next;p-next=q-next;e=q-data;LinkList Listsearch_L(LinkList L,int n)/查找 LNode *p,*q; int k=0; p=L-next;/头结点赋给p int number=1; printf(请输入要查找的数:); scanf(%d,&n); while(p-data!=n)/从头结点开始往下找，直到找到和n相同的元素值 if(p-next=NULL) k=1; break; p=p-next; +number; if(k=0) printf(要查找的数存在，位置是第%d个值n,number); else printf(要查找的数不存在!); return(L);int main2() int n,i,e,m,j; LinkList LA,LB,LC;LNode *MergeList;system(pause);printf(请输入要定义的La链表长度:n);/输入链表LA值。 scanf(%d,&n); if(n100) return 0; CreateList_L(LA, n); printf(LA链表输出为:); TraverseList_L(LA); printf(n); printf(请输入要定义的LB链表长度:n);/输入链表LB的值。 scanf(%d,&n); if(n100) return 0; CreateList_L(LB, n); printf(LB链表输出为:); TraverseList_L(LB); printf(n); system(CLS); printf(LA链表输出为:); TraverseList_L(LA); printf(n); printf(LB链表输出为:); TraverseList_L(LB); printf(n); add:printf(1.对链表进行合并操作n);printf(2.对链表进行插入操作n);printf(3.对链表进行删除操作n);printf(4.对链表进行查找操作n);printf(按5返回); printf(n);printf(请输入数字键进行操作n);scanf(%d,&m);printf(n);switch(m)case 1: printf(LA和LB合并后LC链表输出为:);/输出LC MergeList_L(LA,LB,LC); TraverseList_L(LA); printf(n); goto add;case 2: ListInsert_L(LA,i,e);/插入结点。 printf(插入后的链表为：); TraverseList_L(LA); printf(nnn); goto add;case 3: ListDelete_L(LA,i,e); /删除结点。 printf(删除后的链表为:); TraverseList_L(LA); printf(nnn); goto add;case 4:Listsearch_L(LA,n); /查找结点。 goto add;default: break;Status StrAssign(SString &T,char *chars)/生成一个其值等于串常量chars的 串T int i,len;len = strlen(chars);T0 = len;for(i=1; i = len; i+)Ti = charsi-1;return OK;void get_next(SString T, int next)/求next函数值 int i=1,j=0,k;next1 = 0;while(iT0)if(j = 0 | Ti = Tj)+i; +j; nexti = j;else j = nextj;for(k=1; k = i; k+) printf(%4d,nextk);void get_nextval(SString T, int nextval)/求nextval函数值 int i=1,j=0,k;nextval1 = 0;while(iT0)if(j = 0 | Ti = Tj)+i; +j;if(Ti!=Tj) nextvali = j;else nextvali =