//
// main.cpp
// 1
//
// Created by apple on 2017/12/10.
// Copyright © 2017年 apple. All rights reserved.
//
// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
//
//#include "stdafx.h"
#include<stdio.h>//调用库函数，输出输入东西
#include<stdlib.h>//abs（）绝对值函数，求绝对值是整数的时候用，systen("pause")运行停下来时用
#include<string.h>//字符串函数
#include<ctype.h>//isupper()函数来判断字符是否为大写字母
#include<time.h>//clock: 获取程序开始执行后占用的处理器时间，返回值clock_t。
//time：获取当前系统时间（UTC时间）的time_t值。本程序中用于计算程序运行的效率
#define maxqsize 1000//定义一个maxqsize 空间为1000
typedef struct vnode {//线性表用链表实现，vnode表示链表中的一个节点，可以是头节点也可以是中间节点
char word[20];//定义单词长度
int count;
vnode* next;//表示下一个节点的指针
}*linklist;//线性表的定义
typedef struct tree {
char word[20];
int count;
tree *lcchild, *rcchild;
}*Bitree, *queueelem;//二叉树的的节点，可以是头节点或者中间节点，Bitree是一个类型
typedef struct queue {//循环队列
queueelem *data;//对应Bitree类型，是二叉树
int rear, front, tag;//tag 为判断队的状态1为满 0为空 front指向队头，rear指向队尾
}*Q;
void inordertraverse(Bitree r, FILE* fp)//中序遍历输出结果到文档
{
if (r == NULL)return;
inordertraverse(r->lcchild, fp);
fprintf(fp, "%-16s%3d\n", r->word, r->count);
inordertraverse(r->rcchild, fp);//先遍历左子树，然后输出自己，最后遍历右子树
}
void initqueue(queue &q) {//初始化队列
q.data = (queueelem *)malloc(maxqsize * sizeof(queueelem));//(queueelem *)是一个类型名，q.data申请一块内存，大小为(maxqsize * sizeof(queueelem))，malloc返回一个void*类型的指针,存放maxqsize这个队列元素
q.tag = q.front = q.rear = 0;//使队列的状态为空为0
return;
}
void enqueue(queue &q, queueelem e)//进队
{
if (q.tag == 1)return;//如果队满了，返回
q.data[q.rear] = e;//插入元素e为q的新队尾元素
q.rear = (q.rear + 1) % maxqsize;//防止下标超出maxqsize,后移队尾指针指向下一个入队元素的下标
if (q.rear == q.front)q.tag = 1;//头指针和尾指针重叠，则队列满，tag=1
else q.tag = 2;//既不满也不空
}
void dequeue(queue &q, queueelem &e)//出队
{
if (q.tag == 0)return;//若队为空，返回
e = q.data[q.front];//e取队头元素，从后入从前出
q.front = (q.front + 1) % maxqsize;//防止下标超出maxqsize,后移队头指针指向下一个出队元素的下标
if (q.rear == q.front)q.tag = 0;//头指针和尾指针重叠，则队列空，tag=1
else q.tag = 2;
}
linklist head;//全局变量，线性表的表头
Bitree root;//全局变量，二叉树的根节点
void Content1()//设置两个选项函数
{
printf("****************************************************\n\n");
printf("1:连续执行完毕并显示执行时间\n");
printf("2:单步执行\n");
printf("3:返回主菜单\n");
printf("****************************************************\n");
}
void Content2()
{
printf("****************************************************\n\n");
printf("1:识别并统计单词\n");
printf("2:删除低频单词并输出\n");
printf("3:输出其余单词及其频率\n");
printf("4:计算ASL值\n");
printf("5:返回上一级菜单\n");
printf("****************************************************\n");
}
void LinearSortByCharacter()//对线性表按照字符进行排序
{
linklist p, q, r;
q = head->next->next;
head->next->next = NULL;
while (q)//判断r后是否还有结点
{
r = q; q = q->next;
for (p = head; p->next; p = p->next)//p指向头结点，若p的下一个存在，则p指向p的下一个
if (strcmp(r->word, p->next->word) < 0)//若字符串r小于字符串p，则为-1<0,需要调换位置
//如果是要改成按照评频率进行排序，把这句话改成if(r->count > p->next->count)就可以
break;
r->next = p->next; p->next = r;//交换位置
}
}
void LinearReadWord()//读取文件内容存入
{
FILE* fp = fopen("Infile.txt", "r");//读取文件
if (fp)
printf("文件读取成功\n");
char ch[35], str[16];
linklist p, q;
int i, j;
head = (linklist)malloc(sizeof(vnode));//获取vonde的字段长度，强制转化为linklist的类型，head变量就代表地址长度和vnode一样所占内存空间同样大小的linklist.
head->next = NULL;//首地址的下一个为空
while (~fscanf(fp, "%s", ch))//从fp中读取一个字符放到ch中，～按位取反
{
j = 0;
for (i = 0;; i++)//循环跳出条件缺省，只有两个条件但是分号不能少
if (isalpha(ch[i]))//判断ch[i]中的是否为字母，当为字母时返回非零值，执行下面的语句小写2大写1
str[j++] = ch[i];//将ch[i]中是字母的存入str[]数组中
else if (j)//把j=0的情况去掉了，就是第一个字符一定会是英文字符
{
str[j] = 0;//如果不是英文字符且到了不是英文字符的位置，字符串结束，末位置置为“\0”
for (j = 0; str[j]; j++)//把大写转换成小写
if (isupper(str[j]))//判断是否为大写字母
str[j] += 32;//若果是的话ascii码加32变成小写字母
for (p = head; p->next; p = p->next)
if (strcmp(str, p->next->word) == 0)break;//找到已有单词，跳出查找
if (p->next)
p->next->count++;//找到count++，往下一个查找
else {//没找到new一个节点
q = (linklist)malloc(sizeof(vnode));//找不到的话创建一个新的节点
strcpy(q->word, str);//把str复制到q->word中，复制函数
q->count = 1;
p->next = q; q->next = NULL;
}
j = 0;//j=0的情况
if (!ch[i])break;
}
else if (!ch[i])
break;
}
fclose(fp);
}
void LinearDeleteWord()//删除频率小于5的词汇，线性链表删除节点
{
linklist p = head, q;
if (!p) {
printf("尚未读入单词，请先读取文件\n");
return;
}
while (p->next)//当p的下一个元素存在时
if (p->next->count<5)
{
q = p->next; p->next = q->next;
printf("删除单词：%s, %d\n", q->word, q->count);
free(q);//释放q
}
else p = p->next;//若大于五，p后移
printf("删除完成\n");
}
void LinearPrintWord()//打印所有剩下的词汇到文件
{
linklist p;
if (!head) {//头指针没有元素
printf("尚未读入单词，请先读取文件\n");
return;
}
if (head->next == NULL) {//头指针的下一个为空
printf("单词已被完全删除，无剩余单词\n");
return;
}
LinearSortByCharacter();//对线性表字符进行排序
p = head->next;//p指向头指针的后一个元素
FILE* fp = fopen("outfile1.txt", "w");//建立outfile1.txt,写入文件
while (p)
{
fprintf(fp, " %-16s%3d\n", p->word, p->count);//输出的字符串左对齐，而且占16个字符，以三位为固定宽度输出的整形数，不足三位前面部空格，满足三位按实际位数输出
p = p->next;
}
if (fp)printf("文件写入成功\n");
fclose(fp);
}
void LinearCalculateASL()//线性表计算ASL
{
linklist p = head;//p指向头指针
float asl;
int sn = 0, wn = 0, count = 0;
