数据结构练习---基于不同策略的英文单词检索系统(顺序表，单链表，二叉排序树)

学校课程设计实训周，抽到了这个题，写完之后也有一些收获，放到网上和大家一起学习交流：)

本人数据结构只是学了一些皮毛，代码写的比较简单直接，通俗易懂。还望各路大神多多指教

拿到题目遇到的第一个问题，就是如何从指定路径下读取文件，去除空格及标点符号，并将读取到的英文文章拆分为一个个英文单词存储起来？

我的方法是用isalpha()这个函数来判断是否是英文字母，函数类型定义为bool，若不是英文字母，返回false，就再向后读取一个字符，直到找到第一个英文字母，证明找到了一个英文单词的开头，返回true。设置一个start变量，将这个单词的首字母所在位置记录下来，然后一直向后找，直到再次找到非英文字母，证明一个单词结束，再设置一个end变量记录下结束位置。这样就截取到了一个单词的起始位置。设置一个char型数组，运用循环将单词各字母逐个放入数组，最后加上'\0'，一个个单词就截取成功啦！

int detect(const char *p,SqList &L,LinkList &LL)
{int i=0,m;char temp[20];int start,end;while(p[i]!=0)		//当非空行 {while(judge_alphabet(p[i])==false){i++;}if(judge_alphabet(p[i])){start=i;i++;while(judge_alphabet(p[i])){i++;}}end=i;for(int j=start,k=0;j<=end;k++,j++){temp[k]=p[j];m=k;}temp[m]='\0';L.elem[count].key=temp;			//count为单词个数，也可作为线性表存储单词的下标	 count++;i++;LNode *s=new LNode;s->data=temp;s->next=LL->next;LL->next=s;}
}

遇到的第二个问题就是如何统计整篇文章的单词词频。我的方法是为存储单词的线性表再添加一个flag标志，初始化为true。循环遍历线性表，如果后面再次出现相同的单词，就把该单词所在位置的flag置为false，再次遍历时就直接跳过。

void Getnum(SqList &L)		//获取文章中所有单词词频 
{int j=1;for(int a=1;a<=L.length;a++)	//外层循环，拿第a个单词和线性表所有单词进行比较 {int nums=0;if(L.elem[a].flag==true)	//true证明还没有相同单词，执行比较操作 {for(int i=1;i<=L.length;i++)		//内层循环，依次遍历整个线性表 {if(L.elem[a].key==L.elem[i].key){L.elem[i].flag=false;nums++;}else	continue;}words_num[j]=nums;		//将所有单词词频存放在word_num这个数组中 L.elem[j].key=L.elem[a].key;j++;}}
}

实现功能中还要求输出各查找方式的ASL，这里就直接输出：线性表查找为（n+1）/2，折半查找为log以2为底（n+1）-1，二叉排序树为㏒以2为底（n+1）

需要动脑子的应该只有这么多内容，其他都是一些比较基础的定义结构，初始化，读取调用等函数，平常数据结构课上应该都有练习，这里就不再赘述了，下面贴上完整代码

