数据结构实验代码分享

题目：通信录查询系统（查找应用）

【问题描述】

设计散列表（哈希表）实现通讯录查找系统。

(1) 设每个记录有下列数据项：电话号码、用户名、地址；

(2) 从键盘输入各记录，分别以电话号码为关键字建立散列表；

(3) 采用任意方法解决冲突；

(4) 查找并显示给定电话号码的记录；

(5) 通讯录信息文件保存；

【实现功能】

主函数：根据选单的选项调用各函数，并完成相应的功能。

Create()的功能：创建新的通讯录。

Append()的功能：在通讯录的末尾写入新的信息，并返回选单。

Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有

此人的信息，并返回选单。

Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，

并返回选单。

Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信

息，并返回选单。

List()的功能：显示通讯录中的所有记录。

Save()的功能：保存通讯录中的所有记录到指定文件中。

设计思路

自顶向下拆解任务：

接收输入数据；
创建HTable；
实现各个功能。

接收输入数据：

　　　　a) 输入数据包括姓名 + 联系电话 + 地址，可以考虑用一个Class打包

 1 // 联系人 类
 2 class Contact {
 3 public:
 4     string tel;     // 电话号码
 5     string name;    // 姓名
 6     string addr;    // 地址
 7     Contact* next;
 8 
 9     Contact() : next(nullptr) {}
10     Contact(const string &_tel, const string &_name, const string &_addr) 
11         : tel(_tel), name(_name), addr(_addr), next(nullptr) {}
12     ~Contact() {}
13 
14     void print() {
15         printf("%s, %s, %s\n", name.c_str(), tel.c_str(), addr.c_str());
16         // std::cout << name << " " << tel << " " << addr << "\n";
17     }
18 };

Contact class

　　　　b) 输入数据不定长，以 ‘@’ 作为结束标志

 1 第一种方式（行输入，比较好看）：
 2         string line;
 3         string name, tel, addr;
 4 
 5         // 行获取数据，'@'作为结束标志
 6         while (true) {
 7             getline(cin, line);
 8             if (line == "@") {
 9                 break;
10             }
11             std::istringstream iss(line);
12             iss >> tel >> name >> addr;
13             // 插入至HTable  
14         }    
15 
16 第二种方式（逐词输入，比较简单）：
17         string tel, name, addr;
18         do {
19             cin >> tel >> name >> addr;
20             // 插入至HTable  
21         } while(cin.get() != '\n');

不定长数据输入

　　　2. 创建HTable：

　　　　a) 我的哈希表使用的是数字分析法确定地址，具体来说是电话号码后三位；再使用链接法处理冲突；

　　　　b) 哈希表的基本操作有三，分别是：插入（insert） + 查找（search） + 删除（remove）。我将这三个基本操作和存放数据的数组打包起来，作为HashTable类（详见下文“代码实现”部分）；

　　　　c) 存储输入数据时，将它们作为一个个联系人插入进HTable即可。

　　　3. 实现各个功能：

　　　　a) 说到底，这些功能的实现实际上是基本操作按某种顺序的组合，比如修改Alter() == 查找search() + 删除remove() + 插入insert()；

　　　　b) 因此，我编写了一些入口函数，并将它们设置为public供外界调用，而其他关键部分比如 Hash() 与存储数据的数组与 HTable基本操作则设置为private隐藏起来。

代码实现

贴一下HTable及其基本操作的实现吧，入口函数就不贴了：

 1 // HashTable类
 2 class HashTable {
 3 private:
 4     vector<Contact*> HTable;
 5     int size;
 6     
 7     // Hash函数: 数字分析法，tel作为key，取其后三位
 8         // 注：应当来说，取tel后四位比较合理，但如此一来HTable的size应为10000，vscode的调试里装不下了?
 9     int Hash(const string &key) {
10         // 输入检查 没写。
11 
12         string sstr = key.substr(key.length() - 3); // 取key后三位作为子串
13         int num = std::stoi(sstr); // 字符串按字面量转为数字
14         return num;
15     }
16 
17     // 插入键值对:
18     void insert(const string &tel, const string &name, const string &addr) {
19         int index = Hash(tel);
20         Contact* newContact = new Contact(tel, name, addr);
21 
22         // 如果该位置为空，则直接插入
23         if (HTable[index] == nullptr) {
24             HTable[index] = newContact;
25         } else {
26             // 否则，新节点头插法入链表
27             newContact->next = HTable[index];
28             HTable[index] = newContact;
29         }
30     }
31 
32     // 查找键对应的值
33     Contact* search(const string &tel) {
34         int index = Hash(tel);
35         Contact* curr = HTable[index];
36 
37         // 在链表中查找键对应的值（顺序查找可优化成AVL 或 RBT什么的）
38         while (curr != nullptr) {
39             if (curr->tel == tel) {
40                 return curr;
41             }
42             curr = curr->next;
43         }
44 
45         return nullptr;
46     }
47 
48     // 删除键值对
49     void remove(const string &tel) {
50         int index = Hash(tel);
51         Contact* curr = HTable[index];
52         Contact* prev = nullptr;
53 
54         // 在链表中查找并删除键值对
55         while (curr != nullptr) {
56             if (curr->tel == tel) {
57                 if (prev == nullptr) {
58                     HTable[index] = curr->next;
59                 } else {
60                     prev->next = curr->next;
61                 }
62                 delete curr;
63                 return;
64             }
65             prev = curr;
66             curr = curr->next;
67         }
68         return;
69     }
70 
71 public:
72     HashTable(int s) : size(s) {
73         HTable.resize(size, nullptr);
74     }
75 
76     ~HashTable() {
77         // 释放哈希表中的所有节点
78         for (int i = 0; i < size; ++i) {
79             Contact* curr = HTable[i];
80             while (curr != nullptr) {
81                 Contact* temp = curr;
82                 curr = curr->next;
83                 delete temp;
84             }
85         }
86     }
　//　。。。。。。
// 。。。。。。。。。。

87 };