课程设计 数据结构.docx
- 文档编号:12882456
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:11
- 大小:17.04KB
课程设计 数据结构.docx
《课程设计 数据结构.docx》由会员分享,可在线阅读,更多相关《课程设计 数据结构.docx(11页珍藏版)》请在冰点文库上搜索。
课程设计数据结构
课程设计要求及任务描述:
程序要求:
1、一次读取文件的一行;读取文件使用iostream
2、除去行中所有的标点符号,利用附录A的程序代码;
3、对于每一行:
a)在你构建的索引结构中查找单词;
b)如果没有找到(出现新词)就将它插入索引;
c)如果找到就更新该词的出现次数(次数加1)。
4、所有行都读入完成后,对索引结构按照字典顺序进行排序。
每一行都应包括该单词本身、出现次数,如果有能力,程序还应包含出现该单词的页码。
目标:
使用C++语言为任意书籍构造索引字典(英文书)。
输入:
书籍的文本文件;测试用例为abc.txt
输出:
包含索引的文本文件,包括排序后的英文字典,英文出现次数,出现该英文的页码
报告
一、题目分析
程序的主要功能是从一个文本文件中读入内容,然后将单词从中分离出来并记录出现次数,最后将处理结果写入另一个文件。
二、总体设计
1.从用户的指定文本文件中读入abc.txt内容——包括了英文、标点符号、特殊符号及中文等其他字符。
2.将大写字母转换为小写字母。
3.按字母表的顺序,记录每个单词及其出现的次数和出现的页码。
4.输出output--abc.txt
三、实验器材
PC机一台,WindowsXP系统,VC++
四、制作步骤
具体步骤如下:
int2str()函数:
函数中将int型的数据转换为string;
lowercaseWords()函数:
函数将文本输入的大写转换成小写字母。
Find_Word()函数:
函数对已存储的单词进行查找是程序的主体。
还包括记录每个单词及其出现的次数和出现的页码
Insert_Word()函数:
函数用来将新出现的单词插入到链表中。
sort()函数:
函数将链表以字典顺序排序
OutputList()函数:
函数将处理后的数据输入到一个文本中(output-abc.txt)。
UpdateList()函数:
函数调用包括Find_Word()函数在内的子函数来更新链表
main()函数:
程序入口
五、程序代码
#include
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
classSkipList
{
public:
SkipList*next;
stringkey;
intkeyCount;
stringpage;
};
//此函数由:
蕭鴻森,Clare,台灣,台北,blog提供,致谢。
stringint2str(int&i)
{
strings;
stringstreamss(s);
ss<
returnss.str();
}
//Removeallcharactersexceptletters(A-Z,a-z)fromline,
//exceptkeep'-'or'\''iftheyarebetweenletters.
voidlowercaseWords(string&line)
{
for(string:
:
iteratorit=line.begin();it!
=line.end();++it)
if(!
isalpha(*it))
{
if(*it!
='-'&&*it!
='\''||it==line.begin()||it+1==line.end()||!
isalpha(*(it-1))||!
isalpha(*(it+1)))
*it='';
}else
{
*it=tolower(*it);
}
}
//对已存储的单词进行查找
intFind_Word(SkipList*x,stringword,inta)
{
intflag=1,b;
strings;
s=int2str(a);
if(x->key!
=word)
{
while(x->next!
=NULL)
{
if(x->key==word)//flag==0,匹配成功;否则,匹配失败
{
flag=0;
x->keyCount=x->keyCount+1;//统计单词出现次数
b=x->page.length();//统计单词出现页码
if(b<1)
{
if(x->page!
=s)
x->page=x->page+""+s;
}
else
{
if(x->page.substr(b-1,b)!
=s)
x->page=x->page+","+s;
}
break;
}
x=x->next;
}
}
else
flag=0;
returnflag;
}
//插入新出现的单词
voidInsert_Word(SkipList*head,stringword,inta)
{
SkipList*z,*s;
stringst;
z=head;
st=int2str(a);
s=newSkipList();
s->keyCount=1;
s->page=""+st;
while(z->next!
=NULL)
{
if(word<=z->key)//在z节点后插入
{
s->key=word;
s->next=z->next;
z->next=s;
break;
}
z=z->next;
}
if(z->next==NULL)//结尾插入
{
s->key=word;
z->next=s;
s->next=NULL;
}
}
//将链表以字典顺序排序
SkipListsort(SkipList*head)
{
SkipList*p1,*p2,*p3,*p4,*p5;
boolflag;
p3=head;
while(p3->next->next!
=NULL)//链表向前推进
{
p2=p3->next;
p5=p2;
p1=p2;
flag=false;
while(p1->next!
=NULL)//内存循环终止的条件
{
if(p5->key>p1->next->key)//找出原链表中剩余节点中值最小的节点
{
p5=p1->next;
p4=p1;
flag=true;
}
p1=p1->next;
}
if(flag)//交换两个节点的顺序,值小的节点往前调
{
if(p2==p4)//此种情况为要交换顺序的两个节点相邻
{
p2->next=p5->next;
p5->next=p2;
p3->next=p5;
}
else//这种情况为要交换的两个节点不相邻
{
SkipList*temp=p5->next;
p5->next=p2->next;
p3->next=p5;
p4->next=p2;
p2->next=temp;
}
}
p3=p3->next;
}
return*head;
}
//生成txt文本输出引索结果
voidOutputList(SkipList*head)
{
SkipList*p;
ofstreamofile("C:
\\t\\Output-abc.txt");
sort(head);//先排序后输出
p=head;
while(p->next!
=NULL)
{
ofile< ofile<<"("< ofile< p=p->next; } } //更新链表(出现新词就将它插入索引,找到就更新该词的出现次数) voidUpdateList(SkipList*head,stringword,inta) { SkipList*x; intflag=0; x=head; flag=Fand_Word(x,word,a); if(flag==0){} else Insert_Word(x,word,a); } voidmain() { cout<<"---BEGIN---\n\n";//辅助信息,可注释掉 stringword,line; SkipList*head; intlinecount=0,wordcount=0; intpage=1; head=newSkipList(); head->next=NULL; head->key="a"; head->keyCount=0; ifstreamifile("E: \\t\\abc.txt"); ofstreamofile("E: \\t\\Output-abc.txt"); while(getline(ifile,line)) { cout< lowercaseWords(line); cout< istringstreamiss(line,istringstream: : in); while(iss>>word) { UpdateList(head,word,page); wordcount++; } linecount++; if(linecount>=40) { page++; linecount=1; } } OutputList(head->next); //帮助测试所用信息,与题目要求无关 cout< cout<<"wordcountis: "; cout< cout<<"linecountis: "; cout< cout<<"pageis: "; cout< cout<<"\n----END----\n";//辅助信息,可注释掉 }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课程设计 数据结构