数据结构课程设计文章编辑集合运算.doc

成都理工大学数据结构 课程设计报告计算机科学与技术一班 王力立学 号 成都理工大学计算机科学与技术系数据结构课程设计设计说明书题目文章编辑 集合运算起止日期： 学生姓名班级成绩指导教师(签字) 计算机科学与技术系 目录文章编辑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文章编辑一、 需求分析1. 问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。2. 基本要求静态存储一页文章，每行最多不超过80个字符，共N行，要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能。输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；3. 需求分析（1）将文本转换为链表储存。（2）统计各个字符数量。（3）能够将该链表打印出来，并且执行删除某一节点的操作。（4）查找并匹配字符串，并得到对应的位置。4. 开发环境系统环境：Microsoft Windows10 专业版开发环境：Microsoft Visual Studio 2015开发平台：Win64开发语言：C+编译器：Intel Parallel Studio XE 2013硬件环境：（1） CPU：Intel Core i7-4710MQ（2） 内存：16GB（3） 显示卡：NVIDIA GeForce GTX960M二、 概要设计1. 流程图2. 结构体构造本程序采用的数据结构是单链表形式，在每个节点中存储一个字符，用指针的方式连接，形成链表，通过遍历的方式来打印和搜寻所需的字符。3. 设计思想本程序旨在处理文字，重点即是先将文本转化为链表存储，然后用对应的函数遍历链表，得出字符的数值。使用KMP算法查找对应的字符串，并使用删除节点的方式完成字符串的删除操作。三、 详细设计1. 结构体构造/ 构造存储字符的结构体 typedef struct listNodechar word;struct listNode *next; wordList, *list;/ 构造储存字符数量的结构体typedef struct int alpha;int digit;int blank;int sum; numStruct, *numNode;/ 构造储存字符位置的结构体typedef struct posNodeint pos;struct posNode *next; posStruct, *posList;2. 函数构造/ 线性链表初始化函数：链表头指针int wordList_init( list *res);/ 存储结构初始化函数：结构指针int numNode_init( numNode *num);/ 字符位置链表初始化函数：结构指针int posNode_init( posList *posP);/ 字符位置链表增加与储存函数：头指针，插入字符int posNode_add( posList *posP, int posNum);/ 链表增加与储存函数：头指针，插入字符int wordList_add( list *res, char letter);/ 文本转换链表函数，同时计算文本中的字符类别和数量：链表头指针，结构体指针int text_transform( list *res, numNode *num);/ 删除链表的某一节点：该节点的前一个节点的指针int wordList_delete( list *now);/ 链表打印：头指针void wordList_print( list *res);/ 计算next数组的值：void nextArray_make( char strFind, int next);/ KMP算法：int KMP( char strRes, char strFind, int next);/ KMP统计出现次数int stringRepeat_count( char strRes, char strFind, posList *posL);/ 字符串查询：链表头指针，结构void string_search( list *res, numNode *num);/ 字符串删除函数：链表头指针，结构void string_delete( list *res, numNode *num);/ 菜单函数void menu();3. 重点函数分析在这个程序当中，个人认为最重要的部分就是KMP算法的实现，这个算法的搜索速度极其快速，但是因为不太容易理解，所以实现上有些困难。KMP算法相对于普通的搜索算法，最大的优势就是使用了一个next数组来帮助算法程序跳转，通过减少比对时间来优化效率。这个算法的核心也就是是next数组的求法。Next数组保证每一次比对完成以后向后跳转的具体位置。而KMP算法的核心即是计算字符串string，每一个位置之前的字符串的前面部分和后部分的公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。这样构造的算法可以在最大程度上向后跳转节约时间。四、 调试与测试在调试本程序时，为了保证输入输出的值的正确，基本思路是在每个函数写好以后对该函数的效果进行测试，保证该函数能正常运行并得出对应正确的结果，并且对可能会影响到的指针的值进行处理，保证程序的健壮性。如果程序出现了致命的错误，我就会打开断点调试功能筛查是哪个地方出了问题，然后进行修改。五、 执行结果本程序所需要的文章以文本形式放在程序同目录下的input_text.txt内。打开程序时会自动加载转换本文本，并且不会对原文本进行更改。以下是演示图片。六、 源代码#include #include #include / 构造存储字符的结构体 typedef struct listNodechar word;struct listNode *next; wordList, *list;/ 构造储存字符数量的结构体typedef struct int alpha;int digit;int blank;int sum; numStruct, *numNode;/ 构造储存字符位置的结构体typedef struct posNodeint pos;struct posNode *next; posStruct, *posList;/ 线性链表初始化函数：链表头指针int wordList_init( list *res);/ 存储结构初始化函数：结构指针int numNode_init( numNode *num);/ 字符位置链表初始化函数：结构指针int posNode_init( posList *posP);/ 字符位置链表增加与储存函数：头指针，插入字符int posNode_add( posList *posP, int posNum);/ 链表增加与储存函数：头指针，插入字符int wordList_add( list *res, char letter);/ 文本转换链表函数，同时计算文本中的字符类别和数量：链表头指针，结构体指针int text_transform( list *res, numNode *num);/ 删除链表的某一节点：该节点的前一个节点的指针int wordList_delete( list *now);/ 链表打印：头指针void wordList_print( list *res);/ 计算next数组的值：void nextArray_make( char strFind, int next);/ KMP算法：int KMP( char strRes, char strFind, int next);/ KMP统计出现次数int stringRepeat_count( char strRes, char strFind, posList *posL);/ 字符串查询：链表头指针，结构void string_search( list *res, numNode *num);/ 字符串删除函数：链表头指针，结构void string_delete( list *res, numNode *num);/ 菜单函数void menu();/ 主函数int main (void)menu();return 0;/ 线性链表初始化函数：链表头指针int wordList_init( list *res)(*res) = (list)malloc(sizeof(wordList);if( (*res) )(*res)-next = NULL;(*res)-word = ;return 1;elseprintf(空间分配失败，请重试。n);return 0;/ 存储结构初始化函数：结构指针int numNode_init( numNode *num)(*num) = (numNode)malloc(sizeof(numStruct);if( (*num) )(*num)-alpha = 0;(*num)-digit = 0;(*num)-blank = 0;(*num)-sum = 0;return 1;elseprintf(空间分配失败，请重试。n);return 0;/ 字符位置链表初始化函数：结构指针int posNode_init( posList *posP)(*posP) = (posList)malloc(sizeof(posStruct);if (*posP)(*posP)-next = NULL;(*posP)-pos = 0;elsereturn 0;/ 字符位置链表增加与储存函数：头指针，插入字符int posNode_add( posList *posP, int posNum)while (*posP)-next)(*posP) = (*posP)-next;/ 分配空间(*posP)-next = (posList)malloc(sizeof(posStruct);if (*posP)-next)(*posP) = (*posP)-next;(*posP)-next = NULL;(*posP)-pos = posNum;return 1;elseprintf(空间分配失败，请重试。n);return 0;/ 链表增加与储存函数：头指针，插入字符int wordList_add( list *res, char letter)while (*res)-next)(*res) = (*res)-next;/ 分配空间(*res)-next = (list)malloc(sizeof(wordList);if (*res)-next)(*res) = (*res)-next;(*res)-next = NULL;(*res)-word = letter;return 1;elseprintf(空间分配失败，请重试。n);return 0;/ 文本转换链表函数，同时计算文本中的字符类别和数量：链表头指针，结构体指针int text_transform( list *res, numNode *num)/ 文件操作，打开文件FILE *fp;fp = fopen( input_text.txt, r);char letter;/ 初始化链表wordList_init( &(*res);numNode_init( &(*num);/ 重新声明变量，操作resNow来构建链表list resNow = (*res);/ 循环将文本读入线性表中while( (letter = getc(fp) != EOF)wordList_add( &resNow, letter);if( isalpha( letter) )(*num)-alpha+; /求字母数else if( isdigit( letter)(*num)-digit+; /求数字个数else if( letter = )(*num)-blank+; /求空格数(*num)-sum+;/ 关闭文件fclose(fp);/ 删除链表的某一节点：该节点的前一个节点的指针int wordList_delete( list *now)list temp = (*now)-next;(*now)-next = temp-next;free(temp);return 1;/ 链表打印：头指针void wordList_print( list *res)list temp = (*res);while( temp-next )temp = temp-next;printf(%c,temp-word);/ 计算next数组的值：void nextArray_make( char strFind, int next)int i,j;int len = strlen(strFind); next0 = -1;/next0放上-1 i = 0;/指向字符串每个字符的指针 j = -1; while( i len )/没有到达结尾的话 if( j = -1 | strFindi = strFindj)/如果是第一个字符或遇到相同的字符 i+;j+;nexti = j; else j = nextj; / for( i = 0; i len; i+)/输出next值 / printf(%d,nexti); / / KMP算法：int KMP( char strRes, char strFind, int next) int i, j; i = j = 0;int lenRes = strlen(strRes);int lenFind = strlen(strFind); while( i lenRes & j lenFind )int nextlenTemp;nextArray_make( strFind, next);int pos = KMP( strTemp, strFind, next);if(pos = -1)break;elsestrTemp = &(strTemppos+lenFind);lenTemp = strlen(strTemp);repeatCount+;posCount += (pos + lenFind);printf(n第 %d 在第 %d 个位置出现。n, repeatCount, posCount);posNode_add( &tempPOS, posCount);return repeatCount;/ 字符串查询：链表头指针，结构void string_search( list *res, numNode *num)printf(n请输入您想要查找的字符串：n);/ 获得最大长度为文本文件大小的字符串数组char strFind(*num)-sum;scanf(%s,&strFind);/ 将链表转换为数组处理char strRes(*num)-sum;list temp = (*res);int i = 0;while( temp-next )temp = temp-next;strResi = temp-word;i+;posList pos;posNode_init( &pos);int repeatCount = stringRepeat_count( strRes, strFind, &pos);if ( repeatCount)printf(n该字符串“ %s ”在本文本中出现了 %d 次。, strFind, repeatCount);else printf(没有搜索到该文本。);/ 字符串删除函数：链表头指针，结构void string_delete( list *res, numNode *num)printf(n请输入您想要删除的字符串：n);/ 获得最大长度为文本文件大小的字符串数组char strFind(*num)-sum;scanf(%s,&strFind);/ 将链表转换为数组处理char strRes(*num)-sum;list temp = (*res);int i = 0;while( temp-next )temp = temp-next;strResi = temp-word;i+;posList pos;posNode_init( &pos);int repeatCount = stringRepeat_count( strRes, strFind, &pos);if ( !repeatCount)printf(没有搜索到该文本。);return;printf(n该字符串“ %s ”在本文本中出现了 %d 次。n, strFind, repeatCount);printf(n您确认删除这个字符串吗？nn回复数字 1 来确认此操作。n);i = 0;scanf(%d,&i);if ( i = 1)int count = 0;list temp = (*res);pos = pos-next;while( temp-next & pos)int lenDelete = strlen(strFind);count+;if ( count = pos-pos)count += lenDelete;while ( lenDelete)wordList_delete( &temp);lenDelete-;pos = pos-next;temp = temp-next;printf(nn删除成功，现文本如下：nn);wordList_print( &(*res);return;/ 菜单函数void menu()/ 声明链表头指针list res;/ 声明数量结构体numNode num;/ 将文本转换为链表保存并统计字符数量text_transform( &res, &num);int funChoose;while (1)printf(n请输入序号来选择您需要的功能：nn);printf(1.显示文本nn2.显示字符统计情况。nn3.查询字符串nn4.删除字符串nn);scanf(%d, &funChoose);system(cls);if ( funChoose = 1)wordList_print( &res); else if ( funChoose = 2)printf(n字母数：%dnn数字数：%dnn空格数：%dnn字符总数：%dn, num-alpha, num-digit, num-blank, num-sum); else if ( funChoose = 3)string_search( &res, &num); else if ( funChoose = 4)string_delete( &res, &num);elseprintf(n请输入正确的选择数字。);printf(nnn);system(pause);system(cls);集合运算一、 需求分析1. 问题描述使用链表来表示集合，完成集合的合并，求交集等操作。2. 基本要求（1）用链表表示两个集合（2）对两个集合分别从小到大排序（3）两个集合合并成另一个新集合，如数值相同，合并为一个数据项（4）求出两个集合的交集建立一个新的集合。3. 需求分析（1）将该集合转换为链表储存。（2）分别对两个集合进行排序操作。（3）合并两个集合，排序并合并相同数据项。（4）打印出交集。4. 开发环境系统环境：Microsoft Windows10 专业版开发环境：Microsoft Visual Studio 2015开发平台：Win64开发语言：C+编译器：Intel Parallel Studio XE 2013硬件环境：（1） CPU：Intel Core i7-4710MQ（2） 内存：16GB（3） 显示卡：NVIDIA GeForce GTX960M二、 概要设计1. 流程图2. 结构体构造本程序采用的数据结构是单链表形式，在每个节点中存储集合中的一个元素，用指针的方式连接，形成链表，通过遍历的方式来排序和打印元素。3. 设计思想本程序旨在集合运算，所以一开始便构造两个链表分别存储两个集合，并进行分别排序。最后使用总处理函数得到交集和并集，具体设计在第三节的重点函数分析中。三、 详细设计1. 结构体构造/ 构造结构体储存数据typedef struct nodeint num; struct node *next; groupList, *list;2. 函数构造/ 链表初始化函数：链表头指针int group_init( list *res);/ 链表增加函数：链表头指针，值int group_add( list *res, int num);/ 删除该节点的下个节点：头指针void group_delete( list *res);/ 链表打印函数：头指针void group_print( list *res);/ 获取集合：头指针，集合元素总数void group_get( list *res, int numSum);/ 链表的冒泡排序：头指针void group_BubbleSort( list *res);/ 链表的总处理：四个头指针/ 在这个函数中调用了冒泡排序函数和删除节点函数void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter);/ 菜单函数void menu ();3. 重点函数分析本程序的重点在于链表的总处理函数，在此附上代码和说明。因为本程序较为简单，所以没有特意重新构造一个链表来分别保存并集和交集。这个函数的基本思路是讲这两个链表合在一起进行排序，然后遍历这个总链表。当遍历到两次出现同一个值时，证明这个值在两个链表中均出现过。则将其放到新构造的交集链表中。而当出现了三次时，则删除。由此得到的遍历后的链表即为并集的集合。/ 链表的总处理：四个头指针void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter) list a, 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 #include / 构造结构体储存数据typedef struct nodeint num; struct node *next; groupList, *list;/ 链表初始化函数：链表头指针int group_init( list *res);/ 链表增加函数：链表头指针，值int group_add( list *res, int num);/ 删除该节点的下个节点：头指针void group_delete( list *res);/ 链表打印函数：头指针void group_print( list *res);/ 获取集合：头指针，集合元素总数void group_get( list *res, int numSum);/ 链表的冒泡排序：头指针void group_BubbleSort( list *res);/ 链表的总处理：四个头指针void group_process( list *groupA, list *groupB, list *groupUnion, list *groupInter);/ 菜单函数void menu ();int main (void)menu(); return 0;/ 链表初始化函数：链表头指针int group_init( list *res) / 分配空间 (*res) = (list)malloc(sizeof(groupList); if (*res) (*res)-next = NULL; (*res)-num = 0; return 1; else return 0; / 链表增加函数：链表头指针，值int group_add( list *res, int num) / 判断当前指针是否指向最后一个节点 while(*res)-next) (*res) = (*res)-next; printf(指针有误。); / 分配空间 (*res)-next = (list)malloc(sizeof(groupList); if (*res)-next) (*