大二上的数据结构课设，采用python实现一个包含三种数据结构的英汉词典，

## 课题要求： 设计实现一个小型英汉双解词典（***） 问题描述：设计一个英汉双解电子词典，支持查找、插入、删除等功能。 基本要求：实现字典常用的数据结构包括有序表、AVL树、Patricia Tree（简称PAT tree，它是一棵压缩存储的二叉树结构）、散列表等，可以选择 一种数据结构，实现字典的基本操作，查找单词、插入单词（插入时，先查找，找不到则插入，找到则提示用户）、删除单词（删除时，先查找，找到 则删除，找不到则提示用户）等。字典是按字母顺序排列的，不能用顺序查找，插入或删除单词后，要保持字典的有序性。 测试数据：任一英文单词。 考核要求： （1）至少选两种以上的数据结构实现字典的查找、插入、删除等操作， （2）如果采用线性结构且无序，成绩为不及格。 （3）设计图形用户界面。 提示：字典可以自己建立，但必须按字母a~z建立26个文件，建议从网上下载，文件类型为txt。 达到以上考核要求，成绩为优秀，否则成绩向下浮动。 ## （一）软件的基本功能 使用的数据结构包括、AVL树、Trie树、散列表，实现字典的基本操作，查找单词、插入单词（插入时，先查找，找不到则插入，找到则提示用户）、删除单词（删除时，先查找，找到则删除，找不到则提示用户） ## （二）软件的提高功能 实现了图形界面，具有良好的交互。 Trie树实现模糊搜索。 ## （三）输入/输出形式 输入：英文字符串 输出：显示在列表域里 ## （四）使用的数据结构： AVL树，trie树，hash表 ## （五）主程序流程  ## （六）模块调用关系  ## （七）现概要设计的数据类型 ### 一、AVL树： AVL树其实就是一种改进后的二叉搜索树，他带有平衡因子，不会出现像二叉搜索树那样都排到一端极端情况，AVL树也可以叫做自平衡二叉搜索树。他的关键就是通过旋转，从而让树达到一个平衡状态，而在旋转的过程中，也要保持左小右大的特征 （1）.AVL树的插入操作：本质上是在普通二叉搜索树的插入操作上加了判断操作，递归的判断每一节点是否平衡，如果不平衡，就进行旋转操作，而旋转操作分为四种情况 四种旋转情况: 1.RR型不平衡：插入的元素是右子树的右子树，这时候需要左旋  2.LL型不平衡：插入的元素是左子树的左子树：这时候需要右旋  3.LR型不平衡:插入的元素是左子树的右子树：这时候需要左旋再右旋  4.RL型不平衡:插入的元素是右子树的左子树：这时候需要右旋再左旋  （2）.AVL树的删除 AVL树的删除有些复杂，具体步骤也是在二叉排序树的删除上进行优化，分为三种情况，首先找到要删除的节点 1.删除叶子节点，直接删，然后递归判断是否平衡，进行旋转 2.只有一个孩子： <1>.只有左子树：直接将左子树的值赋给该节点 <2>.只有右子树：直接将右子树的值赋给该节点 3.同时拥有左右子树： 普通的二叉搜索树，只要将左子树的最右节点或者右子树的最左节点赋给该节点就可以了，AVL树就是在这步上，进行了选择，以用来优化删除过程的速度。我们可以比较该节点的左右子树高度，选择较高点的一方。 如果左子树高度大于右子树高度，则找到左子树的最右节点，将该节点赋予要删除的节点，最后再删除最右节点。 如果右子树高度大于左子树高度，则找到右子树的最左节点，将该节点赋予要删除的节点，最后再删除最左节点。 以上是删除过程。 落实到代码上，又有一点不一样， 我们在查找那个点的过程(递归实现)中，就要根据要删除点的大小，来判断是向右子树还是向左子树走下去，当回来的时候，已经就实现了删除，这时候就得判断是否失衡，所以在向下走的时候，就得在每一步之后，进行判断，这里和插入的过程中一样，就是以上那四种情况。进行左旋或者右旋。 ### 二、Trie树： Trie树是一种字典树，在python中，利用字典来实现，每个数据的key是字母，value是一个节点，该节点储存着val关键值，来记录该点是否为一个单词，还有chines来记录该点的中文。以及child{}，来储存接下来的数据  ``` python class trie_node:     def __init__(self) -> None:         self.chines=""         self.child={}         self.val=False#该节点是否构成单词 ``` Trie树的查找：给定一个单词，遍历该单词的每个字母，然后在node的child中找这个字母，如果找到了就继续往下找，没找到的话就直接退出，走到最后判断node的val是否为True，如果为True，则找到该单词。否则不存在。 Trie树的删除和插入都和查找差不多，插入操作就是，从根节点开始，遍历所要插入的单词，如果遍历的字母不存在那么就创造一个新的点来存储这个字符，直到最后，将val标为True 删除操作就更简单了，先查找，如果找到，就将该节点的val标为False Trie树的可以实现一定程度的模糊查找：   利用trie树的特殊储存结构，来查出具有相同前缀的单词 ### 三、哈希表： 处理冲突：采用拉链法处理冲突 哈希函数为: 将一个单词的每个字母的Unicode编码乘以该字母在字符串的对应位置，最后取和。 例：`cat，index=(ord(c)*0+ord(a)*1+ord(t)*2)%mod` ## 四、图形界面： 图形界面我使用的是pyside6,实现图形界面 ## 补充 环境：windows 10 x64 用到的第三方模块：PySide6 用到的数据结构：AVL树、trie树、哈希表。 开发工具：vs-code 1.70.1 完成日期：2022年12月