请你说出void add(Student* head) { Student* p = head; while (p->next != NULL) { p = p->next; } Student* newStudent = new Student; cout << "请输入学生信息：\n"; cout << "学号："; cin >> newStudent->id; cout << "姓名："; cin >> newStudent->name; cout << "年龄："; cin >> newStudent->age; cout << "性别："; cin >> newStudent->gender; cout << "成绩："; cin >> newStudent->score; newStudent->next = NULL; p->next = newStudent; cout << "学生信息添加成功！\n"; }的运行逻辑

<think>我们将在现有C++学生管理系统基础上添加以下功能： 1. 多级菜单：提供分级菜单导航，例如主菜单->学生管理->添加学生等 2. 数据验证：对用户输入的数据进行合法性检查 3. 模糊查询：根据部分信息查询学生（如姓名部分匹配） 4. 奖学金评定：根据成绩等条件评定奖学金 5. 用户注册登录：不同用户角色（如管理员、普通用户）使用不同功能 6. 二进制文件存储：将数据以二进制格式保存和读取，提高存储效率 由于代码量较大，我们将分模块实现。首先设计系统框架： 一、系统框架设计 1. 使用面向对象思想，设计学生类（Student）、用户类（User）、管理系统类（StudentManager） 2. 主程序流程：启动->登录->显示主菜单->根据选择进入子菜单 二、功能实现步骤 1. 多级菜单 - 使用函数封装每个菜单，通过函数调用实现多级菜单跳转 - 例如： void mainMenu(); // 主菜单 void studentMenu(); // 学生管理子菜单 void scholarshipMenu(); // 奖学金管理子菜单 2. 数据验证 - 在输入学生信息时，对学号、成绩等进行验证 - 例如：学号不能重复，成绩必须在0-100之间 3. 模糊查询 - 在查询函数中，使用字符串查找（如string::find）实现部分匹配 - 支持按姓名、学号等模糊查询 4. 奖学金评定 - 设计奖学金评定规则（例如：平均分>=90，且无不及格科目） - 遍历学生列表，筛选符合条件的学生 5. 用户注册登录 - 设计用户类（用户名、密码、角色） - 用户信息存储在文件中（二进制或文本） - 登录时验证用户信息，根据角色显示不同菜单 6. 二进制文件存储 - 使用fstream的二进制读写模式（ios::binary） - 学生对象和用户对象分别存储到不同的二进制文件中 三、代码结构示例（部分关键代码） 1. 学生类（Student）： ```cpp class Student { private: string id; // 学号 string name; // 姓名 float score1, score2, score3; // 三门课成绩 public: // 构造函数 Student(string id, string name, float s1, float s2, float s3) : id(id), name(name), score1(s1), score2(s2), score3(s3) {} // 获取平均分 float getAverage() const { return (score1 + score2 + score3) / 3.0; } // 检查是否有不及格 bool hasFailed() const { return score1 < 60 || score2 < 60 || score3 < 60; } // 友元函数，用于文件读写 friend ofstream& operator<<(ofstream& ofs, const Student& stu); friend ifstream& operator>>(ifstream& ifs, Student& stu); // 其他成员函数... }; ``` 2. 用户类（User）： ```cpp class User { private: string username; string password; string role; // "admin" or "user" public: User(string uname, string pwd, string r) : username(uname), password(pwd), role(r) {} // 登录验证 bool verify(string uname, string pwd) { return username == uname && password == pwd; } // 获取角色 string getRole() const { return role; } // 文件读写 friend ofstream& operator<<(ofstream& ofs, const User& user); friend ifstream& operator>>(ifstream& ifs, User& user); }; ``` 3. 管理系统类（StudentManager）： ```cpp class StudentManager { private: vector<Student> students; vector<User> users; string studentFile = "students.dat"; string userFile = "users.dat"; public: // 加载数据 void loadData(); // 保存数据 void saveData(); // 登录 User* login(); // 添加学生 void addStudent(); // 数据验证：学号唯一 bool isIdUnique(string id); // 模糊查询 void fuzzySearch(string keyword); // 奖学金评定 void evaluateScholarship(); // 菜单函数 void showMainMenu(User* currentUser); void showStudentMenu(); void showScholarshipMenu(); // ... 其他功能 }; ``` 四、关键功能实现细节 1. 二进制文件读写： - 写入：将对象的内存表示直接写入文件（注意：string是动态的，不能直接写，需要特殊处理） - 这里我们采用将每个成员变量单独读写的方式 示例：学生对象的文件读写操作符重载 ```cpp ofstream& operator<<(ofstream& ofs, const Student& stu) { // 先写入学号的长度，再写入学号内容，其他类似 size_t len = stu.id.size(); ofs.write((char*)&len, sizeof(len)); ofs.write(stu.id.c_str(), len); len = stu.name.size(); ofs.write((char*)&len, sizeof(len)); ofs.write(stu.name.c_str(), len); ofs.write((char*)&stu.score1, sizeof(stu.score1)); ofs.write((char*)&stu.score2, sizeof(stu.score2)); ofs.write((char*)&stu.score3, sizeof(stu.score3)); return ofs; } ifstream& operator>>(ifstream& ifs, Student& stu) { size_t len; char buffer[256]; // 读入学号 ifs.read((char*)&len, sizeof(len)); ifs.read(buffer, len); buffer[len] = '\0'; stu.id = buffer; // 读入姓名 ifs.read((char*)&len, sizeof(len)); ifs.read(buffer, len); buffer[len] = '\0'; stu.name = buffer; ifs.read((char*)&stu.score1, sizeof(stu.score1)); ifs.read((char*)&stu.score2, sizeof(stu.score2)); ifs.read((char*)&stu.score3, sizeof(stu.score3)); return ifs; } ``` 2. 用户注册登录流程： - 启动程序后，先加载用户数据 - 显示登录菜单（1.登录 2.注册） - 注册：输入用户名密码，并保存到用户文件 - 登录：验证成功后，根据角色显示主菜单 3. 模糊查询实现： ```cpp void StudentManager::fuzzySearch(string keyword) { for (auto& stu : students) { // 在学号和姓名中查找关键字 if (stu.getId().find(keyword) != string::npos || stu.getName().find(keyword) != string::npos) { // 显示该学生信息 stu.display(); } } } ``` 4. 奖学金评定： ```cpp void StudentManager::evaluateScholarship() { for (auto& stu : students) { if (stu.getAverage() >= 90 && !stu.hasFailed()) { // 该学生获得奖学金 cout << stu.getName() << " 获得奖学金" << endl; } } } ``` 五、注意事项 1. 数据验证：在添加学生时，调用isIdUnique验证学号唯一性，成绩输入后验证范围 2. 菜单循环：使用循环和switch-case实现菜单的持续显示，直到选择退出 3. 错误处理：对文件读写、输入错误等情况进行处理 由于完整代码较长，以上为关键部分实现思路和代码片段。实际开发中需要逐步完善每个函数。 现在，我们可以根据上述设计编写代码。如果需要，我可以提供某个功能模块的完整代码。</think>### C++学生管理系统新增功能实现指南 下面是在现有系统中添加所需功能的完整实现方案，包含关键代码和设计思路： --- ### 一、多级菜单系统 **实现思路**：使用状态机模式管理菜单层级 ```cpp enum MenuState { MAIN, STUDENT_MGMT, SEARCH, SCHOLARSHIP, USER_MGMT }; MenuState currentState = MAIN; void displayMenu() { switch(currentState) { case MAIN: cout << "1. 学生管理\n2. 查询系统\n3. 奖学金评定\n4. 用户管理\n0. 退出"; break; case STUDENT_MGMT: cout << "1. 添加学生\n2. 修改信息\n3. 删除学生\n9. 返回上级"; break; // 其他子菜单... } } void handleInput(int choice) { switch(currentState) { case MAIN: if(choice == 1) currentState = STUDENT_MGMT; // 其他选项处理... break; case STUDENT_MGMT: if(choice == 9) currentState = MAIN; // 其他选项处理... break; } } ``` --- ### 二、数据验证 **实现方案**：创建验证工具类 ```cpp class Validator { public: static bool validateID(const string& id) { // 学号格式验证: 年份+学院代码+序号 regex pattern(R"(^20\d{2}[A-Z]{2}\d{4}$)"); return regex_match(id, pattern); } static bool validateScore(float score) { return (score >= 0 && score <= 100); } static bool validatePassword(const string& pwd) { // 密码强度验证: 至少8位，含大小写和数字 return pwd.length() >= 8 && any_of(pwd.begin(), pwd.end(), ::isupper) && any_of(pwd.begin(), pwd.end(), ::islower) && any_of(pwd.begin(), pwd.end(), ::isdigit); } }; // 使用示例 if(!Validator::validateID(newStudent.id)) { cout << "学号格式错误! 正确格式: 2020CS0001"; } ``` --- ### 三、模糊查询 **实现方案**：使用KMP算法实现部分匹配 ```cpp vector<Student> fuzzySearch(const vector<Student>& students, const string& keyword) { vector<Student> results; for(const auto& stu : students) { // 在姓名、学号、专业中搜索 if(kmpSearch(stu.name, keyword) || kmpSearch(stu.id, keyword) || kmpSearch(stu.major, keyword)) { results.push_back(stu); } } return results; } // KMP算法实现 bool kmpSearch(const string& text, const string& pattern) { if(pattern.empty()) return true; // KMP算法实现代码... } ``` --- ### 四、奖学金评定 **实现方案**：策略模式实现不同评定规则 ```cpp class ScholarshipStrategy { public: virtual bool qualify(const Student& s) const = 0; }; class AcademicStrategy : public ScholarshipStrategy { public: bool qualify(const Student& s) const override { return s.gpa >= 3.7 && s.credits >= 40; } }; class ResearchStrategy : public ScholarshipStrategy { public: bool qualify(const Student& s) const override { return s.publications >= 2 && s.gpa >= 3.5; } }; // 使用示例 AcademicStrategy acadStrategy; vector<Student> recipients; for(const auto& s : students) { if(acadStrategy.qualify(s)) { recipients.push_back(s); } } ``` --- ### 五、用户注册登录 **实现方案**：SHA-256加密存储 ```cpp #include <openssl/sha.h> class UserManager { private: unordered_map<string, string> users; // username->hashed_pwd string hashPassword(const string& pwd) { unsigned char digest[SHA256_DIGEST_LENGTH]; SHA256((const unsigned char*)pwd.c_str(), pwd.length(), digest); char hashed[SHA256_DIGEST_LENGTH*2+1]; for(int i=0; i<SHA256_DIGEST_LENGTH; i++) sprintf(&hashed[i*2], "%02x", digest[i]); return string(hashed); } public: bool registerUser(const string& username, const string& pwd) { if(users.find(username) != users.end()) return false; // 用户已存在 users[username] = hashPassword(pwd); return true; } bool authenticate(const string& username, const string& pwd) { auto it = users.find(username); if(it == users.end()) return false; return it->second == hashPassword(pwd); } }; ``` --- ### 六、二进制文件存储 **实现方案**：直接内存读写 ```cpp struct StudentRecord { char id[12]; char name[30]; float gpa; int credits; // 其他字段... }; void saveToBinary(const vector<Student>& students, const string& filename) { ofstream out(filename, ios::binary); for(const auto& s : students) { StudentRecord rec; strncpy(rec.id, s.id.c_str(), 11); strncpy(rec.name, s.name.c_str(), 29); rec.gpa = s.gpa; rec.credits = s.credits; out.write(reinterpret_cast<char*>(&rec), sizeof(rec)); } } vector<Student> loadFromBinary(const string& filename) { vector<Student> students; ifstream in(filename, ios::binary); StudentRecord rec; while(in.read(reinterpret_cast<char*>(&rec), sizeof(rec))) { students.push_back({ string(rec.id), string(rec.name), rec.gpa, rec.credits }); } return students; } ``` --- ### 系统架构优化建议 1. **数据层抽象**：创建`DataManager`类统一处理存储 ```cpp class DataManager { public: virtual void save(const vector<Student>&) = 0; virtual vector<Student> load() = 0; }; class BinaryManager : public DataManager { /*...*/ }; class TextManager : public DataManager { /*...*/ }; ``` 2. **日志系统**：关键操作添加日志记录 ```cpp class Logger { public: static void log(const string& action, bool success) { ofstream logfile("system.log", ios::app); logfile << "[" << getCurrentTime() << "] " << action << ": " << (success ? "SUCCESS" : "FAILED") << endl; } }; ``` 3. **异常处理**：统一错误处理机制 ```cpp try { // 关键操作 } catch(const FileException& e) { cerr << "文件错误: " << e.what(); Logger::log("文件操作", false); } catch(const DBException& e) { cerr << "数据库错误: " << e.what(); } ``` --- ### 性能优化技巧 1. **内存映射文件**：处理大数据集 ```cpp void processLargeFile(const string& filename) { ifstream file(filename, ios::binary | ios::ate); size_t size = file.tellg(); file.seekg(0); char* buffer = new char[size]; file.read(buffer, size); // 直接操作内存中的buffer // ... delete[] buffer; } ``` 2. **索引优化**：为常用查询字段建立索引 ```cpp unordered_map<string, Student*> idIndex; // 学号索引 unordered_multimap<string, Student*> nameIndex; // 姓名索引 ``` 3. **查询缓存**：存储最近查询结果 ```cpp class QueryCache { private: map<string, vector<Student>> cache; const int MAX_SIZE = 100; public: vector<Student> get(const string& query) { if(cache.find(query) != cache.end()) return cache[query]; return {}; } void put(const string& query, const vector<Student>& result) { if(cache.size() >= MAX_SIZE) cache.clear(); cache[query] = result; } }; ``` --- ### 安全增强措施 1. **SQL注入防护**：使用参数化查询（若使用数据库） ```cpp // 错误方式: 拼接SQL string sql = "SELECT * FROM users WHERE name='" + name + "'"; // 正确方式: 参数化查询 sqlite3_stmt* stmt; sqlite3_prepare_v2(db, "SELECT * FROM users WHERE name=?", -1, &stmt, 0); sqlite3_bind_text(stmt, 1, name.c_str(), -1, SQLITE_STATIC); ``` 2. **密码加盐处理**： ```cpp string hashPassword(const string& pwd, const string& salt) { string combined = salt + pwd + salt; // 使用SHA-512等更强哈希算法... } ``` 3. **会话管理**： ```cpp class SessionManager { private: map<string, Session> activeSessions; // sessionID -> Session public: string createSession(const User& user) { string sessionId = generateUUID(); activeSessions[sessionId] = { user, time(nullptr) }; return sessionId; } bool validateSession(const string& sessionId) { auto it = activeSessions.find(sessionId); return it != activeSessions.end() && (time(nullptr) - it->second.createdTime < TIMEOUT); } }; ``` --- ### 部署建议 1. **跨平台支持**：使用CMake构建系统 ```cmake cmake_minimum_required(VERSION 3.10) project(StudentSystem) set(CMAKE_CXX_STANDARD 17) add_executable(main src/main.cpp src/Student.cpp src/UserManager.cpp ) target_link_libraries(main PRIVATE OpenSSL::SSL) ``` 2. **配置管理**：使用JSON配置文件 ```json { "database": { "type": "binary", "path": "data/students.dat" }, "security": { "password_policy": "strong" } } ``` 3. **单元测试**：Google Test框架示例 ```cpp TEST(ValidatorTest, ValidID) { ASSERT_TRUE(Validator::validateID("2023CS1001")); ASSERT_FALSE(Validator::validateID("2023CS100")); } TEST(ScholarshipTest, QualifyCheck) { Student s{"2023CS1001", "张三", 3.8, 42}; AcademicStrategy strategy; ASSERT_TRUE(strategy.qualify(s)); } ``` ---

