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

成都理工大学数据结构 课程设计报告计算机科学与技术一班 王力立
学 号

成都理工大学
计算机科学与技术系

数据结构课程设计
设计说明书

题目
文章编辑 集合运算

起止日期：

学生姓名

班级

成绩

指导教师(签字)

计算机科学与技术系

目录

文章编辑 2
一、 需求分析 2
1. 问题描述 2
2. 基本要求 2
3. 需求分析 2
4. 开发环境 3
二、 概要设计 3
1. 流程图 3
2. 结构体构造 4
3. 设计思想 4
三、 详细设计 4
1. 结构体构造 4
2. 函数构造 5
3. 重点函数分析 6
四、 调试与测试 6
五、 执行结果 7
六、 源代码 8

集合运算 18
一、 需求分析 18
1. 问题描述 18
2. 基本要求 18
3. 需求分析 18
4. 开发环境 18
二、 概要设计 19
1. 流程图 19
2. 结构体构造 19
3. 设计思想 19
三、 详细设计 19
1. 结构体构造 19
2. 函数构造 20
3. 重点函数分析 21
四、 调试与测试 22
五、 关键源程序清单和执行结果 22
六、 源代码 23

文章编辑
一、 需求分析
1. 问题描述
输入一页文字，程序可以统计出文字、数字、空格的个数。

2. 基本要求
静态存储一页文章，每行最多不超过80个字符，共N行，要求：
（1）分别统计出其中英文字母数和空格数及整篇文章总字数；
（2）统计某一字符串在文章中出现的次数，并输出该次数；
（3）删除某一子串，并将后面的字符前移。

存储结构使用线性表，分别用几个子函数实现相应的功能。

输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

输出形式：
（1）分行输出用户输入的各行字符；
（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"
（3）输出删除某一字符串后的文章；

3. 需求分析
（1）将文本转换为链表储存。
（2）统计各个字符数量。
（3）能够将该链表打印出来，并且执行删除某一节点的操作。
（4）查找并匹配字符串，并得到对应的位置。

4. 开发环境
系统环境：Microsoft Windows®10 专业版
开发环境：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 listNode{
char word;
struct listNode *next;
} wordList, *list;

// 构造储存字符数量的结构体
typedef struct {
int alpha;
int digit;
int blank;
int sum;
} numStruct, *numNode;

// 构造储存字符位置的结构体
typedef struct posNode{
int 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 <stdio.h>
#include <stdlib.h>
#include <string.h>

// 构造存储字符的结构体
typedef struct listNode{
char word;
struct listNode *next;
} wordList, *list;

// 构造储存字符数量的结构体
typedef struct {
int alpha;
int digit;
int blank;
int sum;
} numStruct, *numNode;

// 构造储存字符位置的结构体
typedef struct posNode{
int 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;
}else{
printf("空间分配失败，请重试。\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;
}else{
printf("空间分配失败，请重试。\n");
return 0;
}
}

// 字符位置链表初始化函数：结构指针
int posNode_init( posList *posP){
(*posP) = (posList)malloc(sizeof(posStruct));
if ((*posP)){
(*posP)->next = NULL;
(*posP)->pos = 0;
}else{
return 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;
}else{
printf("空间分配失败，请重试。\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;
}else{
printf("空间分配失败，请重试。\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);
next[0] = -1; //next[0]放上-1
i = 0; //指向字符串每个字符的指针
j = -1;
while( i < len ){//没有到达结尾的话
if( j == -1 || strFind[i] == strFind[j]){//如果是第一个字符或遇到相同的字符
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
// for( i = 0; i < len; i++){//输出next[]值
// printf("%d",next[i]);
// }
}

// 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 ){
if( j == -1 || strRes[i] == strFind[j] ){
i++;
j++;
}
else
j = next[j];
}

if( j == lenFind )
return i-lenFind;
else
return -1;
}

// KMP统计出现次数
int stringRepeat_count( char strRes[], char strFind[], posList *posL){
int lenRes = strlen(strRes);
int lenFind = strlen(strFind);
int lenTemp = 0;
int repeatCount = 0;

char *strTemp;

int next[lenRes];
nextArray_make( strFind, next);
int pos = KMP( strRes, strFind, next);
if(pos == -1){
return 0;
}
strTemp = &(strRes[pos+lenFind]);
lenTemp = strlen(strTemp);

repeatCount = 1;

printf("\n第 %d 次在第 %d 个位置出现。\n", repeatCount, (pos+1));

int posCount = pos + 1;

posList tempPOS = (*posL);

posNode_add( &tempPOS, posCount);

while ( lenTemp > lenFind ){
int next[lenTemp];
nextArray_make( strFind, next);
int pos = 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);
}
}
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;
strRes[i] = 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;
strRes[i] = 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您确认删除这个字符串吗？\n\n回复数字 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("\n\n删除成功，现文本如下：\n\n");
wordList_print( &(*res));
}
return;
}

// 菜单函数
void menu(){
// 声明链表头指针
list res;
// 声明数量结构体
numNode num;

// 将文本转换为链表保存并统计字符数量
text_transform( &res, &num);

int funChoose;

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);
} else if ( funChoose == 2){
printf("\n字母数：%d\n\n数字数：%d\n\n空格数：%d\n\n字符总数：%d\n", num->alpha, num->digit, num->blank, num->sum);
} else if ( funChoose == 3){
string_search( &res, &num);
} else if ( funChoose == 4){
string_delete( &res, &num);
}else{
printf("\n请输入正确的选择数字。");
}
printf("\n\n\n");
system("pause");
system("cls");
}
}

集合运算
一、 需求分析
1. 问题描述
使用链表来表示集合，完成集合的合并，求交集等操作。

2. 基本要求
（1）用链表表示两个集合
（2）对两个集合分别从小到大排序
（3）两个集合合并成另一个新集合，如数值相同，合并为一个数据项
（4）求出两个集合的交集建立一个新的集合。
3. 需求分析
（1）将该集合转换为链表储存。
（2）分别对两个集合进行排序操作。
（3）合并两个集合，排序并合并相同数据项。
（4）打印出交集。

4. 开发环境
系统环境：Microsoft Windows®10 专业版
开发环境：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 node{
int 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 <stdio.h>
#include <stdlib.h>

// 构造结构体储存数据
typedef struct node{
int 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){
(*