版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
成都理工大学数据结构课程设计报告计算机科学与技术一班王力立学号成都理工大学计算机科学与技术系数据结构课程设计设计说明书题目文章编辑集合运算起止日期:学生姓名班级成绩指导教师(签字)计算机科学与技术系
目录文章编辑 2一、 需求分析 21. 问题描述 22. 基本要求 23. 需求分析 24. 开发环境 3二、 概要设计 31. 流程图 32. 结构体构造 43. 设计思想 4三、 详细设计 41. 结构体构造 42. 函数构造 53. 重点函数分析 6四、 调试与测试 6五、 执行结果 7六、 源代码 8集合运算 18一、 需求分析 181. 问题描述 182. 基本要求 183. 需求分析 184. 开发环境 18二、 概要设计 191. 流程图 192. 结构体构造 193. 设计思想 19三、 详细设计 191. 结构体构造 192. 函数构造 203. 重点函数分析 21四、 调试与测试 22五、 关键源程序清单和执行结果 22六、 源代码 23
文章编辑需求分析问题描述输入一页文字,程序可以统计出文字、数字、空格的个数。基本要求静态存储一页文章,每行最多不超过80个字符,共N行,要求:(1)分别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章中出现的次数,并输出该次数;(3)删除某一子串,并将后面的字符前移。存储结构使用线性表,分别用几个子函数实现相应的功能。输入数据的形式和范围:可以输入大写、小写的英文字母、任何数字及标点符号。输出形式:(1)分行输出用户输入的各行字符;(2)分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"(3)输出删除某一字符串后的文章;需求分析(1)将文本转换为链表储存。(2)统计各个字符数量。(3)能够将该链表打印出来,并且执行删除某一节点的操作。(4)查找并匹配字符串,并得到对应的位置。开发环境系统环境:MicrosoftWindows®10专业版开发环境:MicrosoftVisualStudio2015开发平台:Win64开发语言:C++编译器:Intel®ParallelStudioXE2013硬件环境:CPU:IntelCorei7-4710MQ内存:16GB显示卡:NVIDIAGeForceGTX960M概要设计流程图结构体构造本程序采用的数据结构是单链表形式,在每个节点中存储一个字符,用指针的方式连接,形成链表,通过遍历的方式来打印和搜寻所需的字符。设计思想本程序旨在处理文字,重点即是先将文本转化为链表存储,然后用对应的函数遍历链表,得出字符的数值。使用KMP算法查找对应的字符串,并使用删除节点的方式完成字符串的删除操作。详细设计结构体构造//构造存储字符的结构体typedefstructlistNode{ charword; structlistNode*next;}wordList,*list;//构造储存字符数量的结构体typedefstruct{ intalpha; intdigit; intblank; intsum;}numStruct,*numNode;//构造储存字符位置的结构体typedefstructposNode{ intpos; structposNode*next;}posStruct,*posList;函数构造//线性链表初始化函数:链表头指针intwordList_init(list*res);//存储结构初始化函数:结构指针intnumNode_init(numNode*num);//字符位置链表初始化函数:结构指针intposNode_init(posList*posP);//字符位置链表增加与储存函数:头指针,插入字符intposNode_add(posList*posP,intposNum);//链表增加与储存函数:头指针,插入字符intwordList_add(list*res,charletter);//文本转换链表函数,同时计算文本中的字符类别和数量:链表头指针,结构体指针inttext_transform(list*res,numNode*num);//删除链表的某一节点:该节点的前一个节点的指针intwordList_delete(list*now);//链表打印:头指针voidwordList_print(list*res);//计算next数组的值:voidnextArray_make(charstrFind[],intnext[]);//KMP算法:intKMP(charstrRes[],charstrFind[],intnext[]);//KMP统计出现次数intstringRepeat_count(charstrRes[],charstrFind[],posList*posL);//字符串查询:链表头指针,结构voidstring_search(list*res,numNode*num);//字符串删除函数:链表头指针,结构voidstring_delete(list*res,numNode*num);//菜单函数voidmenu();重点函数分析在这个程序当中,个人认为最重要的部分就是KMP算法的实现,这个算法的搜索速度极其快速,但是因为不太容易理解,所以实现上有些困难。KMP算法相对于普通的搜索算法,最大的优势就是使用了一个next数组来帮助算法程序跳转,通过减少比对时间来优化效率。这个算法的核心也就是是next数组的求法。Next数组保证每一次比对完成以后向后跳转的具体位置。而KMP算法的核心即是计算字符串string,每一个位置之前的字符串的前面部分和后部分的公共部分的最大长度(不包括字符串本身,否则最大长度始终是字符串本身)。这样构造的算法可以在最大程度上向后跳转节约时间。调试与测试在调试本程序时,为了保证输入输出的值的正确,基本思路是在每个函数写好以后对该函数的效果进行测试,保证该函数能正常运行并得出对应正确的结果,并且对可能会影响到的指针的值进行处理,保证程序的健壮性。如果程序出现了致命的错误,我就会打开断点调试功能筛查是哪个地方出了问题,然后进行修改。执行结果本程序所需要的文章以文本形式放在程序同目录下的input_text.txt内。打开程序时会自动加载转换本文本,并且不会对原文本进行更改。以下是演示图片。源代码#include<stdio.h>#include<stdlib.h>#include<string.h>//构造存储字符的结构体typedefstructlistNode{ charword; structlistNode*next;}wordList,*list;//构造储存字符数量的结构体typedefstruct{ intalpha; intdigit; intblank; intsum;}numStruct,*numNode;//构造储存字符位置的结构体typedefstructposNode{ intpos; structposNode*next;}posStruct,*posList;//线性链表初始化函数:链表头指针intwordList_init(list*res);//存储结构初始化函数:结构指针intnumNode_init(numNode*num);//字符位置链表初始化函数:结构指针intposNode_init(posList*posP);//字符位置链表增加与储存函数:头指针,插入字符intposNode_add(posList*posP,intposNum);//链表增加与储存函数:头指针,插入字符intwordList_add(list*res,charletter);//文本转换链表函数,同时计算文本中的字符类别和数量:链表头指针,结构体指针inttext_transform(list*res,numNode*num);//删除链表的某一节点:该节点的前一个节点的指针intwordList_delete(list*now);//链表打印:头指针voidwordList_print(list*res);//计算next数组的值:voidnextArray_make(charstrFind[],intnext[]);//KMP算法:intKMP(charstrRes[],charstrFind[],intnext[]);//KMP统计出现次数intstringRepeat_count(charstrRes[],charstrFind[],posList*posL);//字符串查询:链表头指针,结构voidstring_search(list*res,numNode*num);//字符串删除函数:链表头指针,结构voidstring_delete(list*res,numNode*num);//菜单函数voidmenu();//主函数intmain(void){ menu(); return0;}//线性链表初始化函数:链表头指针intwordList_init(list*res){ (*res)=(list)malloc(sizeof(wordList)); if((*res)){ (*res)->next=NULL; (*res)->word=''; return1; }else{ printf("空间分配失败,请重试。\n"); return0; }}//存储结构初始化函数:结构指针intnumNode_init(numNode*num){ (*num)=(numNode)malloc(sizeof(numStruct)); if((*num)){ (*num)->alpha=0; (*num)->digit=0; (*num)->blank=0; (*num)->sum=0; return1; }else{ printf("空间分配失败,请重试。\n"); return0; }}//字符位置链表初始化函数:结构指针intposNode_init(posList*posP){ (*posP)=(posList)malloc(sizeof(posStruct)); if((*posP)){ (*posP)->next=NULL; (*posP)->pos=0; }else{ return0; }}//字符位置链表增加与储存函数:头指针,插入字符intposNode_add(posList*posP,intposNum){ while((*posP)->next){ (*posP)=(*posP)->next; } //分配空间 (*posP)->next=(posList)malloc(sizeof(posStruct)); if((*posP)->next){ (*posP)=(*posP)->next; (*posP)->next=NULL; (*posP)->pos=posNum; return1; }else{ printf("空间分配失败,请重试。\n"); return0; }}//链表增加与储存函数:头指针,插入字符intwordList_add(list*res,charletter){ while((*res)->next){ (*res)=(*res)->next; } //分配空间 (*res)->next=(list)malloc(sizeof(wordList)); if((*res)->next){ (*res)=(*res)->next; (*res)->next=NULL; (*res)->word=letter; return1; }else{ printf("空间分配失败,请重试。\n"); return0; }}//文本转换链表函数,同时计算文本中的字符类别和数量:链表头指针,结构体指针inttext_transform(list*res,numNode*num){ //文件操作,打开文件 FILE*fp; fp=fopen("input_text.txt","r"); charletter; //初始化链表 wordList_init(&(*res)); numNode_init(&(*num)); //重新声明变量,操作resNow来构建链表 listresNow=(*res); //循环将文本读入线性表中 while((letter=getc(fp))!=EOF){ wordList_add(&resNow,letter); if(isalpha(letter)) (*num)->alpha++;//求字母数 elseif(isdigit(letter)) (*num)->digit++;//求数字个数 elseif(letter=='') (*num)->blank++;//求空格数 (*num)->sum++; } //关闭文件 fclose(fp);}//删除链表的某一节点:该节点的前一个节点的指针intwordList_delete(list*now){ listtemp=(*now)->next; (*now)->next=temp->next; free(temp); return1;}//链表打印:头指针voidwordList_print(list*res){ listtemp=(*res); while(temp->next){ temp=temp->next; printf("%c",temp->word); }}//计算next数组的值:voidnextArray_make(charstrFind[],intnext[]){ inti,j; intlen=strlen(strFind);next[0]=-1; //next[0]放上-1i=0; //指向字符串每个字符的指针j=-1;while(i<len){//没有到达结尾的话if(j==-1||strFind[i]==strFind[j]){//如果是第一个字符或遇到相同的字符i++; j++; next[i]=j;}elsej=next[j];}//for(i=0;i<len;i++){//输出next[]值//printf("%d",next[i]);//}}//KMP算法:intKMP(charstrRes[],charstrFind[],intnext[]){inti,j;i=j=0; intlenRes=strlen(strRes); intlenFind=strlen(strFind);while(i<lenRes&&j<lenFind){if(j==-1||strRes[i]==strFind[j]){i++; j++;}elsej=next[j];}if(j==lenFind) returni-lenFind;else return-1;}//KMP统计出现次数intstringRepeat_count(charstrRes[],charstrFind[],posList*posL){ intlenRes=strlen(strRes); intlenFind=strlen(strFind); intlenTemp=0; intrepeatCount=0; char*strTemp; intnext[lenRes]; nextArray_make(strFind,next); intpos=KMP(strRes,strFind,next); if(pos==-1){ return0; } strTemp=&(strRes[pos+lenFind]); lenTemp=strlen(strTemp); repeatCount=1; printf("\n第%d次在第%d个位置出现。\n",repeatCount,(pos+1)); intposCount=pos+1; posListtempPOS=(*posL); posNode_add(&tempPOS,posCount); while(lenTemp>lenFind){ intnext[lenTemp]; nextArray_make(strFind,next); intpos=KMP(strTemp,strFind,next); if(pos==-1){ break; }else{ strTemp=&(strTemp[pos+lenFind]); lenTemp=strlen(strTemp); repeatCount++; posCount+=(pos+lenFind); printf("\n第%d在第%d个位置出现。\n",repeatCount,posCount); posNode_add(&tempPOS,posCount); } } returnrepeatCount;}//字符串查询:链表头指针,结构voidstring_search(list*res,numNode*num){ printf("\n请输入您想要查找的字符串:\n"); //获得最大长度为文本文件大小的字符串数组 charstrFind[(*num)->sum]; scanf("%s",&strFind); //将链表转换为数组处理 charstrRes[(*num)->sum]; listtemp=(*res); inti=0; while(temp->next){ temp=temp->next; strRes[i]=temp->word; i++; } posListpos; posNode_init(&pos); intrepeatCount=stringRepeat_count(strRes,strFind,&pos); if(repeatCount){ printf("\n该字符串“%s”在本文本中出现了%d次。",strFind,repeatCount); }else{ printf("没有搜索到该文本。"); }}//字符串删除函数:链表头指针,结构voidstring_delete(list*res,numNode*num){ printf("\n请输入您想要删除的字符串:\n"); //获得最大长度为文本文件大小的字符串数组 charstrFind[(*num)->sum]; scanf("%s",&strFind); //将链表转换为数组处理 charstrRes[(*num)->sum]; listtemp=(*res); inti=0; while(temp->next){ temp=temp->next; strRes[i]=temp->word; i++; } posListpos; posNode_init(&pos); intrepeatCount=stringRepeat_count(strRes,strFind,&pos); if(!repeatCount){ printf("没有搜索到该文本。"); return; } printf("\n该字符串“%s”在本文本中出现了%d次。\n",strFind,repeatCount); printf("\n您确认删除这个字符串吗?\n\n回复数字1来确认此操作。\n"); i=0; scanf("%d",&i); if(i==1){ intcount=0; listtemp=(*res); pos=pos->next; while(temp->next&&pos){ intlenDelete=strlen(strFind); count++; if(count==pos->pos){ count+=lenDelete; while(lenDelete){ wordList_delete(&temp); lenDelete--; } pos=pos->next; } temp=temp->next; } printf("\n\n删除成功,现文本如下:\n\n"); wordList_print(&(*res)); } return;}//菜单函数voidmenu(){ //声明链表头指针 listres; //声明数量结构体 numNodenum; //将文本转换为链表保存并统计字符数量 text_transform(&res,&num); intfunChoose; while(1){ printf("\n请输入序号来选择您需要的功能:\n\n"); printf("1.显示文本\n\n2.显示字符统计情况。\n\n3.查询字符串\n\n4.删除字符串\n\n"); scanf("%d",&funChoose); system("cls"); if(funChoose==1){ wordList_print(&res); }elseif(funChoose==2){ printf("\n字母数:%d\n\n数字数:%d\n\n空格数:%d\n\n字符总数:%d\n",num->alpha,num->digit,num->blank,num->sum); }elseif(funChoose==3){ string_search(&res,&num); }elseif(funChoose==4){ string_delete(&res,&num); }else{ printf("\n请输入正确的选择数字。"); } printf("\n\n\n"); system("pause"); system("cls"); }}
集合运算需求分析问题描述使用链表来表示集合,完成集合的合并,求交集等操作。基本要求(1)用链表表示两个集合(2)对两个集合分别从小到大排序(3)两个集合合并成另一个新集合,如数值相同,合并为一个数据项(4)求出两个集合的交集建立一个新的集合。需求分析(1)将该集合转换为链表储存。(2)分别对两个集合进行排序操作。(3)合并两个集合,排序并合并相同数据项。(4)打印出交集。开发环境系统环境:MicrosoftWindows®10专业版开发环境:MicrosoftVisualStudio2015开发平台:Win64开发语言:C++编译器:Intel®ParallelStudioXE2013硬件环境:CPU:IntelCorei7-4710MQ内存:16GB显示卡:NVIDIAGeForceGTX960M概要设计流程图结构体构造本程序采用的数据结构是单链表形式,在每个节点中存储集合中的一个元素,用指针的方式连接,形成链表,通过遍历的方式来排序和打印元素。设计思想本程序旨在集合运算,所以一开始便构造两个链表分别存储两个集合,并进行分别排序。最后使用总处理函数得到交集和并集,具体设计在第三节的重点函数分析中。详细设计结构体构造//构造结构体储存数据typedefstructnode{ intnum;structnode*next;}groupList,*list;函数构造//链表初始化函数:链表头指针intgroup_init(list*res);//链表增加函数:链表头指针,值intgroup_add(list*res,intnum);//删除该节点的下个节点:头指针voidgroup_delete(list*res);//链表打印函数:头指针voidgroup_print(list*res);//获取集合:头指针,集合元素总数voidgroup_get(list*res,intnumSum);//链表的冒泡排序:头指针voidgroup_BubbleSort(list*res);//链表的总处理:四个头指针//在这个函数中调用了冒泡排序函数和删除节点函数voidgroup_process(list*groupA,list*groupB,list*groupUnion,list*groupInter);//菜单函数voidmenu();重点函数分析本程序的重点在于链表的总处理函数,在此附上代码和说明。因为本程序较为简单,所以没有特意重新构造一个链表来分别保存并集和交集。这个函数的基本思路是讲这两个链表合在一起进行排序,然后遍历这个总链表。当遍历到两次出现同一个值时,证明这个值在两个链表中均出现过。则将其放到新构造的交集链表中。而当出现了三次时,则删除。由此得到的遍历后的链表即为并集的集合。//链表的总处理:四个头指针voidgroup_process(list*groupA,list*groupB,list*groupUnion,list*groupInter){lista,b,c,temp;c=(*groupInter);//将AB链表合在一起temp=(*groupA);while(temp->next){temp=temp->next;}temp->next=(*groupB)->next;temp=(*groupA);//排序总链表group_BubbleSort(&temp);//总链表中的重复数据计入交集链表中while(temp->next){b=temp;temp=temp->next;if(a=temp->next){if(a->num==temp->num){if(!(*groupInter)->next){group_add(&c,a->num);}if(a->num!=c->num){group_add(&c,a->num);}//删除重复数据group_delete(&temp);temp=b;}}}//剩下的即是合集(*groupUnion)=(*groupA);}调试与测试在调试本程序时,为了保证输入输出的值的正确,基本思路是在每个函数写好以后对该函数的效果进行测试,保证该函数能正常运行并得出对应正确的结果,并且对可能会影响到的指针的值进行处理,保证程序的健壮性。如果程序出现了致命的错误,我就会打开断点调试功能筛查是哪个地方出了问题,然后进行修改。关键源程序清单和执行结果源代码#include<stdio.h>#include<stdlib.h>//构造结构体储存数据typedefstructnode{ intnum;structnode*next;}groupList,*list;//链表初始化函数:链表头指针intgroup_init(list*res);//链表增加函数:链表头指针,值intgroup_add(list*res,intnum);//删除该节点的下个节点:头指针voidgroup_delete(list*res);//链表打印函数:头指针voidgroup_print(list*res);//获取集合:头指针,集合元素总数voidgroup_get(list*res,intnumSum);//链表的冒泡排序:头指针voidgroup_BubbleSort(list*res);//链表的总处理:四个头指针voidgroup_process(list*groupA,list*groupB,list*groupUnion,list*groupInter);//菜单函数voidmenu();intmain(void){ menu(); return0;}//链表初始化函数:链表头指针intgroup_init(list*res){//分配空间(*res)=(list)malloc(sizeof(groupList));if((*res)){(*res)->next=NULL;(*res)->num='0';return1;}else{return0;}}//链表增加函数:链表头指针,值intgroup_add(list*res,intnum){//判断当前指针是否指向最后一个节点while((*res)->next){(*res)=(*res)->next;printf("指针有误。");}//分配空间(*res)->next=(list)malloc(sizeof(groupList));if((*res)->next){(*res)=(*res)->next;(*res)->next=NULL;(*res)->num=num;return1;}else{return0;}}//删除该节点的下个节点:头指针voidgroup_delete(list*res){listtemp=(*res)->next;if(temp->next){(*res)->next=temp->next;free(temp);}}//链表打印函数:头指针voidgroup_print(list*res){//循环打印项listtemp=(*res);while(temp->next){temp=temp->next;printf("%d",temp->num);}}//获取集合:头指针,集合元素总数voidgroup_get(list*res,intnumSum){inti=1;listtemp=(*res);inttempNum;while(i<=numSum){printf("请输入第%d个元素:\n",i);scanf("%d",&tempNum);group_add(&temp,tempNum);i++;}printf("\n该集合录入完成!\n");}//链表的冒泡排序:头指针voidgroup_BubbleSort(list*res){ listn,m; m=(*res)->next; n=(*res)->next; for(m=(*res)->next;m;m=m->next){for(n=m->next;n;n=n->next){if((m->num)>(n->num)){inttemp=m->num; m->num=n->num; n->num=temp;}}}}//链表的总处理:四个头指针voidgroup_process(list*groupA,list*groupB,list*groupUnion,list*groupInter){lista,b,c,temp;c=(*groupInter);//将AB链表合在一起temp=(*groupA);while(temp->next){temp=temp->next;}temp->next=(*groupB)->next;temp=(*groupA);//排序总链表group_BubbleSort(&temp);//总链表中的重复数据计入交集链表中while(temp->next){b=temp;te
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 单片机原理及应用(C51版)教案第7章 单片机并行扩展技术-16比9
- 广东省惠州市2023-2024学年九年级上学期第一次月考数学试题(无答案)
- 苏教版八年级生物上册第7单元第十九章生态系统第二节生态系统中的能量流动和物质循环课件
- 全国赛课一等奖英语七年级上册(人教2024年新编)《Unit 1 Section A Pronunciation》课件
- 2024-2025学年版块12 简单机械 专题12-1 杠杆 (含答案) 初中物理尖子生自主招生培优讲义83讲
- DB1410T 080-2024旱地小麦低温灾害防控技术规程
- 内蒙古呼和浩特市2024年中考数学试卷(含答案)
- 陕西省2019年中考历史真题试卷(含答案)
- 化 学物质构成的奥秘课件-2024-2025学年九年级化学人教版(2024)上册
- 小班三角形的教学课件教学课件教学
- 服装车间标准工时 工价 各类型工序价库汇总xls
- 《绝境求生·核城裂变》纪录片观后感
- 车间加工生产记录表格模板
- Creo原创教程(六) top-down-design之骨架模型 球阀建模举例
- 溢流面混凝土施工方案选择及施工方法浅谈
- (完整word版)化学实验室仪器药品清单
- 医院非产科孕情管理和三病检测工作方案
- 物品出入库明细表格
- 柔性制造技术的五个类型
- 基于stm32的低频数字相位测量仪
- 第四章 造纸化学
评论
0/150
提交评论