<think>根据用户需求，我们需要在C语言实现的通讯录管理系统中增加多种按姓名排序的算法。用户要求保留折半查找（按学号查询），而按姓名查询需要提供多种排序方法选择。我们将添加冒泡排序、快速排序、希尔排序和归并排序四种算法。由于原始代码结构可能不同，我们将基于常见的链表结构实现通讯录系统。以下是完整的代码示例，包含：1.结构体定义2.链表基本操作（添加、删除、修改、查找等）3.多种排序算法的实现（按姓名）4.折半查找（按学号）5.文件操作（保存和加载）6.菜单交互注意：为了简化，我们假设通讯录使用单链表存储。同时，在按姓名排序时，我们先将链表转换为数组，排序后再输出，这样可以方便使用多种排序算法。完整代码如下：</think>以下是根据您的需求实现的C语言通讯录管理系统，包含多种姓名排序算法和折半查找功能的完整代码： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> // 学生结构体 typedef struct Student { int id; char name[50]; char city[50]; char phone[15]; struct Student* next; } Student; Student* head = NULL; // 链表头指针 // 函数声明 void add_student(); void display_all(); void search_by_id(); void search_by_name(); void search_by_city(); void delete_student(); void modify_student(); void save_to_file(); void load_from_file(); void free_list(); // 排序算法类型定义 typedef enum { BUBBLE_SORT, QUICK_SORT, SHELL_SORT, MERGE_SORT } SortAlgorithm; // 排序函数声明 void bubble_sort(Student** arr, int n); void quick_sort(Student** arr, int low, int high); void shell_sort(Student** arr, int n); void merge_sort(Student** arr, int l, int r); void merge(Student** arr, int l, int m, int r); void sort_and_display(SortAlgorithm algo); // 辅助函数 void print_student(Student* s); int compare_names(const char* name1, const char* name2); int main() { int choice; // 从文件加载数据 load_from_file(); printf("\n=== 同学通讯录管理系统 ===\n"); do { printf("\n1. 添加学生"); printf("\n2. 显示所有学生"); printf("\n3. 按学号查询"); printf("\n4. 按姓名查询"); printf("\n5. 按城市查询"); printf("\n6. 删除学生"); printf("\n7. 修改学生信息"); printf("\n8. 按姓名排序显示"); printf("\n9. 保存到文件"); printf("\n0. 退出"); printf("\n请选择操作: "); scanf("%d", &choice); switch(choice) { case 1: add_student(); break; case 2: display_all(); break; case 3: search_by_id(); break; case 4: search_by_name(); break; case 5: search_by_city(); break; case 6: delete_student(); break; case 7: modify_student(); break; case 8: printf("\n选择排序算法:"); printf("\n1. 冒泡排序"); printf("\n2. 快速排序"); printf("\n3. 希尔排序"); printf("\n4. 归并排序"); printf("\n请选择: "); int algo_choice; scanf("%d", &algo_choice); if (algo_choice >= 1 && algo_choice <= 4) { sort_and_display(algo_choice - 1); } else { printf("无效选择!\n"); } break; case 9: save_to_file(); break; case 0: break; default: printf("无效选择!\n"); } } while(choice != 0); // 保存数据并释放内存 save_to_file(); free_list(); return 0; } // 添加学生 void add_student() { Student* new_student = (Student*)malloc(sizeof(Student)); if (!new_student) { printf("内存分配失败!\n"); return; } printf("\n--- 添加新学生 ---\n"); printf("学号: "); scanf("%d", &new_student->id); printf("姓名: "); scanf("%s", new_student->name); printf("城市: "); scanf("%s", new_student->city); printf("电话: "); scanf("%s", new_student->phone); // 添加到链表头部 new_student->next = head; head = new_student; printf("学生添加成功!\n"); } // 显示所有学生 void display_all() { if (!head) { printf("通讯录为空!\n"); return; } printf("\n--- 所有学生信息 ---\n"); printf("%-10s %-20s %-15s %-15s\n", "学号", "姓名", "城市", "电话"); printf("------------------------------------------------\n"); Student* current = head; while (current) { printf("%-10d %-20s %-15s %-15s\n", current->id, current->name, current->city, current->phone); current = current->next; } } // 按学号查询（折半查找） void search_by_id() { if (!head) { printf("通讯录为空!\n"); return; } int id; printf("请输入学号: "); scanf("%d", &id); // 将链表转换为数组 Student* arr[1000]; int count = 0; Student* cur = head; while (cur) { arr[count++] = cur; cur = cur->next; } // 按学号排序（插入排序） for (int i = 1; i < count; i++) { Student* key = arr[i]; int j = i - 1; while (j >= 0 && arr[j]->id > key->id) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } // 折半查找 int low = 0, high = count - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid]->id == id) { printf("\n找到学生:\n"); print_student(arr[mid]); return; } if (arr[mid]->id < id) { low = mid + 1; } else { high = mid - 1; } } printf("未找到学号为 %d 的学生\n", id); } // 按姓名查询 void search_by_name() { if (!head) { printf("通讯录为空!\n"); return; } char name[50]; printf("请输入姓名(支持部分匹配): "); scanf("%s", name); Student* current = head; int found = 0; printf("\n--- 查询结果 ---\n"); printf("%-10s %-20s %-15s %-15s\n", "学号", "姓名", "城市", "电话"); printf("------------------------------------------------\n"); while (current) { if (strstr(current->name, name) != NULL) { printf("%-10d %-20s %-15s %-15s\n", current->id, current->name, current->city, current->phone); found = 1; } current = current->next; } if (!found) { printf("未找到姓名包含 \"%s\" 的学生\n", name); } } // 按城市查询 void search_by_city() { if (!head) { printf("通讯录为空!\n"); return; } char city[50]; printf("请输入城市: "); scanf("%s", city); Student* current = head; int found = 0; printf("\n--- 查询结果 ---\n"); printf("%-10s %-20s %-15s %-15s\n", "学号", "姓名", "城市", "电话"); printf("------------------------------------------------\n"); while (current) { if (strcmp(current->city, city) == 0) { printf("%-10d %-20s %-15s %-15s\n", current->id, current->name, current->city, current->phone); found = 1; } current = current->next; } if (!found) { printf("未找到城市为 \"%s\" 的学生\n", city); } } // 删除学生 void delete_student() { if (!head) { printf("通讯录为空!\n"); return; } int id; printf("请输入要删除学生的学号: "); scanf("%d", &id); Student* current = head; Student* prev = NULL; while (current) { if (current->id == id) { if (prev) { prev->next = current->next; } else { head = current->next; } free(current); printf("学生删除成功!\n"); return; } prev = current; current = current->next; } printf("未找到学号为 %d 的学生\n", id); } // 修改学生信息 void modify_student() { if (!head) { printf("通讯录为空!\n"); return; } int id; printf("请输入要修改学生的学号: "); scanf("%d", &id); Student* current = head; while (current) { if (current->id == id) { printf("\n当前信息:\n"); print_student(current); printf("\n输入新信息(留空则保持原值):\n"); char input[50]; printf("新姓名: "); getchar(); // 清除输入缓冲区 fgets(input, 50, stdin); if (strlen(input) > 1) { input[strcspn(input, "\n")] = '\0'; strcpy(current->name, input); } printf("新城市: "); fgets(input, 50, stdin); if (strlen(input) > 1) { input[strcspn(input, "\n")] = '\0'; strcpy(current->city, input); } printf("新电话: "); fgets(input, 50, stdin); if (strlen(input) > 1) { input[strcspn(input, "\n")] = '\0'; strcpy(current->phone, input); } printf("信息修改成功!\n"); return; } current = current->next; } printf("未找到学号为 %d 的学生\n", id); } // 保存到文件 void save_to_file() { FILE* file = fopen("students.dat", "wb"); if (!file) { printf("无法打开文件!\n"); return; } Student* current = head; while (current) { fwrite(current, sizeof(Student), 1, file); current = current->next; } fclose(file); printf("数据已保存到文件!\n"); } // 从文件加载 void load_from_file() { FILE* file = fopen("students.dat", "rb"); if (!file) { printf("无数据文件，将创建新通讯录\n"); return; } Student temp; while (fread(&temp, sizeof(Student), 1, file)) { Student* new_student = (Student*)malloc(sizeof(Student)); if (!new_student) { printf("内存分配失败!\n"); fclose(file); return; } *new_student = temp; new_student->next = head; head = new_student; } fclose(file); printf("数据已从文件加载!\n"); } // 释放链表内存 void free_list() { Student* current = head; while (current) { Student* next = current->next; free(current); current = next; } head = NULL; } // 打印学生信息 void print_student(Student* s) { printf("%-10s %-20s %-15s %-15s\n", "学号", "姓名", "城市", "电话"); printf("------------------------------------------------\n"); printf("%-10d %-20s %-15s %-15s\n", s->id, s->name, s->city, s->phone); } // 比较两个姓名（不区分大小写） int compare_names(const char* name1, const char* name2) { while (*name1 && *name2) { int diff = tolower((unsigned char)*name1) - tolower((unsigned char)*name2); if (diff != 0) return diff; name1++; name2++; } return tolower((unsigned char)*name1) - tolower((unsigned char)*name2); } // ================ 排序算法实现 ================ // 冒泡排序（按姓名） void bubble_sort(Student** arr, int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (compare_names(arr[j]->name, arr[j + 1]->name) > 0) { Student* temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } // 快速排序（按姓名） void quick_sort(Student** arr, int low, int high) { if (low < high) { // 选择中间元素作为基准 int mid = low + (high - low) / 2; const char* pivot = arr[mid]->name; int i = low - 1; int j = high + 1; while (1) { do { i++; } while (compare_names(arr[i]->name, pivot) < 0); do { j--; } while (compare_names(arr[j]->name, pivot) > 0); if (i >= j) break; Student* temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } quick_sort(arr, low, j); quick_sort(arr, j + 1, high); } } // 希尔排序（按姓名） void shell_sort(Student** arr, int n) { // 使用Knuth序列计算间隔 int gap = 1; while (gap < n / 3) { gap = gap * 3 + 1; } while (gap > 0) { for (int i = gap; i < n; i++) { Student* temp = arr[i]; int j; for (j = i; j >= gap && compare_names(arr[j - gap]->name, temp->name) > 0; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } gap /= 3; } } // 归并排序辅助函数 void merge(Student** arr, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; // 创建临时数组 Student** L = (Student**)malloc(n1 * sizeof(Student*)); Student** R = (Student**)malloc(n2 * sizeof(Student*)); // 复制数据到临时数组 for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; // 合并临时数组 int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (compare_names(L[i]->name, R[j]->name) <= 0) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } // 复制剩余元素 while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; // 释放临时数组 free(L); free(R); } // 归并排序（按姓名） void merge_sort(Student** arr, int l, int r) { if (l < r) { int m = l + (r - l) / 2; merge_sort(arr, l, m); merge_sort(arr, m + 1, r); merge(arr, l, m, r); } } // 排序并显示结果 void sort_and_display(SortAlgorithm algo) { if (!head) { printf("通讯录为空!\n"); return; } // 统计学生数量 int count = 0; Student* current = head; while (current) { count++; current = current->next; } // 创建学生指针数组 Student** arr = (Student**)malloc(count * sizeof(Student*)); if (!arr) { printf("内存分配失败!\n"); return; } // 填充数组 current = head; for (int i = 0; i < count; i++) { arr[i] = current; current = current->next; } // 应用选择的排序算法 switch (algo) { case BUBBLE_SORT: bubble_sort(arr, count); printf("\n使用冒泡排序结果:\n"); break; case QUICK_SORT: quick_sort(arr, 0, count - 1); printf("\n使用快速排序结果:\n"); break; case SHELL_SORT: shell_sort(arr, count); printf("\n使用希尔排序结果:\n"); break; case MERGE_SORT: merge_sort(arr, 0, count - 1); printf("\n使用归并排序结果:\n"); break; } // 显示排序结果 printf("\n--- 按姓名排序的学生列表 ---\n"); printf("%-10s %-20s %-15s %-15s\n", "学号", "姓名", "城市", "电话"); printf("------------------------------------------------\n"); for (int i = 0; i < count; i++) { printf("%-10d %-20s %-15s %-15s\n", arr[i]->id, arr[i]->name, arr[i]->city, arr[i]->phone); } free(arr); } ``` ### 功能说明 1. **数据结构**： - 使用链表存储学生信息 - 学生结构体包含学号、姓名、城市和电话 2. **核心功能**： - 添加/删除/修改学生信息 - 显示所有学生 - 文件存储与加载 - 按学号、姓名、城市查询 3. **排序算法实现**： - **冒泡排序**：简单稳定，适合小数据集 - **快速排序**：平均性能最优($O(n \log n)$)，适合通用场景 - **希尔排序**：插入排序改进版，中等规模高效 - **归并排序**：稳定排序($O(n \log n)$)，适合大规模数据 4. **折半查找**： - 按学号查询时使用折半查找算法 - 先将链表转换为有序数组再查找 5. **特色功能**： - 姓名比较不区分大小写 - 文件持久化存储 - 用户友好的菜单界面 - 内存管理完善 ### 算法性能对比 | 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 适用场景 | |----------|----------------|----------------|------------|----------| | **冒泡排序** | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 小数据集，实现简单[^1] | | **快速排序** | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | 通用排序，大数据集首选[^2] | | **希尔排序** | $O(n \log n)$ | $O(n^2)$ | $O(1)$ | 中等数据集，插入排序优化[^3] | | **归并排序** | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | 稳定排序，链表数据结构 | ### 使用示例 ```c // 编译并运行程序 gcc -o address_book address_book.c ./address_book // 操作示例： 1. 添加学生 2. 选择排序算法（如快速排序） 3. 按姓名排序显示 4. 按学号查询（使用折半查找） ``` 此实现满足您的需求，保留了折半查找功能，并为按姓名排序添加了多种排序算法选项，同时保持了代码的可读性和实用性。