#include 
#include    //c++操作文件所需的头文件
#include 
#include 	//判断字符是否是字母 
#include		//数学方法 
using namespace std;
#define MAXSIZE 10000   //顺序表的最大长度int count=1;	//既是单词个数又是线性表下标，一会儿输出单词个数记得count-1
int words=0;	//统计欲查找单词频数 
int words_num[MAXSIZE];		//存放所有单词词频 
typedef struct{string key;		//存放单词bool flag;		//设置标志，若查找单词在后面出现过，就把该单词所在位置下的flag置为falseint words;		//统计词频,若查询单词在后面再次出现，words++ 
}ElemType;
typedef struct{					//线性表结构ElemType elem[MAXSIZE];int length;
}SqList;typedef struct LNode{			//单链表结构 string data;struct LNode *next;
}LNode,*LinkList;typedef struct BSTNode{			//二叉链表结构 string data;struct BSTNode *Lchild,*Rchild;
}BSTNode,*BSTree;void Init_SqList(SqList &L)			//初始化线性表 
{L.length = 0;for(int i=0;inext = NULL;
}
bool judge_alphabet(char ch)		//判断是否为英文字母 
{if(isalpha(ch))return true;elsereturn false;
}
int detect(const char *p,SqList &L,LinkList &LL)
{int i=0,m;char temp[20];int start,end;while(p[i]!=0)		//当非空行 {while(judge_alphabet(p[i])==false){i++;}if(judge_alphabet(p[i])){start=i;i++;while(judge_alphabet(p[i])){i++;}}end=i;for(int j=start,k=0;j<=end;k++,j++){temp[k]=p[j];m=k;}temp[m]='\0';L.elem[count].key=temp;			//count为单词个数，也可作为线性表存储单词的下标	 count++;i++;LNode *s=new LNode;s->data=temp;s->next=LL->next;LL->next=s;}
}//将文件C:\book.txt中的数据逐条读入顺序表L中
void ReadData(SqList &L,LinkList &LL,BSTree &T)
{int i=0;string temp;ifstream infile("d:\\Obama.txt");  //以输入的方式（读文件的方式）打开文件c:\book.txtwhile(!infile.eof())   //只要文件没读完，就读一行数据到顺序表L中的第i个分量中{getline(infile,temp);const char *p=temp.c_str();if(strlen(p)!=0){detect(p,L,LL);}}L.length = count-1;infile.close();
}void WriteData(SqList L)
{int q;ofstream outfile("d:\\words.txt");		//将单词总数及词频信息保存在新的txt中 outfile<<"单词总数为:"<next;/*while(p!=NULL)		//以单链表形式输出所有单词 {cout<data;p=p->next;}cout<next;while(p!=NULL){if(p->data==key)words++;p=p->next;}return words;}void InsertSort(SqList &L)		//使用直接插入法对线性表L进行排序 
{int i,j;for(i=2;idata=e;s->Lchild=s->Rchild=NULL;T=s;}else if(edata)Insert_BST(T->Lchild,e);else if(e>T->data)Insert_BST(T->Rchild,e);
}
void Create_BST(BSTree &T,SqList L)		//创建二叉排序树 
{int i=1;string e;T=NULL;e=L.elem[1].key;while(i<=L.length){Insert_BST(T,e);i++;e=L.elem[i].key;}
}
void InorderBST(BSTree T)		//中序遍历并输出二叉排序树 
{if(T){InorderBST(T->Lchild);cout<data<<"  ";InorderBST(T->Rchild);}
}BSTree SearchBST(BSTree T,string key)		//二叉排序树的查找 
{if(!T||key==T->data)	return T;else if(keydata)	return SearchBST(T->Lchild,key);else return SearchBST(T->Rchild,key);
}void Delete(BSTree &T,BSTNode *p,BSTNode *f)		//二叉排序树中p所指结点的删除 
{BSTNode *q,*s;q=p;if(p->Rchild  && p->Lchild )   //p所指结点的左右子树均非空{s=p->Lchild;while(s->Rchild){q=s;s=s->Rchild;}p->data=s->data;if(q==p)	q->Lchild=s->Lchild;else q->Rchild=s->Lchild;delete s;}else if(p->Rchild ==NULL)   //p所指结点只有左子树{p=p->Lchild;}else if(p->Lchild ==NULL)   //p所指结点只有右子树{p=p->Rchild;}if(f==NULL) T=NULL;    //T只有一个根结点，且被删除的是根结点else if(q==f->Lchild )  f->Lchild =p;   //被删结点是双亲f的左孩子else   f->Rchild =p;    //被删结点是双亲f的右孩子delete q;    //释放被删结点
}bool DeleteBST(BSTree &T,string key)		//二叉排序树的删除 
{BSTNode *p=T,*f=NULL;    while(p)     //从二叉排序树的根开始，查找关键字为key的结点，并用p指向它，f指向p的双亲{if(p->data == key)     //找到关键字为key的结点，且p指向它break;f=p;                       //f为p的双亲if(p->data > key)      //在p的左子树中继续查找p=p->Lchild ;else                       //在p的右子树中继续查找p=p->Rchild ;}if(p==NULL)            //T中不存在关键字等于key的结点，返回falsereturn false;Delete(T,p,f);         //在二叉排序树T中删除p所指结点（关键字为key的结点），f指向p的双亲return true;           //删除成功，返回true
}void show_main_menu()
{cout<<"			-----------------------------------------"<>n;cout<>n;cout<>word; num = Sq_Search(LSq,word);if(num>0)cout<<"查找成功！"<<"\n该词词频为:"<>n;cout<>word;num = LL_Search(LL,word);if(num>0)cout<<"查找成功！"<<"\n该词词频为:"<>n;cout<>word;InsertSort(LSq);num=Search_Bin(LSq,word);if(num>0)cout<>n;cout<>word;num1=SearchBST(T,word);if(num1>0)cout<>word;if(DeleteBST(T,word)==false)cout<<"\n删除失败！！ 二叉排序树中不存在单词 "<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！